Skip to contentSkip to conversation

rcu_nest: fix concurrency issues

PATCH Superseded Junchang Wang 2 participants 5 messages Apr 30, 2019 – May 8, 2019

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 rcu_nest: fix concurrency issues

Variable "rcu_gp_ctr" is incremented by the updater and is fetched by readers concurrently. So protect this variable by using READ_ONCE() and WRITE_ONCE().

Per-thread variable "rcu_read_gp" is updated by the reader and is read by the updater. So protect it by using READ_ONCE() and WRITE_ONCE().

The type of "rcu_gp_ctr" is changed to unsigned long because the behavior of the overflow of a signed long integer is not well defined in C yet.

Refine the code snippet in "rcu_read_lock" that allows a reader to start over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of "rcu_reader_gp", the reader starts over.

---
 CodeSamples/defer/rcu_nest.c |  5 +++--
 CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++--------
 2 files changed, 20 insertions(+), 10 deletions(-)
CodeSamples/defer/rcu_nest.c +3 -2
index 64e4087..362f466 100644
@@ -35,7 +35,7 @@ void synchronize_rcu(void)
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT;
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT);
 	smp_mb();
 
 	/*
@@ -45,7 +45,8 @@ void synchronize_rcu(void)
 
 	for_each_thread(t) {
 		while (rcu_gp_ongoing(t) &&
-		       ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+		       ((READ_ONCE(per_thread(rcu_reader_gp, t)) -
+			 rcu_gp_ctr) < 0)) {
 			/*@@@ poll(NULL, 0, 10); */
 			barrier();
 		}
CodeSamples/defer/rcu_nest.h +17 -8
index bcc4cde..65ce203 100644
@@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock);
 #define RCU_GP_CTR_SHIFT 7
 #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT)
 #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1)
-long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
-DEFINE_PER_THREAD(long, rcu_reader_gp);
+#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8)
+unsigned long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
+DEFINE_PER_THREAD(unsigned long, rcu_reader_gp);
 
 static inline int rcu_gp_ongoing(int cpu)
 {
@@ -39,8 +40,8 @@ static void rcu_init(void)
 
 static void rcu_read_lock(void)
 {
-	long tmp;
-	long *rrgp;
+	unsigned long tmp;
+	unsigned long *rrgp;
 
 	/*
 	 * If this is the outermost RCU read-side critical section,
@@ -52,13 +53,21 @@ static void rcu_read_lock(void)
 retry:
 	tmp = *rrgp;
 	if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)
-		tmp = rcu_gp_ctr;
+		tmp = READ_ONCE(rcu_gp_ctr);
 	tmp++;
-	*rrgp = tmp;
+	WRITE_ONCE(*rrgp, tmp);
 	smp_mb();
+
+	/*
+	 * A reader could be suspended in between fetching the value of *rrgp
+	 * and writting the updated value back into *rrgp. During this
+	 * time period, the grace-period counter might have advanced very far.
+	 * In this case, we force the reader to start over.
+	 */
+
 	if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
-	    ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
-		(*rrgp)--;
+	    (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) {
+		WRITE_ONCE(*rrgp, *rrgp - 1);
 		goto retry;
 	}
 }
Signature · 1 line
2.7.4
#1 lore raw
Quoted 10 lines · Junchang Wang

Variable "rcu_gp_ctr" is incremented by the updater and is fetched by readers concurrently. So protect this variable by using READ_ONCE() and WRITE_ONCE().

Per-thread variable "rcu_read_gp" is updated by the reader and is read by the updater. So protect it by using READ_ONCE() and WRITE_ONCE().

The type of "rcu_gp_ctr" is changed to unsigned long because the behavior of the overflow of a signed long integer is not well defined in C yet.

Quoted 8 lines

Refine the code snippet in "rcu_read_lock" that allows a reader to start over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of "rcu_reader_gp", the reader starts over.

First, thank you for doing this! Lots of good improvements!!!

A few comments below.

Thanx, Paul

Quoted 59 lines
---
 CodeSamples/defer/rcu_nest.c |  5 +++--
 CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++--------
 2 files changed, 20 insertions(+), 10 deletions(-)
CodeSamples/defer/rcu_nest.c +3 -2
index 64e4087..362f466 100644
@@ -35,7 +35,7 @@ void synchronize_rcu(void)
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT;
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT);
 	smp_mb();
 
 	/*
@@ -45,7 +45,8 @@ void synchronize_rcu(void)
 
 	for_each_thread(t) {
 		while (rcu_gp_ongoing(t) &&
-		       ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+		       ((READ_ONCE(per_thread(rcu_reader_gp, t)) -
+			 rcu_gp_ctr) < 0)) {
 			/*@@@ poll(NULL, 0, 10); */
 			barrier();
 		}
CodeSamples/defer/rcu_nest.h +5 -4
index bcc4cde..65ce203 100644
@@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock);
 #define RCU_GP_CTR_SHIFT 7
 #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT)
 #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1)
-long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
-DEFINE_PER_THREAD(long, rcu_reader_gp);
+#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8)
+unsigned long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
+DEFINE_PER_THREAD(unsigned long, rcu_reader_gp);
 
 static inline int rcu_gp_ongoing(int cpu)
 {
@@ -39,8 +40,8 @@ static void rcu_init(void)
 
 static void rcu_read_lock(void)
 {
-	long tmp;
-	long *rrgp;
+	unsigned long tmp;
+	unsigned long *rrgp;
 
 	/*
 	 * If this is the outermost RCU read-side critical section,
@@ -52,13 +53,21 @@ static void rcu_read_lock(void)
 retry:
 	tmp = *rrgp;
 	if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 63

Quoted 10 lines
CodeSamples/defer/rcu_nest.h +6 -2
-		tmp = rcu_gp_ctr;
+		tmp = READ_ONCE(rcu_gp_ctr);
 	tmp++;
-	*rrgp = tmp;
+	WRITE_ONCE(*rrgp, tmp);
 	smp_mb();
+
+	/*
+	 * A reader could be suspended in between fetching the value of *rrgp
+	 * and writting the updated value back into *rrgp. During this

s/writting/writing/

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 69

Quoted 8 lines
CodeSamples/defer/rcu_nest.h +5 -2
+	 * time period, the grace-period counter might have advanced very far.
+	 * In this case, we force the reader to start over.
+	 */
+
 	if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
-	    ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
-		(*rrgp)--;
+	    (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) {

Does this work correctly if the value of tmp is just a bit less than ULONG_MAX? It looks to me like it does not.

Quoted 7 lines
CodeSamples/defer/rcu_nest.h +1 -0
+		WRITE_ONCE(*rrgp, *rrgp - 1);
 		goto retry;
 	}
 }
Signature · 1 line
2.7.4
#2 lore raw
Quoted 98 lines · Paul E. McKenney
Quoted 10 lines · Junchang Wang

Variable "rcu_gp_ctr" is incremented by the updater and is fetched by readers concurrently. So protect this variable by using READ_ONCE() and WRITE_ONCE().

Per-thread variable "rcu_read_gp" is updated by the reader and is read by the updater. So protect it by using READ_ONCE() and WRITE_ONCE().

The type of "rcu_gp_ctr" is changed to unsigned long because the behavior of the overflow of a signed long integer is not well defined in C yet.

Quoted 8 lines

Refine the code snippet in "rcu_read_lock" that allows a reader to start over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of "rcu_reader_gp", the reader starts over.

First, thank you for doing this! Lots of good improvements!!!

A few comments below.

Thanx, Paul

Quoted 59 lines
---
 CodeSamples/defer/rcu_nest.c |  5 +++--
 CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++--------
 2 files changed, 20 insertions(+), 10 deletions(-)
CodeSamples/defer/rcu_nest.c +3 -2
index 64e4087..362f466 100644
@@ -35,7 +35,7 @@ void synchronize_rcu(void)
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT;
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT);
 	smp_mb();
 
 	/*
@@ -45,7 +45,8 @@ void synchronize_rcu(void)
 
 	for_each_thread(t) {
 		while (rcu_gp_ongoing(t) &&
-		       ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+		       ((READ_ONCE(per_thread(rcu_reader_gp, t)) -
+			 rcu_gp_ctr) < 0)) {
 			/*@@@ poll(NULL, 0, 10); */
 			barrier();
 		}
CodeSamples/defer/rcu_nest.h +5 -4
index bcc4cde..65ce203 100644
@@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock);
 #define RCU_GP_CTR_SHIFT 7
 #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT)
 #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1)
-long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
-DEFINE_PER_THREAD(long, rcu_reader_gp);
+#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8)
+unsigned long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
+DEFINE_PER_THREAD(unsigned long, rcu_reader_gp);
 
 static inline int rcu_gp_ongoing(int cpu)
 {
@@ -39,8 +40,8 @@ static void rcu_init(void)
 
 static void rcu_read_lock(void)
 {
-	long tmp;
-	long *rrgp;
+	unsigned long tmp;
+	unsigned long *rrgp;
 
 	/*
 	 * If this is the outermost RCU read-side critical section,
@@ -52,13 +53,21 @@ static void rcu_read_lock(void)
 retry:
 	tmp = *rrgp;
 	if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 63

Quoted 10 lines
CodeSamples/defer/rcu_nest.h +6 -2
-		tmp = rcu_gp_ctr;
+		tmp = READ_ONCE(rcu_gp_ctr);
 	tmp++;
-	*rrgp = tmp;
+	WRITE_ONCE(*rrgp, tmp);
 	smp_mb();
+
+	/*
+	 * A reader could be suspended in between fetching the value of *rrgp
+	 * and writting the updated value back into *rrgp. During this

s/writting/writing/

Quoted 12 lines

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 69

Quoted 8 lines
CodeSamples/defer/rcu_nest.h +5 -2
+	 * time period, the grace-period counter might have advanced very far.
+	 * In this case, we force the reader to start over.
+	 */
+
 	if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
-	    ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
-		(*rrgp)--;
+	    (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) {

Does this work correctly if the value of tmp is just a bit less than ULONG_MAX? It looks to me like it does not.

Hi Paul,

Thanks for reviewing the code. Yes, the statement you pointed out is buggy when both rcu_gp_ctr and tmp are close to ULONG_MAX. I was trying to rewrite to code to check for true overflow, but, as you have pointed out in a previous mail, that could make the code complex if we want to be exact. So I go back to the logic you used before. Please check the updated code below:

+
+ /*
+ * A reader could be suspended in between fetching the value of *rrgp
+ * and writting the updated value back into *rrgp. During this
+ * time period, the grace-period counter might have advanced very far.
+ * In this case, we force the reader to start over.
+ */
+
if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
- ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
- (*rrgp)--;
+ (READ_ONCE(rcu_gp_ctr) - (tmp-1)) > MAX_GP_ADV_DISTANCE) {
+ WRITE_ONCE(*rrgp, *rrgp - 1);
goto retry;
}
}

Note that if *rcu_gp_ctr* has not been changed since its value was first read and stored in *tmp*, then its value is less than *tmp* by 1. Since both *rcu_gp_ctr* and *tmp* are now unsigned long integers, (rcu_gp_ctr - tmp) will generate a very large integer number, so I replace that with (READ_ONCE(rcu_gp_ctr) - (tmp-1)). Please let me know if that looks OK.

Thanks,
--Junchang

Quoted 8 lines
Quoted 7 lines
CodeSamples/defer/rcu_nest.h +1 -0
+		WRITE_ONCE(*rrgp, *rrgp - 1);
 		goto retry;
 	}
 }
Signature · 1 line
2.7.4
#3 lore raw
Quoted 138 lines · Junchang Wang
Quoted 98 lines · Paul E. McKenney
Quoted 10 lines · Junchang Wang

Variable "rcu_gp_ctr" is incremented by the updater and is fetched by readers concurrently. So protect this variable by using READ_ONCE() and WRITE_ONCE().

Per-thread variable "rcu_read_gp" is updated by the reader and is read by the updater. So protect it by using READ_ONCE() and WRITE_ONCE().

The type of "rcu_gp_ctr" is changed to unsigned long because the behavior of the overflow of a signed long integer is not well defined in C yet.

Quoted 8 lines

Refine the code snippet in "rcu_read_lock" that allows a reader to start over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of "rcu_reader_gp", the reader starts over.

First, thank you for doing this! Lots of good improvements!!!

A few comments below.

Thanx, Paul

Quoted 59 lines
---
 CodeSamples/defer/rcu_nest.c |  5 +++--
 CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++--------
 2 files changed, 20 insertions(+), 10 deletions(-)
CodeSamples/defer/rcu_nest.c +3 -2
index 64e4087..362f466 100644
@@ -35,7 +35,7 @@ void synchronize_rcu(void)
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT;
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT);
 	smp_mb();
 
 	/*
@@ -45,7 +45,8 @@ void synchronize_rcu(void)
 
 	for_each_thread(t) {
 		while (rcu_gp_ongoing(t) &&
-		       ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+		       ((READ_ONCE(per_thread(rcu_reader_gp, t)) -
+			 rcu_gp_ctr) < 0)) {
 			/*@@@ poll(NULL, 0, 10); */
 			barrier();
 		}
CodeSamples/defer/rcu_nest.h +5 -4
index bcc4cde..65ce203 100644
@@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock);
 #define RCU_GP_CTR_SHIFT 7
 #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT)
 #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1)
-long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
-DEFINE_PER_THREAD(long, rcu_reader_gp);
+#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8)
+unsigned long rcu_gp_ctr = 0;	/* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
+DEFINE_PER_THREAD(unsigned long, rcu_reader_gp);
 
 static inline int rcu_gp_ongoing(int cpu)
 {
@@ -39,8 +40,8 @@ static void rcu_init(void)
 
 static void rcu_read_lock(void)
 {
-	long tmp;
-	long *rrgp;
+	unsigned long tmp;
+	unsigned long *rrgp;
 
 	/*
 	 * If this is the outermost RCU read-side critical section,
@@ -52,13 +53,21 @@ static void rcu_read_lock(void)
 retry:
 	tmp = *rrgp;
 	if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 63

Quoted 10 lines
CodeSamples/defer/rcu_nest.h +6 -2
-		tmp = rcu_gp_ctr;
+		tmp = READ_ONCE(rcu_gp_ctr);
 	tmp++;
-	*rrgp = tmp;
+	WRITE_ONCE(*rrgp, tmp);
 	smp_mb();
+
+	/*
+	 * A reader could be suspended in between fetching the value of *rrgp
+	 * and writting the updated value back into *rrgp. During this

s/writting/writing/

Quoted 12 lines

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 69

Quoted 8 lines
CodeSamples/defer/rcu_nest.h +5 -2
+	 * time period, the grace-period counter might have advanced very far.
+	 * In this case, we force the reader to start over.
+	 */
+
 	if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
-	    ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
-		(*rrgp)--;
+	    (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) {

Does this work correctly if the value of tmp is just a bit less than ULONG_MAX? It looks to me like it does not.

Hi Paul,

Thanks for reviewing the code. Yes, the statement you pointed out is buggy when both rcu_gp_ctr and tmp are close to ULONG_MAX. I was trying to rewrite to code to check for true overflow, but, as you have pointed out in a previous mail, that could make the code complex if we want to be exact. So I go back to the logic you used before. Please check the updated code below:

CodeSamples/defer/rcu_nest.h +10 -2
+
+	/*
+	 * A reader could be suspended in between fetching the value of *rrgp
+	 * and writting the updated value back into *rrgp. During this
+	 * time period, the grace-period counter might have advanced very far.
+	 * In this case, we force the reader to start over.
+	 */
+
 	if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
-	    ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
-		(*rrgp)--;
+	    (READ_ONCE(rcu_gp_ctr) - (tmp-1)) > MAX_GP_ADV_DISTANCE) {
+		WRITE_ONCE(*rrgp, *rrgp - 1);
 		goto retry;
 	}
 }
Quoted 5 lines

Note that if *rcu_gp_ctr* has not been changed since its value was first read and stored in *tmp*, then its value is less than *tmp* by 1. Since both *rcu_gp_ctr* and *tmp* are now unsigned long integers, (rcu_gp_ctr - tmp) will generate a very large integer number, so I replace that with (READ_ONCE(rcu_gp_ctr) - (tmp-1)). Please let me know if that looks OK.

There are a couple of ways to make this work. One of them is as shown in time_after() in the Linux kernel, and another is as shown in ULONG_CMP_GE().

And yes, the C standard is less helpful than it might be in this area. You can thank old ones-complement machines and newer machines that trap on signed integer overflow. ;-)

Thanx, Paul

Quoted 12 lines

Thanks,
--Junchang

Quoted 8 lines
Quoted 7 lines
CodeSamples/defer/rcu_nest.h +1 -0
+		WRITE_ONCE(*rrgp, *rrgp - 1);
 		goto retry;
 	}
 }
Signature · 1 line
2.7.4
#4 lore raw
Quoted 140 lines · Paul E. McKenney
Quoted 138 lines · Junchang Wang
Quoted 107 lines · Paul E. McKenney
Quoted 10 lines · Junchang Wang

Variable "rcu_gp_ctr" is incremented by the updater and is fetched by readers concurrently. So protect this variable by using READ_ONCE() and WRITE_ONCE().

Per-thread variable "rcu_read_gp" is updated by the reader and is read by the updater. So protect it by using READ_ONCE() and WRITE_ONCE().

The type of "rcu_gp_ctr" is changed to unsigned long because the behavior of the overflow of a signed long integer is not well defined in C yet.

Quoted 8 lines

Refine the code snippet in "rcu_read_lock" that allows a reader to start over. In this version, we add micro MAX_GP_ADV_DISTANCE which is by default set to (RCU_GP_CTR_NEST_MASK << 8). Once a reader notices that MAX_GP_ADV_DISTANCE grace-periods have elapsed since fetching the value of "rcu_reader_gp", the reader starts over.

First, thank you for doing this! Lots of good improvements!!!

A few comments below.

Thanx, Paul

Quoted 59 lines
---
 CodeSamples/defer/rcu_nest.c |  5 +++--
 CodeSamples/defer/rcu_nest.h | 25 +++++++++++++++++--------
 2 files changed, 20 insertions(+), 10 deletions(-)
CodeSamples/defer/rcu_nest.c +3 -2
index 64e4087..362f466 100644
@@ -35,7 +35,7 @@ void synchronize_rcu(void)
 
   /* Advance to a new grace-period number, enforce ordering. */
 
-  rcu_gp_ctr += RCU_GP_CTR_BOTTOM_BIT;
+  WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + RCU_GP_CTR_BOTTOM_BIT);
   smp_mb();
 
   /*
@@ -45,7 +45,8 @@ void synchronize_rcu(void)
 
   for_each_thread(t) {
           while (rcu_gp_ongoing(t) &&
-                 ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+                 ((READ_ONCE(per_thread(rcu_reader_gp, t)) -
+                   rcu_gp_ctr) < 0)) {
                   /*@@@ poll(NULL, 0, 10); */
                   barrier();
           }
CodeSamples/defer/rcu_nest.h +5 -4
index bcc4cde..65ce203 100644
@@ -24,8 +24,9 @@ DEFINE_SPINLOCK(rcu_gp_lock);
 #define RCU_GP_CTR_SHIFT 7
 #define RCU_GP_CTR_BOTTOM_BIT (1 << RCU_GP_CTR_SHIFT)
 #define RCU_GP_CTR_NEST_MASK (RCU_GP_CTR_BOTTOM_BIT - 1)
-long rcu_gp_ctr = 0;      /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
-DEFINE_PER_THREAD(long, rcu_reader_gp);
+#define MAX_GP_ADV_DISTANCE (RCU_GP_CTR_NEST_MASK << 8)
+unsigned long rcu_gp_ctr = 0;     /* increment by RCU_GP_CTR_BOTTOM_BIT each gp. */
+DEFINE_PER_THREAD(unsigned long, rcu_reader_gp);
 
 static inline int rcu_gp_ongoing(int cpu)
 {
@@ -39,8 +40,8 @@ static void rcu_init(void)
 
 static void rcu_read_lock(void)
 {
-  long tmp;
-  long *rrgp;
+  unsigned long tmp;
+  unsigned long *rrgp;
 
   /*
    * If this is the outermost RCU read-side critical section,
@@ -52,13 +53,21 @@ static void rcu_read_lock(void)
 retry:
   tmp = *rrgp;
   if ((tmp & RCU_GP_CTR_NEST_MASK) == 0)

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 63

Quoted 10 lines
CodeSamples/defer/rcu_nest.h +6 -2
-          tmp = rcu_gp_ctr;
+          tmp = READ_ONCE(rcu_gp_ctr);
   tmp++;
-  *rrgp = tmp;
+  WRITE_ONCE(*rrgp, tmp);
   smp_mb();
+
+  /*
+   * A reader could be suspended in between fetching the value of *rrgp
+   * and writting the updated value back into *rrgp. During this

s/writting/writing/

CodeSamples/defer/rcu_nest.h static void rcu_read_lock(void) · line 69

Quoted 8 lines
CodeSamples/defer/rcu_nest.h +5 -2
+   * time period, the grace-period counter might have advanced very far.
+   * In this case, we force the reader to start over.
+   */
+
   if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
-      ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
-          (*rrgp)--;
+      (READ_ONCE(rcu_gp_ctr) > tmp + MAX_GP_ADV_DISTANCE)) {
Quoted 3 lines

Does this work correctly if the value of tmp is just a bit less than ULONG_MAX? It looks to me like it does not.

Hi Paul,

Thanks for reviewing the code. Yes, the statement you pointed out is buggy when both rcu_gp_ctr and tmp are close to ULONG_MAX. I was trying to rewrite to code to check for true overflow, but, as you have pointed out in a previous mail, that could make the code complex if we want to be exact. So I go back to the logic you used before. Please check the updated code below:

CodeSamples/defer/rcu_nest.h +10 -2
+
+     /*
+      * A reader could be suspended in between fetching the value of *rrgp
+      * and writting the updated value back into *rrgp. During this
+      * time period, the grace-period counter might have advanced very far.
+      * In this case, we force the reader to start over.
+      */
+
      if (((tmp & RCU_GP_CTR_NEST_MASK) == 1) &&
-         ((rcu_gp_ctr - tmp) > (RCU_GP_CTR_NEST_MASK << 8)) != 0) {
-             (*rrgp)--;
+         (READ_ONCE(rcu_gp_ctr) - (tmp-1)) > MAX_GP_ADV_DISTANCE) {
+             WRITE_ONCE(*rrgp, *rrgp - 1);
              goto retry;
      }
 }
Quoted 10 lines
Quoted 5 lines

Note that if *rcu_gp_ctr* has not been changed since its value was first read and stored in *tmp*, then its value is less than *tmp* by 1. Since both *rcu_gp_ctr* and *tmp* are now unsigned long integers, (rcu_gp_ctr - tmp) will generate a very large integer number, so I replace that with (READ_ONCE(rcu_gp_ctr) - (tmp-1)). Please let me know if that looks OK.

There are a couple of ways to make this work. One of them is as shown in time_after() in the Linux kernel, and another is as shown in ULONG_CMP_GE().

Hi Paul,

Thanks for referencing me to these functions, which look great. I will send a new patch soon.

Thanks,
--Junchang

Quoted 18 lines

And yes, the C standard is less helpful than it might be in this area. You can thank old ones-complement machines and newer machines that trap on signed integer overflow. ;-)

Thanx, Paul

Quoted 12 lines

Thanks,
--Junchang

Quoted 8 lines
Quoted 7 lines
CodeSamples/defer/rcu_nest.h +1 -1
+          WRITE_ONCE(*rrgp, *rrgp - 1);
           goto retry;
   }
 }
--

2.7.4