-
Notifications
You must be signed in to change notification settings - Fork 37.7k
coins: fix cachedCoinsUsage
accounting in CCoinsViewCache
#32313
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.
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
base: master
Are you sure you want to change the base?
Conversation
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. Code Coverage & BenchmarksFor details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32313. ReviewsSee the guideline for information on the review process. ConflictsReviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first. |
src/coins.cpp
Outdated
@@ -195,6 +201,7 @@ bool CCoinsViewCache::BatchWrite(CoinsViewCacheCursor& cursor, const uint256 &ha | |||
// and mark it as dirty. | |||
itUs = cacheCoins.try_emplace(it->first).first; | |||
CCoinsCacheEntry& entry{itUs->second}; | |||
cachedCoinsUsage -= entry.coin.DynamicMemoryUsage(); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The entry has an empty coin here, it was just created. So this is just subtracting zero.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Thanks, I'll add an assert in that case to explain why this branch wasn't symmetric with the other one.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't think we should add an assert here to explain. The comment right above says Create the coin in the parent cache
.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Doesn't the presence of the original cache-usage-update indicate that the comment isn't enough?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Sorry, what is the original cache-usage-update? AFAICT this line was added in this PR, and there is no cache-usage-update here?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I prefer code over comments (the comment can be wrong, the code validates) - and since the usual pattern is basically:
cachedCoinsUsage -= itUs->second.coin.DynamicMemoryUsage();
if (cursor.WillErase(*it)) {
itUs->second.coin = std::move(it->second.coin);
} else {
itUs->second.coin = it->second.coin;
}
cachedCoinsUsage += itUs->second.coin.DynamicMemoryUsage();
it makes sense to explain (via code) why here we don't need the first part:
assert(entry.coin.DynamicMemoryUsage() == 0); // i.e. we didn't forget the symmetry, it's on purpose
if (cursor.WillErase(*it)) {
entry.coin = std::move(it->second.coin);
} else {
entry.coin = it->second.coin;
}
cachedCoinsUsage += entry.coin.DynamicMemoryUsage();
Do you still think we don't need it?
4bd4805
to
763be0a
Compare
cachedCoinsUsage
usages in CCoinsViewCache
cachedCoinsUsage
usages in CCoinsViewCache
Rebased to allow CI running the new tests. |
763be0a
to
a0468a8
Compare
cachedCoinsUsage
usages in CCoinsViewCache
cachedCoinsUsage
usages in CCoinsViewCache
cachedCoinsUsage
usages in CCoinsViewCache
cachedCoinsUsage
accounting in CCoinsViewCache
@@ -46,9 +46,6 @@ unsigned-integer-overflow:CRollingBloomFilter::insert | |||
unsigned-integer-overflow:RollingBloomHash | |||
unsigned-integer-overflow:CCoinsViewCache::AddCoin | |||
unsigned-integer-overflow:CCoinsViewCache::BatchWrite | |||
unsigned-integer-overflow:CCoinsViewCache::DynamicMemoryUsage | |||
unsigned-integer-overflow:CCoinsViewCache::SpendCoin | |||
unsigned-integer-overflow:CCoinsViewCache::Uncache |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
it would be better to file this separately and explain why it isn't needed (or rather since when)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
They were introduced in https://github.com/bitcoin/bitcoin/pull/28865/files#diff-bca63b54ad7fcc2df12f3237fd8775810c1b849c49110f702920655778fcc248R45-R49, I don't see any concrete explanation for what the problem was - and couldn't reproduce any fuzzing problem when I've removed these.
@fanquake, can you help us out here, do you remember why these were added?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I ran the following on Linux for a1fe87eb668e8a1eeeef335951547882b5fb52d8
:
cmake --preset=libfuzzer && cmake --build build_fuzz && \
FUZZ=coin_grinder build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coin_grinder_is_optimal build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coincontrol build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coins_deserialize build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coins_view build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coinscache_sim build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coinselection_bnb build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coinselection_knapsack build_fuzz/bin/fuzz -runs=500000 && \
FUZZ=coinselection_srd build_fuzz/bin/fuzz -runs=500000
They all passed (actually ran a few until -runs=1000000
but got bored at the end).
Am I missing anything important here?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Am I missing anything important here?
Yes, the preset doesn't check for those. You'll have to run with the integer sanitizer to be able to detect integer sanitizer issues.
The testing steps are also explained in the comment: #28865 (comment)
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
As mentioned in #32296 (comment), I can't always reproduce these locally, it's why I used the CI to verify why these were needed in the first place.
I have tried every combination I could think of locally, I couldn't reproduce any such errors in coins. If you can, please let me know how to do that exactly.
Is there any other CI run I should be looking at to see if there are other failures?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Whenever I tried going back to pre-cmake times, I couldn't get it to compile and run again (on Mac or on Linux). Not the first time I try to do a git bisect, but it always turns bad really quickly.
I tried pushing a PR to my fork with the original PR that introduced the suppressions + removing DynamicMemoryUsage
, SpendCoin
and Uncache
suppressionss from ubsan.
The build is failing with similar problems that I see locally but don't see any unsigned-integer-overflow
complaints. #28865 l0rinc#10
Can you give me a hint of what else to try?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
They were introduced in https://github.com/bitcoin/bitcoin/pull/28865/files#diff-bca63b54ad7fcc2df12f3237fd8775810c1b849c49110f702920655778fcc248R45-R49,
@fanquake, can you help us out here, do you remember why these were added?
You can recreate the failures by checking out to that commit (fd30e96), applying this diff (which includes the supression being done here):
diff --git a/ci/test/00_setup_env_native_fuzz.sh b/ci/test/00_setup_env_native_fuzz.sh
index 3585b2b417..ce45917e99 100755
--- a/ci/test/00_setup_env_native_fuzz.sh
+++ b/ci/test/00_setup_env_native_fuzz.sh
@@ -6,7 +6,7 @@
export LC_ALL=C.UTF-8
-export CI_IMAGE_NAME_TAG="docker.io/ubuntu:23.10" # This version will reach EOL in Jul 2024, and can be replaced by "ubuntu:24.04" (or anything else that ships the wanted clang version).
+export CI_IMAGE_NAME_TAG="docker.io/ubuntu:24.04" # This version will reach EOL in Jul 2024, and can be replaced by "ubuntu:24.04" (or anything else that ships the wanted clang version).
export CONTAINER_NAME=ci_native_fuzz
export PACKAGES="clang-17 llvm-17 libclang-rt-17-dev libevent-dev libboost-dev libsqlite3-dev"
export NO_DEPENDS=1
diff --git a/test/sanitizer_suppressions/ubsan b/test/sanitizer_suppressions/ubsan
index 63d2215aab..d3fc2a59ff 100644
--- a/test/sanitizer_suppressions/ubsan
+++ b/test/sanitizer_suppressions/ubsan
@@ -42,11 +42,6 @@ unsigned-integer-overflow:arith_uint256.h
unsigned-integer-overflow:CBloomFilter::Hash
unsigned-integer-overflow:CRollingBloomFilter::insert
unsigned-integer-overflow:RollingBloomHash
-unsigned-integer-overflow:CCoinsViewCache::AddCoin
-unsigned-integer-overflow:CCoinsViewCache::BatchWrite
-unsigned-integer-overflow:CCoinsViewCache::DynamicMemoryUsage
-unsigned-integer-overflow:CCoinsViewCache::SpendCoin
-unsigned-integer-overflow:CCoinsViewCache::Uncache
unsigned-integer-overflow:CompressAmount
unsigned-integer-overflow:DecompressAmount
unsigned-integer-overflow:crypto/
and running the native_fuzz CI job (on aarch64):
time env -i HOME="$HOME" PATH="$PATH" USER="$USER" bash -c 'MAKEJOBS="-j17" FILE_ENV="./ci/test/00_setup_env_native_fuzz.sh" ./ci/test_run_all.sh'
<snip>
#170921 REDUCE cov: 1694 ft: 6197 corp: 478/22Kb lim: 240 exec/s: 3351 rss: 208Mb L: 20/219 MS: 1 EraseBytes-
#171261 REDUCE cov: 1694 ft: 6200 corp: 479/22Kb lim: 240 exec/s: 3358 rss: 208Mb L: 193/219 MS: 5 ChangeBinInt-ChangeBit-ChangeByte-CrossOver-CrossOver-
#171550 REDUCE cov: 1694 ft: 6200 corp: 479/22Kb lim: 240 exec/s: 3363 rss: 208Mb L: 42/219 MS: 4 CopyPart-ChangeByte-PersAutoDict-EraseBytes- DE: "\024\000"-
#171657 REDUCE cov: 1694 ft: 6200 corp: 479/22Kb lim: 240 exec/s: 3365 rss: 208Mb L: 51/219 MS: 2 InsertByte-EraseBytes-
coins.cpp:132:22: runtime error: unsigned integer overflow: 0 - 64 cannot be represented in type 'size_t' (aka 'unsigned long')
#0 0xaaaab73bc134 in CCoinsViewCache::SpendCoin(COutPoint const&, Coin*) src/coins.cpp:132:22
#1 0xaaaab57cbc94 in coins_view_fuzz_target(Span<unsigned char const>)::$_4::operator()() const src/test/fuzz/coins_view.cpp:89:40
#2 0xaaaab57cbc94 in unsigned long CallOneOf<coins_view_fuzz_target(Span<unsigned char const>)::$_0, coins_view_fuzz_target(Span<unsigned char const>)::$_1, coins_view_fuzz_target(Span<unsigned char const>)::$_2, coins_view_fuzz_target(Span<unsigned char const>)::$_3, coins_view_fuzz_target(Span<unsigned char const>)::$_4, coins_view_fuzz_target(Span<unsigned char const>)::$_5, coins_view_fuzz_target(Span<unsigned char const>)::$_6, coins_view_fuzz_target(Span<unsigned char const>)::$_7, coins_view_fuzz_target(Span<unsigned char const>)::$_8, coins_view_fuzz_target(Span<unsigned char const>)::$_9, coins_view_fuzz_target(Span<unsigned char const>)::$_10>(FuzzedDataProvider&, coins_view_fuzz_target(Span<unsigned char const>)::$_0, coins_view_fuzz_target(Span<unsigned char const>)::$_1, coins_view_fuzz_target(Span<unsigned char const>)::$_2, coins_view_fuzz_target(Span<unsigned char const>)::$_3, coins_view_fuzz_target(Span<unsigned char const>)::$_4, coins_view_fuzz_target(Span<unsigned char const>)::$_5, coins_view_fuzz_target(Span<unsigned char const>)::$_6, coins_view_fuzz_target(Span<unsigned char const>)::$_7, coins_view_fuzz_target(Span<unsigned char const>)::$_8, coins_view_fuzz_target(Span<unsigned char const>)::$_9, coins_view_fuzz_target(Span<unsigned char const>)::$_10) src/./test/fuzz/util.h:43:27
#3 0xaaaab57cbc94 in coins_view_fuzz_target(Span<unsigned char const>) src/test/fuzz/coins_view.cpp:58:9
#4 0xaaaab5d2319c in std::function<void (Span<unsigned char const>)>::operator()(Span<unsigned char const>) const /usr/bin/../lib/gcc/aarch64-linux-gnu/13/../../../../include/c++/13/bits/std_function.h:591:9
#5 0xaaaab5d2319c in LLVMFuzzerTestOneInput src/test/fuzz/fuzz.cpp:178:5
#6 0xaaaab5545050 in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long) (/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz+0x1925050) (BuildId: 82e180570288de2f70ceeee1ed5d7cd3729696ab)
#7 0xaaaab5544798 in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool, bool*) (/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz+0x1924798) (BuildId: 82e180570288de2f70ceeee1ed5d7cd3729696ab)
#8 0xaaaab5545f90 in fuzzer::Fuzzer::MutateAndTestOne() (/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz+0x1925f90) (BuildId: 82e180570288de2f70ceeee1ed5d7cd3729696ab)
#9 0xaaaab5546cdc in fuzzer::Fuzzer::Loop(std::vector<fuzzer::SizedFile, std::allocator<fuzzer::SizedFile>>&) (/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz+0x1926cdc) (BuildId: 82e180570288de2f70ceeee1ed5d7cd3729696ab)
#10 0xaaaab5534e70 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long)) (/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz+0x1914e70) (BuildId: 82e180570288de2f70ceeee1ed5d7cd3729696ab)
#11 0xaaaab555e0ac in main (/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz+0x193e0ac) (BuildId: 82e180570288de2f70ceeee1ed5d7cd3729696ab)
#12 0xffffb4aa84c0 (/lib/aarch64-linux-gnu/libc.so.6+0x284c0) (BuildId: 1d7249a4f207d07166ff4be43acdc68a01faaa04)
#13 0xffffb4aa8594 in __libc_start_main (/lib/aarch64-linux-gnu/libc.so.6+0x28594) (BuildId: 1d7249a4f207d07166ff4be43acdc68a01faaa04)
#14 0xaaaab552afac in _start (/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz+0x190afac) (BuildId: 82e180570288de2f70ceeee1ed5d7cd3729696ab)
SUMMARY: UndefinedBehaviorSanitizer: unsigned-integer-overflow coins.cpp:132:22 in
MS: 1 CopyPart-; base unit: 81111e927920a57969bb7efb23d89de00d09a5ec
0xff,0xef,0xfe,0x0,0x1,0x3,0x0,0x1,0xff,0xff,0xff,0xff,0xff,0x3,0x0,0x1,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x3,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xfe,0xff,0xfa,0x0,0x0,0x0,0x0,0x80,0x76,0x0,0x0,0x0,0x0,0x68,0x5c,0xff,0xff,0xff,0xff,0xef,0xfe,0x0,0x1,0x3,0x0,0x1,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x3,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x3,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xfe,0xff,0xfa,0x0,0x0,0x0,0x0,0x80,0x76,0x0,0x0,0x0,0x0,0x68,0x5c,0xff,0xff,0xff,0xff,0xef,0xfe,0x0,0x1,0x3,0x0,0x1,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x3,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xfe,0xff,0xfa,0x7,
\377\357\376\000\001\003\000\001\377\377\377\377\377\003\000\001\377\377\377\377\377\377\377\003\377\377\377\377\377\377\377\377\377\377\376\377\372\000\000\000\000\200v\000\000\000\000h\\\377\377\377\377\357\376\000\001\003\000\001\377\377\377\377\377\377\377\003\377\377\377\377\377\377\377\377\377\377\377\003\377\377\377\377\377\377\377\377\377\377\376\377\372\000\000\000\000\200v\000\000\000\000h\\\377\377\377\377\357\376\000\001\003\000\001\377\377\377\377\377\377\377\003\377\377\377\377\377\377\377\377\377\377\376\377\372\007
artifact_prefix='./'; Test unit written to ./crash-2ea01576a6e0a74d403920761ea2ff6f0bf41752
Base64: /+/+AAEDAAH//////wMAAf////////8D//////////////7/+gAAAACAdgAAAABoXP/////v/gABAwAB/////////wP//////////////wP//////////////v/6AAAAAIB2AAAAAGhc/////+/+AAEDAAH/////////A//////////////+//oH
Target ['/ci_container_base/ci/scratch/build/bitcoin-aarch64-unknown-linux-gnu/src/test/fuzz/fuzz', '-max_total_time=60'] failed with exit code 1
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
You can recreate the failures
Thanks a lot @fanquake, I managed to reproduce it this way (seeing that l0rinc#10 was failing, I was trying to run them manually instead of relying on the ci scripts).
why it isn't needed (or rather since when)
Thanks @maflcko for insisting, I have changed the order of commits to place the suppression removal at the very end since we still had a few failures for the first few commits - it's easier to remove them all at the end only, where I couldn't reproduce any such failure anymore.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Seems fine, but it may be better to remove the suppression in the exact commit that removes the need for it. This would make it easier to revert the commit atomically in one go, if there is need for whatever reason.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Any accounting inconsistency could've caused it to become negative and fail, so instead of removing these suppressions in the last commit that fixed the problem (giving the impression that it was just one change that enabled us removing it), I did it separately instead.
Is this important, is this holding back the ACK from your part?
a0468a8
to
0feba07
Compare
This was added for the two branches to be symmetric and to explain why this branch is missing a subtraction. Co-authored-by: Andrew Toth <andrewstoth@gmail.com>
Assert that spent coins already have zero dynamic size, and remove unused leftover counter
Prevents the counter from dropping to 0 while cacheCoins still holds objects
…inserts Guarantees counter stays balanced both on insert and on in‑place replacement. Note that this is currently only called from AssumeUTXO code where it should only insert. Co-authored-by: Andrew Toth <andrewstoth@gmail.com>
These were fixed im previous commits: INFO: Seed: 3018625440 INFO: Loaded 1 modules (641435 inline 8-bit counters): 641435 [0x5810b64ebb78, 0x5810b6588513), INFO: Loaded 1 PC tables (641435 PCs): 641435 [0x5810b6588518,0x5810b6f51ec8), INFO: 1859 files found in /ci_container_base/ci/scratch/qa-assets/fuzz_corpora/coins_view INFO: -max_len is not provided; libFuzzer will not generate inputs larger than 1005297 bytes INFO: seed corpus: files: 1859 min: 2b max: 1005297b total: 48403597b rss: 111Mb /ci_container_base/src/coins.cpp:133:22: runtime error: unsigned integer overflow: 0 - 64 cannot be represented in type 'size_t' (aka 'unsigned long') #0 0x5810b3768b67 in CCoinsViewCache::SpendCoin(COutPoint const&, Coin*) /ci_container_base/ci/scratch/build-x86_64-pc-linux-gnu/src/./coins.cpp:133:22 #1 0x5810b3095ff0 in coins_view_fuzz_target(std::span<unsigned char const, 18446744073709551615ul>)::$_4::operator()() const /ci_container_base/ci/scratch/build-x86_64-pc-linux-gnu/src/test/fuzz /./test/fuzz/coins_view.cpp:87:40 ... SUMMARY: UndefinedBehaviorSanitizer: unsigned-integer-overflow /ci_container_base/src/coins.cpp:133:22
0feba07
to
c7d9c42
Compare
Rebased after fuzz conflicts, ready for review again. |
Split out of #32296 (comment) since this needed more complicated production code changes.
The changes ensure
cachedCoinsUsage
remains balanced throughout all coin operations and that the sanitizers will catch future violations.You can recreate the previous failures as described in #32313 (comment):
The change was tested with the related fuzz test, and asserted before/after each
cachedCoinsUsage
change (in production code and fuzz) that the calculations are still correct by recalculating it from scratch.Details
This part wasn't committed to the code.