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