Atomic operations

Atomic operations

[Mark Kettenis]

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 */

Re: Atomic operations

[Ulrich Drepper]

Mark Kettenis <kettenis@wins.uva.nl> writes:

> 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.

It's an interesting concept.  But I don't think we have to be that
general.  Why should be allow atomic objects of other than the natual
sizes?  The only possible motivation is size but then, with the
spinlock, this is more than nullified (on platforms which don't need
them).

I think defining types atomic_t and uatomic_t (latter is unsigned)
which are guaranteed to have at least 32 bits should be enough.  Do
you know about situations where this is not the case?

The only problem I could see is that you want to have longer types
also on 32bit platforms.  Then I'd suggest

	atomic_least32_t
	uatomic_least32_t
	atomic_least64_t
	uatomic_least64_t

Of course we need then something like your macros since modifying the
64 bit object does not work without it on a 32 bit platform.  Maybe we
can even define atomic_least8_t etc and on platforms like x86 we can
define these with the minimal amount of bits.  So maybe:


#define atomic_object(class, name, size, oper) \
  atomic_object_##oper (class, name, size)

#define atomic_object_INC(class, name, size) \
  class int##size##_t name

#define atomic_object_DEC(class, name, size) \
  class int##size##_t name

#define atomic_object_INC_DEC(class, name, size) \
  class int##size##_t name

#define atomic_object_XADD(class, name, size) \
  class int##size##_t name; \
  __libc_lock_define_initialized (class, __atomic_lock_##name)

#define atomic_object_INC_XADD(class, name, size) \
  class int##size##_t name; \
  __libc_lock_define_initialized (class, __atomic_lock_##name)


The `oper' parameter to atomic_object would then have to be one of

			XADD		CMPX		XADD_CMPX
	INC		INC_XADD	INC_CMPX	INC_XADD_CMPX
	DEC		DEC_XADD	DEC_CMPX	DEC_XADD_CMPX
	INC_DEC		INC_DEC_XADD	INC_DEC_CMPX	INC_DEC_XADD_CMPX


Which shouldn't be too bad.


>     __asm__ __volatile__ ("lock; incl %0" : : "m" (NAME) : "memory")

This does not work.  `lock' only works on

	bt, bts, btr, btc, xchg, add, adc, and


-- 
---------------.      drepper at gnu.org  ,-.   1325 Chesapeake Terrace
Ulrich Drepper  \    ,-------------------'   \  Sunnyvale, CA 94089 USA
Cygnus Solutions `--' drepper at cygnus.com   `------------------------