diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/cluster_linearize.h | 120 | ||||
| -rw-r--r-- | src/test/cluster_linearize_tests.cpp | 39 | ||||
| -rw-r--r-- | src/test/feefrac_tests.cpp | 2 | ||||
| -rw-r--r-- | src/test/fuzz/cluster_linearize.cpp | 51 | ||||
| -rw-r--r-- | src/test/util/cluster_linearize.h | 124 | ||||
| -rw-r--r-- | src/util/check.h | 2 | ||||
| -rw-r--r-- | src/util/feefrac.h | 8 |
7 files changed, 267 insertions, 79 deletions
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h index bcc455874d..a2450f5490 100644 --- a/src/cluster_linearize.h +++ b/src/cluster_linearize.h @@ -57,9 +57,20 @@ class DepGraph /** Data for each transaction, in the same order as the Cluster it was constructed from. */ std::vector<Entry> entries; + /** Which positions are used. */ + SetType m_used; + public: /** Equality operator (primarily for testing purposes). */ - friend bool operator==(const DepGraph&, const DepGraph&) noexcept = default; + friend bool operator==(const DepGraph& a, const DepGraph& b) noexcept + { + if (a.m_used != b.m_used) return false; + // Only compare the used positions within the entries vector. + for (auto idx : a.m_used) { + if (a.entries[idx] != b.entries[idx]) return false; + } + return true; + } // Default constructors. DepGraph() noexcept = default; @@ -80,6 +91,7 @@ public: entries[i].ancestors = SetType::Singleton(i); entries[i].descendants = SetType::Singleton(i); } + m_used = SetType::Fill(ntx); } /** Construct a DepGraph object given a cluster. @@ -98,23 +110,49 @@ public: /** Construct a DepGraph object given another DepGraph and a mapping from old to new. * + * @param depgraph The original DepGraph that is being remapped. + * + * @param mapping A Span such that mapping[i] gives the position in the new DepGraph + * for position i in the old depgraph. Its size must be equal to + * depgraph.PositionRange(). The value of mapping[i] is ignored if + * position i is a hole in depgraph (i.e., if !depgraph.Positions()[i]). + * + * @param pos_range The PositionRange() for the new DepGraph. It must equal the largest + * value in mapping for any used position in depgraph plus 1, or 0 if + * depgraph.TxCount() == 0. + * * Complexity: O(N^2) where N=depgraph.TxCount(). */ - DepGraph(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> mapping) noexcept : DepGraph(depgraph.TxCount()) + DepGraph(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> mapping, ClusterIndex pos_range) noexcept : entries(pos_range) { - Assert(mapping.size() == depgraph.TxCount()); - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + Assume(mapping.size() == depgraph.PositionRange()); + Assume((pos_range == 0) == (depgraph.TxCount() == 0)); + for (ClusterIndex i : depgraph.Positions()) { + auto new_idx = mapping[i]; + Assume(new_idx < pos_range); + // Add transaction. + entries[new_idx].ancestors = SetType::Singleton(new_idx); + entries[new_idx].descendants = SetType::Singleton(new_idx); + m_used.Set(new_idx); // Fill in fee and size. - entries[mapping[i]].feerate = depgraph.entries[i].feerate; + entries[new_idx].feerate = depgraph.entries[i].feerate; + } + for (ClusterIndex i : depgraph.Positions()) { // Fill in dependencies by mapping direct parents. SetType parents; for (auto j : depgraph.GetReducedParents(i)) parents.Set(mapping[j]); AddDependencies(parents, mapping[i]); } + // Verify that the provided pos_range was correct (no unused positions at the end). + Assume(m_used.None() ? (pos_range == 0) : (pos_range == m_used.Last() + 1)); } + /** Get the set of transactions positions in use. Complexity: O(1). */ + const SetType& Positions() const noexcept { return m_used; } + /** Get the range of positions in this DepGraph. All entries in Positions() are in [0, PositionRange() - 1]. */ + ClusterIndex PositionRange() const noexcept { return entries.size(); } /** Get the number of transactions in the graph. Complexity: O(1). */ - auto TxCount() const noexcept { return entries.size(); } + auto TxCount() const noexcept { return m_used.Count(); } /** Get the feerate of a given transaction i. Complexity: O(1). */ const FeeFrac& FeeRate(ClusterIndex i) const noexcept { return entries[i].feerate; } /** Get the mutable feerate of a given transaction i. Complexity: O(1). */ @@ -124,25 +162,59 @@ public: /** Get the descendants of a given transaction i. Complexity: O(1). */ const SetType& Descendants(ClusterIndex i) const noexcept { return entries[i].descendants; } - /** Add a new unconnected transaction to this transaction graph (at the end), and return its - * ClusterIndex. + /** Add a new unconnected transaction to this transaction graph (in the first available + * position), and return its ClusterIndex. * * Complexity: O(1) (amortized, due to resizing of backing vector). */ ClusterIndex AddTransaction(const FeeFrac& feefrac) noexcept { - Assume(TxCount() < SetType::Size()); - ClusterIndex new_idx = TxCount(); - entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx)); + static constexpr auto ALL_POSITIONS = SetType::Fill(SetType::Size()); + auto available = ALL_POSITIONS - m_used; + Assume(available.Any()); + ClusterIndex new_idx = available.First(); + if (new_idx == entries.size()) { + entries.emplace_back(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx)); + } else { + entries[new_idx] = Entry(feefrac, SetType::Singleton(new_idx), SetType::Singleton(new_idx)); + } + m_used.Set(new_idx); return new_idx; } + /** Remove the specified positions from this DepGraph. + * + * The specified positions will no longer be part of Positions(), and dependencies with them are + * removed. Note that due to DepGraph only tracking ancestors/descendants (and not direct + * dependencies), if a parent is removed while a grandparent remains, the grandparent will + * remain an ancestor. + * + * Complexity: O(N) where N=TxCount(). + */ + void RemoveTransactions(const SetType& del) noexcept + { + m_used -= del; + // Remove now-unused trailing entries. + while (!entries.empty() && !m_used[entries.size() - 1]) { + entries.pop_back(); + } + // Remove the deleted transactions from ancestors/descendants of other transactions. Note + // that the deleted positions will retain old feerate and dependency information. This does + // not matter as they will be overwritten by AddTransaction if they get used again. + for (auto& entry : entries) { + entry.ancestors &= m_used; + entry.descendants &= m_used; + } + } + /** Modify this transaction graph, adding multiple parents to a specified child. * * Complexity: O(N) where N=TxCount(). */ void AddDependencies(const SetType& parents, ClusterIndex child) noexcept { + Assume(m_used[child]); + Assume(parents.IsSubsetOf(m_used)); // Compute the ancestors of parents that are not already ancestors of child. SetType par_anc; for (auto par : parents - Ancestors(child)) { @@ -257,7 +329,7 @@ public: * * Complexity: O(TxCount()). */ - bool IsConnected() const noexcept { return IsConnected(SetType::Fill(TxCount())); } + bool IsConnected() const noexcept { return IsConnected(m_used); } /** Append the entries of select to list in a topologically valid order. * @@ -507,11 +579,11 @@ public: */ AncestorCandidateFinder(const DepGraph<SetType>& depgraph LIFETIMEBOUND) noexcept : m_depgraph(depgraph), - m_todo{SetType::Fill(depgraph.TxCount())}, - m_ancestor_set_feerates(depgraph.TxCount()) + m_todo{depgraph.Positions()}, + m_ancestor_set_feerates(depgraph.PositionRange()) { // Precompute ancestor-set feerates. - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + for (ClusterIndex i : m_depgraph.Positions()) { /** The remaining ancestors for transaction i. */ SetType anc_to_add = m_depgraph.Ancestors(i); FeeFrac anc_feerate; @@ -634,22 +706,26 @@ public: SearchCandidateFinder(const DepGraph<SetType>& depgraph, uint64_t rng_seed) noexcept : m_rng(rng_seed), m_sorted_to_original(depgraph.TxCount()), - m_original_to_sorted(depgraph.TxCount()), - m_todo(SetType::Fill(depgraph.TxCount())) + m_original_to_sorted(depgraph.PositionRange()) { - // Determine reordering mapping, by sorting by decreasing feerate. - std::iota(m_sorted_to_original.begin(), m_sorted_to_original.end(), ClusterIndex{0}); + // Determine reordering mapping, by sorting by decreasing feerate. Unusued positions are + // not included, as they will never be looked up anyway. + ClusterIndex sorted_pos{0}; + for (auto i : depgraph.Positions()) { + m_sorted_to_original[sorted_pos++] = i; + } std::sort(m_sorted_to_original.begin(), m_sorted_to_original.end(), [&](auto a, auto b) { auto feerate_cmp = depgraph.FeeRate(a) <=> depgraph.FeeRate(b); if (feerate_cmp == 0) return a < b; return feerate_cmp > 0; }); // Compute reverse mapping. - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + for (ClusterIndex i = 0; i < m_sorted_to_original.size(); ++i) { m_original_to_sorted[m_sorted_to_original[i]] = i; } // Compute reordered dependency graph. - m_sorted_depgraph = DepGraph(depgraph, m_original_to_sorted); + m_sorted_depgraph = DepGraph(depgraph, m_original_to_sorted, m_sorted_to_original.size()); + m_todo = m_sorted_depgraph.Positions(); } /** Check whether any unlinearized transactions remain. */ @@ -1161,7 +1237,7 @@ void PostLinearize(const DepGraph<SetType>& depgraph, Span<ClusterIndex> lineari // During an even pass, the diagram above would correspond to linearization [2,3,0,1], with // groups [2] and [3,0,1]. - std::vector<TxEntry> entries(linearization.size() + 1); + std::vector<TxEntry> entries(depgraph.PositionRange() + 1); // Perform two passes over the linearization. for (int pass = 0; pass < 2; ++pass) { diff --git a/src/test/cluster_linearize_tests.cpp b/src/test/cluster_linearize_tests.cpp index d15e783ea1..cb87dcbffb 100644 --- a/src/test/cluster_linearize_tests.cpp +++ b/src/test/cluster_linearize_tests.cpp @@ -18,6 +18,10 @@ 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) { @@ -26,6 +30,13 @@ void TestDepGraphSerialization(const Cluster<SetType>& cluster, const std::strin // Run normal sanity and correspondence checks, which includes a round-trip test. VerifyDepGraphFromCluster(cluster, depgraph); + // Remove holes (which are expected to be present as HOLE entries in cluster). + SetType holes; + for (ClusterIndex i = 0; i < cluster.size(); ++i) { + if (cluster[i] == HOLE) holes.Set(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. std::vector<unsigned char> encoding; @@ -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/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 bf7db4482c..e75883878e 100644 --- a/src/test/fuzz/cluster_linearize.cpp +++ b/src/test/fuzz/cluster_linearize.cpp @@ -37,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; } @@ -107,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; } @@ -153,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); @@ -170,7 +170,7 @@ 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; @@ -206,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. @@ -327,6 +327,17 @@ FUZZ_TARGET(clusterlin_cluster_serialization) // check for the serialization). DepGraph depgraph(cluster); VerifyDepGraphFromCluster(cluster, depgraph); + + // Remove an arbitrary subset (in order to construct a graph with holes) and verify that it + // still sanity checks (incl. round-tripping serialization). + uint64_t del = provider.ConsumeIntegralInRange<uint64_t>(1, (uint64_t{1} << TestBitSet::Size()) - 1); + TestBitSet setdel; + for (ClusterIndex i = 0; i < TestBitSet::Size(); ++i) { + if (del & 1) setdel.Set(i); + del >>= 1; + } + depgraph.RemoveTransactions(setdel); + SanityCheck(depgraph); } FUZZ_TARGET(clusterlin_depgraph_serialization) @@ -356,7 +367,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); @@ -367,7 +378,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()); } @@ -404,7 +415,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; @@ -457,7 +468,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; @@ -488,7 +499,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()); @@ -553,7 +564,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()); @@ -657,7 +668,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. @@ -840,8 +851,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. @@ -925,9 +936,17 @@ 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.GetReducedChildren(i); diff --git a/src/test/util/cluster_linearize.h b/src/test/util/cluster_linearize.h index bec4d41d38..44cd6590d3 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,16 +134,17 @@ 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. */ + /** 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. @@ -165,10 +175,19 @@ struct DepGraphFormatter } } // Write position information. - // 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); + 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; + } done.Set(idx); } @@ -185,8 +204,7 @@ 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 (before the - * introduction of holes in a further commit, this always equals reordering.size()). */ + /** How big the entries vector in the reconstructed depgraph will be (including holes). */ ClusterIndex total_size{0}; // Read transactions in topological order. @@ -235,18 +253,43 @@ struct DepGraphFormatter assert(reordering.size() < SetType::Size()); auto topo_idx = topo_depgraph.AddTransaction(new_feerate); topo_depgraph.AddDependencies(new_ancestors, topo_idx); - diff %= total_size + 1; - // Insert the new transaction at distance diff back from the end. - for (auto& pos : reordering) { - pos += (pos >= total_size - diff); + 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(total_size++ - 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); + depgraph = DepGraph(topo_depgraph, reordering, total_size); } }; @@ -254,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. @@ -264,8 +318,8 @@ 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. @@ -305,12 +359,12 @@ void SanityCheck(const DepGraph<SetType>& depgraph) // 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, children; - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { - parents.push_back(depgraph.GetReducedParents(i)); - children.push_back(depgraph.GetReducedChildren(i)); + std::vector<SetType> parents(depgraph.PositionRange()), children(depgraph.PositionRange()); + for (ClusterIndex i : depgraph.Positions()) { + parents[i] = depgraph.GetReducedParents(i); + children[i] = depgraph.GetReducedChildren(i); } - for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) { + 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. @@ -382,7 +436,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/util/check.h b/src/util/check.h index a02a1de8dc..8f28f5dc94 100644 --- a/src/util/check.h +++ b/src/util/check.h @@ -40,7 +40,7 @@ void assertion_fail(std::string_view file, int line, std::string_view func, std: /** Helper for Assert()/Assume() */ template <bool IS_ASSERT, typename T> -T&& inline_assertion_check(LIFETIMEBOUND T&& val, [[maybe_unused]] const char* file, [[maybe_unused]] int line, [[maybe_unused]] const char* func, [[maybe_unused]] const char* assertion) +constexpr T&& inline_assertion_check(LIFETIMEBOUND T&& val, [[maybe_unused]] const char* file, [[maybe_unused]] int line, [[maybe_unused]] const char* func, [[maybe_unused]] const char* assertion) { if constexpr (IS_ASSERT #ifdef ABORT_ON_FAILED_ASSUME diff --git a/src/util/feefrac.h b/src/util/feefrac.h index 9772162010..161322b50a 100644 --- a/src/util/feefrac.h +++ b/src/util/feefrac.h @@ -64,13 +64,13 @@ struct FeeFrac int32_t size; /** Construct an IsEmpty() FeeFrac. */ - inline FeeFrac() noexcept : fee{0}, size{0} {} + constexpr inline FeeFrac() noexcept : fee{0}, size{0} {} /** Construct a FeeFrac with specified fee and size. */ - inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {} + constexpr inline FeeFrac(int64_t f, int32_t s) noexcept : fee{f}, size{s} {} - inline FeeFrac(const FeeFrac&) noexcept = default; - inline FeeFrac& operator=(const FeeFrac&) noexcept = default; + constexpr inline FeeFrac(const FeeFrac&) noexcept = default; + constexpr inline FeeFrac& operator=(const FeeFrac&) noexcept = default; /** Check if this is empty (size and fee are 0). */ bool inline IsEmpty() const noexcept { |