diff options
Diffstat (limited to 'src/test')
40 files changed, 890 insertions, 385 deletions
diff --git a/src/test/CMakeLists.txt b/src/test/CMakeLists.txt index 2c9957117c..c23fbae92f 100644 --- a/src/test/CMakeLists.txt +++ b/src/test/CMakeLists.txt @@ -160,14 +160,6 @@ if(ENABLE_WALLET) endif() if(WITH_MULTIPROCESS) - add_library(bitcoin_ipc_test STATIC EXCLUDE_FROM_ALL - ipc_test.cpp - ) - - target_capnp_sources(bitcoin_ipc_test ${PROJECT_SOURCE_DIR} - ipc_test.capnp - ) - target_link_libraries(bitcoin_ipc_test PRIVATE core_interface diff --git a/src/test/addrman_tests.cpp b/src/test/addrman_tests.cpp index da6ff77924..c4f58ebecf 100644 --- a/src/test/addrman_tests.cpp +++ b/src/test/addrman_tests.cpp @@ -196,21 +196,21 @@ BOOST_AUTO_TEST_CASE(addrman_select) BOOST_AUTO_TEST_CASE(addrman_select_by_network) { auto addrman = std::make_unique<AddrMan>(EMPTY_NETGROUPMAN, DETERMINISTIC, GetCheckRatio(m_node)); - BOOST_CHECK(!addrman->Select(/*new_only=*/true, NET_IPV4).first.IsValid()); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_IPV4).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/true, {NET_IPV4}).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_IPV4}).first.IsValid()); // add ipv4 address to the new table CNetAddr source = ResolveIP("252.2.2.2"); CService addr1 = ResolveService("250.1.1.1", 8333); BOOST_CHECK(addrman->Add({CAddress(addr1, NODE_NONE)}, source)); - BOOST_CHECK(addrman->Select(/*new_only=*/true, NET_IPV4).first == addr1); - BOOST_CHECK(addrman->Select(/*new_only=*/false, NET_IPV4).first == addr1); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_IPV6).first.IsValid()); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_ONION).first.IsValid()); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_I2P).first.IsValid()); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_CJDNS).first.IsValid()); - BOOST_CHECK(!addrman->Select(/*new_only=*/true, NET_CJDNS).first.IsValid()); + BOOST_CHECK(addrman->Select(/*new_only=*/true, {NET_IPV4}).first == addr1); + BOOST_CHECK(addrman->Select(/*new_only=*/false, {NET_IPV4}).first == addr1); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_IPV6}).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_ONION}).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_I2P}).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_CJDNS}).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/true, {NET_CJDNS}).first.IsValid()); BOOST_CHECK(addrman->Select(/*new_only=*/false).first == addr1); // add I2P address to the new table @@ -218,25 +218,29 @@ BOOST_AUTO_TEST_CASE(addrman_select_by_network) i2p_addr.SetSpecial("udhdrtrcetjm5sxzskjyr5ztpeszydbh4dpl3pl4utgqqw2v4jna.b32.i2p"); BOOST_CHECK(addrman->Add({i2p_addr}, source)); - BOOST_CHECK(addrman->Select(/*new_only=*/true, NET_I2P).first == i2p_addr); - BOOST_CHECK(addrman->Select(/*new_only=*/false, NET_I2P).first == i2p_addr); - BOOST_CHECK(addrman->Select(/*new_only=*/false, NET_IPV4).first == addr1); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_IPV6).first.IsValid()); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_ONION).first.IsValid()); - BOOST_CHECK(!addrman->Select(/*new_only=*/false, NET_CJDNS).first.IsValid()); + BOOST_CHECK(addrman->Select(/*new_only=*/true, {NET_I2P}).first == i2p_addr); + BOOST_CHECK(addrman->Select(/*new_only=*/false, {NET_I2P}).first == i2p_addr); + BOOST_CHECK(addrman->Select(/*new_only=*/false, {NET_IPV4}).first == addr1); + std::unordered_set<Network> nets_with_entries = {NET_IPV4, NET_I2P}; + BOOST_CHECK(addrman->Select(/*new_only=*/false, nets_with_entries).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_IPV6}).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_ONION}).first.IsValid()); + BOOST_CHECK(!addrman->Select(/*new_only=*/false, {NET_CJDNS}).first.IsValid()); + std::unordered_set<Network> nets_without_entries = {NET_IPV6, NET_ONION, NET_CJDNS}; + BOOST_CHECK(!addrman->Select(/*new_only=*/false, nets_without_entries).first.IsValid()); // bump I2P address to tried table BOOST_CHECK(addrman->Good(i2p_addr)); - BOOST_CHECK(!addrman->Select(/*new_only=*/true, NET_I2P).first.IsValid()); - BOOST_CHECK(addrman->Select(/*new_only=*/false, NET_I2P).first == i2p_addr); + BOOST_CHECK(!addrman->Select(/*new_only=*/true, {NET_I2P}).first.IsValid()); + BOOST_CHECK(addrman->Select(/*new_only=*/false, {NET_I2P}).first == i2p_addr); // add another I2P address to the new table CAddress i2p_addr2; i2p_addr2.SetSpecial("c4gfnttsuwqomiygupdqqqyy5y5emnk5c73hrfvatri67prd7vyq.b32.i2p"); BOOST_CHECK(addrman->Add({i2p_addr2}, source)); - BOOST_CHECK(addrman->Select(/*new_only=*/true, NET_I2P).first == i2p_addr2); + BOOST_CHECK(addrman->Select(/*new_only=*/true, {NET_I2P}).first == i2p_addr2); // ensure that both new and tried table are selected from bool new_selected{false}; @@ -244,7 +248,7 @@ BOOST_AUTO_TEST_CASE(addrman_select_by_network) int counter = 256; while (--counter > 0 && (!new_selected || !tried_selected)) { - const CAddress selected{addrman->Select(/*new_only=*/false, NET_I2P).first}; + const CAddress selected{addrman->Select(/*new_only=*/false, {NET_I2P}).first}; BOOST_REQUIRE(selected == i2p_addr || selected == i2p_addr2); if (selected == i2p_addr) { tried_selected = true; @@ -277,7 +281,7 @@ BOOST_AUTO_TEST_CASE(addrman_select_special) // since the only ipv4 address is on the new table, ensure that the new // table gets selected even if new_only is false. if the table was being // selected at random, this test will sporadically fail - BOOST_CHECK(addrman->Select(/*new_only=*/false, NET_IPV4).first == addr1); + BOOST_CHECK(addrman->Select(/*new_only=*/false, {NET_IPV4}).first == addr1); } BOOST_AUTO_TEST_CASE(addrman_new_collisions) diff --git a/src/test/blockfilter_index_tests.cpp b/src/test/blockfilter_index_tests.cpp index f6024f1ef3..48ae874fcd 100644 --- a/src/test/blockfilter_index_tests.cpp +++ b/src/test/blockfilter_index_tests.cpp @@ -144,7 +144,7 @@ BOOST_FIXTURE_TEST_CASE(blockfilter_index_initial_sync, BuildChainTestingSetup) BOOST_REQUIRE(filter_index.StartBackgroundSync()); // Allow filter index to catch up with the block index. - IndexWaitSynced(filter_index, *Assert(m_node.shutdown)); + IndexWaitSynced(filter_index, *Assert(m_node.shutdown_signal)); // Check that filter index has all blocks that were in the chain before it started. { diff --git a/src/test/blockmanager_tests.cpp b/src/test/blockmanager_tests.cpp index 121f00bd25..c2b95dd861 100644 --- a/src/test/blockmanager_tests.cpp +++ b/src/test/blockmanager_tests.cpp @@ -28,13 +28,13 @@ BOOST_FIXTURE_TEST_SUITE(blockmanager_tests, BasicTestingSetup) BOOST_AUTO_TEST_CASE(blockmanager_find_block_pos) { const auto params {CreateChainParams(ArgsManager{}, ChainType::MAIN)}; - KernelNotifications notifications{*Assert(m_node.shutdown), m_node.exit_status, *Assert(m_node.warnings)}; + KernelNotifications notifications{Assert(m_node.shutdown_request), m_node.exit_status, *Assert(m_node.warnings)}; const BlockManager::Options blockman_opts{ .chainparams = *params, .blocks_dir = m_args.GetBlocksDirPath(), .notifications = notifications, }; - BlockManager blockman{*Assert(m_node.shutdown), blockman_opts}; + BlockManager blockman{*Assert(m_node.shutdown_signal), blockman_opts}; // simulate adding a genesis block normally BOOST_CHECK_EQUAL(blockman.SaveBlockToDisk(params->GenesisBlock(), 0).nPos, BLOCK_SERIALIZATION_HEADER_SIZE); // simulate what happens during reindex @@ -135,13 +135,13 @@ BOOST_FIXTURE_TEST_CASE(blockmanager_block_data_availability, TestChain100Setup) BOOST_AUTO_TEST_CASE(blockmanager_flush_block_file) { - KernelNotifications notifications{*Assert(m_node.shutdown), m_node.exit_status, *Assert(m_node.warnings)}; + KernelNotifications notifications{Assert(m_node.shutdown_request), m_node.exit_status, *Assert(m_node.warnings)}; node::BlockManager::Options blockman_opts{ .chainparams = Params(), .blocks_dir = m_args.GetBlocksDirPath(), .notifications = notifications, }; - BlockManager blockman{*Assert(m_node.shutdown), blockman_opts}; + BlockManager blockman{*Assert(m_node.shutdown_signal), blockman_opts}; // Test blocks with no transactions, not even a coinbase CBlock block1; diff --git a/src/test/cluster_linearize_tests.cpp b/src/test/cluster_linearize_tests.cpp index d15e783ea1..265ccdc805 100644 --- a/src/test/cluster_linearize_tests.cpp +++ b/src/test/cluster_linearize_tests.cpp @@ -18,13 +18,24 @@ using namespace cluster_linearize; namespace { +/** Special magic value that indicates to TestDepGraphSerialization that a cluster entry represents + * a hole. */ +constexpr std::pair<FeeFrac, TestBitSet> HOLE{FeeFrac{0, 0x3FFFFF}, {}}; + template<typename SetType> -void TestDepGraphSerialization(const Cluster<SetType>& cluster, const std::string& hexenc) +void TestDepGraphSerialization(const std::vector<std::pair<FeeFrac, SetType>>& cluster, const std::string& hexenc) { - DepGraph depgraph(cluster); - - // Run normal sanity and correspondence checks, which includes a round-trip test. - VerifyDepGraphFromCluster(cluster, depgraph); + // Construct DepGraph from cluster argument. + DepGraph<SetType> depgraph; + SetType holes; + for (ClusterIndex i = 0; i < cluster.size(); ++i) { + depgraph.AddTransaction(cluster[i].first); + if (cluster[i] == HOLE) holes.Set(i); + } + for (ClusterIndex i = 0; i < cluster.size(); ++i) { + depgraph.AddDependencies(cluster[i].second, i); + } + depgraph.RemoveTransactions(holes); // There may be multiple serializations of the same graph, but DepGraphFormatter's serializer // only produces one of those. Verify that hexenc matches that canonical serialization. @@ -133,6 +144,34 @@ BOOST_AUTO_TEST_CASE(depgraph_ser_tests) skip insertion C): D,A,B,E,C */ "00" /* end of graph */ ); + + // Transactions: A(1,2), B(3,1), C(2,1), D(1,3), E(1,1). Deps: C->A, D->A, D->B, E->D. + // In order: [_, D, _, _, A, _, B, _, _, _, E, _, _, C] (_ being holes). Internally serialized + // in order A,B,C,D,E. + TestDepGraphSerialization<TestBitSet>( + {HOLE, {{1, 3}, {4, 6}}, HOLE, HOLE, {{1, 2}, {}}, HOLE, {{3, 1}, {}}, HOLE, HOLE, HOLE, {{1, 1}, {1}}, HOLE, HOLE, {{2, 1}, {4}}}, + "02" /* A size */ + "02" /* A fee */ + "03" /* A insertion position (3 holes): _, _, _, A */ + "01" /* B size */ + "06" /* B fee */ + "06" /* B insertion position (skip B->A dependency, skip 4 inserts, add 1 hole): _, _, _, A, _, B */ + "01" /* C size */ + "04" /* C fee */ + "01" /* C->A dependency (skip C->B dependency) */ + "0b" /* C insertion position (skip 6 inserts, add 5 holes): _, _, _, A, _, B, _, _, _, _, _, C */ + "03" /* D size */ + "02" /* D fee */ + "01" /* D->B dependency (skip D->C dependency) */ + "00" /* D->A dependency (no skips) */ + "0b" /* D insertion position (skip 11 inserts): _, D, _, _, A, _, B, _, _, _, _, _, C */ + "01" /* E size */ + "02" /* E fee */ + "00" /* E->D dependency (no skips) */ + "04" /* E insertion position (skip E->C dependency, E->B and E->A are implied, skip 3 + inserts): _, D, _, _, A, _, B, _, _, _, E, _, _, C */ + "00" /* end of graph */ + ); } BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/coinstatsindex_tests.cpp b/src/test/coinstatsindex_tests.cpp index 08814c1499..e09aad05e9 100644 --- a/src/test/coinstatsindex_tests.cpp +++ b/src/test/coinstatsindex_tests.cpp @@ -35,7 +35,7 @@ BOOST_FIXTURE_TEST_CASE(coinstatsindex_initial_sync, TestChain100Setup) BOOST_REQUIRE(coin_stats_index.StartBackgroundSync()); - IndexWaitSynced(coin_stats_index, *Assert(m_node.shutdown)); + IndexWaitSynced(coin_stats_index, *Assert(m_node.shutdown_signal)); // Check that CoinStatsIndex works for genesis block. const CBlockIndex* genesis_block_index; @@ -86,7 +86,7 @@ BOOST_FIXTURE_TEST_CASE(coinstatsindex_unclean_shutdown, TestChain100Setup) CoinStatsIndex index{interfaces::MakeChain(m_node), 1 << 20}; BOOST_REQUIRE(index.Init()); BOOST_REQUIRE(index.StartBackgroundSync()); - IndexWaitSynced(index, *Assert(m_node.shutdown)); + IndexWaitSynced(index, *Assert(m_node.shutdown_signal)); std::shared_ptr<const CBlock> new_block; CBlockIndex* new_block_index = nullptr; { diff --git a/src/test/feefrac_tests.cpp b/src/test/feefrac_tests.cpp index 5af3c3d7ed..41c9c0a633 100644 --- a/src/test/feefrac_tests.cpp +++ b/src/test/feefrac_tests.cpp @@ -15,7 +15,7 @@ BOOST_AUTO_TEST_CASE(feefrac_operators) FeeFrac sum{1500, 400}; FeeFrac diff{500, -200}; FeeFrac empty{0, 0}; - FeeFrac zero_fee{0, 1}; // zero-fee allowed + [[maybe_unused]] FeeFrac zero_fee{0, 1}; // zero-fee allowed BOOST_CHECK(empty == FeeFrac{}); // same as no-args diff --git a/src/test/fuzz/CMakeLists.txt b/src/test/fuzz/CMakeLists.txt index 165add2e5a..1c7b0d5c25 100644 --- a/src/test/fuzz/CMakeLists.txt +++ b/src/test/fuzz/CMakeLists.txt @@ -72,6 +72,7 @@ add_executable(fuzz netbase_dns_lookup.cpp node_eviction.cpp p2p_handshake.cpp + p2p_headers_presync.cpp p2p_transport_serialization.cpp package_eval.cpp parse_hd_keypath.cpp diff --git a/src/test/fuzz/addrman.cpp b/src/test/fuzz/addrman.cpp index c324b4fdd9..bcc3dd3e14 100644 --- a/src/test/fuzz/addrman.cpp +++ b/src/test/fuzz/addrman.cpp @@ -186,7 +186,7 @@ public: return false; } - auto IdsReferToSameAddress = [&](int id, int other_id) EXCLUSIVE_LOCKS_REQUIRED(m_impl->cs, other.m_impl->cs) { + auto IdsReferToSameAddress = [&](nid_type id, nid_type other_id) EXCLUSIVE_LOCKS_REQUIRED(m_impl->cs, other.m_impl->cs) { if (id == -1 && other_id == -1) { return true; } @@ -285,7 +285,15 @@ FUZZ_TARGET(addrman, .init = initialize_addrman) auto max_pct = fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, 4096); auto filtered = fuzzed_data_provider.ConsumeBool(); (void)const_addr_man.GetAddr(max_addresses, max_pct, network, filtered); - (void)const_addr_man.Select(fuzzed_data_provider.ConsumeBool(), network); + + std::unordered_set<Network> nets; + for (const auto& net : ALL_NETWORKS) { + if (fuzzed_data_provider.ConsumeBool()) { + nets.insert(net); + } + } + (void)const_addr_man.Select(fuzzed_data_provider.ConsumeBool(), nets); + std::optional<bool> in_new; if (fuzzed_data_provider.ConsumeBool()) { in_new = fuzzed_data_provider.ConsumeBool(); diff --git a/src/test/fuzz/autofile.cpp b/src/test/fuzz/autofile.cpp index 45316b6b21..81761c7bf9 100644 --- a/src/test/fuzz/autofile.cpp +++ b/src/test/fuzz/autofile.cpp @@ -56,7 +56,6 @@ FUZZ_TARGET(autofile) WriteToStream(fuzzed_data_provider, auto_file); }); } - (void)auto_file.Get(); (void)auto_file.IsNull(); if (fuzzed_data_provider.ConsumeBool()) { FILE* f = auto_file.release(); diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp index 2dfdfbb41d..5b3770636a 100644 --- a/src/test/fuzz/cluster_linearize.cpp +++ b/src/test/fuzz/cluster_linearize.cpp @@ -3,6 +3,7 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. #include <cluster_linearize.h> +#include <random.h> #include <serialize.h> #include <streams.h> #include <test/fuzz/fuzz.h> @@ -36,7 +37,7 @@ class SimpleCandidateFinder public: /** Construct an SimpleCandidateFinder for a given graph. */ SimpleCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept : - m_depgraph(depgraph), m_todo{SetType::Fill(depgraph.TxCount())} {} + m_depgraph(depgraph), m_todo{depgraph.Positions()} {} /** Remove a set of transactions from the set of to-be-linearized ones. */ void MarkDone(SetType select) noexcept { m_todo -= select; } @@ -106,7 +107,7 @@ class ExhaustiveCandidateFinder public: /** Construct an ExhaustiveCandidateFinder for a given graph. */ ExhaustiveCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept : - m_depgraph(depgraph), m_todo{SetType::Fill(depgraph.TxCount())} {} + m_depgraph(depgraph), m_todo{depgraph.Positions()} {} /** Remove a set of transactions from the set of to-be-linearized ones. */ void MarkDone(SetType select) noexcept { m_todo -= select; } @@ -152,7 +153,7 @@ std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetTyp { std::vector<ClusterIndex> linearization; SimpleCandidateFinder finder(depgraph); - SetType todo = SetType::Fill(depgraph.TxCount()); + SetType todo = depgraph.Positions(); bool optimal = true; while (todo.Any()) { auto [candidate, iterations_done] = finder.FindCandidateSet(max_iterations); @@ -165,6 +166,23 @@ std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetTyp return {std::move(linearization), optimal}; } +/** Stitch connected components together in a DepGraph, guaranteeing its corresponding cluster is connected. */ +template<typename BS> +void MakeConnected(DepGraph<BS>& depgraph) +{ + auto todo = depgraph.Positions(); + auto comp = depgraph.FindConnectedComponent(todo); + Assume(depgraph.IsConnected(comp)); + todo -= comp; + while (todo.Any()) { + auto nextcomp = depgraph.FindConnectedComponent(todo); + Assume(depgraph.IsConnected(nextcomp)); + depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First()); + todo -= nextcomp; + comp = nextcomp; + } +} + /** Given a dependency graph, and a todo set, read a topological subset of todo from reader. */ template<typename SetType> SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& todo, SpanReader& reader) @@ -188,7 +206,7 @@ template<typename BS> std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader) { std::vector<ClusterIndex> linearization; - TestBitSet todo = TestBitSet::Fill(depgraph.TxCount()); + TestBitSet todo = depgraph.Positions(); // In every iteration one topologically-valid transaction is appended to linearization. while (todo.Any()) { // Compute the set of transactions with no not-yet-included ancestors. @@ -223,59 +241,157 @@ std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanRe } // namespace -FUZZ_TARGET(clusterlin_add_dependency) -{ - // Verify that computing a DepGraph from a cluster, or building it step by step using AddDependency - // have the same effect. - - // Construct a cluster of a certain length, with no dependencies. - FuzzedDataProvider provider(buffer.data(), buffer.size()); - auto num_tx = provider.ConsumeIntegralInRange<ClusterIndex>(2, 32); - Cluster<TestBitSet> cluster(num_tx, std::pair{FeeFrac{0, 1}, TestBitSet{}}); - // Construct the corresponding DepGraph object (also no dependencies). - DepGraph depgraph(cluster); - SanityCheck(depgraph); - // Read (parent, child) pairs, and add them to the cluster and depgraph. - LIMITED_WHILE(provider.remaining_bytes() > 0, TestBitSet::Size() * TestBitSet::Size()) { - auto parent = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx - 1); - auto child = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx - 2); - child += (child >= parent); - cluster[child].second.Set(parent); - depgraph.AddDependency(parent, child); - assert(depgraph.Ancestors(child)[parent]); - assert(depgraph.Descendants(parent)[child]); - } - // Sanity check the result. - SanityCheck(depgraph); - // Verify that the resulting DepGraph matches one recomputed from the cluster. - assert(DepGraph(cluster) == depgraph); -} - -FUZZ_TARGET(clusterlin_cluster_serialization) +FUZZ_TARGET(clusterlin_depgraph_sim) { - // Verify that any graph of transactions has its ancestry correctly computed by DepGraph, and - // if it is a DAG, that it can be serialized as a DepGraph in a way that roundtrips. This - // guarantees that any acyclic cluster has a corresponding DepGraph serialization. + // Simulation test to verify the full behavior of DepGraph. FuzzedDataProvider provider(buffer.data(), buffer.size()); - // Construct a cluster in a naive way (using a FuzzedDataProvider-based serialization). - Cluster<TestBitSet> cluster; - auto num_tx = provider.ConsumeIntegralInRange<ClusterIndex>(1, 32); - cluster.resize(num_tx); - for (ClusterIndex i = 0; i < num_tx; ++i) { - cluster[i].first.size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff); - cluster[i].first.fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff); - for (ClusterIndex j = 0; j < num_tx; ++j) { - if (i == j) continue; - if (provider.ConsumeBool()) cluster[i].second.Set(j); + /** Real DepGraph being tested. */ + DepGraph<TestBitSet> real; + /** Simulated DepGraph (sim[i] is std::nullopt if position i does not exist; otherwise, + * sim[i]->first is its individual feerate, and sim[i]->second is its set of ancestors. */ + std::array<std::optional<std::pair<FeeFrac, TestBitSet>>, TestBitSet::Size()> sim; + /** The number of non-nullopt position in sim. */ + ClusterIndex num_tx_sim{0}; + + /** Read a valid index of a transaction from the provider. */ + auto idx_fn = [&]() { + auto offset = provider.ConsumeIntegralInRange<ClusterIndex>(0, num_tx_sim - 1); + for (ClusterIndex i = 0; i < sim.size(); ++i) { + if (!sim[i].has_value()) continue; + if (offset == 0) return i; + --offset; + } + assert(false); + return ClusterIndex(-1); + }; + + /** Read a valid subset of the transactions from the provider. */ + auto subset_fn = [&]() { + auto range = (uint64_t{1} << num_tx_sim) - 1; + const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range); + auto mask_shifted = mask; + TestBitSet subset; + for (ClusterIndex i = 0; i < sim.size(); ++i) { + if (!sim[i].has_value()) continue; + if (mask_shifted & 1) { + subset.Set(i); + } + mask_shifted >>= 1; + } + assert(mask_shifted == 0); + return subset; + }; + + /** Read any set of transactions from the provider (including unused positions). */ + auto set_fn = [&]() { + auto range = (uint64_t{1} << sim.size()) - 1; + const auto mask = provider.ConsumeIntegralInRange<uint64_t>(0, range); + TestBitSet set; + for (ClusterIndex i = 0; i < sim.size(); ++i) { + if ((mask >> i) & 1) { + set.Set(i); + } + } + return set; + }; + + /** Propagate ancestor information in sim. */ + auto anc_update_fn = [&]() { + while (true) { + bool updates{false}; + for (ClusterIndex chl = 0; chl < sim.size(); ++chl) { + if (!sim[chl].has_value()) continue; + for (auto par : sim[chl]->second) { + if (!sim[chl]->second.IsSupersetOf(sim[par]->second)) { + sim[chl]->second |= sim[par]->second; + updates = true; + } + } + } + if (!updates) break; + } + }; + + /** Compare the state of transaction i in the simulation with the real one. */ + auto check_fn = [&](ClusterIndex i) { + // Compare used positions. + assert(real.Positions()[i] == sim[i].has_value()); + if (sim[i].has_value()) { + // Compare feerate. + assert(real.FeeRate(i) == sim[i]->first); + // Compare ancestors (note that SanityCheck verifies correspondence between ancestors + // and descendants, so we can restrict ourselves to ancestors here). + assert(real.Ancestors(i) == sim[i]->second); } + }; + + LIMITED_WHILE(provider.remaining_bytes() > 0, 1000) { + uint8_t command = provider.ConsumeIntegral<uint8_t>(); + if (num_tx_sim == 0 || ((command % 3) <= 0 && num_tx_sim < TestBitSet::Size())) { + // AddTransaction. + auto fee = provider.ConsumeIntegralInRange<int64_t>(-0x8000000000000, 0x7ffffffffffff); + auto size = provider.ConsumeIntegralInRange<int32_t>(1, 0x3fffff); + FeeFrac feerate{fee, size}; + // Apply to DepGraph. + auto idx = real.AddTransaction(feerate); + // Verify that the returned index is correct. + assert(!sim[idx].has_value()); + for (ClusterIndex i = 0; i < TestBitSet::Size(); ++i) { + if (!sim[i].has_value()) { + assert(idx == i); + break; + } + } + // Update sim. + sim[idx] = {feerate, TestBitSet::Singleton(idx)}; + ++num_tx_sim; + continue; + } + if ((command % 3) <= 1 && num_tx_sim > 0) { + // AddDependencies. + ClusterIndex child = idx_fn(); + auto parents = subset_fn(); + // Apply to DepGraph. + real.AddDependencies(parents, child); + // Apply to sim. + sim[child]->second |= parents; + continue; + } + if (num_tx_sim > 0) { + // Remove transactions. + auto del = set_fn(); + // Propagate all ancestry information before deleting anything in the simulation (as + // intermediary transactions may be deleted which impact connectivity). + anc_update_fn(); + // Compare the state of the transactions being deleted. + for (auto i : del) check_fn(i); + // Apply to DepGraph. + real.RemoveTransactions(del); + // Apply to sim. + for (ClusterIndex i = 0; i < sim.size(); ++i) { + if (sim[i].has_value()) { + if (del[i]) { + --num_tx_sim; + sim[i] = std::nullopt; + } else { + sim[i]->second -= del; + } + } + } + continue; + } + // This should be unreachable (one of the 3 above actions should always be possible). + assert(false); } - // Construct dependency graph, and verify it matches the cluster (which includes a round-trip - // check for the serialization). - DepGraph depgraph(cluster); - VerifyDepGraphFromCluster(cluster, depgraph); + // Compare the real obtained depgraph against the simulation. + anc_update_fn(); + for (ClusterIndex i = 0; i < sim.size(); ++i) check_fn(i); + assert(real.TxCount() == num_tx_sim); + // Sanity check the result (which includes round-tripping serialization, if applicable). + SanityCheck(real); } FUZZ_TARGET(clusterlin_depgraph_serialization) @@ -305,7 +421,7 @@ FUZZ_TARGET(clusterlin_components) reader >> Using<DepGraphFormatter>(depgraph); } catch (const std::ios_base::failure&) {} - TestBitSet todo = TestBitSet::Fill(depgraph.TxCount()); + TestBitSet todo = depgraph.Positions(); while (todo.Any()) { // Find a connected component inside todo. auto component = depgraph.FindConnectedComponent(todo); @@ -316,7 +432,7 @@ FUZZ_TARGET(clusterlin_components) // If todo is the entire graph, and the entire graph is connected, then the component must // be the entire graph. - if (todo == TestBitSet::Fill(depgraph.TxCount())) { + if (todo == depgraph.Positions()) { assert((component == todo) == depgraph.IsConnected()); } @@ -353,7 +469,7 @@ FUZZ_TARGET(clusterlin_components) reader >> VARINT(subset_bits); } catch (const std::ios_base::failure&) {} TestBitSet subset; - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + for (ClusterIndex i : depgraph.Positions()) { if (todo[i]) { if (subset_bits & 1) subset.Set(i); subset_bits >>= 1; @@ -369,6 +485,20 @@ FUZZ_TARGET(clusterlin_components) assert(depgraph.FindConnectedComponent(todo).None()); } +FUZZ_TARGET(clusterlin_make_connected) +{ + // Verify that MakeConnected makes graphs connected. + + SpanReader reader(buffer); + DepGraph<TestBitSet> depgraph; + try { + reader >> Using<DepGraphFormatter>(depgraph); + } catch (const std::ios_base::failure&) {} + MakeConnected(depgraph); + SanityCheck(depgraph); + assert(depgraph.IsConnected()); +} + FUZZ_TARGET(clusterlin_chunking) { // Verify the correctness of the ChunkLinearization function. @@ -392,13 +522,13 @@ FUZZ_TARGET(clusterlin_chunking) } // Naively recompute the chunks (each is the highest-feerate prefix of what remains). - auto todo = TestBitSet::Fill(depgraph.TxCount()); + auto todo = depgraph.Positions(); for (const auto& chunk_feerate : chunking) { assert(todo.Any()); SetInfo<TestBitSet> accumulator, best; for (ClusterIndex idx : linearization) { if (todo[idx]) { - accumulator |= SetInfo(depgraph, idx); + accumulator.Set(depgraph, idx); if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) { best = accumulator; } @@ -423,10 +553,11 @@ FUZZ_TARGET(clusterlin_ancestor_finder) } catch (const std::ios_base::failure&) {} AncestorCandidateFinder anc_finder(depgraph); - auto todo = TestBitSet::Fill(depgraph.TxCount()); + auto todo = depgraph.Positions(); while (todo.Any()) { // Call the ancestor finder's FindCandidateSet for what remains of the graph. assert(!anc_finder.AllDone()); + assert(todo.Count() == anc_finder.NumRemaining()); auto best_anc = anc_finder.FindCandidateSet(); // Sanity check the result. assert(best_anc.transactions.Any()); @@ -458,6 +589,7 @@ FUZZ_TARGET(clusterlin_ancestor_finder) anc_finder.MarkDone(del_set); } assert(anc_finder.AllDone()); + assert(anc_finder.NumRemaining() == 0); } static constexpr auto MAX_SIMPLE_ITERATIONS = 300000; @@ -468,13 +600,17 @@ FUZZ_TARGET(clusterlin_search_finder) // and comparing with the results from SimpleCandidateFinder, ExhaustiveCandidateFinder, and // AncestorCandidateFinder. - // Retrieve an RNG seed and a depgraph from the fuzz input. + // Retrieve an RNG seed, a depgraph, and whether to make it connected, from the fuzz input. SpanReader reader(buffer); DepGraph<TestBitSet> depgraph; uint64_t rng_seed{0}; + uint8_t make_connected{1}; try { - reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed; + reader >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected; } catch (const std::ios_base::failure&) {} + // The most complicated graphs are connected ones (other ones just split up). Optionally force + // the graph to be connected. + if (make_connected) MakeConnected(depgraph); // Instantiate ALL the candidate finders. SearchCandidateFinder src_finder(depgraph, rng_seed); @@ -482,12 +618,13 @@ FUZZ_TARGET(clusterlin_search_finder) ExhaustiveCandidateFinder exh_finder(depgraph); AncestorCandidateFinder anc_finder(depgraph); - auto todo = TestBitSet::Fill(depgraph.TxCount()); + auto todo = depgraph.Positions(); while (todo.Any()) { assert(!src_finder.AllDone()); assert(!smp_finder.AllDone()); assert(!exh_finder.AllDone()); assert(!anc_finder.AllDone()); + assert(anc_finder.NumRemaining() == todo.Count()); // For each iteration, read an iteration count limit from the fuzz input. uint64_t max_iterations = 1; @@ -513,9 +650,17 @@ FUZZ_TARGET(clusterlin_search_finder) assert(found.transactions.IsSupersetOf(depgraph.Ancestors(i) & todo)); } - // At most 2^N-1 iterations can be required: the number of non-empty subsets a graph with N - // transactions has. - assert(iterations_done <= ((uint64_t{1} << todo.Count()) - 1)); + // At most 2^(N-1) iterations can be required: the maximum number of non-empty topological + // subsets a (connected) cluster with N transactions can have. Even when the cluster is no + // longer connected after removing certain transactions, this holds, because the connected + // components are searched separately. + assert(iterations_done <= (uint64_t{1} << (todo.Count() - 1))); + // Additionally, test that no more than sqrt(2^N)+1 iterations are required. This is just + // an empirical bound that seems to hold, without proof. Still, add a test for it so we + // can learn about counterexamples if they exist. + if (iterations_done >= 1 && todo.Count() <= 63) { + Assume((iterations_done - 1) * (iterations_done - 1) <= uint64_t{1} << todo.Count()); + } // Perform quality checks only if SearchCandidateFinder claims an optimal result. if (iterations_done < max_iterations) { @@ -562,6 +707,7 @@ FUZZ_TARGET(clusterlin_search_finder) assert(smp_finder.AllDone()); assert(exh_finder.AllDone()); assert(anc_finder.AllDone()); + assert(anc_finder.NumRemaining() == 0); } FUZZ_TARGET(clusterlin_linearization_chunking) @@ -576,7 +722,7 @@ FUZZ_TARGET(clusterlin_linearization_chunking) } catch (const std::ios_base::failure&) {} // Retrieve a topologically-valid subset of depgraph. - auto todo = TestBitSet::Fill(depgraph.TxCount()); + auto todo = depgraph.Positions(); auto subset = SetInfo(depgraph, ReadTopologicalSet(depgraph, todo, reader)); // Retrieve a valid linearization for depgraph. @@ -621,7 +767,7 @@ FUZZ_TARGET(clusterlin_linearization_chunking) SetInfo<TestBitSet> accumulator, best; for (auto j : linearization) { if (todo[j] && !combined[j]) { - accumulator |= SetInfo(depgraph, j); + accumulator.Set(depgraph, j); if (best.feerate.IsEmpty() || accumulator.feerate > best.feerate) { best = accumulator; } @@ -685,14 +831,19 @@ FUZZ_TARGET(clusterlin_linearize) { // Verify the behavior of Linearize(). - // Retrieve an RNG seed, an iteration count, and a depgraph from the fuzz input. + // Retrieve an RNG seed, an iteration count, a depgraph, and whether to make it connected from + // the fuzz input. SpanReader reader(buffer); DepGraph<TestBitSet> depgraph; uint64_t rng_seed{0}; uint64_t iter_count{0}; + uint8_t make_connected{1}; try { - reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed; + reader >> VARINT(iter_count) >> Using<DepGraphFormatter>(depgraph) >> rng_seed >> make_connected; } catch (const std::ios_base::failure&) {} + // The most complicated graphs are connected ones (other ones just split up). Optionally force + // the graph to be connected. + if (make_connected) MakeConnected(depgraph); // Optionally construct an old linearization for it. std::vector<ClusterIndex> old_linearization; @@ -721,12 +872,24 @@ FUZZ_TARGET(clusterlin_linearize) } // If the iteration count is sufficiently high, an optimal linearization must be found. - // Each linearization step can use up to 2^k iterations, with steps k=1..n. That sum is - // 2 * (2^n - 1) + // Each linearization step can use up to 2^(k-1) iterations, with steps k=1..n. That sum is + // 2^n - 1. const uint64_t n = depgraph.TxCount(); - if (n <= 18 && iter_count > 2U * ((uint64_t{1} << n) - 1U)) { + if (n <= 19 && iter_count > (uint64_t{1} << n)) { assert(optimal); } + // Additionally, if the assumption of sqrt(2^k)+1 iterations per step holds, plus ceil(k/4) + // start-up cost per step, plus ceil(n^2/64) start-up cost overall, we can compute the upper + // bound for a whole linearization (summing for k=1..n) using the Python expression + // [sum((k+3)//4 + int(math.sqrt(2**k)) + 1 for k in range(1, n + 1)) + (n**2 + 63) // 64 for n in range(0, 35)]: + static constexpr uint64_t MAX_OPTIMAL_ITERS[] = { + 0, 4, 8, 12, 18, 26, 37, 51, 70, 97, 133, 182, 251, 346, 480, 666, 927, 1296, 1815, 2545, + 3576, 5031, 7087, 9991, 14094, 19895, 28096, 39690, 56083, 79263, 112041, 158391, 223936, + 316629, 447712 + }; + if (n < std::size(MAX_OPTIMAL_ITERS) && iter_count >= MAX_OPTIMAL_ITERS[n]) { + Assume(optimal); + } // If Linearize claims optimal result, run quality tests. if (optimal) { @@ -742,8 +905,8 @@ FUZZ_TARGET(clusterlin_linearize) // Only for very small clusters, test every topologically-valid permutation. if (depgraph.TxCount() <= 7) { - std::vector<ClusterIndex> perm_linearization(depgraph.TxCount()); - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) perm_linearization[i] = i; + std::vector<ClusterIndex> perm_linearization; + for (ClusterIndex i : depgraph.Positions()) perm_linearization.push_back(i); // Iterate over all valid permutations. do { // Determine whether perm_linearization is topological. @@ -827,30 +990,30 @@ FUZZ_TARGET(clusterlin_postlinearize_tree) // Now construct a new graph, copying the nodes, but leaving only the first parent (even // direction) or the first child (odd direction). DepGraph<TestBitSet> depgraph_tree; - for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { - depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i)); + for (ClusterIndex i = 0; i < depgraph_gen.PositionRange(); ++i) { + if (depgraph_gen.Positions()[i]) { + depgraph_tree.AddTransaction(depgraph_gen.FeeRate(i)); + } else { + // For holes, add a dummy transaction which is deleted below, so that non-hole + // transactions retain their position. + depgraph_tree.AddTransaction(FeeFrac{}); + } } + depgraph_tree.RemoveTransactions(TestBitSet::Fill(depgraph_gen.PositionRange()) - depgraph_gen.Positions()); + if (direction & 1) { for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { - auto children = depgraph_gen.Descendants(i) - TestBitSet::Singleton(i); - // Remove descendants that are children of other descendants. - for (auto j : children) { - if (!children[j]) continue; - children -= depgraph_gen.Descendants(j); - children.Set(j); + auto children = depgraph_gen.GetReducedChildren(i); + if (children.Any()) { + depgraph_tree.AddDependencies(TestBitSet::Singleton(i), children.First()); } - if (children.Any()) depgraph_tree.AddDependency(i, children.First()); } } else { for (ClusterIndex i = 0; i < depgraph_gen.TxCount(); ++i) { - auto parents = depgraph_gen.Ancestors(i) - TestBitSet::Singleton(i); - // Remove ancestors that are parents of other ancestors. - for (auto j : parents) { - if (!parents[j]) continue; - parents -= depgraph_gen.Ancestors(j); - parents.Set(j); + auto parents = depgraph_gen.GetReducedParents(i); + if (parents.Any()) { + depgraph_tree.AddDependencies(TestBitSet::Singleton(parents.First()), i); } - if (parents.Any()) depgraph_tree.AddDependency(parents.First(), i); } } diff --git a/src/test/fuzz/crypto_chacha20poly1305.cpp b/src/test/fuzz/crypto_chacha20poly1305.cpp index 5e62e6f3df..0700ba7fb6 100644 --- a/src/test/fuzz/crypto_chacha20poly1305.cpp +++ b/src/test/fuzz/crypto_chacha20poly1305.cpp @@ -39,7 +39,7 @@ FUZZ_TARGET(crypto_aeadchacha20poly1305) // data). InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>()); - LIMITED_WHILE(provider.ConsumeBool(), 10000) + LIMITED_WHILE(provider.ConsumeBool(), 100) { // Mode: // - Bit 0: whether to use single-plain Encrypt/Decrypt; otherwise use a split at prefix. diff --git a/src/test/fuzz/crypto_common.cpp b/src/test/fuzz/crypto_common.cpp index 8e07dfedb9..5a76d4e1a9 100644 --- a/src/test/fuzz/crypto_common.cpp +++ b/src/test/fuzz/crypto_common.cpp @@ -35,6 +35,10 @@ FUZZ_TARGET(crypto_common) WriteLE64(writele64_arr.data(), random_u64); assert(ReadLE64(writele64_arr.data()) == random_u64); + std::array<uint8_t, 2> writebe16_arr; + WriteBE16(writebe16_arr.data(), random_u16); + assert(ReadBE16(writebe16_arr.data()) == random_u16); + std::array<uint8_t, 4> writebe32_arr; WriteBE32(writebe32_arr.data(), random_u32); assert(ReadBE32(writebe32_arr.data()) == random_u32); diff --git a/src/test/fuzz/integer.cpp b/src/test/fuzz/integer.cpp index e27b2065d5..b9e3154106 100644 --- a/src/test/fuzz/integer.cpp +++ b/src/test/fuzz/integer.cpp @@ -69,7 +69,7 @@ FUZZ_TARGET(integer, .init = initialize_integer) const bool b = fuzzed_data_provider.ConsumeBool(); const Consensus::Params& consensus_params = Params().GetConsensus(); - (void)CheckProofOfWork(u256, u32, consensus_params); + (void)CheckProofOfWorkImpl(u256, u32, consensus_params); if (u64 <= MAX_MONEY) { const uint64_t compressed_money_amount = CompressAmount(u64); assert(u64 == DecompressAmount(compressed_money_amount)); diff --git a/src/test/fuzz/p2p_headers_presync.cpp b/src/test/fuzz/p2p_headers_presync.cpp new file mode 100644 index 0000000000..2670aa8ee4 --- /dev/null +++ b/src/test/fuzz/p2p_headers_presync.cpp @@ -0,0 +1,216 @@ +#include <blockencodings.h> +#include <net.h> +#include <net_processing.h> +#include <netmessagemaker.h> +#include <node/peerman_args.h> +#include <pow.h> +#include <test/fuzz/FuzzedDataProvider.h> +#include <test/fuzz/fuzz.h> +#include <test/fuzz/util.h> +#include <test/util/net.h> +#include <test/util/script.h> +#include <test/util/setup_common.h> +#include <uint256.h> +#include <validation.h> + +namespace { +constexpr uint32_t FUZZ_MAX_HEADERS_RESULTS{16}; + +class HeadersSyncSetup : public TestingSetup +{ + std::vector<CNode*> m_connections; + +public: + HeadersSyncSetup(const ChainType chain_type, TestOpts opts) : TestingSetup(chain_type, opts) + { + PeerManager::Options peerman_opts; + node::ApplyArgsManOptions(*m_node.args, peerman_opts); + peerman_opts.max_headers_result = FUZZ_MAX_HEADERS_RESULTS; + m_node.peerman = PeerManager::make(*m_node.connman, *m_node.addrman, + m_node.banman.get(), *m_node.chainman, + *m_node.mempool, *m_node.warnings, peerman_opts); + + CConnman::Options options; + options.m_msgproc = m_node.peerman.get(); + m_node.connman->Init(options); + } + + void ResetAndInitialize() EXCLUSIVE_LOCKS_REQUIRED(NetEventsInterface::g_msgproc_mutex); + void SendMessage(FuzzedDataProvider& fuzzed_data_provider, CSerializedNetMsg&& msg) + EXCLUSIVE_LOCKS_REQUIRED(NetEventsInterface::g_msgproc_mutex); +}; + +void HeadersSyncSetup::ResetAndInitialize() +{ + m_connections.clear(); + auto& connman = static_cast<ConnmanTestMsg&>(*m_node.connman); + connman.StopNodes(); + + NodeId id{0}; + std::vector<ConnectionType> conn_types = { + ConnectionType::OUTBOUND_FULL_RELAY, + ConnectionType::BLOCK_RELAY, + ConnectionType::INBOUND + }; + + for (auto conn_type : conn_types) { + CAddress addr{}; + m_connections.push_back(new CNode(id++, nullptr, addr, 0, 0, addr, "", conn_type, false)); + CNode& p2p_node = *m_connections.back(); + + connman.Handshake( + /*node=*/p2p_node, + /*successfully_connected=*/true, + /*remote_services=*/ServiceFlags(NODE_NETWORK | NODE_WITNESS), + /*local_services=*/ServiceFlags(NODE_NETWORK | NODE_WITNESS), + /*version=*/PROTOCOL_VERSION, + /*relay_txs=*/true); + + connman.AddTestNode(p2p_node); + } +} + +void HeadersSyncSetup::SendMessage(FuzzedDataProvider& fuzzed_data_provider, CSerializedNetMsg&& msg) +{ + auto& connman = static_cast<ConnmanTestMsg&>(*m_node.connman); + CNode& connection = *PickValue(fuzzed_data_provider, m_connections); + + connman.FlushSendBuffer(connection); + (void)connman.ReceiveMsgFrom(connection, std::move(msg)); + connection.fPauseSend = false; + try { + connman.ProcessMessagesOnce(connection); + } catch (const std::ios_base::failure&) { + } + m_node.peerman->SendMessages(&connection); +} + +CBlockHeader ConsumeHeader(FuzzedDataProvider& fuzzed_data_provider, const uint256& prev_hash, uint32_t prev_nbits) +{ + CBlockHeader header; + header.nNonce = 0; + // Either use the previous difficulty or let the fuzzer choose + header.nBits = fuzzed_data_provider.ConsumeBool() ? + prev_nbits : + fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0x17058EBE, 0x1D00FFFF); + header.nTime = ConsumeTime(fuzzed_data_provider); + header.hashPrevBlock = prev_hash; + header.nVersion = fuzzed_data_provider.ConsumeIntegral<int32_t>(); + return header; +} + +CBlock ConsumeBlock(FuzzedDataProvider& fuzzed_data_provider, const uint256& prev_hash, uint32_t prev_nbits) +{ + auto header = ConsumeHeader(fuzzed_data_provider, prev_hash, prev_nbits); + // In order to reach the headers acceptance logic, the block is + // constructed in a way that will pass the mutation checks. + CBlock block{header}; + CMutableTransaction tx; + tx.vin.resize(1); + tx.vout.resize(1); + tx.vout[0].nValue = 0; + tx.vin[0].scriptSig.resize(2); + block.vtx.push_back(MakeTransactionRef(tx)); + block.hashMerkleRoot = block.vtx[0]->GetHash(); + return block; +} + +void FinalizeHeader(CBlockHeader& header, const ChainstateManager& chainman) +{ + while (!CheckProofOfWork(header.GetHash(), header.nBits, chainman.GetParams().GetConsensus())) { + ++(header.nNonce); + } +} + +// Global setup works for this test as state modification (specifically in the +// block index) would indicate a bug. +HeadersSyncSetup* g_testing_setup; + +void initialize() +{ + static auto setup = MakeNoLogFileContext<HeadersSyncSetup>(ChainType::MAIN, {.extra_args = {"-checkpoints=0"}}); + g_testing_setup = setup.get(); +} +} // namespace + +FUZZ_TARGET(p2p_headers_presync, .init = initialize) +{ + ChainstateManager& chainman = *g_testing_setup->m_node.chainman; + + LOCK(NetEventsInterface::g_msgproc_mutex); + + g_testing_setup->ResetAndInitialize(); + + FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()}; + + CBlockHeader base{chainman.GetParams().GenesisBlock()}; + SetMockTime(base.nTime); + + // The chain is just a single block, so this is equal to 1 + size_t original_index_size{WITH_LOCK(cs_main, return chainman.m_blockman.m_block_index.size())}; + arith_uint256 total_work{WITH_LOCK(cs_main, return chainman.m_best_header->nChainWork)}; + + std::vector<CBlockHeader> all_headers; + + LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 100) + { + auto finalized_block = [&]() { + CBlock block = ConsumeBlock(fuzzed_data_provider, base.GetHash(), base.nBits); + FinalizeHeader(block, chainman); + return block; + }; + + // Send low-work headers, compact blocks, and blocks + CallOneOf( + fuzzed_data_provider, + [&]() NO_THREAD_SAFETY_ANALYSIS { + // Send FUZZ_MAX_HEADERS_RESULTS headers + std::vector<CBlock> headers; + headers.resize(FUZZ_MAX_HEADERS_RESULTS); + for (CBlock& header : headers) { + header = ConsumeHeader(fuzzed_data_provider, base.GetHash(), base.nBits); + FinalizeHeader(header, chainman); + base = header; + } + + all_headers.insert(all_headers.end(), headers.begin(), headers.end()); + + auto headers_msg = NetMsg::Make(NetMsgType::HEADERS, TX_WITH_WITNESS(headers)); + g_testing_setup->SendMessage(fuzzed_data_provider, std::move(headers_msg)); + }, + [&]() NO_THREAD_SAFETY_ANALYSIS { + // Send a compact block + auto block = finalized_block(); + CBlockHeaderAndShortTxIDs cmpct_block{block, fuzzed_data_provider.ConsumeIntegral<uint64_t>()}; + + all_headers.push_back(block); + + auto headers_msg = NetMsg::Make(NetMsgType::CMPCTBLOCK, TX_WITH_WITNESS(cmpct_block)); + g_testing_setup->SendMessage(fuzzed_data_provider, std::move(headers_msg)); + }, + [&]() NO_THREAD_SAFETY_ANALYSIS { + // Send a block + auto block = finalized_block(); + + all_headers.push_back(block); + + auto headers_msg = NetMsg::Make(NetMsgType::BLOCK, TX_WITH_WITNESS(block)); + g_testing_setup->SendMessage(fuzzed_data_provider, std::move(headers_msg)); + }); + } + + // This is a conservative overestimate, as base is only moved forward when sending headers. In theory, + // the longest chain generated by this test is 1600 (FUZZ_MAX_HEADERS_RESULTS * 100) headers. In that case, + // this variable will accurately reflect the chain's total work. + total_work += CalculateClaimedHeadersWork(all_headers); + + // This test should never create a chain with more work than MinimumChainWork. + assert(total_work < chainman.MinimumChainWork()); + + // The headers/blocks sent in this test should never be stored, as the chains don't have the work required + // to meet the anti-DoS work threshold. So, if at any point the block index grew in size, then there's a bug + // in the headers pre-sync logic. + assert(WITH_LOCK(cs_main, return chainman.m_blockman.m_block_index.size()) == original_index_size); + + g_testing_setup->m_node.validation_signals->SyncWithValidationInterfaceQueue(); +} diff --git a/src/test/fuzz/pow.cpp b/src/test/fuzz/pow.cpp index 05cdb740e4..dba999ce4f 100644 --- a/src/test/fuzz/pow.cpp +++ b/src/test/fuzz/pow.cpp @@ -80,7 +80,7 @@ FUZZ_TARGET(pow, .init = initialize_pow) { const std::optional<uint256> hash = ConsumeDeserializable<uint256>(fuzzed_data_provider); if (hash) { - (void)CheckProofOfWork(*hash, fuzzed_data_provider.ConsumeIntegral<unsigned int>(), consensus_params); + (void)CheckProofOfWorkImpl(*hash, fuzzed_data_provider.ConsumeIntegral<unsigned int>(), consensus_params); } } } diff --git a/src/test/fuzz/rpc.cpp b/src/test/fuzz/rpc.cpp index 9122617e46..4db37ab7b7 100644 --- a/src/test/fuzz/rpc.cpp +++ b/src/test/fuzz/rpc.cpp @@ -143,6 +143,7 @@ const std::vector<std::string> RPC_COMMANDS_SAFE_FOR_FUZZING{ "getnetworkhashps", "getnetworkinfo", "getnodeaddresses", + "getorphantxs", "getpeerinfo", "getprioritisedtransactions", "getrawaddrman", diff --git a/src/test/fuzz/script_sign.cpp b/src/test/fuzz/script_sign.cpp index 7725ee699c..9fa5e0b7d8 100644 --- a/src/test/fuzz/script_sign.cpp +++ b/src/test/fuzz/script_sign.cpp @@ -13,6 +13,7 @@ #include <test/fuzz/FuzzedDataProvider.h> #include <test/fuzz/fuzz.h> #include <test/fuzz/util.h> +#include <test/util/transaction_utils.h> #include <util/chaintype.h> #include <util/translation.h> diff --git a/src/test/ipc_test.capnp b/src/test/ipc_test.capnp index 55a3dc2683..46cd08b94a 100644 --- a/src/test/ipc_test.capnp +++ b/src/test/ipc_test.capnp @@ -9,10 +9,15 @@ $Cxx.namespace("gen"); using Proxy = import "/mp/proxy.capnp"; $Proxy.include("test/ipc_test.h"); -$Proxy.includeTypes("ipc/capnp/common-types.h"); +$Proxy.includeTypes("test/ipc_test_types.h"); + +using Mining = import "../ipc/capnp/mining.capnp"; interface FooInterface $Proxy.wrap("FooImplementation") { add @0 (a :Int32, b :Int32) -> (result :Int32); passOutPoint @1 (arg :Data) -> (result :Data); passUniValue @2 (arg :Text) -> (result :Text); + passTransaction @3 (arg :Data) -> (result :Data); + passVectorChar @4 (arg :Data) -> (result :Data); + passBlockState @5 (arg :Mining.BlockValidationState) -> (result :Mining.BlockValidationState); } diff --git a/src/test/ipc_test.cpp b/src/test/ipc_test.cpp index e6de6e3e47..af37434980 100644 --- a/src/test/ipc_test.cpp +++ b/src/test/ipc_test.cpp @@ -12,6 +12,7 @@ #include <test/ipc_test.capnp.proxy.h> #include <test/ipc_test.h> #include <tinyformat.h> +#include <validation.h> #include <future> #include <thread> @@ -61,7 +62,7 @@ void IpcPipeTest() auto connection_client = std::make_unique<mp::Connection>(loop, kj::mv(pipe.ends[0])); auto foo_client = std::make_unique<mp::ProxyClient<gen::FooInterface>>( - connection_client->m_rpc_system.bootstrap(mp::ServerVatId().vat_id).castAs<gen::FooInterface>(), + connection_client->m_rpc_system->bootstrap(mp::ServerVatId().vat_id).castAs<gen::FooInterface>(), connection_client.get(), /* destroy_connection= */ false); foo_promise.set_value(std::move(foo_client)); disconnect_client = [&] { loop.sync([&] { connection_client.reset(); }); }; @@ -88,6 +89,38 @@ void IpcPipeTest() UniValue uni2{foo->passUniValue(uni1)}; BOOST_CHECK_EQUAL(uni1.write(), uni2.write()); + CMutableTransaction mtx; + mtx.version = 2; + mtx.nLockTime = 3; + mtx.vin.emplace_back(txout1); + mtx.vout.emplace_back(COIN, CScript()); + CTransactionRef tx1{MakeTransactionRef(mtx)}; + CTransactionRef tx2{foo->passTransaction(tx1)}; + BOOST_CHECK(*Assert(tx1) == *Assert(tx2)); + + std::vector<char> vec1{'H', 'e', 'l', 'l', 'o'}; + std::vector<char> vec2{foo->passVectorChar(vec1)}; + BOOST_CHECK_EQUAL(std::string_view(vec1.begin(), vec1.end()), std::string_view(vec2.begin(), vec2.end())); + + BlockValidationState bs1; + bs1.Invalid(BlockValidationResult::BLOCK_CHECKPOINT, "reject reason", "debug message"); + BlockValidationState bs2{foo->passBlockState(bs1)}; + BOOST_CHECK_EQUAL(bs1.IsValid(), bs2.IsValid()); + BOOST_CHECK_EQUAL(bs1.IsError(), bs2.IsError()); + BOOST_CHECK_EQUAL(bs1.IsInvalid(), bs2.IsInvalid()); + BOOST_CHECK_EQUAL(static_cast<int>(bs1.GetResult()), static_cast<int>(bs2.GetResult())); + BOOST_CHECK_EQUAL(bs1.GetRejectReason(), bs2.GetRejectReason()); + BOOST_CHECK_EQUAL(bs1.GetDebugMessage(), bs2.GetDebugMessage()); + + BlockValidationState bs3; + BlockValidationState bs4{foo->passBlockState(bs3)}; + BOOST_CHECK_EQUAL(bs3.IsValid(), bs4.IsValid()); + BOOST_CHECK_EQUAL(bs3.IsError(), bs4.IsError()); + BOOST_CHECK_EQUAL(bs3.IsInvalid(), bs4.IsInvalid()); + BOOST_CHECK_EQUAL(static_cast<int>(bs3.GetResult()), static_cast<int>(bs4.GetResult())); + BOOST_CHECK_EQUAL(bs3.GetRejectReason(), bs4.GetRejectReason()); + BOOST_CHECK_EQUAL(bs3.GetDebugMessage(), bs4.GetDebugMessage()); + // Test cleanup: disconnect pipe and join thread disconnect_client(); thread.join(); diff --git a/src/test/ipc_test.h b/src/test/ipc_test.h index 2453bfa23c..2d215a20f1 100644 --- a/src/test/ipc_test.h +++ b/src/test/ipc_test.h @@ -8,6 +8,7 @@ #include <primitives/transaction.h> #include <univalue.h> #include <util/fs.h> +#include <validation.h> class FooImplementation { @@ -15,6 +16,9 @@ public: int add(int a, int b) { return a + b; } COutPoint passOutPoint(COutPoint o) { return o; } UniValue passUniValue(UniValue v) { return v; } + CTransactionRef passTransaction(CTransactionRef t) { return t; } + std::vector<char> passVectorChar(std::vector<char> v) { return v; } + BlockValidationState passBlockState(BlockValidationState s) { return s; } }; void IpcPipeTest(); diff --git a/src/test/ipc_test_types.h b/src/test/ipc_test_types.h new file mode 100644 index 0000000000..b1d4829aa7 --- /dev/null +++ b/src/test/ipc_test_types.h @@ -0,0 +1,12 @@ +// Copyright (c) 2024 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_TEST_IPC_TEST_TYPES_H +#define BITCOIN_TEST_IPC_TEST_TYPES_H + +#include <ipc/capnp/common-types.h> +#include <ipc/capnp/mining-types.h> +#include <test/ipc_test.capnp.h> + +#endif // BITCOIN_TEST_IPC_TEST_TYPES_H diff --git a/src/test/logging_tests.cpp b/src/test/logging_tests.cpp index a6fd44e395..77ec81e597 100644 --- a/src/test/logging_tests.cpp +++ b/src/test/logging_tests.cpp @@ -83,15 +83,15 @@ BOOST_AUTO_TEST_CASE(logging_timer) BOOST_CHECK_EQUAL(micro_timer.LogMsg("msg").substr(0, result_prefix.size()), result_prefix); } -BOOST_FIXTURE_TEST_CASE(logging_LogPrintf_, LogSetup) +BOOST_FIXTURE_TEST_CASE(logging_LogPrintStr, LogSetup) { LogInstance().m_log_sourcelocations = true; - LogPrintf_("fn1", "src1", 1, BCLog::LogFlags::NET, BCLog::Level::Debug, "foo1: %s\n", "bar1"); - LogPrintf_("fn2", "src2", 2, BCLog::LogFlags::NET, BCLog::Level::Info, "foo2: %s\n", "bar2"); - LogPrintf_("fn3", "src3", 3, BCLog::LogFlags::ALL, BCLog::Level::Debug, "foo3: %s\n", "bar3"); - LogPrintf_("fn4", "src4", 4, BCLog::LogFlags::ALL, BCLog::Level::Info, "foo4: %s\n", "bar4"); - LogPrintf_("fn5", "src5", 5, BCLog::LogFlags::NONE, BCLog::Level::Debug, "foo5: %s\n", "bar5"); - LogPrintf_("fn6", "src6", 6, BCLog::LogFlags::NONE, BCLog::Level::Info, "foo6: %s\n", "bar6"); + LogInstance().LogPrintStr("foo1: bar1", "fn1", "src1", 1, BCLog::LogFlags::NET, BCLog::Level::Debug); + LogInstance().LogPrintStr("foo2: bar2", "fn2", "src2", 2, BCLog::LogFlags::NET, BCLog::Level::Info); + LogInstance().LogPrintStr("foo3: bar3", "fn3", "src3", 3, BCLog::LogFlags::ALL, BCLog::Level::Debug); + LogInstance().LogPrintStr("foo4: bar4", "fn4", "src4", 4, BCLog::LogFlags::ALL, BCLog::Level::Info); + LogInstance().LogPrintStr("foo5: bar5", "fn5", "src5", 5, BCLog::LogFlags::NONE, BCLog::Level::Debug); + LogInstance().LogPrintStr("foo6: bar6", "fn6", "src6", 6, BCLog::LogFlags::NONE, BCLog::Level::Info); std::ifstream file{tmp_log_path}; std::vector<std::string> log_lines; for (std::string log; std::getline(file, log);) { @@ -133,11 +133,11 @@ BOOST_FIXTURE_TEST_CASE(logging_LogPrintMacrosDeprecated, LogSetup) BOOST_FIXTURE_TEST_CASE(logging_LogPrintMacros, LogSetup) { - LogTrace(BCLog::NET, "foo6: %s\n", "bar6"); // not logged - LogDebug(BCLog::NET, "foo7: %s\n", "bar7"); - LogInfo("foo8: %s\n", "bar8"); - LogWarning("foo9: %s\n", "bar9"); - LogError("foo10: %s\n", "bar10"); + LogTrace(BCLog::NET, "foo6: %s", "bar6"); // not logged + LogDebug(BCLog::NET, "foo7: %s", "bar7"); + LogInfo("foo8: %s", "bar8"); + LogWarning("foo9: %s", "bar9"); + LogError("foo10: %s", "bar10"); std::ifstream file{tmp_log_path}; std::vector<std::string> log_lines; for (std::string log; std::getline(file, log);) { diff --git a/src/test/merkle_tests.cpp b/src/test/merkle_tests.cpp index 70308cb29a..2b1cf8595d 100644 --- a/src/test/merkle_tests.cpp +++ b/src/test/merkle_tests.cpp @@ -23,110 +23,6 @@ static uint256 ComputeMerkleRootFromBranch(const uint256& leaf, const std::vecto return hash; } -/* This implements a constant-space merkle root/path calculator, limited to 2^32 leaves. */ -static void MerkleComputation(const std::vector<uint256>& leaves, uint256* proot, bool* pmutated, uint32_t branchpos, std::vector<uint256>* pbranch) { - if (pbranch) pbranch->clear(); - if (leaves.size() == 0) { - if (pmutated) *pmutated = false; - if (proot) *proot = uint256(); - return; - } - bool mutated = false; - // count is the number of leaves processed so far. - uint32_t count = 0; - // inner is an array of eagerly computed subtree hashes, indexed by tree - // level (0 being the leaves). - // For example, when count is 25 (11001 in binary), inner[4] is the hash of - // the first 16 leaves, inner[3] of the next 8 leaves, and inner[0] equal to - // the last leaf. The other inner entries are undefined. - uint256 inner[32]; - // Which position in inner is a hash that depends on the matching leaf. - int matchlevel = -1; - // First process all leaves into 'inner' values. - while (count < leaves.size()) { - uint256 h = leaves[count]; - bool matchh = count == branchpos; - count++; - int level; - // For each of the lower bits in count that are 0, do 1 step. Each - // corresponds to an inner value that existed before processing the - // current leaf, and each needs a hash to combine it. - for (level = 0; !(count & ((uint32_t{1}) << level)); level++) { - if (pbranch) { - if (matchh) { - pbranch->push_back(inner[level]); - } else if (matchlevel == level) { - pbranch->push_back(h); - matchh = true; - } - } - mutated |= (inner[level] == h); - h = Hash(inner[level], h); - } - // Store the resulting hash at inner position level. - inner[level] = h; - if (matchh) { - matchlevel = level; - } - } - // Do a final 'sweep' over the rightmost branch of the tree to process - // odd levels, and reduce everything to a single top value. - // Level is the level (counted from the bottom) up to which we've sweeped. - int level = 0; - // As long as bit number level in count is zero, skip it. It means there - // is nothing left at this level. - while (!(count & ((uint32_t{1}) << level))) { - level++; - } - uint256 h = inner[level]; - bool matchh = matchlevel == level; - while (count != ((uint32_t{1}) << level)) { - // If we reach this point, h is an inner value that is not the top. - // We combine it with itself (Bitcoin's special rule for odd levels in - // the tree) to produce a higher level one. - if (pbranch && matchh) { - pbranch->push_back(h); - } - h = Hash(h, h); - // Increment count to the value it would have if two entries at this - // level had existed. - count += ((uint32_t{1}) << level); - level++; - // And propagate the result upwards accordingly. - while (!(count & ((uint32_t{1}) << level))) { - if (pbranch) { - if (matchh) { - pbranch->push_back(inner[level]); - } else if (matchlevel == level) { - pbranch->push_back(h); - matchh = true; - } - } - h = Hash(inner[level], h); - level++; - } - } - // Return result. - if (pmutated) *pmutated = mutated; - if (proot) *proot = h; -} - -static std::vector<uint256> ComputeMerkleBranch(const std::vector<uint256>& leaves, uint32_t position) { - std::vector<uint256> ret; - MerkleComputation(leaves, nullptr, nullptr, position, &ret); - return ret; -} - -static std::vector<uint256> BlockMerkleBranch(const CBlock& block, uint32_t position) -{ - std::vector<uint256> leaves; - leaves.resize(block.vtx.size()); - for (size_t s = 0; s < block.vtx.size(); s++) { - leaves[s] = block.vtx[s]->GetHash(); - } - return ComputeMerkleBranch(leaves, position); -} - // Older version of the merkle root computation code, for comparison. static uint256 BlockBuildMerkleTree(const CBlock& block, bool* fMutated, std::vector<uint256>& vMerkleTree) { diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp index 9f35690460..6cf2757b2d 100644 --- a/src/test/miner_tests.cpp +++ b/src/test/miner_tests.cpp @@ -608,7 +608,7 @@ void MinerTestingSetup::TestPrioritisedMining(const CScript& scriptPubKey, const BOOST_AUTO_TEST_CASE(CreateNewBlock_validity) { // Note that by default, these tests run with size accounting enabled. - CScript scriptPubKey = CScript() << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"_hex_v_u8 << OP_CHECKSIG; + CScript scriptPubKey = CScript() << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"_hex << OP_CHECKSIG; std::unique_ptr<CBlockTemplate> pblocktemplate; CTxMemPool& tx_mempool{*m_node.mempool}; diff --git a/src/test/multisig_tests.cpp b/src/test/multisig_tests.cpp index 7a3e8e3a47..29a73d03d2 100644 --- a/src/test/multisig_tests.cpp +++ b/src/test/multisig_tests.cpp @@ -10,6 +10,7 @@ #include <script/sign.h> #include <script/signingprovider.h> #include <test/util/setup_common.h> +#include <test/util/transaction_utils.h> #include <tinyformat.h> #include <uint256.h> diff --git a/src/test/script_p2sh_tests.cpp b/src/test/script_p2sh_tests.cpp index f91203cc48..096de0724f 100644 --- a/src/test/script_p2sh_tests.cpp +++ b/src/test/script_p2sh_tests.cpp @@ -11,6 +11,7 @@ #include <script/sign.h> #include <script/signingprovider.h> #include <test/util/setup_common.h> +#include <test/util/transaction_utils.h> #include <validation.h> #include <vector> diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp index 0e2a1631ce..59eb90bd27 100644 --- a/src/test/script_tests.cpp +++ b/src/test/script_tests.cpp @@ -123,7 +123,6 @@ void DoTest(const CScript& scriptPubKey, const CScript& scriptSig, const CScript ScriptError err; const CTransaction txCredit{BuildCreditingTransaction(scriptPubKey, nValue)}; CMutableTransaction tx = BuildSpendingTransaction(scriptSig, scriptWitness, txCredit); - CMutableTransaction tx2 = tx; BOOST_CHECK_MESSAGE(VerifyScript(scriptSig, scriptPubKey, &scriptWitness, flags, MutableTransactionSignatureChecker(&tx, 0, txCredit.vout[0].nValue, MissingDataBehavior::ASSERT_FAIL), &err) == expect, message); BOOST_CHECK_MESSAGE(err == scriptError, FormatScriptError(err) + " where " + FormatScriptError((ScriptError_t)scriptError) + " expected: " + message); @@ -1368,6 +1367,13 @@ static CScript ScriptFromHex(const std::string& str) return ToScript(*Assert(TryParseHex(str))); } +BOOST_AUTO_TEST_CASE(script_byte_array_u8_vector_equivalence) +{ + const CScript scriptPubKey1 = CScript() << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"_hex_v_u8 << OP_CHECKSIG; + const CScript scriptPubKey2 = CScript() << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f"_hex << OP_CHECKSIG; + BOOST_CHECK(scriptPubKey1 == scriptPubKey2); +} + BOOST_AUTO_TEST_CASE(script_FindAndDelete) { // Exercise the FindAndDelete functionality @@ -1421,7 +1427,7 @@ BOOST_AUTO_TEST_CASE(script_FindAndDelete) // prefix, leaving 02ff03 which is push-two-bytes: s = ToScript("0302ff030302ff03"_hex); d = ToScript("03"_hex); - expect = CScript() << "ff03"_hex_v_u8 << "ff03"_hex_v_u8; + expect = CScript() << "ff03"_hex << "ff03"_hex; BOOST_CHECK_EQUAL(FindAndDelete(s, d), 2); BOOST_CHECK(s == expect); diff --git a/src/test/streams_tests.cpp b/src/test/streams_tests.cpp index 9217f05945..777122df6d 100644 --- a/src/test/streams_tests.cpp +++ b/src/test/streams_tests.cpp @@ -261,7 +261,7 @@ BOOST_AUTO_TEST_CASE(streams_buffered_file) for (uint8_t j = 0; j < 40; ++j) { file << j; } - std::rewind(file.Get()); + file.seek(0, SEEK_SET); // The buffer size (second arg) must be greater than the rewind // amount (third arg). @@ -391,7 +391,7 @@ BOOST_AUTO_TEST_CASE(streams_buffered_file_skip) for (uint8_t j = 0; j < 40; ++j) { file << j; } - std::rewind(file.Get()); + file.seek(0, SEEK_SET); // The buffer is 25 bytes, allow rewinding 10 bytes. BufferedFile bf{file, 25, 10}; @@ -444,7 +444,7 @@ BOOST_AUTO_TEST_CASE(streams_buffered_file_rand) for (uint8_t i = 0; i < fileSize; ++i) { file << i; } - std::rewind(file.Get()); + file.seek(0, SEEK_SET); size_t bufSize = m_rng.randrange(300) + 1; size_t rewindSize = m_rng.randrange(bufSize); diff --git a/src/test/system_tests.cpp b/src/test/system_tests.cpp index bf50a61327..a5d9be07d5 100644 --- a/src/test/system_tests.cpp +++ b/src/test/system_tests.cpp @@ -3,7 +3,7 @@ // file COPYING or http://www.opensource.org/licenses/mit-license.php. // -#include <config/bitcoin-config.h> // IWYU pragma: keep +#include <bitcoin-build-config.h> // IWYU pragma: keep #include <test/util/setup_common.h> #include <common/run_command.h> #include <univalue.h> @@ -47,7 +47,7 @@ BOOST_AUTO_TEST_CASE(run_command) } { // Return non-zero exit code, with error message for stderr - const std::string command{"python3 -c 'import sys; print(\"err\", file=sys.stderr); sys.exit(2)'"}; + const std::string command{"sh -c 'echo err 1>&2 && false'"}; const std::string expected{"err"}; BOOST_CHECK_EXCEPTION(RunCommandParseJSON(command), std::runtime_error, [&](const std::runtime_error& e) { const std::string what(e.what()); diff --git a/src/test/transaction_tests.cpp b/src/test/transaction_tests.cpp index 462abd5222..3430a5bbfa 100644 --- a/src/test/transaction_tests.cpp +++ b/src/test/transaction_tests.cpp @@ -852,24 +852,24 @@ BOOST_AUTO_TEST_CASE(test_IsStandard) CheckIsNotStandard(t, "scriptpubkey"); // MAX_OP_RETURN_RELAY-byte TxoutType::NULL_DATA (standard) - t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef3804678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex_v_u8; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef3804678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex; BOOST_CHECK_EQUAL(MAX_OP_RETURN_RELAY, t.vout[0].scriptPubKey.size()); CheckIsStandard(t); // MAX_OP_RETURN_RELAY+1-byte TxoutType::NULL_DATA (non-standard) - t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef3804678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef3800"_hex_v_u8; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef3804678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef3800"_hex; BOOST_CHECK_EQUAL(MAX_OP_RETURN_RELAY + 1, t.vout[0].scriptPubKey.size()); CheckIsNotStandard(t, "scriptpubkey"); // Data payload can be encoded in any way... - t.vout[0].scriptPubKey = CScript() << OP_RETURN << ""_hex_v_u8; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << ""_hex; CheckIsStandard(t); - t.vout[0].scriptPubKey = CScript() << OP_RETURN << "00"_hex_v_u8 << "01"_hex_v_u8; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << "00"_hex << "01"_hex; CheckIsStandard(t); // OP_RESERVED *is* considered to be a PUSHDATA type opcode by IsPushOnly()! - t.vout[0].scriptPubKey = CScript() << OP_RETURN << OP_RESERVED << -1 << 0 << "01"_hex_v_u8 << 2 << 3 << 4 << 5 << 6 << 7 << 8 << 9 << 10 << 11 << 12 << 13 << 14 << 15 << 16; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << OP_RESERVED << -1 << 0 << "01"_hex << 2 << 3 << 4 << 5 << 6 << 7 << 8 << 9 << 10 << 11 << 12 << 13 << 14 << 15 << 16; CheckIsStandard(t); - t.vout[0].scriptPubKey = CScript() << OP_RETURN << 0 << "01"_hex_v_u8 << 2 << "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"_hex_v_u8; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << 0 << "01"_hex << 2 << "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"_hex; CheckIsStandard(t); // ...so long as it only contains PUSHDATA's @@ -883,13 +883,13 @@ BOOST_AUTO_TEST_CASE(test_IsStandard) // Only one TxoutType::NULL_DATA permitted in all cases t.vout.resize(2); - t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex_v_u8; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex; t.vout[0].nValue = 0; - t.vout[1].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex_v_u8; + t.vout[1].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex; t.vout[1].nValue = 0; CheckIsNotStandard(t, "multi-op-return"); - t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex_v_u8; + t.vout[0].scriptPubKey = CScript() << OP_RETURN << "04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38"_hex; t.vout[1].scriptPubKey = CScript() << OP_RETURN; CheckIsNotStandard(t, "multi-op-return"); diff --git a/src/test/txindex_tests.cpp b/src/test/txindex_tests.cpp index 5a32b02ad9..9ee5387830 100644 --- a/src/test/txindex_tests.cpp +++ b/src/test/txindex_tests.cpp @@ -33,7 +33,7 @@ BOOST_FIXTURE_TEST_CASE(txindex_initial_sync, TestChain100Setup) BOOST_REQUIRE(txindex.StartBackgroundSync()); // Allow tx index to catch up with the block index. - IndexWaitSynced(txindex, *Assert(m_node.shutdown)); + IndexWaitSynced(txindex, *Assert(m_node.shutdown_signal)); // Check that txindex excludes genesis block transactions. const CBlock& genesis_block = Params().GenesisBlock(); diff --git a/src/test/util/cluster_linearize.h b/src/test/util/cluster_linearize.h index 9477d2ed41..871aa9d74e 100644 --- a/src/test/util/cluster_linearize.h +++ b/src/test/util/cluster_linearize.h @@ -27,7 +27,7 @@ using TestBitSet = BitSet<32>; template<typename SetType> bool IsAcyclic(const DepGraph<SetType>& depgraph) noexcept { - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + for (ClusterIndex i : depgraph.Positions()) { if ((depgraph.Ancestors(i) & depgraph.Descendants(i)) != SetType::Singleton(i)) { return false; } @@ -57,11 +57,14 @@ bool IsAcyclic(const DepGraph<SetType>& depgraph) noexcept * by parent relations that were serialized before it). * - The various insertion positions in the cluster, from the very end of the cluster, to the * front. + * - The appending of 1, 2, 3, ... holes at the end of the cluster, followed by appending the new + * transaction. * - * Let's say you have a 7-transaction cluster, consisting of transactions F,A,C,B,G,E,D, but - * serialized in order A,B,C,D,E,F,G, because that happens to be a topological ordering. By the - * time G gets serialized, what has been serialized already represents the cluster F,A,C,B,E,D (in - * that order). G has B and E as direct parents, and E depends on C. + * Let's say you have a 7-transaction cluster, consisting of transactions F,A,C,B,_,G,E,_,D + * (where _ represent holes; unused positions within the DepGraph) but serialized in order + * A,B,C,D,E,F,G, because that happens to be a topological ordering. By the time G gets serialized, + * what has been serialized already represents the cluster F,A,C,B,_,E,_,D (in that order). G has B + * and E as direct parents, and E depends on C. * * In this case, the possibilities are, in order: * - [ ] the dependency G->F @@ -71,17 +74,23 @@ bool IsAcyclic(const DepGraph<SetType>& depgraph) noexcept * - [ ] the dependency G->A * - [ ] put G at the end of the cluster * - [ ] put G before D + * - [ ] put G before the hole before D * - [X] put G before E + * - [ ] put G before the hole before E * - [ ] put G before B * - [ ] put G before C * - [ ] put G before A * - [ ] put G before F + * - [ ] add 1 hole at the end of the cluster, followed by G + * - [ ] add 2 holes at the end of the cluster, followed by G + * - [ ] add ... * - * The skip values in this case are 1 (G->F), 1 (G->D), 3 (G->A, G at end, G before D). No skip - * after 3 is needed (or permitted), because there can only be one position for G. Also note that - * G->C is not included in the list of possibilities, as it is implied by the included G->E and - * E->C that came before it. On deserialization, if the last skip value was 8 or larger (putting - * G before the beginning of the cluster), it is interpreted as wrapping around back to the end. + * The skip values in this case are 1 (G->F), 1 (G->D), 4 (G->A, G at end, G before D, G before + * hole). No skip after 4 is needed (or permitted), because there can only be one position for G. + * Also note that G->C is not included in the list of possibilities, as it is implied by the + * included G->E and E->C that came before it. On deserialization, if the last skip value was 8 or + * larger (putting G before the beginning of the cluster), it is interpreted as wrapping around + * back to the end. * * * Rationale: @@ -102,7 +111,7 @@ bool IsAcyclic(const DepGraph<SetType>& depgraph) noexcept struct DepGraphFormatter { /** Convert x>=0 to 2x (even), x<0 to -2x-1 (odd). */ - static uint64_t SignedToUnsigned(int64_t x) noexcept + [[maybe_unused]] static uint64_t SignedToUnsigned(int64_t x) noexcept { if (x < 0) { return 2 * uint64_t(-(x + 1)) + 1; @@ -112,7 +121,7 @@ struct DepGraphFormatter } /** Convert even x to x/2 (>=0), odd x to -(x/2)-1 (<0). */ - static int64_t UnsignedToSigned(uint64_t x) noexcept + [[maybe_unused]] static int64_t UnsignedToSigned(uint64_t x) noexcept { if (x & 1) { return -int64_t(x / 2) - 1; @@ -125,18 +134,18 @@ struct DepGraphFormatter static void Ser(Stream& s, const DepGraph<SetType>& depgraph) { /** Construct a topological order to serialize the transactions in. */ - std::vector<ClusterIndex> topo_order(depgraph.TxCount()); - std::iota(topo_order.begin(), topo_order.end(), ClusterIndex{0}); + std::vector<ClusterIndex> topo_order; + topo_order.reserve(depgraph.TxCount()); + for (auto i : depgraph.Positions()) topo_order.push_back(i); std::sort(topo_order.begin(), topo_order.end(), [&](ClusterIndex a, ClusterIndex b) { auto anc_a = depgraph.Ancestors(a).Count(), anc_b = depgraph.Ancestors(b).Count(); if (anc_a != anc_b) return anc_a < anc_b; return a < b; }); - /** Which transactions the deserializer already knows when it has deserialized what has - * been serialized here so far, and in what order. */ - std::vector<ClusterIndex> rebuilt_order; - rebuilt_order.reserve(depgraph.TxCount()); + /** Which positions (incl. holes) the deserializer already knows when it has deserialized + * what has been serialized here so far. */ + SetType done; // Loop over the transactions in topological order. for (ClusterIndex topo_idx = 0; topo_idx < topo_order.size(); ++topo_idx) { @@ -166,14 +175,20 @@ struct DepGraphFormatter } } // Write position information. - ClusterIndex insert_distance = 0; - while (insert_distance < rebuilt_order.size()) { - // Loop to find how far from the end in rebuilt_order to insert. - if (idx > *(rebuilt_order.end() - 1 - insert_distance)) break; - ++insert_distance; + auto add_holes = SetType::Fill(idx) - done - depgraph.Positions(); + if (add_holes.None()) { + // The new transaction is to be inserted N positions back from the end of the + // cluster. Emit N to indicate that that many insertion choices are skipped. + auto skips = (done - SetType::Fill(idx)).Count(); + s << VARINT(diff + skips); + } else { + // The new transaction is to be appended at the end of the cluster, after N holes. + // Emit current_cluster_size + N, to indicate all insertion choices are skipped, + // plus N possibilities for the number of holes. + s << VARINT(diff + done.Count() + add_holes.Count()); + done |= add_holes; } - rebuilt_order.insert(rebuilt_order.end() - insert_distance, idx); - s << VARINT(diff + insert_distance); + done.Set(idx); } // Output a final 0 to denote the end of the graph. @@ -186,13 +201,19 @@ struct DepGraphFormatter /** The dependency graph which we deserialize into first, with transactions in * topological serialization order, not original cluster order. */ DepGraph<SetType> topo_depgraph; - /** Mapping from cluster order to serialization order, used later to reconstruct the + /** Mapping from serialization order to cluster order, used later to reconstruct the * cluster order. */ std::vector<ClusterIndex> reordering; + /** How big the entries vector in the reconstructed depgraph will be (including holes). */ + ClusterIndex total_size{0}; // Read transactions in topological order. - try { - while (true) { + while (true) { + FeeFrac new_feerate; //!< The new transaction's fee and size. + SetType new_ancestors; //!< The new transaction's ancestors (excluding itself). + uint64_t diff{0}; //!< How many potential parents/insertions we have to skip. + bool read_error{false}; + try { // Read size. Size 0 signifies the end of the DepGraph. int32_t size; s >> VARINT_MODE(size, VarIntMode::NONNEGATIVE_SIGNED); @@ -204,21 +225,18 @@ struct DepGraphFormatter s >> VARINT(coded_fee); coded_fee &= 0xFFFFFFFFFFFFF; // Enough for fee between -21M...21M BTC. static_assert(0xFFFFFFFFFFFFF > uint64_t{2} * 21000000 * 100000000); - auto fee = UnsignedToSigned(coded_fee); - // Extend topo_depgraph with the new transaction (at the end). - auto topo_idx = topo_depgraph.AddTransaction({fee, size}); - reordering.push_back(topo_idx); + new_feerate = {UnsignedToSigned(coded_fee), size}; // Read dependency information. - uint64_t diff = 0; //!< How many potential parents we have to skip. + auto topo_idx = reordering.size(); s >> VARINT(diff); for (ClusterIndex dep_dist = 0; dep_dist < topo_idx; ++dep_dist) { /** Which topo_depgraph index we are currently considering as parent of topo_idx. */ ClusterIndex dep_topo_idx = topo_idx - 1 - dep_dist; // Ignore transactions which are already known ancestors of topo_idx. - if (topo_depgraph.Descendants(dep_topo_idx)[topo_idx]) continue; + if (new_ancestors[dep_topo_idx]) continue; if (diff == 0) { // When the skip counter has reached 0, add an actual dependency. - topo_depgraph.AddDependency(dep_topo_idx, topo_idx); + new_ancestors |= topo_depgraph.Ancestors(dep_topo_idx); // And read the number of skips after it. s >> VARINT(diff); } else { @@ -226,31 +244,52 @@ struct DepGraphFormatter --diff; } } - // If we reach this point, we can interpret the remaining skip value as how far from the - // end of reordering topo_idx should be placed (wrapping around), so move it to its - // correct location. The preliminary reordering.push_back(topo_idx) above was to make - // sure that if a deserialization exception occurs, topo_idx still appears somewhere. - reordering.pop_back(); - reordering.insert(reordering.end() - (diff % (reordering.size() + 1)), topo_idx); + } catch (const std::ios_base::failure&) { + // Continue even if a read error was encountered. + read_error = true; } - } catch (const std::ios_base::failure&) {} - - // Construct the original cluster order depgraph. - depgraph = {}; - // Add transactions to depgraph in the original cluster order. - for (auto topo_idx : reordering) { - depgraph.AddTransaction(topo_depgraph.FeeRate(topo_idx)); - } - // Translate dependencies from topological to cluster order. - for (ClusterIndex idx = 0; idx < reordering.size(); ++idx) { - ClusterIndex topo_idx = reordering[idx]; - for (ClusterIndex dep_idx = 0; dep_idx < reordering.size(); ++dep_idx) { - ClusterIndex dep_topo_idx = reordering[dep_idx]; - if (topo_depgraph.Ancestors(topo_idx)[dep_topo_idx]) { - depgraph.AddDependency(dep_idx, idx); + // Construct a new transaction whenever we made it past the new_feerate construction. + if (new_feerate.IsEmpty()) break; + assert(reordering.size() < SetType::Size()); + auto topo_idx = topo_depgraph.AddTransaction(new_feerate); + topo_depgraph.AddDependencies(new_ancestors, topo_idx); + if (total_size < SetType::Size()) { + // Normal case. + diff %= SetType::Size(); + if (diff <= total_size) { + // Insert the new transaction at distance diff back from the end. + for (auto& pos : reordering) { + pos += (pos >= total_size - diff); + } + reordering.push_back(total_size++ - diff); + } else { + // Append diff - total_size holes at the end, plus the new transaction. + total_size = diff; + reordering.push_back(total_size++); + } + } else { + // In case total_size == SetType::Size, it is not possible to insert the new + // transaction without exceeding SetType's size. Instead, interpret diff as an + // index into the holes, and overwrite a position there. This branch is never used + // when deserializing the output of the serializer, but gives meaning to otherwise + // invalid input. + diff %= (SetType::Size() - reordering.size()); + SetType holes = SetType::Fill(SetType::Size()); + for (auto pos : reordering) holes.Reset(pos); + for (auto pos : holes) { + if (diff == 0) { + reordering.push_back(pos); + break; + } + --diff; } } + // Stop if a read error was encountered during deserialization. + if (read_error) break; } + + // Construct the original cluster order depgraph. + depgraph = DepGraph(topo_depgraph, reordering, total_size); } }; @@ -258,8 +297,19 @@ struct DepGraphFormatter template<typename SetType> void SanityCheck(const DepGraph<SetType>& depgraph) { + // Verify Positions and PositionRange consistency. + ClusterIndex num_positions{0}; + ClusterIndex position_range{0}; + for (ClusterIndex i : depgraph.Positions()) { + ++num_positions; + position_range = i + 1; + } + assert(num_positions == depgraph.TxCount()); + assert(position_range == depgraph.PositionRange()); + assert(position_range >= num_positions); + assert(position_range <= SetType::Size()); // Consistency check between ancestors internally. - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + for (ClusterIndex i : depgraph.Positions()) { // Transactions include themselves as ancestors. assert(depgraph.Ancestors(i)[i]); // If a is an ancestor of b, then b's ancestors must include all of a's ancestors. @@ -268,13 +318,27 @@ void SanityCheck(const DepGraph<SetType>& depgraph) } } // Consistency check between ancestors and descendants. - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { - for (ClusterIndex j = 0; j < depgraph.TxCount(); ++j) { + for (ClusterIndex i : depgraph.Positions()) { + for (ClusterIndex j : depgraph.Positions()) { assert(depgraph.Ancestors(i)[j] == depgraph.Descendants(j)[i]); } + // No transaction is a parent or child of itself. + auto parents = depgraph.GetReducedParents(i); + auto children = depgraph.GetReducedChildren(i); + assert(!parents[i]); + assert(!children[i]); + // Parents of a transaction do not have ancestors inside those parents (except itself). + // Note that even the transaction itself may be missing (if it is part of a cycle). + for (auto parent : parents) { + assert((depgraph.Ancestors(parent) & parents).IsSubsetOf(SetType::Singleton(parent))); + } + // Similar for children and descendants. + for (auto child : children) { + assert((depgraph.Descendants(child) & children).IsSubsetOf(SetType::Singleton(child))); + } } - // If DepGraph is acyclic, serialize + deserialize must roundtrip. if (IsAcyclic(depgraph)) { + // If DepGraph is acyclic, serialize + deserialize must roundtrip. std::vector<unsigned char> ser; VectorWriter writer(ser, 0); writer << Using<DepGraphFormatter>(depgraph); @@ -292,42 +356,36 @@ void SanityCheck(const DepGraph<SetType>& depgraph) reader >> Using<DepGraphFormatter>(decoded_depgraph); assert(depgraph == decoded_depgraph); assert(reader.empty()); - } -} -/** Verify that a DepGraph corresponds to the information in a cluster. */ -template<typename SetType> -void VerifyDepGraphFromCluster(const Cluster<SetType>& cluster, const DepGraph<SetType>& depgraph) -{ - // Sanity check the depgraph, which includes a check for correspondence between ancestors and - // descendants, so it suffices to check just ancestors below. - SanityCheck(depgraph); - // Verify transaction count. - assert(cluster.size() == depgraph.TxCount()); - // Verify feerates. - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { - assert(depgraph.FeeRate(i) == cluster[i].first); - } - // Verify ancestors. - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { - // Start with the transaction having itself as ancestor. - auto ancestors = SetType::Singleton(i); - // Add parents of ancestors to the set of ancestors until it stops changing. - while (true) { - const auto old_ancestors = ancestors; - for (auto ancestor : ancestors) { - ancestors |= cluster[ancestor].second; - } - if (old_ancestors == ancestors) break; + // In acyclic graphs, the union of parents with parents of parents etc. yields the + // full ancestor set (and similar for children and descendants). + std::vector<SetType> parents(depgraph.PositionRange()), children(depgraph.PositionRange()); + for (ClusterIndex i : depgraph.Positions()) { + parents[i] = depgraph.GetReducedParents(i); + children[i] = depgraph.GetReducedChildren(i); } - // Compare against depgraph. - assert(depgraph.Ancestors(i) == ancestors); - // Some additional sanity tests: - // - Every transaction has itself as ancestor. - assert(ancestors[i]); - // - Every transaction has its direct parents as ancestors. - for (auto parent : cluster[i].second) { - assert(ancestors[parent]); + for (auto i : depgraph.Positions()) { + // Initialize the set of ancestors with just the current transaction itself. + SetType ancestors = SetType::Singleton(i); + // Iteratively add parents of all transactions in the ancestor set to itself. + while (true) { + const auto old_ancestors = ancestors; + for (auto j : ancestors) ancestors |= parents[j]; + // Stop when no more changes are being made. + if (old_ancestors == ancestors) break; + } + assert(ancestors == depgraph.Ancestors(i)); + + // Initialize the set of descendants with just the current transaction itself. + SetType descendants = SetType::Singleton(i); + // Iteratively add children of all transactions in the descendant set to itself. + while (true) { + const auto old_descendants = descendants; + for (auto j : descendants) descendants |= children[j]; + // Stop when no more changes are being made. + if (old_descendants == descendants) break; + } + assert(descendants == depgraph.Descendants(i)); } } } @@ -341,7 +399,7 @@ void SanityCheck(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> lin TestBitSet done; for (auto i : linearization) { // Check transaction position is in range. - assert(i < depgraph.TxCount()); + assert(depgraph.Positions()[i]); // Check topology and lack of duplicates. assert((depgraph.Ancestors(i) - done) == TestBitSet::Singleton(i)); done.Set(i); diff --git a/src/test/util/setup_common.cpp b/src/test/util/setup_common.cpp index fa89ceb332..7465846356 100644 --- a/src/test/util/setup_common.cpp +++ b/src/test/util/setup_common.cpp @@ -104,7 +104,8 @@ static void ExitFailure(std::string_view str_err) BasicTestingSetup::BasicTestingSetup(const ChainType chainType, TestOpts opts) : m_args{} { - m_node.shutdown = &m_interrupt; + m_node.shutdown_signal = &m_interrupt; + m_node.shutdown_request = [this]{ return m_interrupt(); }; m_node.args = &gArgs; std::vector<const char*> arguments = Cat( { @@ -224,7 +225,7 @@ ChainTestingSetup::ChainTestingSetup(const ChainType chainType, TestOpts opts) m_cache_sizes = CalculateCacheSizes(m_args); - m_node.notifications = std::make_unique<KernelNotifications>(*Assert(m_node.shutdown), m_node.exit_status, *Assert(m_node.warnings)); + m_node.notifications = std::make_unique<KernelNotifications>(Assert(m_node.shutdown_request), m_node.exit_status, *Assert(m_node.warnings)); m_make_chainman = [this, &chainparams, opts] { Assert(!m_node.chainman); @@ -245,7 +246,7 @@ ChainTestingSetup::ChainTestingSetup(const ChainType chainType, TestOpts opts) .blocks_dir = m_args.GetBlocksDirPath(), .notifications = chainman_opts.notifications, }; - m_node.chainman = std::make_unique<ChainstateManager>(*Assert(m_node.shutdown), chainman_opts, blockman_opts); + m_node.chainman = std::make_unique<ChainstateManager>(*Assert(m_node.shutdown_signal), chainman_opts, blockman_opts); LOCK(m_node.chainman->GetMutex()); m_node.chainman->m_blockman.m_block_tree_db = std::make_unique<BlockTreeDB>(DBParams{ .path = m_args.GetDataDirNet() / "blocks" / "index", diff --git a/src/test/util/setup_common.h b/src/test/util/setup_common.h index 30d4280fa5..f9cf5d9157 100644 --- a/src/test/util/setup_common.h +++ b/src/test/util/setup_common.h @@ -75,6 +75,23 @@ struct BasicTestingSetup { fs::path m_path_root; fs::path m_path_lock; bool m_has_custom_datadir{false}; + /** @brief Test-specific arguments and settings. + * + * This member is intended to be the primary source of settings for code + * being tested by unit tests. It exists to make tests more self-contained + * and reduce reliance on global state. + * + * Usage guidelines: + * 1. Prefer using m_args where possible in test code. + * 2. If m_args is not accessible, use m_node.args as a fallback. + * 3. Avoid direct references to gArgs in test code. + * + * Note: Currently, m_node.args points to gArgs for backwards + * compatibility. In the future, it will point to m_args to further isolate + * test environments. + * + * @see https://github.com/bitcoin/bitcoin/issues/25055 for additional context. + */ ArgsManager m_args; }; @@ -274,11 +291,9 @@ std::ostream& operator<<(std::ostream& os, const uint256& num); class HasReason { public: - explicit HasReason(const std::string& reason) : m_reason(reason) {} - bool operator()(const std::exception& e) const - { - return std::string(e.what()).find(m_reason) != std::string::npos; - }; + explicit HasReason(std::string_view reason) : m_reason(reason) {} + bool operator()(std::string_view s) const { return s.find(m_reason) != std::string_view::npos; } + bool operator()(const std::exception& e) const { return (*this)(e.what()); } private: const std::string m_reason; diff --git a/src/test/util/transaction_utils.cpp b/src/test/util/transaction_utils.cpp index 5727da4444..a588e61944 100644 --- a/src/test/util/transaction_utils.cpp +++ b/src/test/util/transaction_utils.cpp @@ -90,3 +90,24 @@ void BulkTransaction(CMutableTransaction& tx, int32_t target_weight) assert(GetTransactionWeight(CTransaction(tx)) >= target_weight); assert(GetTransactionWeight(CTransaction(tx)) <= target_weight + 3); } + +bool SignSignature(const SigningProvider &provider, const CScript& fromPubKey, CMutableTransaction& txTo, unsigned int nIn, const CAmount& amount, int nHashType, SignatureData& sig_data) +{ + assert(nIn < txTo.vin.size()); + + MutableTransactionSignatureCreator creator(txTo, nIn, amount, nHashType); + + bool ret = ProduceSignature(provider, creator, fromPubKey, sig_data); + UpdateInput(txTo.vin.at(nIn), sig_data); + return ret; +} + +bool SignSignature(const SigningProvider &provider, const CTransaction& txFrom, CMutableTransaction& txTo, unsigned int nIn, int nHashType, SignatureData& sig_data) +{ + assert(nIn < txTo.vin.size()); + const CTxIn& txin = txTo.vin[nIn]; + assert(txin.prevout.n < txFrom.vout.size()); + const CTxOut& txout = txFrom.vout[txin.prevout.n]; + + return SignSignature(provider, txout.scriptPubKey, txTo, nIn, txout.nValue, nHashType, sig_data); +} diff --git a/src/test/util/transaction_utils.h b/src/test/util/transaction_utils.h index 80f2d1acbf..4a18ab6ab4 100644 --- a/src/test/util/transaction_utils.h +++ b/src/test/util/transaction_utils.h @@ -6,6 +6,7 @@ #define BITCOIN_TEST_UTIL_TRANSACTION_UTILS_H #include <primitives/transaction.h> +#include <script/sign.h> #include <array> @@ -30,4 +31,23 @@ std::vector<CMutableTransaction> SetupDummyInputs(FillableSigningProvider& keyst // by appending a single output with padded output script void BulkTransaction(CMutableTransaction& tx, int32_t target_weight); +/** + * Produce a satisfying script (scriptSig or witness). + * + * @param provider Utility containing the information necessary to solve a script. + * @param fromPubKey The script to produce a satisfaction for. + * @param txTo The spending transaction. + * @param nIn The index of the input in `txTo` referring the output being spent. + * @param amount The value of the output being spent. + * @param nHashType Signature hash type. + * @param sig_data Additional data provided to solve a script. Filled with the resulting satisfying + * script and whether the satisfaction is complete. + * + * @return True if the produced script is entirely satisfying `fromPubKey`. + **/ +bool SignSignature(const SigningProvider &provider, const CScript& fromPubKey, CMutableTransaction& txTo, + unsigned int nIn, const CAmount& amount, int nHashType, SignatureData& sig_data); +bool SignSignature(const SigningProvider &provider, const CTransaction& txFrom, CMutableTransaction& txTo, + unsigned int nIn, int nHashType, SignatureData& sig_data); + #endif // BITCOIN_TEST_UTIL_TRANSACTION_UTILS_H diff --git a/src/test/util_string_tests.cpp b/src/test/util_string_tests.cpp index 8b974ffe6f..1574fe2358 100644 --- a/src/test/util_string_tests.cpp +++ b/src/test/util_string_tests.cpp @@ -5,6 +5,7 @@ #include <util/string.h> #include <boost/test/unit_test.hpp> +#include <test/util/setup_common.h> using namespace util; @@ -21,9 +22,7 @@ inline void PassFmt(util::ConstevalFormatString<NumArgs> fmt) template <unsigned WrongNumArgs> inline void FailFmtWithError(std::string_view wrong_fmt, std::string_view error) { - using ErrType = const char*; - auto check_throw{[error](const ErrType& str) { return str == error; }}; - BOOST_CHECK_EXCEPTION(util::ConstevalFormatString<WrongNumArgs>::Detail_CheckNumFormatSpecifiers(wrong_fmt), ErrType, check_throw); + BOOST_CHECK_EXCEPTION(util::ConstevalFormatString<WrongNumArgs>::Detail_CheckNumFormatSpecifiers(wrong_fmt), const char*, HasReason(error)); } BOOST_AUTO_TEST_CASE(ConstevalFormatString_NumSpec) diff --git a/src/test/validation_chainstate_tests.cpp b/src/test/validation_chainstate_tests.cpp index 30c5982b17..c9cca8af04 100644 --- a/src/test/validation_chainstate_tests.cpp +++ b/src/test/validation_chainstate_tests.cpp @@ -4,6 +4,7 @@ // #include <chainparams.h> #include <consensus/validation.h> +#include <node/kernel_notifications.h> #include <random.h> #include <rpc/blockchain.h> #include <sync.h> @@ -69,14 +70,18 @@ BOOST_AUTO_TEST_CASE(validation_chainstate_resize_caches) BOOST_FIXTURE_TEST_CASE(chainstate_update_tip, TestChain100Setup) { ChainstateManager& chainman = *Assert(m_node.chainman); - uint256 curr_tip = ::g_best_block; + const auto get_notify_tip{[&]() { + LOCK(m_node.notifications->m_tip_block_mutex); + return m_node.notifications->m_tip_block; + }}; + uint256 curr_tip = get_notify_tip(); // Mine 10 more blocks, putting at us height 110 where a valid assumeutxo value can // be found. mineBlocks(10); // After adding some blocks to the tip, best block should have changed. - BOOST_CHECK(::g_best_block != curr_tip); + BOOST_CHECK(get_notify_tip() != curr_tip); // Grab block 1 from disk; we'll add it to the background chain later. std::shared_ptr<CBlock> pblockone = std::make_shared<CBlock>(); @@ -91,15 +96,15 @@ BOOST_FIXTURE_TEST_CASE(chainstate_update_tip, TestChain100Setup) // Ensure our active chain is the snapshot chainstate. BOOST_CHECK(WITH_LOCK(::cs_main, return chainman.IsSnapshotActive())); - curr_tip = ::g_best_block; + curr_tip = get_notify_tip(); // Mine a new block on top of the activated snapshot chainstate. mineBlocks(1); // Defined in TestChain100Setup. // After adding some blocks to the snapshot tip, best block should have changed. - BOOST_CHECK(::g_best_block != curr_tip); + BOOST_CHECK(get_notify_tip() != curr_tip); - curr_tip = ::g_best_block; + curr_tip = get_notify_tip(); BOOST_CHECK_EQUAL(chainman.GetAll().size(), 2); @@ -135,10 +140,10 @@ BOOST_FIXTURE_TEST_CASE(chainstate_update_tip, TestChain100Setup) // Ensure tip is as expected BOOST_CHECK_EQUAL(background_cs.m_chain.Tip()->GetBlockHash(), pblockone->GetHash()); - // g_best_block should be unchanged after adding a block to the background + // get_notify_tip() should be unchanged after adding a block to the background // validation chain. BOOST_CHECK(block_added); - BOOST_CHECK_EQUAL(curr_tip, ::g_best_block); + BOOST_CHECK_EQUAL(curr_tip, get_notify_tip()); } BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/validation_chainstatemanager_tests.cpp b/src/test/validation_chainstatemanager_tests.cpp index b4fcfbd853..6c2a825e64 100644 --- a/src/test/validation_chainstatemanager_tests.cpp +++ b/src/test/validation_chainstatemanager_tests.cpp @@ -382,7 +382,7 @@ struct SnapshotTestSetup : TestChain100Setup { LOCK(::cs_main); chainman.ResetChainstates(); BOOST_CHECK_EQUAL(chainman.GetAll().size(), 0); - m_node.notifications = std::make_unique<KernelNotifications>(*Assert(m_node.shutdown), m_node.exit_status, *Assert(m_node.warnings)); + m_node.notifications = std::make_unique<KernelNotifications>(Assert(m_node.shutdown_request), m_node.exit_status, *Assert(m_node.warnings)); const ChainstateManager::Options chainman_opts{ .chainparams = ::Params(), .datadir = chainman.m_options.datadir, @@ -397,7 +397,7 @@ struct SnapshotTestSetup : TestChain100Setup { // For robustness, ensure the old manager is destroyed before creating a // new one. m_node.chainman.reset(); - m_node.chainman = std::make_unique<ChainstateManager>(*Assert(m_node.shutdown), chainman_opts, blockman_opts); + m_node.chainman = std::make_unique<ChainstateManager>(*Assert(m_node.shutdown_signal), chainman_opts, blockman_opts); } return *Assert(m_node.chainman); } |