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