Network Cache: Add thread-safe accessors for storage paths
[WebKit-https.git] / Source / WebKit2 / NetworkProcess / cache / NetworkCacheStorage.cpp
index b023f2b..10fd155 100644 (file)
@@ -43,6 +43,11 @@ namespace NetworkCache {
 
 static const char networkCacheSubdirectory[] = "WebKitCache";
 static const char versionDirectoryPrefix[] = "Version ";
+static const char recordsDirectoryName[] = "Records";
+static const char blobsDirectoryName[] = "Blobs";
+static const char bodyPostfix[] = "-body";
+
+static double computeRecordWorth(FileTimes);
 
 std::unique_ptr<Storage> Storage::open(const String& cachePath)
 {
@@ -60,41 +65,115 @@ static String makeVersionedDirectoryPath(const String& baseDirectoryPath)
     return WebCore::pathByAppendingComponent(baseDirectoryPath, versionSubdirectory);
 }
 
+static String makeRecordsDirectoryPath(const String& baseDirectoryPath)
+{
+    return WebCore::pathByAppendingComponent(makeVersionedDirectoryPath(baseDirectoryPath), recordsDirectoryName);
+}
+
+static String makeBlobDirectoryPath(const String& baseDirectoryPath)
+{
+    return WebCore::pathByAppendingComponent(makeVersionedDirectoryPath(baseDirectoryPath), blobsDirectoryName);
+}
+
 Storage::Storage(const String& baseDirectoryPath)
-    : m_baseDirectoryPath(baseDirectoryPath)
-    , m_directoryPath(makeVersionedDirectoryPath(baseDirectoryPath))
+    : m_basePath(baseDirectoryPath)
+    , m_recordsPath(makeRecordsDirectoryPath(baseDirectoryPath))
     , m_ioQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage", WorkQueue::Type::Concurrent))
-    , m_backgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage", WorkQueue::Type::Concurrent, WorkQueue::QOS::Background))
+    , m_backgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.background", WorkQueue::Type::Concurrent, WorkQueue::QOS::Background))
+    , m_serialBackgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.serialBackground", WorkQueue::Type::Serial, WorkQueue::QOS::Background))
+    , m_blobStorage(makeBlobDirectoryPath(baseDirectoryPath))
 {
     deleteOldVersions();
-    initialize();
+    synchronize();
+}
+
+
+String Storage::basePath() const
+{
+    return m_basePath.isolatedCopy();
+}
+
+String Storage::versionPath() const
+{
+    return makeVersionedDirectoryPath(basePath());
+}
+
+String Storage::recordsPath() const
+{
+    return m_recordsPath.isolatedCopy();
+}
+
+size_t Storage::approximateSize() const
+{
+    return m_approximateSize + m_blobStorage.approximateSize();
 }
 
-void Storage::initialize()
+void Storage::synchronize()
 {
     ASSERT(RunLoop::isMain());
 
-    StringCapture cachePathCapture(m_directoryPath);
+    if (m_synchronizationInProgress || m_shrinkInProgress)
+        return;
+    m_synchronizationInProgress = true;
+
+    LOG(NetworkCacheStorage, "(NetworkProcess) synchronizing cache");
 
-    backgroundIOQueue().dispatch([this, cachePathCapture] {
-        String cachePath = cachePathCapture.string();
-        traverseCacheFiles(cachePath, [this](const String& fileName, const String& partitionPath) {
+    backgroundIOQueue().dispatch([this] {
+        auto filter = std::make_unique<ContentsFilter>();
+        size_t size = 0;
+        unsigned count = 0;
+        traverseCacheFiles(recordsPath(), [&filter, &size, &count](const String& fileName, const String& partitionPath) {
             Key::HashType hash;
             if (!Key::stringToHash(fileName, hash))
                 return;
-            unsigned shortHash = Key::toShortHash(hash);
-            RunLoop::main().dispatch([this, shortHash] {
-                m_contentsFilter.add(shortHash);
-            });
             auto filePath = WebCore::pathByAppendingComponent(partitionPath, fileName);
             long long fileSize = 0;
             WebCore::getFileSize(filePath, fileSize);
-            m_approximateSize += fileSize;
+            if (!fileSize)
+                return;
+            filter->add(hash);
+            size += fileSize;
+            ++count;
         });
+
+        auto* filterPtr = filter.release();
+        RunLoop::main().dispatch([this, filterPtr, size] {
+            auto filter = std::unique_ptr<ContentsFilter>(filterPtr);
+
+            for (auto hash : m_contentsFilterHashesAddedDuringSynchronization)
+                filter->add(hash);
+            m_contentsFilterHashesAddedDuringSynchronization.clear();
+
+            m_contentsFilter = WTF::move(filter);
+            m_approximateSize = size;
+            m_synchronizationInProgress = false;
+        });
+
+        m_blobStorage.synchronize();
+
+        LOG(NetworkCacheStorage, "(NetworkProcess) cache synchronization completed size=%zu count=%d", size, count);
     });
 }
 
-static String directoryPathForKey(const Key& key, const String& cachePath)
+void Storage::addToContentsFilter(const Key& key)
+{
+    ASSERT(RunLoop::isMain());
+
+    if (m_contentsFilter)
+        m_contentsFilter->add(key.hash());
+
+    // If we get new entries during filter synchronization take care to add them to the new filter as well.
+    if (m_synchronizationInProgress)
+        m_contentsFilterHashesAddedDuringSynchronization.append(key.hash());
+}
+
+bool Storage::mayContain(const Key& key) const
+{
+    ASSERT(RunLoop::isMain());
+    return !m_contentsFilter || m_contentsFilter->mayContain(key.hash());
+}
+
+static String partitionPathForKey(const Key& key, const String& cachePath)
 {
     ASSERT(!key.partition().isEmpty());
     return WebCore::pathByAppendingComponent(cachePath, key.partition());
@@ -105,18 +184,19 @@ static String fileNameForKey(const Key& key)
     return key.hashAsString();
 }
 
-static String filePathForKey(const Key& key, const String& cachePath)
+static String recordPathForKey(const Key& key, const String& cachePath)
+{
+    return WebCore::pathByAppendingComponent(partitionPathForKey(key, cachePath), fileNameForKey(key));
+}
+
+static String bodyPathForRecordPath(const String& recordPath)
 {
-    return WebCore::pathByAppendingComponent(directoryPathForKey(key, cachePath), fileNameForKey(key));
+    return recordPath + bodyPostfix;
 }
 
-static Ref<IOChannel> openFileForKey(const Key& key, IOChannel::Type type, const String& cachePath)
+static String bodyPathForKey(const Key& key, const String& cachePath)
 {
-    auto directoryPath = directoryPathForKey(key, cachePath);
-    auto filePath = WebCore::pathByAppendingComponent(directoryPath, fileNameForKey(key));
-    if (type == IOChannel::Type::Create)
-        WebCore::makeAllDirectories(directoryPath);
-    return IOChannel::open(filePath, type);
+    return bodyPathForRecordPath(recordPathForKey(key, cachePath));
 }
 
 static unsigned hashData(const Data& data)
@@ -129,25 +209,25 @@ static unsigned hashData(const Data& data)
     return hasher.hash();
 }
 
-struct EntryMetaData {
-    EntryMetaData() { }
-    explicit EntryMetaData(const Key& key)
+struct RecordMetaData {
+    RecordMetaData() { }
+    explicit RecordMetaData(const Key& key)
         : cacheStorageVersion(Storage::version)
         , key(key)
     { }
 
     unsigned cacheStorageVersion;
     Key key;
-    std::chrono::milliseconds timeStamp;
+    // FIXME: Add encoder/decoder for time_point.
+    std::chrono::milliseconds epochRelativeTimeStamp;
     unsigned headerChecksum;
     uint64_t headerOffset;
     uint64_t headerSize;
-    unsigned bodyChecksum;
-    uint64_t bodyOffset;
+    SHA1::Digest bodyHash;
     uint64_t bodySize;
 };
 
-static bool decodeEntryMetaData(EntryMetaData& metaData, const Data& fileData)
+static bool decodeRecordMetaData(RecordMetaData& metaData, const Data& fileData)
 {
     bool success = false;
     fileData.apply([&metaData, &success](const uint8_t* data, size_t size) {
@@ -156,34 +236,36 @@ static bool decodeEntryMetaData(EntryMetaData& metaData, const Data& fileData)
             return false;
         if (!decoder.decode(metaData.key))
             return false;
-        if (!decoder.decode(metaData.timeStamp))
+        if (!decoder.decode(metaData.epochRelativeTimeStamp))
             return false;
         if (!decoder.decode(metaData.headerChecksum))
             return false;
         if (!decoder.decode(metaData.headerSize))
             return false;
-        if (!decoder.decode(metaData.bodyChecksum))
+        if (!decoder.decode(metaData.bodyHash))
             return false;
         if (!decoder.decode(metaData.bodySize))
             return false;
         if (!decoder.verifyChecksum())
             return false;
         metaData.headerOffset = decoder.currentOffset();
-        metaData.bodyOffset = WTF::roundUpToMultipleOf(pageSize(), metaData.headerOffset + metaData.headerSize);
         success = true;
         return false;
     });
     return success;
 }
 
-static bool decodeEntryHeader(const Data& fileData, EntryMetaData& metaData, Data& data)
+static bool decodeRecordHeader(const Data& fileData, RecordMetaData& metaData, Data& data)
 {
-    if (!decodeEntryMetaData(metaData, fileData))
-        return false;
-    if (metaData.cacheStorageVersion != Storage::version)
+    if (!decodeRecordMetaData(metaData, fileData)) {
+        LOG(NetworkCacheStorage, "(NetworkProcess) meta data decode failure");
         return false;
-    if (metaData.headerOffset + metaData.headerSize > metaData.bodyOffset)
+    }
+
+    if (metaData.cacheStorageVersion != Storage::version) {
+        LOG(NetworkCacheStorage, "(NetworkProcess) version mismatch");
         return false;
+    }
 
     auto headerData = fileData.subrange(metaData.headerOffset, metaData.headerSize);
     if (metaData.headerChecksum != hashData(headerData)) {
@@ -194,88 +276,84 @@ static bool decodeEntryHeader(const Data& fileData, EntryMetaData& metaData, Dat
     return true;
 }
 
-static std::unique_ptr<Storage::Entry> decodeEntry(const Data& fileData, int fd, const Key& key)
+static std::unique_ptr<Storage::Record> createRecord(const Data& recordData, const BlobStorage::Blob& bodyBlob, const Key& key)
 {
-    EntryMetaData metaData;
+    RecordMetaData metaData;
     Data headerData;
-    if (!decodeEntryHeader(fileData, metaData, headerData))
+    if (!decodeRecordHeader(recordData, metaData, headerData))
         return nullptr;
 
     if (metaData.key != key)
         return nullptr;
-    if (metaData.bodyOffset + metaData.bodySize != fileData.size())
-        return nullptr;
 
-    auto bodyData = mapFile(fd, metaData.bodyOffset, metaData.bodySize);
-    if (bodyData.isNull()) {
-        LOG(NetworkCacheStorage, "(NetworkProcess) map failed");
+    // Sanity check against time stamps in future.
+    auto timeStamp = std::chrono::system_clock::time_point(metaData.epochRelativeTimeStamp);
+    if (timeStamp > std::chrono::system_clock::now())
         return nullptr;
-    }
-
-    if (metaData.bodyChecksum != hashData(bodyData)) {
-        LOG(NetworkCacheStorage, "(NetworkProcess) data checksum mismatch");
+    if (metaData.bodySize != bodyBlob.data.size())
+        return nullptr;
+    if (metaData.bodyHash != bodyBlob.hash)
         return nullptr;
-    }
 
-    return std::make_unique<Storage::Entry>(Storage::Entry {
+    return std::make_unique<Storage::Record>(Storage::Record {
         metaData.key,
-        metaData.timeStamp,
+        timeStamp,
         headerData,
-        bodyData
+        bodyBlob.data
     });
 }
 
-static Data encodeEntryMetaData(const EntryMetaData& entry)
+static Data encodeRecordMetaData(const RecordMetaData& metaData)
 {
     Encoder encoder;
 
-    encoder << entry.cacheStorageVersion;
-    encoder << entry.key;
-    encoder << entry.timeStamp;
-    encoder << entry.headerChecksum;
-    encoder << entry.headerSize;
-    encoder << entry.bodyChecksum;
-    encoder << entry.bodySize;
+    encoder << metaData.cacheStorageVersion;
+    encoder << metaData.key;
+    encoder << metaData.epochRelativeTimeStamp;
+    encoder << metaData.headerChecksum;
+    encoder << metaData.headerSize;
+    encoder << metaData.bodyHash;
+    encoder << metaData.bodySize;
 
     encoder.encodeChecksum();
 
     return Data(encoder.buffer(), encoder.bufferSize());
 }
 
-static Data encodeEntryHeader(const Storage::Entry& entry)
+static Data encodeRecordHeader(const Storage::Record& record, SHA1::Digest bodyHash)
 {
-    EntryMetaData metaData(entry.key);
-    metaData.timeStamp = entry.timeStamp;
-    metaData.headerChecksum = hashData(entry.header);
-    metaData.headerSize = entry.header.size();
-    metaData.bodyChecksum = hashData(entry.body);
-    metaData.bodySize = entry.body.size();
-
-    auto encodedMetaData = encodeEntryMetaData(metaData);
-    auto headerData = concatenate(encodedMetaData, entry.header);
-    if (!entry.body.size())
-        return { headerData };
-
-    size_t dataOffset = WTF::roundUpToMultipleOf(pageSize(), headerData.size());
-    Vector<uint8_t, 4096> filler(dataOffset - headerData.size(), 0);
-    Data alignmentData(filler.data(), filler.size());
-
-    return concatenate(headerData, alignmentData);
+    RecordMetaData metaData(record.key);
+    metaData.epochRelativeTimeStamp = std::chrono::duration_cast<std::chrono::milliseconds>(record.timeStamp.time_since_epoch());
+    metaData.headerChecksum = hashData(record.header);
+    metaData.headerSize = record.header.size();
+    metaData.bodyHash = bodyHash;
+    metaData.bodySize = record.body.size();
+
+    auto encodedMetaData = encodeRecordMetaData(metaData);
+    auto headerData = concatenate(encodedMetaData, record.header);
+    return { headerData };
 }
 
-void Storage::removeEntry(const Key& key)
+void Storage::remove(const Key& key)
 {
     ASSERT(RunLoop::isMain());
 
-    // For simplicity we don't reduce m_approximateSize on removals caused by load or decode errors.
-    // The next cache shrink will update the size.
+    // We can't remove the key from the Bloom filter (but some false positives are expected anyway).
+    // For simplicity we also don't reduce m_approximateSize on removals.
+    // The next synchronization will update everything.
 
-    if (m_contentsFilter.mayContain(key.shortHash()))
-        m_contentsFilter.remove(key.shortHash());
+    serialBackgroundIOQueue().dispatch([this, key] {
+        auto recordsPath = this->recordsPath();
+        WebCore::deleteFile(recordPathForKey(key, recordsPath));
+        m_blobStorage.remove(bodyPathForKey(key, recordsPath));
+    });
+}
 
-    StringCapture filePathCapture(filePathForKey(key, m_directoryPath));
-    backgroundIOQueue().dispatch([this, filePathCapture] {
-        WebCore::deleteFile(filePathCapture.string());
+void Storage::updateFileModificationTime(const String& path)
+{
+    StringCapture filePathCapture(path);
+    serialBackgroundIOQueue().dispatch([filePathCapture] {
+        updateFileModificationTimeIfNeeded(filePathCapture.string());
     });
 }
 
@@ -284,30 +362,37 @@ void Storage::dispatchReadOperation(const ReadOperation& read)
     ASSERT(RunLoop::isMain());
     ASSERT(m_activeReadOperations.contains(&read));
 
-    StringCapture cachePathCapture(m_directoryPath);
-    ioQueue().dispatch([this, &read, cachePathCapture] {
-        auto channel = openFileForKey(read.key, IOChannel::Type::Read, cachePathCapture.string());
-        int fd = channel->fileDescriptor();
-        channel->read(0, std::numeric_limits<size_t>::max(), [this, &read, fd](Data& fileData, int error) {
-            if (error) {
-                removeEntry(read.key);
-                read.completionHandler(nullptr);
-            } else {
-                auto entry = decodeEntry(fileData, fd, read.key);
-                bool success = read.completionHandler(WTF::move(entry));
-                if (!success)
-                    removeEntry(read.key);
-            }
-
-            ASSERT(m_activeReadOperations.contains(&read));
-            m_activeReadOperations.remove(&read);
-            dispatchPendingReadOperations();
-
-            LOG(NetworkCacheStorage, "(NetworkProcess) read complete error=%d", error);
+    ioQueue().dispatch([this, &read] {
+        auto recordsPath = this->recordsPath();
+        auto recordPath = recordPathForKey(read.key, recordsPath);
+        auto bodyPath = bodyPathForKey(read.key, recordsPath);
+        // FIXME: Body and header retrieves can be done in parallel.
+        auto bodyBlob = m_blobStorage.get(bodyPath);
+
+        RefPtr<IOChannel> channel = IOChannel::open(recordPath, IOChannel::Type::Read);
+        channel->read(0, std::numeric_limits<size_t>::max(), [this, &read, bodyBlob](Data& fileData, int error) {
+            auto record = error ? nullptr : createRecord(fileData, bodyBlob, read.key);
+            finishReadOperation(read, WTF::move(record));
         });
     });
 }
 
+void Storage::finishReadOperation(const ReadOperation& read, std::unique_ptr<Record> record)
+{
+    ASSERT(RunLoop::isMain());
+
+    bool success = read.completionHandler(WTF::move(record));
+    if (success)
+        updateFileModificationTime(recordPathForKey(read.key, recordsPath()));
+    else
+        remove(read.key);
+    ASSERT(m_activeReadOperations.contains(&read));
+    m_activeReadOperations.remove(&read);
+    dispatchPendingReadOperations();
+
+    LOG(NetworkCacheStorage, "(NetworkProcess) read complete success=%d", success);
+}
+
 void Storage::dispatchPendingReadOperations()
 {
     ASSERT(RunLoop::isMain());
@@ -332,11 +417,11 @@ void Storage::dispatchPendingReadOperations()
 template <class T> bool retrieveFromMemory(const T& operations, const Key& key, Storage::RetrieveCompletionHandler& completionHandler)
 {
     for (auto& operation : operations) {
-        if (operation->entry.key == key) {
+        if (operation->record.key == key) {
             LOG(NetworkCacheStorage, "(NetworkProcess) found write operation in progress");
-            auto entry = operation->entry;
-            RunLoop::main().dispatch([entry, completionHandler] {
-                completionHandler(std::make_unique<Storage::Entry>(entry));
+            auto record = operation->record;
+            RunLoop::main().dispatch([record, completionHandler] {
+                completionHandler(std::make_unique<Storage::Record>(record));
             });
             return true;
         }
@@ -344,18 +429,95 @@ template <class T> bool retrieveFromMemory(const T& operations, const Key& key,
     return false;
 }
 
+void Storage::dispatchPendingWriteOperations()
+{
+    ASSERT(RunLoop::isMain());
+
+    const int maximumActiveWriteOperationCount { 3 };
+
+    while (!m_pendingWriteOperations.isEmpty()) {
+        if (m_activeWriteOperations.size() >= maximumActiveWriteOperationCount) {
+            LOG(NetworkCacheStorage, "(NetworkProcess) limiting parallel writes");
+            return;
+        }
+        auto writeOperation = m_pendingWriteOperations.takeFirst();
+        auto& write = *writeOperation;
+        m_activeWriteOperations.add(WTF::move(writeOperation));
+
+        dispatchWriteOperation(write);
+    }
+}
+
+void Storage::dispatchWriteOperation(const WriteOperation& write)
+{
+    ASSERT(RunLoop::isMain());
+    ASSERT(m_activeWriteOperations.contains(&write));
+
+    // This was added already when starting the store but filter might have been wiped.
+    addToContentsFilter(write.record.key);
+
+    backgroundIOQueue().dispatch([this, &write] {
+        auto recordsPath = this->recordsPath();
+        auto partitionPath = partitionPathForKey(write.record.key, recordsPath);
+        auto recordPath = recordPathForKey(write.record.key, recordsPath);
+        auto bodyPath = bodyPathForKey(write.record.key, recordsPath);
+
+        WebCore::makeAllDirectories(partitionPath);
+
+        // Store the body.
+        auto blob = m_blobStorage.add(bodyPath, write.record.body);
+        if (blob.data.isNull()) {
+            RunLoop::main().dispatch([this, &write] {
+                finishWriteOperation(write);
+            });
+            return;
+        }
+
+        // Tell the client we now have a disk-backed map for this data.
+        size_t minimumMapSize = pageSize();
+        if (blob.data.size() >= minimumMapSize && blob.data.isMap() && write.mappedBodyHandler) {
+            auto& mappedBodyHandler = write.mappedBodyHandler;
+            RunLoop::main().dispatch([blob, mappedBodyHandler] {
+                mappedBodyHandler(blob.data);
+            });
+        }
+
+        // Store the header and meta data.
+        auto encodedHeader = encodeRecordHeader(write.record, blob.hash);
+        auto channel = IOChannel::open(recordPath, IOChannel::Type::Create);
+        int fd = channel->fileDescriptor();
+        size_t headerSize = encodedHeader.size();
+        channel->write(0, encodedHeader, [this, &write, headerSize, fd](int error) {
+            // On error the entry still stays in the contents filter until next synchronization.
+            m_approximateSize += headerSize;
+            finishWriteOperation(write);
+
+            LOG(NetworkCacheStorage, "(NetworkProcess) write complete error=%d", error);
+        });
+    });
+}
+
+void Storage::finishWriteOperation(const WriteOperation& write)
+{
+    ASSERT(m_activeWriteOperations.contains(&write));
+    m_activeWriteOperations.remove(&write);
+    dispatchPendingWriteOperations();
+
+    shrinkIfNeeded();
+}
+
 void Storage::retrieve(const Key& key, unsigned priority, RetrieveCompletionHandler&& completionHandler)
 {
     ASSERT(RunLoop::isMain());
     ASSERT(priority <= maximumRetrievePriority);
     ASSERT(!key.isNull());
 
-    if (!m_maximumSize) {
+    if (!m_capacity) {
         completionHandler(nullptr);
         return;
     }
 
-    if (!m_contentsFilter.mayContain(key.shortHash())) {
+    if (!mayContain(key)) {
         completionHandler(nullptr);
         return;
     }
@@ -369,257 +531,188 @@ void Storage::retrieve(const Key& key, unsigned priority, RetrieveCompletionHand
     dispatchPendingReadOperations();
 }
 
-void Storage::store(const Entry& entry, StoreCompletionHandler&& completionHandler)
+void Storage::store(const Record& record, MappedBodyHandler&& mappedBodyHandler)
 {
     ASSERT(RunLoop::isMain());
-    ASSERT(!entry.key.isNull());
+    ASSERT(!record.key.isNull());
 
-    if (!m_maximumSize) {
-        completionHandler(false, { });
+    if (!m_capacity)
         return;
-    }
 
-    m_pendingWriteOperations.append(new WriteOperation { entry, { }, WTF::move(completionHandler) });
+    m_pendingWriteOperations.append(new WriteOperation { record, WTF::move(mappedBodyHandler) });
 
     // Add key to the filter already here as we do lookups from the pending operations too.
-    m_contentsFilter.add(entry.key.shortHash());
+    addToContentsFilter(record.key);
 
     dispatchPendingWriteOperations();
 }
 
-void Storage::update(const Entry& updateEntry, const Entry& existingEntry, StoreCompletionHandler&& completionHandler)
+void Storage::traverse(TraverseFlags flags, std::function<void (const Record*, const RecordInfo&)>&& traverseHandler)
 {
-    ASSERT(RunLoop::isMain());
-    ASSERT(!existingEntry.key.isNull());
-    ASSERT(existingEntry.key == updateEntry.key);
-
-    if (!m_maximumSize) {
-        completionHandler(false, { });
-        return;
-    }
+    ioQueue().dispatch([this, flags, traverseHandler] {
+        traverseCacheFiles(recordsPath(), [this, flags, &traverseHandler](const String& fileName, const String& partitionPath) {
+            auto recordPath = WebCore::pathByAppendingComponent(partitionPath, fileName);
 
-    m_pendingWriteOperations.append(new WriteOperation { updateEntry, existingEntry, WTF::move(completionHandler) });
+            RecordInfo info;
+            if (flags & TraverseFlag::ComputeWorth)
+                info.worth = computeRecordWorth(fileTimes(recordPath));
+            if (flags & TraverseFlag::ShareCount)
+                info.bodyShareCount = m_blobStorage.shareCount(bodyPathForRecordPath(recordPath));
 
-    dispatchPendingWriteOperations();
-}
-
-void Storage::traverse(std::function<void (const Entry*)>&& traverseHandler)
-{
-    StringCapture cachePathCapture(m_directoryPath);
-    ioQueue().dispatch([this, cachePathCapture, traverseHandler] {
-        String cachePath = cachePathCapture.string();
-        traverseCacheFiles(cachePath, [this, &traverseHandler](const String& fileName, const String& partitionPath) {
-            auto filePath = WebCore::pathByAppendingComponent(partitionPath, fileName);
-            auto channel = IOChannel::open(filePath, IOChannel::Type::Read);
-            const size_t headerReadSize = 16 << 10;
+            auto channel = IOChannel::open(recordPath, IOChannel::Type::Read);
             // FIXME: Traversal is slower than it should be due to lack of parallelism.
-            channel->readSync(0, headerReadSize, [this, &traverseHandler](Data& fileData, int) {
-                EntryMetaData metaData;
+            channel->readSync(0, std::numeric_limits<size_t>::max(), [this, &traverseHandler, &info](Data& fileData, int) {
+                RecordMetaData metaData;
                 Data headerData;
-                if (decodeEntryHeader(fileData, metaData, headerData)) {
-                    Entry entry { metaData.key, metaData.timeStamp, headerData, { } };
-                    traverseHandler(&entry);
+                if (decodeRecordHeader(fileData, metaData, headerData)) {
+                    Record record { metaData.key, std::chrono::system_clock::time_point(metaData.epochRelativeTimeStamp), headerData, { } };
+                    info.bodySize = metaData.bodySize;
+                    info.bodyHash = String::fromUTF8(SHA1::hexDigest(metaData.bodyHash));
+                    traverseHandler(&record, info);
                 }
             });
         });
         RunLoop::main().dispatch([this, traverseHandler] {
-            traverseHandler(nullptr);
+            traverseHandler(nullptr, { });
         });
     });
 }
 
-void Storage::dispatchPendingWriteOperations()
+void Storage::setCapacity(size_t capacity)
 {
     ASSERT(RunLoop::isMain());
 
-    const int maximumActiveWriteOperationCount { 3 };
+#if !ASSERT_DISABLED
+    const size_t assumedAverageRecordSize = 50 << 10;
+    size_t maximumRecordCount = capacity / assumedAverageRecordSize;
+    // ~10 bits per element are required for <1% false positive rate.
+    size_t effectiveBloomFilterCapacity = ContentsFilter::tableSize / 10;
+    // If this gets hit it might be time to increase the filter size.
+    ASSERT(maximumRecordCount < effectiveBloomFilterCapacity);
+#endif
 
-    while (!m_pendingWriteOperations.isEmpty()) {
-        if (m_activeWriteOperations.size() >= maximumActiveWriteOperationCount) {
-            LOG(NetworkCacheStorage, "(NetworkProcess) limiting parallel writes");
-            return;
-        }
-        auto writeOperation = m_pendingWriteOperations.takeFirst();
-        auto& write = *writeOperation;
-        m_activeWriteOperations.add(WTF::move(writeOperation));
+    m_capacity = capacity;
 
-        if (write.existingEntry && m_contentsFilter.mayContain(write.entry.key.shortHash())) {
-            dispatchHeaderWriteOperation(write);
-            continue;
-        }
-        dispatchFullWriteOperation(write);
-    }
+    shrinkIfNeeded();
 }
 
-void Storage::dispatchFullWriteOperation(const WriteOperation& write)
+void Storage::clear()
 {
     ASSERT(RunLoop::isMain());
-    ASSERT(m_activeWriteOperations.contains(&write));
-
-    if (!m_contentsFilter.mayContain(write.entry.key.shortHash()))
-        m_contentsFilter.add(write.entry.key.shortHash());
-
-    StringCapture cachePathCapture(m_directoryPath);
-    backgroundIOQueue().dispatch([this, &write, cachePathCapture] {
-        auto encodedHeader = encodeEntryHeader(write.entry);
-        auto headerAndBodyData = concatenate(encodedHeader, write.entry.body);
-
-        auto channel = openFileForKey(write.entry.key, IOChannel::Type::Create, cachePathCapture.string());
-        int fd = channel->fileDescriptor();
-        size_t bodyOffset = encodedHeader.size();
-
-        channel->write(0, headerAndBodyData, [this, &write, bodyOffset, fd](int error) {
-            LOG(NetworkCacheStorage, "(NetworkProcess) write complete error=%d", error);
-            if (error) {
-                if (m_contentsFilter.mayContain(write.entry.key.shortHash()))
-                    m_contentsFilter.remove(write.entry.key.shortHash());
-            }
-            size_t bodySize = write.entry.body.size();
-            size_t totalSize = bodyOffset + bodySize;
-
-            m_approximateSize += totalSize;
-
-            bool shouldMapBody = !error && bodySize >= pageSize();
-            auto bodyMap = shouldMapBody ? mapFile(fd, bodyOffset, bodySize) : Data();
+    LOG(NetworkCacheStorage, "(NetworkProcess) clearing cache");
 
-            write.completionHandler(!error, bodyMap);
+    if (m_contentsFilter)
+        m_contentsFilter->clear();
+    m_approximateSize = 0;
 
-            ASSERT(m_activeWriteOperations.contains(&write));
-            m_activeWriteOperations.remove(&write);
-            dispatchPendingWriteOperations();
+    ioQueue().dispatch([this] {
+        auto recordsPath = this->recordsPath();
+        traverseDirectory(recordsPath, DT_DIR, [&recordsPath](const String& subdirName) {
+            String subdirPath = WebCore::pathByAppendingComponent(recordsPath, subdirName);
+            traverseDirectory(subdirPath, DT_REG, [&subdirPath](const String& fileName) {
+                WebCore::deleteFile(WebCore::pathByAppendingComponent(subdirPath, fileName));
+            });
+            WebCore::deleteEmptyDirectory(subdirPath);
         });
-    });
 
-    shrinkIfNeeded();
+        // This cleans unreferences blobs.
+        m_blobStorage.synchronize();
+    });
 }
 
-void Storage::dispatchHeaderWriteOperation(const WriteOperation& write)
+static double computeRecordWorth(FileTimes times)
 {
-    ASSERT(RunLoop::isMain());
-    ASSERT(write.existingEntry);
-    ASSERT(m_activeWriteOperations.contains(&write));
-    ASSERT(m_contentsFilter.mayContain(write.entry.key.shortHash()));
+    using namespace std::chrono;
+    auto age = system_clock::now() - times.creation;
+    // File modification time is updated manually on cache read. We don't use access time since OS may update it automatically.
+    auto accessAge = times.modification - times.creation;
 
-    // Try to update the header of an existing entry.
-    StringCapture cachePathCapture(m_directoryPath);
-    backgroundIOQueue().dispatch([this, &write, cachePathCapture] {
-        auto headerData = encodeEntryHeader(write.entry);
-        auto existingHeaderData = encodeEntryHeader(write.existingEntry.value());
+    // For sanity.
+    if (age <= 0_s || accessAge < 0_s || accessAge > age)
+        return 0;
 
-        bool pageRoundedHeaderSizeChanged = headerData.size() != existingHeaderData.size();
-        if (pageRoundedHeaderSizeChanged) {
-            LOG(NetworkCacheStorage, "(NetworkProcess) page-rounded header size changed, storing full entry");
-            RunLoop::main().dispatch([this, &write] {
-                dispatchFullWriteOperation(write);
-            });
-            return;
-        }
+    // We like old entries that have been accessed recently.
+    return duration<double>(accessAge) / age;
+}
 
-        auto channel = openFileForKey(write.entry.key, IOChannel::Type::Write, cachePathCapture.string());
-        channel->write(0, headerData, [this, &write](int error) {
-            LOG(NetworkCacheStorage, "(NetworkProcess) update complete error=%d", error);
+static double deletionProbability(FileTimes times, unsigned bodyShareCount)
+{
+    static const double maximumProbability { 0.33 };
+    static const unsigned maximumEffectiveShareCount { 5 };
 
-            if (error)
-                removeEntry(write.entry.key);
+    auto worth = computeRecordWorth(times);
 
-            write.completionHandler(!error, { });
+    // Adjust a bit so the most valuable entries don't get deleted at all.
+    auto effectiveWorth = std::min(1.1 * worth, 1.);
 
-            ASSERT(m_activeWriteOperations.contains(&write));
-            m_activeWriteOperations.remove(&write);
-            dispatchPendingWriteOperations();
-        });
-    });
-}
+    auto probability =  (1 - effectiveWorth) * maximumProbability;
 
-void Storage::setMaximumSize(size_t size)
-{
-    ASSERT(RunLoop::isMain());
-    m_maximumSize = size;
+    // It is less useful to remove an entry that shares its body data.
+    if (bodyShareCount)
+        probability /= std::min(bodyShareCount, maximumEffectiveShareCount);
 
-    shrinkIfNeeded();
+    return probability;
 }
 
-void Storage::clear()
+void Storage::shrinkIfNeeded()
 {
     ASSERT(RunLoop::isMain());
-    LOG(NetworkCacheStorage, "(NetworkProcess) clearing cache");
-
-    m_contentsFilter.clear();
-    m_approximateSize = 0;
-
-    StringCapture directoryPathCapture(m_directoryPath);
 
-    ioQueue().dispatch([directoryPathCapture] {
-        String directoryPath = directoryPathCapture.string();
-        traverseDirectory(directoryPath, DT_DIR, [&directoryPath](const String& subdirName) {
-            String subdirPath = WebCore::pathByAppendingComponent(directoryPath, subdirName);
-            traverseDirectory(subdirPath, DT_REG, [&subdirPath](const String& fileName) {
-                WebCore::deleteFile(WebCore::pathByAppendingComponent(subdirPath, fileName));
-            });
-            WebCore::deleteEmptyDirectory(subdirPath);
-        });
-    });
+    if (approximateSize() > m_capacity)
+        shrink();
 }
 
-void Storage::shrinkIfNeeded()
+void Storage::shrink()
 {
     ASSERT(RunLoop::isMain());
 
-    static const double deletionProbability { 0.25 };
-
-    if (m_approximateSize <= m_maximumSize)
-        return;
-    if (m_shrinkInProgress)
+    if (m_shrinkInProgress || m_synchronizationInProgress)
         return;
     m_shrinkInProgress = true;
 
-    LOG(NetworkCacheStorage, "(NetworkProcess) shrinking cache approximateSize=%zu, m_maximumSize=%zu", static_cast<size_t>(m_approximateSize), m_maximumSize);
+    LOG(NetworkCacheStorage, "(NetworkProcess) shrinking cache approximateSize=%zu capacity=%zu", approximateSize(), m_capacity);
 
-    m_approximateSize = 0;
+    backgroundIOQueue().dispatch([this] {
+        auto recordsPath = this->recordsPath();
+        traverseCacheFiles(recordsPath, [this](const String& fileName, const String& partitionPath) {
+            auto recordPath = WebCore::pathByAppendingComponent(partitionPath, fileName);
+            auto bodyPath = bodyPathForRecordPath(recordPath);
 
-    StringCapture cachePathCapture(m_directoryPath);
-    backgroundIOQueue().dispatch([this, cachePathCapture] {
-        String cachePath = cachePathCapture.string();
-        traverseCacheFiles(cachePath, [this](const String& fileName, const String& partitionPath) {
-            auto filePath = WebCore::pathByAppendingComponent(partitionPath, fileName);
+            auto times = fileTimes(recordPath);
+            unsigned bodyShareCount = m_blobStorage.shareCount(bodyPath);
+            auto probability = deletionProbability(times, bodyShareCount);
 
-            bool shouldDelete = randomNumber() < deletionProbability;
-            if (!shouldDelete) {
-                long long fileSize = 0;
-                WebCore::getFileSize(filePath, fileSize);
-                m_approximateSize += fileSize;
-                return;
-            }
+            bool shouldDelete = randomNumber() < probability;
 
-            WebCore::deleteFile(filePath);
-            Key::HashType hash;
-            if (!Key::stringToHash(fileName, hash))
-                return;
-            unsigned shortHash = Key::toShortHash(hash);
-            RunLoop::main().dispatch([this, shortHash] {
-                if (m_contentsFilter.mayContain(shortHash))
-                    m_contentsFilter.remove(shortHash);
-            });
+            LOG(NetworkCacheStorage, "Deletion probability=%f bodyLinkCount=%d shouldDelete=%d", probability, bodyShareCount, shouldDelete);
+
+            if (shouldDelete) {
+                WebCore::deleteFile(recordPath);
+                m_blobStorage.remove(bodyPath);
+            }
         });
 
         // Let system figure out if they are really empty.
-        traverseDirectory(cachePath, DT_DIR, [&cachePath](const String& subdirName) {
-            auto partitionPath = WebCore::pathByAppendingComponent(cachePath, subdirName);
+        traverseDirectory(recordsPath, DT_DIR, [&recordsPath](const String& subdirName) {
+            auto partitionPath = WebCore::pathByAppendingComponent(recordsPath, subdirName);
             WebCore::deleteEmptyDirectory(partitionPath);
         });
 
-        m_shrinkInProgress = false;
+        RunLoop::main().dispatch([this] {
+            m_shrinkInProgress = false;
+            // We could synchronize during the shrink traversal. However this is fast and it is better to have just one code path.
+            synchronize();
+        });
 
-        LOG(NetworkCacheStorage, "(NetworkProcess) cache shrink completed approximateSize=%zu", static_cast<size_t>(m_approximateSize));
+        LOG(NetworkCacheStorage, "(NetworkProcess) cache shrink completed");
     });
 }
 
 void Storage::deleteOldVersions()
 {
     // Delete V1 cache.
-    StringCapture cachePathCapture(m_baseDirectoryPath);
-    backgroundIOQueue().dispatch([cachePathCapture] {
-        String cachePath = cachePathCapture.string();
+    backgroundIOQueue().dispatch([this] {
+        auto cachePath = basePath();
         traverseDirectory(cachePath, DT_DIR, [&cachePath](const String& subdirName) {
             if (subdirName.startsWith(versionDirectoryPrefix))
                 return;
@@ -630,6 +723,7 @@ void Storage::deleteOldVersions()
             WebCore::deleteEmptyDirectory(partitionPath);
         });
     });
+    // FIXME: Delete V2 cache.
 }
 
 }