osq_lock: fix osq_lock queue corruption
PATCH 1/1 osq_lock: fix osq_lock queue corruption
Fix ordering of link creation between node->prev and prev->next in osq_lock(). A case in which the status of optimistic spin queue is CPU6->CPU2 in which CPU6 has acquired the lock.
tail
v
,-. <- ,-.
|6| |2|
-' -> -'
At this point if CPU0 comes in to acquire osq_lock, it will update the tail count.
CPU2 CPU0
----------------------------------
tail v ,-. <- ,-. ,-. |6| |2| |0| `-' -> `-' `-'
After tail count update if CPU2 starts to unqueue itself from optimistic spin queue, it will find updated tail count with CPU0 and update CPU2 node->next to NULL in osq_wait_next().
unqueue-A
tail
v
,-. <- ,-. ,-. |6| |2| |0| `-' `-' `-'
unqueue-B
->tail != curr && !node->next
If reordering of following stores happen thenprev->next where prev being CPU2 would be updated to point to CPU0 node:
tail v ,-. <- ,-. ,-. |6| |2| |0| `-' -> `-' -> `-'
osq_wait_next()
node->next <- 0
xchg(node->next, NULL)
tail
v
,-. <- ,-. ,-.
|6| |2| |0|
`-' `-' `-'unqueue-C
At this point if next instructionWRITE_ONCE(next->prev, prev);
in CPU2 path is committed before the update of CPU0 node->prev = prev then CPU0 node->prev will point to CPU6 node.
tail
V----------. v
,-. <- ,-. ,-.
|6| |2| |0|
`-' `-' `-'
`----------^At this point if CPU0 path's node->prev = prev is committed resulting in change of CPU0 prev back to CPU2 node. CPU2 node->next is NULL currently,
tail v ,-. <- ,-. <- ,-. |6| |2| |0| `-' `-' `-' `----------^
so if CPU0 gets into unqueue path of osq_lock it will keep spinning in infinite loop as condition prev->next == node will never be true.
--- kernel/locking/osq_lock.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)
kernel/locking/osq_lock.c +13 -0
@@ -109,6 +109,19 @@ bool osq_lock(struct optimistic_spin_queue *lock) prev =decode_cpu (old); node->prev = prev; + +/* +* osq_lock() unqueue +* +* node->prev = prev osq_wait_next() +* WMB MB +* prev->next = node next->prev = prev //unqueue-C +* +* Here 'node->prev' and 'next->prev' are the same variable and we need +* to ensure these stores happen in-order to avoid corrupting the list. +*/ +smp_wmb (); +WRITE_ONCE (prev->next, node);/*
Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc., is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.
Quoted 105 lines · Prateek Sood
Fix ordering of link creation between
node->prevandprev->nextinosq_lock(). A case in which the status of optimistic spin queue isCPU6->CPU2in which CPU6 has acquired the lock.tail
v
,-. <- ,-.
|6| |2|
-' ->-'At this point if CPU0 comes in to acquire
osq_lock, it will update the tail count.CPU2 CPU0
----------------------------------tail v ,-. <- ,-. ,-. |6| |2| |0| `-' -> `-' `-'After tail count update if CPU2 starts to unqueue itself from optimistic spin queue, it will find updated tail count with CPU0 and update CPU2
node->nextto NULL inosq_wait_next().unqueue-A
tail
v,-. <- ,-. ,-. |6| |2| |0| `-' `-' `-'unqueue-B
->tail != curr && !node->nextIf reordering of following stores happen then
prev->nextwhere prev being CPU2 would be updated to point to CPU0 node:tail v ,-. <- ,-. ,-. |6| |2| |0| `-' -> `-' -> `-'
osq_wait_next()node->next <- 0 xchg(node->next, NULL) tail v ,-. <- ,-. ,-. |6| |2| |0| `-' `-' `-'unqueue-C
At this point if next instruction
WRITE_ONCE(next->prev, prev);
in CPU2 path is committed before the update of CPU0node->prev= prev then CPU0node->prevwill point to CPU6 node.tail V----------. v ,-. <- ,-. ,-. |6| |2| |0| `-' `-' `-' `----------^At this point if CPU0 path's
node->prev= prev is committed resulting in change of CPU0 prev back to CPU2 node. CPU2node->nextis NULL currently,tail v ,-. <- ,-. <- ,-. |6| |2| |0| `-' `-' `-' `----------^so if CPU0 gets into unqueue path of
osq_lockit will keep spinning in infinite loop as conditionprev->next== node will never be true.Signed-off-by Prateek Sood <[email protected]>--- kernel/locking/osq_lock.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)kernel/locking/osq_lock.c +6
-0@@ -109,6 +109,19 @@ bool osq_lock(struct optimistic_spin_queue *lock) prev =decode_cpu (old); node->prev = prev; + +/* +* osq_lock() unqueue +* +* node->prev = prev osq_wait_next() +* WMB MB
kernel/locking/osq_lock.c bool osq_lock(struct optimistic_spin_queue *lock) · line 127
Quoted 10 lines
kernel/locking/osq_lock.c +7
-0+* prev->next = node next->prev = prev //unqueue-C +* +* Here 'node->prev' and 'next->prev' are the same variable and we need +* to ensure these stores happen in-order to avoid corrupting the list. +*/ +smp_wmb (); +WRITE_ONCE (prev->next, node);/*
Hi Peter,
I have updated the change log and comments in code.
Signature · 3 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc., is a member of Code Aurora Forum, a Linux Foundation Collaborative Project
Quoted 99 lines · Prateek Sood
Fix ordering of link creation between
node->prevandprev->nextinosq_lock(). A case in which the status of optimistic spin queue isCPU6->CPU2in which CPU6 has acquired the lock.tail
v
,-. <- ,-.
|6| |2|
-' ->-'At this point if CPU0 comes in to acquire
osq_lock, it will update the tail count.CPU2 CPU0
----------------------------------tail v ,-. <- ,-. ,-. |6| |2| |0| `-' -> `-' `-'After tail count update if CPU2 starts to unqueue itself from optimistic spin queue, it will find updated tail count with CPU0 and update CPU2
node->nextto NULL inosq_wait_next().unqueue-A
tail
v,-. <- ,-. ,-. |6| |2| |0| `-' `-' `-'unqueue-B
->tail != curr && !node->nextIf reordering of following stores happen then
prev->nextwhere prev being CPU2 would be updated to point to CPU0 node:tail v ,-. <- ,-. ,-. |6| |2| |0| `-' -> `-' -> `-'
osq_wait_next()node->next <- 0 xchg(node->next, NULL) tail v ,-. <- ,-. ,-. |6| |2| |0| `-' `-' `-'unqueue-C
At this point if next instruction
WRITE_ONCE(next->prev, prev);
in CPU2 path is committed before the update of CPU0node->prev= prev then CPU0node->prevwill point to CPU6 node.tail V----------. v ,-. <- ,-. ,-. |6| |2| |0| `-' `-' `-' `----------^At this point if CPU0 path's
node->prev= prev is committed resulting in change of CPU0 prev back to CPU2 node. CPU2node->nextis NULL currently,tail v ,-. <- ,-. <- ,-. |6| |2| |0| `-' `-' `-' `----------^so if CPU0 gets into unqueue path of
osq_lockit will keep spinning in infinite loop as conditionprev->next== node will never be true.Signed-off-by Prateek Sood <[email protected]>--- kernel/locking/osq_lock.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)kernel/locking/osq_lock.c +1
-0@@ -109,6 +109,19 @@ bool osq_lock(struct optimistic_spin_queue *lock) prev =decode_cpu (old); node->prev = prev; +
kernel/locking/osq_lock.c bool osq_lock(struct optimistic_spin_queue *lock) · line 122
Quoted 10 lines
kernel/locking/osq_lock.c +10
-0+/* +* osq_lock() unqueue +* +* node->prev = prev osq_wait_next() +* WMB MB +* prev->next = node next->prev = prev //unqueue-C +* +* Here 'node->prev' and 'next->prev' are the same variable and we need +* to ensure these stores happen in-order to avoid corrupting the list. +*/
The interested pattern/behavior remains somehow implicit in this snippet (for example, as you described above, a load "reading from" the store to prev->next is implicit in that osq_wait_next()); however I was unable to come up with an alternative solution without complicating the comment.
Andrea
Quoted 9 lines
kernel/locking/osq_lock.c +2
-0+smp_wmb (); +WRITE_ONCE (prev->next, node);/* Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc., is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.