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.
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.
| 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.
No conflicts as of last run.
192@@ -193,13 +193,13 @@ std::optional<std::pair<DiagramCheckError, std::string>> ImprovesFeerateDiagram(
193 // Require that the replacement strictly improve the mempool's feerate diagram.
194 std::vector<FeeFrac> old_diagram, new_diagram;
195
196- const auto diagram_results{pool.CalculateFeerateDiagramsForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)};
197+ const auto diagram_results{pool.CalculateChunksForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)};
diagram_results seems a bit off, and references to diagrams being returned for CalculateChunksForRBF in declaration, etc.
approach ACK
this conflicts with #29724 so I’ll give it a fuller treatment after
156+ * The implied diagram for each starts at (0, 0), then contains for each chunk the cumulative fee
157+ * and size up to that chunk, and then extends infinitely to the right with a horizontal line.
158 *
159- * A feerate diagram consists of a list of (fee, size) points with the property that size
160- * is strictly increasing and that the first entry is (0, 0).
161+ * The sum of the FeeFracs in either of the chunks data sets cannot overflow (sum fees < 2^63,
0 * The sum of the FeeFracs in either of the chunks' data sets cannot overflow (sum fees < 2^63,
179 }
180- // The total fee of the new diagram should be the total fee of the old
181- // diagram - replaced_fee + replacement_fees
182- assert(calc_results->first.back().fee - replaced_fee + replacement_fees == calc_results->second.back().fee);
183- assert(calc_results->first.back().size - replaced_size + replacement_vsize == calc_results->second.back().size);
184+ // The total fee & size of the new diagram minus replaced fee &size should be the total fee & size of the old
0 // The total fee & size of the new diagram minus replaced fee & size should be the total fee & size of the old
ACK 4bf7e1a005853cb57ae3a051bcdfc5c149b1f1db
didn’t run fuzz tests
135@@ -147,33 +136,34 @@ FUZZ_TARGET(package_rbf, .init = initialize_package_rbf)
136 pool.CalculateDescendants(txiter, all_conflicts);
137 }
138
139- // Calculate the feerate diagrams for a replacement.
140+ // Calculate the chunks for a replacement.
141 CAmount replacement_fees = ConsumeMoney(fuzzed_data_provider);
142- int64_t replacement_vsize = fuzzed_data_provider.ConsumeIntegralInRange<int64_t>(1, 1000000);
143- auto calc_results{pool.CalculateFeerateDiagramsForRBF(replacement_fees, replacement_vsize, direct_conflicts, all_conflicts)};
144+ int32_t replacement_vsize = fuzzed_data_provider.ConsumeIntegralInRange<int32_t>(1, 1000000);
FeeFrac::size field is an int32_t, which allows using the FeeFrac{replacement_fees, replacement_vsize} constructor below.
116- BOOST_CHECK(generated_diagram[0] == empty);
117- BOOST_CHECK(generated_diagram[1] == empty);
118- BOOST_CHECK(generated_diagram[2] == oversized_2);
119- BOOST_CHECK(generated_diagram[3] == oversized_2 + oversized_1);
120- BOOST_CHECK(generated_diagram[4] == oversized_2 + oversized_1 + p1);
121- BOOST_CHECK(generated_diagram[5] == oversized_2 + oversized_1 + p1 + zero_fee);
build_diagram_test any more, and comparison of oversized chunks is already tested above.
package_rbf crash (base64): rbf-2369c110673171b822af54ba3f33aabab58e7aeb.crash.txt
util/feefrac.cpp:44 CompareChunks: Assertion slope_ap.size > 0 failed.
UBSan package_rbf crash (base64):
rbf-ubsan-fac11eca92adf89df0e6840e5faa58873144d98a.crash.txt
0INFO: Running with entropic power schedule (0xFF, 100).
1INFO: Seed: 3880912967
2INFO: Loaded 1 modules (756212 inline 8-bit counters): 756212 [0xaaaadcf1c108, 0xaaaadcfd4afc),
3INFO: Loaded 1 PC tables (756212 PCs): 756212 [0xaaaadcfd4b00,0xaaaaddb5ea40),
4/workdir/fuzz_bins/fuzz_libfuzzer_ubsan: Running 1 inputs 1 time(s) each.
5Running: /workdir/crashes/fac11eca92adf89df0e6840e5faa58873144d98a
6util/feefrac.h:84:14: runtime error: signed integer overflow: 2146794745 + 784680 cannot be represented in type 'int32_t' (aka 'int')
7 [#0](/bitcoin-bitcoin/0/) 0xaaaada9508ac in FeeFrac::operator+=(FeeFrac const&) src/./util/feefrac.h:84:14
8 [#1](/bitcoin-bitcoin/1/) 0xaaaada9508ac in package_rbf_fuzz_target(Span<unsigned char const>) src/test/fuzz/rbf.cpp:150:23
9 [#2](/bitcoin-bitcoin/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
10 [#3](/bitcoin-bitcoin/3/) 0xaaaadaaaee28 in LLVMFuzzerTestOneInput src/test/fuzz/fuzz.cpp:180:5
11 [#4](/bitcoin-bitcoin/4/) 0xaaaada28e6a8 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) /llvm-project/compiler-rt/lib/fuzzer/FuzzerLoop.cpp:614:13
12 [#5](/bitcoin-bitcoin/5/) 0xaaaada27a0f0 in fuzzer::RunOneTest(fuzzer::Fuzzer*, char const*, unsigned long) /llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:324:6
13 [#6](/bitcoin-bitcoin/6/) 0xaaaada27f3a8 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) /llvm-project/compiler-rt/lib/fuzzer/FuzzerDriver.cpp:859:9
14 [#7](/bitcoin-bitcoin/7/) 0xaaaada2a9174 in main /llvm-project/compiler-rt/lib/fuzzer/FuzzerMain.cpp:20:10
15 [#8](/bitcoin-bitcoin/8/) 0xffffaa4e6dc0 (/lib/aarch64-linux-gnu/libc.so.6+0x26dc0) (BuildId: dd6b2df07eec5dadc4ad6d330cdf600ad76785aa)
16 [#9](/bitcoin-bitcoin/9/) 0xffffaa4e6e94 in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x26e94) (BuildId: dd6b2df07eec5dadc4ad6d330cdf600ad76785aa)
17 [#10](/bitcoin-bitcoin/10/) 0xaaaada27226c in _start (/workdir/fuzz_bins/fuzz_libfuzzer_ubsan+0x291226c)
18
19SUMMARY: UndefinedBehaviorSanitizer: signed-integer-overflow util/feefrac.h:84:14 in
