Atomic Operations

“Where did atomic.h go?!?”

..was my surprised reaction when I compiled one of my applications in Debian Etch for the first time. It compiled with no problems on Sarge and on Gentoo, but couldn’t find the atomic.h header file on Etch. A bit confused, I asked my friend, and he didn’t seem to know at the first queries, so after I figured it out, I wrote this post.

First, to understand why was atomic.h removed, you should know the following: * The /usr/include/asm/atomic.h , as it is found on Debian Sarge is a kernel header, somehow cleaned up to compile well in user-space, but still a kernel header. * Including kernel headers in user-space is generally bad idea, unless you are using the kernel API (e.g. for an ioctl). * The atomic.h header, in particular, was not meant to be included in user-space. For example, if on a SMP machine you don’t compile with CONFIG_SMP, the operations will loose their atomicity. Even worse, on some architecture the atomic.h is completely broken in user-space because it’s working by disabling interrupts. Here is a LKML thread on the subject. * It’s Linux specific, other Unix-es might not have an equivalent.

Despite these things, many applications (e.g. mysql) used the atomic.h because of the lack of alternatives. There is no equivalent in glibc. Some framework libraries, like GLib or apr have their own implementation for atomic operations but linking against them just for that doesn’t always make sense. Simulating them with pthread spin locks is not much of an option either, as much of the performance is wasted. Finally, maintaining assembly versions in each application is out of the question.

The good news is that now there is a good and portable solution: gcc atomic builtins. Since they are provided by the compiler, who is our specialist in generating machine code, they are sure to be correct on all supported architectures and operating systems. In fact, it makes so much sense to me to have the atomic operations as a language extension that I’m surprised we had to wait until version 4.1 of gcc to see them implemented. The downsides are that (1) some old processor will not use them efficiently and (2) the API is a little cumbersome.

To get you going, here is an in-place replacement for the atomic.h header:

#ifndef _ATOMIC_H
#define _ATOMIC_H

/**
 * Atomic type.
 */

typedef struct {
    volatile int counter;
} atomic_t;

#define ATOMIC_INIT(i)  { (i) }

/**
 * Read atomic variable
 * @param v pointer of type atomic_t
 *
 * Atomically reads the value of @v.
 */
#define atomic_read(v) ((v)->counter)

/**
 * Set atomic variable
 * @param v pointer of type atomic_t
 * @param i required value
 */
#define atomic_set(v,i) (((v)->counter) = (i))

/**
 * Add to the atomic variable
 * @param i integer value to add
 * @param v pointer of type atomic_t
 */
static inline void atomic_add( int i, atomic_t *v )
{
         (void)__sync_add_and_fetch(&v->counter, i);
}

/**
 * Subtract the atomic variable
 * @param i integer value to subtract
 * @param v pointer of type atomic_t
 *
 * Atomically subtracts @i from @v.
 */
static inline void atomic_sub( int i, atomic_t *v )
{
        (void)__sync_sub_and_fetch(&v->counter, i);
}

/**
 * Subtract value from variable and test result
 * @param i integer value to subtract
 * @param v pointer of type atomic_t
 *
 * Atomically subtracts @i from @v and returns
 * true if the result is zero, or false for all
 * other cases.
 */
static inline int atomic_sub_and_test( int i, atomic_t *v )
{
        return !(__sync_sub_and_fetch(&v->counter, i));
}

/**
 * Increment atomic variable
 * @param v pointer of type atomic_t
 *
 * Atomically increments @v by 1.
 */
static inline void atomic_inc( atomic_t *v )
{
       (void)__sync_fetch_and_add(&v->counter, 1);
}

/**
 * @brief decrement atomic variable
 * @param v: pointer of type atomic_t
 *
 * Atomically decrements @v by 1.  Note that the guaranteed
 * useful range of an atomic_t is only 24 bits.
 */
static inline void atomic_dec( atomic_t *v )
{
       (void)__sync_fetch_and_sub(&v->counter, 1);
}

/**
 * @brief Decrement and test
 * @param v pointer of type atomic_t
 *
 * Atomically decrements @v by 1 and
 * returns true if the result is 0, or false for all other
 * cases.
 */
static inline int atomic_dec_and_test( atomic_t *v )
{
       return !(__sync_sub_and_fetch(&v->counter, 1));
}

/**
 * @brief Increment and test
 * @param v pointer of type atomic_t
 *
 * Atomically increments @v by 1
 * and returns true if the result is zero, or false for all
 * other cases.
 */
static inline int atomic_inc_and_test( atomic_t *v )
{
      return !(__sync_add_and_fetch(&v->counter, 1));
}

/**
 * @brief add and test if negative
 * @param v pointer of type atomic_t
 * @param i integer value to add
 *
 * Atomically adds @i to @v and returns true
 * if the result is negative, or false when
 * result is greater than or equal to zero.
 */
static inline int atomic_add_negative( int i, atomic_t *v )
{
       return (__sync_add_and_fetch(&v->counter, i) < 0);
}

#endif

Pretty straight forward isn't it? It could be even more powerful and simpler if you don't need precise compatibility with atomic.h. For example, atomic_add could easily return the result values:

static inline int atomic_add( int i, atomic_t *v )
{
         return __sync_add_and_fetch(&v->counter, i);
}

As a second example, consider a compare and swap operation, frequently used in lock-free algorithms. Once again, it's trivially:

/**
 * @brief compare and swap
 * @param v pointer of type atomic_t
 *
 * If the current value of @b v is @b oldval,
 * then write @b newval into @b v. Returns #TRUE if
 * the comparison is successful and @b newval was
 * written.
 */
static inline int atomic_cas( atomic_t *v, int oldval, int newval )
{
        return __sync_bool_compare_and_swap(&v->counter, oldval, newval);
}

Found this useful? Leave a comment.

14 thoughts on “Atomic Operations

  1. Wian Potgieter

    Great! mysql-gui-tools compiles :D
    I’m going to save atomic.h in ~ so that I can restore it next time I lose it.

    Thanks a million!

    Reply
  2. Valeriu PaloĊŸ

    This is excellent information! Thank you!

    I was trying to implement a lock-free queue and desperately needed a stable implementation of an atomic CAS. I had no idea about the GCC built-ins, so you opened my eyes.

    Great job!

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>