• Will Deacon's avatar
    locking/qspinlock: Remove unbounded cmpxchg() loop from locking slowpath · 59fb586b
    Will Deacon authored
    
    
    The qspinlock locking slowpath utilises a "pending" bit as a simple form
    of an embedded test-and-set lock that can avoid the overhead of explicit
    queuing in cases where the lock is held but uncontended. This bit is
    managed using a cmpxchg() loop which tries to transition the uncontended
    lock word from (0,0,0) -> (0,0,1) or (0,0,1) -> (0,1,1).
    
    Unfortunately, the cmpxchg() loop is unbounded and lockers can be starved
    indefinitely if the lock word is seen to oscillate between unlocked
    (0,0,0) and locked (0,0,1). This could happen if concurrent lockers are
    able to take the lock in the cmpxchg() loop without queuing and pass it
    around amongst themselves.
    
    This patch fixes the problem by unconditionally setting _Q_PENDING_VAL
    using atomic_fetch_or, and then inspecting the old value to see whether
    we need to spin on the current lock owner, or whether we now effectively
    hold the lock. The tricky scenario is when concurrent lockers end up
    queuing on the lock and the lock becomes available, causing us to see
    a lockword of (n,0,0). With pending now set, simply queuing could lead
    to deadlock as the head of the queue may not have observed the pending
    flag being cleared. Conversely, if the head of the queue did observe
    pending being cleared, then it could transition the lock from (n,0,0) ->
    (0,0,1) meaning that any attempt to "undo" our setting of the pending
    bit could race with a concurrent locker trying to set it.
    
    We handle this race by preserving the pending bit when taking the lock
    after reaching the head of the queue and leaving the tail entry intact
    if we saw pending set, because we know that the tail is going to be
    updated shortly.
    Signed-off-by: default avatarWill Deacon <will.deacon@arm.com>
    Acked-by: default avatarPeter Zijlstra (Intel) <peterz@infradead.org>
    Acked-by: default avatarWaiman Long <longman@redhat.com>
    Cc: Linus Torvalds <torvalds@linux-foundation.org>
    Cc: Thomas Gleixner <tglx@linutronix.de>
    Cc: boqun.feng@gmail.com
    Cc: linux-arm-kernel@lists.infradead.org
    Cc: paulmck@linux.vnet.ibm.com
    Link: http://lkml.kernel.org/r/1524738868-31318-6-git-send-email-will.deacon@arm.com
    
    Signed-off-by: default avatarIngo Molnar <mingo@kernel.org>
    59fb586b
qspinlock.c 14.7 KB