rcu: direct algorithmic SRCU implementation

The current implementation of synchronize_srcu_expedited() can cause severe OS jitter due to its use of synchronize_sched(), which in turn invokes try_stop_cpus(), which causes each CPU to be sent an IPI. This can result in severe performance degradation for real-time workloads and especially for short-interation-length HPC workloads. Furthermore, because only one instance of try_stop_cpus() can be making forward progress at a given time, only one instance of synchronize_srcu_expedited() can make forward progress at a time, even if they are all operating on distinct srcu_struct structures.

This commit, inspired by an earlier implementation by Peter Zijlstra
(https://lkml.org/lkml/2012/1/31/211) and by further offline discussions, takes a strictly algorithmic bits-in-memory approach. This has the disadvantage of requiring one explicit memory-barrier instruction in each of srcu_read_lock() and srcu_read_unlock(), but on the other hand completely dispenses with OS jitter and furthermore allows SRCU to be used freely by CPUs that RCU believes to be idle or offline.

The update-side implementation handles the single read-side memory barrier by rechecking the per-CPU counters after summing them and by running through the update-side state machine twice.

This implementation has passed moderate rcutorture testing on both 32-bit x86 and 64-bit Power. A call_srcu() function will be present in a later version of this patch.

kernel/srcu.c +0 -2

@@ -131,10 +214,11 @@ int __srcu_read_lock(struct srcu_struct *sp)
 	int idx;
 
 	preempt_disable();
-	idx = sp->completed & 0x1;
-	barrier();  /* ensure compiler looks -once- at sp->completed. */

Quoted 18 lines · Paul E. McKenney

The current implementation of synchronize_srcu_expedited() can cause severe OS jitter due to its use of synchronize_sched(), which in turn invokes try_stop_cpus(), which causes each CPU to be sent an IPI. This can result in severe performance degradation for real-time workloads and especially for short-interation-length HPC workloads. Furthermore, because only one instance of try_stop_cpus() can be making forward progress at a given time, only one instance of synchronize_srcu_expedited() can make forward progress at a time, even if they are all operating on distinct srcu_struct structures.

This commit, inspired by an earlier implementation by Peter Zijlstra
(https://lkml.org/lkml/2012/1/31/211) and by further offline discussions, takes a strictly algorithmic bits-in-memory approach. This has the disadvantage of requiring one explicit memory-barrier instruction in each of srcu_read_lock() and srcu_read_unlock(), but on the other hand completely dispenses with OS jitter and furthermore allows SRCU to be used freely by CPUs that RCU believes to be idle or offline.

Quoted 3 lines

The update-side implementation handles the single read-side memory barrier by rechecking the per-CPU counters after summing them and by running through the update-side state machine twice.

Yeah, getting rid of that second memory barrier in srcu_read_lock() is pure magic :-)

Quoted 3 lines

This implementation has passed moderate rcutorture testing on both 32-bit x86 and 64-bit Power. A call_srcu() function will be present in a later version of this patch.

Goodness ;-)

Quoted 6 lines

kernel/srcu.c +0 -2

@@ -131,10 +214,11 @@ int __srcu_read_lock(struct srcu_struct *sp)
 	int idx;
 
 	preempt_disable();
-	idx = sp->completed & 0x1;
-	barrier();  /* ensure compiler looks -once- at sp->completed. */

kernel/srcu.c int __srcu_read_lock(struct srcu_struct *sp) · line 224

Quoted 10 lines

kernel/srcu.c +5 -2

-	per_cpu_ptr(sp->per_cpu_ref, smp_processor_id())->c[idx]++;
-	srcu_barrier();  /* ensure compiler won't misorder critical section. */
+	idx = rcu_dereference_index_check(sp->completed,
+					  rcu_read_lock_sched_held()) & 0x1;
+	ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, smp_processor_id())->c[idx]) +=
+		SRCU_USAGE_COUNT + 1;
+	smp_mb(); /* B */  /* Avoid leaking the critical section. */
 	preempt_enable();
 	return idx;
 }

You could use __this_cpu_* muck to shorten some of that.

Acked-by Peter Zijlstra <[email protected]>

Quoted 23 lines · Peter Zijlstra

Quoted 18 lines · Paul E. McKenney

The current implementation of synchronize_srcu_expedited() can cause severe OS jitter due to its use of synchronize_sched(), which in turn invokes try_stop_cpus(), which causes each CPU to be sent an IPI. This can result in severe performance degradation for real-time workloads and especially for short-interation-length HPC workloads. Furthermore, because only one instance of try_stop_cpus() can be making forward progress at a given time, only one instance of synchronize_srcu_expedited() can make forward progress at a time, even if they are all operating on distinct srcu_struct structures.

This commit, inspired by an earlier implementation by Peter Zijlstra
(https://lkml.org/lkml/2012/1/31/211) and by further offline discussions, takes a strictly algorithmic bits-in-memory approach. This has the disadvantage of requiring one explicit memory-barrier instruction in each of srcu_read_lock() and srcu_read_unlock(), but on the other hand completely dispenses with OS jitter and furthermore allows SRCU to be used freely by CPUs that RCU believes to be idle or offline.

Quoted 3 lines

The update-side implementation handles the single read-side memory barrier by rechecking the per-CPU counters after summing them and by running through the update-side state machine twice.

Quoted 8 lines

Yeah, getting rid of that second memory barrier in srcu_read_lock() is pure magic :-)

Quoted 3 lines

This implementation has passed moderate rcutorture testing on both 32-bit x86 and 64-bit Power. A call_srcu() function will be present in a later version of this patch.

Goodness ;-)

Glad you like the magic and the prospect of call_srcu(). ;-)

Quoted 18 lines

Quoted 6 lines

kernel/srcu.c +0 -2

@@ -131,10 +214,11 @@ int __srcu_read_lock(struct srcu_struct *sp)
 	int idx;
 
 	preempt_disable();
-	idx = sp->completed & 0x1;
-	barrier();  /* ensure compiler looks -once- at sp->completed. */

kernel/srcu.c int __srcu_read_lock(struct srcu_struct *sp) · line 224

Quoted 10 lines

kernel/srcu.c +5 -2

-	per_cpu_ptr(sp->per_cpu_ref, smp_processor_id())->c[idx]++;
-	srcu_barrier();  /* ensure compiler won't misorder critical section. */
+	idx = rcu_dereference_index_check(sp->completed,
+					  rcu_read_lock_sched_held()) & 0x1;
+	ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, smp_processor_id())->c[idx]) +=
+		SRCU_USAGE_COUNT + 1;
+	smp_mb(); /* B */  /* Avoid leaking the critical section. */
 	preempt_enable();
 	return idx;
 }

You could use __this_cpu_* muck to shorten some of that.

Ah, so something like this?

	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 
		SRCU_USAGE_COUNT + 1;

Now that you mention it, this does look nicer, applied here and to srcu_read_unlock().

Quoted 2 lines

Acked-by Peter Zijlstra <[email protected]>

Thanx, Paul

Quoted 7 lines

Ah, so something like this?

      ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 
              SRCU_USAGE_COUNT + 1;

Now that you mention it, this does look nicer, applied here and to srcu_read_unlock().

I think Peter refers to __this_cpu_add().

Quoted 5 lines · Mathieu Desnoyers

Quoted 5 lines

Ah, so something like this?

      ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 
              SRCU_USAGE_COUNT + 1;

Quoted 4 lines

Quoted 2 lines

Now that you mention it, this does look nicer, applied here and to srcu_read_unlock().

I think Peter refers to __this_cpu_add().

I'm not sure that implies the ACCESS_ONCE() thing

kernel/srcu.c +49 -2

+/*
+ * To be called from the update side after an index flip.  Returns true
+ * if the modulo sum of the counters is stably zero, false if there is
+ * some possibility of non-zero.
+ */
+static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
-	int sum;
 
-	sum = 0;
+	/*
+	 * Note that srcu_readers_active_idx() can incorrectly return
+	 * zero even though there is a pre-existing reader throughout.
+	 * To see this, suppose that task A is in a very long SRCU
+	 * read-side critical section that started on CPU 0, and that
+	 * no other reader exists, so that the modulo sum of the counters
+	 * is equal to one.  Then suppose that task B starts executing
+	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
+	 * task C starts reading on CPU 0, so that its increment is not
+	 * summed, but finishes reading on CPU 2, so that its decrement
+	 * -is- summed.  Then when task B completes its sum, it will
+	 * incorrectly get zero, despite the fact that task A has been
+	 * in its SRCU read-side critical section the whole time.
+	 *
+	 * We therefore do a validation step should srcu_readers_active_idx()
+	 * return zero.
+	 */
+	if (srcu_readers_active_idx(sp, idx) != 0)
+		return false;
+
+	/*
+	 * Since the caller recently flipped ->completed, we can see at
+	 * most one increment of each CPU's counter from this point
+	 * forward.  The reason for this is that the reader CPU must have
+	 * fetched the index before srcu_readers_active_idx checked
+	 * that CPU's counter, but not yet incremented its counter.
+	 * Its eventual counter increment will follow the read in
+	 * srcu_readers_active_idx(), and that increment is immediately
+	 * followed by smp_mb() B.  Because smp_mb() D is between
+	 * the ->completed flip and srcu_readers_active_idx()'s read,
+	 * that CPU's subsequent load of ->completed must see the new
+	 * value, and therefore increment the counter in the other rank.
+	 */
+	smp_mb(); /* A */
+
+	/*
+	 * Now, we check the ->snap array that srcu_readers_active_idx()
+	 * filled in from the per-CPU counter values.  Since both
+	 * __srcu_read_lock() and __srcu_read_unlock() increment the
+	 * upper bits of the per-CPU counter, an increment/decrement
+	 * pair will change the value of the counter.  Since there is
+	 * only one possible increment, the only way to wrap the counter
+	 * is to have a huge number of counter decrements, which requires

kernel/srcu.c +14 -2

+	 *
+	 * Therefore, if srcu_readers_active_idx() returned zero, and
+	 * none of the counters changed, we know that the zero was the
+	 * correct sum.
+	 *
+	 * Of course, it is possible that a task might be delayed
+	 * for a very long time in __srcu_read_lock() after fetching
+	 * the index but before incrementing its counter.  This
+	 * possibility will be dealt with in __synchronize_srcu().
+	 */
 	for_each_possible_cpu(cpu)
-		sum += per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx];
-	return sum;
+		if (sp->snap[cpu] !=
+		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
+			return false;  /* False zero reading! */
+	return true;
 }

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 54 lines

kernel/srcu.c +49 -2

+/*
+ * To be called from the update side after an index flip.  Returns true
+ * if the modulo sum of the counters is stably zero, false if there is
+ * some possibility of non-zero.
+ */
+static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
-	int sum;
 
-	sum = 0;
+	/*
+	 * Note that srcu_readers_active_idx() can incorrectly return
+	 * zero even though there is a pre-existing reader throughout.
+	 * To see this, suppose that task A is in a very long SRCU
+	 * read-side critical section that started on CPU 0, and that
+	 * no other reader exists, so that the modulo sum of the counters
+	 * is equal to one.  Then suppose that task B starts executing
+	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
+	 * task C starts reading on CPU 0, so that its increment is not
+	 * summed, but finishes reading on CPU 2, so that its decrement
+	 * -is- summed.  Then when task B completes its sum, it will
+	 * incorrectly get zero, despite the fact that task A has been
+	 * in its SRCU read-side critical section the whole time.
+	 *
+	 * We therefore do a validation step should srcu_readers_active_idx()
+	 * return zero.
+	 */
+	if (srcu_readers_active_idx(sp, idx) != 0)
+		return false;
+
+	/*
+	 * Since the caller recently flipped ->completed, we can see at
+	 * most one increment of each CPU's counter from this point
+	 * forward.  The reason for this is that the reader CPU must have
+	 * fetched the index before srcu_readers_active_idx checked
+	 * that CPU's counter, but not yet incremented its counter.
+	 * Its eventual counter increment will follow the read in
+	 * srcu_readers_active_idx(), and that increment is immediately
+	 * followed by smp_mb() B.  Because smp_mb() D is between
+	 * the ->completed flip and srcu_readers_active_idx()'s read,
+	 * that CPU's subsequent load of ->completed must see the new
+	 * value, and therefore increment the counter in the other rank.
+	 */
+	smp_mb(); /* A */
+
+	/*
+	 * Now, we check the ->snap array that srcu_readers_active_idx()
+	 * filled in from the per-CPU counter values.  Since both
+	 * __srcu_read_lock() and __srcu_read_unlock() increment the
+	 * upper bits of the per-CPU counter, an increment/decrement
+	 * pair will change the value of the counter.  Since there is
+	 * only one possible increment, the only way to wrap the counter
+	 * is to have a huge number of counter decrements, which requires

kernel/srcu.c EXPORT_SYMBOL_GPL(init_srcu_struct); · line 156

Quoted 10 lines

kernel/srcu.c +10 -0

+	 * a huge number of tasks and huge SRCU read-side critical-section
+	 * nesting levels, even on 32-bit systems.
+	 *
+	 * All of the ways of confusing the readings require that the scan
+	 * in srcu_readers_active_idx() see the read-side task's decrement,
+	 * but not its increment.  However, between that decrement and
+	 * increment are smb_mb() B and C.  Either or both of these pair
+	 * with smp_mb() A above to ensure that the scan below will see
+	 * the read-side tasks's increment, thus noting a difference in
+	 * the counter values between the two passes.

Hi Paul,

I think the implementation is correct, but the explanation above might be improved. Let's consider the following a scenario, where a reader is migrated between increment of the counter and issuing the memory barrier in the read lock:

A,B,C are readers
D is synchronize_rcu (one flip'n'wait)

CPU A CPU B CPU C CPU D

                                    c[1]++
                                    smp_mb(1)
                                                  read c[0] -> 0
c[0]++
(implicit smp_mb (2))
      -> migrated ->
                    (implicit smp_mb (3))
                    smp_mb (4)
                    smp_mb (5)
                    c[1]--
                                                  read c[1] -> -1
                                                  read c[2] -> 1
                                                  (false 0 sum)
                                                  smp_mb (6)
                                                  re-check each.
                                    c[1]--

re-check: because we observed c[1] == -1, thanks to the implicit memory barriers within thread migration (2 and 3), we can assume that we _will_ observe the updated value of c[0] after smp_mb (6).

The current explanation states that memory barriers 4 and 5, along with 6, are responsible for ensuring that the increment will be observed by the re-check. However, I doubt they have anything to do with it: it's rather the implicit memory barriers in thread migration, along with program order guarantees on writes to the same address, that seems to be the reason why we can do this ordering assumption.

Does it make sense, or shall I get another coffee to wake myself up ? ;)

Thanks,

Mathieu

Quoted 18 lines

kernel/srcu.c +14 -2

+	 *
+	 * Therefore, if srcu_readers_active_idx() returned zero, and
+	 * none of the counters changed, we know that the zero was the
+	 * correct sum.
+	 *
+	 * Of course, it is possible that a task might be delayed
+	 * for a very long time in __srcu_read_lock() after fetching
+	 * the index but before incrementing its counter.  This
+	 * possibility will be dealt with in __synchronize_srcu().
+	 */
 	for_each_possible_cpu(cpu)
-		sum += per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx];
-	return sum;
+		if (sp->snap[cpu] !=
+		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
+			return false;  /* False zero reading! */
+	return true;
 }

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 99 lines · * Mathieu Desnoyers ([email protected]) wrote:

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 54 lines

kernel/srcu.c +49 -2

+/*
+ * To be called from the update side after an index flip.  Returns true
+ * if the modulo sum of the counters is stably zero, false if there is
+ * some possibility of non-zero.
+ */
+static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
-	int sum;
 
-	sum = 0;
+	/*
+	 * Note that srcu_readers_active_idx() can incorrectly return
+	 * zero even though there is a pre-existing reader throughout.
+	 * To see this, suppose that task A is in a very long SRCU
+	 * read-side critical section that started on CPU 0, and that
+	 * no other reader exists, so that the modulo sum of the counters
+	 * is equal to one.  Then suppose that task B starts executing
+	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
+	 * task C starts reading on CPU 0, so that its increment is not
+	 * summed, but finishes reading on CPU 2, so that its decrement
+	 * -is- summed.  Then when task B completes its sum, it will
+	 * incorrectly get zero, despite the fact that task A has been
+	 * in its SRCU read-side critical section the whole time.
+	 *
+	 * We therefore do a validation step should srcu_readers_active_idx()
+	 * return zero.
+	 */
+	if (srcu_readers_active_idx(sp, idx) != 0)
+		return false;
+
+	/*
+	 * Since the caller recently flipped ->completed, we can see at
+	 * most one increment of each CPU's counter from this point
+	 * forward.  The reason for this is that the reader CPU must have
+	 * fetched the index before srcu_readers_active_idx checked
+	 * that CPU's counter, but not yet incremented its counter.
+	 * Its eventual counter increment will follow the read in
+	 * srcu_readers_active_idx(), and that increment is immediately
+	 * followed by smp_mb() B.  Because smp_mb() D is between
+	 * the ->completed flip and srcu_readers_active_idx()'s read,
+	 * that CPU's subsequent load of ->completed must see the new
+	 * value, and therefore increment the counter in the other rank.
+	 */
+	smp_mb(); /* A */
+
+	/*
+	 * Now, we check the ->snap array that srcu_readers_active_idx()
+	 * filled in from the per-CPU counter values.  Since both
+	 * __srcu_read_lock() and __srcu_read_unlock() increment the
+	 * upper bits of the per-CPU counter, an increment/decrement
+	 * pair will change the value of the counter.  Since there is
+	 * only one possible increment, the only way to wrap the counter
+	 * is to have a huge number of counter decrements, which requires

kernel/srcu.c EXPORT_SYMBOL_GPL(init_srcu_struct); · line 156

Quoted 10 lines

kernel/srcu.c +10 -0

+	 * a huge number of tasks and huge SRCU read-side critical-section
+	 * nesting levels, even on 32-bit systems.
+	 *
+	 * All of the ways of confusing the readings require that the scan
+	 * in srcu_readers_active_idx() see the read-side task's decrement,
+	 * but not its increment.  However, between that decrement and
+	 * increment are smb_mb() B and C.  Either or both of these pair
+	 * with smp_mb() A above to ensure that the scan below will see
+	 * the read-side tasks's increment, thus noting a difference in
+	 * the counter values between the two passes.

Hi Paul,

I think the implementation is correct, but the explanation above might be improved. Let's consider the following a scenario, where a reader is migrated between increment of the counter and issuing the memory barrier in the read lock:

A,B,C are readers
D is synchronize_rcu (one flip'n'wait)

CPU A CPU B CPU C CPU D

                                    c[1]++
                                    smp_mb(1)
                                                  read c[0] -> 0
c[0]++
(implicit smp_mb (2))
      -> migrated ->
                    (implicit smp_mb (3))
                    smp_mb (4)
                    smp_mb (5)
                    c[1]--
                                                  read c[1] -> -1
                                                  read c[2] -> 1
                                                  (false 0 sum)
                                                  smp_mb (6)
                                                  re-check each.
                                    c[1]--

re-check: because we observed c[1] == -1, thanks to the implicit memory barriers within thread migration (2 and 3), we can assume that we _will_ observe the updated value of c[0] after smp_mb (6).

Quoted 6 lines

The current explanation states that memory barriers 4 and 5, along with 6, are responsible for ensuring that the increment will be observed by the re-check. However, I doubt they have anything to do with it: it's rather the implicit memory barriers in thread migration, along with program order guarantees on writes to the same address, that seems to be the reason why we can do this ordering assumption.

Please disregard the part about program order: CPU A writes to c[0], and CPU B writes to c[1], which are two different memory locations. The rest of my discussion stands though.

Simply reasoning about write to c[0], memory barriers 2-3, write to c[1], along with c[1] read, memory barrier 6, and then c[0] read is enough to explain the ordering guarantees you need, without invoking program order.

Thanks,

Mathieu

Quoted 33 lines

Does it make sense, or shall I get another coffee to wake myself up ? ;)

Thanks,

Mathieu

Quoted 18 lines

kernel/srcu.c +14 -2

+	 *
+	 * Therefore, if srcu_readers_active_idx() returned zero, and
+	 * none of the counters changed, we know that the zero was the
+	 * correct sum.
+	 *
+	 * Of course, it is possible that a task might be delayed
+	 * for a very long time in __srcu_read_lock() after fetching
+	 * the index but before incrementing its counter.  This
+	 * possibility will be dealt with in __synchronize_srcu().
+	 */
 	for_each_possible_cpu(cpu)
-		sum += per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx];
-	return sum;
+		if (sp->snap[cpu] !=
+		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
+			return false;  /* False zero reading! */
+	return true;
 }

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Quoted 111 lines · Mathieu Desnoyers

Quoted 99 lines · * Mathieu Desnoyers ([email protected]) wrote:

* Paul E. McKenney ([email protected]) wrote:
[...]

Quoted 54 lines

kernel/srcu.c +49 -2

+/*
+ * To be called from the update side after an index flip.  Returns true
+ * if the modulo sum of the counters is stably zero, false if there is
+ * some possibility of non-zero.
+ */
+static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
-	int sum;
 
-	sum = 0;
+	/*
+	 * Note that srcu_readers_active_idx() can incorrectly return
+	 * zero even though there is a pre-existing reader throughout.
+	 * To see this, suppose that task A is in a very long SRCU
+	 * read-side critical section that started on CPU 0, and that
+	 * no other reader exists, so that the modulo sum of the counters
+	 * is equal to one.  Then suppose that task B starts executing
+	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
+	 * task C starts reading on CPU 0, so that its increment is not
+	 * summed, but finishes reading on CPU 2, so that its decrement
+	 * -is- summed.  Then when task B completes its sum, it will
+	 * incorrectly get zero, despite the fact that task A has been
+	 * in its SRCU read-side critical section the whole time.
+	 *
+	 * We therefore do a validation step should srcu_readers_active_idx()
+	 * return zero.
+	 */
+	if (srcu_readers_active_idx(sp, idx) != 0)
+		return false;
+
+	/*
+	 * Since the caller recently flipped ->completed, we can see at
+	 * most one increment of each CPU's counter from this point
+	 * forward.  The reason for this is that the reader CPU must have
+	 * fetched the index before srcu_readers_active_idx checked
+	 * that CPU's counter, but not yet incremented its counter.
+	 * Its eventual counter increment will follow the read in
+	 * srcu_readers_active_idx(), and that increment is immediately
+	 * followed by smp_mb() B.  Because smp_mb() D is between
+	 * the ->completed flip and srcu_readers_active_idx()'s read,
+	 * that CPU's subsequent load of ->completed must see the new
+	 * value, and therefore increment the counter in the other rank.
+	 */
+	smp_mb(); /* A */
+
+	/*
+	 * Now, we check the ->snap array that srcu_readers_active_idx()
+	 * filled in from the per-CPU counter values.  Since both
+	 * __srcu_read_lock() and __srcu_read_unlock() increment the
+	 * upper bits of the per-CPU counter, an increment/decrement
+	 * pair will change the value of the counter.  Since there is
+	 * only one possible increment, the only way to wrap the counter
+	 * is to have a huge number of counter decrements, which requires

kernel/srcu.c EXPORT_SYMBOL_GPL(init_srcu_struct); · line 156

Quoted 10 lines

kernel/srcu.c +10 -0

+	 * a huge number of tasks and huge SRCU read-side critical-section
+	 * nesting levels, even on 32-bit systems.
+	 *
+	 * All of the ways of confusing the readings require that the scan
+	 * in srcu_readers_active_idx() see the read-side task's decrement,
+	 * but not its increment.  However, between that decrement and
+	 * increment are smb_mb() B and C.  Either or both of these pair
+	 * with smp_mb() A above to ensure that the scan below will see
+	 * the read-side tasks's increment, thus noting a difference in
+	 * the counter values between the two passes.

Hi Paul,

I think the implementation is correct, but the explanation above might be improved. Let's consider the following a scenario, where a reader is migrated between increment of the counter and issuing the memory barrier in the read lock:

A,B,C are readers
D is synchronize_rcu (one flip'n'wait)

CPU A CPU B CPU C CPU D

                                    c[1]++
                                    smp_mb(1)
                                                  read c[0] -> 0
c[0]++
(implicit smp_mb (2))
      -> migrated ->
                    (implicit smp_mb (3))
                    smp_mb (4)
                    smp_mb (5)
                    c[1]--
                                                  read c[1] -> -1
                                                  read c[2] -> 1
                                                  (false 0 sum)
                                                  smp_mb (6)
                                                  re-check each.
                                    c[1]--

re-check: because we observed c[1] == -1, thanks to the implicit memory barriers within thread migration (2 and 3), we can assume that we _will_ observe the updated value of c[0] after smp_mb (6).

Quoted 6 lines

The current explanation states that memory barriers 4 and 5, along with 6, are responsible for ensuring that the increment will be observed by the re-check. However, I doubt they have anything to do with it: it's rather the implicit memory barriers in thread migration, along with program order guarantees on writes to the same address, that seems to be the reason why we can do this ordering assumption.

Please disregard the part about program order: CPU A writes to c[0], and CPU B writes to c[1], which are two different memory locations. The rest of my discussion stands though.

Quoted 4 lines

Simply reasoning about write to c[0], memory barriers 2-3, write to c[1], along with c[1] read, memory barrier 6, and then c[0] read is enough to explain the ordering guarantees you need, without invoking program order.

I am assuming that if the scheduler migrates a process, it applies enough memory ordering to allow the proof to operate as if it had stayed on a single CPU throughout.

The reasoning for this would consider the
scheduler access and memory barriers

-- but there would be an arbitrarily
large number of migration patterns, so I am not convinced that it would help...

Thanx, Paul

Quoted 44 lines

Thanks,

Mathieu

Quoted 33 lines

Does it make sense, or shall I get another coffee to wake myself up ? ;)

Thanks,

Mathieu

Quoted 18 lines

kernel/srcu.c +14 -2

+	 *
+	 * Therefore, if srcu_readers_active_idx() returned zero, and
+	 * none of the counters changed, we know that the zero was the
+	 * correct sum.
+	 *
+	 * Of course, it is possible that a task might be delayed
+	 * for a very long time in __srcu_read_lock() after fetching
+	 * the index but before incrementing its counter.  This
+	 * possibility will be dealt with in __synchronize_srcu().
+	 */
 	for_each_possible_cpu(cpu)
-		sum += per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx];
-	return sum;
+		if (sp->snap[cpu] !=
+		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
+			return false;  /* False zero reading! */
+	return true;
 }

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Signature · 4 lines

Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

This brings the following question then: which memory barriers, in the scheduler activity, act as full memory barriers to migrated threads ? I see that the rq_lock is taken, but this lock is permeable in one direction (operations can spill into the critical section). I'm probably missing something else, but this something else probably needs to be documented somewhere, since we are doing tons of assumptions based on it.

Quoted 7 lines · Mathieu Desnoyers

This brings the following question then: which memory barriers, in the scheduler activity, act as full memory barriers to migrated threads ? I see that the rq_lock is taken, but this lock is permeable in one direction (operations can spill into the critical section). I'm probably missing something else, but this something else probably needs to be documented somewhere, since we are doing tons of assumptions based on it.

A migration consists of two context switches, one switching out the task on the old cpu, and one switching in the task on the new cpu.

Now on x86 all the rq->lock grabbery is plenty implied memory barriers to make anybody happy.

But I think, since there's guaranteed order (can't switch to before switching from) you can match the UNLOCK from the switch-from to the LOCK from the switch-to to make your complete MB.

Does that work or do we need more?

Hrm, I think we'd need a little more than just lock/unlock ordering guarantees. Let's consider the following, where the stores would be expected to be seen as "store A before store B" by CPU 2

CPU 0 CPU 1 CPU 2

load B, smp_rmb, load A in loop, expecting that when updated A is observed, B is always observed as updated too.
store A
(lock is permeable:
outside can leak
inside)
lock(rq->lock)

-> migration ->

unlock(rq->lock)
(lock is permeable:
outside can leak inside)
store B

Does that make sense, or should I get my first morning coffee ? :)

Quoted 17 lines · Mathieu Desnoyers

Hrm, I think we'd need a little more than just lock/unlock ordering guarantees. Let's consider the following, where the stores would be expected to be seen as "store A before store B" by CPU 2

CPU 0 CPU 1 CPU 2

load B, smp_rmb, load A in loop, expecting that when updated A is observed, B is always observed as updated too.
store A
(lock is permeable:
outside can leak
inside)
lock(rq->lock)

Quoted 6 lines

-> migration ->

unlock(rq->lock)
(lock is permeable:
outside can leak inside)
store B

You got the pairing the wrong way around, I suggested:

store A

switch-out
UNLOCK

-> migration ->

switch-in
LOCK

store B

While both LOCK and UNLOCK are semi-permeable, A won't pass the UNLOCK and B won't pass the LOCK.

Yes, A can pass switch-out LOCK, but that doesn't matter much since the switch-in cannot happen until we've passed UNLOCK.

And yes B can pass switch-in UNLOCK, but again, I can't see that being a problem since the LOCK will avoid it being visible before A.

Quoted 2 lines

Does that make sense, or should I get my first morning coffee ? :)

Probably.. but that's not saying I'm not wrong ;-)

Ah, so this is what I missed: the context switch has its lock/unlock pair, the following migration is performed under its own lock/unlock pair, and the following context switch also has its lock/unlock pair. So yes, this should be sufficient to act as a full memory barrier.

Quoted 17 lines · Mathieu Desnoyers

Hrm, I think we'd need a little more than just lock/unlock ordering guarantees. Let's consider the following, where the stores would be expected to be seen as "store A before store B" by CPU 2

CPU 0 CPU 1 CPU 2

load B, smp_rmb, load A in loop, expecting that when updated A is observed, B is always observed as updated too.
store A
(lock is permeable:
outside can leak
inside)
lock(rq->lock)

Quoted 6 lines

-> migration ->

unlock(rq->lock)
(lock is permeable:
outside can leak inside)
store B

You got the pairing the wrong way around, I suggested:

store A

switch-out
UNLOCK

-> migration ->

switch-in
LOCK

store B

While both LOCK and UNLOCK are semi-permeable, A won't pass the UNLOCK and B won't pass the LOCK.

Yes, A can pass switch-out LOCK, but that doesn't matter much since the switch-in cannot happen until we've passed UNLOCK.

And yes B can pass switch-in UNLOCK, but again, I can't see that being a problem since the LOCK will avoid it being visible before A.

Quoted 1 line

Does that make sense, or should I get my first morning coffee ? :)

Probably.. but that's not saying I'm not wrong ;-)

/*
* Helper function for synchronize_srcu() and synchronize_srcu_expedited(). */

kernel/srcu.c +7 -6

-static void __synchronize_srcu(struct srcu_struct *sp, void (*sync_func)(void))
+static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 {
 	int idx;

@@ -178,90 +316,51 @@ static void __synchronize_srcu(struct srcu_struct *sp, void (*sync_func)(void))
 			   !lock_is_held(&rcu_sched_lock_map),
 			   "Illegal synchronize_srcu() in same-type SRCU (or RCU) read-side critical section");
 
-	idx = sp->completed;
+	idx = ACCESS_ONCE(sp->completed);
 	mutex_lock(&sp->mutex);
 
 	/*
 	 * Check to see if someone else did the work for us while we were
-	 * waiting to acquire the lock.  We need -two- advances of
+	 * waiting to acquire the lock.  We need -three- advances of
 	 * the counter, not just one.  If there was but one, we might have
 	 * shown up -after- our helper's first synchronize_sched(), thus
 	 * having failed to prevent CPU-reordering races with concurrent
-	 * srcu_read_unlock()s on other CPUs (see comment below).  So we
-	 * either (1) wait for two or (2) supply the second ourselves.
+	 * srcu_read_unlock()s on other CPUs (see comment below).  If there
+	 * was only two, we are guaranteed to have waited through only one
+	 * full index-flip phase.  So we either (1) wait for three or
+	 * (2) supply the additional ones we need.
 	 */
 
-	if ((sp->completed - idx) >= 2) {

Quoted 32 lines · Paul E. McKenney

/*
* Helper function for synchronize_srcu() and synchronize_srcu_expedited(). */

kernel/srcu.c +7 -6

-static void __synchronize_srcu(struct srcu_struct *sp, void (*sync_func)(void))
+static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 {
 	int idx;

@@ -178,90 +316,51 @@ static void __synchronize_srcu(struct srcu_struct *sp, void (*sync_func)(void))
 			   !lock_is_held(&rcu_sched_lock_map),
 			   "Illegal synchronize_srcu() in same-type SRCU (or RCU) read-side critical section");
 
-	idx = sp->completed;
+	idx = ACCESS_ONCE(sp->completed);
 	mutex_lock(&sp->mutex);
 
 	/*
 	 * Check to see if someone else did the work for us while we were
-	 * waiting to acquire the lock.  We need -two- advances of
+	 * waiting to acquire the lock.  We need -three- advances of
 	 * the counter, not just one.  If there was but one, we might have
 	 * shown up -after- our helper's first synchronize_sched(), thus
 	 * having failed to prevent CPU-reordering races with concurrent
-	 * srcu_read_unlock()s on other CPUs (see comment below).  So we
-	 * either (1) wait for two or (2) supply the second ourselves.
+	 * srcu_read_unlock()s on other CPUs (see comment below).  If there
+	 * was only two, we are guaranteed to have waited through only one
+	 * full index-flip phase.  So we either (1) wait for three or
+	 * (2) supply the additional ones we need.
 	 */
 
-	if ((sp->completed - idx) >= 2) {

kernel/srcu.c static void __synchronize_srcu(struct srcu_struct *sp, void (*sync_func)(void)) · line 340

Quoted 10 lines

kernel/srcu.c +5 -3

+	if (sp->completed == idx + 2)
+		idx = 1;
+	else if (sp->completed == idx + 3) {
 		mutex_unlock(&sp->mutex);
 		return;
-	}
-
-	sync_func();  /* Force memory barrier on all CPUs. */
+	} else
+		idx = 0;

Hi, Paul

I don't think this check-and-return path is needed since we will introduce call_srcu().

We just need a correct code to show how it works and to be used for a while, and new call_srcu() will be implemented based on this correct code which will be removed.

And I think this unneeded check-and-return path is incorrect. See the following:

Reader Updater Helper thread

			old_ptr = rcu_ptr;
			/* rcu_ptr = NULL; but be reordered to (1) */
			start synchronize_srcu()
			idx = ACCESS_ONCE(sp->completed);(2)
									synchronize_srcu()
									synchronize_srcu()
srcu_read_lock();
old_ptr = rcu_ptr;
			rcu_ptr = NULL;(1)
			mutex_lock() and read sp->completed
			and return from synchronize_srcu()
			free(old_ptr);

use freed old_ptr
srcu_read_unlock();

So, we need a smb_mb() between (1) and (2) to force the order.

__synchronize_srcu() {
	smp_mb(); /* F */
	idx = ACCESS_ONCE(sp->completed); /* (2) */

	....
}

And this smp_mb() F is paired with helper's smp_mb() D. So if Updater sees X advances of ->completed, Updater must sees X times of *full* flip_and_wait(). So We need see -two- advances of ->completed from Helper only, not -three-.

        if (sp->completed == idx + 1)
                idx = 1;
        else if (sp->completed == idx + 2) {
                mutex_unlock(&sp->mutex);
                return;
        } else
                idx = 0;

Or simpler:

__synchronize_srcu() {
	unsigned int idx;   /* <-------- unsigned */

	/* comments for smp_mb() F */
	smp_mb(); /* F */
	idx = ACCESS_ONCE(sp->completed);

	mutex_lock(&sp->mutex);
	idx = sp->completed - idx;

	/* original comments */
	for (; idx < 2; idx++)
                flip_idx_and_wait(sp, expedited);
        mutex_unlock(&sp->mutex);
}

At last, I can't understand the comments of this check-and-return path. So maybe the above reply and I are totally wrong.

But the comments of this check-and-return path does not describe the code well(especially the order), and it contains the old "synchronize_sched()" which make me confuse.

My conclusion, we can just remove the check-and-return path to reduce the complexity since we will introduce call_srcu().

This new srcu is very great, especially the SRCU_USAGE_COUNT for every lock/unlock witch forces any increment/decrement pair changes the counter for me.

Thanks,
Lai

--
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 3 lines

My conclusion, we can just remove the check-and-return path to reduce the complexity since we will introduce call_srcu().

If I actually submit the above upstream, that would be quite reasonable. My thought is that patch remains RFC and the upstream version has call_srcu().

Quoted 4 lines

This new srcu is very great, especially the SRCU_USAGE_COUNT for every lock/unlock witch forces any increment/decrement pair changes the counter for me.

Glad you like it! ;-)

And thank you for your review and feedback!

Quoted 7 lines · Paul E. McKenney

Quoted 3 lines

My conclusion, we can just remove the check-and-return path to reduce the complexity since we will introduce call_srcu().

If I actually submit the above upstream, that would be quite reasonable. My thought is that patch remains RFC and the upstream version has call_srcu().

Does the work of call_srcu() is started or drafted?

Quoted 4 lines

Quoted 3 lines

This new srcu is very great, especially the SRCU_USAGE_COUNT for every lock/unlock witch forces any increment/decrement pair changes the counter for me.

Quoted 3 lines

Glad you like it! ;-)

And thank you for your review and feedback!

Could you add my Reviewed-by when this patch is last submitted?

Reviewed-by Lai Jiangshan <[email protected]>

Quoted 6 lines · Lai Jiangshan

Quoted 4 lines · Paul E. McKenney

Quoted 3 lines

My conclusion, we can just remove the check-and-return path to reduce the complexity since we will introduce call_srcu().

Quoted 5 lines

Quoted 3 lines

If I actually submit the above upstream, that would be quite reasonable. My thought is that patch remains RFC and the upstream version has call_srcu().

Does the work of call_srcu() is started or drafted?

I do have a draft design, and am currently beating it into shape. No actual code yet, though. The general idea at the moment is as follows:

o The state machine must be preemptible. I recently received
a bug report about 200-microsecond latency spikes on a system with more than a thousand CPUs, so the summation of the per-CPU counters and subsequent recheck cannot be in a preempt-disable region. I am therefore currently thinking in terms of a kthread.

o At the moment, having a per-srcu_struct kthread seems excessive.
I am planning on a single kthread to do the counter summation and checking. Further parallelism might be useful in the future, but I would want to see someone run into problems before adding more complexity.

o There needs to be a linked list of srcu_struct structures so
that they can be traversed by the state-machine kthread.

o If there are expedited SRCU callbacks anywhere, the kthread
would scan through the list of srcu_struct structures quickly (perhaps pausing a few microseconds between). If there are no expedited SRCU callbacks, the kthread would wait a jiffy or so between scans.

o If a given srcu_struct structure has been scanned too many times
(say, more than ten times) while waiting for the counters to go to zero, it loses expeditedness. It makes no sense for the kthread to go CPU-bound just because some SRCU reader somewhere is blocked in its SRCU read-side critical section.

o Expedited SRCU callbacks cannot be delayed by normal SRCU
callbacks, but neither can expedited callbacks be allowed to starve normal callbacks. I am thinking in terms of invoking these from softirq context, with a pair of multi-tailed callback queues per CPU, stored in the same structure as the per-CPU counters.

o There are enough srcu_struct structures in the Linux that
it does not make sense to force softirq to dig through them all any time any one of them has callbacks ready to invoke. One way to deal with this is to have a per-CPU set of linked lists of of srcu_struct_array structures, so that the kthread enqueues a given structure when it transitions to having callbacks ready to invoke, and softirq dequeues it. This can be done locklessly given that there is only one producer and one consumer.

o We can no longer use the trick of pushing callbacks to another
CPU from the CPU_DYING notifier because it is likely that CPU hotplug will stop using stop_cpus(). I am therefore thinking in terms of a set of orphanages (two for normal, two more for expedited -- one set of each for callbacks ready to invoke, the other for still-waiting callbacks).

o There will need to be an srcu_barrier() that can be called
before cleanup_srcu_struct(). Otherwise, someone will end up freeing up an srcu_struct that still has callbacks outstanding.

But what did you have in mind?

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

This new srcu is very great, especially the SRCU_USAGE_COUNT for every lock/unlock witch forces any increment/decrement pair changes the counter for me.

Quoted 8 lines

Quoted 3 lines

Glad you like it! ;-)

And thank you for your review and feedback!

Could you add my Reviewed-by when this patch is last submitted?

Reviewed-by Lai Jiangshan <[email protected]>

Will do, thank you!

Thanx, Paul

Quoted 11 lines · Paul E. McKenney

Quoted 10 lines · Lai Jiangshan

Quoted 7 lines · Paul E. McKenney

Quoted 3 lines

My conclusion, we can just remove the check-and-return path to reduce the complexity since we will introduce call_srcu().

If I actually submit the above upstream, that would be quite reasonable. My thought is that patch remains RFC and the upstream version has call_srcu().

Quoted 4 lines

Quoted 1 line

Does the work of call_srcu() is started or drafted?

I do have a draft design, and am currently beating it into shape. No actual code yet, though. The general idea at the moment is as follows:

If you don't mind, I will implement it.(it requires your new version of SRCU implementation)

Quoted 5 lines

o The state machine must be preemptible. I recently received
a bug report about 200-microsecond latency spikes on a system with more than a thousand CPUs, so the summation of the per-CPU counters and subsequent recheck cannot be in a preempt-disable region. I am therefore currently thinking in terms of a kthread.

sure.

Addition:
Srcu callbacks must run on process context and sleepable, (and therefore they finish orderless). We can't change the current rcu-callback, we must design a new for srcu. These do not introduce any complexity, we reuse the workqueue. All ready srcu-callback will be delivered to workqueue. so state-machine-thread only to do counter summation and checking and delivering.

workqueue do all the complexity for us, it will auto alloc threads when needed(when the callback is sleep, or there are too much ready callbacks).

struct srcu_head is a little bigger than struct rcu_head, it contain a union for struct work_struct.

(synchronize_srcu()'s callbacks are special handled)

Quoted 5 lines

o At the moment, having a per-srcu_struct kthread seems excessive.
I am planning on a single kthread to do the counter summation and checking. Further parallelism might be useful in the future, but I would want to see someone run into problems before adding more complexity.

Simple is important, I vote for a single kthread to do the counter summation and checking, and left the convenient that we can introduce parallelism thread easy.

Quoted 8 lines

o There needs to be a linked list of srcu_struct structures so
that they can be traversed by the state-machine kthread.

o If there are expedited SRCU callbacks anywhere, the kthread
would scan through the list of srcu_struct structures quickly (perhaps pausing a few microseconds between). If there are no expedited SRCU callbacks, the kthread would wait a jiffy or so between scans.

Sure
But I think generic expedited SRCU callbacks are make no sense, we could just allow expedited SRCU callbacks for synchronize_srcu_expedited() only.

Quoted 11 lines

o If a given srcu_struct structure has been scanned too many times
(say, more than ten times) while waiting for the counters to go to zero, it loses expeditedness. It makes no sense for the kthread to go CPU-bound just because some SRCU reader somewhere is blocked in its SRCU read-side critical section.

o Expedited SRCU callbacks cannot be delayed by normal SRCU
callbacks, but neither can expedited callbacks be allowed to starve normal callbacks. I am thinking in terms of invoking these from softirq context, with a pair of multi-tailed callback queues per CPU, stored in the same structure as the per-CPU counters.

My Addition design, callbacks are not running in softirq context. And state-machine-thread is not delay by any normal callbacks.

But all synchronize_srcu()'s callback are done in state-machine-thread (it is just a wake up), not in workqueue.

Since we allow expedited SRCU callbacks for synchronize_srcu_expedited() only, Expedited SRCU callbacks will not be delayed by normal srcu callbacks.

I don't think we need to use per CPU callback queues, since SRCU callbacks are rare(compared to rcu callbacks)

Quoted 9 lines

o There are enough srcu_struct structures in the Linux that
it does not make sense to force softirq to dig through them all any time any one of them has callbacks ready to invoke. One way to deal with this is to have a per-CPU set of linked lists of of srcu_struct_array structures, so that the kthread enqueues a given structure when it transitions to having callbacks ready to invoke, and softirq dequeues it. This can be done locklessly given that there is only one producer and one consumer.

Quoted 6 lines

o We can no longer use the trick of pushing callbacks to another
CPU from the CPU_DYING notifier because it is likely that CPU hotplug will stop using stop_cpus(). I am therefore thinking in terms of a set of orphanages (two for normal, two more for expedited -- one set of each for callbacks ready to invoke, the other for still-waiting callbacks).

no such issues in srcu.c if we use workqueue.

Quoted 3 lines

o There will need to be an srcu_barrier() that can be called
before cleanup_srcu_struct(). Otherwise, someone will end up freeing up an srcu_struct that still has callbacks outstanding.

Sure.

when use workqueue, the delivering is ordered.

srcu_barrier()

{
	synchronzie_srcu();
	flush_workqueue();
}

Quoted 1 line

But what did you have in mind?

I agree most of your design, but my relaxing the ability for callbacks and using workqueue ideas make things simpler.

Thanks,
Lai

Quoted 19 lines

Quoted 5 lines

Quoted 5 lines

Quoted 4 lines

This new srcu is very great, especially the SRCU_USAGE_COUNT for every lock/unlock witch forces any increment/decrement pair changes the counter for me.

Quoted 8 lines

Quoted 3 lines

Glad you like it! ;-)

And thank you for your review and feedback!

Could you add my Reviewed-by when this patch is last submitted?

Reviewed-by Lai Jiangshan <[email protected]>

Will do, thank you!

Thanx, Paul

From abe3fd64d08f74f13e8111e333a9790e9e6d782c Mon Sep 17 00:00:00 2001

From de49bb517e6367776e2226b931346ab6c798b122 Mon Sep 17 00:00:00 2001

+ ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += -1;

Quoted 1 line

From de49bb517e6367776e2226b931346ab6c798b122 Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Wed, 22 Feb 2012 10:41:59 +0800
Subject: [PATCH 2/3 RFC paul/rcu/srcu] srcu: only increase the upper bit for srcu_read_lock()

The algorithm/smp_mb()s ensure 'there is only one srcu_read_lock() between flip and recheck for a cpu'.
Increment of the upper bit for srcu_read_lock() only can ensure a single pair of lock/unlock change the cpu counter.

Signed-off-by Lai Jiangshan <[email protected]>

---
 include/linux/srcu.h |    2 +-
 kernel/srcu.c        |   11 +++++------
 2 files changed, 6 insertions(+), 7 deletions(-)

include/linux/srcu.h +1 -1

index a478c8e..5b49d41 100644
@@ -35,7 +35,7 @@ struct srcu_struct_array {
 };
 
 /* Bit definitions for field ->c above and ->snap below. */
-#define SRCU_USAGE_BITS		2
+#define SRCU_USAGE_BITS		1
 #define SRCU_REF_MASK		(ULONG_MAX >> SRCU_USAGE_BITS)
 #define SRCU_USAGE_COUNT	(SRCU_REF_MASK + 1)
 

kernel/srcu.c +5 -6

index 17e95bc..a51ac48 100644
@@ -138,10 +138,10 @@ static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 
 	/*
 	 * Now, we check the ->snap array that srcu_readers_active_idx()
-	 * filled in from the per-CPU counter values.  Since both
-	 * __srcu_read_lock() and __srcu_read_unlock() increment the
-	 * upper bits of the per-CPU counter, an increment/decrement
-	 * pair will change the value of the counter.  Since there is
+	 * filled in from the per-CPU counter values. Since
+	 * __srcu_read_lock() increments the upper bits of
+	 * the per-CPU counter, an increment/decrement pair will
+	 * change the value of the counter.  Since there is
 	 * only one possible increment, the only way to wrap the counter
 	 * is to have a huge number of counter decrements, which requires
 	 * a huge number of tasks and huge SRCU read-side critical-section

@@ -234,8 +234,7 @@ void __srcu_read_unlock(struct srcu_struct *sp, int idx)
 {
 	preempt_disable();
 	smp_mb(); /* C */  /* Avoid leaking the critical section. */
-	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) +=
-		SRCU_USAGE_COUNT - 1;
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += -1;
 	preempt_enable();
 }
 EXPORT_SYMBOL_GPL(__srcu_read_unlock);

Signature · 1 line

1.7.4.4

Quoted 5 lines · Lai Jiangshan

Quoted 1 line

From de49bb517e6367776e2226b931346ab6c798b122 Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Wed, 22 Feb 2012 10:41:59 +0800
Subject: [PATCH 2/3 RFC paul/rcu/srcu] srcu: only increase the upper bit for srcu_read_lock()

Quoted 4 lines

The algorithm/smp_mb()s ensure 'there is only one srcu_read_lock() between flip and recheck for a cpu'.
Increment of the upper bit for srcu_read_lock() only can ensure a single pair of lock/unlock change the cpu counter.

Very nice! Also makes is more clear in that no combination of operations including exactly one increment can possibly wrap back to the same value, because the upper bit would be different.

In deference to Peter Zijlstra's sensibilities, I changed the:

	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += -1;

to:

	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) -= 1;

I did manage to resist the temptation to instead say:

	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) -= +1;

;-)

Queued, thank you!

Thanx, Paul

Quoted 51 lines

Signed-off-by Lai Jiangshan <[email protected]>

---
 include/linux/srcu.h |    2 +-
 kernel/srcu.c        |   11 +++++------
 2 files changed, 6 insertions(+), 7 deletions(-)

include/linux/srcu.h +1 -1

index a478c8e..5b49d41 100644
@@ -35,7 +35,7 @@ struct srcu_struct_array {
 };
 
 /* Bit definitions for field ->c above and ->snap below. */
-#define SRCU_USAGE_BITS		2
+#define SRCU_USAGE_BITS		1
 #define SRCU_REF_MASK		(ULONG_MAX >> SRCU_USAGE_BITS)
 #define SRCU_USAGE_COUNT	(SRCU_REF_MASK + 1)
 

kernel/srcu.c +5 -6

index 17e95bc..a51ac48 100644
@@ -138,10 +138,10 @@ static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 
 	/*
 	 * Now, we check the ->snap array that srcu_readers_active_idx()
-	 * filled in from the per-CPU counter values.  Since both
-	 * __srcu_read_lock() and __srcu_read_unlock() increment the
-	 * upper bits of the per-CPU counter, an increment/decrement
-	 * pair will change the value of the counter.  Since there is
+	 * filled in from the per-CPU counter values. Since
+	 * __srcu_read_lock() increments the upper bits of
+	 * the per-CPU counter, an increment/decrement pair will
+	 * change the value of the counter.  Since there is
 	 * only one possible increment, the only way to wrap the counter
 	 * is to have a huge number of counter decrements, which requires
 	 * a huge number of tasks and huge SRCU read-side critical-section

@@ -234,8 +234,7 @@ void __srcu_read_unlock(struct srcu_struct *sp, int idx)
 {
 	preempt_disable();
 	smp_mb(); /* C */  /* Avoid leaking the critical section. */
-	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) +=
-		SRCU_USAGE_COUNT - 1;
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += -1;
 	preempt_enable();
 }
 EXPORT_SYMBOL_GPL(__srcu_read_unlock);

Signature · 1 line

1.7.4.4

Make that without underflow -- one increment and 2^31+1 decrements would in fact return the counter to its original value, but that would require cramming more than two billion tasks into a 32-bit address space, which I believe to be sufficiently unlikely. (Famous last words...)

Quoted 4 lines · Paul E. McKenney

Make that without underflow -- one increment and 2^31+1 decrements would in fact return the counter to its original value, but that would require cramming more than two billion tasks into a 32-bit address space, which I believe to be sufficiently unlikely. (Famous last words...)

I'll just expect to see you as President of the United States, counting your money you won in the lottery, and being awarded a Nobel Prize for curing cancer.

From 4ddf62aaf2c4ebe6b9d4a1c596e8b43a678f1f0d Mon Sep 17 00:00:00 2001

Quoted 1 line

From 4ddf62aaf2c4ebe6b9d4a1c596e8b43a678f1f0d Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Wed, 22 Feb 2012 14:12:02 +0800
Subject: [PATCH 3/3 RFC paul/rcu/srcu] srcu: flip only once for every grace period

flip_idx_and_wait() is not changed, and is split as two functions and only a short comments is added for smp_mb() E.

__synchronize_srcu() use a different algorithm for "leak" readers. detail is in the comments of the patch.

Signed-off-by Lai Jiangshan <[email protected]>

---
 kernel/srcu.c |  105 ++++++++++++++++++++++++++++++++++----------------------
 1 files changed, 64 insertions(+), 41 deletions(-)

kernel/srcu.c +64 -41

index a51ac48..346f9d7 100644
@@ -249,6 +249,37 @@ EXPORT_SYMBOL_GPL(__srcu_read_unlock);
  */
 #define SYNCHRONIZE_SRCU_READER_DELAY 5
 
+static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
+{
+	int trycount = 0;
+
+	/*
+	 * SRCU read-side critical sections are normally short, so wait
+	 * a small amount of time before possibly blocking.
+	 */
+	if (!srcu_readers_active_idx_check(sp, idx)) {
+		udelay(SYNCHRONIZE_SRCU_READER_DELAY);
+		while (!srcu_readers_active_idx_check(sp, idx)) {
+			if (expedited && ++ trycount < 10)
+				udelay(SYNCHRONIZE_SRCU_READER_DELAY);
+			else
+				schedule_timeout_interruptible(1);
+		}
+	}
+
+	/*
+	 * The following smp_mb() E pairs with srcu_read_unlock()'s
+	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
+	 * sees srcu_read_unlock()'s counter decrement, then any
+	 * of the current task's subsequent code will happen after
+	 * that SRCU read-side critical section.
+	 *
+	 * It also ensures the order between the above waiting and
+	 * the next flipping.
+	 */
+	smp_mb(); /* E */
+}
+
 /*
  * Flip the readers' index by incrementing ->completed, then wait
  * until there are no more readers using the counters referenced by

@@ -258,12 +289,12 @@ EXPORT_SYMBOL_GPL(__srcu_read_unlock);
  * Of course, it is possible that a reader might be delayed for the
  * full duration of flip_idx_and_wait() between fetching the
  * index and incrementing its counter.  This possibility is handled
- * by __synchronize_srcu() invoking flip_idx_and_wait() twice.
+ * by the next __synchronize_srcu() invoking wait_idx() for such readers
+ * before start a new grace perioad.
  */
 static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
 {
 	int idx;
-	int trycount = 0;
 
 	idx = sp->completed++ & 0x1;
 

@@ -278,28 +309,7 @@ static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
 	 */
 	smp_mb(); /* D */
 
-	/*
-	 * SRCU read-side critical sections are normally short, so wait
-	 * a small amount of time before possibly blocking.
-	 */
-	if (!srcu_readers_active_idx_check(sp, idx)) {
-		udelay(SYNCHRONIZE_SRCU_READER_DELAY);
-		while (!srcu_readers_active_idx_check(sp, idx)) {
-			if (expedited && ++ trycount < 10)
-				udelay(SYNCHRONIZE_SRCU_READER_DELAY);
-			else
-				schedule_timeout_interruptible(1);
-		}
-	}
-
-	/*
-	 * The following smp_mb() E pairs with srcu_read_unlock()'s
-	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
-	 * sees srcu_read_unlock()'s counter decrement, then any
-	 * of the current task's subsequent code will happen after
-	 * that SRCU read-side critical section.
-	 */
-	smp_mb(); /* E */
+	wait_idx(sp, idx, expedited);
 }
 
 /*

@@ -307,8 +317,6 @@ static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
  */
 static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 {
-	int idx = 0;
-
 	rcu_lockdep_assert(!lock_is_held(&sp->dep_map) &&
 			   !lock_is_held(&rcu_bh_lock_map) &&
 			   !lock_is_held(&rcu_lock_map) &&

@@ -318,27 +326,42 @@ static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 	mutex_lock(&sp->mutex);
 
 	/*
-	 * If there were no helpers, then we need to do two flips of
-	 * the index.  The first flip is required if there are any
-	 * outstanding SRCU readers even if there are no new readers
-	 * running concurrently with the first counter flip.
-	 *
-	 * The second flip is required when a new reader picks up
+	 * When in the previous grace perioad, if a reader picks up
 	 * the old value of the index, but does not increment its
 	 * counter until after its counters is summed/rechecked by
-	 * srcu_readers_active_idx_check().  In this case, the current SRCU
+	 * srcu_readers_active_idx_check(). In this case, the previous SRCU
 	 * grace period would be OK because the SRCU read-side critical
-	 * section started after this SRCU grace period started, so the
+	 * section started after the SRCU grace period started, so the
 	 * grace period is not required to wait for the reader.
 	 *
-	 * However, the next SRCU grace period would be waiting for the
-	 * other set of counters to go to zero, and therefore would not
-	 * wait for the reader, which would be very bad.  To avoid this
-	 * bad scenario, we flip and wait twice, clearing out both sets
-	 * of counters.
+	 * However, such leftover readers affect this new SRCU grace period.
+	 * So we have to wait for such readers. This wait_idx() should be
+	 * considerred as the wait_idx() in the flip_idx_and_wait() of
+	 * the previous grace perioad except that it is for leftover readers
+	 * started before this synchronize_srcu(). So when it returns,
+	 * there is no leftover readers that starts before this grace period.
+	 *
+	 * If there are some leftover readers that do not increment its
+	 * counter until after its counters is summed/rechecked by
+	 * srcu_readers_active_idx_check(), In this case, this SRCU
+	 * grace period would be OK as above comments says. We defines
+	 * such readers as leftover-leftover readers, we consider these
+	 * readers fteched index of (sp->completed + 1), it means they
+	 * are considerred as exactly the same as the readers after this
+	 * grace period.
+	 *
+	 * wait_idx() is expected very fast, because leftover readers
+	 * are unlikely produced.
 	 */
-	for (; idx < 2; idx++)
-		flip_idx_and_wait(sp, expedited);
+	wait_idx(sp, (sp->completed - 1) & 0x1, expedited);
+
+	/*
+	 * Starts a new grace period, this flip is required if there are
+	 * any outstanding SRCU readers even if there are no new readers
+	 * running concurrently with the counter flip.
+	 */
+	flip_idx_and_wait(sp, expedited);
+
 	mutex_unlock(&sp->mutex);
 }
 

Signature · 1 line

1.7.4.4

Quoted 1 line

From 4ddf62aaf2c4ebe6b9d4a1c596e8b43a678f1f0d Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Wed, 22 Feb 2012 14:12:02 +0800
Subject: [PATCH 3/3 RFC paul/rcu/srcu] srcu: flip only once for every grace period

flip_idx_and_wait() is not changed, and is split as two functions and only a short comments is added for smp_mb() E.

__synchronize_srcu() use a different algorithm for "leak" readers. detail is in the comments of the patch.

Signed-off-by Lai Jiangshan <[email protected]>

---
 kernel/srcu.c |  105 ++++++++++++++++++++++++++++++++++----------------------
 1 files changed, 64 insertions(+), 41 deletions(-)

kernel/srcu.c +0 -0

index a51ac48..346f9d7 100644

kernel/srcu.c +61 -41

+
+	/*
+	 * SRCU read-side critical sections are normally short, so wait
+	 * a small amount of time before possibly blocking.
+	 */
+	if (!srcu_readers_active_idx_check(sp, idx)) {
+		udelay(SYNCHRONIZE_SRCU_READER_DELAY);
+		while (!srcu_readers_active_idx_check(sp, idx)) {
+			if (expedited && ++ trycount < 10)
+				udelay(SYNCHRONIZE_SRCU_READER_DELAY);
+			else
+				schedule_timeout_interruptible(1);
+		}
+	}
+
+	/*
+	 * The following smp_mb() E pairs with srcu_read_unlock()'s
+	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
+	 * sees srcu_read_unlock()'s counter decrement, then any
+	 * of the current task's subsequent code will happen after
+	 * that SRCU read-side critical section.
+	 *
+	 * It also ensures the order between the above waiting and
+	 * the next flipping.
+	 */
+	smp_mb(); /* E */
+}
+
 /*
  * Flip the readers' index by incrementing ->completed, then wait
  * until there are no more readers using the counters referenced by

@@ -258,12 +289,12 @@ EXPORT_SYMBOL_GPL(__srcu_read_unlock);
  * Of course, it is possible that a reader might be delayed for the
  * full duration of flip_idx_and_wait() between fetching the
  * index and incrementing its counter.  This possibility is handled
- * by __synchronize_srcu() invoking flip_idx_and_wait() twice.
+ * by the next __synchronize_srcu() invoking wait_idx() for such readers
+ * before start a new grace perioad.
  */
 static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
 {
 	int idx;
-	int trycount = 0;
 
 	idx = sp->completed++ & 0x1;
 

@@ -278,28 +309,7 @@ static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
 	 */
 	smp_mb(); /* D */
 
-	/*
-	 * SRCU read-side critical sections are normally short, so wait
-	 * a small amount of time before possibly blocking.
-	 */
-	if (!srcu_readers_active_idx_check(sp, idx)) {
-		udelay(SYNCHRONIZE_SRCU_READER_DELAY);
-		while (!srcu_readers_active_idx_check(sp, idx)) {
-			if (expedited && ++ trycount < 10)
-				udelay(SYNCHRONIZE_SRCU_READER_DELAY);
-			else
-				schedule_timeout_interruptible(1);
-		}
-	}
-
-	/*
-	 * The following smp_mb() E pairs with srcu_read_unlock()'s
-	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
-	 * sees srcu_read_unlock()'s counter decrement, then any
-	 * of the current task's subsequent code will happen after
-	 * that SRCU read-side critical section.
-	 */
-	smp_mb(); /* E */
+	wait_idx(sp, idx, expedited);
 }
 
 /*

@@ -307,8 +317,6 @@ static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
  */
 static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 {
-	int idx = 0;
-
 	rcu_lockdep_assert(!lock_is_held(&sp->dep_map) &&
 			   !lock_is_held(&rcu_bh_lock_map) &&
 			   !lock_is_held(&rcu_lock_map) &&

@@ -318,27 +326,42 @@ static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 	mutex_lock(&sp->mutex);
 
 	/*
-	 * If there were no helpers, then we need to do two flips of
-	 * the index.  The first flip is required if there are any
-	 * outstanding SRCU readers even if there are no new readers
-	 * running concurrently with the first counter flip.
-	 *
-	 * The second flip is required when a new reader picks up
+	 * When in the previous grace perioad, if a reader picks up
 	 * the old value of the index, but does not increment its
 	 * counter until after its counters is summed/rechecked by
-	 * srcu_readers_active_idx_check().  In this case, the current SRCU
+	 * srcu_readers_active_idx_check(). In this case, the previous SRCU
 	 * grace period would be OK because the SRCU read-side critical
-	 * section started after this SRCU grace period started, so the
+	 * section started after the SRCU grace period started, so the
 	 * grace period is not required to wait for the reader.
 	 *
-	 * However, the next SRCU grace period would be waiting for the
-	 * other set of counters to go to zero, and therefore would not
-	 * wait for the reader, which would be very bad.  To avoid this
-	 * bad scenario, we flip and wait twice, clearing out both sets
-	 * of counters.
+	 * However, such leftover readers affect this new SRCU grace period.
+	 * So we have to wait for such readers. This wait_idx() should be
+	 * considerred as the wait_idx() in the flip_idx_and_wait() of
+	 * the previous grace perioad except that it is for leftover readers
+	 * started before this synchronize_srcu(). So when it returns,
+	 * there is no leftover readers that starts before this grace period.
+	 *
+	 * If there are some leftover readers that do not increment its
+	 * counter until after its counters is summed/rechecked by
+	 * srcu_readers_active_idx_check(), In this case, this SRCU
+	 * grace period would be OK as above comments says. We defines
+	 * such readers as leftover-leftover readers, we consider these
+	 * readers fteched index of (sp->completed + 1), it means they
+	 * are considerred as exactly the same as the readers after this
+	 * grace period.
+	 *
+	 * wait_idx() is expected very fast, because leftover readers
+	 * are unlikely produced.
 	 */
-	for (; idx < 2; idx++)
-		flip_idx_and_wait(sp, expedited);
+	wait_idx(sp, (sp->completed - 1) & 0x1, expedited);
+
+	/*
+	 * Starts a new grace period, this flip is required if there are
+	 * any outstanding SRCU readers even if there are no new readers
+	 * running concurrently with the counter flip.
+	 */
+	flip_idx_and_wait(sp, expedited);
+
 	mutex_unlock(&sp->mutex);
 }
 

Quoted 24 lines · Lai Jiangshan

Quoted 1 line

From 4ddf62aaf2c4ebe6b9d4a1c596e8b43a678f1f0d Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Wed, 22 Feb 2012 14:12:02 +0800
Subject: [PATCH 3/3 RFC paul/rcu/srcu] srcu: flip only once for every grace period

flip_idx_and_wait() is not changed, and is split as two functions and only a short comments is added for smp_mb() E.

__synchronize_srcu() use a different algorithm for "leak" readers. detail is in the comments of the patch.

Signed-off-by Lai Jiangshan <[email protected]>

---
 kernel/srcu.c |  105 ++++++++++++++++++++++++++++++++++----------------------
 1 files changed, 64 insertions(+), 41 deletions(-)

kernel/srcu.c +0 -0

index a51ac48..346f9d7 100644
@@ -249,6 +249,37 @@ EXPORT_SYMBOL_GPL(__srcu_read_unlock);
  */
 #define SYNCHRONIZE_SRCU_READER_DELAY 5
 

kernel/srcu.c EXPORT_SYMBOL_GPL(__srcu_read_unlock); · line 254

Quoted 3 lines

kernel/srcu.c +3 -0

+static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
+{
+	int trycount = 0;

Hi, Paul

smp_mb() D also needs to be moved here, could you fix it before push it.
I thought it(smp_mb()) always here in my mind, wrong assumption.

Sorry.

Thanks,
Lai

Quoted 143 lines

kernel/srcu.c +61 -41

+
+	/*
+	 * SRCU read-side critical sections are normally short, so wait
+	 * a small amount of time before possibly blocking.
+	 */
+	if (!srcu_readers_active_idx_check(sp, idx)) {
+		udelay(SYNCHRONIZE_SRCU_READER_DELAY);
+		while (!srcu_readers_active_idx_check(sp, idx)) {
+			if (expedited && ++ trycount < 10)
+				udelay(SYNCHRONIZE_SRCU_READER_DELAY);
+			else
+				schedule_timeout_interruptible(1);
+		}
+	}
+
+	/*
+	 * The following smp_mb() E pairs with srcu_read_unlock()'s
+	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
+	 * sees srcu_read_unlock()'s counter decrement, then any
+	 * of the current task's subsequent code will happen after
+	 * that SRCU read-side critical section.
+	 *
+	 * It also ensures the order between the above waiting and
+	 * the next flipping.
+	 */
+	smp_mb(); /* E */
+}
+
 /*
  * Flip the readers' index by incrementing ->completed, then wait
  * until there are no more readers using the counters referenced by

@@ -258,12 +289,12 @@ EXPORT_SYMBOL_GPL(__srcu_read_unlock);
  * Of course, it is possible that a reader might be delayed for the
  * full duration of flip_idx_and_wait() between fetching the
  * index and incrementing its counter.  This possibility is handled
- * by __synchronize_srcu() invoking flip_idx_and_wait() twice.
+ * by the next __synchronize_srcu() invoking wait_idx() for such readers
+ * before start a new grace perioad.
  */
 static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
 {
 	int idx;
-	int trycount = 0;
 
 	idx = sp->completed++ & 0x1;
 

@@ -278,28 +309,7 @@ static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
 	 */
 	smp_mb(); /* D */
 
-	/*
-	 * SRCU read-side critical sections are normally short, so wait
-	 * a small amount of time before possibly blocking.
-	 */
-	if (!srcu_readers_active_idx_check(sp, idx)) {
-		udelay(SYNCHRONIZE_SRCU_READER_DELAY);
-		while (!srcu_readers_active_idx_check(sp, idx)) {
-			if (expedited && ++ trycount < 10)
-				udelay(SYNCHRONIZE_SRCU_READER_DELAY);
-			else
-				schedule_timeout_interruptible(1);
-		}
-	}
-
-	/*
-	 * The following smp_mb() E pairs with srcu_read_unlock()'s
-	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
-	 * sees srcu_read_unlock()'s counter decrement, then any
-	 * of the current task's subsequent code will happen after
-	 * that SRCU read-side critical section.
-	 */
-	smp_mb(); /* E */
+	wait_idx(sp, idx, expedited);
 }
 
 /*

@@ -307,8 +317,6 @@ static void flip_idx_and_wait(struct srcu_struct *sp, bool expedited)
  */
 static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 {
-	int idx = 0;
-
 	rcu_lockdep_assert(!lock_is_held(&sp->dep_map) &&
 			   !lock_is_held(&rcu_bh_lock_map) &&
 			   !lock_is_held(&rcu_lock_map) &&

@@ -318,27 +326,42 @@ static void __synchronize_srcu(struct srcu_struct *sp, bool expedited)
 	mutex_lock(&sp->mutex);
 
 	/*
-	 * If there were no helpers, then we need to do two flips of
-	 * the index.  The first flip is required if there are any
-	 * outstanding SRCU readers even if there are no new readers
-	 * running concurrently with the first counter flip.
-	 *
-	 * The second flip is required when a new reader picks up
+	 * When in the previous grace perioad, if a reader picks up
 	 * the old value of the index, but does not increment its
 	 * counter until after its counters is summed/rechecked by
-	 * srcu_readers_active_idx_check().  In this case, the current SRCU
+	 * srcu_readers_active_idx_check(). In this case, the previous SRCU
 	 * grace period would be OK because the SRCU read-side critical
-	 * section started after this SRCU grace period started, so the
+	 * section started after the SRCU grace period started, so the
 	 * grace period is not required to wait for the reader.
 	 *
-	 * However, the next SRCU grace period would be waiting for the
-	 * other set of counters to go to zero, and therefore would not
-	 * wait for the reader, which would be very bad.  To avoid this
-	 * bad scenario, we flip and wait twice, clearing out both sets
-	 * of counters.
+	 * However, such leftover readers affect this new SRCU grace period.
+	 * So we have to wait for such readers. This wait_idx() should be
+	 * considerred as the wait_idx() in the flip_idx_and_wait() of
+	 * the previous grace perioad except that it is for leftover readers
+	 * started before this synchronize_srcu(). So when it returns,
+	 * there is no leftover readers that starts before this grace period.
+	 *
+	 * If there are some leftover readers that do not increment its
+	 * counter until after its counters is summed/rechecked by
+	 * srcu_readers_active_idx_check(), In this case, this SRCU
+	 * grace period would be OK as above comments says. We defines
+	 * such readers as leftover-leftover readers, we consider these
+	 * readers fteched index of (sp->completed + 1), it means they
+	 * are considerred as exactly the same as the readers after this
+	 * grace period.
+	 *
+	 * wait_idx() is expected very fast, because leftover readers
+	 * are unlikely produced.
 	 */
-	for (; idx < 2; idx++)
-		flip_idx_and_wait(sp, expedited);
+	wait_idx(sp, (sp->completed - 1) & 0x1, expedited);
+
+	/*
+	 * Starts a new grace period, this flip is required if there are
+	 * any outstanding SRCU readers even if there are no new readers
+	 * running concurrently with the counter flip.
+	 */
+	flip_idx_and_wait(sp, expedited);
+
 	mutex_unlock(&sp->mutex);
 }
 

From 77af819872ddab065d3a46758471b80f31b30e5e Mon Sep 17 00:00:00 2001

From 40724998e2d121c2b5a5bd75114625cfd9d4f9a9 Mon Sep 17 00:00:00 2001

Quoted 1 line

From 40724998e2d121c2b5a5bd75114625cfd9d4f9a9 Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Mon, 27 Feb 2012 14:22:47 +0800
Subject: [PATCH 2/2] srcu: implement Peter's checking algorithm

This patch implement the algorithm as Peter's:
https://lkml.org/lkml/2012/2/1/119

o Make the checking lock-free and we can perform parallel checking,
Although almost parallel checking makes no sense, but we need it when 1) the original checking task is preempted for long, 2) sychronize_srcu_expedited(), 3) avoid lock(see next)

o Since it is lock-free, we save a mutex in state machine for

	call_srcu().

o Remove the SRCU_REF_MASK and remove the coupling with the flipping.

	(so we can remove the preempt_disable() in future, but use
	 __this_cpu_inc() instead.)

o reduce a smp_mb(), simplify the comments and make the smp_mb() pairs
more intuitive.

Inspired-by Peter Zijlstra <[email protected]>

Signed-off-by Lai Jiangshan <[email protected]>

---
 include/linux/srcu.h |    7 +--
 kernel/srcu.c        |  137 ++++++++++++++++++++-----------------------------
 2 files changed, 57 insertions(+), 87 deletions(-)

include/linux/srcu.h +1 -6

index 5b49d41..15354db 100644
@@ -32,18 +32,13 @@
 
 struct srcu_struct_array {
 	unsigned long c[2];
+	unsigned long seq[2];
 };
 
-/* Bit definitions for field ->c above and ->snap below. */
-#define SRCU_USAGE_BITS		1
-#define SRCU_REF_MASK		(ULONG_MAX >> SRCU_USAGE_BITS)
-#define SRCU_USAGE_COUNT	(SRCU_REF_MASK + 1)
-
 struct srcu_struct {
 	unsigned completed;
 	struct srcu_struct_array __percpu *per_cpu_ref;
 	struct mutex mutex;
-	unsigned long snap[NR_CPUS];
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map dep_map;
 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */

kernel/srcu.c +56 -81

index 47ee35d..376b583 100644
@@ -73,10 +73,25 @@ EXPORT_SYMBOL_GPL(init_srcu_struct);
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 /*
+ * Returns approximate total sequence of readers on the specified rank
+ * of per-CPU counters.
+ */
+static unsigned long srcu_readers_seq_idx(struct srcu_struct *sp, int idx)
+{
+	int cpu;
+	unsigned long sum = 0;
+	unsigned long t;
+
+	for_each_possible_cpu(cpu) {
+		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->seq[idx]);
+		sum += t;
+	}
+	return sum;
+}
+
+/*
  * Returns approximate number of readers active on the specified rank
- * of per-CPU counters.  Also snapshots each counter's value in the
- * corresponding element of sp->snap[] for later use validating
- * the sum.
+ * of per-CPU counters.
  */
 static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 {

@@ -87,26 +102,36 @@ static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 	for_each_possible_cpu(cpu) {
 		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]);
 		sum += t;
-		sp->snap[cpu] = t;
 	}
-	return sum & SRCU_REF_MASK;
+	return sum;
 }
 
-/*
- * To be called from the update side after an index flip.  Returns true
- * if the modulo sum of the counters is stably zero, false if there is
- * some possibility of non-zero.
- */
 static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
+	unsigned long seq;
+
+	seq = srcu_readers_seq_idx(sp, idx);
+
+	/*
+	 * smp_mb() A pairs with smp_mb() B for critical section.
+	 * It ensures that the SRCU read-side critical section whose
+	 * read-lock is not seen by the following srcu_readers_active_idx()
+	 * will see any updates that before the current task performed before.
+	 * (So we don't need to care these readers this time)
+	 *
+	 * Also, if we see the increment of the seq, we must see the
+	 * increment of the active counter in the following
+	 * srcu_readers_active_idx().
+	 */
+	smp_mb(); /* A */
 
 	/*
 	 * Note that srcu_readers_active_idx() can incorrectly return
 	 * zero even though there is a pre-existing reader throughout.
 	 * To see this, suppose that task A is in a very long SRCU
 	 * read-side critical section that started on CPU 0, and that
-	 * no other reader exists, so that the modulo sum of the counters
+	 * no other reader exists, so that the sum of the counters
 	 * is equal to one.  Then suppose that task B starts executing
 	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
 	 * task C starts reading on CPU 0, so that its increment is not

@@ -122,53 +147,26 @@ static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 		return false;
 
 	/*
-	 * Since the caller recently flipped ->completed, we can see at
-	 * most one increment of each CPU's counter from this point
-	 * forward.  The reason for this is that the reader CPU must have
-	 * fetched the index before srcu_readers_active_idx checked
-	 * that CPU's counter, but not yet incremented its counter.
-	 * Its eventual counter increment will follow the read in
-	 * srcu_readers_active_idx(), and that increment is immediately
-	 * followed by smp_mb() B.  Because smp_mb() D is between
-	 * the ->completed flip and srcu_readers_active_idx()'s read,
-	 * that CPU's subsequent load of ->completed must see the new
-	 * value, and therefore increment the counter in the other rank.
-	 */
-	smp_mb(); /* A */
-
-	/*
-	 * Now, we check the ->snap array that srcu_readers_active_idx()
-	 * filled in from the per-CPU counter values. Since
-	 * __srcu_read_lock() increments the upper bits of the per-CPU
-	 * counter, an increment/decrement pair will change the value
-	 * of the counter.  Since there is only one possible increment,
-	 * the only way to wrap the counter is to have a huge number of
-	 * counter decrements, which requires a huge number of tasks and
-	 * huge SRCU read-side critical-section nesting levels, even on
-	 * 32-bit systems.
-	 *
-	 * All of the ways of confusing the readings require that the scan
-	 * in srcu_readers_active_idx() see the read-side task's decrement,
-	 * but not its increment.  However, between that decrement and
-	 * increment are smb_mb() B and C.  Either or both of these pair
-	 * with smp_mb() A above to ensure that the scan below will see
-	 * the read-side tasks's increment, thus noting a difference in
-	 * the counter values between the two passes.
+	 * Validation step, smp_mb() D pairs with smp_mb() C. If the above
+	 * srcu_readers_active_idx() see a decrement of the active counter
+	 * in srcu_read_unlock(), it should see one of these for corresponding
+	 * srcu_read_lock():
+	 * 	See the increment of the active counter,
+	 * 	Failed to see the increment of the active counter.
+	 * The second one can cause srcu_readers_active_idx() incorrectly
+	 * return zero, but it means the above srcu_readers_seq_idx() does not
+	 * see the increment of the seq(ref: comments of smp_mb() A),
+	 * and the following srcu_readers_seq_idx() sees the increment of
+	 * the seq. The seq is changed.
 	 *
-	 * Therefore, if srcu_readers_active_idx() returned zero, and
-	 * none of the counters changed, we know that the zero was the
-	 * correct sum.
-	 *
-	 * Of course, it is possible that a task might be delayed
-	 * for a very long time in __srcu_read_lock() after fetching
-	 * the index but before incrementing its counter.  This
-	 * possibility will be dealt with in __synchronize_srcu().
+	 * This smp_mb() D pairs with smp_mb() C for critical section.
+	 * then any of the current task's subsequent code will happen after
+	 * that SRCU read-side critical section whose read-unlock is seen in
+	 * srcu_readers_active_idx().
 	 */
-	for_each_possible_cpu(cpu)
-		if (sp->snap[cpu] !=
-		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
-			return false;  /* False zero reading! */
-	return true;
+	smp_mb(); /* D */
+
+	return srcu_readers_seq_idx(sp, idx) == seq;
 }
 
 /**

@@ -216,9 +214,9 @@ int __srcu_read_lock(struct srcu_struct *sp)
 	preempt_disable();
 	idx = rcu_dereference_index_check(sp->completed,
 					  rcu_read_lock_sched_held()) & 0x1;
-	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) +=
-		SRCU_USAGE_COUNT + 1;
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 1;
 	smp_mb(); /* B */  /* Avoid leaking the critical section. */
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->seq[idx]) += 1;
 	preempt_enable();
 	return idx;
 }

@@ -258,17 +256,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 	int trycount = 0;
 
 	/*
-	 * If a reader fetches the index before the ->completed increment,
-	 * but increments its counter after srcu_readers_active_idx_check()
-	 * sums it, then smp_mb() D will pair with __srcu_read_lock()'s
-	 * smp_mb() B to ensure that the SRCU read-side critical section
-	 * will see any updates that the current task performed before its
-	 * call to synchronize_srcu(), or to synchronize_srcu_expedited(),
-	 * as the case may be.
-	 */
-	smp_mb(); /* D */
-
-	/*
 	 * SRCU read-side critical sections are normally short, so wait
 	 * a small amount of time before possibly blocking.
 	 */

@@ -281,18 +268,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 				schedule_timeout_interruptible(1);
 		}
 	}
-
-	/*
-	 * The following smp_mb() E pairs with srcu_read_unlock()'s
-	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
-	 * sees srcu_read_unlock()'s counter decrement, then any
-	 * of the current task's subsequent code will happen after
-	 * that SRCU read-side critical section.
-	 *
-	 * It also ensures the order between the above waiting and
-	 * the next flipping.
-	 */
-	smp_mb(); /* E */
 }
 
 static void srcu_flip(struct srcu_struct *sp)

Signature · 1 line

1.7.4.4

Quoted 14 lines · Lai Jiangshan

Quoted 1 line

From 40724998e2d121c2b5a5bd75114625cfd9d4f9a9 Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Mon, 27 Feb 2012 14:22:47 +0800
Subject: [PATCH 2/2] srcu: implement Peter's checking algorithm

This patch implement the algorithm as Peter's:
https://lkml.org/lkml/2012/2/1/119

o Make the checking lock-free and we can perform parallel checking,
Although almost parallel checking makes no sense, but we need it when 1) the original checking task is preempted for long, 2) sychronize_srcu_expedited(), 3) avoid lock(see next)

o Since it is lock-free, we save a mutex in state machine for

Quoted 8 lines

	call_srcu().

o Remove the SRCU_REF_MASK and remove the coupling with the flipping.

	(so we can remove the preempt_disable() in future, but use
	 __this_cpu_inc() instead.)

o reduce a smp_mb(), simplify the comments and make the smp_mb() pairs
more intuitive.

Hello, Lai,

Interesting approach!

What happens given the following sequence of events?

o CPU 0 in srcu_readers_active_idx_check() invokes
srcu_readers_seq_idx(), getting some number back.

o CPU 0 invokes srcu_readers_active_idx(), summing the

	->c[] array up through CPU 3.

o CPU 1 invokes __srcu_read_lock(), and increments its counter

	but not yet its ->seq[] element.

o CPU 0 completes its summing of the ->c[] array, incorrectly
obtaining zero.

o CPU 0 invokes srcu_readers_seq_idx(), getting the same
number back that it got last time.

o In parallel with the previous step, CPU 1 executes out of order
(as permitted by the lack of a second memory barrier in __srcu_read_lock()), starting up the critical section before incrementing its ->seq[] element.

o Because CPU 0 is not aware that CPU 1 is an SRCU reader, it
completes the SRCU grace period before CPU 1 completes its SRCU read-side critical section.

This actually might be safe, but I need to think more about it. In the meantime, I figured I should ask your thoughts.

Thanx, Paul

Quoted 233 lines

Inspired-by Peter Zijlstra <[email protected]>

Signed-off-by Lai Jiangshan <[email protected]>

---
 include/linux/srcu.h |    7 +--
 kernel/srcu.c        |  137 ++++++++++++++++++++-----------------------------
 2 files changed, 57 insertions(+), 87 deletions(-)

include/linux/srcu.h +1 -6

index 5b49d41..15354db 100644
@@ -32,18 +32,13 @@
 
 struct srcu_struct_array {
 	unsigned long c[2];
+	unsigned long seq[2];
 };
 
-/* Bit definitions for field ->c above and ->snap below. */
-#define SRCU_USAGE_BITS		1
-#define SRCU_REF_MASK		(ULONG_MAX >> SRCU_USAGE_BITS)
-#define SRCU_USAGE_COUNT	(SRCU_REF_MASK + 1)
-
 struct srcu_struct {
 	unsigned completed;
 	struct srcu_struct_array __percpu *per_cpu_ref;
 	struct mutex mutex;
-	unsigned long snap[NR_CPUS];
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map dep_map;
 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */

kernel/srcu.c +56 -81

index 47ee35d..376b583 100644
@@ -73,10 +73,25 @@ EXPORT_SYMBOL_GPL(init_srcu_struct);
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 /*
+ * Returns approximate total sequence of readers on the specified rank
+ * of per-CPU counters.
+ */
+static unsigned long srcu_readers_seq_idx(struct srcu_struct *sp, int idx)
+{
+	int cpu;
+	unsigned long sum = 0;
+	unsigned long t;
+
+	for_each_possible_cpu(cpu) {
+		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->seq[idx]);
+		sum += t;
+	}
+	return sum;
+}
+
+/*
  * Returns approximate number of readers active on the specified rank
- * of per-CPU counters.  Also snapshots each counter's value in the
- * corresponding element of sp->snap[] for later use validating
- * the sum.
+ * of per-CPU counters.
  */
 static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 {

@@ -87,26 +102,36 @@ static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 	for_each_possible_cpu(cpu) {
 		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]);
 		sum += t;
-		sp->snap[cpu] = t;
 	}
-	return sum & SRCU_REF_MASK;
+	return sum;
 }
 
-/*
- * To be called from the update side after an index flip.  Returns true
- * if the modulo sum of the counters is stably zero, false if there is
- * some possibility of non-zero.
- */
 static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
+	unsigned long seq;
+
+	seq = srcu_readers_seq_idx(sp, idx);
+
+	/*
+	 * smp_mb() A pairs with smp_mb() B for critical section.
+	 * It ensures that the SRCU read-side critical section whose
+	 * read-lock is not seen by the following srcu_readers_active_idx()
+	 * will see any updates that before the current task performed before.
+	 * (So we don't need to care these readers this time)
+	 *
+	 * Also, if we see the increment of the seq, we must see the
+	 * increment of the active counter in the following
+	 * srcu_readers_active_idx().
+	 */
+	smp_mb(); /* A */
 
 	/*
 	 * Note that srcu_readers_active_idx() can incorrectly return
 	 * zero even though there is a pre-existing reader throughout.
 	 * To see this, suppose that task A is in a very long SRCU
 	 * read-side critical section that started on CPU 0, and that
-	 * no other reader exists, so that the modulo sum of the counters
+	 * no other reader exists, so that the sum of the counters
 	 * is equal to one.  Then suppose that task B starts executing
 	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
 	 * task C starts reading on CPU 0, so that its increment is not

@@ -122,53 +147,26 @@ static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 		return false;
 
 	/*
-	 * Since the caller recently flipped ->completed, we can see at
-	 * most one increment of each CPU's counter from this point
-	 * forward.  The reason for this is that the reader CPU must have
-	 * fetched the index before srcu_readers_active_idx checked
-	 * that CPU's counter, but not yet incremented its counter.
-	 * Its eventual counter increment will follow the read in
-	 * srcu_readers_active_idx(), and that increment is immediately
-	 * followed by smp_mb() B.  Because smp_mb() D is between
-	 * the ->completed flip and srcu_readers_active_idx()'s read,
-	 * that CPU's subsequent load of ->completed must see the new
-	 * value, and therefore increment the counter in the other rank.
-	 */
-	smp_mb(); /* A */
-
-	/*
-	 * Now, we check the ->snap array that srcu_readers_active_idx()
-	 * filled in from the per-CPU counter values. Since
-	 * __srcu_read_lock() increments the upper bits of the per-CPU
-	 * counter, an increment/decrement pair will change the value
-	 * of the counter.  Since there is only one possible increment,
-	 * the only way to wrap the counter is to have a huge number of
-	 * counter decrements, which requires a huge number of tasks and
-	 * huge SRCU read-side critical-section nesting levels, even on
-	 * 32-bit systems.
-	 *
-	 * All of the ways of confusing the readings require that the scan
-	 * in srcu_readers_active_idx() see the read-side task's decrement,
-	 * but not its increment.  However, between that decrement and
-	 * increment are smb_mb() B and C.  Either or both of these pair
-	 * with smp_mb() A above to ensure that the scan below will see
-	 * the read-side tasks's increment, thus noting a difference in
-	 * the counter values between the two passes.
+	 * Validation step, smp_mb() D pairs with smp_mb() C. If the above
+	 * srcu_readers_active_idx() see a decrement of the active counter
+	 * in srcu_read_unlock(), it should see one of these for corresponding
+	 * srcu_read_lock():
+	 * 	See the increment of the active counter,
+	 * 	Failed to see the increment of the active counter.
+	 * The second one can cause srcu_readers_active_idx() incorrectly
+	 * return zero, but it means the above srcu_readers_seq_idx() does not
+	 * see the increment of the seq(ref: comments of smp_mb() A),
+	 * and the following srcu_readers_seq_idx() sees the increment of
+	 * the seq. The seq is changed.
 	 *
-	 * Therefore, if srcu_readers_active_idx() returned zero, and
-	 * none of the counters changed, we know that the zero was the
-	 * correct sum.
-	 *
-	 * Of course, it is possible that a task might be delayed
-	 * for a very long time in __srcu_read_lock() after fetching
-	 * the index but before incrementing its counter.  This
-	 * possibility will be dealt with in __synchronize_srcu().
+	 * This smp_mb() D pairs with smp_mb() C for critical section.
+	 * then any of the current task's subsequent code will happen after
+	 * that SRCU read-side critical section whose read-unlock is seen in
+	 * srcu_readers_active_idx().
 	 */
-	for_each_possible_cpu(cpu)
-		if (sp->snap[cpu] !=
-		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
-			return false;  /* False zero reading! */
-	return true;
+	smp_mb(); /* D */
+
+	return srcu_readers_seq_idx(sp, idx) == seq;
 }
 
 /**

@@ -216,9 +214,9 @@ int __srcu_read_lock(struct srcu_struct *sp)
 	preempt_disable();
 	idx = rcu_dereference_index_check(sp->completed,
 					  rcu_read_lock_sched_held()) & 0x1;
-	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) +=
-		SRCU_USAGE_COUNT + 1;
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 1;
 	smp_mb(); /* B */  /* Avoid leaking the critical section. */
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->seq[idx]) += 1;
 	preempt_enable();
 	return idx;
 }

@@ -258,17 +256,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 	int trycount = 0;
 
 	/*
-	 * If a reader fetches the index before the ->completed increment,
-	 * but increments its counter after srcu_readers_active_idx_check()
-	 * sums it, then smp_mb() D will pair with __srcu_read_lock()'s
-	 * smp_mb() B to ensure that the SRCU read-side critical section
-	 * will see any updates that the current task performed before its
-	 * call to synchronize_srcu(), or to synchronize_srcu_expedited(),
-	 * as the case may be.
-	 */
-	smp_mb(); /* D */
-
-	/*
 	 * SRCU read-side critical sections are normally short, so wait
 	 * a small amount of time before possibly blocking.
 	 */

@@ -281,18 +268,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 				schedule_timeout_interruptible(1);
 		}
 	}
-
-	/*
-	 * The following smp_mb() E pairs with srcu_read_unlock()'s
-	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
-	 * sees srcu_read_unlock()'s counter decrement, then any
-	 * of the current task's subsequent code will happen after
-	 * that SRCU read-side critical section.
-	 *
-	 * It also ensures the order between the above waiting and
-	 * the next flipping.
-	 */
-	smp_mb(); /* E */
 }
 
 static void srcu_flip(struct srcu_struct *sp)

Signature · 1 line

1.7.4.4

Quoted 30 lines · Paul E. McKenney

Quoted 14 lines · Lai Jiangshan

Quoted 1 line

From 40724998e2d121c2b5a5bd75114625cfd9d4f9a9 Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Mon, 27 Feb 2012 14:22:47 +0800
Subject: [PATCH 2/2] srcu: implement Peter's checking algorithm

This patch implement the algorithm as Peter's:
https://lkml.org/lkml/2012/2/1/119

o Make the checking lock-free and we can perform parallel checking,
Although almost parallel checking makes no sense, but we need it when 1) the original checking task is preempted for long, 2) sychronize_srcu_expedited(), 3) avoid lock(see next)

o Since it is lock-free, we save a mutex in state machine for

Quoted 8 lines

	call_srcu().

o Remove the SRCU_REF_MASK and remove the coupling with the flipping.

	(so we can remove the preempt_disable() in future, but use
	 __this_cpu_inc() instead.)

o reduce a smp_mb(), simplify the comments and make the smp_mb() pairs
more intuitive.

Hello, Lai,

Interesting approach!

What happens given the following sequence of events?

Quoted 8 lines

o CPU 0 in srcu_readers_active_idx_check() invokes
srcu_readers_seq_idx(), getting some number back.

o CPU 0 invokes srcu_readers_active_idx(), summing the

	->c[] array up through CPU 3.

o CPU 1 invokes __srcu_read_lock(), and increments its counter

	but not yet its ->seq[] element.

Any __srcu_read_lock() whose increment of active counter is not seen by srcu_readers_active_idx() is considerred as "reader-started-after-this-srcu_readers_active_idx_check()", We don't need to wait.

As you said, this srcu C.S 's increment seq is not seen by above srcu_readers_seq_idx().

Quoted 6 lines

o CPU 0 completes its summing of the ->c[] array, incorrectly
obtaining zero.

o CPU 0 invokes srcu_readers_seq_idx(), getting the same
number back that it got last time.

If it incorrectly get zero, it means __srcu_read_unlock() is seen in srcu_readers_active_idx(), and it means the increment of seq is seen in this srcu_readers_seq_idx(), it is different from the above seq that it got last time.

increment of seq is not seen by above srcu_readers_seq_idx(), but is seen by later one, so the two returned seq is different, this is the core of Peter's algorithm, and this was written in the comments(Sorry for my bad English). Or maybe I miss your means in this mail.

Thanks,
Lai

Quoted 250 lines

o In parallel with the previous step, CPU 1 executes out of order
(as permitted by the lack of a second memory barrier in __srcu_read_lock()), starting up the critical section before incrementing its ->seq[] element.

o Because CPU 0 is not aware that CPU 1 is an SRCU reader, it
completes the SRCU grace period before CPU 1 completes its SRCU read-side critical section.

This actually might be safe, but I need to think more about it. In the meantime, I figured I should ask your thoughts.

Thanx, Paul

Quoted 233 lines

Inspired-by Peter Zijlstra <[email protected]>

Signed-off-by Lai Jiangshan <[email protected]>

---
 include/linux/srcu.h |    7 +--
 kernel/srcu.c        |  137 ++++++++++++++++++++-----------------------------
 2 files changed, 57 insertions(+), 87 deletions(-)

include/linux/srcu.h +1 -6

index 5b49d41..15354db 100644
@@ -32,18 +32,13 @@
 
 struct srcu_struct_array {
 	unsigned long c[2];
+	unsigned long seq[2];
 };
 
-/* Bit definitions for field ->c above and ->snap below. */
-#define SRCU_USAGE_BITS		1
-#define SRCU_REF_MASK		(ULONG_MAX >> SRCU_USAGE_BITS)
-#define SRCU_USAGE_COUNT	(SRCU_REF_MASK + 1)
-
 struct srcu_struct {
 	unsigned completed;
 	struct srcu_struct_array __percpu *per_cpu_ref;
 	struct mutex mutex;
-	unsigned long snap[NR_CPUS];
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map dep_map;
 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */

kernel/srcu.c +56 -81

index 47ee35d..376b583 100644
@@ -73,10 +73,25 @@ EXPORT_SYMBOL_GPL(init_srcu_struct);
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 /*
+ * Returns approximate total sequence of readers on the specified rank
+ * of per-CPU counters.
+ */
+static unsigned long srcu_readers_seq_idx(struct srcu_struct *sp, int idx)
+{
+	int cpu;
+	unsigned long sum = 0;
+	unsigned long t;
+
+	for_each_possible_cpu(cpu) {
+		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->seq[idx]);
+		sum += t;
+	}
+	return sum;
+}
+
+/*
  * Returns approximate number of readers active on the specified rank
- * of per-CPU counters.  Also snapshots each counter's value in the
- * corresponding element of sp->snap[] for later use validating
- * the sum.
+ * of per-CPU counters.
  */
 static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 {

@@ -87,26 +102,36 @@ static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 	for_each_possible_cpu(cpu) {
 		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]);
 		sum += t;
-		sp->snap[cpu] = t;
 	}
-	return sum & SRCU_REF_MASK;
+	return sum;
 }
 
-/*
- * To be called from the update side after an index flip.  Returns true
- * if the modulo sum of the counters is stably zero, false if there is
- * some possibility of non-zero.
- */
 static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
+	unsigned long seq;
+
+	seq = srcu_readers_seq_idx(sp, idx);
+
+	/*
+	 * smp_mb() A pairs with smp_mb() B for critical section.
+	 * It ensures that the SRCU read-side critical section whose
+	 * read-lock is not seen by the following srcu_readers_active_idx()
+	 * will see any updates that before the current task performed before.
+	 * (So we don't need to care these readers this time)
+	 *
+	 * Also, if we see the increment of the seq, we must see the
+	 * increment of the active counter in the following
+	 * srcu_readers_active_idx().
+	 */
+	smp_mb(); /* A */
 
 	/*
 	 * Note that srcu_readers_active_idx() can incorrectly return
 	 * zero even though there is a pre-existing reader throughout.
 	 * To see this, suppose that task A is in a very long SRCU
 	 * read-side critical section that started on CPU 0, and that
-	 * no other reader exists, so that the modulo sum of the counters
+	 * no other reader exists, so that the sum of the counters
 	 * is equal to one.  Then suppose that task B starts executing
 	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
 	 * task C starts reading on CPU 0, so that its increment is not

@@ -122,53 +147,26 @@ static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 		return false;
 
 	/*
-	 * Since the caller recently flipped ->completed, we can see at
-	 * most one increment of each CPU's counter from this point
-	 * forward.  The reason for this is that the reader CPU must have
-	 * fetched the index before srcu_readers_active_idx checked
-	 * that CPU's counter, but not yet incremented its counter.
-	 * Its eventual counter increment will follow the read in
-	 * srcu_readers_active_idx(), and that increment is immediately
-	 * followed by smp_mb() B.  Because smp_mb() D is between
-	 * the ->completed flip and srcu_readers_active_idx()'s read,
-	 * that CPU's subsequent load of ->completed must see the new
-	 * value, and therefore increment the counter in the other rank.
-	 */
-	smp_mb(); /* A */
-
-	/*
-	 * Now, we check the ->snap array that srcu_readers_active_idx()
-	 * filled in from the per-CPU counter values. Since
-	 * __srcu_read_lock() increments the upper bits of the per-CPU
-	 * counter, an increment/decrement pair will change the value
-	 * of the counter.  Since there is only one possible increment,
-	 * the only way to wrap the counter is to have a huge number of
-	 * counter decrements, which requires a huge number of tasks and
-	 * huge SRCU read-side critical-section nesting levels, even on
-	 * 32-bit systems.
-	 *
-	 * All of the ways of confusing the readings require that the scan
-	 * in srcu_readers_active_idx() see the read-side task's decrement,
-	 * but not its increment.  However, between that decrement and
-	 * increment are smb_mb() B and C.  Either or both of these pair
-	 * with smp_mb() A above to ensure that the scan below will see
-	 * the read-side tasks's increment, thus noting a difference in
-	 * the counter values between the two passes.
+	 * Validation step, smp_mb() D pairs with smp_mb() C. If the above
+	 * srcu_readers_active_idx() see a decrement of the active counter
+	 * in srcu_read_unlock(), it should see one of these for corresponding
+	 * srcu_read_lock():
+	 * 	See the increment of the active counter,
+	 * 	Failed to see the increment of the active counter.
+	 * The second one can cause srcu_readers_active_idx() incorrectly
+	 * return zero, but it means the above srcu_readers_seq_idx() does not
+	 * see the increment of the seq(ref: comments of smp_mb() A),
+	 * and the following srcu_readers_seq_idx() sees the increment of
+	 * the seq. The seq is changed.
 	 *
-	 * Therefore, if srcu_readers_active_idx() returned zero, and
-	 * none of the counters changed, we know that the zero was the
-	 * correct sum.
-	 *
-	 * Of course, it is possible that a task might be delayed
-	 * for a very long time in __srcu_read_lock() after fetching
-	 * the index but before incrementing its counter.  This
-	 * possibility will be dealt with in __synchronize_srcu().
+	 * This smp_mb() D pairs with smp_mb() C for critical section.
+	 * then any of the current task's subsequent code will happen after
+	 * that SRCU read-side critical section whose read-unlock is seen in
+	 * srcu_readers_active_idx().
 	 */
-	for_each_possible_cpu(cpu)
-		if (sp->snap[cpu] !=
-		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
-			return false;  /* False zero reading! */
-	return true;
+	smp_mb(); /* D */
+
+	return srcu_readers_seq_idx(sp, idx) == seq;
 }
 
 /**

@@ -216,9 +214,9 @@ int __srcu_read_lock(struct srcu_struct *sp)
 	preempt_disable();
 	idx = rcu_dereference_index_check(sp->completed,
 					  rcu_read_lock_sched_held()) & 0x1;
-	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) +=
-		SRCU_USAGE_COUNT + 1;
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 1;
 	smp_mb(); /* B */  /* Avoid leaking the critical section. */
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->seq[idx]) += 1;
 	preempt_enable();
 	return idx;
 }

@@ -258,17 +256,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 	int trycount = 0;
 
 	/*
-	 * If a reader fetches the index before the ->completed increment,
-	 * but increments its counter after srcu_readers_active_idx_check()
-	 * sums it, then smp_mb() D will pair with __srcu_read_lock()'s
-	 * smp_mb() B to ensure that the SRCU read-side critical section
-	 * will see any updates that the current task performed before its
-	 * call to synchronize_srcu(), or to synchronize_srcu_expedited(),
-	 * as the case may be.
-	 */
-	smp_mb(); /* D */
-
-	/*
 	 * SRCU read-side critical sections are normally short, so wait
 	 * a small amount of time before possibly blocking.
 	 */

@@ -281,18 +268,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 				schedule_timeout_interruptible(1);
 		}
 	}
-
-	/*
-	 * The following smp_mb() E pairs with srcu_read_unlock()'s
-	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
-	 * sees srcu_read_unlock()'s counter decrement, then any
-	 * of the current task's subsequent code will happen after
-	 * that SRCU read-side critical section.
-	 *
-	 * It also ensures the order between the above waiting and
-	 * the next flipping.
-	 */
-	smp_mb(); /* E */
 }
 
 static void srcu_flip(struct srcu_struct *sp)

Signature · 1 line

1.7.4.4

Quoted 61 lines · Lai Jiangshan

Quoted 30 lines · Paul E. McKenney

Quoted 14 lines · Lai Jiangshan

Quoted 1 line

From 40724998e2d121c2b5a5bd75114625cfd9d4f9a9 Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Mon, 27 Feb 2012 14:22:47 +0800
Subject: [PATCH 2/2] srcu: implement Peter's checking algorithm

This patch implement the algorithm as Peter's:
https://lkml.org/lkml/2012/2/1/119

o Make the checking lock-free and we can perform parallel checking,
Although almost parallel checking makes no sense, but we need it when 1) the original checking task is preempted for long, 2) sychronize_srcu_expedited(), 3) avoid lock(see next)

o Since it is lock-free, we save a mutex in state machine for

Quoted 8 lines

	call_srcu().

o Remove the SRCU_REF_MASK and remove the coupling with the flipping.

	(so we can remove the preempt_disable() in future, but use
	 __this_cpu_inc() instead.)

o reduce a smp_mb(), simplify the comments and make the smp_mb() pairs
more intuitive.

Hello, Lai,

Interesting approach!

What happens given the following sequence of events?

Quoted 8 lines

o CPU 0 in srcu_readers_active_idx_check() invokes
srcu_readers_seq_idx(), getting some number back.

o CPU 0 invokes srcu_readers_active_idx(), summing the

	->c[] array up through CPU 3.

o CPU 1 invokes __srcu_read_lock(), and increments its counter

	but not yet its ->seq[] element.

Any __srcu_read_lock() whose increment of active counter is not seen by srcu_readers_active_idx() is considerred as "reader-started-after-this-srcu_readers_active_idx_check()", We don't need to wait.

As you said, this srcu C.S 's increment seq is not seen by above srcu_readers_seq_idx().

Quoted 6 lines

o CPU 0 completes its summing of the ->c[] array, incorrectly
obtaining zero.

o CPU 0 invokes srcu_readers_seq_idx(), getting the same
number back that it got last time.

If it incorrectly get zero, it means __srcu_read_unlock() is seen in srcu_readers_active_idx(), and it means the increment of seq is seen in this srcu_readers_seq_idx(), it is different from the above seq that it got last time.

Quoted 5 lines

increment of seq is not seen by above srcu_readers_seq_idx(), but is seen by later one, so the two returned seq is different, this is the core of Peter's algorithm, and this was written in the comments(Sorry for my bad English). Or maybe I miss your means in this mail.

OK, good, this analysis agrees with what I was thinking.

So my next question is about the lock freedom. This lock freedom has to be limited in nature and carefully implemented. The reasons for this are:

1. Readers can block in any case, which can of course block both
synchronize_srcu_expedited() and synchronize_srcu().

2. Because only one CPU at a time can be incrementing ->completed,
some sort of lock with preemption disabling will of course be needed. Alternatively, an rt_mutex could be used for its priority-inheritance properties.

3. Once some CPU has incremented ->completed, all CPUs that might
still be summing up the old indexes must stop. If they don't, they might incorrectly call a too-short grace period in case of ->seq[]-sum overflow on 32-bit systems.

Or did you have something else in mind?

Thanx, Paul

Quoted 254 lines

Thanks,
Lai

Quoted 250 lines

o In parallel with the previous step, CPU 1 executes out of order
(as permitted by the lack of a second memory barrier in __srcu_read_lock()), starting up the critical section before incrementing its ->seq[] element.

o Because CPU 0 is not aware that CPU 1 is an SRCU reader, it
completes the SRCU grace period before CPU 1 completes its SRCU read-side critical section.

This actually might be safe, but I need to think more about it. In the meantime, I figured I should ask your thoughts.

Thanx, Paul

Quoted 233 lines

Inspired-by Peter Zijlstra <[email protected]>

Signed-off-by Lai Jiangshan <[email protected]>

---
 include/linux/srcu.h |    7 +--
 kernel/srcu.c        |  137 ++++++++++++++++++++-----------------------------
 2 files changed, 57 insertions(+), 87 deletions(-)

include/linux/srcu.h +1 -6

index 5b49d41..15354db 100644
@@ -32,18 +32,13 @@
 
 struct srcu_struct_array {
 	unsigned long c[2];
+	unsigned long seq[2];
 };
 
-/* Bit definitions for field ->c above and ->snap below. */
-#define SRCU_USAGE_BITS		1
-#define SRCU_REF_MASK		(ULONG_MAX >> SRCU_USAGE_BITS)
-#define SRCU_USAGE_COUNT	(SRCU_REF_MASK + 1)
-
 struct srcu_struct {
 	unsigned completed;
 	struct srcu_struct_array __percpu *per_cpu_ref;
 	struct mutex mutex;
-	unsigned long snap[NR_CPUS];
 #ifdef CONFIG_DEBUG_LOCK_ALLOC
 	struct lockdep_map dep_map;
 #endif /* #ifdef CONFIG_DEBUG_LOCK_ALLOC */

kernel/srcu.c +56 -81

index 47ee35d..376b583 100644
@@ -73,10 +73,25 @@ EXPORT_SYMBOL_GPL(init_srcu_struct);
 #endif /* #else #ifdef CONFIG_DEBUG_LOCK_ALLOC */
 
 /*
+ * Returns approximate total sequence of readers on the specified rank
+ * of per-CPU counters.
+ */
+static unsigned long srcu_readers_seq_idx(struct srcu_struct *sp, int idx)
+{
+	int cpu;
+	unsigned long sum = 0;
+	unsigned long t;
+
+	for_each_possible_cpu(cpu) {
+		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->seq[idx]);
+		sum += t;
+	}
+	return sum;
+}
+
+/*
  * Returns approximate number of readers active on the specified rank
- * of per-CPU counters.  Also snapshots each counter's value in the
- * corresponding element of sp->snap[] for later use validating
- * the sum.
+ * of per-CPU counters.
  */
 static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 {

@@ -87,26 +102,36 @@ static unsigned long srcu_readers_active_idx(struct srcu_struct *sp, int idx)
 	for_each_possible_cpu(cpu) {
 		t = ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]);
 		sum += t;
-		sp->snap[cpu] = t;
 	}
-	return sum & SRCU_REF_MASK;
+	return sum;
 }
 
-/*
- * To be called from the update side after an index flip.  Returns true
- * if the modulo sum of the counters is stably zero, false if there is
- * some possibility of non-zero.
- */
 static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 {
 	int cpu;
+	unsigned long seq;
+
+	seq = srcu_readers_seq_idx(sp, idx);
+
+	/*
+	 * smp_mb() A pairs with smp_mb() B for critical section.
+	 * It ensures that the SRCU read-side critical section whose
+	 * read-lock is not seen by the following srcu_readers_active_idx()
+	 * will see any updates that before the current task performed before.
+	 * (So we don't need to care these readers this time)
+	 *
+	 * Also, if we see the increment of the seq, we must see the
+	 * increment of the active counter in the following
+	 * srcu_readers_active_idx().
+	 */
+	smp_mb(); /* A */
 
 	/*
 	 * Note that srcu_readers_active_idx() can incorrectly return
 	 * zero even though there is a pre-existing reader throughout.
 	 * To see this, suppose that task A is in a very long SRCU
 	 * read-side critical section that started on CPU 0, and that
-	 * no other reader exists, so that the modulo sum of the counters
+	 * no other reader exists, so that the sum of the counters
 	 * is equal to one.  Then suppose that task B starts executing
 	 * srcu_readers_active_idx(), summing up to CPU 1, and then that
 	 * task C starts reading on CPU 0, so that its increment is not

@@ -122,53 +147,26 @@ static bool srcu_readers_active_idx_check(struct srcu_struct *sp, int idx)
 		return false;
 
 	/*
-	 * Since the caller recently flipped ->completed, we can see at
-	 * most one increment of each CPU's counter from this point
-	 * forward.  The reason for this is that the reader CPU must have
-	 * fetched the index before srcu_readers_active_idx checked
-	 * that CPU's counter, but not yet incremented its counter.
-	 * Its eventual counter increment will follow the read in
-	 * srcu_readers_active_idx(), and that increment is immediately
-	 * followed by smp_mb() B.  Because smp_mb() D is between
-	 * the ->completed flip and srcu_readers_active_idx()'s read,
-	 * that CPU's subsequent load of ->completed must see the new
-	 * value, and therefore increment the counter in the other rank.
-	 */
-	smp_mb(); /* A */
-
-	/*
-	 * Now, we check the ->snap array that srcu_readers_active_idx()
-	 * filled in from the per-CPU counter values. Since
-	 * __srcu_read_lock() increments the upper bits of the per-CPU
-	 * counter, an increment/decrement pair will change the value
-	 * of the counter.  Since there is only one possible increment,
-	 * the only way to wrap the counter is to have a huge number of
-	 * counter decrements, which requires a huge number of tasks and
-	 * huge SRCU read-side critical-section nesting levels, even on
-	 * 32-bit systems.
-	 *
-	 * All of the ways of confusing the readings require that the scan
-	 * in srcu_readers_active_idx() see the read-side task's decrement,
-	 * but not its increment.  However, between that decrement and
-	 * increment are smb_mb() B and C.  Either or both of these pair
-	 * with smp_mb() A above to ensure that the scan below will see
-	 * the read-side tasks's increment, thus noting a difference in
-	 * the counter values between the two passes.
+	 * Validation step, smp_mb() D pairs with smp_mb() C. If the above
+	 * srcu_readers_active_idx() see a decrement of the active counter
+	 * in srcu_read_unlock(), it should see one of these for corresponding
+	 * srcu_read_lock():
+	 * 	See the increment of the active counter,
+	 * 	Failed to see the increment of the active counter.
+	 * The second one can cause srcu_readers_active_idx() incorrectly
+	 * return zero, but it means the above srcu_readers_seq_idx() does not
+	 * see the increment of the seq(ref: comments of smp_mb() A),
+	 * and the following srcu_readers_seq_idx() sees the increment of
+	 * the seq. The seq is changed.
 	 *
-	 * Therefore, if srcu_readers_active_idx() returned zero, and
-	 * none of the counters changed, we know that the zero was the
-	 * correct sum.
-	 *
-	 * Of course, it is possible that a task might be delayed
-	 * for a very long time in __srcu_read_lock() after fetching
-	 * the index but before incrementing its counter.  This
-	 * possibility will be dealt with in __synchronize_srcu().
+	 * This smp_mb() D pairs with smp_mb() C for critical section.
+	 * then any of the current task's subsequent code will happen after
+	 * that SRCU read-side critical section whose read-unlock is seen in
+	 * srcu_readers_active_idx().
 	 */
-	for_each_possible_cpu(cpu)
-		if (sp->snap[cpu] !=
-		    ACCESS_ONCE(per_cpu_ptr(sp->per_cpu_ref, cpu)->c[idx]))
-			return false;  /* False zero reading! */
-	return true;
+	smp_mb(); /* D */
+
+	return srcu_readers_seq_idx(sp, idx) == seq;
 }
 
 /**

@@ -216,9 +214,9 @@ int __srcu_read_lock(struct srcu_struct *sp)
 	preempt_disable();
 	idx = rcu_dereference_index_check(sp->completed,
 					  rcu_read_lock_sched_held()) & 0x1;
-	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) +=
-		SRCU_USAGE_COUNT + 1;
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->c[idx]) += 1;
 	smp_mb(); /* B */  /* Avoid leaking the critical section. */
+	ACCESS_ONCE(this_cpu_ptr(sp->per_cpu_ref)->seq[idx]) += 1;
 	preempt_enable();
 	return idx;
 }

@@ -258,17 +256,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 	int trycount = 0;
 
 	/*
-	 * If a reader fetches the index before the ->completed increment,
-	 * but increments its counter after srcu_readers_active_idx_check()
-	 * sums it, then smp_mb() D will pair with __srcu_read_lock()'s
-	 * smp_mb() B to ensure that the SRCU read-side critical section
-	 * will see any updates that the current task performed before its
-	 * call to synchronize_srcu(), or to synchronize_srcu_expedited(),
-	 * as the case may be.
-	 */
-	smp_mb(); /* D */
-
-	/*
 	 * SRCU read-side critical sections are normally short, so wait
 	 * a small amount of time before possibly blocking.
 	 */

@@ -281,18 +268,6 @@ static void wait_idx(struct srcu_struct *sp, int idx, bool expedited)
 				schedule_timeout_interruptible(1);
 		}
 	}
-
-	/*
-	 * The following smp_mb() E pairs with srcu_read_unlock()'s
-	 * smp_mb C to ensure that if srcu_readers_active_idx_check()
-	 * sees srcu_read_unlock()'s counter decrement, then any
-	 * of the current task's subsequent code will happen after
-	 * that SRCU read-side critical section.
-	 *
-	 * It also ensures the order between the above waiting and
-	 * the next flipping.
-	 */
-	smp_mb(); /* E */
 }
 
 static void srcu_flip(struct srcu_struct *sp)

Signature · 1 line

1.7.4.4

Quoted 86 lines · Paul E. McKenney

Quoted 61 lines · Lai Jiangshan

Quoted 30 lines · Paul E. McKenney

Quoted 14 lines · Lai Jiangshan

Quoted 1 line

From 40724998e2d121c2b5a5bd75114625cfd9d4f9a9 Mon Sep 17 00:00:00 2001

From: Lai Jiangshan <[email protected]>
Date: Mon, 27 Feb 2012 14:22:47 +0800
Subject: [PATCH 2/2] srcu: implement Peter's checking algorithm

This patch implement the algorithm as Peter's:
https://lkml.org/lkml/2012/2/1/119

o Make the checking lock-free and we can perform parallel checking,
Although almost parallel checking makes no sense, but we need it when 1) the original checking task is preempted for long, 2) sychronize_srcu_expedited(), 3) avoid lock(see next)

o Since it is lock-free, we save a mutex in state machine for

Quoted 8 lines

	call_srcu().

o Remove the SRCU_REF_MASK and remove the coupling with the flipping.

	(so we can remove the preempt_disable() in future, but use
	 __this_cpu_inc() instead.)

o reduce a smp_mb(), simplify the comments and make the smp_mb() pairs
more intuitive.

Hello, Lai,

Interesting approach!

What happens given the following sequence of events?

Quoted 8 lines

o CPU 0 in srcu_readers_active_idx_check() invokes
srcu_readers_seq_idx(), getting some number back.

o CPU 0 invokes srcu_readers_active_idx(), summing the

	->c[] array up through CPU 3.

o CPU 1 invokes __srcu_read_lock(), and increments its counter

	but not yet its ->seq[] element.

Any __srcu_read_lock() whose increment of active counter is not seen by srcu_readers_active_idx() is considerred as "reader-started-after-this-srcu_readers_active_idx_check()", We don't need to wait.

As you said, this srcu C.S 's increment seq is not seen by above srcu_readers_seq_idx().

Quoted 6 lines

o CPU 0 completes its summing of the ->c[] array, incorrectly
obtaining zero.

o CPU 0 invokes srcu_readers_seq_idx(), getting the same
number back that it got last time.

If it incorrectly get zero, it means __srcu_read_unlock() is seen in srcu_readers_active_idx(), and it means the increment of seq is seen in this srcu_readers_seq_idx(), it is different from the above seq that it got last time.

Quoted 5 lines

increment of seq is not seen by above srcu_readers_seq_idx(), but is seen by later one, so the two returned seq is different, this is the core of Peter's algorithm, and this was written in the comments(Sorry for my bad English). Or maybe I miss your means in this mail.

OK, good, this analysis agrees with what I was thinking.

So my next question is about the lock freedom. This lock freedom has to be limited in nature and carefully implemented. The reasons for this are:

1. Readers can block in any case, which can of course block both
synchronize_srcu_expedited() and synchronize_srcu().

2. Because only one CPU at a time can be incrementing ->completed,
some sort of lock with preemption disabling will of course be needed. Alternatively, an rt_mutex could be used for its priority-inheritance properties.

3. Once some CPU has incremented ->completed, all CPUs that might
still be summing up the old indexes must stop. If they don't, they might incorrectly call a too-short grace period in case of ->seq[]-sum overflow on 32-bit systems.