releases/4.4.157/locking-osq_lock-fix-osq_lock-queue-corruption.patch

   1 From 50972fe78f24f1cd0b9d7bbf1f87d2be9e4f412e Mon Sep 17 00:00:00 2001
   2 From: Prateek Sood <prsood@codeaurora.org>
   3 Date: Fri, 14 Jul 2017 19:17:56 +0530
   4 Subject: locking/osq_lock: Fix osq_lock queue corruption
   5
   6 From: Prateek Sood <prsood@codeaurora.org>
   7
   8 commit 50972fe78f24f1cd0b9d7bbf1f87d2be9e4f412e upstream.
   9
  10 Fix ordering of link creation between node->prev and prev->next in
  11 osq_lock(). A case in which the status of optimistic spin queue is
  12 CPU6->CPU2 in which CPU6 has acquired the lock.
  13
  14         tail
  15           v
  16   ,-. <- ,-.
  17   |6|    |2|
  18   `-' -> `-'
  19
  20 At this point if CPU0 comes in to acquire osq_lock, it will update the
  21 tail count.
  22
  23   CPU2                  CPU0
  24   ----------------------------------
  25
  26                                        tail
  27                                          v
  28                           ,-. <- ,-.    ,-.
  29                           |6|    |2|    |0|
  30                           `-' -> `-'    `-'
  31
  32 After tail count update if CPU2 starts to unqueue itself from
  33 optimistic spin queue, it will find an updated tail count with CPU0 and
  34 update CPU2 node->next to NULL in osq_wait_next().
  35
  36   unqueue-A
  37
  38                tail
  39                  v
  40   ,-. <- ,-.    ,-.
  41   |6|    |2|    |0|
  42   `-'    `-'    `-'
  43
  44   unqueue-B
  45
  46   ->tail != curr && !node->next
  47
  48 If reordering of following stores happen then prev->next where prev
  49 being CPU2 would be updated to point to CPU0 node:
  50
  51                                        tail
  52                                          v
  53                           ,-. <- ,-.    ,-.
  54                           |6|    |2|    |0|
  55                           `-'    `-' -> `-'
  56
  57   osq_wait_next()
  58     node->next <- 0
  59     xchg(node->next, NULL)
  60
  61                tail
  62                  v
  63   ,-. <- ,-.    ,-.
  64   |6|    |2|    |0|
  65   `-'    `-'    `-'
  66
  67   unqueue-C
  68
  69 At this point if next instruction
  70         WRITE_ONCE(next->prev, prev);
  71 in CPU2 path is committed before the update of CPU0 node->prev = prev then
  72 CPU0 node->prev will point to CPU6 node.
  73
  74                tail
  75     v----------. v
  76   ,-. <- ,-.    ,-.
  77   |6|    |2|    |0|
  78   `-'    `-'    `-'
  79      `----------^
  80
  81 At this point if CPU0 path's node->prev = prev is committed resulting
  82 in change of CPU0 prev back to CPU2 node. CPU2 node->next is NULL
  83 currently,
  84
  85                                        tail
  86                                          v
  87                           ,-. <- ,-. <- ,-.
  88                           |6|    |2|    |0|
  89                           `-'    `-'    `-'
  90                              `----------^
  91
  92 so if CPU0 gets into unqueue path of osq_lock it will keep spinning
  93 in infinite loop as condition prev->next == node will never be true.
  94
  95 Signed-off-by: Prateek Sood <prsood@codeaurora.org>
  96 [ Added pictures, rewrote comments. ]
  97 Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
  98 Cc: Linus Torvalds <torvalds@linux-foundation.org>
  99 Cc: Peter Zijlstra <peterz@infradead.org>
 100 Cc: Thomas Gleixner <tglx@linutronix.de>
 101 Cc: sramana@codeaurora.org
 102 Link: http://lkml.kernel.org/r/1500040076-27626-1-git-send-email-prsood@codeaurora.org
 103 Signed-off-by: Ingo Molnar <mingo@kernel.org>
 104 Signed-off-by: Amit Pundir <amit.pundir@linaro.org>
 105 Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
 106
 107 ---
 108  kernel/locking/osq_lock.c |   13 +++++++++++++
 109  1 file changed, 13 insertions(+)
 110
 111 --- a/kernel/locking/osq_lock.c
 112 +++ b/kernel/locking/osq_lock.c
 113 @@ -104,6 +104,19 @@ bool osq_lock(struct optimistic_spin_que
 114
 115         prev = decode_cpu(old);
 116         node->prev = prev;
 117 +
 118 +       /*
 119 +        * osq_lock()                   unqueue
 120 +        *
 121 +        * node->prev = prev            osq_wait_next()
 122 +        * WMB                          MB
 123 +        * prev->next = node            next->prev = prev // unqueue-C
 124 +        *
 125 +        * Here 'node->prev' and 'next->prev' are the same variable and we need
 126 +        * to ensure these stores happen in-order to avoid corrupting the list.
 127 +        */
 128 +       smp_wmb();
 129 +
 130         WRITE_ONCE(prev->next, node);
 131
 132         /*