diff --git a/src/cuckoocache.h b/src/cuckoocache.h --- a/src/cuckoocache.h +++ b/src/cuckoocache.h @@ -121,9 +121,11 @@ * * Read Operations: * - contains() for `erase=false` + * - get() for `erase=false` * * Read+Erase Operations: * - contains() for `erase=true` + * - get() for `erase=true` * * Erase Operations: * - allow_erase() @@ -421,11 +423,14 @@ * is not guaranteed to return true. * * @param e the element to insert + * @param weither to replace if an existing element with the same key is + * found. * @post one of the following: All previously inserted elements and e are * now in the table, one previously inserted element is evicted from the - * table, the entry attempted to be inserted is evicted. + * table, the entry attempted to be inserted is evicted. If replace is true + * and a matching element already exists, it is updated accordingly. */ - inline void insert(Element e) { + inline void insert(Element e, bool replace = false) { epoch_check(); uint32_t last_loc = invalid(); bool last_epoch = true; @@ -434,6 +439,9 @@ // If we have, make sure that it does not get deleted. for (const uint32_t loc : locs) { if (table[loc].getKey() == e.getKey()) { + if (replace) { + table[loc] = std::move(e); + } please_keep(loc); epoch_flags[loc] = last_epoch; return; @@ -501,24 +509,50 @@ * * contains returns a bool set true if the element was found. * - * @param e the element to check + * @param k the key to check * @param erase whether to attempt setting the garbage collect flag * * @post if erase is true and the element is found, then the garbage collect * flag is set * @returns true if the element is found, false otherwise */ - inline bool contains(const Key &k, const bool erase) const { + bool contains(const Key &k, const bool erase) const { + return find(k, erase) != nullptr; + } + + /** + * get is almost identical to contains(), with the difference that it + * obtains the found element (for Elements that contain key and value, + * this has the effect of obtaining the found value). + * + * @param e the element to check + * @param erase + * + * @post If the element is found, it is copied into e. If erase is true + * and the element is found, then the garbage collect flag is set. + * @returns true if the element is found, false otherwise + */ + bool get(Element &e, const bool erase) const { + if (const Element *eptr = find(e.getKey(), erase)) { + e = *eptr; + return true; + } + + return false; + } + +private: + const Element *find(const Key &k, const bool erase) const { std::array locs = compute_hashes(k); for (const uint32_t loc : locs) { if (table[loc].getKey() == k) { if (erase) { allow_erase(loc); } - return true; + return &table[loc]; } } - return false; + return nullptr; } }; diff --git a/src/test/cuckoocache_tests.cpp b/src/test/cuckoocache_tests.cpp --- a/src/test/cuckoocache_tests.cpp +++ b/src/test/cuckoocache_tests.cpp @@ -27,15 +27,88 @@ */ BOOST_AUTO_TEST_SUITE(cuckoocache_tests); +/** + * Example key/value element. The key is 28 bytes long and the value 4, for a + * total of 32 bytes. + */ +struct TestMapElement { + struct KeyType { + std::array data; + + KeyType() = default; + KeyType(const KeyType &rhs) = default; + + KeyType(const uint256 &k) { + std::copy(k.begin() + 4, k.end(), data.begin()); + } + + bool operator==(const KeyType &rhs) const { return rhs.data == data; } + }; + +private: + KeyType key; + uint32_t value; + +public: + TestMapElement() = default; + TestMapElement(const TestMapElement &rhs) = default; + + TestMapElement(const uint256 &data) + : TestMapElement(data, data.GetUint64(0)) {} + TestMapElement(const KeyType &keyIn, uint32_t valueIn) + : key(keyIn), value(valueIn) {} + + const KeyType &getKey() const { return key; } + uint32_t getValue() const { return value; } + + class CacheHasher { + public: + template + uint32_t operator()(const KeyType &k) const { + static_assert(hash_select < 8, "only has 8 hashes available."); + + const auto &d = k.data; + + uint32_t u; + if (hash_select < 7) { + std::memcpy(&u, d.begin() + 4 * hash_select, 4); + } else { + // We are required to produce 8 subhashes but all key bytes have + // been used once already. So, we grab a mix of bits from each + // of the other blobs. We try to ensure more entropy on the + // higher bits, as these are what primarily get used to + // determine the index. + u = (uint32_t(d[0] & 0x07) << 29) + + (uint32_t(d[4] & 0x07) << 26) + + (uint32_t(d[8] & 0x0f) << 22) + + (uint32_t(d[16] & 0x3f) << 16) + + (uint32_t(d[20] & 0xff) << 8) + + (uint32_t(d[24] & 0xff) << 0); + } + return u; + } + }; + + friend class CuckooCache::cache; +}; + +static_assert(sizeof(TestMapElement) == 32, "TestMapElement must be 32 bytes"); + +// For convenience. +using CuckooCacheSet = + CuckooCache::cache, SignatureCacheHasher>; +using CuckooCacheMap = + CuckooCache::cache; +using TestMapKey = TestMapElement::KeyType; + /** * Test that no values not inserted into the cache are read out of it. * - * There are no repeats in the first 200000 insecure_GetRandHash calls + * There are no repeats in the first 400000 insecure_GetRandHash calls */ BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) { SeedInsecureRand(true); - CuckooCache::cache, SignatureCacheHasher> - cc{}; + CuckooCacheSet cc{}; size_t megabytes = 4; cc.setup_bytes(megabytes << 20); for (int x = 0; x < 100000; ++x) { @@ -44,6 +117,15 @@ for (int x = 0; x < 100000; ++x) { BOOST_CHECK(!cc.contains(InsecureRand256(), false)); } + + CuckooCacheMap cm{}; + cm.setup_bytes(megabytes << 20); + for (int x = 0; x < 100000; ++x) { + cm.insert(TestMapElement(InsecureRand256())); + } + for (int x = 0; x < 100000; ++x) { + BOOST_CHECK(!cm.contains(TestMapKey(InsecureRand256()), false)); + } }; /** @@ -58,9 +140,9 @@ size_t bytes = megabytes * (1 << 20); set.setup_bytes(bytes); uint32_t n_insert = static_cast(load * (bytes / sizeof(uint256))); - hashes.resize(n_insert); + hashes.reserve(n_insert); for (uint32_t i = 0; i < n_insert; ++i) { - hashes[i] = InsecureRand256(); + hashes.emplace_back(InsecureRand256()); } /** * We make a copy of the hashes because future optimizations of the @@ -112,10 +194,12 @@ double HitRateThresh = 0.98; size_t megabytes = 4; for (double load = 0.1; load < 2; load *= 2) { - double hits = - test_cache, - SignatureCacheHasher>>(megabytes, - load); + double hits = test_cache(megabytes, load); + BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); + } + + for (double load = 0.1; load < 2; load *= 2) { + double hits = test_cache(megabytes, load); BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); } } @@ -187,8 +271,8 @@ BOOST_AUTO_TEST_CASE(cuckoocache_erase_ok) { size_t megabytes = 4; - test_cache_erase, - SignatureCacheHasher>>(megabytes); + test_cache_erase(megabytes); + test_cache_erase(megabytes); } template @@ -280,9 +364,8 @@ BOOST_AUTO_TEST_CASE(cuckoocache_erase_parallel_ok) { size_t megabytes = 4; - test_cache_erase_parallel, - SignatureCacheHasher>>( - megabytes); + test_cache_erase_parallel(megabytes); + test_cache_erase_parallel(megabytes); } template static void test_cache_generations() { @@ -379,9 +462,63 @@ BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate); } + BOOST_AUTO_TEST_CASE(cuckoocache_generations) { - test_cache_generations, - SignatureCacheHasher>>(); + test_cache_generations(); + test_cache_generations(); +} + +BOOST_AUTO_TEST_CASE(cuckoocache_map_element) { + // Check the hash is parsed properly. + uint256 hash = uint256S( + "baadf00dcafebeef00000000bada550ff1ce00000000000000000000deadc0de"); + uint256 key = uint256S( + "baadf00dcafebeef00000000bada550ff1ce00000000000000000000abadba5e"); + const TestMapElement e(hash); + + BOOST_CHECK_EQUAL(e.getValue(), 0xdeadc0de); + BOOST_CHECK(e.getKey() == TestMapElement(key).getKey()); +} + +BOOST_AUTO_TEST_CASE(cuckoocache_map) { + SeedInsecureRand(true); + + // 4k cache. + CuckooCacheMap cm{}; + cm.setup_bytes(4 * 1024); + + for (int x = 0; x < 100000; ++x) { + const TestMapElement e1(InsecureRand256()); + const TestMapElement e2(e1.getKey(), e1.getValue() ^ 0xbabe); + + BOOST_CHECK(e1.getKey() == e2.getKey()); + BOOST_CHECK(e1.getValue() != e2.getValue()); + + // Insert a KV pair in the map and checks that it is effectively + // inserted. + BOOST_CHECK(!cm.contains(e1.getKey(), false)); + cm.insert(e1); + BOOST_CHECK(cm.contains(e1.getKey(), false)); + + // Check that we recover the proper value from the map. + TestMapElement e(e1.getKey(), 0); + BOOST_CHECK(cm.get(e, false)); + BOOST_CHECK(e.getKey() == e1.getKey()); + BOOST_CHECK(e.getValue() == e1.getValue()); + + // Insert without replace will not change the value. + e = e2; + cm.insert(e2); + BOOST_CHECK(cm.get(e, false)); + BOOST_CHECK(e.getKey() == e1.getKey()); + BOOST_CHECK(e.getValue() == e1.getValue()); + + // Insert and replace. + cm.insert(e2, true); + BOOST_CHECK(cm.get(e, false)); + BOOST_CHECK(e.getKey() == e2.getKey()); + BOOST_CHECK(e.getValue() == e2.getValue()); + } } BOOST_AUTO_TEST_SUITE_END();