Re: Atomic operations on the ARM

[Richard Earnshaw <rearnsha at arm dot com>]

> On Thu, Oct 03, 2002 at 11:31:15AM -0500, Benjamin Kosnik wrote:
> > 
> > > Sure, but if they don't work then there's not much point in them being 
> > > 'light-weight'!
> > 
> > If they don't work, they shouldn't exist, and the generic routines
> > (which do nothing, and are not atomic) should be used, period.
> > 
> > Perhaps the arm configuration should just use the generics, hmm?
> 
> This doesn't make sense.  We have generic threading locks; yes, it's
> heavyweight; but it works.  Isn't correctness important?

I would have thought that correctness came before efficiency...

> 
> Richard, does the problem with using swp in this context also affect
> ARM/Linux?  Glibc appears to use the just about the same code for
> atomic operations.

I haven't seen the glibc code, but if it was trying to do an atomic add 
using the SWP based sequence that was in atomicity.h, then yes, it's 
broken.

The problem was a race condition if the store back failed to find the 
original value stored in memory after the update:

1 0:
2	ldr     %0, [%3]
3	add     %1, %0, %4
4	swp     %2, %1, [%3]  <-- if this fails
5	cmp     %0, %2        <-- in this test
6	swpne   %1, %2, [%3]  <-- try to restore other change
7	bne     0b

that is, the instruction at line 6 tries to put back the value that was in 
memory at line 4 (before we tried to store our own update).  But what if 
another thread also tries to update at that point? the value it inserts in 
between the two swap operations will be lost.  The attachment in PR 3584 
illustrates the problem excellently.

I think there are three cases to consider, cooperative threading on a 
machine, non-cooperative threading and multi-processor.

For cooperative threading there's no problem, since the sequence will 
never voluntarily yeild.

For non-cooperative threading the problem can be solved with a mutex and a 
thread_yeild() function, more below.

For multi-cpu, the cheapest solution would be a spin-lock sequence:

int spinlock = 0;

void __atomic_add(Atomic_int *mem, int *val)
{
  while (swp(spinlock, -1) == -1)
    ;

  *mem += val;

  spinlock = 0;
}

For the non-cooperative threading version, the only change needed is to 
add a thread_yeild call in the while loop (OK, we might be able to manage 
without, since threads are always forcibly descheduled eventually, unless 
we have some sort of priority scheme).

We could get clever and use a single bit in _Atomic_word to be a mutex 
bit, and effectively make it a bit-field, effectively

typedef struct
{
  int mutex:1;
  signed int val:31
} _Atomic_word;

But that would involve fixing the source code that directly accesses this 
type and changing it to use set and read macros.

But really the above is just the same as using a mutex, since almost 
certainly a good threading implementation on the ARM would be already 
using swp to handle the mutex...

So I've no idea why the generic atomicity.h doesn't define 
__exchange_and_add as

#include <gthr.h>

typedef int _Atomic_word;

__gthread_mutex_t _Atomic_add_mutex __attribute__ ((weak));

static inline _Atomic_word
__attribute__ ((__unused__))
__exchange_and_add (volatile _Atomic_word* mem, int val)
{
   _Atomic_word result;

   __gthread_mutex_lock (&_Atomic_add_mutex);

   result = *mem;
   *mem = result + val;

  __gthread_mutex_unlock (&_Atomic_add_mutex);
  return result;
}



R.