>From 798445931ab13a7fab28d9a9271f719adf14c89a Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@xxxxxxxxx>
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@xxxxxxxxx>
---
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
