What is the correct and optimal implementation of atomic_ref and atomic with padding bits?

user_2945027 0
Viewed 307

TL;DR: Should std::atomic CAS with padding bits zero padding bits in constructor, or deal with them via CAS retries / masked LL/SC? Consider also atomic_ref CAS, and atomic wait for both atomic and atomic_ref.

Some trivial types in C++ do not have unique_representation, std::has_unique_object_representations_v is false for them, it means, that values that are equivalent may not memcmp bit-wise equal.

One of reasons for that is having padding bits. Padding bits are unused bit-field bits, structure alignment bytes, or extra padding for, say, 10-byte float.

C++2a has excluded padding atomic<T>::compare_exchange_strong and compare_exchange_weak comparison. See:

Now the question is, how can this be correctly and efficiently implemented, especially taking into account having atomic_ref. x86 support only bitwise equality in CAS, I expect it is similar with other CPU architectures.

  • One way to do it is to clear padding bits form source value in constructor, store, exchange, and clear the desired value in compare_exchange_*. This way it seems that atomic_ref constructor has to be atomic, and there's a "pay for something you don't use", if compare_exchange operation is not used.
  • Another way I see is to copy the padding bits from observed value in compare_exchange loop. So CAS loop would exit only in value bits mismatch. This seem to defeat the purpose of the division between strong and weak CAS, since weak CAS should not consistently fail, and with this approach it may. Although LL/SC-based CAS seem to be able to do its inner comparison with padding bit naturally excluded, so weak CAS without loop is possible.

So the questions here are:

  • Which of the approaches (if any) is correct? Are there other correct approaches?
  • If multiple approaches are correct, which is generally more efficient?

Note that atomic<T>::wait / atomic_ref<T>::wait also has to deal with padding bits, and the approach has to be shared.

Note that there is an easy way to obtain non-zero padding bits:

struct S {
  int i : 17;
};
S* s = (S*)malloc(sizeof(S));
s->i = 1;

struct S2 {
  std::uint8_t  j;
  std::uint16_t k;
};

S2* s2 = (S2*)malloc(sizeof(S2));
s2->j = 2;
...
s2->k = 3;
stdatomic c++20 micro-optimization x86
1 Answers

The atomic_ref<T> constructor should always be trivial, not touching the referenced object. Nobody wants an extra atomic store or RMW to clear the padding bits on the off chance that they're non-zero. atomic_ref is designed to be re-constructed every time you want to access an object atomically. It needs to optimize away.

Also, we don't want to make code using non-atomic objects slower just in case something somewhere might use atomic_ref.

(That said, if the padding is a whole number of bytes, those could be stored to with 1 or more plain store(s) before a CAS. Nothing (except raw CAS instructions) should ever depend on what values are read from those padding bits / bytes so it doesn't matter if there's potential for tearing of the object representation. The padding isn't part of the T value, so the value can't be torn.)

I don't see any clear way to implement everything efficiently for atomic_ref<T>; objects with non-zero padding bits can happen easily. This ISO C++ change seems hard to implement on machines with hardware CAS, not LL/SC. ISO C++ has historically been very conservative about any change that can't easily be supported on existing mainstream ISAs so this seems strange unless there's some trick they had in mind that I'm not seeing.

In most cases it won't be harmful to use the existing behaviour, and could be swept under the rug as being allowed by the "as-if" rule when it happens in a CAS retry loop that uses the last-seen value of the object as the "desired". Same goes for atomic<T>.

But that doesn't apply for code that creates a new T and uses it as the "expected" arg to a CAS, or where each CAS failure has visible side-effects.

For atomic<T> (not atomic_ref<T>), it might be possible to implement the proposed C++20 change (CAS compares values, not memcmp object-representations) without hurting performance for non-atomic objects: Ensure padding bits/bytes are always in the same canonical state, 0 being the obvious choice.

Sanitize / canonicalize the padding bits in the atomic<T> constructor, and in every new value used with store, exchange and CAS.

C++20 also changes the default constructor for std::atomic<T> from being trivial (no initialization except for zero-init of static storage) to (C++20) value-initializing the underlying object with T(), i.e. zero for primitive types. (C++20 also deprecates std::atomic_init, which nobody used because it was a clunky design.)

So I think we can assume that every std::atomic<T> object has been constructed by a std::atomic<T> constructor. The possible problem is that some existing code might just cast a pointer to atomic<T>* and use it without using placement-new. If that's officially Undefined Behaviour in C++20, then it's that code's problem (especially if it has any expectations about what CAS will do on a T with padding).

The C++20 constructors should ensure that any padding is zeroed, not just value bits. Further atomic operations shouldn't change this, as long as CAS ensures that desired is similarly canonical. And exchange and store similarly sanitize / canonicalize their inputs if they contain any padding bits.

On x86-64, I think the only primitive type with padding is 10-byte long double on x86-64 System V; on Windows it's the same as double.

As discussed in comments, this canonicalization could maybe take the form of widening stores to the part of the object that comes right before the padding. e.g. x86-64 struct { int i; void *p; } access to .i could do a 64-bit store to make sure the 32 bits of padding after the int were zeroed.

Relying on this for objects in memory would have to be part of the ABI, but if we only do it as part of store, exchange, and CAS then it wouldn't have to be ABI-visible for normal objects. But yes, it would be an ABI change to require it for atomic<T>

Original answer, not accounting for the C++20 change

This is more like guidelines for how to make a nice C++17 implementation; I hadn't really read the C++20 change when I wrote this, I was thinking of it as a "nice to have", not a standards requirement. Some of this might still be useful. I think it's impossible to have full safety for atomic_ref without efficiency problems (in all code touching a struct with padding). So IMO this should probably remain a minor wart.

If you're ever writing padding bits explicitly, write them as zero when convenient. (i.e. when you have to make up some padding bits to go with some fresh value bits.) If some other code happens to use atomic_ref<> on this object, they'll avoid spurious CAS failure on the first iteration if your expected also uses zeros for the padding bits.

Don't leave padding unwritten when first initializing an object; e.g. widen a dword store to qword to cover both an int and the alignment-padding before a void* in a struct. Usually that will let you store zeros for basically free.

But don't let this stop you from optimizing copies of such objects into SIMD movdqa or whatever (i.e. memcpy); if it would take extra work to canonicalize the padding bits to zero, don't do it. Hopefully they'll already be zero, and in the rare case they're not, a CAS will sort it out if one is ever used on this object.

Don't make the common case worse (for non-atomic objects) just because of the existence of atomic_ref. If people use CAS_weak or CAS_strong on a C++ object with padding, they need to be prepared for the possibility of spurious failure due to mismatched padding. This is a real thing that can happen on other C++ implementations, so making less efficient code in other places to make it impossible is a bad idea.

This seem to defeat the purpose of the division between strong and weak CAS, since weak CAS should not consistently fail, and with this approach it may

To avoid spurious failures: Make sure that expected = x.load() loads the correct padding bits, not just the value bits, so an x.CAS(expected, desired) will succeed if x hasn't changed. Most CAS on objects with padding start by loading the old value.

Also when CAS updates expected, make sure that updates the padding bits in the object, same as a load. (It's important that both ways work: some badly written (or more complex) CAS retry loops do a .load inside the loop, instead of using the expected from the last attempt.)

In the majority of cases, that avoids spurious failure due to padding bits, or at worst causes one retry as the padding bits are updated. That seems fine.

But possibly you'd want to do tmp = x.load() and mutate that tmp before using that as the expected for the next CAS, maybe to wait for some other thread to have done something. Or create a tmp from scratch.

If we allow the compiler to re-generate the padding bits in tmp when it's modified, we could have CAS failure that a valid loop will never escape from. This is arguably the code's fault for doing that on an object with padding, so IDK if this is something compilers really need to handle. Ideally the optimizer should see that a value is being used as an "expected" for CAS and preserve padding when mutating, but that's only practical in limited cases.

I don't know how practical this hypothetical example is. In most cases a programmer can avoid it by simply filling the padding in a struct with a dummy variable, or using a wider integer type. x87 long double is a possible problem, though; on x86-64 System V it has sizeof(long double) == 16, with 6 of those bytes being padding. So you can't put your own bytes there.

Related: Intel's compiler apparently has a bug where memcmp is optimized into a compare of just the value bits, for a struct containing int and void*. So memcmp can say they're equal, but then CAS fails: compare_exchange_strong failing despite data matching expected value. I think this is a real bug; ISO C++ says memcmp compares the full object representation, same as what CAS does. I think ISO C++ nails down enough about padding bits that on a given implementation you can know they exist and where they are, so there isn't room for the as-if rule to pretend that they changed value between C++ statements.

LL/SC CAS

Yes, I'd recommend only comparing based on value bits if you have to do it manually to implement CAS on top of LL/SC. That's probably what most people really want. (Unless that makes the code less efficient, e.g. with bitfields. If it's a lot easier to just compare a whole register, do that instead of e.g. unpacking a byte and 16-bit element from a 32-bit register.)

user_2241320
Related