Implementation of delta-sync support on client-side.

This commit adds client-side support for delta-sync, this adds a new
3rdparty submodule `gh:ahmedammar/zsync`. This zsync tree is a modified
version of upstream, adding some needed support for the upload path and
other requirements.

If the server does not announce the required zsync capability then a
full upload/download is fallen back to. Delta synchronization can be
enabled/disabled using command line, config, or gui options.

On both upload and download paths, a check is made for the existance of
a zsync metadata file on the server for a given path. This is provided
by a dav property called `zsync`, found during discovery phase. If it
doesn't exist the code reverts back to a complete upload or download,
i.e. previous implementations. In the case of upload, a new zsync
metadata file will be uploaded as part of the chunked upload and future
synchronizations will be delta-sync capable.

Chunked uploads no longer use sequential file names for each chunk id,
instead, they are named as the byte offset into the remote file, this is
a minimally intrusive modification to allow fo delta-sync and legacy
code paths to run seamlessly. A new http header OC-Total-File-Length is
sent, which informs the server of the final expected size of the file
not just the total transmitted bytes as reported by OC-Total-Length.

The seeding and generation of the zsync metadata file is done in a
separate thread since this is a cpu intensive task, ensuring main thread
is not blocked.

This commit closes owncloud/client#179.

3 files changed, 380 insertions, 11 deletions

diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index b23678543..619811c75 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -1,6 +1,7 @@
 include_directories(${QT_INCLUDES}
                     ${CMAKE_SOURCE_DIR}/src
                     ${CMAKE_SOURCE_DIR}/src/3rdparty/qtokenizer
+                    ${CMAKE_SOURCE_DIR}/src/3rdparty/zsync/c
                     ${CMAKE_SOURCE_DIR}/src/csync
                     ${CMAKE_SOURCE_DIR}/src/csync/std
                     ${CMAKE_SOURCE_DIR}/src/gui
@@ -50,6 +51,7 @@ owncloud_add_test(SyncMove "syncenginetestutils.h")
 owncloud_add_test(SyncConflict "syncenginetestutils.h")
 owncloud_add_test(SyncFileStatusTracker "syncenginetestutils.h")
 owncloud_add_test(ChunkingNg "syncenginetestutils.h")
+owncloud_add_test(Zsync "syncenginetestutils.h")
 owncloud_add_test(UploadReset "syncenginetestutils.h")
 owncloud_add_test(AllFilesDeleted "syncenginetestutils.h")
 owncloud_add_test(FolderWatcher "${FolderWatcher_SRC}")
diff --git a/test/syncenginetestutils.h b/test/syncenginetestutils.h
index f7cf4eb46..ea9939fea 100644
--- a/test/syncenginetestutils.h
+++ b/test/syncenginetestutils.h
@@ -12,6 +12,7 @@
 #include "filesystem.h"
 #include "syncengine.h"
 #include "common/syncjournaldb.h"
+#include <cstring>
 
 #include <QDir>
 #include <QNetworkReply>
@@ -68,7 +69,8 @@ public:
     virtual void remove(const QString &relativePath) = 0;
     virtual void insert(const QString &relativePath, qint64 size = 64, char contentChar = 'W') = 0;
     virtual void setContents(const QString &relativePath, char contentChar) = 0;
-    virtual void appendByte(const QString &relativePath) = 0;
+    virtual void appendByte(const QString &relativePath, char contentChar = 0) = 0;
+    virtual void modifyByte(const QString &relativePath, quint64 offset, char contentChar) = 0;
     virtual void mkdir(const QString &relativePath) = 0;
     virtual void rename(const QString &relativePath, const QString &relativeDestinationDirectory) = 0;
     virtual void setModTime(const QString &relativePath, const QDateTime &modTime) = 0;
@@ -107,14 +109,29 @@ public:
         file.open(QFile::WriteOnly);
         file.write(QByteArray{}.fill(contentChar, size));
     }
-    void appendByte(const QString &relativePath) override {
+    void appendByte(const QString &relativePath, char contentChar) override
+    {
         QFile file{_rootDir.filePath(relativePath)};
         QVERIFY(file.exists());
         file.open(QFile::ReadWrite);
-        QByteArray contents = file.read(1);
+        QByteArray contents;
+        if (contentChar)
+            contents += contentChar;
+        else
+            contents = file.read(1);
         file.seek(file.size());
         file.write(contents);
     }
+    void modifyByte(const QString &relativePath, quint64 offset, char contentChar) override
+    {
+        QFile file{ _rootDir.filePath(relativePath) };
+        QVERIFY(file.exists());
+        file.open(QFile::ReadWrite);
+        file.seek(offset);
+        file.write(&contentChar, 1);
+        file.close();
+    }
+
     void mkdir(const QString &relativePath) override {
         _rootDir.mkpath(relativePath);
     }
@@ -190,12 +207,23 @@ public:
         file->contentChar = contentChar;
     }
 
-    void appendByte(const QString &relativePath) override {
+    void appendByte(const QString &relativePath, char contentChar = 0) override
+    {
+        Q_UNUSED(contentChar);
         FileInfo *file = findInvalidatingEtags(relativePath);
         Q_ASSERT(file);
         file->size += 1;
     }
 
+    void modifyByte(const QString &relativePath, quint64 offset, char contentChar) override
+    {
+        Q_UNUSED(offset);
+        Q_UNUSED(contentChar);
+        FileInfo *file = findInvalidatingEtags(relativePath);
+        Q_ASSERT(file);
+        Q_ASSERT(!"unimplemented");
+    }
+
     void mkdir(const QString &relativePath) override {
         createDir(relativePath);
     }
@@ -365,6 +393,7 @@ public:
             xml.writeTextElement(ocUri, QStringLiteral("permissions"), fileInfo.isShared ? QStringLiteral("SRDNVCKW") : QStringLiteral("RDNVCKW"));
             xml.writeTextElement(ocUri, QStringLiteral("id"), fileInfo.fileId);
             xml.writeTextElement(ocUri, QStringLiteral("checksums"), fileInfo.checksums);
+            xml.writeTextElement(ocUri, QStringLiteral("zsync"), QStringLiteral("true"));
             buffer.write(fileInfo.extraDavProperties);
             xml.writeEndElement(); // prop
             xml.writeTextElement(davUri, QStringLiteral("status"), "HTTP/1.1 200 OK");
@@ -593,6 +622,7 @@ public:
     }
 
     void abort() override {
+        setError(OperationCanceledError, "Operation Canceled");
         aborted = true;
     }
     qint64 bytesAvailable() const override {
@@ -612,6 +642,87 @@ public:
     using QNetworkReply::setRawHeader;
 };
 
+class FakeGetWithDataReply : public QNetworkReply
+{
+    Q_OBJECT
+public:
+    const FileInfo *fileInfo;
+    const char *payload;
+    quint64 size;
+    quint64 offset = 0;
+    bool aborted = false;
+
+    FakeGetWithDataReply(FileInfo &remoteRootFileInfo, const QByteArray &data, QNetworkAccessManager::Operation op, const QNetworkRequest &request, QObject *parent)
+        : QNetworkReply{ parent }
+    {
+        setRequest(request);
+        setUrl(request.url());
+        setOperation(op);
+        open(QIODevice::ReadOnly);
+
+        Q_ASSERT(!data.isEmpty());
+        payload = data.data();
+        size = data.length();
+        QString fileName = getFilePathFromUrl(request.url());
+        Q_ASSERT(!fileName.isEmpty());
+        fileInfo = remoteRootFileInfo.find(fileName);
+        QMetaObject::invokeMethod(this, "respond", Qt::QueuedConnection);
+
+        if (request.hasRawHeader("Range")) {
+            QByteArray range = request.rawHeader("Range");
+            quint64 start, end;
+            const char *r = range.constData();
+            int res = sscanf(r, "bytes=%llu-%llu", &start, &end);
+            if (res == 2) {
+                payload += start;
+                size -= start;
+            }
+        }
+    }
+
+    Q_INVOKABLE void respond()
+    {
+        if (aborted) {
+            setError(OperationCanceledError, "Operation Canceled");
+            emit metaDataChanged();
+            emit finished();
+            return;
+        }
+        setHeader(QNetworkRequest::ContentLengthHeader, size);
+        setAttribute(QNetworkRequest::HttpStatusCodeAttribute, 200);
+        setRawHeader("OC-ETag", fileInfo->etag.toLatin1());
+        setRawHeader("ETag", fileInfo->etag.toLatin1());
+        setRawHeader("OC-FileId", fileInfo->fileId);
+        emit metaDataChanged();
+        if (bytesAvailable())
+            emit readyRead();
+        emit finished();
+    }
+
+    void abort() override
+    {
+        setError(OperationCanceledError, "Operation Canceled");
+        aborted = true;
+    }
+    qint64 bytesAvailable() const override
+    {
+        if (aborted)
+            return 0;
+        return size + QIODevice::bytesAvailable();
+    }
+
+    qint64 readData(char *data, qint64 maxlen) override
+    {
+        qint64 len = std::min(size, quint64(maxlen));
+        std::memcpy(data, payload + offset, len);
+        size -= len;
+        offset += len;
+        return len;
+    }
+
+    // useful to be public for testing
+    using QNetworkReply::setRawHeader;
+};
 
 class FakeChunkMoveReply : public QNetworkReply
 {
@@ -630,27 +741,36 @@ public:
 
         QString source = getFilePathFromUrl(request.url());
         Q_ASSERT(!source.isEmpty());
-        Q_ASSERT(source.endsWith("/.file"));
-        source = source.left(source.length() - qstrlen("/.file"));
+        Q_ASSERT(source.endsWith("/.file") || source.endsWith("/.file.zsync"));
+        if (source.endsWith("/.file"))
+            source = source.left(source.length() - qstrlen("/.file"));
+        if (source.endsWith("/.file.zsync"))
+            source = source.left(source.length() - qstrlen("/.file.zsync"));
         auto sourceFolder = uploadsFileInfo.find(source);
         Q_ASSERT(sourceFolder);
         Q_ASSERT(sourceFolder->isDir);
         int count = 0;
         int size = 0;
+        qlonglong prev = 0;
         char payload = '\0';
 
-        do {
-            QString chunkName = QString::number(count).rightJustified(8, '0');
-            if (!sourceFolder->children.contains(chunkName))
-                break;
+
+        // Ignore .zsync metadata
+        if (sourceFolder->children.contains(".zsync"))
+            sourceFolder->children.remove(".zsync");
+
+        for (auto chunkName : sourceFolder->children.keys()) {
             auto &x = sourceFolder->children[chunkName];
+            if (chunkName.toLongLong() != prev)
+                break;
             Q_ASSERT(!x.isDir);
             Q_ASSERT(x.size > 0); // There should not be empty chunks
             size += x.size;
             Q_ASSERT(!payload || payload == x.contentChar);
             payload = x.contentChar;
             ++count;
-        } while(true);
+            prev = chunkName.toLongLong() + x.size;
+        }
 
         Q_ASSERT(count > 1); // There should be at least two chunks, otherwise why would we use chunking?
         QCOMPARE(sourceFolder->children.count(), count); // There should not be holes or extra files
@@ -709,6 +829,97 @@ public:
     qint64 readData(char *, qint64) override { return 0; }
 };
 
+class FakeChunkZsyncMoveReply : public QNetworkReply
+{
+    Q_OBJECT
+    FileInfo *fileInfo;
+
+public:
+    FakeChunkZsyncMoveReply(FileInfo &uploadsFileInfo, FileInfo &remoteRootFileInfo,
+        QNetworkAccessManager::Operation op, const QNetworkRequest &request,
+        quint64 delayMs, QVector<quint64> &mods, QObject *parent)
+        : QNetworkReply{ parent }
+    {
+        setRequest(request);
+        setUrl(request.url());
+        setOperation(op);
+        open(QIODevice::ReadOnly);
+
+        Q_ASSERT(!mods.isEmpty());
+
+        QString source = getFilePathFromUrl(request.url());
+        Q_ASSERT(!source.isEmpty());
+        Q_ASSERT(source.endsWith("/.file.zsync"));
+        source = source.left(source.length() - qstrlen("/.file.zsync"));
+        auto sourceFolder = uploadsFileInfo.find(source);
+        Q_ASSERT(sourceFolder);
+        Q_ASSERT(sourceFolder->isDir);
+        int count = 0;
+
+        // Ignore .zsync metadata
+        if (sourceFolder->children.contains(".zsync"))
+            sourceFolder->children.remove(".zsync");
+
+        for (auto chunkName : sourceFolder->children.keys()) {
+            auto &x = sourceFolder->children[chunkName];
+            Q_ASSERT(!x.isDir);
+            Q_ASSERT(x.size > 0); // There should not be empty chunks
+            quint64 start = quint64(chunkName.toLongLong());
+            auto it = mods.begin();
+            while (it != mods.end()) {
+                if (*it >= start && *it < start + x.size) {
+                    ++count;
+                    mods.erase(it);
+                } else
+                    ++it;
+            }
+        }
+
+        Q_ASSERT(count > 0); // There should be at least one chunk
+        Q_ASSERT(mods.isEmpty()); // All files should match a modification
+
+        QString fileName = getFilePathFromUrl(QUrl::fromEncoded(request.rawHeader("Destination")));
+        Q_ASSERT(!fileName.isEmpty());
+
+        Q_ASSERT((fileInfo = remoteRootFileInfo.find(fileName)));
+
+        QVERIFY(request.hasRawHeader("If")); // The client should put this header
+        if (request.rawHeader("If") != QByteArray("<" + request.rawHeader("Destination") + "> ([\"" + fileInfo->etag.toLatin1() + "\"])")) {
+            QMetaObject::invokeMethod(this, "respondPreconditionFailed", Qt::QueuedConnection);
+            return;
+        }
+
+        if (!fileInfo) {
+            abort();
+            return;
+        }
+        fileInfo->lastModified = OCC::Utility::qDateTimeFromTime_t(request.rawHeader("X-OC-Mtime").toLongLong());
+        remoteRootFileInfo.find(fileName, /*invalidate_etags=*/true);
+
+        QTimer::singleShot(delayMs, this, &FakeChunkZsyncMoveReply::respond);
+    }
+
+    Q_INVOKABLE void respond()
+    {
+        setAttribute(QNetworkRequest::HttpStatusCodeAttribute, 201);
+        setRawHeader("OC-ETag", fileInfo->etag.toLatin1());
+        setRawHeader("ETag", fileInfo->etag.toLatin1());
+        setRawHeader("OC-FileId", fileInfo->fileId);
+        emit metaDataChanged();
+        emit finished();
+    }
+
+    Q_INVOKABLE void respondPreconditionFailed()
+    {
+        setAttribute(QNetworkRequest::HttpStatusCodeAttribute, 412);
+        setError(InternalServerError, "Precondition Failed");
+        emit metaDataChanged();
+        emit finished();
+    }
+
+    void abort() override {}
+    qint64 readData(char *, qint64) override { return 0; }
+};
 
 class FakeErrorReply : public QNetworkReply
 {
diff --git a/test/testzsync.cpp b/test/testzsync.cpp
new file mode 100644
index 000000000..f9c76ca84
--- /dev/null
+++ b/test/testzsync.cpp
@@ -0,0 +1,156 @@
+/*
+ *    This software is in the public domain, furnished "as is", without technical
+ *    support, and with no warranty, express or implied, as to its usefulness for
+ *    any purpose.
+ *
+ */
+
+#include <QtTest>
+#include "syncenginetestutils.h"
+#include <syncengine.h>
+#include <propagatecommonzsync.h>
+
+using namespace OCC;
+
+QStringList findConflicts(const FileInfo &dir)
+{
+    QStringList conflicts;
+    for (const auto &item : dir.children) {
+        if (item.name.contains("conflict")) {
+            conflicts.append(item.path());
+        }
+    }
+    return conflicts;
+}
+
+static quint64 blockstart_from_offset(quint64 offset)
+{
+    return offset & ~quint64(ZSYNC_BLOCKSIZE - 1);
+}
+
+class TestZsync : public QObject
+{
+    Q_OBJECT
+
+private slots:
+
+    void testFileDownloadSimple()
+    {
+        FakeFolder fakeFolder{ FileInfo::A12_B12_C12_S12() };
+        fakeFolder.syncEngine().account()->setCapabilities({ { "dav", QVariantMap{ { "chunking", "1.0" }, { "zsync", "1.0" } } } });
+
+        SyncOptions opt;
+        opt._deltaSyncEnabled = true;
+        opt._deltaSyncMinFileSize = 0;
+        fakeFolder.syncEngine().setSyncOptions(opt);
+
+        const int size = 100 * 1000 * 1000;
+        QByteArray metadata;
+
+        // Test 1: NEW file upload with zsync metadata
+        fakeFolder.localModifier().insert("A/a0", size);
+        fakeFolder.localModifier().appendByte("A/a0", 'X');
+        qsrand(QDateTime::currentDateTime().toTime_t());
+        for (int i = 0; i < 10; i++) {
+            quint64 offset = qrand() % size;
+            fakeFolder.localModifier().modifyByte("A/a0", offset, 'Y');
+        }
+        fakeFolder.setServerOverride([&](QNetworkAccessManager::Operation op, const QNetworkRequest &request, QIODevice *data) -> QNetworkReply * {
+            if (op == QNetworkAccessManager::PutOperation && request.url().toString().endsWith(".zsync")) {
+                metadata = data->readAll();
+                return new FakePutReply{ fakeFolder.uploadState(), op, request, metadata, this };
+            }
+
+            return nullptr;
+        });
+        QVERIFY(fakeFolder.syncOnce());
+        QCOMPARE(fakeFolder.currentLocalState(), fakeFolder.currentRemoteState());
+
+        // Keep hold of original file contents
+        QFile f(fakeFolder.localPath() + "/A/a0");
+        f.open(QIODevice::ReadOnly);
+        QByteArray data = f.readAll();
+        f.close();
+
+        // Test 2: update local file to unchanged version and download changes
+        fakeFolder.localModifier().remove("A/a0");
+        fakeFolder.localModifier().insert("A/a0", size);
+        auto currentMtime = QDateTime::currentDateTimeUtc();
+        fakeFolder.remoteModifier().setModTime("A/a0", currentMtime);
+        fakeFolder.setServerOverride([&](QNetworkAccessManager::Operation op, const QNetworkRequest &request, QIODevice *) -> QNetworkReply * {
+            QUrlQuery query(request.url());
+            if (op == QNetworkAccessManager::GetOperation) {
+                if (query.hasQueryItem("zsync")) {
+                    return new FakeGetWithDataReply{ fakeFolder.remoteModifier(), metadata, op, request, this };
+                }
+
+                return new FakeGetWithDataReply{ fakeFolder.remoteModifier(), data, op, request, this };
+            }
+
+            return nullptr;
+        });
+        QVERIFY(fakeFolder.syncOnce());
+        auto conflicts = findConflicts(fakeFolder.currentLocalState().children["A"]);
+        QCOMPARE(conflicts.size(), 1);
+        for (auto c : conflicts) {
+            fakeFolder.localModifier().remove(c);
+        }
+        QCOMPARE(fakeFolder.currentLocalState(), fakeFolder.currentRemoteState());
+    }
+
+    void testFileUploadSimple()
+    {
+        FakeFolder fakeFolder{ FileInfo::A12_B12_C12_S12() };
+        fakeFolder.syncEngine().account()->setCapabilities({ { "dav", QVariantMap{ { "chunking", "1.0" }, { "zsync", "1.0" } } } });
+
+        SyncOptions opt;
+        opt._deltaSyncEnabled = true;
+        opt._deltaSyncMinFileSize = 0;
+        fakeFolder.syncEngine().setSyncOptions(opt);
+
+        const int size = 100 * 1000 * 1000;
+        QByteArray metadata;
+
+        // Test 1: NEW file upload with zsync metadata
+        fakeFolder.localModifier().insert("A/a0", size);
+        fakeFolder.setServerOverride([&](QNetworkAccessManager::Operation op, const QNetworkRequest &request, QIODevice *data) -> QNetworkReply * {
+            if (op == QNetworkAccessManager::PutOperation && request.url().toString().endsWith(".zsync")) {
+                metadata = data->readAll();
+                return new FakePutReply{ fakeFolder.uploadState(), op, request, metadata, this };
+            }
+
+            return nullptr;
+        });
+        QVERIFY(fakeFolder.syncOnce());
+        QCOMPARE(fakeFolder.currentLocalState(), fakeFolder.currentRemoteState());
+
+        // Test 2: Modify local contents and ensure that modified chunks are sent
+        QVector<quint64> mods;
+        qsrand(QDateTime::currentDateTime().toTime_t());
+        fakeFolder.localModifier().appendByte("A/a0", 'X');
+        mods.append(blockstart_from_offset(size + 1));
+        for (int i = 0; i < 10; i++) {
+            quint64 offset = qrand() % size;
+            fakeFolder.localModifier().modifyByte("A/a0", offset, 'Y');
+            mods.append(blockstart_from_offset(offset));
+        }
+        fakeFolder.setServerOverride([&](QNetworkAccessManager::Operation op, const QNetworkRequest &request, QIODevice *) -> QNetworkReply * {
+            QUrlQuery query(request.url());
+            if (op == QNetworkAccessManager::GetOperation && query.hasQueryItem("zsync")) {
+                return new FakeGetWithDataReply{ fakeFolder.remoteModifier(), metadata, op, request, this };
+            }
+
+            if (request.attribute(QNetworkRequest::CustomVerbAttribute) == QLatin1String("MOVE")) {
+                return new FakeChunkZsyncMoveReply{ fakeFolder.uploadState(), fakeFolder.remoteModifier(), op, request, 0, mods, this };
+            }
+
+            return nullptr;
+        });
+        QVERIFY(fakeFolder.syncOnce());
+        fakeFolder.remoteModifier().appendByte("A/a0", 'X');
+        QCOMPARE(fakeFolder.currentLocalState(), fakeFolder.currentRemoteState());
+    }
+};
+
+QTEST_GUILESS_MAIN(TestZsync)
+#include "testzsync.moc"