6

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.

3 Answers 3

11

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;
}
2
  • Why did you have to post that, makes my inline assembler look so rubbish ;) Aug 11, 2013 at 23:35
  • Hah! Well, VC++ optimizes that code like rubbish and supports no inline asm for 64-bit so don't feel bad. Aug 11, 2013 at 23:44
4

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.

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.

3
  • 1
    your statement "to do something atomically, a basic starting point is that it is a single instruction" is inaccurate. It either (1) needs to be a single instruction, or (2) the processor needs to support operations such as LL/SC or CMPXCHG or hardware transactional memory, that allow lock-free spinloops using these operations to be used to create more complicated atomic operations. Or (3) you need to using a locking protocol.
    – Krazy Glew
    Jan 25, 2016 at 15:01
  • @MatsPetersson, do you need a lock in front of the cmpxcchg16b?
    – ergohack
    Mar 14, 2018 at 0:37
  • @ergohack: I think you are right, I've added a lock. Mar 14, 2018 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.