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