* [PATCH 1/6] defer: Employ new scheme for 'lst:defer:Hazard-Pointer Storage and Erasure'
2018-12-03 15:33 [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Akira Yokosawa
@ 2018-12-03 15:35 ` Akira Yokosawa
2018-12-03 15:37 ` [PATCH 2/6] defer: Employ new scheme for snippets of route_hazptr.c Akira Yokosawa
` (5 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: Akira Yokosawa @ 2018-12-03 15:35 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From a526b98e4fe052223c82dbd3cf961d40bc27f294 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Tue, 4 Dec 2018 00:13:47 +0900
Subject: [PATCH 1/6] defer: Employ new scheme for 'lst:defer:Hazard-Pointer Storage and Erasure'
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
defer/hazptr.tex | 58 ++++++++++++++++++++++++++++----------------------------
1 file changed, 29 insertions(+), 29 deletions(-)
diff --git a/defer/hazptr.tex b/defer/hazptr.tex
index 1aca813..588f603 100644
--- a/defer/hazptr.tex
+++ b/defer/hazptr.tex
@@ -22,33 +22,30 @@ and there are no longer any hazard pointers referencing it, that element
may safely be freed.
\begin{listing}[btp]
-{ \scriptsize
-\begin{verbbox}
- 1 int hp_store(void **p, void **hp)
- 2 {
- 3 void *tmp;
- 4
- 5 tmp = READ_ONCE(*p);
- 6 WRITE_ONCE(*hp, tmp);
- 7 smp_mb();
- 8 if (tmp != READ_ONCE(*p) ||
- 9 tmp == HAZPTR_POISON) {
-10 WRITE_ONCE(*hp, NULL);
-11 return 0;
-12 }
-13 return 1;
-14 }
-15
-16 void hp_erase(void **hp)
-17 {
-18 smp_mb();
-19 WRITE_ONCE(*hp, NULL);
-20 hp_free(hp);
-21 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{linelabel}[ln:defer:Hazard-Pointer Storage and Erasure]
+\begin{VerbatimL}[commandchars=\\\[\]]
+int hp_store(void **p, void **hp) \lnlbl[store:b]
+{
+ void *tmp;
+
+ tmp = READ_ONCE(*p);
+ WRITE_ONCE(*hp, tmp);
+ smp_mb();
+ if (tmp != READ_ONCE(*p) || tmp == HAZPTR_POISON) {
+ WRITE_ONCE(*hp, NULL);
+ return 0;
+ }
+ return 1;
+} \lnlbl[store:e]
+
+void hp_erase(void **hp) \lnlbl[erase:b]
+{
+ smp_mb();
+ WRITE_ONCE(*hp, NULL);
+ hp_free(hp);
+} \lnlbl[erase:e]
+\end{VerbatimL}
+\end{linelabel}
\caption{Hazard-Pointer Storage and Erasure}
\label{lst:defer:Hazard-Pointer Storage and Erasure}
\end{listing}
@@ -56,13 +53,16 @@ may safely be freed.
Of course, this means that hazard-pointer acquisition must be carried
out quite carefully in order to avoid destructive races with concurrent
deletion.
+\begin{lineref}[ln:defer:Hazard-Pointer Storage and Erasure]
One implementation is shown in
Listing~\ref{lst:defer:Hazard-Pointer Storage and Erasure},
-which shows \co{hp_store()} on lines~1-14 and \co{hp_erase()} on
-lines~16-21.
+which shows \co{hp_store()} on
+lines~\lnref{store:b}-\lnref{store:e} and \co{hp_erase()} on
+lines~\lnref{erase:b}-\lnref{erase:e}.
The \co{smp_mb()} primitive will be described in detail in
Chapter~\ref{chp:Advanced Synchronization: Memory Ordering}, but may be ignored for
the purposes of this brief overview.
+\end{lineref}
The \co{hp_store()} function records a hazard pointer at \co{hp} for the data
element whose pointer is referenced by \co{p}, while checking for
--
2.7.4
^ permalink raw reply related [flat|nested] 8+ messages in thread* [PATCH 2/6] defer: Employ new scheme for snippets of route_hazptr.c
2018-12-03 15:33 [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Akira Yokosawa
2018-12-03 15:35 ` [PATCH 1/6] defer: Employ new scheme for 'lst:defer:Hazard-Pointer Storage and Erasure' Akira Yokosawa
@ 2018-12-03 15:37 ` Akira Yokosawa
2018-12-03 15:39 ` [PATCH 3/6] defer: Employ new scheme for snippet of seqlock.h Akira Yokosawa
` (4 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: Akira Yokosawa @ 2018-12-03 15:37 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From be603d83f1555cea7c2e1e6d1306c613ceb79b21 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Tue, 4 Dec 2018 00:15:18 +0900
Subject: [PATCH 2/6] defer: Employ new scheme for snippets of route_hazptr.c
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/defer/route_hazptr.c | 50 ++++++++++--------
defer/hazptr.tex | 110 +++++----------------------------------
2 files changed, 40 insertions(+), 120 deletions(-)
diff --git a/CodeSamples/defer/route_hazptr.c b/CodeSamples/defer/route_hazptr.c
index 49e6e4a..c9285c6 100644
--- a/CodeSamples/defer/route_hazptr.c
+++ b/CodeSamples/defer/route_hazptr.c
@@ -23,58 +23,61 @@
#include "hazptr.h"
/* Route-table entry to be included in the routing list. */
+//\begin{snippet}[labelbase=ln:defer:route_hazptr:lookup,commandchars=\\\[\]]
struct route_entry {
- struct hazptr_head hh;
+ struct hazptr_head hh; //\lnlbl{hh}
struct route_entry *re_next;
unsigned long addr;
unsigned long iface;
- int re_freed;
+ int re_freed; //\lnlbl{re_freed}
};
-
+ //\fcvexclude
struct route_entry route_list;
DEFINE_SPINLOCK(routelock);
-
-/* This thread's fixed-sized set of hazard pointers. */
+ //\fcvexclude
+/* This thread's fixed-sized set of hazard pointers. */ //\fcvexclude
hazard_pointer __thread *my_hazptr;
-/*
- * Look up a route entry, return the corresponding interface.
- */
+/* \fcvexclude
+ * Look up a route entry, return the corresponding interface. \fcvexclude
+ */ //\fcvexclude
unsigned long route_lookup(unsigned long addr)
{
int offset = 0;
struct route_entry *rep;
struct route_entry **repp;
-retry:
+retry: //\lnlbl{retry}
repp = &route_list.re_next;
do {
rep = READ_ONCE(*repp);
if (rep == NULL)
return ULONG_MAX;
- if (rep == (struct route_entry *)HAZPTR_POISON)
+ if (rep == (struct route_entry *)HAZPTR_POISON) //\lnlbl{acq:b}
goto retry; /* element deleted. */
-
- /* Store a hazard pointer. */
+ //\fcvexclude
+ /* Store a hazard pointer. */ //\fcvexclude
my_hazptr[offset].p = &rep->hh;
offset = !offset;
smp_mb(); /* Force pointer loads in order. */
-
- /* Recheck the hazard pointer against the original. */
+ //\fcvexclude
+ /* Recheck the hazard pointer against the original. */ //\fcvexclude
if (READ_ONCE(*repp) != rep)
- goto retry;
-
- /* Advance to next. */
+ goto retry; //\lnlbl{acq:e}
+ //\fcvexclude
+ /* Advance to next. */ //\fcvexclude
repp = &rep->re_next;
} while (rep->addr != addr);
if (READ_ONCE(rep->re_freed))
abort();
return rep->iface;
}
+//\end{snippet}
/*
* Add an element to the route table.
*/
+//\begin{snippet}[labelbase=ln:defer:route_hazptr:add_del,commandchars=\\\[\]]
int route_add(unsigned long addr, unsigned long interface)
{
struct route_entry *rep;
@@ -84,7 +87,7 @@ int route_add(unsigned long addr, unsigned long interface)
return -ENOMEM;
rep->addr = addr;
rep->iface = interface;
- rep->re_freed = 0;
+ rep->re_freed = 0; //\lnlbl{init_freed}
spin_lock(&routelock);
rep->re_next = route_list.re_next;
route_list.re_next = rep;
@@ -92,9 +95,9 @@ int route_add(unsigned long addr, unsigned long interface)
return 0;
}
-/*
- * Remove the specified element from the route table.
- */
+/* \fcvexclude
+ * Remove the specified element from the route table. \fcvexclude
+ */ //\fcvexclude
int route_del(unsigned long addr)
{
struct route_entry *rep;
@@ -108,9 +111,9 @@ int route_del(unsigned long addr)
break;
if (rep->addr == addr) {
*repp = rep->re_next;
- rep->re_next = (struct route_entry *)HAZPTR_POISON;
+ rep->re_next = (struct route_entry *)HAZPTR_POISON; //\lnlbl{poison}
spin_unlock(&routelock);
- hazptr_free_later(&rep->hh);
+ hazptr_free_later(&rep->hh); //\lnlbl{free_later}
return 0;
}
repp = &rep->re_next;
@@ -118,6 +121,7 @@ int route_del(unsigned long addr)
spin_unlock(&routelock);
return -ENOENT;
}
+//\end{snippet}
/*
* Clear all elements from the route table.
diff --git a/defer/hazptr.tex b/defer/hazptr.tex
index 588f603..98ba002 100644
--- a/defer/hazptr.tex
+++ b/defer/hazptr.tex
@@ -181,101 +181,13 @@ Chapter~\ref{chp:Data Structures}
and in other publications~\cite{ThomasEHart2007a,McKenney:2013:SDS:2483852.2483867,MagedMichael04a}.
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct route_entry {
- 2 struct hazptr_head hh;
- 3 struct route_entry *re_next;
- 4 unsigned long addr;
- 5 unsigned long iface;
- 6 int re_freed;
- 7 };
- 8 struct route_entry route_list;
- 9 DEFINE_SPINLOCK(routelock);
-10 hazard_pointer __thread *my_hazptr;
-11
-12 unsigned long route_lookup(unsigned long addr)
-13 {
-14 int offset = 0;
-15 struct route_entry *rep;
-16 struct route_entry **repp;
-17
-18 retry:
-19 repp = &route_list.re_next;
-20 do {
-21 rep = READ_ONCE(*repp);
-22 if (rep == NULL)
-23 return ULONG_MAX;
-24 if (rep == (struct route_entry *)HAZPTR_POISON)
-25 goto retry;
-26 my_hazptr[offset].p = &rep->hh;
-27 offset = !offset;
-28 smp_mb();
-29 if (READ_ONCE(*repp) != rep)
-30 goto retry;
-31 repp = &rep->re_next;
-32 } while (rep->addr != addr);
-33 if (READ_ONCE(rep->re_freed))
-34 abort();
-35 return rep->iface;
-36 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_hazptr@lookup.fcv}
\caption{Hazard-Pointer Pre-BSD Routing Table Lookup}
\label{lst:defer:Hazard-Pointer Pre-BSD Routing Table Lookup}
\end{listing}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 int route_add(unsigned long addr,
- 2 unsigned long interface)
- 3 {
- 4 struct route_entry *rep;
- 5
- 6 rep = malloc(sizeof(*rep));
- 7 if (!rep)
- 8 return -ENOMEM;
- 9 rep->addr = addr;
-10 rep->iface = interface;
-11 rep->re_freed = 0;
-12 spin_lock(&routelock);
-13 rep->re_next = route_list.re_next;
-14 route_list.re_next = rep;
-15 spin_unlock(&routelock);
-16 return 0;
-17 }
-18
-19 int route_del(unsigned long addr)
-20 {
-21 struct route_entry *rep;
-22 struct route_entry **repp;
-23
-24 spin_lock(&routelock);
-25 repp = &route_list.re_next;
-26 for (;;) {
-27 rep = *repp;
-28 if (rep == NULL)
-29 break;
-30 if (rep->addr == addr) {
-31 *repp = rep->re_next;
-32 rep->re_next =
-33 (struct route_entry *)HAZPTR_POISON;
-34 spin_unlock(&routelock);
-35 hazptr_free_later(&rep->hh);
-36 return 0;
-37 }
-38 repp = &rep->re_next;
-39 }
-40 spin_unlock(&routelock);
-41 return -ENOENT;
-42 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_hazptr@add_del.fcv}
\caption{Hazard-Pointer Pre-BSD Routing Table Add/Delete}
\label{lst:defer:Hazard-Pointer Pre-BSD Routing Table Add/Delete}
\end{listing}
@@ -293,24 +205,28 @@ on
page~\pageref{lst:defer:Sequential Pre-BSD Routing Table},
so only differences will be discussed.
+\begin{lineref}[ln:defer:route_hazptr:lookup]
Starting with
Listing~\ref{lst:defer:Hazard-Pointer Pre-BSD Routing Table Lookup},
-line~2 shows the \co{->hh} field used to queue objects pending
+line~\lnref{hh} shows the \co{->hh} field used to queue objects pending
hazard-pointer free,
-line~6 shows the \co{->re_freed} field used to detect use-after-free bugs,
-and lines~24-30 attempt to acquire a hazard pointer, branching
-to line~18's \co{retry} label on failure.
+line~\lnref{re_freed} shows the \co{->re_freed} field used to detect use-after-free bugs,
+and lines~\lnref{acq:b}-\lnref{acq:e} attempt to acquire a hazard pointer, branching
+to line~\lnref{retry}'s \co{retry} label on failure.
+\end{lineref}
+\begin{lineref}[ln:defer:route_hazptr:add_del]
In
Listing~\ref{lst:defer:Hazard-Pointer Pre-BSD Routing Table Add/Delete},
-line~11 initializes \co{->re_freed},
-lines~32 and~33 poison the \co{->re_next} field of the newly removed
+line~\lnref{init_freed} initializes \co{->re_freed},
+line~\lnref{poison} poisons the \co{->re_next} field of the newly removed
object, and
-line~35 passes that object to the hazard pointers's
+line~\lnref{free_later} passes that object to the hazard pointers's
\co{hazptr_free_later()} function, which will free that object once it
is safe to do so.
The spinlocks work the same as in
Listing~\ref{lst:defer:Reference-Counted Pre-BSD Routing Table Add/Delete}.
+\end{lineref}
\begin{figure}[tb]
\centering
--
2.7.4
^ permalink raw reply related [flat|nested] 8+ messages in thread* [PATCH 3/6] defer: Employ new scheme for snippet of seqlock.h
2018-12-03 15:33 [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Akira Yokosawa
2018-12-03 15:35 ` [PATCH 1/6] defer: Employ new scheme for 'lst:defer:Hazard-Pointer Storage and Erasure' Akira Yokosawa
2018-12-03 15:37 ` [PATCH 2/6] defer: Employ new scheme for snippets of route_hazptr.c Akira Yokosawa
@ 2018-12-03 15:39 ` Akira Yokosawa
2018-12-03 15:41 ` [PATCH 4/6] defer: Employ new scheme for snippets of route_seqlock.c Akira Yokosawa
` (3 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: Akira Yokosawa @ 2018-12-03 15:39 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 6a5f865a117ceea5b924506b9bd55f622b95365f Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Tue, 4 Dec 2018 00:15:45 +0900
Subject: [PATCH 3/6] defer: Employ new scheme for snippet of seqlock.h
Also convert inline snippets in hazptr.tex.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/defer/seqlock.h | 55 +++++++++--------
defer/seqlock.tex | 146 +++++++++++++++++---------------------------
2 files changed, 85 insertions(+), 116 deletions(-)
diff --git a/CodeSamples/defer/seqlock.h b/CodeSamples/defer/seqlock.h
index c994285..dece371 100644
--- a/CodeSamples/defer/seqlock.h
+++ b/CodeSamples/defer/seqlock.h
@@ -18,50 +18,53 @@
* Copyright (c) 2008 Paul E. McKenney, IBM Corporation.
*/
-typedef struct {
- unsigned long seq;
+//\begin{snippet}[labelbase=ln:defer:seqlock:impl,commandchars=\\\[\]]
+typedef struct { //\lnlbl{typedef:b}
+ unsigned long seq; //\lnlbl{typedef:seq}
spinlock_t lock;
-} seqlock_t;
+} seqlock_t; //\lnlbl{typedef:e}
-#define DEFINE_SEQ_LOCK(name) seqlock_t name = { \
- .seq = 0, \
- .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
-};
-
-static inline void seqlock_init(seqlock_t *slp)
+#define DEFINE_SEQ_LOCK(name) seqlock_t name = { /* \fcvexclude */ \
+ .seq = 0, /* \fcvexclude */ \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), /* \fcvexclude */ \
+}; /* \fcvexclude */
+ /* \fcvexclude */
+static inline void seqlock_init(seqlock_t *slp) //\lnlbl{init:b}
{
slp->seq = 0;
spin_lock_init(&slp->lock);
-}
+} //\lnlbl{init:e}
-static inline unsigned long read_seqbegin(seqlock_t *slp)
+static inline unsigned long read_seqbegin(seqlock_t *slp) //\lnlbl{read_seqbegin:b}
{
unsigned long s;
- s = READ_ONCE(slp->seq);
- smp_mb();
- return s & ~0x1UL;
-}
+ s = READ_ONCE(slp->seq); //\lnlbl{read_seqbegin:fetch}
+ smp_mb(); //\lnlbl{read_seqbegin:mb}
+ return s & ~0x1UL; //\lnlbl{read_seqbegin:ret}
+} //\lnlbl{read_seqbegin:e}
-static inline int read_seqretry(seqlock_t *slp, unsigned long oldseq)
+static inline int read_seqretry(seqlock_t *slp, //\lnlbl{read_seqretry:b}
+ unsigned long oldseq)
{
unsigned long s;
- smp_mb();
- s = READ_ONCE(slp->seq);
- return s != oldseq;
-}
+ smp_mb(); //\lnlbl{read_seqretry:mb}
+ s = READ_ONCE(slp->seq); //\lnlbl{read_seqretry:fetch}
+ return s != oldseq; //\lnlbl{read_seqretry:ret}
+} //\lnlbl{read_seqretry:e}
-static inline void write_seqlock(seqlock_t *slp)
+static inline void write_seqlock(seqlock_t *slp) //\lnlbl{write_seqlock:b}
{
spin_lock(&slp->lock);
++slp->seq;
smp_mb();
-}
+} //\lnlbl{write_seqlock:e}
-static inline void write_sequnlock(seqlock_t *slp)
+static inline void write_sequnlock(seqlock_t *slp) //\lnlbl{write_sequnlock:b}
{
- smp_mb();
- ++slp->seq;
+ smp_mb(); //\lnlbl{write_sequnlock:mb}
+ ++slp->seq; //\lnlbl{write_sequnlock:inc}
spin_unlock(&slp->lock);
-}
+} //\lnlbl{write_sequnlock:e}
+//\end{snippet}
diff --git a/defer/seqlock.tex b/defer/seqlock.tex
index 84da3c0..7fabc35 100644
--- a/defer/seqlock.tex
+++ b/defer/seqlock.tex
@@ -50,30 +50,22 @@ very rarely need to retry.
} \QuickQuizEnd
\begin{listing}[bp]
-{ \scriptsize
-\begin{verbbox}
- 1 do {
- 2 seq = read_seqbegin(&test_seqlock);
- 3 /* read-side access. */
- 4 } while (read_seqretry(&test_seqlock, seq));
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{VerbatimL}
+do {
+ seq = read_seqbegin(&test_seqlock);
+ /* read-side access. */
+} while (read_seqretry(&test_seqlock, seq));
+\end{VerbatimL}
\caption{Sequence-Locking Reader}
\label{lst:defer:Sequence-Locking Reader}
\end{listing}
\begin{listing}[bp]
-{ \scriptsize
-\begin{verbbox}
- 1 write_seqlock(&test_seqlock);
- 2 /* Update */
- 3 write_sequnlock(&test_seqlock);
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{VerbatimL}
+write_seqlock(&test_seqlock);
+/* Update */
+write_sequnlock(&test_seqlock);
+\end{VerbatimL}
\caption{Sequence-Locking Writer}
\label{lst:defer:Sequence-Locking Writer}
\end{listing}
@@ -101,55 +93,7 @@ quantities used for timekeeping.
It is also used in pathname traversal to detect concurrent rename operations.
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 typedef struct {
- 2 unsigned long seq;
- 3 spinlock_t lock;
- 4 } seqlock_t;
- 5
- 6 static void seqlock_init(seqlock_t *slp)
- 7 {
- 8 slp->seq = 0;
- 9 spin_lock_init(&slp->lock);
-10 }
-11
-12 static unsigned long read_seqbegin(seqlock_t *slp)
-13 {
-14 unsigned long s;
-15
-16 s = READ_ONCE(slp->seq);
-17 smp_mb();
-18 return s & ~0x1UL;
-19 }
-20
-21 static int read_seqretry(seqlock_t *slp,
-22 unsigned long oldseq)
-23 {
-24 unsigned long s;
-25
-26 smp_mb();
-27 s = READ_ONCE(slp->seq);
-28 return s != oldseq;
-29 }
-30
-31 static void write_seqlock(seqlock_t *slp)
-32 {
-33 spin_lock(&slp->lock);
-34 ++slp->seq;
-35 smp_mb();
-36 }
-37
-38 static void write_sequnlock(seqlock_t *slp)
-39 {
-40 smp_mb();
-41 ++slp->seq;
-42 spin_unlock(&slp->lock);
-43 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/seqlock@impl.fcv}
\caption{Sequence-Locking Implementation}
\label{lst:defer:Sequence-Locking Implementation}
\end{listing}
@@ -157,18 +101,26 @@ It is also used in pathname traversal to detect concurrent rename operations.
A simple implementation of sequence locks is shown in
Listing~\ref{lst:defer:Sequence-Locking Implementation}
(\path{seqlock.h}).
-The \co{seqlock_t} data structure is shown on lines~1-4, and contains
+\begin{lineref}[ln:defer:seqlock:impl:typedef]
+The \co{seqlock_t} data structure is shown on
+lines~\lnref{b}-\lnref{e}, and contains
the sequence number along with a lock to serialize writers.
-Lines~6-10 show \co{seqlock_init()}, which, as the name indicates,
+\end{lineref}
+\begin{lineref}[ln:defer:seqlock:impl:init]
+Lines~\lnref{b}-\lnref{e} show \co{seqlock_init()}, which, as the name indicates,
initializes a \co{seqlock_t}.
+\end{lineref}
-Lines~12-19 show \co{read_seqbegin()}, which begins a sequence-lock
+\begin{lineref}[ln:defer:seqlock:impl:read_seqbegin]
+Lines~\lnref{b}-\lnref{e} show \co{read_seqbegin()}, which begins a sequence-lock
read-side critical section.
-Line~16 takes a snapshot of the sequence counter, and line~17 orders
+Line~\lnref{fetch} takes a snapshot of the sequence counter, and
+line~\lnref{mb} orders
this snapshot operation before the caller's critical section.
-Finally, line~18 returns the value of the snapshot (with the least-significant
+Finally, line~\lnref{ret} returns the value of the snapshot (with the least-significant
bit cleared), which the caller
will pass to a later call to \co{read_seqretry()}.
+\end{lineref}
\QuickQuiz{}
Why not have \co{read_seqbegin()} in
@@ -185,17 +137,20 @@ will pass to a later call to \co{read_seqretry()}.
check internal to \co{read_seqbegin()} might be preferable.
} \QuickQuizEnd
-Lines~21-29 show \co{read_seqretry()}, which returns true if there
+\begin{lineref}[ln:defer:seqlock:impl:read_seqretry]
+Lines~\lnref{b}-\lnref{e} show \co{read_seqretry()}, which returns true if there
was at least one writer since the time of the corresponding
call to \co{read_seqbegin()}.
-Line~26 orders the caller's prior critical section before line~27's
+Line~\lnref{mb} orders the caller's prior critical section before line~\lnref{fetch}'s
fetch of the new snapshot of the sequence counter.
-Finally, line~28 checks whether the sequence counter has changed,
+Finally, line~\lnref{ret} checks whether the sequence counter has changed,
in other words, whether there has been at least one writer, and returns
true if so.
+\end{lineref}
\QuickQuiz{}
- Why is the \co{smp_mb()} on line~26 of
+ Why is the \co{smp_mb()} on
+ line~\ref{ln:defer:seqlock:impl:read_seqretry:mb} of
Listing~\ref{lst:defer:Sequence-Locking Implementation}
needed?
\QuickQuizAnswer{
@@ -213,19 +168,23 @@ true if so.
\QuickQuizAnswer{
In older versions of the Linux kernel, no.
- In very new versions of the Linux kernel, line~16 could use
+ \begin{lineref}[ln:defer:seqlock:impl]
+ In very new versions of the Linux kernel,
+ line~\lnref{read_seqbegin:fetch} could use
\co{smp_load_acquire()} instead of \co{READ_ONCE()}, which
- in turn would allow the \co{smp_mb()} on line~17 to be dropped.
- Similarly, line~41 could use an \co{smp_store_release()}, for
+ in turn would allow the \co{smp_mb()} on
+ line~\lnref{read_seqbegin:mb} to be dropped.
+ Similarly, line~\lnref{write_sequnlock:inc} could use an
+ \co{smp_store_release()}, for
example, as follows:
-\begin{minipage}[c][5ex][c]{\columnwidth}\scriptsize
-\begin{verbatim}
+\begin{VerbatimU}
smp_store_release(&slp->seq, READ_ONCE(slp->seq) + 1);
-\end{verbatim}
-\end{minipage}
+\end{VerbatimU}
- This would allow the \co{smp_mb()} on line~40 to be dropped.
+ This would allow the \co{smp_mb()} on
+ line~\lnref{write_sequnlock:mb} to be dropped.
+ \end{lineref}
} \QuickQuizEnd
\QuickQuiz{}
@@ -239,12 +198,16 @@ smp_store_release(&slp->seq, READ_ONCE(slp->seq) + 1);
situation, in which case, go wild with the sequence-locking updates!
} \QuickQuizEnd
-Lines~31-36 show \co{write_seqlock()}, which simply acquires the lock,
+\begin{lineref}[ln:defer:seqlock:impl:write_seqlock]
+Lines~\lnref{b}-\lnref{e} show \co{write_seqlock()}, which simply acquires the lock,
increments the sequence number, and executes a memory barrier to ensure
that this increment is ordered before the caller's critical section.
-Lines~38-43 show \co{write_sequnlock()}, which executes a memory barrier
+\end{lineref}
+\begin{lineref}[ln:defer:seqlock:impl:write_sequnlock]
+Lines~\lnref{b}-\lnref{e} show \co{write_sequnlock()}, which executes a memory barrier
to ensure that the caller's critical section is ordered before the
-increment of the sequence number on line~44, then releases the lock.
+increment of the sequence number on line~\lnref{inc}, then releases the lock.
+\end{lineref}
\QuickQuiz{}
What if something else serializes writers, so that the lock
@@ -255,7 +218,8 @@ increment of the sequence number on line~44, then releases the lock.
} \QuickQuizEnd
\QuickQuiz{}
- Why isn't \co{seq} on line~2 of
+ Why isn't \co{seq} on
+ line~\ref{ln:defer:seqlock:impl:typedef:seq} of
Listing~\ref{lst:defer:Sequence-Locking Implementation}
\co{unsigned} rather than \co{unsigned long}?
After all, if \co{unsigned} is good enough for the Linux
@@ -266,7 +230,9 @@ increment of the sequence number on line~44, then releases the lock.
it to ignore the following sequence of events:
\begin{enumerate}
\item Thread~0 executes \co{read_seqbegin()}, picking up
- \co{->seq} in line~16, noting that the value is even,
+ \co{->seq} in
+ line~\ref{ln:defer:seqlock:impl:read_seqbegin:fetch},
+ noting that the value is even,
and thus returning to the caller.
\item Thread~0 starts executing its read-side critical section,
but is then preempted for a long time.
--
2.7.4
^ permalink raw reply related [flat|nested] 8+ messages in thread* [PATCH 4/6] defer: Employ new scheme for snippets of route_seqlock.c
2018-12-03 15:33 [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Akira Yokosawa
` (2 preceding siblings ...)
2018-12-03 15:39 ` [PATCH 3/6] defer: Employ new scheme for snippet of seqlock.h Akira Yokosawa
@ 2018-12-03 15:41 ` Akira Yokosawa
2018-12-03 15:42 ` [PATCH 5/6] defer: Employ new scheme for snippets in rcuintro and rcufundamental Akira Yokosawa
` (2 subsequent siblings)
6 siblings, 0 replies; 8+ messages in thread
From: Akira Yokosawa @ 2018-12-03 15:41 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 8232875eee86903a48912cacdd5d2268e5ff8d64 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Tue, 4 Dec 2018 00:16:17 +0900
Subject: [PATCH 4/6] defer: Employ new scheme for snippets of route_seqlock.c
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/defer/route_seqlock.c | 56 ++++++++++---------
defer/seqlock.tex | 113 ++++++--------------------------------
2 files changed, 48 insertions(+), 121 deletions(-)
diff --git a/CodeSamples/defer/route_seqlock.c b/CodeSamples/defer/route_seqlock.c
index 8224682..969704b 100644
--- a/CodeSamples/defer/route_seqlock.c
+++ b/CodeSamples/defer/route_seqlock.c
@@ -23,19 +23,20 @@
#include "seqlock.h"
/* Route-table entry to be included in the routing list. */
+//\begin{snippet}[labelbase=ln:defer:route_seqlock:lookup,commandchars=\\\[\]]
struct route_entry {
struct route_entry *re_next;
unsigned long addr;
unsigned long iface;
- int re_freed;
+ int re_freed; //\lnlbl{struct:re_freed}
};
-
+ //\fcvexclude
struct route_entry route_list;
-DEFINE_SEQ_LOCK(sl);
+DEFINE_SEQ_LOCK(sl); //\lnlbl{struct:sl}
-/*
- * Look up a route entry, return the corresponding interface.
- */
+/* \fcvexclude
+ * Look up a route entry, return the corresponding interface. \fcvexclude
+ */ //\fcvexclude
unsigned long route_lookup(unsigned long addr)
{
struct route_entry *rep;
@@ -43,31 +44,33 @@ unsigned long route_lookup(unsigned long addr)
unsigned long ret;
unsigned long s;
-retry:
- s = read_seqbegin(&sl);
+retry: //\lnlbl{lookup:retry}
+ s = read_seqbegin(&sl); //\lnlbl{lookup:r_sqbegin}
repp = &route_list.re_next;
do {
rep = READ_ONCE(*repp);
if (rep == NULL) {
- if (read_seqretry(&sl, s))
- goto retry;
+ if (read_seqretry(&sl, s)) //\lnlbl{lookup:r_sqretry1}
+ goto retry; //\lnlbl{lookup:goto_retry1}
return ULONG_MAX;
}
-
- /* Advance to next. */
+ //\fcvexclude
+ /* Advance to next. */ //\fcvexclude
repp = &rep->re_next;
} while (rep->addr != addr);
- if (READ_ONCE(rep->re_freed))
- abort();
+ if (READ_ONCE(rep->re_freed)) //\lnlbl{lookup:chk_freed}
+ abort(); //\lnlbl{lookup:abort}
ret = rep->iface;
- if (read_seqretry(&sl, s))
- goto retry;
+ if (read_seqretry(&sl, s)) //\lnlbl{lookup:r_sqretry2}
+ goto retry; //\lnlbl{lookup:goto_retry2}
return ret;
}
+//\end{snippet}
/*
* Add an element to the route table.
*/
+//\begin{snippet}[labelbase=ln:defer:route_seqlock:add_del,commandchars=\\\[\]]
int route_add(unsigned long addr, unsigned long interface)
{
struct route_entry *rep;
@@ -77,23 +80,23 @@ int route_add(unsigned long addr, unsigned long interface)
return -ENOMEM;
rep->addr = addr;
rep->iface = interface;
- rep->re_freed = 0;
- write_seqlock(&sl);
+ rep->re_freed = 0; //\lnlbl{add:clr_freed}
+ write_seqlock(&sl); //\lnlbl{add:w_sqlock}
rep->re_next = route_list.re_next;
route_list.re_next = rep;
- write_sequnlock(&sl);
+ write_sequnlock(&sl); //\lnlbl{add:w_squnlock}
return 0;
}
-/*
- * Remove the specified element from the route table.
- */
+/* \fcvexclude
+ * Remove the specified element from the route table. \fcvexclude
+ */ //\fcvexclude
int route_del(unsigned long addr)
{
struct route_entry *rep;
struct route_entry **repp;
- write_seqlock(&sl);
+ write_seqlock(&sl); //\lnlbl{del:w_sqlock}
repp = &route_list.re_next;
for (;;) {
rep = *repp;
@@ -101,17 +104,18 @@ int route_del(unsigned long addr)
break;
if (rep->addr == addr) {
*repp = rep->re_next;
- write_sequnlock(&sl);
+ write_sequnlock(&sl); //\lnlbl{del:w_squnlock1}
smp_mb();
- rep->re_freed = 1;
+ rep->re_freed = 1; //\lnlbl{del:set_freed}
free(rep);
return 0;
}
repp = &rep->re_next;
}
- write_sequnlock(&sl);
+ write_sequnlock(&sl); //\lnlbl{del:w_squnlock2}
return -ENOENT;
}
+//\end{snippet}
/*
* Clear all elements from the route table.
diff --git a/defer/seqlock.tex b/defer/seqlock.tex
index 7fabc35..3eabf31 100644
--- a/defer/seqlock.tex
+++ b/defer/seqlock.tex
@@ -263,100 +263,13 @@ increment of the sequence number on line~\lnref{inc}, then releases the lock.
} \QuickQuizEnd
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct route_entry {
- 2 struct route_entry *re_next;
- 3 unsigned long addr;
- 4 unsigned long iface;
- 5 int re_freed;
- 6 };
- 7 struct route_entry route_list;
- 8 DEFINE_SEQ_LOCK(sl);
- 9
-10 unsigned long route_lookup(unsigned long addr)
-11 {
-12 struct route_entry *rep;
-13 struct route_entry **repp;
-14 unsigned long ret;
-15 unsigned long s;
-16
-17 retry:
-18 s = read_seqbegin(&sl);
-19 repp = &route_list.re_next;
-20 do {
-21 rep = READ_ONCE(*repp);
-22 if (rep == NULL) {
-23 if (read_seqretry(&sl, s))
-24 goto retry;
-25 return ULONG_MAX;
-26 }
-27 repp = &rep->re_next;
-28 } while (rep->addr != addr);
-29 if (READ_ONCE(rep->re_freed))
-30 abort();
-31 ret = rep->iface;
-32 if (read_seqretry(&sl, s))
-33 goto retry;
-34 return ret;
-35 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_seqlock@lookup.fcv}
\caption{Sequence-Locked Pre-BSD Routing Table Lookup (BUGGY!!!)}
\label{lst:defer:Sequence-Locked Pre-BSD Routing Table Lookup}
\end{listing}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 int route_add(unsigned long addr,
- 2 unsigned long interface)
- 3 {
- 4 struct route_entry *rep;
- 5
- 6 rep = malloc(sizeof(*rep));
- 7 if (!rep)
- 8 return -ENOMEM;
- 9 rep->addr = addr;
-10 rep->iface = interface;
-11 rep->re_freed = 0;
-12 write_seqlock(&sl);
-13 rep->re_next = route_list.re_next;
-14 route_list.re_next = rep;
-15 write_sequnlock(&sl);
-16 return 0;
-17 }
-18
-19 int route_del(unsigned long addr)
-20 {
-21 struct route_entry *rep;
-22 struct route_entry **repp;
-23
-24 write_seqlock(&sl);
-25 repp = &route_list.re_next;
-26 for (;;) {
-27 rep = *repp;
-28 if (rep == NULL)
-29 break;
-30 if (rep->addr == addr) {
-31 *repp = rep->re_next;
-32 write_sequnlock(&sl);
-33 smp_mb();
-34 rep->re_freed = 1;
-35 free(rep);
-36 return 0;
-37 }
-38 repp = &rep->re_next;
-39 }
-40 write_sequnlock(&sl);
-41 return -ENOENT;
-42 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_seqlock@add_del.fcv}
\caption{Sequence-Locked Pre-BSD Routing Table Add/Delete (BUGGY!!!)}
\label{lst:defer:Sequence-Locked Pre-BSD Routing Table Add/Delete}
\end{listing}
@@ -370,19 +283,29 @@ shows \co{route_add()} and \co{route_del()} (\path{route_seqlock.c}).
This implementation is once again similar to its counterparts in earlier
sections, so only the differences will be highlighted.
+\begin{lineref}[ln:defer:route_seqlock:lookup]
In
Listing~\ref{lst:defer:Sequence-Locked Pre-BSD Routing Table Lookup},
-line~5 adds \co{->re_freed}, which is checked on lines~29 and~30.
-Line~8 adds a sequence lock, which is used by \co{route_lookup()}
-on lines~18, 23, and~32, with lines~24 and~33 branching back to
-the \co{retry} label on line~17.
+line~\lnref{struct:re_freed} adds \co{->re_freed}, which is checked on
+lines~\lnref{lookup:chk_freed} and~\lnref{lookup:abort}.
+Line~\lnref{struct:sl} adds a sequence lock, which is used by \co{route_lookup()}
+\end{lineref}
+\begin{lineref}[ln:defer:route_seqlock:lookup:lookup]
+on lines~\lnref{r_sqbegin}, \lnref{r_sqretry1}, and~\lnref{r_sqretry2},
+with lines~\lnref{goto_retry1} and~\lnref{goto_retry2} branching back to
+the \co{retry} label on line~\lnref{retry}.
The effect is to retry any lookup that runs concurrently with an update.
+\end{lineref}
+\begin{lineref}[ln:defer:route_seqlock:add_del]
In
Listing~\ref{lst:defer:Sequence-Locked Pre-BSD Routing Table Add/Delete},
-lines~12, 15, 24, and~40 acquire and release the sequence lock,
-while lines~11, 33, and~44 handle \co{->re_freed}.
+lines~\lnref{add:w_sqlock}, \lnref{add:w_squnlock}, \lnref{del:w_sqlock},
+\lnref{del:w_squnlock1}, and~\lnref{del:w_squnlock2}
+acquire and release the sequence lock,
+while lines~\lnref{add:clr_freed} and~\lnref{del:set_freed} handle \co{->re_freed}.
This implementation is therefore quite straightforward.
+\end{lineref}
\begin{figure}[tb]
\centering
--
2.7.4
^ permalink raw reply related [flat|nested] 8+ messages in thread* [PATCH 5/6] defer: Employ new scheme for snippets in rcuintro and rcufundamental
2018-12-03 15:33 [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Akira Yokosawa
` (3 preceding siblings ...)
2018-12-03 15:41 ` [PATCH 4/6] defer: Employ new scheme for snippets of route_seqlock.c Akira Yokosawa
@ 2018-12-03 15:42 ` Akira Yokosawa
2018-12-03 15:44 ` [PATCH 6/6] defer: Employ new scheme for snippets of route_rcu.c Akira Yokosawa
2018-12-03 17:23 ` [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Paul E. McKenney
6 siblings, 0 replies; 8+ messages in thread
From: Akira Yokosawa @ 2018-12-03 15:42 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 7bd805e63060278c9222b39c8c238227835f04a4 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Tue, 4 Dec 2018 00:16:42 +0900
Subject: [PATCH 5/6] defer: Employ new scheme for snippets in rcuintro and rcufundamental
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
defer/rcufundamental.tex | 381 ++++++++++++++++++++++-------------------------
defer/rcuintro.tex | 13 +-
2 files changed, 179 insertions(+), 215 deletions(-)
diff --git a/defer/rcufundamental.tex b/defer/rcufundamental.tex
index 2660e7d..3a5fad2 100644
--- a/defer/rcufundamental.tex
+++ b/defer/rcufundamental.tex
@@ -69,26 +69,22 @@ summarizes RCU fundamentals.
\label{sec:defer:Publish-Subscribe Mechanism}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct foo {
- 2 int a;
- 3 int b;
- 4 int c;
- 5 };
- 6 struct foo *gp = NULL;
- 7
- 8 /* . . . */
- 9
- 10 p = kmalloc(sizeof(*p), GFP_KERNEL);
- 11 p->a = 1;
- 12 p->b = 2;
- 13 p->c = 3;
- 14 gp = p;
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{VerbatimL}
+struct foo {
+ int a;
+ int b;
+ int c;
+};
+struct foo *gp = NULL;
+
+/* . . . */
+
+p = kmalloc(sizeof(*p), GFP_KERNEL);
+p->a = 1;
+p->b = 2;
+p->c = 3;
+gp = p;
+\end{VerbatimL}
\caption{Data Structure Publication (Unsafe)}
\label{lst:defer:Data Structure Publication (Unsafe)}
\end{listing}
@@ -116,17 +112,12 @@ We therefore encapsulate them into a primitive
\co{rcu_assign_pointer()} that has publication semantics.
The last four lines would then be as follows:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 p->a = 1;
- 2 p->b = 2;
- 3 p->c = 3;
- 4 rcu_assign_pointer(gp, p);
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+p->a = 1;
+p->b = 2;
+p->c = 3;
+rcu_assign_pointer(gp, p);
+\end{VerbatimN}
The \co{rcu_assign_pointer()}
would \emph{publish} the new structure, forcing both the compiler
@@ -137,17 +128,12 @@ However, it is not sufficient to only enforce ordering at the
updater, as the reader must enforce proper ordering as well.
Consider for example the following code fragment:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 p = gp;
- 2 if (p != NULL) {
- 3 do_something_with(p->a, p->b, p->c);
- 4 }
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+p = gp;
+if (p != NULL) {
+ do_something_with(p->a, p->b, p->c);
+}
+\end{VerbatimN}
Although this code fragment might well seem immune to misordering,
unfortunately, the
@@ -177,19 +163,14 @@ directives are required for this purpose:\footnote{
\co{memory_order_acquire}, thus emitting a needless memory-barrier
instruction on weakly ordered systems.)}
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 rcu_read_lock();
- 2 p = rcu_dereference(gp);
- 3 if (p != NULL) {
- 4 do_something_with(p->a, p->b, p->c);
- 5 }
- 6 rcu_read_unlock();
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+rcu_read_lock();
+p = rcu_dereference(gp);
+if (p != NULL) {
+ do_something_with(p->a, p->b, p->c);
+}
+rcu_read_unlock();
+\end{VerbatimN}
The \co{rcu_dereference()} primitive can thus be thought of
as \emph{subscribing} to a given value of the specified pointer,
@@ -240,27 +221,25 @@ Figure~\ref{fig:defer:Linux Linked List Abbreviated},
which shows only the non-header (blue) elements.
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct foo {
- 2 struct list_head *list;
- 3 int a;
- 4 int b;
- 5 int c;
- 6 };
- 7 LIST_HEAD(head);
- 8
- 9 /* . . . */
- 10
- 11 p = kmalloc(sizeof(*p), GFP_KERNEL);
- 12 p->a = 1;
- 13 p->b = 2;
- 14 p->c = 3;
- 15 list_add_rcu(&p->list, &head);
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{linelabel}[ln:defer:RCU Data Structure Publication]
+\begin{VerbatimL}[commandchars=\\\[\]]
+struct foo {
+ struct list_head *list;
+ int a;
+ int b;
+ int c;
+};
+LIST_HEAD(head);
+
+/* . . . */
+
+p = kmalloc(sizeof(*p), GFP_KERNEL);
+p->a = 1;
+p->b = 2;
+p->c = 3;
+list_add_rcu(&p->list, &head); \lnlbl[add_rcu]
+\end{VerbatimL}
+\end{linelabel}
\caption{RCU Data Structure Publication}
\label{lst:defer:RCU Data Structure Publication}
\end{listing}
@@ -269,7 +248,8 @@ Adapting the pointer-publish example for the linked list results in
the code shown in
Listing~\ref{lst:defer:RCU Data Structure Publication}.
-Line~15 must be protected by some synchronization mechanism (most
+Line~\ref{ln:defer:RCU Data Structure Publication:add_rcu}
+must be protected by some synchronization mechanism (most
commonly some sort of lock) to prevent multiple \co{list_add_rcu()}
instances from executing concurrently.
However, such synchronization does not prevent this \co{list_add()}
@@ -277,18 +257,13 @@ instance from executing concurrently with RCU readers.
Subscribing to an RCU-protected list is straightforward:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 rcu_read_lock();
- 2 list_for_each_entry_rcu(p, head, list) {
- 3 do_something_with(p->a, p->b, p->c);
- 4 }
- 5 rcu_read_unlock();
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+rcu_read_lock();
+list_for_each_entry_rcu(p, head, list) {
+ do_something_with(p->a, p->b, p->c);
+}
+rcu_read_unlock();
+\end{VerbatimN}
The \co{list_add_rcu()} primitive publishes an entry, inserting it at
the head of the specified list, guaranteeing that the corresponding
@@ -331,27 +306,25 @@ in the same way lists are, as shown in
Figure~\ref{fig:defer:Linux Linked List Abbreviated}.
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct foo {
- 2 struct hlist_node *list;
- 3 int a;
- 4 int b;
- 5 int c;
- 6 };
- 7 HLIST_HEAD(head);
- 8
- 9 /* . . . */
- 10
- 11 p = kmalloc(sizeof(*p), GFP_KERNEL);
- 12 p->a = 1;
- 13 p->b = 2;
- 14 p->c = 3;
- 15 hlist_add_head_rcu(&p->list, &head);
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{linelabel}[ln:defer:RCU hlist Publication]
+\begin{VerbatimL}[commandchars=\\\[\]]
+struct foo {
+ struct hlist_node *list;
+ int a;
+ int b;
+ int c;
+};
+HLIST_HEAD(head);
+
+/* . . . */
+
+p = kmalloc(sizeof(*p), GFP_KERNEL);
+p->a = 1;
+p->b = 2;
+p->c = 3;
+hlist_add_head_rcu(&p->list, &head); \lnlbl[add_head]
+\end{VerbatimL}
+\end{linelabel}
\caption{RCU {\tt hlist} Publication}
\label{lst:defer:RCU hlist Publication}
\end{listing}
@@ -360,24 +333,20 @@ Publishing a new element to an RCU-protected hlist is quite similar
to doing so for the circular list,
as shown in Listing~\ref{lst:defer:RCU hlist Publication}.
-As before, line~15 must be protected by some sort of synchronization
+As before, line~\ref{ln:defer:RCU hlist Publication:add_head}
+must be protected by some sort of synchronization
mechanism, for example, a lock.
Subscribing to an RCU-protected hlist is also similar to the
circular list:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 rcu_read_lock();
- 2 hlist_for_each_entry_rcu(p, head, list) {
- 3 do_something_with(p->a, p->b, p->c);
- 4 }
- 5 rcu_read_unlock();
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+rcu_read_lock();
+hlist_for_each_entry_rcu(p, head, list) {
+ do_something_with(p->a, p->b, p->c);
+}
+rcu_read_unlock();
+\end{VerbatimN}
\begin{table*}[tb]
\renewcommand*{\arraystretch}{1.2}
@@ -488,33 +457,31 @@ RCU to wait for readers:
\end{enumerate}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct foo {
- 2 struct list_head *list;
- 3 int a;
- 4 int b;
- 5 int c;
- 6 };
- 7 LIST_HEAD(head);
- 8
- 9 /* . . . */
- 10
- 11 p = search(head, key);
- 12 if (p == NULL) {
- 13 /* Take appropriate action, unlock, & return. */
- 14 }
- 15 q = kmalloc(sizeof(*p), GFP_KERNEL);
- 16 *q = *p;
- 17 q->b = 2;
- 18 q->c = 3;
- 19 list_replace_rcu(&p->list, &q->list);
- 20 synchronize_rcu();
- 21 kfree(p);
-\end{verbbox}
+\begin{linelabel}[ln:defer:Canonical RCU Replacement Example]
+\begin{VerbatimL}[commandchars=\\\[\]]
+struct foo {
+ struct list_head *list;
+ int a;
+ int b;
+ int c;
+};
+LIST_HEAD(head);
+
+/* . . . */
+
+p = search(head, key); \lnlbl[search]
+if (p == NULL) {
+ /* Take appropriate action, unlock, & return. */
}
-\centering
-\theverbbox
+q = kmalloc(sizeof(*p), GFP_KERNEL);
+*q = *p; \lnlbl[copy]
+q->b = 2; \lnlbl[update]
+q->c = 3;
+list_replace_rcu(&p->list, &q->list); \lnlbl[replace]
+synchronize_rcu(); \lnlbl[sync_rcu]
+kfree(p); \lnlbl[kfree]
+\end{VerbatimL}
+\end{linelabel}
\caption{Canonical RCU Replacement Example}
\label{lst:defer:Canonical RCU Replacement Example}
\end{listing}
@@ -524,10 +491,15 @@ Listing~\ref{lst:defer:Canonical RCU Replacement Example},
adapted from those in Section~\ref{sec:defer:Publish-Subscribe Mechanism},
demonstrates this process, with field \co{a} being the search key.
-Lines~19, 20, and~21 implement the three steps called out above.
-Lines~16-19 gives RCU (``read-copy update'') its name: while permitting
-concurrent \emph{reads}, line~16 \emph{copies} and lines~17-19
+\begin{lineref}[ln:defer:Canonical RCU Replacement Example]
+Lines~\lnref{replace}, \lnref{sync_rcu}, and~\lnref{kfree}
+implement the three steps called out above.
+Lines~\lnref{copy}-\lnref{replace}
+gives RCU (``read-copy update'') its name: while permitting
+concurrent \emph{reads}, line~\lnref{copy} \emph{copies} and
+lines~\lnref{update}-\lnref{replace}
do an \emph{update}.
+\end{lineref}
As discussed in Section~\ref{sec:defer:Introduction to RCU},
the \co{synchronize_rcu()} primitive can be quite simple
@@ -563,24 +535,24 @@ We can now revisit the deletion example from
Section~\ref{sec:defer:Introduction to RCU},
but now with the benefit of a firm understanding of the fundamental
concepts underlying RCU.
+\begin{lineref}[ln:defer:Canonical RCU Replacement Example]
To begin this new version of the deletion example,
-we will modify lines~11-21 in
+we will modify
+lines~\lnref{search}-\lnref{kfree} in
Listing~\ref{lst:defer:Canonical RCU Replacement Example}
to read as follows:
-
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 p = search(head, key);
- 2 if (p != NULL) {
- 3 list_del_rcu(&p->list);
- 4 synchronize_rcu();
- 5 kfree(p);
- 6 }
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\end{lineref}
+
+\begin{linelabel}[ln:defer:RCU Deletion From Linked List]
+\begin{VerbatimN}[commandchars=\\\[\]]
+p = search(head, key);
+if (p != NULL) {
+ list_del_rcu(&p->list); \lnlbl[del_rcu]
+ synchronize_rcu(); \lnlbl[sync_rcu]
+ kfree(p);
+}
+\end{VerbatimN}
+\end{linelabel}
\begin{figure}[tb]
\centering
@@ -601,8 +573,9 @@ Please note that
we have omitted the backwards pointers and the link from the tail
of the list to the head for clarity.
+\begin{lineref}[ln:defer:RCU Deletion From Linked List]
After the \co{list_del_rcu()} on
-line~3 has completed, the \co{5,6,7}~element
+line~\lnref{del_rcu} has completed, the \co{5,6,7}~element
has been removed from the list, as shown in the second row of
Figure~\ref{fig:defer:RCU Deletion From Linked List}.
Since readers do not synchronize directly with updaters,
@@ -626,12 +599,13 @@ element~\co{5,6,7} after exiting from their RCU read-side
critical sections.
Therefore,
once the \co{synchronize_rcu()} on
-line~4 completes, so that all pre-existing readers are
+line~\lnref{sync_rcu} completes, so that all pre-existing readers are
guaranteed to have completed,
there can be no more readers referencing this
element, as indicated by its green shading on the third row of
Figure~\ref{fig:defer:RCU Deletion From Linked List}.
We are thus back to a single version of the list.
+\end{lineref}
At this point, the \co{5,6,7}~element may safely be
freed, as shown on the final row of
@@ -648,20 +622,17 @@ here are the last few lines of the
example shown in
Listing~\ref{lst:defer:Canonical RCU Replacement Example}:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 q = kmalloc(sizeof(*p), GFP_KERNEL);
- 2 *q = *p;
- 3 q->b = 2;
- 4 q->c = 3;
- 5 list_replace_rcu(&p->list, &q->list);
- 6 synchronize_rcu();
- 7 kfree(p);
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{linelabel}[ln:defer:Canonical RCU Replacement Example (2nd)]
+\begin{VerbatimN}[commandchars=\\\[\],firstnumber=15]
+q = kmalloc(sizeof(*p), GFP_KERNEL); \lnlbl[kmalloc]
+*q = *p; \lnlbl[copy]
+q->b = 2; \lnlbl[update1]
+q->c = 3; \lnlbl[update2]
+list_replace_rcu(&p->list, &q->list); \lnlbl[replace]
+synchronize_rcu(); \lnlbl[sync_rcu]
+kfree(p); \lnlbl[kfree]
+\end{VerbatimN}
+\end{linelabel}
\begin{figure}[tbp]
\centering
@@ -689,24 +660,26 @@ The following text describes how to replace the \co{5,6,7} element
with \co{5,2,3} in such a way that any given reader sees one of these
two values.
-Line~1 \co{kmalloc()}s a replacement element, as follows,
+\begin{lineref}[ln:defer:Canonical RCU Replacement Example (2nd)]
+Line~\lnref{kmalloc} \co{kmalloc()}s a replacement element, as follows,
resulting in the state as shown in the second row of
Figure~\ref{fig:defer:RCU Replacement in Linked List}.
At this point, no reader can hold a reference to the newly allocated
element (as indicated by its green shading), and it is uninitialized
(as indicated by the question marks).
-Line~2 copies the old element to the new one, resulting in the
+Line~\lnref{copy} copies the old element to the new one, resulting in the
state as shown in the third row of
Figure~\ref{fig:defer:RCU Replacement in Linked List}.
The newly allocated element still cannot be referenced by readers, but
it is now initialized.
-Line~3 updates \co{q->b} to the value ``2'', and
-line~4 updates \co{q->c} to the value ``3'', as shown on the fourth row of
+Line~\lnref{update1} updates \co{q->b} to the value ``2'', and
+line~\lnref{update2} updates \co{q->c} to the value ``3'',
+as shown on the fourth row of
Figure~\ref{fig:defer:RCU Replacement in Linked List}.
-Now, line~5 does the replacement, so that the new element is
+Now, line~\lnref{replace} does the replacement, so that the new element is
finally visible to readers, and hence is shaded red, as shown on
the fifth row of
Figure~\ref{fig:defer:RCU Replacement in Linked List}.
@@ -716,7 +689,7 @@ therefore now shaded yellow), but
new readers will instead see the \co{5,2,3} element.
But any given reader is guaranteed to see some well-defined list.
-After the \co{synchronize_rcu()} on line~6 returns,
+After the \co{synchronize_rcu()} on line~\lnref{sync_rcu} returns,
a grace period will have elapsed, and so all reads that started before the
\co{list_replace_rcu()} will have completed.
In particular, any readers that might have been holding references
@@ -729,9 +702,10 @@ Figure~\ref{fig:defer:RCU Replacement in Linked List}.
As far as the readers are concerned, we are back to having a single version
of the list, but with the new element in place of the old.
-After the \co{kfree()} on line~7 completes, the list will
+After the \co{kfree()} on line~\lnref{kfree} completes, the list will
appear as shown on the final row of
Figure~\ref{fig:defer:RCU Replacement in Linked List}.
+\end{lineref}
Despite the fact that RCU was named after the replacement case,
the vast majority of RCU usage within the Linux kernel relies on
@@ -753,23 +727,18 @@ versions of the list active at a given time.
Listing~\ref{lst:defer:Concurrent RCU Deletion}.
\begin{listing}[htbp]
-\scriptsize
-{
-\begin{verbbox}
- 1 spin_lock(&mylock);
- 2 p = search(head, key);
- 3 if (p == NULL)
- 4 spin_unlock(&mylock);
- 5 else {
- 6 list_del_rcu(&p->list);
- 7 spin_unlock(&mylock);
- 8 synchronize_rcu();
- 9 kfree(p);
- 10 }
-\end{verbbox}
+\begin{VerbatimL}
+spin_lock(&mylock);
+p = search(head, key);
+if (p == NULL)
+ spin_unlock(&mylock);
+else {
+ list_del_rcu(&p->list);
+ spin_unlock(&mylock);
+ synchronize_rcu();
+ kfree(p);
}
-\centering
-\theverbbox
+\end{VerbatimL}
\caption{Concurrent RCU Deletion}
\label{lst:defer:Concurrent RCU Deletion}
\end{listing}
diff --git a/defer/rcuintro.tex b/defer/rcuintro.tex
index 6e909c9..3259a19 100644
--- a/defer/rcuintro.tex
+++ b/defer/rcuintro.tex
@@ -146,15 +146,10 @@ with time advancing from the top of the figure to the bottom.
Although production-quality implementations of this approach can be
quite complex, a toy implementation is exceedingly simple:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 for_each_online_cpu(cpu)
- 2 run_on(cpu);
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+for_each_online_cpu(cpu)
+ run_on(cpu);
+\end{VerbatimN}
The \co{for_each_online_cpu()} primitive iterates over all CPUs, and
the \co{run_on()} function causes the current thread to execute on the
--
2.7.4
^ permalink raw reply related [flat|nested] 8+ messages in thread* [PATCH 6/6] defer: Employ new scheme for snippets of route_rcu.c
2018-12-03 15:33 [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Akira Yokosawa
` (4 preceding siblings ...)
2018-12-03 15:42 ` [PATCH 5/6] defer: Employ new scheme for snippets in rcuintro and rcufundamental Akira Yokosawa
@ 2018-12-03 15:44 ` Akira Yokosawa
2018-12-03 17:23 ` [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Paul E. McKenney
6 siblings, 0 replies; 8+ messages in thread
From: Akira Yokosawa @ 2018-12-03 15:44 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 955dcb167cc6d8136c693ad193e0cd711a495150 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Tue, 4 Dec 2018 00:17:12 +0900
Subject: [PATCH 6/6] defer: Employ new scheme for snippets of route_rcu.c
Also convert inline snippets in rcuusage.tex.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/defer/route_rcu.c | 75 +++---
defer/rcuusage.tex | 523 +++++++++++++++++-------------------------
2 files changed, 256 insertions(+), 342 deletions(-)
diff --git a/CodeSamples/defer/route_rcu.c b/CodeSamples/defer/route_rcu.c
index 1fd69ea..168eead 100644
--- a/CodeSamples/defer/route_rcu.c
+++ b/CodeSamples/defer/route_rcu.c
@@ -31,48 +31,51 @@
#include "../api.h"
/* Route-table entry to be included in the routing list. */
+//\begin{snippet}[labelbase=ln:defer:route_rcu:lookup,commandchars=\\\[\]]
struct route_entry {
- struct rcu_head rh;
+ struct rcu_head rh; //\lnlbl{rh}
struct cds_list_head re_next;
unsigned long addr;
unsigned long iface;
- int re_freed;
+ int re_freed; //\lnlbl{re_freed}
};
-
+ //\fcvexclude
CDS_LIST_HEAD(route_list);
DEFINE_SPINLOCK(routelock);
-static void re_free(struct route_entry *rep)
-{
- WRITE_ONCE(rep->re_freed, 1);
- free(rep);
-}
-
-/*
- * Look up a route entry, return the corresponding interface.
- */
+static void re_free(struct route_entry *rep) //\fcvexclude
+{ //\fcvexclude
+ WRITE_ONCE(rep->re_freed, 1); //\fcvexclude
+ free(rep); //\fcvexclude
+} //\fcvexclude
+ //\fcvexclude
+/* \fcvexclude
+ * Look up a route entry, return the corresponding interface. \fcvexclude
+ */ //\fcvexclude
unsigned long route_lookup(unsigned long addr)
{
struct route_entry *rep;
unsigned long ret;
- rcu_read_lock();
+ rcu_read_lock(); //\lnlbl{lock}
cds_list_for_each_entry_rcu(rep, &route_list, re_next) {
if (rep->addr == addr) {
ret = rep->iface;
- if (READ_ONCE(rep->re_freed))
- abort();
- rcu_read_unlock();
+ if (READ_ONCE(rep->re_freed)) //\lnlbl{chk_freed}
+ abort(); //\lnlbl{abort}
+ rcu_read_unlock(); //\lnlbl{unlock1}
return ret;
}
}
- rcu_read_unlock();
+ rcu_read_unlock(); //\lnlbl{unlock2}
return ULONG_MAX;
}
+//\end{snippet}
/*
* Add an element to the route table.
*/
+//\begin{snippet}[labelbase=ln:defer:route_rcu:add_del,commandchars=\\\[\]]
int route_add(unsigned long addr, unsigned long interface)
{
struct route_entry *rep;
@@ -83,38 +86,46 @@ int route_add(unsigned long addr, unsigned long interface)
rep->addr = addr;
rep->iface = interface;
rep->re_freed = 0;
- spin_lock(&routelock);
- cds_list_add_rcu(&rep->re_next, &route_list);
- spin_unlock(&routelock);
+ spin_lock(&routelock); //\lnlbl{add:lock}
+ cds_list_add_rcu(&rep->re_next, &route_list); //\lnlbl{add:add_rcu}
+ spin_unlock(&routelock); //\lnlbl{add:unlock}
return 0;
}
-static void route_cb(struct rcu_head *rhp)
+static void route_cb(struct rcu_head *rhp) //\lnlbl{cb:b}
{
- struct route_entry *rep = container_of(rhp, struct route_entry, rh);
+ struct route_entry *rep = container_of(rhp, struct route_entry, rh); //\fcvexclude
+ //\fcvexclude
+ re_free(rep); //\fcvexclude
+/* --- Alternative code for code snippet: begin --- \fcvexclude
+ struct route_entry *rep;
- re_free(rep);
-}
+ rep = container_of(rhp, struct route_entry, rh);
+ WRITE_ONCE(rep->re_freed, 1);
+ free(rep);
+ --- Alternative code for code snippet: end --- */ //\fcvexclude
+} //\lnlbl{cb:e}
-/*
- * Remove the specified element from the route table.
- */
+/* \fcvexclude
+ * Remove the specified element from the route table. \fcvexclude
+ */ //\fcvexclude
int route_del(unsigned long addr)
{
struct route_entry *rep;
- spin_lock(&routelock);
+ spin_lock(&routelock); //\lnlbl{del:lock}
cds_list_for_each_entry(rep, &route_list, re_next) {
if (rep->addr == addr) {
- cds_list_del_rcu(&rep->re_next);
- spin_unlock(&routelock);
- call_rcu(&rep->rh, route_cb);
+ cds_list_del_rcu(&rep->re_next);//\lnlbl{del:del_rcu}
+ spin_unlock(&routelock); //\lnlbl{del:unlock1}
+ call_rcu(&rep->rh, route_cb); //\lnlbl{del:call_rcu}
return 0;
}
}
- spin_unlock(&routelock);
+ spin_unlock(&routelock); //\lnlbl{del:unlock2}
return -ENOENT;
}
+//\end{snippet}
/*
* Clear all elements from the route table.
diff --git a/defer/rcuusage.tex b/defer/rcuusage.tex
index ed0c8be..a6772a4 100644
--- a/defer/rcuusage.tex
+++ b/defer/rcuusage.tex
@@ -44,95 +44,13 @@ Section~\ref{sec:defer:RCU Usage Summary} provides a summary.
\label{sec:defer:RCU for Pre-BSD Routing}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct route_entry {
- 2 struct rcu_head rh;
- 3 struct cds_list_head re_next;
- 4 unsigned long addr;
- 5 unsigned long iface;
- 6 int re_freed;
- 7 };
- 8 CDS_LIST_HEAD(route_list);
- 9 DEFINE_SPINLOCK(routelock);
-10
-11 unsigned long route_lookup(unsigned long addr)
-12 {
-13 struct route_entry *rep;
-14 unsigned long ret;
-15
-16 rcu_read_lock();
-17 cds_list_for_each_entry_rcu(rep, &route_list,
-18 re_next) {
-19 if (rep->addr == addr) {
-20 ret = rep->iface;
-21 if (READ_ONCE(rep->re_freed))
-22 abort();
-23 rcu_read_unlock();
-24 return ret;
-25 }
-26 }
-27 rcu_read_unlock();
-28 return ULONG_MAX;
-29 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_rcu@lookup.fcv}
\caption{RCU Pre-BSD Routing Table Lookup}
\label{lst:defer:RCU Pre-BSD Routing Table Lookup}
\end{listing}
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 int route_add(unsigned long addr,
- 2 unsigned long interface)
- 3 {
- 4 struct route_entry *rep;
- 5
- 6 rep = malloc(sizeof(*rep));
- 7 if (!rep)
- 8 return -ENOMEM;
- 9 rep->addr = addr;
-10 rep->iface = interface;
-11 rep->re_freed = 0;
-12 spin_lock(&routelock);
-13 cds_list_add_rcu(&rep->re_next, &route_list);
-14 spin_unlock(&routelock);
-15 return 0;
-16 }
-17
-18 static void route_cb(struct rcu_head *rhp)
-19 {
-20 struct route_entry *rep;
-21
-22 rep = container_of(rhp, struct route_entry, rh);
-23 WRITE_ONCE(rep->re_freed, 1);
-24 free(rep);
-25 }
-26
-27 int route_del(unsigned long addr)
-28 {
-29 struct route_entry *rep;
-30
-31 spin_lock(&routelock);
-32 cds_list_for_each_entry(rep, &route_list,
-33 re_next) {
-34 if (rep->addr == addr) {
-35 cds_list_del_rcu(&rep->re_next);
-36 spin_unlock(&routelock);
-37 call_rcu(&rep->rh, route_cb);
-38 return 0;
-39 }
-40 }
-41 spin_unlock(&routelock);
-42 return -ENOENT;
-43 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/defer/route_rcu@add_del.fcv}
\caption{RCU Pre-BSD Routing Table Add/Delete}
\label{lst:defer:RCU Pre-BSD Routing Table Add/Delete}
\end{listing}
@@ -144,17 +62,24 @@ show code for an RCU-protected Pre-BSD routing table
The former shows data structures and \co{route_lookup()},
and the latter shows \co{route_add()} and \co{route_del()}.
+\begin{lineref}[ln:defer:route_rcu:lookup]
In Listing~\ref{lst:defer:RCU Pre-BSD Routing Table Lookup},
-line~2 adds the \co{->rh} field used by RCU reclamation,
-line~6 adds the \co{->re_freed} use-after-free-check field,
-lines~16, 17, 23, and~27 add RCU read-side protection,
-and lines~21 and~22 add the use-after-free check.
+line~\lnref{rh} adds the \co{->rh} field used by RCU reclamation,
+line~\lnref{re_freed} adds the \co{->re_freed} use-after-free-check field,
+lines~\lnref{lock}, \lnref{unlock1}, and~\lnref{unlock2}
+add RCU read-side protection,
+and lines~\lnref{chk_freed} and~\lnref{abort} add the use-after-free check.
+\end{lineref}
+\begin{lineref}[ln:defer:route_rcu:add_del]
In Listing~\ref{lst:defer:RCU Pre-BSD Routing Table Add/Delete},
-lines~12, 14, 31, 36, and~41 add update-side locking,
-lines~13 and~35 add RCU update-side protection,
-line~37 causes \co{route_cb()} to be invoked after a grace period elapses,
-and lines~18-25 define \co{route_cb()}.
+lines~\lnref{add:lock}, \lnref{add:unlock}, \lnref{del:lock},
+\lnref{del:unlock1}, and~\lnref{del:unlock2} add update-side locking,
+lines~\lnref{add:add_rcu} and~\lnref{del:del_rcu} add RCU update-side protection,
+line~\lnref{del:call_rcu} causes \co{route_cb()} to be invoked after
+a grace period elapses,
+and lines~\lnref{cb:b}-\lnref{cb:e} define \co{route_cb()}.
This is minimal added code for a working concurrent implementation.
+\end{lineref}
\begin{figure}[tb]
\centering
@@ -279,42 +204,27 @@ Figure~\ref{fig:defer:Performance Advantage of RCU Over Reader-Writer Locking}.
First, consider that the inner loop used to
take this measurement is as follows:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 for (i = 0; i < CSCOUNT_SCALE; i++) {
- 2 rcu_read_lock();
- 3 rcu_read_unlock();
- 4 }
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+for (i = 0; i < CSCOUNT_SCALE; i++) {
+ rcu_read_lock();
+ rcu_read_unlock();
+}
+\end{VerbatimN}
Next, consider the effective definitions of \co{rcu_read_lock()}
and \co{rcu_read_unlock()}:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 #define rcu_read_lock() do { } while (0)
- 2 #define rcu_read_unlock() do { } while (0)
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+#define rcu_read_lock() do { } while (0)
+#define rcu_read_unlock() do { } while (0)
+\end{VerbatimN}
Consider also that the compiler does simple optimizations,
allowing it to replace the loop with:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
+\begin{VerbatimN}
i = CSCOUNT_SCALE;
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\end{VerbatimN}
So the ``measurement'' of 100 femtoseconds is simply the fixed
overhead of the timing measurements divided by the number of
@@ -407,16 +317,11 @@ cycle.
RCU read-side primitives is via the following (illegal) sequence
of statements:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\small
-\begin{verbatim}
+\begin{VerbatimU}
rcu_read_lock();
synchronize_rcu();
rcu_read_unlock();
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\end{VerbatimU}
The \co{synchronize_rcu()} cannot return until all
pre-existing RCU read-side critical sections complete, but
@@ -445,23 +350,18 @@ Attempting to do such an upgrade with reader-writer locking results
in deadlock.
A sample code fragment that does an RCU read-to-update upgrade follows:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 rcu_read_lock();
- 2 list_for_each_entry_rcu(p, &head, list_field) {
- 3 do_something_with(p);
- 4 if (need_update(p)) {
- 5 spin_lock(my_lock);
- 6 do_update(p);
- 7 spin_unlock(&my_lock);
- 8 }
- 9 }
- 10 rcu_read_unlock();
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+rcu_read_lock();
+list_for_each_entry_rcu(p, &head, list_field) {
+ do_something_with(p);
+ if (need_update(p)) {
+ spin_lock(my_lock);
+ do_update(p);
+ spin_unlock(&my_lock);
+ }
+}
+rcu_read_unlock();
+\end{VerbatimN}
Note that \co{do_update()} is executed under
the protection of the lock \emph{and} under RCU read-side protection.
@@ -691,17 +591,12 @@ the RCU read-side primitives may be used as a restricted
reference-counting mechanism.
For example, consider the following code fragment:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 rcu_read_lock(); /* acquire reference. */
- 2 p = rcu_dereference(head);
- 3 /* do something with p. */
- 4 rcu_read_unlock(); /* release reference. */
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+rcu_read_lock(); /* acquire reference. */
+p = rcu_dereference(head);
+/* do something with p. */
+rcu_read_unlock(); /* release reference. */
+\end{VerbatimN}
The \co{rcu_read_lock()} primitive can be thought of as
acquiring a reference to \co{p}, because a grace period
@@ -716,20 +611,15 @@ from one task to another.
Regardless of these restrictions,
the following code can safely delete \co{p}:
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\scriptsize
-\begin{verbatim}
- 1 spin_lock(&mylock);
- 2 p = head;
- 3 rcu_assign_pointer(head, NULL);
- 4 spin_unlock(&mylock);
- 5 /* Wait for all references to be released. */
- 6 synchronize_rcu();
- 7 kfree(p);
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+spin_lock(&mylock);
+p = head;
+rcu_assign_pointer(head, NULL);
+spin_unlock(&mylock);
+/* Wait for all references to be released. */
+synchronize_rcu();
+kfree(p);
+\end{VerbatimN}
The assignment to \co{head} prevents any future references
to \co{p} from being acquired, and the \co{synchronize_rcu()}
@@ -877,55 +767,57 @@ guaranteed to remain in existence for the duration of that RCU
read-side critical section.
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 int delete(int key)
- 2 {
- 3 struct element *p;
- 4 int b;
- 5
- 6 b = hashfunction(key);
- 7 rcu_read_lock();
- 8 p = rcu_dereference(hashtable[b]);
- 9 if (p == NULL || p->key != key) {
- 10 rcu_read_unlock();
- 11 return 0;
- 12 }
- 13 spin_lock(&p->lock);
- 14 if (hashtable[b] == p && p->key == key) {
- 15 rcu_read_unlock();
- 16 rcu_assign_pointer(hashtable[b], NULL);
- 17 spin_unlock(&p->lock);
- 18 synchronize_rcu();
- 19 kfree(p);
- 20 return 1;
- 21 }
- 22 spin_unlock(&p->lock);
- 23 rcu_read_unlock();
- 24 return 0;
- 25 }
-\end{verbbox}
+\begin{linelabel}[ln:defer:Existence Guarantees Enable Per-Element Locking]
+\begin{VerbatimL}[commandchars=\\\@\$]
+int delete(int key)
+{
+ struct element *p;
+ int b;
+
+ b = hashfunction(key); \lnlbl@hash$
+ rcu_read_lock(); \lnlbl@rdlock$
+ p = rcu_dereference(hashtable[b]);
+ if (p == NULL || p->key != key) { \lnlbl@chkkey$
+ rcu_read_unlock(); \lnlbl@rdunlock1$
+ return 0; \lnlbl@ret_0:a$
+ }
+ spin_lock(&p->lock); \lnlbl@acq$
+ if (hashtable[b] == p && p->key == key) {\lnlbl@chkkey2$
+ rcu_read_unlock(); \lnlbl@rdunlock2$
+ rcu_assign_pointer(hashtable[b], NULL);\lnlbl@remove$
+ spin_unlock(&p->lock); \lnlbl@rel1$
+ synchronize_rcu(); \lnlbl@sync_rcu$
+ kfree(p); \lnlbl@kfree$
+ return 1; \lnlbl@ret_1$
+ }
+ spin_unlock(&p->lock); \lnlbl@rel2$
+ rcu_read_unlock(); \lnlbl@rdunlock3$
+ return 0; \lnlbl@ret_0:b$
}
-\centering
-\theverbbox
+\end{VerbatimL}
+\end{linelabel}
\caption{Existence Guarantees Enable Per-Element Locking}
\label{lst:defer:Existence Guarantees Enable Per-Element Locking}
\end{listing}
+\begin{lineref}[ln:defer:Existence Guarantees Enable Per-Element Locking]
Listing~\ref{lst:defer:Existence Guarantees Enable Per-Element Locking}
demonstrates how RCU-based existence guarantees can enable
per-element locking via a function that deletes an element from
a hash table.
-Line~6 computes a hash function, and line~7 enters an RCU
+Line~\lnref{hash} computes a hash function, and line~\lnref{rdlock} enters an RCU
read-side critical section.
-If line~9 finds that the corresponding bucket of the hash table is
+If line~\lnref{chkkey} finds that the corresponding bucket of the hash table is
empty or that the element present is not the one we wish to delete,
-then line~10 exits the RCU read-side critical section and line~11
+then line~\lnref{rdunlock1} exits the RCU read-side critical section and
+line~\lnref{ret_0:a}
indicates failure.
+\end{lineref}
\QuickQuiz{}
What if the element we need to delete is not the first element
- of the list on line~9 of
+ of the list on
+ line~\ref{ln:defer:Existence Guarantees Enable Per-Element Locking:chkkey} of
Listing~\ref{lst:defer:Existence Guarantees Enable Per-Element Locking}?
\QuickQuizAnswer{
As with
@@ -936,24 +828,29 @@ indicates failure.
full chaining.
} \QuickQuizEnd
-Otherwise, line~13 acquires the update-side spinlock, and
-line~14 then checks that the element is still the one that we want.
-If so, line~15 leaves the RCU read-side critical section,
-line~16 removes it from the table, line~17 releases
-the lock, line~18 waits for all pre-existing RCU read-side critical
-sections to complete, line~19 frees the newly removed element,
-and line~20 indicates success.
-If the element is no longer the one we want, line~22 releases
-the lock, line~23 leaves the RCU read-side critical section,
-and line~24 indicates failure to delete the specified key.
+\begin{lineref}[ln:defer:Existence Guarantees Enable Per-Element Locking]
+Otherwise, line~\lnref{acq} acquires the update-side spinlock, and
+line~\lnref{chkkey2} then checks that the element is still the one that we want.
+If so, line~\lnref{rdunlock2} leaves the RCU read-side critical section,
+line~\lnref{remove} removes it from the table, line~\lnref{rel1} releases
+the lock, line~\lnref{sync_rcu} waits for all pre-existing RCU read-side critical
+sections to complete, line~\lnref{kfree} frees the newly removed element,
+and line~\lnref{ret_1} indicates success.
+If the element is no longer the one we want, line~\lnref{rel2} releases
+the lock, line~\lnref{rdunlock3} leaves the RCU read-side critical section,
+and line~\lnref{ret_0:b} indicates failure to delete the specified key.
+\end{lineref}
\QuickQuiz{}
+ \begin{lineref}[ln:defer:Existence Guarantees Enable Per-Element Locking]
Why is it OK to exit the RCU read-side critical section on
- line~15 of
+ line~\lnref{rdunlock2} of
Listing~\ref{lst:defer:Existence Guarantees Enable Per-Element Locking}
- before releasing the lock on line~17?
+ before releasing the lock on line~\lnref{rel1}?
+ \end{lineref}
\QuickQuizAnswer{
- First, please note that the second check on line~14 is
+ \begin{lineref}[ln:defer:Existence Guarantees Enable Per-Element Locking]
+ First, please note that the second check on line~\lnref{chkkey2} is
necessary because some other
CPU might have removed this element while we were waiting
to acquire the lock.
@@ -970,42 +867,48 @@ and line~24 indicates failure to delete the specified key.
% A re-check is necessary if the key can mutate or if it is
% necessary to reject deleted entries (in cases where deletion
% is recorded by mutating the key.
+ \end{lineref}
} \QuickQuizEnd
\QuickQuiz{}
+ \begin{lineref}[ln:defer:Existence Guarantees Enable Per-Element Locking]
Why not exit the RCU read-side critical section on
- line~23 of
+ line~\lnref{rdunlock3} of
Listing~\ref{lst:defer:Existence Guarantees Enable Per-Element Locking}
- before releasing the lock on line~22?
+ before releasing the lock on line~\lnref{rel2}?
+ \end{lineref}
\QuickQuizAnswer{
+ \begin{lineref}[ln:defer:Existence Guarantees Enable Per-Element Locking]
Suppose we reverse the order of these two lines.
Then this code is vulnerable to the following sequence of
events:
\begin{enumerate}
\item CPU~0 invokes \co{delete()}, and finds the element
- to be deleted, executing through line~15.
+ to be deleted, executing through line~\lnref{rdunlock2}.
It has not yet actually deleted the element, but
is about to do so.
\item CPU~1 concurrently invokes \co{delete()}, attempting
to delete this same element.
However, CPU~0 still holds the lock, so CPU~1 waits
- for it at line~13.
- \item CPU~0 executes lines~16 and 17, and blocks at
- line~18 waiting for CPU~1 to exit its RCU read-side
- critical section.
- \item CPU~1 now acquires the lock, but the test on line~14
+ for it at line~\lnref{acq}.
+ \item CPU~0 executes lines~\lnref{remove} and~\lnref{rel1},
+ and blocks at line~\lnref{sync_rcu} waiting for CPU~1
+ to exit its RCU read-side critical section.
+ \item CPU~1 now acquires the lock, but the test on line~\lnref{chkkey2}
fails because CPU~0 has already removed the element.
- CPU~1 now executes line~22 (which we switched with line~23
+ CPU~1 now executes line~\lnref{rel2}
+ (which we switched with line~\lnref{rdunlock3}
for the purposes of this Quick Quiz)
and exits its RCU read-side critical section.
\item CPU~0 can now return from \co{synchronize_rcu()},
- and thus executes line~19, sending the element to
+ and thus executes line~\lnref{kfree}, sending the element to
the freelist.
\item CPU~1 now attempts to release a lock for an element
that has been freed, and, worse yet, possibly
reallocated as some other type of data structure.
This is a fatal memory-corruption error.
\end{enumerate}
+ \end{lineref}
} \QuickQuizEnd
Alert readers will recognize this as only a slight variation on
@@ -1127,84 +1030,88 @@ A simplified version of this code is shown
Listing~\ref{lst:defer:Using RCU to Wait for NMIs to Finish}.
\begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
- 1 struct profile_buffer {
- 2 long size;
- 3 atomic_t entry[0];
- 4 };
- 5 static struct profile_buffer *buf = NULL;
- 6
- 7 void nmi_profile(unsigned long pcvalue)
- 8 {
- 9 struct profile_buffer *p = rcu_dereference(buf);
- 10
- 11 if (p == NULL)
- 12 return;
- 13 if (pcvalue >= p->size)
- 14 return;
- 15 atomic_inc(&p->entry[pcvalue]);
- 16 }
- 17
- 18 void nmi_stop(void)
- 19 {
- 20 struct profile_buffer *p = buf;
- 21
- 22 if (p == NULL)
- 23 return;
- 24 rcu_assign_pointer(buf, NULL);
- 25 synchronize_sched();
- 26 kfree(p);
- 27 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{linelabel}[ln:defer:Using RCU to Wait for NMIs to Finish]
+\begin{VerbatimL}[commandchars=\\\@\$]
+struct profile_buffer { \lnlbl@struct:b$
+ long size;
+ atomic_t entry[0];
+}; \lnlbl@struct:e$
+static struct profile_buffer *buf = NULL; \lnlbl@struct:buf$
+
+void nmi_profile(unsigned long pcvalue) \lnlbl@nmi_profile:b$
+{
+ struct profile_buffer *p = rcu_dereference(buf);\lnlbl@nmi_profile:rcu_deref$
+
+ if (p == NULL) \lnlbl@nmi_profile:if_NULL$
+ return; \lnlbl@nmi_profile:ret:a$
+ if (pcvalue >= p->size) \lnlbl@nmi_profile:if_oor$
+ return; \lnlbl@nmi_profile:ret:b$
+ atomic_inc(&p->entry[pcvalue]); \lnlbl@nmi_profile:inc$
+} \lnlbl@nmi_profile:e$
+
+void nmi_stop(void) \lnlbl@nmi_stop:b$
+{
+ struct profile_buffer *p = buf; \lnlbl@nmi_stop:fetch$
+
+ if (p == NULL) \lnlbl@nmi_stop:if_NULL$
+ return; \lnlbl@nmi_stop:ret$
+ rcu_assign_pointer(buf, NULL); \lnlbl@nmi_stop:NULL$
+ synchronize_sched(); \lnlbl@nmi_stop:sync_sched$
+ kfree(p); \lnlbl@nmi_stop:kfree$
+} \lnlbl@nmi_stop:e$
+\end{VerbatimL}
+\end{linelabel}
\caption{Using RCU to Wait for NMIs to Finish}
\label{lst:defer:Using RCU to Wait for NMIs to Finish}
\end{listing}
-Lines~1-4 define a \co{profile_buffer} structure, containing a
+\begin{lineref}[ln:defer:Using RCU to Wait for NMIs to Finish:struct]
+Lines~\lnref{b}-\lnref{e} define a \co{profile_buffer} structure, containing a
size and an indefinite array of entries.
-Line~5 defines a pointer to a profile buffer, which is
+Line~\lnref{buf} defines a pointer to a profile buffer, which is
presumably initialized elsewhere to point to a dynamically allocated
region of memory.
+\end{lineref}
-Lines~7-16 define the \co{nmi_profile()} function,
+\begin{lineref}[ln:defer:Using RCU to Wait for NMIs to Finish:nmi_profile]
+Lines~\lnref{b}-\lnref{e} define the \co{nmi_profile()} function,
which is called from within an NMI handler.
As such, it cannot be preempted, nor can it be interrupted by a normal
interrupts handler, however, it is still subject to delays due to cache misses,
ECC errors, and cycle stealing by other hardware threads within the same
core.
-Line~9 gets a local pointer to the profile buffer using the
+Line~\lnref{rcu_deref} gets a local pointer to the profile buffer using the
\co{rcu_dereference()} primitive to ensure memory ordering on
DEC Alpha, and
-lines~11 and~12 exit from this function if there is no
-profile buffer currently allocated, while lines~13 and~14
+lines~\lnref{if_NULL} and~\lnref{ret:a} exit from this function if there is no
+profile buffer currently allocated, while lines~\lnref{if_oor} and~\lnref{ret:b}
exit from this function if the \co{pcvalue} argument
is out of range.
-Otherwise, line~15 increments the profile-buffer entry indexed
+Otherwise, line~\lnref{inc} increments the profile-buffer entry indexed
by the \co{pcvalue} argument.
Note that storing the size with the buffer guarantees that the
range check matches the buffer, even if a large buffer is suddenly
replaced by a smaller one.
+\end{lineref}
-Lines~18-27 define the \co{nmi_stop()} function,
+\begin{lineref}[ln:defer:Using RCU to Wait for NMIs to Finish:nmi_stop]
+Lines~\lnref{b}-\lnref{e} define the \co{nmi_stop()} function,
where the caller is responsible for mutual exclusion (for example,
holding the correct lock).
-Line~20 fetches a pointer to the profile buffer, and
-lines~22 and~23 exit the function if there is no buffer.
-Otherwise, line~24 \co{NULL}s out the profile-buffer pointer
+Line~\lnref{fetch} fetches a pointer to the profile buffer, and
+lines~\lnref{if_NULL} and~\lnref{ret} exit the function if there is no buffer.
+Otherwise, line~\lnref{NULL} \co{NULL}s out the profile-buffer pointer
(using the \co{rcu_assign_pointer()} primitive to maintain
memory ordering on weakly ordered machines),
-and line~25 waits for an RCU Sched grace period to elapse,
+and line~\lnref{sync_sched} waits for an RCU Sched grace period to elapse,
in particular, waiting for all non-preemptible regions of code,
including NMI handlers, to complete.
-Once execution continues at line~26, we are guaranteed that
+Once execution continues at line~\lnref{kfree}, we are guaranteed that
any instance of \co{nmi_profile()} that obtained a
pointer to the old buffer has returned.
It is therefore safe to free the buffer, in this case using the
\co{kfree()} primitive.
+\end{lineref}
\QuickQuiz{}
Suppose that the \co{nmi_profile()} function was preemptible.
@@ -1218,46 +1125,42 @@ It is therefore safe to free the buffer, in this case using the
Listing~\ref{lst:defer:Using RCU to Wait for Mythical Preemptible NMIs to Finish}.
%
\begin{listing}[tb]
-{\scriptsize
-\begin{verbbox}
- 1 struct profile_buffer {
- 2 long size;
- 3 atomic_t entry[0];
- 4 };
- 5 static struct profile_buffer *buf = NULL;
- 6
- 7 void nmi_profile(unsigned long pcvalue)
- 8 {
- 9 struct profile_buffer *p;
- 10
- 11 rcu_read_lock();
- 12 p = rcu_dereference(buf);
- 13 if (p == NULL) {
- 14 rcu_read_unlock();
- 15 return;
- 16 }
- 17 if (pcvalue >= p->size) {
- 18 rcu_read_unlock();
- 19 return;
- 20 }
- 21 atomic_inc(&p->entry[pcvalue]);
- 22 rcu_read_unlock();
- 23 }
- 24
- 25 void nmi_stop(void)
- 26 {
- 27 struct profile_buffer *p = buf;
- 28
- 29 if (p == NULL)
- 30 return;
- 31 rcu_assign_pointer(buf, NULL);
- 32 synchronize_rcu();
- 33 kfree(p);
- 34 }
-\end{verbbox}
+\begin{VerbatimL}
+struct profile_buffer {
+ long size;
+ atomic_t entry[0];
+};
+static struct profile_buffer *buf = NULL;
+
+void nmi_profile(unsigned long pcvalue)
+{
+ struct profile_buffer *p;
+
+ rcu_read_lock();
+ p = rcu_dereference(buf);
+ if (p == NULL) {
+ rcu_read_unlock();
+ return;
+ }
+ if (pcvalue >= p->size) {
+ rcu_read_unlock();
+ return;
+ }
+ atomic_inc(&p->entry[pcvalue]);
+ rcu_read_unlock();
}
-\centering
-\theverbbox
+
+void nmi_stop(void)
+{
+ struct profile_buffer *p = buf;
+
+ if (p == NULL)
+ return;
+ rcu_assign_pointer(buf, NULL);
+ synchronize_rcu();
+ kfree(p);
+}
+\end{VerbatimL}
\caption{Using RCU to Wait for Mythical Preemptible NMIs to Finish}
\label{lst:defer:Using RCU to Wait for Mythical Preemptible NMIs to Finish}
\end{listing}
--
2.7.4
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH 0/6] defer: Employ new scheme for code snippets (cont.)
2018-12-03 15:33 [PATCH 0/6] defer: Employ new scheme for code snippets (cont.) Akira Yokosawa
` (5 preceding siblings ...)
2018-12-03 15:44 ` [PATCH 6/6] defer: Employ new scheme for snippets of route_rcu.c Akira Yokosawa
@ 2018-12-03 17:23 ` Paul E. McKenney
6 siblings, 0 replies; 8+ messages in thread
From: Paul E. McKenney @ 2018-12-03 17:23 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Tue, Dec 04, 2018 at 12:33:32AM +0900, Akira Yokosawa wrote:
> Hi Paul,
>
> This is a followup patch set to update remaining code snippets
> in chapter "defer".
>
> My first thought was that patches #5 and #6 might conflict with
> upcoming updates to reflect consolidation of RCU flavors, but it
> looks like these code snippets are unlikely to be affected.
>
> Patch #1 assumes that you intentionally presented a different
> set of hazptr API from the one used in hazptr.h.
>
> Thanks, Akira
Applied and pushed, thank you!
Thanx, Paul
> --
> Akira Yokosawa (6):
> defer: Employ new scheme for 'lst:defer:Hazard-Pointer Storage and
> Erasure'
> defer: Employ new scheme for snippets of route_hazptr.c
> defer: Employ new scheme for snippet of seqlock.h
> defer: Employ new scheme for snippets of route_seqlock.c
> defer: Employ new scheme for snippets in rcuintro and rcufundamental
> defer: Employ new scheme for snippets of route_rcu.c
>
> CodeSamples/defer/route_hazptr.c | 50 ++--
> CodeSamples/defer/route_rcu.c | 75 +++---
> CodeSamples/defer/route_seqlock.c | 56 ++--
> CodeSamples/defer/seqlock.h | 55 ++--
> defer/hazptr.tex | 168 +++---------
> defer/rcufundamental.tex | 381 +++++++++++++--------------
> defer/rcuintro.tex | 13 +-
> defer/rcuusage.tex | 523 ++++++++++++++++----------------------
> defer/seqlock.tex | 259 ++++++-------------
> 9 files changed, 637 insertions(+), 943 deletions(-)
>
> --
> 2.7.4
>
^ permalink raw reply [flat|nested] 8+ messages in thread