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
Add minisketch subtree and integrate into build/test #23114
Add minisketch subtree and integrate into build/test #23114
Conversation
1915a03
to
a5d51b7
Compare
Looks like at least one reason this is failing is because clmul detection is inaccurate here. This was apparently fixed upstream by this commit. Pulling in that change should fix that problem.
|
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. 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. |
It looks like https://github.com/bitcoin/bitcoin/pull/23114/checks?check_run_id=3731233027 might've caught a real minisketch bug? |
@theuni It's not; unsigned overflow is well-defined (but our sanitizer is overly strict). In this case it's computing "A - B + C", where the overall result is positive, but (A - B) is negative. Reordering the expression, or turning off the unsigned overflow sanitizer would be possible solutions. |
a5d51b7
to
d855a4e
Compare
I've pulled in the improved clmul detection. That should fix the failing 32 bit CentOS 8 and multiprocess builds. I've also made a change that should fix the failing Win64 CI. |
@fanquake Could you pull in a temp/hack version of sipa/minisketch#49 here to see if it makes the sanitizer happy? |
It is not allowed to link anything other than the fuzz tests with |
Thanks for the pointer, @MarcoFalke. @fanquake: You can take (and squash) theuni@aaa53f2 which should fix that in the simplest way. |
for (uint64_t e = 0; e < 84; ++e) { | ||
sketch.Add(e*1337 + b*13337 + offset); | ||
} | ||
offset += (*sketch.Decode(32))[0]; |
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.
Why use the optional
version of Decode
if the value is ignored?
Also, what's the offset's purpose here? It's not obvious to me what will be in [0]
.
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.
Also, what's the offset's purpose here? It's not obvious to me what will be in [0].
From my reading, it seems to give a random deterministic value?
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's just to make sure the inputs to the algorithm are vaguely randomized (and also, so the compiler can't optimize the decode call out).
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 for why the optional version: no strong reason, but this avoids a separate temporary variable to place the result in.
d855a4e
to
eb7b16b
Compare
Cherry-picked sipa/minisketch#49 and sipa/minisketch/pull/51 (minus the CI change) for testing.
Integrated this change. Rebased on master to resolve a conflict. |
I don't understand the problem here. Does the sanitizer want the high bits masked off before shifting or something?
|
@theuni Yes, exactly. That's not going to happen. We should just not enable unsigned integer sanitizer - it's going to cause alarm bells all over the place. |
The sanitizer error can be fixed by disabling the sanitizer or adding a suppression to |
3dd14ce
to
f22af45
Compare
Buildsystem/wrapper re-ACK f22af45. My remaining wrapper nit isn't a big deal. |
git-subtree-dir: src/minisketch git-subtree-split: 89629eb2c7e262b39ba489b93b111760baded4b3
AC_DEFINE'd values won't be passed down to minisketch because it does not use bitcoin-config.h. Thus we need a way to know if we should manually add defines for minisketch files.
f22af45
to
29173d6
Compare
Guix Build: bash-5.1# find guix-build-$(git rev-parse --short=12 HEAD)/output/ -type f -print0 | env LC_ALL=C sort -z | xargs -r0 sha256sum
89b9bc3994ee82f15eb522c6085c88e9d14e1f12887eb64b8fa6eafdba6f78ed guix-build-29173d6c6ca0/output/aarch64-linux-gnu/SHA256SUMS.part
2b1689ee1c37759663bc08c86c0c39e09a9567b7dcfb153af6d3c15bb6483081 guix-build-29173d6c6ca0/output/aarch64-linux-gnu/bitcoin-29173d6c6ca0-aarch64-linux-gnu-debug.tar.gz
a58477250142ffc319684f935589058431df8239a7123dfd6976fa6553812975 guix-build-29173d6c6ca0/output/aarch64-linux-gnu/bitcoin-29173d6c6ca0-aarch64-linux-gnu.tar.gz
43dafdb7d6d2d4d5048505addc9ebe9eaa9a99e915f5b6538e761fbeef1a6a10 guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/SHA256SUMS.part
4a56f45d91ce0c2cd667f2f7dd05a32778359fdb31598569aa0a331207db4320 guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/bitcoin-29173d6c6ca0-arm-linux-gnueabihf-debug.tar.gz
13f2ffbbf04b17cf0114428e34d8da3a9c0d695e0701e3ee3bb3797e407002db guix-build-29173d6c6ca0/output/arm-linux-gnueabihf/bitcoin-29173d6c6ca0-arm-linux-gnueabihf.tar.gz
0d20ba62b54469109a7e1767678742c211bf7ac995c5a0fb4a31b5310bdcb144 guix-build-29173d6c6ca0/output/dist-archive/bitcoin-29173d6c6ca0.tar.gz
e5d4c1223fa6494399368d57148d65c1ea8f8178c7c4ac4050c2f9fc15c4c34e guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/SHA256SUMS.part
be31fe98d97e3d1bbf55eefd0e752eb3903141040c3f42cecc5a147ba535124f guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/bitcoin-29173d6c6ca0-powerpc64-linux-gnu-debug.tar.gz
00a7594ed7f4a24cf2b4cb03356630d94dd1053712d913c7218db301ffbd8a8d guix-build-29173d6c6ca0/output/powerpc64-linux-gnu/bitcoin-29173d6c6ca0-powerpc64-linux-gnu.tar.gz
2785c709c05710b6db7aa6f0210cda0897c896fe23e883ae9f02aab0b758e906 guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/SHA256SUMS.part
483b81890ba35813fa8c1e1670581e3b574e5cca3c487effc2ba43e82e1b935e guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/bitcoin-29173d6c6ca0-powerpc64le-linux-gnu-debug.tar.gz
3f2d8a25e38086b030200a56098c5ff427c4f1d851c114476656cfcf038bf567 guix-build-29173d6c6ca0/output/powerpc64le-linux-gnu/bitcoin-29173d6c6ca0-powerpc64le-linux-gnu.tar.gz
8bacce59257057d40bb84f6f62cb3992f3bb5ce61ef2ed57a5dcf20b4c143097 guix-build-29173d6c6ca0/output/riscv64-linux-gnu/SHA256SUMS.part
fe3a19b8cac2a42fbbd6ed1a67b5942eca9e8218656c438bb7bd909a53ca4aee guix-build-29173d6c6ca0/output/riscv64-linux-gnu/bitcoin-29173d6c6ca0-riscv64-linux-gnu-debug.tar.gz
4954f8a05b2674cdbb6a24d95d31126cbdfe64f4f4dfda2d860f2cc4935d34c4 guix-build-29173d6c6ca0/output/riscv64-linux-gnu/bitcoin-29173d6c6ca0-riscv64-linux-gnu.tar.gz
0fd610c9147cb714d43c1c59872f981ba1e46108c89ab6c7813bd7f0089c87dc guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/SHA256SUMS.part
fc7fd5ad415c18e4eb7e8796a4ba8ae9a61e178a4f7f7a987a983e6294f89379 guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx-unsigned.dmg
dfa4d38cbd10c3b69bd0906895bd3113764fa5f5f3b10ec632769bf0fb5b396c guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx-unsigned.tar.gz
abeda851f9165d3c4175f23c1b08c1a455d632bc8f17fd2b5412301c2971a69a guix-build-29173d6c6ca0/output/x86_64-apple-darwin19/bitcoin-29173d6c6ca0-osx64.tar.gz
866a0258831e01b407c24485b7073806ed53b2edae907f12474ba8c873dac18d guix-build-29173d6c6ca0/output/x86_64-linux-gnu/SHA256SUMS.part
bbf7f367929d5a3226de0ff96148e5eddd05495c18fb159a2fcc89632c07d44c guix-build-29173d6c6ca0/output/x86_64-linux-gnu/bitcoin-29173d6c6ca0-x86_64-linux-gnu-debug.tar.gz
e94592e85bd84bc346d30b08b163b55d640783bc530cfcdb7553e15c7b59a17d guix-build-29173d6c6ca0/output/x86_64-linux-gnu/bitcoin-29173d6c6ca0-x86_64-linux-gnu.tar.gz
2ea5e404e6ac8ac1634a8a27fc49b230602d3c4ad3caa3e7f9ebfce0ee2df5f2 guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/SHA256SUMS.part
fdaeea7e6f2884ef49f901718d0e1d4a81768fa63d5de49ef47357470cfa2197 guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win-unsigned.tar.gz
33dd8a2b69f7cdf3aa05df2b39908483ec07affb8034a1f2f5a76ebca2877389 guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64-debug.zip
e724eda8888fa2017430abb50fb146c934ec686cde13a555835dfc33ae228a70 guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64-setup-unsigned.exe
2adf2e26c2faf588078822b0b41601f5aabdfabd9c998de4e50b325bd9e3ef36 guix-build-29173d6c6ca0/output/x86_64-w64-mingw32/bitcoin-29173d6c6ca0-win64.zip |
/* Remember which implementation has the best median benchmark time. */ | ||
if (!benches.empty()) { | ||
std::sort(benches.begin(), benches.end()); | ||
if (!best || best->first > benches[5]) { |
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.
Where does [5] come from?
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's the middle of the 11 benchmarks (we're trying to find the implementation with the best median benchmark score).
Concept ACK, Approach ACK For the benefit of reviewers who weren't at the Core dev IRC meeting yesterday the build stuff seems to be pretty much ready (thanks to @theuni, @fanquake @dongcarl etc). It seems like we are in the final phase of testing for the Minisketch library now pre-merge and hence previous PR review clubs (Python 1 and 2, C++ 3) may be a useful resource for reviewers. Reviews and testing the library should (presumably) be posted on this PR. Once this is (hopefully) merged that opens the door to a greater review focus on the Erlay PR. It seems to me that that PR has been waiting on this to get to a final(ish) state. |
#include <cstdint> | ||
|
||
/** Wrapper around Minisketch::Minisketch(32, implementation, capacity). */ | ||
Minisketch MakeMinisketch32(size_t capacity); |
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.
Can this wrapper also encapsulate minisketch_compute_max_elements
? This is the only library-level function that's gonna be leaked into txreconciliation.cpp
. See how I use it:
size_t max_elements = minisketch_compute_max_elements(RECON_FIELD_SIZE, remote_sketch_capacity, RECON_FALSE_POSITIVE_COEF);
std::vector<uint64_t> differences(max_elements);
if (local_sketch.Merge(remote_sketch).Decode(differences)) {
I don't think there's a way to avoid it? Or maybe it's fine to have it leaked?
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.
This can be done later though.
ACK 29173d6
|
Contributing GUIX hashes, mine match @fanquake
|
…ith-system-univalue` 0f95247 Integrate univalue into our buildsystem (Cory Fields) 9b49ed6 Squashed 'src/univalue/' changes from 98fadc0909..a44caf65fe (fanquake) Pull request description: This PR more tightly integrates building Univalue into our build system. This follows the same approach we use for [LevelDB](https://github.com/bitcoin-core/leveldb/), ([`Makefile.leveldb.include`](https://github.com/bitcoin/bitcoin/blob/master/src/Makefile.leveldb.include)), and [CRC32C](https://github.com/bitcoin-core/crc32c) ([`Makefile.crc32c.include`](https://github.com/bitcoin/bitcoin/blob/master/src/Makefile.crc32c.include)), and will be the same approach we use for [minisketch](https://github.com/sipa/minisketch); see bitcoin#23114. This approach yields a number of benefits, including: * Faster configuration due to one less subconfigure being run during `./configure` i.e 22s with this PR vs 26s * Faster autoconf i.e 13s with this PR vs 17s * Improved caching * No more issues with compiler flags i.e bitcoin#12467 * More direct control means we can build exactly the objects we want There might be one argument against making this change, which is that builders should have the option to use "proper shared/system libraries". However, I think that falls down for a few reasons. The first being that we already don't support building with a number of system libraries (secp256k1, leveldb, crc32c); some for good reason. Univalue is really the odd one out at the moment. Note that the only fork of Core I'm aware of, that actively patches in support for using system libs, also explicitly marks them as ["DANGEROUS"](https://github.com/bitcoinknots/bitcoin/blob/a886811721ce66eb586871706b3f5dd27518ac3e/configure.ac#L1430) and ["NOT SUPPORTED"](https://github.com/bitcoinknots/bitcoin/blob/a886811721ce66eb586871706b3f5dd27518ac3e/configure.ac#L1312). So it would seem they exist more to satisfy a distro requirement, as opposed to something that anyone should, or would actually use in practice. PRs like bitcoin#22412 highlight the "issue" with us operating with our own Univalue fork, where we actively fix bugs, and make improvements, when upstream (https://github.com/jgarzik/univalue) may not be taking those improvements, and by all accounts, is not currently actively maintained. Bitcoin Core should not be hamstrung into not being able to fix bugs in a library, and/or have to litter our source with "workarounds", i.e bitcoin#22412, for bugs we've already fixed, based on the fact that an upstream project is not actively being maintained. Allowing builders to use system libs is really only exacerbating this problem, with little benefit to our project. Bitcoin Core is not quite like your average piece of distro packaged software. There is the potential for us to give the same treatment to libsecp256k1, however it seems doing that is currently less straightforward. ACKs for top commit: dongcarl: ACK 0f95247 less my comment above, always nice to have an include-able `sources.mk` which makes integration easier. theuni: ACK 0f95247. Thanks fanquake for keeping this going. Tree-SHA512: a7f2e41ee7cba06ae72388638e86b264eca1b9a8b81c15d1d7b45df960c88c3b91578b4ade020f8cc61d75cf8d16914575f9a78fa4cef9c12be63504ed804b99
This takes over #21859, which has recently switched to my integration branch. A few more build issues came up (and have been fixed) since, and after discussing with sipa it was decided I would open a PR to shepherd any final changes through.
Only changes since my last update to the branch in the previous PR have been rebasing on master and fixing an issue with a header in an introduced file.