Inside Bitcoin

251        }
252        return std::nullopt;
253    };
254
255    /** Flush changes in top cache to the one below. */
256    auto flush = [&]() {
257        assert(caches.size() >= 1);
258        auto& cache = sim_caches[caches.size()];
259        auto& prev_cache = sim_caches[caches.size() - 1];
260        for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
261            if (cache.entry[outpointidx].entrytype != EntryType::NONE) {
262                prev_cache.entry[outpointidx] = cache.entry[outpointidx];
263                cache.entry[outpointidx].entrytype = EntryType::NONE;
264            }
265        }
266    };
267
268    /** Helper creating a fetch scope for the top cache (which must be a CoinsViewOverlay). */
269    const auto make_fetch_scope{[&] {
270        auto& overlay{static_cast<CoinsViewOverlay&>(*caches.back())};
271        return std::make_unique<OverlayFetchScope>(overlay, data.block);
272    }};
273
274    // Main simulation loop: read commands from the fuzzer input, and apply them
275    // to both the real cache stack and the simulation.
276    FuzzedDataProvider provider(buffer.data(), buffer.size());
277    LIMITED_WHILE (provider.remaining_bytes(), 10000) {
278        // Every operation (except "Change height") moves current height forward,
279        // so it functions as a kind of epoch, making ~all UTXOs unique.
280        ++current_height;
281        // Make sure there is always at least one CCoinsViewCache.
282        if (caches.empty()) {
283            caches.emplace_back(new CCoinsViewCache(&bottom, /*deterministic=*/true));
284            fetch_scopes.emplace_back();
285            sim_caches[caches.size()].Wipe();
286        }
287        assert(caches.size() == fetch_scopes.size());
288
289        // Execute command.
290        CallOneOf(
291            provider,
292
293            [&]() { // PeekCoin/GetCoin
294                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
295                // Look up in simulation data.
296                auto sim = lookup(outpointidx);
297                // Look up in real caches.
298                auto realcoin = provider.ConsumeBool() ?
299                    caches.back()->PeekCoin(data.outpoints[outpointidx]) :
300                    caches.back()->GetCoin(data.outpoints[outpointidx]);
301                // Compare results.
302                if (!sim.has_value()) {
303                    assert(!realcoin);
304                } else {
305                    assert(realcoin && !realcoin->IsSpent());
306                    const auto& simcoin = data.coins[sim->first];
307                    assert(realcoin->out == simcoin.out);
308                    assert(realcoin->fCoinBase == simcoin.fCoinBase);
309                    assert(realcoin->nHeight == sim->second);
310                }
311            },
312
313            [&]() { // HaveCoin
314                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
315                // Look up in simulation data.
316                auto sim = lookup(outpointidx);
317                // Look up in real caches.
318                auto real = caches.back()->HaveCoin(data.outpoints[outpointidx]);
319                // Compare results.
320                assert(sim.has_value() == real);
321            },
322
323            [&]() { // HaveCoinInCache
324                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
325                // Invoke on real cache (there is no equivalent in simulation, so nothing to compare result with).
326                (void)caches.back()->HaveCoinInCache(data.outpoints[outpointidx]);
327            },
328
329            [&]() { // AccessCoin
330                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
331                // Look up in simulation data.
332                auto sim = lookup(outpointidx);
333                // Look up in real caches.
334                const auto& realcoin = caches.back()->AccessCoin(data.outpoints[outpointidx]);
335                // Compare results.
336                if (!sim.has_value()) {
337                    assert(realcoin.IsSpent());
338                } else {
339                    assert(!realcoin.IsSpent());
340                    const auto& simcoin = data.coins[sim->first];
341                    assert(simcoin.out == realcoin.out);
342                    assert(simcoin.fCoinBase == realcoin.fCoinBase);
343                    assert(realcoin.nHeight == sim->second);
344                }
345            },
346
347            [&]() { // AddCoin (only possible_overwrite if necessary)
348                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
349                uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
350                // Look up in simulation data (to know whether we must set possible_overwrite or not).
351                auto sim = lookup(outpointidx);
352                // Invoke on real caches.
353                Coin coin = data.coins[coinidx];
354                coin.nHeight = current_height;
355                caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), sim.has_value());
356                // Apply to simulation data.
357                auto& entry = sim_caches[caches.size()].entry[outpointidx];
358                entry.entrytype = EntryType::UNSPENT;
359                entry.coinidx = coinidx;
360                entry.height = current_height;
361            },
362
363            [&]() { // AddCoin (always possible_overwrite)
364                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
365                uint32_t coinidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_COINS - 1);
366                // Invoke on real caches.
367                Coin coin = data.coins[coinidx];
368                coin.nHeight = current_height;
369                caches.back()->AddCoin(data.outpoints[outpointidx], std::move(coin), true);
370                // Apply to simulation data.
371                auto& entry = sim_caches[caches.size()].entry[outpointidx];
372                entry.entrytype = EntryType::UNSPENT;
373                entry.coinidx = coinidx;
374                entry.height = current_height;
375            },
376
377            [&]() { // SpendCoin (moveto = nullptr)
378                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
379                // Invoke on real caches.
380                caches.back()->SpendCoin(data.outpoints[outpointidx], nullptr);
381                // Apply to simulation data.
382                sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
383            },
384
385            [&]() { // SpendCoin (with moveto)
386                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
387                // Look up in simulation data (to compare the returned *moveto with).
388                auto sim = lookup(outpointidx);
389                // Invoke on real caches.
390                Coin realcoin;
391                caches.back()->SpendCoin(data.outpoints[outpointidx], &realcoin);
392                // Apply to simulation data.
393                sim_caches[caches.size()].entry[outpointidx].entrytype = EntryType::SPENT;
394                // Compare *moveto with the value expected based on simulation data.
395                if (!sim.has_value()) {
396                    assert(realcoin.IsSpent());
397                } else {
398                    assert(!realcoin.IsSpent());
399                    const auto& simcoin = data.coins[sim->first];
400                    assert(simcoin.out == realcoin.out);
401                    assert(simcoin.fCoinBase == realcoin.fCoinBase);
402                    assert(realcoin.nHeight == sim->second);
403                }
404            },
405
406            [&]() { // Uncache
407                uint32_t outpointidx = provider.ConsumeIntegralInRange<uint32_t>(0, NUM_OUTPOINTS - 1);
408                // Apply to real caches (there is no equivalent in our simulation).
409                caches.back()->Uncache(data.outpoints[outpointidx]);
410            },
411
412            [&]() { // Add a cache level (if not already at the max).
413                if (caches.size() != MAX_CACHES) {
414                    // Apply to real caches.
415                    if (provider.ConsumeBool()) {
416                        caches.emplace_back(new CCoinsViewCache(&*caches.back(), /*deterministic=*/true));
417                        fetch_scopes.emplace_back();
418                    } else {
419                        caches.emplace_back(new CoinsViewOverlay(&*caches.back(), g_thread_pool, /*deterministic=*/true));
420                        fetch_scopes.emplace_back(make_fetch_scope());
421                    }
422                    // Apply to simulation data.
423                    sim_caches[caches.size()].Wipe();
424                }
425            },
426
427            [&]() { // Remove a cache level.
428                // Apply to real caches (this reduces caches.size(), implicitly doing the same on the simulation data).
429                caches.back()->SanityCheck();
430                fetch_scopes.pop_back();
431                caches.pop_back();
432            },
433
434            [&]() { // Flush.
435                // CoinsViewOverlay::Flush() must have all inputs consumed before being called
436                if (auto* overlay{dynamic_cast<CoinsViewOverlay*>(caches.back().get())};
437                    overlay && !overlay->AllInputsConsumed()) {
438                    return;
439                }
440                // Apply to simulation data.
441                flush();
442                // Apply to real caches.
443                caches.back()->Flush(/*reallocate_cache=*/provider.ConsumeBool());
444            },
445
446            [&]() { // Sync.
447                if (fetch_scopes.back()) return; // CoinsViewOverlay::Sync() is never called in production
448                // Apply to simulation data (note that in our simulation, syncing and flushing is the same thing).
449                flush();
450                // Apply to real caches.
451                caches.back()->Sync();
452            },
453
454            [&]() { // Reset.
455                sim_caches[caches.size()].Wipe();
456                // Apply to real caches. Optionally start fetching again.
457                if (fetch_scopes.back() && provider.ConsumeBool()) {
458                    fetch_scopes.back().reset(); // Stop fetching before starting again.
459                    fetch_scopes.back() = make_fetch_scope();
460                } else {
461                    (void)caches.back()->CreateResetGuard();
462                }
463            },
464
465            [&]() { // GetCacheSize
466                (void)caches.back()->GetCacheSize();
467            },
468
469            [&]() { // DynamicMemoryUsage
470                (void)caches.back()->DynamicMemoryUsage();
471            },
472
473            [&]() { // Change height
474                current_height = provider.ConsumeIntegralInRange<uint32_t>(1, current_height - 1);
475            }
476        );
477    }
478
479    // Sanity check all the remaining caches
480    for (const auto& cache : caches) {
481        cache->SanityCheck();
482    }
483
484    // Full comparison between caches and simulation data, from bottom to top,
485    for (unsigned sim_idx = 1; sim_idx <= caches.size(); ++sim_idx) {
486        auto& cache = *caches[sim_idx - 1];
487        size_t cache_size = 0;
488
489        for (uint32_t outpointidx = 0; outpointidx < NUM_OUTPOINTS; ++outpointidx) {
490            cache_size += cache.HaveCoinInCache(data.outpoints[outpointidx]);
491            const auto real{cache.PeekCoin(data.outpoints[outpointidx])};
492            auto sim = lookup(outpointidx, sim_idx);
493            if (!sim.has_value()) {
494                assert(!real);
495            } else {
496                assert(!real->IsSpent());
497                assert(real->out == data.coins[sim->first].out);
498                assert(real->fCoinBase == data.coins[sim->first].fCoinBase);
499                assert(real->nHeight == sim->second);
500            }