This builds on #31363, adding more functionality to the txgraph module, specifically:
TxGraph::GetMainStagingDiagrams(), a function to obtain feerate diagrams for both the main graph and the staged changes to it, including only the clusters that differ between the two.
TxGraph::GetBlockBuilder(), a function to obtain an object which can efficiently iterate the chunks of the (main) graph from high to low chunk feerate, allowing each to be skipped or included.
TxGraph::GetWorstMainChunk(), a function to obtain the last chunk that would be returned by GetBlockBuilder()’s returned object, intended for eviction.
DrahtBot
commented at 2:50 pm on December 8, 2024:
contributor
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
sipa force-pushed
on Dec 8, 2024
sipa force-pushed
on Dec 8, 2024
DrahtBot removed the label
CI failed
on Dec 8, 2024
glozow added the label
Mempool
on Dec 17, 2024
sipa force-pushed
on Dec 20, 2024
sipa force-pushed
on Dec 22, 2024
sipa force-pushed
on Jan 8, 2025
sipa
commented at 11:30 pm on January 8, 2025:
member
I have simplified the eviction interface. Instead of getting a TxGraph::Evictor object through TxGraph::GetEvictor(), there is now a simpler TxGraph::GetWorstMainChunk() function, which is a pure inspector.
DrahtBot added the label
CI failed
on Jan 9, 2025
DrahtBot
commented at 0:51 am on January 9, 2025:
contributor
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
sipa force-pushed
on Jan 9, 2025
DrahtBot removed the label
CI failed
on Jan 9, 2025
sipa force-pushed
on Jan 9, 2025
DrahtBot
commented at 11:40 pm on January 9, 2025:
contributor
Try to run the tests locally, according to the documentation. However, a CI failure may still
happen due to a number of reasons, for example:
Possibly due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.
A sanitizer issue, which can only be found by compiling with the sanitizer and running the
affected test.
An intermittent issue.
Leave a comment here, if you need help tracking down a confusing failure.
DrahtBot added the label
CI failed
on Jan 9, 2025
sipa force-pushed
on Jan 10, 2025
DrahtBot removed the label
CI failed
on Jan 10, 2025
sipa force-pushed
on Jan 10, 2025
clusterlin: add FixLinearization function + fuzz test
This function takes an existing ordering for transactions in a DepGraph, and
makes it a valid linearization for it (i.e., topological). Any topological
prefix of the input remains untouched.
30beeff0ae
clusterlin: make IsAcyclic() a DepGraph member function
... instead of being a separate test-only function.
91fcc73089
txgraph: (feature) add initial version
This adds an initial version of the txgraph module, with the TxGraph class.
It encapsulates knowledge about the fees, sizes, and dependencies between all
mempool transactions, but nothing else.
In particular, it lacks knowledge about txids, inputs, outputs, CTransactions,
... and so for. Instead, it exposes a generic TxGraph::Ref type to reference
nodes in the TxGraph, which can be passed around and stored by layers on top.
0eb039bcf3
txgraph: (tests) add simulation fuzz test
This adds a simulation fuzz test for txgraph, by comparing with a naive
reimplementation that models the entire graph as a single DepGraph, and
clusters in TxGraph as connected components within that DepGraph.
18c8eafcd7
txgraph: (tests) add internal sanity check function
To make testing more powerful, expose a function to perform an internal sanity
check on the state of a TxGraph. This is especially important as TxGraphImpl
contains many redundantly represented pieces of information:
* graph contains clusters, which refer to entries, but the entries refer back
* graph maintains pointers to Ref objects, which point back to the graph.
This lets us make sure they are always in sync.
ca9e539c9e
txgraph: (feature) make max cluster count configurable and "oversize" state
Instead of leaving the responsibility on higher layers to guarantee that
no connected component within TxGraph (a barely exposed concept, except through
GetCluster()) exceeds the cluster count limit, move this responsibility to
TxGraph itself:
* TxGraph retains a cluster count limit, but it becomes configurable at construction
time (this primarily helps with testing that it is properly enforced).
* It is always allowed to perform mutators on TxGraph, even if they would cause the
cluster count limit to be exceeded. Instead, TxGraph exposes an IsOversized()
function, which queries whether it is in a special "oversize" state.
* During oversize state, many inspectors are unavailable, but mutators remain valid,
so the higher layer can "fix" the oversize state before continuing.
652d5aad6e
txgraph: (optimization) delay chunking while sub-acceptable
Chunk-based information (primarily, chunk feerates) are never accessed without
first bringing the relevant Clusters to an "acceptable" quality level. Thus,
while operations are ongoing and Clusters are not acceptable, we can omit
computing the chunkings and chunk feerates for Clusters.
2734dcb344
txgraph: (optimization) special-case removal of tail of cluster
When transactions are removed from the tail of a cluster, we know the existing
linearization remains acceptable/optimal (if it already was), but may just need
splitting, so special case these into separate quality levels.
a5a41bbd61
txgraph: (refactor) group per-graph data in ClusterSet
This is a preparation for a next commit where a TxGraph will start representing
potentially two distinct graphs (a main one, and a staging one with proposed
changes).
b2b17e7a10
txgraph: (refactor) abstract out ClearLocator
Move a number of related modifications to TxGraphImpl into a separate
function for removal of transactions. This is preparation for a later
commit where this will be useful in more than one place.
eb05507849
txgraph: (feature) add staging support
In order to make it easy to evaluate proposed changes to a TxGraph, introduce a
"staging" mode, where mutators (AddTransaction, AddDependency, RemoveTransaction)
do not modify the actual graph, but just a staging version of it. That staging
graph can then be commited (replacing the main one with it), or aborted (discarding
the staging).
7b106d7ac0
txgraph: (feature) destroying Ref means removing transaction
Before this commit, if a TxGraph::Ref object is destroyed, it becomes impossible
to refer to, but the actual corresponding transaction node in the TxGraph remains,
and remains indefinitely as there is no way to remove it.
Fix this by making the destruction of TxGraph::Ref trigger immediate removal of
the corresponding transaction in TxGraph, both in main and staging if it exists.
05b35a0f4f
txgraph: (feature) expose ability to compare transactions
In order to make it possible for higher layers to compare transaction quality
(ordering within the implicit total ordering on the mempool), expose a comparison
function and test it.
4005a901af
txgraph: (feature) Add DoWork function
This can be called when the caller has time to spend now, and wants future operations
to be fast.
This interface lets one iterate efficiently over the chunks of the main
graph in a TxGraph, in the same order as CompareMainOrder. Each chunk
can be marked as "included" or "skipped" (and in the latter case,
dependent chunks will be skipped).
This is a metadata mirror of the GitHub repository
bitcoin/bitcoin.
This site is not affiliated with GitHub.
Content is generated from a GitHub metadata backup.
generated: 2025-01-21 06:12 UTC
This site is hosted by @0xB10C More mirrored repositories can be found on mirror.b10c.me
