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").

ACK on the prevector.h and ubsan change

ACK 0df2f79c0, I have tested the code

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

• build: ensure we aren't using GNU extensions #18088 (build: ensure we aren't using GNU extensions by fanquake)
• Make all tests pass UBSan without using any UBSan suppressions #17208 (Make all tests pass UBSan without using any UBSan suppressions by practicalswift)

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.

ACK 5f26855

ACK 5f26855

Very glad to see two UBSan suppressions go away! :)

@jamesob Might wanna benchmark this one instead of the previous attempt if you haven't already ☺️

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).

@laanwj Agree.

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 0x55f5cfb48a4e in prevector<28u, unsigned char, unsigned int, int>::swap(prevector<28u, unsigned char, unsigned int, int>&) src/./prevector.h:453:9
    #1 0x55f5cfb4168e in prevector<28u, unsigned char, unsigned int, int>::operator=(prevector<28u, unsigned char, unsigned int, int>&&) src/./prevector.h:273:9
    #2 0x55f5cfb4168e in CScript::operator=(CScript&&) src/./script/script.h:390:7
    #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: 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: 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: 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.