achieve GCC cas function for version 4.1.2 and earlier

Question

My new company project, they want the code run for the 32-bit, the compile server is a CentOS 5.0 with GCC 4.1.1, that was the nightmare.
There are lots of functions using in the project like __sync_fetch_and_add was given in GCC 4.1.2 and later.

I was told can not upgrade GCC version, so I have to make another solution after Googling for several hours.

When I wrote a demo to test, I just got the wrong answer, the code blow want to replace function __sync_fetch_and_add

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

static int count = 0;

int compare_and_swap(int* reg, int oldval, int newval) 
{
    register char result;
#ifdef __i386__
    __asm__ volatile ("lock; cmpxchgl %3, %0; setz %1" 
                     : "=m"(*reg), "=q" (result) 
                     : "m" (*reg), "r" (newval), "a" (oldval) 
                     : "memory");
    return result;
#elif defined(__x86_64__)
    __asm__ volatile ("lock; cmpxchgq %3, %0; setz %1" 
                     : "=m"(*reg), "=q" (result) 
                     : "m" (*reg), "r" (newval), "a" (oldval) 
                     : "memory");
    return result;
#else
    #error:architecture not supported and gcc too old
#endif

}

void *test_func(void *arg)
{
    int i = 0;
    for(i = 0; i < 2000; ++i) {
        compare_and_swap((int *)&count, count, count + 1);
    }

    return NULL;
}

int main(int argc, const char *argv[])
{
    pthread_t id[10];
    int i = 0;

    for(i = 0; i < 10; ++i){
        pthread_create(&id[i], NULL, test_func, NULL);
    }

    for(i = 0; i < 10; ++i) {
        pthread_join(id[i], NULL);
    }
    //10*2000=20000
    printf("%d\n", count);

    return 0;
}

Whent I got the wrong result:

[root@centos-linux-7 workspace]# ./asm
17123
[root@centos-linux-7 workspace]# ./asm
14670
[root@centos-linux-7 workspace]# ./asm
14604
[root@centos-linux-7 workspace]# ./asm
13837
[root@centos-linux-7 workspace]# ./asm
14043
[root@centos-linux-7 workspace]# ./asm
16160
[root@centos-linux-7 workspace]# ./asm
15271
[root@centos-linux-7 workspace]# ./asm
15280
[root@centos-linux-7 workspace]# ./asm
15465
[root@centos-linux-7 workspace]# ./asm
16673

I realize in this line

compare_and_swap((int *)&count, count, count + 1); 

count + 1 was wrong!

Then how can I implement the same function as __sync_fetch_and_add. The compare_and_swap function works when the third parameter is constant.

By the way, compare_and_swap function is that right? I just Googled for that, not familiar with assembly.

I got despair with this question.

………………………………………………………………………………………………………………………………………………………………………………………………………………………

after seeing the answer below,I use while and got the right answer,but seems confuse more. here is the code:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

static unsigned long  count = 0;

int sync_add_and_fetch(int* reg, int oldval, int incre) 
{
    register char result;
#ifdef __i386__
    __asm__ volatile ("lock; cmpxchgl %3, %0; setz %1" : "=m"(*reg), "=q" (result) : "m" (*reg), "r" (oldval + incre), "a" (oldval) : "memory");
    return result;
#elif defined(__x86_64__)
    __asm__ volatile ("lock; cmpxchgq %3, %0; setz %1" : "=m"(*reg), "=q" (result) : "m" (*reg), "r" (newval + incre), "a" (oldval) : "memory");
    return result;
#else
    #error:architecture not supported and gcc too old
#endif

}


void *test_func(void *arg)
{
    int i=0;
    int result = 0;
    for(i=0;i<2000;++i)
    {
        result = 0;
        while(0 == result)
        {
            result = sync_add_and_fetch((int *)&count, count, 1);
        }
    }

    return NULL;
}

int main(int argc, const char *argv[])
{
    pthread_t id[10];
    int i = 0;

    for(i=0;i<10;++i){
        pthread_create(&id[i],NULL,test_func,NULL);
    }

    for(i=0;i<10;++i){
        pthread_join(id[i],NULL);
    }
    //10*2000=20000
    printf("%u\n",count);

    return 0;
}

the answer goes right to 20000,so i think when you use sync_add_and_fetch function,you should goes with a while loop is stupid,so I write like this:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>

static unsigned long  count = 0;

int compare_and_swap(int* reg, int oldval, int incre) 
{
    register char result;
#ifdef __i386__
    __asm__ volatile ("lock; cmpxchgl %3, %0; setz %1" : "=m"(*reg), "=q" (result) : "m" (*reg), "r" (oldval + incre), "a" (oldval) : "memory");
    return result;
#elif defined(__x86_64__)
    __asm__ volatile ("lock; cmpxchgq %3, %0; setz %1" : "=m"(*reg), "=q" (result) : "m" (*reg), "r" (newval + incre), "a" (oldval) : "memory");
    return result;
#else
    #error:architecture not supported and gcc too old
#endif

}

void sync_add_and_fetch(int *reg,int oldval,int incre)
{
    int ret = 0;
    while(0 == ret)
    {
       ret = compare_and_swap(reg,oldval,incre);
    }
}

void *test_func(void *arg)
{
    int i=0;
    for(i=0;i<2000;++i)
    {
        sync_add_and_fetch((int *)&count, count, 1);
    }

    return NULL;
}

int main(int argc, const char *argv[])
{
    pthread_t id[10];
    int i = 0;

    for(i=0;i<10;++i){
        pthread_create(&id[i],NULL,test_func,NULL);
    }

    for(i=0;i<10;++i){
        pthread_join(id[i],NULL);
    }
    //10*2000=20000
    printf("%u\n",count);

    return 0;
}

but when i run this code with ./asm after g++ -g -o asm asm.cpp -lpthread.the asm just stuck for more than 5min,see top in another terminal:

3861 root 19 0 102m 888 732 S 400 0.0 2:51.06 asm

I just confused,is this code not the same?

Answer 1

The 64-bit compare_and_swap is wrong as it swaps 64 bits but int is only 32 bits.

compare_and_swap should be used in a loop which retries it until is succeeds.

Answer 2

Your result look right to me. lock cmpxchg succeeds most of the time, but will fail if another core beat you to the punch. You're doing 20k attempts to cmpxchg count+1, not 20k atomic increments.

To write __sync_fetch_and_add with inline asm, you'll want to use lock xadd. It's specifically designed to implement fetch-add.

Implementing other operations, like fetch-or or fetch-and, require a CAS retry loop if you actually need the old value. So you could make a version of the function that doesn't return the old value, and is just a sync-and without the fetch, using lock and with a memory destination. (Compiler builtins can make this optimization based on whether the result is needed or not, but an inline asm implementation doesn't get a chance to choose asm based on that information.)

For efficiency, remember that and, or, add and many other instructions can use immediate operands, so a "re"(src) constraint would be appropriate (not "ri" for int64_t on x86-64, because that would allow immediates too large. https://gcc.gnu.org/onlinedocs/gcc/Machine-Constraints.html). But cmpxchg, xadd, and xchg can't use immediates, of course.

I'd suggest looking at compiler output for modern gcc (e.g. on http://godbolt.org/) for functions using the builtin, to see what compilers do.

---

But beware that inline asm can compile correctly given one set of surrounding code, but not the way you expect given different code. e.g. if the surrounding code copied a value after using CAS on it (probably unlikely), the compiler might decide to give the asm template two different memory operands for "=m"(*reg) and "m"(*reg), but your asm template assumes they will always be the same address.

IDK if gcc4.1 supports it, but "+m"(*reg) would declare a read/write memory operand. Otherwise perhaps you can use a matching constraint to say that the input is in the same location as an earlier operand, like "0"(*reg). But that might only work for registers, not memory, I didn't check.

---

"a" (oldval) is a bug: cmpxchg writes EAX on failure.

It's not ok to tell the compiler you leave a reg unmodified, and then write an asm template that does modify it. You will get unpredictable behaviour from stepping on the compiler's toes.

See c inline assembly getting "operand size mismatch" when using cmpxchg for a safe inline-asm wrapper for lock cmpxchg. It's written for gcc6 flag-output, so you'll have to back-port that and maybe a few other syntax details to crusty old gcc4.1.

That answer also addresses returning the old value so it doesn't have to be separately loaded.

(Using ancient gcc4.1 sounds like a bad idea to me, especially for writing multi-threaded code. So much room for error from porting working code with __sync builtins to hand-rolled asm. The risks of using a newer compiler, like stable gcc5.5 if not gcc7.4, are different but probably smaller.)

If you're going to rewrite code using __sync builtins, the sane thing would be to rewrite it using C11 stdatomic.h, or GNU C's more modern __atomic builtins that are intended to replace __sync.

The Linux kernel does successfully use inline asm for hand-rolled atomics, though, so it's certainly possible.

Answer 3

If you truly are in such a predicament, I would start with the following header file:

#ifndef   SYNC_H
#define   SYNC_H
#if defined(__x86_64__) || defined(__i386__)

static inline int  sync_val_compare_and_swap_int(int *ptr, int oldval, int newval)
{
    __asm__ __volatile__( "lock cmpxchgl %[newval], %[ptr]"
                        : "+a" (oldval), [ptr] "+m" (*ptr)
                        : [newval] "r" (newval)
                        : "memory" );
    return oldval;
}

static inline int  sync_fetch_and_add_int(int *ptr, int val)
{
    __asm__ __volatile__( "lock xaddl %[val], %[ptr]"
                        : [val] "+r" (val), [ptr] "+m" (*ptr)
                        :
                        : "memory" );
    return val;
}


static inline int  sync_add_and_fetch_int(int *ptr, int val)
{
    const int  old = val;
    __asm__ __volatile__( "lock xaddl %[val], %[ptr]"
                        : [val] "+r" (val), [ptr] "+m" (*ptr)
                        :
                        : "memory" );
    return old + val;
}

static inline int  sync_fetch_and_sub_int(int *ptr, int val) { return sync_fetch_and_add_int(ptr, -val); }
static inline int  sync_sub_and_fetch_int(int *ptr, int val) { return sync_add_and_fetch_int(ptr, -val); }

/* Memory barrier */
static inline void  sync_synchronize(void) { __asm__ __volatile__( "mfence" ::: "memory"); }

#else
#error Unsupported architecture.
#endif
#endif /* SYNC_H */

The same extended inline assembly works for both x86 and x86-64. Only the int type is implemented, and you do need to replace possible __sync_synchronize() calls with sync_synchronize(), and each __sync_...() call with sync_..._int().

To test, you can use e.g.

#include <stdlib.h>
#include <pthread.h>
#include <string.h>
#include <errno.h>
#include <stdio.h>
#include "sync.h"

#define  THREADS   16
#define  PERTHREAD 8000

void *test_func1(void *sumptr)
{
    int *const sum = sumptr;
    int        n = PERTHREAD;
    while (n-->0)
        sync_add_and_fetch_int(sum, n + 1);
    return NULL;
}

void *test_func2(void *sumptr)
{
    int *const sum = sumptr;
    int        n = PERTHREAD;
    while (n-->0)
        sync_fetch_and_add_int(sum, n + 1);
    return NULL;
}

void *test_func3(void *sumptr)
{
    int *const sum = sumptr;
    int        n = PERTHREAD;
    int        oldval, curval, newval;
    while (n-->0) {
        curval = *sum;
        do {
            oldval = curval;
            newval = curval + n + 1;
        } while ((curval = sync_val_compare_and_swap_int(sum, oldval, newval)) != oldval);
    }
    return NULL;
}

static void *(*worker[3])(void *) = { test_func1, test_func2, test_func3 };

int main(void)
{
    pthread_t       thread[THREADS];
    pthread_attr_t  attrs;
    int             sum = 0;
    int             t, result;

    pthread_attr_init(&attrs);
    pthread_attr_setstacksize(&attrs, 65536);
    for (t = 0; t < THREADS; t++) {
        result = pthread_create(thread + t, &attrs, worker[t % 3], &sum);
        if (result) {
            fprintf(stderr, "Failed to create thread %d of %d: %s.\n", t+1, THREADS, strerror(errno));
            exit(EXIT_FAILURE);
        }
    }
    pthread_attr_destroy(&attrs);

    for (t = 0; t < THREADS; t++)
        pthread_join(thread[t], NULL);

    t = THREADS * PERTHREAD * (PERTHREAD + 1) / 2;
    if (sum == t)
        printf("sum = %d (as expected)\n", sum);
    else
        printf("sum = %d (expected %d)\n", sum, t);

    return EXIT_SUCCESS;
}

Unfortunately, I don't have an ancient version of GCC to test, so this has only been tested with GCC 5.4.0 and GCC-4.9.3 for x86 and x86-64 (using -O2) on Linux.

If you find any bugs or issues in the above, please let me know in a comment so I can verify and fix as needed.