Skip to contentSkip to conversation

Toyrcu: replace plain accesses with READ_ONCE()

PATCH Superseded Junchang Wang 2 participants 8 messages Apr 29, 2019 – May 1, 2019

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover Toyrcu: replace plain accesses with READ_ONCE()

Hi list,

Variable rcu_gp_ctr is accessed concurrently by the updater and readers, and hence should be protected by READ_ONCE() and WRITE_ONCE(). This patch set updates rcu and rcu_qs.

The tex file is updated accordingly. And a new scheme, which is suggested by Akira and can extract code snippets from the source code, has been applied.

Please note that rcu_nest also needs to be updated. I will first make sure that I'm fully understand how it works, and then submit a patch for it.

--
Junchang Wang (2):
rcu: Use READ_ONCE() and WRITE_ONCE() for shared variable rcu_gp_ctr
rcu_qs: Use READ_ONCE() AND WRITE_ONCE() for shared variable
rcu_gp_ctr

 CodeSamples/defer/rcu.c    |  30 ++++---
 CodeSamples/defer/rcu.h    |  21 +++--
 CodeSamples/defer/rcu_qs.c |  29 ++++---
 CodeSamples/defer/rcu_qs.h |  42 ++++-----
 appendix/toyrcu/toyrcu.tex | 207 +++++++++++++++++----------------------------
 5 files changed, 146 insertions(+), 183 deletions(-)
Signature · 1 line
2.7.4
#1 lore raw

PATCH v3 1/2 rcu: Use READ_ONCE() and WRITE_ONCE() for shared variable rcu_gp_ctr

Replace the plain accesses with READ_ONCE()/WRITE_ONCE(). And then update the tex file accordingly. A new scheme, which directly extracts snippet from rcu.[hc], is applied.

---
 CodeSamples/defer/rcu.c    | 30 ++++++++-------
 CodeSamples/defer/rcu.h    | 21 ++++++----
 appendix/toyrcu/toyrcu.tex | 95 +++++++++++++++++++---------------------------
 3 files changed, 68 insertions(+), 78 deletions(-)
CodeSamples/defer/rcu.c +16 -14
index 4b868cc..4ca2739 100644
@@ -21,45 +21,47 @@
 #include "../api.h"
 #include "rcu.h"
 
-void synchronize_rcu(void)
+//\begin{snippet}[labelbase=ln:defer:rcu:synchronize,gobbleblank=yes,commandchars=\%\@\$]
+void synchronize_rcu(void)			//\lnlbl{syn:b}
 {
 	int t;
 
 	/* Memory barrier ensures mutation seen before grace period. */
 
-	smp_mb();
+	smp_mb();				//\lnlbl{syn:mb1}
 
 	/* Only one synchronize_rcu() at a time. */
 
-	spin_lock(&rcu_gp_lock);
+	spin_lock(&rcu_gp_lock);		//\lnlbl{syn:spinlock}
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += 2;
-	smp_mb();
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + 2); //\lnlbl{syn:increasegp}
+	smp_mb();				//\lnlbl{syn:mb2}
 
 	/*
 	 * Wait until all threads are either out of their RCU read-side
 	 * critical sections or are aware of the new grace period.
 	 */
 
-	for_each_thread(t) {
-		while ((per_thread(rcu_reader_gp, t) & 0x1) &&
-		       ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+	for_each_thread(t) {			//\lnlbl{syn:scan:b}
+		while ((per_thread(rcu_reader_gp, t) & 0x1) &&//\lnlbl{syn:even}
+		       ((per_thread(rcu_reader_gp, t) -	//\lnlbl{syn:gt1}
+		         rcu_gp_ctr) < 0)) {		//\lnlbl{syn:gt2}
 			/*@@@ poll(NULL, 0, 10); */
-			barrier();
+			barrier();		//\lnlbl{syn:barrier}
 		}
-	}
+	}					//\lnlbl{syn:scan:e}
 
 	/* Let other synchronize_rcu() instances move ahead. */
 
-	spin_unlock(&rcu_gp_lock);
+	spin_unlock(&rcu_gp_lock);		//\lnlbl{syn:spinunlock}
 
 	/* Ensure that any subsequent free()s happen -after- above checks. */
 
-	smp_mb();
-}
-
+	smp_mb();				//\lnlbl{syn:mb3}
+}						//\lnlbl{syn:e}
+//\end{snippet}
 #ifdef TEST
 #include "rcutorture.h"
 #endif /* #ifdef TEST */
CodeSamples/defer/rcu.h +13 -8
index f493f8b..3641c33 100644
@@ -31,7 +31,8 @@ static inline void rcu_init(void)
 	init_per_thread(rcu_reader_gp_snap, 0);
 }
 
-static inline void rcu_read_lock(void)
+//\begin{snippet}[labelbase=ln:defer:rcu:read_lock_unlock,gobbleblank=yes,commandchars=\%\@\$]
+static inline void rcu_read_lock(void)			//\lnlbl{lock:b}
 {
 	/*
 	 * Copy the current GP counter to this thread's counter, setting
@@ -41,11 +42,12 @@ static inline void rcu_read_lock(void)
 	 * periodic per-thread processing.)
 	 */
 
-	__get_thread_var(rcu_reader_gp) = rcu_gp_ctr + 1;
-	smp_mb();
-}
-
-static inline void rcu_read_unlock(void)
+	__get_thread_var(rcu_reader_gp) =		//\lnlbl{lock:gp1}
+		READ_ONCE(rcu_gp_ctr) + 1;		//\lnlbl{lock:gp2}
+	smp_mb();					//\lnlbl{lock:mb}
+}							//\lnlbl{lock:e}
+								//\fcvblank
+static inline void rcu_read_unlock(void)		//\lnlbl{unlock:b}
 {
 	/*
 	 * Copy the current GP counter to this thread's counter, but
@@ -54,8 +56,11 @@ static inline void rcu_read_unlock(void)
 	 * the memory barrier requires periodic per-thread processing.)
 	 */
 
-	smp_mb();
-	__get_thread_var(rcu_reader_gp) = rcu_gp_ctr;
+	smp_mb();					//\lnlbl{unlock:mb}
+	__get_thread_var(rcu_reader_gp) =		//\lnlbl{unlock:gp1}
+		READ_ONCE(rcu_gp_ctr);			//\lnlbl{unlock:gp2}
 }
+								//\fcvblank
+//\end{snippet}
 
 extern void synchronize_rcu(void);
appendix/toyrcu/toyrcu.tex +39 -56

171 lines not on this page · raw message

Signature · 1 line
2.7.4
Reviewed-by on v3 1/2
#2 lore raw

Re: [PATCH v3 1/2] rcu: Use READ_ONCE() and WRITE_ONCE() for shared variable rcu_gp_ctr

Hi Junchang,

Please see inline comments below:

Quoted 1 line · Junchang Wang

Replace the plain accesses with READ_ONCE()/WRITE_ONCE(). And then update

How about:

s/the plain/racy plain/

?

Quoted 16 lines

the tex file accordingly. A new scheme, which directly extracts snippet from rcu.[hc], is applied.

---
 CodeSamples/defer/rcu.c    | 30 ++++++++-------
 CodeSamples/defer/rcu.h    | 21 ++++++----
 appendix/toyrcu/toyrcu.tex | 95 +++++++++++++++++++---------------------------
 3 files changed, 68 insertions(+), 78 deletions(-)
CodeSamples/defer/rcu.c +0 -0
index 4b868cc..4ca2739 100644

CodeSamples/defer/rcu.c line 28

Quoted 9 lines
CodeSamples/defer/rcu.c +2 -1
@@ -21,45 +21,47 @@
 #include "../api.h"
 #include "rcu.h"
 
-void synchronize_rcu(void)
+//\begin{snippet}[labelbase=ln:defer:rcu:synchronize,gobbleblank=yes,commandchars=\%\@\$]
+void synchronize_rcu(void)			//\lnlbl{syn:b}
 {
 	int t;
 

We need a "//\fcvblank" here.

Quoted 20 lines
CodeSamples/defer/rcu.c +4 -4
 	/* Memory barrier ensures mutation seen before grace period. */
 
-	smp_mb();
+	smp_mb();				//\lnlbl{syn:mb1}
 
 	/* Only one synchronize_rcu() at a time. */
 
-	spin_lock(&rcu_gp_lock);
+	spin_lock(&rcu_gp_lock);		//\lnlbl{syn:spinlock}
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += 2;
-	smp_mb();
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + 2); //\lnlbl{syn:increasegp}
+	smp_mb();				//\lnlbl{syn:mb2}
 
 	/*
 	 * Wait until all threads are either out of their RCU read-side
 	 * critical sections or are aware of the new grace period.

CodeSamples/defer/rcu.c line 51

Quoted 10 lines
CodeSamples/defer/rcu.c +4 -3
 	 */
 
-	for_each_thread(t) {
-		while ((per_thread(rcu_reader_gp, t) & 0x1) &&
-		       ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+	for_each_thread(t) {			//\lnlbl{syn:scan:b}
+		while ((per_thread(rcu_reader_gp, t) & 0x1) &&//\lnlbl{syn:even}
+		       ((per_thread(rcu_reader_gp, t) -	//\lnlbl{syn:gt1}
+		         rcu_gp_ctr) < 0)) {		//\lnlbl{syn:gt2}
 			/*@@@ poll(NULL, 0, 10); */

The original snippet in toyrcu.tex corresponds to this poll() call.

CodeSamples/defer/rcu.c line 52

Quoted 2 lines
CodeSamples/defer/rcu.c +1 -1
-			barrier();
+			barrier();		//\lnlbl{syn:barrier}

So one way to keep the snippet consistent with the text is to use the following construct.

#ifndef FCV_SNIPPET
			/*@@@ poll(NULL, 0, 10); */
			barrier();
#else
			poll(NULL, 0, 10);	//\lnlbl{syn:poll}

#endif

Quoted 185 lines
CodeSamples/defer/rcu.c +5 -5
 		}
-	}
+	}					//\lnlbl{syn:scan:e}
 
 	/* Let other synchronize_rcu() instances move ahead. */
 
-	spin_unlock(&rcu_gp_lock);
+	spin_unlock(&rcu_gp_lock);		//\lnlbl{syn:spinunlock}
 
 	/* Ensure that any subsequent free()s happen -after- above checks. */
 
-	smp_mb();
-}
-
+	smp_mb();				//\lnlbl{syn:mb3}
+}						//\lnlbl{syn:e}
+//\end{snippet}
 #ifdef TEST
 #include "rcutorture.h"
 #endif /* #ifdef TEST */
CodeSamples/defer/rcu.h +13 -8
index f493f8b..3641c33 100644
@@ -31,7 +31,8 @@ static inline void rcu_init(void)
 	init_per_thread(rcu_reader_gp_snap, 0);
 }
 
-static inline void rcu_read_lock(void)
+//\begin{snippet}[labelbase=ln:defer:rcu:read_lock_unlock,gobbleblank=yes,commandchars=\%\@\$]
+static inline void rcu_read_lock(void)			//\lnlbl{lock:b}
 {
 	/*
 	 * Copy the current GP counter to this thread's counter, setting
@@ -41,11 +42,12 @@ static inline void rcu_read_lock(void)
 	 * periodic per-thread processing.)
 	 */
 
-	__get_thread_var(rcu_reader_gp) = rcu_gp_ctr + 1;
-	smp_mb();
-}
-
-static inline void rcu_read_unlock(void)
+	__get_thread_var(rcu_reader_gp) =		//\lnlbl{lock:gp1}
+		READ_ONCE(rcu_gp_ctr) + 1;		//\lnlbl{lock:gp2}
+	smp_mb();					//\lnlbl{lock:mb}
+}							//\lnlbl{lock:e}
+								//\fcvblank
+static inline void rcu_read_unlock(void)		//\lnlbl{unlock:b}
 {
 	/*
 	 * Copy the current GP counter to this thread's counter, but
@@ -54,8 +56,11 @@ static inline void rcu_read_unlock(void)
 	 * the memory barrier requires periodic per-thread processing.)
 	 */
 
-	smp_mb();
-	__get_thread_var(rcu_reader_gp) = rcu_gp_ctr;
+	smp_mb();					//\lnlbl{unlock:mb}
+	__get_thread_var(rcu_reader_gp) =		//\lnlbl{unlock:gp1}
+		READ_ONCE(rcu_gp_ctr);			//\lnlbl{unlock:gp2}
 }
+								//\fcvblank
+//\end{snippet}
 
 extern void synchronize_rcu(void);
appendix/toyrcu/toyrcu.tex +23 -47
index c0a45a8..f7fc07b 100644
@@ -1218,44 +1218,8 @@ thread-local accesses to one, as is done in the next section.
 \end{listing}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 static void rcu_read_lock(void)
- 2 {
- 3   __get_thread_var(rcu_reader_gp) =
- 4     ACCESS_ONCE(rcu_gp_ctr) + 1;
- 5   smp_mb();
- 6 }
- 7 
- 8 static void rcu_read_unlock(void)
- 9 {
-10   smp_mb();
-11   __get_thread_var(rcu_reader_gp) =
-12     ACCESS_ONCE(rcu_gp_ctr);
-13 }
-14 
-15 void synchronize_rcu(void)
-16 {
-17   int t;
-18 
-19   smp_mb();
-20   spin_lock(&rcu_gp_lock);
-21   ACCESS_ONCE(rcu_gp_ctr) += 2;
-22   smp_mb();
-23   for_each_thread(t) {
-24     while ((per_thread(rcu_reader_gp, t) & 0x1) &&
-25             ((per_thread(rcu_reader_gp, t) -
-26               ACCESS_ONCE(rcu_gp_ctr)) < 0)) {
-27       poll(NULL, 0, 10);
-28     }
-29   }
-30   spin_unlock(&rcu_gp_lock);
-31   smp_mb();
-32 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/rcu@read_lock_unlock.fcv}\vspace*{-11pt}\fvset{firstnumber=last}
+\input{CodeSamples/defer/[email protected]}\fvset{firstnumber=auto}
 \caption{Free-Running Counter Using RCU}
 \label{lst:app:toyrcu:Free-Running Counter Using RCU}
 \end{listing}
@@ -1267,25 +1231,34 @@ that takes on only even-numbered values, with data shown in
 Listing~\ref{lst:app:toyrcu:Data for Free-Running Counter Using RCU}.
 The resulting \co{rcu_read_lock()} implementation is extremely
 straightforward.
-Lines~3 and~4 simply add one to the global free-running \co{rcu_gp_ctr}
+\begin{lineref}[ln:defer:rcu:read_lock_unlock:lock]
+Lines~\lnref{gp1} and~\lnref{gp2} simply
+add one to the global free-running \co{rcu_gp_ctr}
 variable and stores the resulting odd-numbered value into the
 \co{rcu_reader_gp} per-thread variable.
-Line~5 executes a memory barrier to prevent the content of the
+Line~\lnref{mb} executes a memory barrier to prevent the content of the
 subsequent RCU read-side critical section from ``leaking out''.
+\end{lineref}
 
+\begin{lineref}[ln:defer:rcu:read_lock_unlock:unlock]
 The \co{rcu_read_unlock()} implementation is similar.
-Line~10 executes a memory barrier, again to prevent the prior RCU
+Line~\lnref{mb} executes a memory barrier, again to prevent the prior RCU
 read-side critical section from ``leaking out''.
-Lines~11 and~12 then copy the \co{rcu_gp_ctr} global variable to the
+Lines~\lnref{gp1} and~\lnref{gp2} then
+copy the \co{rcu_gp_ctr} global variable to the
 \co{rcu_reader_gp} per-thread variable, leaving this per-thread
 variable with an even-numbered value so that a concurrent instance
 of \co{synchronize_rcu()} will know to ignore it.
+\end{lineref}
 
 \QuickQuiz{}
+	\begin{lineref}[ln:defer:rcu:read_lock_unlock:unlock]
 	If any even value is sufficient to tell \co{synchronize_rcu()}
-	to ignore a given task, why don't lines~10 and~11 of
+	to ignore a given task, why don't lines~\lnref{gp1}
+	and~\lnref{gp2} of
 	Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
 	simply assign zero to \co{rcu_reader_gp}?
+	\end{lineref}
 \QuickQuizAnswer{
 	Assigning zero (or any other even-numbered constant)
 	would in fact work, but assigning the value of
@@ -1294,39 +1267,46 @@ of \co{synchronize_rcu()} will know to ignore it.
 	thread last exited an RCU read-side critical section.
 } \QuickQuizEnd
 
+\begin{lineref}[ln:defer:rcu:synchronize:syn]
 Thus, \co{synchronize_rcu()} could wait for all of the per-thread
 \co{rcu_reader_gp} variables to take on even-numbered values.
 However, it is possible to do much better than that because
 \co{synchronize_rcu()} need only wait on \emph{pre-existing}
 RCU read-side critical sections.
-Line~19 executes a memory barrier to prevent prior manipulations
+Line~\lnref{mb1} executes a memory barrier to prevent prior manipulations
 of RCU-protected data structures from being reordered (by either
-the CPU or the compiler) to follow the increment on line~21.
-Line~20 acquires the \co{rcu_gp_lock} (and line~30 releases it)
+the CPU or the compiler) to follow the increment on
+line~\lnref{increasegp}.
+Line~\lnref{spinlock} acquires the \co{rcu_gp_lock}
+(and line~\lnref{spinunlock} releases it)
 in order to prevent multiple
 \co{synchronize_rcu()} instances from running concurrently.
-Line~21 then increments the global \co{rcu_gp_ctr} variable by
+Line~\lnref{increasegp} then increments the global \co{rcu_gp_ctr} variable by
 two, so that all pre-existing RCU read-side critical sections will
 have corresponding per-thread \co{rcu_reader_gp} variables with
 values less than that of \co{rcu_gp_ctr}, modulo the machine's
 word size.
 Recall also that threads with even-numbered values of \co{rcu_reader_gp}

appendix/toyrcu/toyrcu.tex of \co{synchronize_rcu()} will know to ignore it. · line 1295

Quoted 10 lines
appendix/toyrcu/toyrcu.tex +5 -4
 are not in an RCU read-side critical section,
-so that lines~23-29 scan the \co{rcu_reader_gp} values until they
-all are either even (line~24) or are greater than the global
-\co{rcu_gp_ctr} (lines~25-26).
-Line~27 blocks for a short period of time to wait for a
+so that lines~\lnref{scan:b}-\lnref{scan:e}
+scan the \co{rcu_reader_gp} values until they
+all are either even (line~\lnref{even}) or are greater than the global
+\co{rcu_gp_ctr} (lines~\lnref{gt1}-\lnref{gt2}).
+Line~\lnref{barrier} blocks for a short period of time to wait for a

s/\lnref{barrier}/\lnref{poll}/
"poll" is the label used in the "#ifndef FCV_SNIPPET" construct suggested above.

appendix/toyrcu/toyrcu.tex variables.

Quoted 35 lines
appendix/toyrcu/toyrcu.tex +8 -4
 pre-existing RCU read-side critical section, but this can be replaced with
 a spin-loop if grace-period latency is of the essence.
-Finally, the memory barrier at line~31 ensures that any subsequent
+Finally, the memory barrier at line~\lnref{mb3} ensures that any subsequent
 destruction will not be reordered into the preceding loop.
+\end{lineref}
 
 \QuickQuiz{}
-	Why are the memory barriers on lines~19 and~31 of
+	\begin{lineref}[ln:defer:rcu:synchronize:syn]
+	Why are the memory barriers on lines~\lnref{mb1} and~\lnref{mb3} of
 	Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
 	needed?
 	Aren't the memory barriers inherent in the locking
-	primitives on lines~20 and~30 sufficient?
+	primitives on lines~\lnref{spinlock} and~\lnref{spinunlock} sufficient?
+	\end{lineref}
 \QuickQuizAnswer{
 	These memory barriers are required because the locking
 	primitives are only guaranteed to confine the critical
@@ -1355,11 +1335,12 @@ such CPUs.
 	This work is left as an exercise for the reader.
 } \QuickQuizEnd
 
+\begin{lineref}[ln:defer:rcu:read_lock_unlock:lock]
 This implementation suffers from some serious shortcomings in
 addition to the high update-side overhead noted earlier.
 First, it is no longer permissible to nest RCU read-side critical
 sections, a topic that is taken up in the next section.
-Second, if a reader is preempted at line~3 of
+Second, if a reader is preempted at line~\lnref{gp1} of
 Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU} after fetching from
 \co{rcu_gp_ctr} but before storing to \co{rcu_reader_gp},
 and if the \co{rcu_gp_ctr} counter then runs through more than half
@@ -1371,7 +1352,8 @@ variables.

Please put \end{lineref} ahead of \QuickQuiz{}.
\QuickQuiz{} should have its own pair of \begin{lineref} and \end{lineref}. It looks like you have figured this out and taken care of the paring in 2/2 of this patch set, but it is desirable to make sure each commit builds properly.

Quoted 10 lines
appendix/toyrcu/toyrcu.tex +2 -1
 \QuickQuiz{}
 	Is the possibility of readers being preempted in
-	lines~3-4 of Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
+	lines~\lnref{gp1}-\lnref{gp2} of
+	Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
 	a real problem, in other words, is there a real sequence
 	of events that could lead to failure?
 	If not, why not?

appendix/toyrcu/toyrcu.tex variables. · line 1373

Quoted 4 lines
appendix/toyrcu/toyrcu.tex +1 -0
@@ -1388,6 +1370,7 @@ variables.
 	added in that section greatly reduces the time required to
 	overflow the counter.
 } \QuickQuizEnd
+\end{lineref}

Ditto.

With those fixed,

Thanks, Akira

Quoted 4 lines
appendix/toyrcu/toyrcu.tex +0 -0
 \section{Nestable RCU Based on Free-Running Counter}
 \label{sec:app:toyrcu:Nestable RCU Based on Free-Running Counter}
 
#3 lore raw

Re: [PATCH v3 1/2] rcu: Use READ_ONCE() and WRITE_ONCE() for shared variable rcu_gp_ctr

Quoted 310 lines · Akira Yokosawa

Hi Junchang,

Please see inline comments below:

Quoted 1 line · Junchang Wang

Replace the plain accesses with READ_ONCE()/WRITE_ONCE(). And then update

How about:

s/the plain/racy plain/

?

Quoted 16 lines

the tex file accordingly. A new scheme, which directly extracts snippet from rcu.[hc], is applied.

---
 CodeSamples/defer/rcu.c    | 30 ++++++++-------
 CodeSamples/defer/rcu.h    | 21 ++++++----
 appendix/toyrcu/toyrcu.tex | 95 +++++++++++++++++++---------------------------
 3 files changed, 68 insertions(+), 78 deletions(-)
CodeSamples/defer/rcu.c +0 -0
index 4b868cc..4ca2739 100644

CodeSamples/defer/rcu.c line 28

Quoted 9 lines
CodeSamples/defer/rcu.c +2 -1
@@ -21,45 +21,47 @@
 #include "../api.h"
 #include "rcu.h"
 
-void synchronize_rcu(void)
+//\begin{snippet}[labelbase=ln:defer:rcu:synchronize,gobbleblank=yes,commandchars=\%\@\$]
+void synchronize_rcu(void)                   //\lnlbl{syn:b}
 {
      int t;
 

We need a "//\fcvblank" here.

Quoted 20 lines
CodeSamples/defer/rcu.c +4 -4
      /* Memory barrier ensures mutation seen before grace period. */
 
-     smp_mb();
+     smp_mb();                               //\lnlbl{syn:mb1}
 
      /* Only one synchronize_rcu() at a time. */
 
-     spin_lock(&rcu_gp_lock);
+     spin_lock(&rcu_gp_lock);                //\lnlbl{syn:spinlock}
 
      /* Advance to a new grace-period number, enforce ordering. */
 
-     rcu_gp_ctr += 2;
-     smp_mb();
+     WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + 2); //\lnlbl{syn:increasegp}
+     smp_mb();                               //\lnlbl{syn:mb2}
 
      /*
       * Wait until all threads are either out of their RCU read-side
       * critical sections or are aware of the new grace period.

CodeSamples/defer/rcu.c line 51

Quoted 10 lines
CodeSamples/defer/rcu.c +4 -3
       */
 
-     for_each_thread(t) {
-             while ((per_thread(rcu_reader_gp, t) & 0x1) &&
-                    ((per_thread(rcu_reader_gp, t) - rcu_gp_ctr) < 0)) {
+     for_each_thread(t) {                    //\lnlbl{syn:scan:b}
+             while ((per_thread(rcu_reader_gp, t) & 0x1) &&//\lnlbl{syn:even}
+                    ((per_thread(rcu_reader_gp, t) - //\lnlbl{syn:gt1}
+                      rcu_gp_ctr) < 0)) {            //\lnlbl{syn:gt2}
                      /*@@@ poll(NULL, 0, 10); */

The original snippet in toyrcu.tex corresponds to this poll() call.

CodeSamples/defer/rcu.c line 52

Quoted 2 lines
CodeSamples/defer/rcu.c +1 -1
-                     barrier();
+                     barrier();              //\lnlbl{syn:barrier}

So one way to keep the snippet consistent with the text is to use the following construct.

#ifndef FCV_SNIPPET
                        /*@@@ poll(NULL, 0, 10); */
                        barrier();
#else
                        poll(NULL, 0, 10);      //\lnlbl{syn:poll}

#endif

Quoted 185 lines
CodeSamples/defer/rcu.c +5 -5
              }
-     }
+     }                                       //\lnlbl{syn:scan:e}
 
      /* Let other synchronize_rcu() instances move ahead. */
 
-     spin_unlock(&rcu_gp_lock);
+     spin_unlock(&rcu_gp_lock);              //\lnlbl{syn:spinunlock}
 
      /* Ensure that any subsequent free()s happen -after- above checks. */
 
-     smp_mb();
-}
-
+     smp_mb();                               //\lnlbl{syn:mb3}
+}                                            //\lnlbl{syn:e}
+//\end{snippet}
 #ifdef TEST
 #include "rcutorture.h"
 #endif /* #ifdef TEST */
CodeSamples/defer/rcu.h +13 -8
index f493f8b..3641c33 100644
@@ -31,7 +31,8 @@ static inline void rcu_init(void)
      init_per_thread(rcu_reader_gp_snap, 0);
 }
 
-static inline void rcu_read_lock(void)
+//\begin{snippet}[labelbase=ln:defer:rcu:read_lock_unlock,gobbleblank=yes,commandchars=\%\@\$]
+static inline void rcu_read_lock(void)                       //\lnlbl{lock:b}
 {
      /*
       * Copy the current GP counter to this thread's counter, setting
@@ -41,11 +42,12 @@ static inline void rcu_read_lock(void)
       * periodic per-thread processing.)
       */
 
-     __get_thread_var(rcu_reader_gp) = rcu_gp_ctr + 1;
-     smp_mb();
-}
-
-static inline void rcu_read_unlock(void)
+     __get_thread_var(rcu_reader_gp) =               //\lnlbl{lock:gp1}
+             READ_ONCE(rcu_gp_ctr) + 1;              //\lnlbl{lock:gp2}
+     smp_mb();                                       //\lnlbl{lock:mb}
+}                                                    //\lnlbl{lock:e}
+                                                             //\fcvblank
+static inline void rcu_read_unlock(void)             //\lnlbl{unlock:b}
 {
      /*
       * Copy the current GP counter to this thread's counter, but
@@ -54,8 +56,11 @@ static inline void rcu_read_unlock(void)
       * the memory barrier requires periodic per-thread processing.)
       */
 
-     smp_mb();
-     __get_thread_var(rcu_reader_gp) = rcu_gp_ctr;
+     smp_mb();                                       //\lnlbl{unlock:mb}
+     __get_thread_var(rcu_reader_gp) =               //\lnlbl{unlock:gp1}
+             READ_ONCE(rcu_gp_ctr);                  //\lnlbl{unlock:gp2}
 }
+                                                             //\fcvblank
+//\end{snippet}
 
 extern void synchronize_rcu(void);
appendix/toyrcu/toyrcu.tex +23 -47
index c0a45a8..f7fc07b 100644
@@ -1218,44 +1218,8 @@ thread-local accesses to one, as is done in the next section.
 \end{listing}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 static void rcu_read_lock(void)
- 2 {
- 3   __get_thread_var(rcu_reader_gp) =
- 4     ACCESS_ONCE(rcu_gp_ctr) + 1;
- 5   smp_mb();
- 6 }
- 7
- 8 static void rcu_read_unlock(void)
- 9 {
-10   smp_mb();
-11   __get_thread_var(rcu_reader_gp) =
-12     ACCESS_ONCE(rcu_gp_ctr);
-13 }
-14
-15 void synchronize_rcu(void)
-16 {
-17   int t;
-18
-19   smp_mb();
-20   spin_lock(&rcu_gp_lock);
-21   ACCESS_ONCE(rcu_gp_ctr) += 2;
-22   smp_mb();
-23   for_each_thread(t) {
-24     while ((per_thread(rcu_reader_gp, t) & 0x1) &&
-25             ((per_thread(rcu_reader_gp, t) -
-26               ACCESS_ONCE(rcu_gp_ctr)) < 0)) {
-27       poll(NULL, 0, 10);
-28     }
-29   }
-30   spin_unlock(&rcu_gp_lock);
-31   smp_mb();
-32 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/rcu@read_lock_unlock.fcv}\vspace*{-11pt}\fvset{firstnumber=last}
+\input{CodeSamples/defer/[email protected]}\fvset{firstnumber=auto}
 \caption{Free-Running Counter Using RCU}
 \label{lst:app:toyrcu:Free-Running Counter Using RCU}
 \end{listing}
@@ -1267,25 +1231,34 @@ that takes on only even-numbered values, with data shown in
 Listing~\ref{lst:app:toyrcu:Data for Free-Running Counter Using RCU}.
 The resulting \co{rcu_read_lock()} implementation is extremely
 straightforward.
-Lines~3 and~4 simply add one to the global free-running \co{rcu_gp_ctr}
+\begin{lineref}[ln:defer:rcu:read_lock_unlock:lock]
+Lines~\lnref{gp1} and~\lnref{gp2} simply
+add one to the global free-running \co{rcu_gp_ctr}
 variable and stores the resulting odd-numbered value into the
 \co{rcu_reader_gp} per-thread variable.
-Line~5 executes a memory barrier to prevent the content of the
+Line~\lnref{mb} executes a memory barrier to prevent the content of the
 subsequent RCU read-side critical section from ``leaking out''.
+\end{lineref}
 
+\begin{lineref}[ln:defer:rcu:read_lock_unlock:unlock]
 The \co{rcu_read_unlock()} implementation is similar.
-Line~10 executes a memory barrier, again to prevent the prior RCU
+Line~\lnref{mb} executes a memory barrier, again to prevent the prior RCU
 read-side critical section from ``leaking out''.
-Lines~11 and~12 then copy the \co{rcu_gp_ctr} global variable to the
+Lines~\lnref{gp1} and~\lnref{gp2} then
+copy the \co{rcu_gp_ctr} global variable to the
 \co{rcu_reader_gp} per-thread variable, leaving this per-thread
 variable with an even-numbered value so that a concurrent instance
 of \co{synchronize_rcu()} will know to ignore it.
+\end{lineref}
 
 \QuickQuiz{}
+     \begin{lineref}[ln:defer:rcu:read_lock_unlock:unlock]
      If any even value is sufficient to tell \co{synchronize_rcu()}
-     to ignore a given task, why don't lines~10 and~11 of
+     to ignore a given task, why don't lines~\lnref{gp1}
+     and~\lnref{gp2} of
      Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
      simply assign zero to \co{rcu_reader_gp}?
+     \end{lineref}
 \QuickQuizAnswer{
      Assigning zero (or any other even-numbered constant)
      would in fact work, but assigning the value of
@@ -1294,39 +1267,46 @@ of \co{synchronize_rcu()} will know to ignore it.
      thread last exited an RCU read-side critical section.
 } \QuickQuizEnd
 
+\begin{lineref}[ln:defer:rcu:synchronize:syn]
 Thus, \co{synchronize_rcu()} could wait for all of the per-thread
 \co{rcu_reader_gp} variables to take on even-numbered values.
 However, it is possible to do much better than that because
 \co{synchronize_rcu()} need only wait on \emph{pre-existing}
 RCU read-side critical sections.
-Line~19 executes a memory barrier to prevent prior manipulations
+Line~\lnref{mb1} executes a memory barrier to prevent prior manipulations
 of RCU-protected data structures from being reordered (by either
-the CPU or the compiler) to follow the increment on line~21.
-Line~20 acquires the \co{rcu_gp_lock} (and line~30 releases it)
+the CPU or the compiler) to follow the increment on
+line~\lnref{increasegp}.
+Line~\lnref{spinlock} acquires the \co{rcu_gp_lock}
+(and line~\lnref{spinunlock} releases it)
 in order to prevent multiple
 \co{synchronize_rcu()} instances from running concurrently.
-Line~21 then increments the global \co{rcu_gp_ctr} variable by
+Line~\lnref{increasegp} then increments the global \co{rcu_gp_ctr} variable by
 two, so that all pre-existing RCU read-side critical sections will
 have corresponding per-thread \co{rcu_reader_gp} variables with
 values less than that of \co{rcu_gp_ctr}, modulo the machine's
 word size.
 Recall also that threads with even-numbered values of \co{rcu_reader_gp}

appendix/toyrcu/toyrcu.tex of \co{synchronize_rcu()} will know to ignore it. · line 1295

Quoted 10 lines
appendix/toyrcu/toyrcu.tex +5 -4
 are not in an RCU read-side critical section,
-so that lines~23-29 scan the \co{rcu_reader_gp} values until they
-all are either even (line~24) or are greater than the global
-\co{rcu_gp_ctr} (lines~25-26).
-Line~27 blocks for a short period of time to wait for a
+so that lines~\lnref{scan:b}-\lnref{scan:e}
+scan the \co{rcu_reader_gp} values until they
+all are either even (line~\lnref{even}) or are greater than the global
+\co{rcu_gp_ctr} (lines~\lnref{gt1}-\lnref{gt2}).
+Line~\lnref{barrier} blocks for a short period of time to wait for a

s/\lnref{barrier}/\lnref{poll}/
"poll" is the label used in the "#ifndef FCV_SNIPPET" construct suggested above.

Quoted 24 lines
appendix/toyrcu/toyrcu.tex +6 -3
 pre-existing RCU read-side critical section, but this can be replaced with
 a spin-loop if grace-period latency is of the essence.
-Finally, the memory barrier at line~31 ensures that any subsequent
+Finally, the memory barrier at line~\lnref{mb3} ensures that any subsequent
 destruction will not be reordered into the preceding loop.
+\end{lineref}
 
 \QuickQuiz{}
-     Why are the memory barriers on lines~19 and~31 of
+     \begin{lineref}[ln:defer:rcu:synchronize:syn]
+     Why are the memory barriers on lines~\lnref{mb1} and~\lnref{mb3} of
      Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
      needed?
      Aren't the memory barriers inherent in the locking
-     primitives on lines~20 and~30 sufficient?
+     primitives on lines~\lnref{spinlock} and~\lnref{spinunlock} sufficient?
+     \end{lineref}
 \QuickQuizAnswer{
      These memory barriers are required because the locking
      primitives are only guaranteed to confine the critical
@@ -1355,11 +1335,12 @@ such CPUs.
      This work is left as an exercise for the reader.
 } \QuickQuizEnd
 
Quoted 17 lines

appendix/toyrcu/toyrcu.tex variables.

Quoted 11 lines
appendix/toyrcu/toyrcu.tex +2 -1
+\begin{lineref}[ln:defer:rcu:read_lock_unlock:lock]
 This implementation suffers from some serious shortcomings in
 addition to the high update-side overhead noted earlier.
 First, it is no longer permissible to nest RCU read-side critical
 sections, a topic that is taken up in the next section.
-Second, if a reader is preempted at line~3 of
+Second, if a reader is preempted at line~\lnref{gp1} of
 Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU} after fetching from
 \co{rcu_gp_ctr} but before storing to \co{rcu_reader_gp},
 and if the \co{rcu_gp_ctr} counter then runs through more than half
@@ -1371,7 +1352,8 @@ variables.

Please put \end{lineref} ahead of \QuickQuiz{}.
\QuickQuiz{} should have its own pair of \begin{lineref} and \end{lineref}. It looks like you have figured this out and taken care of the paring in 2/2 of this patch set, but it is desirable to make sure each commit builds properly.

Hi Akira,

Thanks a lot for reviewing the patch set. I will submit a new version soon.

Thanks,
--Junchang

Quoted 27 lines
Quoted 10 lines
appendix/toyrcu/toyrcu.tex +2 -1
 \QuickQuiz{}
      Is the possibility of readers being preempted in
-     lines~3-4 of Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
+     lines~\lnref{gp1}-\lnref{gp2} of
+     Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
      a real problem, in other words, is there a real sequence
      of events that could lead to failure?
      If not, why not?

appendix/toyrcu/toyrcu.tex variables. · line 1373

Quoted 4 lines
appendix/toyrcu/toyrcu.tex +1 -0
@@ -1388,6 +1370,7 @@ variables.
      added in that section greatly reduces the time required to
      overflow the counter.
 } \QuickQuizEnd
+\end{lineref}

Ditto.

With those fixed,

Thanks, Akira

Quoted 4 lines
appendix/toyrcu/toyrcu.tex +0 -0
 \section{Nestable RCU Based on Free-Running Counter}
 \label{sec:app:toyrcu:Nestable RCU Based on Free-Running Counter}
 
#4 lore raw

PATCH v3 2/2 rcu_qs: Use READ_ONCE() AND WRITE_ONCE() for shared variable rcu_gp_ctr

In reply to Junchang Wang

Replace the plain accesses with READ_ONCE()/WRITE_ONCE(). And then update the tex file accordingly. A new scheme, which directly extracts snippet from rcu_qs.[hc], is applied.

---
 CodeSamples/defer/rcu_qs.c |  29 ++++++------
 CodeSamples/defer/rcu_qs.h |  42 +++++++++--------
 appendix/toyrcu/toyrcu.tex | 114 ++++++++++++++++-----------------------------
 3 files changed, 79 insertions(+), 106 deletions(-)
CodeSamples/defer/rcu_qs.c +16 -13
index 27e45f7..8dc174f 100644
@@ -27,44 +27,47 @@
 #include "../api.h"
 #include "rcu_qs.h"
 
-void synchronize_rcu(void)
+//\begin{snippet}[labelbase=ln:defer:rcu_qs:synchronize,gobbleblank=yes,commandchars=\%\@\$]
+void synchronize_rcu(void)			//\lnlbl{syn:b}
 {
 	int t;
-
+							//\fcvblank
 	/* Memory barrier ensures mutation seen before grace period. */
 
-	smp_mb();
+	smp_mb();				//\lnlbl{syn:mb1}
 
 	/* Only one synchronize_rcu() at a time. */
 
-	spin_lock(&rcu_gp_lock);
+	spin_lock(&rcu_gp_lock);		//\lnlbl{syn:spinlock}
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += 2;
-	smp_mb();
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + 2);	//\lnlbl{syn:increasegp}
+	smp_mb();				//\lnlbl{syn:mb2}
 
 	/*
 	 * Wait until all threads are either out of their RCU read-side
 	 * critical sections or are aware of the new grace period.
 	 */
 
-	for_each_thread(t) {
-		while (rcu_gp_ongoing(t) &&
-		       ((per_thread(rcu_reader_qs_gp, t) - rcu_gp_ctr) < 0)) {
+	for_each_thread(t) {			//\lnlbl{syn:scan:b}
+		while (rcu_gp_ongoing(t) &&	//\lnlbl{syn:ongoing}
+		       ((per_thread(rcu_reader_qs_gp, t)//\lnlbl{syn:gp1}
+		         - rcu_gp_ctr) < 0)) {	//\lnlbl{syn:gp2}
 			/* @@@ poll(NULL, 0, 10); */
-			barrier();
+			barrier();		//\lnlbl{syn:barrier}
 		}
-	}
+	}					//\lnlbl{syn:scan:e}
 
 	/* Let other synchronize_rcu() instances move ahead. */
 
-	spin_unlock(&rcu_gp_lock);
+	spin_unlock(&rcu_gp_lock);		//\lnlbl{syn:spinunlock}
 
 	/* Ensure that any subsequent free()s happen -after- above checks. */
 
-	smp_mb();
+	smp_mb();				//\lnlbl{syn:mb3}
 }
+//\end{snippet}
 
 #ifdef TEST
 #include "rcutorture.h"
CodeSamples/defer/rcu_qs.h +23 -19

54 lines not on this page · raw message

appendix/toyrcu/toyrcu.tex +40 -74

206 lines not on this page · raw message

Signature · 1 line
2.7.4
Reviewed-by on v3 2/2
#5 lore raw

Re: [PATCH v3 2/2] rcu_qs: Use READ_ONCE() AND WRITE_ONCE() for shared variable rcu_gp_ctr

Hi Junchang,

Please find inline comments below.

Quoted 1 line · Junchang Wang

Replace the plain accesses with READ_ONCE()/WRITE_ONCE(). And then update

s/the plain/racy plain/

Quoted 48 lines

the tex file accordingly. A new scheme, which directly extracts snippet from rcu_qs.[hc], is applied.

---
 CodeSamples/defer/rcu_qs.c |  29 ++++++------
 CodeSamples/defer/rcu_qs.h |  42 +++++++++--------
 appendix/toyrcu/toyrcu.tex | 114 ++++++++++++++++-----------------------------
 3 files changed, 79 insertions(+), 106 deletions(-)
CodeSamples/defer/rcu_qs.c +7 -6
index 27e45f7..8dc174f 100644
@@ -27,44 +27,47 @@
 #include "../api.h"
 #include "rcu_qs.h"
 
-void synchronize_rcu(void)
+//\begin{snippet}[labelbase=ln:defer:rcu_qs:synchronize,gobbleblank=yes,commandchars=\%\@\$]
+void synchronize_rcu(void)			//\lnlbl{syn:b}
 {
 	int t;
-
+							//\fcvblank
 	/* Memory barrier ensures mutation seen before grace period. */
 
-	smp_mb();
+	smp_mb();				//\lnlbl{syn:mb1}
 
 	/* Only one synchronize_rcu() at a time. */
 
-	spin_lock(&rcu_gp_lock);
+	spin_lock(&rcu_gp_lock);		//\lnlbl{syn:spinlock}
 
 	/* Advance to a new grace-period number, enforce ordering. */
 
-	rcu_gp_ctr += 2;
-	smp_mb();
+	WRITE_ONCE(rcu_gp_ctr, rcu_gp_ctr + 2);	//\lnlbl{syn:increasegp}
+	smp_mb();				//\lnlbl{syn:mb2}
 
 	/*
 	 * Wait until all threads are either out of their RCU read-side
 	 * critical sections or are aware of the new grace period.
 	 */
 

CodeSamples/defer/rcu_qs.c line 58

Quoted 10 lines
CodeSamples/defer/rcu_qs.c +5 -4
-	for_each_thread(t) {
-		while (rcu_gp_ongoing(t) &&
-		       ((per_thread(rcu_reader_qs_gp, t) - rcu_gp_ctr) < 0)) {
+	for_each_thread(t) {			//\lnlbl{syn:scan:b}
+		while (rcu_gp_ongoing(t) &&	//\lnlbl{syn:ongoing}
+		       ((per_thread(rcu_reader_qs_gp, t)//\lnlbl{syn:gp1}
+		         - rcu_gp_ctr) < 0)) {	//\lnlbl{syn:gp2}
 			/* @@@ poll(NULL, 0, 10); */
-			barrier();
+			barrier();		//\lnlbl{syn:barrier}

So we need another "#ifndef FCV_SNIPPET" construct here...

Quoted 101 lines
CodeSamples/defer/rcu_qs.c +4 -3
 		}
-	}
+	}					//\lnlbl{syn:scan:e}
 
 	/* Let other synchronize_rcu() instances move ahead. */
 
-	spin_unlock(&rcu_gp_lock);
+	spin_unlock(&rcu_gp_lock);		//\lnlbl{syn:spinunlock}
 
 	/* Ensure that any subsequent free()s happen -after- above checks. */
 
-	smp_mb();
+	smp_mb();				//\lnlbl{syn:mb3}
 }
+//\end{snippet}
 
 #ifdef TEST
 #include "rcutorture.h"
CodeSamples/defer/rcu_qs.h +23 -19
index 3bb45a4..26c3fb5 100644
@@ -48,31 +48,35 @@ static void rcu_init(void)
 	init_per_thread(rcu_reader_qs_gp, rcu_gp_ctr);
 }
 
-static void rcu_read_lock(void)
+//\begin{snippet}[labelbase=ln:defer:rcu_qs:read_lock_unlock,gobbleblank=yes,commandchars=\%\@\$]
+static void rcu_read_lock(void)			//\lnlbl{lock:b}
 {
 }
-
+							//\fcvblank
 static void rcu_read_unlock(void)
 {
-}
-
-static void rcu_quiescent_state(void)
+}						//\lnlbl{unlock:e}
+							//\fcvblank
+static void rcu_quiescent_state(void)		//\lnlbl{qs:b}
 {
-	smp_mb();
-	__get_thread_var(rcu_reader_qs_gp) = ACCESS_ONCE(rcu_gp_ctr) + 1;
-	smp_mb();
-}
-
-static void rcu_thread_offline(void)
+	smp_mb();				//\lnlbl{qs:mb1}
+	__get_thread_var(rcu_reader_qs_gp) =	//\lnlbl{qs:gp1}
+		READ_ONCE(rcu_gp_ctr) + 1;	//\lnlbl{qs:gp2}
+	smp_mb();				//\lnlbl{qs:mb2}
+}						//\lnlbl{qs:e}
+							//\fcvblank
+static void rcu_thread_offline(void)		//\lnlbl{offline:b}
 {
-	smp_mb();
-	__get_thread_var(rcu_reader_qs_gp) = ACCESS_ONCE(rcu_gp_ctr);
-	smp_mb();
-}
-
-static void rcu_thread_online(void)
+	smp_mb();				//\lnlbl{offline:mb1}
+	__get_thread_var(rcu_reader_qs_gp) =	//\lnlbl{offline:gp1}
+		READ_ONCE(rcu_gp_ctr);		//\lnlbl{offline:gp2}
+	smp_mb();				//\lnlbl{offline:mb2}
+}						//\lnlbl{offline:e}
+							//\fcvblank
+static void rcu_thread_online(void)		//\lnlbl{online:b}
 {
-	rcu_quiescent_state();
-}
+	rcu_quiescent_state();			//\lnlbl{online:qs}
+}						//\lnlbl{online:e}
+//\end{snippet}
 
 extern void synchronize_rcu(void);
appendix/toyrcu/toyrcu.tex +3 -0
index f7fc07b..a7ce98a 100644
@@ -1349,8 +1349,10 @@ will ignore the subsequent RCU read-side critical section.
 Third and finally, this implementation requires that the enclosing software
 environment be able to enumerate threads and maintain per-thread
 variables.
+\end{lineref}
 
 \QuickQuiz{}
+	\begin{lineref}[ln:defer:rcu:read_lock_unlock:lock]
 	Is the possibility of readers being preempted in
 	lines~\lnref{gp1}-\lnref{gp2} of
 	Listing~\ref{lst:app:toyrcu:Free-Running Counter Using RCU}
@@ -1359,6 +1361,7 @@ variables.
 	If not, why not?
 	If so, what is the sequence of events, and how can the
 	failure be addressed?
+	\end{lineref}
 \QuickQuizAnswer{
 	It is a real problem, there is a sequence of events leading to
 	failure, and there are a number of possible ways of

appendix/toyrcu/toyrcu.tex variables. · line 1373

Quoted 4 lines
appendix/toyrcu/toyrcu.tex +0 -1
@@ -1370,7 +1373,6 @@ variables.
 	added in that section greatly reduces the time required to
 	overflow the counter.
 } \QuickQuizEnd
-\end{lineref}

These changes should be moved to 1/2.

Quoted 107 lines
appendix/toyrcu/toyrcu.tex +19 -43
 \section{Nestable RCU Based on Free-Running Counter}
 \label{sec:app:toyrcu:Nestable RCU Based on Free-Running Counter}
@@ -1673,50 +1675,19 @@ overhead.
 \end{listing}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 static void rcu_read_lock(void)
-  2 {
-  3 }
-  4
-  5 static void rcu_read_unlock(void)
-  6 {
-  7 }
-  8
-  9 rcu_quiescent_state(void)
- 10 {
- 11   smp_mb();
- 12   __get_thread_var(rcu_reader_qs_gp) =
- 13     ACCESS_ONCE(rcu_gp_ctr) + 1;
- 14   smp_mb();
- 15 }
- 16
- 17 static void rcu_thread_offline(void)
- 18 {
- 19   smp_mb();
- 20   __get_thread_var(rcu_reader_qs_gp) =
- 21     ACCESS_ONCE(rcu_gp_ctr);
- 22   smp_mb();
- 23 }
- 24
- 25 static void rcu_thread_online(void)
- 26 {
- 27   rcu_quiescent_state();
- 28 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/rcu_qs@read_lock_unlock.fcv}
 \caption{Quiescent-State-Based RCU Read Side}
 \label{lst:app:toyrcu:Quiescent-State-Based RCU Read Side}
 \end{listing}
 
+\begin{lineref}[ln:defer:rcu_qs:read_lock_unlock]
 Listing~\ref{lst:app:toyrcu:Quiescent-State-Based RCU Read Side}
 (\path{rcu_qs.h})
 shows the read-side primitives used to construct a user-level
 implementation of RCU based on quiescent states, with the data shown in
 Listing~\ref{lst:app:toyrcu:Data for Quiescent-State-Based RCU}.
-As can be seen from lines~1-7 in the listing, the \co{rcu_read_lock()}
+As can be seen from lines~\lnref{lock:b}-\lnref{unlock:e} in the listing,
+the \co{rcu_read_lock()}
 and \co{rcu_read_unlock()} primitives do nothing, and can in fact
 be expected to be inlined and optimized away, as they are in
 server builds of the Linux kernel.
@@ -1724,11 +1695,14 @@ This is due to the fact that quiescent-state-based RCU implementations
 \emph{approximate} the extents of RCU read-side critical sections
 using the aforementioned quiescent states.
 Each of these quiescent states contains a call to
-\co{rcu_quiescent_state()}, which is shown from lines~9-15 in the listing.
+\co{rcu_quiescent_state()}, which is shown from
+lines~\lnref{qs:b}-\lnref{qs:e} in the listing.
 Threads entering extended quiescent states (for example, when blocking)
-may instead call \co{rcu_thread_offline()} (lines~17-23) when entering
+may instead call \co{rcu_thread_offline()}
+(lines~\lnref{offline:b}-\lnref{offline:e}) when entering
 an extended quiescent state and then call
-\co{rcu_thread_online()} (lines~25-28) when leaving it.
+\co{rcu_thread_online()}
+(lines~\lnref{online:b}-\lnref{online:e}) when leaving it.
 As such, \co{rcu_thread_online()} is analogous to \co{rcu_read_lock()}
 and \co{rcu_thread_offline()} is analogous to \co{rcu_read_unlock()}.
 In addition, \co{rcu_quiescent_state()} can be thought of as a
@@ -1741,13 +1715,16 @@ In addition, \co{rcu_quiescent_state()} can be thought of as a
 	performance optimizations.}
 It is illegal to invoke \co{rcu_quiescent_state()}, \co{rcu_thread_offline()},
 or \co{rcu_thread_online()} from an RCU read-side critical section.
+\end{lineref}
 
-In \co{rcu_quiescent_state()}, line~11 executes a memory barrier
+\begin{lineref}[ln:defer:rcu_qs:read_lock_unlock:qs]
+In \co{rcu_quiescent_state()}, line~\lnref{mb1} executes a memory barrier
 to prevent any code prior to the quiescent state (including possible
 RCU read-side critical sections) from being reordered
 into the quiescent state.
-Lines~12-13 pick up a copy of the global \co{rcu_gp_ctr}, using
-\co{ACCESS_ONCE()} to ensure that the compiler does not employ any
+Lines~\lnref{gp1}-\lnref{gp2} pick up
+a copy of the global \co{rcu_gp_ctr}, using
+\co{READ_ONCE()} to ensure that the compiler does not employ any
 optimizations that would result in \co{rcu_gp_ctr} being fetched
 more than once,
 and then adds one to the value fetched and stores it into
@@ -1756,15 +1733,20 @@ instance of \co{synchronize_rcu()} will see an odd-numbered value,
 thus becoming aware that a new RCU read-side critical section has started.
 Instances of \co{synchronize_rcu()} that are waiting on older
 RCU read-side critical sections will thus know to ignore this new one.
-Finally, line~14 executes a memory barrier, which prevents subsequent
+Finally, line~\lnref{mb2} executes a memory barrier, which prevents subsequent
 code (including a possible RCU read-side critical section) from being
-re-ordered with the lines~12-13.
+re-ordered with the lines~\lnref{gp1}-\lnref{gp2}.
+\end{lineref}
 

appendix/toyrcu/toyrcu.tex instance of \co{synchronize_rcu()} will see an odd-numbered value, · line 1749

Quoted 10 lines
appendix/toyrcu/toyrcu.tex +5 -1
 \QuickQuiz{}
-	Doesn't the additional memory barrier shown on line~14 of
+	\begin{lineref}[ln:defer:rcu_qs:read_lock_unlock:qs]
+	Doesn't the additional memory barrier shown on line~\lnref{mb2} of
 	Listing~\ref{lst:app:toyrcu:Quiescent-State-Based RCU Read Side}
 	greatly increase the overhead of \co{rcu_quiescent_state}?
+	\end{lineref}
 \QuickQuizAnswer{
+	\begin{lineref}[ln:defer:rcu_qs:read_lock_unlock:qs]
+	Doesn't the additional memory barrier shown on line~\lnref{mb2} of

??? This line shouldn't have been pasted.

With these fixed,

Thanks, Akira

Quoted 76 lines
appendix/toyrcu/toyrcu.tex +13 -29
 	Indeed it does!
 	An application using this implementation of RCU should therefore
 	invoke \co{rcu_quiescent_state} sparingly, instead using
@@ -1772,9 +1754,11 @@ re-ordered with the lines~12-13.
 	time.
 
 	However, this memory barrier is absolutely required so that
-	other threads will see the store on lines~12-13 before any
+	other threads will see the store on
+	lines~\lnref{gp1}-\lnref{gp2} before any
 	subsequent RCU read-side critical sections executed by the
 	caller.
+	\end{lineref}
 } \QuickQuizEnd
 
 Some applications might use RCU only occasionally, but use it very heavily
@@ -1794,17 +1778,22 @@ Any concurrent instances of \co{synchronize_rcu()} will thus know to
 ignore this thread.
 
 \QuickQuiz{}
-	Why are the two memory barriers on lines~19 and 22 of
+	\begin{lineref}[ln:defer:rcu_qs:read_lock_unlock:qs]
+	Why are the two memory barriers on lines~\lnref{mb1} and \lnref{mb2} of
 	Listing~\ref{lst:app:toyrcu:Quiescent-State-Based RCU Read Side}
 	needed?
+	\end{lineref}
 \QuickQuizAnswer{
-	The memory barrier on line~19 prevents any RCU read-side
+	\begin{lineref}[ln:defer:rcu_qs:read_lock_unlock:qs]
+	The memory barrier on line~\lnref{mb1} prevents any RCU read-side
 	critical sections that might precede the
 	call to \co{rcu_thread_offline()} won't be reordered by either
-	the compiler or the CPU to follow the assignment on lines~20-21.
-	The memory barrier on line~22 is, strictly speaking, unnecessary,
+	the compiler or the CPU to follow the assignment on
+	lines~\lnref{gp1}-\lnref{gp2}.
+	The memory barrier on line~\lnref{mb2} is, strictly speaking, unnecessary,
 	as it is illegal to have any RCU read-side critical sections
 	following the call to \co{rcu_thread_offline()}.
+	\end{lineref}
 } \QuickQuizEnd
 
 The \co{rcu_thread_online()} function simply invokes
@@ -1812,30 +1801,7 @@ The \co{rcu_thread_online()} function simply invokes
 quiescent state.
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 void synchronize_rcu(void)
-  2 {
-  3   int t;
-  4
-  5   smp_mb();
-  6   spin_lock(&rcu_gp_lock);
-  7   rcu_gp_ctr += 2;
-  8   smp_mb();
-  9   for_each_thread(t) {
- 10     while (rcu_gp_ongoing(t) &&
- 11            ((per_thread(rcu_reader_qs_gp, t) -
- 12              rcu_gp_ctr) < 0)) {
- 13       poll(NULL, 0, 10);
- 14     }
- 15   }
- 16   spin_unlock(&rcu_gp_lock);
- 17   smp_mb();
- 18 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/[email protected]}
 \caption{RCU Update Side Using Quiescent States}
 \label{lst:app:toyrcu:RCU Update Side Using Quiescent States}
 \end{listing}
#6 lore raw
In reply to Junchang Wang
Quoted 6 lines · Junchang Wang

Hi list,

Variable rcu_gp_ctr is accessed concurrently by the updater and readers, and hence should be protected by READ_ONCE() and WRITE_ONCE(). This patch set updates rcu and rcu_qs.

Quoted 7 lines

The tex file is updated accordingly. And a new scheme, which is suggested by Akira and can extract code snippets from the source code, has been applied.

Please note that rcu_nest also needs to be updated. I will first make sure that I'm fully understand how it works, and then submit a patch for it.

Hi Junchang,

Thanks for doing all this.
One thing I'd like you to be aware of is that when a patch is updated heavily like this, Reviewed-by: tags should be dropped.
I'll review this patch set in a few days. Please give me a little while.

Thanks, Akira

Quoted 13 lines

--
Junchang Wang (2):
rcu: Use READ_ONCE() and WRITE_ONCE() for shared variable rcu_gp_ctr
rcu_qs: Use READ_ONCE() AND WRITE_ONCE() for shared variable
rcu_gp_ctr

 CodeSamples/defer/rcu.c    |  30 ++++---
 CodeSamples/defer/rcu.h    |  21 +++--
 CodeSamples/defer/rcu_qs.c |  29 ++++---
 CodeSamples/defer/rcu_qs.h |  42 ++++-----
 appendix/toyrcu/toyrcu.tex | 207 +++++++++++++++++----------------------------
 5 files changed, 146 insertions(+), 183 deletions(-)
#7 lore raw
Quoted 16 lines · Akira Yokosawa
Quoted 6 lines · Junchang Wang

Hi list,

Variable rcu_gp_ctr is accessed concurrently by the updater and readers, and hence should be protected by READ_ONCE() and WRITE_ONCE(). This patch set updates rcu and rcu_qs.

Quoted 7 lines

The tex file is updated accordingly. And a new scheme, which is suggested by Akira and can extract code snippets from the source code, has been applied.

Please note that rcu_nest also needs to be updated. I will first make sure that I'm fully understand how it works, and then submit a patch for it.

Quoted 5 lines

Hi Junchang,

Thanks for doing all this.
One thing I'd like you to be aware of is that when a patch is updated heavily like this, Reviewed-by: tags should be dropped.

Got it. Thanks, Akira.

--Junchang

Quoted 18 lines

I'll review this patch set in a few days. Please give me a little while.

Thanks, Akira

Quoted 13 lines

--
Junchang Wang (2):
rcu: Use READ_ONCE() and WRITE_ONCE() for shared variable rcu_gp_ctr
rcu_qs: Use READ_ONCE() AND WRITE_ONCE() for shared variable
rcu_gp_ctr

 CodeSamples/defer/rcu.c    |  30 ++++---
 CodeSamples/defer/rcu.h    |  21 +++--
 CodeSamples/defer/rcu_qs.c |  29 ++++---
 CodeSamples/defer/rcu_qs.h |  42 ++++-----
 appendix/toyrcu/toyrcu.tex | 207 +++++++++++++++++----------------------------
 5 files changed, 146 insertions(+), 183 deletions(-)