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