aboutsummaryrefslogtreecommitdiff
path: root/src/test
diff options
context:
space:
mode:
Diffstat (limited to 'src/test')
-rw-r--r--src/test/blockfilter_index_tests.cpp2
-rw-r--r--src/test/blockmanager_tests.cpp8
-rw-r--r--src/test/cluster_linearize_tests.cpp49
-rw-r--r--src/test/coinstatsindex_tests.cpp4
-rw-r--r--src/test/feefrac_tests.cpp2
-rw-r--r--src/test/fuzz/cluster_linearize.cpp249
-rw-r--r--src/test/ipc_test.cpp2
-rw-r--r--src/test/merkle_tests.cpp104
-rw-r--r--src/test/system_tests.cpp2
-rw-r--r--src/test/txindex_tests.cpp2
-rw-r--r--src/test/util/cluster_linearize.h234
-rw-r--r--src/test/util/setup_common.cpp7
-rw-r--r--src/test/util/setup_common.h17
-rw-r--r--src/test/validation_chainstate_tests.cpp18
-rw-r--r--src/test/validation_chainstatemanager_tests.cpp4
15 files changed, 413 insertions, 291 deletions
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/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index d91f85d867..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);
@@ -169,14 +170,14 @@ std::pair<std::vector<ClusterIndex>, bool> SimpleLinearize(const DepGraph<SetTyp
template<typename BS>
void MakeConnected(DepGraph<BS>& depgraph)
{
- auto todo = BS::Fill(depgraph.TxCount());
+ 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.AddDependency(comp.Last(), nextcomp.First());
+ depgraph.AddDependencies(BS::Singleton(comp.Last()), nextcomp.First());
todo -= nextcomp;
comp = nextcomp;
}
@@ -205,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.
@@ -240,59 +241,157 @@ std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanRe
} // namespace
-FUZZ_TARGET(clusterlin_add_dependency)
+FUZZ_TARGET(clusterlin_depgraph_sim)
{
- // Verify that computing a DepGraph from a cluster, or building it step by step using AddDependency
- // have the same effect.
+ // Simulation test to verify the full behavior of DepGraph.
- // 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)
-{
- // 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.
+ /** 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);
+ };
- FuzzedDataProvider provider(buffer.data(), buffer.size());
+ /** 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;
+ };
- // 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);
+ /** 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)
@@ -322,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);
@@ -333,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());
}
@@ -370,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;
@@ -423,7 +522,7 @@ 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;
@@ -454,7 +553,7 @@ 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());
@@ -519,7 +618,7 @@ 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());
@@ -623,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.
@@ -806,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.
@@ -891,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/ipc_test.cpp b/src/test/ipc_test.cpp
index 91eba9214f..af37434980 100644
--- a/src/test/ipc_test.cpp
+++ b/src/test/ipc_test.cpp
@@ -62,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(); }); };
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/system_tests.cpp b/src/test/system_tests.cpp
index 7a9a14d5ac..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>
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 b86ebcd78b..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:
@@ -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.
@@ -189,10 +204,16 @@ struct DepGraphFormatter
/** 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 (preliminarily at the end).
- auto topo_idx = topo_depgraph.AddTransaction({fee, size});
- reordering.push_back(reordering.size());
+ 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,23 +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 the new transaction should be placed (wrapping
- // around), so remove the preliminary position it was put in above (which was to
- // make sure that if a deserialization exception occurs, the new transaction still
- // has some entry in reordering).
- reordering.pop_back();
- ClusterIndex insert_distance = diff % (reordering.size() + 1);
- // And then update reordering to reflect this new transaction's insertion.
- for (auto& pos : reordering) {
- pos += (pos >= reordering.size() - insert_distance);
+ } catch (const std::ios_base::failure&) {
+ // Continue even if a read error was encountered.
+ read_error = true;
+ }
+ // 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;
}
- reordering.push_back(reordering.size() - insert_distance);
}
- } catch (const std::ios_base::failure&) {}
+ // Stop if a read error was encountered during deserialization.
+ if (read_error) break;
+ }
// Construct the original cluster order depgraph.
- depgraph = DepGraph(topo_depgraph, reordering);
+ depgraph = DepGraph(topo_depgraph, reordering, total_size);
}
};
@@ -250,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.
@@ -260,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);
@@ -284,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));
}
}
}
@@ -333,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 f5a3c0dcee..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;
};
diff --git a/src/test/validation_chainstate_tests.cpp b/src/test/validation_chainstate_tests.cpp
index 702af6578d..c9cca8af04 100644
--- a/src/test/validation_chainstate_tests.cpp
+++ b/src/test/validation_chainstate_tests.cpp
@@ -70,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 = m_node.notifications->m_tip_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(m_node.notifications->m_tip_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>();
@@ -92,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 = m_node.notifications->m_tip_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(m_node.notifications->m_tip_block != curr_tip);
+ BOOST_CHECK(get_notify_tip() != curr_tip);
- curr_tip = m_node.notifications->m_tip_block;
+ curr_tip = get_notify_tip();
BOOST_CHECK_EQUAL(chainman.GetAll().size(), 2);
@@ -136,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, m_node.notifications->m_tip_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);
}
generated by cgit v1.2.3 (git 2.26.2) at 2025-02-17 09:17:39 +0000