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