P0528R3 Atomic Compare-And-Exchange With Padding Bits

[StephanTLavavej]

P0528R3 Atomic Compare-And-Exchange With Padding Bits
P1123R0 Atomic Compare-And-Exchange With Padding Bits For atomic_ref

This needs compiler support, tracked by Microsoft-internal VSO-778892 and MSVC-PR-233835, which will be available in VS 2019 16.7 Preview 1.

[AlexGuteniev]

What is intrinsic name?

[CaseyCarter]

Oh, I suppose that would be useful, eh?

The intrinsic is __builtin_zero_non_value_bits. It takes a pointer to an object, and zeroes padding bits in the representation of that object when evaluated at runtime. At compiletime / in a constant expression it has no effect. Together, that means we can write something like:

constexpr atomic(T x) noexcept : stored_value(x) {
  __builtin_zero_non_value_bits(&stored_value);
}

without any weird is_constant_evaluated dance to avoid the intrinsic in constant-initializers.

(And now I'm wondering what the intrinsic does when pointed at a union whose member types have representations with varying amounts of padding, e.g., union { char c; int i; double d; }. It can't know which member is active. EDIT: Simple enough: that union has no padding. All 64 bits of its object representation are value bits since they are sometimes used to represent a value. Yes, that means such a union with the char member active can break with CAS in an atomic, and that's expected.)

[AlexGuteniev]

Oh, I suppose that would be useful, eh?

Honestly, this one is not that much useful.

I mean it can be used to implement atomic<T>::compare_exchange_*, it can also be used to implement properly atomic<T>::wait.

But it is not useful to implement atomic_ref<T>::compare_exchange_* or atomic_ref<T>::wait.

Need a better intrinsic.

[CaseyCarter]

But it is not useful to implement atomic_ref<T>::compare_exchange_* or atomic_ref<T>::wait.

Could we rewrite the representation of the object in memory with padding bits zeroed in atomic_ref's constructor? Without some way to fix the values of the padding bits I don't think these functions can be made lock-free: processors don't have operations that atomically compare value representations.

[AlexGuteniev]

Could we rewrite the representation of the object in memory with padding bits zeroed in atomic_ref's constructor?

It is dangerous. __builtin_zero_non_value_bits is not atomic.

I'm also not sure if it is useful. The value can be rewritten later not with this or other atomic_ref, but directly by other means.

Without some way to fix the values of the padding bits I don't think these functions can be made lock-free: processors don't have operations that atomically compare value representations.

At least strong CAS can be implemented: on failure, if failure is due to padding bits, consider it spurious, and retry with padding bits set to those from the value observed by CAS.

Probably it is not the best way to implement it generally, so apparently we'll should still go with that intrinsic for atomic and special-case atomic_ref.

Are test feature macros distinct from atomic and atomic_ref ?

[StephanTLavavej]

https://isocpp.org/std/standing-documents/sd-6-sg10-feature-test-recommendations records all feature-test macros; AFAIK these papers don't have macros.

[AlexGuteniev]

Actually, I would prefer detection of padding bits, and if there are, fall back to strong CAS that is retrying on padding bits difference. For both atomic_ref and atomic.

The point is that with padding bits workaround implemented inside CAS, we don't need to pay for the existence of CAS if we use only constructor, load, store and exchange

Actually, I thing even weak CAS can be made. Just do load before CAS and grab expected padding bits, and move them into the value being compared against.

And as weak CAS is implemented using LL/SC, there is a way to handle padding bits as a part of LL/SC based weak CAS just by altering inner comparison. This applies to strong CAS on LL/SC as well.

[CaseyCarter]

Could we rewrite the representation of the object in memory with padding bits zeroed in atomic_ref's constructor?

It is dangerous. __builtin_zero_non_value_bits is not atomic.

The last modification to the value denoted by an atomic_ref before that atomic_ref begins its lifetime is not atomic with or without my suggestion.

I'm also not sure if it is useful. The value can be rewritten later not with this or other atomic_ref, but directly by other means.

Not during the lifetime of an atomic_ref, it can't: "While any atomic_ref instances exist that reference the *ptr object, all accesses to that object shall exclusively occur through those atomic_ref instances."

Without some way to fix the values of the padding bits I don't think these functions can be made lock-free: processors don't have operations that atomically compare value representations.

At least strong CAS can be implemented: on failure, if failure is due to padding bits, consider it spurious, and retry with padding bits set to those from the value observed by CAS.

Fair enough; I observe that __builtin_zero_non_value_bits is sufficient to implement the "if failure is due to padding bits" part of your suggested CAS behavior (we zero the padding of expected on entry, and update it to actual if expected is equal to a copy of actual with padding bits zeroed).

[AlexGuteniev]

Not during the lifetime of an atomic_ref, it can't: "While any atomic_ref instances exist that reference the *ptr object, all accesses to that object shall exclusively occur through those atomic_ref instances."

Ok, assume one atomic_ref is construction, another is already used. Or two atomic_refs are constructed at the same time.

Fair enough; I observe that __builtin_zero_non_value_bits is sufficient to implement the "if failure is due to padding bits" part of your suggested CAS behavior (we zero the padding of expected on entry, and update it to actual if expected is equal to a copy of actual with padding bits zeroed).

I think it is a bit suboptimal for x86 and very suboptimal for ARM.

My suggestion:

1. Implement uint64_t __builting_get_valu_bit_mask64(void*) thru uint8_t __builting_get_valu_bit_mask8(void*). For x64, also 128-bit version is needed.
2. For x86/x64, compare this way: (expected ^ observed) & significant_bit_mask
3. For ARM: Add _InterlockedCompareExchangeMasked intrinisc, that would implement masked test in its embedded comparison
4. For future weak ARM <atomic>: make compare_exchange_weak really weak on ARM64 #775 : Implement weak version as WeakMasked, not just weak.

[AlexGuteniev]

So, would you request another intrinsics, or still want to implement with the one you have?

I suggest new, since with the current:

• The implementation cannot be optimized for the case when no no-value bits on x86
• The implementation is very suboptimal on ARM