Changeset 181700 in webkit


Ignore:
Timestamp:
Mar 18, 2015, 10:40:34 AM (11 years ago)
Author:
Antti Koivisto
Message:

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.

Location:
trunk/Source/WebKit2
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebKit2/ChangeLog

    r181689 r181700  
     12015-03-17  Antti Koivisto  <antti@apple.com>
     2
     3        Prune least valuable cache entries first
     4        https://bugs.webkit.org/show_bug.cgi?id=142810
     5        rdar://problem/19632130
     6
     7        Reviewed by Darin Adler.
     8
     9        When pruning the cache estimate relative value of each entry using formula
     10
     11        age = current time - creation time
     12        accessAge = last access time - creation time
     13        value = accessAge / age
     14
     15        That is, we value entries that have been accessed recently and survived in the cache longest.
     16
     17        The most valuable entries don't get deleted at all while the deletion probablity ramps up for
     18        lower value entries.
     19
     20        * NetworkProcess/cache/NetworkCacheFileSystemPosix.h:
     21        (WebKit::NetworkCache::fileTimes):
     22
     23            Get the creation time and access time for a file.
     24
     25        (WebKit::NetworkCache::updateFileAccessTimeIfNeeded):
     26
     27            Update access time manually if the file system doesn't do it automatically.
     28
     29        * NetworkProcess/cache/NetworkCacheIOChannel.h:
     30        (WebKit::NetworkCache::IOChannel::path):
     31        (WebKit::NetworkCache::IOChannel::type):
     32        * NetworkProcess/cache/NetworkCacheIOChannelCocoa.mm:
     33        (WebKit::NetworkCache::IOChannel::IOChannel):
     34        (WebKit::NetworkCache::IOChannel::open):
     35
     36            Remember the file path and move most of the work to constructor.
     37
     38        * NetworkProcess/cache/NetworkCacheStorage.cpp:
     39        (WebKit::NetworkCache::Storage::Storage):
     40        (WebKit::NetworkCache::Storage::remove):
     41        (WebKit::NetworkCache::Storage::updateFileAccessTime):
     42        (WebKit::NetworkCache::Storage::dispatchReadOperation):
     43        (WebKit::NetworkCache::deletionProbability):
     44
     45            Compute the probability based on entry age and access time.
     46
     47        (WebKit::NetworkCache::Storage::shrinkIfNeeded):
     48        * NetworkProcess/cache/NetworkCacheStorage.h:
     49        (WebKit::NetworkCache::Storage::serialBackgroundIOQueue):
     50        (WebKit::NetworkCache::Storage::deleteQueue): Deleted.
     51
     52            More generic name.
     53
    1542015-03-18  Chris Dumez  <cdumez@apple.com>
    255

  • trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheFileSystemPosix.h

    r181140 r181700  
    3232#include <WebCore/FileSystem.h>
    3333#include <dirent.h>
     34#include <sys/stat.h>
     35#include <sys/time.h>
    3436#include <wtf/text/CString.h>
    3537
    … …  
    6870}
    6971
     72struct FileTimes {
     73    std::chrono::system_clock::time_point creation;
     74    std::chrono::system_clock::time_point access;
     75};
     76
     77inline FileTimes fileTimes(const String& path)
     78{
     79    struct stat fileInfo;
     80    if (stat(WebCore::fileSystemRepresentation(path).data(), &fileInfo))
     81        return { };
     82    return { std::chrono::system_clock::from_time_t(fileInfo.st_birthtime), std::chrono::system_clock::from_time_t(fileInfo.st_atime) };
     83}
     84
     85inline void updateFileAccessTimeIfNeeded(const String& path)
     86{
     87    auto times = fileTimes(path);
     88    if (times.creation != times.access) {
     89        // Don't update more than once per hour;
     90        if (std::chrono::system_clock::now() - times.access < std::chrono::hours(1))
     91            return;
     92    }
     93    // This really updates both access time and modification time.
     94    utimes(WebCore::fileSystemRepresentation(path).data(), 0);
     95}
     96
    7097}
    7198}

  • trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheIOChannel.h

    r181161 r181700  
    4646    void write(size_t offset, const Data&, std::function<void (int error)>);
    4747
     48    const String& path() const { return m_path; }
     49    Type type() const { return m_type; }
     50
    4851    int fileDescriptor() const { return m_fileDescriptor; }
    4952
    5053private:
    51     IOChannel(int fd);
     54    IOChannel(const String& filePath, IOChannel::Type);
    5255
     56    String m_path;
     57    Type m_type;
     58
     59    int m_fileDescriptor { 0 };
    5360#if PLATFORM(COCOA)
    5461    DispatchPtr<dispatch_io_t> m_dispatchIO;
    5562#endif
    56     int m_fileDescriptor { 0 };
    5763};
    5864

  • trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheIOChannelCocoa.mm

    r181424 r181700  
    4040namespace NetworkCache {
    4141
    42 IOChannel::IOChannel(int fd)
    43     : m_fileDescriptor(fd)
    44 {
    45     m_dispatchIO = adoptDispatch(dispatch_io_create(DISPATCH_IO_RANDOM, fd, dispatch_get_main_queue(), [fd](int) {
    46         close(fd);
    47     }));
    48     ASSERT(m_dispatchIO.get());
    49     // This makes the channel read/write all data before invoking the handlers.
    50     dispatch_io_set_low_water(m_dispatchIO.get(), std::numeric_limits<size_t>::max());
    51 }
    52 
    53 Ref<IOChannel> IOChannel::open(const String& filePath, IOChannel::Type type)
     42IOChannel::IOChannel(const String& filePath, Type type)
     43    : m_path(filePath)
     44    , m_type(type)
    5445{
    5546    int oflag;
    5647    mode_t mode;
    5748
    58     switch (type) {
     49    switch (m_type) {
    5950    case Type::Create:
    6051        oflag = O_RDWR | O_CREAT | O_TRUNC | O_NONBLOCK;
    … …  
    7263    CString path = WebCore::fileSystemRepresentation(filePath);
    7364    int fd = ::open(path.data(), oflag, mode);
     65    m_fileDescriptor = fd;
    7466
    75     return adoptRef(*new IOChannel(fd));
     67    m_dispatchIO = adoptDispatch(dispatch_io_create(DISPATCH_IO_RANDOM, fd, dispatch_get_main_queue(), [fd](int) {
     68        close(fd);
     69    }));
     70    ASSERT(m_dispatchIO.get());
     71    // This makes the channel read/write all data before invoking the handlers.
     72    dispatch_io_set_low_water(m_dispatchIO.get(), std::numeric_limits<size_t>::max());
     73}
     74
     75Ref<IOChannel> IOChannel::open(const String& filePath, IOChannel::Type type)
     76{
     77    return adoptRef(*new IOChannel(filePath, type));
    7678}
    7779

  • trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.cpp

    r181424 r181700  
    6666    , m_ioQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage", WorkQueue::Type::Concurrent))
    6767    , m_backgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.background", WorkQueue::Type::Concurrent, WorkQueue::QOS::Background))
    68     , m_deleteQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.delete", WorkQueue::Type::Serial, WorkQueue::QOS::Background))
     68    , m_serialBackgroundIOQueue(WorkQueue::create("com.apple.WebKit.Cache.Storage.serialBackground", WorkQueue::Type::Serial, WorkQueue::QOS::Background))
    6969{
    7070    deleteOldVersions();
    … …  
    283283
    284284    StringCapture filePathCapture(filePathForKey(key, m_directoryPath));
    285     deleteQueue().dispatch([this, filePathCapture] {
     285    serialBackgroundIOQueue().dispatch([this, filePathCapture] {
    286286        WebCore::deleteFile(filePathCapture.string());
     287    });
     288}
     289
     290void Storage::updateFileAccessTime(IOChannel& channel)
     291{
     292    StringCapture filePathCapture(channel.path());
     293    serialBackgroundIOQueue().dispatch([filePathCapture] {
     294        updateFileAccessTimeIfNeeded(filePathCapture.string());
    287295    });
    288296}
    … …  
    295303    StringCapture cachePathCapture(m_directoryPath);
    296304    ioQueue().dispatch([this, &read, cachePathCapture] {
    297         auto channel = openFileForKey(read.key, IOChannel::Type::Read, cachePathCapture.string());
    298         int fd = channel->fileDescriptor();
    299         channel->read(0, std::numeric_limits<size_t>::max(), [this, &read, fd](Data& fileData, int error) {
     305        RefPtr<IOChannel> channel = openFileForKey(read.key, IOChannel::Type::Read, cachePathCapture.string());
     306        channel->read(0, std::numeric_limits<size_t>::max(), [this, channel, &read](Data& fileData, int error) {
    300307            if (error) {
    301308                remove(read.key);
    302309                read.completionHandler(nullptr);
    303310            } else {
    304                 auto entry = decodeEntry(fileData, fd, read.key);
     311                auto entry = decodeEntry(fileData, channel->fileDescriptor(), read.key);
    305312                bool success = read.completionHandler(WTF::move(entry));
    306                 if (!success)
     313                if (success)
     314                    updateFileAccessTime(*channel);
     315                else
    307316                    remove(read.key);
    308317            }
    … …  
    570579}
    571580
     581static double deletionProbability(FileTimes times)
     582{
     583    static const double maximumProbability { 0.33 };
     584
     585    using namespace std::chrono;
     586    auto age = system_clock::now() - times.creation;
     587    auto accessAge = times.access - times.creation;
     588
     589    // For sanity.
     590    if (age <= seconds::zero() || accessAge < seconds::zero() || accessAge > age)
     591        return maximumProbability;
     592
     593    // We like old entries that have been accessed recently.
     594    auto relativeValue = duration<double>(accessAge) / age;
     595
     596    // Adjust a bit so the most valuable entries don't get deleted at all.
     597    auto effectiveValue = std::min(1.1 * relativeValue, 1.);
     598
     599    return (1 - effectiveValue) * maximumProbability;
     600}
     601
    572602void Storage::shrinkIfNeeded()
    573603{
    574604    ASSERT(RunLoop::isMain());
    575 
    576     static const double deletionProbability { 0.25 };
    577605
    578606    if (m_approximateSize <= m_maximumSize)
    … …  
    592620            auto filePath = WebCore::pathByAppendingComponent(partitionPath, fileName);
    593621
    594             bool shouldDelete = randomNumber() < deletionProbability;
     622            auto times = fileTimes(filePath);
     623            auto probability = deletionProbability(times);
     624            bool shouldDelete = randomNumber() < probability;
     625
     626            LOG(NetworkCacheStorage, "Deletion probability=%f shouldDelete=%d", probability, shouldDelete);
     627
    595628            if (!shouldDelete) {
    596629                long long fileSize = 0;

  • trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h

    r181364 r181700  
    4040namespace WebKit {
    4141namespace NetworkCache {
     42
     43class IOChannel;
    4244
    4345class Storage {
    … …  
    9698    void dispatchPendingWriteOperations();
    9799
     100    void updateFileAccessTime(IOChannel&);
     101
    98102    WorkQueue& ioQueue() { return m_ioQueue.get(); }
    99103    WorkQueue& backgroundIOQueue() { return m_backgroundIOQueue.get(); }
    100     WorkQueue& deleteQueue() { return m_deleteQueue.get(); }
     104    WorkQueue& serialBackgroundIOQueue() { return m_serialBackgroundIOQueue.get(); }
    101105
    102106    const String m_baseDirectoryPath;
    … …  
    118122    Ref<WorkQueue> m_ioQueue;
    119123    Ref<WorkQueue> m_backgroundIOQueue;
    120     Ref<WorkQueue> m_deleteQueue;
     124    Ref<WorkQueue> m_serialBackgroundIOQueue;
    121125};
    122126
Note: See TracChangeset for help on using the changeset viewer.