Skip to contentSkip to conversation

Further conversion of code snippets (howto, cpu, SMPdesign)

PATCH In review Akira Yokosawa 2 participants 9 messages Nov 4, 2018 – Nov 5, 2018

lore
Share & tools
lore
#0 lore raw

cover Further conversion of code snippets (howto, cpu, SMPdesign)

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(-)
Signature · 1 line
2.7.4
#1 lore raw

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

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

---
 cpu/overview.tex | 15 +++++---------
 howto/howto.tex  | 60 ++++++++++++++++++++++----------------------------------
 2 files changed, 28 insertions(+), 47 deletions(-)
cpu/overview.tex +5 -10
index 7c02c13..071cf7c 100644
@@ -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
howto/howto.tex +23 -37

83 lines not on this page · raw message

Signature · 1 line
2.7.4
#2 lore raw

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

In reply to Akira Yokosawa

From c516d1ab6d3930d0431aa30a4cf4e3004d70a865 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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 */

---
 CodeSamples/SMPdesign/lockhdeq.c | 19 ++++++++++++-------
 SMPdesign/partexercises.tex      | 24 +++++++-----------------
 2 files changed, 19 insertions(+), 24 deletions(-)
CodeSamples/SMPdesign/lockhdeq.c +12 -7
index d6cc099..8ba635b 100644
@@ -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)
 {
SMPdesign/partexercises.tex +7 -17
index db4b5d8..5b5fd5a 100644
@@ -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
Signature · 1 line
2.7.4
#3 lore raw

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

In reply to Akira Yokosawa

From 966f43a286dedd32a577409fa54221b42f50d8cd Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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

---
 CodeSamples/SMPdesign/lockhdeq.c |  34 +++---
 CodeSamples/SMPdesign/locktdeq.c |  70 ++++++------
 SMPdesign/partexercises.tex      | 237 +++++++++++++--------------------------
 3 files changed, 132 insertions(+), 209 deletions(-)
CodeSamples/SMPdesign/lockhdeq.c +18 -16
index 8ba635b..1b57423 100644
@@ -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
CodeSamples/SMPdesign/locktdeq.c +36 -34

94 lines not on this page · raw message

SMPdesign/partexercises.tex +78 -159

300 lines not on this page · raw message

Signature · 1 line
2.7.4
#4 lore raw

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

In reply to Akira Yokosawa

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

---
 SMPdesign/SMPdesign.tex | 357 +++++++++++++++++++++++-------------------------
 1 file changed, 170 insertions(+), 187 deletions(-)
SMPdesign/SMPdesign.tex +170 -187
index 824de41..06a0c8c 100644
@@ -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
Signature · 1 line
2.7.4
#5 lore raw

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

In reply to Akira Yokosawa

From b5efb413687874a667443943069c021e6c827d7b Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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".

---
 CodeSamples/SMPdesign/smpalloc.c |  57 ++++++++++--------
 SMPdesign/SMPdesign.tex          | 122 ++++++++++-----------------------------
 2 files changed, 63 insertions(+), 116 deletions(-)
CodeSamples/SMPdesign/smpalloc.c +33 -24
index 149e226..72262d6 100644
@@ -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)
 {
SMPdesign/SMPdesign.tex +30 -92

162 lines not on this page · raw message

Signature · 1 line
2.7.4
#6 lore raw

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

In reply to Akira Yokosawa

From b36ad7a4fc1e62b276bb607a6a654e7efa5fec38 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 SMPdesign/beyond.tex | 319 +++++++++++++++++++++++++++------------------------
 1 file changed, 168 insertions(+), 151 deletions(-)
SMPdesign/beyond.tex +168 -151
index 88e2b31..5997f86 100644
@@ -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
Signature · 1 line
2.7.4
#7 lore raw

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

In reply to Akira Yokosawa

From c79bceb489aa3742e9b9668c84fc1b09613b5fc8 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.

---
 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(-)
CodeSamples/SMPdesign/maze/maze.h +6 -0
index a256278..f1d1343 100644
@@ -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[]);
 
CodeSamples/SMPdesign/maze/maze_fg.c +9 -9
index aa1bafa..69af238 100644
@@ -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;
 			}
 
CodeSamples/SMPdesign/maze/maze_part.c +9 -9
index 16080d4..2f92e11 100644
@@ -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;
Signature · 1 line
2.7.4
#8 lore raw
In reply to Akira Yokosawa
Quoted 8 lines · 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.

;-)

Quoted 7 lines

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

Quoted 28 lines

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(-)
Signature · 1 line
2.7.4