This has no functional affect, as the any CBlockIndex*s which
to_mark_failed is set to will already have been marked failed.
Also prevents a situation where block already marked as
BLOCK_FAILED_CHILD is again unconditionally marked as
BLOCK_FAILED_VALID in the final |= BLOCK_FAILED_VALID.
invalid_block ----------> block_index
- before this commit, only if block_index is not invalid, it will mark
block_index as BLOCK_FAILED_CHILD
- it's possible that block_index encountered is invalid and was marked
as BLOCK_FAILED_VALID previously
- in this case, correctly update BlockStatus of block_index by
clearing BLOCK_FAILED_VALID and then setting it to BLOCK_FAILED_CHILD
when a block is invalidated using InvalidateBlock, check that:
1. it's status is BLOCK_FAILED_VALID
2. it's children's status is BLOCK_FAILED_CHILD
and not BLOCK_FAILED_VALID
3. it's ancestors are valid
this block of code is not reached on master since other than
initialisation, all other iterations have invalid_walk_tip
and to_mark_failed pointers in some form of this layout
where 1, 2, 3 and 4 are block heights.
invalid_walk_tip
↓
1 <- 2 <- 3 <- 4
↑
to_mark_failed
fix it so that blocks are correctly marked as BLOCK_FAILED_CHILD
if it's a descendant of BLOCK_FAILED_VALID block.
This change stresses that all ZMQ messages share the same structure
and that they differ only in the format of the bodies. Previously this
was not clear.
Further it removes the notion of endianness of 32-byte hashes,
as it was misleading, and replaces it with the term 'reversed byte
order' (as opposed to natural or normal byte order produced by hashing
functions).
Additionally, it states that ZMQ 32-byte hashes are in the same format
as in RPC. Previously it incorrectly stated that the two were in
different formats.
* Range-for avoids ++i/i++ debate and decreases linecount.
* seen_multipath is only used if multipath_segment_index hasn't already been set. Rename it to seen_substitutes to better describe what it does, now that the context implies its involved in multipath.
57d8b1f1b3 cmake: Avoid fuzzer "multiple definition of `main'" errors (Ryan Ofsky)
Pull request description:
This change builds libraries with `-fsanitize=fuzzer-no-link` instead of `-fsanitize=fuzzer` when the cmake `-DSANITIZERS=fuzzer` option is specified. This is necessary to make fuzzing and IPC cmake options compatible with each other and avoid CI failures in #30975 which enables IPC in the fuzzer CI build:
https://cirrus-ci.com/task/5366255504326656?logs=ci#L2817https://cirrus-ci.com/task/5233064575500288?logs=ci#L2384
The failures can also be reproduced by checking out #31741 and building with `cmake -B build -DBUILD_FOR_FUZZING=ON -DSANITIZERS=fuzzer -DENABLE_IPC=ON` with this fix reverted.
The fix updates the cmake build so when `-DSANITIZERS=fuzzer` is specified, the fuzz test binary is built with `-fsanitize=fuzzer` (so it can use libFuzzer's main function), and libraries are built with `-fsanitize=fuzzer-no-link` (so they can be linked into other executables with their own main functions).
Previously when `-DSANITIZERS=fuzzer` was specified, `-fsanitize=fuzzer` was applied to ALL libraries and executables. This was inappropriate because it made it impossible to build any executables other than the fuzz test executable without triggering link errors:
- `` multiple definition of `main' ``
- `` "undefined reference to `LLVMFuzzerTestOneInput' ``
if they depended on any libraries instrumented for fuzzing.
This was especially a problem when the `ENABLE_IPC` option was set because it made building the `mpgen` code generator impossible so nothing else that depended on generated sources, including the fuzz test binary, could be built either.
This commit was previously part of https://github.com/bitcoin/bitcoin/pull/31741 and had some discussion there starting in https://github.com/bitcoin/bitcoin/pull/31741#pullrequestreview-2619682385
---
This PR is part of the [process separation project](https://github.com/bitcoin/bitcoin/issues/28722).
ACKs for top commit:
hebasto:
ACK 57d8b1f1b3, tested on Ubuntu 24.04.
Tree-SHA512: 4011adbc0b08742e83cf7c0560d3d5b5694a863358e6ac9a21239626b4a8fedceca66db34b5a46136a7b26849bb1d8710c894689322ae97e1c407687c3f57d50
ae6b6ea296 wallet: remove redundant `Assert` call when block is disconnected (rkrux)
Pull request description:
It was highlighted in a PR discussion previously that the recently moved `Assert` macro call inside the block disconnected loop had been redundant for quite a while because of the presence of the `assert` macro call at the start of the function. Therefore, it is removed now.
refs #https://github.com/bitcoin/bitcoin/pull/31757#discussion_r1995416821
ACKs for top commit:
fjahr:
utACK ae6b6ea296
l0rinc:
crACK ae6b6ea296
hodlinator:
Code Review ACK ae6b6ea296
Prabhat1308:
Code Review ACK [`ae6b6ea`](ae6b6ea296)
Tree-SHA512: 6bbced88f4b39afcacefb7babe97c180a397d9cd55f18c4c2875bd594547dcdccb2059ac32495e0e8d4e7263b4c1349ca80b2f0fbd46b4450d1d847ba5abd903
d065208f0f test: get rid of redundant TODO tag (Chandra Pratap)
Pull request description:
The `FEE` parameter in `test/functional/feature_dbcrash.py::generate_small_transaction()` is not a fee rate, but an absolute fee. Hence, it doesn't make sense to replace it with node relay based fee calculation. Get rid of the TODO comment suggesting otherwise.
ACKs for top commit:
maflcko:
lgtm ACK d065208f0f
Tree-SHA512: f2b7f51ffb23de8e14ca071edd731410176a20750115a65db0ae67714389e03ffe1593ce88368e96d211329bd93c772f665de7c3a59b932681bc5b80db908d9f
This abstracts out the finding of the connected component that includes
a given element from FindConnectedComponent (which just finds any connected
component).
Use this in the txgraph fuzz test, which was effectively reimplementing this
logic. At the same time, improve its performance by replacing a vector with a
set.
ca55613fd1 test: Add functional test for bitcoin-chainstate (TheCharlatan)
3f9c716e7f test: Fix docstring for cmake migration (TheCharlatan)
Pull request description:
While the `bitcoin-chainstate` utility is not shipped in a release, it is the only current utility directly using the bitcoin kernel library. Adding a simple test for it is useful for checking that the library is actually usable. The test is also useful in future to demonstrate that the `bitcoin-chainstate` binary using the API for the kernel library introduced in #30595 actually works and offers similar features.
ACKs for top commit:
laanwj:
Code review ACK ca55613fd1
maflcko:
ACK ca55613fd1🎭
kevkevinpal:
ACK ca55613fd1
Tree-SHA512: 282627f5fac868a84aab9962ef2cbd3a8d3941d9f9dc2a3f26db1e7706ffa8051637ab5f8372676800e426e077ca40449a9e3e42a003048472339d81ed81bca8
a82829f37e test: simplify (w)txid checks by avoiding .calc_sha256 calls (Sebastian Falbesoner)
346a099fc1 test: avoid unneeded hash -> uint256 -> hash roundtrips (Sebastian Falbesoner)
Pull request description:
In the functional test framework we currently have a strong tendency to treat and store identifiers that result from hash functions (e.g. (w)txids, block hashes) as integers, which seems an unnatural and confusing choice. Hashes are just pseudo-random sequences of bytes, and there is usually no need to apply integer operations on them; the only exceptions I could think of is PoW-verification of block hashes with the less-than (`<`) operator, or interpreting the byte-string as scalar in the EC-context for e.g. key derivation.
I'd hence argue that most uses of `ser_uint256`/`uint256_from_str` and txid conversions via `int(txid/blockhash, 16)` are potential code smells and should be reduced to a minimum long-term if possible. This PR is a first step into this direction, intentionally kept small with (what I think) uncontroversial changes for demonstration purposes, to check out if other contributors are interested in this. A next step could be to change the classes of primitives (CTransaction, CBlock etc.) and network messages (msg_) to store hash results as actual bytes (maybe in a class wrapping the bytes that offers conversion from/to human-readable strings [1], for easier interaction with RPC calls and debug outputs) rather than ints. But that would of course need larger, potentially more controversial changes, and its questionable if its really worth the effort.
[1] unfortunately, txids and block hashes are shown to user in reverse byte order, so e.g. a txid_bytes->txid_str conversion is not just a simple `txid_bytes.hex()`, but a `txid_bytes[::-1].hex()`
ACKs for top commit:
maflcko:
review ACK a82829f37e🐘
rkrux:
Concept and utACK a82829f37e
ryanofsky:
Code review ACK a82829f37e. Nice changes, and sorry about the false bug report
Tree-SHA512: bb0465802d743a495207800f922b65f49ed0d20552f95bb0bee764944664092aad74812e29df6e01ef40bcb8f9bc6c84c7e9cbbe6f008ee1a14d94ed88e698b4
It was highlighted in a PR discussion previously that the recently
moved `Assert` macro call inside the block disconnected loop had
been redundant for quite a while because of the presence of the
`assert` macro call at the start of the function. Therefore, it
is removed now.
refs #https://github.com/bitcoin/bitcoin/pull/31757#discussion_r1995416821
329a0dcdaf doc: clarify the documentation of `Assume` (ismaelsadeeq)
Pull request description:
An Expression inside `Assume` may be optimized away in production builds when the compiler proves they are side-effect-free.
This use case is demonstrated in #31363 and is suggested to be documented in https://github.com/bitcoin/bitcoin/pull/31363#issuecomment-2736410023.
ACKs for top commit:
l0rinc:
ACK 329a0dcdaf
hodlinator:
re-ACK 329a0dcdaf
jonatack:
ACK 329a0dcdaf
rkrux:
re-ACK 329a0dcdaf
Tree-SHA512: 4bbb807a1e632694863c1a1fa2e93cc5a756b19f8d78f0642ebe7ffafb01835765fa66c76a680dc6f3c412a5abb0c4a33fb7212c26b4b2d80b6b3b7ee8284b2e
248fdd88dc test: accept unordered tracepoints in... (willcl-ark)
Pull request description:
We have encountered an instance where the tracepoints were not collected in the same order they were fired (#31951).
Tracepoint ordering is not guaranteed in userspace for a number of reasons.
As this test does not require a strict collection/processing order collect `expected` and `actual` events into dicts and compare them.
This will gracefully handle both the number of events, and out-of-order events should they reoccur in the future.
Fixes: #31951
ACKs for top commit:
0xB10C:
re-ACK 248fdd88dc
laanwj:
Code review ACK 248fdd88dc
Tree-SHA512: 78d1aa936194d386d919ed26133aac3af5fc6d3d0b1fe1e767288d9e6226e2c701d640e71e994a63ccd48344bd2a0db508cb353cdd5ce1f644cd6f7313654623
52ede28a8a doc: Update comments for AreInputsStandard to match code (Anthony Towns)
Pull request description:
The comment about extra data stuffed in scriptSigs was introduced in #4365 which introduced `ScriptSigArgsExpected()`, and became incorrect after #7387 / #7453 (checks are now performed by `SCRIPT_VERIFY_CLEANSTACK` during script validation and `IsPushOnly()` in `IsStandardTx()`). Drops the details on what a p2sh with many checksigs would look like, which was already done in #4365, but only for main.cpp not the duplicated comment in main.h, which was merged into policy/policy.cpp in #6335 and later moved to the right place in #10682.
ACKs for top commit:
instagibbs:
ACK 52ede28a8a
darosior:
ACK 52ede28a8a
Tree-SHA512: 5ee9a775c81d4c23aca2f8f938ab8bfa7605af489ddb78788613195be8744c7fb7a37bae271093f67f572577452651d4958706b55346e99cf8d32ac0fc34df03
52ac17757e cmake: Add `NO_CACHE_IF_FAILED` option for checking linker flags (Hennadii Stepanov)
Pull request description:
Use it for checking `-fsanitize`.
This change improves the user experience when the configuration step fails due to a missing library. Now, there is no need to manually clean the CMake cache after installing the required library.
Addresses [this](https://github.com/bitcoin/bitcoin/issues/31942#issuecomment-2703801270) comment from https://github.com/bitcoin/bitcoin/issues/31942.
ACKs for top commit:
fanquake:
ACK 52ac17757e
Tree-SHA512: 4004110585413792faa01551cf5a5b3b0de7f213c7a1dd333647107741f84abf626fd0ed067fc17e4c5a523de549432738d3752facf25d1e3dab240be8d13d03
9f35d4d070 test: fix intermittent timeout in p2p_ibd_stalling.py (Martin Zumsande)
Pull request description:
After sending the headers message add a sync, so that we wait until the header message from the previous peer has been received before connecting additional peers.
In the failed NetBSD run linked in #32090, the second node managed to complete the handshake and send its own headers message before the message from the first node was received.
Fixes#32090
ACKs for top commit:
maflcko:
lgtm ACK 9f35d4d070
Tree-SHA512: 30a98c6ec04f819c892ab5ce76a309df81b3a4644be021f938eefddbd00ec4141e055c3cf735c9e04ce2fe9e950470a99d54cb6be43230110348a802a6a6c252
b1de59e896 fuzz: extract unsequenced operations with side-effects (Lőrinc)
Pull request description:
https://github.com/bitcoin/bitcoin/pull/30746#discussion_r1817851827 introduced unsequenced operations with side-effects - which is undefined behavior, i.e. the right hand side can be evaluated before the left hand side, which happens to mutate it.
<details>
<summary>Tried to find other occurrences</summary>
```bash
clang++ --analyze -std=c++20 -I./src -I./src/test -I./src/test/fuzz src/test/fuzz/base_encode_decode.cpp src/psbt.cpp
```
but it didn't warn about UB.
Grepped for similar ones, but could find any other one in the codebase:
```bash
> grep -rnE --include='*.cpp' --include='*.h' '\b(\w+)\(([^)]*\b(\w+)\b[^)]*)\)\s*==\s*\3\.' .
./src/test/arith_uint256_tests.cpp:373: BOOST_CHECK(R1L.GetHex() == R1L.ToString());
./src/test/arith_uint256_tests.cpp:374: BOOST_CHECK(R2L.GetHex() == R2L.ToString());
./src/test/arith_uint256_tests.cpp:375: BOOST_CHECK(OneL.GetHex() == OneL.ToString());
./src/test/arith_uint256_tests.cpp:376: BOOST_CHECK(MaxL.GetHex() == MaxL.ToString());
./src/test/fuzz/cluster_linearize.cpp:565: assert(depgraph.FeeRate(best_anc.transactions) == best_anc.feerate);
./src/test/fuzz/cluster_linearize.cpp:646: assert(depgraph.FeeRate(found.transactions) == found.feerate);
./src/test/fuzz/cluster_linearize.cpp:765: assert(depgraph.FeeRate(chunk_info.transactions) == chunk_info.feerate);
./src/test/fuzz/base_encode_decode.cpp:95: assert(DecodeBase64PSBT(psbt, random_string, error) == error.empty());
./src/test/fuzz/key.cpp:102: assert(pubkey.data() == pubkey.begin());
./src/test/skiplist_tests.cpp:42: BOOST_CHECK(vIndex[from].GetAncestor(0) == vIndex.data());
./src/script/signingprovider.cpp:535: ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) {
./src/pubkey.h:78: return vch.size() > 0 && GetLen(vch[0]) == vch.size();
./src/cluster_linearize.h:881: Assume(elem.inc.feerate.IsEmpty() == elem.pot_feerate.IsEmpty());
```
</details>
Hodlinator deduced the UB on Windows in https://github.com/bitcoin/bitcoin/issues/32135#issuecomment-2751723855Fixes#32135
ACKs for top commit:
maflcko:
lgtm ACK b1de59e896
hodlinator:
ACK b1de59e896
marcofleon:
Nice, ACK b1de59e896
brunoerg:
code review ACK b1de59e896
Tree-SHA512: d66524424c7f749eba870f5bd6038da79666ac638047b31dd8ff15a77d927facb54b4735e8afb7984648fdc9e2dd59ea213996c352301fa05978f041511361d4
963355037f depends: set CMAKE_*_COMPILER_TARGET in toolchain (fanquake)
Pull request description:
According to the CMake docs, this is the correct way to setup a toolchain file for cross-compilation using Clang. See https://cmake.org/cmake/help/latest/manual/cmake-toolchains.7.html#cross-compiling-using-clang
Internally it looks like CMake will only take this variable into account if it detects the compiler to be Clang, so this shouldn't effect other builds, but in the case of our Apple cross builds, we'd end up with a duplicated `--target=$ARCH-apple-darwin` on the compiler line, given we are already setting `--target` for Darwin builds.
Would fix#31748.
ACKs for top commit:
hebasto:
ACK 963355037f, tested on Ubuntu 24.10.
Tree-SHA512: 1aa0c5d9cb069ce277e53b5551baf5249c449331b0a160edb9a8ceb56209f886a9e2051e2ba63e0874904f652ace0280b7483dd5d81bfff9e993eb18abb961ad
0000fb3fd9 doc: Remove outdated and stale todo comment (MarcoFalke)
fa2b529f92 refactor: Remove redundant call to IsArgSet (MarcoFalke)
fa29842c1f refactor: Remove IsArgSet guard when fallback value is provided (MarcoFalke)
Pull request description:
`IsArgSet` is problematic:
* It returns whether an arg has been set, even if it has been negated. `IsArgSet` is sometimes used to check for a truthy value, which is wrong, but usually harmless. Cleanup of those cases may or may not be done in a follow-up.
* In most other cases, calling it is redundant, because the immediately following `Get*Arg` calls can already return an `std::optional` nullopt value to indicate an unset arg.
So relieve both issues by removing all `IsArgSet` that are redundant.
ACKs for top commit:
pablomartin4btc:
re-ACK 0000fb3fd9
ryanofsky:
Code review ACK 0000fb3fd9. No changes since last review other than rebase.
Tree-SHA512: d142d71d136b2dbd5fd005667875099777704176f5e08fdeb38f05d6afce40b435a257c5bb6a1f545459fe4f81f967cee3083ab666cb0befdef3f6234f1e3d32
fb2b05b125 build: Remove bitness suffix from Windows installer (Hennadii Stepanov)
Pull request description:
Since support for 32-bit Windows has been dropped, the suffix is no longer necessary.
ACKs for top commit:
l0rinc:
utACK fb2b05b125
hodlinator:
ACK fb2b05b125
laanwj:
ACK fb2b05b125
Tree-SHA512: cef18ddbc21bb8b57fd1f6b26d0c8bdee4aa47a20552c1f02ac7fcc084ab9887dcb2632c9e0915fbce156d843625aaad01a3ad5e11fbed56548e404719cc9a52
e3ce2bd982 Remove needless borrow to fix Clippy warning (dennsikl)
Pull request description:
Pull Request Description
**Summary**
Removes a needless borrow in `test/lint/test_runner/src/main.rs` that triggered a
Clippy warning (`needless_borrows_for_generic_args`). This minor refactoring
makes the code cleaner without changing functionality.
**Rationale**
- Eliminates a Clippy warning when running:
```bash
cargo clippy --manifest-path test/lint/test_runner/Cargo.toml -- -D warnings
ACKs for top commit:
maflcko:
lgtm ACK e3ce2bd982
kevkevinpal:
ACK [e3ce2bd](e3ce2bd982)
TheCharlatan:
ACK e3ce2bd982
Tree-SHA512: 9f3e07b45df0af6ad4bf87216b257108cc9b50b8e6bc591cac58b5cf6f78ebaeff27181cb0e8a6bc401626e1c707b925315f2e5ebd8dd5216e04c95d70237f85
b2ea365648 txgraph: Add Get{Ancestors,Descendants}Union functions (feature) (Pieter Wuille)
54bceddd3a txgraph: Multiple inputs to Get{Ancestors,Descendant}Refs (preparation) (Pieter Wuille)
aded047019 txgraph: Add CountDistinctClusters function (feature) (Pieter Wuille)
b685d322c9 txgraph: Add DoWork function (feature) (Pieter Wuille)
295a1ca8bb txgraph: Expose ability to compare transactions (feature) (Pieter Wuille)
22c68cd153 txgraph: Allow Refs to outlive the TxGraph (feature) (Pieter Wuille)
82fa3573e1 txgraph: Destroying Ref means removing transaction (feature) (Pieter Wuille)
6b037ceddf txgraph: Cache oversizedness of graphs (optimization) (Pieter Wuille)
8c70688965 txgraph: Add staging support (feature) (Pieter Wuille)
c99c7300b4 txgraph: Abstract out ClearLocator (refactor) (Pieter Wuille)
34aa3da5ad txgraph: Group per-graph data in ClusterSet (refactor) (Pieter Wuille)
36dd5edca5 txgraph: Special-case removal of tail of cluster (Optimization) (Pieter Wuille)
5801e0fb2b txgraph: Delay chunking while sub-acceptable (optimization) (Pieter Wuille)
57f5499882 txgraph: Avoid looking up the same child cluster repeatedly (optimization) (Pieter Wuille)
1171953ac6 txgraph: Avoid representative lookup for each dependency (optimization) (Pieter Wuille)
64f69ec8c3 txgraph: Make max cluster count configurable and "oversize" state (feature) (Pieter Wuille)
1d27b74c8e txgraph: Add GetChunkFeerate function (feature) (Pieter Wuille)
c80aecc24d txgraph: Avoid per-group vectors for clusters & dependencies (optimization) (Pieter Wuille)
ee57e93099 txgraph: Add internal sanity check function (tests) (Pieter Wuille)
05abf336f9 txgraph: Add simulation fuzz test (tests) (Pieter Wuille)
8ad3ed2681 txgraph: Add initial version (feature) (Pieter Wuille)
6eab3b2d73 feefrac: Introduce tagged wrappers to distinguish vsize/WU rates (Pieter Wuille)
d449773899 scripted-diff: (refactor) ClusterIndex -> DepGraphIndex (Pieter Wuille)
bfeb69f6e0 clusterlin: Make IsAcyclic() a DepGraph member function (Pieter Wuille)
0aa874a357 clusterlin: Add FixLinearization function + fuzz test (Pieter Wuille)
Pull request description:
Part of cluster mempool: #30289.
### 1. Overview
This introduces the `TxGraph` class, which encapsulates knowledge about the (effective) fees, sizes, and dependencies between all mempool transactions, but nothing else. In particular, it lacks knowledge about `CTransaction`, inputs, outputs, txids, wtxids, prioritization, validatity, policy rules, and a lot more. Being restricted to just those aspects of the mempool makes the behavior very easy to fully specify (ignoring the actual linearizations produced), and write simulation-based tests for (which are included in this PR).
### 2. Interface
The interface can be largely categorized into:
* Mutation functions:
* `AddTransaction` (add a new transaction with specified feerate, and get a `Ref` object back to identify it).
* `RemoveTransaction` (given a `Ref` object, remove the transaction).
* `AddDependency` (given two `Ref` objects, add a dependency between them).
* `SetTransactionFee` (modify the fee associated with a Ref object).
* Inspector functions:
* `GetAncestors` (get the ancestor set in the form of `Ref*` pointers)
* `GetAncestorsUnion` (like above, but for the union of ancestors of multiple `Ref*` pointers)
* `GetDescendants` (get the descendant set in the form of `Ref*` pointers)
* `GetDescendantsUnion` (like above, but for the union of ancestors of multiple `Ref*` pointers)
* `GetCluster` (get the connected component set in the form of `Ref*` pointers, in the order they would be mined).
* `GetIndividualFeerate` (get the feerate of a transaction)
* `GetChunkFeerate` (get the mining score of a transaction)
* `CountDistinctClusters` (count the number of distinct clusters a list of `Ref`s belong to)
* Staging functions:
* `StartStaging` (make all future mutations operate on a proposed transaction graph)
* `CommitStaging` (apply all the changes that are staged)
* `AbortStaging` (discard all the changes that are staged)
* Miscellaneous functions:
* `DoWork` (do queued-up computations now, so that future operations are fast)
This `TxGraph::Ref` type used as a "handle" on transactions in the graph can be inherited from, and the idea is that in the full cluster mempool implementation (#28676, after it is rebased on this), `CTxMempoolEntry` will inherit from it, and all actually used Ref objects will be `CTxMempoolEntry`s. With that, the mempool code can just cast any `Ref*` returned by txgraph to `CTxMempoolEntry*`.
### 3. Implementation
Internally the graph data is kept in clustered form (partitioned into connected components), for which linearizations are maintained and updated as needed using the `cluster_linearize.h` algorithms under the hood, but this is hidden from the users of this class. Implementation-wise, mutations are generally applied lazily, appending to queues of to-be-removed transactions and to-be-added dependencies, so they can be batched for higher performance. Inspectors will generally only evaluate as much as is needed to answer queries, with roughly 5 levels of processing to go to fully instantiated and acceptable cluster linearizations, in order:
1. `ApplyRemovals` (take batches of to-be-removed transactions and translate them to "holes" in the corresponding Clusters/DepGraphs).
2. `SplitAll` (creating holes in Clusters may cause them to break apart into smaller connected components, so make turn them into separate Clusters/linearizations).
3. `GroupClusters` (figure out which Clusters will need to be combined in order to add requested to-be-added dependencies, as these may span clusters).
4. `ApplyDependencies` (actually merge Clusters as precomputed by `GroupClusters`, and add the dependencies between them).
5. `MakeAcceptable` (perform the LIMO linearization algorithm on Clusters to make sure their linearizations are acceptable).
### 4. Future work
This is only an initial version of TxGraph, and some functionality is missing before #28676 can be rebased on top of it:
* The ability to get comparative feerate diagrams before/after for the set of staged changes (to evaluate RBF incentive-compatibility).
* Mining interface (ability to iterate transactions quickly in mining score order) (see #31444).
* Eviction interface (reverse of mining order, plus memory usage accounting) (see #31444).
* Ability to fix oversizedness of clusters (before or after committing) - this is needed for reorgs where aborting/rejecting the change just is not an option (see #31553).
* Interface for controlling how much effort is spent on LIMO. In this PR it is hardcoded.
Then there are further improvements possible which would not block other work:
* Making Cluster a virtual class with different implementations based on transaction count (which could dramatically reduce memory usage, as most Clusters are just a single transaction, for which the current implementation is overkill).
* The ability to have background thread(s) for improving cluster linearizations.
ACKs for top commit:
instagibbs:
reACK b2ea365648
ajtowns:
reACK b2ea365648
ismaelsadeeq:
reACK b2ea365648🚀
glozow:
ACK b2ea365648
Tree-SHA512: 0f86f73d37651fe47d469db1384503bbd1237b4556e5d50b1d0a3dd27754792d6fc3481f77a201cf2ed36c6ca76e0e44c30e175d112aacb53dfdb9e11d8abc6b
The 'FEE' parameter in test/functional/feature_dbcrash.py::
generate_small_transaction() is not a fee rate, but an
absolute fee. Hence, it doesn't make sense to replace it
with node relay based fee calculation. Get rid of the TODO
comment suggesting otherwise.
...interface_usdt_utxocache.py
We have encountered an instance where the tracepoints were not collected
in the same order they were fired (#31951).
Tracepoint ordering is not guaranteed in userspace for a number of
reasons.
As this test does not require a strict collection/processing order
collect `expected` and `actual` events into dicts and compare them.
This will gracefully handle both the number of events, and out-of-order
events should they reoccur in the future.
Update the example wherein the PSBT sends bitcoin to an address instead
of creating an OP_RETURN output. Also, update the RPC description to
reflect the fact that the created transaction is unsigned.
This affects docs of the following RPCs:
`bumpfee`, `psbtbumpfee`, `send`, `walletcreatefundedpsbt`, `createpsbt`,
and `createrawtransaction`
It was not evident to me that this field creates an `OP_RETURN` output until
I read the code and tried it out. Thus, making the doc explicitly mention it.
