osq_lock: fix osq_lock queue corruption
Subsystems (2)
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. At this point if CPU0 comes in to acquire osq_lock, it will update the tail count. 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(). If reordering of following stores happen then prev->next where prev being CPU2 would be updated to point to CPU0 node:
node->prev = prev; WRITE_ONCE(prev->next, node); At this point if next instruction WRITE_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. 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, 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 | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+)
kernel/locking/osq_lock.c +26 -0
@@ -104,6 +104,32 @@ bool osq_lock(struct optimistic_spin_queue *lock) prev =decode_cpu (old); node->prev = prev; + +/* +* We need to avoid reordering of link updation sequence of osq. +* A case in which the status of optimistic spin queue is +* CPU6->CPU2 in which CPU6 has acquired the lock. At this point +* if CPU0 comes in to acquire osq_lock, it will update the tail +* count. 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(). If +* reordering of following stores happen then prev->next where prev +* being CPU2 would be updated to point to CPU0 node: +* node->prev = prev; +* WRITE_ONCE(prev->next, node); +* +* At this point if next instruction +* WRITE_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. 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, 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. +*/ +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.
Peter Zijlstra
maintainerI added a few pictures, just the text didn't want to make sense to me.
Quoted 3 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|
-' -> -'
Quoted 2 lines
At this point if CPU0 comes in to acquire
osq_lock, it will update the tail count.
CPU2 CPU0
----------------------------------
tail v ,-. <- ,-. ,-. |6| |2| |0| `-' -> `-' `-'
Quoted 3 lines
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->next
Quoted 2 lines
If 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
Quoted 4 lines
At this point if next instruction
WRITE_ONCE(next->prev, prev);in CPU2 path is committed before the update of CPU0
node->prev= prev then CPU0node->prevwill point to CPU6 node.
tail
v----------. v
,-. <- ,-. ,-.
|6| |2| |0|
`-' `-' `-'
`----------^Quoted 3 lines
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| `-' `-' `-' `----------^
Quoted 2 lines
so if CPU0 gets into unqueue path of
osq_lockit will keep spinning in infinite loop as conditionprev->next== node will never be true.
Also updated the comment..
--- 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_que 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);/*
tip-bot for Prateek Sood
merge bot[tip:locking/core] locking/osq_lock: Fix osq_lock queue corruption
In reply to Prateek Soodlocking/osq_lock: Fix osq_lock queue corruption
Commit-ID: 50972fe78f24f1cd0b9d7bbf1f87d2be9e4f412e Gitweb: http://git.kernel.org/tip/50972fe78f24f1cd0b9d7bbf1f87d2be9e4f412e Author: Prateek Sood <[email protected]> AuthorDate: Fri, 14 Jul 2017 19:17:56 +0530 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 10 Aug 2017 12:28:54 +0200
locking/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 an 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 then prev->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 instruction
WRITE_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);/*
Re: [tip:locking/core] locking/osq_lock: Fix osq_lock queue corruption
Quoted 9 lines · tip-bot for Prateek Sood
Signed-off-by Prateek Sood <[email protected]>[ Added pictures, rewrote comments. ]Signed-off-by Peter Zijlstra (Intel) <[email protected]>Cc Linus Torvalds <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Thomas Gleixner <[email protected]>Signed-off-by Ingo Molnar <[email protected]>
Any reason -stable wasn't Cc'ed here? This goes back to 3.15:
fb0527bd5ea (locking/mutexes: Introduce cancelable MCS lock for adaptive spinning)
Thanks,
Davidlohr
Peter Zijlstra
maintainerRe: [tip:locking/core] locking/osq_lock: Fix osq_lock queue corruption
Quoted 12 lines · Davidlohr Bueso
Quoted 9 lines · tip-bot for Prateek Sood
Signed-off-by Prateek Sood <[email protected]>[ Added pictures, rewrote comments. ]Signed-off-by Peter Zijlstra (Intel) <[email protected]>Cc Linus Torvalds <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Thomas Gleixner <[email protected]>Signed-off-by Ingo Molnar <[email protected]>
Quoted 3 lines
Any reason -stable wasn't Cc'ed here? This goes back to 3.15:
fb0527bd5ea(locking/mutexes: Introduce cancelable MCS lock for adaptive spinning)
No real reason, and yes, I should have done a Fixes tag I suppose :/
Re: [tip:locking/core] locking/osq_lock: Fix osq_lock queue corruption
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Davidlohr Bueso
Quoted 9 lines · tip-bot for Prateek Sood
Signed-off-by Prateek Sood <[email protected]>[ Added pictures, rewrote comments. ]Signed-off-by Peter Zijlstra (Intel) <[email protected]>Cc Linus Torvalds <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Thomas Gleixner <[email protected]>Signed-off-by Ingo Molnar <[email protected]>
Quoted 5 lines
Quoted 3 lines
Any reason -stable wasn't Cc'ed here? This goes back to 3.15:
fb0527bd5ea(locking/mutexes: Introduce cancelable MCS lock for adaptive spinning)No real reason, and yes, I should have done a Fixes tag I suppose :/
Ok, Cc'ed now.
Thanks,
Davidlohr