coinscache_sim.cpp raw
1 // Copyright (c) 2023-present 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 <crypto/sha256.h>
7 #include <kernel/chainstatemanager_opts.h>
8 #include <primitives/block.h>
9 #include <primitives/transaction.h>
10 #include <test/fuzz/FuzzedDataProvider.h>
11 #include <test/fuzz/fuzz.h>
12 #include <test/fuzz/util.h>
13 #include <test/util/setup_common.h>
14 #include <util/threadpool.h>
15
16 #include <cassert>
17 #include <cstdint>
18 #include <memory>
19 #include <optional>
20 #include <vector>
21
22 namespace {
23
24 /** Number of distinct COutPoint values used in this test. */
25 constexpr uint32_t NUM_OUTPOINTS = 256;
26 /** Number of distinct Coin values used in this test (ignoring nHeight). */
27 constexpr uint32_t NUM_COINS = 256;
28 /** Maximum number CCoinsViewCache objects used in this test. */
29 constexpr uint32_t MAX_CACHES = 4;
30 /** Data type large enough to hold NUM_COINS-1. */
31 using coinidx_type = uint8_t;
32
33 struct PrecomputedData
34 {
35 //! Randomly generated COutPoint values.
36 COutPoint outpoints[NUM_OUTPOINTS];
37
38 //! Randomly generated Coin values.
39 Coin coins[NUM_COINS];
40
41 //! Block with a tx containing as inputs the above outpoints.
42 CBlock block;
43
44 PrecomputedData()
45 {
46 static const uint8_t PREFIX_O[1] = {'o'}; /** Hash prefix for outpoint hashes. */
47 static const uint8_t PREFIX_S[1] = {'s'}; /** Hash prefix for coins scriptPubKeys. */
48 static const uint8_t PREFIX_M[1] = {'m'}; /** Hash prefix for coins nValue/fCoinBase. */
49
50 CMutableTransaction coinbase;
51 coinbase.vin.emplace_back();
52 block.vtx.push_back(MakeTransactionRef(coinbase));
53
54 CMutableTransaction tx;
55 for (uint32_t i = 0; i < NUM_OUTPOINTS; ++i) {
56 uint32_t idx = (i * 1200U) >> 12; /* Map 3 or 4 entries to same txid. */
57 const uint8_t ser[4] = {uint8_t(idx), uint8_t(idx >> 8), uint8_t(idx >> 16), uint8_t(idx >> 24)};
58 uint256 txid;
59 CSHA256().Write(PREFIX_O, 1).Write(ser, sizeof(ser)).Finalize(txid.begin());
60 outpoints[i].hash = Txid::FromUint256(txid);
61 outpoints[i].n = i;
62 tx.vin.emplace_back(outpoints[i]);
63 }
64 block.vtx.push_back(MakeTransactionRef(tx));
65
66 for (uint32_t i = 0; i < NUM_COINS; ++i) {
67 const uint8_t ser[4] = {uint8_t(i), uint8_t(i >> 8), uint8_t(i >> 16), uint8_t(i >> 24)};
68 uint256 hash;
69 CSHA256().Write(PREFIX_S, 1).Write(ser, sizeof(ser)).Finalize(hash.begin());
70 /* Convert hash to scriptPubkeys (of different lengths, so SanityCheck's cached memory
71 * usage check has a chance to detect mismatches). */
72 switch (i % 5U) {
73 case 0: /* P2PKH */
74 coins[i].out.scriptPubKey.resize(25);
75 coins[i].out.scriptPubKey[0] = OP_DUP;
76 coins[i].out.scriptPubKey[1] = OP_HASH160;
77 coins[i].out.scriptPubKey[2] = 20;
78 std::copy(hash.begin(), hash.begin() + 20, coins[i].out.scriptPubKey.begin() + 3);
79 coins[i].out.scriptPubKey[23] = OP_EQUALVERIFY;
80 coins[i].out.scriptPubKey[24] = OP_CHECKSIG;
81 break;
82 case 1: /* P2SH */
83 coins[i].out.scriptPubKey.resize(23);
84 coins[i].out.scriptPubKey[0] = OP_HASH160;
85 coins[i].out.scriptPubKey[1] = 20;
86 std::copy(hash.begin(), hash.begin() + 20, coins[i].out.scriptPubKey.begin() + 2);
87 coins[i].out.scriptPubKey[22] = OP_EQUAL;
88 break;
89 case 2: /* P2WPKH */
90 coins[i].out.scriptPubKey.resize(22);
91 coins[i].out.scriptPubKey[0] = OP_0;
92 coins[i].out.scriptPubKey[1] = 20;
93 std::copy(hash.begin(), hash.begin() + 20, coins[i].out.scriptPubKey.begin() + 2);
94 break;
95 case 3: /* P2WSH */
96 coins[i].out.scriptPubKey.resize(34);
97 coins[i].out.scriptPubKey[0] = OP_0;
98 coins[i].out.scriptPubKey[1] = 32;
99 std::copy(hash.begin(), hash.begin() + 32, coins[i].out.scriptPubKey.begin() + 2);
100 break;
101 case 4: /* P2TR */
102 coins[i].out.scriptPubKey.resize(34);
103 coins[i].out.scriptPubKey[0] = OP_1;
104 coins[i].out.scriptPubKey[1] = 32;
105 std::copy(hash.begin(), hash.begin() + 32, coins[i].out.scriptPubKey.begin() + 2);
106 break;
107 }
108 /* Hash again to construct nValue and fCoinBase. */
109 CSHA256().Write(PREFIX_M, 1).Write(ser, sizeof(ser)).Finalize(hash.begin());
110 coins[i].out.nValue = CAmount(hash.GetUint64(0) % MAX_MONEY);
111 coins[i].fCoinBase = (hash.GetUint64(1) & 7) == 0;
112 coins[i].nHeight = 0; /* Real nHeight used in simulation is set dynamically. */
113 }
114 }
115 };
116
117 enum class EntryType : uint8_t
118 {
119 /* This entry in the cache does not exist (so we'd have to look in the parent cache). */
120 NONE,
121
122 /* This entry in the cache corresponds to an unspent coin. */
123 UNSPENT,
124
125 /* This entry in the cache corresponds to a spent coin. */
126 SPENT,
127 };
128
129 struct CacheEntry
130 {
131 /* Type of entry. */
132 EntryType entrytype;
133
134 /* Index in the coins array this entry corresponds to (only if entrytype == UNSPENT). */
135 coinidx_type coinidx;
136
137 /* nHeight value for this entry (so the coins[coinidx].nHeight value is ignored; only if entrytype == UNSPENT). */
138 uint32_t height;
139 };
140
141 struct CacheLevel
142 {
143 CacheEntry entry[NUM_OUTPOINTS];
144
145 void Wipe() {
146 for (uint32_t i = 0; i < NUM_OUTPOINTS; ++i) {
147 entry[i].entrytype = EntryType::NONE;
148 }
149 }
150 };
151
152 /** Class for the base of the hierarchy (roughly simulating a memory-backed CCoinsViewDB).
153 *
154 * The initial state consists of the empty UTXO set.
155 */
156 class CoinsViewBottom final : public CoinsViewEmpty
157 {
158 std::map<COutPoint, Coin> m_data;
159
160 public:
161 std::optional<Coin> GetCoin(const COutPoint& outpoint) const final
162 {
163 if (auto it{m_data.find(outpoint)}; it != m_data.end()) {
164 assert(!it->second.IsSpent());
165 return it->second;
166 }
167 return std::nullopt;
168 }
169
170 void BatchWrite(CoinsViewCacheCursor& cursor, const uint256&) final
171 {
172 for (auto it{cursor.Begin()}; it != cursor.End(); it = cursor.NextAndMaybeErase(*it)) {
173 if (it->second.IsDirty()) {
174 if (it->second.coin.IsSpent()) {
175 m_data.erase(it->first);
176 } else {
177 if (cursor.WillErase(*it)) {
178 m_data[it->first] = std::move(it->second.coin);
179 } else {
180 m_data[it->first] = it->second.coin;
181 }
182 }
183 } else {
184 /* For non-dirty entries being written, compare them with what we have. */
185 auto it2 = m_data.find(it->first);
186 if (it->second.coin.IsSpent()) {
187 assert(it2 == m_data.end());
188 } else {
189 assert(it2 != m_data.end());
190 assert(it->second.coin.out == it2->second.out);
191 assert(it->second.coin.fCoinBase == it2->second.fCoinBase);
192 assert(it->second.coin.nHeight == it2->second.nHeight);
193 }
194 }
195 }
196 }
197 };
198
199 // Hold a non-movable ResetGuard on the heap so StartFetching can remain active
200 // for the lifetime of a CoinsViewOverlay cache level.
201 struct OverlayFetchScope
202 {
203 CCoinsViewCache::ResetGuard guard;
204 OverlayFetchScope(CoinsViewOverlay& view, const CBlock& block) : guard(view.StartFetching(block)) {}
205 };
206
207 // Reuse a single global thread pool across fuzz iterations. Creating and destroying a pool every
208 // iteration leaks memory, since iterations can run faster than the OS can tear down the threads.
209 std::shared_ptr<ThreadPool> g_thread_pool{std::make_shared<ThreadPool>("cache_fuzz")};
210 Mutex g_thread_pool_mutex;
211
212 void StartPoolIfNeeded() EXCLUSIVE_LOCKS_REQUIRED(!g_thread_pool_mutex)
213 {
214 LOCK(g_thread_pool_mutex);
215 if (!g_thread_pool->WorkersCount()) g_thread_pool->Start(DEFAULT_PREVOUTFETCH_THREADS);
216 }
217
218 } // namespace
219
220 FUZZ_TARGET(coinscache_sim, .init = [] { static auto setup{MakeNoLogFileContext<>()}; }) EXCLUSIVE_LOCKS_REQUIRED(!g_thread_pool_mutex)
221 {
222 SeedRandomStateForTest(SeedRand::ZEROS);
223 StartPoolIfNeeded();
224 /** Precomputed COutPoint and CCoins values. */
225 static const PrecomputedData data;
226
227 /** Dummy coinsview instance (base of the hierarchy). */
228 CoinsViewBottom bottom;
229 /** Real CCoinsViewCache objects. */
230 std::vector<std::unique_ptr<CCoinsViewCache>> caches;
231 /** Long-lived StartFetching guard (nullptr unless corresponding level is a CoinsViewOverlay). */
232 std::unique_ptr<OverlayFetchScope> overlay_fetch_scope;
233 /** Simulated cache data (sim_caches[0] matches bottom, sim_caches[i+1] matches caches[i]). */
234 CacheLevel sim_caches[MAX_CACHES + 1];
235 /** Current height in the simulation. */
236 uint32_t current_height = 1U;
237
238 // Initialize bottom simulated cache.
239 sim_caches[0].Wipe();
240
241 /** Helper lookup function in the simulated cache stack. */
242 auto lookup = [&](uint32_t outpointidx, int sim_idx = -1) -> std::optional<std::pair<coinidx_type, uint32_t>> {
243 uint32_t cache_idx = sim_idx == -1 ? caches.size() : sim_idx;
244 while (true) {
245 const auto& entry = sim_caches[cache_idx].entry[outpointidx];
246 if (entry.entrytype == EntryType::UNSPENT) {
247 return {{entry.coinidx, entry.height}};
248 } else if (entry.entrytype == EntryType::SPENT) {
249 return std::nullopt;
250 };
251 if (cache_idx == 0) break;
252 --cache_idx;
253 }
254 return std::nullopt;
255 };
256
257 /** Flush changes in top cache to the one below. */
258 auto flush = [&]() {
259 assert(caches.size() >= 1);
260 auto& cache = sim_caches[caches.size()];
261 auto& prev_cache = sim_caches[caches.size() - 1];
262 for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
263 if (cache.entry[outpointidx].entrytype != EntryType::NONE) {
264 prev_cache.entry[outpointidx] = cache.entry[outpointidx];
265 cache.entry[outpointidx].entrytype = EntryType::NONE;
266 }
267 }
268 };
269
270 // Main simulation loop: read commands from the fuzzer input, and apply them
271 // to both the real cache stack and the simulation.
272 FuzzedDataProvider provider(buffer.data(), buffer.size());
273 LIMITED_WHILE(provider.remaining_bytes(), 10000) {
274 // Every operation (except "Change height") moves current height forward,
275 // so it functions as a kind of epoch, making ~all UTXOs unique.
276 ++current_height;
277 // Make sure there is always at least one CCoinsViewCache.
278 if (caches.empty()) {
279 caches.emplace_back(new CCoinsViewCache(&bottom, /*deterministic=*/true));
280 sim_caches[caches.size()].Wipe();
281 }
282
283 // Execute command.
284 CallOneOf(
285 provider,
286
287 [&]() { // PeekCoin/GetCoin
288 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
289 // Look up in simulation data.
290 auto sim = lookup(outpointidx);
291 // Look up in real caches.
292 auto realcoin = provider.ConsumeBool() ?
293 caches.back()->PeekCoin(data.outpoints[outpointidx]) :
294 caches.back()->GetCoin(data.outpoints[outpointidx]);
295 // Compare results.
296 if (!sim.has_value()) {
297 assert(!realcoin);
298 } else {
299 assert(realcoin && !realcoin->IsSpent());
300 const auto& simcoin = data.coins[sim->first];
301 assert(realcoin->out == simcoin.out);
302 assert(realcoin->fCoinBase == simcoin.fCoinBase);
303 assert(realcoin->nHeight == sim->second);
304 }
305 },
306
307 [&]() { // HaveCoin
308 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
309 // Look up in simulation data.
310 auto sim = lookup(outpointidx);
311 // Look up in real caches.
312 auto real = caches.back()->HaveCoin(data.outpoints[outpointidx]);
313 // Compare results.
314 assert(sim.has_value() == real);
315 },
316
317 [&]() { // HaveCoinInCache
318 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
319 // Invoke on real cache (there is no equivalent in simulation, so nothing to compare result with).
320 (void)caches.back()->HaveCoinInCache(data.outpoints[outpointidx]);
321 },
322
323 [&]() { // AccessCoin
324 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
325 // Look up in simulation data.
326 auto sim = lookup(outpointidx);
327 // Look up in real caches.
328 const auto& realcoin = caches.back()->AccessCoin(data.outpoints[outpointidx]);
329 // Compare results.
330 if (!sim.has_value()) {
331 assert(realcoin.IsSpent());
332 } else {
333 assert(!realcoin.IsSpent());
334 const auto& simcoin = data.coins[sim->first];
335 assert(simcoin.out == realcoin.out);
336 assert(simcoin.fCoinBase == realcoin.fCoinBase);
337 assert(realcoin.nHeight == sim->second);
338 }
339 },
340
341 [&]() { // AddCoin (only possible_overwrite if necessary)
342 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
343 uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
344 // Look up in simulation data (to know whether we must set possible_overwrite or not).
345 auto sim = lookup(outpointidx);
346 // Invoke on real caches.
347 Coin coin = data.coins[coinidx];
348 coin.nHeight = current_height;
349 caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), sim.has_value());
350 // Apply to simulation data.
351 auto& entry = sim_caches[caches.size()].entry[outpointidx];
352 entry.entrytype = EntryType::UNSPENT;
353 entry.coinidx = coinidx;
354 entry.height = current_height;
355 },
356
357 [&]() { // AddCoin (always possible_overwrite)
358 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
359 uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
360 // Invoke on real caches.
361 Coin coin = data.coins[coinidx];
362 coin.nHeight = current_height;
363 caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), true);
364 // Apply to simulation data.
365 auto& entry = sim_caches[caches.size()].entry[outpointidx];
366 entry.entrytype = EntryType::UNSPENT;
367 entry.coinidx = coinidx;
368 entry.height = current_height;
369 },
370
371 [&]() { // SpendCoin (moveto = nullptr)
372 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
373 // Invoke on real caches.
374 caches.back()->SpendCoin(data.outpoints[outpointidx], nullptr);
375 // Apply to simulation data.
376 sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
377 },
378
379 [&]() { // SpendCoin (with moveto)
380 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
381 // Look up in simulation data (to compare the returned *moveto with).
382 auto sim = lookup(outpointidx);
383 // Invoke on real caches.
384 Coin realcoin;
385 caches.back()->SpendCoin(data.outpoints[outpointidx], &realcoin);
386 // Apply to simulation data.
387 sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
388 // Compare *moveto with the value expected based on simulation data.
389 if (!sim.has_value()) {
390 assert(realcoin.IsSpent());
391 } else {
392 assert(!realcoin.IsSpent());
393 const auto& simcoin = data.coins[sim->first];
394 assert(simcoin.out == realcoin.out);
395 assert(simcoin.fCoinBase == realcoin.fCoinBase);
396 assert(realcoin.nHeight == sim->second);
397 }
398 },
399
400 [&]() { // Uncache
401 uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
402 // Apply to real caches (there is no equivalent in our simulation).
403 caches.back()->Uncache(data.outpoints[outpointidx]);
404 },
405
406 [&]() { // Add a cache level (if not already at the max).
407 if (caches.size() != MAX_CACHES) {
408 if (overlay_fetch_scope) {
409 overlay_fetch_scope.reset();
410 sim_caches[caches.size()].Wipe();
411 }
412 // Apply to real caches.
413 if (provider.ConsumeBool()) {
414 caches.emplace_back(new CCoinsViewCache(&*caches.back(), /*deterministic=*/true));
415 } else {
416 caches.emplace_back(new CoinsViewOverlay(&*caches.back(), g_thread_pool, /*deterministic=*/true));
417 auto& overlay{static_cast<CoinsViewOverlay&>(*caches.back())};
418 overlay_fetch_scope = std::make_unique<OverlayFetchScope>(overlay, data.block);
419 }
420 // Apply to simulation data.
421 sim_caches[caches.size()].Wipe();
422 }
423 },
424
425 [&]() { // Remove a cache level.
426 // Apply to real caches (this reduces caches.size(), implicitly doing the same on the simulation data).
427 caches.back()->SanityCheck();
428 overlay_fetch_scope.reset();
429 caches.pop_back();
430 },
431
432 [&]() { // Flush.
433 // CoinsViewOverlay::Flush() must have all inputs consumed before being called
434 if (auto* overlay{dynamic_cast<CoinsViewOverlay*>(caches.back().get())};
435 overlay && !overlay->AllInputsConsumed()) {
436 return;
437 }
438 // Apply to simulation data.
439 flush();
440 // Apply to real caches.
441 caches.back()->Flush(/*reallocate_cache=*/provider.ConsumeBool());
442 },
443
444 [&]() { // Sync.
445 if (overlay_fetch_scope) return; // CoinsViewOverlay::Sync() is never called in production
446 // Apply to simulation data (note that in our simulation, syncing and flushing is the same thing).
447 flush();
448 // Apply to real caches.
449 caches.back()->Sync();
450 },
451
452 [&]() { // Reset.
453 sim_caches[caches.size()].Wipe();
454 // Apply to real caches. Optionally start fetching again.
455 if (overlay_fetch_scope && provider.ConsumeBool()) {
456 overlay_fetch_scope.reset();
457 auto& overlay{static_cast<CoinsViewOverlay&>(*caches.back())};
458 overlay_fetch_scope = std::make_unique<OverlayFetchScope>(overlay, data.block);
459 } else {
460 (void)caches.back()->CreateResetGuard();
461 }
462 },
463
464 [&]() { // GetCacheSize
465 (void)caches.back()->GetCacheSize();
466 },
467
468 [&]() { // DynamicMemoryUsage
469 (void)caches.back()->DynamicMemoryUsage();
470 },
471
472 [&]() { // Change height
473 current_height = provider.ConsumeIntegralInRange<uint32_t>(1, current_height - 1);
474 }
475 );
476 }
477
478 // Sanity check all the remaining caches
479 for (const auto& cache : caches) {
480 cache->SanityCheck();
481 }
482
483 // Full comparison between caches and simulation data, from bottom to top,
484 for (unsigned sim_idx = 1; sim_idx <= caches.size(); ++sim_idx) {
485 auto& cache = *caches[sim_idx - 1];
486 size_t cache_size = 0;
487
488 for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
489 cache_size += cache.HaveCoinInCache(data.outpoints[outpointidx]);
490 const auto real{cache.PeekCoin(data.outpoints[outpointidx])};
491 auto sim = lookup(outpointidx, sim_idx);
492 if (!sim.has_value()) {
493 assert(!real);
494 } else {
495 assert(!real->IsSpent());
496 assert(real->out == data.coins[sim->first].out);
497 assert(real->fCoinBase == data.coins[sim->first].fCoinBase);
498 assert(real->nHeight == sim->second);
499 }
500 }
501
502 // HaveCoinInCache ignores spent coins, so GetCacheSize() may exceed it.
503 assert(cache.GetCacheSize() >= cache_size);
504 }
505
506 // Compare the bottom coinsview (not a CCoinsViewCache) with sim_cache[0].
507 for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
508 auto realcoin = bottom.GetCoin(data.outpoints[outpointidx]);
509 auto sim = lookup(outpointidx, 0);
510 if (!sim.has_value()) {
511 assert(!realcoin);
512 } else {
513 assert(realcoin && !realcoin->IsSpent());
514 assert(realcoin->out == data.coins[sim->first].out);
515 assert(realcoin->fCoinBase == data.coins[sim->first].fCoinBase);
516 assert(realcoin->nHeight == sim->second);
517 }
518 }
519 }
520