src/test/coins_tests.cpp

   1 // Copyright (c) 2014 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 "coins.h"
   6 #include "random.h"
   7 #include "uint256.h"
   8
   9 #include <vector>
  10 #include <map>
  11
  12 #include <boost/test/unit_test.hpp>
  13
  14 namespace
  15 {
  16 class CCoinsViewTest : public CCoinsView
  17 {
  18     uint256 hashBestBlock_;
  19     std::map<uint256, CCoins> map_;
  20
  21 public:
  22     bool GetCoins(const uint256& txid, CCoins& coins) const
  23     {
  24         std::map<uint256, CCoins>::const_iterator it = map_.find(txid);
  25         if (it == map_.end()) {
  26             return false;
  27         }
  28         coins = it->second;
  29         if (coins.IsPruned() && insecure_rand() % 2 == 0) {
  30             // Randomly return false in case of an empty entry.
  31             return false;
  32         }
  33         return true;
  34     }
  35
  36     bool HaveCoins(const uint256& txid) const
  37     {
  38         CCoins coins;
  39         return GetCoins(txid, coins);
  40     }
  41
  42     uint256 GetBestBlock() const { return hashBestBlock_; }
  43
  44     bool BatchWrite(CCoinsMap& mapCoins, const uint256& hashBlock)
  45     {
  46         for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); ) {
  47             map_[it->first] = it->second.coins;
  48             if (it->second.coins.IsPruned() && insecure_rand() % 3 == 0) {
  49                 // Randomly delete empty entries on write.
  50                 map_.erase(it->first);
  51             }
  52             mapCoins.erase(it++);
  53         }
  54         mapCoins.clear();
  55         hashBestBlock_ = hashBlock;
  56         return true;
  57     }
  58
  59     bool GetStats(CCoinsStats& stats) const { return false; }
  60 };
  61 }
  62
  63 BOOST_AUTO_TEST_SUITE(coins_tests)
  64
  65 static const unsigned int NUM_SIMULATION_ITERATIONS = 40000;
  66
  67 // This is a large randomized insert/remove simulation test on a variable-size
  68 // stack of caches on top of CCoinsViewTest.
  69 //
  70 // It will randomly create/update/delete CCoins entries to a tip of caches, with
  71 // txids picked from a limited list of random 256-bit hashes. Occasionally, a
  72 // new tip is added to the stack of caches, or the tip is flushed and removed.
  73 //
  74 // During the process, booleans are kept to make sure that the randomized
  75 // operation hits all branches.
  76 BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
  77 {
  78     // Various coverage trackers.
  79     bool removed_all_caches = false;
  80     bool reached_4_caches = false;
  81     bool added_an_entry = false;
  82     bool removed_an_entry = false;
  83     bool updated_an_entry = false;
  84     bool found_an_entry = false;
  85     bool missed_an_entry = false;
  86
  87     // A simple map to track what we expect the cache stack to represent.
  88     std::map<uint256, CCoins> result;
  89
  90     // The cache stack.
  91     CCoinsViewTest base; // A CCoinsViewTest at the bottom.
  92     std::vector<CCoinsViewCache*> stack; // A stack of CCoinsViewCaches on top.
  93     stack.push_back(new CCoinsViewCache(&base)); // Start with one cache.
  94
  95     // Use a limited set of random transaction ids, so we do test overwriting entries.
  96     std::vector<uint256> txids;
  97     txids.resize(NUM_SIMULATION_ITERATIONS / 8);
  98     for (unsigned int i = 0; i < txids.size(); i++) {
  99         txids[i] = GetRandHash();
 100     }
 101
 102     for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
 103         // Do a random modification.
 104         {
 105             uint256 txid = txids[insecure_rand() % txids.size()]; // txid we're going to modify in this iteration.
 106             CCoins& coins = result[txid];
 107             CCoinsModifier entry = stack.back()->ModifyCoins(txid);
 108             BOOST_CHECK(coins == *entry);
 109             if (insecure_rand() % 5 == 0 || coins.IsPruned()) {
 110                 if (coins.IsPruned()) {
 111                     added_an_entry = true;
 112                 } else {
 113                     updated_an_entry = true;
 114                 }
 115                 coins.nVersion = insecure_rand();
 116                 coins.vout.resize(1);
 117                 coins.vout[0].nValue = insecure_rand();
 118                 *entry = coins;
 119             } else {
 120                 coins.Clear();
 121                 entry->Clear();
 122                 removed_an_entry = true;
 123             }
 124         }
 125
 126         // Once every 1000 iterations and at the end, verify the full cache.
 127         if (insecure_rand() % 1000 == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
 128             for (std::map<uint256, CCoins>::iterator it = result.begin(); it != result.end(); it++) {
 129                 const CCoins* coins = stack.back()->AccessCoins(it->first);
 130                 if (coins) {
 131                     BOOST_CHECK(*coins == it->second);
 132                     found_an_entry = true;
 133                 } else {
 134                     BOOST_CHECK(it->second.IsPruned());
 135                     missed_an_entry = true;
 136                 }
 137             }
 138         }
 139
 140         if (insecure_rand() % 100 == 0) {
 141             // Every 100 iterations, change the cache stack.
 142             if (stack.size() > 0 && insecure_rand() % 2 == 0) {
 143                 stack.back()->Flush();
 144                 delete stack.back();
 145                 stack.pop_back();
 146             }
 147             if (stack.size() == 0 || (stack.size() < 4 && insecure_rand() % 2)) {
 148                 CCoinsView* tip = &base;
 149                 if (stack.size() > 0) {
 150                     tip = stack.back();
 151                 } else {
 152                     removed_all_caches = true;
 153                 }
 154                 stack.push_back(new CCoinsViewCache(tip));
 155                 if (stack.size() == 4) {
 156                     reached_4_caches = true;
 157                 }
 158             }
 159         }
 160     }
 161
 162     // Clean up the stack.
 163     while (stack.size() > 0) {
 164         delete stack.back();
 165         stack.pop_back();
 166     }
 167
 168     // Verify coverage.
 169     BOOST_CHECK(removed_all_caches);
 170     BOOST_CHECK(reached_4_caches);
 171     BOOST_CHECK(added_an_entry);
 172     BOOST_CHECK(removed_an_entry);
 173     BOOST_CHECK(updated_an_entry);
 174     BOOST_CHECK(found_an_entry);
 175     BOOST_CHECK(missed_an_entry);
 176 }
 177
 178 BOOST_AUTO_TEST_SUITE_END()