Skip to content

feefrac: avoid explicitly computing diagram; compare based on chunks #29757

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 1 commit into from
Apr 24, 2024
Merged

feefrac: avoid explicitly computing diagram; compare based on chunks #29757

merged 1 commit into from
Apr 24, 2024

Conversation

sipa
Copy link
Member

@sipa sipa commented Mar 28, 2024 •
edited
Loading

This merges the BuildDiagramFromChunks and CompareFeeRateDiagram introduced in #29242 into a single CompareChunks function, which operates on sorted chunk data rather than diagrams, instead computing the diagram on the fly.

This avoids the need for the construction of an intermediary diagram object, and removes the slightly arbitrary "all diagrams must start at (0, 0)" requirement.

Not a big deal, but I think the result is a bit cleaner and not really more complicated.

@DrahtBot
Copy link
Contributor

DrahtBot commented Mar 28, 2024 •
edited
Loading

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, instagibbs

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

Conflicts

No conflicts as of last run.

@DrahtBot DrahtBot mentioned this pull request Mar 28, 2024
Merged
instagibbs
instagibbs reviewed Mar 29, 2024
View reviewed changes
Copy link
Member

@instagibbs instagibbs left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

approach ACK

this conflicts with #29724 so I'll give it a fuller treatment after

@sipa sipa force-pushed the 202403_implicit_diagram branch 2 times, most recently from b30395e to 4bf7e1a Compare March 30, 2024 02:06
@sipa
Copy link
Member Author

sipa commented Mar 30, 2024

Rebased after #29724, and made a few more minor code simplifications.

instagibbs
instagibbs approved these changes Apr 3, 2024
View reviewed changes
Copy link
Member

@instagibbs instagibbs left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK 4bf7e1a

didn't run fuzz tests

@sipa sipa force-pushed the 202403_implicit_diagram branch from 4bf7e1a to 43e2f6d Compare April 4, 2024 02:08
instagibbs
instagibbs approved these changes Apr 4, 2024
View reviewed changes
Copy link
Member

@instagibbs instagibbs left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK 43e2f6d

@DrahtBot DrahtBot removed the CI failed label Apr 4, 2024
glozow
glozow reviewed Apr 4, 2024
View reviewed changes
Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

code review ACK 43e2f6d

@bitcoin bitcoin deleted a comment from krisisnotok Apr 4, 2024
@sipa sipa force-pushed the 202403_implicit_diagram branch 2 times, most recently from a253f22 to c2fdcf4 Compare April 4, 2024 23:16
@instagibbs
Copy link
Member

ACK c2fdcf4

@DrahtBot DrahtBot requested a review from glozow April 5, 2024 05:52
glozow
glozow reviewed Apr 5, 2024
View reviewed changes
Copy link
Member

@glozow glozow left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

reACK c2fdcf4

@dergoegge
Copy link
Member

package_rbf crash (base64): rbf-2369c110673171b822af54ba3f33aabab58e7aeb.crash.txt

util/feefrac.cpp:44 CompareChunks: Assertion slope_ap.size > 0 failed.

@dergoegge
Copy link
Member

UBSan package_rbf crash (base64):
rbf-ubsan-fac11eca92adf89df0e6840e5faa58873144d98a.crash.txt

INFO: Running with entropic power schedule (0xFF, 100).
INFO: Seed: 3880912967
INFO: Loaded 1 modules   (756212 inline 8-bit counters): 756212 [0xaaaadcf1c108, 0xaaaadcfd4afc),
INFO: Loaded 1 PC tables (756212 PCs): 756212 [0xaaaadcfd4b00,0xaaaaddb5ea40),
/workdir/fuzz_bins/fuzz_libfuzzer_ubsan: Running 1 inputs 1 time(s) each.
Running: /workdir/crashes/fac11eca92adf89df0e6840e5faa58873144d98a
util/feefrac.h:84:14: runtime error: signed integer overflow: 2146794745 + 784680 cannot be represented in type 'int32_t' (aka 'int')
    #0 0xaaaada9508ac in FeeFrac::operator+=(FeeFrac const&) src/./util/feefrac.h:84:14
    #1 0xaaaada9508ac in package_rbf_fuzz_target(Span<unsigned char const>) src/test/fuzz/rbf.cpp:150:23
    #2 0xaaaadaaaee28 in std::function<void (Span<unsigned char const>)>::operator()(Span<unsigned char const>) const /usr/lib/gcc/aarch64-linux-gnu/13/../../../../include/c++/13/bits/std_function.h:591:9
    #3 0xaaaadaaaee28 in LLVMFuzzerTestOneInput src/test/fuzz/fuzz.cpp:180:5
    #4 0xaaaada28e6a8 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /llvm-project/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:614:13
    #5 0xaaaada27a0f0 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) /llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:324:6
    #6 0xaaaada27f3a8 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) /llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:859:9
    #7 0xaaaada2a9174 in main /llvm-project/compiler-rt/lib/fuzzer/FuzzerMain.cpp:20:10
    #8 0xffffaa4e6dc0  (/lib/aarch64-linux-gnu/libc.so.6+0x26dc0) (BuildId: dd6b2df07eec5dadc4ad6d330cdf600ad76785aa)
    #9 0xffffaa4e6e94 in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x26e94) (BuildId: dd6b2df07eec5dadc4ad6d330cdf600ad76785aa)
    #10 0xaaaada27226c in _start (/workdir/fuzz_bins/fuzz_libfuzzer_ubsan+0x291226c)

SUMMARY: UndefinedBehaviorSanitizer: signed-integer-overflow util/feefrac.h:84:14 in

@sipa
Copy link
Member Author

sipa commented Apr 11, 2024

@dergoegge Do those fuzz seeds trigger issues on master too?

@instagibbs
Copy link
Member

looks to be happening on master and I think both reports are from the same underlying issue. Investigating.

@maflcko
Copy link
Member

maflcko commented Apr 13, 2024

https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=68020#c1

@glozow glozow mentioned this pull request Apr 15, 2024
Open
42 tasks
@instagibbs instagibbs mentioned this pull request Apr 15, 2024
Merged
glozow added a commit that referenced this pull request Apr 22, 2024
@glozow
Merge #29879: fuzz: explicitly cap the vsize of RBFs for diagram checks
ba7c67f 
016ed24 fuzz: explicitly cap the vsize of RBFs for diagram checks (Greg Sanders)

Pull request description:

  In master we are hitting a case where vsize transactions much larger than max standard size are causing an overflow in not-yet-exposed RBF diagram checking code: #29757 (comment)

  `ConsumeTxMemPoolEntry` is creating entries with tens of thousands of sigops cost, causing the resulting RBFs to be "overly large".

  To fix this I cause the fuzz test to stop adding transactions to the mempool when we reach a potential overflow of `int32_t`.

ACKs for top commit:
  glozow:
    ACK 016ed24
  marcofleon:
    ACK 016ed24. I ran libFuzzer on `package_rbf` on the current master branch until the overflow was encountered. Then I built the PR branch and ran the fuzzer using the crash input.

Tree-SHA512: b3ffc98d2c4598eb3010edd58b9370aab1441aafbb1044c83b2b90c17dfe9135b8de9dba475dd0108863c1ffedede443cd978e95231a41cf1f0715629197fa51
@sipa sipa force-pushed the 202403_implicit_diagram branch from c2fdcf4 to b22901d Compare April 22, 2024 13:38
@sipa
Copy link
Member Author

sipa commented Apr 22, 2024

Rebased after the merge of #29879.

@glozow
Copy link
Member

glozow commented Apr 23, 2024

reACK b22901d

@DrahtBot DrahtBot requested a review from instagibbs April 23, 2024 15:57
instagibbs
instagibbs approved these changes Apr 23, 2024
View reviewed changes
Copy link
Member

@instagibbs instagibbs left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

reACK b22901d

@glozow glozow merged commit 2a07c46 into bitcoin:master Apr 24, 2024
@bitcoin bitcoin locked and limited conversation to collaborators Apr 24, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Reviewers

@glozow glozow glozow left review comments

+1 more reviewer

@instagibbs instagibbs instagibbs approved these changes

Reviewers whose approvals may not affect merge requirements
Assignees
No one assigned
Labels
Utils/log/libs
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
6 participants
@sipa @DrahtBot @instagibbs @dergoegge @maflcko @glozow