On Tue, Jul 27, 2021 at 09:52:26AM +0800, Wang Rui wrote: > I think the forward progress are guaranteed while all operations are > atomic(ll/sc or amo). If ll/sc runs on a fast cpu, there will be > random delays, is that okay? Else, for such hardware, we can't even > implement generic spinlock with ll/sc. > > And I also think that the hardware supports normal store for > unlocking. (e.g. arch_spin_unlock) > > In qspinlock, when _Q_PENDING_BITS == 1, it's available for all > hardware, because the clear_pending/clear_pending_set_locked are all > atomic operations. Isn't it? > > Q: Why live lock happens while _Q_PENDING_BITS == 8? > A: I found a case is: > > * CPU A updates sub-word of qpsinlock at high frequency with normal store. > * CPU B do xchg_tail with load + cmpxchg, and the value of load is always not equal to the value of ll(cmpxchg). > > qspinlock: > 0: locked > 1: pending > 2: tail > > CPU A CPU B > 1: 1: <--------------------+ > sh $newval, &locked lw $v1, &qspinlock | > add $newval, 1 and $t1, $v1, ~mask | > b 1b or $t1, $t1, newval | (live lock path) > ll $v2, &qspinlock | > bne $v1, $v2, 1b -----+ > sc $t1, &qspinlock > beq $t1, 0, 1b > > If xchg_tail like this, at least there is no live lock on Loongson > > xchg_tail: > > 1: > ll $v1, &qspinlock > and $t1, $v1, ~mask > or $t1, $t1, newval > sc $t1, &qspinlock > beq $t1, 0, 1b > > For hardware that ll/sc is based on cache coherency, I think sc is > easy to succeed. The ll makes cache-line is exclusive by CPU B, and > the store of CPU A needs to acquire exclusive again, the sc may be > completed before this. This! I've been saying this for ages. All those xchg16() implementations are broken for using cmpxchg() on LL/SC. Not because xchg16() is fundamentally flawed. Perhaps we should introduce: atomic_nand_or() and atomic_fetch_nand_or() and implement short xchg() using those, then we can have the whole masks setup shared. It just means you get to implement those primitives for *all* archs :-) Also, the _Q_PENDING_BITS==1 case can use that primitive.
