Skip to contentSkip to conversation

MUTEX: Introduce simple mutex implementation

PATCH [email protected] 2 participants 3 messages Dec 16, 2005

lore
Share & tools
lore
#0 lore raw
Quoted 6 lines

Now my point about using LL/SC is that:

	1,C,A	cmpxchg(0,1) [failed]
	1,C,A	cmpxchg(1,3) [success]
	3,C,A	...
Quoted 6 lines

Can be turned into:

	1,C,A	x = LL()
	1,C,A	x |= 2;
	1,C,A	SC(3) [success]
	3,C,A	...

... which can be turned back into

1,C,A x = load()
1,C,A x' = x | 2;
1,C,A cmpxchg(x,x') [success]
3,C,A ...

which will fail and retry in exactly the same contention cases as the LL/SC. The only thing that LL gives you that's nice is a hint that an SC is due very soon and so resisting a cache eviction for a couple of cycles might be a good idea.

The reason that we tend to do the former is optimism that the lock won't be held. If that's a bad assumption, make it more pessimistic.

LL/SC can detect double changes during the critical section, but it's very similar in expressive power to load + CMPXCHG.

#1 lore raw

Review

Quoted 13 lines · [email protected] wrote:
Quoted 6 lines

Can be turned into:

	1,C,A	x = LL()
	1,C,A	x |= 2;
	1,C,A	SC(3) [success]
	3,C,A	...

... which can be turned back into

(quoted diff) +0 -0
 	1,C,A	x = load()
 	1,C,A	x' = x | 2;
 	1,C,A	cmpxchg(x,x') [success]
 	3,C,A	...

Which would be totally pointless.

If you have LL/SC, then the odds are you _don't_ have CMPXCHG, and that CMPXCHG is implemented using LL/SC, so what you end up with is:

1,C,A x = load()

 	1,C,A	x' = x | 2;
	1,C,A	y = LL()
	1,C,A	if (y == x)
	1,X,A		SC(x');

3,C,A ...

David

#2 lore raw
Quoted 4 lines

Which would be totally pointless.

If you have LL/SC, then the odds are you _don't_ have CMPXCHG, and that CMPXCHG is implemented using LL/SC, so what you end up with is:

Ah, you're not quite understanding what I wrote, but I see the confusion.

I took "turned into" to mean "ported to an architecture with the other primitive", and intended it that when I said "turned back". That's obviously pointless if you're emulating one with the other.

The point I was making is that, for any LL/SC sequence, there is an exactly analagous LD/CMPXCHG version, so you never have to have more CMPXCHGs than SCs.

This was an attempt to disprove your claim that LL/SC was better by more than a very small factor.

It it possible to optimize for the contention-free case and do away with the initial load, at the expense of an additional CMPXCHG in the failure case.