[PATCH 0/7] Further conversion of code snippets (howto, cpu, SMPdesign)

[PATCH 0/7] Further conversion of code snippets (howto, cpu, SMPdesign)

[Akira Yokosawa]

Hi Paul,

This is another set of patches converting code snippets to new scheme.
Notes on the changes other than simple conversion follow.

Patch #2 contains somewhat ugly hack in lockhdeq.c to suppress
"____cacheline_internodealigned_in_smp" in the resulting snippet.
I'm afraid it could hurt your eyes.

Patch #5 renames "percpu*" to "perthread*" to respect the names
used in actual code.

Patch #6 includes substitution of ACCESS_ONCE -> READ_ONCE.

Patch #7 does the substitution under CodeSamples. It also adds
a couple of function prototypes in maze.h.

        Thanks, Akira
--
Akira Yokosawa (7):
  howto, cpu: Employ new scheme for command/code snippets
  SMPdesign: Employ new scheme for snippet of lockhdeq.c
  SMPdesign: Employ new scheme for snippet of lockhdeq.c and locktdeq.c
  SMPdesign: Employ new scheme for inline snippets
  SMPdesign: Employ new scheme for snippets from smpalloc.c
  SMPdesign/beyond: Employ new scheme for inline pseudocode snippets
  CodeSamples/SMPdesign/maze: Substitute {READ/WRITE}_ONCE() for
    ACCESS_ONCE()

 CodeSamples/SMPdesign/lockhdeq.c       |  53 ++--
 CodeSamples/SMPdesign/locktdeq.c       |  70 ++---
 CodeSamples/SMPdesign/maze/maze.h      |   6 +
 CodeSamples/SMPdesign/maze/maze_fg.c   |  18 +-
 CodeSamples/SMPdesign/maze/maze_part.c |  18 +-
 CodeSamples/SMPdesign/smpalloc.c       |  57 ++--
 SMPdesign/SMPdesign.tex                | 479 ++++++++++++++-------------------
 SMPdesign/beyond.tex                   | 319 +++++++++++-----------
 SMPdesign/partexercises.tex            | 263 ++++++------------
 cpu/overview.tex                       |  15 +-
 howto/howto.tex                        |  60 ++---
 11 files changed, 605 insertions(+), 753 deletions(-)

-- 
2.7.4

[PATCH 1/7] howto, cpu: Employ new scheme for command/code snippets

[Akira Yokosawa]

From 687613a6796f9c2b2539757e9041b6f89e94f426 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 28 Oct 2018 17:41:47 +0900
Subject: [PATCH 1/7] howto, cpu: Employ new scheme for command/code snippets

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 cpu/overview.tex | 15 +++++---------
 howto/howto.tex  | 60 ++++++++++++++++++++++----------------------------------
 2 files changed, 28 insertions(+), 47 deletions(-)

diff --git a/cpu/overview.tex b/cpu/overview.tex
index 7c02c13..071cf7c 100644
--- a/cpu/overview.tex
+++ b/cpu/overview.tex
@@ -203,16 +203,11 @@ Appendix~\ref{chp:app:whymb:Why Memory Barriers?}.
 In the meantime, consider the following simple lock-based critical
 section:
 
-\vspace{5pt}
-\begin{minipage}[t]{\columnwidth}
-\small
-\begin{verbatim}
-  1 spin_lock(&mylock);
-  2 a = a + 1;
-  3 spin_unlock(&mylock);
-\end{verbatim}
-\end{minipage}
-\vspace{5pt}
+\begin{VerbatimN}
+spin_lock(&mylock);
+a = a + 1;
+spin_unlock(&mylock);
+\end{VerbatimN}
 
 \begin{figure}[tb]
 \centering
diff --git a/howto/howto.tex b/howto/howto.tex
index e88bd90..2fbf8a3 100644
--- a/howto/howto.tex
+++ b/howto/howto.tex
@@ -346,13 +346,9 @@ this source code may be found in the \path{CodeSamples} directory
 of this book's git tree.
 For example, on UNIX systems, you should be able to type the following:
 
-\begin{quote}
-	{\scriptsize
-	\begin{verbatim}
-		find CodeSamples -name rcu_rcpls.c -print
-	\end{verbatim}
-	}
-\end{quote}
+\begin{VerbatimU}
+find CodeSamples -name rcu_rcpls.c -print
+\end{VerbatimU}
 
 This command will locate the file \path{rcu_rcpls.c}, which is called out in
 Appendix~\ref{chp:app:``Toy'' RCU Implementations}.
@@ -362,36 +358,28 @@ Other types of systems have well-known ways of locating files by filename.
 \label{sec:howto:Whose Book Is This?}
 
 \begin{listing*}[tbp]
-{
-\scriptsize
-\begin{verbbox}
-  1 git clone git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/perfbook.git
-  2 cd perfbook
-  3 # You may need to install a font here. See item 1 in FAQ.txt.
-  4 make
-  5 evince perfbook.pdf & # Two-column version
-  6 make perfbook-1c.pdf
-  7 evince perfbook-1c.pdf & # One-column version for e-readers
-\end{verbbox}
-}
-\hspace*{1in}\OneColumnHSpace{-0.5in}\theverbbox
+\begin{VerbatimL}
+git clone git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/perfbook.git
+cd perfbook
+# You may need to install a font here. See item 1 in FAQ.txt.
+make
+evince perfbook.pdf & # Two-column version
+make perfbook-1c.pdf
+evince perfbook-1c.pdf & # One-column version for e-readers
+\end{VerbatimL}
 \caption{Creating an Up-To-Date PDF}
 \label{lst:howto:Creating a Up-To-Date PDF}
 \end{listing*}
 
 \begin{listing*}[tbp]
-{
-\scriptsize
-\begin{verbbox}
-  1 git remote update
-  2 git checkout origin/master
-  3 make
-  4 evince perfbook.pdf & # Two-column version
-  5 make perfbook-1c.pdf
-  6 evince perfbook-1c.pdf & # One-column version for e-readers
-\end{verbbox}
-}
-\hspace*{1in}\OneColumnHSpace{-0.5in}\theverbbox
+\begin{VerbatimL}
+git remote update
+git checkout origin/master
+make
+evince perfbook.pdf & # Two-column version
+make perfbook-1c.pdf
+evince perfbook-1c.pdf & # One-column version for e-readers
+\end{VerbatimL}
 \caption{Generating an Updated PDF}
 \label{lst:howto:Generating an Updated PDF}
 \end{listing*}
@@ -441,11 +429,9 @@ One important requirement is that each patch (or commit, in the case
 of a \co{git pull} request) must contain a valid \co{Signed-off-by:} line,
 which has the following format:
 
-\begin{quote}
-	{ \scriptsize
-	\co{Signed-off-by: My Name <myname@example.org>}
-	}
-\end{quote}
+\begin{VerbatimU}
+Signed-off-by: My Name <myname@example.org>
+\end{VerbatimU}
 
 Please see \url{http://lkml.org/lkml/2007/1/15/219} for an example
 patch containing a \co{Signed-off-by:} line.
-- 
2.7.4

[PATCH 2/7] SMPdesign: Employ new scheme for snippet of lockhdeq.c

[Akira Yokosawa]

From c516d1ab6d3930d0431aa30a4cf4e3004d70a865 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 28 Oct 2018 18:11:44 +0900
Subject: [PATCH 2/7] SMPdesign: Employ new scheme for snippet of lockhdeq.c

To remove " ____cacheline_internodealigned_in_smp" in the resulting
snippet, provide alternative statement in a comment block as follows:

	spinlock_t rlock ____cacheline_internodealigned_in_smp;	//\fcvexclude
/* -- begin alternative code for snippet \fcvexclude
	spinlock_t rlock;				//\lnlbl{rlock}
   -- end alternative code for snippet \fcvexclude */

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 CodeSamples/SMPdesign/lockhdeq.c | 19 ++++++++++++-------
 SMPdesign/partexercises.tex      | 24 +++++++-----------------
 2 files changed, 19 insertions(+), 24 deletions(-)

diff --git a/CodeSamples/SMPdesign/lockhdeq.c b/CodeSamples/SMPdesign/lockhdeq.c
index d6cc099..8ba635b 100644
--- a/CodeSamples/SMPdesign/lockhdeq.c
+++ b/CodeSamples/SMPdesign/lockhdeq.c
@@ -129,15 +129,20 @@ void deq_push_r(struct cds_list_head *e, struct deq *p)
 
 #define PDEQ_N_BKTS 4
 
+//\begin{snippet}[labelbase=ln:SMPdesign:lockhdeq:struct_pdeq,commandchars=\\\@\$]
 struct pdeq {
-	spinlock_t llock;
-	int lidx;
-	/* char pad1[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */
-	spinlock_t rlock ____cacheline_internodealigned_in_smp;
-	int ridx;
-	/* char pad2[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */
-	struct deq bkt[PDEQ_N_BKTS];
+	spinlock_t llock;				//\lnlbl{llock}
+	int lidx;					//\lnlbl{lidx}
+	/* char pad1[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */	//\fcvexclude
+	spinlock_t rlock ____cacheline_internodealigned_in_smp;			//\fcvexclude
+/* -- begin alternative code for snippet \fcvexclude
+	spinlock_t rlock;				//\lnlbl{rlock}
+   -- end alternative code for snippet \fcvexclude */
+	int ridx;					//\lnlbl{ridx}
+	/* char pad2[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */	//\fcvexclude
+	struct deq bkt[PDEQ_N_BKTS];			//\lnlbl{bkt}
 };
+//\end{snippet}
 
 static int moveleft(int idx)
 {
diff --git a/SMPdesign/partexercises.tex b/SMPdesign/partexercises.tex
index db4b5d8..5b5fd5a 100644
--- a/SMPdesign/partexercises.tex
+++ b/SMPdesign/partexercises.tex
@@ -342,19 +342,7 @@ Each underlying single-lock double-ended queue holds a one-quarter
 slice of the full parallel double-ended queue.
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 struct pdeq {
-  2   spinlock_t llock;
-  3   int lidx;
-  4   spinlock_t rlock;
-  5   int ridx;
-  6   struct deq bkt[DEQ_N_BKTS];
-  7 };
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/SMPdesign/lockhdeq@struct_pdeq.fcv}
 \caption{Lock-Based Parallel Double-Ended Queue Data Structure}
 \label{lst:SMPdesign:Lock-Based Parallel Double-Ended Queue Data Structure}
 \end{listing}
@@ -363,13 +351,15 @@ Listing~\ref{lst:SMPdesign:Lock-Based Parallel Double-Ended Queue Data Structure
 shows the corresponding C-language data structure, assuming an
 existing \co{struct deq} that provides a trivially locked
 double-ended-queue implementation.
-This data structure contains the left-hand lock on line~2,
-the left-hand index on line~3, the right-hand lock on line~4
+\begin{lineref}[ln:SMPdesign:lockhdeq:struct_pdeq]
+This data structure contains the left-hand lock on line~\lnref{llock},
+the left-hand index on line~\lnref{lidx}, the right-hand lock on line~\lnref{rlock}
 (which is cache-aligned in the actual implementation),
-the right-hand index on line~5, and, finally, the hashed array
-of simple lock-based double-ended queues on line~6.
+the right-hand index on line~\lnref{ridx}, and, finally, the hashed array
+of simple lock-based double-ended queues on line~\lnref{bkt}.
 A high-performance implementation would of course use padding or special
 alignment directives to avoid false sharing.
+\end{lineref}
 
 \begin{listing*}[bp]
 { \scriptsize
-- 
2.7.4

[PATCH 3/7] SMPdesign: Employ new scheme for snippet of lockhdeq.c and locktdeq.c

[Akira Yokosawa]

From 966f43a286dedd32a577409fa54221b42f50d8cd Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Mon, 29 Oct 2018 21:07:28 +0900
Subject: [PATCH 3/7] SMPdesign: Employ new scheme for snippet of lockhdeq.c and locktdeq.c

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 CodeSamples/SMPdesign/lockhdeq.c |  34 +++---
 CodeSamples/SMPdesign/locktdeq.c |  70 ++++++------
 SMPdesign/partexercises.tex      | 237 +++++++++++++--------------------------
 3 files changed, 132 insertions(+), 209 deletions(-)

diff --git a/CodeSamples/SMPdesign/lockhdeq.c b/CodeSamples/SMPdesign/lockhdeq.c
index 8ba635b..1b57423 100644
--- a/CodeSamples/SMPdesign/lockhdeq.c
+++ b/CodeSamples/SMPdesign/lockhdeq.c
@@ -166,19 +166,20 @@ void init_pdeq(struct pdeq *d)
 		init_deq(&d->bkt[i]);
 }
 
-struct cds_list_head *pdeq_pop_l(struct pdeq *d)
+//\begin{snippet}[labelbase=ln:SMPdesign:lockhdeq:pop_push,commandchars=\\\@\$]
+struct cds_list_head *pdeq_pop_l(struct pdeq *d)//\lnlbl{popl:b}
 {
 	struct cds_list_head *e;
 	int i;
 
-	spin_lock(&d->llock);
-	i = moveright(d->lidx);
-	e = deq_pop_l(&d->bkt[i]);
-	if (e != NULL)
-		d->lidx = i;
-	spin_unlock(&d->llock);
-	return e;
-}
+	spin_lock(&d->llock);			//\lnlbl{popl:acq}
+	i = moveright(d->lidx);			//\lnlbl{popl:idx}
+	e = deq_pop_l(&d->bkt[i]);		//\lnlbl{popl:deque}
+	if (e != NULL)				//\lnlbl{popl:check}
+		d->lidx = i;			//\lnlbl{popl:record}
+	spin_unlock(&d->llock);			//\lnlbl{popl:rel}
+	return e;				//\lnlbl{popl:return}
+}						//\lnlbl{popl:e}
 
 struct cds_list_head *pdeq_pop_r(struct pdeq *d)
 {
@@ -194,16 +195,16 @@ struct cds_list_head *pdeq_pop_r(struct pdeq *d)
 	return e;
 }
 
-void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)
+void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)//\lnlbl{pushl:b}
 {
 	int i;
 
-	spin_lock(&d->llock);
-	i = d->lidx;
-	deq_push_l(e, &d->bkt[i]);
-	d->lidx = moveleft(d->lidx);
-	spin_unlock(&d->llock);
-}
+	spin_lock(&d->llock);				//\lnlbl{pushl:acq}
+	i = d->lidx;					//\lnlbl{pushl:idx}
+	deq_push_l(e, &d->bkt[i]);			//\lnlbl{pushl:enque}
+	d->lidx = moveleft(d->lidx);			//\lnlbl{pushl:update}
+	spin_unlock(&d->llock);				//\lnlbl{pushl:rel}
+}							//\lnlbl{pushl:e}
 
 void pdeq_push_r(struct cds_list_head *e, struct pdeq *d)
 {
@@ -215,6 +216,7 @@ void pdeq_push_r(struct cds_list_head *e, struct pdeq *d)
 	d->ridx = moveright(d->ridx);
 	spin_unlock(&d->rlock);
 }
+//\end{snippet}
 
 #ifdef TEST
 #define DEQ_AND_PDEQ
diff --git a/CodeSamples/SMPdesign/locktdeq.c b/CodeSamples/SMPdesign/locktdeq.c
index 335a68b..4a0ca51 100644
--- a/CodeSamples/SMPdesign/locktdeq.c
+++ b/CodeSamples/SMPdesign/locktdeq.c
@@ -99,58 +99,60 @@ void init_pdeq(struct pdeq *d)
 	init_deq(&d->rdeq);
 }
 
-struct cds_list_head *pdeq_pop_l(struct pdeq *d)
+//\begin{snippet}[labelbase=ln:SMPdesign:locktdeq:pop_push,commandchars=\\\@\$]
+struct cds_list_head *pdeq_pop_l(struct pdeq *d)		//\lnlbl{popl:b}
 {
 	struct cds_list_head *e;
 
-	spin_lock(&d->llock);
-	e = deq_pop_l(&d->ldeq);
+	spin_lock(&d->llock);					//\lnlbl{popl:acq:l}
+	e = deq_pop_l(&d->ldeq);				//\lnlbl{popl:deq:ll}
 	if (e == NULL) {
-		spin_lock(&d->rlock);
-		e = deq_pop_l(&d->rdeq);
-		cds_list_splice(&d->rdeq.chain, &d->ldeq.chain);
-		CDS_INIT_LIST_HEAD(&d->rdeq.chain);
-		spin_unlock(&d->rlock);
-	}
-	spin_unlock(&d->llock);
+		spin_lock(&d->rlock);				//\lnlbl{popl:acq:r}
+		e = deq_pop_l(&d->rdeq);			//\lnlbl{popl:deq:lr}
+		cds_list_splice(&d->rdeq.chain, &d->ldeq.chain);//\lnlbl{popl:move}
+		CDS_INIT_LIST_HEAD(&d->rdeq.chain);		//\lnlbl{popl:init:r}
+		spin_unlock(&d->rlock);				//\lnlbl{popl:rel:r}
+	}							//\lnlbl{popl:skip}
+	spin_unlock(&d->llock);					//\lnlbl{popl:rel:l}
 	return e;
-}
+}								//\lnlbl{popl:e}
 
-struct cds_list_head *pdeq_pop_r(struct pdeq *d)
+struct cds_list_head *pdeq_pop_r(struct pdeq *d)		//\lnlbl{popr:b}
 {
 	struct cds_list_head *e;
 
-	spin_lock(&d->rlock);
-	e = deq_pop_r(&d->rdeq);
-	if (e == NULL) {
-		spin_unlock(&d->rlock);
-		spin_lock(&d->llock);
-		spin_lock(&d->rlock);
-		e = deq_pop_r(&d->rdeq);
-		if (e == NULL) {
-			e = deq_pop_r(&d->ldeq);
-			cds_list_splice(&d->ldeq.chain, &d->rdeq.chain);
-			CDS_INIT_LIST_HEAD(&d->ldeq.chain);
+	spin_lock(&d->rlock);					//\lnlbl{popr:acq:r1}
+	e = deq_pop_r(&d->rdeq);				//\lnlbl{popr:deq:rr1}
+	if (e == NULL) {					//\lnlbl{popr:check1}
+		spin_unlock(&d->rlock);				//\lnlbl{popr:rel:r1}
+		spin_lock(&d->llock);				//\lnlbl{popr:acq:l}
+		spin_lock(&d->rlock);				//\lnlbl{popr:acq:r2}
+		e = deq_pop_r(&d->rdeq);			//\lnlbl{popr:deq:rr2}
+		if (e == NULL) {				//\lnlbl{popr:check2}
+			e = deq_pop_r(&d->ldeq);			//\lnlbl{popr:deq:rl}
+			cds_list_splice(&d->ldeq.chain, &d->rdeq.chain);//\lnlbl{popr:move}
+			CDS_INIT_LIST_HEAD(&d->ldeq.chain);		//\lnlbl{popr:init:l}
 		}
-		spin_unlock(&d->llock);
-	}
-	spin_unlock(&d->rlock);
+		spin_unlock(&d->llock);				//\lnlbl{popr:rel:l}
+	}							//\lnlbl{popr:skip2}
+	spin_unlock(&d->rlock);					//\lnlbl{popr:rel:r2}
 	return e;
-}
+}								//\lnlbl{popr:e}
 
-void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)
+void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)	//\lnlbl{pushl:b}
 {
-	spin_lock(&d->llock);
-	deq_push_l(e, &d->ldeq);
-	spin_unlock(&d->llock);
-}
+	spin_lock(&d->llock);					//\lnlbl{pushl:acq:l}
+	deq_push_l(e, &d->ldeq);				//\lnlbl{pushl:que:l}
+	spin_unlock(&d->llock);					//\lnlbl{pushl:rel:l}
+}								//\lnlbl{pushl:e}
 
-void pdeq_push_r(struct cds_list_head *e, struct pdeq *d)
+void pdeq_push_r(struct cds_list_head *e, struct pdeq *d)	//\lnlbl{pushr:b}
 {
 	spin_lock(&d->rlock);
 	deq_push_r(e, &d->rdeq);
 	spin_unlock(&d->rlock);
-}
+}								//\lnlbl{pushr:e}
+//\end{snippet}
 
 #ifdef TEST
 #include "deqtorture.h"
diff --git a/SMPdesign/partexercises.tex b/SMPdesign/partexercises.tex
index 5b5fd5a..5ce7e86 100644
--- a/SMPdesign/partexercises.tex
+++ b/SMPdesign/partexercises.tex
@@ -361,65 +361,11 @@ A high-performance implementation would of course use padding or special
 alignment directives to avoid false sharing.
 \end{lineref}
 
-\begin{listing*}[bp]
-{ \scriptsize
-\begin{verbbox}
-  1 struct cds_list_head *pdeq_pop_l(struct pdeq *d)
-  2 {
-  3   struct cds_list_head *e;
-  4   int i;
-  5 
-  6   spin_lock(&d->llock);
-  7   i = moveright(d->lidx);
-  8   e = deq_pop_l(&d->bkt[i]);
-  9   if (e != NULL)
- 10     d->lidx = i;
- 11   spin_unlock(&d->llock);
- 12   return e;
- 13 }
- 14 
- 15 struct cds_list_head *pdeq_pop_r(struct pdeq *d)
- 16 {
- 17   struct cds_list_head *e;
- 18   int i;
- 19 
- 20   spin_lock(&d->rlock);
- 21   i = moveleft(d->ridx);
- 22   e = deq_pop_r(&d->bkt[i]);
- 23   if (e != NULL)
- 24     d->ridx = i;
- 25   spin_unlock(&d->rlock);
- 26   return e;
- 27 }
- 28 
- 29 void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)
- 30 {
- 31   int i;
- 32 
- 33   spin_lock(&d->llock);
- 34   i = d->lidx;
- 35   deq_push_l(e, &d->bkt[i]);
- 36   d->lidx = moveleft(d->lidx);
- 37   spin_unlock(&d->llock);
- 38 }
- 39 
- 40 void pdeq_push_r(struct cds_list_head *e, struct pdeq *d)
- 41 {
- 42   int i;
- 43 
- 44   spin_lock(&d->rlock);
- 45   i = d->ridx;
- 46   deq_push_r(e, &d->bkt[i]);
- 47   d->ridx = moveright(d->ridx);
- 48   spin_unlock(&d->rlock);
- 49 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{listing}[tbp]
+\input{CodeSamples/SMPdesign/lockhdeq@pop_push.fcv}
 \caption{Lock-Based Parallel Double-Ended Queue Implementation}
 \label{lst:SMPdesign:Lock-Based Parallel Double-Ended Queue Implementation}
-\end{listing*}
+\end{listing}
 
 Listing~\ref{lst:SMPdesign:Lock-Based Parallel Double-Ended Queue Implementation}
 (\path{lockhdeq.c})
@@ -430,22 +376,34 @@ shows the implementation of the enqueue and dequeue functions.\footnote{
 Discussion will focus on the left-hand operations, as the right-hand
 operations are trivially derived from them.
 
-Lines~1-13 show \co{pdeq_pop_l()}, which left\-/dequeues and returns
+\begin{lineref}[ln:SMPdesign:lockhdeq:pop_push:popl]
+Lines~\lnref{b}-\lnref{e} show \co{pdeq_pop_l()},
+which left\-/dequeues and returns
 an element if possible, returning \co{NULL} otherwise.
-Line~6 acquires the left-hand spinlock, and line~7 computes the
+Line~\lnref{acq} acquires the left-hand spinlock,
+and line~\lnref{idx} computes the
 index to be dequeued from.
-Line~8 dequeues the element, and, if line~9 finds the result to be
-non-\co{NULL}, line~10 records the new left-hand index.
-Either way, line~11 releases the lock, and, finally, line~12 returns
+Line~\lnref{deque} dequeues the element, and,
+if line~\lnref{check} finds the result to be
+non-\co{NULL}, line~\lnref{record} records the new left-hand index.
+Either way, line~\lnref{rel} releases the lock, and,
+finally, line~\lnref{return} returns
 the element if there was one, or \co{NULL} otherwise.
+\end{lineref}
 
-Lines~29-38 shows \co{pdeq_push_l()}, which left-enqueues the specified
+\begin{lineref}[ln:SMPdesign:lockhdeq:pop_push:pushl]
+Lines~\lnref{b}-\lnref{e} shows \co{pdeq_push_l()},
+which left-enqueues the specified
 element.
-Line~33 acquires the left-hand lock, and line~34 picks up the left-hand
+Line~\lnref{acq} acquires the left-hand lock,
+and line~\lnref{idx} picks up the left-hand
 index.
-Line~35 left-enqueues the specified element onto the double-ended queue
+Line~\lnref{enque} left-enqueues the specified element
+onto the double-ended queue
 indexed by the left-hand index.
-Line~36 then updates the left-hand index and line~37 releases the lock.
+Line~\lnref{update} then updates the left-hand index
+and line~\lnref{rel} releases the lock.
+\end{lineref}
 
 As noted earlier, the right-hand operations are completely analogous
 to their left-handed counterparts, so their analysis is left as an
@@ -500,72 +458,11 @@ the previous section, the compound implementation will build on
 a sequential implementation of a double-ended queue that uses
 neither locks nor atomic operations.
 
-\begin{listing*}[bp]
-{ \scriptsize
-\begin{verbbox}
-  1 struct cds_list_head *pdeq_pop_l(struct pdeq *d)
-  2 {
-  3   struct cds_list_head *e;
-  4 
-  5   spin_lock(&d->llock);
-  6   e = deq_pop_l(&d->ldeq);
-  7   if (e == NULL) {
-  8     spin_lock(&d->rlock);
-  9     e = deq_pop_l(&d->rdeq);
- 10     cds_list_splice(&d->rdeq.chain, &d->ldeq.chain);
- 11     CDS_INIT_LIST_HEAD(&d->rdeq.chain);
- 12     spin_unlock(&d->rlock);
- 13   }
- 14   spin_unlock(&d->llock);
- 15   return e;
- 16 }
- 17 
- 18 struct cds_list_head *pdeq_pop_r(struct pdeq *d)
- 19 {
- 20   struct cds_list_head *e;
- 21 
- 22   spin_lock(&d->rlock);
- 23   e = deq_pop_r(&d->rdeq);
- 24   if (e == NULL) {
- 25     spin_unlock(&d->rlock);
- 26     spin_lock(&d->llock);
- 27     spin_lock(&d->rlock);
- 28     e = deq_pop_r(&d->rdeq);
- 29     if (e == NULL) {
- 30       e = deq_pop_r(&d->ldeq);
- 31       cds_list_splice(&d->ldeq.chain, &d->rdeq.chain);
- 32       CDS_INIT_LIST_HEAD(&d->ldeq.chain);
- 33     }
- 34     spin_unlock(&d->llock);
- 35   }
- 36   spin_unlock(&d->rlock);
- 37   return e;
- 38 }
- 39 
- 40 void pdeq_push_l(struct cds_list_head *e, struct pdeq *d)
- 41 {
- 42   int i;
- 43 
- 44   spin_lock(&d->llock);
- 45   deq_push_l(e, &d->ldeq);
- 46   spin_unlock(&d->llock);
- 47 }
- 48 
- 49 void pdeq_push_r(struct cds_list_head *e, struct pdeq *d)
- 50 {
- 51   int i;
- 52 
- 53   spin_lock(&d->rlock);
- 54   deq_push_r(e, &d->rdeq);
- 55   spin_unlock(&d->rlock);
- 56 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{listing}[tbp]
+\input{CodeSamples/SMPdesign/locktdeq@pop_push.fcv}
 \caption{Compound Parallel Double-Ended Queue Implementation}
 \label{lst:SMPdesign:Compound Parallel Double-Ended Queue Implementation}
-\end{listing*}
+\end{listing}
 
 Listing~\ref{lst:SMPdesign:Compound Parallel Double-Ended Queue Implementation}
 shows the implementation.
@@ -583,50 +480,66 @@ and \co{pdeq_pop_r()} implementations separately.
 	(see Section~\ref{sec:SMPdesign:Dining Philosophers Problem}).
 } \QuickQuizEnd
 
-The \co{pdeq_pop_l()} implementation is shown on lines~1-16
+\begin{lineref}[ln:SMPdesign:locktdeq:pop_push:popl]
+The \co{pdeq_pop_l()} implementation is shown on
+lines~\lnref{b}-\lnref{e}
 of the figure.
-Line~5 acquires the left-hand lock, which line~14 releases.
-Line~6 attempts to left-dequeue an element from the left-hand underlying
-double-ended queue, and, if successful, skips lines~8-13 to simply
+Line~\lnref{acq:l} acquires the left-hand lock,
+which line~\lnref{rel:l} releases.
+Line~\lnref{deq:ll} attempts to left-dequeue an element
+from the left-hand underlying
+double-ended queue, and, if successful,
+skips lines~\lnref{acq:r}-\lnref{skip} to simply
 return this element.
-Otherwise, line~8 acquires the right-hand lock, line~9
+Otherwise, line~\lnref{acq:r} acquires the right-hand lock, line~\lnref{deq:lr}
 left-dequeues an element from the right-hand queue,
-and line~10 moves any remaining elements on the right-hand
-queue to the left-hand queue, line~11 initializes the right-hand queue,
-and line~12 releases the right-hand lock.
-The element, if any, that was dequeued on line~10 will be returned.
+and line~\lnref{move} moves any remaining elements on the right-hand
+queue to the left-hand queue, line~\lnref{init:r} initializes
+the right-hand queue,
+and line~\lnref{rel:r} releases the right-hand lock.
+The element, if any, that was dequeued on line~\lnref{deq:lr} will be returned.
+\end{lineref}
 
-The \co{pdeq_pop_r()} implementation is shown on lines~18-38
+\begin{lineref}[ln:SMPdesign:locktdeq:pop_push:popr]
+The \co{pdeq_pop_r()} implementation is shown on lines~\lnref{b}-\lnref{e}
 of the figure.
-As before, line~22 acquires the right-hand lock (and line~36
-releases it), and line~23 attempts to right-dequeue an element
-from the right-hand queue, and, if successful, skips lines~24-35
+As before, line~\lnref{acq:r1} acquires the right-hand lock
+(and line~\lnref{rel:r2}
+releases it), and line~\lnref{deq:rr1} attempts to right-dequeue an element
+from the right-hand queue, and, if successful,
+skips lines~\lnref{rel:r1}-\lnref{skip2}
 to simply return this element.
-However, if line~24 determines that there was no element to dequeue,
-line~25 releases the right-hand lock and lines~26-27 acquire both
+However, if line~\lnref{check1} determines that there was no element to dequeue,
+line~\lnref{rel:r1} releases the right-hand lock and
+lines~\lnref{acq:l}-\lnref{acq:r2} acquire both
 locks in the proper order.
-Line~28 then attempts to right-dequeue an element from the right-hand
-list again, and if line~29 determines that this second attempt has
-failed, line~30 right-dequeues an element from the left-hand queue
-(if there is one available), line~31 moves any remaining elements
-from the left-hand queue to the right-hand queue, and line~32
+Line~\lnref{deq:rr2} then attempts to right-dequeue an element
+from the right-hand
+list again, and if line~\lnref{check2} determines that this second attempt has
+failed, line~\lnref{deq:rl} right-dequeues an element from the left-hand queue
+(if there is one available), line~\lnref{move} moves any remaining elements
+from the left-hand queue to the right-hand queue, and line~\lnref{init:l}
 initializes the left-hand queue.
-Either way, line~34 releases the left-hand lock.
+Either way, line~\lnref{rel:l} releases the left-hand lock.
+\end{lineref}
 
 \QuickQuiz{}
 	Why is it necessary to retry the right-dequeue operation
-	on line~28 of
+	on line~\ref{ln:SMPdesign:locktdeq:pop_push:popr:deq:rr2} of
 	Listing~\ref{lst:SMPdesign:Compound Parallel Double-Ended Queue Implementation}?
 \QuickQuizAnswer{
+	\begin{lineref}[ln:SMPdesign:locktdeq:pop_push:popr]
 	This retry is necessary because some other thread might have
 	enqueued an element between the time that this thread dropped
-	\co{d->rlock} on line~25 and the time that it reacquired this
-	same lock on line~27.
+	\co{d->rlock} on line~\lnref{rel:r1} and the time that it reacquired this
+	same lock on line~\lnref{acq:r2}.
+	\end{lineref}
 } \QuickQuizEnd
 
 \QuickQuiz{}
 	Surely the left-hand lock must \emph{sometimes} be available!!!
-	So why is it necessary that line~25 of
+	So why is it necessary that
+        line~\ref{ln:SMPdesign:locktdeq:pop_push:popr:rel:r1} of
 	Listing~\ref{lst:SMPdesign:Compound Parallel Double-Ended Queue Implementation}
 	unconditionally release the right-hand lock?
 \QuickQuizAnswer{
@@ -638,13 +551,19 @@ Either way, line~34 releases the left-hand lock.
 	it is worthwhile) is left as an exercise for the reader.
 } \QuickQuizEnd
 
-The \co{pdeq_push_l()} implementation is shown on lines~40-47 of
+\begin{lineref}[ln:SMPdesign:locktdeq:pop_push:pushl]
+The \co{pdeq_push_l()} implementation is shown on
+lines~\lnref{b}-\lnref{e} of
 Listing~\ref{lst:SMPdesign:Compound Parallel Double-Ended Queue Implementation}.
-Line~44 acquires the left-hand spinlock, line~45 left-enqueues the
-element onto the left-hand queue, and finally line~46 releases
+Line~\lnref{acq:l} acquires the left-hand spinlock,
+line~\lnref{que:l} left-enqueues the
+element onto the left-hand queue, and finally line~\lnref{rel:l} releases
 the lock.
-The \co{pdeq_enqueue_r()} implementation (shown on lines~49-56)
+\end{lineref}
+\begin{lineref}[ln:SMPdesign:locktdeq:pop_push:pushr]
+The \co{pdeq_push_r()} implementation (shown on lines~\lnref{b}-\lnref{e})
 is quite similar.
+\end{lineref}
 
 \QuickQuiz{}
 	But in the case where data is flowing in only one direction,
-- 
2.7.4

[PATCH 4/7] SMPdesign: Employ new scheme for inline snippets

[Akira Yokosawa]

From 798445931ab13a7fab28d9a9271f719adf14c89a Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Thu, 1 Nov 2018 07:45:05 +0900
Subject: [PATCH 4/7] SMPdesign: Employ new scheme for inline snippets

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 SMPdesign/SMPdesign.tex | 357 +++++++++++++++++++++++-------------------------
 1 file changed, 170 insertions(+), 187 deletions(-)

diff --git a/SMPdesign/SMPdesign.tex b/SMPdesign/SMPdesign.tex
index 824de41..06a0c8c 100644
--- a/SMPdesign/SMPdesign.tex
+++ b/SMPdesign/SMPdesign.tex
@@ -120,36 +120,32 @@ In contrast, speedups due to sequential optimizations, for example,
 careful choice of data structure, can be arbitrarily large.
 
 \begin{listing}[tbhp]
-{ \scriptsize
-\begin{verbbox}
-  1 struct hash_table
-  2 {
-  3   long nbuckets;
-  4   struct node **buckets;
-  5 };
-  6
-  7 typedef struct node {
-  8   unsigned long key;
-  9   struct node *next;
- 10 } node_t;
- 11
- 12 int hash_search(struct hash_table *h, long key)
- 13 {
- 14   struct node *cur;
- 15
- 16   cur = h->buckets[key % h->nbuckets];
- 17   while (cur != NULL) {
- 18     if (cur->key >= key) {
- 19       return (cur->key == key);
- 20     }
- 21     cur = cur->next;
- 22   }
- 23   return 0;
- 24 }
-\end{verbbox}
+\begin{VerbatimL}[commandchars=\\\[\]]
+struct hash_table
+{
+	long nbuckets;
+	struct node **buckets;
+};
+
+typedef struct node {
+	unsigned long key;
+	struct node *next;
+} node_t;
+
+int hash_search(struct hash_table *h, long key)
+{
+	struct node *cur;
+
+	cur = h->buckets[key % h->nbuckets];
+	while (cur != NULL) {
+		if (cur->key >= key) {
+			return (cur->key == key);
+		}
+		cur = cur->next;
+	}
+	return 0;
 }
-\centering
-\theverbbox
+\end{VerbatimL}
 \caption{Sequential-Program Hash Table Search}
 \label{lst:SMPdesign:Sequential-Program Hash Table Search}
 \end{listing}
@@ -197,43 +193,39 @@ has now become three statements due to the need to release the
 lock before returning.
 
 \begin{listing}[tbhp]
-{ \scriptsize
-\begin{verbbox}
-  1 spinlock_t hash_lock;
-  2
-  3 struct hash_table
-  4 {
-  5   long nbuckets;
-  6   struct node **buckets;
-  7 };
-  8
-  9 typedef struct node {
- 10   unsigned long key;
- 11   struct node *next;
- 12 } node_t;
- 13
- 14 int hash_search(struct hash_table *h, long key)
- 15 {
- 16   struct node *cur;
- 17   int retval;
- 18
- 19   spin_lock(&hash_lock);
- 20   cur = h->buckets[key % h->nbuckets];
- 21   while (cur != NULL) {
- 22     if (cur->key >= key) {
- 23       retval = (cur->key == key);
- 24       spin_unlock(&hash_lock);
- 25       return retval;
- 26     }
- 27     cur = cur->next;
- 28   }
- 29   spin_unlock(&hash_lock);
- 30   return 0;
- 31 }
-\end{verbbox}
+\begin{VerbatimL}[commandchars=\\\[\]]
+spinlock_t hash_lock;
+
+struct hash_table
+{
+	long nbuckets;
+	struct node **buckets;
+};
+
+typedef struct node {
+	unsigned long key;
+	struct node *next;
+} node_t;
+
+int hash_search(struct hash_table *h, long key)
+{
+	struct node *cur;
+	int retval;
+
+	spin_lock(&hash_lock);
+	cur = h->buckets[key % h->nbuckets];
+	while (cur != NULL) {
+		if (cur->key >= key) {
+			retval = (cur->key == key);
+			spin_unlock(&hash_lock);
+			return retval;
+		}
+		cur = cur->next;
+	}
+	spin_unlock(&hash_lock);
+	return 0;
 }
-\centering
-\theverbbox
+\end{VerbatimL}
 \caption{Code-Locking Hash Table Search}
 \label{lst:SMPdesign:Code-Locking Hash Table Search}
 \end{listing}
@@ -292,48 +284,44 @@ The increased scalability again results in a slight increase in complexity
 in the form of an additional data structure, the \co{struct bucket}.
 
 \begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
-  1 struct hash_table
-  2 {
-  3   long nbuckets;
-  4   struct bucket **buckets;
-  5 };
-  6
-  7 struct bucket {
-  8   spinlock_t bucket_lock;
-  9   node_t *list_head;
- 10 };
- 11
- 12 typedef struct node {
- 13   unsigned long key;
- 14   struct node *next;
- 15 } node_t;
- 16
- 17 int hash_search(struct hash_table *h, long key)
- 18 {
- 19   struct bucket *bp;
- 20   struct node *cur;
- 21   int retval;
- 22
- 23   bp = h->buckets[key % h->nbuckets];
- 24   spin_lock(&bp->bucket_lock);
- 25   cur = bp->list_head;
- 26   while (cur != NULL) {
- 27     if (cur->key >= key) {
- 28       retval = (cur->key == key);
- 29       spin_unlock(&bp->bucket_lock);
- 30       return retval;
- 31     }
- 32     cur = cur->next;
- 33   }
- 34   spin_unlock(&bp->bucket_lock);
- 35   return 0;
- 36 }
-\end{verbbox}
+\begin{VerbatimL}
+struct hash_table
+{
+	long nbuckets;
+	struct bucket **buckets;
+};
+
+struct bucket {
+	spinlock_t bucket_lock;
+	node_t *list_head;
+};
+
+typedef struct node {
+	unsigned long key;
+	struct node *next;
+} node_t;
+
+int hash_search(struct hash_table *h, long key)
+{
+	struct bucket *bp;
+	struct node *cur;
+	int retval;
+
+	bp = h->buckets[key % h->nbuckets];
+	spin_lock(&bp->bucket_lock);
+	cur = bp->list_head;
+	while (cur != NULL) {
+		if (cur->key >= key) {
+			retval = (cur->key == key);
+			spin_unlock(&bp->bucket_lock);
+			return retval;
+		}
+		cur = cur->next;
+	}
+	spin_unlock(&bp->bucket_lock);
+	return 0;
 }
-\centering
-\theverbbox
+\end{VerbatimL}
 \caption{Data-Locking Hash Table Search}
 \label{lst:SMPdesign:Data-Locking Hash Table Search}
 \end{listing}
@@ -805,43 +793,39 @@ Listing~\ref{lst:SMPdesign:Reader-Writer-Locking Hash Table Search}
 shows how the hash search might be implemented using reader-writer locking.
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 rwlock_t hash_lock;
-  2
-  3 struct hash_table
-  4 {
-  5   long nbuckets;
-  6   struct node **buckets;
-  7 };
-  8
-  9 typedef struct node {
- 10   unsigned long key;
- 11   struct node *next;
- 12 } node_t;
- 13
- 14 int hash_search(struct hash_table *h, long key)
- 15 {
- 16   struct node *cur;
- 17   int retval;
- 18
- 19   read_lock(&hash_lock);
- 20   cur = h->buckets[key % h->nbuckets];
- 21   while (cur != NULL) {
- 22     if (cur->key >= key) {
- 23       retval = (cur->key == key);
- 24       read_unlock(&hash_lock);
- 25       return retval;
- 26     }
- 27     cur = cur->next;
- 28   }
- 29   read_unlock(&hash_lock);
- 30   return 0;
- 31 }
-\end{verbbox}
+\begin{VerbatimL}[commandchars=\\\[\]]
+rwlock_t hash_lock;
+
+struct hash_table
+{
+	long nbuckets;
+	struct node **buckets;
+};
+
+typedef struct node {
+	unsigned long key;
+	struct node *next;
+} node_t;
+
+int hash_search(struct hash_table *h, long key)
+{
+	struct node *cur;
+	int retval;
+
+	read_lock(&hash_lock);
+	cur = h->buckets[key % h->nbuckets];
+	while (cur != NULL) {
+		if (cur->key >= key) {
+			retval = (cur->key == key);
+			read_unlock(&hash_lock);
+			return retval;
+		}
+		cur = cur->next;
+	}
+	read_unlock(&hash_lock);
+	return 0;
 }
-\centering
-\theverbbox
+\end{VerbatimL}
 \caption{Reader-Writer-Locking Hash Table Search}
 \label{lst:SMPdesign:Reader-Writer-Locking Hash Table Search}
 \end{listing}
@@ -868,51 +852,49 @@ In this case, the simpler data-locking approach would be simpler
 and likely perform better.
 
 \begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
-  1 struct hash_table
-  2 {
-  3   long nbuckets;
-  4   struct bucket **buckets;
-  5 };
-  6
-  7 struct bucket {
-  8   spinlock_t bucket_lock;
-  9   node_t *list_head;
- 10 };
- 11
- 12 typedef struct node {
- 13   spinlock_t node_lock;
- 14   unsigned long key;
- 15   struct node *next;
- 16 } node_t;
- 17
- 18 int hash_search(struct hash_table *h, long key)
- 19 {
- 20   struct bucket *bp;
- 21   struct node *cur;
- 22   int retval;
- 23
- 24   bp = h->buckets[key % h->nbuckets];
- 25   spin_lock(&bp->bucket_lock);
- 26   cur = bp->list_head;
- 27   while (cur != NULL) {
- 28     if (cur->key >= key) {
- 29       spin_lock(&cur->node_lock);
- 30       spin_unlock(&bp->bucket_lock);
- 31       retval = (cur->key == key);
- 32       spin_unlock(&cur->node_lock);
- 33       return retval;
- 34     }
- 35     cur = cur->next;
- 36   }
- 37   spin_unlock(&bp->bucket_lock);
- 38   return 0;
- 39 }
-\end{verbbox}
+\begin{linelabel}[ln:SMPdesign:Hierarchical-Locking Hash Table Search]
+\begin{VerbatimL}[commandchars=\\\[\]]
+struct hash_table
+{
+	long nbuckets;
+	struct bucket **buckets;
+};
+
+struct bucket {
+	spinlock_t bucket_lock;
+	node_t *list_head;
+};
+
+typedef struct node {
+	spinlock_t node_lock;
+	unsigned long key;
+	struct node *next;
+} node_t;
+
+int hash_search(struct hash_table *h, long key)
+{
+	struct bucket *bp;
+	struct node *cur;
+	int retval;
+
+	bp = h->buckets[key % h->nbuckets];
+	spin_lock(&bp->bucket_lock);
+	cur = bp->list_head;
+	while (cur != NULL) {
+		if (cur->key >= key) {
+			spin_lock(&cur->node_lock);
+			spin_unlock(&bp->bucket_lock);
+			retval = (cur->key == key);\lnlbl[retval]
+			spin_unlock(&cur->node_lock);
+			return retval;
+		}
+		cur = cur->next;
+	}
+	spin_unlock(&bp->bucket_lock);
+	return 0;
 }
-\centering
-\theverbbox
+\end{VerbatimL}
+\end{linelabel}
 \caption{Hierarchical-Locking Hash Table Search}
 \label{lst:SMPdesign:Hierarchical-Locking Hash Table Search}
 \end{listing}
@@ -920,7 +902,8 @@ and likely perform better.
 \QuickQuiz{}
 	In what situation would hierarchical locking work well?
 \QuickQuizAnswer{
-	If the comparison on line~31 of
+	If the comparison on
+        line~\ref{ln:SMPdesign:Hierarchical-Locking Hash Table Search:retval} of
 	Listing~\ref{lst:SMPdesign:Hierarchical-Locking Hash Table Search}
 	were replaced by a much heavier-weight operation,
 	then releasing \co{bp->bucket_lock} \emph{might} reduce lock
-- 
2.7.4

[PATCH 5/7] SMPdesign: Employ new scheme for snippets from smpalloc.c

[Akira Yokosawa]

From b5efb413687874a667443943069c021e6c827d7b Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Fri, 2 Nov 2018 00:22:35 +0900
Subject: [PATCH 5/7] SMPdesign: Employ new scheme for snippets from smpalloc.c

NOTE: Names "percpumem" and "percpumempool" are replaced with
"pertheardmem" and "perthreadmempool" to respect those used in
CodeSamples/SMPdesign/smpalloc.c. Wording of "per-CPU" around them
in the text is also modified to "per-thread".

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 CodeSamples/SMPdesign/smpalloc.c |  57 ++++++++++--------
 SMPdesign/SMPdesign.tex          | 122 ++++++++++-----------------------------
 2 files changed, 63 insertions(+), 116 deletions(-)

diff --git a/CodeSamples/SMPdesign/smpalloc.c b/CodeSamples/SMPdesign/smpalloc.c
index 149e226..72262d6 100644
--- a/CodeSamples/SMPdesign/smpalloc.c
+++ b/CodeSamples/SMPdesign/smpalloc.c
@@ -21,13 +21,14 @@
 
 #include "../api.h"
 
+//\begin{snippet}[labelbase=ln:SMPdesign:smpalloc:data_struct,commandchars=\\\@\$]
 #define TARGET_POOL_SIZE 3
 #define GLOBAL_POOL_SIZE 40
 
-struct memblock {
-	char *bytes[CACHE_LINE_SIZE];
-} memblocks[GLOBAL_POOL_SIZE];
-
+struct memblock {				//\fcvexclude
+	char *bytes[CACHE_LINE_SIZE];		//\fcvexclude
+} memblocks[GLOBAL_POOL_SIZE];			//\fcvexclude
+						//\fcvexclude
 struct globalmempool {
 	spinlock_t mutex;
 	int cur;
@@ -40,46 +41,54 @@ struct perthreadmempool {
 };
 
 DEFINE_PER_THREAD(struct perthreadmempool, perthreadmem);
+//\end{snippet}
 
+//\begin{snippet}[labelbase=ln:SMPdesign:smpalloc:alloc,commandchars=\\\@\$]
 struct memblock *memblock_alloc(void)
 {
 	int i;
 	struct memblock *p;
-	struct perthreadmempool *pcpp = &__get_thread_var(perthreadmem);
+	struct perthreadmempool *pcpp;
 
-	if (pcpp->cur < 0) {
-		spin_lock(&globalmem.mutex);
-		for (i = 0; i < TARGET_POOL_SIZE && globalmem.cur >= 0; i++) {
+	pcpp = &__get_thread_var(perthreadmem);			//\lnlbl{pick}
+	if (pcpp->cur < 0) {					//\lnlbl{chk:empty}
+		spin_lock(&globalmem.mutex);			//\lnlbl{ack}
+		for (i = 0; i < TARGET_POOL_SIZE &&		//\lnlbl{loop:b}
+		            globalmem.cur >= 0; i++) {
 			pcpp->pool[i] = globalmem.pool[globalmem.cur];
 			globalmem.pool[globalmem.cur--] = NULL;
-		}
-		pcpp->cur = i - 1;
-		spin_unlock(&globalmem.mutex);
+		}						//\lnlbl{loop:e}
+		pcpp->cur = i - 1;				//\lnlbl{set}
+		spin_unlock(&globalmem.mutex);			//\lnlbl{rel}
 	}
-	if (pcpp->cur >= 0) {
-		p = pcpp->pool[pcpp->cur];
+	if (pcpp->cur >= 0) {					//\lnlbl{chk:notempty}
+		p = pcpp->pool[pcpp->cur];			//\lnlbl{rem:b}
 		pcpp->pool[pcpp->cur--] = NULL;
-		return p;
+		return p;					//\lnlbl{rem:e}
 	}
-	return NULL;
+	return NULL;						//\lnlbl{ret:NULL}
 }
+//\end{snippet}
 
+//\begin{snippet}[labelbase=ln:SMPdesign:smpalloc:free,commandchars=\\\@\$]
 void memblock_free(struct memblock *p)
 {
 	int i;
-	struct perthreadmempool *pcpp = &__get_thread_var(perthreadmem);
+	struct perthreadmempool *pcpp;
 
-	if (pcpp->cur >= 2 * TARGET_POOL_SIZE - 1) {
-		spin_lock(&globalmem.mutex);
-		for (i = pcpp->cur; i >= TARGET_POOL_SIZE; i--) {
+	pcpp = &__get_thread_var(perthreadmem);			//\lnlbl{get}
+	if (pcpp->cur >= 2 * TARGET_POOL_SIZE - 1) {		//\lnlbl{chk:full}
+		spin_lock(&globalmem.mutex);			//\lnlbl{acq}
+		for (i = pcpp->cur; i >= TARGET_POOL_SIZE; i--) {//\lnlbl{loop:b}
 			globalmem.pool[++globalmem.cur] = pcpp->pool[i];
 			pcpp->pool[i] = NULL;
-		}
-		pcpp->cur = i;
-		spin_unlock(&globalmem.mutex);
-	}
-	pcpp->pool[++pcpp->cur] = p;
+		}						//\lnlbl{loop:e}
+		pcpp->cur = i;					//\lnlbl{set}
+		spin_unlock(&globalmem.mutex);			//\lnlbl{rel}
+	}							//\lnlbl{empty:e}
+	pcpp->pool[++pcpp->cur] = p;				//\lnlbl{place}
 }
+//\end{snippet}
 
 void initpools(void)
 {
diff --git a/SMPdesign/SMPdesign.tex b/SMPdesign/SMPdesign.tex
index 06a0c8c..3019ef4 100644
--- a/SMPdesign/SMPdesign.tex
+++ b/SMPdesign/SMPdesign.tex
@@ -971,8 +971,8 @@ caches are shown in
 Listing~\ref{lst:SMPdesign:Allocator-Cache Data Structures}.
 The ``Global Pool'' of Figure~\ref{fig:SMPdesign:Allocator Cache Schematic}
 is implemented by \co{globalmem} of type \co{struct globalmempool},
-and the two CPU pools by the per-CPU variable \co{percpumem} of
-type \co{struct percpumempool}.
+and the two CPU pools by the per-thread variable \co{perthreadmem} of
+type \co{struct perthreadmempool}.
 Both of these data structures have arrays of pointers to blocks
 in their \co{pool} fields, which are filled from index zero upwards.
 Thus, if \co{globalmem.pool[3]} is \co{NULL}, then the remainder of
@@ -988,27 +988,7 @@ must be empty.\footnote{
 	a feel for its operation.}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 #define TARGET_POOL_SIZE 3
-  2 #define GLOBAL_POOL_SIZE 40
-  3
-  4 struct globalmempool {
-  5   spinlock_t mutex;
-  6   int cur;
-  7   struct memblock *pool[GLOBAL_POOL_SIZE];
-  8 } globalmem;
-  9
- 10 struct percpumempool {
- 11   int cur;
- 12   struct memblock *pool[2 * TARGET_POOL_SIZE];
- 13 };
- 14
- 15 DEFINE_PER_THREAD(struct percpumempool, percpumem);
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/SMPdesign/smpalloc@data_struct.fcv}
 \caption{Allocator-Cache Data Structures}
 \label{lst:SMPdesign:Allocator-Cache Data Structures}
 \end{listing}
@@ -1033,97 +1013,55 @@ smaller than the number of non-\co{NULL} pointers.
 
 \subsubsection{Allocation Function}
 
+\begin{lineref}[ln:SMPdesign:smpalloc:alloc]
 The allocation function \co{memblock_alloc()} may be seen in
 Listing~\ref{lst:SMPdesign:Allocator-Cache Allocator Function}.
-Line~7 picks up the current thread's per-thread pool,
+Line~\lnref{pick} picks up the current thread's per-thread pool,
 and line~8 check to see if it is empty.
 
-If so, lines~9-16 attempt to refill it from the global pool
-under the spinlock acquired on line~9 and released on line~16.
-Lines~10-14 move blocks from the global to the per-thread pool until
+If so, lines~\lnref{ack}-\lnref{rel} attempt to refill it
+from the global pool
+under the spinlock acquired on line~\lnref{ack} and released on line~\lnref{rel}.
+Lines~\lnref{loop:b}-\lnref{loop:e} move blocks from the global
+to the per-thread pool until
 either the local pool reaches its target size (half full) or
-the global pool is exhausted, and line~15 sets the per-thread pool's
+the global pool is exhausted, and line~\lnref{set} sets the per-thread pool's
 count to the proper value.
 
-In either case, line~18 checks for the per-thread pool still being
-empty, and if not, lines~19-21 remove a block and return it.
-Otherwise, line~23 tells the sad tale of memory exhaustion.
+In either case, line~\lnref{chk:notempty} checks for the per-thread
+pool still being
+empty, and if not, lines~\lnref{rem:b}-\lnref{rem:e} remove a block and return it.
+Otherwise, line~\lnref{ret:NULL} tells the sad tale of memory exhaustion.
+\end{lineref}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 struct memblock *memblock_alloc(void)
-  2 {
-  3   int i;
-  4   struct memblock *p;
-  5   struct percpumempool *pcpp;
-  6
-  7   pcpp = &__get_thread_var(percpumem);
-  8   if (pcpp->cur < 0) {
-  9     spin_lock(&globalmem.mutex);
- 10     for (i = 0; i < TARGET_POOL_SIZE &&
- 11                 globalmem.cur >= 0; i++) {
- 12       pcpp->pool[i] = globalmem.pool[globalmem.cur];
- 13       globalmem.pool[globalmem.cur--] = NULL;
- 14     }
- 15     pcpp->cur = i - 1;
- 16     spin_unlock(&globalmem.mutex);
- 17   }
- 18   if (pcpp->cur >= 0) {
- 19     p = pcpp->pool[pcpp->cur];
- 20     pcpp->pool[pcpp->cur--] = NULL;
- 21     return p;
- 22   }
- 23   return NULL;
- 24 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/SMPdesign/smpalloc@alloc.fcv}
 \caption{Allocator-Cache Allocator Function}
 \label{lst:SMPdesign:Allocator-Cache Allocator Function}
 \end{listing}
 
 \subsubsection{Free Function}
 
+\begin{lineref}[ln:SMPdesign:smpalloc:free]
 Listing~\ref{lst:SMPdesign:Allocator-Cache Free Function} shows
 the memory-block free function.
-Line~6 gets a pointer to this thread's pool, and
-line~7 checks to see if this per-thread pool is full.
-
-If so, lines~8-15 empty half of the per-thread pool into the global pool,
-with lines~8 and~14 acquiring and releasing the spinlock.
-Lines~9-12 implement the loop moving blocks from the local to the
-global pool, and line~13 sets the per-thread pool's count to the proper
+Line~\lnref{get} gets a pointer to this thread's pool, and
+line~\lnref{chk:full} checks to see if this per-thread pool is full.
+
+If so, lines~\lnref{acq}-\lnref{empty:e} empty half of the per-thread pool
+into the global pool,
+with lines~\lnref{acq} and~\lnref{rel} acquiring and releasing the spinlock.
+Lines~\lnref{loop:b}-\lnref{loop:e} implement the loop moving blocks
+from the local to the
+global pool, and line~\lnref{set} sets the per-thread pool's count to the proper
 value.
 
-In either case, line~16 then places the newly freed block into the
+In either case, line~\lnref{place} then places the newly freed block into the
 per-thread pool.
+\end{lineref}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 void memblock_free(struct memblock *p)
-  2 {
-  3   int i;
-  4   struct percpumempool *pcpp;
-  5
-  6   pcpp = &__get_thread_var(percpumem);
-  7   if (pcpp->cur >= 2 * TARGET_POOL_SIZE - 1) {
-  8     spin_lock(&globalmem.mutex);
-  9     for (i = pcpp->cur; i >= TARGET_POOL_SIZE; i--) {
- 10       globalmem.pool[++globalmem.cur] = pcpp->pool[i];
- 11       pcpp->pool[i] = NULL;
- 12     }
- 13     pcpp->cur = i;
- 14     spin_unlock(&globalmem.mutex);
- 15   }
- 16   pcpp->pool[++pcpp->cur] = p;
- 17 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/SMPdesign/smpalloc@free.fcv}
 \caption{Allocator-Cache Free Function}
 \label{lst:SMPdesign:Allocator-Cache Free Function}
 \end{listing}
-- 
2.7.4

[PATCH 6/7] SMPdesign/beyond: Employ new scheme for inline pseudocode snippets

[Akira Yokosawa]

From b36ad7a4fc1e62b276bb607a6a654e7efa5fec38 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sat, 3 Nov 2018 00:13:28 +0900
Subject: [PATCH 6/7] SMPdesign/beyond: Employ new scheme for inline pseudocode snippets

Also mention Listing~\ref{lst:SMPdesign:SEQ Pseudocode} as pseudocode,
And replace remaining ACCESS_ONCE()s with READ_ONCE()s.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 SMPdesign/beyond.tex | 319 +++++++++++++++++++++++++++------------------------
 1 file changed, 168 insertions(+), 151 deletions(-)

diff --git a/SMPdesign/beyond.tex b/SMPdesign/beyond.tex
index 88e2b31..5997f86 100644
--- a/SMPdesign/beyond.tex
+++ b/SMPdesign/beyond.tex
@@ -54,112 +54,125 @@ presents future directions and concluding remarks.
 \label{sec:SMPdesign:Work-Queue Parallel Maze Solver}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 int maze_solve(maze *mp, cell sc, cell ec)
-  2 {
-  3   cell c = sc;
-  4   cell n;
-  5   int vi = 0;
-  6 
-  7   maze_try_visit_cell(mp, c, c, &n, 1);
-  8   for (;;) {
-  9     while (!maze_find_any_next_cell(mp, c, &n)) {
- 10       if (++vi >= mp->vi)
- 11         return 0;
- 12       c = mp->visited[vi].c;
- 13     }
- 14     do {
- 15       if (n == ec) {
- 16         return 1;
- 17       }
- 18       c = n;
- 19     } while (maze_find_any_next_cell(mp, c, &n));
- 20     c = mp->visited[vi].c;
- 21   }
- 22 }
-\end{verbbox}
+\begin{linelabel}[ln:SMPdesign:SEQ Pseudocode]
+\begin{VerbatimL}[commandchars=\\\@\$]
+int maze_solve(maze *mp, cell sc, cell ec)
+{
+	cell c = sc;
+	cell n;
+	int vi = 0;
+
+	maze_try_visit_cell(mp, c, c, &n, 1);		\lnlbl@initcell$
+	for (;;) {					\lnlbl@loop:b$
+		while (!maze_find_any_next_cell(mp, c, &n)) {\lnlbl@loop2:b$
+			if (++vi >= mp->vi)
+				return 0;
+			c = mp->visited[vi].c;
+		}					\lnlbl@loop2:e$
+		do {					\lnlbl@loop3:b$
+			if (n == ec) {
+				return 1;
+			}
+			c = n;
+		} while (maze_find_any_next_cell(mp, c, &n));\lnlbl@loop3:e$
+		c = mp->visited[vi].c;			\lnlbl@finalize$
+	}						\lnlbl@loop:e$
 }
-\centering
-\theverbbox
+\end{VerbatimL}
+\end{linelabel}
 \caption{SEQ Pseudocode}
 \label{lst:SMPdesign:SEQ Pseudocode}
 \end{listing}
 
 PWQ is based on SEQ, which is shown in
 Listing~\ref{lst:SMPdesign:SEQ Pseudocode}
-(\path{maze_seq.c}).
+(pseudocode for \path{maze_seq.c}).
 The maze is represented by a 2D array of cells and
 a linear-array-based work queue named \co{->visited}.
 
-Line~7 visits the initial cell, and each iteration of the loop spanning
-lines~8-21 traverses passages headed by one cell.
-The loop spanning lines~9-13 scans the \co{->visited[]} array for a
+\begin{lineref}[ln:SMPdesign:SEQ Pseudocode]
+Line~\lnref{initcell} visits the initial cell, and each iteration of the loop spanning
+lines~\lnref{loop:b}-\lnref{loop:e} traverses passages headed by one cell.
+The loop spanning
+lines~\lnref{loop2:b}-\lnref{loop2:e} scans the \co{->visited[]} array for a
 visited cell with an unvisited neighbor, and the loop spanning
-lines~14-19 traverses one fork of the submaze headed by that neighbor.
-Line~20 initializes for the next pass through the outer loop.
+lines~\lnref{loop3:b}-\lnref{loop3:e} traverses one fork of the submaze
+headed by that neighbor.
+Line~\lnref{finalize} initializes for the next pass through the outer loop.
+\end{lineref}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 int maze_try_visit_cell(struct maze *mp, cell c, cell t,
-  2                         cell *n, int d)
-  3 {
-  4   if (!maze_cells_connected(mp, c, t) ||
-  5       (*celladdr(mp, t) & VISITED))
-  6     return 0;
-  7   *n = t;
-  8   mp->visited[mp->vi] = t;
-  9   mp->vi++;
- 10   *celladdr(mp, t) |= VISITED | d;
- 11   return 1;
- 12 }
- 13 
- 14 int maze_find_any_next_cell(struct maze *mp, cell c,
- 15                             cell *n)
- 16 {
- 17   int d = (*celladdr(mp, c) & DISTANCE) + 1;
- 18 
- 19   if (maze_try_visit_cell(mp, c, prevcol(c), n, d))
- 20     return 1;
- 21   if (maze_try_visit_cell(mp, c, nextcol(c), n, d))
- 22     return 1;
- 23   if (maze_try_visit_cell(mp, c, prevrow(c), n, d))
- 24     return 1;
- 25   if (maze_try_visit_cell(mp, c, nextrow(c), n, d))
- 26     return 1;
- 27   return 0;
- 28 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{linelabel}[ln:SMPdesign:SEQ Helper Pseudocode]
+\begin{VerbatimL}[commandchars=\\\@\$]
+int maze_try_visit_cell(struct maze *mp, cell c, cell t, \lnlbl@try:b$
+                        cell *n, int d)
+{
+	if (!maze_cells_connected(mp, c, t) ||	\lnlbl@try:chk:adj$
+	    (*celladdr(mp, t) & VISITED))	\lnlbl@try:chk:not:visited$
+		return 0;			\lnlbl@try:ret:failure$
+	*n = t;					\lnlbl@try:nextcell$
+	mp->visited[mp->vi] = t;		\lnlbl@try:recordnext$
+	mp->vi++;				\lnlbl@try:next:visited$
+	*celladdr(mp, t) |= VISITED | d;	\lnlbl@try:mark:visited$
+	return 1;				\lnlbl@try:ret:success$
+}						\lnlbl@try:e$
+
+int maze_find_any_next_cell(struct maze *mp, cell c, \lnlbl@find:b$
+                            cell *n)
+{
+	int d = (*celladdr(mp, c) & DISTANCE) + 1;	\lnlbl@find:curplus1$
+
+	if (maze_try_visit_cell(mp, c, prevcol(c), n, d))\lnlbl@find:chk:prevcol$
+		return 1;				\lnlbl@find:ret:prevcol$
+	if (maze_try_visit_cell(mp, c, nextcol(c), n, d))\lnlbl@find:chk:nextcol$
+		return 1;				\lnlbl@find:ret:nextcol$
+	if (maze_try_visit_cell(mp, c, prevrow(c), n, d))\lnlbl@find:chk:prevrow$
+		return 1;				\lnlbl@find:ret:prevrow$
+	if (maze_try_visit_cell(mp, c, nextrow(c), n, d))\lnlbl@find:chk:nextrow$
+		return 1;				\lnlbl@find:ret:nextrow$
+	return 0;					\lnlbl@find:ret:false$
+}							\lnlbl@find:e$
+\end{VerbatimL}
+\end{linelabel}
 \caption{SEQ Helper Pseudocode}
 \label{lst:SMPdesign:SEQ Helper Pseudocode}
 \end{listing}
 
-The pseudocode for \co{maze_try_visit_cell()} is shown on lines~1-12
+\begin{lineref}[ln:SMPdesign:SEQ Helper Pseudocode:try]
+The pseudocode for \co{maze_try_visit_cell()} is shown on
+lines~\lnref{b}-\lnref{e}
 of Listing~\ref{lst:SMPdesign:SEQ Helper Pseudocode}
 (\path{maze.c}).
-Line~4 checks to see if cells \co{c} and \co{t} are adjacent and connected,
-while line~5 checks to see if cell \co{t} has not yet been visited.
+Line~\lnref{chk:adj} checks to see if cells \co{c} and \co{t} are
+adjacent and connected,
+while line~\lnref{chk:not:visited} checks to see if cell \co{t} has
+not yet been visited.
 The \co{celladdr()} function returns the address of the specified cell.
-If either check fails, line~6 returns failure.
-Line~7 indicates the next cell, line~8 records this cell in the next
-slot of the \co{->visited[]} array, line~9 indicates that this slot
-is now full, and line~10 marks this cell as visited and also records
-the distance from the maze start.  Line~11 then returns success.
-
-The pseudocode for \co{maze_find_any_next_cell()} is shown on lines~14-28
+If either check fails, line~\lnref{ret:failure} returns failure.
+Line~\lnref{nextcell} indicates the next cell,
+line~\lnref{recordnext} records this cell in the next
+slot of the \co{->visited[]} array,
+line~\lnref{next:visited} indicates that this slot
+is now full, and line~\lnref{mark:visited} marks this cell as visited and also records
+the distance from the maze start.  Line~\lnref{ret:success} then returns success.
+\end{lineref}
+
+\begin{lineref}[ln:SMPdesign:SEQ Helper Pseudocode:find]
+The pseudocode for \co{maze_find_any_next_cell()} is shown on
+lines~\lnref{b}-\lnref{e}
 of Listing~\ref{lst:SMPdesign:SEQ Helper Pseudocode}
 (\path{maze.c}).
-Line~17 picks up the current cell's distance plus 1,
-while lines~19, 21, 23, and~25
-check the cell in each direction, and lines~20, 22, 24, and~26
+Line~\lnref{curplus1} picks up the current cell's distance plus 1,
+while lines~\lnref{chk:prevcol}, \lnref{chk:nextcol}, \lnref{chk:prevrow},
+and~\lnref{chk:nextrow}
+check the cell in each direction, and
+lines~\lnref{ret:prevcol}, \lnref{ret:nextcol}, \lnref{ret:prevrow},
+and~\lnref{ret:nextrow}
 return true if the corresponding cell is a candidate next cell.
 The \co{prevcol()}, \co{nextcol()}, \co{prevrow()}, and \co{nextrow()}
 each do the specified array-index-conversion operation.
-If none of the cells is a candidate, line~27 returns false.
+If none of the cells is a candidate, line~\lnref{ret:false} returns false.
+\end{lineref}
 
 \begin{figure}[tb]
 \centering
@@ -228,60 +241,59 @@ at opposite ends of the solution path, and takes a brief look at the
 performance and scalability consequences.
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 int maze_solve_child(maze *mp, cell *visited, cell sc)
-  2 {
-  3   cell c;
-  4   cell n;
-  5   int vi = 0;
-  6 
-  7   myvisited = visited; myvi = &vi;
-  8   c = visited[vi];
-  9   do {
- 10     while (!maze_find_any_next_cell(mp, c, &n)) {
- 11       if (visited[++vi].row < 0)
- 12         return 0;
- 13       if (ACCESS_ONCE(mp->done))
- 14         return 1;
- 15       c = visited[vi];
- 16     }
- 17     do {
- 18       if (ACCESS_ONCE(mp->done))
- 19         return 1;
- 20       c = n;
- 21     } while (maze_find_any_next_cell(mp, c, &n));
- 22     c = visited[vi];
- 23   } while (!ACCESS_ONCE(mp->done));
- 24   return 1;
- 25 }
-\end{verbbox}
+\begin{linelabel}[ln:SMPdesign:Partitioned Parallel Solver Pseudocode]
+\begin{VerbatimL}[commandchars=\\\@\$]
+int maze_solve_child(maze *mp, cell *visited, cell sc)	\lnlbl@b$
+{
+	cell c;
+	cell n;
+	int vi = 0;
+
+	myvisited = visited; myvi = &vi;		\lnlbl@store:ptr$
+	c = visited[vi];				\lnlbl@retrieve$
+	do {
+		while (!maze_find_any_next_cell(mp, c, &n)) {
+			if (visited[++vi].row < 0)
+				return 0;
+			if (READ_ONCE(mp->done))	\lnlbl@chk:done1$
+				return 1;
+			c = visited[vi];
+		}
+		do {
+			if (READ_ONCE(mp->done))	\lnlbl@chk:done2$
+				return 1;
+			c = n;
+		} while (maze_find_any_next_cell(mp, c, &n));
+		c = visited[vi];
+	} while (!READ_ONCE(mp->done));		\lnlbl@chk:done3$
+	return 1;
 }
-\centering
-\theverbbox
+\end{VerbatimL}
+\end{linelabel}
 \caption{Partitioned Parallel Solver Pseudocode}
 \label{lst:SMPdesign:Partitioned Parallel Solver Pseudocode}
 \end{listing}
 
+\begin{lineref}[ln:SMPdesign:Partitioned Parallel Solver Pseudocode]
 The partitioned parallel algorithm (PART), shown in
 Listing~\ref{lst:SMPdesign:Partitioned Parallel Solver Pseudocode}
 (\path{maze_part.c}),
 is similar to SEQ, but has a few important differences.
 First, each child thread has its own \co{visited} array, passed in by
-the parent as shown on line~1,
+the parent as shown on line~\lnref{b},
 which must be initialized to all [$-1$, $-1$].
-Line~7 stores a pointer to this array into the per-thread variable
+Line~\lnref{store:ptr} stores a pointer to this array into the per-thread variable
 \co{myvisited} to allow access by helper functions, and similarly stores
 a pointer to the local visit index.
 Second, the parent visits the first cell on each child's behalf,
-which the child retrieves on line~8.
+which the child retrieves on line~\lnref{retrieve}.
 Third, the maze is solved as soon as one child locates a cell that has
 been visited by the other child.
 When \co{maze_try_visit_cell()} detects this,
 it sets a \co{->done} field in the maze structure.
 Fourth, each child must therefore periodically check the \co{->done}
-field, as shown on lines~13, 18, and~23.
-The \co{ACCESS_ONCE()} primitive must disable any compiler
+field, as shown on lines~\lnref{chk:done1}, \lnref{chk:done2}, and~\lnref{chk:done3}.
+The \co{READ_ONCE()} primitive must disable any compiler
 optimizations that might combine consecutive loads or that
 might reload the value.
 A C++1x volatile relaxed load suffices~\cite{PeteBecker2011N3242}.
@@ -289,55 +301,60 @@ Finally, the \co{maze_find_any_next_cell()} function must use
 compare-and-swap to mark a cell as visited, however
 no constraints on ordering are required beyond those provided by
 thread creation and join.
+\end{lineref}
 
 \begin{listing}[tbp]
-{ \scriptsize
-\begin{verbbox}
-  1 int maze_try_visit_cell(struct maze *mp, int c, int t,
-  2       int *n, int d)
-  3 {
-  4   cell_t t;
-  5   cell_t *tp;
-  6   int vi;
-  7 
-  8   if (!maze_cells_connected(mp, c, t))
-  9     return 0;
- 10   tp = celladdr(mp, t);
- 11   do {
- 12     t = ACCESS_ONCE(*tp);
- 13     if (t & VISITED) {
- 14       if ((t & TID) != mytid)
- 15         mp->done = 1;
- 16       return 0;
- 17     }
- 18   } while (!CAS(tp, t, t | VISITED | myid | d));
- 19   *n = t;
- 20   vi = (*myvi)++;
- 21   myvisited[vi] = t;
- 22   return 1;
- 23 }
-\end{verbbox}
+\begin{linelabel}[ln:SMPdesign:Partitioned Parallel Helper Pseudocode]
+\begin{VerbatimL}[commandchars=\\\@\$]
+int maze_try_visit_cell(struct maze *mp, int c, int t,
+                        int *n, int d)
+{
+	cell_t t;
+	cell_t *tp;
+	int vi;
+
+	if (!maze_cells_connected(mp, c, t))		\lnlbl@chk:conn:b$
+		return 0;				\lnlbl@chk:conn:e$
+	tp = celladdr(mp, t);
+	do {						\lnlbl@loop:b$
+		t = READ_ONCE(*tp);
+		if (t & VISITED) {			\lnlbl@chk:visited$
+			if ((t & TID) != mytid)		\lnlbl@chk:other$
+				mp->done = 1;		\lnlbl@located$
+			return 0;			\lnlbl@ret:fail$
+		}
+	} while (!CAS(tp, t, t | VISITED | myid | d));	\lnlbl@loop:e$
+	*n = t;						\lnlbl@update:new$
+	vi = (*myvi)++;					\lnlbl@update:visited:b$
+	myvisited[vi] = t;				\lnlbl@update:visited:e$
+	return 1;					\lnlbl@ret:success$
 }
-\centering
-\theverbbox
+\end{VerbatimL}
+\end{linelabel}
 \caption{Partitioned Parallel Helper Pseudocode}
 \label{lst:SMPdesign:Partitioned Parallel Helper Pseudocode}
 \end{listing}
 
+\begin{lineref}[ln:SMPdesign:Partitioned Parallel Helper Pseudocode]
 The pseudocode for \co{maze_find_any_next_cell()} is identical to that shown in
 Listing~\ref{lst:SMPdesign:SEQ Helper Pseudocode},
 but the pseudocode for \co{maze_try_visit_cell()} differs, and
 is shown in
 Listing~\ref{lst:SMPdesign:Partitioned Parallel Helper Pseudocode}.
-Lines~8-9 check to see if the cells are connected, returning failure
+Lines~\lnref{chk:conn:b}-\lnref{chk:conn:e}
+check to see if the cells are connected, returning failure
 if not.
-The loop spanning lines~11-18 attempts to mark the new cell visited.
-Line~13 checks to see if it has already been visited, in which case
-line~16 returns failure, but only after line~14 checks to see if
-we have encountered the other thread, in which case line~15 indicates
+The loop spanning lines~\lnref{loop:b}-\lnref{loop:e} attempts to mark
+the new cell visited.
+Line~\lnref{chk:visited} checks to see if it has already been visited, in which case
+line~\lnref{ret:fail} returns failure, but only after line~\lnref{chk:other}
+checks to see if
+we have encountered the other thread, in which case line~\lnref{located} indicates
 that the solution has been located.
-Line~19 updates to the new cell, lines~20 and~21 update this thread's visited
-array, and line~22 returns success.
+Line~\lnref{update:new} updates to the new cell,
+lines~\lnref{update:visited:b} and~\lnref{update:visited:e} update this thread's visited
+array, and line~\lnref{ret:success} returns success.
+\end{lineref}
 
 \begin{figure}[tb]
 \centering
-- 
2.7.4

[PATCH 7/7] CodeSamples/SMPdesign/maze: Substitute {READ/WRITE}_ONCE() for ACCESS_ONCE()

[Akira Yokosawa]

From c79bceb489aa3742e9b9668c84fc1b09613b5fc8 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sat, 3 Nov 2018 08:25:16 +0900
Subject: [PATCH 7/7] CodeSamples/SMPdesign/maze: Substitute {READ/WRITE}_ONCE() for ACCESS_ONCE()

Also fill in a couple of func prototype in maze.h.

Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
 CodeSamples/SMPdesign/maze/maze.h      |  6 ++++++
 CodeSamples/SMPdesign/maze/maze_fg.c   | 18 +++++++++---------
 CodeSamples/SMPdesign/maze/maze_part.c | 18 +++++++++---------
 3 files changed, 24 insertions(+), 18 deletions(-)

diff --git a/CodeSamples/SMPdesign/maze/maze.h b/CodeSamples/SMPdesign/maze/maze.h
index a256278..f1d1343 100644
--- a/CodeSamples/SMPdesign/maze/maze.h
+++ b/CodeSamples/SMPdesign/maze/maze.h
@@ -79,6 +79,10 @@ struct maze {
 };
 
 #define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
+#define READ_ONCE(x) \
+            ({ typeof(x) ___x = ACCESS_ONCE(x); ___x; })
+#define WRITE_ONCE(x, val) ({ ACCESS_ONCE(x) = (val); })
+
 
 /* CLOCK_MONOTONIC_RAW prefered, but the older CLOCK_MONOTONIC will do. */
 #ifdef CLOCK_MONOTONIC_RAW
@@ -190,8 +194,10 @@ int maze_same_tids(struct maze *mp, int r1, int c1, int r2, int c2);
 void new_empty_maze_solve(struct maze *mp);
 int maze_try_visit_cell(struct maze *mp, int cr, int cc, int tr, int tc,
 			int *nextrow, int *nextcol, int distance);
+int maze_row_col_frac(int rc, int num, int den);
 int maze_solve(struct maze *mp, int startrow, int startcol,
 	       int endrow, int endcol, unsigned long long *t);
+void usage(char *progname, const char *format, ...);
 void maze_solve_usage(void);
 int maze_solve_parse(int i, int argc, char *argv[]);
 
diff --git a/CodeSamples/SMPdesign/maze/maze_fg.c b/CodeSamples/SMPdesign/maze/maze_fg.c
index aa1bafa..69af238 100644
--- a/CodeSamples/SMPdesign/maze/maze_fg.c
+++ b/CodeSamples/SMPdesign/maze/maze_fg.c
@@ -75,7 +75,7 @@ int maze_try_visit_cell(struct maze *mp, int cr, int cc, int tr, int tc,
 		return -1;
 	tp = maze_get_cell_addr(mp, tr, tc);
 	do {
-		t = ACCESS_ONCE(*tp);
+		t = READ_ONCE(*tp);
 		if (t & VISITED)
 			return 1;
 	} while (!__sync_bool_compare_and_swap(tp, t, t | VISITED | myid));
@@ -85,7 +85,7 @@ int maze_try_visit_cell(struct maze *mp, int cr, int cc, int tr, int tc,
 	vi = __sync_add_and_fetch(&mp->vi, 1);
 	mp->visited[vi].row = tr;
 	__sync_synchronize();
-	ACCESS_ONCE(mp->visited[vi].col) = tc;
+	WRITE_ONCE(mp->visited[vi].col, tc);
 	return 0;
 }
 
@@ -121,8 +121,8 @@ void *maze_solve_child(void *arg)
 			 * cell to be added to the visited list, we
 			 * are done and the maze has no solution.
 			 */
-			if (vi >= ACCESS_ONCE(mp->vi) + nthreads) {
-				ACCESS_ONCE(mcsp->done) = -1;
+			if (vi >= READ_ONCE(mp->vi) + nthreads) {
+				WRITE_ONCE(mcsp->done, -1);
 				return NULL;
 			}
 
@@ -131,11 +131,11 @@ void *maze_solve_child(void *arg)
 			 * for one of the other threads to find the
 			 * end cell.
 			 */
-			while ((vi > ACCESS_ONCE(mp->vi) ||
-			        ACCESS_ONCE(mp->visited[vi].col) < 0) &&
-			       !ACCESS_ONCE(mcsp->done))
+			while ((vi > READ_ONCE(mp->vi) ||
+			        READ_ONCE(mp->visited[vi].col) < 0) &&
+			       !READ_ONCE(mcsp->done))
 			       	continue;
-			if (ACCESS_ONCE(mcsp->done))
+			if (READ_ONCE(mcsp->done))
 				return NULL;
 
 			/* check of .col before read of .row. */
@@ -151,7 +151,7 @@ void *maze_solve_child(void *arg)
 		do {
 			/* Did we find the solution? */
 			if (nr == mcsp->endrow && nc == mcsp->endcol) {
-				ACCESS_ONCE(mcsp->done) = 1;
+				WRITE_ONCE(mcsp->done, 1);
 				return NULL;
 			}
 
diff --git a/CodeSamples/SMPdesign/maze/maze_part.c b/CodeSamples/SMPdesign/maze/maze_part.c
index 16080d4..2f92e11 100644
--- a/CodeSamples/SMPdesign/maze/maze_part.c
+++ b/CodeSamples/SMPdesign/maze/maze_part.c
@@ -85,12 +85,12 @@ void maze_solve_propagate(struct maze_child *mcp1, struct maze_child *mcp2)
 	if (__sync_fetch_and_add(&mcp1->see_start, 0)) {
 		(void)__sync_lock_test_and_set(&mcp2->see_start, 1);
 		if (__sync_fetch_and_add(&mcp2->see_end, 0))
-			ACCESS_ONCE(mcsp->done) = 1;
+			WRITE_ONCE(mcsp->done, 1);
 	}
 	if (__sync_fetch_and_add(&mcp1->see_end, 0)) {
 		(void)__sync_lock_test_and_set(&mcp2->see_end, 1);
 		if (__sync_fetch_and_add(&mcp2->see_start, 0))
-			ACCESS_ONCE(mcsp->done) = 1;
+			WRITE_ONCE(mcsp->done, 1);
 	}
 }
 
@@ -111,7 +111,7 @@ void record_encounter(struct maze *mp, int cr, int cc, int tr, int tc)
 	mymcp->adj[theirtid].tr = tr;
 	mymcp->adj[theirtid].tc = tc;
 	if (nthreads == 2)
-		ACCESS_ONCE(mcsp->done) = 1;
+		WRITE_ONCE(mcsp->done, 1);
 	maze_solve_propagate(mymcp, &mymcp->mcp0[theirtid]);
 	maze_solve_propagate(&mymcp->mcp0[theirtid], mymcp);
 }
@@ -128,7 +128,7 @@ int maze_try_visit_cell(struct maze *mp, int cr, int cc, int tr, int tc,
 		return -1;
 	tp = maze_get_cell_addr(mp, tr, tc);
 	do {
-		t = ACCESS_ONCE(*tp);
+		t = READ_ONCE(*tp);
 		if (t & VISITED) {
 			record_encounter(mp, cr, cc, tr, tc);
 			return 1;
@@ -496,7 +496,7 @@ int maze_solve_child_done_check(void)
 	struct maze_child *theirmcp;
 
 	if (nthreads <= 2)
-		return ACCESS_ONCE(mcsp->done);
+		return READ_ONCE(mcsp->done);
 	if (!mymcp->see_start_snap &&
 	    __sync_fetch_and_add(&mymcp->see_start, 0)) {
 		mymcp->see_start_snap = 1;
@@ -508,7 +508,7 @@ int maze_solve_child_done_check(void)
 		need_propagate = 1;
 	}
 	if (!need_propagate)
-		return ACCESS_ONCE(mcsp->done);
+		return READ_ONCE(mcsp->done);
 	for (i = 0; i < nthreads; i++) {
 		if (i == mymcp->myid)
 			continue;
@@ -517,7 +517,7 @@ int maze_solve_child_done_check(void)
 		    __sync_fetch_and_add(&theirmcp->adj[myid].mr, 0) != -1)
 			maze_solve_propagate(mymcp, theirmcp);
 	}
-	return ACCESS_ONCE(mcsp->done);
+	return READ_ONCE(mcsp->done);
 }
 
 /*
@@ -555,7 +555,7 @@ void *maze_solve_child(void *arg)
 		 * go to the following loop to do the exploration.
 		 */
 		while (!maze_find_any_next_cell(mp, cr, cc, &nr, &nc)) {
-			if (++vi >= mcp->vi || ACCESS_ONCE(mcsp->done))
+			if (++vi >= mcp->vi || READ_ONCE(mcsp->done))
 				goto done;
 			cr = mcp->visited[vi].row;
 			cc = mcp->visited[vi].col;
@@ -566,7 +566,7 @@ void *maze_solve_child(void *arg)
 		 * the current path one cell.
 		 */
 		do {
-			if (ACCESS_ONCE(mcsp->done))
+			if (READ_ONCE(mcsp->done))
 				goto done;
 			cr = nr;
 			cc = nc;
-- 
2.7.4

Re: [PATCH 0/7] Further conversion of code snippets (howto, cpu, SMPdesign)

[Paul E. McKenney]

On Sun, Nov 04, 2018 at 09:07:36AM +0900, Akira Yokosawa wrote:
> Hi Paul,
> 
> This is another set of patches converting code snippets to new scheme.
> Notes on the changes other than simple conversion follow.
> 
> Patch #2 contains somewhat ugly hack in lockhdeq.c to suppress
> "____cacheline_internodealigned_in_smp" in the resulting snippet.
> I'm afraid it could hurt your eyes.

;-)

> Patch #5 renames "percpu*" to "perthread*" to respect the names
> used in actual code.
> 
> Patch #6 includes substitution of ACCESS_ONCE -> READ_ONCE.
> 
> Patch #7 does the substitution under CodeSamples. It also adds
> a couple of function prototypes in maze.h.

The boxes for the inline code displays look good to me.  I have queued
these, and will push them once I get back on-grid.  Thank you!!!

							Thanx, Paul

>         Thanks, Akira
> --
> Akira Yokosawa (7):
>   howto, cpu: Employ new scheme for command/code snippets
>   SMPdesign: Employ new scheme for snippet of lockhdeq.c
>   SMPdesign: Employ new scheme for snippet of lockhdeq.c and locktdeq.c
>   SMPdesign: Employ new scheme for inline snippets
>   SMPdesign: Employ new scheme for snippets from smpalloc.c
>   SMPdesign/beyond: Employ new scheme for inline pseudocode snippets
>   CodeSamples/SMPdesign/maze: Substitute {READ/WRITE}_ONCE() for
>     ACCESS_ONCE()
> 
>  CodeSamples/SMPdesign/lockhdeq.c       |  53 ++--
>  CodeSamples/SMPdesign/locktdeq.c       |  70 ++---
>  CodeSamples/SMPdesign/maze/maze.h      |   6 +
>  CodeSamples/SMPdesign/maze/maze_fg.c   |  18 +-
>  CodeSamples/SMPdesign/maze/maze_part.c |  18 +-
>  CodeSamples/SMPdesign/smpalloc.c       |  57 ++--
>  SMPdesign/SMPdesign.tex                | 479 ++++++++++++++-------------------
>  SMPdesign/beyond.tex                   | 319 +++++++++++-----------
>  SMPdesign/partexercises.tex            | 263 ++++++------------
>  cpu/overview.tex                       |  15 +-
>  howto/howto.tex                        |  60 ++---
>  11 files changed, 605 insertions(+), 753 deletions(-)
> 
> -- 
> 2.7.4
>