Toyrcu: replace plain accesses with READ_ONCE()
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
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
@@ -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
@@ -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
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.
Signed-off-by Junchang Wang <[email protected]>Reviewed-by Akira Yokosawa <[email protected]>--- 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
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@@ -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@@ -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
-4are 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
-4pre-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}
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.
Signed-off-by Junchang Wang <[email protected]>Reviewed-by Akira Yokosawa <[email protected]>--- 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
-0CodeSamples/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@@ -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@@ -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
-4are 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 as/\lnref{barrier}/\lnref{poll}/
"poll" is the label used in the "#ifndefFCV_SNIPPET" construct suggested above.Quoted 24 lines
appendix/toyrcu/toyrcu.tex +6
-3pre-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,
Reviewed-by Akira Yokosawa <[email protected]>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}
PATCH v3 2/2 rcu_qs: Use READ_ONCE() AND WRITE_ONCE() for shared variable rcu_gp_ctr
In reply to Junchang WangReplace 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
@@ -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
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.
Signed-off-by Junchang Wang <[email protected]>Reviewed-by Akira Yokosawa <[email protected]>--- 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@@ -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@@ -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@@ -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
-29Indeed 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}
Quoted 6 lines · Junchang Wang
Hi list,
Variable
rcu_gp_ctris accessed concurrently by the updater and readers, and hence should be protected byREAD_ONCE()andWRITE_ONCE(). This patch set updates rcu andrcu_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_nestalso 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: UseREAD_ONCE()andWRITE_ONCE()for shared variablercu_gp_ctr
rcu_qs: UseREAD_ONCE()ANDWRITE_ONCE()for shared variable
rcu_gp_ctrCodeSamples/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(-)
Quoted 16 lines · Akira Yokosawa
Quoted 6 lines · Junchang Wang
Hi list,
Variable
rcu_gp_ctris accessed concurrently by the updater and readers, and hence should be protected byREAD_ONCE()andWRITE_ONCE(). This patch set updates rcu andrcu_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_nestalso 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: UseREAD_ONCE()andWRITE_ONCE()for shared variablercu_gp_ctr
rcu_qs: UseREAD_ONCE()ANDWRITE_ONCE()for shared variable
rcu_gp_ctrCodeSamples/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(-)