Ensure prevector data is appropriately aligned. Earlier discussion in #17530.
Edit laanwj: In contrast to #17530, it does this without increase in size of any of the coin cache data structures (x86_64, clang)
| Struct | (size,align) before | (size,align) after |
|---|---|---|
| Coin | 48, 8 | 48, 8 |
| CCoinsCacheEntry | 56, 8 | 56, 8 |
| CScript | 32, 1 | 32, 8 |
`#pragma pack(1)` prevents aligning the struct and its members to their
required alignment. This can result in code that performs non-aligned
reads and writes to integers and pointers, which is problematic on some
architectures.
It also triggers UBsan — see
https://github.com/bitcoin/bitcoin/pull/17156#issuecomment-543123631
and #17510.
prevector::_union would also work (ie, class alignas(char*) prevector {) and would be a smaller change, but it would be more fragile (breaking if N*sizeof(T) isn’t a multiple of alignof(size_type), or sizeof(size_type)*2 didn’t match alignof(char*)) , so keeping the pack pragma covering only the code that it absolutely needs to seems better.
Concept ACK: it would be really nice to be able to run with UndefinedBehaviorSanitizer (UBSan) without having to use any suppressions.
Reviewers of this PR are encouraged to review also the related PR #17208 (“Make all tests pass UBSan without using any UBSan suppressions”).
8@@ -9,6 +9,11 @@
9 #include <random.h>
10 #include <version.h>
11
12+/* Check structure sizes are nicely packed */
13+static_assert(sizeof(Coin) == 48, "unexpected sizeof(Coin)");
159+ };
160+#pragma pack(pop)
161+ alignas(char*) direct_or_indirect _union = {};
162+ size_type _size = 0;
163+
164+ static_assert(alignof(char*) % alignof(size_type) == 0 && sizeof(char*) % alignof(size_type) == 0, "size_type cannot have more restrictive alignment requirement than pointer");
assert(A && B); is equivalent to assert(A); assert(B);, however the former has the (small) problem that if it fails it is not clear from the message which one of A or B is false.
sizeof(X) is always a multiple of alignof(X), so I think the second half here is just redundant.
8@@ -9,6 +9,11 @@
9 #include <random.h>
10 #include <version.h>
11
12+/* Check structure sizes are nicely packed */
13+static_assert(sizeof(CScript) == 32, "unexpected sizeof(CScript)");
14+static_assert(44 <= sizeof(Coin) && sizeof(Coin) <= 48, "unexpected sizeof(Coin)");
15+static_assert(48 <= sizeof(CCoinsCacheEntry) && sizeof(CCoinsCacheEntry) <= 56, "unexpected sizeof(CCoinsCacheEntry)");
28 constant already. Maybe if #17060 or the like makes progress could add some checks then? Figure it only makes sense to worry about the size of the things you’re caching a bazillion of…
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, 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.
This can be done now that prevector is properly aligned.
ACK 5f26855f109af53a336d5f98ed0ae584e7a31f84
Very glad to see two UBSan suppressions go away! :)
I’m pretty sure the change, as it is now, doesn’t modify the layout of any of the data structures used in UTXO caching.
I think the only case where CScript ended up non-aligned in practice was on the stack in some cases (esp. the fuzzing tests).
This just feels like there must be a better solution. What we’re trying to accomplish here should be completely legal, and shouldn’t require pragma pack at all.
Really the problem is that we want either (size, size, pointer) or (size, bytearray). If we could have a union between those two, with a guarantee the two first fields are merged, we’d be done. But because the language forces us to construct an explicit type for the ((size, pointer) or (bytearray)) structure, it on itself has a stronger alignment than if it were “inlined” so to speak.
That said, I see no way to accomplish that that is guaranteed legal, so ACK.
I’m pretty sure that it’s valid to just union them and access the first size from either.
https://en.cppreference.com/w/cpp/language/data_members
C++11 & before
If a standard-layout union holds two (or more) standard-layout classes as members, and these classes have a common initial sequence of data members, it is well-defined to examine any member of that common initial sequence regardless of which member of the union is active.
C++14 on
In a standard-layout union with an active member of non-union class type T1, it is permitted to read a non-static data member m of another union member of non-union class type T2 provided m is part of the common initial sequence of T1 and T2 (except that reading a volatile member through non-volatile glvalue is undefined).
Therefore something like:
0struct size_field {const size_t s};
1struct direct_t {size_t s; T t[];}
2struct indirect_t {size_t s; size_t s2; T* t;}
3
4union {
5size_field s;
6direct_t direct;
7indirect_t indirect;
8}
reads to me as being standards compliant…
edit: made size_field.s const to express that the value should be read-only from size_field edit: added c++11 spec, which should also be compatible
I’m pretty sure that it’s valid to just union them and access the first size from either.
Yes, my first impulse was also “move the size into the union”, but the last decade of C++ (often enough, something allowed or even recommended one day becomes UB the next) made me scared of these kind of assumptions. I think we’re looking at “aliasing” here as there will be two paths to access the same data.
But I’m not a language lawyer, and common sense tells me to not depend on such edge cases of the standard. Especially given how critical this data structure is to bitcoin verification.
So I’d prefer to merge the current solution. I think it’s guaranteed not to make anything worse or introduce new UB. It uses the same pragmas as before but in a more contained way.
(if someone comes up with a better solution that is easy to see is legal then we can always switch around the code again)
It’s worth noting that this behavior is very well defined in C99 and C++.
The standard seems pretty clear to me:
If two union members are standard-layout types, it’s well-defined to examine their common subsequence on any compiler.
https://en.cppreference.com/w/cpp/language/union
The aliasing rules should only come into play when the field is written to; which we shouldn’t have a problem with as we use the size field to switch on direct/indirectness.
I have mixed feeling overall on if #pragma pack is less edge casey as it in fact does exploit compiler-specific & platform-specific behavior, and the access may be problematic on certain platforms. The code also ends up being more confusing to read IMO and less clear on safety (alignas and the new static_asserts required show that). I’m also a little cagey feeling on using a pragma within a class definition (although the struct can be trivially moved outside the class definition to address this).
I have mixed feeling overall on if #pragma pack is less edge casey as it in fact does exploit compiler-specific
The pragma pack was there already for years, and as far as we know, never gave any issues.
I think this PR does not make anything less safe than it was before. It adds constraints to make sure the previous usage, which already happened to be safe (due to how the data structures were already happened to be laid out), is made explicit.
I do not think this warrants making deeper changes to prevector.
And if a compiler were to ignore the pragma pack completely it still results in correct behavior, just more memory usage. It’s (here) not used to force any binary layout that is relied on.
Review beg for this PR which currently has three fresh ACKs (@laanwj, @sipa and me) and one stale ACK (@vasild) - anyone else interested in reviewing? :)
Would be great to have this merged :)
It’s worth noting that this behavior is very well defined in C99 and C++.
FWIW, I think @JeremyRubin is right in that that’s both safe and a better approach; but in the short term at least it seems to be a much more intrusive change both to merge _size into the union (as _direct._size and _indirect._size or similar) and more importantly to update the _size field in the correct sub-struct (_direct or _indirect) in each case, since the standard only guarantees reading from either sub-struct works, not writing to either…
I was really hoping to see this fix making it to 0.19.1 :\
Can we move forward with this one?
Doesn’t feel good to ship with a known misaligned pointer use in ProduceSignature(…) :(
Reachability:
0prevector.h:453:19: runtime error: reference binding to misaligned address 0x7f24765a4c22 for type 'prevector<28, unsigned char, unsigned int, int>::size_type' (aka 'unsigned int'), which requires 4 byte alignment
1 [#0](/bitcoin-bitcoin/0/) 0x55f5cfb48a4e in prevector<28u, unsigned char, unsigned int, int>::swap(prevector<28u, unsigned char, unsigned int, int>&) src/./prevector.h:453:9
2 [#1](/bitcoin-bitcoin/1/) 0x55f5cfb4168e in prevector<28u, unsigned char, unsigned int, int>::operator=(prevector<28u, unsigned char, unsigned int, int>&&) src/./prevector.h:273:9
3 [#2](/bitcoin-bitcoin/2/) 0x55f5cfb4168e in CScript::operator=(CScript&&) src/./script/script.h:390:7
4 [#3](/bitcoin-bitcoin/3/) 0x55f5cfbce2b6 in ProduceSignature(SigningProvider const&, BaseSignatureCreator const&, CScript const&, SignatureData&) src/script/sign.cpp:240:23
It seems this had a performance related silent merge conflict.
The commit itself increases performance:
0$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
15f26855f10 test: Remove ubsan alignment suppressions
2# Benchmark, evals, iterations, total, min, max, median
3PrevectorDeserializeNontrivial, 5, 6800, 2.56196, 7.44051e-05, 7.63586e-05, 7.53984e-05
4
5$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
61189b6acab Merge [#17109](/bitcoin-bitcoin/17109/): tests: Add fuzzing harness for various functions consuming only integrals
7# Benchmark, evals, iterations, total, min, max, median
8PrevectorDeserializeNontrivial, 5, 6800, 3.03115, 8.75186e-05, 9.02937e-05, 8.95368e-05
However, the merge commit decreases performance:
0$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
12bdc476d4d Merge [#17708](/bitcoin-bitcoin/17708/): prevector: avoid misaligned member accesses
2# Benchmark, evals, iterations, total, min, max, median
3PrevectorDeserializeNontrivial, 5, 6800, 4.06536, 0.00011926, 0.000120323, 0.000119399
4
5$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
6d4fc9aeb8b Merge [#18125](/bitcoin-bitcoin/18125/): doc: remove PPA note from release-process.md
7# Benchmark, evals, iterations, total, min, max, median
8PrevectorDeserializeNontrivial, 5, 6800, 3.21483, 9.32497e-05, 9.52515e-05, 9.48292e-05
It seems this had a performance related silent merge conflict.
It makes sense for this to make things worse in the benchmark I think – the nontrivial constructor prevector in the benchmark is a 116 or 120 byte object (28 4-byte nontrivials, a 4-byte size_t with the number of non-trivials, all aligned to a pointer so padded 4-bytes if pointers are 8-bytes), and the size has moved to the end of that structure rather than the beginning which could well be a different cache line than the first entry or the pointer to the allocated entries.
Could probably confirm this by seeing if changing nontrivial_t::x from int to signed char makes the performance regression disappear.