Diff
Modified: trunk/Source/WebKit2/ChangeLog (179778 => 179779)
--- trunk/Source/WebKit2/ChangeLog 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/ChangeLog 2015-02-07 19:18:30 UTC (rev 179779)
@@ -1,3 +1,56 @@
+2015-02-07 Antti Koivisto <[email protected]>
+
+ 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.
+
2015-02-06 Chris Dumez <[email protected]>
Have SQLiteStatement::database() return a reference
Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCache.cpp (179778 => 179779)
--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCache.cpp 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCache.cpp 2015-02-07 19:18:30 UTC (rev 179779)
@@ -240,6 +240,7 @@
#if !LOG_DISABLED
auto elapsedMS = std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::system_clock::now() - startTime).count();
#endif
+ fprintf(stderr, "retireved %d\n", success);
LOG(NetworkCache, "(NetworkProcess) retrieve complete success=%d priority=%u time=%lldms", success, originalRequest.priority(), elapsedMS);
completionHandler(WTF::move(decodedEntry));
return success;
Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheCoders.cpp (179778 => 179779)
--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheCoders.cpp 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheCoders.cpp 2015-02-07 19:18:30 UTC (rev 179779)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2011, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2014-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -173,6 +173,16 @@
return true;
}
+void NetworkCacheCoder<MD5::Digest>::encode(NetworkCacheEncoder& encoder, const MD5::Digest& digest)
+{
+ encoder.encodeFixedLengthData(digest.data(), sizeof(digest));
}
+bool NetworkCacheCoder<MD5::Digest>::decode(NetworkCacheDecoder& decoder, MD5::Digest& digest)
+{
+ return decoder.decodeFixedLengthData(digest.data(), sizeof(digest));
+}
+
+}
+
#endif
Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheCoders.h (179778 => 179779)
--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheCoders.h 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheCoders.h 2015-02-07 19:18:30 UTC (rev 179779)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2010, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2010, 2014-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -36,6 +36,7 @@
#include <wtf/HashMap.h>
#include <wtf/HashSet.h>
#include <wtf/Vector.h>
+#include <wtf/md5.h>
namespace WebKit {
@@ -255,6 +256,11 @@
static bool decode(NetworkCacheDecoder&, WebCore::CertificateInfo&);
};
+template<> struct NetworkCacheCoder<MD5::Digest> {
+ static void encode(NetworkCacheEncoder&, const MD5::Digest&);
+ static bool decode(NetworkCacheDecoder&, MD5::Digest&);
+};
+
}
#endif
Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheKey.cpp (179778 => 179779)
--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheKey.cpp 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheKey.cpp 2015-02-07 19:18:30 UTC (rev 179779)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -29,6 +29,9 @@
#if ENABLE(NETWORK_CACHE)
#include "NetworkCacheCoders.h"
+#include <wtf/ASCIICType.h>
+#include <wtf/text/CString.h>
+#include <wtf/text/StringBuilder.h>
namespace WebKit {
@@ -56,31 +59,61 @@
{
}
-static NetworkCacheKey::HashType hashString(const String& string)
+static void hashString(MD5& md5, const String& string)
{
- // String::hash() masks away the top bits.
- if (string.is8Bit())
- return StringHasher::computeHash(string.characters8(), string.length());
- return StringHasher::computeHash(string.characters16(), string.length());
+ const uint8_t zero = 0;
+ if (string.is8Bit()) {
+ md5.addBytes(string.characters8(), string.length());
+ md5.addBytes(&zero, 1);
+ return;
+ }
+ auto cString = string.utf8();
+ md5.addBytes(reinterpret_cast<const uint8_t*>(cString.data()), cString.length());
+ md5.addBytes(&zero, 1);
}
NetworkCacheKey::HashType NetworkCacheKey::computeHash() const
{
- return WTF::pairIntHash(hashString(m_method), WTF::pairIntHash(hashString(m_identifier), hashString(m_partition)));
+ // We don't really need a cryptographic hash. The key is always verified against the entry header.
+ // MD5 just happens to be suitably sized, fast and available.
+ MD5 md5;
+ hashString(md5, m_method);
+ hashString(md5, m_partition);
+ hashString(md5, m_identifier);
+ MD5::Digest hash;
+ md5.checksum(hash);
+ return hash;
}
String NetworkCacheKey::hashAsString() const
{
- return String::format("%08x", m_hash);
+ StringBuilder builder;
+ for (auto byte : m_hash) {
+ builder.append(upperNibbleToASCIIHexDigit(byte));
+ builder.append(lowerNibbleToASCIIHexDigit(byte));
+ }
+ return builder.toString();
}
+template <typename CharType> bool hexDigitsToHash(CharType* characters, NetworkCacheKey::HashType& hash)
+{
+ for (unsigned i = 0; i < sizeof(hash); ++i) {
+ auto high = characters[2 * i];
+ auto low = characters[2 * i + 1];
+ if (!isASCIIHexDigit(high) || !isASCIIHexDigit(low))
+ return false;
+ hash[i] = toASCIIHexValue(high, low);
+ }
+ return true;
+}
+
bool NetworkCacheKey::stringToHash(const String& string, HashType& hash)
{
- if (string.length() != 8)
+ if (string.length() != hashStringLength())
return false;
- bool success;
- hash = string.toUIntStrict(&success, 16);
- return success;
+ if (string.is8Bit())
+ return hexDigitsToHash(string.characters8(), hash);
+ return hexDigitsToHash(string.characters16(), hash);
}
bool NetworkCacheKey::operator==(const NetworkCacheKey& other) const
Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheKey.h (179778 => 179779)
--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheKey.h 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheKey.h 2015-02-07 19:18:30 UTC (rev 179779)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -28,6 +28,7 @@
#if ENABLE(NETWORK_CACHE)
+#include <wtf/md5.h>
#include <wtf/text/WTFString.h>
namespace WebKit {
@@ -37,7 +38,7 @@
class NetworkCacheKey {
public:
- typedef unsigned HashType;
+ typedef MD5::Digest HashType;
NetworkCacheKey() { }
NetworkCacheKey(const NetworkCacheKey&);
@@ -47,11 +48,16 @@
const String& method() const { return m_method; }
const String& partition() const { return m_partition; }
const String& identifier() const { return m_identifier; }
+
HashType hash() const { return m_hash; }
+ unsigned shortHash() const { return toShortHash(m_hash); }
- String hashAsString() const;
+ static unsigned toShortHash(const HashType& hash) { return *reinterpret_cast<const unsigned*>(hash.data()); }
static bool stringToHash(const String&, HashType&);
+ static size_t hashStringLength() { return 2 * sizeof(m_hash); }
+ String hashAsString() const;
+
void encode(NetworkCacheEncoder&) const;
static bool decode(NetworkCacheDecoder&, NetworkCacheKey&);
Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h (179778 => 179779)
--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h 2015-02-07 19:18:30 UTC (rev 179779)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -153,12 +153,13 @@
void setMaximumSize(size_t);
void clear();
- static const unsigned version = 1;
+ static const unsigned version = 2;
private:
NetworkCacheStorage(const String& directoryPath);
void initialize();
+ void deleteOldVersions();
void shrinkIfNeeded();
void removeEntry(const NetworkCacheKey&);
@@ -183,6 +184,7 @@
StoreCompletionHandler completionHandler;
};
+ const String m_baseDirectoryPath;
const String m_directoryPath;
size_t m_maximumSize { std::numeric_limits<size_t>::max() };
Modified: trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorageCocoa.mm (179778 => 179779)
--- trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorageCocoa.mm 2015-02-07 17:01:37 UTC (rev 179778)
+++ trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorageCocoa.mm 2015-02-07 19:18:30 UTC (rev 179779)
@@ -1,5 +1,5 @@
/*
- * Copyright (C) 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2015 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -41,7 +41,8 @@
namespace WebKit {
-static const char* networkCacheSubdirectory = "WebKitCache";
+static const char networkCacheSubdirectory[] = "WebKitCache";
+static const char versionDirectoryPrefix[] = "Version ";
template <typename Function>
static void traverseDirectory(const String& path, uint8_t type, const Function& function)
@@ -66,7 +67,7 @@
traverseDirectory(cachePath, DT_DIR, [&cachePath, &function](const String& subdirName) {
String partitionPath = WebCore::pathByAppendingComponent(cachePath, subdirName);
traverseDirectory(partitionPath, DT_REG, [&function, &partitionPath](const String& fileName) {
- if (fileName.length() != 8)
+ if (fileName.length() != NetworkCacheKey::hashStringLength())
return;
function(fileName, partitionPath);
});
@@ -116,13 +117,21 @@
return std::unique_ptr<NetworkCacheStorage>(new NetworkCacheStorage(networkCachePath));
}
-NetworkCacheStorage::NetworkCacheStorage(const String& directoryPath)
- : m_directoryPath(directoryPath)
+static String makeVersionedDirectoryPath(const String& baseDirectoryPath)
+{
+ String versionSubdirectory = versionDirectoryPrefix + String::number(NetworkCacheStorage::version);
+ return WebCore::pathByAppendingComponent(baseDirectoryPath, versionSubdirectory);
+}
+
+NetworkCacheStorage::NetworkCacheStorage(const String& baseDirectoryPath)
+ : m_baseDirectoryPath(baseDirectoryPath)
+ , m_directoryPath(makeVersionedDirectoryPath(baseDirectoryPath))
, m_ioQueue(adoptDispatch(dispatch_queue_create("com.apple.WebKit.Cache.Storage", DISPATCH_QUEUE_CONCURRENT)))
, m_backgroundIOQueue(adoptDispatch(dispatch_queue_create("com.apple.WebKit.Cache.Storage.Background", DISPATCH_QUEUE_CONCURRENT)))
{
dispatch_set_target_queue(m_backgroundIOQueue.get(), dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0));
+ deleteOldVersions();
initialize();
}
@@ -139,8 +148,9 @@
NetworkCacheKey::HashType hash;
if (!NetworkCacheKey::stringToHash(fileName, hash))
return;
- dispatch_async(dispatch_get_main_queue(), [this, hash] {
- m_contentsFilter.add(hash);
+ unsigned shortHash = NetworkCacheKey::toShortHash(hash);
+ dispatch_async(dispatch_get_main_queue(), [this, shortHash] {
+ m_contentsFilter.add(shortHash);
});
++entryCount;
});
@@ -344,8 +354,8 @@
{
ASSERT(RunLoop::isMain());
- if (m_contentsFilter.mayContain(key.hash()))
- m_contentsFilter.remove(key.hash());
+ if (m_contentsFilter.mayContain(key.shortHash()))
+ m_contentsFilter.remove(key.shortHash());
StringCapture filePathCapture(filePathForKey(key, m_directoryPath));
dispatch_async(m_ioQueue.get(), [this, filePathCapture] {
@@ -430,7 +440,7 @@
ASSERT(RunLoop::isMain());
ASSERT(priority <= maximumRetrievePriority);
- if (!m_contentsFilter.mayContain(key.hash())) {
+ if (!m_contentsFilter.mayContain(key.shortHash())) {
completionHandler(nullptr);
return;
}
@@ -449,7 +459,7 @@
{
ASSERT(RunLoop::isMain());
- m_contentsFilter.add(key.hash());
+ m_contentsFilter.add(key.shortHash());
++m_approximateEntryCount;
auto storeOperation = std::make_unique<StoreOperation>(StoreOperation { key, entry, WTF::move(completionHandler) });
@@ -470,8 +480,8 @@
ASSERT_UNUSED(done, done);
LOG(NetworkCacheStorage, "(NetworkProcess) write complete error=%d", error);
if (error) {
- if (m_contentsFilter.mayContain(store.key.hash()))
- m_contentsFilter.remove(store.key.hash());
+ if (m_contentsFilter.mayContain(store.key.shortHash()))
+ m_contentsFilter.remove(store.key.shortHash());
if (m_approximateEntryCount)
--m_approximateEntryCount;
}
@@ -493,7 +503,7 @@
{
ASSERT(RunLoop::isMain());
- if (!m_contentsFilter.mayContain(key.hash())) {
+ if (!m_contentsFilter.mayContain(key.shortHash())) {
LOG(NetworkCacheStorage, "(NetworkProcess) existing entry not found, storing full entry");
store(key, updateEntry, WTF::move(completionHandler));
return;
@@ -599,9 +609,10 @@
NetworkCacheKey::HashType hash;
if (!NetworkCacheKey::stringToHash(fileName, hash))
return;
- dispatch_async(dispatch_get_main_queue(), [this, hash] {
- if (m_contentsFilter.mayContain(hash))
- m_contentsFilter.remove(hash);
+ unsigned shortHash = NetworkCacheKey::toShortHash(hash);
+ dispatch_async(dispatch_get_main_queue(), [this, shortHash] {
+ if (m_contentsFilter.mayContain(shortHash))
+ m_contentsFilter.remove(shortHash);
});
});
m_approximateEntryCount = foundEntryCount - deletedCount;
@@ -611,6 +622,24 @@
});
}
+void NetworkCacheStorage::deleteOldVersions()
+{
+ // Delete V1 cache.
+ StringCapture cachePathCapture(m_baseDirectoryPath);
+ dispatch_async(m_backgroundIOQueue.get(), [cachePathCapture] {
+ String cachePath = cachePathCapture.string();
+ traverseDirectory(cachePath, DT_DIR, [&cachePath](const String& subdirName) {
+ if (subdirName.startsWith(versionDirectoryPrefix))
+ return;
+ String partitionPath = WebCore::pathByAppendingComponent(cachePath, subdirName);
+ traverseDirectory(partitionPath, DT_REG, [&partitionPath](const String& fileName) {
+ WebCore::deleteFile(WebCore::pathByAppendingComponent(partitionPath, fileName));
+ });
+ WebCore::deleteEmptyDirectory(partitionPath);
+ });
+ });
}
+}
+
#endif
