A bit of googling suggests that not even all x86_64 CPUs have the necessary instruction.

As far as I’m aware, all AMD CPUs and all Intel CPUs after the Core 2 support it. That’s basically anything <10 years old and most things <15. Every 32-bit x86 CPU including and after the 486 provides the analogous 32-bit instruction. Linux also uses this for RCU, so hits a bunch of slow paths if it isn’t available.

Did you find your implementation reasonably portable to other 64-bit architectures (I assume 32-bit ones are out of the question)?

You can see the set of supported architectures in the architecture abstraction layer directory. We support:

• x86-[64,32], including x86-64 in an SGX enclave (which gives you a slightly restricted set of instructions)
• Arm (A32/T32 and A64).
• PowerPC[32,64]
• RISC-V [32,64]
• SPARC[32,64]

CHERI support didn’t quite make it for 0.6, it should be landing in the main branch in the next week or two. MTE support should come at a similar time.

I believe we test all of these in CI with QEMU user mode (unless we have real hardware available).

Also, mimalloc doesn’t seem to have this restriction. If you have time to elaborate why you need 128-bit atomics, I for one would be interested to hear.

We use it on x86 for ABA protection in our [multi,single]-producer, multi-consumer stack implementations. The MPMC stack is used for allocating allocators (when you free an allocator, you push it onto a stack, the next one is then popped off) and we use both for managing chunks. We use the SPMC stack for per-allocator chunk collections (multi-consumer because a thread can wake up from an OS low-memory notification and go and return all not-in-use chunks to the OS), MPMC for a global pool so that we can grab chunks from it anywhere.

Most architectures provide load-linked / store-conditional (LL/SC) either in addition to or instead of compare-and-swap (CAS) as a primitive. These are intrinsically ABA-safe. The problem with CAS as a primitive is that you can read a value, another thread then changes the value and changes it back, and then your CAS will succeed. With LL/SC, the SC will fail if another thread has written to the same memory location since the LL. LL/SC, in theory, has forward-progress guarantee problems but most implementations (and, I believe, the PowerPC spec) locks the cache line in exclusive state for a few cycles so that common LL/SC sequences will always proceed.

If you have doubleword compare-and-swap (DCAS) as a primitive then you can avoid ABA by using a pair of the real value and a counter and increment the counter on every store. This means that ABA becomes {A0}{B1}{A2} and so the second DCAS will fail because {A0} == {A2} will fail in the compare.

I’m not sure how mimalloc implements the things that we use the stacks for.

fwiw windows 8.1 and onward require cmpxchg16b, so it is hardly niche

I haven’t looked at the code, but I wouldn’t guess this prevents 32-bit archs from running; they still have double-word cases

I use the following for double-cas on gcc. @david_chisnall may be of interest. Swapping out the asm block for __atomic_compare_exchange on clang Just Works, as should InterlockedCompareExchange128 on msvc.

typedef struct { int64_t x,y; } __attribute__((aligned(16))) DW;
#define DCAS(dst,old,new...) ({ bool _dcas_r; \
 __asm__("lock cmpxchg16b %3" : "=@cce" (_dcas_r), \
                                "+a" ((old)->x), \
                                "+d" ((old)->y), \
                                "+m" (*(dst)) \
                              : "b" ((new).x), \
                                "c" ((new).y)); \
 _dcas_r; })