PickValue will advance a begin iterator on the outpoints set, which is expensive, because it only has a ++ operator. As it is called in a loop of num_in (~outpoints.size()), the runtime is O(outpoints.size() ^ 2).
Fix it by making the runtime linear.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For detailed information about the code coverage, see the test coverage report.
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.
54@@ -55,10 +55,18 @@ FUZZ_TARGET(txorphan, .init = initialize_orphanage)
55 const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, 256);
56 // pick outpoints from outpoints as input. We allow input duplicates on purpose, given we are not
57 // running any transaction validation logic before adding transactions to the orphanage
58- for (uint32_t i = 0; i < num_in; i++) {
59- auto& prevout = PickValue(fuzzed_data_provider, outpoints);
60- // try making transactions unique by setting a random nSequence, but allow duplicate transactions if they happen
61- tx_mut.vin.emplace_back(prevout, CScript{}, fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, CTxIn::SEQUENCE_FINAL));
62+ {
63+ // Create copy of set to allow fast PickValue
We don't call PickValue on the outpoints set directly because PickValue will advance a begin iterator on the set, which is expensive, because it only has a "++" operator. As it would be called in a loop of num_in (~outpoints.size()), the runtime would be O(outpoints.size() ^ 2). Instead we create a std::vector copy of the set, which allows for O(1) std::advance..
I forgot to mention the fuzz input for testing. It is c6efad2b3a41cf2a2a682dabed1310bf5e3c101e. See https://cirrus-ci.com/task/6178647134961664?logs=ci#L4058
0Run txorphan with args ['/ci_container_base/ci/scratch/build/bitcoin-x86_64-pc-linux-gnu/src/test/fuzz/fuzz', '-runs=1', PosixPath('/ci_container_base/ci/scratch/qa-assets/fuzz_seed_corpus/txorphan')]INFO: Running with entropic power schedule (0xFF, 100).
1INFO: Seed: 3180047797
2INFO: Loaded 1 modules (623498 inline 8-bit counters): 623498 [0x55a9ae6a0518, 0x55a9ae7388a2),
3INFO: Loaded 1 PC tables (623498 PCs): 623498 [0x55a9ae7388a8,0x55a9af0bc148),
4INFO: 651 files found in /ci_container_base/ci/scratch/qa-assets/fuzz_seed_corpus/txorphan
5INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 1048576 bytes
6INFO: seed corpus: files: 651 min: 1b max: 2173657b total: 41752504b rss: 114Mb
7[#512](/bitcoin-bitcoin/512/) pulse cov: 2457 ft: 11189 corp: 262/885Kb exec/s: 170 rss: 280Mb
8Slowest unit: 13 s:
9artifact_prefix='./'; Test unit written to ./slow-unit-c6efad2b3a41cf2a2a682dabed1310bf5e3c101e
10[#652](/bitcoin-bitcoin/652/) INITED cov: 2514 ft: 12563 corp: 349/23Mb exec/s: 5 rss: 491Mb
11[#652](/bitcoin-bitcoin/652/) DONE cov: 2514 ft: 12563 corp: 349/23Mb lim: 978076 exec/s: 5 rss: 491Mb
12Done 652 runs in 117 second(s)
🚧 At least one of the CI tasks failed. Debug: https://github.com/bitcoin/bitcoin/runs/27602359666
Make sure to run all tests locally, according to the documentation.
The failure may 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.
54@@ -55,10 +55,27 @@ FUZZ_TARGET(txorphan, .init = initialize_orphanage)
55 const auto num_out = fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, 256);
56 // pick outpoints from outpoints as input. We allow input duplicates on purpose, given we are not
57 // running any transaction validation logic before adding transactions to the orphanage
58- for (uint32_t i = 0; i < num_in; i++) {
59- auto& prevout = PickValue(fuzzed_data_provider, outpoints);
60- // try making transactions unique by setting a random nSequence, but allow duplicate transactions if they happen
61- tx_mut.vin.emplace_back(prevout, CScript{}, fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(0, CTxIn::SEQUENCE_FINAL));
62+ {
outpoints definition to a vector instead?
Happy to push a change that changes this, if someone writes one. Also, I am happy to review a pull request doing the change, if someone opens one.
But this requires changing more lines of code, so I didn’t find it worthwhile to do by myself.
I meant simply:
0diff --git a/src/test/fuzz/txorphan.cpp b/src/test/fuzz/txorphan.cpp
1--- a/src/test/fuzz/txorphan.cpp (revision 37992244e636e52e0c2baff1bc5f36e60d9c956f)
2+++ b/src/test/fuzz/txorphan.cpp (date 1721306232235)
3@@ -37,11 +37,11 @@
4 SetMockTime(ConsumeTime(fuzzed_data_provider));
5
6 TxOrphanage orphanage;
7- std::set<COutPoint> outpoints;
8+ std::vector<COutPoint> outpoints;
9
10 // initial outpoints used to construct transactions later
11 for (uint8_t i = 0; i < 4; i++) {
12- outpoints.emplace(Txid::FromUint256(uint256{i}), 0);
13+ outpoints.emplace_back(Txid::FromUint256(uint256{i}), 0);
14 }
15
16 CTransactionRef ptx_potential_parent = nullptr;
17@@ -67,7 +67,7 @@
18 auto new_tx = MakeTransactionRef(tx_mut);
19 // add newly constructed outpoints to the coin pool
20 for (uint32_t i = 0; i < num_out; i++) {
21- outpoints.emplace(new_tx->GetHash(), i);
22+ outpoints.emplace_back(new_tx->GetHash(), i);
23 }
24 return new_tx;
25 }();
utACK fa030ad6b6c124f332cea071e16c1519ae7ea423
(could you please add me as co-author, l0rinc <pap.lorinc@gmail.com>?)
Co-Authored-By: l0rinc <pap.lorinc@gmail.com>
(could you please add me as co-author,
l0rinc <pap.lorinc@gmail.com>?)
Sure, done