Prune least valuable cache entries first
authorantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 18 Mar 2015 17:40:34 +0000 (17:40 +0000)
committerantti@apple.com <antti@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 18 Mar 2015 17:40:34 +0000 (17:40 +0000)
https://bugs.webkit.org/show_bug.cgi?id=142810
rdar://problem/19632130

Reviewed by Darin Adler.

When pruning the cache estimate relative value of each entry using formula

age = current time - creation time
accessAge = last access time - creation time
value = accessAge / age

That is, we value entries that have been accessed recently and survived in the cache longest.

The most valuable entries don't get deleted at all while the deletion probablity ramps up for
lower value entries.

* NetworkProcess/cache/NetworkCacheFileSystemPosix.h:
(WebKit::NetworkCache::fileTimes):

    Get the creation time and access time for a file.

(WebKit::NetworkCache::updateFileAccessTimeIfNeeded):

    Update access time manually if the file system doesn't do it automatically.

* NetworkProcess/cache/NetworkCacheIOChannel.h:
(WebKit::NetworkCache::IOChannel::path):
(WebKit::NetworkCache::IOChannel::type):
* NetworkProcess/cache/NetworkCacheIOChannelCocoa.mm:
(WebKit::NetworkCache::IOChannel::IOChannel):
(WebKit::NetworkCache::IOChannel::open):

    Remember the file path and move most of the work to constructor.

* NetworkProcess/cache/NetworkCacheStorage.cpp:
(WebKit::NetworkCache::Storage::Storage):
(WebKit::NetworkCache::Storage::remove):
(WebKit::NetworkCache::Storage::updateFileAccessTime):
(WebKit::NetworkCache::Storage::dispatchReadOperation):
(WebKit::NetworkCache::deletionProbability):

    Compute the probability based on entry age and access time.

(WebKit::NetworkCache::Storage::shrinkIfNeeded):
* NetworkProcess/cache/NetworkCacheStorage.h:
(WebKit::NetworkCache::Storage::serialBackgroundIOQueue):
(WebKit::NetworkCache::Storage::deleteQueue): Deleted.

    More generic name.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@181700 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebKit2/ChangeLog
Source/WebKit2/NetworkProcess/cache/NetworkCacheFileSystemPosix.h
Source/WebKit2/NetworkProcess/cache/NetworkCacheIOChannel.h
Source/WebKit2/NetworkProcess/cache/NetworkCacheIOChannelCocoa.mm
Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.cpp
Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h

index 808ac8b..842159a 100644 (file)
@@ -1,3 +1,56 @@
+2015-03-17  Antti Koivisto  <antti@apple.com>
+
+        Prune least valuable cache entries first
+        https://bugs.webkit.org/show_bug.cgi?id=142810
+        rdar://problem/19632130
+
+        Reviewed by Darin Adler.
+
+        When pruning the cache estimate relative value of each entry using formula
+
+        age = current time - creation time
+        accessAge = last access time - creation time
+        value = accessAge / age
+
+        That is, we value entries that have been accessed recently and survived in the cache longest.
+
+        The most valuable entries don't get deleted at all while the deletion probablity ramps up for
+        lower value entries.
+
+        * NetworkProcess/cache/NetworkCacheFileSystemPosix.h:
+        (WebKit::NetworkCache::fileTimes):
+
+            Get the creation time and access time for a file.
+
+        (WebKit::NetworkCache::updateFileAccessTimeIfNeeded):
+
+            Update access time manually if the file system doesn't do it automatically.
+
+        * NetworkProcess/cache/NetworkCacheIOChannel.h:
+        (WebKit::NetworkCache::IOChannel::path):
+        (WebKit::NetworkCache::IOChannel::type):
+        * NetworkProcess/cache/NetworkCacheIOChannelCocoa.mm:
+        (WebKit::NetworkCache::IOChannel::IOChannel):
+        (WebKit::NetworkCache::IOChannel::open):
+
+            Remember the file path and move most of the work to constructor.
+
+        * NetworkProcess/cache/NetworkCacheStorage.cpp:
+        (WebKit::NetworkCache::Storage::Storage):
+        (WebKit::NetworkCache::Storage::remove):
+        (WebKit::NetworkCache::Storage::updateFileAccessTime):
+        (WebKit::NetworkCache::Storage::dispatchReadOperation):
+        (WebKit::NetworkCache::deletionProbability):
+
+            Compute the probability based on entry age and access time.
+
+        (WebKit::NetworkCache::Storage::shrinkIfNeeded):
+        * NetworkProcess/cache/NetworkCacheStorage.h:
+        (WebKit::NetworkCache::Storage::serialBackgroundIOQueue):
+        (WebKit::NetworkCache::Storage::deleteQueue): Deleted.
+
+            More generic name.
+
 2015-03-18  Chris Dumez  <cdumez@apple.com>
 
         [WK2] Log total number of network cache queries using diagnostic logging
index 5748aba..ba56e3c 100644 (file)
@@ -31,6 +31,8 @@
 #include "NetworkCacheKey.h"
 #include <WebCore/FileSystem.h>
 #include <dirent.h>
+#include <sys/stat.h>
+#include <sys/time.h>
 #include <wtf/text/CString.h>
 
 namespace WebKit {
@@ -67,6 +69,31 @@ inline void traverseCacheFiles(const String& cachePath, const Function& function
     });
 }
 
+struct FileTimes {
+    std::chrono::system_clock::time_point creation;
+    std::chrono::system_clock::time_point access;
+};
+
+inline FileTimes fileTimes(const String& path)
+{
+    struct stat fileInfo;
+    if (stat(WebCore::fileSystemRepresentation(path).data(), &fileInfo))
+        return { };
+    return { std::chrono::system_clock::from_time_t(fileInfo.st_birthtime), std::chrono::system_clock::from_time_t(fileInfo.st_atime) };
+}
+
+inline void updateFileAccessTimeIfNeeded(const String& path)
+{
+    auto times = fileTimes(path);
+    if (times.creation != times.access) {
+        // Don't update more than once per hour;
+        if (std::chrono::system_clock::now() - times.access < std::chrono::hours(1))
+            return;
+    }
+    // This really updates both access time and modification time.
+    utimes(WebCore::fileSystemRepresentation(path).data(), 0);
+}
+
 }
 }
 
index fec4fae..9c4799f 100644 (file)
@@ -45,15 +45,21 @@ public:
     void readSync(size_t offset, size_t, std::function<void (Data&, int error)>);
     void write(size_t offset, const Data&, std::function<void (int error)>);
 
+    const String& path() const { return m_path; }
+    Type type() const { return m_type; }
+
     int fileDescriptor() const { return m_fileDescriptor; }
 
 private:
-    IOChannel(int fd);
+    IOChannel(const String& filePath, IOChannel::Type);
+
+    String m_path;
+    Type m_type;
 
+    int m_fileDescriptor { 0 };
 #if PLATFORM(COCOA)
     DispatchPtr<dispatch_io_t> m_dispatchIO;
 #endif
-    int m_fileDescriptor { 0 };
 };
 
 }
index a59f555..bade204 100644 (file)
 namespace WebKit {
 namespace NetworkCache {
 
-IOChannel::IOChannel(int fd)
-    : m_fileDescriptor(fd)
-{
-    m_dispatchIO = adoptDispatch(dispatch_io_create(DISPATCH_IO_RANDOM, fd, dispatch_get_main_queue(), [fd](int) {
-        close(fd);
-    }));
-    ASSERT(m_dispatchIO.get());
-    // This makes the channel read/write all data before invoking the handlers.
-    dispatch_io_set_low_water(m_dispatchIO.get(), std::numeric_limits<size_t>::max());
-}
-
-Ref<IOChannel> IOChannel::open(const String& filePath, IOChannel::Type type)
+IOChannel::IOChannel(const String& filePath, Type type)
+    : m_path(filePath)
+    , m_type(type)
 {
     int oflag;
     mode_t mode;
 
-    switch (type) {
+    switch (m_type) {
     case Type::Create:
         oflag = O_RDWR | O_CREAT | O_TRUNC | O_NONBLOCK;
         mode = S_IRUSR | S_IWUSR;
@@ -71,8 +62,19 @@ Ref<IOChannel> IOChannel::open(const String& filePath, IOChannel::Type type)
 
     CString path = WebCore::fileSystemRepresentation(filePath);
     int fd = ::open(path.data(), oflag, mode);
+    m_fileDescriptor = fd;
 
-    return adoptRef(*new IOChannel(fd));
+    m_dispatchIO = adoptDispatch(dispatch_io_create(DISPATCH_IO_RANDOM, fd, dispatch_get_main_queue(), [fd](int) {
+        close(fd);
+    }));
+    ASSERT(m_dispatchIO.get());
+    // This makes the channel read/write all data before invoking the handlers.
+    dispatch_io_set_low_water(m_dispatchIO.get(), std::numeric_limits<size_t>::max());
+}
+
+Ref<IOChannel> IOChannel::open(const String& filePath, IOChannel::Type type)
+{
+    return adoptRef(*new IOChannel(filePath, type));
 }
 
 void IOChannel::read(size_t offset, size_t size, std::function<void (Data&, int error)> completionHandler)
index c13b991..67ea71e 100644 (file)
@@ -65,7 +65,7 @@ Storage::Storage(const String& baseDirectoryPath)
     , m_directoryPath(makeVersionedDirectoryPath(baseDirectoryPath))
     , m_ioQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage", WorkQueue::Type::Concurrent))
     , m_backgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.background", WorkQueue::Type::Concurrent, WorkQueue::QOS::Background))
-    , m_deleteQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.delete", WorkQueue::Type::Serial, WorkQueue::QOS::Background))
+    , m_serialBackgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.serialBackground", WorkQueue::Type::Serial, WorkQueue::QOS::Background))
 {
     deleteOldVersions();
     initialize();
@@ -282,11 +282,19 @@ void Storage::remove(const Key& key)
         m_contentsFilter.remove(key.shortHash());
 
     StringCapture filePathCapture(filePathForKey(key, m_directoryPath));
-    deleteQueue().dispatch([this, filePathCapture] {
+    serialBackgroundIOQueue().dispatch([this, filePathCapture] {
         WebCore::deleteFile(filePathCapture.string());
     });
 }
 
+void Storage::updateFileAccessTime(IOChannel& channel)
+{
+    StringCapture filePathCapture(channel.path());
+    serialBackgroundIOQueue().dispatch([filePathCapture] {
+        updateFileAccessTimeIfNeeded(filePathCapture.string());
+    });
+}
+
 void Storage::dispatchReadOperation(const ReadOperation& read)
 {
     ASSERT(RunLoop::isMain());
@@ -294,16 +302,17 @@ void Storage::dispatchReadOperation(const ReadOperation& read)
 
     StringCapture cachePathCapture(m_directoryPath);
     ioQueue().dispatch([this, &read, cachePathCapture] {
-        auto channel = openFileForKey(read.key, IOChannel::Type::Read, cachePathCapture.string());
-        int fd = channel->fileDescriptor();
-        channel->read(0, std::numeric_limits<size_t>::max(), [this, &read, fd](Data& fileData, int error) {
+        RefPtr<IOChannel> channel = openFileForKey(read.key, IOChannel::Type::Read, cachePathCapture.string());
+        channel->read(0, std::numeric_limits<size_t>::max(), [this, channel, &read](Data& fileData, int error) {
             if (error) {
                 remove(read.key);
                 read.completionHandler(nullptr);
             } else {
-                auto entry = decodeEntry(fileData, fd, read.key);
+                auto entry = decodeEntry(fileData, channel->fileDescriptor(), read.key);
                 bool success = read.completionHandler(WTF::move(entry));
-                if (!success)
+                if (success)
+                    updateFileAccessTime(*channel);
+                else
                     remove(read.key);
             }
 
@@ -569,12 +578,31 @@ void Storage::clear()
     });
 }
 
+static double deletionProbability(FileTimes times)
+{
+    static const double maximumProbability { 0.33 };
+
+    using namespace std::chrono;
+    auto age = system_clock::now() - times.creation;
+    auto accessAge = times.access - times.creation;
+
+    // For sanity.
+    if (age <= seconds::zero() || accessAge < seconds::zero() || accessAge > age)
+        return maximumProbability;
+
+    // We like old entries that have been accessed recently.
+    auto relativeValue = duration<double>(accessAge) / age;
+
+    // Adjust a bit so the most valuable entries don't get deleted at all.
+    auto effectiveValue = std::min(1.1 * relativeValue, 1.);
+
+    return (1 - effectiveValue) * maximumProbability;
+}
+
 void Storage::shrinkIfNeeded()
 {
     ASSERT(RunLoop::isMain());
 
-    static const double deletionProbability { 0.25 };
-
     if (m_approximateSize <= m_maximumSize)
         return;
     if (m_shrinkInProgress)
@@ -591,7 +619,12 @@ void Storage::shrinkIfNeeded()
         traverseCacheFiles(cachePath, [this](const String& fileName, const String& partitionPath) {
             auto filePath = WebCore::pathByAppendingComponent(partitionPath, fileName);
 
-            bool shouldDelete = randomNumber() < deletionProbability;
+            auto times = fileTimes(filePath);
+            auto probability = deletionProbability(times);
+            bool shouldDelete = randomNumber() < probability;
+
+            LOG(NetworkCacheStorage, "Deletion probability=%f shouldDelete=%d", probability, shouldDelete);
+
             if (!shouldDelete) {
                 long long fileSize = 0;
                 WebCore::getFileSize(filePath, fileSize);
index d349a5c..6cb1909 100644 (file)
@@ -40,6 +40,8 @@
 namespace WebKit {
 namespace NetworkCache {
 
+class IOChannel;
+
 class Storage {
     WTF_MAKE_NONCOPYABLE(Storage);
 public:
@@ -95,9 +97,11 @@ private:
     void dispatchHeaderWriteOperation(const WriteOperation&);
     void dispatchPendingWriteOperations();
 
+    void updateFileAccessTime(IOChannel&);
+
     WorkQueue& ioQueue() { return m_ioQueue.get(); }
     WorkQueue& backgroundIOQueue() { return m_backgroundIOQueue.get(); }
-    WorkQueue& deleteQueue() { return m_deleteQueue.get(); }
+    WorkQueue& serialBackgroundIOQueue() { return m_serialBackgroundIOQueue.get(); }
 
     const String m_baseDirectoryPath;
     const String m_directoryPath;
@@ -117,7 +121,7 @@ private:
 
     Ref<WorkQueue> m_ioQueue;
     Ref<WorkQueue> m_backgroundIOQueue;
-    Ref<WorkQueue> m_deleteQueue;
+    Ref<WorkQueue> m_serialBackgroundIOQueue;
 };
 
 }