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.
Specifying the alignment requirement at the prevector level instead of for 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)");
I don't like statically asserting numbers here. It may differ per platform, architecture.
ACK on the prevector.h and ubsan change
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");
nit: 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.
ACK 0df2f79c0, I have tested the code
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)");
I don't think it should be a compile error if these are too small or big. This means that for any field added/removed to the structure, or possible for new compilers/architectures, these lines have to be updated.
Agree, mostly wanted them in there to check that there weren't any unexpected changes at least on any of the architectures travis checks. (It's 44/48 for 4-byte pointers and 48/56 for 8-byte pointers). Rebased without that commit.
Yeah, it's good for that. I later realized there could be a case for checking CScript's size because it's supposed to be 32 bytes no matter the architecture (assuming pointer sizes <= 128 bit :smiley: ), and it's unlikely for fields to be added to it. But I dunno.
CScript seems like it ought to be reasonably robust, and it's got that 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...
Actually I think to a degree CScript being 32 is non obvious... e.g. the size could be shifted greater if that were expected to be the "hot case" for fitting most CScripts. It does kind of seem like 28 might be too small, and worth re-measuring. P2SH fits in 32, but a segwit output should be 33 bytes long... unless I'm missing some case where 28 is a common size nowadays.
p2pkh, p2sh and p2wpkh should all fit; p2wsh won't fit though (and neither will p2taproot if/when it exists)
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--174a7506f384e20aa4161008e828411d-->
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
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:
struct size_field {const size_t s};
struct direct_t {size_t s; T t[];}
struct indirect_t {size_t s; size_t s2; T* t;}
union {
size_field s;
direct_t direct;
indirect_t indirect;
}
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:
prevector.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
[#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
[#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
[#2](/bitcoin-bitcoin/2/) 0x55f5cfb4168e in CScript::operator=(CScript&&) src/./script/script.h:390:7
[#3](/bitcoin-bitcoin/3/) 0x55f5cfbce2b6 in ProduceSignature(SigningProvider const&, BaseSignatureCreator const&, CScript const&, SignatureData&) src/script/sign.cpp:240:23
I agree with @ajtowns above and support moving forward with fixing this (and following up in the future with a pragma free version if needed).
It seems this had a performance related silent merge conflict.
The commit itself increases performance:
$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
5f26855f10 test: Remove ubsan alignment suppressions
# Benchmark, evals, iterations, total, min, max, median
PrevectorDeserializeNontrivial, 5, 6800, 2.56196, 7.44051e-05, 7.63586e-05, 7.53984e-05
$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
1189b6acab Merge [#17109](/bitcoin-bitcoin/17109/): tests: Add fuzzing harness for various functions consuming only integrals
# Benchmark, evals, iterations, total, min, max, median
PrevectorDeserializeNontrivial, 5, 6800, 3.03115, 8.75186e-05, 9.02937e-05, 8.95368e-05
However, the merge commit decreases performance:
$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
2bdc476d4d Merge [#17708](/bitcoin-bitcoin/17708/): prevector: avoid misaligned member accesses
# Benchmark, evals, iterations, total, min, max, median
PrevectorDeserializeNontrivial, 5, 6800, 4.06536, 0.00011926, 0.000120323, 0.000119399
$ git log -1 --oneline --no-decorate && ./src/bench/bench_bitcoin --filter=PrevectorDeserializeNontrivial
d4fc9aeb8b Merge [#18125](/bitcoin-bitcoin/18125/): doc: remove PPA note from release-process.md
# Benchmark, evals, iterations, total, min, max, median
PrevectorDeserializeNontrivial, 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.