Re: [PATCH] WorkStruct: Implement generic UP cmpxchg() where an arch doesn't support it

[Russell King <rmk+lkml@arm.linux.org.uk>]

On Fri, Dec 08, 2006 at 11:15:58AM -0800, Linus Torvalds wrote:
> On Fri, 8 Dec 2006, Christoph Lameter wrote:
> > 
> > As also shown in this thread: There are restrictions on what you can do 
> > between ll/sc
> 
> This, btw, is almost certainly true on ARM too.
> 
> There are three major reasons for restrictions on ll/sc:
> 
>  - bus-cycle induced things (eg variations of "you cannot do a store in 
>    between the ll and the sc, because it will touch the cache and clear 
>    the bit", where "the store" might be a load too, and "the cache" might
>    be just "the bus interface")

No such restriction on ARM.

>  - trap handling usually clears the internal lock bit too, which means 
>    that depending on the micro-architecture, even internal microtraps 
>    (like even just branch misprediction, but more commonly things like TLB 
>    misses etc) can cause a sc to always fail.

Also not true.  The architectural implementation is:

	ldrex: tags the _physical_ address + cpu number,
		transitions to exclusive access.

	strex: if in exclusive access state and matches the previous
		tagged physical address + cpu number pair, store
		succeeds.

This is typically implemented in hardware, and in the case of a SMP
system, external to the CPU cores themselves.  So all it's doing is
looking at the exclusive accesses.  It is not embedded into the CPU
core so that micro-architectural stuff affects it.

>  - timing. Livelock in particular.

That is a problem that we're facing, and the solution is rather simple.
You need to introduce a CPU-number specific number of cycles before
retrying the operation on failure.

> All of which means that _nobody_ can really do this reliably in C.

I utterly disagree.  I could code atomic_add() as:

extern void cpu_specific_delay(void);

static inline int atomic_add_return(int i, atomic_t *v)
{
	do {
		asm("ldrex %0, [%1]" : "=r" (val) : "r" (v));
		val += i;
		asm("strex %0, %1, [%2]" : "=r" (res) : "r" (val), "r" (v));
		if (res)
			cpu_specific_delay();
	} while (res);

	return val;
}

and actually we /are/ going to have to go down this path to break the
livelock problem, like it or not.  Ditto for the ARM bitops operations,
so we might as well have ARM at least implement a generic ll/sc thing.

Coding the cpu specific delays into every strex site is going to make
them far too heavy to put inline.

> So right now, I think the "cmpxchg" or the "bitmask set" approach are the 
> alternatives. Russell - LL/SC simply isn't on the table as an interface, 
> whether you like it or not.

Buggerit then.  cmpxchg sucks as an interface, and I am going to
continue to assert that.

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