Make TxGraph fuzz tests more deterministic #32191

Part of cluster mempool: #30289

The implicit transaction ordering for transactions in a TxGraphImpl is defined by:

1. higher chunk feerate first
2. lower Cluster* object pointer first
3. lower position within cluster linearization first.

Number (2) is not deterministic, as it intricately depends on the heap allocation algorithm. Fix this by giving each Cluster a unique uint64_t m_sequence value, and sorting by those instead.

The second commit then uses this new approach to optimize GroupClusters a bit more, avoiding some repeated checks and dereferences, by making a local copy of the involved sequence numbers.

Thanks to @dergoegge for pointing this out.

<!--e57a25ab6845829454e8d69fc972939a-->

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

<!--006a51241073e994b41acfe9ec718e94-->

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32191.

<!--021abf342d371248e50ceaed478a90ca-->

Reviews

See the guideline for information on the review process.

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

<!--174a7506f384e20aa4161008e828411d-->

Conflicts

Reviewers, this pull request conflicts with the following ones:

• #32263 (cluster mempool: add TxGraph work controls by sipa)
• #31553 (cluster mempool: add TxGraph reorg functionality by sipa)
• #31444 (cluster mempool: add txgraph diagrams/mining/eviction by sipa)
• #28676 ([WIP] Cluster mempool implementation by sdaftuar)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

looks good, just a few cleanups suggested 631244831ba273fe72c6803f531bc344d0bf1579

confirmed that no sorts remain based on pointers

ACK 3796c16550938fc09fa560d7060b3626506ce526

Couple of typos and one last Assume that'd be nice

git range-diff master 631244831ba273fe72c6803f531bc344d0bf1579 3796c16550938fc09fa560d7060b3626506ce526

ACK https://github.com/bitcoin/bitcoin/pull/32191/commits/133813c503f2894c36442ec5a34c466d95961f45

Not sure if you just want to make it more determinisic, or fully deterministic, but I ran:

git rebase bitcoin-core/master
rm -rf ./bld-cmake && cmake -B ./bld-cmake  -DCMAKE_C_COMPILER='clang' -DCMAKE_CXX_COMPILER='clang++;-stdlib=libc++' -DBUILD_FOR_FUZZING=ON    -DCMAKE_CXX_FLAGS='-fprofile-instr-generate -fcoverage-mapping'                && cmake --build ./bld-cmake
cargo run --manifest-path ./contrib/devtools/deterministic-fuzz-coverage/Cargo.toml -- $PWD/bld-cmake/ $PWD/../b-c-qa-assets/fuzz_corpora/ txgraph  32

I only ran it on a subset of the files txgraph/00* for a few times, and it printed: The coverage was not deterministic between runs.

The output had too little context, so I re-created it with more context:

$ git diff -U9 --no-index  -- bld-cmake/fuzz_det_cov.show.t0.*.txt
diff --git a/bld-cmake/fuzz_det_cov.show.t0.a.txt b/bld-cmake/fuzz_det_cov.show.t0.b.txt
index 0f4fcc3a1d..d5e901bd30 100644
--- a/bld-cmake/fuzz_det_cov.show.t0.a.txt
+++ b/bld-cmake/fuzz_det_cov.show.t0.b.txt
@@ -265929,20 +265929,20 @@
   ------------------
   330|     19|            return (a != nullptr) <=> (b != nullptr);
   331|     19|        }
   332|       |        // If neither pointer is nullptr, compare the Clusters' sequence numbers.
   333|  2.37k|        Assume(a == b || a->m_sequence != b->m_sequence);
   ------------------
   |  |   97|  3.55k|#define Assume(val) inline_assertion_check<false>(val, __FILE__, __LINE__, __func__, #val)
   |  |                                  ^2.37k                             ^2.37k    ^2.37k              ^2.37k
   |  |  ------------------
-  |  |  |  Branch (97:51): [True: 1.19k, False: 1.17k]
-  |  |  |  Branch (97:51): [True: 1.17k, False: 0]
+  |  |  |  Branch (97:51): [True: 1.19k, False: 1.18k]
+  |  |  |  Branch (97:51): [True: 1.18k, False: 0]
   |  |  ------------------
   ------------------
   334|  2.37k|        return a->m_sequence <=> b->m_sequence;
   335|  2.39k|    }
   336|       |
   337|       |public:
   338|       |    /** Construct a new TxGraphImpl with the specified maximum cluster count. */
   339|       |    explicit TxGraphImpl(DepGraphIndex max_cluster_count) noexcept :
   340|      7|        m_max_cluster_count(max_cluster_count)
@@ -266889,23 +266889,23 @@
   974|     32|                auto cluster = FindCluster(index, level);
   975|     32|                if (cluster != nullptr) PullIn(cluster);
                                                       ^30
   ------------------
   |  Branch (975:21): [True: 30, False: 2]
   ------------------
   976|     32|            }
   977|      5|        }
   978|       |        // Group the set of to-be-removed entries by Cluster::m_sequence.
-  979|     93|        std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept {
-  980|     93|            Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
-  981|     93|            Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
-  982|     93|            return CompareClusters(cluster_a, cluster_b) < 0;
-  983|     93|        });
+  979|     94|        std::sort(to_remove.begin(), to_remove.end(), [&](GraphIndex a, GraphIndex b) noexcept {
+  980|     94|            Cluster* cluster_a = m_entries[a].m_locator[level].cluster;
+  981|     94|            Cluster* cluster_b = m_entries[b].m_locator[level].cluster;
+  982|     94|            return CompareClusters(cluster_a, cluster_b) < 0;
+  983|     94|        });
   984|       |        // Process per Cluster.
   985|     28|        std::span to_remove_span{to_remove};
   986|     78|        while (!to_remove_span.empty()) {
   ------------------

This only shows the symptom. That is, a == b does not hold for the same amount of times, even when running over the same set of files. Not sure why that is, though.

For reference, the two inputs I ran against:

sh-5.2$ base64 ./txgraph/00dc359d7b7edffe613622aa7f592960eb4db15d
//9/f///f6wAZIw7AAap5QBkiDsABqnlAAaqq5UABqvTAAauQgAGrJsABq085AatAAAAAAASBrkn
AAa6NgAAAAAAAAatPOQGrdcABq5ZAAaYAAcwVQAHOf4AB+Q6AAc7BqybAAatPOQGrdcABq5ZAAaY
AAcwVQAHOf4AB+Q6AAc7Pwa2JgAGtsAABrd8AAbRagAAAAAAAAAAEga5JwAGujYABgBSAH84lgAH
OUjXBzn+BqqrlQAGq9MABq5CAAasmwAGrQAHOuQABzs/AAc7hQAHCidF9P85lgAHOVUABzn+AAc6
5AAHOz8ABzvlAAaKq1oABgrTAAauQgAGrJsABgCtAGUA1wAGrlkABpgAAAAAAACpAAAAAAAAAAAA
AAAAAAAAAAAAAP////8AAABrAAAAAAAAAAAAAAAAAAAAAAAAAAAA/+oAAAAAAAAAAAAAAAAAAAAA
/+oAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAC0xwAGtXMABrYmAga2AAAAAAAA+///////1ato
cgAAAAAAAAAAAAAAAAAAYBEAAAdg3/////8sAP//

sh-5.2$ base64 ./txgraph/0002cb30d28317066ed82c933c477212d1680c53
//9/f///f6wAZIw7AAap5QBkiDsABqnlAAaqq5UABqvTAAauQgAGrJsABq085AatAAAAAAASBrkn
AAa6NgAGAFIAfzjx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx8fHx
8fE7AAap5QAGqquVAAar0wAGrkoABqybAAYAAAAAAAAAAPHx8fHx8fHx8QAAAAAAAAAAAAAAAAAW
AAAADgAAABUAAAASAAAAEwAAACMAAAAcAAAAJgAAADIRAAAAHVXPRlXPRkZVVc/PRlXPRs/PRlVG
Ws/PBgAAAAUAAAACAAAAAAAAAAAAABgKAAAAAAAAABAAAAAMAAAACAAAAA8AAAAEAAAADQAAACEA
AAAAAAAAAQAAAAkAAAALAAAABwoHRQQANJYABzlVAAaqq5UABqvTAAauQgAGrJsABq085Aat1wAG
rlkABpgAnTBVAAc5/gAHOuQABzs/BrYmAAa2wAAGt3wABtFqAAAHAAAAAAASBrknAAa6NgAGAFIA
fziWAAc5SNcHOf4ABzrkAAc7PwAHO4UABwonRfT/OJYABzlVAAc5/gAHOuQABzs/AAc75QAGqqta
AAar0wAGrkIABqybAAYAAABlrdcABgCumAZZAAAAAAAAqQAAAAAAAAAAAAAAAAAAAAAAAAD/////
AAAAawAAAAAAAAAAAAAAAAAAAAAAAAAAAP/qAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAtMcA
BrVzAAa2JgIGtgAAAAAAAAAAAAAAACpUaHIAQAAAAAAAAAAAAC4AAAA/AAAAJwAAABEAAAAJAAAA
AAAAADwAAAAIAAAAFQAAADkAAAATAAAAEAAAADYAAAACAAAAHQAAADAAAAAAAAAAAABdKQAHXnkA
B18AAABKAAdgEQAAB2Df/////ywA//8=

@maflcko Huh, interesting, will investigate. TxGraphImpl does hold a default-constructed FastRandomContext, but those should within the fuzz tests be seeded deterministically now, right?

Yes, as long as the random context is not global, it should be fine.

@maflcko Fixed, I think! There was another pointer comparison in the fuzz test itself.

+++ b/src/test/fuzz/txgraph.cpp
@@ -206,11 +206,14 @@ struct SimTxGraph
                 ret.push_back(ptr);
             }
         }
-        // Deduplicate.
-        std::sort(ret.begin(), ret.end());
-        ret.erase(std::unique(ret.begin(), ret.end()), ret.end());
-        // Replace input.
-        arg = std::move(ret);
+        // Construct deduplicated version in input (do not use std::sort/std::unique for
+        // deduplication as it'd rely on non-deterministic pointer comparison).
+        arg.clear();
+        for (auto ptr : ret) {
+            if (std::find(arg.begin(), arg.end(), ptr) == arg.end()) {
+                arg.push_back(ptr);
+            }
+        }
     }
 };

Nice. cargo run --manifest-path ./contrib/devtools/deterministic-fuzz-coverage/Cargo.toml -- $PWD/bld-cmake/ $PWD/../b-c-qa-assets/fuzz_corpora/ txgraph 32 from above looks stable now for me.

@maflcko Great, nice tool. I tried it as well with a hastily-constructed txgraph corpus (after -set_cover_merge=1'ing it from 30000 to 700 files), and found no issues.

reACK 2835216ec09cc2d86b091824376b15601e7c7b8a

good catch, didn't check the fuzzer harness for sorts like I did TxGraph itself...

git range-diff master 133813c503f2894c36442ec5a34c466d95961f45 2835216ec09cc2d86b091824376b15601e7c7b8a

ACK 2835216ec09cc2d86b091824376b15601e7c7b8a

On master, using an old corpus, AFL++ shows 30% stability. On this PR, after generating a new corpus (~20 cpu hours), AFL++ is showing 93%. I also ran the determinism script several times using the new corpus and it's passed every time.

utACK 2835216ec09cc2d86b091824376b15601e7c7b8a

5167170015919920