diff options
| -rw-r--r-- | src/cluster_linearize.h | 32 | ||||
| -rw-r--r-- | src/test/fuzz/cluster_linearize.cpp | 80 |
2 files changed, 112 insertions, 0 deletions
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h index 39b6881544..ba60c49ed0 100644 --- a/src/cluster_linearize.h +++ b/src/cluster_linearize.h @@ -184,10 +184,23 @@ struct SetInfo /** Construct a SetInfo for a specified set and feerate. */ SetInfo(const SetType& txn, const FeeFrac& fr) noexcept : transactions(txn), feerate(fr) {} + /** Construct a SetInfo for a given transaction in a depgraph. */ + explicit SetInfo(const DepGraph<SetType>& depgraph, ClusterIndex pos) noexcept : + transactions(SetType::Singleton(pos)), feerate(depgraph.FeeRate(pos)) {} + /** Construct a SetInfo for a set of transactions in a depgraph. */ explicit SetInfo(const DepGraph<SetType>& depgraph, const SetType& txn) noexcept : transactions(txn), feerate(depgraph.FeeRate(txn)) {} + /** Add the transactions of other to this SetInfo (no overlap allowed). */ + SetInfo& operator|=(const SetInfo& other) noexcept + { + Assume(!transactions.Overlaps(other.transactions)); + transactions |= other.transactions; + feerate += other.feerate; + return *this; + } + /** Construct a new SetInfo equal to this, with more transactions added (which may overlap * with the existing transactions in the SetInfo). */ [[nodiscard]] SetInfo Add(const DepGraph<SetType>& depgraph, const SetType& txn) const noexcept @@ -199,6 +212,25 @@ struct SetInfo friend bool operator==(const SetInfo&, const SetInfo&) noexcept = default; }; +/** Compute the feerates of the chunks of linearization. */ +template<typename SetType> +std::vector<FeeFrac> ChunkLinearization(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> linearization) noexcept +{ + std::vector<FeeFrac> ret; + for (ClusterIndex i : linearization) { + /** The new chunk to be added, initially a singleton. */ + auto new_chunk = depgraph.FeeRate(i); + // As long as the new chunk has a higher feerate than the last chunk so far, absorb it. + while (!ret.empty() && new_chunk >> ret.back()) { + new_chunk += ret.back(); + ret.pop_back(); + } + // Actually move that new chunk into the chunking. + ret.push_back(std::move(new_chunk)); + } + return ret; +} + /** Class encapsulating the state needed to find the best remaining ancestor set. * * It is initialized for an entire DepGraph, and parts of the graph can be dropped by calling diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp index 931862b12d..f93eb9c8e3 100644 --- a/src/test/fuzz/cluster_linearize.cpp +++ b/src/test/fuzz/cluster_linearize.cpp @@ -158,6 +158,44 @@ SetType ReadTopologicalSet(const DepGraph<SetType>& depgraph, const SetType& tod return ret & todo; } +/** Given a dependency graph, construct any valid linearization for it, reading from a SpanReader. */ +template<typename BS> +std::vector<ClusterIndex> ReadLinearization(const DepGraph<BS>& depgraph, SpanReader& reader) +{ + std::vector<ClusterIndex> linearization; + TestBitSet todo = TestBitSet::Fill(depgraph.TxCount()); + // 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. + TestBitSet potential_next; + for (auto j : todo) { + if ((depgraph.Ancestors(j) & todo) == TestBitSet::Singleton(j)) { + potential_next.Set(j); + } + } + // There must always be one (otherwise there is a cycle in the graph). + assert(potential_next.Any()); + // Read a number from reader, and interpret it as index into potential_next. + uint64_t idx{0}; + try { + reader >> VARINT(idx); + } catch (const std::ios_base::failure&) {} + idx %= potential_next.Count(); + // Find out which transaction that corresponds to. + for (auto j : potential_next) { + if (idx == 0) { + // When found, add it to linearization and remove it from todo. + linearization.push_back(j); + assert(todo[j]); + todo.Reset(j); + break; + } + --idx; + } + } + return linearization; +} + } // namespace FUZZ_TARGET(clusterlin_add_dependency) @@ -231,6 +269,48 @@ FUZZ_TARGET(clusterlin_depgraph_serialization) assert(IsAcyclic(depgraph)); } +FUZZ_TARGET(clusterlin_chunking) +{ + // Verify the correctness of the ChunkLinearization function. + + // Construct a graph by deserializing. + SpanReader reader(buffer); + DepGraph<TestBitSet> depgraph; + try { + reader >> Using<DepGraphFormatter>(depgraph); + } catch (const std::ios_base::failure&) {} + + // Read a valid linearization for depgraph. + auto linearization = ReadLinearization(depgraph, reader); + + // Invoke the chunking function. + auto chunking = ChunkLinearization(depgraph, linearization); + + // Verify that chunk feerates are monotonically non-increasing. + for (size_t i = 1; i < chunking.size(); ++i) { + assert(!(chunking[i] >> chunking[i - 1])); + } + + // Naively recompute the chunks (each is the highest-feerate prefix of what remains). + auto todo = TestBitSet::Fill(depgraph.TxCount()); + for (const auto& chunk_feerate : chunking) { + assert(todo.Any()); + SetInfo<TestBitSet> accumulator, best; + for (ClusterIndex idx : linearization) { + if (todo[idx]) { + accumulator |= SetInfo(depgraph, idx); + if (best.feerate.IsEmpty() || accumulator.feerate >> best.feerate) { + best = accumulator; + } + } + } + assert(chunk_feerate == best.feerate); + assert(best.transactions.IsSubsetOf(todo)); + todo -= best.transactions; + } + assert(todo.None()); +} + FUZZ_TARGET(clusterlin_ancestor_finder) { // Verify that AncestorCandidateFinder works as expected. |