RCU flavor-consolidation changes for v4.20/v5.0

This commit also changes order of execution from this:

	rcu_dynticks_task_exit();
	rcu_dynticks_eqs_exit();
	trace_rcu_dyntick();
	rcu_cleanup_after_idle();

To this:

	rcu_dynticks_task_exit();
	rcu_dynticks_eqs_exit();
	rcu_cleanup_after_idle();
	trace_rcu_dyntick();

In other words, the calls to trace_rcu_dyntick() and trace_rcu_dyntick()

are reversed. This has no functional effect because the real concern is whether a given call is before or after the call to rcu_dynticks_eqs_exit(), and this patch does not change that. Before the call to rcu_dynticks_eqs_exit(), RCU is not yet watching the current CPU and after that call RCU is watching.

A similar switch in calling order happens on the idle-entry path, with similar lack of effect for the same reasons.

Suggested-by Paul E. McKenney <[email protected]>

Signed-off-by Byungchul Park <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree.c | 61 +++++++++++++++++++++++++++++++----------------
 1 file changed, 41 insertions(+), 20 deletions(-)

kernel/rcu/tree.c +1 -1

index 0b760c1369f7..0adf77923e8b 100644
@@ -771,17 +771,18 @@ void rcu_user_enter(void)
 #endif /* CONFIG_NO_HZ_FULL */
 
 /**
- * rcu_nmi_exit - inform RCU of exit from NMI context
+ * rcu_nmi_exit_common - inform RCU of exit from NMI context

kernel/rcu/tree.c +38 -18

  */
-void rcu_nmi_exit(void)
+static __always_inline void rcu_nmi_exit_common(bool irq)
 {
 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
 

@@ -807,7 +808,22 @@ void rcu_nmi_exit(void)
 	/* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */
 	trace_rcu_dyntick(TPS("Startirq"), rdtp->dynticks_nmi_nesting, 0, rdtp->dynticks);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, 0); /* Avoid store tearing. */
+
+	if (irq)
+		rcu_prepare_for_idle();
+
 	rcu_dynticks_eqs_enter();
+
+	if (irq)
+		rcu_dynticks_task_enter();
+}
+
+/**
+ * rcu_nmi_exit - inform RCU of exit from NMI context
+ */
+void rcu_nmi_exit(void)
+{
+	rcu_nmi_exit_common(false);
 }
 
 /**

@@ -831,14 +847,8 @@ void rcu_nmi_exit(void)
  */
 void rcu_irq_exit(void)
 {
-	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
-
 	lockdep_assert_irqs_disabled();
-	if (rdtp->dynticks_nmi_nesting == 1)
-		rcu_prepare_for_idle();
-	rcu_nmi_exit();
-	if (rdtp->dynticks_nmi_nesting == 0)
-		rcu_dynticks_task_enter();
+	rcu_nmi_exit_common(true);
 }
 
 /*

@@ -921,7 +931,8 @@ void rcu_user_exit(void)
 #endif /* CONFIG_NO_HZ_FULL */
 
 /**
- * rcu_nmi_enter - inform RCU of entry to NMI context
+ * rcu_nmi_enter_common - inform RCU of entry to NMI context
+ * @irq: Is this call from rcu_irq_enter?
  *
  * If the CPU was idle from RCU's viewpoint, update rdtp->dynticks and
  * rdtp->dynticks_nmi_nesting to let the RCU grace-period handling know

@@ -929,10 +940,10 @@ void rcu_user_exit(void)
  * long as the nesting level does not overflow an int.  (You will probably
  * run out of stack space first.)
  *
- * If you add or remove a call to rcu_nmi_enter(), be sure to test
+ * If you add or remove a call to rcu_nmi_enter_common(), be sure to test
  * with CONFIG_RCU_EQS_DEBUG=y.
  */
-void rcu_nmi_enter(void)
+static __always_inline void rcu_nmi_enter_common(bool irq)
 {
 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
 	long incby = 2;

@@ -949,7 +960,15 @@ void rcu_nmi_enter(void)
 	 * period (observation due to Andy Lutomirski).
 	 */
 	if (rcu_dynticks_curr_cpu_in_eqs()) {
+
+		if (irq)
+			rcu_dynticks_task_exit();
+
 		rcu_dynticks_eqs_exit();
+
+		if (irq)
+			rcu_cleanup_after_idle();
+
 		incby = 1;
 	}
 	trace_rcu_dyntick(incby == 1 ? TPS("Endirq") : TPS("++="),

@@ -960,6 +979,14 @@ void rcu_nmi_enter(void)
 	barrier();
 }
 
+/**
+ * rcu_nmi_enter - inform RCU of entry to NMI context
+ */
+void rcu_nmi_enter(void)
+{
+	rcu_nmi_enter_common(false);
+}
+
 /**
  * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle
  *

@@ -984,14 +1011,8 @@ void rcu_nmi_enter(void)
  */
 void rcu_irq_enter(void)
 {
-	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
-
 	lockdep_assert_irqs_disabled();
-	if (rdtp->dynticks_nmi_nesting == 0)
-		rcu_dynticks_task_exit();
-	rcu_nmi_enter();
-	if (rdtp->dynticks_nmi_nesting == 1)
-		rcu_cleanup_after_idle();
+	rcu_nmi_enter_common(true);
 }
 
 /*

Quoted 9 lines · On Wed, 29 Aug 2018 15:20:29 -0700 "Paul E. McKenney"…

This commit also changes order of execution from this:

	rcu_dynticks_task_exit();
	rcu_dynticks_eqs_exit();
	trace_rcu_dyntick();
	rcu_cleanup_after_idle();

To this:

Quoted 6 lines

	rcu_dynticks_task_exit();
	rcu_dynticks_eqs_exit();
	rcu_cleanup_after_idle();
	trace_rcu_dyntick();

In other words, the calls to trace_rcu_dyntick() and trace_rcu_dyntick()

How is trace_rcu_dyntick() and trace_rcu_dyntick reversed ? ;-)

Quoted 23 lines

are reversed. This has no functional effect because the real concern is whether a given call is before or after the call to rcu_dynticks_eqs_exit(), and this patch does not change that. Before the call to rcu_dynticks_eqs_exit(), RCU is not yet watching the current CPU and after that call RCU is watching.

A similar switch in calling order happens on the idle-entry path, with similar lack of effect for the same reasons.

Suggested-by Paul E. McKenney <[email protected]>

Signed-off-by Byungchul Park <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree.c | 61 +++++++++++++++++++++++++++++++----------------
 1 file changed, 41 insertions(+), 20 deletions(-)

kernel/rcu/tree.c +0 -0

index 0b760c1369f7..0adf77923e8b 100644
@@ -771,17 +771,18 @@ void rcu_user_enter(void)
 #endif /* CONFIG_NO_HZ_FULL */
 

kernel/rcu/tree.c void rcu_user_enter(void) · line 783

Quoted 13 lines

kernel/rcu/tree.c +3 -2

 /**
- * rcu_nmi_exit - inform RCU of exit from NMI context
+ * rcu_nmi_exit_common - inform RCU of exit from NMI context
+ * @irq: Is this call from rcu_irq_exit?
  *
  * If we are returning from the outermost NMI handler that interrupted an
  * RCU-idle period, update rdtp->dynticks and rdtp->dynticks_nmi_nesting
  * to let the RCU grace-period handling know that the CPU is back to
  * being RCU-idle.
  *
- * If you add or remove a call to rcu_nmi_exit(), be sure to test
+ * If you add or remove a call to rcu_nmi_exit_common(), be sure to test
  * with CONFIG_RCU_EQS_DEBUG=y.

As this is a static function, this description doesn't make sense. You need to move the description down to the new rcu_nmi_exit() below.

Other than that...

Reviewed-by Steven Rostedt (VMware) <[email protected]>

-- Steve

Quoted 115 lines

kernel/rcu/tree.c +38 -18

  */
-void rcu_nmi_exit(void)
+static __always_inline void rcu_nmi_exit_common(bool irq)
 {
 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
 

@@ -807,7 +808,22 @@ void rcu_nmi_exit(void)
 	/* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */
 	trace_rcu_dyntick(TPS("Startirq"), rdtp->dynticks_nmi_nesting, 0, rdtp->dynticks);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, 0); /* Avoid store tearing. */
+
+	if (irq)
+		rcu_prepare_for_idle();
+
 	rcu_dynticks_eqs_enter();
+
+	if (irq)
+		rcu_dynticks_task_enter();
+}
+
+/**
+ * rcu_nmi_exit - inform RCU of exit from NMI context
+ */
+void rcu_nmi_exit(void)
+{
+	rcu_nmi_exit_common(false);
 }
 
 /**

@@ -831,14 +847,8 @@ void rcu_nmi_exit(void)
  */
 void rcu_irq_exit(void)
 {
-	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
-
 	lockdep_assert_irqs_disabled();
-	if (rdtp->dynticks_nmi_nesting == 1)
-		rcu_prepare_for_idle();
-	rcu_nmi_exit();
-	if (rdtp->dynticks_nmi_nesting == 0)
-		rcu_dynticks_task_enter();
+	rcu_nmi_exit_common(true);
 }
 
 /*

@@ -921,7 +931,8 @@ void rcu_user_exit(void)
 #endif /* CONFIG_NO_HZ_FULL */
 
 /**
- * rcu_nmi_enter - inform RCU of entry to NMI context
+ * rcu_nmi_enter_common - inform RCU of entry to NMI context
+ * @irq: Is this call from rcu_irq_enter?
  *
  * If the CPU was idle from RCU's viewpoint, update rdtp->dynticks and
  * rdtp->dynticks_nmi_nesting to let the RCU grace-period handling know

@@ -929,10 +940,10 @@ void rcu_user_exit(void)
  * long as the nesting level does not overflow an int.  (You will probably
  * run out of stack space first.)
  *
- * If you add or remove a call to rcu_nmi_enter(), be sure to test
+ * If you add or remove a call to rcu_nmi_enter_common(), be sure to test
  * with CONFIG_RCU_EQS_DEBUG=y.
  */
-void rcu_nmi_enter(void)
+static __always_inline void rcu_nmi_enter_common(bool irq)
 {
 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
 	long incby = 2;

@@ -949,7 +960,15 @@ void rcu_nmi_enter(void)
 	 * period (observation due to Andy Lutomirski).
 	 */
 	if (rcu_dynticks_curr_cpu_in_eqs()) {
+
+		if (irq)
+			rcu_dynticks_task_exit();
+
 		rcu_dynticks_eqs_exit();
+
+		if (irq)
+			rcu_cleanup_after_idle();
+
 		incby = 1;
 	}
 	trace_rcu_dyntick(incby == 1 ? TPS("Endirq") : TPS("++="),

@@ -960,6 +979,14 @@ void rcu_nmi_enter(void)
 	barrier();
 }
 
+/**
+ * rcu_nmi_enter - inform RCU of entry to NMI context
+ */
+void rcu_nmi_enter(void)
+{
+	rcu_nmi_enter_common(false);
+}
+
 /**
  * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle
  *

@@ -984,14 +1011,8 @@ void rcu_nmi_enter(void)
  */
 void rcu_irq_enter(void)
 {
-	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
-
 	lockdep_assert_irqs_disabled();
-	if (rdtp->dynticks_nmi_nesting == 0)
-		rcu_dynticks_task_exit();
-	rcu_nmi_enter();
-	if (rdtp->dynticks_nmi_nesting == 1)
-		rcu_cleanup_after_idle();
+	rcu_nmi_enter_common(true);
 }
 
 /*

Quoted 7 lines · On Wed, 29 Aug 2018 15:20:29 -0700 "Paul E. McKenney"…

This commit also changes order of execution from this:

	rcu_dynticks_task_exit();
	rcu_dynticks_eqs_exit();
	trace_rcu_dyntick();
	rcu_cleanup_after_idle();

Quoted 8 lines

To this:

	rcu_dynticks_task_exit();
	rcu_dynticks_eqs_exit();
	rcu_cleanup_after_idle();
	trace_rcu_dyntick();

In other words, the calls to trace_rcu_dyntick() and trace_rcu_dyntick()

How is trace_rcu_dyntick() and trace_rcu_dyntick reversed ? ;-)

Quoted 23 lines

are reversed. This has no functional effect because the real concern is whether a given call is before or after the call to rcu_dynticks_eqs_exit(), and this patch does not change that. Before the call to rcu_dynticks_eqs_exit(), RCU is not yet watching the current CPU and after that call RCU is watching.

A similar switch in calling order happens on the idle-entry path, with similar lack of effect for the same reasons.

Suggested-by Paul E. McKenney <[email protected]>

Signed-off-by Byungchul Park <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree.c | 61 +++++++++++++++++++++++++++++++----------------
 1 file changed, 41 insertions(+), 20 deletions(-)

kernel/rcu/tree.c +0 -0

index 0b760c1369f7..0adf77923e8b 100644
@@ -771,17 +771,18 @@ void rcu_user_enter(void)
 #endif /* CONFIG_NO_HZ_FULL */
 

kernel/rcu/tree.c void rcu_user_enter(void) · line 783

Quoted 13 lines

kernel/rcu/tree.c +3 -2

 /**
- * rcu_nmi_exit - inform RCU of exit from NMI context
+ * rcu_nmi_exit_common - inform RCU of exit from NMI context
+ * @irq: Is this call from rcu_irq_exit?
  *
  * If we are returning from the outermost NMI handler that interrupted an
  * RCU-idle period, update rdtp->dynticks and rdtp->dynticks_nmi_nesting
  * to let the RCU grace-period handling know that the CPU is back to
  * being RCU-idle.
  *
- * If you add or remove a call to rcu_nmi_exit(), be sure to test
+ * If you add or remove a call to rcu_nmi_exit_common(), be sure to test
  * with CONFIG_RCU_EQS_DEBUG=y.

As this is a static function, this description doesn't make sense. You need to move the description down to the new rcu_nmi_exit() below.

Other than that...

Reviewed-by Steven Rostedt (VMware) <[email protected]>

-- Steve

Quoted 115 lines

kernel/rcu/tree.c +38 -18

  */
-void rcu_nmi_exit(void)
+static __always_inline void rcu_nmi_exit_common(bool irq)
 {
 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
 

@@ -807,7 +808,22 @@ void rcu_nmi_exit(void)
 	/* This NMI interrupted an RCU-idle CPU, restore RCU-idleness. */
 	trace_rcu_dyntick(TPS("Startirq"), rdtp->dynticks_nmi_nesting, 0, rdtp->dynticks);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, 0); /* Avoid store tearing. */
+
+	if (irq)
+		rcu_prepare_for_idle();
+
 	rcu_dynticks_eqs_enter();
+
+	if (irq)
+		rcu_dynticks_task_enter();
+}
+
+/**
+ * rcu_nmi_exit - inform RCU of exit from NMI context
+ */
+void rcu_nmi_exit(void)
+{
+	rcu_nmi_exit_common(false);
 }
 
 /**

@@ -831,14 +847,8 @@ void rcu_nmi_exit(void)
  */
 void rcu_irq_exit(void)
 {
-	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
-
 	lockdep_assert_irqs_disabled();
-	if (rdtp->dynticks_nmi_nesting == 1)
-		rcu_prepare_for_idle();
-	rcu_nmi_exit();
-	if (rdtp->dynticks_nmi_nesting == 0)
-		rcu_dynticks_task_enter();
+	rcu_nmi_exit_common(true);
 }
 
 /*

@@ -921,7 +931,8 @@ void rcu_user_exit(void)
 #endif /* CONFIG_NO_HZ_FULL */
 
 /**
- * rcu_nmi_enter - inform RCU of entry to NMI context
+ * rcu_nmi_enter_common - inform RCU of entry to NMI context
+ * @irq: Is this call from rcu_irq_enter?
  *
  * If the CPU was idle from RCU's viewpoint, update rdtp->dynticks and
  * rdtp->dynticks_nmi_nesting to let the RCU grace-period handling know

@@ -929,10 +940,10 @@ void rcu_user_exit(void)
  * long as the nesting level does not overflow an int.  (You will probably
  * run out of stack space first.)
  *
- * If you add or remove a call to rcu_nmi_enter(), be sure to test
+ * If you add or remove a call to rcu_nmi_enter_common(), be sure to test
  * with CONFIG_RCU_EQS_DEBUG=y.
  */
-void rcu_nmi_enter(void)
+static __always_inline void rcu_nmi_enter_common(bool irq)
 {
 	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
 	long incby = 2;

@@ -949,7 +960,15 @@ void rcu_nmi_enter(void)
 	 * period (observation due to Andy Lutomirski).
 	 */
 	if (rcu_dynticks_curr_cpu_in_eqs()) {
+
+		if (irq)
+			rcu_dynticks_task_exit();
+
 		rcu_dynticks_eqs_exit();
+
+		if (irq)
+			rcu_cleanup_after_idle();
+
 		incby = 1;
 	}
 	trace_rcu_dyntick(incby == 1 ? TPS("Endirq") : TPS("++="),

@@ -960,6 +979,14 @@ void rcu_nmi_enter(void)
 	barrier();
 }
 
+/**
+ * rcu_nmi_enter - inform RCU of entry to NMI context
+ */
+void rcu_nmi_enter(void)
+{
+	rcu_nmi_enter_common(false);
+}
+
 /**
  * rcu_irq_enter - inform RCU that current CPU is entering irq away from idle
  *

@@ -984,14 +1011,8 @@ void rcu_nmi_enter(void)
  */
 void rcu_irq_enter(void)
 {
-	struct rcu_dynticks *rdtp = this_cpu_ptr(&rcu_dynticks);
-
 	lockdep_assert_irqs_disabled();
-	if (rdtp->dynticks_nmi_nesting == 0)
-		rcu_dynticks_task_exit();
-	rcu_nmi_enter();
-	if (rdtp->dynticks_nmi_nesting == 1)
-		rcu_cleanup_after_idle();
+	rcu_nmi_enter_common(true);
 }
 
 /*

-----Original Message-----
From: [email protected] [mailto:linux-kernel- [email protected]] On Behalf Of Paul E. McKenney
Sent: Thursday, August 30, 2018 01:21
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Paul E. McKenney <[email protected]>
Subject: [PATCH tip/core/rcu 02/19] rcu: Defer reporting RCU-preempt quiescent states when disabled

This commit defers reporting of RCU-preempt quiescent states at rcu_read_unlock_special() time when any of interrupts, softirq, or preemption are disabled. These deferred quiescent states are reported at a later RCU_SOFTIRQ, context switch, idle entry, or CPU-hotplug offline operation. Of course, if another RCU read-side critical section has started in the meantime, the reporting of the quiescent state will be further deferred.

This also means that disabling preemption, interrupts, and/or softirqs will act as an RCU-preempt read-side critical section.
This is enforced by checking preempt_count() as needed.

Some special cases must be handled on an ad-hoc basis, for example, context switch is a quiescent state even though both the scheduler and do_exit() disable preemption. In these cases, additional calls to rcu_preempt_deferred_qs() override the preemption disabling. Similar logic overrides disabled interrupts in rcu_preempt_check_callbacks() because in this case the quiescent state happened just before the corresponding scheduling-clock interrupt.

In theory, this change lifts a long-standing restriction that required that if interrupts were disabled across a call to rcu_read_unlock() that the matching rcu_read_lock() also be contained within that interrupts-disabled region of code. Because the reporting of the corresponding RCU-preempt quiescent state is now deferred until after interrupts have been enabled, it is no longer possible for this situation to result in deadlocks involving the scheduler's runqueue and priority-inheritance locks. This may allow some code simplification that might reduce interrupt latency a bit. Unfortunately, in practice this would also defer deboosting a low-priority task that had been subjected to RCU priority boosting, so real-time-response considerations might well force this restriction to remain in place.

Because RCU-preempt grace periods are now blocked not only by RCU read- side critical sections, but also by disabling of interrupts, preemption, and softirqs, it will be possible to eliminate RCU-bh and RCU-sched in favor of RCU-preempt in CONFIG_PREEMPT=y kernels. This may require some additional plumbing to provide the network denial-of-service guarantees that have been traditionally provided by RCU-bh. Once these are in place, CONFIG_PREEMPT=n kernels will be able to fold RCU-bh into RCU-sched. This would mean that all kernels would have but one flavor of RCU, which would open the door to significant code cleanup.

Moving to a single flavor of RCU would also have the beneficial effect of reducing the NOCB kthreads by at least a factor of two.

Signed-off-by Paul E. McKenney <[email protected]> [ paulmck:

Apply rcu_read_unlock_special() preempt_count() feedback
from Joel Fernandes. ]
[ paulmck: Adjust rcu_eqs_enter() call to rcu_preempt_deferred_qs() in
response to bug reports from kbuild test robot. ] [ paulmck: Fix bug located
by kbuild test robot involving recursion
via rcu_preempt_deferred_qs(). ]

---
 .../RCU/Design/Requirements/Requirements.html |  50 +++---
 include/linux/rcutiny.h                       |   5 +
 kernel/rcu/tree.c                             |   9 ++
 kernel/rcu/tree.h                             |   3 +
 kernel/rcu/tree_exp.h                         |  71 +++++++--
 kernel/rcu/tree_plugin.h                      | 144 +++++++++++++-----
 6 files changed, 205 insertions(+), 77 deletions(-)

Hi Paul and all,

Quoted 65 lines

-----Original Message-----
From: [email protected] [mailto:linux-kernel- [email protected]] On Behalf Of Paul E. McKenney
Sent: Thursday, August 30, 2018 01:21
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Paul E. McKenney <[email protected]>
Subject: [PATCH tip/core/rcu 02/19] rcu: Defer reporting RCU-preempt quiescent states when disabled

This commit defers reporting of RCU-preempt quiescent states at rcu_read_unlock_special() time when any of interrupts, softirq, or preemption are disabled. These deferred quiescent states are reported at a later RCU_SOFTIRQ, context switch, idle entry, or CPU-hotplug offline operation. Of course, if another RCU read-side critical section has started in the meantime, the reporting of the quiescent state will be further deferred.

This also means that disabling preemption, interrupts, and/or softirqs will act as an RCU-preempt read-side critical section.
This is enforced by checking preempt_count() as needed.

Some special cases must be handled on an ad-hoc basis, for example, context switch is a quiescent state even though both the scheduler and do_exit() disable preemption. In these cases, additional calls to rcu_preempt_deferred_qs() override the preemption disabling. Similar logic overrides disabled interrupts in rcu_preempt_check_callbacks() because in this case the quiescent state happened just before the corresponding scheduling-clock interrupt.

In theory, this change lifts a long-standing restriction that required that if interrupts were disabled across a call to rcu_read_unlock() that the matching rcu_read_lock() also be contained within that interrupts-disabled region of code. Because the reporting of the corresponding RCU-preempt quiescent state is now deferred until after interrupts have been enabled, it is no longer possible for this situation to result in deadlocks involving the scheduler's runqueue and priority-inheritance locks. This may allow some code simplification that might reduce interrupt latency a bit. Unfortunately, in practice this would also defer deboosting a low-priority task that had been subjected to RCU priority boosting, so real-time-response considerations might well force this restriction to remain in place.

Because RCU-preempt grace periods are now blocked not only by RCU read- side critical sections, but also by disabling of interrupts, preemption, and softirqs, it will be possible to eliminate RCU-bh and RCU-sched in favor of RCU-preempt in CONFIG_PREEMPT=y kernels. This may require some additional plumbing to provide the network denial-of-service guarantees that have been traditionally provided by RCU-bh. Once these are in place, CONFIG_PREEMPT=n kernels will be able to fold RCU-bh into RCU-sched. This would mean that all kernels would have but one flavor of RCU, which would open the door to significant code cleanup.

Moving to a single flavor of RCU would also have the beneficial effect of reducing the NOCB kthreads by at least a factor of two.

Signed-off-by Paul E. McKenney <[email protected]> [ paulmck:

Apply rcu_read_unlock_special() preempt_count() feedback
from Joel Fernandes. ]
[ paulmck: Adjust rcu_eqs_enter() call to rcu_preempt_deferred_qs() in
response to bug reports from kbuild test robot. ] [ paulmck: Fix bug located
by kbuild test robot involving recursion
via rcu_preempt_deferred_qs(). ]

Quoted 9 lines

---
 .../RCU/Design/Requirements/Requirements.html |  50 +++---
 include/linux/rcutiny.h                       |   5 +
 kernel/rcu/tree.c                             |   9 ++
 kernel/rcu/tree.h                             |   3 +
 kernel/rcu/tree_exp.h                         |  71 +++++++--
 kernel/rcu/tree_plugin.h                      | 144 +++++++++++++-----
 6 files changed, 205 insertions(+), 77 deletions(-)

We started seeing the trace below in our regression system, after I bisected I found this is the offending commit. This appears immediately on boot.
Please let me know if you need any additional details.

Quoted 77 lines · Ran Rozenstein

Hi Paul and all,

Quoted 65 lines

-----Original Message-----
From: [email protected] [mailto:linux-kernel- [email protected]] On Behalf Of Paul E. McKenney
Sent: Thursday, August 30, 2018 01:21
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Paul E. McKenney <[email protected]>
Subject: [PATCH tip/core/rcu 02/19] rcu: Defer reporting RCU-preempt quiescent states when disabled

This commit defers reporting of RCU-preempt quiescent states at rcu_read_unlock_special() time when any of interrupts, softirq, or preemption are disabled. These deferred quiescent states are reported at a later RCU_SOFTIRQ, context switch, idle entry, or CPU-hotplug offline operation. Of course, if another RCU read-side critical section has started in the meantime, the reporting of the quiescent state will be further deferred.

This also means that disabling preemption, interrupts, and/or softirqs will act as an RCU-preempt read-side critical section.
This is enforced by checking preempt_count() as needed.

Some special cases must be handled on an ad-hoc basis, for example, context switch is a quiescent state even though both the scheduler and do_exit() disable preemption. In these cases, additional calls to rcu_preempt_deferred_qs() override the preemption disabling. Similar logic overrides disabled interrupts in rcu_preempt_check_callbacks() because in this case the quiescent state happened just before the corresponding scheduling-clock interrupt.

In theory, this change lifts a long-standing restriction that required that if interrupts were disabled across a call to rcu_read_unlock() that the matching rcu_read_lock() also be contained within that interrupts-disabled region of code. Because the reporting of the corresponding RCU-preempt quiescent state is now deferred until after interrupts have been enabled, it is no longer possible for this situation to result in deadlocks involving the scheduler's runqueue and priority-inheritance locks. This may allow some code simplification that might reduce interrupt latency a bit. Unfortunately, in practice this would also defer deboosting a low-priority task that had been subjected to RCU priority boosting, so real-time-response considerations might well force this restriction to remain in place.

Because RCU-preempt grace periods are now blocked not only by RCU read- side critical sections, but also by disabling of interrupts, preemption, and softirqs, it will be possible to eliminate RCU-bh and RCU-sched in favor of RCU-preempt in CONFIG_PREEMPT=y kernels. This may require some additional plumbing to provide the network denial-of-service guarantees that have been traditionally provided by RCU-bh. Once these are in place, CONFIG_PREEMPT=n kernels will be able to fold RCU-bh into RCU-sched. This would mean that all kernels would have but one flavor of RCU, which would open the door to significant code cleanup.

Moving to a single flavor of RCU would also have the beneficial effect of reducing the NOCB kthreads by at least a factor of two.

Signed-off-by Paul E. McKenney <[email protected]> [ paulmck:

Apply rcu_read_unlock_special() preempt_count() feedback
from Joel Fernandes. ]
[ paulmck: Adjust rcu_eqs_enter() call to rcu_preempt_deferred_qs() in
response to bug reports from kbuild test robot. ] [ paulmck: Fix bug located
by kbuild test robot involving recursion
via rcu_preempt_deferred_qs(). ]

Quoted 9 lines

---
 .../RCU/Design/Requirements/Requirements.html |  50 +++---
 include/linux/rcutiny.h                       |   5 +
 kernel/rcu/tree.c                             |   9 ++
 kernel/rcu/tree.h                             |   3 +
 kernel/rcu/tree_exp.h                         |  71 +++++++--
 kernel/rcu/tree_plugin.h                      | 144 +++++++++++++-----
 6 files changed, 205 insertions(+), 77 deletions(-)

Quoted 3 lines

We started seeing the trace below in our regression system, after I bisected I found this is the offending commit. This appears immediately on boot.
Please let me know if you need any additional details.

Interesting. Here is the offending function:

	static void rcu_preempt_deferred_qs(struct task_struct *t)
	{
		unsigned long flags;
		bool couldrecurse = t->rcu_read_lock_nesting >= 0;

		if (!rcu_preempt_need_deferred_qs(t))
			return;
		if (couldrecurse)
			t->rcu_read_lock_nesting -= INT_MIN;
		local_irq_save(flags);
		rcu_preempt_deferred_qs_irqrestore(t, flags);
		if (couldrecurse)
			t->rcu_read_lock_nesting += INT_MIN;
	}

Using twos-complement arithmetic (which the kernel build gcc arguments enforce, last I checked) this does work. But as UBSAN says, subtracting INT_MIN is unconditionally undefined behavior according to the C standard.

Good catch!!!

So how do I make the above code not simply function, but rather meet the C standard?

One approach to add INT_MIN going in, then add INT_MAX and then add 1 coming out.

Another approach is to sacrifice the INT_MAX value (should be plenty safe), thus subtract INT_MAX going in and add INT_MAX coming out. For consistency, I suppose that I should change the INT_MIN in __rcu_read_unlock() to -INT_MAX.

I could also leave __rcu_read_unlock() alone and XOR the top bit of t->rcu_read_lock_nesting on entry and exit to/from rcu_preempt_deferred_qs().

Sacrificing the INT_MIN value seems most maintainable, as in the following patch. Thoughts?

------------------------------------------------------------------------

kernel/rcu/tree_plugin.h +1 -1

index bd8186d0f4a7..f1b40c6d36e4 100644
@@ -424,7 +424,7 @@ void __rcu_read_unlock(void)
 		--t->rcu_read_lock_nesting;
 	} else {
 		barrier();  /* critical section before exit code. */
-		t->rcu_read_lock_nesting = INT_MIN;
+		t->rcu_read_lock_nesting = -INT_MAX;
 		barrier();  /* assign before ->rcu_read_unlock_special load */
 		if (unlikely(READ_ONCE(t->rcu_read_unlock_special.s)))
 			rcu_read_unlock_special(t);

Quoted 116 lines · Paul E. McKenney

Quoted 77 lines · Ran Rozenstein

Hi Paul and all,

Quoted 65 lines

-----Original Message-----
From: [email protected] [mailto:linux-kernel- [email protected]] On Behalf Of Paul E. McKenney
Sent: Thursday, August 30, 2018 01:21
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Paul E. McKenney <[email protected]>
Subject: [PATCH tip/core/rcu 02/19] rcu: Defer reporting RCU-preempt quiescent states when disabled

This commit defers reporting of RCU-preempt quiescent states at rcu_read_unlock_special() time when any of interrupts, softirq, or preemption are disabled. These deferred quiescent states are reported at a later RCU_SOFTIRQ, context switch, idle entry, or CPU-hotplug offline operation. Of course, if another RCU read-side critical section has started in the meantime, the reporting of the quiescent state will be further deferred.

This also means that disabling preemption, interrupts, and/or softirqs will act as an RCU-preempt read-side critical section.
This is enforced by checking preempt_count() as needed.

Some special cases must be handled on an ad-hoc basis, for example, context switch is a quiescent state even though both the scheduler and do_exit() disable preemption. In these cases, additional calls to rcu_preempt_deferred_qs() override the preemption disabling. Similar logic overrides disabled interrupts in rcu_preempt_check_callbacks() because in this case the quiescent state happened just before the corresponding scheduling-clock interrupt.

In theory, this change lifts a long-standing restriction that required that if interrupts were disabled across a call to rcu_read_unlock() that the matching rcu_read_lock() also be contained within that interrupts-disabled region of code. Because the reporting of the corresponding RCU-preempt quiescent state is now deferred until after interrupts have been enabled, it is no longer possible for this situation to result in deadlocks involving the scheduler's runqueue and priority-inheritance locks. This may allow some code simplification that might reduce interrupt latency a bit. Unfortunately, in practice this would also defer deboosting a low-priority task that had been subjected to RCU priority boosting, so real-time-response considerations might well force this restriction to remain in place.

Because RCU-preempt grace periods are now blocked not only by RCU read- side critical sections, but also by disabling of interrupts, preemption, and softirqs, it will be possible to eliminate RCU-bh and RCU-sched in favor of RCU-preempt in CONFIG_PREEMPT=y kernels. This may require some additional plumbing to provide the network denial-of-service guarantees that have been traditionally provided by RCU-bh. Once these are in place, CONFIG_PREEMPT=n kernels will be able to fold RCU-bh into RCU-sched. This would mean that all kernels would have but one flavor of RCU, which would open the door to significant code cleanup.

Moving to a single flavor of RCU would also have the beneficial effect of reducing the NOCB kthreads by at least a factor of two.

Signed-off-by Paul E. McKenney <[email protected]> [ paulmck:

Apply rcu_read_unlock_special() preempt_count() feedback
from Joel Fernandes. ]
[ paulmck: Adjust rcu_eqs_enter() call to rcu_preempt_deferred_qs() in
response to bug reports from kbuild test robot. ] [ paulmck: Fix bug located
by kbuild test robot involving recursion
via rcu_preempt_deferred_qs(). ]

Quoted 9 lines

---
 .../RCU/Design/Requirements/Requirements.html |  50 +++---
 include/linux/rcutiny.h                       |   5 +
 kernel/rcu/tree.c                             |   9 ++
 kernel/rcu/tree.h                             |   3 +
 kernel/rcu/tree_exp.h                         |  71 +++++++--
 kernel/rcu/tree_plugin.h                      | 144 +++++++++++++-----
 6 files changed, 205 insertions(+), 77 deletions(-)

Quoted 3 lines

We started seeing the trace below in our regression system, after I bisected I found this is the offending commit. This appears immediately on boot.
Please let me know if you need any additional details.

Interesting. Here is the offending function:

	static void rcu_preempt_deferred_qs(struct task_struct *t)
	{
		unsigned long flags;
		bool couldrecurse = t->rcu_read_lock_nesting >= 0;

		if (!rcu_preempt_need_deferred_qs(t))
			return;
		if (couldrecurse)
			t->rcu_read_lock_nesting -= INT_MIN;
		local_irq_save(flags);
		rcu_preempt_deferred_qs_irqrestore(t, flags);
		if (couldrecurse)
			t->rcu_read_lock_nesting += INT_MIN;
	}

Using twos-complement arithmetic (which the kernel build gcc arguments enforce, last I checked) this does work. But as UBSAN says, subtracting INT_MIN is unconditionally undefined behavior according to the C standard.

Good catch!!!

So how do I make the above code not simply function, but rather meet the C standard?

One approach to add INT_MIN going in, then add INT_MAX and then add 1 coming out.

Another approach is to sacrifice the INT_MAX value (should be plenty safe), thus subtract INT_MAX going in and add INT_MAX coming out. For consistency, I suppose that I should change the INT_MIN in __rcu_read_unlock() to -INT_MAX.

Quoted 6 lines

I could also leave __rcu_read_unlock() alone and XOR the top bit of t->rcu_read_lock_nesting on entry and exit to/from rcu_preempt_deferred_qs().

Sacrificing the INT_MIN value seems most maintainable, as in the following patch. Thoughts?

The INT_MAX naming could be very confusing for nesting levels, could we not instead just define something like:
#define RCU_NESTING_MIN (INT_MIN - 1)
#define RCU_NESTING_MAX (INT_MAX)

and just use that? also one more comment below:

Quoted 15 lines

------------------------------------------------------------------------

kernel/rcu/tree_plugin.h +1 -1

index bd8186d0f4a7..f1b40c6d36e4 100644
@@ -424,7 +424,7 @@ void __rcu_read_unlock(void)
 		--t->rcu_read_lock_nesting;
 	} else {
 		barrier();  /* critical section before exit code. */
-		t->rcu_read_lock_nesting = INT_MIN;
+		t->rcu_read_lock_nesting = -INT_MAX;
 		barrier();  /* assign before ->rcu_read_unlock_special load */
 		if (unlikely(READ_ONCE(t->rcu_read_unlock_special.s)))
 			rcu_read_unlock_special(t);

kernel/rcu/tree_plugin.h static void rcu_preempt_deferred_qs(struct task_struct *t) · line 620

Quoted 6 lines

kernel/rcu/tree_plugin.h +1 -1

@@ -617,11 +617,11 @@ static void rcu_preempt_deferred_qs(struct task_struct *t)
 	if (!rcu_preempt_need_deferred_qs(t))
 		return;
 	if (couldrecurse)
-		t->rcu_read_lock_nesting -= INT_MIN;
+		t->rcu_read_lock_nesting -= INT_MAX;

Shouldn't this be: t->rcu_read_lock_nesting -= -INT_MAX; ?

kernel/rcu/tree_plugin.h static void rcu_preempt_deferred_qs(struct task_struct *t) · line 624

Quoted 5 lines

kernel/rcu/tree_plugin.h +1 -1

 	local_irq_save(flags);
 	rcu_preempt_deferred_qs_irqrestore(t, flags);
 	if (couldrecurse)
-		t->rcu_read_lock_nesting += INT_MIN;
+		t->rcu_read_lock_nesting += INT_MAX;

And t->rcu_read_lock_nesting += -INT_MAX; ?

But apologies if I missed something, thanks,

Quoted 124 lines · Joel Fernandes

Quoted 116 lines · Paul E. McKenney

Quoted 77 lines · Ran Rozenstein

Hi Paul and all,

Quoted 65 lines

-----Original Message-----
From: [email protected] [mailto:linux-kernel- [email protected]] On Behalf Of Paul E. McKenney
Sent: Thursday, August 30, 2018 01:21
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Paul E. McKenney <[email protected]>
Subject: [PATCH tip/core/rcu 02/19] rcu: Defer reporting RCU-preempt quiescent states when disabled

This commit defers reporting of RCU-preempt quiescent states at rcu_read_unlock_special() time when any of interrupts, softirq, or preemption are disabled. These deferred quiescent states are reported at a later RCU_SOFTIRQ, context switch, idle entry, or CPU-hotplug offline operation. Of course, if another RCU read-side critical section has started in the meantime, the reporting of the quiescent state will be further deferred.

This also means that disabling preemption, interrupts, and/or softirqs will act as an RCU-preempt read-side critical section.
This is enforced by checking preempt_count() as needed.

Some special cases must be handled on an ad-hoc basis, for example, context switch is a quiescent state even though both the scheduler and do_exit() disable preemption. In these cases, additional calls to rcu_preempt_deferred_qs() override the preemption disabling. Similar logic overrides disabled interrupts in rcu_preempt_check_callbacks() because in this case the quiescent state happened just before the corresponding scheduling-clock interrupt.

In theory, this change lifts a long-standing restriction that required that if interrupts were disabled across a call to rcu_read_unlock() that the matching rcu_read_lock() also be contained within that interrupts-disabled region of code. Because the reporting of the corresponding RCU-preempt quiescent state is now deferred until after interrupts have been enabled, it is no longer possible for this situation to result in deadlocks involving the scheduler's runqueue and priority-inheritance locks. This may allow some code simplification that might reduce interrupt latency a bit. Unfortunately, in practice this would also defer deboosting a low-priority task that had been subjected to RCU priority boosting, so real-time-response considerations might well force this restriction to remain in place.

Because RCU-preempt grace periods are now blocked not only by RCU read- side critical sections, but also by disabling of interrupts, preemption, and softirqs, it will be possible to eliminate RCU-bh and RCU-sched in favor of RCU-preempt in CONFIG_PREEMPT=y kernels. This may require some additional plumbing to provide the network denial-of-service guarantees that have been traditionally provided by RCU-bh. Once these are in place, CONFIG_PREEMPT=n kernels will be able to fold RCU-bh into RCU-sched. This would mean that all kernels would have but one flavor of RCU, which would open the door to significant code cleanup.

Moving to a single flavor of RCU would also have the beneficial effect of reducing the NOCB kthreads by at least a factor of two.

Signed-off-by Paul E. McKenney <[email protected]> [ paulmck:

Apply rcu_read_unlock_special() preempt_count() feedback
from Joel Fernandes. ]
[ paulmck: Adjust rcu_eqs_enter() call to rcu_preempt_deferred_qs() in
response to bug reports from kbuild test robot. ] [ paulmck: Fix bug located
by kbuild test robot involving recursion
via rcu_preempt_deferred_qs(). ]

Quoted 9 lines

---
 .../RCU/Design/Requirements/Requirements.html |  50 +++---
 include/linux/rcutiny.h                       |   5 +
 kernel/rcu/tree.c                             |   9 ++
 kernel/rcu/tree.h                             |   3 +
 kernel/rcu/tree_exp.h                         |  71 +++++++--
 kernel/rcu/tree_plugin.h                      | 144 +++++++++++++-----
 6 files changed, 205 insertions(+), 77 deletions(-)

Quoted 3 lines

We started seeing the trace below in our regression system, after I bisected I found this is the offending commit. This appears immediately on boot.
Please let me know if you need any additional details.

Interesting. Here is the offending function:

	static void rcu_preempt_deferred_qs(struct task_struct *t)
	{
		unsigned long flags;
		bool couldrecurse = t->rcu_read_lock_nesting >= 0;

		if (!rcu_preempt_need_deferred_qs(t))
			return;
		if (couldrecurse)
			t->rcu_read_lock_nesting -= INT_MIN;
		local_irq_save(flags);
		rcu_preempt_deferred_qs_irqrestore(t, flags);
		if (couldrecurse)
			t->rcu_read_lock_nesting += INT_MIN;
	}

Using twos-complement arithmetic (which the kernel build gcc arguments enforce, last I checked) this does work. But as UBSAN says, subtracting INT_MIN is unconditionally undefined behavior according to the C standard.

Good catch!!!

So how do I make the above code not simply function, but rather meet the C standard?

One approach to add INT_MIN going in, then add INT_MAX and then add 1 coming out.

Another approach is to sacrifice the INT_MAX value (should be plenty safe), thus subtract INT_MAX going in and add INT_MAX coming out. For consistency, I suppose that I should change the INT_MIN in __rcu_read_unlock() to -INT_MAX.

Quoted 6 lines

I could also leave __rcu_read_unlock() alone and XOR the top bit of t->rcu_read_lock_nesting on entry and exit to/from rcu_preempt_deferred_qs().

Sacrificing the INT_MIN value seems most maintainable, as in the following patch. Thoughts?

Quoted 6 lines

The INT_MAX naming could be very confusing for nesting levels, could we not instead just define something like:
#define RCU_NESTING_MIN (INT_MIN - 1)
#define RCU_NESTING_MAX (INT_MAX)

and just use that? also one more comment below:

Hmmm... There is currently no use for RCU_NESTING_MAX, but if the check at the end of __rcu_read_unlock() were to be extended to check for too-deep positive nesting, it would need to check for something like INT_MAX/2. You could of course argue that the current check against INT_MIN/2 should instead be against -INT_MAX/2, but there really isn't much difference between the two.

Another approach would be to convert to unsigned in order to avoid the overflow problem completely.

For the moment, anyway, I am inclined to leave it as is.

Quoted 139 lines · Paul E. McKenney

Quoted 124 lines · Joel Fernandes

Quoted 116 lines · Paul E. McKenney

Quoted 77 lines · Ran Rozenstein

Hi Paul and all,

Quoted 65 lines

-----Original Message-----
From: [email protected] [mailto:linux-kernel- [email protected]] On Behalf Of Paul E. McKenney
Sent: Thursday, August 30, 2018 01:21
To: [email protected]
Cc: [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; [email protected]; Paul E. McKenney <[email protected]>
Subject: [PATCH tip/core/rcu 02/19] rcu: Defer reporting RCU-preempt quiescent states when disabled

This commit defers reporting of RCU-preempt quiescent states at rcu_read_unlock_special() time when any of interrupts, softirq, or preemption are disabled. These deferred quiescent states are reported at a later RCU_SOFTIRQ, context switch, idle entry, or CPU-hotplug offline operation. Of course, if another RCU read-side critical section has started in the meantime, the reporting of the quiescent state will be further deferred.

This also means that disabling preemption, interrupts, and/or softirqs will act as an RCU-preempt read-side critical section.
This is enforced by checking preempt_count() as needed.

Some special cases must be handled on an ad-hoc basis, for example, context switch is a quiescent state even though both the scheduler and do_exit() disable preemption. In these cases, additional calls to rcu_preempt_deferred_qs() override the preemption disabling. Similar logic overrides disabled interrupts in rcu_preempt_check_callbacks() because in this case the quiescent state happened just before the corresponding scheduling-clock interrupt.

In theory, this change lifts a long-standing restriction that required that if interrupts were disabled across a call to rcu_read_unlock() that the matching rcu_read_lock() also be contained within that interrupts-disabled region of code. Because the reporting of the corresponding RCU-preempt quiescent state is now deferred until after interrupts have been enabled, it is no longer possible for this situation to result in deadlocks involving the scheduler's runqueue and priority-inheritance locks. This may allow some code simplification that might reduce interrupt latency a bit. Unfortunately, in practice this would also defer deboosting a low-priority task that had been subjected to RCU priority boosting, so real-time-response considerations might well force this restriction to remain in place.

Because RCU-preempt grace periods are now blocked not only by RCU read- side critical sections, but also by disabling of interrupts, preemption, and softirqs, it will be possible to eliminate RCU-bh and RCU-sched in favor of RCU-preempt in CONFIG_PREEMPT=y kernels. This may require some additional plumbing to provide the network denial-of-service guarantees that have been traditionally provided by RCU-bh. Once these are in place, CONFIG_PREEMPT=n kernels will be able to fold RCU-bh into RCU-sched. This would mean that all kernels would have but one flavor of RCU, which would open the door to significant code cleanup.

Moving to a single flavor of RCU would also have the beneficial effect of reducing the NOCB kthreads by at least a factor of two.

Signed-off-by Paul E. McKenney <[email protected]> [ paulmck:

Apply rcu_read_unlock_special() preempt_count() feedback
from Joel Fernandes. ]
[ paulmck: Adjust rcu_eqs_enter() call to rcu_preempt_deferred_qs() in
response to bug reports from kbuild test robot. ] [ paulmck: Fix bug located
by kbuild test robot involving recursion
via rcu_preempt_deferred_qs(). ]

Quoted 9 lines

---
 .../RCU/Design/Requirements/Requirements.html |  50 +++---
 include/linux/rcutiny.h                       |   5 +
 kernel/rcu/tree.c                             |   9 ++
 kernel/rcu/tree.h                             |   3 +
 kernel/rcu/tree_exp.h                         |  71 +++++++--
 kernel/rcu/tree_plugin.h                      | 144 +++++++++++++-----
 6 files changed, 205 insertions(+), 77 deletions(-)

Quoted 3 lines

We started seeing the trace below in our regression system, after I bisected I found this is the offending commit. This appears immediately on boot.
Please let me know if you need any additional details.

Interesting. Here is the offending function:

	static void rcu_preempt_deferred_qs(struct task_struct *t)
	{
		unsigned long flags;
		bool couldrecurse = t->rcu_read_lock_nesting >= 0;

		if (!rcu_preempt_need_deferred_qs(t))
			return;
		if (couldrecurse)
			t->rcu_read_lock_nesting -= INT_MIN;
		local_irq_save(flags);
		rcu_preempt_deferred_qs_irqrestore(t, flags);
		if (couldrecurse)
			t->rcu_read_lock_nesting += INT_MIN;
	}

Using twos-complement arithmetic (which the kernel build gcc arguments enforce, last I checked) this does work. But as UBSAN says, subtracting INT_MIN is unconditionally undefined behavior according to the C standard.

Good catch!!!

So how do I make the above code not simply function, but rather meet the C standard?

One approach to add INT_MIN going in, then add INT_MAX and then add 1 coming out.

Another approach is to sacrifice the INT_MAX value (should be plenty safe), thus subtract INT_MAX going in and add INT_MAX coming out. For consistency, I suppose that I should change the INT_MIN in __rcu_read_unlock() to -INT_MAX.

Quoted 6 lines

I could also leave __rcu_read_unlock() alone and XOR the top bit of t->rcu_read_lock_nesting on entry and exit to/from rcu_preempt_deferred_qs().

Sacrificing the INT_MIN value seems most maintainable, as in the following patch. Thoughts?

Quoted 6 lines

The INT_MAX naming could be very confusing for nesting levels, could we not instead just define something like:
#define RCU_NESTING_MIN (INT_MIN - 1)
#define RCU_NESTING_MAX (INT_MAX)

and just use that? also one more comment below:

Hmmm... There is currently no use for RCU_NESTING_MAX, but if the check at the end of __rcu_read_unlock() were to be extended to check for too-deep positive nesting, it would need to check for something like INT_MAX/2. You could of course argue that the current check against INT_MIN/2 should instead be against -INT_MAX/2, but there really isn't much difference between the two.

Quoted 4 lines

Another approach would be to convert to unsigned in order to avoid the overflow problem completely.

For the moment, anyway, I am inclined to leave it as is.

Both the unsigned and INT_MIN/2 options sound good to me, but if you want leave it as is, that would be fine as well. thanks,

Quoted 3 lines · Joel Fernandes

Quoted 2 lines · Paul E. McKenney

Quoted 1 line · Joel Fernandes

On Mon, Oct 29, 2018 at 07:27:35AM -0700, Paul E. McKenney wrote:

Quoted 14 lines

Quoted 14 lines

Quoted 6 lines

The INT_MAX naming could be very confusing for nesting levels, could we not instead just define something like:
#define RCU_NESTING_MIN (INT_MIN - 1)
#define RCU_NESTING_MAX (INT_MAX)

and just use that? also one more comment below:

Hmmm... There is currently no use for RCU_NESTING_MAX, but if the check at the end of __rcu_read_unlock() were to be extended to check for too-deep positive nesting, it would need to check for something like INT_MAX/2. You could of course argue that the current check against INT_MIN/2 should instead be against -INT_MAX/2, but there really isn't much difference between the two.

Quoted 7 lines

Quoted 4 lines

Another approach would be to convert to unsigned in order to avoid the overflow problem completely.

For the moment, anyway, I am inclined to leave it as is.

Both the unsigned and INT_MIN/2 options sound good to me, but if you want leave it as is, that would be fine as well. thanks,

One approach would be something like this:

#define RCU_READ_LOCK_BIAS (INT_MAX)
#define RCU_READ_LOCK_NMAX (-INT_MAX)
#define RCU_READ_LOCK_PMAX INT_MAX

Then _rcu_read_unlock() would set ->rcu_read_lock_nesting to -RCU_READ_LOCK_BIAS, and compare against RCU_READ_LOCK_NMAX. The comparison against RCU_READ_LOCK_PMAX would preferably take place just after the increment in __rcu_read_lock(), again only under CONFIG_PROVE_RCU.

rcu_preempt_deferred_qs() would then subtract then add RCU_READ_LOCK_BIAS.

Thoughts?

Hearing no objections, here is the updated patch.

Thanx, Paul

------------------------------------------------------------------------

commit 970cab5d3d206029ed27274a98ea1c3d7e780e53

Author: Paul E. McKenney <[email protected]>
Date:   Mon Oct 29 07:36:50 2018 -0700

rcu: Avoid signed integer overflow in rcu_preempt_deferred_qs()

Subtracting INT_MIN can be interpreted as unconditional signed integer overflow, which according to the C standard is undefined behavior. Therefore, kernel build arguments notwithstanding, it would be good to future-proof the code. This commit therefore substitutes INT_MAX for INT_MIN in order to avoid undefined behavior.

While in the neighborhood, this commit also creates some meaningful
names
for INT_MAX and friends in order to improve readability, as suggested by Joel Fernandes.

Reported-by Ran Rozenstein <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

squash! rcu: Avoid signed integer overflow in rcu_preempt_deferred_qs()

While in the neighborhood, use macros to give meaningful names.

Signed-off-by Paul E. McKenney <[email protected]>

Quoted 29 lines

Hearing no objections, here is the updated patch.

Thanx, Paul

------------------------------------------------------------------------

commit 970cab5d3d206029ed27274a98ea1c3d7e780e53

Author: Paul E. McKenney <[email protected]>
Date:   Mon Oct 29 07:36:50 2018 -0700

rcu: Avoid signed integer overflow in rcu_preempt_deferred_qs()

Subtracting INT_MIN can be interpreted as unconditional signed integer overflow, which according to the C standard is undefined behavior. Therefore, kernel build arguments notwithstanding, it would be good to future-proof the code. This commit therefore substitutes INT_MAX for INT_MIN in order to avoid undefined behavior.

While in the neighborhood, this commit also creates some meaningful
names
for INT_MAX and friends in order to improve readability, as suggested by Joel Fernandes.

Reported-by Ran Rozenstein <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

squash! rcu: Avoid signed integer overflow in rcu_preempt_deferred_qs()

Quoted 3 lines

While in the neighborhood, use macros to give meaningful names.

Signed-off-by Paul E. McKenney <[email protected]>

Hi,

What is the acceptance status of this patch?

RCU's dyntick-idle code is written to tolerate half-interrupts, that it, either an interrupt that invokes rcu_irq_enter() but never invokes the corresponding rcu_irq_exit() on the one hand, or an interrupt that never invokes rcu_irq_enter() but does invoke the "corresponding" rcu_irq_exit() on the other. These things really did happen at one time, as evidenced by this ca-2011 LKML post:

http://lkml.kernel.org/r/[email protected]

The reason why RCU tolerates half-interrupts is that usermode helpers used exceptions to invoke a system call from within the kernel such that the system call did a normal return (not a return from exception) to the calling context. This caused rcu_irq_enter() to be invoked without a matching rcu_irq_exit(). However, usermode helpers have since been rewritten to make much more housebroken use of workqueues, kernel threads, and do_execve(), and therefore should no longer produce half-interrupts. No one knows of any other source of half-interrupts, but then again, no one seems insane enough to go audit the entire kernel to verify that half-interrupts really are a relic of the past.

This commit therefore adds a pair of WARN_ON_ONCE() calls that will trigger in the presence of half interrupts, which the code will continue to handle correctly. If neither of these WARN_ON_ONCE() trigger by mid-2021, then perhaps RCU can stop handling half-interrupts, which would be a considerable simplification.

Reported-by Steven Rostedt <[email protected]>

Reported-by Joel Fernandes <[email protected]>

Reported-by Andy Lutomirski <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Joel Fernandes (Google) <[email protected]>

---
 kernel/rcu/tree.c | 2 ++
 1 file changed, 2 insertions(+)

kernel/rcu/tree.c +2 -0

index dc041c2afbcc..d2b6ade692c9 100644
@@ -714,6 +714,7 @@ static void rcu_eqs_enter(bool user)
 	struct rcu_dynticks *rdtp;
 
 	rdtp = this_cpu_ptr(&rcu_dynticks);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting != DYNTICK_IRQ_NONIDLE);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, 0);
 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
 		     rdtp->dynticks_nesting == 0);

@@ -895,6 +896,7 @@ static void rcu_eqs_exit(bool user)
 	trace_rcu_dyntick(TPS("End"), rdtp->dynticks_nesting, 1, rdtp->dynticks);
 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && !user && !is_idle_task(current));
 	WRITE_ONCE(rdtp->dynticks_nesting, 1);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, DYNTICK_IRQ_NONIDLE);
 }
 

Signature · 1 line

2.17.1

Quoted 20 lines · Paul E. McKenney

RCU's dyntick-idle code is written to tolerate half-interrupts, that it, either an interrupt that invokes rcu_irq_enter() but never invokes the corresponding rcu_irq_exit() on the one hand, or an interrupt that never invokes rcu_irq_enter() but does invoke the "corresponding" rcu_irq_exit() on the other. These things really did happen at one time, as evidenced by this ca-2011 LKML post:

http://lkml.kernel.org/r/[email protected]

The reason why RCU tolerates half-interrupts is that usermode helpers used exceptions to invoke a system call from within the kernel such that the system call did a normal return (not a return from exception) to the calling context. This caused rcu_irq_enter() to be invoked without a matching rcu_irq_exit(). However, usermode helpers have since been rewritten to make much more housebroken use of workqueues, kernel threads, and do_execve(), and therefore should no longer produce half-interrupts. No one knows of any other source of half-interrupts, but then again, no one seems insane enough to go audit the entire kernel to verify that half-interrupts really are a relic of the past.

Quoted 5 lines

This commit therefore adds a pair of WARN_ON_ONCE() calls that will trigger in the presence of half interrupts, which the code will continue to handle correctly. If neither of these WARN_ON_ONCE() trigger by mid-2021, then perhaps RCU can stop handling half-interrupts, which would be a considerable simplification.

Hi Paul and everyone,
I was thinking some more about this patch and whether we can simplify this code much in 2021. Since 2021 is a bit far away, I thought working on it in again to keep it fresh in memory is a good idea ;-)

To me it seems we cannot easily combine the counters (dynticks_nesting and dynticks_nmi_nesting) even if we confirmed that there is no possibility of a half-interrupt scenario (assuming simplication means counter combining like Byungchul tried to do in https://goo.gl/X1U77X). The reason is because these 2 counters need to be tracked separately as they are used differently in the following function:

static int rcu_is_cpu_rrupt_from_idle(void)

{
        return __this_cpu_read(rcu_data.dynticks_nesting) <= 0 &&
               __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
}

dynticks_nesting actually tracks if we entered/exited idle or user mode.

dynticks_nmi_nesting tracks if we entered/exited interrupts.

We have to do the "dynticks_nmi_nesting <= 1" check because rcu_is_cpu_rrupt_from_idle() can possibly be called from an interrupt itself (like timer) so we discount 1 interrupt, and, the "dynticks_nesting <= 0" check is because the CPU MUST be in user or idle for the check to return true. We can't really combine these two into one counter then I think because they both convey different messages.

The only simplication we can do, is probably the "crowbar" updates to dynticks_nmi_nesting can be removed from rcu_eqs_enter/exit once we confirm no more half-interrupts are possible. Which might still be a worthwhile thing to do (while still keeping both counters separate).

However, I think we could combine the counters and lead to simplying the code in case we implement rcu_is_cpu_rrupt_from_idle differently such that it does not need the counters but NOHZ_FULL may take issue with that since it needs rcu_user_enter->rcu_eqs_enter to convey that the CPU is "RCU"-idle.

Actually, I had another question... rcu_user_enter() is a NOOP in !NOHZ_FULL config. In this case I was wondering if the the warning Paul added (in the patch I'm replying to) will really get fired for half-interrupts. The vast majority of the systems I believe are NOHZ_IDLE not NOHZ_FULL.
This is what a half-interrupt really looks like right? Please correct me if I'm wrong:
rcu_irq_enter() [half interrupt causes an exception and thus rcu_irq_enter]
rcu_user_enter() [due to usermode upcall]
rcu_user_exit()
(no more rcu_irq_exit() - hence half an interrupt)

But the rcu_user_enter()/exit is a NOOP in some configs, so will the warning in rcu_eqs_e{xit,nter} really do anything?

Or was the idea with adding the new warnings, that they would fire the next time rcu_idle_enter/exit is called? Like for example:

rcu_irq_enter() [This is due to half-interrupt]
rcu_idle_enter() [Eventually we enter the idle loop at some point
after the half-interrupt and the rcu_eqs_enter() would "crowbar" the dynticks_nmi_nesting counter to 0].

thanks!

- Joel

Quoted 33 lines

Reported-by Steven Rostedt <[email protected]>

Reported-by Joel Fernandes <[email protected]>

Reported-by Andy Lutomirski <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Joel Fernandes (Google) <[email protected]>

---
 kernel/rcu/tree.c | 2 ++
 1 file changed, 2 insertions(+)

kernel/rcu/tree.c +2 -0

index dc041c2afbcc..d2b6ade692c9 100644
@@ -714,6 +714,7 @@ static void rcu_eqs_enter(bool user)
 	struct rcu_dynticks *rdtp;
 
 	rdtp = this_cpu_ptr(&rcu_dynticks);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting != DYNTICK_IRQ_NONIDLE);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, 0);
 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
 		     rdtp->dynticks_nesting == 0);

@@ -895,6 +896,7 @@ static void rcu_eqs_exit(bool user)
 	trace_rcu_dyntick(TPS("End"), rdtp->dynticks_nesting, 1, rdtp->dynticks);
 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && !user && !is_idle_task(current));
 	WRITE_ONCE(rdtp->dynticks_nesting, 1);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, DYNTICK_IRQ_NONIDLE);
 }
 

Signature · 1 line

2.17.1

Quoted 27 lines · Joel Fernandes

Quoted 20 lines · Paul E. McKenney

RCU's dyntick-idle code is written to tolerate half-interrupts, that it, either an interrupt that invokes rcu_irq_enter() but never invokes the corresponding rcu_irq_exit() on the one hand, or an interrupt that never invokes rcu_irq_enter() but does invoke the "corresponding" rcu_irq_exit() on the other. These things really did happen at one time, as evidenced by this ca-2011 LKML post:

http://lkml.kernel.org/r/[email protected]

The reason why RCU tolerates half-interrupts is that usermode helpers used exceptions to invoke a system call from within the kernel such that the system call did a normal return (not a return from exception) to the calling context. This caused rcu_irq_enter() to be invoked without a matching rcu_irq_exit(). However, usermode helpers have since been rewritten to make much more housebroken use of workqueues, kernel threads, and do_execve(), and therefore should no longer produce half-interrupts. No one knows of any other source of half-interrupts, but then again, no one seems insane enough to go audit the entire kernel to verify that half-interrupts really are a relic of the past.

Quoted 5 lines

This commit therefore adds a pair of WARN_ON_ONCE() calls that will trigger in the presence of half interrupts, which the code will continue to handle correctly. If neither of these WARN_ON_ONCE() trigger by mid-2021, then perhaps RCU can stop handling half-interrupts, which would be a considerable simplification.

Quoted 4 lines

Hi Paul and everyone,
I was thinking some more about this patch and whether we can simplify this code much in 2021. Since 2021 is a bit far away, I thought working on it in again to keep it fresh in memory is a good idea ;-)

Indeed, easy to forget. ;-)

Quoted 7 lines

To me it seems we cannot easily combine the counters (dynticks_nesting and dynticks_nmi_nesting) even if we confirmed that there is no possibility of a half-interrupt scenario (assuming simplication means counter combining like Byungchul tried to do in https://goo.gl/X1U77X). The reason is because these 2 counters need to be tracked separately as they are used differently in the following function:

Quoted 7 lines

static int rcu_is_cpu_rrupt_from_idle(void)

{
        return __this_cpu_read(rcu_data.dynticks_nesting) <= 0 &&
               __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
}

dynticks_nesting actually tracks if we entered/exited idle or user mode.

True, though it tracks user mode only in CONFIG_NO_HZ_FULL kernels.

Quoted 1 line

dynticks_nmi_nesting tracks if we entered/exited interrupts.

Including NMIs, yes.

Quoted 12 lines

We have to do the "dynticks_nmi_nesting <= 1" check because rcu_is_cpu_rrupt_from_idle() can possibly be called from an interrupt itself (like timer) so we discount 1 interrupt, and, the "dynticks_nesting <= 0" check is because the CPU MUST be in user or idle for the check to return true. We can't really combine these two into one counter then I think because they both convey different messages.

The only simplication we can do, is probably the "crowbar" updates to dynticks_nmi_nesting can be removed from rcu_eqs_enter/exit once we confirm no more half-interrupts are possible. Which might still be a worthwhile thing to do (while still keeping both counters separate).

Quoted 4 lines

However, I think we could combine the counters and lead to simplying the code in case we implement rcu_is_cpu_rrupt_from_idle differently such that it does not need the counters but NOHZ_FULL may take issue with that since it needs rcu_user_enter->rcu_eqs_enter to convey that the CPU is "RCU"-idle.

I haven't gone through it in detail, but it seems like we should be able to treat in-kernel process-level execution like an interrupt from idle or userspace, as the case might be. If we did that, shouldn't we be able to just do this?

static int rcu_is_cpu_rrupt_from_idle(void)

{
        return __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
}

Quoted 10 lines

Actually, I had another question... rcu_user_enter() is a NOOP in !NOHZ_FULL config. In this case I was wondering if the the warning Paul added (in the patch I'm replying to) will really get fired for half-interrupts. The vast majority of the systems I believe are NOHZ_IDLE not NOHZ_FULL.
This is what a half-interrupt really looks like right? Please correct me if I'm wrong:
rcu_irq_enter() [half interrupt causes an exception and thus rcu_irq_enter]
rcu_user_enter() [due to usermode upcall]
rcu_user_exit()
(no more rcu_irq_exit() - hence half an interrupt)

Quoted 2 lines

But the rcu_user_enter()/exit is a NOOP in some configs, so will the warning in rcu_eqs_e{xit,nter} really do anything?

Yes, because these are also called from rcu_idle_enter() and rcu_idle_exit(), which is invoked even in !NO_HZ_FULL kernels.

Quoted 7 lines

Or was the idea with adding the new warnings, that they would fire the next time rcu_idle_enter/exit is called? Like for example:

rcu_irq_enter() [This is due to half-interrupt]
rcu_idle_enter() [Eventually we enter the idle loop at some point
after the half-interrupt and the rcu_eqs_enter() would "crowbar" the dynticks_nmi_nesting counter to 0].

You got it! ;-)

Quoted 78 lines · Paul E. McKenney

Quoted 27 lines · Joel Fernandes

Quoted 20 lines · Paul E. McKenney

RCU's dyntick-idle code is written to tolerate half-interrupts, that it, either an interrupt that invokes rcu_irq_enter() but never invokes the corresponding rcu_irq_exit() on the one hand, or an interrupt that never invokes rcu_irq_enter() but does invoke the "corresponding" rcu_irq_exit() on the other. These things really did happen at one time, as evidenced by this ca-2011 LKML post:

http://lkml.kernel.org/r/[email protected]

The reason why RCU tolerates half-interrupts is that usermode helpers used exceptions to invoke a system call from within the kernel such that the system call did a normal return (not a return from exception) to the calling context. This caused rcu_irq_enter() to be invoked without a matching rcu_irq_exit(). However, usermode helpers have since been rewritten to make much more housebroken use of workqueues, kernel threads, and do_execve(), and therefore should no longer produce half-interrupts. No one knows of any other source of half-interrupts, but then again, no one seems insane enough to go audit the entire kernel to verify that half-interrupts really are a relic of the past.

Quoted 5 lines

This commit therefore adds a pair of WARN_ON_ONCE() calls that will trigger in the presence of half interrupts, which the code will continue to handle correctly. If neither of these WARN_ON_ONCE() trigger by mid-2021, then perhaps RCU can stop handling half-interrupts, which would be a considerable simplification.

Quoted 4 lines

Hi Paul and everyone,
I was thinking some more about this patch and whether we can simplify this code much in 2021. Since 2021 is a bit far away, I thought working on it in again to keep it fresh in memory is a good idea ;-)

Indeed, easy to forget. ;-)

Quoted 7 lines

To me it seems we cannot easily combine the counters (dynticks_nesting and dynticks_nmi_nesting) even if we confirmed that there is no possibility of a half-interrupt scenario (assuming simplication means counter combining like Byungchul tried to do in https://goo.gl/X1U77X). The reason is because these 2 counters need to be tracked separately as they are used differently in the following function:

Quoted 7 lines

static int rcu_is_cpu_rrupt_from_idle(void)

{
        return __this_cpu_read(rcu_data.dynticks_nesting) <= 0 &&
               __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
}

dynticks_nesting actually tracks if we entered/exited idle or user mode.

True, though it tracks user mode only in CONFIG_NO_HZ_FULL kernels.

Quoted 1 line

dynticks_nmi_nesting tracks if we entered/exited interrupts.

Including NMIs, yes.

Quoted 12 lines

We have to do the "dynticks_nmi_nesting <= 1" check because rcu_is_cpu_rrupt_from_idle() can possibly be called from an interrupt itself (like timer) so we discount 1 interrupt, and, the "dynticks_nesting <= 0" check is because the CPU MUST be in user or idle for the check to return true. We can't really combine these two into one counter then I think because they both convey different messages.

The only simplication we can do, is probably the "crowbar" updates to dynticks_nmi_nesting can be removed from rcu_eqs_enter/exit once we confirm no more half-interrupts are possible. Which might still be a worthwhile thing to do (while still keeping both counters separate).

Quoted 4 lines

However, I think we could combine the counters and lead to simplying the code in case we implement rcu_is_cpu_rrupt_from_idle differently such that it does not need the counters but NOHZ_FULL may take issue with that since it needs rcu_user_enter->rcu_eqs_enter to convey that the CPU is "RCU"-idle.

I haven't gone through it in detail, but it seems like we should be able to treat in-kernel process-level execution like an interrupt from idle or userspace, as the case might be. If we did that, shouldn't we be able to just do this?

Quoted 4 lines

static int rcu_is_cpu_rrupt_from_idle(void)

{
        return __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
}

I think that would work only if this function is always called from an interrupt:

The comments on this function says:
* If the current CPU is idle or running at a first-level (not nested)
* interrupt from idle, return true. The caller must have at least
* disabled preemption.
*/

According to this comment rcu_is_cpu_rrupt_from_idle can be called from somewhere other than an interrupt although from code-reading that does not seem to be.

If it is ever possible to call rcu_is_cpu_rrupt_from_idle from anywhere but an interrupt, then we would have a scenario like:
rcu_eqs_exit() (Called say from rcu_idle_exit)
rcu_is_cpu_rrupt_from_idle (now nesting counter is 1, so the <=1 check
returns true).

This would result in the function falsely claiming the CPU was idle from an RCU standpoint I think.

However both from testing and from code reading, I don't see such a scenario happening.

Could we be more explicit in the code that this function can only
be called from an interrupt, and also we change the code comment to be more clear about it (like the following diff)?

I made the following change and it didn't seem to blow up and also makes the code more clear. The only change I would make if we were considering merging this is to change the BUG_ON to WARN_ON_ONCE but I want to check first if you think this change is useful to do. I think being explicit about the intention is a good thing. I also specifically check for first-level of interrupt nesting (==1).

kernel/rcu/tree.c +8 -3

index a45c45a4a09b..531c63c40001 100644
@@ -377,14 +377,19 @@ static void __maybe_unused rcu_momentary_dyntick_idle(void)
 /**
  * rcu_is_cpu_rrupt_from_idle - see if idle or immediately interrupted from idle
  *
- * If the current CPU is idle or running at a first-level (not nested)
+ * If the current CPU is idle and running at a first-level (not nested)
  * interrupt from idle, return true.  The caller must have at least
  * disabled preemption.
  */
 static int rcu_is_cpu_rrupt_from_idle(void)
 {
-	return __this_cpu_read(rcu_data.dynticks_nesting) <= 0 &&
-	       __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
+	int dynticks_nesting = __this_cpu_read(rcu_data.dynticks_nesting);
+	int dynticks_nmi_nesting = __this_cpu_read(rcu_data.dynticks_nmi_nesting);
+
+	/* This function should only be called from an interrupt */
+	BUG_ON(dynticks_nmi_nesting < 1);
+
+	return dynticks_nmi_nesting == 1 && dynticks_nesting <= 0;
 }
 
 #define DEFAULT_RCU_BLIMIT 10     /* Maximum callbacks per rcu_do_batch. */

Quoted 12 lines

Quoted 12 lines

Actually, I had another question... rcu_user_enter() is a NOOP in !NOHZ_FULL config. In this case I was wondering if the the warning Paul added (in the patch I'm replying to) will really get fired for half-interrupts. The vast majority of the systems I believe are NOHZ_IDLE not NOHZ_FULL.
This is what a half-interrupt really looks like right? Please correct me if I'm wrong:
rcu_irq_enter() [half interrupt causes an exception and thus rcu_irq_enter]
rcu_user_enter() [due to usermode upcall]
rcu_user_exit()
(no more rcu_irq_exit() - hence half an interrupt)

Quoted 5 lines

Quoted 2 lines

But the rcu_user_enter()/exit is a NOOP in some configs, so will the warning in rcu_eqs_e{xit,nter} really do anything?

Yes, because these are also called from rcu_idle_enter() and rcu_idle_exit(), which is invoked even in !NO_HZ_FULL kernels.

Got it.

Quoted 3 lines

Quoted 3 lines

Or was the idea with adding the new warnings, that they would fire the next time rcu_idle_enter/exit is called? Like for example:

Quoted 6 lines

Quoted 4 lines

rcu_irq_enter() [This is due to half-interrupt]
rcu_idle_enter() [Eventually we enter the idle loop at some point
after the half-interrupt and the rcu_eqs_enter() would "crowbar" the dynticks_nmi_nesting counter to 0].

You got it! ;-)

Thanks a lot for confirming,

Quoted 4 lines

Could we be more explicit in the code that this function can only
be called from an interrupt, and also we change the code comment to be more clear about it (like the following diff)?

That would be good!

Nice trick on using dyntick state to check for interrupt nesting, but wouldn't consolidating the counters break that? But is there a lockdep check for being in a hardware interrupt handler? If not, could one be added? This would have the benefit of not adding overhead to the scheduling-clock interrupt in production builds of the Linux kernel, while still finding this bug in testing.

(Another approach would be to use IS_ENABLED(CONFIG_PROVE_RCU), but a lockdep check would be cleaner.)

AFAICS, lockdep does not specifically track when we enter an interrupt, but rather only tracks when interrupts are enabled/disabled.

Quoted 2 lines · On Wed, 13 Mar 2019 11:09:48 -0400 Joel Fernandes <[email protected]>…

AFAICS, lockdep does not specifically track when we enter an interrupt, but rather only tracks when interrupts are enabled/disabled.

It does:

#define __irq_enter()					\
	do {						\
		account_irq_enter_time(current);	\
		preempt_count_add(HARDIRQ_OFFSET);	\
		trace_hardirq_enter();			\
	} while (0)

# define trace_hardirq_enter()			\
do {						\
	current->hardirq_context++;		\
} while (0)

And if the hardirq_context ever does not match "in_irq()" lockdep will complain loudly.

Does this mean that there is a better approach that Joel's suggestion? I believe he would end up with something like this:

	WARN_ON_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) && !in_irq());

It would be nice if there is something like this:

	lockdep_assert_in_irq_handler();

But I haven't seen this. (Not that I have looked particularly hard for such a thing, mind you!)

Quoted 9 lines · On Wed, 13 Mar 2019 08:51:55 -0700 "Paul E. McKenney" <[email protected]>…

Does this mean that there is a better approach that Joel's suggestion? I believe he would end up with something like this:

	WARN_ON_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) && !in_irq());

It would be nice if there is something like this:

	lockdep_assert_in_irq_handler();

Quoted 2 lines

But I haven't seen this. (Not that I have looked particularly hard for such a thing, mind you!)

That would be trivial to implement:

#define lockdep_assert_in_irq() do {
		WARN_ON(debug_locks && !current->hardirq_context);
	} while (0)

Quoted 17 lines · Steven Rostedt

Quoted 11 lines · On Wed, 13 Mar 2019 08:51:55 -0700 "Paul E. McKenney" <[email protected]>…

Does this mean that there is a better approach that Joel's suggestion? I believe he would end up with something like this:

	WARN_ON_ONCE(IS_ENABLED(CONFIG_PROVE_RCU) && !in_irq());

It would be nice if there is something like this:

	lockdep_assert_in_irq_handler();

But I haven't seen this. (Not that I have looked particularly hard for such a thing, mind you!)

That would be trivial to implement:

Quoted 3 lines

#define lockdep_assert_in_irq() do {
		WARN_ON(debug_locks && !current->hardirq_context);
	} while (0)

Looks good to me!

Joel, does this work for you? I could be wrong, but I suspect that Steve is suggesting that you incorporate the above into your eventual patch. ;-)

Oh thanks for pointing that out. Yes it does work for me. I agree with the lockdep API addition and others could benefit from it too. I will incorporate the lockdep API addition into the RCU patch, but let me know if I should rather split it.

Quoted 4 lines · On Thu, 14 Mar 2019 08:31:59 -0400 Joel Fernandes <[email protected]>…

Oh thanks for pointing that out. Yes it does work for me. I agree with the lockdep API addition and others could benefit from it too. I will incorporate the lockdep API addition into the RCU patch, but let me know if I should rather split it.

I'd recommend splitting it (adding the lockdep_assert in a patch by itself), but make sure that patch Cc's the lockdep maintainers and explains the reason for adding it. Might as well Cc the lockdep maintainers on the entire series too.

Quoted 8 lines · On Thu, 14 Mar 2019 09:36:57 -0400 Steven Rostedt <[email protected]> wrote:

Quoted 4 lines · On Thu, 14 Mar 2019 08:31:59 -0400 Joel Fernandes <[email protected]>…

Oh thanks for pointing that out. Yes it does work for me. I agree with the lockdep API addition and others could benefit from it too. I will incorporate the lockdep API addition into the RCU patch, but let me know if I should rather split it.

Quoted 5 lines

I'd recommend splitting it (adding the lockdep_assert in a patch by itself), but make sure that patch Cc's the lockdep maintainers and explains the reason for adding it. Might as well Cc the lockdep maintainers on the entire series too.

Feel free to add "Suggested-by: Steven Rostedt (VMware) <[email protected]>" on that patch too.

Quoted 20 lines · Paul E. McKenney

RCU's dyntick-idle code is written to tolerate half-interrupts, that it, either an interrupt that invokes rcu_irq_enter() but never invokes the corresponding rcu_irq_exit() on the one hand, or an interrupt that never invokes rcu_irq_enter() but does invoke the "corresponding" rcu_irq_exit() on the other. These things really did happen at one time, as evidenced by this ca-2011 LKML post:

http://lkml.kernel.org/r/[email protected]

The reason why RCU tolerates half-interrupts is that usermode helpers used exceptions to invoke a system call from within the kernel such that the system call did a normal return (not a return from exception) to the calling context. This caused rcu_irq_enter() to be invoked without a matching rcu_irq_exit(). However, usermode helpers have since been rewritten to make much more housebroken use of workqueues, kernel threads, and do_execve(), and therefore should no longer produce half-interrupts. No one knows of any other source of half-interrupts, but then again, no one seems insane enough to go audit the entire kernel to verify that half-interrupts really are a relic of the past.

Quoted 5 lines

This commit therefore adds a pair of WARN_ON_ONCE() calls that will trigger in the presence of half interrupts, which the code will continue to handle correctly. If neither of these WARN_ON_ONCE() trigger by mid-2021, then perhaps RCU can stop handling half-interrupts, which would be a considerable simplification.

Hi Paul and everyone,
I was thinking some more about this patch and whether we can simplify this code much in 2021. Since 2021 is a bit far away, I thought working on it in again to keep it fresh in memory is a good idea ;-)

To me it seems we cannot easily combine the counters (dynticks_nesting and dynticks_nmi_nesting) even if we confirmed that there is no possibility of a half-interrupt scenario (assuming simplication means counter combining like Byungchul tried to do in https://goo.gl/X1U77X). The reason is because these 2 counters need to be tracked separately as they are used differently in the following function:

static int rcu_is_cpu_rrupt_from_idle(void)

{
        return __this_cpu_read(rcu_data.dynticks_nesting) <= 0 &&
               __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
}

dynticks_nesting actually tracks if we entered/exited idle or user mode.

dynticks_nmi_nesting tracks if we entered/exited interrupts.

We have to do the "dynticks_nmi_nesting <= 1" check because rcu_is_cpu_rrupt_from_idle() can possibly be called from an interrupt itself (like timer) so we discount 1 interrupt, and, the "dynticks_nesting <= 0" check is because the CPU MUST be in user or idle for the check to return true. We can't really combine these two into one counter then I think because they both convey different messages.

The only simplication we can do, is probably the "crowbar" updates to dynticks_nmi_nesting can be removed from rcu_eqs_enter/exit once we confirm no more half-interrupts are possible. Which might still be a worthwhile thing to do (while still keeping both counters separate).

However, I think we could combine the counters and lead to simplying the code in case we implement rcu_is_cpu_rrupt_from_idle differently such that it does not need the counters but NOHZ_FULL may take issue with that since it needs rcu_user_enter->rcu_eqs_enter to convey that the CPU is "RCU"-idle.

Actually, I had another question... rcu_user_enter() is a NOOP in !NOHZ_FULL config. In this case I was wondering if the the warning Paul added (in the patch I'm replying to) will really get fired for half-interrupts. The vast majority of the systems I believe are NOHZ_IDLE not NOHZ_FULL.
This is what a half-interrupt really looks like right? Please correct me if I'm wrong:
rcu_irq_enter() [half interrupt causes an exception and thus rcu_irq_enter]
rcu_user_enter() [due to usermode upcall]
rcu_user_exit()
(no more rcu_irq_exit() - hence half an interrupt)

But the rcu_user_enter()/exit is a NOOP in some configs, so will the warning in rcu_eqs_e{xit,nter} really do anything?

Or was the idea with adding the new warnings, that they would fire the next time rcu_idle_enter/exit is called? Like for example:

rcu_irq_enter() [This is due to half-interrupt]
rcu_idle_enter() [Eventually we enter the idle loop at some point
after the half-interrupt and the rcu_eqs_enter() would "crowbar" the dynticks_nmi_nesting counter to 0].

thanks!

- Joel

Quoted 33 lines

Reported-by Steven Rostedt <[email protected]>

Reported-by Joel Fernandes <[email protected]>

Reported-by Andy Lutomirski <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Joel Fernandes (Google) <[email protected]>

---
 kernel/rcu/tree.c | 2 ++
 1 file changed, 2 insertions(+)

kernel/rcu/tree.c +2 -0

index dc041c2afbcc..d2b6ade692c9 100644
@@ -714,6 +714,7 @@ static void rcu_eqs_enter(bool user)
 	struct rcu_dynticks *rdtp;
 
 	rdtp = this_cpu_ptr(&rcu_dynticks);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting != DYNTICK_IRQ_NONIDLE);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, 0);
 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
 		     rdtp->dynticks_nesting == 0);

@@ -895,6 +896,7 @@ static void rcu_eqs_exit(bool user)
 	trace_rcu_dyntick(TPS("End"), rdtp->dynticks_nesting, 1, rdtp->dynticks);
 	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && !user && !is_idle_task(current));
 	WRITE_ONCE(rdtp->dynticks_nesting, 1);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting);
 	WRITE_ONCE(rdtp->dynticks_nmi_nesting, DYNTICK_IRQ_NONIDLE);
 }
 

Signature · 1 line

2.17.1

Quoted 31 lines · Joel Fernandes

Quoted 20 lines · Paul E. McKenney

RCU's dyntick-idle code is written to tolerate half-interrupts, that it, either an interrupt that invokes rcu_irq_enter() but never invokes the corresponding rcu_irq_exit() on the one hand, or an interrupt that never invokes rcu_irq_enter() but does invoke the "corresponding" rcu_irq_exit() on the other. These things really did happen at one time, as evidenced by this ca-2011 LKML post:

http://lkml.kernel.org/r/[email protected]

The reason why RCU tolerates half-interrupts is that usermode helpers used exceptions to invoke a system call from within the kernel such that the system call did a normal return (not a return from exception) to the calling context. This caused rcu_irq_enter() to be invoked without a matching rcu_irq_exit(). However, usermode helpers have since been rewritten to make much more housebroken use of workqueues, kernel threads, and do_execve(), and therefore should no longer produce half-interrupts. No one knows of any other source of half-interrupts, but then again, no one seems insane enough to go audit the entire kernel to verify that half-interrupts really are a relic of the past.

Quoted 5 lines

This commit therefore adds a pair of WARN_ON_ONCE() calls that will trigger in the presence of half interrupts, which the code will continue to handle correctly. If neither of these WARN_ON_ONCE() trigger by mid-2021, then perhaps RCU can stop handling half-interrupts, which would be a considerable simplification.

Hi Paul and everyone,
I was thinking some more about this patch and whether we can simplify this code much in 2021. Since 2021 is a bit far away, I thought working on it in again to keep it fresh in memory is a good idea ;-)

Quoted 6 lines

To me it seems we cannot easily combine the counters (dynticks_nesting and dynticks_nmi_nesting) even if we confirmed that there is no possibility of a half-interrupt scenario (assuming simplication means counter combining like Byungchul tried to do in https://goo.gl/X1U77X). The reason is because these 2 counters need to be tracked separately as they are used differently in the following function:

Hi Joel and Paul,

I always love the way to logically approach problems so I'm a fan of all your works :) But I'm JUST curious about something here. Why can't we combine them the way I tried even if we confirm no possibility of half-interrupt? IMHO, the only thing we want to know through calling rcu_is_cpu_rrupt_from_idle() is whether the interrupt comes from RCU-idle or not - of course assuming the caller context always be an well-defined interrupt context like e.g. the tick handler.

So the function can return true if the caller is within a RCU-idle region except a well-known single interrupt nested.

Of course, now that we cannot confirm it yet, the crowbar is necessary. But does it still have a problem even after confirming it? Why? What am I missing? Could you explain why for me? :(

Thanks,
Byungchul

Quoted 84 lines

static int rcu_is_cpu_rrupt_from_idle(void)

{
         return __this_cpu_read(rcu_data.dynticks_nesting) <= 0 &&
                __this_cpu_read(rcu_data.dynticks_nmi_nesting) <= 1;
}

dynticks_nesting actually tracks if we entered/exited idle or user mode.

dynticks_nmi_nesting tracks if we entered/exited interrupts.

We have to do the "dynticks_nmi_nesting <= 1" check because rcu_is_cpu_rrupt_from_idle() can possibly be called from an interrupt itself (like timer) so we discount 1 interrupt, and, the "dynticks_nesting <= 0" check is because the CPU MUST be in user or idle for the check to return true. We can't really combine these two into one counter then I think because they both convey different messages.

The only simplication we can do, is probably the "crowbar" updates to dynticks_nmi_nesting can be removed from rcu_eqs_enter/exit once we confirm no more half-interrupts are possible. Which might still be a worthwhile thing to do (while still keeping both counters separate).

However, I think we could combine the counters and lead to simplying the code in case we implement rcu_is_cpu_rrupt_from_idle differently such that it does not need the counters but NOHZ_FULL may take issue with that since it needs rcu_user_enter->rcu_eqs_enter to convey that the CPU is "RCU"-idle.

Actually, I had another question... rcu_user_enter() is a NOOP in !NOHZ_FULL config. In this case I was wondering if the the warning Paul added (in the patch I'm replying to) will really get fired for half-interrupts. The vast majority of the systems I believe are NOHZ_IDLE not NOHZ_FULL.
This is what a half-interrupt really looks like right? Please correct me if I'm wrong:
rcu_irq_enter() [half interrupt causes an exception and thus rcu_irq_enter]
rcu_user_enter() [due to usermode upcall]
rcu_user_exit()
(no more rcu_irq_exit() - hence half an interrupt)

But the rcu_user_enter()/exit is a NOOP in some configs, so will the warning in rcu_eqs_e{xit,nter} really do anything?

Or was the idea with adding the new warnings, that they would fire the next time rcu_idle_enter/exit is called? Like for example:

rcu_irq_enter() [This is due to half-interrupt]
rcu_idle_enter() [Eventually we enter the idle loop at some point
after the half-interrupt and the rcu_eqs_enter() would "crowbar" the dynticks_nmi_nesting counter to 0].

thanks!

- Joel

Quoted 32 lines

Reported-by Steven Rostedt <[email protected]>

Reported-by Joel Fernandes <[email protected]>

Reported-by Andy Lutomirski <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

Reviewed-by Joel Fernandes (Google) <[email protected]>

---
  kernel/rcu/tree.c | 2 ++
  1 file changed, 2 insertions(+)

kernel/rcu/tree.c +2 -0

index dc041c2afbcc..d2b6ade692c9 100644
@@ -714,6 +714,7 @@ static void rcu_eqs_enter(bool user)
  	struct rcu_dynticks *rdtp;
 
  	rdtp = this_cpu_ptr(&rcu_dynticks);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting != DYNTICK_IRQ_NONIDLE);
  	WRITE_ONCE(rdtp->dynticks_nmi_nesting, 0);
  	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) &&
  		     rdtp->dynticks_nesting == 0);

@@ -895,6 +896,7 @@ static void rcu_eqs_exit(bool user)
  	trace_rcu_dyntick(TPS("End"), rdtp->dynticks_nesting, 1, rdtp->dynticks);
  	WARN_ON_ONCE(IS_ENABLED(CONFIG_RCU_EQS_DEBUG) && !user && !is_idle_task(current));
  	WRITE_ONCE(rdtp->dynticks_nesting, 1);
+	WARN_ON_ONCE(rdtp->dynticks_nmi_nesting);
  	WRITE_ONCE(rdtp->dynticks_nmi_nesting, DYNTICK_IRQ_NONIDLE);
  }
 

Signature · 1 line

2.17.1

Quoted 48 lines · Byungchul Park

Quoted 31 lines · Joel Fernandes

Quoted 20 lines · Paul E. McKenney

RCU's dyntick-idle code is written to tolerate half-interrupts, that it, either an interrupt that invokes rcu_irq_enter() but never invokes the corresponding rcu_irq_exit() on the one hand, or an interrupt that never invokes rcu_irq_enter() but does invoke the "corresponding" rcu_irq_exit() on the other. These things really did happen at one time, as evidenced by this ca-2011 LKML post:

http://lkml.kernel.org/r/[email protected]

The reason why RCU tolerates half-interrupts is that usermode helpers used exceptions to invoke a system call from within the kernel such that the system call did a normal return (not a return from exception) to the calling context. This caused rcu_irq_enter() to be invoked without a matching rcu_irq_exit(). However, usermode helpers have since been rewritten to make much more housebroken use of workqueues, kernel threads, and do_execve(), and therefore should no longer produce half-interrupts. No one knows of any other source of half-interrupts, but then again, no one seems insane enough to go audit the entire kernel to verify that half-interrupts really are a relic of the past.

Quoted 5 lines

This commit therefore adds a pair of WARN_ON_ONCE() calls that will trigger in the presence of half interrupts, which the code will continue to handle correctly. If neither of these WARN_ON_ONCE() trigger by mid-2021, then perhaps RCU can stop handling half-interrupts, which would be a considerable simplification.

Hi Paul and everyone,
I was thinking some more about this patch and whether we can simplify this code much in 2021. Since 2021 is a bit far away, I thought working on it in again to keep it fresh in memory is a good idea ;-)

Quoted 6 lines

To me it seems we cannot easily combine the counters (dynticks_nesting and dynticks_nmi_nesting) even if we confirmed that there is no possibility of a half-interrupt scenario (assuming simplication means counter combining like Byungchul tried to do in https://goo.gl/X1U77X). The reason is because these 2 counters need to be tracked separately as they are used differently in the following function:

Hi Joel and Paul,

I always love the way to logically approach problems so I'm a fan of all your works :) But I'm JUST curious about something here. Why can't we combine them the way I tried even if we confirm no possibility of half-interrupt? IMHO, the only thing we want to know through calling rcu_is_cpu_rrupt_from_idle() is whether the interrupt comes from RCU-idle or not - of course assuming the caller context always be an well-defined interrupt context like e.g. the tick handler.

Quoted 6 lines

So the function can return true if the caller is within a RCU-idle region except a well-known single interrupt nested.

Of course, now that we cannot confirm it yet, the crowbar is necessary. But does it still have a problem even after confirming it? Why? What am I missing? Could you explain why for me? :(

Did you also want to consider the case the function is called from others than
well-known interrupt contexts? If yes, then I agree with you, there doesn't seem to be the kind of code and it's not a good idea to let the function be called generally though.