doc: rcu: remove note on smp_mb during synchronize_rcu
Subsystems (2)
RFC 1/1 doc: rcu: remove note on smp_mb during synchronize_rcu
As per this thread [1], it seems this smp_mb isn't needed anymore:
"So the smp_mb() that I was trying to add doesn't need to be there."
So let us remove this part from the memory ordering documentation.
[1] https://lkml.org/lkml/2017/10/6/707
--- .../Tree-RCU-Memory-Ordering.html | 32 +------------------ 1 file changed, 1 insertion(+), 31 deletions(-)
Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html +1 -31
@@ -77,7 +77,7 @@ The key point is that the lock-acquisition functions, including <tt>smp_mb__after_unlock_lock()</tt> immediately after successful acquisition of the lock. -<p>Therefore, for any given <tt>rcu_node</tt> struction, any access +<p>Therefore, for any given <tt>rcu_node</tt> structure, any access happening before one of the above lock-release functions will be seen by all CPUs as happening before any access happening after a later one of the above lock-acquisition functions.
@@ -162,36 +162,6 @@ an <tt>atomic_add_return()</tt> of zero) to detect idle CPUs. <tr><td> </td></tr> </table> -<p>The approach must be extended to handle one final case, that -of waking a task blocked in <tt>synchronize_rcu()</tt>. -This task might be affinitied to a CPU that is not yet aware that -the grace period has ended, and thus might not yet be subject to -the grace period's memory ordering. -Therefore, there is an <tt>smp_mb()</tt> after the return from -<tt>wait_for_completion()</tt> in the <tt>synchronize_rcu()</tt> -code path. - -<table> -<tr><th> </th></tr> -<tr><th align="left">Quick Quiz:</th></tr> -<tr><td> - What? Where??? - I don't see any <tt>smp_mb()</tt> after the return from - <tt>wait_for_completion()</tt>!!! -</td></tr> -<tr><th align="left">Answer:</th></tr> -<tr><td bgcolor="#ffffff"><font color="ffffff"> - That would be because I spotted the need for that - <tt>smp_mb()</tt> during the creation of this documentation, - and it is therefore unlikely to hit mainline before v4.14. - Kudos to Lance Roy, Will Deacon, Peter Zijlstra, and - Jonathan Cameron for asking questions that sensitized me - to the rather elaborate sequence of events that demonstrate - the need for this memory barrier. -</font></td></tr> -<tr><td> </td></tr> -</table> - <p>Tree RCU's grace--period memory-ordering guarantees rely most heavily on the <tt>rcu_node</tt> structure's <tt>->lock</tt> field, so much so that it is necessary to abbreviate this pattern
Signature · 1 line
2.19.1.568.g152ad8e336-goog
Hi Paul,
Quoted 8 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
[1] https://lkml.org/lkml/2017/10/6/707
Signed-off-by Joel Fernandes (Google) <[email protected]>
I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
thanks,
- Joel
Quoted 57 lines
--- .../Tree-RCU-Memory-Ordering.html | 32 +------------------ 1 file changed, 1 insertion(+), 31 deletions(-)Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html +1
-31@@ -77,7 +77,7 @@ The key point is that the lock-acquisition functions, including <tt>smp_mb__after_unlock_lock()</tt> immediately after successful acquisition of the lock. -<p>Therefore, for any given <tt>rcu_node</tt> struction, any access +<p>Therefore, for any given <tt>rcu_node</tt> structure, any access happening before one of the above lock-release functions will be seen by all CPUs as happening before any access happening after a later one of the above lock-acquisition functions.@@ -162,36 +162,6 @@ an <tt>atomic_add_return()</tt> of zero) to detect idle CPUs. <tr><td> </td></tr> </table> -<p>The approach must be extended to handle one final case, that -of waking a task blocked in <tt>synchronize_rcu()</tt>. -This task might be affinitied to a CPU that is not yet aware that -the grace period has ended, and thus might not yet be subject to -the grace period's memory ordering. -Therefore, there is an <tt>smp_mb()</tt> after the return from -<tt>wait_for_completion()</tt> in the <tt>synchronize_rcu()</tt> -code path. - -<table> -<tr><th> </th></tr> -<tr><th align="left">Quick Quiz:</th></tr> -<tr><td> - What? Where??? - I don't see any <tt>smp_mb()</tt> after the return from - <tt>wait_for_completion()</tt>!!! -</td></tr> -<tr><th align="left">Answer:</th></tr> -<tr><td bgcolor="#ffffff"><font color="ffffff"> - That would be because I spotted the need for that - <tt>smp_mb()</tt> during the creation of this documentation, - and it is therefore unlikely to hit mainline before v4.14. - Kudos to Lance Roy, Will Deacon, Peter Zijlstra, and - Jonathan Cameron for asking questions that sensitized me - to the rather elaborate sequence of events that demonstrate - the need for this memory barrier. -</font></td></tr> -<tr><td> </td></tr> -</table> - <p>Tree RCU's grace--period memory-ordering guarantees rely most heavily on the <tt>rcu_node</tt> structure's <tt>->lock</tt> field, so much so that it is necessary to abbreviate this patternSignature · 1 line
2.19.1.568.g152ad8e336-goog
Quoted 8 lines · Joel Fernandes
Hi Paul,
Quoted 5 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 7 lines
Quoted 3 lines
[1] https://lkml.org/lkml/2017/10/6/707
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
Thanx, Paul
Quoted 63 lines
thanks,
- Joel
Quoted 57 lines
--- .../Tree-RCU-Memory-Ordering.html | 32 +------------------ 1 file changed, 1 insertion(+), 31 deletions(-)Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html +1
-31@@ -77,7 +77,7 @@ The key point is that the lock-acquisition functions, including <tt>smp_mb__after_unlock_lock()</tt> immediately after successful acquisition of the lock. -<p>Therefore, for any given <tt>rcu_node</tt> struction, any access +<p>Therefore, for any given <tt>rcu_node</tt> structure, any access happening before one of the above lock-release functions will be seen by all CPUs as happening before any access happening after a later one of the above lock-acquisition functions.@@ -162,36 +162,6 @@ an <tt>atomic_add_return()</tt> of zero) to detect idle CPUs. <tr><td> </td></tr> </table> -<p>The approach must be extended to handle one final case, that -of waking a task blocked in <tt>synchronize_rcu()</tt>. -This task might be affinitied to a CPU that is not yet aware that -the grace period has ended, and thus might not yet be subject to -the grace period's memory ordering. -Therefore, there is an <tt>smp_mb()</tt> after the return from -<tt>wait_for_completion()</tt> in the <tt>synchronize_rcu()</tt> -code path. - -<table> -<tr><th> </th></tr> -<tr><th align="left">Quick Quiz:</th></tr> -<tr><td> - What? Where??? - I don't see any <tt>smp_mb()</tt> after the return from - <tt>wait_for_completion()</tt>!!! -</td></tr> -<tr><th align="left">Answer:</th></tr> -<tr><td bgcolor="#ffffff"><font color="ffffff"> - That would be because I spotted the need for that - <tt>smp_mb()</tt> during the creation of this documentation, - and it is therefore unlikely to hit mainline before v4.14. - Kudos to Lance Roy, Will Deacon, Peter Zijlstra, and - Jonathan Cameron for asking questions that sensitized me - to the rather elaborate sequence of events that demonstrate - the need for this memory barrier. -</font></td></tr> -<tr><td> </td></tr> -</table> - <p>Tree RCU's grace--period memory-ordering guarantees rely most heavily on the <tt>rcu_node</tt> structure's <tt>->lock</tt> field, so much so that it is necessary to abbreviate this patternSignature · 1 line
2.19.1.568.g152ad8e336-goog
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
No worries, thanks for taking it!
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
BTW I do want to discuss about this smp_mb patch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming that complete() etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if that rcu_read_unlock() triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ the synchronize_rcu.
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?
Or did I miss the points completely? :(
----------------------
TODO list of the index file marking which ones I have finished perusing:
arrayRCU.txt DONE
checklist.txt DONE
listRCU.txt DONE
lockdep.txt DONE
lockdep-splat.txt DONE
NMI-RCU.txt
rcu_dereference.txt
rcubarrier.txt
rculist_nulls.txt
rcuref.txt
rcu.txt
RTFP.txt DONE
stallwarn.txt DONE
torture.txt
UP.txt
whatisRCU.txt DONE
Design
- Data-Structures DONE
- Requirements DONE
- Expedited-Grace-Periods
- Memory Ordering next
Quoted 23 lines · Joel Fernandes
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
Quoted 7 lines
No worries, thanks for taking it!
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
If there is anything I can do to make this a more sustainable task for you, please do not keep it a secret!!!
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.
Actually, I recall an smp_mb() being added, but am not seeing it anywhere relevant to wait_for_completion(). So I might need to add the smp_mb() to synchronize_rcu() and remove the patch (retaining the typo fix). :-/
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?
There is a "network" of locking augmented by smp_mb__after_unlock_lock() that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.
Quoted 1 line
Or did I miss the points completely? :(
A question for the ages for both of us! ;-)
Quoted 20 lines
----------------------
TODO list of the index file marking which ones I have finished perusing:arrayRCU.txt DONE
checklist.txt DONE
listRCU.txt DONE
lockdep.txt DONE
lockdep-splat.txt DONE
NMI-RCU.txt
rcu_dereference.txt
rcubarrier.txt
rculist_nulls.txt
rcuref.txt
rcu.txt
RTFP.txt DONE
stallwarn.txt DONE
torture.txt
UP.txt
whatisRCU.txt DONE
Quoted 5 lines
Design
- Data-Structures DONE
- Requirements DONE
- Expedited-Grace-Periods
- Memory Ordering next
Great progress, and again, thank you!!!
Thanx, Paul
Quoted 26 lines · Paul E. McKenney
Quoted 25 lines · Joel Fernandes
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
No worries, thanks for taking it!
Quoted 8 lines
Quoted 5 lines
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
If there is anything I can do to make this a more sustainable task for you, please do not keep it a secret!!!
Thanks a lot, that means a lot to me! Will do!
Quoted 11 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.
Quoted 3 lines
Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/
No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
Quoted 5 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?
Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that complete() was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.
Did you feel this will violate condition 1. or condition 2. in "Memory-Barrier Guarantees"? Or both?
https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Memory-Barrier%20Guarantees
Quoted 20 lines
Quoted 20 lines
----------------------
TODO list of the index file marking which ones I have finished perusing:arrayRCU.txt DONE
checklist.txt DONE
listRCU.txt DONE
lockdep.txt DONE
lockdep-splat.txt DONE
NMI-RCU.txt
rcu_dereference.txt
rcubarrier.txt
rculist_nulls.txt
rcuref.txt
rcu.txt
RTFP.txt DONE
stallwarn.txt DONE
torture.txt
UP.txt
whatisRCU.txt DONE
Quoted 7 lines
Quoted 5 lines
Design
- Data-Structures DONE
- Requirements DONE
- Expedited-Grace-Periods
- Memory Ordering nextGreat progress, and again, thank you!!!
Thanks and you're welcome!
- Joel
Quoted 49 lines · Joel Fernandes
Quoted 26 lines · Paul E. McKenney
Quoted 25 lines · Joel Fernandes
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
No worries, thanks for taking it!
Quoted 8 lines
Quoted 5 lines
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
If there is anything I can do to make this a more sustainable task for you, please do not keep it a secret!!!
Thanks a lot, that means a lot to me! Will do!
Quoted 11 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.
Quoted 6 lines
Quoted 3 lines
Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
And an smp_mb() is needed in Tree RCU's __wait_rcu_gp(). This is because wait_for_completion() might get a "fly-by" wakeup, which would mean no ordering for code naively thinking that it was ordered after a grace period.
Quoted 7 lines
Quoted 5 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Would it make sense to have an RCU-implementation BoF?
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.
Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.
There is indeed a lock that is unconditionally acquired and released by wait_for_completion(), but it lacks the smp_mb__after_unlock_lock() that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.
SRCU and expedited RCU grace periods handle this correctly. Only the normal grace periods are missing the needed barrier. The probability of failure is extremely low in the common case, which involves all sorts of synchronization on the wakeup path. It would be quite strange (but not impossible) for the wait_for_completion() exit path to -not- to do a full wakeup. Plus the bug requires a reader before the grace period to do a store to some location that post-grace-period code loads from. Which is a very rare use case.
But it still should be fixed. ;-)
Quoted 3 lines
Did you feel this will violate condition 1. or condition 2. in "Memory-Barrier Guarantees"? Or both?
https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Memory-Barrier%20Guarantees
Condition 1. There might be some strange combination of events that could also cause it to also violate condition 2, but I am not immediately seeing it.
Quoted 26 lines
Quoted 26 lines
Quoted 25 lines
----------------------
TODO list of the index file marking which ones I have finished perusing:arrayRCU.txt DONE
checklist.txt DONE
listRCU.txt DONE
lockdep.txt DONE
lockdep-splat.txt DONE
NMI-RCU.txt
rcu_dereference.txt
rcubarrier.txt
rculist_nulls.txt
rcuref.txt
rcu.txt
RTFP.txt DONE
stallwarn.txt DONE
torture.txt
UP.txt
whatisRCU.txt DONEDesign
- Data-Structures DONE
- Requirements DONE
- Expedited-Grace-Periods
- Memory Ordering next
Quoted 3 lines
Quoted 1 line
Great progress, and again, thank you!!!
Thanks and you're welcome!
And here is the fix proposed above. Thoughts?
Thanx, Paul
------------------------------------------------------------------------
commit bf3c11b7b9789283f993d9beb80caaabc4403916
Author: Paul E. McKenney <[email protected]> Date: Thu Nov 1 09:05:02 2018 -0700
rcu: Add full memory barrier in __wait_rcu_gp()
RCU grace periods have extremely strong any-to-any ordering requirements that are met by placing full barriers in various places in the grace-period computation. However, normal grace period requests might be subjected to a "fly-by" wakeup in which the requesting process doesn't actually sleep and in which the corresponding CPU is not yet aware that the grace period has ended. In this case, loads in the code immediately following the synchronize_rcu() call might potentially see values before stores preceding the grace period on other CPUs.
This is an unusual use case, because RCU readers normally read. However, they can do writes, and if they do, we need post-grace-period reads to see those writes.
This commit therefore adds an smp_mb() to the end of __wait_rcu_gp().
Many thanks to Joel Fernandes for the series of questions leading to me realizing that this bug exists!
kernel/rcu/update.c +1 -0
@@ -360,6 +360,7 @@ void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array,wait_for_completion (&rs_array[i].completion);destroy_rcu_head_on_stack (&rs_array[i].head); } +smp_mb ();/* Provide ordering in case of fly-by wakeup. */ }EXPORT_SYMBOL_GPL (__wait_rcu_gp);
Quoted 15 lines · Paul E. McKenney
Quoted 15 lines
Quoted 14 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/
Quoted 7 lines
Quoted 2 lines
No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
And an
smp_mb()is needed in Tree RCU's__wait_rcu_gp(). This is becausewait_for_completion()might get a "fly-by" wakeup, which would mean no ordering for code naively thinking that it was ordered after a grace period.
Makes sense.
Quoted 9 lines
Quoted 7 lines
Quoted 5 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Would it make sense to have an RCU-implementation BoF?
Yes, I would very much like that. I also spoke with my colleage Daniel Colascione and he said he would be interested too.
I think it would make sense also to combine it with other memory-ordering topics like the memory model and rseq/cpu-opv things that Mathieu was doing (if it makes sense to combine). But yes, I am definitely interested in an RCU-implementation BoF session.
Quoted 41 lines
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.SRCU and expedited RCU grace periods handle this correctly. Only the normal grace periods are missing the needed barrier. The probability of failure is extremely low in the common case, which involves all sorts of synchronization on the wakeup path. It would be quite strange (but not impossible) for the
wait_for_completion()exit path to -not- to do a full wakeup. Plus the bug requires a reader before the grace period to do a store to some location that post-grace-period code loads from. Which is a very rare use case.But it still should be fixed. ;-)
Quoted 7 lines
Quoted 3 lines
Did you feel this will violate condition 1. or condition 2. in "Memory-Barrier Guarantees"? Or both?
https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Memory-Barrier%20GuaranteesCondition 1. There might be some strange combination of events that could also cause it to also violate condition 2, but I am not immediately seeing it.
In the previous paragraph, you mentioned the bug "requires a reader before the GP to do a store". However, condition 1 is really different - it is a reader holding a reference to a pointer that is used *after* the synchronize_rcu returns. So that reader's load of the pointer should have completed by the time GP ends, otherwise the reader can look at kfree'd data. That's different right?
For condition 2, I analyzed it below, let me know what you think:
Quoted 35 lines
Thanx, Paul
------------------------------------------------------------------------
commit
bf3c11b7b9789283f993d9beb80caaabc4403916Author: Paul E. McKenney <[email protected]> Date: Thu Nov 1 09:05:02 2018 -0700rcu: Add full memory barrier in
__wait_rcu_gp()RCU grace periods have extremely strong any-to-any ordering requirements that are met by placing full barriers in various places in the grace-period computation. However, normal grace period requests might be subjected to a "fly-by" wakeup in which the requesting process doesn't actually sleep and in which the corresponding CPU is not yet aware that the grace period has ended. In this case, loads in the code immediately following the
synchronize_rcu()call might potentially see values before stores preceding the grace period on other CPUs.This is an unusual use case, because RCU readers normally read. However, they can do writes, and if they do, we need post-grace-period reads to see those writes.
This commit therefore adds an
smp_mb()to the end of__wait_rcu_gp().Many thanks to Joel Fernandes for the series of questions leading to me realizing that this bug exists!
Signed-off-by Paul E. McKenney <[email protected]>kernel/rcu/update.c +0
-0
kernel/rcu/update.c void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array, · line 366
Quoted 7 lines
kernel/rcu/update.c +1
-0@@ -360,6 +360,7 @@ void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array,wait_for_completion (&rs_array[i].completion);destroy_rcu_head_on_stack (&rs_array[i].head); } +smp_mb ();/* Provide ordering in case of fly-by wakeup. */ }EXPORT_SYMBOL_GPL (__wait_rcu_gp);
The fix looks fine to me. Thanks.
If I understand correctly the wait_for_completion() is an ACQUIRE operation, and the complete() is a RELEASE operation aka the "MP pattern". The ACQUIRE/RELEASE semantics allow any writes that happened before the ACQUIRE to get ordered after it. So that would actually imply it is not strong enough for ordering purposes during a "fly-by" wake up scenario and would be a violation of CONDITION 2, I think (not only condition 1 as you said). This is because future readers may accidentally see the writes that happened *before* the synchronize_rcu which is CONDITION 2 in the requirements:
https://goo.gl/8mrDHN (I had to shortlink it ;))
Cheers,
- Joel
Quoted 30 lines · Joel Fernandes
Quoted 15 lines · Paul E. McKenney
Quoted 15 lines
Quoted 14 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/Quoted 7 lines
Quoted 2 lines
No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
And an
smp_mb()is needed in Tree RCU's__wait_rcu_gp(). This is becausewait_for_completion()might get a "fly-by" wakeup, which would mean no ordering for code naively thinking that it was ordered after a grace period.Makes sense.
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Would it make sense to have an RCU-implementation BoF?
Yes, I would very much like that. I also spoke with my colleage Daniel Colascione and he said he would be interested too.
Sounds good!
Quoted 4 lines
I think it would make sense also to combine it with other memory-ordering topics like the memory model and rseq/cpu-opv things that Mathieu was doing (if it makes sense to combine). But yes, I am definitely interested in an RCU-implementation BoF session.
There is an LKMM kernel summit track presentation. I believe that Mathieu's rseq/cpu-opv would be a good one as well, but Mathieu needs to lead this up and it should be a separate BoF. Please do feel free to reach out to him. I am sure that he would be particularly interested in potential uses of rseq and especially cpu-opv.
Quoted 49 lines
Quoted 41 lines
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.SRCU and expedited RCU grace periods handle this correctly. Only the normal grace periods are missing the needed barrier. The probability of failure is extremely low in the common case, which involves all sorts of synchronization on the wakeup path. It would be quite strange (but not impossible) for the
wait_for_completion()exit path to -not- to do a full wakeup. Plus the bug requires a reader before the grace period to do a store to some location that post-grace-period code loads from. Which is a very rare use case.But it still should be fixed. ;-)
Quoted 7 lines
Quoted 3 lines
Did you feel this will violate condition 1. or condition 2. in "Memory-Barrier Guarantees"? Or both?
https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Memory-Barrier%20GuaranteesCondition 1. There might be some strange combination of events that could also cause it to also violate condition 2, but I am not immediately seeing it.
Quoted 6 lines
In the previous paragraph, you mentioned the bug "requires a reader before the GP to do a store". However, condition 1 is really different - it is a reader holding a reference to a pointer that is used *after* the
synchronize_rcureturns. So that reader's load of the pointer should have completed by the time GP ends, otherwise the reader can look at kfree'd data. That's different right?
More specifically, the fix prevents a prior reader's -store- within its critical section to be seen as happening after a load that follows the end of the grace period. So I stand by Condition 1. ;-)
And again, a store within an RCU read-side critical section is a bit on the strange side, but this sort of thing is perfectly legal and is used, albeit rather rarely.
Quoted 47 lines
For condition 2, I analyzed it below, let me know what you think:
Quoted 35 lines
Thanx, Paul
------------------------------------------------------------------------
commit
bf3c11b7b9789283f993d9beb80caaabc4403916Author: Paul E. McKenney <[email protected]> Date: Thu Nov 1 09:05:02 2018 -0700rcu: Add full memory barrier in
__wait_rcu_gp()RCU grace periods have extremely strong any-to-any ordering requirements that are met by placing full barriers in various places in the grace-period computation. However, normal grace period requests might be subjected to a "fly-by" wakeup in which the requesting process doesn't actually sleep and in which the corresponding CPU is not yet aware that the grace period has ended. In this case, loads in the code immediately following the
synchronize_rcu()call might potentially see values before stores preceding the grace period on other CPUs.This is an unusual use case, because RCU readers normally read. However, they can do writes, and if they do, we need post-grace-period reads to see those writes.
This commit therefore adds an
smp_mb()to the end of__wait_rcu_gp().Many thanks to Joel Fernandes for the series of questions leading to me realizing that this bug exists!
Signed-off-by Paul E. McKenney <[email protected]>kernel/rcu/update.c +0
-0kernel/rcu/update.c void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array, · line 366
Quoted 7 lines
kernel/rcu/update.c +1
-0@@ -360,6 +360,7 @@ void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array,wait_for_completion (&rs_array[i].completion);destroy_rcu_head_on_stack (&rs_array[i].head); } +smp_mb ();/* Provide ordering in case of fly-by wakeup. */ }EXPORT_SYMBOL_GPL (__wait_rcu_gp);The fix looks fine to me. Thanks.
Quoted 9 lines
If I understand correctly the
wait_for_completion()is an ACQUIRE operation, and thecomplete()is a RELEASE operation aka the "MP pattern". The ACQUIRE/RELEASE semantics allow any writes that happened before the ACQUIRE to get ordered after it. So that would actually imply it is not strong enough for ordering purposes during a "fly-by" wake up scenario and would be a violation of CONDITION 2, I think (not only condition 1 as you said). This is because future readers may accidentally see the writes that happened *before* thesynchronize_rcuwhich is CONDITION 2 in the requirements:
https://goo.gl/8mrDHN (I had to shortlink it ;))
I do appreciate the shorter link. ;-)
A write happening before the grace period is ordered by the grace period's network of strong barriers, so the fix does not matter in that case. Also, the exact end of the grace period is irrelevant for Condition 2, it is instead the beginning of the grace period compared to the beginning of later RCU read-side critical sections.
Not saying that Condition 2 cannot somehow happen without the memory barrier, just saying that it will take quite a bit more creativity to find a relevant scenario.
Please see below for the updated patch, containing only the typo fix. Please let me know if I messed anything up.
Thanx, Paul
------------------------------------------------------------------------
commit bdf892699a32e82305c7203d61f93cffdfbe8735
Author: Joel Fernandes (Google) <[email protected]> Date: Sat Oct 27 21:30:46 2018 -0700
doc: Fix "struction" typo in RCU memory-ordering documentation.
This commit replaces "struction" with the correct "structure".
Documentation/RCU/Design/Memory-Ordering/Tree-RCU-Memory-Ordering.html +1 -1
@@ -77,7 +77,7 @@ The key point is that the lock-acquisition functions, including <tt>smp_mb__after_unlock_lock()</tt> immediately after successful acquisition of the lock. -<p>Therefore, for any given <tt>rcu_node</tt> struction, any access +<p>Therefore, for any given <tt>rcu_node</tt> structure, any access happening before one of the above lock-release functions will be seen by all CPUs as happening before any access happening after a later one of the above lock-acquisition functions.
On Fri, Nov 02, 2018 at 01:00:00PM -0700, Paul E. McKenney wrote:
[..]
Quoted 10 lines
Quoted 4 lines
I think it would make sense also to combine it with other memory-ordering topics like the memory model and rseq/cpu-opv things that Mathieu was doing (if it makes sense to combine). But yes, I am definitely interested in an RCU-implementation BoF session.
There is an LKMM kernel summit track presentation. I believe that Mathieu's rseq/cpu-opv would be a good one as well, but Mathieu needs to lead this up and it should be a separate BoF. Please do feel free to reach out to him. I am sure that he would be particularly interested in potential uses of rseq and especially cpu-opv.
Cool! Looking forward to LKMM talk and I'll keep in mind to reach out to Mathieu about rseq usecases.
Quoted 56 lines
Quoted 49 lines
Quoted 41 lines
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.SRCU and expedited RCU grace periods handle this correctly. Only the normal grace periods are missing the needed barrier. The probability of failure is extremely low in the common case, which involves all sorts of synchronization on the wakeup path. It would be quite strange (but not impossible) for the
wait_for_completion()exit path to -not- to do a full wakeup. Plus the bug requires a reader before the grace period to do a store to some location that post-grace-period code loads from. Which is a very rare use case.But it still should be fixed. ;-)
Quoted 7 lines
Quoted 3 lines
Did you feel this will violate condition 1. or condition 2. in "Memory-Barrier Guarantees"? Or both?
https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Memory-Barrier%20GuaranteesCondition 1. There might be some strange combination of events that could also cause it to also violate condition 2, but I am not immediately seeing it.
Quoted 6 lines
In the previous paragraph, you mentioned the bug "requires a reader before the GP to do a store". However, condition 1 is really different - it is a reader holding a reference to a pointer that is used *after* the
synchronize_rcureturns. So that reader's load of the pointer should have completed by the time GP ends, otherwise the reader can look at kfree'd data. That's different right?
Quoted 6 lines
More specifically, the fix prevents a prior reader's -store- within its critical section to be seen as happening after a load that follows the end of the grace period. So I stand by Condition 1. ;-) And again, a store within an RCU read-side critical section is a bit on the strange side, but this sort of thing is perfectly legal and is used, albeit rather rarely.
Cool :) I never thought about condition 1 this way but good to know that's possible :)
Quoted 32 lines
Quoted 32 lines
For condition 2, I analyzed it below, let me know what you think:
Quoted 30 lines
Thanx, Paul
------------------------------------------------------------------------
commit
bf3c11b7b9789283f993d9beb80caaabc4403916Author: Paul E. McKenney <[email protected]> Date: Thu Nov 1 09:05:02 2018 -0700rcu: Add full memory barrier in
__wait_rcu_gp()RCU grace periods have extremely strong any-to-any ordering requirements that are met by placing full barriers in various places in the grace-period computation. However, normal grace period requests might be subjected to a "fly-by" wakeup in which the requesting process doesn't actually sleep and in which the corresponding CPU is not yet aware that the grace period has ended. In this case, loads in the code immediately following the
synchronize_rcu()call might potentially see values before stores preceding the grace period on other CPUs.This is an unusual use case, because RCU readers normally read. However, they can do writes, and if they do, we need post-grace-period reads to see those writes.
This commit therefore adds an
smp_mb()to the end of__wait_rcu_gp().Many thanks to Joel Fernandes for the series of questions leading to me realizing that this bug exists!
Signed-off-by Paul E. McKenney <[email protected]>
Quoted 12 lines
Quoted 4 lines
Quoted 4 lines
kernel/rcu/update.c +0
-0Quoted 8 lines
kernel/rcu/update.c void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array, · line 366
Quoted 8 lines
kernel/rcu/update.c +1
-0@@ -360,6 +360,7 @@ void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array,wait_for_completion (&rs_array[i].completion);destroy_rcu_head_on_stack (&rs_array[i].head); } +smp_mb ();/* Provide ordering in case of fly-by wakeup. */ }EXPORT_SYMBOL_GPL (__wait_rcu_gp);
Quoted 12 lines
Quoted 11 lines
The fix looks fine to me. Thanks.
If I understand correctly the
wait_for_completion()is an ACQUIRE operation, and thecomplete()is a RELEASE operation aka the "MP pattern". The ACQUIRE/RELEASE semantics allow any writes that happened before the ACQUIRE to get ordered after it. So that would actually imply it is not strong enough for ordering purposes during a "fly-by" wake up scenario and would be a violation of CONDITION 2, I think (not only condition 1 as you said). This is because future readers may accidentally see the writes that happened *before* thesynchronize_rcuwhich is CONDITION 2 in the requirements:
https://goo.gl/8mrDHN (I had to shortlink it ;))
Quoted 4 lines
I do appreciate the shorter link. ;-)
A write happening before the grace period is ordered by the grace period's network of strong barriers, so the fix does not matter in that case.
I was talking about the acquire/release pairs in the calls to spin_lock and spin_unlock in wait_for_completion, not in the grace period network of rnp locks. Does that make sense?
I thought that during a "fly-by" wake up, that network of strong barriers doesn't really trigger and that that's the problematic scenario. Did I miss something? I was talking about the acquire/release pair in wait_for_completion during that fly-by scenario.
Quoted 10 lines
Also, the exact end of the grace period is irrelevant for Condition 2, it is instead the beginning of the grace period compared to the beginning of later RCU read-side critical sections.
Not saying that Condition 2 cannot somehow happen without the memory barrier, just saying that it will take quite a bit more creativity to find a relevant scenario.
Please see below for the updated patch, containing only the typo fix. Please let me know if I messed anything up.
Looks good to me, thanks!
- Joel
Quoted 7 lines · Joel Fernandes
On Fri, Nov 02, 2018 at 01:00:00PM -0700, Paul E. McKenney wrote:
[..]Quoted 5 lines
Quoted 4 lines
I think it would make sense also to combine it with other memory-ordering topics like the memory model and rseq/cpu-opv things that Mathieu was doing (if it makes sense to combine). But yes, I am definitely interested in an RCU-implementation BoF session.
Quoted 8 lines
Quoted 5 lines
There is an LKMM kernel summit track presentation. I believe that Mathieu's rseq/cpu-opv would be a good one as well, but Mathieu needs to lead this up and it should be a separate BoF. Please do feel free to reach out to him. I am sure that he would be particularly interested in potential uses of rseq and especially cpu-opv.
Cool! Looking forward to LKMM talk and I'll keep in mind to reach out to Mathieu about rseq usecases.
Sounds good!
Quoted 63 lines
Quoted 56 lines
Quoted 49 lines
Quoted 41 lines
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.SRCU and expedited RCU grace periods handle this correctly. Only the normal grace periods are missing the needed barrier. The probability of failure is extremely low in the common case, which involves all sorts of synchronization on the wakeup path. It would be quite strange (but not impossible) for the
wait_for_completion()exit path to -not- to do a full wakeup. Plus the bug requires a reader before the grace period to do a store to some location that post-grace-period code loads from. Which is a very rare use case.But it still should be fixed. ;-)
Quoted 7 lines
Quoted 3 lines
Did you feel this will violate condition 1. or condition 2. in "Memory-Barrier Guarantees"? Or both?
https://www.kernel.org/doc/Documentation/RCU/Design/Requirements/Requirements.html#Memory-Barrier%20GuaranteesCondition 1. There might be some strange combination of events that could also cause it to also violate condition 2, but I am not immediately seeing it.
Quoted 6 lines
In the previous paragraph, you mentioned the bug "requires a reader before the GP to do a store". However, condition 1 is really different - it is a reader holding a reference to a pointer that is used *after* the
synchronize_rcureturns. So that reader's load of the pointer should have completed by the time GP ends, otherwise the reader can look at kfree'd data. That's different right?Quoted 6 lines
More specifically, the fix prevents a prior reader's -store- within its critical section to be seen as happening after a load that follows the end of the grace period. So I stand by Condition 1. ;-) And again, a store within an RCU read-side critical section is a bit on the strange side, but this sort of thing is perfectly legal and is used, albeit rather rarely.
Quoted 2 lines
Cool :) I never thought about condition 1 this way but good to know that's possible :)
I know that feeling... ;-)
Quoted 62 lines
Quoted 32 lines
Quoted 32 lines
For condition 2, I analyzed it below, let me know what you think:
Quoted 30 lines
Thanx, Paul
------------------------------------------------------------------------
commit
bf3c11b7b9789283f993d9beb80caaabc4403916Author: Paul E. McKenney <[email protected]> Date: Thu Nov 1 09:05:02 2018 -0700rcu: Add full memory barrier in
__wait_rcu_gp()RCU grace periods have extremely strong any-to-any ordering requirements that are met by placing full barriers in various places in the grace-period computation. However, normal grace period requests might be subjected to a "fly-by" wakeup in which the requesting process doesn't actually sleep and in which the corresponding CPU is not yet aware that the grace period has ended. In this case, loads in the code immediately following the
synchronize_rcu()call might potentially see values before stores preceding the grace period on other CPUs.This is an unusual use case, because RCU readers normally read. However, they can do writes, and if they do, we need post-grace-period reads to see those writes.
This commit therefore adds an
smp_mb()to the end of__wait_rcu_gp().Many thanks to Joel Fernandes for the series of questions leading to me realizing that this bug exists!
Signed-off-by Paul E. McKenney <[email protected]>Quoted 12 lines
Quoted 4 lines
Quoted 4 lines
kernel/rcu/update.c +0
-0Quoted 8 lines
kernel/rcu/update.c void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array, · line 366
Quoted 8 lines
kernel/rcu/update.c +1
-0@@ -360,6 +360,7 @@ void __wait_rcu_gp(bool checktiny, int n, call_rcu_func_t *crcu_array,wait_for_completion (&rs_array[i].completion);destroy_rcu_head_on_stack (&rs_array[i].head); } +smp_mb ();/* Provide ordering in case of fly-by wakeup. */ }EXPORT_SYMBOL_GPL (__wait_rcu_gp);Quoted 12 lines
Quoted 11 lines
The fix looks fine to me. Thanks.
If I understand correctly the
wait_for_completion()is an ACQUIRE operation, and thecomplete()is a RELEASE operation aka the "MP pattern". The ACQUIRE/RELEASE semantics allow any writes that happened before the ACQUIRE to get ordered after it. So that would actually imply it is not strong enough for ordering purposes during a "fly-by" wake up scenario and would be a violation of CONDITION 2, I think (not only condition 1 as you said). This is because future readers may accidentally see the writes that happened *before* thesynchronize_rcuwhich is CONDITION 2 in the requirements:
https://goo.gl/8mrDHN (I had to shortlink it ;))Quoted 4 lines
I do appreciate the shorter link. ;-)
A write happening before the grace period is ordered by the grace period's network of strong barriers, so the fix does not matter in that case.
Quoted 8 lines
I was talking about the acquire/release pairs in the calls to
spin_lockandspin_unlockinwait_for_completion, not in the grace period network of rnp locks. Does that make sense?I thought that during a "fly-by" wake up, that network of strong barriers doesn't really trigger and that that's the problematic scenario. Did I miss something? I was talking about the acquire/release pair in
wait_for_completionduring that fly-by scenario.
The thing is that the ordering of the wakeup doesn't matter, because in Condition 2, the end of the grace period (which is where the wakeup happens) isn't involved in the ordering. It is instead the ordering of the beginning of the grace period with the beginning of some later RCU read-side critical section.
Another way to look at this is that in Condition 2, we don't have to care when the grace period ends.
Quoted 4 lines
Quoted 4 lines
Also, the exact end of the grace period is irrelevant for Condition 2, it is instead the beginning of the grace period compared to the beginning of later RCU read-side critical sections.
Quoted 8 lines
Quoted 6 lines
Not saying that Condition 2 cannot somehow happen without the memory barrier, just saying that it will take quite a bit more creativity to find a relevant scenario.
Please see below for the updated patch, containing only the typo fix. Please let me know if I messed anything up.
Looks good to me, thanks!
It is queued, likely for the next merge window.
Thanx, Paul
Quoted 96 lines · Paul E. McKenney
Quoted 49 lines · Joel Fernandes
Quoted 26 lines · Paul E. McKenney
Quoted 25 lines · Joel Fernandes
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
No worries, thanks for taking it!
Quoted 8 lines
Quoted 5 lines
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
If there is anything I can do to make this a more sustainable task for you, please do not keep it a secret!!!
Thanks a lot, that means a lot to me! Will do!
Quoted 11 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.Quoted 6 lines
Quoted 3 lines
Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
And an
smp_mb()is needed in Tree RCU's__wait_rcu_gp(). This is becausewait_for_completion()might get a "fly-by" wakeup, which would mean no ordering for code naively thinking that it was ordered after a grace period.Quoted 7 lines
Quoted 5 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Would it make sense to have an RCU-implementation BoF?
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.
Quoted 5 lines
There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.
Sorry to be so persistent, but I did spend some time on this and I still don't get why every CPU would _not_ have executed smp_mb__after_unlock_lock at least once before the wait_for_completion() returns, because every CPU should have atleast called rcu_report_qs_rdp() -> rcu_report_qs_rnp() atleast once to report its QS up the tree right?. Before that procedure, the complete() cannot happen because the complete() itself is in an RCU callback which is executed only once all the QS(s) have been reported.
So I still couldn't see how the synchronize_rcu can return without the rcu_report_qs_rnp called atleast once on the CPU reporting its QS during a grace period.
Would it be possible to provide a small example showing this in least number of steps? I appreciate your time and it would be really helpful. If you feel its too complicated, then feel free to keep this for LPC discussion :)
Thanks,
-Joel
Quoted 111 lines · Joel Fernandes
Quoted 96 lines · Paul E. McKenney
Quoted 49 lines · Joel Fernandes
Quoted 26 lines · Paul E. McKenney
Quoted 25 lines · Joel Fernandes
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
No worries, thanks for taking it!
Quoted 8 lines
Quoted 5 lines
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
If there is anything I can do to make this a more sustainable task for you, please do not keep it a secret!!!
Thanks a lot, that means a lot to me! Will do!
Quoted 11 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.Quoted 6 lines
Quoted 3 lines
Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
And an
smp_mb()is needed in Tree RCU's__wait_rcu_gp(). This is becausewait_for_completion()might get a "fly-by" wakeup, which would mean no ordering for code naively thinking that it was ordered after a grace period.Quoted 7 lines
Quoted 5 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Would it make sense to have an RCU-implementation BoF?
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.Quoted 5 lines
There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.Sorry to be so persistent, but I did spend some time on this and I still don't get why every CPU would _not_ have executed
smp_mb__after_unlock_lockat least once before thewait_for_completion()returns, because every CPU should have atleast calledrcu_report_qs_rdp()->rcu_report_qs_rnp()atleast once to report its QS up the tree right?. Before that procedure, thecomplete()cannot happen because thecomplete()itself is in an RCU callback which is executed only once all the QS(s) have been reported.
Quoted 7 lines
So I still couldn't see how the
synchronize_rcucan return without thercu_report_qs_rnpcalled atleast once on the CPU reporting its QS during a grace period.Would it be possible to provide a small example showing this in least number of steps? I appreciate your time and it would be really helpful. If you feel its too complicated, then feel free to keep this for LPC discussion :)
The key point is that "at least once" does not suffice, other than for the CPU that detects the end of the grace period. The rest of the CPUs must do at least -two- full barriers, which could of course be either smp_mb() on the one hand or smp_mb__after_unlock_lock() after a lock on the other.
The reason for this is the all-to-all ordering that is required. First, the grace period does a fan-in operation as each CPU responds to the grace-period request, informing RCU of its quiescent state while holding a fully ordered lock. Second, some CPU detects the end of the grace period while holding a fully ordered lock. Third, each remaining CPU notes the end of the grace period, again while holding a fully ordered lock.
Now suppose that the wakeup callback for a given call to synchronize_rcu() is on the CPU that detected the end of the grace period, but the task to be awakened will run on some other CPU. Suppose further that this other CPU hasn't yet noticed the end of the grace period, and further yet that it was the first one to report a quiescent state. This means that its most recent fully ordered lock was released too early to order against the other CPUs' quiescent states. Now, as you say, the lock acquisitions and releases for the completion() and wait_for_completion() will cause the awakened CPU to correctly see any pre-grace-period activity on the CPU that detected the end of the grace period. But this is not the case for any of the other CPUs, and won't be until the awakened CPU notes the end of the grace period while holding its fully ordered lock.
So we really do need that memory barrier at the end of __wait_rcu_gp().
Thanx, Paul
Quoted 116 lines · Paul E. McKenney
Quoted 115 lines · Joel Fernandes
Quoted 96 lines · Paul E. McKenney
Quoted 49 lines · Joel Fernandes
Quoted 26 lines · Paul E. McKenney
Quoted 25 lines · Joel Fernandes
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
No worries, thanks for taking it!
Quoted 8 lines
Quoted 5 lines
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
If there is anything I can do to make this a more sustainable task for you, please do not keep it a secret!!!
Thanks a lot, that means a lot to me! Will do!
Quoted 11 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.Quoted 6 lines
Quoted 3 lines
Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
And an
smp_mb()is needed in Tree RCU's__wait_rcu_gp(). This is becausewait_for_completion()might get a "fly-by" wakeup, which would mean no ordering for code naively thinking that it was ordered after a grace period.Quoted 7 lines
Quoted 5 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Would it make sense to have an RCU-implementation BoF?
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.Quoted 5 lines
There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.Sorry to be so persistent, but I did spend some time on this and I still don't get why every CPU would _not_ have executed
smp_mb__after_unlock_lockat least once before thewait_for_completion()returns, because every CPU should have atleast calledrcu_report_qs_rdp()->rcu_report_qs_rnp()atleast once to report its QS up the tree right?. Before that procedure, thecomplete()cannot happen because thecomplete()itself is in an RCU callback which is executed only once all the QS(s) have been reported.So I still couldn't see how the
synchronize_rcucan return without thercu_report_qs_rnpcalled atleast once on the CPU reporting its QS during a grace period.
Quoted 8 lines
Quoted 3 lines
Would it be possible to provide a small example showing this in least number of steps? I appreciate your time and it would be really helpful. If you feel its too complicated, then feel free to keep this for LPC discussion :)
The key point is that "at least once" does not suffice, other than for the CPU that detects the end of the grace period. The rest of the CPUs must do at least -two- full barriers, which could of course be either
smp_mb()on the one hand orsmp_mb__after_unlock_lock()after a lock on the other.
I thought I'll atleast get an understanding of the "atleast two full barriers" point and ask you any questions at LPC, because that's what I'm missing I think. Trying to understand what can go wrong without two full barriers. I'm sure an RCU implementation BoF could really in this regard.
I guess its also documented somewhere in Tree-RCU-Memory-Ordering.html but a quick search through that document didn't show a mention of the two full barriers need.. I think its also a great idea for us to document it there and/or discuss it during the conference.
I went through the litmus test here for some hints on the two-barriers but couldn't find any:
https://lkml.org/lkml/2017/10/5/636
Atleast this commit made me think no extra memory barrier is needed for tree RCU: :-\
https://lore.kernel.org/patchwork/patch/813386/
I'm sure your last email will be useful to me in the future once I can make more sense of the ordering and the need for two full barriers, so thanks a lot for writing it!
- Joel
Quoted 140 lines · Joel Fernandes
Quoted 116 lines · Paul E. McKenney
Quoted 115 lines · Joel Fernandes
Quoted 96 lines · Paul E. McKenney
Quoted 49 lines · Joel Fernandes
Quoted 26 lines · Paul E. McKenney
Quoted 25 lines · Joel Fernandes
Hi Paul,
Quoted 11 lines · Paul E. McKenney
Quoted 10 lines · Joel Fernandes
Hi Paul,
Quoted 7 lines · Joel Fernandes (Google)
As per this thread [1], it seems this
smp_mbisn't needed anymore:
"So thesmp_mb()that I was trying to add doesn't need to be there."So let us remove this part from the memory ordering documentation.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Signed-off-by Joel Fernandes (Google) <[email protected]>I was just checking about this patch. Do you feel it is correct to remove this part from the docs? Are you satisified that a barrier isn't needed there now? Or did I miss something?
Apologies, it got lost in the shuffle. I have now applied it with a bit of rework to the commit log, thank you!
No worries, thanks for taking it!
Quoted 8 lines
Quoted 5 lines
Just wanted to update you on my progress reading/correcting the docs. The 'Memory Ordering' is taking a bit of time so I paused that and I'm focusing on finishing all the other low hanging fruit. This activity is mostly during night hours after the baby is asleep but some times I also manage to sneak it into the day job ;-)
If there is anything I can do to make this a more sustainable task for you, please do not keep it a secret!!!
Thanks a lot, that means a lot to me! Will do!
Quoted 11 lines
Quoted 10 lines
BTW I do want to discuss about this
smp_mbpatch above with you at LPC if you had time, even though we are removing it from the documentation. I thought about it a few times, and I was not able to fully appreciate the need for the barrier (that is even assuming thatcomplete()etc did not do the right thing). Specifically I was wondering same thing Peter said in the above thread I think that - if thatrcu_read_unlock()triggered all the spin locking up the tree of nodes, then why is that locking not sufficient to prevent reads from the read-side section from bleeding out? That would prevent the reader that just unlocked from seeing anything that happens _after_ thesynchronize_rcu.Quoted 6 lines
Quoted 3 lines
Actually, I recall an
smp_mb()being added, but am not seeing it anywhere relevant towait_for_completion(). So I might need to add thesmp_mb()tosynchronize_rcu()and remove the patch (retaining the typo fix). :-/No problem, I'm glad atleast the patch resurfaced the topic of the potential issue :-)
And an
smp_mb()is needed in Tree RCU's__wait_rcu_gp(). This is becausewait_for_completion()might get a "fly-by" wakeup, which would mean no ordering for code naively thinking that it was ordered after a grace period.Quoted 7 lines
Quoted 5 lines
The short form answer is that anything before a grace period on any CPU must be seen by any CPU as being before anything on any CPU after that same grace period. This guarantee requires a rather big hammer.
But yes, let's talk at LPC!
Sounds great, looking forward to discussing this.
Would it make sense to have an RCU-implementation BoF?
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.Quoted 5 lines
There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.Sorry to be so persistent, but I did spend some time on this and I still don't get why every CPU would _not_ have executed
smp_mb__after_unlock_lockat least once before thewait_for_completion()returns, because every CPU should have atleast calledrcu_report_qs_rdp()->rcu_report_qs_rnp()atleast once to report its QS up the tree right?. Before that procedure, thecomplete()cannot happen because thecomplete()itself is in an RCU callback which is executed only once all the QS(s) have been reported.So I still couldn't see how the
synchronize_rcucan return without thercu_report_qs_rnpcalled atleast once on the CPU reporting its QS during a grace period.Quoted 8 lines
Quoted 3 lines
Would it be possible to provide a small example showing this in least number of steps? I appreciate your time and it would be really helpful. If you feel its too complicated, then feel free to keep this for LPC discussion :)
The key point is that "at least once" does not suffice, other than for the CPU that detects the end of the grace period. The rest of the CPUs must do at least -two- full barriers, which could of course be either
smp_mb()on the one hand orsmp_mb__after_unlock_lock()after a lock on the other.I thought I'll atleast get an understanding of the "atleast two full barriers" point and ask you any questions at LPC, because that's what I'm missing I think. Trying to understand what can go wrong without two full barriers. I'm sure an RCU implementation BoF could really in this regard.
I guess its also documented somewhere in Tree-RCU-Memory-Ordering.html but a quick search through that document didn't show a mention of the two full barriers need.. I think its also a great idea for us to document it there and/or discuss it during the conference.
I went through the litmus test here for some hints on the two-barriers but couldn't find any:
https://lkml.org/lkml/2017/10/5/636
Quoted 7 lines
Atleast this commit made me think no extra memory barrier is needed for tree RCU: :-\
https://lore.kernel.org/patchwork/patch/813386/I'm sure your last email will be useful to me in the future once I can make more sense of the ordering and the need for two full barriers, so thanks a lot for writing it!
Hmmm... I have had this argument before, haven't I? Perhaps I should take some time and get my story straight. ;-)
In my defense, I have been doing RCU since the early 1990s, long before executable formal memory models. I kept it working through sheer paranoia, and that is a hard habit to shake...
Thanx, Paul
On Sun, Nov 04, 2018 at 07:43:30PM -0800, Paul E. McKenney wrote:
[...]
Quoted 73 lines
Quoted 65 lines
Quoted 42 lines
Quoted 42 lines
Quoted 24 lines
Quoted 16 lines
Quoted 11 lines
Quoted 10 lines
Also about GP memory ordering and RCU-tree-locking, I think you mentioned to me that the RCU reader-sections are virtually extended both forward and backward and whereever it ends, those paths do heavy-weight synchronization that should be sufficient to prevent memory ordering issues (such as those you mentioned in the Requierments document). That is exactly why we don't need explicit barriers during
rcu_read_unlock. If I recall I asked you why those are not needed. So that answer made sense, but then now on going through the 'Memory Ordering' document, I see that you mentioned there is reliance on the locking. Is that reliance on locking necessary to maintain ordering then?Quoted 4 lines
There is a "network" of locking augmented by
smp_mb__after_unlock_lock()that implements the all-to-all memory ordering mentioned above. But it also needs to handle all the possible complete()/wait_for_completion() races, even those assisted by hypervisor vCPU preemption.Quoted 7 lines
I see, so it sounds like the lock network is just a partial solution. For some reason I thought before that
complete()was even called on the CPU executing the callback, all the CPUs would have acquired and released a lock in the "lock network" atleast once thus ensuring the ordering (due to the fact that the quiescent state reporting has to travel up the tree starting from the leaves), but I think that's not necessarily true so I see your point now.Quoted 5 lines
There is indeed a lock that is unconditionally acquired and released by
wait_for_completion(), but it lacks thesmp_mb__after_unlock_lock()that is required to get full-up any-to-any ordering. And unfortunate timing (as well as spurious wakeups) allow the interaction to have only normal lock-release/acquire ordering, which does not suffice in all cases.Sorry to be so persistent, but I did spend some time on this and I still don't get why every CPU would _not_ have executed
smp_mb__after_unlock_lockat least once before thewait_for_completion()returns, because every CPU should have atleast calledrcu_report_qs_rdp()->rcu_report_qs_rnp()atleast once to report its QS up the tree right?. Before that procedure, thecomplete()cannot happen because thecomplete()itself is in an RCU callback which is executed only once all the QS(s) have been reported.So I still couldn't see how the
synchronize_rcucan return without thercu_report_qs_rnpcalled atleast once on the CPU reporting its QS during a grace period.Quoted 8 lines
Quoted 3 lines
Would it be possible to provide a small example showing this in least number of steps? I appreciate your time and it would be really helpful. If you feel its too complicated, then feel free to keep this for LPC discussion :)
The key point is that "at least once" does not suffice, other than for the CPU that detects the end of the grace period. The rest of the CPUs must do at least -two- full barriers, which could of course be either
smp_mb()on the one hand orsmp_mb__after_unlock_lock()after a lock on the other.I thought I'll atleast get an understanding of the "atleast two full barriers" point and ask you any questions at LPC, because that's what I'm missing I think. Trying to understand what can go wrong without two full barriers. I'm sure an RCU implementation BoF could really in this regard.
I guess its also documented somewhere in Tree-RCU-Memory-Ordering.html but a quick search through that document didn't show a mention of the two full barriers need.. I think its also a great idea for us to document it there and/or discuss it during the conference.
I went through the litmus test here for some hints on the two-barriers but couldn't find any:
https://lkml.org/lkml/2017/10/5/636Quoted 7 lines
Atleast this commit made me think no extra memory barrier is needed for tree RCU: :-\
https://lore.kernel.org/patchwork/patch/813386/I'm sure your last email will be useful to me in the future once I can make more sense of the ordering and the need for two full barriers, so thanks a lot for writing it!
Quoted 6 lines
Hmmm... I have had this argument before, haven't I? Perhaps I should take some time and get my story straight. ;-)
In my defense, I have been doing RCU since the early 1990s, long before executable formal memory models. I kept it working through sheer paranoia, and that is a hard habit to shake...
Sure no problem, thanks a lot for taking another look into it!
Regards,
- Joel