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