MUTEX: Introduce simple mutex implementation
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.
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
-01,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
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.