Atomic operations

[Mark Kettenis <kettenis at wins dot uva dot nl>]

Hi,

Some time ago, in a discussion about my new pthreads implementation,
Ulrich mentioned that I had to make more use of atomic operations to
avoid locks.  He also mentioned that the I'd probably need to make
some improvements to the current cupport for atomic variables in
glibc.  I've come up with a proposal, and I'd like to know what people
think about it.

The idea is conveniently illustrated by giving an example.  Suppose
one wants to define an atomic variable `var' that one wants to
increase, decrease, upon which one also wants to do an atomic
exchange_and_add operation.  In this case one would define the
variable by writing:

  #define VAR_OPERATIONS \
    (__LIBC_ATOMIC_INC | __LIBC_ATOMIC_DEC | __LIBC_ATOMIC_XADD)

   __libc_atomic_operations (var, VAR_OPERATIONS);
   __libc_atomic_define (, int, var);

And use the variable by writing for example:

   __libc_atomic_inc (var);                /* var++;  */

or:

   int oldvar;
   oldvar = __libc_atomic_xadd (var, 4);   /* oldvar = var, var += 4.  */

At the end of this message you'll find how these operations can be
implemented for the i386.  The idea is that the `if'-statements will
all be optimized away.  The only `problem' is the fact that the lock
will always be present, even if it is not used.  I would be interested
in a way to eleminate the lock when possible.  However, I don't think
wasting a few bytes is going tobe a big problem.

Mark


/* Atomic operations.  i386 version.
   Copyright (C) 2000 Free Software Foundation, Inc.
   This file is part of the GNU C Library.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Library General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Library General Public License for more details.

   You should have received a copy of the GNU Library General Public
   License along with the GNU C Library; see the file COPYING.LIB.  If not,
   write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.  */

#ifndef _BITS_LIBC_ATOMIC_H
#define _BITS_LIBC_ATOMIC_H	1

#include <spin-lock.h>

/* According to the Intel documentation the following operations are
   atomic on the Intel Architecture processors:

   - Reading or writing a byte.
   - Reading or writing a word aligned on a 16-bit boundary.
   - Reading or writing a doubleword aligned on a 32-bit boundary.

   The compiler takes care of proper alignment so we don't have to
   worry about unaligned access.

   Bus-locking may be necessary for certain operations to be atomic on
   multiprocessor machines.  According to the Intel documentation this
   is necessary for the following operations:

   - The bit test and modify instructions (BTS, BTR and BTC).
   - The exchange instructions (XADD, CMPXCHG, CMPXCHG8B).
   - The following single-operand arithmetic and logical instructions:
   INC, DEC, NOT, and NEG.
   - The following two-operand arithmetic and logical instructions:
   ADD, ADC, SUB, SBB, AND, OR, and XOR.

   The XCHG instruction is automatically locked.  */

/* Define an atomic variable NAME of type TYPE with storage class
   CLASS.  The operations that must be atomic must be specified with
   __libc_atomic_operations.  Use `extern' for CLASS to declare an
   atomic variable defined in another module.  */
#define __libc_atomic_define(CLASS, TYPE, NAME) \
  CLASS __spin_lock_t NAME##_lock; \
  CLASS volatile TYPE NAME

/* Define that the atomic variable NAME will be operated upon by the
   operations specified in OPERATIONS.  */
#define __libc_atomic_operations(NAME, OPERATIONS) \
  enum { NAME##_operations = OPERATIONS };

/* The operations that can be specified in the last argument to
   __libc_atomic_operations.  These should be OR'd together.  */
#define __LIBC_ATOMIC_INC	0
#define __LIBC_ATOMIC_DEC	0
#define __LIBC_ATOMIC_ADD       0
#define __LIBC_ATOMIC_XADD	1 /* The i386 lacks XADD and CMPXCHG.  */
#define __LIBC_ATOMIC_CMPXCHG	1

/* Increment NAME.  */
#define __libc_atomic_inc(NAME) \
  if (NAME##_operations || sizeof (NAME) != 4)                                \
    {                                                                         \
      __spin_lock (&(NAME##_lock));                                           \
      ++NAME;                                                                 \
      __spin_unlock (&(NAME##_lock));                                         \
    }                                                                         \
  else                                                                        \
    __asm__ __volatile__ ("lock; incl %0" : : "m" (NAME) : "memory")

/* Decrement NAME.  */
#define __libc_atomic_dec(NAME) \
  if (NAME##_operations || sizeof (NAME) != 4)                                \
    {                                                                         \
      __spin_lock (&(NAME##_lock));                                           \
      --NAME;                                                                 \
      __spin_unlock (&(NAME##_lock));                                         \
    }                                                                         \
  else                                                                        \
    __asm__ __volatile__ ("lock; incl %0" : : "m" (NAME) : "memory")

/* Add VAL to NAME.  */
#define __libc_atomic_add(NAME, VAL) \
  if (NAME##_operations || sizeof (NAME) != 4)                                \
    {                                                                         \
      __spin_lock (&(NAME##_lock));                                           \
      NAME += VAL;                                                            \
      __spin_unlock (&(NAME##_lock));                                         \
    }                                                                         \
  else                                                                        \
    __asm__ __volatile__ ("lock; addl %0,%1"                                  \
			  : : "ir" (VAL) "m" (NAME) : "memory")

/* Add VAL to NAME, and return the previous value of NAME.  */
#define __libc_atomic_xadd(NAME, VAL) \
  ({ __typeof (NAME) __result;                                                \
     __spin_lock (&(NAME##_lock));                                            \
     __result = NAME;                                                         \
     NAME += VAL;                                                             \
     __spin_unlock (&(NAME##_lock));                                          \
     result; })

/* Assign NEWVAL to NAME iff the current value of NAME is OLDVAL.
   Return nonzero if the operation succeeded.  */
#define __libc_atomic_cmpxchg(NAME, OLDVAL, NEWVAL) \
  ({ int __result = 0;                                                        \
     __spin_lock (&(NAME##_lock));                                            \
     if (NAME == OLDVAL)                                                      \
       NAME = NEWVAL, __result = 1;                                           \
     __spin_unlock (&(NAME##_lock));                                          \
     __result; })

#endif /* bits/libc-atomic.h */