v3 Provide infrastructure for full-system idle

From: "Paul E. McKenney" <[email protected]>

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy. The handling of these new fields is otherwise quite similar to that for the exiting fields. This commit also adds the initialization required for these fields.

So, why is usermode execution treated differently, with RCU considering it a quiescent state equivalent to idle, while in contrast the new full-system idle state detection considers usermode execution to be non-idle?

It turns out that although one of RCU's quiescent states is usermode execution, it is not a full-system idle state. This is because the purpose of the full-system idle state is not RCU, but rather determining when accurate timekeeping can safely be disabled. Whenever accurate timekeeping is required in a CONFIG_NO_HZ_FULL kernel, at least one CPU must keep the scheduling-clock tick going. If even one CPU is executing in user mode, accurate timekeeping is requires, particularly for architectures where gettimeofday() and friends do not enter the kernel. Only when all CPUs are really and truly idle can accurate timekeeping be disabled, allowing all CPUs to turn off the scheduling clock interrupt, thus greatly improving energy efficiency.

This naturally raises the question "Why is this code in RCU rather than in timekeeping?", and the answer is that RCU has the data and infrastructure to efficiently make this determination.

Quoted 27 lines · Paul E. McKenney

From: "Paul E. McKenney" <[email protected]>

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy. The handling of these new fields is otherwise quite similar to that for the exiting fields. This commit also adds the initialization required for these fields.

So, why is usermode execution treated differently, with RCU considering it a quiescent state equivalent to idle, while in contrast the new full-system idle state detection considers usermode execution to be non-idle?

It turns out that although one of RCU's quiescent states is usermode execution, it is not a full-system idle state. This is because the purpose of the full-system idle state is not RCU, but rather determining when accurate timekeeping can safely be disabled. Whenever accurate timekeeping is required in a CONFIG_NO_HZ_FULL kernel, at least one CPU must keep the scheduling-clock tick going. If even one CPU is executing in user mode, accurate timekeeping is requires, particularly for architectures where gettimeofday() and friends do not enter the kernel. Only when all CPUs are really and truly idle can accurate timekeeping be disabled, allowing all CPUs to turn off the scheduling clock interrupt, thus greatly improving energy efficiency.

Quoted 3 lines

This naturally raises the question "Why is this code in RCU rather than in timekeeping?", and the answer is that RCU has the data and infrastructure to efficiently make this determination.

but but but but... why doesn't the regular nohz code qualify? I'd think that too would be tracking pretty much the same things, no?

}

/*
+ * Unconditionally force exit from full system-idle state. This is
+ * invoked when a normal CPU exits idle, but must be called separately
+ * for the timekeeping CPU (tick_do_timer_cpu). The reason for this
+ * is that the timekeeping CPU is permitted to take scheduling-clock
+ * interrupts while the system is in system-idle state, and of course
+ * rcu_sysidle_exit() has no way of distinguishing a scheduling-clock
+ * interrupt from any other type of interrupt.
+ */

kernel/rcutree_plugin.h +1 -0

+void rcu_sysidle_force_exit(void)

Quoted 12 lines · Paul E. McKenney

}

/*
+ * Unconditionally force exit from full system-idle state. This is
+ * invoked when a normal CPU exits idle, but must be called separately
+ * for the timekeeping CPU (tick_do_timer_cpu). The reason for this
+ * is that the timekeeping CPU is permitted to take scheduling-clock
+ * interrupts while the system is in system-idle state, and of course
+ * rcu_sysidle_exit() has no way of distinguishing a scheduling-clock
+ * interrupt from any other type of interrupt.
+ */

(quoted diff) +1 -0

+void rcu_sysidle_force_exit(void)

Review

Quoted 10 lines

(quoted diff) +10 -0

+{
+	int oldstate = ACCESS_ONCE(full_sysidle_state);
+	int newoldstate;
+
+	/*
+	 * Each pass through the following loop attempts to exit full
+	 * system-idle state.  If contention proves to be a problem,
+	 * a trylock-based contention tree could be used here.
+	 */
+	while (oldstate > RCU_SYSIDLE_SHORT) {

I'm missing a key here.

Let's imagine that the timekeeper has finally set full_sysidle_state = RCU_SYSIDLE_FULL_NOTED with cmpxchg, what guarantees that this CPU is not seeing a stale RCU_SYSIDLE_SHORT value for example?

Quoted 5 lines · Frederic Weisbecker

I'm missing a key here.

Let's imagine that the timekeeper has finally set full_sysidle_state = RCU_SYSIDLE_FULL_NOTED with cmpxchg, what guarantees that this CPU is not seeing a stale RCU_SYSIDLE_SHORT value for example?

Good question! Let's see if I have a reasonable answer. ;-)

I am going to start with the large-CPU case, so that the state is advanced only by the grace-period kthread.

1. Case 1: the timekeeper CPU invoked rcu_sysidle_force_exit().
In this case, this is the same CPU that set full_sysidle_state to RCU_SYSIDLE_FULL_NOTED, so it is guaranteed not to see a stale value.

2. Case 2: Some CPU came out of idle, and invoked rcu_sysidle_exit().
In this case, if this CPU reads a RCU_SYSIDLE_SHORT from full_sysidle_state, this read must have come before the cmpxchg() (on some other CPU) that set it to RCU_SYSIDLE_LONG. Because this CPU's read from full_sysidle_state was preceded by an atomic_inc() that updated this CPU's ->dynticks_idle, that update must also precede the cmpxchg() that set full_sysidle_state to RCU_SYSIDLE_LONG. Because the state advancing is done from within a single thread, the subsequent scan is guaranteed to see the first CPU's update of ->dynticks_idle, and will therefore refrain from advancing full_sysidle_state to RCU_SYSIDLE_FULL.

This will in turn prevent the timekeeping thread from advancing the state to RCU_SYSIDLE_FULL_NOTED, so this scenario cannot happen.

Unfortunately, the reasoning in #2 above does not hold in the small-CPU case because there is the possibility of both the timekeeping CPU and the RCU grace-period kthread concurrently advancing the state machine. This would be bad, good catch!!!

The patch below (untested) is an attempt to fix this. If it actually works, I will merge it in with 6/7.

Anything else I missed? ;-)

Thanx, Paul

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

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

kernel/rcutree.c +1 -1

index aa3f525..fe83085 100644
@@ -1364,7 +1364,7 @@ int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in)
 		}
 		force_qs_rnp(rsp, dyntick_save_progress_counter,
 			     &isidle, &maxj);
-		rcu_sysidle_report(rsp, isidle, maxj);
+		rcu_sysidle_report_gp(rsp, isidle, maxj);
 		fqs_state = RCU_FORCE_QS;
 	} else {
 		/* Handle dyntick-idle and offline CPUs. */

kernel/rcutree.h +2 -2

index 1602c21..657b415 100644
@@ -559,8 +559,8 @@ static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
 				  unsigned long *maxj);
 static bool is_sysidle_rcu_state(struct rcu_state *rsp);
 static void rcu_bind_gp_kthread(void);
-static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
-			       unsigned long maxj);
+static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
+				  unsigned long maxj);
 static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp);
 
 #endif /* #ifndef RCU_TREE_NONCORE */

kernel/rcutree_plugin.h +16 -8

index a4d44c3..f65d9c2 100644
@@ -2655,14 +2655,22 @@ static void rcu_sysidle_cancel(void)
  * scan of the CPUs' dyntick-idle state.
  */
 static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
-			       unsigned long maxj)
+			       unsigned long maxj, bool gpkt)
 {
 	if (rsp != rcu_sysidle_state)
 		return;  /* Wrong flavor, ignore. */
-	if (isidle)
-		rcu_sysidle(maxj);    /* More idle! */
-	else
+	if (isidle) {
+		if (gpkt && nr_cpu_ids > RCU_SYSIDLE_SMALL)
+			rcu_sysidle(maxj);    /* More idle! */
+	} else {
 		rcu_sysidle_cancel(); /* Idle is over. */
+	}
+}
+
+static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
+				  unsigned long maxj)
+{
+	rcu_sysidle_report(rsp, isidle, maxj, true);
 }
 
 /* Callback and function for forcing an RCU grace period. */

@@ -2713,7 +2721,8 @@ bool rcu_sys_is_idle(void)
 				if (!isidle)
 					break;
 			}
-			rcu_sysidle_report(rcu_sysidle_state, isidle, maxj);
+			rcu_sysidle_report(rcu_sysidle_state,
+					   isidle, maxj, false);
 			oldrss = rss;
 			rss = ACCESS_ONCE(full_sysidle_state);
 		}

@@ -2776,8 +2785,8 @@ static void rcu_bind_gp_kthread(void)
 {
 }
 
-static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
-			       unsigned long maxj)
+static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
+				  unsigned long maxj)
 {
 }
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 29 lines · Paul E. McKenney

Quoted 5 lines · Frederic Weisbecker

I'm missing a key here.

Let's imagine that the timekeeper has finally set full_sysidle_state = RCU_SYSIDLE_FULL_NOTED with cmpxchg, what guarantees that this CPU is not seeing a stale RCU_SYSIDLE_SHORT value for example?

Good question! Let's see if I have a reasonable answer. ;-)

I am going to start with the large-CPU case, so that the state is advanced only by the grace-period kthread.

1. Case 1: the timekeeper CPU invoked rcu_sysidle_force_exit().
In this case, this is the same CPU that set full_sysidle_state to RCU_SYSIDLE_FULL_NOTED, so it is guaranteed not to see a stale value.

2. Case 2: Some CPU came out of idle, and invoked rcu_sysidle_exit().
In this case, if this CPU reads a RCU_SYSIDLE_SHORT from full_sysidle_state, this read must have come before the cmpxchg() (on some other CPU) that set it to RCU_SYSIDLE_LONG. Because this CPU's read from full_sysidle_state was preceded by an atomic_inc() that updated this CPU's ->dynticks_idle, that update must also precede the cmpxchg() that set full_sysidle_state to RCU_SYSIDLE_LONG. Because the state advancing is done from within a single thread, the subsequent scan is guaranteed to see the first CPU's update of ->dynticks_idle, and will therefore refrain from advancing full_sysidle_state to RCU_SYSIDLE_FULL.

Quoted 3 lines

This will in turn prevent the timekeeping thread from advancing the state to RCU_SYSIDLE_FULL_NOTED, so this scenario cannot happen.

Ok, so IIUC the safety is guaranteed in the following ordering:

CPU 0 CPU 1

idle = 1 smp_mb()
//for each cpu
if (atomic_read(rdp(1)->dyntick_idle) & 1) atomic_inc(rdp->dyntick_idle)
idle = 0 smp_mb()

if (idle)
cmpxchg(full_sysidle_state, SHORT, LONG) while (full_sysidle_state > SHORT)
//reset with cmpxchg

So it's like:

CPU 0 CPU 1

read I write I
smp_mb() smp_mb()
cmpxchg S read S

I still can't find what guarantees we don't read a value in CPU 1 that is way below what we want.

Quoted 4 lines

Unfortunately, the reasoning in #2 above does not hold in the small-CPU case because there is the possibility of both the timekeeping CPU and the RCU grace-period kthread concurrently advancing the state machine. This would be bad, good catch!!!

It's not like I spotted anything myself but you're welcome :)

Quoted 4 lines

The patch below (untested) is an attempt to fix this. If it actually works, I will merge it in with 6/7.

Anything else I missed? ;-)

Well I guess I'll wait one more night before trying to understand the below ;)

Thanks!

Quoted 93 lines

Thanx, Paul

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

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

kernel/rcutree.c +1 -1

index aa3f525..fe83085 100644
@@ -1364,7 +1364,7 @@ int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in)
 		}
 		force_qs_rnp(rsp, dyntick_save_progress_counter,
 			     &isidle, &maxj);
-		rcu_sysidle_report(rsp, isidle, maxj);
+		rcu_sysidle_report_gp(rsp, isidle, maxj);
 		fqs_state = RCU_FORCE_QS;
 	} else {
 		/* Handle dyntick-idle and offline CPUs. */

kernel/rcutree.h +2 -2

index 1602c21..657b415 100644
@@ -559,8 +559,8 @@ static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
 				  unsigned long *maxj);
 static bool is_sysidle_rcu_state(struct rcu_state *rsp);
 static void rcu_bind_gp_kthread(void);
-static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
-			       unsigned long maxj);
+static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
+				  unsigned long maxj);
 static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp);
 
 #endif /* #ifndef RCU_TREE_NONCORE */

kernel/rcutree_plugin.h +16 -8

index a4d44c3..f65d9c2 100644
@@ -2655,14 +2655,22 @@ static void rcu_sysidle_cancel(void)
  * scan of the CPUs' dyntick-idle state.
  */
 static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
-			       unsigned long maxj)
+			       unsigned long maxj, bool gpkt)
 {
 	if (rsp != rcu_sysidle_state)
 		return;  /* Wrong flavor, ignore. */
-	if (isidle)
-		rcu_sysidle(maxj);    /* More idle! */
-	else
+	if (isidle) {
+		if (gpkt && nr_cpu_ids > RCU_SYSIDLE_SMALL)
+			rcu_sysidle(maxj);    /* More idle! */
+	} else {
 		rcu_sysidle_cancel(); /* Idle is over. */
+	}
+}
+
+static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
+				  unsigned long maxj)
+{
+	rcu_sysidle_report(rsp, isidle, maxj, true);
 }
 
 /* Callback and function for forcing an RCU grace period. */

@@ -2713,7 +2721,8 @@ bool rcu_sys_is_idle(void)
 				if (!isidle)
 					break;
 			}
-			rcu_sysidle_report(rcu_sysidle_state, isidle, maxj);
+			rcu_sysidle_report(rcu_sysidle_state,
+					   isidle, maxj, false);
 			oldrss = rss;
 			rss = ACCESS_ONCE(full_sysidle_state);
 		}

@@ -2776,8 +2785,8 @@ static void rcu_bind_gp_kthread(void)
 {
 }
 
-static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
-			       unsigned long maxj)
+static void rcu_sysidle_report_gp(struct rcu_state *rsp, int isidle,
+				  unsigned long maxj)
 {
 }
 
 
--

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 8 lines · Frederic Weisbecker

So it's like:

CPU 0 CPU 1

read I write I
smp_mb() smp_mb()
cmpxchg S read S

Quoted 2 lines

I still can't find what guarantees we don't read a value in CPU 1 that is way below what we want.

One key point is that there is a second cycle from LONG to FULL.

(Not saying that there is not a bug -- there might well be. In fact, I am starting to think that I need to do another Promela model...

Quoted 7 lines

Quoted 5 lines

Unfortunately, the reasoning in #2 above does not hold in the small-CPU case because there is the possibility of both the timekeeping CPU and the RCU grace-period kthread concurrently advancing the state machine. This would be bad, good catch!!!

It's not like I spotted anything myself but you're welcome :)

I will take them any way I can get them. ;-)

Quoted 5 lines

Quoted 4 lines

The patch below (untested) is an attempt to fix this. If it actually works, I will merge it in with 6/7.

Anything else I missed? ;-)

Quoted 2 lines

Well I guess I'll wait one more night before trying to understand the below ;)

The key point is that the added check means that either the timekeeping CPU is advancing the state machine (if there are few CPUs) or the RCU grace-period kthread is (if there are many CPUs), but never both. Or that is the intent, anyway!

Quoted 12 lines · Paul E. McKenney

Quoted 10 lines · Frederic Weisbecker

So it's like:

CPU 0 CPU 1

read I write I
smp_mb() smp_mb()
cmpxchg S read S

I still can't find what guarantees we don't read a value in CPU 1 that is way below what we want.

Quoted 4 lines

One key point is that there is a second cycle from LONG to FULL.

(Not saying that there is not a bug -- there might well be. In fact, I am starting to think that I need to do another Promela model...

Now I'm very confused :)

I'm far from being a specialist on these matters but I would really love to understand this patchset. Is there any documentation somewhere I can read that could help, something about cycles of committed memory or something?

Quoted 14 lines

Quoted 6 lines

Quoted 4 lines

Unfortunately, the reasoning in #2 above does not hold in the small-CPU case because there is the possibility of both the timekeeping CPU and the RCU grace-period kthread concurrently advancing the state machine. This would be bad, good catch!!!

It's not like I spotted anything myself but you're welcome :)

I will take them any way I can get them. ;-)

Quoted 5 lines

Quoted 4 lines

The patch below (untested) is an attempt to fix this. If it actually works, I will merge it in with 6/7.

Anything else I missed? ;-)

Quoted 7 lines

Quoted 2 lines

Well I guess I'll wait one more night before trying to understand the below ;)

The key point is that the added check means that either the timekeeping CPU is advancing the state machine (if there are few CPUs) or the RCU grace-period kthread is (if there are many CPUs), but never both. Or that is the intent, anyway!

Yeah got that.

Thanks!

Quoted 15 lines · Frederic Weisbecker

Quoted 14 lines · Paul E. McKenney

Quoted 10 lines · Frederic Weisbecker

So it's like:

CPU 0 CPU 1

read I write I
smp_mb() smp_mb()
cmpxchg S read S

I still can't find what guarantees we don't read a value in CPU 1 that is way below what we want.

One key point is that there is a second cycle from LONG to FULL.

Quoted 4 lines

Quoted 2 lines

(Not saying that there is not a bug -- there might well be. In fact, I am starting to think that I need to do another Promela model...

Now I'm very confused :)

To quote a Nobel Laureate who presented at an ISEF here in Portland some years back, "Confusion is the most productive state of mind." ;-)

Quoted 4 lines

I'm far from being a specialist on these matters but I would really love to understand this patchset. Is there any documentation somewhere I can read that could help, something about cycles of committed memory or something?

Documentation/memory-barriers.txt should suffice for this. If you want more rigor, http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

But memory-barrier pairing suffices here. Here is case 2 from my earlier email in more detail. The comments with capital letters mark important memory barriers, some of which are buried in atomic operations.

1. Some CPU coming out of idle:

o rcu_sysidle_exit():

	smp_mb__before_atomic_inc();
	atomic_inc(&rdtp->dynticks_idle);
	smp_mb__after_atomic_inc(); /* A */

o rcu_sysidle_force_exit():

	oldstate = ACCESS_ONCE(full_sysidle_state);

2. RCU GP kthread:

o rcu_sysidle():

	cmpxchg(&full_sysidle_state, RCU_SYSIDLE_SHORT, RCU_SYSIDLE_LONG);
		/* B */

o rcu_sysidle_check_cpu():

	cur = atomic_read(&rdtp->dynticks_idle);

Memory barrier A pairs with memory barrier B, so that if #1's load from full_sysidle_state sees RCU_SYSIDLE_SHORT, we know that #1's atomic_inc() must be visible to #2's atomic_read(). This will cause #2 to recognize that the CPU came out of idle, which will in turn cause it to invoke rcu_sysidle_cancel() instead of rcu_sysidle(), resulting in full_sysidle_state being set to RCU_SYSIDLE_NOT.

Quoted 19 lines · Paul E. McKenney

Quoted 18 lines · Frederic Weisbecker

Quoted 16 lines · Paul E. McKenney

Quoted 10 lines · Frederic Weisbecker

So it's like:

CPU 0 CPU 1

read I write I
smp_mb() smp_mb()
cmpxchg S read S

I still can't find what guarantees we don't read a value in CPU 1 that is way below what we want.

One key point is that there is a second cycle from LONG to FULL.

(Not saying that there is not a bug -- there might well be. In fact, I am starting to think that I need to do another Promela model...

Quoted 4 lines

Quoted 1 line

Now I'm very confused :)

To quote a Nobel Laureate who presented at an ISEF here in Portland some years back, "Confusion is the most productive state of mind." ;-)

Then I must be a very productive guy!

Quoted 33 lines

Quoted 3 lines

I'm far from being a specialist on these matters but I would really love to understand this patchset. Is there any documentation somewhere I can read that could help, something about cycles of committed memory or something?

Documentation/memory-barriers.txt should suffice for this. If you want more rigor, http://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test7.pdf

But memory-barrier pairing suffices here. Here is case 2 from my earlier email in more detail. The comments with capital letters mark important memory barriers, some of which are buried in atomic operations.

1. Some CPU coming out of idle:

o rcu_sysidle_exit():

	smp_mb__before_atomic_inc();
	atomic_inc(&rdtp->dynticks_idle);
	smp_mb__after_atomic_inc(); /* A */

o rcu_sysidle_force_exit():

	oldstate = ACCESS_ONCE(full_sysidle_state);

2. RCU GP kthread:

o rcu_sysidle():

	cmpxchg(&full_sysidle_state, RCU_SYSIDLE_SHORT, RCU_SYSIDLE_LONG);
		/* B */

o rcu_sysidle_check_cpu():

Quoted 8 lines

	cur = atomic_read(&rdtp->dynticks_idle);

Memory barrier A pairs with memory barrier B, so that if #1's load from full_sysidle_state sees RCU_SYSIDLE_SHORT, we know that #1's atomic_inc() must be visible to #2's atomic_read(). This will cause #2 to recognize that the CPU came out of idle, which will in turn cause it to invoke rcu_sysidle_cancel() instead of rcu_sysidle(), resulting in full_sysidle_state being set to RCU_SYSIDLE_NOT.

Ok I get it for that direction.
Now imagine CPU 0 is the RCU GP kthread (#2) and CPU 1 is idle and stays so.

CPU 0 then rounds and see that all CPUs are idle, until it finally sets up RCU_SYSIDLE_SHORT_FULL and finally goes to sleep.

Then CPU 1 wakes up. It really has to see a value above RCU_SYSIDLE_SHORT otherwise it won't do the cmpxchg and see the FULL_NOTED that makes it send the IPI.

What provides the guarantee that CPU 1 sees a value above RCU_SYSIDLE_SHORT? Not on the cmpxchg but when it first dereference with ACCESS_ONCE.

Quoted 38 lines · Frederic Weisbecker

Quoted 21 lines · Paul E. McKenney

1. Some CPU coming out of idle:

o rcu_sysidle_exit():

	smp_mb__before_atomic_inc();
	atomic_inc(&rdtp->dynticks_idle);
	smp_mb__after_atomic_inc(); /* A */

o rcu_sysidle_force_exit():

	oldstate = ACCESS_ONCE(full_sysidle_state);

2. RCU GP kthread:

o rcu_sysidle():

	cmpxchg(&full_sysidle_state, RCU_SYSIDLE_SHORT, RCU_SYSIDLE_LONG);
		/* B */

o rcu_sysidle_check_cpu():

Quoted 8 lines

	cur = atomic_read(&rdtp->dynticks_idle);

Memory barrier A pairs with memory barrier B, so that if #1's load from full_sysidle_state sees RCU_SYSIDLE_SHORT, we know that #1's atomic_inc() must be visible to #2's atomic_read(). This will cause #2 to recognize that the CPU came out of idle, which will in turn cause it to invoke rcu_sysidle_cancel() instead of rcu_sysidle(), resulting in full_sysidle_state being set to RCU_SYSIDLE_NOT.

Ok I get it for that direction.
Now imagine CPU 0 is the RCU GP kthread (#2) and CPU 1 is idle and stays so.

CPU 0 then rounds and see that all CPUs are idle, until it finally sets up RCU_SYSIDLE_SHORT_FULL and finally goes to sleep.

Quoted 6 lines

Then CPU 1 wakes up. It really has to see a value above RCU_SYSIDLE_SHORT otherwise it won't do the cmpxchg and see the FULL_NOTED that makes it send the IPI.

What provides the guarantee that CPU 1 sees a value above RCU_SYSIDLE_SHORT? Not on the cmpxchg but when it first dereference with ACCESS_ONCE.

The trick is that CPU 0 will have scanned, moved to RCU_SYSIDLE_SHORT, scanned, moved to RCU_SYSIDLE_LONG, then scanned again before moving to RCU_SYSIDLE_FULL. Given CPU 1 has been idle all this time, CPU 0 will have read its ->dynticks_idle counter on each scan and seen it having an even value. When CPU 1 comes out of idle, it will atomically increment its ->dyntick_idle(), which will happen after CPU 0's read of ->dyntick_idle() during its last scan.

Because of the memory-barrier pairing above, this means that CPU 1's read from full_sysidle_state must follow the cmpxchg() that set full_sysidle_state to RCU_SYSIDLE_LONG (though not necessarily the two later cmpxchg()s that set it to RCU_SYSIDLE_FULL and RCU_SYSIDLE_FULL_NOTED). But because RCU_SYSIDLE_LONG is greater than RCU_SYSIDLE_SHORT, CPU 1 will take action to end the idle period.

Quoted 54 lines · Paul E. McKenney

Quoted 38 lines · Frederic Weisbecker

Quoted 21 lines · Paul E. McKenney

1. Some CPU coming out of idle:

o rcu_sysidle_exit():

	smp_mb__before_atomic_inc();
	atomic_inc(&rdtp->dynticks_idle);
	smp_mb__after_atomic_inc(); /* A */

o rcu_sysidle_force_exit():

	oldstate = ACCESS_ONCE(full_sysidle_state);

2. RCU GP kthread:

o rcu_sysidle():

	cmpxchg(&full_sysidle_state, RCU_SYSIDLE_SHORT, RCU_SYSIDLE_LONG);
		/* B */

o rcu_sysidle_check_cpu():

Quoted 8 lines

	cur = atomic_read(&rdtp->dynticks_idle);

Memory barrier A pairs with memory barrier B, so that if #1's load from full_sysidle_state sees RCU_SYSIDLE_SHORT, we know that #1's atomic_inc() must be visible to #2's atomic_read(). This will cause #2 to recognize that the CPU came out of idle, which will in turn cause it to invoke rcu_sysidle_cancel() instead of rcu_sysidle(), resulting in full_sysidle_state being set to RCU_SYSIDLE_NOT.

Ok I get it for that direction.
Now imagine CPU 0 is the RCU GP kthread (#2) and CPU 1 is idle and stays so.

CPU 0 then rounds and see that all CPUs are idle, until it finally sets up RCU_SYSIDLE_SHORT_FULL and finally goes to sleep.

Quoted 6 lines

Then CPU 1 wakes up. It really has to see a value above RCU_SYSIDLE_SHORT otherwise it won't do the cmpxchg and see the FULL_NOTED that makes it send the IPI.

What provides the guarantee that CPU 1 sees a value above RCU_SYSIDLE_SHORT? Not on the cmpxchg but when it first dereference with ACCESS_ONCE.

The trick is that CPU 0 will have scanned, moved to RCU_SYSIDLE_SHORT, scanned, moved to RCU_SYSIDLE_LONG, then scanned again before moving to RCU_SYSIDLE_FULL. Given CPU 1 has been idle all this time, CPU 0 will have read its ->dynticks_idle counter on each scan and seen it having an even value. When CPU 1 comes out of idle, it will atomically increment its ->dyntick_idle(), which will happen after CPU 0's read of ->dyntick_idle() during its last scan.

Quoted 6 lines

Because of the memory-barrier pairing above, this means that CPU 1's read from full_sysidle_state must follow the cmpxchg() that set full_sysidle_state to RCU_SYSIDLE_LONG (though not necessarily the two later cmpxchg()s that set it to RCU_SYSIDLE_FULL and RCU_SYSIDLE_FULL_NOTED). But because RCU_SYSIDLE_LONG is greater than RCU_SYSIDLE_SHORT, CPU 1 will take action to end the idle period.

Lets summarize the last sequence, the following happens ordered by time:

        CPU 0                          CPU 1

     cmpxchg(&full_sysidle_state,
             RCU_SYSIDLE_SHORT,
             RCU_SYSIDLE_LONG);

     smp_mb() //cmpxchg

     atomic_read(rdtp(1)->dynticks_idle)

     //CPU 0 goes to sleep
                                       //CPU 1 wakes up
                                       atomic_inc(rdtp(1)->dynticks_idle)

                                       smp_mb()

                                       ACCESS_ONCE(full_sysidle_state)

Are you suggesting that because the CPU 1 executes its atomic_inc() _after_ (in terms of absolute time) the atomic_read of CPU 0, the ordering settled in both sides guarantees that the value read from CPU 1 is the one from the cmpxchg that precedes the atomic_read, or FULL or FULL_NOTED that happen later.

If so that's a big lesson for me.

Quoted 26 lines

Lets summarize the last sequence, the following happens ordered by time:

        CPU 0                          CPU 1

     cmpxchg(&full_sysidle_state,
             RCU_SYSIDLE_SHORT,
             RCU_SYSIDLE_LONG);

     smp_mb() //cmpxchg

     atomic_read(rdtp(1)->dynticks_idle)

     //CPU 0 goes to sleep
                                       //CPU 1 wakes up
                                       atomic_inc(rdtp(1)->dynticks_idle)

                                       smp_mb()

                                       ACCESS_ONCE(full_sysidle_state)

Are you suggesting that because the CPU 1 executes its atomic_inc() _after_ (in terms of absolute time) the atomic_read of CPU 0, the ordering settled in both sides guarantees that the value read from CPU 1 is the one from the cmpxchg that precedes the atomic_read, or FULL or FULL_NOTED that happen later.

Quoted 1 line

If so that's a big lesson for me.

It is not absolute time that matters. Instead, it is the fact that CPU 0, when reading from ->dynticks_idle, read the old value before the atomic_inc(). Therefore, anything CPU 0 did before that memory barrier preceding CPU 0's read must come before anything CPU 1 did after that memory barrier following the atomic_inc(). For this to work, there must be some access to the same variable on each CPU.

Or, if you must think in terms of time, you need a separate independent timeline for each variable, with no direct mapping from one timeline to another, except resulting from memory-barrier interactions.

Thanx, Paul

Quoted 26 lines · Paul E. McKenney

Quoted 26 lines

Lets summarize the last sequence, the following happens ordered by time:

        CPU 0                          CPU 1

     cmpxchg(&full_sysidle_state,
             RCU_SYSIDLE_SHORT,
             RCU_SYSIDLE_LONG);

     smp_mb() //cmpxchg

     atomic_read(rdtp(1)->dynticks_idle)

     //CPU 0 goes to sleep
                                       //CPU 1 wakes up
                                       atomic_inc(rdtp(1)->dynticks_idle)

                                       smp_mb()

                                       ACCESS_ONCE(full_sysidle_state)

Are you suggesting that because the CPU 1 executes its atomic_inc() _after_ (in terms of absolute time) the atomic_read of CPU 0, the ordering settled in both sides guarantees that the value read from CPU 1 is the one from the cmpxchg that precedes the atomic_read, or FULL or FULL_NOTED that happen later.

Quoted 8 lines

Quoted 1 line

If so that's a big lesson for me.

It is not absolute time that matters. Instead, it is the fact that CPU 0, when reading from ->dynticks_idle, read the old value before the atomic_inc(). Therefore, anything CPU 0 did before that memory barrier preceding CPU 0's read must come before anything CPU 1 did after that memory barrier following the atomic_inc(). For this to work, there must be some access to the same variable on each CPU.

Aren't we in the following situation?

CPU 0 CPU 1

STORE A STORE B
LOAD B LOAD A

If so and referring to your perfbook, this is an "ears to mouth" situation. And it seems to describe there is no strong guarantee in that situation.

Quoted 6 lines

Or, if you must think in terms of time, you need a separate independent timeline for each variable, with no direct mapping from one timeline to another, except resulting from memory-barrier interactions.

Thanx, Paul

Quoted 38 lines · Frederic Weisbecker

Quoted 26 lines · Paul E. McKenney

Quoted 26 lines

Lets summarize the last sequence, the following happens ordered by time:

        CPU 0                          CPU 1

     cmpxchg(&full_sysidle_state,
             RCU_SYSIDLE_SHORT,
             RCU_SYSIDLE_LONG);

     smp_mb() //cmpxchg

     atomic_read(rdtp(1)->dynticks_idle)

     //CPU 0 goes to sleep
                                       //CPU 1 wakes up
                                       atomic_inc(rdtp(1)->dynticks_idle)

                                       smp_mb()

                                       ACCESS_ONCE(full_sysidle_state)

Are you suggesting that because the CPU 1 executes its atomic_inc() _after_ (in terms of absolute time) the atomic_read of CPU 0, the ordering settled in both sides guarantees that the value read from CPU 1 is the one from the cmpxchg that precedes the atomic_read, or FULL or FULL_NOTED that happen later.

Quoted 8 lines

Quoted 1 line

If so that's a big lesson for me.

It is not absolute time that matters. Instead, it is the fact that CPU 0, when reading from ->dynticks_idle, read the old value before the atomic_inc(). Therefore, anything CPU 0 did before that memory barrier preceding CPU 0's read must come before anything CPU 1 did after that memory barrier following the atomic_inc(). For this to work, there must be some access to the same variable on each CPU.

Aren't we in the following situation?

Quoted 8 lines

CPU 0 CPU 1

STORE A STORE B
LOAD B LOAD A

If so and referring to your perfbook, this is an "ears to mouth" situation. And it seems to describe there is no strong guarantee in that situation.

"Yes" to the first, but on modern hardware, "no" to the second. The key paragraph is Section 12.2.4.5:

The following pairings from Table 12.1 can be used on modern hardware, but might fail on some systems that were produced in the 1990s. However, these can safely be used on all mainstream hardware introduced since the year 2000.

That said, you are not the first to be confused by this, so I might need to rework this section to make it clear that each can in fact be used on modern hardware.

If you happen to have an old Sequent NUMA-Q or Symmetry box lying around, things are a bit different. On the other hand, I don't believe that any of these old boxes are still running Linux. (Hey, I am as sentimental as the next guy, but there are limits!)

I updated this section and pushed it, please let me know if this helps!

Quoted 51 lines · Paul E. McKenney

Quoted 38 lines · Frederic Weisbecker

Quoted 26 lines · Paul E. McKenney

Quoted 26 lines

Lets summarize the last sequence, the following happens ordered by time:

        CPU 0                          CPU 1

     cmpxchg(&full_sysidle_state,
             RCU_SYSIDLE_SHORT,
             RCU_SYSIDLE_LONG);

     smp_mb() //cmpxchg

     atomic_read(rdtp(1)->dynticks_idle)

     //CPU 0 goes to sleep
                                       //CPU 1 wakes up
                                       atomic_inc(rdtp(1)->dynticks_idle)

                                       smp_mb()

                                       ACCESS_ONCE(full_sysidle_state)

Are you suggesting that because the CPU 1 executes its atomic_inc() _after_ (in terms of absolute time) the atomic_read of CPU 0, the ordering settled in both sides guarantees that the value read from CPU 1 is the one from the cmpxchg that precedes the atomic_read, or FULL or FULL_NOTED that happen later.

Quoted 8 lines

Quoted 1 line

If so that's a big lesson for me.

It is not absolute time that matters. Instead, it is the fact that CPU 0, when reading from ->dynticks_idle, read the old value before the atomic_inc(). Therefore, anything CPU 0 did before that memory barrier preceding CPU 0's read must come before anything CPU 1 did after that memory barrier following the atomic_inc(). For this to work, there must be some access to the same variable on each CPU.

Aren't we in the following situation?

Quoted 8 lines

CPU 0 CPU 1

STORE A STORE B
LOAD B LOAD A

If so and referring to your perfbook, this is an "ears to mouth" situation. And it seems to describe there is no strong guarantee in that situation.

"Yes" to the first, but on modern hardware, "no" to the second. The key paragraph is Section 12.2.4.5:

Quoted 4 lines

The following pairings from Table 12.1 can be used on modern hardware, but might fail on some systems that were produced in the 1990s. However, these can safely be used on all mainstream hardware introduced since the year 2000.

Right I missed that!

Quoted 10 lines

That said, you are not the first to be confused by this, so I might need to rework this section to make it clear that each can in fact be used on modern hardware.

If you happen to have an old Sequent NUMA-Q or Symmetry box lying around, things are a bit different. On the other hand, I don't believe that any of these old boxes are still running Linux. (Hey, I am as sentimental as the next guy, but there are limits!)

I updated this section and pushed it, please let me know if this helps!

I don't know because I encountered some troubles to build it, I'm seeing thousand lines like this:

Name "main::opt_help" used only once: possible typo at /usr/bin/a2ping line 534. /usr/bin/a2ping: not a GS output from gs -dSAFER ./cartoons/whippersnapper300.eps -> ./cartoons/whippersnapper300.pdf Name "main::opt_extra" used only once: possible typo at /usr/bin/a2ping line 546. Name "main::opt_help" used only once: possible typo at /usr/bin/a2ping line 534. /usr/bin/a2ping: not a GS output from gs -dSAFER
make: *** [embedfonts] Error 1

Anyway I looked at the diff and it looks indeed clearer, thanks!

So back to the issue, I think we made nice progresses with my rusty brain ;-) But just to be clear, I'm pasting that again for just a few precisions:

        CPU 0                                CPU 1

       cmpxchg(&full_sysidle_state,          //CPU 1 wakes up
                RCU_SYSIDLE_SHORT,           atomic_inc(rdtp(1)->dynticks_idle)
                RCU_SYSIDLE_LONG);

       smp_mb() //cmpxchg                    smp_mb()
       atomic_read(rdtp(1)->dynticks_idle)   ACCESS_ONCE(full_sysidle_state
      //CPU 0 goes to sleep

1) If CPU 0 sets RCU_SYSIDLE_LONG and sees dynticks_idle as even, do we have the _guarantee_ that later CPU 1 sees full_sysidle_state == RCU_SYSIDLE_LONG (or any later full_sysidle_state value) due to the connection between atomic_read / atomic_inc and the barriers that come along?

2) You taught me once that barrier != memory committed, and it has been one of the hardest trauma in my life. How can we be sure that CPU 1 sees memory as committed from CPU 0? The only fact that we read an even value from CPU 0 is enough for the connection between the atomic_read() and atomic_inc() and all the barriers that come along?

3) In your book it says: "recent hardware would guarantee that at least one of the loads saw the value stored by the corresponding store".

At least one? So in our example, CPU 0 could see dynticks_idle as even (success to see some prior store done in CPU 1) but following the above statement reasoning, CPU 1 might not see the corresponding store and see, for example RCU_SYSIDLE_SHORT?

I'm really sorry to bother you with that... :-(

Quoted 10 lines · Frederic Weisbecker

I don't know because I encountered some troubles to build it, I'm seeing thousand lines like this:

Name "main::opt_help" used only once: possible typo at /usr/bin/a2ping line 534. /usr/bin/a2ping: not a GS output from gs -dSAFER ./cartoons/whippersnapper300.eps -> ./cartoons/whippersnapper300.pdf Name "main::opt_extra" used only once: possible typo at /usr/bin/a2ping line 546. Name "main::opt_help" used only once: possible typo at /usr/bin/a2ping line 534. /usr/bin/a2ping: not a GS output from gs -dSAFER
make: *** [embedfonts] Error 1

Strange. My version of a2ping is Ubuntu 12.04's:

a2ping.pl 2.77p, 2006-11-15 -- Written by <[email protected]> from April 2003.

You have something more recent?

Quoted 15 lines

So back to the issue, I think we made nice progresses with my rusty brain ;-) But just to be clear, I'm pasting that again for just a few precisions:

        CPU 0                                CPU 1

       cmpxchg(&full_sysidle_state,          //CPU 1 wakes up
                RCU_SYSIDLE_SHORT,           atomic_inc(rdtp(1)->dynticks_idle)
                RCU_SYSIDLE_LONG);

       smp_mb() //cmpxchg                    smp_mb()
       atomic_read(rdtp(1)->dynticks_idle)   ACCESS_ONCE(full_sysidle_state
      //CPU 0 goes to sleep

Quoted 3 lines

1) If CPU 0 sets RCU_SYSIDLE_LONG and sees dynticks_idle as even, do we have the _guarantee_ that later CPU 1 sees full_sysidle_state == RCU_SYSIDLE_LONG (or any later full_sysidle_state value) due to the connection between atomic_read / atomic_inc and the barriers that come along?

No, we do not have this guarantee.

What happens instead is that CPU 0 later sets RCU_SYSIDLE_FULL after having again seen CPU 1's ->dynticks_idle having an even (idle) value. If CPU 1 later increments its ->dynticks_idle to an odd (non-idle) value, then does a memory barrier, and then reads full_sysidle_state, then CPU 1 is guaranteed to see RCU_SYSIDLE_LONG. Please note that CPU 1 is -not- obligated to see RCU_SYSIDLE_FULL, much less RCU_SYSIDLE_NOTED.

However, when CPU 1 does an atomic operation on full_sysidle_state that returns the old value, CPU 1 is guaranteed to get the most recent state. (Without this guarantee, we could have a cactus state of values for full_sysidle_state, which might make alternate-universe fans happy, but which would be really hard to program.)

This is why we need an RCU_SYSIDLE_LONG state in addition to RCU_SYSIDLE_SHORT and RCU_SYSIDLE_FULL.

Quoted 4 lines

2) You taught me once that barrier != memory committed, and it has been one of the hardest trauma in my life. How can we be sure that CPU 1 sees memory as committed from CPU 0? The only fact that we read an even value from CPU 0 is enough for the connection between the atomic_read() and atomic_inc() and all the barriers that come along?

My condolences on the trauma! Now, if you will look directly into the light... ;-)

We cannot be sure. All we can be sure of is the memory-barrier relationships and coherence order of each individual memory location.

The basic memory-barrier relationships are of the following form:

	CPU 0		CPU 1
	ref A		ref C
	smp_mb()	smp_mb()
	ref B		ref D

If the results of these references show that ref C saw the results of ref B, then you know that ref D is guaranteed to see the results of ref A. There are no guarantees on time delay. At least there are no guarantees on time delay that the various hardware vendors are willing to tell us about.

For the coherence order of each individual memory location, let's focus on full_sysidle_state. Suppose that CPU 0 uses cmpxchg() to advance it from RCU_SYSIDLE_NOT to RCU_SYSIDLE_SHORT to RCU_SYSIDLE_LONG to RCU_SYSIDLE_FULL and finally to RCU_SYSIDLE_NOTED. When CPU 1 uses a normal load to access full_sysidle_state, it is only guaranteed to see RCU_SYSIDLE_LONG, because RCU_SYSIDLE_LONG is the value that CPU 0 last wrote prior to an access of CPU 1's ->dynticks_idle counter.

However, CPU 1 then uses a cmpxchg() loop to change the value of full_sysidle_state back to RCU_SYSIDLE_NOT in rcu_sysidle_force_exit(). At this point, CPU 1 cannot be allowed to see an old value of full_sysidle_state, because this would contradict the cmpxchg() return values that CPU 0 saw in rcu_sysidle(). Therefore, the cmpxchg() in rcu_sysidle_force_exit() is obligated to return the most recent value.

How does the hardware do this? Well, for loads, the hardware can look just in its own cache, which might well contain an outdated value. In contrast, for cmpxchg(), the CPU must invalidate full_sysidle_state from all other caches, which ensures that the most recent value becomes available.

So one way to guarantee most-recent results is to always
use atomic instructions to access the variables, for example, atomic_add(&full_sysidle_state, 0) instead of a simple load instruction. Might be some performance degradation, but you know what they way about free lunches. ;-)

Quoted 7 lines

3) In your book it says: "recent hardware would guarantee that at least one of the loads saw the value stored by the corresponding store".

At least one? So in our example, CPU 0 could see dynticks_idle as even (success to see some prior store done in CPU 1) but following the above statement reasoning, CPU 1 might not see the corresponding store and see, for example RCU_SYSIDLE_SHORT?

Ah, yes, the kernel of Dekker's algorithm. ;-)

	CPU 0		CPU 1

	A=1		B=1
	smp_mb()	smp_mb()
	r1=B		r2=A

The initial values of both A and B are zero.

And yes, this does have the same form as the manipulations of full_sysidle_state and ->dynticks_idle.

Let's suppose that neither CPU saw the results of either CPU's store. The after both CPUs finished, we would have r1==0&&r2==0. Let's start with the r1==0.

The r1==0 means that CPU 0 loaded from B before CPU 1 stored to B:
After all, otherwise, we would have r1==1. But because of memory-barrier pairing, this means that CPU 1's load from A must see the results of CPU 0's store to A, and therefore r2==1.

The procedure starting with r2==0 follows the same line of reasoning. Therefore, r1==0&&r2==0 cannot happen, which implies that at least one of the CPU's loads must see the other CPU's store.

Quoted 2 lines

I'm really sorry to bother you with that... :-(

Absolutely not a problem! In fact, the above discussion is now yet another infamous Quick Quiz in perfbook. ;-)

Thanx, Paul