Changeset 179779 in webkit


Ignore:
Timestamp:
Feb 7, 2015 11:18:30 AM (9 years ago)
Author:
Antti Koivisto
Message:

Use longer hashes for cache keys
​https://bugs.webkit.org/show_bug.cgi?id=141356

Reviewed by Darin Adler.

The current key hashes are 32bit. We should use longer hashes to eliminate collisions.

This patch switches us to using MD5 digests for the cache key hashes. As a result the file names for the cache
entries grow from 8 to 32 character.

Note that we don't need a cryptographic hash (full cache keys are verified against the entries).
MD5 just happens to be fast, convenient and available.

The patch also moves the whole cache hierarchy down to a versioned subdirectory ("WebKitCache/Version 2")
and deletes any old style cache files if they exist.

  • NetworkProcess/cache/NetworkCacheCoders.cpp:

(WebKit::NetworkCacheCoder<MD5::Digest>::encode):
(WebKit::NetworkCacheCoder<MD5::Digest>::decode):

  • NetworkProcess/cache/NetworkCacheCoders.h:
  • NetworkProcess/cache/NetworkCacheKey.cpp:

(WebKit::NetworkCacheKey::NetworkCacheKey):
(WebKit::hashString):
(WebKit::NetworkCacheKey::computeHash):
(WebKit::NetworkCacheKey::hashAsString):
(WebKit::NetworkCacheKey::stringToHash):

  • NetworkProcess/cache/NetworkCacheKey.h:

(WebKit::NetworkCacheKey::shortHash):
(WebKit::NetworkCacheKey::toShortHash):

32bit hash to use in the bloom filter.

(WebKit::NetworkCacheKey::hashStringLength):

  • NetworkProcess/cache/NetworkCacheStorage.h:

Bump the version.

  • NetworkProcess/cache/NetworkCacheStorageCocoa.mm:

(WebKit::traverseCacheFiles):
(WebKit::makeVersionedDirectoryPath):
(WebKit::NetworkCacheStorage::NetworkCacheStorage):
(WebKit::NetworkCacheStorage::initialize):
(WebKit::NetworkCacheStorage::removeEntry):
(WebKit::NetworkCacheStorage::retrieve):
(WebKit::NetworkCacheStorage::store):
(WebKit::NetworkCacheStorage::update):
(WebKit::NetworkCacheStorage::shrinkIfNeeded):
(WebKit::NetworkCacheStorage::deleteOldVersions):

Wipe out the version 1 cache.

Location:
trunk/Source/WebKit2
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebKit2/ChangeLog

    r179774 r179779  
     12015-02-07  Antti Koivisto  <antti@apple.com>
     2
     3        Use longer hashes for cache keys
     4        https://bugs.webkit.org/show_bug.cgi?id=141356
     5
     6        Reviewed by Darin Adler.
     7
     8        The current key hashes are 32bit. We should use longer hashes to eliminate collisions.
     9
     10        This patch switches us to using MD5 digests for the cache key hashes. As a result the file names for the cache
     11        entries grow from 8 to 32 character.
     12
     13        Note that we don't need a cryptographic hash (full cache keys are verified against the entries).
     14        MD5 just happens to be fast, convenient and available.
     15
     16        The patch also moves the whole cache hierarchy down to a versioned subdirectory ("WebKitCache/Version 2")
     17        and deletes any old style cache files if they exist.
     18
     19        * NetworkProcess/cache/NetworkCacheCoders.cpp:
     20        (WebKit::NetworkCacheCoder<MD5::Digest>::encode):
     21        (WebKit::NetworkCacheCoder<MD5::Digest>::decode):
     22        * NetworkProcess/cache/NetworkCacheCoders.h:
     23        * NetworkProcess/cache/NetworkCacheKey.cpp:
     24        (WebKit::NetworkCacheKey::NetworkCacheKey):
     25        (WebKit::hashString):
     26        (WebKit::NetworkCacheKey::computeHash):
     27        (WebKit::NetworkCacheKey::hashAsString):
     28        (WebKit::NetworkCacheKey::stringToHash):
     29        * NetworkProcess/cache/NetworkCacheKey.h:
     30        (WebKit::NetworkCacheKey::shortHash):
     31        (WebKit::NetworkCacheKey::toShortHash):
     32
     33            32bit hash to use in the bloom filter.
     34
     35        (WebKit::NetworkCacheKey::hashStringLength):
     36        * NetworkProcess/cache/NetworkCacheStorage.h:
     37
     38            Bump the version.
     39
     40        * NetworkProcess/cache/NetworkCacheStorageCocoa.mm:
     41        (WebKit::traverseCacheFiles):
     42        (WebKit::makeVersionedDirectoryPath):
     43        (WebKit::NetworkCacheStorage::NetworkCacheStorage):
     44        (WebKit::NetworkCacheStorage::initialize):
     45        (WebKit::NetworkCacheStorage::removeEntry):
     46        (WebKit::NetworkCacheStorage::retrieve):
     47        (WebKit::NetworkCacheStorage::store):
     48        (WebKit::NetworkCacheStorage::update):
     49        (WebKit::NetworkCacheStorage::shrinkIfNeeded):
     50        (WebKit::NetworkCacheStorage::deleteOldVersions):
     51
     52            Wipe out the version 1 cache.
     53
    1542015-02-06  Chris Dumez  <cdumez@apple.com>
    255

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

    r179708 r179779  
    241241        auto elapsedMS = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - startTime).count();
    242242#endif
     243        fprintf(stderr, "retireved %d\n", success);
    243244        LOG(NetworkCache, "(NetworkProcess) retrieve complete success=%d priority=%u time=%lldms", success, originalRequest.priority(), elapsedMS);
    244245        completionHandler(WTF::move(decodedEntry));

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

    r176400 r179779  
    11/*
    2  * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
     2 * Copyright (C) 2011, 2014-2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    174174}
    175175
     176void NetworkCacheCoder<MD5::Digest>::encode(NetworkCacheEncoder& encoder, const MD5::Digest& digest)
     177{
     178    encoder.encodeFixedLengthData(digest.data(), sizeof(digest));
     179}
     180
     181bool NetworkCacheCoder<MD5::Digest>::decode(NetworkCacheDecoder& decoder, MD5::Digest& digest)
     182{
     183    return decoder.decodeFixedLengthData(digest.data(), sizeof(digest));
     184}
     185
    176186}
    177187

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

    r176400 r179779  
    11/*
    2  * Copyright (C) 2010, 2014 Apple Inc. All rights reserved.
     2 * Copyright (C) 2010, 2014-2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    3737#include <wtf/HashSet.h>
    3838#include <wtf/Vector.h>
     39#include <wtf/md5.h>
    3940
    4041namespace WebKit {
    … …  
    256257};
    257258
     259template<> struct NetworkCacheCoder<MD5::Digest> {
     260    static void encode(NetworkCacheEncoder&, const MD5::Digest&);
     261    static bool decode(NetworkCacheDecoder&, MD5::Digest&);
     262};
     263
    258264}
    259265

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

    r177294 r179779  
    11/*
    2  * Copyright (C) 2014 Apple Inc. All rights reserved.
     2 * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    3030
    3131#include "NetworkCacheCoders.h"
     32#include <wtf/ASCIICType.h>
     33#include <wtf/text/CString.h>
     34#include <wtf/text/StringBuilder.h>
    3235
    3336namespace WebKit {
    … …  
    5760}
    5861
    59 static NetworkCacheKey::HashType hashString(const String& string)
     62static void hashString(MD5& md5, const String& string)
    6063{
    61     // String::hash() masks away the top bits.
    62     if (string.is8Bit())
    63         return StringHasher::computeHash(string.characters8(), string.length());
    64     return StringHasher::computeHash(string.characters16(), string.length());
     64    const uint8_t zero = 0;
     65    if (string.is8Bit()) {
     66        md5.addBytes(string.characters8(), string.length());
     67        md5.addBytes(&zero, 1);
     68        return;
     69    }
     70    auto cString = string.utf8();
     71    md5.addBytes(reinterpret_cast<const uint8_t*>(cString.data()), cString.length());
     72    md5.addBytes(&zero, 1);
    6573}
    6674
    6775NetworkCacheKey::HashType NetworkCacheKey::computeHash() const
    6876{
    69     return WTF::pairIntHash(hashString(m_method), WTF::pairIntHash(hashString(m_identifier), hashString(m_partition)));
     77    // We don't really need a cryptographic hash. The key is always verified against the entry header.
     78    // MD5 just happens to be suitably sized, fast and available.
     79    MD5 md5;
     80    hashString(md5, m_method);
     81    hashString(md5, m_partition);
     82    hashString(md5, m_identifier);
     83    MD5::Digest hash;
     84    md5.checksum(hash);
     85    return hash;
    7086}
    7187
    7288String NetworkCacheKey::hashAsString() const
    7389{
    74     return String::format("%08x", m_hash);
     90    StringBuilder builder;
     91    for (auto byte : m_hash) {
     92        builder.append(upperNibbleToASCIIHexDigit(byte));
     93        builder.append(lowerNibbleToASCIIHexDigit(byte));
     94    }
     95    return builder.toString();
     96}
     97
     98template <typename CharType> bool hexDigitsToHash(CharType* characters, NetworkCacheKey::HashType& hash)
     99{
     100    for (unsigned i = 0; i < sizeof(hash); ++i) {
     101        auto high = characters[2 * i];
     102        auto low = characters[2 * i + 1];
     103        if (!isASCIIHexDigit(high) || !isASCIIHexDigit(low))
     104            return false;
     105        hash[i] = toASCIIHexValue(high, low);
     106    }
     107    return true;
    75108}
    76109
    77110bool NetworkCacheKey::stringToHash(const String& string, HashType& hash)
    78111{
    79     if (string.length() != 8)
     112    if (string.length() != hashStringLength())
    80113        return false;
    81     bool success;
    82     hash = string.toUIntStrict(&success, 16);
    83     return success;
     114    if (string.is8Bit())
     115        return hexDigitsToHash(string.characters8(), hash);
     116    return hexDigitsToHash(string.characters16(), hash);
    84117}
    85118

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

    r177294 r179779  
    11/*
    2  * Copyright (C) 2014 Apple Inc. All rights reserved.
     2 * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    2929#if ENABLE(NETWORK_CACHE)
    3030
     31#include <wtf/md5.h>
    3132#include <wtf/text/WTFString.h>
    3233
    … …  
    3839class NetworkCacheKey {
    3940public:
    40     typedef unsigned HashType;
     41    typedef MD5::Digest HashType;
    4142
    4243    NetworkCacheKey() { }
    … …  
    4849    const String& partition() const { return m_partition; }
    4950    const String& identifier() const { return m_identifier; }
     51
    5052    HashType hash() const { return m_hash; }
     53    unsigned shortHash() const  { return toShortHash(m_hash); }
    5154
     55    static unsigned toShortHash(const HashType& hash) { return *reinterpret_cast<const unsigned*>(hash.data()); }
     56    static bool stringToHash(const String&, HashType&);
     57
     58    static size_t hashStringLength() { return 2 * sizeof(m_hash); }
    5259    String hashAsString() const;
    53     static bool stringToHash(const String&, HashType&);
    5460
    5561    void encode(NetworkCacheEncoder&) const;

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

    r179708 r179779  
    11/*
    2  * Copyright (C) 2014 Apple Inc. All rights reserved.
     2 * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    154154    void clear();
    155155
    156     static const unsigned version = 1;
     156    static const unsigned version = 2;
    157157
    158158private:
    … …  
    160160
    161161    void initialize();
     162    void deleteOldVersions();
    162163    void shrinkIfNeeded();
    163164
    … …  
    184185    };
    185186
     187    const String m_baseDirectoryPath;
    186188    const String m_directoryPath;
    187189

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

    r179727 r179779  
    11/*
    2  * Copyright (C) 2014 Apple Inc. All rights reserved.
     2 * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
    33 *
    44 * Redistribution and use in source and binary forms, with or without
    … …  
    4242namespace WebKit {
    4343
    44 static const char* networkCacheSubdirectory = "WebKitCache";
     44static const char networkCacheSubdirectory[] = "WebKitCache";
     45static const char versionDirectoryPrefix[] = "Version ";
    4546
    4647template <typename Function>
    … …  
    6768        String partitionPath = WebCore::pathByAppendingComponent(cachePath, subdirName);
    6869        traverseDirectory(partitionPath, DT_REG, [&function, &partitionPath](const String& fileName) {
    69             if (fileName.length() != 8)
     70            if (fileName.length() != NetworkCacheKey::hashStringLength())
    7071                return;
    7172            function(fileName, partitionPath);
    … …  
    117118}
    118119
    119 NetworkCacheStorage::NetworkCacheStorage(const String& directoryPath)
    120     : m_directoryPath(directoryPath)
     120static String makeVersionedDirectoryPath(const String& baseDirectoryPath)
     121{
     122    String versionSubdirectory = versionDirectoryPrefix + String::number(NetworkCacheStorage::version);
     123    return WebCore::pathByAppendingComponent(baseDirectoryPath, versionSubdirectory);
     124}
     125
     126NetworkCacheStorage::NetworkCacheStorage(const String& baseDirectoryPath)
     127    : m_baseDirectoryPath(baseDirectoryPath)
     128    , m_directoryPath(makeVersionedDirectoryPath(baseDirectoryPath))
    121129    , m_ioQueue(adoptDispatch(dispatch_queue_create("com.apple.WebKit.Cache.Storage", DISPATCH_QUEUE_CONCURRENT)))
    122130    , m_backgroundIOQueue(adoptDispatch(dispatch_queue_create("com.apple.WebKit.Cache.Storage.Background", DISPATCH_QUEUE_CONCURRENT)))
    … …  
    124132    dispatch_set_target_queue(m_backgroundIOQueue.get(), dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0));
    125133
     134    deleteOldVersions();
    126135    initialize();
    127136}
    … …  
    140149            if (!NetworkCacheKey::stringToHash(fileName, hash))
    141150                return;
    142             dispatch_async(dispatch_get_main_queue(), [this, hash] {
    143                 m_contentsFilter.add(hash);
     151            unsigned shortHash = NetworkCacheKey::toShortHash(hash);
     152            dispatch_async(dispatch_get_main_queue(), [this, shortHash] {
     153                m_contentsFilter.add(shortHash);
    144154            });
    145155            ++entryCount;
    … …  
    345355    ASSERT(RunLoop::isMain());
    346356
    347     if (m_contentsFilter.mayContain(key.hash()))
    348         m_contentsFilter.remove(key.hash());
     357    if (m_contentsFilter.mayContain(key.shortHash()))
     358        m_contentsFilter.remove(key.shortHash());
    349359
    350360    StringCapture filePathCapture(filePathForKey(key, m_directoryPath));
    … …  
    431441    ASSERT(priority <= maximumRetrievePriority);
    432442
    433     if (!m_contentsFilter.mayContain(key.hash())) {
     443    if (!m_contentsFilter.mayContain(key.shortHash())) {
    434444        completionHandler(nullptr);
    435445        return;
    … …  
    450460    ASSERT(RunLoop::isMain());
    451461
    452     m_contentsFilter.add(key.hash());
     462    m_contentsFilter.add(key.shortHash());
    453463    ++m_approximateEntryCount;
    454464
    … …  
    471481            LOG(NetworkCacheStorage, "(NetworkProcess) write complete error=%d", error);
    472482            if (error) {
    473                 if (m_contentsFilter.mayContain(store.key.hash()))
    474                     m_contentsFilter.remove(store.key.hash());
     483                if (m_contentsFilter.mayContain(store.key.shortHash()))
     484                    m_contentsFilter.remove(store.key.shortHash());
    475485                if (m_approximateEntryCount)
    476486                    --m_approximateEntryCount;
    … …  
    494504    ASSERT(RunLoop::isMain());
    495505
    496     if (!m_contentsFilter.mayContain(key.hash())) {
     506    if (!m_contentsFilter.mayContain(key.shortHash())) {
    497507        LOG(NetworkCacheStorage, "(NetworkProcess) existing entry not found, storing full entry");
    498508        store(key, updateEntry, WTF::move(completionHandler));
    … …  
    600610            if (!NetworkCacheKey::stringToHash(fileName, hash))
    601611                return;
    602             dispatch_async(dispatch_get_main_queue(), [this, hash] {
    603                 if (m_contentsFilter.mayContain(hash))
    604                     m_contentsFilter.remove(hash);
     612            unsigned shortHash = NetworkCacheKey::toShortHash(hash);
     613            dispatch_async(dispatch_get_main_queue(), [this, shortHash] {
     614                if (m_contentsFilter.mayContain(shortHash))
     615                    m_contentsFilter.remove(shortHash);
    605616            });
    606617        });
    … …  
    612623}
    613624
     625void NetworkCacheStorage::deleteOldVersions()
     626{
     627    // Delete V1 cache.
     628    StringCapture cachePathCapture(m_baseDirectoryPath);
     629    dispatch_async(m_backgroundIOQueue.get(), [cachePathCapture] {
     630        String cachePath = cachePathCapture.string();
     631        traverseDirectory(cachePath, DT_DIR, [&cachePath](const String& subdirName) {
     632            if (subdirName.startsWith(versionDirectoryPrefix))
     633                return;
     634            String partitionPath = WebCore::pathByAppendingComponent(cachePath, subdirName);
     635            traverseDirectory(partitionPath, DT_REG, [&partitionPath](const String& fileName) {
     636                WebCore::deleteFile(WebCore::pathByAppendingComponent(partitionPath, fileName));
     637            });
     638            WebCore::deleteEmptyDirectory(partitionPath);
     639        });
     640    });
     641}
     642
    614643}
    615644
Note: See TracChangeset for help on using the changeset viewer.