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