fix rcu_try_flip_waitack_needed() to prevent grace-period stall
PATCH 1/1 fix rcu_try_flip_waitack_needed() to prevent grace-period stall
The comment was correct -- need to make the code match the comment. Without this patch, if a CPU goes dynticks idle (and stays there forever) in just the right phase of preemptible-RCU grace-period processing, grace periods stall. The offending sequence of events (courtesy of Promela/spin, at least after I got the liveness criterion coded correctly...) is as follows:
o CPU 0 is in dynticks-idle mode. Its dynticks_progress_counter
is (say) 10.
o CPU 0 takes an interrupt, so rcu_irq_enter() increments CPU 0's
dynticks_progress_counter to 11.
o CPU 1 is doing RCU grace-period processing in rcu_try_flip_idle(),
sees rcu_pending(), so invokes dyntick_save_progress_counter(), which in turn takes a snapshot of CPU 0's dynticks_progress_counter into CPU 0's rcu_dyntick_snapshot -- now set to 11. CPU 1 then updates the RCU grace-period state to rcu_try_flip_waitack().
o CPU 0 returns from its interrupt, so rcu_irq_exit() increments
CPU 0's dynticks_progress_counter to 12.
o CPU 1 later invokes rcu_try_flip_waitack(), which notices that
CPU 0 has not yet responded, and hence in turn invokes rcu_try_flip_waitack_needed(). This function examines the state of CPU 0's dynticks_progress_counter and rcu_dyntick_snapshot variables, which it copies to curr (== 12) and snap (== 11), respectively.
Because curr!=snap, the first condition fails.
Because curr-snap is only 1 and snap is odd, the second condition fails.
rcu_try_flip_waitack_needed() therefore incorrectly concludes that it must wait for CPU 0 to explicitly acknowledge the counter flip.
o CPU 0 remains forever in dynticks-idle mode, never taking
any more hardware interrupts or any NMIs, and never running any more tasks. (Of course, -something- will usually eventually happen, which might be why we haven't seen this one in the wild. Still should be fixed!)
Therefore the grace period never ends. Fix is to make the code match the comment, as shown below. With this fix, the above scenario would be satisfied with curr being even, and allow the grace period to proceed.
---
rcupreempt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/rcupreempt.c +1 -1
@@ -569,7 +569,7 @@ rcu_try_flip_waitack_needed(int cpu)* that this CPU already acknowledged the counter. */ -if ((curr - snap) >2 || (snap &0x1 ) ==0 ) +if ((curr - snap) >2 || (curr &0x1 ) ==0 )return 0 ;/* We need this CPU to explicitly acknowledge the counter flip. */
Quoted 44 lines · Paul E. McKenney
The comment was correct -- need to make the code match the comment. Without this patch, if a CPU goes dynticks idle (and stays there forever) in just the right phase of preemptible-RCU grace-period processing, grace periods stall. The offending sequence of events (courtesy of Promela/spin, at least after I got the liveness criterion coded correctly...) is as follows:
o CPU 0 is in dynticks-idle mode. Its
dynticks_progress_counteris (say) 10.o CPU 0 takes an interrupt, so
rcu_irq_enter()increments CPU 0's
dynticks_progress_counterto 11.o CPU 1 is doing RCU grace-period processing in
rcu_try_flip_idle(),
seesrcu_pending(), so invokesdyntick_save_progress_counter(), which in turn takes a snapshot of CPU 0'sdynticks_progress_counterinto CPU 0'srcu_dyntick_snapshot-- now set to 11. CPU 1 then updates the RCU grace-period state torcu_try_flip_waitack().o CPU 0 returns from its interrupt, so
rcu_irq_exit()increments
CPU 0'sdynticks_progress_counterto 12.o CPU 1 later invokes
rcu_try_flip_waitack(), which notices that
CPU 0 has not yet responded, and hence in turn invokesrcu_try_flip_waitack_needed(). This function examines the state of CPU 0'sdynticks_progress_counterandrcu_dyntick_snapshotvariables, which it copies to curr (== 12) and snap (== 11), respectively.Because curr!=snap, the first condition fails.
Because curr-snap is only 1 and snap is odd, the second condition fails.
rcu_try_flip_waitack_needed()therefore incorrectly concludes that it must wait for CPU 0 to explicitly acknowledge the counter flip.o CPU 0 remains forever in dynticks-idle mode, never taking
any more hardware interrupts or any NMIs, and never running any more tasks. (Of course, -something- will usually eventually happen, which might be why we haven't seen this one in the wild. Still should be fixed!)
Quoted 6 lines
Therefore the grace period never ends. Fix is to make the code match the comment, as shown below. With this fix, the above scenario would be satisfied with curr being even, and allow the grace period to proceed.
Signed-off-by Paul E. McKenney <[email protected]>
Paul, should this go upstream ASAP?
Quoted 22 lines
---
rcupreempt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)diff -urpNa -X dontdiff
linux-2.6.25-rc6/kernel/rcupreempt.clinux-2.6.25-rc6-rcunohz-if/kernel/rcupreempt.ckernel/rcupreempt.c +1
-2@@ -569,7 +569,7 @@ rcu_try_flip_waitack_needed(int cpu)* that this CPU already acknowledged the counter. */ -if ((curr - snap) >2 || (snap &0x1 ) ==0 ) +if ((curr - snap) >2 || (curr &0x1 ) ==0 )return 0 ;/* We need this CPU to explicitly acknowledge the counter flip. */ --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 45 lines · Peter Zijlstra
Quoted 44 lines · Paul E. McKenney
The comment was correct -- need to make the code match the comment. Without this patch, if a CPU goes dynticks idle (and stays there forever) in just the right phase of preemptible-RCU grace-period processing, grace periods stall. The offending sequence of events (courtesy of Promela/spin, at least after I got the liveness criterion coded correctly...) is as follows:
o CPU 0 is in dynticks-idle mode. Its
dynticks_progress_counteris (say) 10.o CPU 0 takes an interrupt, so
rcu_irq_enter()increments CPU 0's
dynticks_progress_counterto 11.o CPU 1 is doing RCU grace-period processing in
rcu_try_flip_idle(),
seesrcu_pending(), so invokesdyntick_save_progress_counter(), which in turn takes a snapshot of CPU 0'sdynticks_progress_counterinto CPU 0'srcu_dyntick_snapshot-- now set to 11. CPU 1 then updates the RCU grace-period state torcu_try_flip_waitack().o CPU 0 returns from its interrupt, so
rcu_irq_exit()increments
CPU 0'sdynticks_progress_counterto 12.o CPU 1 later invokes
rcu_try_flip_waitack(), which notices that
CPU 0 has not yet responded, and hence in turn invokesrcu_try_flip_waitack_needed(). This function examines the state of CPU 0'sdynticks_progress_counterandrcu_dyntick_snapshotvariables, which it copies to curr (== 12) and snap (== 11), respectively.Because curr!=snap, the first condition fails.
Because curr-snap is only 1 and snap is odd, the second condition fails.
rcu_try_flip_waitack_needed()therefore incorrectly concludes that it must wait for CPU 0 to explicitly acknowledge the counter flip.o CPU 0 remains forever in dynticks-idle mode, never taking
any more hardware interrupts or any NMIs, and never running any more tasks. (Of course, -something- will usually eventually happen, which might be why we haven't seen this one in the wild. Still should be fixed!)
Quoted 8 lines
Quoted 6 lines
Therefore the grace period never ends. Fix is to make the code match the comment, as shown below. With this fix, the above scenario would be satisfied with curr being even, and allow the grace period to proceed.
Signed-off-by Paul E. McKenney <[email protected]>Paul, should this go upstream ASAP?
Given that any activity (task wakeup, interrupt, NMI) on the offending CPU gets things going again, I have a hard time labeling it as super urgent. So I could argue for it being added to the last release candidate, but not to the final release itself.
Seem reasonable?
Thanx, Paul
Quoted 23 lines
Quoted 22 lines
---
rcupreempt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)diff -urpNa -X dontdiff
linux-2.6.25-rc6/kernel/rcupreempt.clinux-2.6.25-rc6-rcunohz-if/kernel/rcupreempt.ckernel/rcupreempt.c +1
-2@@ -569,7 +569,7 @@ rcu_try_flip_waitack_needed(int cpu)* that this CPU already acknowledged the counter. */ -if ((curr - snap) >2 || (snap &0x1 ) ==0 ) +if ((curr - snap) >2 || (curr &0x1 ) ==0 )return 0 ;/* We need this CPU to explicitly acknowledge the counter flip. */ --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 44 lines · On Fri, 21 Mar 2008 13:38:21 -0700 "Paul E. McKenney"…
The comment was correct -- need to make the code match the comment. Without this patch, if a CPU goes dynticks idle (and stays there forever) in just the right phase of preemptible-RCU grace-period processing, grace periods stall. The offending sequence of events (courtesy of Promela/spin, at least after I got the liveness criterion coded correctly...) is as follows:
o CPU 0 is in dynticks-idle mode. Its
dynticks_progress_counteris (say) 10.o CPU 0 takes an interrupt, so
rcu_irq_enter()increments CPU 0's
dynticks_progress_counterto 11.o CPU 1 is doing RCU grace-period processing in
rcu_try_flip_idle(),
seesrcu_pending(), so invokesdyntick_save_progress_counter(), which in turn takes a snapshot of CPU 0'sdynticks_progress_counterinto CPU 0'srcu_dyntick_snapshot-- now set to 11. CPU 1 then updates the RCU grace-period state torcu_try_flip_waitack().o CPU 0 returns from its interrupt, so
rcu_irq_exit()increments
CPU 0'sdynticks_progress_counterto 12.o CPU 1 later invokes
rcu_try_flip_waitack(), which notices that
CPU 0 has not yet responded, and hence in turn invokesrcu_try_flip_waitack_needed(). This function examines the state of CPU 0'sdynticks_progress_counterandrcu_dyntick_snapshotvariables, which it copies to curr (== 12) and snap (== 11), respectively.Because curr!=snap, the first condition fails.
Because curr-snap is only 1 and snap is odd, the second condition fails.
rcu_try_flip_waitack_needed()therefore incorrectly concludes that it must wait for CPU 0 to explicitly acknowledge the counter flip.o CPU 0 remains forever in dynticks-idle mode, never taking
any more hardware interrupts or any NMIs, and never running any more tasks. (Of course, -something- will usually eventually happen, which might be why we haven't seen this one in the wild. Still should be fixed!)
Quoted 4 lines
Therefore the grace period never ends. Fix is to make the code match the comment, as shown below. With this fix, the above scenario would be satisfied with curr being even, and allow the grace period to proceed.
Am having a ton of fun here putting my tree back together after a week's worth of whee-look-at-all-the-stuff-ive-never-seen-before-which-just-got-merged discoveries. (Which are not too bad actually)
This patch ran afoul of this change in Linus's tree:
kernel/rcupreempt.c +2 -2
@@ -1007,10 +1007,10 @@ void __synchronize_sched(void)if (sched_getaffinity (0 , &oldmask) <0 ) oldmask = cpu_possible_map;for_each_online_cpu (cpu) { -sched_setaffinity (0 ,cpumask_of_cpu (cpu)); +sched_setaffinity (0 , &cpumask_of_cpu (cpu));schedule (); } -sched_setaffinity (0 , oldmask); +sched_setaffinity (0 , &oldmask); }EXPORT_SYMBOL_GPL (__synchronize_sched);
I fixed it by simply removing the above changed lines. Please check that the result makes sense and that we don't need to carry the above change forward in any way?
I also removed the Cc:stable from this patch based on your followup discussion with Peter.
Thanks.
From: "Paul E. McKenney" <[email protected]>
The comment was correct -- need to make the code match the comment. Without this patch, if a CPU goes dynticks idle (and stays there forever) in just the right phase of preemptible-RCU grace-period processing, grace periods stall. The offending sequence of events (courtesy of Promela/spin, at least after I got the liveness criterion coded correctly...) is as follows:
o CPU 0 is in dynticks-idle mode. Its dynticks_progress_counter
is (say) 10.
o CPU 0 takes an interrupt, so rcu_irq_enter() increments CPU 0's
dynticks_progress_counter to 11.
o CPU 1 is doing RCU grace-period processing in rcu_try_flip_idle(),
sees rcu_pending(), so invokes dyntick_save_progress_counter(), which in turn takes a snapshot of CPU 0's dynticks_progress_counter into CPU 0's rcu_dyntick_snapshot -- now set to 11. CPU 1 then updates the RCU grace-period state to rcu_try_flip_waitack().
o CPU 0 returns from its interrupt, so rcu_irq_exit() increments
CPU 0's dynticks_progress_counter to 12.
o CPU 1 later invokes rcu_try_flip_waitack(), which notices that
CPU 0 has not yet responded, and hence in turn invokes rcu_try_flip_waitack_needed(). This function examines the state of CPU 0's dynticks_progress_counter and rcu_dyntick_snapshot variables, which it copies to curr (== 12) and snap (== 11), respectively.
Because curr!=snap, the first condition fails.
Because curr-snap is only 1 and snap is odd, the second condition fails.
rcu_try_flip_waitack_needed() therefore incorrectly concludes that it must wait for CPU 0 to explicitly acknowledge the counter flip.
o CPU 0 remains forever in dynticks-idle mode, never taking
any more hardware interrupts or any NMIs, and never running any more tasks. (Of course, -something- will usually eventually happen, which might be why we haven't seen this one in the wild. Still should be fixed!)
Therefore the grace period never ends. Fix is to make the code match the comment, as shown below. With this fix, the above scenario would be satisfied with curr being even, and allow the grace period to proceed.
---
kernel/rcupreempt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/rcupreempt.c renamed from kernel/rcupreempt.c~rcu-fix-rcu_try_flip_waitack_needed-to-prevent-grace-period-stall +1 -1
@@ -567,7 +567,7 @@ rcu_try_flip_waitack_needed(int cpu)* that this CPU already acknowledged the counter. */ -if ((curr - snap) >2 || (snap &0x1 ) ==0 ) +if ((curr - snap) >2 || (curr &0x1 ) ==0 )return 0 ;/* We need this CPU to explicitly acknowledge the counter flip. */
_
Quoted 46 lines · Andrew Morton
Quoted 44 lines · On Fri, 21 Mar 2008 13:38:21 -0700 "Paul E. McKenney"…
The comment was correct -- need to make the code match the comment. Without this patch, if a CPU goes dynticks idle (and stays there forever) in just the right phase of preemptible-RCU grace-period processing, grace periods stall. The offending sequence of events (courtesy of Promela/spin, at least after I got the liveness criterion coded correctly...) is as follows:
o CPU 0 is in dynticks-idle mode. Its
dynticks_progress_counteris (say) 10.o CPU 0 takes an interrupt, so
rcu_irq_enter()increments CPU 0's
dynticks_progress_counterto 11.o CPU 1 is doing RCU grace-period processing in
rcu_try_flip_idle(),
seesrcu_pending(), so invokesdyntick_save_progress_counter(), which in turn takes a snapshot of CPU 0'sdynticks_progress_counterinto CPU 0'srcu_dyntick_snapshot-- now set to 11. CPU 1 then updates the RCU grace-period state torcu_try_flip_waitack().o CPU 0 returns from its interrupt, so
rcu_irq_exit()increments
CPU 0'sdynticks_progress_counterto 12.o CPU 1 later invokes
rcu_try_flip_waitack(), which notices that
CPU 0 has not yet responded, and hence in turn invokesrcu_try_flip_waitack_needed(). This function examines the state of CPU 0'sdynticks_progress_counterandrcu_dyntick_snapshotvariables, which it copies to curr (== 12) and snap (== 11), respectively.Because curr!=snap, the first condition fails.
Because curr-snap is only 1 and snap is odd, the second condition fails.
rcu_try_flip_waitack_needed()therefore incorrectly concludes that it must wait for CPU 0 to explicitly acknowledge the counter flip.o CPU 0 remains forever in dynticks-idle mode, never taking
any more hardware interrupts or any NMIs, and never running any more tasks. (Of course, -something- will usually eventually happen, which might be why we haven't seen this one in the wild. Still should be fixed!)
Quoted 8 lines
Quoted 4 lines
Therefore the grace period never ends. Fix is to make the code match the comment, as shown below. With this fix, the above scenario would be satisfied with curr being even, and allow the grace period to proceed.
Am having a ton of fun here putting my tree back together after a week's worth of whee-look-at-all-the-stuff-ive-never-seen-before-which-just-got-merged discoveries. (Which are not too bad actually)
Linus did seem to be a bit more active than usual this time around. ;-)
Quoted 17 lines
This patch ran afoul of this change in Linus's tree:
kernel/rcupreempt.c +2
-2@@ -1007,10 +1007,10 @@ void __synchronize_sched(void)if (sched_getaffinity (0 , &oldmask) <0 ) oldmask = cpu_possible_map;for_each_online_cpu (cpu) { -sched_setaffinity (0 ,cpumask_of_cpu (cpu)); +sched_setaffinity (0 , &cpumask_of_cpu (cpu));schedule (); } -sched_setaffinity (0 , oldmask); +sched_setaffinity (0 , &oldmask); }EXPORT_SYMBOL_GPL (__synchronize_sched);
Quoted 3 lines
I fixed it by simply removing the above changed lines. Please check that the result makes sense and that we don't need to carry the above change forward in any way?
Yes, this change to the sched_setaffinity() API shouldn't affect the rest of the patch in any way. The patch below looks sensible. I guess my next forward-port of the call_rcu_sched() patch should be something I get started on quickly, as it might take longer than usual. ;-)
BTW, the above code is removed be the call_rcu_sched() patch in any case.
Thanx, Paul
Quoted 83 lines
I also removed the Cc:stable from this patch based on your followup discussion with Peter.
Thanks.
From: "Paul E. McKenney" <[email protected]>
The comment was correct -- need to make the code match the comment. Without this patch, if a CPU goes dynticks idle (and stays there forever) in just the right phase of preemptible-RCU grace-period processing, grace periods stall. The offending sequence of events (courtesy of Promela/spin, at least after I got the liveness criterion coded correctly...) is as follows:
o CPU 0 is in dynticks-idle mode. Its
dynticks_progress_counteris (say) 10.o CPU 0 takes an interrupt, so
rcu_irq_enter()increments CPU 0's
dynticks_progress_counterto 11.o CPU 1 is doing RCU grace-period processing in
rcu_try_flip_idle(),
seesrcu_pending(), so invokesdyntick_save_progress_counter(), which in turn takes a snapshot of CPU 0'sdynticks_progress_counterinto CPU 0'srcu_dyntick_snapshot-- now set to 11. CPU 1 then updates the RCU grace-period state torcu_try_flip_waitack().o CPU 0 returns from its interrupt, so
rcu_irq_exit()increments
CPU 0'sdynticks_progress_counterto 12.o CPU 1 later invokes
rcu_try_flip_waitack(), which notices that
CPU 0 has not yet responded, and hence in turn invokesrcu_try_flip_waitack_needed(). This function examines the state of CPU 0'sdynticks_progress_counterandrcu_dyntick_snapshotvariables, which it copies to curr (== 12) and snap (== 11), respectively.Because curr!=snap, the first condition fails.
Because curr-snap is only 1 and snap is odd, the second condition fails.
rcu_try_flip_waitack_needed()therefore incorrectly concludes that it must wait for CPU 0 to explicitly acknowledge the counter flip.o CPU 0 remains forever in dynticks-idle mode, never taking
any more hardware interrupts or any NMIs, and never running any more tasks. (Of course, -something- will usually eventually happen, which might be why we haven't seen this one in the wild. Still should be fixed!)Therefore the grace period never ends. Fix is to make the code match the comment, as shown below. With this fix, the above scenario would be satisfied with curr being even, and allow the grace period to proceed.
Signed-off-by Paul E. McKenney <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Ingo Molnar <[email protected]>Cc Josh Triplett <[email protected]>Cc Dipankar Sarma <[email protected]>Signed-off-by Andrew Morton <[email protected]>---
kernel/rcupreempt.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)diff -puN
kernel/rcupreempt.c~rcu-fix-rcu_try_flip_waitack_needed-to-prevent-grace-period-stallkernel/rcupreempt.ckernel/rcupreempt.c renamed from kernel/rcupreempt.c~rcu-fix-rcu_try_flip_waitack_needed-to-prevent-grace-period-stall +1
-1@@ -567,7 +567,7 @@ rcu_try_flip_waitack_needed(int cpu)* that this CPU already acknowledged the counter. */ -if ((curr - snap) >2 || (snap &0x1 ) ==0 ) +if ((curr - snap) >2 || (curr &0x1 ) ==0 )return 0 ;/* We need this CPU to explicitly acknowledge the counter flip. */ _