Atomic CAS with pad (#23, P0528R3) by AlexGuteniev · Pull Request #1029 · microsoft/STL

AlexGuteniev · 2020-07-10T19:44:25Z

Only use __builtin_zero_non_value_bits in compare_exchange_strong:
- Using in constructor will not work properly for atomic_ref
- Using in constructor will force to use it in store and exchange which is sub-optiomal
- Computing mask in CAS might be useful for LL/SC implementation, if masked CAS is exposed as intrinsic
Only expose the feature for C++20

stl/inc/atomic

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

stl/inc/atomic

AlexGuteniev · 2020-07-11T12:51:26Z

Now the test pass, I also improved a bit coverage by using more interesting bit pattern, and filed LLVM-46685. It is ready for review.

AlexGuteniev · 2020-07-11T13:16:50Z

I use _HAS_CXX20. It might make sense to have this feature unconditionally.

StephanTLavavej

One last batch of questions, then I think this will be ready - thanks!

stl/inc/atomic

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

stl/inc/atomic

Co-authored-by: Stephan T. Lavavej <stl@nuwen.net>

BillyONeal

I think this is ready to merge once the default constructed _Ty issue is resolved.

BillyONeal · 2020-07-20T23:10:34Z

stl/inc/atomic

+// Padding bits should not participate in cmpxchg comparison starting in C++20.
+// Clang does not have __builtin_zero_non_value_bits to exclude these bits to implement this C++20 feature.
+// The EDG front-end substitutes everything and runs into incomplete types passed to atomic<T>.
+#if _HAS_CXX20 && !defined(__clang__) /* TRANSITION, LLVM-46685 */ && !defined(__EDG__)


(Sure that's not a normal use case problem, but neither is this whole feature)

Indeed.

I'm OK with leaving it '20 only.

stl/inc/atomic

…orage_for formerly of <execution>.

BillyONeal

This passed in the DevDiv system.

BillyONeal · 2020-07-21T00:27:49Z

Replayed as https://devdiv.visualstudio.com/DefaultCollection/DevDiv/_git/msvc/pullrequest/262351

StephanTLavavej · 2020-07-21T00:46:09Z

stl/inc/atomic

+        __builtin_zero_non_value_bits(_Ptr());
+    }
+
+    _Ty& _Ref() noexcept {


Pre-existing:

Suggested change

_Ty& _Ref() noexcept {

_NODISCARD _Ty& _Ref() noexcept {

StephanTLavavej · 2020-07-21T00:46:38Z

stl/inc/atomic

+        return reinterpret_cast<_Ty&>(_Storage);
+    }
+
+    _Ty* _Ptr() noexcept {


As this function is newly added, let's make it nodiscard:

Suggested change

_Ty* _Ptr() noexcept {

_NODISCARD _Ty* _Ptr() noexcept {

StephanTLavavej · 2020-07-21T00:49:55Z

stl/inc/atomic

+    }
+
+    _Ty* _Ptr() noexcept {
+        return reinterpret_cast<_Ty*>(_STD addressof(_Storage));


_Storage is unsigned char[N] so it's immune to operator& evil:

Suggested change

return reinterpret_cast<_Ty*>(_STD addressof(_Storage));

return reinterpret_cast<_Ty*>(_Storage);

StephanTLavavej · 2020-07-21T00:57:18Z

stl/inc/atomic

 _STD_BEGIN
+// STRUCT TEMPLATE _Storage_for
+struct _Form_mask_t {};
+_INLINE_VAR constexpr _Form_mask_t _Form_mask;


C++14 had an annoying rule about default-init of const objects. That was fixed in C++17, but (1) even if it's not causing compiler errors in the tests, I'm worried about our compiler support matrix and (2) there are 0 occurrences of _INLINE_VAR constexpr \w+ \w+; in the STL, but 6 of _INLINE_VAR constexpr \w+ \w+\{\}; (namely adopt_lock, defer_lock, try_to_lock, ignore, piecewise_construct, and allocator_arg). There are an additional 5 occurrences of inline constexpr \w+ \w+\{\}; (all in C++17+ code) where the braces aren't necessary, but provided. There are 5 occurrences of inline constexpr \w+ \w+; all in ranges (ranges::cbegin etc.) where we omit the braces because it's C++20.

Suggested change

_INLINE_VAR constexpr _Form_mask_t _Form_mask;

_INLINE_VAR constexpr _Form_mask_t _Form_mask{};

StephanTLavavej · 2020-07-21T00:57:56Z

stl/inc/atomic

+template <class _Ty>
+inline constexpr bool _Cmpxchg_has_padding_bits_v =
+    !has_unique_object_representations_v<_Ty> && !is_floating_point_v<_Ty>;
+#endif


Missing #endif comment.

StephanTLavavej · 2020-07-21T01:11:54Z

stl/inc/atomic

-                break;
+        if constexpr (_Cmpxchg_has_padding_bits_v<_Ty>) {
+            _Storage_for<_Ty> _Mask{_Form_mask};
+            const long long _Mask_val = _Atomic_reinterpret_as<long long>(_Mask._Ref());


long long here appears to be incorrect, since this is for 1-byte _Ty. (Indeed, 2-byte below uses short.)

🤦‍♂️ Sorry for murdering your poor boy @AlexGuteniev

StephanTLavavej · 2020-07-21T01:20:33Z

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

+};
+#pragma warning(pop)
+
+#pragma pack(push)


Why is packing being pushed/popped here, when it's apparently not being altered?

StephanTLavavej · 2020-07-21T01:21:46Z

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

@@ -53,8 +70,35 @@ struct alignas(4) X4 {
    void set(char v) {


Nitpick: Some, but not all, of the set() functions are being changed to take their parameters by const value.

StephanTLavavej · 2020-07-21T01:23:24Z

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

 template <class X, std::size_t S>
 void test() {
    static_assert(sizeof(X) == S, "Unexpected size");
+    static_assert(!std::has_unique_object_representations_v<X>, "No padding type");


This test should directly include <type_traits> for std::has_unique_object_representations_v.

StephanTLavavej · 2020-07-21T01:26:07Z

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

 template <class X, std::size_t S>
 void test() {
    static_assert(sizeof(X) == S, "Unexpected size");
+    static_assert(!std::has_unique_object_representations_v<X>, "No padding type");


I find this static_assert message hard to understand (it is actually less clear than the condition being tested). Something like "Expected type to contain padding" would make sense.

stl/inc/atomic

CaseyCarter

I can't find anything Stephan missed; LGTM after fixing his comments.

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

Co-authored-by: Casey Carter <cartec69@gmail.com>

AlexGuteniev · 2020-07-21T03:11:09Z

@BillyONeal, have you noticed a comment where I am proposing to get back to the almost original design except handling atomic_ref differently - clear pading with atomic and after first fail?

#1029 (comment)

BillyONeal · 2020-07-21T03:35:02Z

@BillyONeal, have you noticed a comment where I am proposing to get back to the almost original design except handling atomic_ref differently - clear pading with atomic and after first fail?

#1029 (comment)

That looks OK to me (although since this is ~ready to land and atomic_ref is not yet ready to land I would prefer this land first)

stl/inc/atomic

AlexGuteniev · 2020-07-21T03:42:22Z

Ok, let's have this, and I'll propose another option with another PR after that (and by having PR on top of this, it would be easier to evaluate just the difference)

Co-authored-by: Stephan T. Lavavej <stl@nuwen.net>

BillyONeal · 2020-07-21T03:53:51Z

@AlexGuteniev I guess I misunderstood then? Since it seems your proposal there only affects atomic_ref, not atomic.

AlexGuteniev · 2020-07-21T04:33:28Z

@AlexGuteniev I guess I misunderstood then? Since it seems your proposal there only affects atomic_ref, not atomic.

The proposal

changes atomic to the originally designed (use __builtin_zero_non_value_bits in constructor of atomic, store, exchange, and for desired value of compare_exchange_*)
on top of that, for atomic_ref does not add anything to constructor. But adds another step in compare_exchange_*: if type may have padding, and padding bits mismatched, atomically zero them in storage lock and, and retry CAS just once.

Unfortunately, yes, this proposal is:

not uniform for atomic and atomic_ref, so has to go after atomic_ref
has even slightly more complexity that the original design (atomically zero atomic_ref in constructor vs in failed CAS).

The good side is avoiding inner CAS loop while still keeping atomic_ref constructor no-op.

BillyONeal · 2020-07-21T08:00:03Z

@AlexGuteniev: If it's more complex than the current plan of record and is only optimizing for the exceedingly rare atomic<type with padding bits> then I'm not sure it's worth it.

BillyONeal · 2020-07-21T08:00:39Z

Thanks for your contribution! 🎉

AlexGuteniev · 2020-07-21T08:05:46Z

is only optimizing for the exceedingly rare atomic<type with padding bits> then I'm not sure it's worth it.

Yes, for the simplicity, the current one is the best bet I think.
The proposal is only somewhat better for some use cases of atomic<type with padding bits> at the expense of being slightly worse for some others cases of atomic<type with padding bits>.

BillyONeal · 2020-07-21T08:07:33Z

And thanks for landing your first feature :D

AlexGuteniev · 2020-07-21T08:08:47Z

And thank you for your patience :)

Co-authored-by: Stephan T. Lavavej <stl@nuwen.net> Co-authored-by: Billy Robert O'Neal III <bion@microsoft.com> Co-authored-by: Casey Carter <cartec69@gmail.com>

Atomic CAS with pad (microsoft#23, P0528R3)

60884ab

AlexGuteniev requested a review from a team as a code owner July 10, 2020 19:44

formatting

edd535b

AlexGuteniev mentioned this pull request Jul 10, 2020

Implementation of std::atomic::wait #593

Merged

4 tasks

StephanTLavavej requested changes Jul 10, 2020

View reviewed changes

StephanTLavavej added the cxx20 C++20 feature label Jul 10, 2020

StephanTLavavej requested changes Jul 10, 2020

View reviewed changes

stl/inc/atomic Outdated Show resolved Hide resolved

AlexGuteniev added 2 commits July 11, 2020 05:34

Address review comments

c3c6c1c

more review comments

00f0ce4

AlexGuteniev mentioned this pull request Jul 11, 2020

P0528R3 Atomic Compare-And-Exchange With Padding Bits #23

Closed

AlexGuteniev marked this pull request as draft July 11, 2020 03:48

AlexGuteniev added 3 commits July 11, 2020 14:37

Disable for EDG too

2b635e5

Skip test for clang, also more interesting bits

facabae

TRANSITION, LLVM-46685

c072791

AlexGuteniev marked this pull request as ready for review July 11, 2020 12:49

AlexGuteniev requested a review from StephanTLavavej July 11, 2020 12:54

AlexGuteniev added 3 commits July 11, 2020 17:48

Improve TRANSITION comment

2250eec

Don't use has_unique_object_representations_v

cec43ef

longer

c6a7614

AlexGuteniev mentioned this pull request Jul 12, 2020

<atomic>: make compare_exchange_weak really weak on ARM64 #775

Open

StephanTLavavej requested changes Jul 15, 2020

View reviewed changes

AlexGuteniev added 3 commits July 15, 2020 09:26

centralize preprocessor

de3b54d

test cleanup

979cac7

undef

56793a7

AlexGuteniev requested a review from StephanTLavavej July 15, 2020 06:31

StephanTLavavej approved these changes Jul 15, 2020

View reviewed changes

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp Show resolved Hide resolved

stl/inc/atomic Outdated Show resolved Hide resolved

stl/inc/atomic Outdated Show resolved Hide resolved

AlexGuteniev and others added 2 commits July 15, 2020 12:03

Update stl/inc/atomic

dcdfa48

Co-authored-by: Stephan T. Lavavej <stl@nuwen.net>

Update stl/inc/atomic

97076e4

Co-authored-by: Stephan T. Lavavej <stl@nuwen.net>

BillyONeal suggested changes Jul 20, 2020

View reviewed changes

BillyONeal added 2 commits July 20, 2020 16:35

Merge remote-tracking branch 'origin/master' into cmpxchg

027e7b9

Fix compare_exchange when _Ty has a nontrivial default ctor using _St…

1b75b4e

…orage_for formerly of <execution>.

BillyONeal approved these changes Jul 21, 2020

View reviewed changes

StephanTLavavej requested changes Jul 21, 2020

View reviewed changes

stl/inc/atomic Show resolved Hide resolved

Fix STL CR comments.

76de2ad

BillyONeal requested a review from StephanTLavavej July 21, 2020 01:59

CaseyCarter approved these changes Jul 21, 2020

View reviewed changes

CaseyCarter reviewed Jul 21, 2020

View reviewed changes

tests/std/tests/P0528R3_cmpxchg_pad/test.cpp Outdated Show resolved Hide resolved

Update tests/std/tests/P0528R3_cmpxchg_pad/test.cpp

5280628

Co-authored-by: Casey Carter <cartec69@gmail.com>

StephanTLavavej approved these changes Jul 21, 2020

View reviewed changes

stl/inc/atomic Outdated Show resolved Hide resolved

Update stl/inc/atomic

c2feae9

Co-authored-by: Stephan T. Lavavej <stl@nuwen.net>

StephanTLavavej approved these changes Jul 21, 2020

View reviewed changes

BillyONeal merged commit c10ae01 into microsoft:master Jul 21, 2020

AlexGuteniev deleted the cmpxchg branch July 21, 2020 08:05

StephanTLavavej linked an issue Jul 21, 2020 that may be closed by this pull request

P0528R3 Atomic Compare-And-Exchange With Padding Bits #23

Closed

AlexGuteniev mentioned this pull request Jul 25, 2020

atomic_ref (#2, p0019r8) #843

Merged

	return reinterpret_cast<_Ty*>(_STD addressof(_Storage));
	return reinterpret_cast<_Ty*>(_Storage);

	_INLINE_VAR constexpr _Form_mask_t _Form_mask;
	_INLINE_VAR constexpr _Form_mask_t _Form_mask{};

Conversation

AlexGuteniev commented Jul 10, 2020

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

AlexGuteniev commented Jul 11, 2020

Uh oh!

AlexGuteniev commented Jul 11, 2020

Uh oh!

StephanTLavavej left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

BillyONeal left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

BillyONeal left a comment

Choose a reason for hiding this comment

Uh oh!

BillyONeal commented Jul 21, 2020

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

CaseyCarter left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

AlexGuteniev commented Jul 21, 2020

Uh oh!

BillyONeal commented Jul 21, 2020

Uh oh!

Uh oh!

AlexGuteniev commented Jul 21, 2020

Uh oh!

BillyONeal commented Jul 21, 2020

Uh oh!

AlexGuteniev commented Jul 21, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

BillyONeal commented Jul 21, 2020

Uh oh!

BillyONeal commented Jul 21, 2020

AlexGuteniev commented Jul 21, 2020 •

edited

Loading