0f7fd3bdf7a0575710c5f96a31ec42faf8944a93
[WebKit-https.git] / Source / WebKit2 / NetworkProcess / cache / NetworkCacheStorage.cpp
1 /*
2  * Copyright (C) 2014-2015 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 #if ENABLE(NETWORK_CACHE)
30
31 #include "Logging.h"
32 #include "NetworkCacheCoders.h"
33 #include "NetworkCacheFileSystemPosix.h"
34 #include "NetworkCacheIOChannel.h"
35 #include <wtf/PageBlock.h>
36 #include <wtf/RandomNumber.h>
37 #include <wtf/RunLoop.h>
38 #include <wtf/text/CString.h>
39 #include <wtf/text/StringBuilder.h>
40
41 namespace WebKit {
42 namespace NetworkCache {
43
44 static const char networkCacheSubdirectory[] = "WebKitCache";
45 static const char versionDirectoryPrefix[] = "Version ";
46 static const char recordsDirectoryName[] = "Records";
47 static const char blobsDirectoryName[] = "Blobs";
48 static const char bodyPostfix[] = "-body";
49
50 static double computeRecordWorth(FileTimes);
51
52 std::unique_ptr<Storage> Storage::open(const String& cachePath)
53 {
54     ASSERT(RunLoop::isMain());
55
56     String networkCachePath = WebCore::pathByAppendingComponent(cachePath, networkCacheSubdirectory);
57     if (!WebCore::makeAllDirectories(networkCachePath))
58         return nullptr;
59     return std::unique_ptr<Storage>(new Storage(networkCachePath));
60 }
61
62 static String makeVersionedDirectoryPath(const String& baseDirectoryPath)
63 {
64     String versionSubdirectory = versionDirectoryPrefix + String::number(Storage::version);
65     return WebCore::pathByAppendingComponent(baseDirectoryPath, versionSubdirectory);
66 }
67
68 static String makeRecordDirectoryPath(const String& baseDirectoryPath)
69 {
70     return WebCore::pathByAppendingComponent(makeVersionedDirectoryPath(baseDirectoryPath), recordsDirectoryName);
71 }
72
73 static String makeBlobDirectoryPath(const String& baseDirectoryPath)
74 {
75     return WebCore::pathByAppendingComponent(makeVersionedDirectoryPath(baseDirectoryPath), blobsDirectoryName);
76 }
77
78 Storage::Storage(const String& baseDirectoryPath)
79     : m_baseDirectoryPath(baseDirectoryPath)
80     , m_directoryPath(makeRecordDirectoryPath(baseDirectoryPath))
81     , m_ioQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage", WorkQueue::Type::Concurrent))
82     , m_backgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.background", WorkQueue::Type::Concurrent, WorkQueue::QOS::Background))
83     , m_serialBackgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.serialBackground", WorkQueue::Type::Serial, WorkQueue::QOS::Background))
84     , m_blobStorage(makeBlobDirectoryPath(baseDirectoryPath))
85 {
86     deleteOldVersions();
87     synchronize();
88 }
89
90 size_t Storage::approximateSize() const
91 {
92     return m_approximateSize + m_blobStorage.approximateSize();
93 }
94
95 void Storage::synchronize()
96 {
97     ASSERT(RunLoop::isMain());
98
99     if (m_synchronizationInProgress || m_shrinkInProgress)
100         return;
101     m_synchronizationInProgress = true;
102
103     LOG(NetworkCacheStorage, "(NetworkProcess) synchronizing cache");
104
105     StringCapture cachePathCapture(m_directoryPath);
106     backgroundIOQueue().dispatch([this, cachePathCapture] {
107         String cachePath = cachePathCapture.string();
108
109         auto filter = std::make_unique<ContentsFilter>();
110         size_t size = 0;
111         unsigned count = 0;
112         traverseCacheFiles(cachePath, [&filter, &size, &count](const String& fileName, const String& partitionPath) {
113             Key::HashType hash;
114             if (!Key::stringToHash(fileName, hash))
115                 return;
116             auto filePath = WebCore::pathByAppendingComponent(partitionPath, fileName);
117             long long fileSize = 0;
118             WebCore::getFileSize(filePath, fileSize);
119             if (!fileSize)
120                 return;
121             filter->add(hash);
122             size += fileSize;
123             ++count;
124         });
125
126         auto* filterPtr = filter.release();
127         RunLoop::main().dispatch([this, filterPtr, size] {
128             auto filter = std::unique_ptr<ContentsFilter>(filterPtr);
129
130             for (auto hash : m_contentsFilterHashesAddedDuringSynchronization)
131                 filter->add(hash);
132             m_contentsFilterHashesAddedDuringSynchronization.clear();
133
134             m_contentsFilter = WTF::move(filter);
135             m_approximateSize = size;
136             m_synchronizationInProgress = false;
137         });
138
139         m_blobStorage.synchronize();
140
141         LOG(NetworkCacheStorage, "(NetworkProcess) cache synchronization completed size=%zu count=%d", size, count);
142     });
143 }
144
145 void Storage::addToContentsFilter(const Key& key)
146 {
147     ASSERT(RunLoop::isMain());
148
149     if (m_contentsFilter)
150         m_contentsFilter->add(key.hash());
151
152     // If we get new entries during filter synchronization take care to add them to the new filter as well.
153     if (m_synchronizationInProgress)
154         m_contentsFilterHashesAddedDuringSynchronization.append(key.hash());
155 }
156
157 bool Storage::mayContain(const Key& key) const
158 {
159     ASSERT(RunLoop::isMain());
160     return !m_contentsFilter || m_contentsFilter->mayContain(key.hash());
161 }
162
163 static String partitionPathForKey(const Key& key, const String& cachePath)
164 {
165     ASSERT(!key.partition().isEmpty());
166     return WebCore::pathByAppendingComponent(cachePath, key.partition());
167 }
168
169 static String fileNameForKey(const Key& key)
170 {
171     return key.hashAsString();
172 }
173
174 static String recordPathForKey(const Key& key, const String& cachePath)
175 {
176     return WebCore::pathByAppendingComponent(partitionPathForKey(key, cachePath), fileNameForKey(key));
177 }
178
179 static String bodyPathForRecordPath(const String& recordPath)
180 {
181     return recordPath + bodyPostfix;
182 }
183
184 static String bodyPathForKey(const Key& key, const String& cachePath)
185 {
186     return bodyPathForRecordPath(recordPathForKey(key, cachePath));
187 }
188
189 static unsigned hashData(const Data& data)
190 {
191     StringHasher hasher;
192     data.apply([&hasher](const uint8_t* data, size_t size) {
193         hasher.addCharacters(data, size);
194         return true;
195     });
196     return hasher.hash();
197 }
198
199 struct RecordMetaData {
200     RecordMetaData() { }
201     explicit RecordMetaData(const Key& key)
202         : cacheStorageVersion(Storage::version)
203         , key(key)
204     { }
205
206     unsigned cacheStorageVersion;
207     Key key;
208     // FIXME: Add encoder/decoder for time_point.
209     std::chrono::milliseconds epochRelativeTimeStamp;
210     unsigned headerChecksum;
211     uint64_t headerOffset;
212     uint64_t headerSize;
213     SHA1::Digest bodyHash;
214     uint64_t bodySize;
215 };
216
217 static bool decodeRecordMetaData(RecordMetaData& metaData, const Data& fileData)
218 {
219     bool success = false;
220     fileData.apply([&metaData, &success](const uint8_t* data, size_t size) {
221         Decoder decoder(data, size);
222         if (!decoder.decode(metaData.cacheStorageVersion))
223             return false;
224         if (!decoder.decode(metaData.key))
225             return false;
226         if (!decoder.decode(metaData.epochRelativeTimeStamp))
227             return false;
228         if (!decoder.decode(metaData.headerChecksum))
229             return false;
230         if (!decoder.decode(metaData.headerSize))
231             return false;
232         if (!decoder.decode(metaData.bodyHash))
233             return false;
234         if (!decoder.decode(metaData.bodySize))
235             return false;
236         if (!decoder.verifyChecksum())
237             return false;
238         metaData.headerOffset = decoder.currentOffset();
239         success = true;
240         return false;
241     });
242     return success;
243 }
244
245 static bool decodeRecordHeader(const Data& fileData, RecordMetaData& metaData, Data& data)
246 {
247     if (!decodeRecordMetaData(metaData, fileData)) {
248         LOG(NetworkCacheStorage, "(NetworkProcess) meta data decode failure");
249         return false;
250     }
251
252     if (metaData.cacheStorageVersion != Storage::version) {
253         LOG(NetworkCacheStorage, "(NetworkProcess) version mismatch");
254         return false;
255     }
256
257     auto headerData = fileData.subrange(metaData.headerOffset, metaData.headerSize);
258     if (metaData.headerChecksum != hashData(headerData)) {
259         LOG(NetworkCacheStorage, "(NetworkProcess) header checksum mismatch");
260         return false;
261     }
262     data = { headerData };
263     return true;
264 }
265
266 static std::unique_ptr<Storage::Record> createRecord(const Data& recordData, const BlobStorage::Blob& bodyBlob, const Key& key)
267 {
268     RecordMetaData metaData;
269     Data headerData;
270     if (!decodeRecordHeader(recordData, metaData, headerData))
271         return nullptr;
272
273     if (metaData.key != key)
274         return nullptr;
275
276     // Sanity check against time stamps in future.
277     auto timeStamp = std::chrono::system_clock::time_point(metaData.epochRelativeTimeStamp);
278     if (timeStamp > std::chrono::system_clock::now())
279         return nullptr;
280     if (metaData.bodySize != bodyBlob.data.size())
281         return nullptr;
282     if (metaData.bodyHash != bodyBlob.hash)
283         return nullptr;
284
285     return std::make_unique<Storage::Record>(Storage::Record {
286         metaData.key,
287         timeStamp,
288         headerData,
289         bodyBlob.data
290     });
291 }
292
293 static Data encodeRecordMetaData(const RecordMetaData& metaData)
294 {
295     Encoder encoder;
296
297     encoder << metaData.cacheStorageVersion;
298     encoder << metaData.key;
299     encoder << metaData.epochRelativeTimeStamp;
300     encoder << metaData.headerChecksum;
301     encoder << metaData.headerSize;
302     encoder << metaData.bodyHash;
303     encoder << metaData.bodySize;
304
305     encoder.encodeChecksum();
306
307     return Data(encoder.buffer(), encoder.bufferSize());
308 }
309
310 static Data encodeRecordHeader(const Storage::Record& record, SHA1::Digest bodyHash)
311 {
312     RecordMetaData metaData(record.key);
313     metaData.epochRelativeTimeStamp = std::chrono::duration_cast<std::chrono::milliseconds>(record.timeStamp.time_since_epoch());
314     metaData.headerChecksum = hashData(record.header);
315     metaData.headerSize = record.header.size();
316     metaData.bodyHash = bodyHash;
317     metaData.bodySize = record.body.size();
318
319     auto encodedMetaData = encodeRecordMetaData(metaData);
320     auto headerData = concatenate(encodedMetaData, record.header);
321     return { headerData };
322 }
323
324 void Storage::remove(const Key& key)
325 {
326     ASSERT(RunLoop::isMain());
327
328     // We can't remove the key from the Bloom filter (but some false positives are expected anyway).
329     // For simplicity we also don't reduce m_approximateSize on removals.
330     // The next synchronization will update everything.
331
332     StringCapture recordPathCapture(recordPathForKey(key, m_directoryPath));
333     StringCapture bodyPathCapture(bodyPathForKey(key, m_directoryPath));
334     serialBackgroundIOQueue().dispatch([this, recordPathCapture, bodyPathCapture] {
335         WebCore::deleteFile(recordPathCapture.string());
336         m_blobStorage.remove(bodyPathCapture.string());
337     });
338 }
339
340 void Storage::updateFileModificationTime(const String& path)
341 {
342     StringCapture filePathCapture(path);
343     serialBackgroundIOQueue().dispatch([filePathCapture] {
344         updateFileModificationTimeIfNeeded(filePathCapture.string());
345     });
346 }
347
348 void Storage::dispatchReadOperation(const ReadOperation& read)
349 {
350     ASSERT(RunLoop::isMain());
351     ASSERT(m_activeReadOperations.contains(&read));
352
353     StringCapture cachePathCapture(m_directoryPath);
354     ioQueue().dispatch([this, &read, cachePathCapture] {
355         auto recordPath = recordPathForKey(read.key, cachePathCapture.string());
356         auto bodyPath = bodyPathForKey(read.key, cachePathCapture.string());
357         // FIXME: Body and header retrieves can be done in parallel.
358         auto bodyBlob = m_blobStorage.get(bodyPath);
359
360         RefPtr<IOChannel> channel = IOChannel::open(recordPath, IOChannel::Type::Read);
361         channel->read(0, std::numeric_limits<size_t>::max(), [this, &read, bodyBlob](Data& fileData, int error) {
362             auto record = error ? nullptr : createRecord(fileData, bodyBlob, read.key);
363             finishReadOperation(read, WTF::move(record));
364         });
365     });
366 }
367
368 void Storage::finishReadOperation(const ReadOperation& read, std::unique_ptr<Record> record)
369 {
370     ASSERT(RunLoop::isMain());
371
372     bool success = read.completionHandler(WTF::move(record));
373     if (success)
374         updateFileModificationTime(recordPathForKey(read.key, m_directoryPath));
375     else
376         remove(read.key);
377     ASSERT(m_activeReadOperations.contains(&read));
378     m_activeReadOperations.remove(&read);
379     dispatchPendingReadOperations();
380
381     LOG(NetworkCacheStorage, "(NetworkProcess) read complete success=%d", success);
382 }
383
384 void Storage::dispatchPendingReadOperations()
385 {
386     ASSERT(RunLoop::isMain());
387
388     const int maximumActiveReadOperationCount = 5;
389
390     for (int priority = maximumRetrievePriority; priority >= 0; --priority) {
391         if (m_activeReadOperations.size() > maximumActiveReadOperationCount) {
392             LOG(NetworkCacheStorage, "(NetworkProcess) limiting parallel retrieves");
393             return;
394         }
395         auto& pendingRetrieveQueue = m_pendingReadOperationsByPriority[priority];
396         if (pendingRetrieveQueue.isEmpty())
397             continue;
398         auto readOperation = pendingRetrieveQueue.takeFirst();
399         auto& read = *readOperation;
400         m_activeReadOperations.add(WTF::move(readOperation));
401         dispatchReadOperation(read);
402     }
403 }
404
405 template <class T> bool retrieveFromMemory(const T& operations, const Key& key, Storage::RetrieveCompletionHandler& completionHandler)
406 {
407     for (auto& operation : operations) {
408         if (operation->record.key == key) {
409             LOG(NetworkCacheStorage, "(NetworkProcess) found write operation in progress");
410             auto record = operation->record;
411             RunLoop::main().dispatch([record, completionHandler] {
412                 completionHandler(std::make_unique<Storage::Record>(record));
413             });
414             return true;
415         }
416     }
417     return false;
418 }
419
420 void Storage::dispatchPendingWriteOperations()
421 {
422     ASSERT(RunLoop::isMain());
423
424     const int maximumActiveWriteOperationCount { 3 };
425
426     while (!m_pendingWriteOperations.isEmpty()) {
427         if (m_activeWriteOperations.size() >= maximumActiveWriteOperationCount) {
428             LOG(NetworkCacheStorage, "(NetworkProcess) limiting parallel writes");
429             return;
430         }
431         auto writeOperation = m_pendingWriteOperations.takeFirst();
432         auto& write = *writeOperation;
433         m_activeWriteOperations.add(WTF::move(writeOperation));
434
435         dispatchWriteOperation(write);
436     }
437 }
438
439 void Storage::dispatchWriteOperation(const WriteOperation& write)
440 {
441     ASSERT(RunLoop::isMain());
442     ASSERT(m_activeWriteOperations.contains(&write));
443
444     // This was added already when starting the store but filter might have been wiped.
445     addToContentsFilter(write.record.key);
446
447     StringCapture cachePathCapture(m_directoryPath);
448     backgroundIOQueue().dispatch([this, &write, cachePathCapture] {
449         auto partitionPath = partitionPathForKey(write.record.key, cachePathCapture.string());
450         auto recordPath = recordPathForKey(write.record.key, cachePathCapture.string());
451         auto bodyPath = bodyPathForKey(write.record.key, cachePathCapture.string());
452
453         WebCore::makeAllDirectories(partitionPath);
454
455         // Store the body.
456         auto blob = m_blobStorage.add(bodyPath, write.record.body);
457         if (blob.data.isNull()) {
458             RunLoop::main().dispatch([this, &write] {
459                 finishWriteOperation(write);
460             });
461             return;
462         }
463
464         // Tell the client we now have a disk-backed map for this data.
465         size_t minimumMapSize = pageSize();
466         if (blob.data.size() >= minimumMapSize && blob.data.isMap() && write.mappedBodyHandler) {
467             auto& mappedBodyHandler = write.mappedBodyHandler;
468             RunLoop::main().dispatch([blob, mappedBodyHandler] {
469                 mappedBodyHandler(blob.data);
470             });
471         }
472
473         // Store the header and meta data.
474         auto encodedHeader = encodeRecordHeader(write.record, blob.hash);
475         auto channel = IOChannel::open(recordPath, IOChannel::Type::Create);
476         int fd = channel->fileDescriptor();
477         size_t headerSize = encodedHeader.size();
478         channel->write(0, encodedHeader, [this, &write, headerSize, fd](int error) {
479             // On error the entry still stays in the contents filter until next synchronization.
480             m_approximateSize += headerSize;
481             finishWriteOperation(write);
482
483             LOG(NetworkCacheStorage, "(NetworkProcess) write complete error=%d", error);
484         });
485     });
486 }
487
488 void Storage::finishWriteOperation(const WriteOperation& write)
489 {
490     ASSERT(m_activeWriteOperations.contains(&write));
491     m_activeWriteOperations.remove(&write);
492     dispatchPendingWriteOperations();
493
494     shrinkIfNeeded();
495 }
496
497 void Storage::retrieve(const Key& key, unsigned priority, RetrieveCompletionHandler&& completionHandler)
498 {
499     ASSERT(RunLoop::isMain());
500     ASSERT(priority <= maximumRetrievePriority);
501     ASSERT(!key.isNull());
502
503     if (!m_capacity) {
504         completionHandler(nullptr);
505         return;
506     }
507
508     if (!mayContain(key)) {
509         completionHandler(nullptr);
510         return;
511     }
512
513     if (retrieveFromMemory(m_pendingWriteOperations, key, completionHandler))
514         return;
515     if (retrieveFromMemory(m_activeWriteOperations, key, completionHandler))
516         return;
517
518     m_pendingReadOperationsByPriority[priority].append(new ReadOperation { key, WTF::move(completionHandler) });
519     dispatchPendingReadOperations();
520 }
521
522 void Storage::store(const Record& record, MappedBodyHandler&& mappedBodyHandler)
523 {
524     ASSERT(RunLoop::isMain());
525     ASSERT(!record.key.isNull());
526
527     if (!m_capacity)
528         return;
529
530     m_pendingWriteOperations.append(new WriteOperation { record, WTF::move(mappedBodyHandler) });
531
532     // Add key to the filter already here as we do lookups from the pending operations too.
533     addToContentsFilter(record.key);
534
535     dispatchPendingWriteOperations();
536 }
537
538 void Storage::traverse(TraverseFlags flags, std::function<void (const Record*, const RecordInfo&)>&& traverseHandler)
539 {
540     StringCapture cachePathCapture(m_directoryPath);
541     ioQueue().dispatch([this, flags, cachePathCapture, traverseHandler] {
542         String cachePath = cachePathCapture.string();
543         traverseCacheFiles(cachePath, [this, flags, &traverseHandler](const String& fileName, const String& partitionPath) {
544             auto recordPath = WebCore::pathByAppendingComponent(partitionPath, fileName);
545
546             RecordInfo info;
547             if (flags & TraverseFlag::ComputeWorth)
548                 info.worth = computeRecordWorth(fileTimes(recordPath));
549             if (flags & TraverseFlag::ShareCount)
550                 info.bodyShareCount = m_blobStorage.shareCount(bodyPathForRecordPath(recordPath));
551
552             auto channel = IOChannel::open(recordPath, IOChannel::Type::Read);
553             // FIXME: Traversal is slower than it should be due to lack of parallelism.
554             channel->readSync(0, std::numeric_limits<size_t>::max(), [this, &traverseHandler, &info](Data& fileData, int) {
555                 RecordMetaData metaData;
556                 Data headerData;
557                 if (decodeRecordHeader(fileData, metaData, headerData)) {
558                     Record record { metaData.key, std::chrono::system_clock::time_point(metaData.epochRelativeTimeStamp), headerData, { } };
559                     info.bodySize = metaData.bodySize;
560                     info.bodyHash = String::fromUTF8(SHA1::hexDigest(metaData.bodyHash));
561                     traverseHandler(&record, info);
562                 }
563             });
564         });
565         RunLoop::main().dispatch([this, traverseHandler] {
566             traverseHandler(nullptr, { });
567         });
568     });
569 }
570
571 void Storage::setCapacity(size_t capacity)
572 {
573     ASSERT(RunLoop::isMain());
574
575 #if !ASSERT_DISABLED
576     const size_t assumedAverageRecordSize = 50 << 10;
577     size_t maximumRecordCount = capacity / assumedAverageRecordSize;
578     // ~10 bits per element are required for <1% false positive rate.
579     size_t effectiveBloomFilterCapacity = ContentsFilter::tableSize / 10;
580     // If this gets hit it might be time to increase the filter size.
581     ASSERT(maximumRecordCount < effectiveBloomFilterCapacity);
582 #endif
583
584     m_capacity = capacity;
585
586     shrinkIfNeeded();
587 }
588
589 void Storage::clear()
590 {
591     ASSERT(RunLoop::isMain());
592     LOG(NetworkCacheStorage, "(NetworkProcess) clearing cache");
593
594     if (m_contentsFilter)
595         m_contentsFilter->clear();
596     m_approximateSize = 0;
597
598     StringCapture directoryPathCapture(m_directoryPath);
599
600     ioQueue().dispatch([this, directoryPathCapture] {
601         String directoryPath = directoryPathCapture.string();
602         traverseDirectory(directoryPath, DT_DIR, [&directoryPath](const String& subdirName) {
603             String subdirPath = WebCore::pathByAppendingComponent(directoryPath, subdirName);
604             traverseDirectory(subdirPath, DT_REG, [&subdirPath](const String& fileName) {
605                 WebCore::deleteFile(WebCore::pathByAppendingComponent(subdirPath, fileName));
606             });
607             WebCore::deleteEmptyDirectory(subdirPath);
608         });
609
610         // This cleans unreferences blobs.
611         m_blobStorage.synchronize();
612     });
613 }
614
615 static double computeRecordWorth(FileTimes times)
616 {
617     using namespace std::chrono;
618     auto age = system_clock::now() - times.creation;
619     // File modification time is updated manually on cache read. We don't use access time since OS may update it automatically.
620     auto accessAge = times.modification - times.creation;
621
622     // For sanity.
623     if (age <= 0_s || accessAge < 0_s || accessAge > age)
624         return 0;
625
626     // We like old entries that have been accessed recently.
627     return duration<double>(accessAge) / age;
628 }
629
630 static double deletionProbability(FileTimes times, unsigned bodyShareCount)
631 {
632     static const double maximumProbability { 0.33 };
633     static const unsigned maximumEffectiveShareCount { 5 };
634
635     auto worth = computeRecordWorth(times);
636
637     // Adjust a bit so the most valuable entries don't get deleted at all.
638     auto effectiveWorth = std::min(1.1 * worth, 1.);
639
640     auto probability =  (1 - effectiveWorth) * maximumProbability;
641
642     // It is less useful to remove an entry that shares its body data.
643     if (bodyShareCount)
644         probability /= std::min(bodyShareCount, maximumEffectiveShareCount);
645
646     return probability;
647 }
648
649 void Storage::shrinkIfNeeded()
650 {
651     ASSERT(RunLoop::isMain());
652
653     if (approximateSize() > m_capacity)
654         shrink();
655 }
656
657 void Storage::shrink()
658 {
659     ASSERT(RunLoop::isMain());
660
661     if (m_shrinkInProgress || m_synchronizationInProgress)
662         return;
663     m_shrinkInProgress = true;
664
665     LOG(NetworkCacheStorage, "(NetworkProcess) shrinking cache approximateSize=%zu capacity=%zu", approximateSize(), m_capacity);
666
667     StringCapture cachePathCapture(m_directoryPath);
668     backgroundIOQueue().dispatch([this, cachePathCapture] {
669         String cachePath = cachePathCapture.string();
670         traverseCacheFiles(cachePath, [this](const String& fileName, const String& partitionPath) {
671             auto recordPath = WebCore::pathByAppendingComponent(partitionPath, fileName);
672             auto bodyPath = bodyPathForRecordPath(recordPath);
673
674             auto times = fileTimes(recordPath);
675             unsigned bodyShareCount = m_blobStorage.shareCount(bodyPath);
676             auto probability = deletionProbability(times, bodyShareCount);
677
678             bool shouldDelete = randomNumber() < probability;
679
680             LOG(NetworkCacheStorage, "Deletion probability=%f bodyLinkCount=%d shouldDelete=%d", probability, bodyShareCount, shouldDelete);
681
682             if (shouldDelete) {
683                 WebCore::deleteFile(recordPath);
684                 m_blobStorage.remove(bodyPath);
685             }
686         });
687
688         // Let system figure out if they are really empty.
689         traverseDirectory(cachePath, DT_DIR, [&cachePath](const String& subdirName) {
690             auto partitionPath = WebCore::pathByAppendingComponent(cachePath, subdirName);
691             WebCore::deleteEmptyDirectory(partitionPath);
692         });
693
694         RunLoop::main().dispatch([this] {
695             m_shrinkInProgress = false;
696             // We could synchronize during the shrink traversal. However this is fast and it is better to have just one code path.
697             synchronize();
698         });
699
700         LOG(NetworkCacheStorage, "(NetworkProcess) cache shrink completed");
701     });
702 }
703
704 void Storage::deleteOldVersions()
705 {
706     // Delete V1 cache.
707     StringCapture cachePathCapture(m_baseDirectoryPath);
708     backgroundIOQueue().dispatch([cachePathCapture] {
709         String cachePath = cachePathCapture.string();
710         traverseDirectory(cachePath, DT_DIR, [&cachePath](const String& subdirName) {
711             if (subdirName.startsWith(versionDirectoryPrefix))
712                 return;
713             String partitionPath = WebCore::pathByAppendingComponent(cachePath, subdirName);
714             traverseDirectory(partitionPath, DT_REG, [&partitionPath](const String& fileName) {
715                 WebCore::deleteFile(WebCore::pathByAppendingComponent(partitionPath, fileName));
716             });
717             WebCore::deleteEmptyDirectory(partitionPath);
718         });
719     });
720     // FIXME: Delete V2 cache.
721 }
722
723 }
724 }
725
726 #endif