Line data    Source code

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