Re: [PATCH 1/19] MUTEX: Introduce simple mutex implementation

Russell King
2005-12-16T14:31:10Z

On Fri, Dec 16, 2005 at 08:46:44AM -0500, Linh Dang wrote:
>
> Russell King <rmk+lkml@arm.linux.org.uk> wrote:
>
> > On Sat, Dec 17, 2005 at 12:01:27AM +1100, Nick Piggin wrote:
> >> You were proposing a worse default, which is the reason I suggested
> >> it.
> >
> > I'd like to qualify that. "for architectures with native cmpxchg".
> >
> > For general consumption (not specifically related to mutex stuff)...
> >
> > For architectures with llsc, sequences stuch as:
> >
> > load
> > modify
> > cmpxchg
> >
> > are inefficient because they have to be implemented as:
> >
> > load
> > modify
> > load
> > compare
> > store conditional
> >
>
> I dont know what arch u have in mind but for ppc it is:
>
> load-reserve
> modify
> store-conditional
>
> and NOT the sequence you show.

Wrong - because you haven't understood what I'm getting at. If you're
using "cmpxchg" as the low level generic atomic operation (as in the
atomic_cmpxchg() function) then atomic_cmpxchg _has_ to be implemented
on llsc as:

load (reserve if you need this detail)
compare
store conditional

So, let's illustrate this. Let's say you want to atomically multiply
a value by N.

do {
old = atomic_read(&foo);
new = old * N;
} while(atomic_cmpxchg(&foo, old, new) != old);

For an architecture supporting cmpxchg, this becomes:

loop: load foo => old
new = old * N
cmpxchg ret, old, new, foo
compare ret & old
if not equal goto loop

And for architectures with llsc, this becomes:

loop: load foo => old
new = old * N
loop2: load locked foo => ret
compare ret & old
if equal store conditional new in foo
if store failed because we lost the lock, goto loop2
compare ret & old
if not equal goto loop

Do you now see what I mean? (yup, ARM is a llsc architecture.)

--
Russell King
Linux kernel 2.6 ARM Linux - http://www.arm.linux.org.uk/
maintainer of: 2.6 Serial core