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