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 <uint256.h>
12 #include <undo.h>
13 #include <util/strencodings.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(SeedRand::ZEROS);
283 g_mock_deterministic_tests = true;
284
285 bool spent_a_duplicate_coinbase = false;
286 // A simple map to track what we expect the cache stack to represent.
287 std::map<COutPoint, Coin> result;
288
289 // The cache stack.
290 CCoinsViewTest base; // A CCoinsViewTest at the bottom.
291 std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top.
292 stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
293
294 // Track the txids we've used in various sets
295 std::set<COutPoint> coinbase_coins;
296 std::set<COutPoint> disconnected_coins;
297 std::set<COutPoint> duplicate_coins;
298 std::set<COutPoint> utxoset;
299
300 for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
301 uint32_t randiter = InsecureRand32();
302
303 // 19/20 txs add a new transaction
304 if (randiter % 20 < 19) {
305 CMutableTransaction tx;
306 tx.vin.resize(1);
307 tx.vout.resize(1);
308 tx.vout[0].nValue = i; //Keep txs unique unless intended to duplicate
309 tx.vout[0].scriptPubKey.assign(InsecureRand32() & 0x3F, 0); // Random sizes so we can test memory usage accounting
310 unsigned int height = InsecureRand32();
311 Coin old_coin;
312
313 // 2/20 times create a new coinbase
314 if (randiter % 20 < 2 || coinbase_coins.size() < 10) {
315 // 1/10 of those times create a duplicate coinbase
316 if (InsecureRandRange(10) == 0 && coinbase_coins.size()) {
317 auto utxod = FindRandomFrom(coinbase_coins);
318 // Reuse the exact same coinbase
319 tx = CMutableTransaction{std::get<0>(utxod->second)};
320 // shouldn't be available for reconnection if it's been duplicated
321 disconnected_coins.erase(utxod->first);
322
323 duplicate_coins.insert(utxod->first);
324 }
325 else {
326 coinbase_coins.insert(COutPoint(tx.GetHash(), 0));
327 }
328 assert(CTransaction(tx).IsCoinBase());
329 }
330
331 // 17/20 times reconnect previous or add a regular tx
332 else {
333
334 COutPoint prevout;
335 // 1/20 times reconnect a previously disconnected tx
336 if (randiter % 20 == 2 && disconnected_coins.size()) {
337 auto utxod = FindRandomFrom(disconnected_coins);
338 tx = CMutableTransaction{std::get<0>(utxod->second)};
339 prevout = tx.vin[0].prevout;
340 if (!CTransaction(tx).IsCoinBase() && !utxoset.count(prevout)) {
341 disconnected_coins.erase(utxod->first);
342 continue;
343 }
344
345 // If this tx is already IN the UTXO, then it must be a coinbase, and it must be a duplicate
346 if (utxoset.count(utxod->first)) {
347 assert(CTransaction(tx).IsCoinBase());
348 assert(duplicate_coins.count(utxod->first));
349 }
350 disconnected_coins.erase(utxod->first);
351 }
352
353 // 16/20 times create a regular tx
354 else {
355 auto utxod = FindRandomFrom(utxoset);
356 prevout = utxod->first;
357
358 // Construct the tx to spend the coins of prevouthash
359 tx.vin[0].prevout = prevout;
360 assert(!CTransaction(tx).IsCoinBase());
361 }
362 // In this simple test coins only have two states, spent or unspent, save the unspent state to restore
363 old_coin = result[prevout];
364 // Update the expected result of prevouthash to know these coins are spent
365 result[prevout].Clear();
366
367 utxoset.erase(prevout);
368
369 // The test is designed to ensure spending a duplicate coinbase will work properly
370 // if that ever happens and not resurrect the previously overwritten coinbase
371 if (duplicate_coins.count(prevout)) {
372 spent_a_duplicate_coinbase = true;
373 }
374
375 }
376 // Update the expected result to know about the new output coins
377 assert(tx.vout.size() == 1);
378 const COutPoint outpoint(tx.GetHash(), 0);
379 result[outpoint] = Coin(tx.vout[0], height, CTransaction(tx).IsCoinBase(), CTransaction(tx).IsCoinStake());
380
381 // Call UpdateCoins on the top cache
382 CTxUndo undo;
383 UpdateCoins(CTransaction(tx), *(stack.back()), undo, height);
384
385 // Update the utxo set for future spends
386 utxoset.insert(outpoint);
387
388 // Track this tx and undo info to use later
389 utxoData.emplace(outpoint, std::make_tuple(tx,undo,old_coin));
390 } else if (utxoset.size()) {
391 //1/20 times undo a previous transaction
392 auto utxod = FindRandomFrom(utxoset);
393
394 CTransaction &tx = std::get<0>(utxod->second);
395 CTxUndo &undo = std::get<1>(utxod->second);
396 Coin &orig_coin = std::get<2>(utxod->second);
397
398 // Update the expected result
399 // Remove new outputs
400 result[utxod->first].Clear();
401 // If not coinbase restore prevout
402 if (!tx.IsCoinBase()) {
403 result[tx.vin[0].prevout] = orig_coin;
404 }
405
406 // Disconnect the tx from the current UTXO
407 // See code in DisconnectBlock
408 // remove outputs
409 BOOST_CHECK(stack.back()->SpendCoin(utxod->first));
410 // restore inputs
411 if (!tx.IsCoinBase()) {
412 const COutPoint &out = tx.vin[0].prevout;
413 Coin coin = undo.vprevout[0];
414 ApplyTxInUndo(std::move(coin), *(stack.back()), out);
415 }
416 // Store as a candidate for reconnection
417 disconnected_coins.insert(utxod->first);
418
419 // Update the utxoset
420 utxoset.erase(utxod->first);
421 if (!tx.IsCoinBase())
422 utxoset.insert(tx.vin[0].prevout);
423 }
424
425 // Once every 1000 iterations and at the end, verify the full cache.
426 if (InsecureRandRange(1000) == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
427 for (const auto& entry : result) {
428 bool have = stack.back()->HaveCoin(entry.first);
429 const Coin& coin = stack.back()->AccessCoin(entry.first);
430 BOOST_CHECK(have == !coin.IsSpent());
431 BOOST_CHECK(coin == entry.second);
432 }
433 }
434
435 // One every 10 iterations, remove a random entry from the cache
436 if (utxoset.size() > 1 && InsecureRandRange(30) == 0) {
437 stack[InsecureRand32() % stack.size()]->Uncache(FindRandomFrom(utxoset)->first);
438 }
439 if (disconnected_coins.size() > 1 && InsecureRandRange(30) == 0) {
440 stack[InsecureRand32() % stack.size()]->Uncache(FindRandomFrom(disconnected_coins)->first);
441 }
442 if (duplicate_coins.size() > 1 && InsecureRandRange(30) == 0) {
443 stack[InsecureRand32() % stack.size()]->Uncache(FindRandomFrom(duplicate_coins)->first);
444 }
445
446 if (InsecureRandRange(100) == 0) {
447 // Every 100 iterations, flush an intermediate cache
448 if (stack.size() > 1 && InsecureRandBool() == 0) {
449 unsigned int flushIndex = InsecureRandRange(stack.size() - 1);
450 BOOST_CHECK(stack[flushIndex]->Flush());
451 }
452 }
453 if (InsecureRandRange(100) == 0) {
454 // Every 100 iterations, change the cache stack.
455 if (stack.size() > 0 && InsecureRandBool() == 0) {
456 BOOST_CHECK(stack.back()->Flush());
457 delete stack.back();
458 stack.pop_back();
459 }
460 if (stack.size() == 0 || (stack.size() < 4 && InsecureRandBool())) {
461 CCoinsView* tip = &base;
462 if (stack.size() > 0) {
463 tip = stack.back();
464 }
465 stack.push_back(new CCoinsViewCacheTest(tip));
466 }
467 }
468 }
469
470 // Clean up the stack.
471 while (stack.size() > 0) {
472 delete stack.back();
473 stack.pop_back();
474 }
475
476 // Verify coverage.
477 BOOST_CHECK(spent_a_duplicate_coinbase);
478
479 g_mock_deterministic_tests = false;
480 }
481
BOOST_AUTO_TEST_CASE(ccoins_serialization)482 BOOST_AUTO_TEST_CASE(ccoins_serialization)
483 {
484 // Good example
485 CDataStream ss1(ParseHex("97f23c835800816115944e077fe7c803cfa57f29b36bf87c1d35"), SER_DISK, CLIENT_VERSION);
486 Coin cc1;
487 ss1 >> cc1;
488 BOOST_CHECK_EQUAL(cc1.fCoinBase, false);
489 BOOST_CHECK_EQUAL(cc1.nHeight, 101999);
490 BOOST_CHECK_EQUAL(cc1.out.nValue, CAmount{60000000000});
491 BOOST_CHECK_EQUAL(HexStr(cc1.out.scriptPubKey), HexStr(GetScriptForDestination(PKHash(uint160(ParseHex("816115944e077fe7c803cfa57f29b36bf87c1d35"))))));
492
493 // Good example
494 CDataStream ss2(ParseHex("8ddf77bbd123008c988f1a4a4de2161e0f50aac7f17e7f9555caa4"), SER_DISK, CLIENT_VERSION);
495 Coin cc2;
496 ss2 >> cc2;
497 BOOST_CHECK_EQUAL(cc2.fCoinBase, true);
498 BOOST_CHECK_EQUAL(cc2.nHeight, 60445);
499 BOOST_CHECK_EQUAL(cc2.out.nValue, 110397);
500 BOOST_CHECK_EQUAL(HexStr(cc2.out.scriptPubKey), HexStr(GetScriptForDestination(PKHash(uint160(ParseHex("8c988f1a4a4de2161e0f50aac7f17e7f9555caa4"))))));
501
502 // Smallest possible example
503 CDataStream ss3(ParseHex("000006"), SER_DISK, CLIENT_VERSION);
504 Coin cc3;
505 ss3 >> cc3;
506 BOOST_CHECK_EQUAL(cc3.fCoinBase, false);
507 BOOST_CHECK_EQUAL(cc3.nHeight, 0U);
508 BOOST_CHECK_EQUAL(cc3.out.nValue, 0);
509 BOOST_CHECK_EQUAL(cc3.out.scriptPubKey.size(), 0U);
510
511 // scriptPubKey that ends beyond the end of the stream
512 CDataStream ss4(ParseHex("000007"), SER_DISK, CLIENT_VERSION);
513 try {
514 Coin cc4;
515 ss4 >> cc4;
516 BOOST_CHECK_MESSAGE(false, "We should have thrown");
517 } catch (const std::ios_base::failure&) {
518 }
519
520 // Very large scriptPubKey (3*10^9 bytes) past the end of the stream
521 CDataStream tmp(SER_DISK, CLIENT_VERSION);
522 uint64_t x = 3000000000ULL;
523 tmp << VARINT(x);
524 BOOST_CHECK_EQUAL(HexStr(tmp.begin(), tmp.end()), "8a95c0bb00");
525 CDataStream ss5(ParseHex("00008a95c0bb00"), SER_DISK, CLIENT_VERSION);
526 try {
527 Coin cc5;
528 ss5 >> cc5;
529 BOOST_CHECK_MESSAGE(false, "We should have thrown");
530 } catch (const std::ios_base::failure&) {
531 }
532 }
533
534 const static COutPoint OUTPOINT;
535 const static CAmount PRUNED = -1;
536 const static CAmount ABSENT = -2;
537 const static CAmount FAIL = -3;
538 const static CAmount VALUE1 = 100;
539 const static CAmount VALUE2 = 200;
540 const static CAmount VALUE3 = 300;
541 const static char DIRTY = CCoinsCacheEntry::DIRTY;
542 const static char FRESH = CCoinsCacheEntry::FRESH;
543 const static char NO_ENTRY = -1;
544
545 const static auto FLAGS = {char(0), FRESH, DIRTY, char(DIRTY | FRESH)};
546 const static auto CLEAN_FLAGS = {char(0), FRESH};
547 const static auto ABSENT_FLAGS = {NO_ENTRY};
548
SetCoinsValue(CAmount value,Coin & coin)549 static void SetCoinsValue(CAmount value, Coin& coin)
550 {
551 assert(value != ABSENT);
552 coin.Clear();
553 assert(coin.IsSpent());
554 if (value != PRUNED) {
555 coin.out.nValue = value;
556 coin.nHeight = 1;
557 assert(!coin.IsSpent());
558 }
559 }
560
InsertCoinsMapEntry(CCoinsMap & map,CAmount value,char flags)561 static size_t InsertCoinsMapEntry(CCoinsMap& map, CAmount value, char flags)
562 {
563 if (value == ABSENT) {
564 assert(flags == NO_ENTRY);
565 return 0;
566 }
567 assert(flags != NO_ENTRY);
568 CCoinsCacheEntry entry;
569 entry.flags = flags;
570 SetCoinsValue(value, entry.coin);
571 auto inserted = map.emplace(OUTPOINT, std::move(entry));
572 assert(inserted.second);
573 return inserted.first->second.coin.DynamicMemoryUsage();
574 }
575
GetCoinsMapEntry(const CCoinsMap & map,CAmount & value,char & flags)576 void GetCoinsMapEntry(const CCoinsMap& map, CAmount& value, char& flags)
577 {
578 auto it = map.find(OUTPOINT);
579 if (it == map.end()) {
580 value = ABSENT;
581 flags = NO_ENTRY;
582 } else {
583 if (it->second.coin.IsSpent()) {
584 value = PRUNED;
585 } else {
586 value = it->second.coin.out.nValue;
587 }
588 flags = it->second.flags;
589 assert(flags != NO_ENTRY);
590 }
591 }
592
WriteCoinsViewEntry(CCoinsView & view,CAmount value,char flags)593 void WriteCoinsViewEntry(CCoinsView& view, CAmount value, char flags)
594 {
595 CCoinsMap map;
596 InsertCoinsMapEntry(map, value, flags);
597 BOOST_CHECK(view.BatchWrite(map, {}));
598 }
599
600 class SingleEntryCacheTest
601 {
602 public:
SingleEntryCacheTest(CAmount base_value,CAmount cache_value,char cache_flags)603 SingleEntryCacheTest(CAmount base_value, CAmount cache_value, char cache_flags)
604 {
605 WriteCoinsViewEntry(base, base_value, base_value == ABSENT ? NO_ENTRY : DIRTY);
606 cache.usage() += InsertCoinsMapEntry(cache.map(), cache_value, cache_flags);
607 }
608
609 CCoinsView root;
610 CCoinsViewCacheTest base{&root};
611 CCoinsViewCacheTest cache{&base};
612 };
613
CheckAccessCoin(CAmount base_value,CAmount cache_value,CAmount expected_value,char cache_flags,char expected_flags)614 static void CheckAccessCoin(CAmount base_value, CAmount cache_value, CAmount expected_value, char cache_flags, char expected_flags)
615 {
616 SingleEntryCacheTest test(base_value, cache_value, cache_flags);
617 test.cache.AccessCoin(OUTPOINT);
618 test.cache.SelfTest();
619
620 CAmount result_value;
621 char result_flags;
622 GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
623 BOOST_CHECK_EQUAL(result_value, expected_value);
624 BOOST_CHECK_EQUAL(result_flags, expected_flags);
625 }
626
BOOST_AUTO_TEST_CASE(ccoins_access)627 BOOST_AUTO_TEST_CASE(ccoins_access)
628 {
629 /* Check AccessCoin behavior, requesting a coin from a cache view layered on
630 * top of a base view, and checking the resulting entry in the cache after
631 * the access.
632 *
633 * Base Cache Result Cache Result
634 * Value Value Value Flags Flags
635 */
636 CheckAccessCoin(ABSENT, ABSENT, ABSENT, NO_ENTRY , NO_ENTRY );
637 CheckAccessCoin(ABSENT, PRUNED, PRUNED, 0 , 0 );
638 CheckAccessCoin(ABSENT, PRUNED, PRUNED, FRESH , FRESH );
639 CheckAccessCoin(ABSENT, PRUNED, PRUNED, DIRTY , DIRTY );
640 CheckAccessCoin(ABSENT, PRUNED, PRUNED, DIRTY|FRESH, DIRTY|FRESH);
641 CheckAccessCoin(ABSENT, VALUE2, VALUE2, 0 , 0 );
642 CheckAccessCoin(ABSENT, VALUE2, VALUE2, FRESH , FRESH );
643 CheckAccessCoin(ABSENT, VALUE2, VALUE2, DIRTY , DIRTY );
644 CheckAccessCoin(ABSENT, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH);
645 CheckAccessCoin(PRUNED, ABSENT, ABSENT, NO_ENTRY , NO_ENTRY );
646 CheckAccessCoin(PRUNED, PRUNED, PRUNED, 0 , 0 );
647 CheckAccessCoin(PRUNED, PRUNED, PRUNED, FRESH , FRESH );
648 CheckAccessCoin(PRUNED, PRUNED, PRUNED, DIRTY , DIRTY );
649 CheckAccessCoin(PRUNED, PRUNED, PRUNED, DIRTY|FRESH, DIRTY|FRESH);
650 CheckAccessCoin(PRUNED, VALUE2, VALUE2, 0 , 0 );
651 CheckAccessCoin(PRUNED, VALUE2, VALUE2, FRESH , FRESH );
652 CheckAccessCoin(PRUNED, VALUE2, VALUE2, DIRTY , DIRTY );
653 CheckAccessCoin(PRUNED, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH);
654 CheckAccessCoin(VALUE1, ABSENT, VALUE1, NO_ENTRY , 0 );
655 CheckAccessCoin(VALUE1, PRUNED, PRUNED, 0 , 0 );
656 CheckAccessCoin(VALUE1, PRUNED, PRUNED, FRESH , FRESH );
657 CheckAccessCoin(VALUE1, PRUNED, PRUNED, DIRTY , DIRTY );
658 CheckAccessCoin(VALUE1, PRUNED, PRUNED, DIRTY|FRESH, DIRTY|FRESH);
659 CheckAccessCoin(VALUE1, VALUE2, VALUE2, 0 , 0 );
660 CheckAccessCoin(VALUE1, VALUE2, VALUE2, FRESH , FRESH );
661 CheckAccessCoin(VALUE1, VALUE2, VALUE2, DIRTY , DIRTY );
662 CheckAccessCoin(VALUE1, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH);
663 }
664
CheckSpendCoins(CAmount base_value,CAmount cache_value,CAmount expected_value,char cache_flags,char expected_flags)665 static void CheckSpendCoins(CAmount base_value, CAmount cache_value, CAmount expected_value, char cache_flags, char expected_flags)
666 {
667 SingleEntryCacheTest test(base_value, cache_value, cache_flags);
668 test.cache.SpendCoin(OUTPOINT);
669 test.cache.SelfTest();
670
671 CAmount result_value;
672 char result_flags;
673 GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
674 BOOST_CHECK_EQUAL(result_value, expected_value);
675 BOOST_CHECK_EQUAL(result_flags, expected_flags);
676 };
677
BOOST_AUTO_TEST_CASE(ccoins_spend)678 BOOST_AUTO_TEST_CASE(ccoins_spend)
679 {
680 /* Check SpendCoin behavior, requesting a coin from a cache view layered on
681 * top of a base view, spending, and then checking
682 * the resulting entry in the cache after the modification.
683 *
684 * Base Cache Result Cache Result
685 * Value Value Value Flags Flags
686 */
687 CheckSpendCoins(ABSENT, ABSENT, ABSENT, NO_ENTRY , NO_ENTRY );
688 CheckSpendCoins(ABSENT, PRUNED, PRUNED, 0 , DIRTY );
689 CheckSpendCoins(ABSENT, PRUNED, ABSENT, FRESH , NO_ENTRY );
690 CheckSpendCoins(ABSENT, PRUNED, PRUNED, DIRTY , DIRTY );
691 CheckSpendCoins(ABSENT, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY );
692 CheckSpendCoins(ABSENT, VALUE2, PRUNED, 0 , DIRTY );
693 CheckSpendCoins(ABSENT, VALUE2, ABSENT, FRESH , NO_ENTRY );
694 CheckSpendCoins(ABSENT, VALUE2, PRUNED, DIRTY , DIRTY );
695 CheckSpendCoins(ABSENT, VALUE2, ABSENT, DIRTY|FRESH, NO_ENTRY );
696 CheckSpendCoins(PRUNED, ABSENT, ABSENT, NO_ENTRY , NO_ENTRY );
697 CheckSpendCoins(PRUNED, PRUNED, PRUNED, 0 , DIRTY );
698 CheckSpendCoins(PRUNED, PRUNED, ABSENT, FRESH , NO_ENTRY );
699 CheckSpendCoins(PRUNED, PRUNED, PRUNED, DIRTY , DIRTY );
700 CheckSpendCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY );
701 CheckSpendCoins(PRUNED, VALUE2, PRUNED, 0 , DIRTY );
702 CheckSpendCoins(PRUNED, VALUE2, ABSENT, FRESH , NO_ENTRY );
703 CheckSpendCoins(PRUNED, VALUE2, PRUNED, DIRTY , DIRTY );
704 CheckSpendCoins(PRUNED, VALUE2, ABSENT, DIRTY|FRESH, NO_ENTRY );
705 CheckSpendCoins(VALUE1, ABSENT, PRUNED, NO_ENTRY , DIRTY );
706 CheckSpendCoins(VALUE1, PRUNED, PRUNED, 0 , DIRTY );
707 CheckSpendCoins(VALUE1, PRUNED, ABSENT, FRESH , NO_ENTRY );
708 CheckSpendCoins(VALUE1, PRUNED, PRUNED, DIRTY , DIRTY );
709 CheckSpendCoins(VALUE1, PRUNED, ABSENT, DIRTY|FRESH, NO_ENTRY );
710 CheckSpendCoins(VALUE1, VALUE2, PRUNED, 0 , DIRTY );
711 CheckSpendCoins(VALUE1, VALUE2, ABSENT, FRESH , NO_ENTRY );
712 CheckSpendCoins(VALUE1, VALUE2, PRUNED, DIRTY , DIRTY );
713 CheckSpendCoins(VALUE1, VALUE2, ABSENT, DIRTY|FRESH, NO_ENTRY );
714 }
715
CheckAddCoinBase(CAmount base_value,CAmount cache_value,CAmount modify_value,CAmount expected_value,char cache_flags,char expected_flags,bool coinbase)716 static void CheckAddCoinBase(CAmount base_value, CAmount cache_value, CAmount modify_value, CAmount expected_value, char cache_flags, char expected_flags, bool coinbase)
717 {
718 SingleEntryCacheTest test(base_value, cache_value, cache_flags);
719
720 CAmount result_value;
721 char result_flags;
722 try {
723 CTxOut output;
724 output.nValue = modify_value;
725 test.cache.AddCoin(OUTPOINT, Coin(std::move(output), 1, coinbase, false), coinbase);
726 test.cache.SelfTest();
727 GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
728 } catch (std::logic_error&) {
729 result_value = FAIL;
730 result_flags = NO_ENTRY;
731 }
732
733 BOOST_CHECK_EQUAL(result_value, expected_value);
734 BOOST_CHECK_EQUAL(result_flags, expected_flags);
735 }
736
737 // Simple wrapper for CheckAddCoinBase function above that loops through
738 // different possible base_values, making sure each one gives the same results.
739 // This wrapper lets the coins_add test below be shorter and less repetitive,
740 // while still verifying that the CoinsViewCache::AddCoin implementation
741 // ignores base values.
742 template <typename... Args>
CheckAddCoin(Args &&...args)743 static void CheckAddCoin(Args&&... args)
744 {
745 for (const CAmount base_value : {ABSENT, PRUNED, VALUE1})
746 CheckAddCoinBase(base_value, std::forward<Args>(args)...);
747 }
748
BOOST_AUTO_TEST_CASE(ccoins_add)749 BOOST_AUTO_TEST_CASE(ccoins_add)
750 {
751 /* Check AddCoin behavior, requesting a new coin from a cache view,
752 * writing a modification to the coin, and then checking the resulting
753 * entry in the cache after the modification. Verify behavior with the
754 * with the AddCoin potential_overwrite argument set to false, and to true.
755 *
756 * Cache Write Result Cache Result potential_overwrite
757 * Value Value Value Flags Flags
758 */
759 CheckAddCoin(ABSENT, VALUE3, VALUE3, NO_ENTRY , DIRTY|FRESH, false);
760 CheckAddCoin(ABSENT, VALUE3, VALUE3, NO_ENTRY , DIRTY , true );
761 CheckAddCoin(PRUNED, VALUE3, VALUE3, 0 , DIRTY|FRESH, false);
762 CheckAddCoin(PRUNED, VALUE3, VALUE3, 0 , DIRTY , true );
763 CheckAddCoin(PRUNED, VALUE3, VALUE3, FRESH , DIRTY|FRESH, false);
764 CheckAddCoin(PRUNED, VALUE3, VALUE3, FRESH , DIRTY|FRESH, true );
765 CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY , DIRTY , false);
766 CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY , DIRTY , true );
767 CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, false);
768 CheckAddCoin(PRUNED, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true );
769 CheckAddCoin(VALUE2, VALUE3, FAIL , 0 , NO_ENTRY , false);
770 CheckAddCoin(VALUE2, VALUE3, VALUE3, 0 , DIRTY , true );
771 CheckAddCoin(VALUE2, VALUE3, FAIL , FRESH , NO_ENTRY , false);
772 CheckAddCoin(VALUE2, VALUE3, VALUE3, FRESH , DIRTY|FRESH, true );
773 CheckAddCoin(VALUE2, VALUE3, FAIL , DIRTY , NO_ENTRY , false);
774 CheckAddCoin(VALUE2, VALUE3, VALUE3, DIRTY , DIRTY , true );
775 CheckAddCoin(VALUE2, VALUE3, FAIL , DIRTY|FRESH, NO_ENTRY , false);
776 CheckAddCoin(VALUE2, VALUE3, VALUE3, DIRTY|FRESH, DIRTY|FRESH, true );
777 }
778
CheckWriteCoins(CAmount parent_value,CAmount child_value,CAmount expected_value,char parent_flags,char child_flags,char expected_flags)779 void CheckWriteCoins(CAmount parent_value, CAmount child_value, CAmount expected_value, char parent_flags, char child_flags, char expected_flags)
780 {
781 SingleEntryCacheTest test(ABSENT, parent_value, parent_flags);
782
783 CAmount result_value;
784 char result_flags;
785 try {
786 WriteCoinsViewEntry(test.cache, child_value, child_flags);
787 test.cache.SelfTest();
788 GetCoinsMapEntry(test.cache.map(), result_value, result_flags);
789 } catch (std::logic_error&) {
790 result_value = FAIL;
791 result_flags = NO_ENTRY;
792 }
793
794 BOOST_CHECK_EQUAL(result_value, expected_value);
795 BOOST_CHECK_EQUAL(result_flags, expected_flags);
796 }
797
BOOST_AUTO_TEST_CASE(ccoins_write)798 BOOST_AUTO_TEST_CASE(ccoins_write)
799 {
800 /* Check BatchWrite behavior, flushing one entry from a child cache to a
801 * parent cache, and checking the resulting entry in the parent cache
802 * after the write.
803 *
804 * Parent Child Result Parent Child Result
805 * Value Value Value Flags Flags Flags
806 */
807 CheckWriteCoins(ABSENT, ABSENT, ABSENT, NO_ENTRY , NO_ENTRY , NO_ENTRY );
808 CheckWriteCoins(ABSENT, PRUNED, PRUNED, NO_ENTRY , DIRTY , DIRTY );
809 CheckWriteCoins(ABSENT, PRUNED, ABSENT, NO_ENTRY , DIRTY|FRESH, NO_ENTRY );
810 CheckWriteCoins(ABSENT, VALUE2, VALUE2, NO_ENTRY , DIRTY , DIRTY );
811 CheckWriteCoins(ABSENT, VALUE2, VALUE2, NO_ENTRY , DIRTY|FRESH, DIRTY|FRESH);
812 CheckWriteCoins(PRUNED, ABSENT, PRUNED, 0 , NO_ENTRY , 0 );
813 CheckWriteCoins(PRUNED, ABSENT, PRUNED, FRESH , NO_ENTRY , FRESH );
814 CheckWriteCoins(PRUNED, ABSENT, PRUNED, DIRTY , NO_ENTRY , DIRTY );
815 CheckWriteCoins(PRUNED, ABSENT, PRUNED, DIRTY|FRESH, NO_ENTRY , DIRTY|FRESH);
816 CheckWriteCoins(PRUNED, PRUNED, PRUNED, 0 , DIRTY , DIRTY );
817 CheckWriteCoins(PRUNED, PRUNED, PRUNED, 0 , DIRTY|FRESH, DIRTY );
818 CheckWriteCoins(PRUNED, PRUNED, ABSENT, FRESH , DIRTY , NO_ENTRY );
819 CheckWriteCoins(PRUNED, PRUNED, ABSENT, FRESH , DIRTY|FRESH, NO_ENTRY );
820 CheckWriteCoins(PRUNED, PRUNED, PRUNED, DIRTY , DIRTY , DIRTY );
821 CheckWriteCoins(PRUNED, PRUNED, PRUNED, DIRTY , DIRTY|FRESH, DIRTY );
822 CheckWriteCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, DIRTY , NO_ENTRY );
823 CheckWriteCoins(PRUNED, PRUNED, ABSENT, DIRTY|FRESH, DIRTY|FRESH, NO_ENTRY );
824 CheckWriteCoins(PRUNED, VALUE2, VALUE2, 0 , DIRTY , DIRTY );
825 CheckWriteCoins(PRUNED, VALUE2, VALUE2, 0 , DIRTY|FRESH, DIRTY );
826 CheckWriteCoins(PRUNED, VALUE2, VALUE2, FRESH , DIRTY , DIRTY|FRESH);
827 CheckWriteCoins(PRUNED, VALUE2, VALUE2, FRESH , DIRTY|FRESH, DIRTY|FRESH);
828 CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY , DIRTY , DIRTY );
829 CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY , DIRTY|FRESH, DIRTY );
830 CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY|FRESH, DIRTY , DIRTY|FRESH);
831 CheckWriteCoins(PRUNED, VALUE2, VALUE2, DIRTY|FRESH, DIRTY|FRESH, DIRTY|FRESH);
832 CheckWriteCoins(VALUE1, ABSENT, VALUE1, 0 , NO_ENTRY , 0 );
833 CheckWriteCoins(VALUE1, ABSENT, VALUE1, FRESH , NO_ENTRY , FRESH );
834 CheckWriteCoins(VALUE1, ABSENT, VALUE1, DIRTY , NO_ENTRY , DIRTY );
835 CheckWriteCoins(VALUE1, ABSENT, VALUE1, DIRTY|FRESH, NO_ENTRY , DIRTY|FRESH);
836 CheckWriteCoins(VALUE1, PRUNED, PRUNED, 0 , DIRTY , DIRTY );
837 CheckWriteCoins(VALUE1, PRUNED, FAIL , 0 , DIRTY|FRESH, NO_ENTRY );
838 CheckWriteCoins(VALUE1, PRUNED, ABSENT, FRESH , DIRTY , NO_ENTRY );
839 CheckWriteCoins(VALUE1, PRUNED, FAIL , FRESH , DIRTY|FRESH, NO_ENTRY );
840 CheckWriteCoins(VALUE1, PRUNED, PRUNED, DIRTY , DIRTY , DIRTY );
841 CheckWriteCoins(VALUE1, PRUNED, FAIL , DIRTY , DIRTY|FRESH, NO_ENTRY );
842 CheckWriteCoins(VALUE1, PRUNED, ABSENT, DIRTY|FRESH, DIRTY , NO_ENTRY );
843 CheckWriteCoins(VALUE1, PRUNED, FAIL , DIRTY|FRESH, DIRTY|FRESH, NO_ENTRY );
844 CheckWriteCoins(VALUE1, VALUE2, VALUE2, 0 , DIRTY , DIRTY );
845 CheckWriteCoins(VALUE1, VALUE2, FAIL , 0 , DIRTY|FRESH, NO_ENTRY );
846 CheckWriteCoins(VALUE1, VALUE2, VALUE2, FRESH , DIRTY , DIRTY|FRESH);
847 CheckWriteCoins(VALUE1, VALUE2, FAIL , FRESH , DIRTY|FRESH, NO_ENTRY );
848 CheckWriteCoins(VALUE1, VALUE2, VALUE2, DIRTY , DIRTY , DIRTY );
849 CheckWriteCoins(VALUE1, VALUE2, FAIL , DIRTY , DIRTY|FRESH, NO_ENTRY );
850 CheckWriteCoins(VALUE1, VALUE2, VALUE2, DIRTY|FRESH, DIRTY , DIRTY|FRESH);
851 CheckWriteCoins(VALUE1, VALUE2, FAIL , DIRTY|FRESH, DIRTY|FRESH, NO_ENTRY );
852
853 // The checks above omit cases where the child flags are not DIRTY, since
854 // they would be too repetitive (the parent cache is never updated in these
855 // cases). The loop below covers these cases and makes sure the parent cache
856 // is always left unchanged.
857 for (const CAmount parent_value : {ABSENT, PRUNED, VALUE1})
858 for (const CAmount child_value : {ABSENT, PRUNED, VALUE2})
859 for (const char parent_flags : parent_value == ABSENT ? ABSENT_FLAGS : FLAGS)
860 for (const char child_flags : child_value == ABSENT ? ABSENT_FLAGS : CLEAN_FLAGS)
861 CheckWriteCoins(parent_value, child_value, parent_value, parent_flags, child_flags, parent_flags);
862 }
863
864 BOOST_AUTO_TEST_SUITE_END()
865