cuckoocache_tests.cpp
1 // Copyright (c) 2012-present The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #include <cuckoocache.h> 6 #include <random.h> 7 #include <script/sigcache.h> 8 #include <test/util/random.h> 9 #include <test/util/setup_common.h> 10 #include <util/byte_units.h> 11 12 #include <boost/test/unit_test.hpp> 13 14 #include <deque> 15 #include <mutex> 16 #include <shared_mutex> 17 #include <thread> 18 #include <vector> 19 20 /** Test Suite for CuckooCache 21 * 22 * 1. All tests should have a deterministic result (using insecure rand 23 * with deterministic seeds) 24 * 2. Some test methods are templated to allow for easier testing 25 * against new versions / comparing 26 * 3. Results should be treated as a regression test, i.e., did the behavior 27 * change significantly from what was expected. This can be OK, depending on 28 * the nature of the change, but requires updating the tests to reflect the new 29 * expected behavior. For example improving the hit rate may cause some tests 30 * using BOOST_CHECK_CLOSE to fail. 31 * 32 */ 33 BOOST_FIXTURE_TEST_SUITE(cuckoocache_tests, BasicTestingSetup); 34 35 /* Test that no values not inserted into the cache are read out of it. 36 * 37 * There are no repeats in the first 200000 m_rng.rand256() calls 38 */ 39 BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) 40 { 41 SeedRandomForTest(SeedRand::ZEROS); 42 CuckooCache::cache<uint256, SignatureCacheHasher> cc{}; 43 cc.setup_bytes(4_MiB); 44 for (int x = 0; x < 100000; ++x) { 45 cc.insert(m_rng.rand256()); 46 } 47 for (int x = 0; x < 100000; ++x) { 48 BOOST_CHECK(!cc.contains(m_rng.rand256(), false)); 49 } 50 }; 51 52 struct HitRateTest : BasicTestingSetup { 53 /** This helper returns the hit rate when bytes*load worth of entries are 54 * inserted into a bytes sized cache 55 */ 56 template <typename Cache> 57 double test_cache(size_t bytes, double load) 58 { 59 SeedRandomForTest(SeedRand::ZEROS); 60 std::vector<uint256> hashes; 61 Cache set{}; 62 set.setup_bytes(bytes); 63 uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); 64 hashes.resize(n_insert); 65 for (uint32_t i = 0; i < n_insert; ++i) { 66 uint32_t* ptr = (uint32_t*)hashes[i].begin(); 67 for (uint8_t j = 0; j < 8; ++j) 68 *(ptr++) = m_rng.rand32(); 69 } 70 /** We make a copy of the hashes because future optimizations of the 71 * cuckoocache may overwrite the inserted element, so the test is 72 * "future proofed". 73 */ 74 std::vector<uint256> hashes_insert_copy = hashes; 75 /** Do the insert */ 76 for (const uint256& h : hashes_insert_copy) 77 set.insert(h); 78 /** Count the hits */ 79 uint32_t count = 0; 80 for (const uint256& h : hashes) 81 count += set.contains(h, false); 82 double hit_rate = ((double)count) / ((double)n_insert); 83 return hit_rate; 84 } 85 86 /** The normalized hit rate for a given load. 87 * 88 * The semantics are a little confusing, so please see the below 89 * explanation. 90 * 91 * Examples: 92 * 93 * 1. at load 0.5, we expect a perfect hit rate, so we multiply by 94 * 1.0 95 * 2. at load 2.0, we expect to see half the entries, so a perfect hit rate 96 * would be 0.5. Therefore, if we see a hit rate of 0.4, 0.4*2.0 = 0.8 is the 97 * normalized hit rate. 98 * 99 * This is basically the right semantics, but has a bit of a glitch depending on 100 * how you measure around load 1.0 as after load 1.0 your normalized hit rate 101 * becomes effectively perfect, ignoring freshness. 102 */ 103 static double normalize_hit_rate(double hits, double load) 104 { 105 return hits * std::max(load, 1.0); 106 } 107 }; // struct HitRateTest 108 109 /** Check the hit rate on loads ranging from 0.1 to 1.6 */ 110 BOOST_FIXTURE_TEST_CASE(cuckoocache_hit_rate_ok, HitRateTest) 111 { 112 /** Arbitrarily selected Hit Rate threshold that happens to work for this test 113 * as a lower bound on performance. 114 */ 115 double HitRateThresh = 0.98; 116 for (double load = 0.1; load < 2; load *= 2) { 117 double hits = test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>(4_MiB, load); 118 BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); 119 } 120 } 121 122 123 struct EraseTest : BasicTestingSetup { 124 /** This helper checks that erased elements are preferentially inserted onto and 125 * that the hit rate of "fresher" keys is reasonable*/ 126 template <typename Cache> 127 void test_cache_erase(size_t bytes) 128 { 129 double load = 1; 130 SeedRandomForTest(SeedRand::ZEROS); 131 std::vector<uint256> hashes; 132 Cache set{}; 133 set.setup_bytes(bytes); 134 uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); 135 hashes.resize(n_insert); 136 for (uint32_t i = 0; i < n_insert; ++i) { 137 uint32_t* ptr = (uint32_t*)hashes[i].begin(); 138 for (uint8_t j = 0; j < 8; ++j) 139 *(ptr++) = m_rng.rand32(); 140 } 141 /** We make a copy of the hashes because future optimizations of the 142 * cuckoocache may overwrite the inserted element, so the test is 143 * "future proofed". 144 */ 145 std::vector<uint256> hashes_insert_copy = hashes; 146 147 /** Insert the first half */ 148 for (uint32_t i = 0; i < (n_insert / 2); ++i) 149 set.insert(hashes_insert_copy[i]); 150 /** Erase the first quarter */ 151 for (uint32_t i = 0; i < (n_insert / 4); ++i) 152 BOOST_CHECK(set.contains(hashes[i], true)); 153 /** Insert the second half */ 154 for (uint32_t i = (n_insert / 2); i < n_insert; ++i) 155 set.insert(hashes_insert_copy[i]); 156 157 /** elements that we marked as erased but are still there */ 158 size_t count_erased_but_contained = 0; 159 /** elements that we did not erase but are older */ 160 size_t count_stale = 0; 161 /** elements that were most recently inserted */ 162 size_t count_fresh = 0; 163 164 for (uint32_t i = 0; i < (n_insert / 4); ++i) 165 count_erased_but_contained += set.contains(hashes[i], false); 166 for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i) 167 count_stale += set.contains(hashes[i], false); 168 for (uint32_t i = (n_insert / 2); i < n_insert; ++i) 169 count_fresh += set.contains(hashes[i], false); 170 171 double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0); 172 double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0); 173 double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0); 174 175 // Check that our hit_rate_fresh is perfect 176 BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); 177 // Check that we have a more than 2x better hit rate on stale elements than 178 // erased elements. 179 BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); 180 } 181 }; // struct EraseTest 182 183 BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_ok, EraseTest) 184 { 185 test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(4_MiB); 186 } 187 188 struct EraseParallelTest : BasicTestingSetup { 189 template <typename Cache> 190 void test_cache_erase_parallel(size_t bytes) 191 { 192 double load = 1; 193 SeedRandomForTest(SeedRand::ZEROS); 194 std::vector<uint256> hashes; 195 Cache set{}; 196 set.setup_bytes(bytes); 197 uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); 198 hashes.resize(n_insert); 199 for (uint32_t i = 0; i < n_insert; ++i) { 200 uint32_t* ptr = (uint32_t*)hashes[i].begin(); 201 for (uint8_t j = 0; j < 8; ++j) 202 *(ptr++) = m_rng.rand32(); 203 } 204 /** We make a copy of the hashes because future optimizations of the 205 * cuckoocache may overwrite the inserted element, so the test is 206 * "future proofed". 207 */ 208 std::vector<uint256> hashes_insert_copy = hashes; 209 std::shared_mutex mtx; 210 211 { 212 /** Grab lock to make sure we release inserts */ 213 std::unique_lock<std::shared_mutex> l(mtx); 214 /** Insert the first half */ 215 for (uint32_t i = 0; i < (n_insert / 2); ++i) 216 set.insert(hashes_insert_copy[i]); 217 } 218 219 /** Spin up 3 threads to run contains with erase. 220 */ 221 std::vector<std::thread> threads; 222 threads.reserve(3); 223 /** Erase the first quarter */ 224 for (uint32_t x = 0; x < 3; ++x) 225 /** Each thread is emplaced with x copy-by-value 226 */ 227 threads.emplace_back([&, x] { 228 std::shared_lock<std::shared_mutex> l(mtx); 229 size_t ntodo = (n_insert/4)/3; 230 size_t start = ntodo*x; 231 size_t end = ntodo*(x+1); 232 for (uint32_t i = start; i < end; ++i) { 233 bool contains = set.contains(hashes[i], true); 234 assert(contains); 235 } 236 }); 237 238 /** Wait for all threads to finish 239 */ 240 for (std::thread& t : threads) 241 t.join(); 242 /** Grab lock to make sure we observe erases */ 243 std::unique_lock<std::shared_mutex> l(mtx); 244 /** Insert the second half */ 245 for (uint32_t i = (n_insert / 2); i < n_insert; ++i) 246 set.insert(hashes_insert_copy[i]); 247 248 /** elements that we marked erased but that are still there */ 249 size_t count_erased_but_contained = 0; 250 /** elements that we did not erase but are older */ 251 size_t count_stale = 0; 252 /** elements that were most recently inserted */ 253 size_t count_fresh = 0; 254 255 for (uint32_t i = 0; i < (n_insert / 4); ++i) 256 count_erased_but_contained += set.contains(hashes[i], false); 257 for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i) 258 count_stale += set.contains(hashes[i], false); 259 for (uint32_t i = (n_insert / 2); i < n_insert; ++i) 260 count_fresh += set.contains(hashes[i], false); 261 262 double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0); 263 double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0); 264 double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0); 265 266 // Check that our hit_rate_fresh is perfect 267 BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0); 268 // Check that we have a more than 2x better hit rate on stale elements than 269 // erased elements. 270 BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained); 271 } 272 }; // struct EraseParallelTest 273 BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_parallel_ok, EraseParallelTest) 274 { 275 test_cache_erase_parallel<CuckooCache::cache<uint256, SignatureCacheHasher>>(4_MiB); 276 } 277 278 279 struct GenerationsTest : BasicTestingSetup { 280 template <typename Cache> 281 void test_cache_generations() 282 { 283 // This test checks that for a simulation of network activity, the fresh hit 284 // rate is never below 99%, and the number of times that it is worse than 285 // 99.9% are less than 1% of the time. 286 double min_hit_rate = 0.99; 287 double tight_hit_rate = 0.999; 288 double max_rate_less_than_tight_hit_rate = 0.01; 289 // A cache that meets this specification is therefore shown to have a hit 290 // rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) + 291 // min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% == 99.89% 292 // hit rate with low variance. 293 294 // We use deterministic values, but this test has also passed on many 295 // iterations with non-deterministic values, so it isn't "overfit" to the 296 // specific entropy in FastRandomContext(true) and implementation of the 297 // cache. 298 SeedRandomForTest(SeedRand::ZEROS); 299 300 // block_activity models a chunk of network activity. n_insert elements are 301 // added to the cache. The first and last n/4 are stored for removal later 302 // and the middle n/2 are not stored. This models a network which uses half 303 // the signatures of recently (since the last block) added transactions 304 // immediately and never uses the other half. 305 struct block_activity { 306 std::vector<uint256> reads; 307 block_activity(uint32_t n_insert, FastRandomContext& rng, Cache& c) 308 { 309 std::vector<uint256> inserts; 310 inserts.resize(n_insert); 311 reads.reserve(n_insert / 2); 312 for (uint32_t i = 0; i < n_insert; ++i) { 313 uint32_t* ptr = (uint32_t*)inserts[i].begin(); 314 for (uint8_t j = 0; j < 8; ++j) 315 *(ptr++) = rng.rand32(); 316 } 317 for (uint32_t i = 0; i < n_insert / 4; ++i) 318 reads.push_back(inserts[i]); 319 for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i) 320 reads.push_back(inserts[i]); 321 for (const auto& h : inserts) 322 c.insert(h); 323 } 324 }; 325 326 const uint32_t BLOCK_SIZE = 1000; 327 // We expect window size 60 to perform reasonably given that each epoch 328 // stores 45% of the cache size (~472k). 329 const uint32_t WINDOW_SIZE = 60; 330 const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2; 331 const double load = 10; 332 const size_t bytes{4_MiB}; 333 const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256))); 334 335 std::vector<block_activity> hashes; 336 Cache set{}; 337 set.setup_bytes(bytes); 338 hashes.reserve(n_insert / BLOCK_SIZE); 339 std::deque<block_activity> last_few; 340 uint32_t out_of_tight_tolerance = 0; 341 uint32_t total = n_insert / BLOCK_SIZE; 342 // we use the deque last_few to model a sliding window of blocks. at each 343 // step, each of the last WINDOW_SIZE block_activities checks the cache for 344 // POP_AMOUNT of the hashes that they inserted, and marks these erased. 345 for (uint32_t i = 0; i < total; ++i) { 346 if (last_few.size() == WINDOW_SIZE) 347 last_few.pop_front(); 348 last_few.emplace_back(BLOCK_SIZE, m_rng, set); 349 uint32_t count = 0; 350 for (auto& act : last_few) 351 for (uint32_t k = 0; k < POP_AMOUNT; ++k) { 352 count += set.contains(act.reads.back(), true); 353 act.reads.pop_back(); 354 } 355 // We use last_few.size() rather than WINDOW_SIZE for the correct 356 // behavior on the first WINDOW_SIZE iterations where the deque is not 357 // full yet. 358 double hit = (double(count)) / (last_few.size() * POP_AMOUNT); 359 // Loose Check that hit rate is above min_hit_rate 360 BOOST_CHECK(hit > min_hit_rate); 361 // Tighter check, count number of times we are less than tight_hit_rate 362 // (and implicitly, greater than min_hit_rate) 363 out_of_tight_tolerance += hit < tight_hit_rate; 364 } 365 // Check that being out of tolerance happens less than 366 // max_rate_less_than_tight_hit_rate of the time 367 BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate); 368 } 369 }; // struct GenerationsTest 370 BOOST_FIXTURE_TEST_CASE(cuckoocache_generations, GenerationsTest) 371 { 372 test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>(); 373 } 374 375 BOOST_AUTO_TEST_SUITE_END();