Soundness of AtomicCell::compare_exchange is dubious

[RalfJung]

AtomicCell<T>::compare_exchange will, if I understand the code correctly, use AtomucU*::compare_exchange_weak if T has the right size. But this means that e.g. for (u8, u16), which has size 4, it will transmute these pairs into u32 and compare them as integers. However, such pairs contain a padding byte, meaning that the u32 contains some uninitialized memory. Having uninitialized memory in a u32 is uncharted territory at best, but performing actual operations on such a datum (as opposed to just load/store) brings us very close to UB. I am not sure what the rules are in LLVM for this case, but under the proposed poison semantics I think the comparison will return poison and hence using it in an if is UB. For Rust, I think the intention is to make any operation on uninitialized data UB (like it is in C), meaning the comparison would already return UB.

Strictly speaking, this affects not just the fast path, but also the arbitrarily-sized case: bytes_eq might compare uninitialized bytes.

[BurntSushi]

But this means that e.g. for (u8, u16), which has size 4, it will transmute these pairs into u32 and compare them as integers.

If you don't mind me asking, is the transmute itself UB as well? In particular, I had thought that the in-memory representation of tuples isn't guaranteed? Or is it just the ordering of fields that isn't guaranteed?

[RalfJung]

Well, the code checks that the sizes match. Ignoring complicated issues around pointers, the only way in which transmuting a 4-byte piece of data to u32 is UB is if there are bit patterns that are not valid for u32 -- which boils down to the question of whether uninitialized bytes are allowed in u32.

[jeehoonkang]

It seems C/C++ standard committee members tend to agree that all bit patterns are valid for u32 and other unsigned integer types: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0907r4.html "For unsigned integer types, the bits of the object representation are ..." I think it's reasonable, because (once we agree to use two's complement) there's no other sane choice.

@RalfJung That sounds overly restrictive to me.

IMO, it should be possible to transmute a value of any type T into [u8; size_of::<T>()], read those bytes, and transmute back into T without UB. I would bet a lot of C and Rust code has been written under that assumption.

[jeehoonkang]

@stjepang To be very pedantic (sorry!), u8 is special in that everything can be legally cast to an array of u8 in Rust or char in C/C++. But u32 is not special in that sense, at least according to the C/C++ standard :(

And yet I agree with your sentiment: I believe representing an object of any type as u32 or any other unsigned integer types should not be UB. Edit: in other words, u8 should not be special at the first place.

[hanna-kruppe]

I am not aware of any precedent for u8 being special in Rust, and in fact all the discussion of the invariants of integer types I'm aware of treats all integer types alike. It's true that in C and C++, char and its signed/unsigned variants are very special, but that is precisely one of the thorny parts of writing unsafe code in those languages that Rust should try to smooth out.

Thanks for the clarification! I agree with you and would expect u8 to not get special treatment over other integer types. It's all just bytes to me.

[RalfJung]

This is Rust, not C++. :)

"For unsigned integer types, the bits of the object representation are ..." I think it's reasonable, because (once we agree to use two's complement) there's no other sane choice.

Remember that every bit can be 0, 1 or uninitialized. Even the C++ standards committee acknowledges this, though just indirectly -- namely, it acknowledges that "indeterminate values" can be "unstable" in the sense that x == x on an integer can be false. This can only be the case if there are states beyond 0 and 1.
I agree every sequence of 0 and 1 is fine in u32. But for uninitialized, it is far from reasonable to allow such bits in a u32. (And indeed I picked u32 as an arbitrary example here, the rules should be the same for all integer types.)

If we allow that, we have to answer other hard questions like what happens when you do arithmetic or comparison involving uninitialized bits. That's why I think that any uninitialized bits (outside of padding) should only exist in a MaybeUninit -- that is, a [MaybeUninit<u8>; N] can represent any data, but a [u8; N] cannot.
There is a conflict between permitting arithmetic and other operations on a type, and permitting it to hold "strange bits" (uninitialized bits, but also transmuted pointers can be a problem here) -- and since u8 permits arithmetic, it should not permit "strange bits".

It's all just bytes to me.

But bytes are complicated.

@RalfJung Fair enough, this is difficult. :(

It might be helpful to look at what C/C++ do on atomic compare-exchange with arbitrary (non-POD) data. This is interesting:

The comparison and copying are bitwise (similar to std::memcmp and std::memcpy); no constructor, assignment operator, or comparison operator are used.

When a weak compare-and-exchange would require a loop and a strong one would not, the strong one is preferable unless the object representation of T may include padding bits, (until C++20) trap bits, or offers multiple object representations for the same value (e.g. floating-point NaN). In those cases, weak compare-and-exchange typically works because it quickly converges on some stable object representation.

For a union with bits that participate in the value representations of some members but not the others, compare-and-exchange might always fail because such padding bits have indeterminate values when they do not participate in the value representation of the active member.

Padding bits that never participate in an object's value representation are ignored.

Source: https://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange

Boost atomics will do reinterpret_cast just like AtomicCell (source). However, on MSVC-8 and MSVC-9, spinlocks are used because otherwise the compiler would miscompile code (source).

[RalfJung]

Yeah, I figured this would be related to memcmp but unfortunately I was not able to find anything precise about memcmp on padding bytes. We have two kinds of problems here:

• Is the LLVM IR we currently generate for this valid, or does it have UB? The atomic comparison and byte_eq are working with poisoned data, so I am not sure. We could argue that atomic reads are frozen (which is an assumption AtomicCell already makes for volatile reads), which would help for the atomic comparisons but not for the fallback case (the data compared by byte_eq is read with a normal, non-atomic non-volatile load). However, the C++ spec you are quoting makes it sound like it is not at all clear that atomic reads are frozen...

• Beyond the LLVM rules, are there extra Rust rules this violates? This is where the part about having uninitialized bits in a u32 comes in. I'd prefer if this was all MaybeUninit<u32> but of course we don't have atomic operations on those...

[RalfJung]

@Amanieu @stjepang with the newly proposed ptr::freeze and if you remove AtomicCell::get_mut, I think this can be made sound. You basically just have to make sure that you only ever write frozen stuff into the cell, and freeze things before you compare them. In contrast to the "zero padding"-based schemes @Amanieu suggested at the all-hands, this does not require a special function that knows where the padding bytes are.

[Amanieu]

That doesn't exactly solve the problem though: compare_exchange returns a T with the current value in the atomic if the compare fails. In the most common use case (CAS loop) this will be passed back in as the current argument to compare_exchange in the next loop iteration.

However since the padding bytes in T are always undef, the freeze operation could freeze them into a different value than the one in the atomic, which would cause the next compare_exchange call to fail even though the value in the atomic was not changed since the last iteration. This could result in the CAS loop never converging to a stable state.