Changeset 182363 in webkit
- Timestamp:
- Apr 5, 2015 11:45:38 AM (9 years ago)
- Location:
- trunk
- Files:
-
- 8 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/Source/WTF/ChangeLog
r182321 r182363 1 2015-04-05 Antti Koivisto <antti@apple.com> 2 3 Bloom filter should support longer hashes 4 https://bugs.webkit.org/show_bug.cgi?id=143419 5 6 Reviewed by Dan Bernstein. 7 8 It currently supports 'unsigned' hash only which is inconvenient and doesn't have enough independent bits for larger filters. 9 10 Support arbitrarily sized hashes of type std::array<uint8_t, hashSize> (like SHA1::Digest and MD5::Digest). 11 12 * wtf/BloomFilter.h: 13 (WTF::BloomFilter<keyBits>::keysFromHash): 14 (WTF::BloomFilter<keyBits>::mayContain): 15 (WTF::BloomFilter<keyBits>::add): 16 1 17 2015-04-03 Antti Koivisto <antti@apple.com> 2 18 -
trunk/Source/WTF/wtf/BloomFilter.h
r182321 r182363 45 45 46 46 void add(unsigned hash); 47 // For example SHA1::Digest. 48 template <size_t hashSize> void add(const std::array<uint8_t, hashSize>&); 49 47 50 void add(const BloomFilter&); 48 51 … … 50 53 // but never false negatives (claim it doesn't contain a key it does). 51 54 bool mayContain(unsigned hash) const; 55 template <size_t hashSize> bool mayContain(const std::array<uint8_t, hashSize>&) const; 52 56 53 57 void clear(); … … 63 67 static unsigned arrayIndex(unsigned key) { return key / bitsPerPosition; } 64 68 static unsigned bitMask(unsigned key) { return 1 << (key % bitsPerPosition); } 69 template <size_t hashSize> static std::pair<unsigned, unsigned> keysFromHash(const std::array<uint8_t, hashSize>&); 65 70 66 71 bool isBitSet(unsigned key) const; … … 89 94 setBit(hash); 90 95 setBit(hash >> 16); 96 } 97 98 template <unsigned keyBits> 99 template <size_t hashSize> 100 inline std::pair<unsigned, unsigned> BloomFilter<keyBits>::keysFromHash(const std::array<uint8_t, hashSize>& hash) 101 { 102 // We could use larger k value than 2 for long hashes. 103 static_assert(hashSize >= 2 * sizeof(unsigned), "Hash array too short"); 104 return { 105 *reinterpret_cast<const unsigned*>(hash.data()), 106 *reinterpret_cast<const unsigned*>(hash.data() + sizeof(unsigned)) 107 }; 108 } 109 110 template <unsigned keyBits> 111 template <size_t hashSize> 112 inline bool BloomFilter<keyBits>::mayContain(const std::array<uint8_t, hashSize>& hash) const 113 { 114 auto keys = keysFromHash(hash); 115 return isBitSet(keys.first) && isBitSet(keys.second); 116 } 117 118 template <unsigned keyBits> 119 template <size_t hashSize> 120 inline void BloomFilter<keyBits>::add(const std::array<uint8_t, hashSize>& hash) 121 { 122 auto keys = keysFromHash(hash); 123 setBit(keys.first); 124 setBit(keys.second); 91 125 } 92 126 -
trunk/Source/WebKit2/ChangeLog
r182362 r182363 1 2015-04-05 Antti Koivisto <antti@apple.com> 2 3 Bloom filter should support longer hashes 4 https://bugs.webkit.org/show_bug.cgi?id=143419 5 6 Reviewed by Dan Bernstein. 7 8 Use the hash digest directly in the contents filter instead of going via shortHash. 9 10 * NetworkProcess/cache/NetworkCacheKey.h: 11 (WebKit::NetworkCache::Key::hash): 12 (WebKit::NetworkCache::Key::shortHash): Deleted. 13 (WebKit::NetworkCache::Key::toShortHash): Deleted. 14 15 No longer needed. 16 17 * NetworkProcess/cache/NetworkCacheStorage.cpp: 18 (WebKit::NetworkCache::Storage::synchronize): 19 (WebKit::NetworkCache::Storage::addToContentsFilter): 20 (WebKit::NetworkCache::Storage::mayContain): 21 * NetworkProcess/cache/NetworkCacheStorage.h: 22 1 23 2015-04-05 Antti Koivisto <antti@apple.com> 2 24 -
trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheKey.h
r182296 r182363 56 56 57 57 HashType hash() const { return m_hash; } 58 unsigned shortHash() const { return toShortHash(m_hash); }59 58 60 static unsigned toShortHash(const HashType& hash) { return *reinterpret_cast<const unsigned*>(hash.data()); }61 59 static bool stringToHash(const String&, HashType&); 62 60 -
trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.cpp
r182362 r182363 100 100 if (!fileSize) 101 101 return; 102 filter->add( Key::toShortHash(hash));102 filter->add(hash); 103 103 size += fileSize; 104 104 ++count; … … 127 127 128 128 if (m_contentsFilter) 129 m_contentsFilter->add(key. shortHash());129 m_contentsFilter->add(key.hash()); 130 130 131 131 // If we get new entries during filter synchronization take care to add them to the new filter as well. 132 132 if (m_synchronizationInProgress) 133 m_contentsFilterHashesAddedDuringSynchronization.append(key. shortHash());133 m_contentsFilterHashesAddedDuringSynchronization.append(key.hash()); 134 134 } 135 135 … … 137 137 { 138 138 ASSERT(RunLoop::isMain()); 139 return !m_contentsFilter || m_contentsFilter->mayContain(key. shortHash());139 return !m_contentsFilter || m_contentsFilter->mayContain(key.hash()); 140 140 } 141 141 -
trunk/Source/WebKit2/NetworkProcess/cache/NetworkCacheStorage.h
r182361 r182363 130 130 bool m_shrinkInProgress { false }; 131 131 132 Vector< unsigned> m_contentsFilterHashesAddedDuringSynchronization;132 Vector<Key::HashType> m_contentsFilterHashesAddedDuringSynchronization; 133 133 134 134 static const int maximumRetrievePriority = 4; -
trunk/Tools/ChangeLog
r182332 r182363 1 2015-04-05 Antti Koivisto <antti@apple.com> 2 3 Bloom filter should support longer hashes 4 https://bugs.webkit.org/show_bug.cgi?id=143419 5 6 Reviewed by Dan Bernstein. 7 8 * TestWebKitAPI/Tests/WTF/BloomFilter.cpp: 9 (TestWebKitAPI::generateRandomDigests): 10 (TestWebKitAPI::TEST): 11 1 12 2015-04-03 Csaba Osztrogonác <ossy@webkit.org> 2 13 -
trunk/Tools/TestWebKitAPI/Tests/WTF/BloomFilter.cpp
r182321 r182363 28 28 #include <wtf/BloomFilter.h> 29 29 #include <wtf/RandomNumber.h> 30 #include <wtf/SHA1.h> 30 31 31 32 namespace TestWebKitAPI { … … 39 40 } 40 41 42 static Vector<SHA1::Digest> generateRandomDigests(size_t hashCount) 43 { 44 Vector<SHA1::Digest> hashes; 45 SHA1 sha1; 46 for (unsigned i = 0; i < hashCount; ++i) { 47 double random = randomNumber(); 48 sha1.addBytes(reinterpret_cast<uint8_t*>(&random), sizeof(double)); 49 SHA1::Digest digest; 50 sha1.computeHash(digest); 51 hashes.append(digest); 52 } 53 return hashes; 54 } 55 41 56 TEST(WTF_BloomFilter, Basic) 42 57 { … … 56 71 mayContainCount += filter.mayContain(hash) ? 1 : 0; 57 72 // False positive rate is ~0.09% so this should always be true. 73 EXPECT_TRUE(mayContainCount < hashCount / 10); 74 75 for (auto hash : moreHashes) 76 filter.add(hash); 77 78 for (auto hash : hashes) 79 EXPECT_TRUE(filter.mayContain(hash)); 80 for (auto hash : moreHashes) 81 EXPECT_TRUE(filter.mayContain(hash)); 82 } 83 84 TEST(WTF_BloomFilter, BasicDigest) 85 { 86 const unsigned hashCount = 1000; 87 auto hashes = generateRandomDigests(hashCount); 88 89 BloomFilter<20> filter; 90 for (auto hash : hashes) 91 filter.add(hash); 92 93 for (auto hash : hashes) 94 EXPECT_TRUE(filter.mayContain(hash)); 95 96 auto moreHashes = generateRandomDigests(hashCount); 97 unsigned mayContainCount = 0; 98 for (auto hash : moreHashes) 99 mayContainCount += filter.mayContain(hash) ? 1 : 0; 100 // False positive rate is ~0.000004% so this should always be true. 58 101 EXPECT_TRUE(mayContainCount < hashCount / 10); 59 102
Note: See TracChangeset
for help on using the changeset viewer.