>From e94531367e4c5bc66a7cabe2e1e41e80dedf5a53 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@xxxxxxxxx>
Date: Sun, 23 Dec 2018 22:58:09 +0900
Subject: [PATCH 08/11] datastruct: Employ new scheme for snippets of hash_bkt_rcu and hash_resize
Other than mechanical conversion, fix cross reference to
Listing 10.13 in Quick Quiz 10.13.
Also there appears an smp_mb() in Lising 10.10, which has no
explanation in the text. The memory barrier was added in commit
1daf3670c304 ("Fix resizable hash table memory ordering") along
with a synchronize_rcu() in hashtab_resize().
Signed-off-by: Akira Yokosawa <akiyks@xxxxxxxxx>
---
CodeSamples/datastruct/hash/hash_bkt_rcu.c | 33 +-
CodeSamples/datastruct/hash/hash_resize.c | 232 ++++++++------
datastruct/datastruct.tex | 492 ++++++++---------------------
3 files changed, 284 insertions(+), 473 deletions(-)
diff --git a/CodeSamples/datastruct/hash/hash_bkt_rcu.c b/CodeSamples/datastruct/hash/hash_bkt_rcu.c
index 45abf03..bb74087 100644
--- a/CodeSamples/datastruct/hash/hash_bkt_rcu.c
+++ b/CodeSamples/datastruct/hash/hash_bkt_rcu.c
@@ -65,16 +65,20 @@ static void hashtab_unlock(struct hashtab *htp, unsigned long hash)
spin_unlock(&HASH2BKT(htp, hash)->htb_lock);
}
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt_rcu:lock_unlock,commandchars=\\\[\]]
/* Read-side lock/unlock functions. */
-static void hashtab_lock_lookup(struct hashtab *htp, unsigned long hash)
+static void hashtab_lock_lookup(struct hashtab *htp,
+ unsigned long hash)
{
rcu_read_lock();
}
-static void hashtab_unlock_lookup(struct hashtab *htp, unsigned long hash)
+static void hashtab_unlock_lookup(struct hashtab *htp,
+ unsigned long hash)
{
rcu_read_unlock();
}
+//\end{snippet}
/* Update-side lock/unlock functions. */
static void hashtab_lock_mod(struct hashtab *htp, unsigned long hash)
@@ -94,6 +98,7 @@ void hashtab_lookup_done(struct ht_elem *htep)
{
}
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt_rcu:lookup,commandchars=\\\[\]]
/*
* Look up a key. Caller must have acquired either a read-side or update-side
* lock via either hashtab_lock_lookup() or hashtab_lock_mod(). Note that
@@ -103,13 +108,17 @@ void hashtab_lookup_done(struct ht_elem *htep)
* Note that the caller is responsible for mapping from whatever type
* of key is in use to an unsigned long, passed in via "hash".
*/
-struct ht_elem *hashtab_lookup(struct hashtab *htp, unsigned long hash,
- void *key)
+struct ht_elem *hashtab_lookup(struct hashtab *htp,
+ unsigned long hash,
+ void *key)
{
- struct ht_elem *htep;
+ struct ht_bucket *htb;
+ struct ht_elem *htep;
- cds_list_for_each_entry_rcu(htep, &HASH2BKT(htp, hash)->htb_head,
- hte_next) {
+ htb = HASH2BKT(htp, hash);
+ cds_list_for_each_entry_rcu(htep,
+ &htb->htb_head,
+ hte_next) {
if (htep->hte_hash != hash)
continue;
if (htp->ht_cmp(htep, key))
@@ -117,15 +126,20 @@ struct ht_elem *hashtab_lookup(struct hashtab *htp, unsigned long hash,
}
return NULL;
}
+//\end{snippet}
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt_rcu:add_del,commandchars=\\\[\]]
/*
* Add an element to the hash table. Caller must have acquired the
* update-side lock via hashtab_lock_mod().
*/
-void hashtab_add(struct hashtab *htp, unsigned long hash, struct ht_elem *htep)
+void hashtab_add(struct hashtab *htp,
+ unsigned long hash,
+ struct ht_elem *htep)
{
htep->hte_hash = hash;
- cds_list_add_rcu(&htep->hte_next, &HASH2BKT(htp, hash)->htb_head);
+ cds_list_add_rcu(&htep->hte_next,
+ &HASH2BKT(htp, hash)->htb_head);
}
/*
@@ -136,6 +150,7 @@ void hashtab_del(struct ht_elem *htep)
{
cds_list_del_rcu(&htep->hte_next);
}
+//\end{snippet}
/*
* Allocate a new hash table with the specified number of buckets.
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index ab76b23..285075e 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -25,10 +25,11 @@
#include <urcu.h>
#include "../../api.h"
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:data,commandchars=\\\@\$]
/* Hash-table element to be included in structures in a hash table. */
struct ht_elem {
struct rcu_head rh;
- struct cds_list_head hte_next[2];
+ struct cds_list_head hte_next[2]; //\lnlbl{ht_elem:next}
unsigned long hte_hash;
};
@@ -39,23 +40,26 @@ struct ht_bucket {
};
/* Hash-table instance, duplicated at resize time. */
-struct ht {
- long ht_nbuckets;
- long ht_resize_cur;
- struct ht *ht_new;
- int ht_idx;
- void *ht_hash_private;
- int (*ht_cmp)(void *hash_private, struct ht_elem *htep, void *key);
+struct ht { //\lnlbl{ht:b}
+ long ht_nbuckets; //\lnlbl{ht:nbuckets}
+ long ht_resize_cur; //\lnlbl{ht:resize_cur}
+ struct ht *ht_new; //\lnlbl{ht:new}
+ int ht_idx; //\lnlbl{ht:idx}
+ void *ht_hash_private; //\lnlbl{ht:hash_private}
+ int (*ht_cmp)(void *hash_private,
+ struct ht_elem *htep,
+ void *key);
long (*ht_gethash)(void *hash_private, void *key);
- void *(*ht_getkey)(struct ht_elem *htep);
- struct ht_bucket ht_bkt[0];
-};
+ void *(*ht_getkey)(struct ht_elem *htep); //\lnlbl{ht:getkey}
+ struct ht_bucket ht_bkt[0]; //\lnlbl{ht:bkt}
+}; //\lnlbl{ht:e}
/* Top-level hash-table data structure, including buckets. */
-struct hashtab {
+struct hashtab { //\lnlbl{hashtab:b}
struct ht *ht_cur;
spinlock_t ht_lock;
-};
+}; //\lnlbl{hashtab:e}
+//\end{snippet}
/* Allocate a hash-table instance. */
struct ht *
@@ -114,28 +118,34 @@ void hashtab_free(struct hashtab *htp_master)
free(htp_master);
}
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:get_bucket,commandchars=\\\@\$]
/* Get hash bucket corresponding to key, ignoring the possibility of resize. */
-static struct ht_bucket *
+static struct ht_bucket * //\lnlbl{single:b}
ht_get_bucket_single(struct ht *htp, void *key, long *b)
{
- *b = htp->ht_gethash(htp->ht_hash_private, key) % htp->ht_nbuckets;
- return &htp->ht_bkt[*b];
-}
+ *b = htp->ht_gethash(htp->ht_hash_private, //\lnlbl{single:gethash:b}
+ key) % htp->ht_nbuckets; //\lnlbl{single:gethash:e}
+ return &htp->ht_bkt[*b]; //\lnlbl{single:return}
+} //\lnlbl{single:e}
/* Get hash bucket correesponding to key, accounting for resize. */
-static struct ht_bucket *ht_get_bucket(struct ht **htp, void *key, long *b, int *i)
+static struct ht_bucket * //\lnlbl{b}
+ht_get_bucket(struct ht **htp, void *key, long *b, int *i)
{
- struct ht_bucket *htbp = ht_get_bucket_single(*htp, key, b);
+ struct ht_bucket *htbp;
- if (*b <= (*htp)->ht_resize_cur) {
+ htbp = ht_get_bucket_single(*htp, key, b); //\lnlbl{call_single}
+ //\fcvexclude
+ if (*b <= (*htp)->ht_resize_cur) { //\lnlbl{resized}
smp_mb(); /* order ->ht_resize_cur before ->ht_new. */
- *htp = (*htp)->ht_new;
- htbp = ht_get_bucket_single(*htp, key, b);
+ *htp = (*htp)->ht_new; //\lnlbl{newtable}
+ htbp = ht_get_bucket_single(*htp, key, b); //\lnlbl{newbucket}
}
- if (i)
- *i = (*htp)->ht_idx;
- return htbp;
-}
+ if (i) //\lnlbl{chk_i}
+ *i = (*htp)->ht_idx; //\lnlbl{set_idx}
+ return htbp; //\lnlbl{return}
+} //\lnlbl{e}
+//\end{snippet}
/* Read-side lock/unlock functions. */
static void hashtab_lock_lookup(struct hashtab *htp_master, void *key)
@@ -148,35 +158,41 @@ static void hashtab_unlock_lookup(struct hashtab *htp_master, void *key)
rcu_read_unlock();
}
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:lock_unlock_mod,commandchars=\\\[\]]
/* Update-side lock/unlock functions. */
-static void hashtab_lock_mod(struct hashtab *htp_master, void *key)
+static void //\lnlbl{lock:b}
+hashtab_lock_mod(struct hashtab *htp_master, void *key)
{
long b;
struct ht *htp;
struct ht_bucket *htbp;
struct ht_bucket *htbp_new;
- rcu_read_lock();
- htp = rcu_dereference(htp_master->ht_cur);
- htbp = ht_get_bucket_single(htp, key, &b);
- spin_lock(&htbp->htb_lock);
- if (b > htp->ht_resize_cur)
- return;
- htp = htp->ht_new;
- htbp_new = ht_get_bucket_single(htp, key, &b);
- spin_lock(&htbp_new->htb_lock);
- spin_unlock(&htbp->htb_lock);
-}
-
-static void hashtab_unlock_mod(struct hashtab *htp_master, void *key)
+ rcu_read_lock(); //\lnlbl{lock:rcu_lock}
+ htp = rcu_dereference(htp_master->ht_cur); //\lnlbl{lock:refhashtbl}
+ htbp = ht_get_bucket_single(htp, key, &b); //\lnlbl{lock:refbucket}
+ spin_lock(&htbp->htb_lock); //\lnlbl{lock:acq_bucket}
+ if (b > htp->ht_resize_cur) //\lnlbl{lock:chk_resz_dist}
+ return; //\lnlbl{lock:fastret}
+ htp = htp->ht_new; //\lnlbl{lock:new_hashtbl}
+ htbp_new = ht_get_bucket_single(htp, key, &b); //\lnlbl{lock:get_newbucket}
+ spin_lock(&htbp_new->htb_lock); //\lnlbl{lock:acq_newbucket}
+ spin_unlock(&htbp->htb_lock); //\lnlbl{lock:rel_oldbucket}
+} //\lnlbl{lock:e}
+
+static void //\lnlbl{unlock:b}
+hashtab_unlock_mod(struct hashtab *htp_master, void *key)
{
long b;
- struct ht *htp = rcu_dereference(htp_master->ht_cur);
- struct ht_bucket *htbp = ht_get_bucket(&htp, key, &b, NULL);
+ struct ht *htp;
+ struct ht_bucket *htbp;
- spin_unlock(&htbp->htb_lock);
- rcu_read_unlock();
-}
+ htp = rcu_dereference(htp_master->ht_cur); //\lnlbl{unlock:get_curtbl}
+ htbp = ht_get_bucket(&htp, key, &b, NULL); //\lnlbl{unlock:get_curbucket}
+ spin_unlock(&htbp->htb_lock); //\lnlbl{unlock:rel_curbucket}
+ rcu_read_unlock(); //\lnlbl{unlock:rcu_unlock}
+} //\lnlbl{unlock:e}
+//\end{snippet}
/*
* Finished using a looked up hashtable element.
@@ -185,63 +201,74 @@ void hashtab_lookup_done(struct ht_elem *htep)
{
}
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:access,commandchars=\\\@\$]
/*
* Look up a key. Caller must have acquired either a read-side or update-side
* lock via either hashtab_lock_lookup() or hashtab_lock_mod(). Note that
* the return is a pointer to the ht_elem: Use offset_of() or equivalent
* to get a pointer to the full data structure.
*/
-struct ht_elem *hashtab_lookup(struct hashtab *htp_master, void *key)
+struct ht_elem * //\lnlbl{lookup:b}
+hashtab_lookup(struct hashtab *htp_master, void *key)
{
long b;
int i;
- struct ht *htp = rcu_dereference(htp_master->ht_cur);
+ struct ht *htp;
struct ht_elem *htep;
- struct ht_bucket *htbp = ht_get_bucket(&htp, key, &b, &i);
+ struct ht_bucket *htbp;
- cds_list_for_each_entry_rcu(htep, &htbp->htb_head, hte_next[i]) {
- if (htp->ht_cmp(htp->ht_hash_private, htep, key))
- return htep;
- }
- return NULL;
-}
+ htp = rcu_dereference(htp_master->ht_cur); //\lnlbl{lookup:get_curtbl}
+ htbp = ht_get_bucket(&htp, key, &b, &i); //\lnlbl{lookup:get_curbucket}
+ cds_list_for_each_entry_rcu(htep, //\lnlbl{lookup:loop:b}
+ &htbp->htb_head,
+ hte_next[i]) {
+ if (htp->ht_cmp(htp->ht_hash_private, htep, key)) //\lnlbl{lookup:match}
+ return htep; //\lnlbl{lookup:ret_match}
+ } //\lnlbl{lookup:loop:e}
+ return NULL; //\lnlbl{lookup:ret_NULL}
+} //\lnlbl{lookup:e}
/*
* Add an element to the hash table. Caller must have acquired the
* update-side lock via hashtab_lock_mod().
*/
-void hashtab_add(struct hashtab *htp_master, struct ht_elem *htep)
+void hashtab_add(struct hashtab *htp_master, //\lnlbl{add:b}
+ struct ht_elem *htep)
{
long b;
int i;
- struct ht *htp = rcu_dereference(htp_master->ht_cur);
- struct ht_bucket *htbp = ht_get_bucket(&htp, htp->ht_getkey(htep),
- &b, &i);
+ struct ht *htp;
+ struct ht_bucket *htbp;
- cds_list_add_rcu(&htep->hte_next[i], &htbp->htb_head);
-}
+ htp = rcu_dereference(htp_master->ht_cur); //\lnlbl{add:get_curtbl}
+ htbp = ht_get_bucket(&htp, htp->ht_getkey(htep), &b, &i); //\lnlbl{add:get_curbucket}
+ cds_list_add_rcu(&htep->hte_next[i], &htbp->htb_head); //\lnlbl{add:add}
+} //\lnlbl{add:e}
/*
* Remove the specified element from the hash table. Caller must have
* acquired the update-side lock via hashtab_lock_mod().
*/
-void hashtab_del(struct hashtab *htp_master, struct ht_elem *htep)
+void hashtab_del(struct hashtab *htp_master, //\lnlbl{del:b}
+ struct ht_elem *htep)
{
long b;
int i;
- struct ht *htp = rcu_dereference(htp_master->ht_cur);
+ struct ht *htp;
- (void)ht_get_bucket(&htp, htp->ht_getkey(htep), &b, &i);
- cds_list_del_rcu(&htep->hte_next[i]);
-}
+ htp = rcu_dereference(htp_master->ht_cur); //\lnlbl{del:get_curtbl}
+ (void)ht_get_bucket(&htp, htp->ht_getkey(htep), &b, &i); //\lnlbl{del:get_curidx}
+ cds_list_del_rcu(&htep->hte_next[i]); //\lnlbl{del:del}
+} //\lnlbl{del:e}
+//\end{snippet}
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:resize,commandchars=\\\@\$]
/* Resize a hash table. */
-int
-hashtab_resize(struct hashtab *htp_master,
- unsigned long nbuckets, void *hash_private,
- int (*cmp)(void *hash_private, struct ht_elem *htep, void *key),
- long (*gethash)(void *hash_private, void *key),
- void *(*getkey)(struct ht_elem *htep))
+int hashtab_resize(struct hashtab *htp_master,
+ unsigned long nbuckets, void *hash_private,
+ int (*cmp)(void *hash_private, struct ht_elem *htep, void *key),
+ long (*gethash)(void *hash_private, void *key),
+ void *(*getkey)(struct ht_elem *htep))
{
struct ht *htp;
struct ht *htp_new;
@@ -252,44 +279,41 @@ hashtab_resize(struct hashtab *htp_master,
struct ht_bucket *htbp_new;
long b;
- if (!spin_trylock(&htp_master->ht_lock))
- return -EBUSY;
- htp = htp_master->ht_cur;
- htp_new = ht_alloc(nbuckets,
- hash_private ? hash_private : htp->ht_hash_private,
- cmp ? cmp : htp->ht_cmp,
- gethash ? gethash : htp->ht_gethash,
- getkey ? getkey : htp->ht_getkey);
- if (htp_new == NULL) {
- spin_unlock(&htp_master->ht_lock);
- return -ENOMEM;
+ if (!spin_trylock(&htp_master->ht_lock)) //\lnlbl{trylock}
+ return -EBUSY; //\lnlbl{ret_busy}
+ htp = htp_master->ht_cur; //\lnlbl{get_curtbl}
+ htp_new = ht_alloc(nbuckets, //\lnlbl{alloc:b}
+ hash_private ? hash_private : htp->ht_hash_private,
+ cmp ? cmp : htp->ht_cmp,
+ gethash ? gethash : htp->ht_gethash,
+ getkey ? getkey : htp->ht_getkey); //\lnlbl{alloc:e}
+ if (htp_new == NULL) { //\lnlbl{chk_nomem}
+ spin_unlock(&htp_master->ht_lock); //\lnlbl{rel_nomem}
+ return -ENOMEM; //\lnlbl{ret_nomem}
}
- htp->ht_new = htp_new;
- synchronize_rcu();
- idx = htp->ht_idx;
+ htp->ht_new = htp_new; //\lnlbl{set_newtbl}
+ synchronize_rcu(); //\lnlbl{sync_rcu}
+ idx = htp->ht_idx; //\lnlbl{get_curidx}
htp_new->ht_idx = !idx;
- for (i = 0; i < htp->ht_nbuckets; i++) {
- htbp = &htp->ht_bkt[i];
- spin_lock(&htbp->htb_lock);
- htp->ht_resize_cur = i;
- cds_list_for_each_entry(htep, &htbp->htb_head, hte_next[idx]) {
- htbp_new =
- ht_get_bucket_single(htp_new,
- htp_new->ht_getkey(htep),
- &b);
+ for (i = 0; i < htp->ht_nbuckets; i++) { //\lnlbl{loop:b}
+ htbp = &htp->ht_bkt[i]; //\lnlbl{get_oldcur}
+ spin_lock(&htbp->htb_lock); //\lnlbl{acq_oldcur}
+ htp->ht_resize_cur = i; //\lnlbl{update_resize}
+ cds_list_for_each_entry(htep, &htbp->htb_head, hte_next[idx]) { //\lnlbl{loop_list:b}
+ htbp_new = ht_get_bucket_single(htp_new, htp_new->ht_getkey(htep), &b);
spin_lock(&htbp_new->htb_lock);
- cds_list_add_rcu(&htep->hte_next[!idx],
- &htbp_new->htb_head);
+ cds_list_add_rcu(&htep->hte_next[!idx], &htbp_new->htb_head);
spin_unlock(&htbp_new->htb_lock);
- }
- spin_unlock(&htbp->htb_lock);
- }
- rcu_assign_pointer(htp_master->ht_cur, htp_new);
- synchronize_rcu();
- spin_unlock(&htp_master->ht_lock);
- free(htp);
- return 0;
+ } //\lnlbl{loop_list:e}
+ spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
+ } //\lnlbl{loop:e}
+ rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
+ synchronize_rcu(); //\lnlbl{sync_rcu_2}
+ spin_unlock(&htp_master->ht_lock); //\lnlbl{rel_master}
+ free(htp); //\lnlbl{free}
+ return 0; //\lnlbl{ret_success}
}
+//\end{snippet}
/* Test functions. */
long tgh(void *hash_private, void *key)
diff --git a/datastruct/datastruct.tex b/datastruct/datastruct.tex
index 65eb650..f75b42b 100644
--- a/datastruct/datastruct.tex
+++ b/datastruct/datastruct.tex
@@ -471,23 +471,7 @@ section~\cite{McKenney:2013:SDS:2483852.2483867}.
\label{sec:datastruct:RCU-Protected Hash Table Implementation}
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 static void hashtab_lock_lookup(struct hashtab *htp,
- 2 unsigned long hash)
- 3 {
- 4 rcu_read_lock();
- 5 }
- 6
- 7 static void hashtab_unlock_lookup(struct hashtab *htp,
- 8 unsigned long hash)
- 9 {
-10 rcu_read_unlock();
-11 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_bkt_rcu@lock_unlock.fcv}
\caption{RCU-Protected Hash-Table Read-Side Concurrency Control}
\label{lst:datastruct:RCU-Protected Hash-Table Read-Side Concurrency Control}
\end{listing}
@@ -507,33 +491,7 @@ shown in
Listing~\ref{lst:datastruct:RCU-Protected Hash-Table Read-Side Concurrency Control}.
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 struct ht_elem
- 2 *hashtab_lookup(struct hashtab *htp,
- 3 unsigned long hash,
- 4 void *key,
- 5 int (*cmp)(struct ht_elem *htep,
- 6 void *key))
- 7 {
- 8 struct ht_bucket *htb;
- 9 struct ht_elem *htep;
-10
-11 htb = HASH2BKT(htp, hash);
-12 cds_list_for_each_entry_rcu(htep,
-13 &htb->htb_head,
-14 hte_next) {
-15 if (htep->hte_hash != hash)
-16 continue;
-17 if (cmp(htep, key))
-18 return htep;
-19 }
-20 return NULL;
-21 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_bkt_rcu@xxxxxxxxxx}
\caption{RCU-Protected Hash-Table Lookup}
\label{lst:datastruct:RCU-Protected Hash-Table Lookup}
\end{listing}
@@ -576,26 +534,7 @@ RCU read-side critical section, for example, the caller must invoke
} \QuickQuizEnd
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 void
- 2 hashtab_add(struct hashtab *htp,
- 3 unsigned long hash,
- 4 struct ht_elem *htep)
- 5 {
- 6 htep->hte_hash = hash;
- 7 cds_list_add_rcu(&htep->hte_next,
- 8 &HASH2BKT(htp, hash)->htb_head);
- 9 }
-10
-11 void hashtab_del(struct ht_elem *htep)
-12 {
-13 cds_list_del_rcu(&htep->hte_next);
-14 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_bkt_rcu@add_del.fcv}
\caption{RCU-Protected Hash-Table Modification}
\label{lst:datastruct:RCU-Protected Hash-Table Modification}
\end{listing}
@@ -939,51 +878,18 @@ which is the subject of the next section.
\label{sec:datastruct:Resizable Hash Table Implementation}
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 struct ht_elem {
- 2 struct rcu_head rh;
- 3 struct cds_list_head hte_next[2];
- 4 unsigned long hte_hash;
- 5 };
- 6
- 7 struct ht_bucket {
- 8 struct cds_list_head htb_head;
- 9 spinlock_t htb_lock;
-10 };
-11
-12 struct ht {
-13 long ht_nbuckets;
-14 long ht_resize_cur;
-15 struct ht *ht_new;
-16 int ht_idx;
-17 void *ht_hash_private;
-18 int (*ht_cmp)(void *hash_private,
-19 struct ht_elem *htep,
-20 void *key);
-21 long (*ht_gethash)(void *hash_private,
-22 void *key);
-23 void *(*ht_getkey)(struct ht_elem *htep);
-24 struct ht_bucket ht_bkt[0];
-25 };
-26
-27 struct hashtab {
-28 struct ht *ht_cur;
-29 spinlock_t ht_lock;
-30 };
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_resize@xxxxxxxx}
\caption{Resizable Hash-Table Data Structures}
\label{lst:datastruct:Resizable Hash-Table Data Structures}
\end{listing}
+\begin{lineref}[ln:datastruct:hash_resize:data]
Resizing is accomplished by the classic approach of inserting a level
of indirection, in this case, the \co{ht} structure shown on
-lines~12-25 of
+lines~\lnref{ht:b}-\lnref{ht:e} of
Listing~\ref{lst:datastruct:Resizable Hash-Table Data Structures}.
-The \co{hashtab} structure shown on lines~27-30 contains only a
+The \co{hashtab} structure shown on
+lines~\lnref{hashtab:b}-\lnref{hashtab:e} contains only a
pointer to the current \co{ht} structure along with a spinlock that
is used to serialize concurrent attempts to resize the hash table.
If we were to use a traditional lock- or atomic-operation-based
@@ -993,15 +899,17 @@ However, because resize operations should be relatively infrequent,
we should be able to make good use of RCU.
The \co{ht} structure represents a specific size of the hash table,
-as specified by the \co{->ht_nbuckets} field on line~13.
+as specified by the \co{->ht_nbuckets} field on line~\lnref{ht:nbuckets}.
The size is stored in the same structure containing the array of
-buckets (\co{->ht_bkt[]} on line~24) in order to avoid mismatches between
+buckets (\co{->ht_bkt[]} on
+line~\lnref{ht:bkt}) in order to avoid mismatches between
the size and the array.
-The \co{->ht_resize_cur} field on line~14 is equal to $-1$ unless a resize
+The \co{->ht_resize_cur} field on
+line~\lnref{ht:resize_cur} is equal to $-1$ unless a resize
operation
is in progress, in which case it indicates the index of the bucket whose
elements are being inserted into the new hash table, which is referenced
-by the \co{->ht_new} field on line~15.
+by the \co{->ht_new} field on line~\lnref{ht:new}.
If there is no resize operation in progress, \co{->ht_new} is \co{NULL}.
Thus, a resize operation proceeds by allocating a new \co{ht} structure
and referencing it via the \co{->ht_new} pointer, then advancing
@@ -1011,13 +919,15 @@ table is linked into the \co{hashtab} structure's \co{->ht_cur} field.
Once all old readers have completed, the old hash table's \co{ht} structure
may be freed.
-The \co{->ht_idx} field on line~16 indicates which of the two sets of
+The \co{->ht_idx} field on
+line~\lnref{ht:idx} indicates which of the two sets of
list pointers are being used by this instantiation of the hash table,
and is used to index the \co{->hte_next[]} array in the \co{ht_elem}
-structure on line~3.
+structure on line~\lnref{ht_elem:next}.
The \co{->ht_hash_private}, \co{->ht_cmp()}, \co{->ht_gethash()},
-and \co{->ht_getkey()} fields on lines~17-23
+and \co{->ht_getkey()} fields on
+lines~\lnref{ht:hash_private}-\lnref{ht:getkey}
collectively define the per-element key and the hash function.
The \co{->ht_hash_private} allows the hash function to be
perturbed~\cite{McKenney89c,McKenney90,McKenney91}, which can be
@@ -1044,62 +954,40 @@ from the new table.
Conversely, if the bucket that would be selected from the old table
has not yet been distributed, then the bucket should be selected from
the old table.
+\end{lineref}
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 static struct ht_bucket *
- 2 ht_get_bucket_single(struct ht *htp,
- 3 void *key, long *b)
- 4 {
- 5 *b = htp->ht_gethash(htp->ht_hash_private,
- 6 key) % htp->ht_nbuckets;
- 7 return &htp->ht_bkt[*b];
- 8 }
- 9
-10 static struct ht_bucket *
-11 ht_get_bucket(struct ht **htp, void *key,
-12 long *b, int *i)
-13 {
-14 struct ht_bucket *htbp;
-15
-16 htbp = ht_get_bucket_single(*htp, key, b);
-17 if (*b <= (*htp)->ht_resize_cur) {
-18 *htp = (*htp)->ht_new;
-19 htbp = ht_get_bucket_single(*htp, key, b);
-20 }
-21 if (i)
-22 *i = (*htp)->ht_idx;
-23 return htbp;
-24 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv}
\caption{Resizable Hash-Table Bucket Selection}
\label{lst:datastruct:Resizable Hash-Table Bucket Selection}
\end{listing}
+\begin{lineref}[ln:datastruct:hash_resize:get_bucket]
Bucket selection is shown in
Listing~\ref{lst:datastruct:Resizable Hash-Table Bucket Selection},
-which shows \co{ht_get_bucket_single()} on lines~1-8 and
-\co{ht_get_bucket()} on lines~10-24.
+which shows \co{ht_get_bucket_single()} on
+lines~\lnref{single:b}-\lnref{single:e} and
+\co{ht_get_bucket()} on lines~\lnref{b}-\lnref{e}.
The \co{ht_get_bucket_single()} function returns a reference to the bucket
corresponding to the specified key in the specified hash table, without
making any allowances for resizing.
It also stores the hash value corresponding to the key into the location
-referenced by parameter \co{b} on lines~5 and ~6.
-Line~7 then returns a reference to the corresponding bucket.
+referenced by parameter \co{b} on
+lines~\lnref{single:gethash:b} and ~\lnref{single:gethash:e}.
+Line~\lnref{single:return} then returns a reference to the corresponding bucket.
The \co{ht_get_bucket()} function handles hash-table selection, invoking
-\co{ht_get_bucket_single()} on line~16 to select the bucket
+\co{ht_get_bucket_single()} on
+line~\lnref{call_single} to select the bucket
corresponding to the hash in the current
hash table, storing the hash value through parameter \co{b}.
-If line~17 determines that the table is being resized and that
-line~16's bucket has already been distributed across the new hash
-table, then line~18 selects the new hash table and line~19
+If line~\lnref{resized} determines that the table is being resized and that
+line~\lnref{call_single}'s bucket has already been distributed across the new hash
+table, then line~\lnref{newtable} selects the new hash table and
+line~\lnref{newbucket}
selects the bucket corresponding to the hash in the new hash table,
again storing the hash value through parameter \co{b}.
+\end{lineref}
\QuickQuiz{}
The code in
@@ -1113,9 +1001,11 @@ again storing the hash value through parameter \co{b}.
new table.
} \QuickQuizEnd
-If line~21 finds that parameter \co{i} is non-\co{NULL}, then
-line~22 stores the pointer-set index for the selected hash table.
-Finally, line~23 returns a reference to the selected hash bucket.
+\begin{lineref}[ln:datastruct:hash_resize:get_bucket]
+If line~\lnref{chk_i} finds that parameter \co{i} is non-\co{NULL}, then
+line~\lnref{set_idx} stores the pointer-set index for the selected hash table.
+Finally, line~\lnref{return} returns a reference to the selected hash bucket.
+\end{lineref}
\QuickQuiz{}
How does the code in
@@ -1134,44 +1024,7 @@ will permit lookups and modifications to run concurrently
with a resize operation.
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 void hashtab_lock_mod(struct hashtab *htp_master,
- 2 void *key)
- 3 {
- 4 long b;
- 5 struct ht *htp;
- 6 struct ht_bucket *htbp;
- 7 struct ht_bucket *htbp_new;
- 8
- 9 rcu_read_lock();
-10 htp = rcu_dereference(htp_master->ht_cur);
-11 htbp = ht_get_bucket_single(htp, key, &b);
-12 spin_lock(&htbp->htb_lock);
-13 if (b > htp->ht_resize_cur)
-14 return;
-15 htp = htp->ht_new;
-16 htbp_new = ht_get_bucket_single(htp, key, &b);
-17 spin_lock(&htbp_new->htb_lock);
-18 spin_unlock(&htbp->htb_lock);
-19 }
-20
-21 void hashtab_unlock_mod(struct hashtab *htp_master,
-22 void *key)
-23 {
-24 long b;
-25 struct ht *htp;
-26 struct ht_bucket *htbp;
-27
-28 htp = rcu_dereference(htp_master->ht_cur);
-29 htbp = ht_get_bucket(&htp, key, &b, NULL);
-30 spin_unlock(&htbp->htb_lock);
-31 rcu_read_unlock();
-32 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv}
\caption{Resizable Hash-Table Update-Side Concurrency Control}
\label{lst:datastruct:Resizable Hash-Table Update-Side Concurrency Control}
\end{listing}
@@ -1184,28 +1037,33 @@ must now deal with the possibility of a
concurrent resize operation as shown in
Listing~\ref{lst:datastruct:Resizable Hash-Table Update-Side Concurrency Control}.
-The \co{hashtab_lock_mod()} spans lines~1-19 in the listing.
-Line~9 enters an RCU read-side critical section to prevent
+\begin{lineref}[ln:datastruct:hash_resize:lock_unlock_mod:lock]
+The \co{hashtab_lock_mod()} spans
+lines~\lnref{b}-\lnref{e} in the listing.
+Line~\lnref{rcu_lock} enters an RCU read-side critical section to prevent
the data structures from being freed during the traversal,
-line~10 acquires a reference to the current hash table, and then
-line~11 obtains a reference to the bucket in this hash table
+line~\lnref{refhashtbl} acquires a reference to the current hash table, and then
+line~\lnref{refbucket} obtains a reference to the bucket in this hash table
corresponding to the key.
-Line~12 acquires that bucket's lock, which will prevent any concurrent
+Line~\lnref{acq_bucket} acquires that bucket's lock, which will prevent any concurrent
resizing operation from distributing that bucket, though of course it
will have no effect if the resizing operation has already distributed
this bucket.
-Line~13 then checks to see if a concurrent resize operation has
+Line~\lnref{chk_resz_dist} then checks to see if a concurrent resize operation has
already distributed this bucket across the new hash table, and if not,
-line~14 returns with the selected hash bucket's lock held (and also
+line~\lnref{fastret} returns with the selected hash bucket's lock held (and also
within an RCU read-side critical section).
Otherwise, a concurrent resize operation has already distributed this
-bucket, so line~15 proceeds to the new hash table and line~16
+bucket, so line~\lnref{new_hashtbl} proceeds to the new hash table and
+line~\lnref{get_newbucket}
selects the bucket corresponding to the key.
-Finally, line~17 acquires the bucket's lock and line~18 releases the
+Finally, line~\lnref{acq_newbucket} acquires the bucket's lock and
+line~\lnref{rel_oldbucket} releases the
lock for the old hash table's bucket.
Once again, \co{hashtab_lock_mod()} exits within an RCU read-side critical
section.
+\end{lineref}
\QuickQuiz{}
The code in
@@ -1222,14 +1080,18 @@ section.
Carrying out this optimization is left as an exercise for the reader.
} \QuickQuizEnd
+\begin{lineref}[ln:datastruct:hash_resize:lock_unlock_mod:unlock]
The \co{hashtab_unlock_mod()} function releases the lock acquired by
\co{hashtab_lock_mod()}.
-Line~28 picks up the current hash table, and then line~29 invokes
+Line~\lnref{get_curtbl} picks up the current hash table, and then
+line~\lnref{get_curbucket} invokes
\co{ht_get_bucket()} in order to gain a reference to the bucket that
corresponds to the key---and of course this bucket might well be in a
new hash table.
-Line~30 releases the bucket's lock and finally line~31 exits the
+Line~\lnref{rel_curbucket} releases the bucket's lock and finally
+line~\lnref{rcu_unlock} exits the
RCU read-side critical section.
+\end{lineref}
\QuickQuiz{}
Suppose that one thread is inserting an element into the
@@ -1252,64 +1114,7 @@ RCU read-side critical section.
} \QuickQuizEnd
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 struct ht_elem *
- 2 hashtab_lookup(struct hashtab *htp_master,
- 3 void *key)
- 4 {
- 5 long b;
- 6 int i;
- 7 struct ht *htp;
- 8 struct ht_elem *htep;
- 9 struct ht_bucket *htbp;
-10
-11 htp = rcu_dereference(htp_master->ht_cur);
-12 htbp = ht_get_bucket(&htp, key, &b, &i);
-13 cds_list_for_each_entry_rcu(htep,
-14 &htbp->htb_head,
-15 hte_next[i]) {
-16 if (htp->ht_cmp(htp->ht_hash_private,
-17 htep, key))
-18 return htep;
-19 }
-20 return NULL;
-21 }
-22
-23 void
-24 hashtab_add(struct hashtab *htp_master,
-25 struct ht_elem *htep)
-26 {
-27 long b;
-28 int i;
-29 struct ht *htp;
-30 struct ht_bucket *htbp;
-31
-32 htp = rcu_dereference(htp_master->ht_cur);
-33 htbp = ht_get_bucket(&htp, htp->ht_getkey(htep),
-34 &b, &i);
-35 cds_list_add_rcu(&htep->hte_next[i],
-36 &htbp->htb_head);
-37 }
-38
-39 void
-40 hashtab_del(struct hashtab *htp_master,
-41 struct ht_elem *htep)
-42 {
-43 long b;
-44 int i;
-45 struct ht *htp;
-46 struct ht_bucket *htbp;
-47
-48 htp = rcu_dereference(htp_master->ht_cur);
-49 htbp = ht_get_bucket(&htp, htp->ht_getkey(htep),
-50 &b, &i);
-51 cds_list_del_rcu(&htep->hte_next[i]);
-52 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_resize@xxxxxxxxxx}
\caption{Resizable Hash-Table Access Functions}
\label{lst:datastruct:Resizable Hash-Table Access Functions}
\end{listing}
@@ -1320,19 +1125,26 @@ The \co{hashtab_lookup()}, \co{hashtab_add()}, and \co{hashtab_del()}
functions shown in
Listing~\ref{lst:datastruct:Resizable Hash-Table Access Functions}.
-The \co{hashtab_lookup()} function on lines~1-21 of the figure does
+\begin{lineref}[ln:datastruct:hash_resize:access:lookup]
+The \co{hashtab_lookup()} function on
+lines~\lnref{b}-\lnref{e} of the figure does
hash lookups.
-Line~11 fetches the current hash table and line~12 obtains a reference
+Line~\lnref{get_curtbl} fetches the current hash table and
+line~\lnref{get_curbucket} obtains a reference
to the bucket corresponding to the specified key.
This bucket will be located in a new resized hash table when a
resize operation has progressed past the bucket in the old hash
table that contained the desired data element.
-Note that line~12 also passes back the index that will be used to
+Note that line~\lnref{get_curbucket} also passes back the index that will be used to
select the correct set of pointers from the pair in each element.
-The loop spanning lines~13-19 searches the bucket, so that if line~16
-detects a match, line~18 returns a pointer to the enclosing data element.
-Otherwise, if there is no match, line~20 returns \co{NULL} to indicate
+The loop spanning lines~\lnref{loop:b}-\lnref{loop:e} searches the bucket,
+so that if line~\lnref{match}
+detects a match,
+line~\lnref{ret_match} returns a pointer to the enclosing data element.
+Otherwise, if there is no match,
+line~\lnref{ret_NULL} returns \co{NULL} to indicate
failure.
+\end{lineref}
\QuickQuiz{}
In the \co{hashtab_lookup()} function in
@@ -1353,10 +1165,12 @@ failure.
just added, which certainly sounds like a bug to me!
} \QuickQuizEnd
-The \co{hashtab_add()} function on lines~23-37 of the figure adds
+\begin{lineref}[ln:datastruct:hash_resize:access:add]
+The \co{hashtab_add()} function on lines~\lnref{b}-\lnref{e} of the figure adds
new data elements to the hash table.
-Lines~32-34 obtain a pointer to the hash bucket corresponding to
-the key (and provide the index), as before, and line~35 adds the new
+Lines~\lnref{get_curtbl}-\lnref{get_curbucket} obtain a pointer to
+the hash bucket corresponding to
+the key (and provide the index), as before, and line~\lnref{add} adds the new
element to the table.
The caller is required to handle concurrency, for example, by invoking
\co{hashtab_lock_mod()} before the call to \co{hashtab_add()} and invoking
@@ -1365,14 +1179,19 @@ These two concurrency-control functions will correctly synchronize with
a concurrent resize operation: If the resize operation has already
progressed beyond the bucket that this data element would have been added to,
then the element is added to the new table.
+\end{lineref}
-The \co{hashtab_del()} function on lines~39-52 of the figure removes
+\begin{lineref}[ln:datastruct:hash_resize:access:del]
+The \co{hashtab_del()} function on
+lines~\lnref{b}-\lnref{e} of the figure removes
an existing element from the hash table.
-Lines~48-50 provide the bucket and index as before, and line~51 removes
+Lines~\lnref{get_curtbl}-\lnref{get_curidx} provide the index as before,
+and line~\lnref{del} removes
the specified element.
As with \co{hashtab_add()}, the caller is responsible for concurrency
control and this concurrency control suffices for synchronizing with
a concurrent resize operation.
+\end{lineref}
\QuickQuiz{}
The \co{hashtab_del()} function in
@@ -1397,125 +1216,82 @@ a concurrent resize operation.
} \QuickQuizEnd
\begin{listing*}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 int hashtab_resize(struct hashtab *htp_master,
- 2 unsigned long nbuckets, void *hash_private,
- 3 int (*cmp)(void *hash_private, struct ht_elem *htep, void *key),
- 4 long (*gethash)(void *hash_private, void *key),
- 5 void *(*getkey)(struct ht_elem *htep))
- 6 {
- 7 struct ht *htp;
- 8 struct ht *htp_new;
- 9 int i;
-10 int idx;
-11 struct ht_elem *htep;
-12 struct ht_bucket *htbp;
-13 struct ht_bucket *htbp_new;
-14 unsigned long hash;
-15 long b;
-16
-17 if (!spin_trylock(&htp_master->ht_lock))
-18 return -EBUSY;
-19 htp = htp_master->ht_cur;
-20 htp_new = ht_alloc(nbuckets,
-21 hash_private ? hash_private : htp->ht_hash_private,
-22 cmp ? cmp : htp->ht_cmp,
-23 gethash ? gethash : htp->ht_gethash,
-24 getkey ? getkey : htp->ht_getkey);
-25 if (htp_new == NULL) {
-26 spin_unlock(&htp_master->ht_lock);
-27 return -ENOMEM;
-28 }
-29 htp->ht_new = htp_new;
-30 synchronize_rcu();
-31 idx = htp->ht_idx;
-32 htp_new->ht_idx = !idx;
-33 for (i = 0; i < htp->ht_nbuckets; i++) {
-34 htbp = &htp->ht_bkt[i];
-35 spin_lock(&htbp->htb_lock);
-36 htp->ht_resize_cur = i;
-37 cds_list_for_each_entry(htep, &htbp->htb_head, hte_next[idx]) {
-38 htbp_new = ht_get_bucket_single(htp_new, htp_new->ht_getkey(htep), &b);
-39 spin_lock(&htbp_new->htb_lock);
-40 cds_list_add_rcu(&htep->hte_next[!idx], &htbp_new->htb_head);
-41 spin_unlock(&htbp_new->htb_lock);
-42 }
-43 spin_unlock(&htbp->htb_lock);
-44 }
-45 rcu_assign_pointer(htp_master->ht_cur, htp_new);
-46 synchronize_rcu();
-47 spin_unlock(&htp_master->ht_lock);
-48 free(htp);
-49 return 0;
-50 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_resize@xxxxxxxxxx}
\caption{Resizable Hash-Table Resizing}
\label{lst:datastruct:Resizable Hash-Table Resizing}
\end{listing*}
+\begin{lineref}[ln:datastruct:hash_resize:resize]
The actual resizing itself is carried out by \co{hashtab_resize}, shown in
Listing~\ref{lst:datastruct:Resizable Hash-Table Resizing} on
page~\pageref{lst:datastruct:Resizable Hash-Table Resizing}.
-Line~17 conditionally acquires the top-level \co{->ht_lock}, and if
-this acquisition fails, line~18 returns \co{-EBUSY} to indicate that
+Line~\lnref{trylock} conditionally acquires the top-level \co{->ht_lock}, and if
+this acquisition fails, line~\lnref{ret_busy} returns \co{-EBUSY} to indicate that
a resize is already in progress.
-Otherwise, line~19 picks up a reference to the current hash table,
-and lines~21-24 allocate a new hash table of the desired size.
+Otherwise, line~\lnref{get_curtbl} picks up a reference to the current hash table,
+and lines~\lnref{alloc:b}-\lnref{alloc:e} allocate a new hash table of the desired size.
If a new set of hash/key functions have been specified, these are
used for the new table, otherwise those of the old table are preserved.
-If line~25 detects memory-allocation failure, line~26 releases \co{->ht_lock}
-and line~27 returns a failure indication.
+If line~\lnref{chk_nomem} detects memory-allocation failure,
+line~\lnref{rel_nomem} releases \co{->ht_lock}
+and line~\lnref{ret_nomem} returns a failure indication.
-Line~29 starts the bucket-distribution process by installing a reference
+Line~\lnref{set_newtbl} starts the bucket-distribution process by installing a reference
to the new table into the \co{->ht_new} field of the old table.
-Line~30 ensures that all readers who are not aware of the new table
+Line~\lnref{sync_rcu} ensures that all readers who are not aware of the new table
complete before the resize operation continues.
-Line~31 picks up the current table's index and stores its inverse to
+Line~\lnref{get_curidx} picks up the current table's index and stores its inverse to
the new hash table, thus ensuring that the two hash tables avoid overwriting
each other's linked lists.
-Each pass through the loop spanning lines~33-44 distributes the contents
+Each pass through the loop spanning lines~\lnref{loop:b}-\lnref{loop:e} distributes the contents
of one of the old hash table's buckets into the new hash table.
-Line~34 picks up a reference to the old table's current bucket,
-line~35 acquires that bucket's spinlock, and line~36 updates
+Line~\lnref{get_oldcur} picks up a reference to the old table's current bucket,
+line~\lnref{acq_oldcur} acquires that bucket's spinlock, and
+line~\lnref{update_resize} updates
\co{->ht_resize_cur} to indicate that this bucket is being distributed.
+\end{lineref}
\QuickQuiz{}
+ \begin{lineref}[ln:datastruct:hash_resize:resize]
In the \co{hashtab_resize()} function in
- Listing~\ref{lst:datastruct:Resizable Hash-Table Access Functions},
- what guarantees that the update to \co{->ht_new} on line~29
+ Listing~\ref{lst:datastruct:Resizable Hash-Table Resizing},
+ what guarantees that the update to \co{->ht_new} on line~\lnref{set_newtbl}
will be seen as happening before the update to \co{->ht_resize_cur}
- on line~36 from the perspective of \co{hashtab_lookup()},
+ on line~\lnref{update_resize} from the perspective of \co{hashtab_lookup()},
\co{hashtab_add()}, and \co{hashtab_del()}?
+ \end{lineref}
\QuickQuizAnswer{
- The \co{synchronize_rcu()} on line~30 of
- Listing~\ref{lst:datastruct:Resizable Hash-Table Access Functions}
+ \begin{lineref}[ln:datastruct:hash_resize:resize]
+ The \co{synchronize_rcu()} on line~\lnref{sync_rcu} of
+ Listing~\ref{lst:datastruct:Resizable Hash-Table Resizing}
ensures that all pre-existing RCU readers have completed between
the time that we install the new hash-table reference on
- line~29 and the time that we update \co{->ht_resize_cur} on
- line~36.
+ line~\lnref{set_newtbl} and the time that we update \co{->ht_resize_cur} on
+ line~\lnref{update_resize}.
This means that any reader that sees a non-negative value
of \co{->ht_resize_cur} cannot have started before the
assignment to \co{->ht_new}, and thus must be able to see
the reference to the new hash table.
+ \end{lineref}
} \QuickQuizEnd
-Each pass through the loop spanning lines~37-42 adds one data element
+\begin{lineref}[ln:datastruct:hash_resize:resize]
+Each pass through the loop spanning
+lines~\lnref{loop_list:b}-\lnref{loop_list:e} adds one data element
from the current old-table bucket to the corresponding new-table bucket,
holding the new-table bucket's lock during the add operation.
-Finally, line~43 releases the old-table bucket lock.
+Finally, line~\lnref{rel_oldcur} releases the old-table bucket lock.
-Execution reaches line~45 once all old-table buckets have been distributed
+Execution reaches line~\lnref{rcu_assign} once all old-table buckets have been distributed
across the new table.
-Line~45 installs the newly created table as the current one, and
-line~46 waits for all old readers (who might still be referencing
+Line~\lnref{rcu_assign} installs the newly created table as the current one, and
+line~\lnref{sync_rcu_2} waits for all old readers (who might still be referencing
the old table) to complete.
-Then line~47 releases the resize-serialization lock, line~48 frees
-the old hash table, and finally line~48 returns success.
+Then line~\lnref{rel_master} releases the resize-serialization lock,
+line~\lnref{free} frees
+the old hash table, and finally line~\lnref{ret_success} returns success.
+\end{lineref}
\subsection{Resizable Hash Table Discussion}
\label{sec:datastruct:Resizable Hash Table Discussion}
@@ -1994,16 +1770,12 @@ that element, they would incur expensive cache misses, degrading both
performance and scalability.
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
-1 struct hash_elem {
-2 struct ht_elem e;
-3 long __attribute__ ((aligned(64))) counter;
-4 };
-\end{verbbox}
-}
-\centering
-\theverbbox
+\begin{VerbatimL}
+struct hash_elem {
+ struct ht_elem e;
+ long __attribute__ ((aligned(64))) counter;
+};
+\end{VerbatimL}
\caption{Alignment for 64-Byte Cache Lines}
\label{lst:datastruct:Alignment for 64-Byte Cache Lines}
\end{listing}
--
2.7.4
