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.
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--006a51241073e994b41acfe9ec718e94-->
For detailed information about the code coverage, see the test coverage report.
<!--021abf342d371248e50ceaed478a90ca-->
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
Perhaps a more descriptive comment would be good, e.g.: 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..
Thanks, done!
I forgot to mention the fuzz input for testing. It is c6efad2b3a41cf2a2a682dabed1310bf5e3c101e. See https://cirrus-ci.com/task/6178647134961664?logs=ci#L4058
Run 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).
INFO: Seed: 3180047797
INFO: Loaded 1 modules (623498 inline 8-bit counters): 623498 [0x55a9ae6a0518, 0x55a9ae7388a2),
INFO: Loaded 1 PC tables (623498 PCs): 623498 [0x55a9ae7388a8,0x55a9af0bc148),
INFO: 651 files found in /ci_container_base/ci/scratch/qa-assets/fuzz_seed_corpus/txorphan
INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 1048576 bytes
INFO: seed corpus: files: 651 min: 1b max: 2173657b total: 41752504b rss: 114Mb
[#512](/bitcoin-bitcoin/512/) pulse cov: 2457 ft: 11189 corp: 262/885Kb exec/s: 170 rss: 280Mb
Slowest unit: 13 s:
artifact_prefix='./'; Test unit written to ./slow-unit-c6efad2b3a41cf2a2a682dabed1310bf5e3c101e
[#652](/bitcoin-bitcoin/652/) INITED cov: 2514 ft: 12563 corp: 349/23Mb exec/s: 5 rss: 491Mb
[#652](/bitcoin-bitcoin/652/) DONE cov: 2514 ft: 12563 corp: 349/23Mb lim: 978076 exec/s: 5 rss: 491Mb
Done 652 runs in 117 second(s)
utACK fa4e7964792255a34df4813c834aaa2f8ca53e46
<!--85328a0da195eb286784d51f73fa0af9-->
🚧 At least one of the CI tasks failed. <sub>Debug: https://github.com/bitcoin/bitcoin/runs/27602359666</sub>
<details><summary>Hints</summary>
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.
</details>
Re-running known Wine CI 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 | + {
Since a random access vector seems to resolve the problem, is there any reason we cannot change the 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:
diff --git a/src/test/fuzz/txorphan.cpp b/src/test/fuzz/txorphan.cpp
--- a/src/test/fuzz/txorphan.cpp (revision 37992244e636e52e0c2baff1bc5f36e60d9c956f)
+++ b/src/test/fuzz/txorphan.cpp (date 1721306232235)
@@ -37,11 +37,11 @@
SetMockTime(ConsumeTime(fuzzed_data_provider));
TxOrphanage orphanage;
- std::set<COutPoint> outpoints;
+ std::vector<COutPoint> outpoints;
// initial outpoints used to construct transactions later
for (uint8_t i = 0; i < 4; i++) {
- outpoints.emplace(Txid::FromUint256(uint256{i}), 0);
+ outpoints.emplace_back(Txid::FromUint256(uint256{i}), 0);
}
CTransactionRef ptx_potential_parent = nullptr;
@@ -67,7 +67,7 @@
auto new_tx = MakeTransactionRef(tx_mut);
// add newly constructed outpoints to the coin pool
for (uint32_t i = 0; i < num_out; i++) {
- outpoints.emplace(new_tx->GetHash(), i);
+ outpoints.emplace_back(new_tx->GetHash(), i);
}
return new_tx;
}();
Yeah, I guess, given that duplicates are tolerated either way
Agree that using a vector (i.e. the 3-line diff) does seem like it solves this problem in a simpler + faster way. Having duplicate outpoints should be fine and maybe even more coverage. Fuzzed with the 3-line diff for a bit.
Thanks, done!
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
ACK fa33a63bd9458f3487a0592983c1363cd30a3c74, thanks for taking the suggestion
utACK fa33a63bd9458f3487a0592983c1363cd30a3c74