Further conversion of code snippets (howto, cpu, SMPdesign)
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
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
@@ -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
PATCH 2/7 SMPdesign: Employ new scheme for snippet of lockhdeq.c
In reply to Akira YokosawaFrom 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
@@ -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
@@ -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
PATCH 3/7 SMPdesign: Employ new scheme for snippet of lockhdeq.c and locktdeq.c
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 4/7 SMPdesign: Employ new scheme for inline snippets
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 5/7 SMPdesign: Employ new scheme for snippets from smpalloc.c
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 6/7 SMPdesign/beyond: Employ new scheme for inline pseudocode snippets
In reply to Akira YokosawaFrom 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
@@ -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
PATCH 7/7 CodeSamples/SMPdesign/maze: Substitute {READ/WRITE}_ONCE() for ACCESS_ONCE()
In reply to Akira YokosawaFrom 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
@@ -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
@@ -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
@@ -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
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.cto 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 oflockhdeq.c
SMPdesign: Employ new scheme for snippet oflockhdeq.candlocktdeq.c
SMPdesign: Employ new scheme for inline snippets
SMPdesign: Employ new scheme for snippets fromsmpalloc.cSMPdesign/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