aboutsummaryrefslogtreecommitdiff
path: root/src/test/util/cluster_linearize.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/test/util/cluster_linearize.h')
-rw-r--r--src/test/util/cluster_linearize.h250
1 files changed, 154 insertions, 96 deletions
diff --git a/src/test/util/cluster_linearize.h b/src/test/util/cluster_linearize.h
index 508a08133c..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) {
@@ -155,7 +164,7 @@ struct DepGraphFormatter
// Ignore transactions which are already known to be ancestors.
if (depgraph.Descendants(dep_idx).Overlaps(written_parents)) continue;
if (depgraph.Ancestors(idx)[dep_idx]) {
- // When an actual parent is encounted, encode how many non-parents were skipped
+ // When an actual parent is encountered, encode how many non-parents were skipped
// before it.
s << VARINT(diff);
diff = 0;
@@ -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);
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-23 12:12:57 +0000