fuzz: Speed up PickValue in txorphan #30474

pull maflcko wants to merge 1 commits into bitcoin:master from maflcko:2407-fuzz-txo changing 1 files +4 −4
  1. maflcko commented at 2:44 pm on July 17, 2024: member

    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.

  2. DrahtBot commented at 2:44 pm on July 17, 2024: contributor

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

    Code Coverage

    For detailed information about the code coverage, see the test coverage report.

    Reviews

    See the guideline for information on the review process.

    Type Reviewers
    ACK glozow, dergoegge
    Stale ACK paplorinc

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

  3. DrahtBot added the label Tests on Jul 17, 2024
  4. in src/test/fuzz/txorphan.cpp:59 in fabd2c4726 outdated
    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
    


    dergoegge commented at 7:41 am on July 18, 2024:
    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..

    maflcko commented at 7:50 am on July 18, 2024:
    Thanks, done!
  5. maflcko commented at 7:46 am on July 18, 2024: member

    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)
    

    Screenshot from 2024-07-18 09-45-16

  6. maflcko force-pushed on Jul 18, 2024
  7. dergoegge approved
  8. dergoegge commented at 8:09 am on July 18, 2024: member
    utACK fa4e7964792255a34df4813c834aaa2f8ca53e46
  9. DrahtBot added the label CI failed on Jul 18, 2024
  10. DrahtBot commented at 9:16 am on July 18, 2024: contributor

    🚧 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.

  11. maflcko commented at 9:20 am on July 18, 2024: member
    Re-running known Wine CI failure.
  12. DrahtBot removed the label CI failed on Jul 18, 2024
  13. in src/test/fuzz/txorphan.cpp:58 in fa4e796479 outdated
    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+            {
    


    paplorinc commented at 12:43 pm on July 18, 2024:
    Since a random access vector seems to resolve the problem, is there any reason we cannot change the outpoints definition to a vector instead?

    maflcko commented at 1:27 pm on July 18, 2024:

    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.


    paplorinc commented at 1:50 pm on July 18, 2024:

    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         }();
    

    maflcko commented at 1:55 pm on July 18, 2024:
    Yeah, I guess, given that duplicates are tolerated either way

    glozow commented at 4:53 pm on July 18, 2024:
    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.

    maflcko commented at 6:44 am on July 23, 2024:
    Thanks, done!
  14. glozow commented at 9:12 am on July 19, 2024: member
    concept ACK, thanks @maflcko!
  15. maflcko force-pushed on Jul 23, 2024
  16. paplorinc commented at 7:31 am on July 23, 2024: contributor

    utACK fa030ad6b6c124f332cea071e16c1519ae7ea423

    (could you please add me as co-author, l0rinc <pap.lorinc@gmail.com>?)

  17. DrahtBot requested review from glozow on Jul 23, 2024
  18. DrahtBot requested review from dergoegge on Jul 23, 2024
  19. fuzz: Speed up PickValue in txorphan
    Co-Authored-By: l0rinc <pap.lorinc@gmail.com>
    fa33a63bd9
  20. maflcko force-pushed on Jul 23, 2024
  21. maflcko commented at 8:39 am on July 23, 2024: member

    (could you please add me as co-author, l0rinc <pap.lorinc@gmail.com>?)

    Sure, done

  22. glozow commented at 9:15 am on July 23, 2024: member
    ACK fa33a63bd9458f3487a0592983c1363cd30a3c74, thanks for taking the suggestion
  23. DrahtBot requested review from paplorinc on Jul 23, 2024
  24. dergoegge approved
  25. dergoegge commented at 9:25 am on July 23, 2024: member
    utACK fa33a63bd9458f3487a0592983c1363cd30a3c74
  26. fanquake merged this on Jul 23, 2024
  27. fanquake closed this on Jul 23, 2024

  28. maflcko deleted the branch on Jul 23, 2024

github-metadata-mirror

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: 2024-10-18 04:12 UTC

This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me