Re: how atomic is the atomic set instruction?

[Bill Gatliff <bgat@xxxxxxxxxxxxxxx>]

Ali Günhan Akyürek wrote:
>  
> I thought:
>  
> v->counter = i;
> is compiled as something like that:
>  
> load r1, [i]
> // hımm!!, what if switching occurs here and another thread changes the
> value "i". It is a wrong behaviour.
> store r,1[counter]

No, it isn't wrong behavior.  It's just undesired behavior--- to you.

Assuming ARM for a second, at the end of that statement the value
placed in 'counter' is either the old value of 'i', or the new value.
 That's because (a) the LDR instruction that reads the value of 'i'
itself can't be interrupted, and (b) ditto for the STR instruction
used to update 'counter'.

However, you cannot predict which value for 'i' will end up in
'counter' during a simultaneous update to 'i', because this code is a
read-modify-write operation (where the modify step is just "move the
value over"); on ARM, read-modify-writes are not uninterruptible in
the general case.

So, if your design demands that the value placed in 'counter' always
be the latest value of 'i', then you have to put the above statement
into a critical section or you risk a "race condition"--- and that's
true whether you use the above code as written, or wrap the accesses
to 'counter' and 'i' with atomic_*().  Because the "problem" you are
referring to doesn't lie with atomic accesses to the operands, but
with the fact that the statement as a whole is a read-modify-write.

In the general case, however, your example is pretty dangerous in
another way too.  If tomorrow that statement is running on a machine
that doesn't have atomic accessors like LDR/STR for integers, then you
might not get merely the old or new value of 'i' into 'counter': you
might get a munged-up value entirely.  That's because the sequence of
instructions to update 'i' might get interrupted part-way through, and
so you end up with half of the old value in 'counter', plus half of
the new value.  Ouch.

On non-atomic-int machines, atomic_*()'s fix the part of the problem
that lies with reading/writing the operands.  But they don't address
the meta-problem, which is the fact that the statement as a whole is
still a read-modify-write.

Incidentally, if you wrap the whole statement into a critical section
(spin_lock_irqsave, etc.), then you mask the fact that you really need
atomic_*()'s as well.  The most bulletproof and portable code would
use atomic_*()'s where necessary too.  The compiler will turn
atomic_*()'s into no-ops for the appropriate architectures.


> What do you advice me for CompAndSwap? I think something like this is
> not possible without disabling interrupts and reenabling interrupts as
> in atomic_cmpxchg.

I haven't looked in detail at your design requirements, so I can't
offer a detailed solution.  But in general, you want to minimize the
data that's shared between contexts, and then access the shared data
very carefully.  Use a state transition diagram, for example, to help
you understand all the possible sequences of events for the shared
data accesses.

Also, there might be a CS (computer science)-inspired approach to the
implementation you are after.  Try Google, but subject the search
results to the same careful scrutiny you would give code that you
wrote yourself.

A spinlock might be helpful, but the cmpxchg might be useful for
setting flags in a way that can avoid hits to your interrupt latency.
 Kind of how some of the new ARMv7 instructions work vs. the old SWP
for semaphores.  It's probably best if you understand how that's done
before you dive into your Stack implementation.

In general, the troublesome parts are usually in the data structure
that manages the data itself, and not the data.  I.e. the
implementation of your stack, and not the data that's actually on the
stack.


b.g.
-- 
Bill Gatliff
bgat@xxxxxxxxxxxxxxx

-------------------------------------------------------------------
List admin: http://lists.arm.linux.org.uk/mailman/listinfo/linux-arm
FAQ:        http://www.arm.linux.org.uk/mailinglists/faq.php
Etiquette:  http://www.arm.linux.org.uk/mailinglists/etiquette.php