depgraph: add memory usage control (feature)
What the developer wrote
Authored by Pieter Wuille
depgraph: add memory usage control (feature)
Co-Authored-By: Lőrinc <pap.lorinc@gmail.com>
What changed, and why it matters
This commit adds a memory-shrinking helper called Compact() to an internal Bitcoin Core data structure (DepGraph) used when ordering groups of transactions. It also adds a way to report how much memory the structure uses, and updates a fuzz test to exercise both. There is no direct security fix here; it is a memory-usage control feature that may help limit resource consumption during fuzzing or normal operation.
No immediate action required. Treat as a routine feature/refactoring commit. If memory usage of cluster linearization is a concern, ensure production callers invoke Compact() at appropriate intervals and set hard memory limits elsewhere.
Security signals we found
Adds memory-usage reporting and compaction to a transaction-clustering data structure
Fuzz target now exercises compaction and asserts non-increasing memory after compaction
No explicit bug fix, bounds enforcement, or input validation change
Evidence from the diff
The patch introduces DepGraph::Compact() (shrink_to_fit on the entries vector), DepGraph::DynamicMemoryUsage() (via memusage.h), and wires them into the clusterlin_depgraph_sim fuzz target. The fuzzer now has a fourth command (0-3) that periodically compacts the graph and asserts memory does not increase. The change is defensive: it gives callers a way to bound memory growth of the dependency graph, but it does not by itself enforce a bound or patch a known vulnerability.
Changed components
src/cluster_linearize.hsrc/test/fuzz/cluster_linearize.cppInspect captured patch +72 / −51
diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index bec44d97..73c8a037 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -12,6 +12,7 @@
#include <utility>
#include <vector>
+#include <memusage.h>
#include <random.h>
#include <span.h>
#include <util/feefrac.h>
@@ -332,6 +333,17 @@ public:
}
return true;
}
+
+ /** Reduce memory usage if possible. No observable effect. */
+ void Compact() noexcept
+ {
+ entries.shrink_to_fit();
+ }
+
+ size_t DynamicMemoryUsage() const noexcept
+ {
+ return memusage::DynamicUsage(entries);
+ }
};
/** A set of transactions together with their aggregate feerate. */
diff --git a/src/test/fuzz/cluster_linearize.cpp b/src/test/fuzz/cluster_linearize.cpp
index 5cdcf799..61b95c71 100644
--- a/src/test/fuzz/cluster_linearize.cpp
+++ b/src/test/fuzz/cluster_linearize.cpp
@@ -452,63 +452,72 @@ FUZZ_TARGET(clusterlin_depgraph_sim)
}
};
+ auto last_compaction_pos{real.PositionRange()};
+
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 (DepGraphIndex i = 0; i < TestBitSet::Size(); ++i) {
- if (!sim[i].has_value()) {
- assert(idx == i);
- break;
+ int command = provider.ConsumeIntegral<uint8_t>() % 4;
+ while (true) {
+ // Iterate decreasing command until an applicable branch is found.
+ if (num_tx_sim < TestBitSet::Size() && command-- == 0) {
+ // 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 (DepGraphIndex 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.
- DepGraphIndex 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 (DepGraphIndex 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;
+ // Update sim.
+ sim[idx] = {feerate, TestBitSet::Singleton(idx)};
+ ++num_tx_sim;
+ break;
+ } else if (num_tx_sim > 0 && command-- == 0) {
+ // AddDependencies.
+ DepGraphIndex child = idx_fn();
+ auto parents = subset_fn();
+ // Apply to DepGraph.
+ real.AddDependencies(parents, child);
+ // Apply to sim.
+ sim[child]->second |= parents;
+ break;
+ } else if (num_tx_sim > 0 && command-- == 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 (DepGraphIndex 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;
+ }
}
}
+ break;
+ } else if (command-- == 0) {
+ // Compact.
+ const size_t mem_before{real.DynamicMemoryUsage()};
+ real.Compact();
+ const size_t mem_after{real.DynamicMemoryUsage()};
+ assert(real.PositionRange() < last_compaction_pos ? mem_after < mem_before : mem_after <= mem_before);
+ last_compaction_pos = real.PositionRange();
+ break;
}
- continue;
}
- // This should be unreachable (one of the 3 above actions should always be possible).
- assert(false);
}
// Compare the real obtained depgraph against the simulation.
Why this scored 18/100
Community notes
Notes can correct, qualify, or add evidence to the AI analysis. Every note shown here has been validated by a human moderator.
The AI analysis stands alone for now. Submit a note if you can add evidence or important context.