How to atomically add and fetch a 128-bit number in C++?

Question

I use Linux x86_64 and clang 3.3.

Is this even possible in theory?

std::atomic<__int128_t> doesn't work (undefined references to some functions).

__atomic_add_fetch also doesn't work ('error: cannot compile this atomic library call yet').

Both std::atomic and __atomic_add_fetch work with 64-bit numbers.

Answer 1

It's not possible to do this with a single instruction, but you can emulate it and still be lock-free. Except for the very earliest AMD64 CPUs, x64 supports the CMPXCHG16B instruction. With a little multi-precision math, you can do this pretty easily.

I'm afraid I don't know the instrinsic for CMPXCHG16B in GCC, but hopefully you get the idea of having a spin loop of CMPXCHG16B. Here's some untested code for VC++:

// atomically adds 128-bit src to dst, with src getting the old dst.
void fetch_add_128b(uint64_t *dst, uint64_t* src)
{
    uint64_t srclo, srchi, olddst[2], exchlo, exchhi;

    srchi = src[0];
    srclo = src[1];
    olddst[0] = dst[0];
    olddst[1] = dst[1];

    do
    {
        exchlo = srclo + olddst[1];
        exchhi = srchi + olddst[0] + (exchlo < srclo); // add and carry
    }
    while(!_InterlockedCompareExchange128((long long*)dst,
                                          exchhi, exchlo,
                                          (long long*)olddst));

    src[0] = olddst[0];
    src[1] = olddst[1];
}

Edit: here's some untested code going off of what I could find for the GCC intrinsics:

// atomically adds 128-bit src to dst, returning the old dst.
__uint128_t fetch_add_128b(__uint128_t *dst, __uint128_t src)
{
    __uint128_t dstval, olddst;

    dstval = *dst;

    do
    {
        olddst = dstval;
        dstval = __sync_val_compare_and_swap(dst, dstval, dstval + src);
    }
    while(dstval != olddst);

    return dstval;
}

Answer 2

That isn't possible. There is no x86-64 instruction that does a 128-bit add in one instruction, and to do something atomically, a basic starting point is that it is a single instruction (there are some instructions which aren't atomic even then, but that's another matter).

You will need to use some other lock around the 128-bit number.

Edit: It is possible that one could come up with something that uses something like this:

 __volatile__ __asm__(
    "     mov            %0, %%rax\n"
    "     mov            %0+4, %%rdx\n"
    "     mov            %1,%%rbx\n"
    "     mov            %1+4,%%rcx\n"
    "1:\n
    "     add            %%rax, %%rbx\n"
    "     adc            %%rdx, %%rcx\n"
    "     lock;cmpxcchg16b %0\n"
    "     jnz            1b\n"
    : "=0"
    : "0"(&arg1), "1"(&arg2));

That's just something I just hacked up, and I haven't compiled it, never mind validated that it will work. But the principle is that it repeats until it compares equal.

Edit2: Darn typing too slow, Cory Nelson just posted the same thing, but using intrisics.

Edit3: Update loop to not unnecessary read memory that doesn't need reading... CMPXCHG16B does that for us.

Answer 3

Yes; you need to tell your compiler that you're on hardware that supports it.

This answer is going to assume you're on x86-64; there's likely a similar spec for arm.

From the generic x86-64 microarchitecture levels, you'll want at least x86-64-v2 to let the compiler know that you have the cmpxchg16b instruction.

Here's a working godbolt, note the compiler flag -march=x86-64-v2: https://godbolt.org/z/PvaojqGcx

For more reading on the x86-64-psABI, the spec is published here.