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

[Russell King]

On Fri, Dec 16, 2005 at 08:46:44AM -0500, Linh Dang wrote:
> 
> Russell King <rmk+lkml@xxxxxxxxxxxxxxxx> 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
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/