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