Line data    Source code

       1             : // Copyright (c) 2012-2021 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 <test/util/setup_common.h>
       6             : 
       7             : #include <cuckoocache.h>
       8             : #include <random.h>
       9             : #include <script/sigcache.h>
      10             : #include <test/util/random.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         146 : BOOST_AUTO_TEST_SUITE(cuckoocache_tests);
      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 insecure_GetRandHash calls
      38             :  */
      39         148 : BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes)
      40             : {
      41           1 :     SeedInsecureRand(SeedRand::ZEROS);
      42           1 :     CuckooCache::cache<uint256, SignatureCacheHasher> cc{};
      43           1 :     size_t megabytes = 4;
      44           1 :     cc.setup_bytes(megabytes << 20);
      45      100001 :     for (int x = 0; x < 100000; ++x) {
      46      100000 :         cc.insert(InsecureRand256());
      47      100000 :     }
      48      100001 :     for (int x = 0; x < 100000; ++x) {
      49      100000 :         BOOST_CHECK(!cc.contains(InsecureRand256(), false));
      50      100000 :     }
      51           1 : };
      52             : 
      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           5 : static double test_cache(size_t megabytes, double load)
      58             : {
      59           5 :     SeedInsecureRand(SeedRand::ZEROS);
      60           5 :     std::vector<uint256> hashes;
      61           5 :     Cache set{};
      62           5 :     size_t bytes = megabytes * (1 << 20);
      63           5 :     set.setup_bytes(bytes);
      64           5 :     uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
      65           5 :     hashes.resize(n_insert);
      66      406326 :     for (uint32_t i = 0; i < n_insert; ++i) {
      67      406321 :         uint32_t* ptr = (uint32_t*)hashes[i].begin();
      68     3656889 :         for (uint8_t j = 0; j < 8; ++j)
      69     3250568 :             *(ptr++) = InsecureRand32();
      70      406321 :     }
      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           5 :     std::vector<uint256> hashes_insert_copy = hashes;
      76             :     /** Do the insert */
      77      406326 :     for (const uint256& h : hashes_insert_copy)
      78      406321 :         set.insert(h);
      79             :     /** Count the hits */
      80           5 :     uint32_t count = 0;
      81      406326 :     for (const uint256& h : hashes)
      82      406321 :         count += set.contains(h, false);
      83           5 :     double hit_rate = ((double)count) / ((double)n_insert);
      84           5 :     return hit_rate;
      85           5 : }
      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           5 : static double normalize_hit_rate(double hits, double load)
     105             : {
     106           5 :     return hits * std::max(load, 1.0);
     107             : }
     108             : 
     109             : /** Check the hit rate on loads ranging from 0.1 to 1.6 */
     110         148 : BOOST_AUTO_TEST_CASE(cuckoocache_hit_rate_ok)
     111             : {
     112             :     /** Arbitrarily selected Hit Rate threshold that happens to work for this test
     113             :      * as a lower bound on performance.
     114             :      */
     115           1 :     double HitRateThresh = 0.98;
     116           1 :     size_t megabytes = 4;
     117           6 :     for (double load = 0.1; load < 2; load *= 2) {
     118           5 :         double hits = test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes, load);
     119           5 :         BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh);
     120           5 :     }
     121           1 : }
     122             : 
     123             : 
     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           1 : static void test_cache_erase(size_t megabytes)
     128             : {
     129           1 :     double load = 1;
     130           1 :     SeedInsecureRand(SeedRand::ZEROS);
     131           1 :     std::vector<uint256> hashes;
     132           1 :     Cache set{};
     133           1 :     size_t bytes = megabytes * (1 << 20);
     134           1 :     set.setup_bytes(bytes);
     135           1 :     uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
     136           1 :     hashes.resize(n_insert);
     137      131073 :     for (uint32_t i = 0; i < n_insert; ++i) {
     138      131072 :         uint32_t* ptr = (uint32_t*)hashes[i].begin();
     139     1179648 :         for (uint8_t j = 0; j < 8; ++j)
     140     1048576 :             *(ptr++) = InsecureRand32();
     141      131072 :     }
     142             :     /** We make a copy of the hashes because future optimizations of the
     143             :      * cuckoocache may overwrite the inserted element, so the test is
     144             :      * "future proofed".
     145             :      */
     146           1 :     std::vector<uint256> hashes_insert_copy = hashes;
     147             : 
     148             :     /** Insert the first half */
     149       65537 :     for (uint32_t i = 0; i < (n_insert / 2); ++i)
     150       65536 :         set.insert(hashes_insert_copy[i]);
     151             :     /** Erase the first quarter */
     152       32769 :     for (uint32_t i = 0; i < (n_insert / 4); ++i)
     153       32768 :         BOOST_CHECK(set.contains(hashes[i], true));
     154             :     /** Insert the second half */
     155       65537 :     for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
     156       65536 :         set.insert(hashes_insert_copy[i]);
     157             : 
     158             :     /** elements that we marked as erased but are still there */
     159           1 :     size_t count_erased_but_contained = 0;
     160             :     /** elements that we did not erase but are older */
     161           1 :     size_t count_stale = 0;
     162             :     /** elements that were most recently inserted */
     163           1 :     size_t count_fresh = 0;
     164             : 
     165       32769 :     for (uint32_t i = 0; i < (n_insert / 4); ++i)
     166       32768 :         count_erased_but_contained += set.contains(hashes[i], false);
     167       32769 :     for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
     168       32768 :         count_stale += set.contains(hashes[i], false);
     169       65537 :     for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
     170       65536 :         count_fresh += set.contains(hashes[i], false);
     171             : 
     172           1 :     double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
     173           1 :     double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
     174           1 :     double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
     175             : 
     176             :     // Check that our hit_rate_fresh is perfect
     177           1 :     BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0);
     178             :     // Check that we have a more than 2x better hit rate on stale elements than
     179             :     // erased elements.
     180           1 :     BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
     181           1 : }
     182             : 
     183         148 : BOOST_AUTO_TEST_CASE(cuckoocache_erase_ok)
     184             : {
     185           1 :     size_t megabytes = 4;
     186           1 :     test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
     187           1 : }
     188             : 
     189             : template <typename Cache>
     190           1 : static void test_cache_erase_parallel(size_t megabytes)
     191             : {
     192           1 :     double load = 1;
     193           1 :     SeedInsecureRand(SeedRand::ZEROS);
     194           1 :     std::vector<uint256> hashes;
     195           1 :     Cache set{};
     196           1 :     size_t bytes = megabytes * (1 << 20);
     197           1 :     set.setup_bytes(bytes);
     198           1 :     uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
     199           1 :     hashes.resize(n_insert);
     200      131073 :     for (uint32_t i = 0; i < n_insert; ++i) {
     201      131072 :         uint32_t* ptr = (uint32_t*)hashes[i].begin();
     202     1179648 :         for (uint8_t j = 0; j < 8; ++j)
     203     1048576 :             *(ptr++) = InsecureRand32();
     204      131072 :     }
     205             :     /** We make a copy of the hashes because future optimizations of the
     206             :      * cuckoocache may overwrite the inserted element, so the test is
     207             :      * "future proofed".
     208             :      */
     209           1 :     std::vector<uint256> hashes_insert_copy = hashes;
     210           1 :     std::shared_mutex mtx;
     211             : 
     212             :     {
     213             :         /** Grab lock to make sure we release inserts */
     214           1 :         std::unique_lock<std::shared_mutex> l(mtx);
     215             :         /** Insert the first half */
     216       65537 :         for (uint32_t i = 0; i < (n_insert / 2); ++i)
     217       65536 :             set.insert(hashes_insert_copy[i]);
     218           1 :     }
     219             : 
     220             :     /** Spin up 3 threads to run contains with erase.
     221             :      */
     222           1 :     std::vector<std::thread> threads;
     223           1 :     threads.reserve(3);
     224             :     /** Erase the first quarter */
     225           4 :     for (uint32_t x = 0; x < 3; ++x)
     226             :         /** Each thread is emplaced with x copy-by-value
     227             :         */
     228           6 :         threads.emplace_back([&, x] {
     229           3 :             std::shared_lock<std::shared_mutex> l(mtx);
     230           3 :             size_t ntodo = (n_insert/4)/3;
     231           3 :             size_t start = ntodo*x;
     232           3 :             size_t end = ntodo*(x+1);
     233       25995 :             for (uint32_t i = start; i < end; ++i) {
     234       25992 :                 bool contains = set.contains(hashes[i], true);
     235       25992 :                 assert(contains);
     236       25992 :             }
     237           3 :         });
     238             : 
     239             :     /** Wait for all threads to finish
     240             :      */
     241           4 :     for (std::thread& t : threads)
     242           3 :         t.join();
     243             :     /** Grab lock to make sure we observe erases */
     244           1 :     std::unique_lock<std::shared_mutex> l(mtx);
     245             :     /** Insert the second half */
     246       65537 :     for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
     247       65536 :         set.insert(hashes_insert_copy[i]);
     248             : 
     249             :     /** elements that we marked erased but that are still there */
     250           1 :     size_t count_erased_but_contained = 0;
     251             :     /** elements that we did not erase but are older */
     252           1 :     size_t count_stale = 0;
     253             :     /** elements that were most recently inserted */
     254           1 :     size_t count_fresh = 0;
     255             : 
     256       32769 :     for (uint32_t i = 0; i < (n_insert / 4); ++i)
     257       32768 :         count_erased_but_contained += set.contains(hashes[i], false);
     258       32769 :     for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
     259       32768 :         count_stale += set.contains(hashes[i], false);
     260       65537 :     for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
     261       65536 :         count_fresh += set.contains(hashes[i], false);
     262             : 
     263           1 :     double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
     264           1 :     double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
     265           1 :     double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
     266             : 
     267             :     // Check that our hit_rate_fresh is perfect
     268           1 :     BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0);
     269             :     // Check that we have a more than 2x better hit rate on stale elements than
     270             :     // erased elements.
     271           1 :     BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
     272           1 : }
     273         148 : BOOST_AUTO_TEST_CASE(cuckoocache_erase_parallel_ok)
     274             : {
     275           1 :     size_t megabytes = 4;
     276           1 :     test_cache_erase_parallel<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
     277           1 : }
     278             : 
     279             : 
     280             : template <typename Cache>
     281           1 : static 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           1 :     double min_hit_rate = 0.99;
     287           1 :     double tight_hit_rate = 0.999;
     288           1 :     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           1 :     SeedInsecureRand(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        2620 :         block_activity(uint32_t n_insert, Cache& c) : reads()
     308        1310 :         {
     309        1310 :             std::vector<uint256> inserts;
     310        1310 :             inserts.resize(n_insert);
     311        1310 :             reads.reserve(n_insert / 2);
     312     1311310 :             for (uint32_t i = 0; i < n_insert; ++i) {
     313     1310000 :                 uint32_t* ptr = (uint32_t*)inserts[i].begin();
     314    11790000 :                 for (uint8_t j = 0; j < 8; ++j)
     315    10480000 :                     *(ptr++) = InsecureRand32();
     316     1310000 :             }
     317      328810 :             for (uint32_t i = 0; i < n_insert / 4; ++i)
     318      327500 :                 reads.push_back(inserts[i]);
     319      328810 :             for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i)
     320      327500 :                 reads.push_back(inserts[i]);
     321     1311310 :             for (const auto& h : inserts)
     322     1310000 :                 c.insert(h);
     323        2620 :         }
     324             :     };
     325             : 
     326           1 :     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           1 :     const uint32_t WINDOW_SIZE = 60;
     330           1 :     const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2;
     331           1 :     const double load = 10;
     332           1 :     const size_t megabytes = 4;
     333           1 :     const size_t bytes = megabytes * (1 << 20);
     334           1 :     const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
     335             : 
     336           1 :     std::vector<block_activity> hashes;
     337           1 :     Cache set{};
     338           1 :     set.setup_bytes(bytes);
     339           1 :     hashes.reserve(n_insert / BLOCK_SIZE);
     340           1 :     std::deque<block_activity> last_few;
     341           1 :     uint32_t out_of_tight_tolerance = 0;
     342           1 :     uint32_t total = n_insert / BLOCK_SIZE;
     343             :     // we use the deque last_few to model a sliding window of blocks. at each
     344             :     // step, each of the last WINDOW_SIZE block_activities checks the cache for
     345             :     // POP_AMOUNT of the hashes that they inserted, and marks these erased.
     346        1311 :     for (uint32_t i = 0; i < total; ++i) {
     347        1310 :         if (last_few.size() == WINDOW_SIZE)
     348        1250 :             last_few.pop_front();
     349        1310 :         last_few.emplace_back(BLOCK_SIZE, set);
     350        1310 :         uint32_t count = 0;
     351       78140 :         for (auto& act : last_few)
     352      691470 :             for (uint32_t k = 0; k < POP_AMOUNT; ++k) {
     353      614640 :                 count += set.contains(act.reads.back(), true);
     354      614640 :                 act.reads.pop_back();
     355      614640 :             }
     356             :         // We use last_few.size() rather than WINDOW_SIZE for the correct
     357             :         // behavior on the first WINDOW_SIZE iterations where the deque is not
     358             :         // full yet.
     359        1310 :         double hit = (double(count)) / (last_few.size() * POP_AMOUNT);
     360             :         // Loose Check that hit rate is above min_hit_rate
     361        1310 :         BOOST_CHECK(hit > min_hit_rate);
     362             :         // Tighter check, count number of times we are less than tight_hit_rate
     363             :         // (and implicitly, greater than min_hit_rate)
     364        1310 :         out_of_tight_tolerance += hit < tight_hit_rate;
     365        1310 :     }
     366             :     // Check that being out of tolerance happens less than
     367             :     // max_rate_less_than_tight_hit_rate of the time
     368           1 :     BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate);
     369           1 : }
     370         148 : BOOST_AUTO_TEST_CASE(cuckoocache_generations)
     371             : {
     372           1 :     test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>();
     373           1 : }
     374             : 
     375         146 : BOOST_AUTO_TEST_SUITE_END();