diff options
Diffstat (limited to 'src/test/util/cluster_linearize.h')
| -rw-r--r-- | src/test/util/cluster_linearize.h | 248 |
1 files changed, 153 insertions, 95 deletions
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); |