DWCAS fun

[JBakamovic]

Hi Martin,

There are a loath of interesting utilities you host in your repo, this one, in particular, caught my attention because I can see you're using DWCAS lock-free technique.

Given that I occasionally go through the lock-free programming rabbit hole myself, I hope you don't mind sharing a few things I have with you here.

According to the x86-64 manual

Note that CMPXCHG16B requires that the destination (memory) operand be 16-byte aligned.

the first precondition for DWCAS appears to be that destination operand must be 16-byte aligned.

Given I don't see this is a case here

intrusive_lfstack/include/avakar/intrusive/lfstack.h

Line 24 in ab522c2

struct _next_t

perhaps this should be transformed to

alignas(16) struct _next_t

in order to really materialize this guarantee?

Also, I made some experiments now, but also in the past which is why I resonated with this code, and I remember that support for DWCAS was a bit kludgy, to say the least.

My findings were, and still are, that essentially support for DWCAS on GCC+Linux is broken. E.g. no CMPXCHG16B instruction will be emitted but rather a call into __atomic_compare_exchange which has the freedom, as you already know, to use the mutexes beneath and which it probably will given the absence of CMPXCHG16B in generated codegen. This can be seen in this godbolt example if you remove the static_assert.

So, it seems like even plain clang+Linux isn't sufficient unless you compile the code with -march=native. I found out that -mcx16 seems to have the same effect. This, however, doesn't help with the GCC and I think only the very old versions of GCC handled it correctly.

Good thing is that at least static_assert such as

static_assert(std::atomic<_next_t>::is_always_lock_free);

will be triggered correctly for all the combinations I tried

Only true solution for all of this fun, as I see it, is to handcraft the assembly, or another option would be to use boost because it handles it already that way.

Cheers,
Adi

[avakar]

Hi, Adi!

perhaps this should be transformed to alignas(16) struct _next_t

That's not really necessary, std::atomic<...> adjusts the alignment accordingly. You would indeed have to align the struct if you wanted to use it with std::atomic_ref, for example. Try the following.

#include <atomic>

struct _next_t
{
        void * node;
        void * pincount;
};

// Note that std::atomic aligns itself so that CMPXCHG16B can be used
static_assert(alignof(_next_t) == 8);
static_assert(alignof(std::atomic<_next_t>) == 16);

Conversely, over-aligning the structure might be harmful. Currently, alignof(lfstack_node) == 8, but if I over-aligned _next_t to 16, then alignof(lfstack_node) would be 16, potentially forcing user's nodes to pack less densely.

---

no CMPXCHG16B instruction will be emitted

Yes, lfstack forwards std::atomic<lfstack_node::_next_t>::is_always_lock_free as lfstack<...>::is_always_lock_free (and there's is_lock_free() as well). You need to assert on that if you absolutely require absence of mutexes.

It's not that the support in the compiler is broken, the problem is that there are (relatively few) AMD64 processors without CMPXCHG16B, therefore std::atomic needs to be able to fallback to mutexes in this case -- thus the call to __atomic_compare_exchange, which dynamically decides whether to use a mutex or the instruction.

I can confirm that on my machine, without any g++ flags, __atomic_compare_exchange_16 gets called, which immediately branches to the following.

=> 0x7ffff7faf9f0:      endbr64
   0x7ffff7faf9f4:      mov    %rsi,%r9
   0x7ffff7faf9f7:      push   %rbx
   0x7ffff7faf9f8:      mov    %rdi,%r8
   0x7ffff7faf9fb:      mov    (%rsi),%rsi
   0x7ffff7faf9fe:      mov    0x8(%r9),%rdi
   0x7ffff7fafa02:      mov    %rdx,%rbx
   0x7ffff7fafa05:      mov    %rsi,%rax
   0x7ffff7fafa08:      mov    %rdi,%rdx
   0x7ffff7fafa0b:      lock cmpxchg16b (%r8)
   0x7ffff7fafa10:      mov    %rdi,%rcx
   0x7ffff7fafa13:      xor    %rax,%rsi
   0x7ffff7fafa16:      mov    $0x1,%edi
   0x7ffff7fafa1b:      xor    %rdx,%rcx
   0x7ffff7fafa1e:      or     %rsi,%rcx
   0x7ffff7fafa21:      je     0x7ffff7fafa2c
   0x7ffff7fafa23:      mov    %rax,(%r9)
   0x7ffff7fafa26:      xor    %edi,%edi
   0x7ffff7fafa28:      mov    %rdx,0x8(%r9)
   0x7ffff7fafa2c:      mov    %edi,%eax
   0x7ffff7fafa2e:      pop    %rbx
   0x7ffff7fafa2f:      ret

I'd say that the fact that -march=native removes the dynamic branch completely indicates that the compiler support is not only not broken, but awesomely good. :)

[JBakamovic]

std::atomic<...> adjusts the alignment accordingly.

Later on, that's kinda exactly what my thoughts were. Why not SFINAE this use-case in the library and align the storage as necessary? Thanks for confirming and clarifying this for lazy me!

if I over-aligned _next_t to 16, then alignof(lfstack_node) would be 16, potentially forcing user's nodes to pack less densely.

Yes, that's true. Perhaps a saner version of my original suggestion would be to alignas(16) std::atomic<_next_t> _top; but given that std::atomic already does that for us it, of course, makes no sense.

std::atomic needs to be able to fallback to mutexes in this case -- thus the call to __atomic_compare_exchange, which dynamically decides whether to use a mutex or the instruction.

Right, the perils of ifunc but I still found it intriguing why

static_assert(std::atomic<_next_t>::is_always_lock_free);

is triggered and now during this discussion, I think I figured it out.

1. With -march=native we get the cmpxchg16b inlined directly and static_assert is not triggered.
2. Without -march=native we get __atomic_compare_exchange_16, which, as you demonstrated, will highly likely re-route to cmpxchg16b under the hood. But we will hit the static_assert which is a confusing bit.

2nd case seemed a little bit unexpected because although the resulting codegen will make use of cmpxchg16b, we will nonetheless hit the static_assert suggesting that our HW doesn't have that capability.

I thought this was a bug but according to the standard, ATOMIC_..._LOCK_FREE macros can expand to the value which suggests that type is "sometimes" lock-free.

The ATOMIC_..._LOCK_FREE macros indicate the lock-free property of the corresponding atomic types, with the signed and unsigned variants grouped together. The properties also apply to the corresponding (partial) specializations of the atomic template. A value of 0 indicates that the types are never lock-free. A value of 1 indicates that the types are sometimes lock-free. A value of 2 indicates that the types are always lock-free.

And although the standard is not explicit about what "sometimes lock-free" means, I think this is exactly the case from above. It covers the ifunc runtime checks.

The reasoning behind this is probably what you said, that some older CPUs don't have DWCAS available, so compilers are a bit careful in this regard but I'd expect GCC to inline (and not hit the static_assert) if I built the code with the -march=skylake switch. According to wiki, cmpxchg16b is made available with x86-64-v2 spec and Intel-wise first microarchitecture implementing it were Nehalem and Jaguar, so Skylake definitely has this instruction.

[avakar]

Note that std::atomic always had atomic<>::is_lock_free(), which tells you -- at runtime -- whether all supported operations are lock-free. On the other hand, is_always_lock_free was added in C++17, is constexpr, and will be true only if the lock-freeness is known at compile-time to be guaranteed.

In my case, for example, I get atomic<_next_t>::is_always_lock_free as false at compile time, but atomic<_next_t>::is_lock_free() as true at runtime.

I agree with your assessment of -march=skylake, I would expect is_always_lock_free to be true there. CPUs that don't have CMPXCHG16B are extremely rare.

[JBakamovic]

In my case, for example, I get atomic<_next_t>::is_always_lock_free as false at compile time, but atomic<_next_t>::is_lock_free() as true at runtime.

That makes sense. Thanks for the discussion!