879f1dccf363001099956373419735f5077cb969
[WebKit.git] / Source / WebKit / NetworkProcess / cache / NetworkCacheStorage.cpp
1 /*
2  * Copyright (C) 2014-2017 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "NetworkCacheStorage.h"
28
29 #include "Logging.h"
30 #include "NetworkCacheCoders.h"
31 #include "NetworkCacheFileSystem.h"
32 #include "NetworkCacheIOChannel.h"
33 #include <mutex>
34 #include <wtf/Condition.h>
35 #include <wtf/Lock.h>
36 #include <wtf/RandomNumber.h>
37 #include <wtf/RunLoop.h>
38 #include <wtf/text/CString.h>
39
40 namespace WebKit {
41 namespace NetworkCache {
42
43 static const char saltFileName[] = "salt";
44 static const char versionDirectoryPrefix[] = "Version ";
45 static const char recordsDirectoryName[] = "Records";
46 static const char blobsDirectoryName[] = "Blobs";
47 static const char blobSuffix[] = "-blob";
48
49 static double computeRecordWorth(FileTimes);
50
51 struct Storage::ReadOperation {
52     WTF_MAKE_FAST_ALLOCATED;
53 public:
54     ReadOperation(Storage& storage, const Key& key, RetrieveCompletionHandler&& completionHandler)
55         : storage(storage)
56         , key(key)
57         , completionHandler(WTFMove(completionHandler))
58     { }
59
60     void cancel();
61     bool finish();
62
63     Ref<Storage> storage;
64
65     const Key key;
66     const RetrieveCompletionHandler completionHandler;
67     
68     std::unique_ptr<Record> resultRecord;
69     SHA1::Digest expectedBodyHash;
70     BlobStorage::Blob resultBodyBlob;
71     std::atomic<unsigned> activeCount { 0 };
72     bool isCanceled { false };
73 };
74
75 void Storage::ReadOperation::cancel()
76 {
77     ASSERT(RunLoop::isMain());
78
79     if (isCanceled)
80         return;
81     isCanceled = true;
82     completionHandler(nullptr);
83 }
84
85 bool Storage::ReadOperation::finish()
86 {
87     ASSERT(RunLoop::isMain());
88
89     if (isCanceled)
90         return false;
91     if (resultRecord && resultRecord->body.isNull()) {
92         if (resultBodyBlob.hash == expectedBodyHash)
93             resultRecord->body = resultBodyBlob.data;
94         else
95             resultRecord = nullptr;
96     }
97     return completionHandler(WTFMove(resultRecord));
98 }
99
100 struct Storage::WriteOperation {
101     WTF_MAKE_FAST_ALLOCATED;
102 public:
103     WriteOperation(Storage& storage, const Record& record, MappedBodyHandler&& mappedBodyHandler)
104         : storage(storage)
105         , record(record)
106         , mappedBodyHandler(WTFMove(mappedBodyHandler))
107     { }
108     Ref<Storage> storage;
109
110     const Record record;
111     const MappedBodyHandler mappedBodyHandler;
112
113     std::atomic<unsigned> activeCount { 0 };
114 };
115
116 struct Storage::TraverseOperation {
117     WTF_MAKE_FAST_ALLOCATED;
118 public:
119     TraverseOperation(Storage& storage, const String& type, TraverseFlags flags, TraverseHandler&& handler)
120         : storage(storage)
121         , type(type)
122         , flags(flags)
123         , handler(WTFMove(handler))
124     { }
125     Ref<Storage> storage;
126
127     const String type;
128     const TraverseFlags flags;
129     const TraverseHandler handler;
130
131     Lock activeMutex;
132     Condition activeCondition;
133     unsigned activeCount { 0 };
134 };
135
136 static String makeVersionedDirectoryPath(const String& baseDirectoryPath)
137 {
138     String versionSubdirectory = versionDirectoryPrefix + String::number(Storage::version);
139     return WebCore::FileSystem::pathByAppendingComponent(baseDirectoryPath, versionSubdirectory);
140 }
141
142 static String makeRecordsDirectoryPath(const String& baseDirectoryPath)
143 {
144     return WebCore::FileSystem::pathByAppendingComponent(makeVersionedDirectoryPath(baseDirectoryPath), recordsDirectoryName);
145 }
146
147 static String makeBlobDirectoryPath(const String& baseDirectoryPath)
148 {
149     return WebCore::FileSystem::pathByAppendingComponent(makeVersionedDirectoryPath(baseDirectoryPath), blobsDirectoryName);
150 }
151
152 static String makeSaltFilePath(const String& baseDirectoryPath)
153 {
154     return WebCore::FileSystem::pathByAppendingComponent(makeVersionedDirectoryPath(baseDirectoryPath), saltFileName);
155 }
156
157 RefPtr<Storage> Storage::open(const String& cachePath, Mode mode)
158 {
159     ASSERT(RunLoop::isMain());
160
161     if (!WebCore::FileSystem::makeAllDirectories(makeVersionedDirectoryPath(cachePath)))
162         return nullptr;
163     auto salt = readOrMakeSalt(makeSaltFilePath(cachePath));
164     if (!salt)
165         return nullptr;
166     return adoptRef(new Storage(cachePath, mode, *salt));
167 }
168
169 void traverseRecordsFiles(const String& recordsPath, const String& expectedType, const RecordFileTraverseFunction& function)
170 {
171     traverseDirectory(recordsPath, [&](const String& partitionName, DirectoryEntryType entryType) {
172         if (entryType != DirectoryEntryType::Directory)
173             return;
174         String partitionPath = WebCore::FileSystem::pathByAppendingComponent(recordsPath, partitionName);
175         traverseDirectory(partitionPath, [&](const String& actualType, DirectoryEntryType entryType) {
176             if (entryType != DirectoryEntryType::Directory)
177                 return;
178             if (!expectedType.isEmpty() && expectedType != actualType)
179                 return;
180             String recordDirectoryPath = WebCore::FileSystem::pathByAppendingComponent(partitionPath, actualType);
181             traverseDirectory(recordDirectoryPath, [&function, &recordDirectoryPath, &actualType](const String& fileName, DirectoryEntryType entryType) {
182                 if (entryType != DirectoryEntryType::File || fileName.length() < Key::hashStringLength())
183                     return;
184
185                 String hashString = fileName.substring(0, Key::hashStringLength());
186                 auto isBlob = fileName.length() > Key::hashStringLength() && fileName.endsWith(blobSuffix);
187                 function(fileName, hashString, actualType, isBlob, recordDirectoryPath);
188             });
189         });
190     });
191 }
192
193 static void deleteEmptyRecordsDirectories(const String& recordsPath)
194 {
195     traverseDirectory(recordsPath, [&recordsPath](const String& partitionName, DirectoryEntryType type) {
196         if (type != DirectoryEntryType::Directory)
197             return;
198
199         // Delete [type] sub-folders.
200         String partitionPath = WebCore::FileSystem::pathByAppendingComponent(recordsPath, partitionName);
201         traverseDirectory(partitionPath, [&partitionPath](const String& subdirName, DirectoryEntryType entryType) {
202             if (entryType != DirectoryEntryType::Directory)
203                 return;
204
205             // Let system figure out if it is really empty.
206             WebCore::FileSystem::deleteEmptyDirectory(WebCore::FileSystem::pathByAppendingComponent(partitionPath, subdirName));
207         });
208
209         // Delete [Partition] folders.
210         // Let system figure out if it is really empty.
211         WebCore::FileSystem::deleteEmptyDirectory(WebCore::FileSystem::pathByAppendingComponent(recordsPath, partitionName));
212     });
213 }
214
215 Storage::Storage(const String& baseDirectoryPath, Mode mode, Salt salt)
216     : m_basePath(baseDirectoryPath)
217     , m_recordsPath(makeRecordsDirectoryPath(baseDirectoryPath))
218     , m_mode(mode)
219     , m_salt(salt)
220     , m_canUseSharedMemoryForBodyData(canUseSharedMemoryForPath(baseDirectoryPath))
221     , m_readOperationTimeoutTimer(*this, &Storage::cancelAllReadOperations)
222     , m_writeOperationDispatchTimer(*this, &Storage::dispatchPendingWriteOperations)
223     , m_ioQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage", WorkQueue::Type::Concurrent))
224     , m_backgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.background", WorkQueue::Type::Concurrent, WorkQueue::QOS::Background))
225     , m_serialBackgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.serialBackground", WorkQueue::Type::Serial, WorkQueue::QOS::Background))
226     , m_blobStorage(makeBlobDirectoryPath(baseDirectoryPath), m_salt)
227 {
228     deleteOldVersions();
229     synchronize();
230 }
231
232 Storage::~Storage()
233 {
234     ASSERT(RunLoop::isMain());
235     ASSERT(m_activeReadOperations.isEmpty());
236     ASSERT(m_activeWriteOperations.isEmpty());
237     ASSERT(m_activeTraverseOperations.isEmpty());
238     ASSERT(!m_synchronizationInProgress);
239     ASSERT(!m_shrinkInProgress);
240 }
241
242 String Storage::basePath() const
243 {
244     return m_basePath.isolatedCopy();
245 }
246
247 String Storage::versionPath() const
248 {
249     return makeVersionedDirectoryPath(basePath());
250 }
251
252 String Storage::recordsPath() const
253 {
254     return m_recordsPath.isolatedCopy();
255 }
256
257 size_t Storage::approximateSize() const
258 {
259     return m_approximateRecordsSize + m_blobStorage.approximateSize();
260 }
261
262 void Storage::synchronize()
263 {
264     ASSERT(RunLoop::isMain());
265
266     if (m_synchronizationInProgress || m_shrinkInProgress)
267         return;
268     m_synchronizationInProgress = true;
269
270     LOG(NetworkCacheStorage, "(NetworkProcess) synchronizing cache");
271
272     backgroundIOQueue().dispatch([this, protectedThis = makeRef(*this)] () mutable {
273         auto recordFilter = std::make_unique<ContentsFilter>();
274         auto blobFilter = std::make_unique<ContentsFilter>();
275         size_t recordsSize = 0;
276         unsigned count = 0;
277         String anyType;
278         traverseRecordsFiles(recordsPath(), anyType, [&recordFilter, &blobFilter, &recordsSize, &count](const String& fileName, const String& hashString, const String& type, bool isBlob, const String& recordDirectoryPath) {
279             auto filePath = WebCore::FileSystem::pathByAppendingComponent(recordDirectoryPath, fileName);
280
281             Key::HashType hash;
282             if (!Key::stringToHash(hashString, hash)) {
283                 WebCore::FileSystem::deleteFile(filePath);
284                 return;
285             }
286             long long fileSize = 0;
287             WebCore::FileSystem::getFileSize(filePath, fileSize);
288             if (!fileSize) {
289                 WebCore::FileSystem::deleteFile(filePath);
290                 return;
291             }
292
293             if (isBlob) {
294                 blobFilter->add(hash);
295                 return;
296             }
297
298             recordFilter->add(hash);
299             recordsSize += fileSize;
300             ++count;
301         });
302
303         RunLoop::main().dispatch([this, recordFilter = WTFMove(recordFilter), blobFilter = WTFMove(blobFilter), recordsSize]() mutable {
304             for (auto& recordFilterKey : m_recordFilterHashesAddedDuringSynchronization)
305                 recordFilter->add(recordFilterKey);
306             m_recordFilterHashesAddedDuringSynchronization.clear();
307
308             for (auto& hash : m_blobFilterHashesAddedDuringSynchronization)
309                 blobFilter->add(hash);
310             m_blobFilterHashesAddedDuringSynchronization.clear();
311
312             m_recordFilter = WTFMove(recordFilter);
313             m_blobFilter = WTFMove(blobFilter);
314             m_approximateRecordsSize = recordsSize;
315             m_synchronizationInProgress = false;
316         });
317
318         m_blobStorage.synchronize();
319
320         deleteEmptyRecordsDirectories(recordsPath());
321
322         LOG(NetworkCacheStorage, "(NetworkProcess) cache synchronization completed size=%zu count=%u", recordsSize, count);
323
324         RunLoop::main().dispatch([protectedThis = WTFMove(protectedThis)] { });
325     });
326 }
327
328 void Storage::addToRecordFilter(const Key& key)
329 {
330     ASSERT(RunLoop::isMain());
331
332     if (m_recordFilter)
333         m_recordFilter->add(key.hash());
334
335     // If we get new entries during filter synchronization take care to add them to the new filter as well.
336     if (m_synchronizationInProgress)
337         m_recordFilterHashesAddedDuringSynchronization.append(key.hash());
338 }
339
340 bool Storage::mayContain(const Key& key) const
341 {
342     ASSERT(RunLoop::isMain());
343     return !m_recordFilter || m_recordFilter->mayContain(key.hash());
344 }
345
346 bool Storage::mayContainBlob(const Key& key) const
347 {
348     ASSERT(RunLoop::isMain());
349     return !m_blobFilter || m_blobFilter->mayContain(key.hash());
350 }
351
352 String Storage::recordDirectoryPathForKey(const Key& key) const
353 {
354     ASSERT(!key.type().isEmpty());
355     return WebCore::FileSystem::pathByAppendingComponent(WebCore::FileSystem::pathByAppendingComponent(recordsPath(), key.partitionHashAsString()), key.type());
356 }
357
358 String Storage::recordPathForKey(const Key& key) const
359 {
360     return WebCore::FileSystem::pathByAppendingComponent(recordDirectoryPathForKey(key), key.hashAsString());
361 }
362
363 static String blobPathForRecordPath(const String& recordPath)
364 {
365     return recordPath + blobSuffix;
366 }
367
368 String Storage::blobPathForKey(const Key& key) const
369 {
370     return blobPathForRecordPath(recordPathForKey(key));
371 }
372
373 struct RecordMetaData {
374     RecordMetaData() { }
375     explicit RecordMetaData(const Key& key)
376         : cacheStorageVersion(Storage::version)
377         , key(key)
378     { }
379
380     unsigned cacheStorageVersion;
381     Key key;
382     std::chrono::system_clock::time_point timeStamp;
383     SHA1::Digest headerHash;
384     uint64_t headerSize { 0 };
385     SHA1::Digest bodyHash;
386     uint64_t bodySize { 0 };
387     bool isBodyInline { false };
388
389     // Not encoded as a field. Header starts immediately after meta data.
390     uint64_t headerOffset { 0 };
391 };
392
393 static bool decodeRecordMetaData(RecordMetaData& metaData, const Data& fileData)
394 {
395     bool success = false;
396     fileData.apply([&metaData, &success](const uint8_t* data, size_t size) {
397         WTF::Persistence::Decoder decoder(data, size);
398         if (!decoder.decode(metaData.cacheStorageVersion))
399             return false;
400         if (!decoder.decode(metaData.key))
401             return false;
402         if (!decoder.decode(metaData.timeStamp))
403             return false;
404         if (!decoder.decode(metaData.headerHash))
405             return false;
406         if (!decoder.decode(metaData.headerSize))
407             return false;
408         if (!decoder.decode(metaData.bodyHash))
409             return false;
410         if (!decoder.decode(metaData.bodySize))
411             return false;
412         if (!decoder.decode(metaData.isBodyInline))
413             return false;
414         if (!decoder.verifyChecksum())
415             return false;
416         metaData.headerOffset = decoder.currentOffset();
417         success = true;
418         return false;
419     });
420     return success;
421 }
422
423 static bool decodeRecordHeader(const Data& fileData, RecordMetaData& metaData, Data& headerData, const Salt& salt)
424 {
425     if (!decodeRecordMetaData(metaData, fileData)) {
426         LOG(NetworkCacheStorage, "(NetworkProcess) meta data decode failure");
427         return false;
428     }
429
430     if (metaData.cacheStorageVersion != Storage::version) {
431         LOG(NetworkCacheStorage, "(NetworkProcess) version mismatch");
432         return false;
433     }
434
435     headerData = fileData.subrange(metaData.headerOffset, metaData.headerSize);
436     if (metaData.headerHash != computeSHA1(headerData, salt)) {
437         LOG(NetworkCacheStorage, "(NetworkProcess) header checksum mismatch");
438         return false;
439     }
440     return true;
441 }
442
443 void Storage::readRecord(ReadOperation& readOperation, const Data& recordData)
444 {
445     ASSERT(!RunLoop::isMain());
446
447     RecordMetaData metaData;
448     Data headerData;
449     if (!decodeRecordHeader(recordData, metaData, headerData, m_salt))
450         return;
451
452     if (metaData.key != readOperation.key)
453         return;
454
455     // Sanity check against time stamps in future.
456     if (metaData.timeStamp > std::chrono::system_clock::now())
457         return;
458
459     Data bodyData;
460     if (metaData.isBodyInline) {
461         size_t bodyOffset = metaData.headerOffset + headerData.size();
462         if (bodyOffset + metaData.bodySize != recordData.size())
463             return;
464         bodyData = recordData.subrange(bodyOffset, metaData.bodySize);
465         if (metaData.bodyHash != computeSHA1(bodyData, m_salt))
466             return;
467     }
468
469     readOperation.expectedBodyHash = metaData.bodyHash;
470     readOperation.resultRecord = std::make_unique<Storage::Record>(Storage::Record {
471         metaData.key,
472         metaData.timeStamp,
473         headerData,
474         bodyData,
475         metaData.bodyHash
476     });
477 }
478
479 static Data encodeRecordMetaData(const RecordMetaData& metaData)
480 {
481     WTF::Persistence::Encoder encoder;
482
483     encoder << metaData.cacheStorageVersion;
484     encoder << metaData.key;
485     encoder << metaData.timeStamp;
486     encoder << metaData.headerHash;
487     encoder << metaData.headerSize;
488     encoder << metaData.bodyHash;
489     encoder << metaData.bodySize;
490     encoder << metaData.isBodyInline;
491
492     encoder.encodeChecksum();
493
494     return Data(encoder.buffer(), encoder.bufferSize());
495 }
496
497 std::optional<BlobStorage::Blob> Storage::storeBodyAsBlob(WriteOperation& writeOperation)
498 {
499     auto blobPath = blobPathForKey(writeOperation.record.key);
500
501     // Store the body.
502     auto blob = m_blobStorage.add(blobPath, writeOperation.record.body);
503     if (blob.data.isNull())
504         return { };
505
506     ++writeOperation.activeCount;
507
508     RunLoop::main().dispatch([this, blob, &writeOperation] {
509         if (m_blobFilter)
510             m_blobFilter->add(writeOperation.record.key.hash());
511         if (m_synchronizationInProgress)
512             m_blobFilterHashesAddedDuringSynchronization.append(writeOperation.record.key.hash());
513
514         if (writeOperation.mappedBodyHandler)
515             writeOperation.mappedBodyHandler(blob.data);
516
517         finishWriteOperation(writeOperation);
518     });
519     return blob;
520 }
521
522 Data Storage::encodeRecord(const Record& record, std::optional<BlobStorage::Blob> blob)
523 {
524     ASSERT(!blob || bytesEqual(blob.value().data, record.body));
525
526     RecordMetaData metaData(record.key);
527     metaData.timeStamp = record.timeStamp;
528     metaData.headerHash = computeSHA1(record.header, m_salt);
529     metaData.headerSize = record.header.size();
530     metaData.bodyHash = blob ? blob.value().hash : computeSHA1(record.body, m_salt);
531     metaData.bodySize = record.body.size();
532     metaData.isBodyInline = !blob;
533
534     auto encodedMetaData = encodeRecordMetaData(metaData);
535     auto headerData = concatenate(encodedMetaData, record.header);
536
537     if (metaData.isBodyInline)
538         return concatenate(headerData, record.body);
539
540     return { headerData };
541 }
542
543 void Storage::removeFromPendingWriteOperations(const Key& key)
544 {
545     while (true) {
546         auto found = m_pendingWriteOperations.findIf([&key](auto& operation) {
547             return operation->record.key == key;
548         });
549
550         if (found == m_pendingWriteOperations.end())
551             break;
552
553         m_pendingWriteOperations.remove(found);
554     }
555 }
556
557 void Storage::remove(const Key& key)
558 {
559     ASSERT(RunLoop::isMain());
560
561     if (!mayContain(key))
562         return;
563
564     auto protectedThis = makeRef(*this);
565
566     // We can't remove the key from the Bloom filter (but some false positives are expected anyway).
567     // For simplicity we also don't reduce m_approximateSize on removals.
568     // The next synchronization will update everything.
569
570     removeFromPendingWriteOperations(key);
571
572     serialBackgroundIOQueue().dispatch([this, protectedThis = WTFMove(protectedThis), key] () mutable {
573         deleteFiles(key);
574         RunLoop::main().dispatch([protectedThis = WTFMove(protectedThis)] { });
575     });
576 }
577
578 void Storage::remove(const Vector<Key>& keys, Function<void ()>&& completionHandler)
579 {
580     ASSERT(RunLoop::isMain());
581
582     Vector<Key> keysToRemove;
583     keysToRemove.reserveInitialCapacity(keys.size());
584
585     for (auto& key : keys) {
586         if (!mayContain(key))
587             continue;
588         removeFromPendingWriteOperations(key);
589         keysToRemove.uncheckedAppend(key);
590     }
591
592     serialBackgroundIOQueue().dispatch([this, protectedThis = makeRef(*this), keysToRemove = WTFMove(keysToRemove), completionHandler = WTFMove(completionHandler)] () mutable {
593         for (auto& key : keysToRemove)
594             deleteFiles(key);
595
596         RunLoop::main().dispatch([protectedThis = WTFMove(protectedThis), completionHandler = WTFMove(completionHandler)] {
597             if (completionHandler)
598                 completionHandler();
599         });
600     });
601 }
602
603 void Storage::deleteFiles(const Key& key)
604 {
605     ASSERT(!RunLoop::isMain());
606
607     WebCore::FileSystem::deleteFile(recordPathForKey(key));
608     m_blobStorage.remove(blobPathForKey(key));
609 }
610
611 void Storage::updateFileModificationTime(const String& path)
612 {
613     serialBackgroundIOQueue().dispatch([path = path.isolatedCopy()] {
614         updateFileModificationTimeIfNeeded(path);
615     });
616 }
617
618 void Storage::dispatchReadOperation(std::unique_ptr<ReadOperation> readOperationPtr)
619 {
620     ASSERT(RunLoop::isMain());
621
622     auto& readOperation = *readOperationPtr;
623     m_activeReadOperations.add(WTFMove(readOperationPtr));
624
625     // Avoid randomness during testing.
626     if (m_mode != Mode::Testing) {
627         // I/O pressure may make disk operations slow. If they start taking very long time we rather go to network.
628         const Seconds readTimeout = 1500_ms;
629         m_readOperationTimeoutTimer.startOneShot(readTimeout);
630     }
631
632     bool shouldGetBodyBlob = mayContainBlob(readOperation.key);
633
634     ioQueue().dispatch([this, &readOperation, shouldGetBodyBlob] {
635         auto recordPath = recordPathForKey(readOperation.key);
636
637         ++readOperation.activeCount;
638         if (shouldGetBodyBlob)
639             ++readOperation.activeCount;
640
641         auto channel = IOChannel::open(recordPath, IOChannel::Type::Read);
642         channel->read(0, std::numeric_limits<size_t>::max(), &ioQueue(), [this, &readOperation](const Data& fileData, int error) {
643             if (!error)
644                 readRecord(readOperation, fileData);
645             finishReadOperation(readOperation);
646         });
647
648         if (shouldGetBodyBlob) {
649             // Read the blob in parallel with the record read.
650             auto blobPath = blobPathForKey(readOperation.key);
651             readOperation.resultBodyBlob = m_blobStorage.get(blobPath);
652             finishReadOperation(readOperation);
653         }
654     });
655 }
656
657 void Storage::finishReadOperation(ReadOperation& readOperation)
658 {
659     ASSERT(readOperation.activeCount);
660     // Record and blob reads must finish.
661     if (--readOperation.activeCount)
662         return;
663
664     RunLoop::main().dispatch([this, &readOperation] {
665         bool success = readOperation.finish();
666         if (success)
667             updateFileModificationTime(recordPathForKey(readOperation.key));
668         else if (!readOperation.isCanceled)
669             remove(readOperation.key);
670
671         auto protectedThis = makeRef(*this);
672
673         ASSERT(m_activeReadOperations.contains(&readOperation));
674         m_activeReadOperations.remove(&readOperation);
675
676         if (m_activeReadOperations.isEmpty())
677             m_readOperationTimeoutTimer.stop();
678         
679         dispatchPendingReadOperations();
680
681         LOG(NetworkCacheStorage, "(NetworkProcess) read complete success=%d", success);
682     });
683 }
684
685 void Storage::cancelAllReadOperations()
686 {
687     ASSERT(RunLoop::isMain());
688
689     for (auto& readOperation : m_activeReadOperations)
690         readOperation->cancel();
691
692     size_t pendingCount = 0;
693     for (int priority = maximumRetrievePriority; priority >= 0; --priority) {
694         auto& pendingRetrieveQueue = m_pendingReadOperationsByPriority[priority];
695         pendingCount += pendingRetrieveQueue.size();
696         for (auto it = pendingRetrieveQueue.rbegin(), end = pendingRetrieveQueue.rend(); it != end; ++it)
697             (*it)->cancel();
698         pendingRetrieveQueue.clear();
699     }
700
701     LOG(NetworkCacheStorage, "(NetworkProcess) retrieve timeout, canceled %u active and %zu pending", m_activeReadOperations.size(), pendingCount);
702 }
703
704 void Storage::dispatchPendingReadOperations()
705 {
706     ASSERT(RunLoop::isMain());
707
708     const int maximumActiveReadOperationCount = 5;
709
710     for (int priority = maximumRetrievePriority; priority >= 0; --priority) {
711         if (m_activeReadOperations.size() > maximumActiveReadOperationCount) {
712             LOG(NetworkCacheStorage, "(NetworkProcess) limiting parallel retrieves");
713             return;
714         }
715         auto& pendingRetrieveQueue = m_pendingReadOperationsByPriority[priority];
716         if (pendingRetrieveQueue.isEmpty())
717             continue;
718         dispatchReadOperation(pendingRetrieveQueue.takeLast());
719     }
720 }
721
722 template <class T> bool retrieveFromMemory(const T& operations, const Key& key, Storage::RetrieveCompletionHandler& completionHandler)
723 {
724     for (auto& operation : operations) {
725         if (operation->record.key == key) {
726             LOG(NetworkCacheStorage, "(NetworkProcess) found write operation in progress");
727             RunLoop::main().dispatch([record = operation->record, completionHandler = WTFMove(completionHandler)] {
728                 completionHandler(std::make_unique<Storage::Record>(record));
729             });
730             return true;
731         }
732     }
733     return false;
734 }
735
736 void Storage::dispatchPendingWriteOperations()
737 {
738     ASSERT(RunLoop::isMain());
739
740     const int maximumActiveWriteOperationCount { 1 };
741
742     while (!m_pendingWriteOperations.isEmpty()) {
743         if (m_activeWriteOperations.size() >= maximumActiveWriteOperationCount) {
744             LOG(NetworkCacheStorage, "(NetworkProcess) limiting parallel writes");
745             return;
746         }
747         dispatchWriteOperation(m_pendingWriteOperations.takeLast());
748     }
749 }
750
751 static bool shouldStoreBodyAsBlob(const Data& bodyData)
752 {
753     const size_t maximumInlineBodySize { 16 * 1024 };
754     return bodyData.size() > maximumInlineBodySize;
755 }
756
757 void Storage::dispatchWriteOperation(std::unique_ptr<WriteOperation> writeOperationPtr)
758 {
759     ASSERT(RunLoop::isMain());
760
761     auto& writeOperation = *writeOperationPtr;
762     m_activeWriteOperations.add(WTFMove(writeOperationPtr));
763
764     // This was added already when starting the store but filter might have been wiped.
765     addToRecordFilter(writeOperation.record.key);
766
767     backgroundIOQueue().dispatch([this, &writeOperation] {
768         auto recordDirectorPath = recordDirectoryPathForKey(writeOperation.record.key);
769         auto recordPath = recordPathForKey(writeOperation.record.key);
770
771         WebCore::FileSystem::makeAllDirectories(recordDirectorPath);
772
773         ++writeOperation.activeCount;
774
775         bool shouldStoreAsBlob = shouldStoreBodyAsBlob(writeOperation.record.body);
776         auto blob = shouldStoreAsBlob ? storeBodyAsBlob(writeOperation) : std::nullopt;
777
778         auto recordData = encodeRecord(writeOperation.record, blob);
779
780         auto channel = IOChannel::open(recordPath, IOChannel::Type::Create);
781         size_t recordSize = recordData.size();
782         channel->write(0, recordData, nullptr, [this, &writeOperation, recordSize](int error) {
783             // On error the entry still stays in the contents filter until next synchronization.
784             m_approximateRecordsSize += recordSize;
785             finishWriteOperation(writeOperation);
786
787             LOG(NetworkCacheStorage, "(NetworkProcess) write complete error=%d", error);
788         });
789     });
790 }
791
792 void Storage::finishWriteOperation(WriteOperation& writeOperation)
793 {
794     ASSERT(RunLoop::isMain());
795     ASSERT(writeOperation.activeCount);
796     ASSERT(m_activeWriteOperations.contains(&writeOperation));
797
798     if (--writeOperation.activeCount)
799         return;
800
801     auto protectedThis = makeRef(*this);
802
803     m_activeWriteOperations.remove(&writeOperation);
804     dispatchPendingWriteOperations();
805
806     shrinkIfNeeded();
807 }
808
809 void Storage::retrieve(const Key& key, unsigned priority, RetrieveCompletionHandler&& completionHandler)
810 {
811     ASSERT(RunLoop::isMain());
812     ASSERT(priority <= maximumRetrievePriority);
813     ASSERT(!key.isNull());
814
815     if (!m_capacity) {
816         completionHandler(nullptr);
817         return;
818     }
819
820     if (!mayContain(key)) {
821         completionHandler(nullptr);
822         return;
823     }
824
825     if (retrieveFromMemory(m_pendingWriteOperations, key, completionHandler))
826         return;
827     if (retrieveFromMemory(m_activeWriteOperations, key, completionHandler))
828         return;
829
830     auto readOperation = std::make_unique<ReadOperation>(*this, key, WTFMove(completionHandler));
831     m_pendingReadOperationsByPriority[priority].prepend(WTFMove(readOperation));
832     dispatchPendingReadOperations();
833 }
834
835 void Storage::store(const Record& record, MappedBodyHandler&& mappedBodyHandler)
836 {
837     ASSERT(RunLoop::isMain());
838     ASSERT(!record.key.isNull());
839
840     if (!m_capacity)
841         return;
842
843     auto writeOperation = std::make_unique<WriteOperation>(*this, record, WTFMove(mappedBodyHandler));
844     m_pendingWriteOperations.prepend(WTFMove(writeOperation));
845
846     // Add key to the filter already here as we do lookups from the pending operations too.
847     addToRecordFilter(record.key);
848
849     bool isInitialWrite = m_pendingWriteOperations.size() == 1;
850     if (!isInitialWrite)
851         return;
852
853     m_writeOperationDispatchTimer.startOneShot(m_initialWriteDelay);
854 }
855
856 void Storage::traverse(const String& type, TraverseFlags flags, TraverseHandler&& traverseHandler)
857 {
858     ASSERT(RunLoop::isMain());
859     ASSERT(traverseHandler);
860     // Avoid non-thread safe Function copies.
861
862     auto traverseOperationPtr = std::make_unique<TraverseOperation>(*this, type, flags, WTFMove(traverseHandler));
863     auto& traverseOperation = *traverseOperationPtr;
864     m_activeTraverseOperations.add(WTFMove(traverseOperationPtr));
865
866     ioQueue().dispatch([this, &traverseOperation] {
867         traverseRecordsFiles(recordsPath(), traverseOperation.type, [this, &traverseOperation](const String& fileName, const String& hashString, const String& type, bool isBlob, const String& recordDirectoryPath) {
868             ASSERT(type == traverseOperation.type || traverseOperation.type.isEmpty());
869             if (isBlob)
870                 return;
871
872             auto recordPath = WebCore::FileSystem::pathByAppendingComponent(recordDirectoryPath, fileName);
873
874             double worth = -1;
875             if (traverseOperation.flags & TraverseFlag::ComputeWorth)
876                 worth = computeRecordWorth(fileTimes(recordPath));
877             unsigned bodyShareCount = 0;
878             if (traverseOperation.flags & TraverseFlag::ShareCount)
879                 bodyShareCount = m_blobStorage.shareCount(blobPathForRecordPath(recordPath));
880
881             std::unique_lock<Lock> lock(traverseOperation.activeMutex);
882             ++traverseOperation.activeCount;
883
884             auto channel = IOChannel::open(recordPath, IOChannel::Type::Read);
885             channel->read(0, std::numeric_limits<size_t>::max(), nullptr, [this, &traverseOperation, worth, bodyShareCount](Data& fileData, int) {
886                 RecordMetaData metaData;
887                 Data headerData;
888                 if (decodeRecordHeader(fileData, metaData, headerData, m_salt)) {
889                     Record record {
890                         metaData.key,
891                         metaData.timeStamp,
892                         headerData,
893                         { },
894                         metaData.bodyHash
895                     };
896                     RecordInfo info {
897                         static_cast<size_t>(metaData.bodySize),
898                         worth,
899                         bodyShareCount,
900                         String::fromUTF8(SHA1::hexDigest(metaData.bodyHash))
901                     };
902                     traverseOperation.handler(&record, info);
903                 }
904
905                 std::lock_guard<Lock> lock(traverseOperation.activeMutex);
906                 --traverseOperation.activeCount;
907                 traverseOperation.activeCondition.notifyOne();
908             });
909
910             const unsigned maximumParallelReadCount = 5;
911             traverseOperation.activeCondition.wait(lock, [&traverseOperation] {
912                 return traverseOperation.activeCount <= maximumParallelReadCount;
913             });
914         });
915         {
916             // Wait for all reads to finish.
917             std::unique_lock<Lock> lock(traverseOperation.activeMutex);
918             traverseOperation.activeCondition.wait(lock, [&traverseOperation] {
919                 return !traverseOperation.activeCount;
920             });
921         }
922         RunLoop::main().dispatch([this, &traverseOperation] {
923             traverseOperation.handler(nullptr, { });
924
925             auto protectedThis = makeRef(*this);
926
927             m_activeTraverseOperations.remove(&traverseOperation);
928         });
929     });
930 }
931
932 void Storage::setCapacity(size_t capacity)
933 {
934     ASSERT(RunLoop::isMain());
935
936 #if !ASSERT_DISABLED
937     const size_t assumedAverageRecordSize = 50 << 10;
938     size_t maximumRecordCount = capacity / assumedAverageRecordSize;
939     // ~10 bits per element are required for <1% false positive rate.
940     size_t effectiveBloomFilterCapacity = ContentsFilter::tableSize / 10;
941     // If this gets hit it might be time to increase the filter size.
942     ASSERT(maximumRecordCount < effectiveBloomFilterCapacity);
943 #endif
944
945     m_capacity = capacity;
946
947     shrinkIfNeeded();
948 }
949
950 void Storage::clear(const String& type, std::chrono::system_clock::time_point modifiedSinceTime, Function<void ()>&& completionHandler)
951 {
952     ASSERT(RunLoop::isMain());
953     LOG(NetworkCacheStorage, "(NetworkProcess) clearing cache");
954
955     if (m_recordFilter)
956         m_recordFilter->clear();
957     if (m_blobFilter)
958         m_blobFilter->clear();
959     m_approximateRecordsSize = 0;
960
961     ioQueue().dispatch([this, protectedThis = makeRef(*this), modifiedSinceTime, completionHandler = WTFMove(completionHandler), type = type.isolatedCopy()] () mutable {
962         auto recordsPath = this->recordsPath();
963         traverseRecordsFiles(recordsPath, type, [modifiedSinceTime](const String& fileName, const String& hashString, const String& type, bool isBlob, const String& recordDirectoryPath) {
964             auto filePath = WebCore::FileSystem::pathByAppendingComponent(recordDirectoryPath, fileName);
965             if (modifiedSinceTime > std::chrono::system_clock::time_point::min()) {
966                 auto times = fileTimes(filePath);
967                 if (times.modification < modifiedSinceTime)
968                     return;
969             }
970             WebCore::FileSystem::deleteFile(filePath);
971         });
972
973         deleteEmptyRecordsDirectories(recordsPath);
974
975         // This cleans unreferenced blobs.
976         m_blobStorage.synchronize();
977
978         RunLoop::main().dispatch([protectedThis = WTFMove(protectedThis), completionHandler = WTFMove(completionHandler)] {
979             if (completionHandler)
980                 completionHandler();
981         });
982     });
983 }
984
985 static double computeRecordWorth(FileTimes times)
986 {
987     using namespace std::chrono;
988     using namespace std::literals::chrono_literals;
989
990     auto age = system_clock::now() - times.creation;
991     // File modification time is updated manually on cache read. We don't use access time since OS may update it automatically.
992     auto accessAge = times.modification - times.creation;
993
994     // For sanity.
995     if (age <= 0s || accessAge < 0s || accessAge > age)
996         return 0;
997
998     // We like old entries that have been accessed recently.
999     return duration<double>(accessAge) / age;
1000 }
1001
1002 static double deletionProbability(FileTimes times, unsigned bodyShareCount)
1003 {
1004     static const double maximumProbability { 0.33 };
1005     static const unsigned maximumEffectiveShareCount { 5 };
1006
1007     auto worth = computeRecordWorth(times);
1008
1009     // Adjust a bit so the most valuable entries don't get deleted at all.
1010     auto effectiveWorth = std::min(1.1 * worth, 1.);
1011
1012     auto probability =  (1 - effectiveWorth) * maximumProbability;
1013
1014     // It is less useful to remove an entry that shares its body data.
1015     if (bodyShareCount)
1016         probability /= std::min(bodyShareCount, maximumEffectiveShareCount);
1017
1018     return probability;
1019 }
1020
1021 void Storage::shrinkIfNeeded()
1022 {
1023     ASSERT(RunLoop::isMain());
1024
1025     // Avoid randomness caused by cache shrinks.
1026     if (m_mode == Mode::Testing)
1027         return;
1028
1029     if (approximateSize() > m_capacity)
1030         shrink();
1031 }
1032
1033 void Storage::shrink()
1034 {
1035     ASSERT(RunLoop::isMain());
1036
1037     if (m_shrinkInProgress || m_synchronizationInProgress)
1038         return;
1039     m_shrinkInProgress = true;
1040
1041     LOG(NetworkCacheStorage, "(NetworkProcess) shrinking cache approximateSize=%zu capacity=%zu", approximateSize(), m_capacity);
1042
1043     backgroundIOQueue().dispatch([this, protectedThis = makeRef(*this)] () mutable {
1044         auto recordsPath = this->recordsPath();
1045         String anyType;
1046         traverseRecordsFiles(recordsPath, anyType, [this](const String& fileName, const String& hashString, const String& type, bool isBlob, const String& recordDirectoryPath) {
1047             if (isBlob)
1048                 return;
1049
1050             auto recordPath = WebCore::FileSystem::pathByAppendingComponent(recordDirectoryPath, fileName);
1051             auto blobPath = blobPathForRecordPath(recordPath);
1052
1053             auto times = fileTimes(recordPath);
1054             unsigned bodyShareCount = m_blobStorage.shareCount(blobPath);
1055             auto probability = deletionProbability(times, bodyShareCount);
1056
1057             bool shouldDelete = randomNumber() < probability;
1058
1059             LOG(NetworkCacheStorage, "Deletion probability=%f bodyLinkCount=%d shouldDelete=%d", probability, bodyShareCount, shouldDelete);
1060
1061             if (shouldDelete) {
1062                 WebCore::FileSystem::deleteFile(recordPath);
1063                 m_blobStorage.remove(blobPath);
1064             }
1065         });
1066
1067         RunLoop::main().dispatch([this, protectedThis = WTFMove(protectedThis)] {
1068             m_shrinkInProgress = false;
1069             // We could synchronize during the shrink traversal. However this is fast and it is better to have just one code path.
1070             synchronize();
1071         });
1072
1073         LOG(NetworkCacheStorage, "(NetworkProcess) cache shrink completed");
1074     });
1075 }
1076
1077 void Storage::deleteOldVersions()
1078 {
1079     backgroundIOQueue().dispatch([this, protectedThis = makeRef(*this)] () mutable {
1080         auto cachePath = basePath();
1081         traverseDirectory(cachePath, [&cachePath](const String& subdirName, DirectoryEntryType type) {
1082             if (type != DirectoryEntryType::Directory)
1083                 return;
1084             if (!subdirName.startsWith(versionDirectoryPrefix))
1085                 return;
1086             auto versionString = subdirName.substring(strlen(versionDirectoryPrefix));
1087             bool success;
1088             unsigned directoryVersion = versionString.toUIntStrict(&success);
1089             if (!success)
1090                 return;
1091             if (directoryVersion >= version)
1092                 return;
1093 #if PLATFORM(MAC)
1094             if (directoryVersion == lastStableVersion)
1095                 return;
1096 #endif
1097
1098             auto oldVersionPath = WebCore::FileSystem::pathByAppendingComponent(cachePath, subdirName);
1099             LOG(NetworkCacheStorage, "(NetworkProcess) deleting old cache version, path %s", oldVersionPath.utf8().data());
1100
1101             deleteDirectoryRecursively(oldVersionPath);
1102         });
1103
1104         RunLoop::main().dispatch([protectedThis = WTFMove(protectedThis)] { });
1105     });
1106 }
1107
1108 }
1109 }