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