locking/qspinlock: Ensure node is initialised before updating prev->next

Web:        https://git.kernel.org/torvalds/c/95bcade33a8af38755c9b0636e36a36ad3789fe6
Commit:     95bcade33a8af38755c9b0636e36a36ad3789fe6
Parent:     79e902382637a2f421b7f295dcf9934d80d84d7d
Refname:    refs/heads/master
Author:     Will Deacon <[email protected]>
AuthorDate: Tue Feb 13 13:22:56 2018 +0000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Tue Feb 13 14:50:14 2018 +0100

    locking/qspinlock: Ensure node is initialised before updating prev->next
    
    When a locker ends up queuing on the qspinlock locking slowpath, we
    initialise the relevant mcs node and publish it indirectly by updating
    the tail portion of the lock word using xchg_tail. If we find that there
    was a pre-existing locker in the queue, we subsequently update their
    ->next field to point at our node so that we are notified when it's our
    turn to take the lock.
    
    This can be roughly illustrated as follows:
    
      /* Initialise the fields in node and encode a pointer to node in tail */
      tail = initialise_node(node);
    
      /*
       * Exchange tail into the lockword using an atomic read-modify-write
       * operation with release semantics
       */
      old = xchg_tail(lock, tail);
    
      /* If there was a pre-existing waiter ... */
      if (old & _Q_TAIL_MASK) {
            prev = decode_tail(old);
            smp_read_barrier_depends();
    
            /* ... then update their ->next field to point to node.
            WRITE_ONCE(prev->next, node);
      }
    
    The conditional update of prev->next therefore relies on the address
    dependency from the result of xchg_tail ensuring order against the
    prior initialisation of node. However, since the release semantics of
    the xchg_tail operation apply only to the write portion of the RmW,
    then this ordering is not guaranteed and it is possible for the CPU
    to return old before the writes to node have been published, consequently
    allowing us to point prev->next to an uninitialised node.
    
    This patch fixes the problem by making the update of prev->next a RELEASE
    operation, which also removes the reliance on dependency ordering.
    
    Signed-off-by: Will Deacon <[email protected]>
    Acked-by: Peter Zijlstra (Intel) <[email protected]>
    Cc: Linus Torvalds <[email protected]>
    Cc: Thomas Gleixner <[email protected]>
    Link: http://lkml.kernel.org/r/[email protected]
    Signed-off-by: Ingo Molnar <[email protected]>
---
 kernel/locking/qspinlock.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
index 38ece035039e..348c8cec1042 100644
--- a/kernel/locking/qspinlock.c
+++ b/kernel/locking/qspinlock.c
@@ -408,14 +408,15 @@ queue:
 	 */
 	if (old & _Q_TAIL_MASK) {
 		prev = decode_tail(old);
+
 		/*
-		 * The above xchg_tail() is also a load of @lock which
-		 * generates, through decode_tail(), a pointer.  The address
-		 * dependency matches the RELEASE of xchg_tail() such that
-		 * the subsequent access to @prev happens after.
+		 * We must ensure that the stores to @node are observed before
+		 * the write to prev->next. The address dependency from
+		 * xchg_tail is not sufficient to ensure this because the read
+		 * component of xchg_tail is unordered with respect to the
+		 * initialisation of @node.
 		 */