src/test/coins_tests.cpp

   1 // Copyright (c) 2014-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 "coins.h"
   6 #include "script/standard.h"
   7 #include "uint256.h"
   8 #include "undo.h"
   9 #include "utilstrencodings.h"
  10 #include "test/test_bitcoin.h"
  11 #include "validation.h"
  12 #include "consensus/validation.h"
  13
  14 #include <vector>
  15 #include <map>
  16
  17 #include <boost/test/unit_test.hpp>
  18
  19 int ApplyTxInUndo(Coin&& undo, CCoinsViewCache& view, const COutPoint& out);
  20 void UpdateCoins(const CTransaction& tx, CCoinsViewCache& inputs, CTxUndo &txundo, int nHeight);
  21
  22 namespace
  23 {
  24 //! equality test
  25 bool operator==(const Coin &a, const Coin &b) {
  26     // Empty Coin objects are always equal.
  27     if (a.IsSpent() && b.IsSpent()) return true;
  28     return a.fCoinBase == b.fCoinBase &&
  29            a.nHeight == b.nHeight &&
  30            a.out == b.out;
  31 }
  32
  33 class CCoinsViewTest : public CCoinsView
  34 {
  35     uint256 hashBestBlock_;
  36     std::map<COutPoint, Coin> map_;
  37
  38 public:
  39     bool GetCoin(const COutPoint& outpoint, Coin& coin) const override
  40     {
  41         std::map<COutPoint, Coin>::const_iterator it = map_.find(outpoint);
  42         if (it == map_.end()) {
  43             return false;
  44         }
  45         coin = it->second;
  46         if (coin.IsSpent() && InsecureRandBool() == 0) {
  47             // Randomly return false in case of an empty entry.
  48             return false;
  49         }
  50         return true;
  51     }
  52
  53     uint256 GetBestBlock() const override { return hashBestBlock_; }
  54
  55     bool BatchWrite(CCoinsMap& mapCoins, const uint256& hashBlock) override
  56     {
  57         for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); ) {
  58             if (it->second.flags & CCoinsCacheEntry::DIRTY) {
  59                 // Same optimization used in CCoinsViewDB is to only write dirty entries.
  60                 map_[it->first] = it->second.coin;
  61                 if (it->second.coin.IsSpent() && InsecureRandRange(3) == 0) {
  62                     // Randomly delete empty entries on write.
  63                     map_.erase(it->first);
  64                 }
  65             }
  66             mapCoins.erase(it++);
  67         }
  68         if (!hashBlock.IsNull())
  69             hashBestBlock_ = hashBlock;
  70         return true;
  71     }
  72 };
  73
  74 class CCoinsViewCacheTest : public CCoinsViewCache
  75 {
  76 public:
  77     CCoinsViewCacheTest(CCoinsView* _base) : CCoinsViewCache(_base) {}
  78
  79     void SelfTest() const
  80     {
  81         // Manually recompute the dynamic usage of the whole data, and compare it.
  82         size_t ret = memusage::DynamicUsage(cacheCoins);
  83         size_t count = 0;
  84         for (CCoinsMap::iterator it = cacheCoins.begin(); it != cacheCoins.end(); it++) {
  85             ret += it->second.coin.DynamicMemoryUsage();
  86             ++count;
  87         }
  88         BOOST_CHECK_EQUAL(GetCacheSize(), count);
  89         BOOST_CHECK_EQUAL(DynamicMemoryUsage(), ret);
  90     }
  91
  92     CCoinsMap& map() { return cacheCoins; }
  93     size_t& usage() { return cachedCoinsUsage; }
  94 };
  95
  96 } // namespace
  97
  98 BOOST_FIXTURE_TEST_SUITE(coins_tests, BasicTestingSetup)
  99
 100 static const unsigned int NUM_SIMULATION_ITERATIONS = 40000;
 101
 102 // This is a large randomized insert/remove simulation test on a variable-size
 103 // stack of caches on top of CCoinsViewTest.
 104 //
 105 // It will randomly create/update/delete Coin entries to a tip of caches, with
 106 // txids picked from a limited list of random 256-bit hashes. Occasionally, a
 107 // new tip is added to the stack of caches, or the tip is flushed and removed.
 108 //
 109 // During the process, booleans are kept to make sure that the randomized
 110 // operation hits all branches.
 111 BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
 112 {
 113     // Various coverage trackers.
 114     bool removed_all_caches = false;
 115     bool reached_4_caches = false;
 116     bool added_an_entry = false;
 117     bool added_an_unspendable_entry = false;
 118     bool removed_an_entry = false;
 119     bool updated_an_entry = false;
 120     bool found_an_entry = false;
 121     bool missed_an_entry = false;
 122     bool uncached_an_entry = false;
 123
 124     // A simple map to track what we expect the cache stack to represent.
 125     std::map<COutPoint, Coin> result;
 126
 127     // The cache stack.
 128     CCoinsViewTest base; // A CCoinsViewTest at the bottom.
 129     std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top.
 130     stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
 131
 132     // Use a limited set of random transaction ids, so we do test overwriting entries.
 133     std::vector<uint256> txids;
 134     txids.resize(NUM_SIMULATION_ITERATIONS / 8);
 135     for (unsigned int i = 0; i < txids.size(); i++) {
 136         txids[i] = InsecureRand256();
 137     }
 138
 139     for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
 140         // Do a random modification.
 141         {
 142             uint256 txid = txids[InsecureRandRange(txids.size())]; // txid we're going to modify in this iteration.
 143             Coin& coin = result[COutPoint(txid, 0)];
 144
 145             // Determine whether to test HaveCoin before or after Access* (or both). As these functions
 146             // can influence each other's behaviour by pulling things into the cache, all combinations
 147             // are tested.
 148             bool test_havecoin_before = InsecureRandBits(2) == 0;
 149             bool test_havecoin_after = InsecureRandBits(2) == 0;
 150
 151             bool result_havecoin = test_havecoin_before ? stack.back()->HaveCoin(COutPoint(txid, 0)) : false;
 152             const Coin& entry = (InsecureRandRange(500) == 0) ? AccessByTxid(*stack.back(), txid) : stack.back()->AccessCoin(COutPoint(txid, 0));
 153             BOOST_CHECK(coin == entry);
 154             BOOST_CHECK(!test_havecoin_before || result_havecoin == !entry.IsSpent());
 155
 156             if (test_havecoin_after) {
 157                 bool ret = stack.back()->HaveCoin(COutPoint(txid, 0));
 158                 BOOST_CHECK(ret == !entry.IsSpent());
 159             }
 160
 161             if (InsecureRandRange(5) == 0 || coin.IsSpent()) {
 162                 Coin newcoin;
 163                 newcoin.out.nValue = InsecureRand32();
 164                 newcoin.nHeight = 1;
 165                 if (InsecureRandRange(16) == 0 && coin.IsSpent()) {
 166                     newcoin.out.scriptPubKey.assign(1 + InsecureRandBits(6), OP_RETURN);
 167                     BOOST_CHECK(newcoin.out.scriptPubKey.IsUnspendable());
 168                     added_an_unspendable_entry = true;
 169                 } else {
 170                     newcoin.out.scriptPubKey.assign(InsecureRandBits(6), 0); // Random sizes so we can test memory usage accounting
 171                     (coin.IsSpent() ? added_an_entry : updated_an_entry) = true;
 172                     coin = newcoin;
 173                 }
 174                 stack.back()->AddCoin(COutPoint(txid, 0), std::move(newcoin), !coin.IsSpent() || InsecureRand32() & 1);
 175             } else {
 176                 removed_an_entry = true;
 177                 coin.Clear();
 178                 stack.back()->SpendCoin(COutPoint(txid, 0));
 179             }
 180         }
 181
 182         // One every 10 iterations, remove a random entry from the cache
 183         if (InsecureRandRange(10) == 0) {
 184             COutPoint out(txids[InsecureRand32() % txids.size()], 0);
 185             int cacheid = InsecureRand32() % stack.size();
 186             stack[cacheid]->Uncache(out);
 187             uncached_an_entry |= !stack[cacheid]->HaveCoinInCache(out);
 188         }
 189
 190         // Once every 1000 iterations and at the end, verify the full cache.
 191         if (InsecureRandRange(1000) == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
 192             for (auto it = result.begin(); it != result.end(); it++) {
 193                 bool have = stack.back()->HaveCoin(it->first);
 194                 const Coin& coin = stack.back()->AccessCoin(it->first);
 195                 BOOST_CHECK(have == !coin.IsSpent());
 196                 BOOST_CHECK(coin == it->second);
 197                 if (coin.IsSpent()) {
 198                     missed_an_entry = true;
 199                 } else {
 200                     BOOST_CHECK(stack.back()->HaveCoinInCache(it->first));
 201                     found_an_entry = true;
 202                 }
 203             }
 204             for (const CCoinsViewCacheTest *test : stack) {
 205                 test->SelfTest();
 206             }
 207         }
 208
 209         if (InsecureRandRange(100) == 0) {
 210             // Every 100 iterations, flush an intermediate cache
 211             if (stack.size() > 1 && InsecureRandBool() == 0) {
 212                 unsigned int flushIndex = InsecureRandRange(stack.size() - 1);
 213                 stack[flushIndex]->Flush();
 214             }
 215         }
 216         if (InsecureRandRange(100) == 0) {
 217             // Every 100 iterations, change the cache stack.
 218             if (stack.size() > 0 && InsecureRandBool() == 0) {
 219                 //Remove the top cache
 220                 stack.back()->Flush();
 221                 delete stack.back();
 222                 stack.pop_back();
 223             }
 224             if (stack.size() == 0 || (stack.size() < 4 && InsecureRandBool())) {
 225                 //Add a new cache
 226                 CCoinsView* tip = &base;
 227                 if (stack.size() > 0) {
 228                     tip = stack.back();
 229                 } else {
 230                     removed_all_caches = true;
 231                 }
 232                 stack.push_back(new CCoinsViewCacheTest(tip));
 233                 if (stack.size() == 4) {
 234                     reached_4_caches = true;
 235                 }
 236             }
 237         }
 238     }
 239
 240     // Clean up the stack.
 241     while (stack.size() > 0) {
 242         delete stack.back();
 243         stack.pop_back();
 244     }
 245
 246     // Verify coverage.
 247     BOOST_CHECK(removed_all_caches);
 248     BOOST_CHECK(reached_4_caches);
 249     BOOST_CHECK(added_an_entry);
 250     BOOST_CHECK(added_an_unspendable_entry);
 251     BOOST_CHECK(removed_an_entry);
 252     BOOST_CHECK(updated_an_entry);
 253     BOOST_CHECK(found_an_entry);
 254     BOOST_CHECK(missed_an_entry);
 255     BOOST_CHECK(uncached_an_entry);
 256 }
 257
 258 // Store of all necessary tx and undo data for next test
 259 typedef std::map<COutPoint, std::tuple<CTransaction,CTxUndo,Coin>> UtxoData;
 260 UtxoData utxoData;
 261
 262 UtxoData::iterator FindRandomFrom(const std::set<COutPoint> &utxoSet) {
 263     assert(utxoSet.size());
 264     auto utxoSetIt = utxoSet.lower_bound(COutPoint(InsecureRand256(), 0));
 265     if (utxoSetIt == utxoSet.end()) {
 266         utxoSetIt = utxoSet.begin();
 267     }
 268     auto utxoDataIt = utxoData.find(*utxoSetIt);
 269     assert(utxoDataIt != utxoData.end());
 270     return utxoDataIt;
 271 }
 272
 273
 274 // This test is similar to the previous test
 275 // except the emphasis is on testing the functionality of UpdateCoins
 276 // random txs are created and UpdateCoins is used to update the cache stack
 277 // In particular it is tested that spending a duplicate coinbase tx
 278 // has the expected effect (the other duplicate is overwritten at all cache levels)
 279 BOOST_AUTO_TEST_CASE(updatecoins_simulation_test)
 280 {
 281     bool spent_a_duplicate_coinbase = false;
 282     // A simple map to track what we expect the cache stack to represent.
 283     std::map<COutPoint, Coin> result;
 284
 285     // The cache stack.
 286     CCoinsViewTest base; // A CCoinsViewTest at the bottom.
 287     std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top.
 288     stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
 289
 290     // Track the txids we've used in various sets
 291     std::set<COutPoint> coinbase_coins;
 292     std::set<COutPoint> disconnected_coins;
 293     std::set<COutPoint> duplicate_coins;
 294     std::set<COutPoint> utxoset;
 295
 296     for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
 297         uint32_t randiter = InsecureRand32();
 298
 299         // 19/20 txs add a new transaction
 300         if (randiter % 20 < 19) {
 301             CMutableTransaction tx;
 302             tx.vin.resize(1);
 303             tx.vout.resize(1);
 304             tx.vout[0].nValue = i; //Keep txs unique unless intended to duplicate
 305             tx.vout[0].scriptPubKey.assign(InsecureRand32() & 0x3F, 0); // Random sizes so we can test memory usage accounting
 306             unsigned int height = InsecureRand32();
 307             Coin old_coin;
 308
 309             // 2/20 times create a new coinbase
 310             if (randiter % 20 < 2 || coinbase_coins.size() < 10) {
 311                 // 1/10 of those times create a duplicate coinbase
 312                 if (InsecureRandRange(10) == 0 && coinbase_coins.size()) {
 313                     auto utxod = FindRandomFrom(coinbase_coins);
 314                     // Reuse the exact same coinbase
 315                     tx = std::get<0>(utxod->second);
 316                     // shouldn't be available for reconnection if its been duplicated
 317                     disconnected_coins.erase(utxod->first);
 318
 319                     duplicate_coins.insert(utxod->first);
 320                 }
 321                 else {
 322                     coinbase_coins.insert(COutPoint(tx.GetHash(), 0));
 323                 }
 324                 assert(CTransaction(tx).IsCoinBase());
 325             }
 326
 327             // 17/20 times reconnect previous or add a regular tx
 328             else {
 329
 330                 COutPoint prevout;
 331                 // 1/20 times reconnect a previously disconnected tx
 332                 if (randiter % 20 == 2 && disconnected_coins.size()) {
 333                     auto utxod = FindRandomFrom(disconnected_coins);
 334                     tx = std::get<0>(utxod->second);
 335                     prevout = tx.vin[0].prevout;
 336                     if (!CTransaction(tx).IsCoinBase() && !utxoset.count(prevout)) {
 337                         disconnected_coins.erase(utxod->first);
 338                         continue;
 339                     }
 340
 341                     // If this tx is already IN the UTXO, then it must be a coinbase, and it must be a duplicate
 342                     if (utxoset.count(utxod->first)) {
 343                         assert(CTransaction(tx).IsCoinBase());
 344                         assert(duplicate_coins.count(utxod->first));
 345                     }
 346                     disconnected_coins.erase(utxod->first);
 347                 }
 348
 349                 // 16/20 times create a regular tx
 350                 else {
 351                     auto utxod = FindRandomFrom(utxoset);
 352                     prevout = utxod->first;
 353
 354                     // Construct the tx to spend the coins of prevouthash
 355                     tx.vin[0].prevout = prevout;
 356                     assert(!CTransaction(tx).IsCoinBase());
 357                 }
 358                 // In this simple test coins only have two states, spent or unspent, save the unspent state to restore
 359                 old_coin = result[prevout];
 360                 // Update the expected result of prevouthash to know these coins are spent
 361                 result[prevout].Clear();
 362
 363                 utxoset.erase(prevout);
 364
 365                 // The test is designed to ensure spending a duplicate coinbase will work properly
 366                 // if that ever happens and not resurrect the previously overwritten coinbase
 367                 if (duplicate_coins.count(prevout)) {
 368                     spent_a_duplicate_coinbase = true;
 369                 }
 370
 371             }
 372             // Update the expected result to know about the new output coins
 373             assert(tx.vout.size() == 1);
 374             const COutPoint outpoint(tx.GetHash(), 0);
 375             result[outpoint] = Coin(tx.vout[0], height, CTransaction(tx).IsCoinBase());
 376
 377             // Call UpdateCoins on the top cache
 378             CTxUndo undo;
 379             UpdateCoins(tx, *(stack.back()), undo, height);
 380
 381             // Update the utxo set for future spends
 382             utxoset.insert(outpoint);
 383
 384             // Track this tx and undo info to use later
 385             utxoData.emplace(outpoint, std::make_tuple(tx,undo,old_coin));
 386         } else if (utxoset.size()) {
 387             //1/20 times undo a previous transaction
 388             auto utxod = FindRandomFrom(utxoset);
 389
 390             CTransaction &tx = std::get<0>(utxod->second);
 391             CTxUndo &undo = std::get<1>(utxod->second);
 392             Coin &orig_coin = std::get<2>(utxod->second);
 393
 394             // Update the expected result
 395             // Remove new outputs
 396             result[utxod->first].Clear();
 397             // If not coinbase restore prevout
 398             if (!tx.IsCoinBase()) {
 399                 result[tx.vin[0].prevout] = orig_coin;
 400             }
 401
 402             // Disconnect the tx from the current UTXO
 403             // See code in DisconnectBlock
 404             // remove outputs
 405             stack.back()->SpendCoin(utxod->first);
 406             // restore inputs
 407             if (!tx.IsCoinBase()) {
 408                 const COutPoint &out = tx.vin[0].prevout;
 409                 Coin coin = undo.vprevout[0];
 410                 ApplyTxInUndo(std::move(coin), *(stack.back()), out);
 411             }
 412             // Store as a candidate for reconnection
 413             disconnected_coins.insert(utxod->first);
 414
 415             // Update the utxoset
 416             utxoset.erase(utxod->first);
 417             if (!tx.IsCoinBase())
 418                 utxoset.insert(tx.vin[0].prevout);
 419         }
 420
 421         // Once every 1000 iterations and at the end, verify the full cache.
 422         if (InsecureRandRange(1000) == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
 423             for (auto it = result.begin(); it != result.end(); it++) {
 424                 bool have = stack.back()->HaveCoin(it->first);
 425                 const Coin& coin = stack.back()->AccessCoin(it->first);
 426                 BOOST_CHECK(have == !coin.IsSpent());
 427                 BOOST_CHECK(coin == it->second);
 428             }
 429         }
 430
 431         // One every 10 iterations, remove a random entry from the cache
 432         if (utxoset.size() > 1 && InsecureRandRange(30) == 0) {
 433             stack[InsecureRand32() % stack.size()]->Uncache(FindRandomFrom(utxoset)->first);
 434         }
 435         if (disconnected_coins.size() > 1 && InsecureRandRange(30) == 0) {
 436             stack[InsecureRand32() % stack.size()]->Uncache(FindRandomFrom(disconnected_coins)->first);
 437         }
 438         if (duplicate_coins.size() > 1 && InsecureRandRange(30) == 0) {
 439             stack[InsecureRand32() % stack.size()]->Uncache(FindRandomFrom(duplicate_coins)->first);
 440         }
 441
 442         if (InsecureRandRange(100) == 0) {
 443             // Every 100 iterations, flush an intermediate cache
 444             if (stack.size() > 1 && InsecureRandBool() == 0) {
 445                 unsigned int flushIndex = InsecureRandRange(stack.size() - 1);
 446                 stack[flushIndex]->Flush();
 447             }
 448         }
 449         if (InsecureRandRange(100) == 0) {
 450             // Every 100 iterations, change the cache stack.
 451             if (stack.size() > 0 && InsecureRandBool() == 0) {
 452                 stack.back()->Flush();
 453                 delete stack.back();
 454                 stack.pop_back();
 455             }
 456             if (stack.size() == 0 || (stack.size() < 4 && InsecureRandBool())) {
 457                 CCoinsView* tip = &base;
 458                 if (stack.size() > 0) {
 459                     tip = stack.back();
 460                 }
 461                 stack.push_back(new CCoinsViewCacheTest(tip));
 462             }
 463         }
 464     }
 465
 466     // Clean up the stack.
 467     while (stack.size() > 0) {
 468         delete stack.back();
 469         stack.pop_back();
 470     }
 471
 472     // Verify coverage.
 473     BOOST_CHECK(spent_a_duplicate_coinbase);
 474 }
 475
 476 BOOST_AUTO_TEST_CASE(ccoins_serialization)
 477 {
 478     // Good example
 479     CDataStream ss1(ParseHex("97f23c835800816115944e077fe7c803cfa57f29b36bf87c1d35"), SER_DISK, CLIENT_VERSION);
 480     Coin cc1;
 481     ss1 >> cc1;
 482     BOOST_CHECK_EQUAL(cc1.fCoinBase, false);
 483     BOOST_CHECK_EQUAL(cc1.nHeight, 203998);
 484     BOOST_CHECK_EQUAL(cc1.out.nValue, 60000000000ULL);
 485     BOOST_CHECK_EQUAL(HexStr(cc1.out.scriptPubKey), HexStr(GetScriptForDestination(CKeyID(uint160(ParseHex("816115944e077fe7c803cfa57f29b36bf87c1d35"))))));
 486
 487     // Good example
 488     CDataStream ss2(ParseHex("8ddf77bbd123008c988f1a4a4de2161e0f50aac7f17e7f9555caa4"), SER_DISK, CLIENT_VERSION);
 489     Coin cc2;
 490     ss2 >> cc2;
 491     BOOST_CHECK_EQUAL(cc2.fCoinBase, true);
 492     BOOST_CHECK_EQUAL(cc2.nHeight, 120891);
 493     BOOST_CHECK_EQUAL(cc2.out.nValue, 110397);
 494     BOOST_CHECK_EQUAL(HexStr(cc2.out.scriptPubKey), HexStr(GetScriptForDestination(CKeyID(uint160(ParseHex("8c988f1a4a4de2161e0f50aac7f17e7f9555caa4"))))));
 495
 496     // Smallest possible example
 497     CDataStream ss3(ParseHex("000006"), SER_DISK, CLIENT_VERSION);
 498     Coin cc3;
 499     ss3 >> cc3;
 500     BOOST_CHECK_EQUAL(cc3.fCoinBase, false);
 501     BOOST_CHECK_EQUAL(cc3.nHeight, 0);
 502     BOOST_CHECK_EQUAL(cc3.out.nValue, 0);
 503     BOOST_CHECK_EQUAL(cc3.out.scriptPubKey.size(), 0);
 504
 505     // scriptPubKey that ends beyond the end of the stream
 506     CDataStream ss4(ParseHex("000007"), SER_DISK, CLIENT_VERSION);
 507     try {
 508         Coin cc4;
 509         ss4 >> cc4;
 510         BOOST_CHECK_MESSAGE(false, "We should have thrown");
 511     } catch (const std::ios_base::failure& e) {
 512     }
 513
 514     // Very large scriptPubKey (3*10^9 bytes) past the end of the stream
 515     CDataStream tmp(SER_DISK, CLIENT_VERSION);
 516     uint64_t x = 3000000000ULL;
 517     tmp << VARINT(x);
 518     BOOST_CHECK_EQUAL(HexStr(tmp.begin(), tmp.end()), "8a95c0bb00");
 519     CDataStream ss5(ParseHex("00008a95c0bb00"), SER_DISK, CLIENT_VERSION);
 520     try {
 521         Coin cc5;
 522         ss5 >> cc5;
 523         BOOST_CHECK_MESSAGE(false, "We should have thrown");
 524     } catch (const std::ios_base::failure& e) {
 525     }
 526 }
 527
 528 const static COutPoint OUTPOINT;
 529 const static CAmount PRUNED = -1;
 530 const static CAmount ABSENT = -2;
 531 const static CAmount FAIL = -3;
 532 const static CAmount VALUE1 = 100;
 533 const static CAmount VALUE2 = 200;
 534 const static CAmount VALUE3 = 300;
 535 const static char DIRTY = CCoinsCacheEntry::DIRTY;
 536 const static char FRESH = CCoinsCacheEntry::FRESH;
 537 const static char NO_ENTRY = -1;
 538
 539 const static auto FLAGS = {char(0), FRESH, DIRTY, char(DIRTY | FRESH)};
 540 const static auto CLEAN_FLAGS = {char(0), FRESH};
 541 const static auto ABSENT_FLAGS = {NO_ENTRY};
 542
 543 void SetCoinsValue(CAmount value, Coin& coin)
 544 {
 545     assert(value != ABSENT);
 546     coin.Clear();
 547     assert(coin.IsSpent());
 548     if (value != PRUNED) {
 549         coin.out.nValue = value;
 550         coin.nHeight = 1;
 551         assert(!coin.IsSpent());
 552     }
 553 }
 554
 555 size_t InsertCoinsMapEntry(CCoinsMap& map, CAmount value, char flags)
 556 {
 557     if (value == ABSENT) {
 558         assert(flags == NO_ENTRY);
 559         return 0;
 560     }
 561     assert(flags != NO_ENTRY);
 562     CCoinsCacheEntry entry;
 563     entry.flags = flags;
 564     SetCoinsValue(value, entry.coin);
 565     auto inserted = map.emplace(OUTPOINT, std::move(entry));
 566     assert(inserted.second);
 567     return inserted.first->second.coin.DynamicMemoryUsage();
 568 }
 569
 570 void GetCoinsMapEntry(const CCoinsMap& map, CAmount& value, char& flags)
 571 {
 572     auto it = map.find(OUTPOINT);
 573     if (it == map.end()) {
 574         value = ABSENT;
 575         flags = NO_ENTRY;
 576     } else {
 577         if (it->second.coin.IsSpent()) {
 578             value = PRUNED;
 579         } else {
 580             value = it->second.coin.out.nValue;
 581         }
 582         flags = it->second.flags;
 583         assert(flags != NO_ENTRY);
 584     }
 585 }
 586
 587 void WriteCoinsViewEntry(CCoinsView& view, CAmount value, char flags)
 588 {
 589     CCoinsMap map;
 590     InsertCoinsMapEntry(map, value, flags);
 591     view.BatchWrite(map, {});
 592 }
 593
 594 class SingleEntryCacheTest
 595 {
 596 public:
 597     SingleEntryCacheTest(CAmount base_value, CAmount cache_value, char cache_flags)
 598     {
 599         WriteCoinsViewEntry(base, base_value, base_value == ABSENT ? NO_ENTRY : DIRTY);
 600         cache.usage() += InsertCoinsMapEntry(cache.map(), cache_value, cache_flags);
 601     }
 602
 603     CCoinsView root;
 604     CCoinsViewCacheTest base{&root};
 605     CCoinsViewCacheTest cache{&base};
 606 };
 607
 608 void CheckAccessCoin(CAmount base_value, CAmount cache_value, CAmount expected_value, char cache_flags, char expected_flags)
 609 {
 610     SingleEntryCacheTest test(base_value, cache_value, cache_flags);
 611     test.cache.AccessCoin(OUTPOINT);
 612     test.cache.SelfTest();
 613
 614     CAmount result_value;
 615     char result_flags;
 616     GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
 617     BOOST_CHECK_EQUAL(result_value, expected_value);
 618     BOOST_CHECK_EQUAL(result_flags, expected_flags);
 619 }
 620
 621 BOOST_AUTO_TEST_CASE(ccoins_access)
 622 {
 623     /* Check AccessCoin behavior, requesting a coin from a cache view layered on
 624      * top of a base view, and checking the resulting entry in the cache after
 625      * the access.
 626      *
 627      *               Base    Cache   Result  Cache        Result
 628      *               Value   Value   Value   Flags        Flags
 629      */
 630     CheckAccessCoin(ABSENT, ABSENT, ABSENT, NO_ENTRY   , NO_ENTRY   );
 631     CheckAccessCoin(ABSENT, PRUNED, PRUNED, 0          , 0          );
 632     CheckAccessCoin(ABSENT, PRUNED, PRUNED, FRESH      , FRESH      );
 633     CheckAccessCoin(ABSENT, PRUNED, PRUNED, DIRTY      , DIRTY      );
 634     CheckAccessCoin(ABSENT, PRUNED, PRUNED, DIRTY|FRESH, DIRTY|FRESH);
 635     CheckAccessCoin(ABSENT, VALUE2, VALUE2, 0          , 0          );
 636     CheckAccessCoin(ABSENT, VALUE2, VALUE2, FRESH      , FRESH      );
 637     CheckAccessCoin(ABSENT, VALUE2, VALUE2, DIRTY      , DIRTY      );
 638     CheckAccessCoin(ABSENT, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH);
 639     CheckAccessCoin(PRUNED, ABSENT, ABSENT, NO_ENTRY   , NO_ENTRY   );
 640     CheckAccessCoin(PRUNED, PRUNED, PRUNED, 0          , 0          );
 641     CheckAccessCoin(PRUNED, PRUNED, PRUNED, FRESH      , FRESH      );
 642     CheckAccessCoin(PRUNED, PRUNED, PRUNED, DIRTY      , DIRTY      );
 643     CheckAccessCoin(PRUNED, PRUNED, PRUNED, DIRTY|FRESH, DIRTY|FRESH);
 644     CheckAccessCoin(PRUNED, VALUE2, VALUE2, 0          , 0          );
 645     CheckAccessCoin(PRUNED, VALUE2, VALUE2, FRESH      , FRESH      );
 646     CheckAccessCoin(PRUNED, VALUE2, VALUE2, DIRTY      , DIRTY      );
 647     CheckAccessCoin(PRUNED, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH);
 648     CheckAccessCoin(VALUE1, ABSENT, VALUE1, NO_ENTRY   , 0          );
 649     CheckAccessCoin(VALUE1, PRUNED, PRUNED, 0          , 0          );
 650     CheckAccessCoin(VALUE1, PRUNED, PRUNED, FRESH      , FRESH      );
 651     CheckAccessCoin(VALUE1, PRUNED, PRUNED, DIRTY      , DIRTY      );
 652     CheckAccessCoin(VALUE1, PRUNED, PRUNED, DIRTY|FRESH, DIRTY|FRESH);
 653     CheckAccessCoin(VALUE1, VALUE2, VALUE2, 0          , 0          );
 654     CheckAccessCoin(VALUE1, VALUE2, VALUE2, FRESH      , FRESH      );
 655     CheckAccessCoin(VALUE1, VALUE2, VALUE2, DIRTY      , DIRTY      );
 656     CheckAccessCoin(VALUE1, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH);
 657 }
 658
 659 void CheckSpendCoins(CAmount base_value, CAmount cache_value, CAmount expected_value, char cache_flags, char expected_flags)
 660 {
 661     SingleEntryCacheTest test(base_value, cache_value, cache_flags);
 662     test.cache.SpendCoin(OUTPOINT);
 663     test.cache.SelfTest();
 664
 665     CAmount result_value;
 666     char result_flags;
 667     GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
 668     BOOST_CHECK_EQUAL(result_value, expected_value);
 669     BOOST_CHECK_EQUAL(result_flags, expected_flags);
 670 };
 671
 672 BOOST_AUTO_TEST_CASE(ccoins_spend)
 673 {
 674     /* Check SpendCoin behavior, requesting a coin from a cache view layered on
 675      * top of a base view, spending, and then checking
 676      * the resulting entry in the cache after the modification.
 677      *
 678      *              Base    Cache   Result  Cache        Result
 679      *              Value   Value   Value   Flags        Flags
 680      */
 681     CheckSpendCoins(ABSENT, ABSENT, ABSENT, NO_ENTRY   , NO_ENTRY   );
 682     CheckSpendCoins(ABSENT, PRUNED, PRUNED, 0          , DIRTY      );
 683     CheckSpendCoins(ABSENT, PRUNED, ABSENT, FRESH      , NO_ENTRY   );
 684     CheckSpendCoins(ABSENT, PRUNED, PRUNED, DIRTY      , DIRTY      );
 685     CheckSpendCoins(ABSENT, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY   );
 686     CheckSpendCoins(ABSENT, VALUE2, PRUNED, 0          , DIRTY      );
 687     CheckSpendCoins(ABSENT, VALUE2, ABSENT, FRESH      , NO_ENTRY   );
 688     CheckSpendCoins(ABSENT, VALUE2, PRUNED, DIRTY      , DIRTY      );
 689     CheckSpendCoins(ABSENT, VALUE2, ABSENT, DIRTY|FRESH, NO_ENTRY   );
 690     CheckSpendCoins(PRUNED, ABSENT, ABSENT, NO_ENTRY   , NO_ENTRY   );
 691     CheckSpendCoins(PRUNED, PRUNED, PRUNED, 0          , DIRTY      );
 692     CheckSpendCoins(PRUNED, PRUNED, ABSENT, FRESH      , NO_ENTRY   );
 693     CheckSpendCoins(PRUNED, PRUNED, PRUNED, DIRTY      , DIRTY      );
 694     CheckSpendCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY   );
 695     CheckSpendCoins(PRUNED, VALUE2, PRUNED, 0          , DIRTY      );
 696     CheckSpendCoins(PRUNED, VALUE2, ABSENT, FRESH      , NO_ENTRY   );
 697     CheckSpendCoins(PRUNED, VALUE2, PRUNED, DIRTY      , DIRTY      );
 698     CheckSpendCoins(PRUNED, VALUE2, ABSENT, DIRTY|FRESH, NO_ENTRY   );
 699     CheckSpendCoins(VALUE1, ABSENT, PRUNED, NO_ENTRY   , DIRTY      );
 700     CheckSpendCoins(VALUE1, PRUNED, PRUNED, 0          , DIRTY      );
 701     CheckSpendCoins(VALUE1, PRUNED, ABSENT, FRESH      , NO_ENTRY   );
 702     CheckSpendCoins(VALUE1, PRUNED, PRUNED, DIRTY      , DIRTY      );
 703     CheckSpendCoins(VALUE1, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY   );
 704     CheckSpendCoins(VALUE1, VALUE2, PRUNED, 0          , DIRTY      );
 705     CheckSpendCoins(VALUE1, VALUE2, ABSENT, FRESH      , NO_ENTRY   );
 706     CheckSpendCoins(VALUE1, VALUE2, PRUNED, DIRTY      , DIRTY      );
 707     CheckSpendCoins(VALUE1, VALUE2, ABSENT, DIRTY|FRESH, NO_ENTRY   );
 708 }
 709
 710 void CheckAddCoinBase(CAmount base_value, CAmount cache_value, CAmount modify_value, CAmount expected_value, char cache_flags, char expected_flags, bool coinbase)
 711 {
 712     SingleEntryCacheTest test(base_value, cache_value, cache_flags);
 713
 714     CAmount result_value;
 715     char result_flags;
 716     try {
 717         CTxOut output;
 718         output.nValue = modify_value;
 719         test.cache.AddCoin(OUTPOINT, Coin(std::move(output), 1, coinbase), coinbase);
 720         test.cache.SelfTest();
 721         GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
 722     } catch (std::logic_error& e) {
 723         result_value = FAIL;
 724         result_flags = NO_ENTRY;
 725     }
 726
 727     BOOST_CHECK_EQUAL(result_value, expected_value);
 728     BOOST_CHECK_EQUAL(result_flags, expected_flags);
 729 }
 730
 731 // Simple wrapper for CheckAddCoinBase function above that loops through
 732 // different possible base_values, making sure each one gives the same results.
 733 // This wrapper lets the coins_add test below be shorter and less repetitive,
 734 // while still verifying that the CoinsViewCache::AddCoin implementation
 735 // ignores base values.
 736 template <typename... Args>
 737 void CheckAddCoin(Args&&... args)
 738 {
 739     for (CAmount base_value : {ABSENT, PRUNED, VALUE1})
 740         CheckAddCoinBase(base_value, std::forward<Args>(args)...);
 741 }
 742
 743 BOOST_AUTO_TEST_CASE(ccoins_add)
 744 {
 745     /* Check AddCoin behavior, requesting a new coin from a cache view,
 746      * writing a modification to the coin, and then checking the resulting
 747      * entry in the cache after the modification. Verify behavior with the
 748      * with the AddCoin potential_overwrite argument set to false, and to true.
 749      *
 750      *           Cache   Write   Result  Cache        Result       potential_overwrite
 751      *           Value   Value   Value   Flags        Flags
 752      */
 753     CheckAddCoin(ABSENT, VALUE3, VALUE3, NO_ENTRY   , DIRTY|FRESH, false);
 754     CheckAddCoin(ABSENT, VALUE3, VALUE3, NO_ENTRY   , DIRTY      , true );
 755     CheckAddCoin(PRUNED, VALUE3, VALUE3, 0          , DIRTY|FRESH, false);
 756     CheckAddCoin(PRUNED, VALUE3, VALUE3, 0          , DIRTY      , true );
 757     CheckAddCoin(PRUNED, VALUE3, VALUE3, FRESH      , DIRTY|FRESH, false);
 758     CheckAddCoin(PRUNED, VALUE3, VALUE3, FRESH      , DIRTY|FRESH, true );
 759     CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY      , DIRTY      , false);
 760     CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY      , DIRTY      , true );
 761     CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, false);
 762     CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true );
 763     CheckAddCoin(VALUE2, VALUE3, FAIL  , 0          , NO_ENTRY   , false);
 764     CheckAddCoin(VALUE2, VALUE3, VALUE3, 0          , DIRTY      , true );
 765     CheckAddCoin(VALUE2, VALUE3, FAIL  , FRESH      , NO_ENTRY   , false);
 766     CheckAddCoin(VALUE2, VALUE3, VALUE3, FRESH      , DIRTY|FRESH, true );
 767     CheckAddCoin(VALUE2, VALUE3, FAIL  , DIRTY      , NO_ENTRY   , false);
 768     CheckAddCoin(VALUE2, VALUE3, VALUE3, DIRTY      , DIRTY      , true );
 769     CheckAddCoin(VALUE2, VALUE3, FAIL  , DIRTY|FRESH, NO_ENTRY   , false);
 770     CheckAddCoin(VALUE2, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true );
 771 }
 772
 773 void CheckWriteCoins(CAmount parent_value, CAmount child_value, CAmount expected_value, char parent_flags, char child_flags, char expected_flags)
 774 {
 775     SingleEntryCacheTest test(ABSENT, parent_value, parent_flags);
 776
 777     CAmount result_value;
 778     char result_flags;
 779     try {
 780         WriteCoinsViewEntry(test.cache, child_value, child_flags);
 781         test.cache.SelfTest();
 782         GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
 783     } catch (std::logic_error& e) {
 784         result_value = FAIL;
 785         result_flags = NO_ENTRY;
 786     }
 787
 788     BOOST_CHECK_EQUAL(result_value, expected_value);
 789     BOOST_CHECK_EQUAL(result_flags, expected_flags);
 790 }
 791
 792 BOOST_AUTO_TEST_CASE(ccoins_write)
 793 {
 794     /* Check BatchWrite behavior, flushing one entry from a child cache to a
 795      * parent cache, and checking the resulting entry in the parent cache
 796      * after the write.
 797      *
 798      *              Parent  Child   Result  Parent       Child        Result
 799      *              Value   Value   Value   Flags        Flags        Flags
 800      */
 801     CheckWriteCoins(ABSENT, ABSENT, ABSENT, NO_ENTRY   , NO_ENTRY   , NO_ENTRY   );
 802     CheckWriteCoins(ABSENT, PRUNED, PRUNED, NO_ENTRY   , DIRTY      , DIRTY      );
 803     CheckWriteCoins(ABSENT, PRUNED, ABSENT, NO_ENTRY   , DIRTY|FRESH, NO_ENTRY   );
 804     CheckWriteCoins(ABSENT, VALUE2, VALUE2, NO_ENTRY   , DIRTY      , DIRTY      );
 805     CheckWriteCoins(ABSENT, VALUE2, VALUE2, NO_ENTRY   , DIRTY|FRESH, DIRTY|FRESH);
 806     CheckWriteCoins(PRUNED, ABSENT, PRUNED, 0          , NO_ENTRY   , 0          );
 807     CheckWriteCoins(PRUNED, ABSENT, PRUNED, FRESH      , NO_ENTRY   , FRESH      );
 808     CheckWriteCoins(PRUNED, ABSENT, PRUNED, DIRTY      , NO_ENTRY   , DIRTY      );
 809     CheckWriteCoins(PRUNED, ABSENT, PRUNED, DIRTY|FRESH, NO_ENTRY   , DIRTY|FRESH);
 810     CheckWriteCoins(PRUNED, PRUNED, PRUNED, 0          , DIRTY      , DIRTY      );
 811     CheckWriteCoins(PRUNED, PRUNED, PRUNED, 0          , DIRTY|FRESH, DIRTY      );
 812     CheckWriteCoins(PRUNED, PRUNED, ABSENT, FRESH      , DIRTY      , NO_ENTRY   );
 813     CheckWriteCoins(PRUNED, PRUNED, ABSENT, FRESH      , DIRTY|FRESH, NO_ENTRY   );
 814     CheckWriteCoins(PRUNED, PRUNED, PRUNED, DIRTY      , DIRTY      , DIRTY      );
 815     CheckWriteCoins(PRUNED, PRUNED, PRUNED, DIRTY      , DIRTY|FRESH, DIRTY      );
 816     CheckWriteCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, DIRTY      , NO_ENTRY   );
 817     CheckWriteCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, DIRTY|FRESH, NO_ENTRY   );
 818     CheckWriteCoins(PRUNED, VALUE2, VALUE2, 0          , DIRTY      , DIRTY      );
 819     CheckWriteCoins(PRUNED, VALUE2, VALUE2, 0          , DIRTY|FRESH, DIRTY      );
 820     CheckWriteCoins(PRUNED, VALUE2, VALUE2, FRESH      , DIRTY      , DIRTY|FRESH);
 821     CheckWriteCoins(PRUNED, VALUE2, VALUE2, FRESH      , DIRTY|FRESH, DIRTY|FRESH);
 822     CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY      , DIRTY      , DIRTY      );
 823     CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY      , DIRTY|FRESH, DIRTY      );
 824     CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY|FRESH, DIRTY      , DIRTY|FRESH);
 825     CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH, DIRTY|FRESH);
 826     CheckWriteCoins(VALUE1, ABSENT, VALUE1, 0          , NO_ENTRY   , 0          );
 827     CheckWriteCoins(VALUE1, ABSENT, VALUE1, FRESH      , NO_ENTRY   , FRESH      );
 828     CheckWriteCoins(VALUE1, ABSENT, VALUE1, DIRTY      , NO_ENTRY   , DIRTY      );
 829     CheckWriteCoins(VALUE1, ABSENT, VALUE1, DIRTY|FRESH, NO_ENTRY   , DIRTY|FRESH);
 830     CheckWriteCoins(VALUE1, PRUNED, PRUNED, 0          , DIRTY      , DIRTY      );
 831     CheckWriteCoins(VALUE1, PRUNED, FAIL  , 0          , DIRTY|FRESH, NO_ENTRY   );
 832     CheckWriteCoins(VALUE1, PRUNED, ABSENT, FRESH      , DIRTY      , NO_ENTRY   );
 833     CheckWriteCoins(VALUE1, PRUNED, FAIL  , FRESH      , DIRTY|FRESH, NO_ENTRY   );
 834     CheckWriteCoins(VALUE1, PRUNED, PRUNED, DIRTY      , DIRTY      , DIRTY      );
 835     CheckWriteCoins(VALUE1, PRUNED, FAIL  , DIRTY      , DIRTY|FRESH, NO_ENTRY   );
 836     CheckWriteCoins(VALUE1, PRUNED, ABSENT, DIRTY|FRESH, DIRTY      , NO_ENTRY   );
 837     CheckWriteCoins(VALUE1, PRUNED, FAIL  , DIRTY|FRESH, DIRTY|FRESH, NO_ENTRY   );
 838     CheckWriteCoins(VALUE1, VALUE2, VALUE2, 0          , DIRTY      , DIRTY      );
 839     CheckWriteCoins(VALUE1, VALUE2, FAIL  , 0          , DIRTY|FRESH, NO_ENTRY   );
 840     CheckWriteCoins(VALUE1, VALUE2, VALUE2, FRESH      , DIRTY      , DIRTY|FRESH);
 841     CheckWriteCoins(VALUE1, VALUE2, FAIL  , FRESH      , DIRTY|FRESH, NO_ENTRY   );
 842     CheckWriteCoins(VALUE1, VALUE2, VALUE2, DIRTY      , DIRTY      , DIRTY      );
 843     CheckWriteCoins(VALUE1, VALUE2, FAIL  , DIRTY      , DIRTY|FRESH, NO_ENTRY   );
 844     CheckWriteCoins(VALUE1, VALUE2, VALUE2, DIRTY|FRESH, DIRTY      , DIRTY|FRESH);
 845     CheckWriteCoins(VALUE1, VALUE2, FAIL  , DIRTY|FRESH, DIRTY|FRESH, NO_ENTRY   );
 846
 847     // The checks above omit cases where the child flags are not DIRTY, since
 848     // they would be too repetitive (the parent cache is never updated in these
 849     // cases). The loop below covers these cases and makes sure the parent cache
 850     // is always left unchanged.
 851     for (CAmount parent_value : {ABSENT, PRUNED, VALUE1})
 852         for (CAmount child_value : {ABSENT, PRUNED, VALUE2})
 853             for (char parent_flags : parent_value == ABSENT ? ABSENT_FLAGS : FLAGS)
 854                 for (char child_flags : child_value == ABSENT ? ABSENT_FLAGS : CLEAN_FLAGS)
 855                     CheckWriteCoins(parent_value, child_value, parent_value, parent_flags, child_flags, parent_flags);
 856 }
 857
 858 BOOST_AUTO_TEST_SUITE_END()