Line data Source code
1 : // Copyright (c) 2014 The Bitcoin Core developers
2 : // Distributed under the MIT software license, see the accompanying
3 : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 :
5 : #include "coins.h"
6 : #include "random.h"
7 : #include "uint256.h"
8 : #include "test/test_bitcoin.h"
9 :
10 : #include <vector>
11 : #include <map>
12 :
13 : #include <boost/test/unit_test.hpp>
14 :
15 : namespace
16 : {
17 7 : class CCoinsViewTest : public CCoinsView
18 : {
19 : uint256 hashBestBlock_;
20 : std::map<uint256, CCoins> map_;
21 :
22 : public:
23 74915 : bool GetCoins(const uint256& txid, CCoins& coins) const
24 : {
25 149830 : std::map<uint256, CCoins>::const_iterator it = map_.find(txid);
26 149830 : if (it == map_.end()) {
27 : return false;
28 : }
29 38882 : coins = it->second;
30 38882 : if (coins.IsPruned() && insecure_rand() % 2 == 0) {
31 : // Randomly return false in case of an empty entry.
32 : return false;
33 : }
34 32514 : return true;
35 : }
36 :
37 0 : bool HaveCoins(const uint256& txid) const
38 : {
39 0 : CCoins coins;
40 0 : return GetCoins(txid, coins);
41 : }
42 :
43 0 : uint256 GetBestBlock() const { return hashBestBlock_; }
44 :
45 43 : bool BatchWrite(CCoinsMap& mapCoins, const uint256& hashBlock)
46 : {
47 36623 : for (CCoinsMap::iterator it = mapCoins.begin(); it != mapCoins.end(); ) {
48 73074 : map_[it->first] = it->second.coins;
49 36537 : if (it->second.coins.IsPruned() && insecure_rand() % 3 == 0) {
50 : // Randomly delete empty entries on write.
51 3549 : map_.erase(it->first);
52 : }
53 73074 : mapCoins.erase(it++);
54 : }
55 : mapCoins.clear();
56 43 : hashBestBlock_ = hashBlock;
57 43 : return true;
58 : }
59 :
60 0 : bool GetStats(CCoinsStats& stats) const { return false; }
61 : };
62 :
63 186 : class CCoinsViewCacheTest : public CCoinsViewCache
64 : {
65 : public:
66 186 : CCoinsViewCacheTest(CCoinsView* base) : CCoinsViewCache(base) {}
67 :
68 110 : void SelfTest() const
69 : {
70 : // Manually recompute the dynamic usage of the whole data, and compare it.
71 220 : size_t ret = memusage::DynamicUsage(cacheCoins);
72 818284 : for (CCoinsMap::iterator it = cacheCoins.begin(); it != cacheCoins.end(); it++) {
73 408977 : ret += it->second.coins.DynamicMemoryUsage();
74 : }
75 550 : BOOST_CHECK_EQUAL(DynamicMemoryUsage(), ret);
76 110 : }
77 :
78 : };
79 :
80 : }
81 :
82 1 : BOOST_FIXTURE_TEST_SUITE(coins_tests, BasicTestingSetup)
83 :
84 : static const unsigned int NUM_SIMULATION_ITERATIONS = 40000;
85 :
86 : // This is a large randomized insert/remove simulation test on a variable-size
87 : // stack of caches on top of CCoinsViewTest.
88 : //
89 : // It will randomly create/update/delete CCoins entries to a tip of caches, with
90 : // txids picked from a limited list of random 256-bit hashes. Occasionally, a
91 : // new tip is added to the stack of caches, or the tip is flushed and removed.
92 : //
93 : // During the process, booleans are kept to make sure that the randomized
94 : // operation hits all branches.
95 6 : BOOST_AUTO_TEST_CASE(coins_cache_simulation_test)
96 : {
97 : // Various coverage trackers.
98 1 : bool removed_all_caches = false;
99 1 : bool reached_4_caches = false;
100 1 : bool added_an_entry = false;
101 1 : bool removed_an_entry = false;
102 1 : bool updated_an_entry = false;
103 1 : bool found_an_entry = false;
104 1 : bool missed_an_entry = false;
105 :
106 : // A simple map to track what we expect the cache stack to represent.
107 : std::map<uint256, CCoins> result;
108 :
109 : // The cache stack.
110 1 : CCoinsViewTest base; // A CCoinsViewTest at the bottom.
111 : std::vector<CCoinsViewCacheTest*> stack; // A stack of CCoinsViewCaches on top.
112 2 : stack.push_back(new CCoinsViewCacheTest(&base)); // Start with one cache.
113 :
114 : // Use a limited set of random transaction ids, so we do test overwriting entries.
115 : std::vector<uint256> txids;
116 1 : txids.resize(NUM_SIMULATION_ITERATIONS / 8);
117 10002 : for (unsigned int i = 0; i < txids.size(); i++) {
118 10000 : txids[i] = GetRandHash();
119 : }
120 :
121 40000 : for (unsigned int i = 0; i < NUM_SIMULATION_ITERATIONS; i++) {
122 : // Do a random modification.
123 : {
124 120000 : uint256 txid = txids[insecure_rand() % txids.size()]; // txid we're going to modify in this iteration.
125 40000 : CCoins& coins = result[txid];
126 40000 : CCoinsModifier entry = stack.back()->ModifyCoins(txid);
127 320000 : BOOST_CHECK(coins == *entry);
128 40000 : if (insecure_rand() % 5 == 0 || coins.IsPruned()) {
129 23404 : if (coins.IsPruned()) {
130 : added_an_entry = true;
131 : } else {
132 4064 : updated_an_entry = true;
133 : }
134 23404 : coins.nVersion = insecure_rand();
135 46808 : coins.vout.resize(1);
136 23404 : coins.vout[0].nValue = insecure_rand();
137 23404 : *entry = coins;
138 : } else {
139 16596 : coins.Clear();
140 16596 : entry->Clear();
141 16596 : removed_an_entry = true;
142 40000 : }
143 : }
144 :
145 : // Once every 1000 iterations and at the end, verify the full cache.
146 40000 : if (insecure_rand() % 1000 == 1 || i == NUM_SIMULATION_ITERATIONS - 1) {
147 399110 : for (std::map<uint256, CCoins>::iterator it = result.begin(); it != result.end(); it++) {
148 399020 : const CCoins* coins = stack.back()->AccessCoins(it->first);
149 199510 : if (coins) {
150 1346592 : BOOST_CHECK(*coins == it->second);
151 : found_an_entry = true;
152 : } else {
153 249488 : BOOST_CHECK(it->second.IsPruned());
154 : missed_an_entry = true;
155 : }
156 : }
157 930 : BOOST_FOREACH(const CCoinsViewCacheTest *test, stack) {
158 110 : test->SelfTest();
159 : }
160 : }
161 :
162 40000 : if (insecure_rand() % 100 == 0) {
163 : // Every 100 iterations, change the cache stack.
164 752 : if (stack.size() > 0 && insecure_rand() % 2 == 0) {
165 183 : stack.back()->Flush();
166 183 : delete stack.back();
167 183 : stack.pop_back();
168 : }
169 1085 : if (stack.size() == 0 || (stack.size() < 4 && insecure_rand() % 2)) {
170 185 : CCoinsView* tip = &base;
171 370 : if (stack.size() > 0) {
172 142 : tip = stack.back();
173 : } else {
174 : removed_all_caches = true;
175 : }
176 370 : stack.push_back(new CCoinsViewCacheTest(tip));
177 370 : if (stack.size() == 4) {
178 38 : reached_4_caches = true;
179 : }
180 : }
181 : }
182 : }
183 :
184 : // Clean up the stack.
185 8 : while (stack.size() > 0) {
186 3 : delete stack.back();
187 3 : stack.pop_back();
188 : }
189 :
190 : // Verify coverage.
191 5 : BOOST_CHECK(removed_all_caches);
192 8 : BOOST_CHECK(reached_4_caches);
193 8 : BOOST_CHECK(added_an_entry);
194 8 : BOOST_CHECK(removed_an_entry);
195 8 : BOOST_CHECK(updated_an_entry);
196 8 : BOOST_CHECK(found_an_entry);
197 8 : BOOST_CHECK(missed_an_entry);
198 1 : }
199 :
200 3 : BOOST_AUTO_TEST_SUITE_END()
|
