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();