* [PATCH 00/11] datastruct: Employ new scheme for code snippet
@ 2018-12-24 14:46 Akira Yokosawa
2018-12-24 14:53 ` [PATCH 01/11] fcvextract.pl: Enhance comment block handling of C source Akira Yokosawa
` (11 more replies)
0 siblings, 12 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 14:46 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
Hi Paul,
This patch set consists of enhancement of fcvextract.pl,
update of snippets in datastruct, and some minor tweaks.
fcvextract.pl now suppresses comment blocks in C source and
supports alternative code for snippets in #ifndef blocks,
which won't be affected by the suppression of comment blocks.
Also, labeling of the form /* \lnlbl{label} */ is now supported
in C snippets.
Patch #1 adds comment block handling to fcvextract.pl, without
changing the default behavior.
Patch #2 adds a couple of explicit options to snippets which
have comments to be displayed. It also converts alternative
code fragments using "#ifndef FCV_EXCLUDE" so that they survive
comment block suppression.
Patch #3 changes the default to "keepcomment=no".
This removes a couple of comments in Listings 4.8 and 9.5.
Patch #4 removes now redundant "\fcvexclude" around comment
blocks. It also uses "#ifndef FCV_SNIPPET" to reduce \fcvexclude
uses.
Patch #5 adds support of "/* \lnlbl{label} */" labeling.
Patch #6 updates snippets of hash_bkt.c. "struct hashtab"
now has the "ht_cmp" field and I updated the text to mention
it. You might want to do some rewording.
Patch #7 adds the "ht_cmp" field in the hashdiagram figure
(still in .fig).
Patch #8 updates the rest of snippets in datastruct. It also
fixes typo in cross references of Listing 10.13.
By this change, an smp_mb() appears in ht_get_bucket()
(Listing 10.10).
My guess is that the counterpart barrier is the first
synchronize_rcu() in hashtab_resize(). It might deserve some
explanation or a Quick Quiz. Also, Answer to Quick Quiz 10.13
might need some expansion, since it looks as though hash_reorder.c
used something more than the pure RCU protection. But I might be
completely misreading here...
Patches #9 and #10 are minor tweaks in appearance of
Listing 10.13. As you can see, tab-space width can be
adjusted per snippet.
Patch #11 permits more chances of hyphenation.
I'm thinking of globally widening tab space of snippets for
1C layout. Let me do some experiment.
Thanks, Akira
--
Akira Yokosawa (11):
fcvextract.pl: Enhance comment block handling of C source
CodeSamples: Add explicit 'keepcomment=yes' options
fcvextract.pl: Make 'keepcomment=no' as default
CodeSamples: Remove redundant \fcvexclude
fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source
datastruct: Employ new scheme for snippets of hash_bkt.c
datastruct: Update hashdiagram figure
datastruct: Employ new scheme for snippets of hash_bkt_rcu and
hash_resize
Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env
Use wider tabsize for snippet in 'listing*'
datastruct: Tweak hyphenation
CodeSamples/SMPdesign/lockhdeq.c | 11 +-
CodeSamples/SMPdesign/smpalloc.c | 8 +-
CodeSamples/count/count_end.c | 8 +-
CodeSamples/count/count_lim.c | 8 +-
CodeSamples/count/count_tstat.c | 10 +-
CodeSamples/datastruct/hash/hash_bkt.c | 96 ++--
CodeSamples/datastruct/hash/hash_bkt_rcu.c | 33 +-
CodeSamples/datastruct/hash/hash_resize.c | 232 +++++-----
CodeSamples/defer/route_hazptr.c | 20 +-
CodeSamples/defer/route_rcu.c | 36 +-
CodeSamples/defer/route_refcnt.c | 16 +-
CodeSamples/defer/route_seq.c | 18 +-
CodeSamples/defer/route_seqlock.c | 14 +-
CodeSamples/defer/seqlock.h | 12 +-
CodeSamples/locking/locked_list.c | 6 +-
CodeSamples/toolsoftrade/forkjoinvar.c | 2 +-
CodeSamples/toolsoftrade/pcreate.c | 2 +-
datastruct/datastruct.tex | 687 ++++++++---------------------
datastruct/hashdiagram.fig | 103 ++---
perfbook.tex | 2 +
pfhyphex.tex | 1 +
utilities/fcvextract.pl | 87 +++-
22 files changed, 627 insertions(+), 785 deletions(-)
--
2.7.4
^ permalink raw reply [flat|nested] 37+ messages in thread
* [PATCH 01/11] fcvextract.pl: Enhance comment block handling of C source
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
@ 2018-12-24 14:53 ` Akira Yokosawa
2018-12-24 14:55 ` [PATCH 02/11] CodeSamples: Add explicit 'keepcomment=yes' options Akira Yokosawa
` (10 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 14:53 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From b7193f419457aff8b34c4d293f6b747770d1a911 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 09:12:48 +0900
Subject: [PATCH 01/11] fcvextract.pl: Enhance comment block handling of C source
Add an option "keepcomment" to \begin{snippet} meta command.
As a first step, default is "keepcomment=yes".
"keepcomment=no" will suppress comment blocks of the form
/* ... */ from appearing in the extracted snippet.
The default will be changed to "keepcomment=no" once the
explicit "keepcomment=yes" options are added where necessary.
Also add code to support "#ifndef FCV_SNIPPET -- #else -- #endif"
conditional to allow alternative code for snippet,
which is embedded using a comment block in a couple of code
samples as follows at the moment:
<actual code> //\fcvexclude
/* --- begin alternative code for snippet \fcvexclude
<alternative code>
--- end alternative code for snippet \fcvexclude */
This won't work with "keepcomment=no". Instead, it can be embedded
in the following way:
#ifndef FCV_SNIPPET
<actual code>
#else
<alternative code>
#endif
NOTE 1: "#else" is optional.
NOTE 2: FCV_SNIPPET should never be defined.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
| 82 ++++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 77 insertions(+), 5 deletions(-)
--git a/utilities/fcvextract.pl b/utilities/fcvextract.pl
index ce549d3..2ad201f 100755
--- a/utilities/fcvextract.pl
+++ b/utilities/fcvextract.pl
@@ -89,6 +89,22 @@
# To omit a line in extracted snippet, put "\fcvexclude" in comment
# on the line.
#
+# By default, comment blocks of the form "/* ... */" in C language
+# code will be kept in the extracted snippet. To omit those blocks,
+# put an option "keepcomment=no" to \begin{snippet} meta command.
+#
+# Also, this script recognizes #ifndef -- #else -- #endif conditional
+# of the following form to allow alternative code for snippet:
+#
+# #ifndef FCV_SNIPPET
+# <actual code>
+# #else
+# <alternative code for snippet>
+# #endif
+#
+# NOTE: "#ifdef FCV_SNIPPET" is not recognized.
+# "#else" can be omitted.
+#
# Copyright (C) Akira Yokosawa, 2018
#
# Authors: Akira Yokosawa <akiyks@gmail.com>
@@ -97,6 +113,7 @@ use strict;
use warnings;
my $src_file;
+my $c_src = 0;
my $lnlbl_re;
my $line;
my $edit_line;
@@ -113,6 +130,9 @@ my $file_name;
my $func_name;
my $label;
my $env_name = "VerbatimL" ;
+my $keepcomment = 1;
+my $incomment = 0;
+my $ifndef = 0;
my $other_opts;
$src_file = $ARGV[0];
@@ -121,8 +141,9 @@ $extract_labelbase = $ARGV[1];
$begin_re = qr/\\begin\{snippet\}.*labelbase=[^,\]]*$extract_labelbase[,\]]/ ;
$end_re = qr/\\end\{snippet\}/;
-if ($src_file =~ /.*\.h$/ ) {
+if ($src_file =~ /.*\.[ch]$/ ) {
$lnlbl_re = qr!(.*?)(\s*//\s*)\\lnlbl\{(.*)}\s*$!;
+ $c_src = 1;
} elsif ($src_file =~ /.*\.c$/ ) {
$lnlbl_re = qr!(.*?)(\s*//\s*)\\lnlbl\{(.*)}\s*$!;
} elsif ($src_file =~ /.*\.spin$/ ) {
@@ -143,14 +164,57 @@ while($line = <>) {
last;
}
if ($extracting == 2) {
- if (($line =~ /$end_re/) && ($extracting == 2)) {
+ if ($line =~ /$end_re/) {
last;
}
if ($line =~ /\\fcvexclude/) {
- # skip this line
- } elsif ($line =~ m!$lnlbl_re!) {
+ next; # skip this line
+ }
+ if ($c_src && !$keepcomment) {
+ if ($incomment) {
+ if ($line =~ /\*\/(.*$)/) {
+ $line = $1;
+ $incomment = 0;
+ } else {
+ $line = "";
+ }
+ } else {
+ if ($line =~ /(.*)\/\*.*\*\/(.*)/) {
+ $line = $1 . $2;
+ if ($line =~ /\S/) {
+ $line = $line . "\n";
+ } else {
+ next;
+ }
+ } elsif ($line =~ /(.*)\/\*.*/) {
+ $line = $1;
+ $incomment = 1;
+ }
+ }
+ }
+ if ($ifndef == 1) {
+ if ($line =~ /\#else/) {
+ $ifndef = 2;
+ } elsif ($line =~ /\#endif/) {
+ $ifndef = 0;
+ }
+ next;
+ }
+ if ($ifndef == 2) {
+ if ($line =~ /\#endif/ ) {
+ $ifndef = 0;
+ next;
+ }
+ }
+ if ($c_src && $line =~ /\#ifndef\s+FCV_SNIPPET/) {
+ $ifndef = 1;
+ next;
+ }
+ if ($line =~ m!$lnlbl_re!) {
$edit_line = $1 . $esc_bsl . "lnlbl" . $esc_open . $3 . $esc_close ;
print $edit_line . "\n" ;
+ } elsif ($line eq "") {
+ next;
} else {
print $line ;
}
@@ -158,7 +222,7 @@ while($line = <>) {
if ($extracting == 1) {
print "% Do not edit!\n" ;
print "% Generated by utilities/fcvextract.pl.\n" ;
- if ($line =~ /labelbase=([^,]+)/) {
+ if ($line =~ /labelbase=([^,\]]+)/) {
print "\\begin\{linelabel}\[$1\]\n" ;
$_ = $line ;
s/labelbase=[^,\]]+,?// ;
@@ -191,6 +255,14 @@ while($line = <>) {
$esc_open = "\{" ;
$esc_close = "\}" ;
}
+ if ($line =~ /keepcomment=([^,\]]+).\]/) {
+ if ($1 eq "no") {
+ $keepcomment = 0;
+ }
+ $_ = $line;
+ s/keepcomment=[^,\]]+,?// ;
+ $line = $_ ;
+ }
if ($line =~ /\[(.*)\]$/) {
$_ = $1 ;
s/,$// ;
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 02/11] CodeSamples: Add explicit 'keepcomment=yes' options
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
2018-12-24 14:53 ` [PATCH 01/11] fcvextract.pl: Enhance comment block handling of C source Akira Yokosawa
@ 2018-12-24 14:55 ` Akira Yokosawa
2018-12-24 14:56 ` [PATCH 03/11] fcvextract.pl: Make 'keepcomment=no' as default Akira Yokosawa
` (9 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 14:55 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From f3f0bb0be7ce81a418aed0fe56e6bad06c36aaca Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 12:28:32 +0900
Subject: [PATCH 02/11] CodeSamples: Add explicit 'keepcomment=yes' options
Comment blocks in these snippets should be kept after the change
of default to "keepcomment=no".
Also use "#ifndef FCV_SNIPPET -- #else -- #endif" to embed
alternative code for snippet. Otherwise they would disappear with
"keepcomment=no".
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/SMPdesign/lockhdeq.c | 7 ++++---
CodeSamples/count/count_tstat.c | 2 +-
CodeSamples/defer/route_rcu.c | 11 ++++++-----
CodeSamples/toolsoftrade/forkjoinvar.c | 2 +-
CodeSamples/toolsoftrade/pcreate.c | 2 +-
5 files changed, 13 insertions(+), 11 deletions(-)
diff --git a/CodeSamples/SMPdesign/lockhdeq.c b/CodeSamples/SMPdesign/lockhdeq.c
index 1b57423..64873be 100644
--- a/CodeSamples/SMPdesign/lockhdeq.c
+++ b/CodeSamples/SMPdesign/lockhdeq.c
@@ -134,10 +134,11 @@ struct pdeq {
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
+#ifndef FCV_SNIPPET
+ spinlock_t rlock ____cacheline_internodealigned_in_smp;
+#else /* FCV_SNIPPET */
spinlock_t rlock; //\lnlbl{rlock}
- -- end alternative code for snippet \fcvexclude */
+#endif /* FCV_SNIPPET */
int ridx; //\lnlbl{ridx}
/* char pad2[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */ //\fcvexclude
struct deq bkt[PDEQ_N_BKTS]; //\lnlbl{bkt}
diff --git a/CodeSamples/count/count_tstat.c b/CodeSamples/count/count_tstat.c
index d30ee48..00bf957 100644
--- a/CodeSamples/count/count_tstat.c
+++ b/CodeSamples/count/count_tstat.c
@@ -22,7 +22,7 @@
#include "../api.h"
-//\begin{snippet}[labelbase=ln:count:count_tstat:whole,commandchars=\\\@\$]
+//\begin{snippet}[labelbase=ln:count:count_tstat:whole,keepcomment=yes,commandchars=\\\@\$]
unsigned long __thread counter = 0;
unsigned long *counterp[NR_THREADS] = { NULL };
int finalthreadcount = 0;
diff --git a/CodeSamples/defer/route_rcu.c b/CodeSamples/defer/route_rcu.c
index 168eead..f147848 100644
--- a/CodeSamples/defer/route_rcu.c
+++ b/CodeSamples/defer/route_rcu.c
@@ -94,16 +94,17 @@ int route_add(unsigned long addr, unsigned long interface)
static void route_cb(struct rcu_head *rhp) //\lnlbl{cb:b}
{
- struct route_entry *rep = container_of(rhp, struct route_entry, rh); //\fcvexclude
- //\fcvexclude
- re_free(rep); //\fcvexclude
-/* --- Alternative code for code snippet: begin --- \fcvexclude
+#ifndef FCV_SNIPPET
+ struct route_entry *rep = container_of(rhp, struct route_entry, rh);
+
+ re_free(rep);
+#else /* FCV_SNIPPET */
struct route_entry *rep;
rep = container_of(rhp, struct route_entry, rh);
WRITE_ONCE(rep->re_freed, 1);
free(rep);
- --- Alternative code for code snippet: end --- */ //\fcvexclude
+#endif /* FCV_SNIPPET */
} //\lnlbl{cb:e}
/* \fcvexclude
diff --git a/CodeSamples/toolsoftrade/forkjoinvar.c b/CodeSamples/toolsoftrade/forkjoinvar.c
index 1580478..1ba0b8d 100644
--- a/CodeSamples/toolsoftrade/forkjoinvar.c
+++ b/CodeSamples/toolsoftrade/forkjoinvar.c
@@ -24,7 +24,7 @@
#include <errno.h>
#include "../api.h"
-// \begin{snippet}[labelbase=ln:toolsoftrade:forkjoinvar:main,commandchars=\$\@\^]
+// \begin{snippet}[labelbase=ln:toolsoftrade:forkjoinvar:main,keepcomment=yes,commandchars=\$\@\^]
int x = 0;
int main(int argc, char *argv[])
diff --git a/CodeSamples/toolsoftrade/pcreate.c b/CodeSamples/toolsoftrade/pcreate.c
index 695a7b7..1eef8bb 100644
--- a/CodeSamples/toolsoftrade/pcreate.c
+++ b/CodeSamples/toolsoftrade/pcreate.c
@@ -26,7 +26,7 @@
#include <errno.h>
#include "../api.h"
-// \begin{snippet}[labelbase=ln:toolsoftrade:pcreate:mythread,commandchars=\$\@\^]
+// \begin{snippet}[labelbase=ln:toolsoftrade:pcreate:mythread,keepcomment=yes,commandchars=\$\@\^]
int x = 0;
void *mythread(void *arg)
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 03/11] fcvextract.pl: Make 'keepcomment=no' as default
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
2018-12-24 14:53 ` [PATCH 01/11] fcvextract.pl: Enhance comment block handling of C source Akira Yokosawa
2018-12-24 14:55 ` [PATCH 02/11] CodeSamples: Add explicit 'keepcomment=yes' options Akira Yokosawa
@ 2018-12-24 14:56 ` Akira Yokosawa
2018-12-24 14:57 ` [PATCH 04/11] CodeSamples: Remove redundant \fcvexclude Akira Yokosawa
` (8 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 14:56 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From e9d75e866a39a9c9af9bf4c2da7c64225b302d42 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 13:43:57 +0900
Subject: [PATCH 03/11] fcvextract.pl: Make 'keepcomment=no' as default
This change removes comments in Listings 4.8 and 9.5, which were
inadvertently sneaked in during the scheme update.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
| 10 +++++-----
1 file changed, 5 insertions(+), 5 deletions(-)
--git a/utilities/fcvextract.pl b/utilities/fcvextract.pl
index 2ad201f..71e761d 100755
--- a/utilities/fcvextract.pl
+++ b/utilities/fcvextract.pl
@@ -90,8 +90,8 @@
# on the line.
#
# By default, comment blocks of the form "/* ... */" in C language
-# code will be kept in the extracted snippet. To omit those blocks,
-# put an option "keepcomment=no" to \begin{snippet} meta command.
+# code will be removed in the extracted snippet. To keep those blocks,
+# put an option "keepcomment=yes" to \begin{snippet} meta command.
#
# Also, this script recognizes #ifndef -- #else -- #endif conditional
# of the following form to allow alternative code for snippet:
@@ -130,7 +130,7 @@ my $file_name;
my $func_name;
my $label;
my $env_name = "VerbatimL" ;
-my $keepcomment = 1;
+my $keepcomment = 0;
my $incomment = 0;
my $ifndef = 0;
my $other_opts;
@@ -256,8 +256,8 @@ while($line = <>) {
$esc_close = "\}" ;
}
if ($line =~ /keepcomment=([^,\]]+).\]/) {
- if ($1 eq "no") {
- $keepcomment = 0;
+ if ($1 eq "yes") {
+ $keepcomment = 1;
}
$_ = $line;
s/keepcomment=[^,\]]+,?// ;
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 04/11] CodeSamples: Remove redundant \fcvexclude
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (2 preceding siblings ...)
2018-12-24 14:56 ` [PATCH 03/11] fcvextract.pl: Make 'keepcomment=no' as default Akira Yokosawa
@ 2018-12-24 14:57 ` Akira Yokosawa
2018-12-24 14:59 ` [PATCH 05/11] fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source Akira Yokosawa
` (7 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 14:57 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 426d265864aa5865da6a331493d22996bfddd4a8 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 14:50:04 +0900
Subject: [PATCH 04/11] CodeSamples: Remove redundant \fcvexclude
Now that comment blocks are removed in snippets by default,
we can remove redundant \fcvexclude.
Also use "#ifndef FCV_SNIPPET -- #endif" instead of \fcvexclude
where applicable.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/SMPdesign/lockhdeq.c | 4 ++--
CodeSamples/SMPdesign/smpalloc.c | 8 +++++---
CodeSamples/count/count_end.c | 8 +++++---
CodeSamples/count/count_lim.c | 8 +++++---
CodeSamples/count/count_tstat.c | 8 +++++---
CodeSamples/defer/route_hazptr.c | 20 ++++++++++----------
CodeSamples/defer/route_rcu.c | 25 +++++++++++++------------
CodeSamples/defer/route_refcnt.c | 16 ++++++++--------
CodeSamples/defer/route_seq.c | 18 +++++++++---------
CodeSamples/defer/route_seqlock.c | 14 +++++++-------
CodeSamples/defer/seqlock.h | 12 +++++++-----
CodeSamples/locking/locked_list.c | 6 ++++--
12 files changed, 80 insertions(+), 67 deletions(-)
diff --git a/CodeSamples/SMPdesign/lockhdeq.c b/CodeSamples/SMPdesign/lockhdeq.c
index 64873be..ac5225a 100644
--- a/CodeSamples/SMPdesign/lockhdeq.c
+++ b/CodeSamples/SMPdesign/lockhdeq.c
@@ -133,14 +133,14 @@ void deq_push_r(struct cds_list_head *e, struct deq *p)
struct pdeq {
spinlock_t llock; //\lnlbl{llock}
int lidx; //\lnlbl{lidx}
- /* char pad1[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */ //\fcvexclude
+ /* char pad1[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */
#ifndef FCV_SNIPPET
spinlock_t rlock ____cacheline_internodealigned_in_smp;
#else /* FCV_SNIPPET */
spinlock_t rlock; //\lnlbl{rlock}
#endif /* FCV_SNIPPET */
int ridx; //\lnlbl{ridx}
- /* char pad2[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */ //\fcvexclude
+ /* char pad2[CACHE_LINE_SIZE - sizeof(spinlock_t) - sizeof(int)]; */
struct deq bkt[PDEQ_N_BKTS]; //\lnlbl{bkt}
};
//\end{snippet}
diff --git a/CodeSamples/SMPdesign/smpalloc.c b/CodeSamples/SMPdesign/smpalloc.c
index 72262d6..87678b3 100644
--- a/CodeSamples/SMPdesign/smpalloc.c
+++ b/CodeSamples/SMPdesign/smpalloc.c
@@ -25,9 +25,11 @@
#define TARGET_POOL_SIZE 3
#define GLOBAL_POOL_SIZE 40
-struct memblock { //\fcvexclude
- char *bytes[CACHE_LINE_SIZE]; //\fcvexclude
-} memblocks[GLOBAL_POOL_SIZE]; //\fcvexclude
+#ifndef FCV_SNIPPET
+struct memblock {
+ char *bytes[CACHE_LINE_SIZE];
+} memblocks[GLOBAL_POOL_SIZE];
+#endif /* FCV_SNIPPET */
//\fcvexclude
struct globalmempool {
spinlock_t mutex;
diff --git a/CodeSamples/count/count_end.c b/CodeSamples/count/count_end.c
index 61f9d81..2ccc0d2 100644
--- a/CodeSamples/count/count_end.c
+++ b/CodeSamples/count/count_end.c
@@ -46,9 +46,11 @@ static __inline__ unsigned long read_count(void)
return sum; //\lnlbl{read:return}
}
-__inline__ void count_init(void) //\fcvexclude
-{ //\fcvexclude
-} //\fcvexclude
+#ifndef FCV_SNIPPET
+__inline__ void count_init(void)
+{
+}
+#endif /* FCV_SNIPPET */
//\fcvexclude
void count_register_thread(unsigned long *p) //\lnlbl{reg:b}
{
diff --git a/CodeSamples/count/count_lim.c b/CodeSamples/count/count_lim.c
index c207beb..db0219b 100644
--- a/CodeSamples/count/count_lim.c
+++ b/CodeSamples/count/count_lim.c
@@ -107,9 +107,11 @@ static __inline__ void balance_count(void) //\lnlbl{balance:b}
globalcount -= counter; //\lnlbl{balance:adjglobal}
} //\lnlbl{balance:e}
-void count_init(void) //\fcvexclude
-{ //\fcvexclude
-} //\fcvexclude
+#ifndef FCV_SNIPPET
+void count_init(void)
+{
+}
+#endif /* FCV_SNIPPET */
//\fcvexclude
void count_register_thread(void) //\lnlbl{register:b}
{
diff --git a/CodeSamples/count/count_tstat.c b/CodeSamples/count/count_tstat.c
index 00bf957..87eab94 100644
--- a/CodeSamples/count/count_tstat.c
+++ b/CodeSamples/count/count_tstat.c
@@ -45,9 +45,11 @@ static __inline__ unsigned long read_count(void)
return sum;
}
-void count_init(void) //\fcvexclude
-{ //\fcvexclude
-} //\fcvexclude
+#ifndef FCV_SNIPPET
+void count_init(void)
+{
+}
+#endif /* FCV_SNIPPET */
//\fcvexclude
void count_register_thread(unsigned long *p)
{
diff --git a/CodeSamples/defer/route_hazptr.c b/CodeSamples/defer/route_hazptr.c
index 0881c51..1d777cf 100644
--- a/CodeSamples/defer/route_hazptr.c
+++ b/CodeSamples/defer/route_hazptr.c
@@ -35,12 +35,12 @@ struct route_entry {
struct route_entry route_list;
DEFINE_SPINLOCK(routelock);
//\fcvexclude
-/* This thread's fixed-sized set of hazard pointers. */ //\fcvexclude
+/* This thread's fixed-sized set of hazard pointers. */
hazard_pointer __thread *my_hazptr;
-/* \fcvexclude
- * Look up a route entry, return the corresponding interface. \fcvexclude
- */ //\fcvexclude
+/*
+ * Look up a route entry, return the corresponding interface.
+ */
unsigned long route_lookup(unsigned long addr)
{
int offset = 0;
@@ -56,16 +56,16 @@ retry: //\lnlbl{retry}
if (rep == (struct route_entry *)HAZPTR_POISON) //\lnlbl{acq:b}
goto retry; /* element deleted. */
//\fcvexclude
- /* Store a hazard pointer. */ //\fcvexclude
+ /* Store a hazard pointer. */
my_hazptr[offset].p = &rep->hh;
offset = !offset;
smp_mb(); /* Force pointer loads in order. */
//\fcvexclude
- /* Recheck the hazard pointer against the original. */ //\fcvexclude
+ /* Recheck the hazard pointer against the original. */
if (READ_ONCE(*repp) != rep)
goto retry; //\lnlbl{acq:e}
//\fcvexclude
- /* Advance to next. */ //\fcvexclude
+ /* Advance to next. */
repp = &rep->re_next;
} while (rep->addr != addr);
if (READ_ONCE(rep->re_freed))
@@ -95,9 +95,9 @@ int route_add(unsigned long addr, unsigned long interface)
return 0;
}
-/* \fcvexclude
- * Remove the specified element from the route table. \fcvexclude
- */ //\fcvexclude
+/*
+ * Remove the specified element from the route table.
+ */
int route_del(unsigned long addr)
{
struct route_entry *rep;
diff --git a/CodeSamples/defer/route_rcu.c b/CodeSamples/defer/route_rcu.c
index f147848..525b598 100644
--- a/CodeSamples/defer/route_rcu.c
+++ b/CodeSamples/defer/route_rcu.c
@@ -42,16 +42,17 @@ struct route_entry {
//\fcvexclude
CDS_LIST_HEAD(route_list);
DEFINE_SPINLOCK(routelock);
+#ifndef FCV_SNIPPET
+static void re_free(struct route_entry *rep)
+{
+ WRITE_ONCE(rep->re_freed, 1);
+ free(rep);
+}
+#endif /* FCV_SNIPPET */
-static void re_free(struct route_entry *rep) //\fcvexclude
-{ //\fcvexclude
- WRITE_ONCE(rep->re_freed, 1); //\fcvexclude
- free(rep); //\fcvexclude
-} //\fcvexclude
- //\fcvexclude
-/* \fcvexclude
- * Look up a route entry, return the corresponding interface. \fcvexclude
- */ //\fcvexclude
+/*
+ * Look up a route entry, return the corresponding interface.
+ */
unsigned long route_lookup(unsigned long addr)
{
struct route_entry *rep;
@@ -107,9 +108,9 @@ static void route_cb(struct rcu_head *rhp) //\lnlbl{cb:b}
#endif /* FCV_SNIPPET */
} //\lnlbl{cb:e}
-/* \fcvexclude
- * Remove the specified element from the route table. \fcvexclude
- */ //\fcvexclude
+/*
+ * Remove the specified element from the route table.
+ */
int route_del(unsigned long addr)
{
struct route_entry *rep;
diff --git a/CodeSamples/defer/route_refcnt.c b/CodeSamples/defer/route_refcnt.c
index 4833919..6f37bd7 100644
--- a/CodeSamples/defer/route_refcnt.c
+++ b/CodeSamples/defer/route_refcnt.c
@@ -40,9 +40,9 @@ static void re_free(struct route_entry *rep) //\lnlbl{re_free:b}
free(rep);
} //\lnlbl{re_free:e}
-/* \fcvexclude
- * Look up a route entry, return the corresponding interface. \fcvexclude
- */ //\fcvexclude
+/*
+ * Look up a route entry, return the corresponding interface.
+ */
unsigned long route_lookup(unsigned long addr)
{
int old;
@@ -61,7 +61,7 @@ retry:
if (rep == NULL) //\lnlbl{lookup:check_NULL}
return ULONG_MAX;
//\fcvexclude
- /* Acquire a reference if the count is non-zero. */ //\fcvexclude
+ /* Acquire a reference if the count is non-zero. */
do { //\lnlbl{lookup:acq:b}
if (READ_ONCE(rep->re_freed)) //\lnlbl{lookup:check_uaf}
abort(); //\lnlbl{lookup:abort}
@@ -72,7 +72,7 @@ retry:
} while (atomic_cmpxchg(&rep->re_refcnt,
old, new) != old); //\lnlbl{lookup:acq:e}
//\fcvexclude
- /* Advance to next. */ //\fcvexclude
+ /* Advance to next. */
repp = &rep->re_next;
} while (rep->addr != addr);
ret = rep->iface;
@@ -104,9 +104,9 @@ int route_add(unsigned long addr, unsigned long interface)
return 0;
}
-/* \fcvexclude
- * Remove the specified element from the route table. \fcvexclude
- */ //\fcvexclude
+/*
+ * Remove the specified element from the route table.
+ */
int route_del(unsigned long addr)
{
struct route_entry *rep;
diff --git a/CodeSamples/defer/route_seq.c b/CodeSamples/defer/route_seq.c
index 535ed09..cc84e6a 100644
--- a/CodeSamples/defer/route_seq.c
+++ b/CodeSamples/defer/route_seq.c
@@ -32,9 +32,9 @@ struct route_entry { //\lnlbl{entry:b}
//\fcvexclude
CDS_LIST_HEAD(route_list); //\lnlbl{entry:header}
-/* \fcvexclude
- * Look up a route entry, return the corresponding interface. \fcvexclude
- */ //\fcvexclude
+/*
+ * Look up a route entry, return the corresponding interface.
+ */
unsigned long route_lookup(unsigned long addr) //\lnlbl{lookup:b}
{
struct route_entry *rep;
@@ -49,9 +49,9 @@ unsigned long route_lookup(unsigned long addr) //\lnlbl{lookup:b}
return ULONG_MAX;
} //\lnlbl{lookup:e}
-/* \fcvexclude
- * Add an element to the route table. \fcvexclude
- */ //\fcvexclude
+/*
+ * Add an element to the route table.
+ */
int route_add(unsigned long addr, unsigned long interface)//\lnlbl{add:b}
{
struct route_entry *rep;
@@ -65,9 +65,9 @@ int route_add(unsigned long addr, unsigned long interface)//\lnlbl{add:b}
return 0;
} //\lnlbl{add:e}
-/* \fcvexclude
- * Remove the specified element from the route table. \fcvexclude
- */ //\fcvexclude
+/*
+ * Remove the specified element from the route table.
+ */
int route_del(unsigned long addr) //\lnlbl{del:b}
{
struct route_entry *rep;
diff --git a/CodeSamples/defer/route_seqlock.c b/CodeSamples/defer/route_seqlock.c
index e87cdb1..dfdc99f 100644
--- a/CodeSamples/defer/route_seqlock.c
+++ b/CodeSamples/defer/route_seqlock.c
@@ -34,9 +34,9 @@ struct route_entry {
struct route_entry route_list;
DEFINE_SEQ_LOCK(sl); //\lnlbl{struct:sl}
-/* \fcvexclude
- * Look up a route entry, return the corresponding interface. \fcvexclude
- */ //\fcvexclude
+/*
+ * Look up a route entry, return the corresponding interface.
+ */
unsigned long route_lookup(unsigned long addr)
{
struct route_entry *rep;
@@ -55,7 +55,7 @@ retry: //\lnlbl{lookup:retry}
return ULONG_MAX;
}
//\fcvexclude
- /* Advance to next. */ //\fcvexclude
+ /* Advance to next. */
repp = &rep->re_next;
} while (rep->addr != addr);
if (READ_ONCE(rep->re_freed)) //\lnlbl{lookup:chk_freed}
@@ -88,9 +88,9 @@ int route_add(unsigned long addr, unsigned long interface)
return 0;
}
-/* \fcvexclude
- * Remove the specified element from the route table. \fcvexclude
- */ //\fcvexclude
+/*
+ * Remove the specified element from the route table.
+ */
int route_del(unsigned long addr)
{
struct route_entry *rep;
diff --git a/CodeSamples/defer/seqlock.h b/CodeSamples/defer/seqlock.h
index 16165d0..d8bccc3 100644
--- a/CodeSamples/defer/seqlock.h
+++ b/CodeSamples/defer/seqlock.h
@@ -24,11 +24,13 @@ typedef struct { //\lnlbl{typedef:b}
spinlock_t lock;
} seqlock_t; //\lnlbl{typedef:e}
-#define DEFINE_SEQ_LOCK(name) seqlock_t name = { /* \fcvexclude */ \
- .seq = 0, /* \fcvexclude */ \
- .lock = __SPIN_LOCK_UNLOCKED(name.lock), /* \fcvexclude */ \
-}; /* \fcvexclude */
- /* \fcvexclude */
+#ifndef FCV_SNIPPET
+#define DEFINE_SEQ_LOCK(name) seqlock_t name = { \
+ .seq = 0, \
+ .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
+};
+#endif /* FCV_SNIPPET */
+ //\fcvexclude
static inline void seqlock_init(seqlock_t *slp) //\lnlbl{init:b}
{
slp->seq = 0;
diff --git a/CodeSamples/locking/locked_list.c b/CodeSamples/locking/locked_list.c
index 0580b09..a8018de 100644
--- a/CodeSamples/locking/locked_list.c
+++ b/CodeSamples/locking/locked_list.c
@@ -26,8 +26,10 @@ struct locked_list {
struct cds_list_head h;
};
-struct cds_list_head *list_next(struct locked_list *lp, //\fcvexclude
- struct cds_list_head *np); //\fcvexclude
+#ifndef FCV_SNIPPET
+struct cds_list_head *list_next(struct locked_list *lp,
+ struct cds_list_head *np);
+#endif /* FCV_SNIPPET */
//\fcvexclude
struct cds_list_head *list_start(struct locked_list *lp)
{
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 05/11] fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (3 preceding siblings ...)
2018-12-24 14:57 ` [PATCH 04/11] CodeSamples: Remove redundant \fcvexclude Akira Yokosawa
@ 2018-12-24 14:59 ` Akira Yokosawa
2018-12-24 15:00 ` [PATCH 06/11] datastruct: Employ new scheme for snippets of hash_bkt.c Akira Yokosawa
` (6 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 14:59 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From f5a7cdba0ffb249111f4cf0d83896c0ce368e736 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 15:06:59 +0900
Subject: [PATCH 05/11] fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source
To embed labels on a multi-line macro definition, we need to
support the following way of labeling:
#define MULTILINE_MACRO ({ FOO /* \lnlbl{foo} */ \
BAR }) //\lnlbl{bar}
This style of labels work in snippets without the "keepcomment=yes"
option.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
| 5 +++++
1 file changed, 5 insertions(+)
--git a/utilities/fcvextract.pl b/utilities/fcvextract.pl
index 71e761d..f8f274b 100755
--- a/utilities/fcvextract.pl
+++ b/utilities/fcvextract.pl
@@ -115,6 +115,7 @@ use warnings;
my $src_file;
my $c_src = 0;
my $lnlbl_re;
+my $lnlbl_re2;
my $line;
my $edit_line;
my $extract_labelbase;
@@ -143,6 +144,7 @@ $end_re = qr/\\end\{snippet\}/;
if ($src_file =~ /.*\.[ch]$/ ) {
$lnlbl_re = qr!(.*?)(\s*//\s*)\\lnlbl\{(.*)}\s*$!;
+ $lnlbl_re2 = qr!(.*?)(s*/\*\s*)\\lnlbl\{(.*)}\s*\*/(.*)$!;
$c_src = 1;
} elsif ($src_file =~ /.*\.c$/ ) {
$lnlbl_re = qr!(.*?)(\s*//\s*)\\lnlbl\{(.*)}\s*$!;
@@ -170,6 +172,9 @@ while($line = <>) {
if ($line =~ /\\fcvexclude/) {
next; # skip this line
}
+ if ($c_src && $line =~ m!$lnlbl_re2!) {
+ $line = $1 . $esc_bsl . "lnlbl" . $esc_open . $3 . $esc_close . $4 . "\n" ;
+ }
if ($c_src && !$keepcomment) {
if ($incomment) {
if ($line =~ /\*\/(.*$)/) {
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 06/11] datastruct: Employ new scheme for snippets of hash_bkt.c
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (4 preceding siblings ...)
2018-12-24 14:59 ` [PATCH 05/11] fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source Akira Yokosawa
@ 2018-12-24 15:00 ` Akira Yokosawa
2018-12-24 15:01 ` [PATCH 07/11] datastruct: Update hashdiagram figure Akira Yokosawa
` (5 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 15:00 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 4e71dc2a3c253e78785f5320f8dd9419d968bf25 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 15:13:01 +0900
Subject: [PATCH 06/11] datastruct: Employ new scheme for snippets of hash_bkt.c
Also update text to reflect the change in struct hashtab adding
ht_cmp field, which was done in commit a988f7798f75 ("Define
comparison function at initialization").
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/datastruct/hash/hash_bkt.c | 96 +++++++++-------
datastruct/datastruct.tex | 193 +++++++++------------------------
2 files changed, 111 insertions(+), 178 deletions(-)
diff --git a/CodeSamples/datastruct/hash/hash_bkt.c b/CodeSamples/datastruct/hash/hash_bkt.c
index af7b2dc..10faab9 100644
--- a/CodeSamples/datastruct/hash/hash_bkt.c
+++ b/CodeSamples/datastruct/hash/hash_bkt.c
@@ -21,38 +21,45 @@
#define _LGPL_SOURCE
#include "../../api.h"
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt:struct,commandchars=\\\@\$]
/* Hash-table element to be included in structures in a hash table. */
-struct ht_elem {
+struct ht_elem { //\lnlbl{elem:b}
struct cds_list_head hte_next;
unsigned long hte_hash;
-};
+}; //\lnlbl{elem:e}
/* Hash-table bucket element. */
-struct ht_bucket {
+struct ht_bucket { //\lnlbl{bucket:b}
struct cds_list_head htb_head;
spinlock_t htb_lock;
-};
+}; //\lnlbl{bucket:e}
/* Top-level hash-table data structure, including buckets. */
-struct hashtab {
+struct hashtab { //\lnlbl{tab:b}
unsigned long ht_nbuckets;
int (*ht_cmp)(struct ht_elem *htep, void *key);
struct ht_bucket ht_bkt[0];
-};
+}; //\lnlbl{tab:e}
+//\end{snippet}
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt:map_lock,commandchars=\!\@\$]
/* Map from hash value to corresponding bucket. */
-#define HASH2BKT(htp, h) (&(htp)->ht_bkt[h % (htp)->ht_nbuckets])
+#define HASH2BKT(htp, h) /* \lnlbl{map:b} */\
+ (&(htp)->ht_bkt[h % (htp)->ht_nbuckets]) //\lnlbl{map:e}
/* Underlying lock/unlock functions. */
-static void hashtab_lock(struct hashtab *htp, unsigned long hash)
+static void hashtab_lock(struct hashtab *htp,
+ unsigned long hash)
{
spin_lock(&HASH2BKT(htp, hash)->htb_lock);
}
-static void hashtab_unlock(struct hashtab *htp, unsigned long hash)
+static void hashtab_unlock(struct hashtab *htp,
+ unsigned long hash)
{
spin_unlock(&HASH2BKT(htp, hash)->htb_lock);
}
+//\end{snippet}
/* Read-side lock/unlock functions. */
static void hashtab_lock_lookup(struct hashtab *htp, unsigned long hash)
@@ -83,6 +90,7 @@ void hashtab_lookup_done(struct ht_elem *htep)
{
}
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt: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
@@ -92,30 +100,35 @@ 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;
-
- cds_list_for_each_entry(htep,
- &HASH2BKT(htp, hash)->htb_head,
- hte_next) {
- if (htep->hte_hash != hash)
- continue;
- if (htp->ht_cmp(htep, key))
- return htep;
- }
- return NULL;
+ struct ht_bucket *htb;
+ struct ht_elem *htep;
+
+ htb = HASH2BKT(htp, hash); //\lnlbl{map}
+ cds_list_for_each_entry(htep, &htb->htb_head, hte_next) { //\lnlbl{loop:b}
+ if (htep->hte_hash != hash) //\lnlbl{hashmatch}
+ continue; //\lnlbl{next}
+ if (htp->ht_cmp(htep, key)) //\lnlbl{keymatch}
+ return htep; //\lnlbl{return}
+ } //\lnlbl{loop:e}
+ return NULL; //\lnlbl{ret_NULL}
}
+//\end{snippet}
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt: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(&htep->hte_next, &HASH2BKT(htp, hash)->htb_head);
+ htep->hte_hash = hash; //\lnlbl{add:set}
+ cds_list_add(&htep->hte_next, //\lnlbl{add:add:b}
+ &HASH2BKT(htp, hash)->htb_head); //\lnlbl{add:add:e}
}
/*
@@ -126,36 +139,41 @@ void hashtab_del(struct ht_elem *htep)
{
cds_list_del_init(&htep->hte_next);
}
+//\end{snippet}
+//\begin{snippet}[labelbase=ln:datastruct:hash_bkt:alloc_free,commandchars=\\\@\$]
/*
* Allocate a new hash table with the specified number of buckets.
*/
-struct hashtab *hashtab_alloc(unsigned long nbuckets,
- int (*cmp)(struct ht_elem *htep, void *key))
+struct hashtab *
+hashtab_alloc(unsigned long nbuckets,
+ int (*cmp)(struct ht_elem *htep, void *key))
{
struct hashtab *htp;
int i;
- htp = malloc(sizeof(*htp) + nbuckets * sizeof(struct ht_bucket));
- if (htp == NULL)
- return NULL;
- htp->ht_nbuckets = nbuckets;
- htp->ht_cmp = cmp;
- for (i = 0; i < nbuckets; i++) {
- CDS_INIT_LIST_HEAD(&htp->ht_bkt[i].htb_head);
- spin_lock_init(&htp->ht_bkt[i].htb_lock);
- }
- return htp;
+ htp = malloc(sizeof(*htp) + //\lnlbl{alloc:alloc:b}
+ nbuckets * sizeof(struct ht_bucket)); //\lnlbl{alloc:alloc:e}
+ if (htp == NULL) //\lnlbl{alloc:chk_NULL}
+ return NULL; //\lnlbl{alloc:ret_NULL}
+ htp->ht_nbuckets = nbuckets; //\lnlbl{alloc:set_nbck}
+ htp->ht_cmp = cmp; //\lnlbl{alloc:set_cmp}
+ for (i = 0; i < nbuckets; i++) { //\lnlbl{alloc:loop:b}
+ CDS_INIT_LIST_HEAD(&htp->ht_bkt[i].htb_head); //\lnlbl{alloc:init_head}
+ spin_lock_init(&htp->ht_bkt[i].htb_lock); //\lnlbl{alloc:init_lock}
+ } //\lnlbl{alloc:loop:e}
+ return htp; //\lnlbl{alloc:return}
}
/*
* Free a hash table. It is the caller's responsibility to ensure that it
* is empty and no longer in use.
*/
-void hashtab_free(struct hashtab *htp)
+void hashtab_free(struct hashtab *htp) //\lnlbl{free:b}
{
free(htp);
-}
+} //\lnlbl{free:e}
+//\end{snippet}
#ifdef TEST_HASH
#include "hashtorture.h"
diff --git a/datastruct/datastruct.tex b/datastruct/datastruct.tex
index b3068d4..65eb650 100644
--- a/datastruct/datastruct.tex
+++ b/datastruct/datastruct.tex
@@ -141,26 +141,7 @@ offers excellent scalability.
\label{sec:datastruct:Hash-Table Implementation}
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 struct ht_elem {
- 2 struct cds_list_head hte_next;
- 3 unsigned long hte_hash;
- 4 };
- 5
- 6 struct ht_bucket {
- 7 struct cds_list_head htb_head;
- 8 spinlock_t htb_lock;
- 9 };
-10
-11 struct hashtab {
-12 unsigned long ht_nbuckets;
-13 struct ht_bucket ht_bkt[0];
-14 };
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_bkt@struct.fcv}
\caption{Hash-Table Data Structures}
\label{lst:datastruct:Hash-Table Data Structures}
\end{listing}
@@ -172,21 +153,25 @@ offers excellent scalability.
\label{fig:datastruct:Hash-Table Data-Structure Diagram}
\end{figure}
+\begin{lineref}[ln:datastruct:hash_bkt:struct]
Listing~\ref{lst:datastruct:Hash-Table Data Structures}
(\path{hash_bkt.c})
shows a set of data structures used in a simple fixed-sized hash
table using chaining and per-hash-bucket locking, and
Figure~\ref{fig:datastruct:Hash-Table Data-Structure Diagram}
diagrams how they fit together.
-The \co{hashtab} structure (lines~11-14 in
+The \co{hashtab} structure (lines~\lnref{tab:b}-\lnref{tab:e} in
Listing~\ref{lst:datastruct:Hash-Table Data Structures})
-contains four \co{ht_bucket} structures (lines~6-9 in
+contains four \co{ht_bucket} structures
+(lines~\lnref{bucket:b}-\lnref{bucket:e} in
Listing~\ref{lst:datastruct:Hash-Table Data Structures}),
-with the \co{->ht_nbuckets} field controlling the number of buckets.
+with the \co{->ht_nbuckets} field controlling the number of buckets
+and the \co{->ht_cmp} field holding the pointer to key-comparison
+function.
Each such bucket contains a list header \co{->htb_head} and
a lock \co{->htb_lock}.
The list headers chain \co{ht_elem} structures
-(lines~1-4 in
+(lines~\lnref{elem:b}-\lnref{elem:e} in
Listing~\ref{lst:datastruct:Hash-Table Data Structures})
through their
\co{->hte_next} fields, and each \co{ht_elem} structure also caches
@@ -194,99 +179,64 @@ the corresponding element's hash value in the \co{->hte_hash} field.
The \co{ht_elem} structure would be included in the larger structure
being placed in the hash table, and this larger structure might contain
a complex key.
+\end{lineref}
The diagram shown in
Figure~\ref{fig:datastruct:Hash-Table Data-Structure Diagram}
has bucket~0 with two elements and bucket~2 with one.
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 #define HASH2BKT(htp, h) \
- 2 (&(htp)->ht_bkt[h % (htp)->ht_nbuckets])
- 3
- 4 static void hashtab_lock(struct hashtab *htp,
- 5 unsigned long hash)
- 6 {
- 7 spin_lock(&HASH2BKT(htp, hash)->htb_lock);
- 8 }
- 9
-10 static void hashtab_unlock(struct hashtab *htp,
-11 unsigned long hash)
-12 {
-13 spin_unlock(&HASH2BKT(htp, hash)->htb_lock);
-14 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_bkt@map_lock.fcv}
\caption{Hash-Table Mapping and Locking}
\label{lst:datastruct:Hash-Table Mapping and Locking}
\end{listing}
+\begin{lineref}[ln:datastruct:hash_bkt:map_lock:map]
Listing~\ref{lst:datastruct:Hash-Table Mapping and Locking}
shows mapping and locking functions.
-Lines~1 and~2 show the macro \co{HASH2BKT()}, which maps from a hash value
+Lines~\lnref{b} and~\lnref{e}
+show the macro \co{HASH2BKT()}, which maps from a hash value
to the corresponding \co{ht_bucket} structure.
This macro uses a simple modulus: if more aggressive hashing is required,
the caller needs to implement it when mapping from key to hash value.
The remaining two functions acquire and release the \co{->htb_lock}
corresponding to the specified hash value.
+\end{lineref}
\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(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@lookup.fcv}
\caption{Hash-Table Lookup}
\label{lst:datastruct:Hash-Table Lookup}
\end{listing}
+\begin{lineref}[ln:datastruct:hash_bkt:lookup]
Listing~\ref{lst:datastruct:Hash-Table Lookup}
shows \co{hashtab_lookup()},
which returns a pointer to the element with the specified hash and key if it
exists, or \co{NULL} otherwise.
This function takes both a hash value and a pointer to the key because
this allows users of this function to use arbitrary keys and
-arbitrary hash functions, with the key-comparison function passed in via
-\co{cmp()}, in a manner similar to \co{qsort()}.
-Line~11 maps from the hash value to a pointer to the corresponding
+arbitrary hash functions.
+Line~\lnref{map} maps from the hash value to a pointer to the corresponding
hash bucket.
-Each pass through the loop spanning lines~12-19 examines one element
+Each pass through the loop spanning
+lines~\lnref{loop:b}-\lnref{loop:e} examines one element
of the bucket's hash chain.
-Line~15 checks to see if the hash values match, and if not, line~16
+Line~\lnref{hashmatch} checks to see if the hash values match, and if not,
+line~\lnref{next}
proceeds to the next element.
-Line~17 checks to see if the actual key matches, and if so,
-line~18 returns a pointer to the matching element.
-If no element matches, line~20 returns \co{NULL}.
+Line~\lnref{keymatch} checks to see if the actual key matches, and if so,
+line~\lnref{return} returns a pointer to the matching element.
+If no element matches, line~\lnref{ret_NULL} returns \co{NULL}.
+\end{lineref}
\QuickQuiz{}
- But isn't the double comparison on lines~15-18 in
+ \begin{lineref}[ln:datastruct:hash_bkt:lookup]
+ But isn't the double comparison on
+ lines~\lnref{hashmatch}-\lnref{return} in
Listing~\ref{lst:datastruct:Hash-Table Lookup} inefficient
in the case where the key fits into an unsigned long?
+ \end{lineref}
\QuickQuizAnswer{
Indeed it is!
However, hash tables quite frequently store information with
@@ -298,26 +248,7 @@ If no element matches, line~20 returns \co{NULL}.
} \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(&htep->hte_next,
- 8 &HASH2BKT(htp, hash)->htb_head);
- 9 }
-10
-11 void hashtab_del(struct ht_elem *htep)
-12 {
-13 cds_list_del_init(&htep->hte_next);
-14 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_bkt@add_del.fcv}
\caption{Hash-Table Modification}
\label{lst:datastruct:Hash-Table Modification}
\end{listing}
@@ -326,9 +257,11 @@ Listing~\ref{lst:datastruct:Hash-Table Modification}
shows the \co{hashtab_add()} and \co{hashtab_del()} functions
that add and delete elements from the hash table, respectively.
+\begin{lineref}[ln:datastruct:hash_bkt:add_del:add]
The \co{hashtab_add()} function simply sets the element's hash
-value on line~6, then adds it to the corresponding bucket on
-lines~7 and~8.
+value on line~\lnref{set}, then adds it to the corresponding bucket on
+lines~\lnref{add:b} and~\lnref{add:e}.
+\end{lineref}
The \co{hashtab_del()} function simply removes the specified element
from whatever hash chain it is on, courtesy of the doubly linked
nature of the hash-chain lists.
@@ -338,35 +271,7 @@ or modifying this same bucket, for example, by invoking
\co{hashtab_lock()} beforehand.
\begin{listing}[tb]
-{ \scriptsize
-\begin{verbbox}
- 1 struct hashtab *
- 2 hashtab_alloc(unsigned long nbuckets)
- 3 {
- 4 struct hashtab *htp;
- 5 int i;
- 6
- 7 htp = malloc(sizeof(*htp) +
- 8 nbuckets *
- 9 sizeof(struct ht_bucket));
-10 if (htp == NULL)
-11 return NULL;
-12 htp->ht_nbuckets = nbuckets;
-13 for (i = 0; i < nbuckets; i++) {
-14 CDS_INIT_LIST_HEAD(&htp->ht_bkt[i].htb_head);
-15 spin_lock_init(&htp->ht_bkt[i].htb_lock);
-16 }
-17 return htp;
-18 }
-19
-20 void hashtab_free(struct hashtab *htp)
-21 {
-22 free(htp);
-23 }
-\end{verbbox}
-}
-\centering
-\theverbbox
+\input{CodeSamples/datastruct/hash/hash_bkt@alloc_free.fcv}
\caption{Hash-Table Allocation and Free}
\label{lst:datastruct:Hash-Table Allocation and Free}
\end{listing}
@@ -374,14 +279,24 @@ or modifying this same bucket, for example, by invoking
Listing~\ref{lst:datastruct:Hash-Table Allocation and Free}
shows \co{hashtab_alloc()} and \co{hashtab_free()},
which do hash-table allocation and freeing, respectively.
-Allocation begins on lines~7-9 with allocation of the underlying memory.
-If line~10 detects that memory has been exhausted, line~11 returns
+\begin{lineref}[ln:datastruct:hash_bkt:alloc_free:alloc]
+Allocation begins on
+lines~\lnref{alloc:b}-\lnref{alloc:e} with allocation of the underlying memory.
+If line~\lnref{chk_NULL} detects that memory has been exhausted,
+line~\lnref{ret_NULL} returns
\co{NULL} to the caller.
-Otherwise, line~12 initializes the number of buckets, and the loop
-spanning lines~13-16 initializes the buckets themselves,
-including the chain list header on line~14 and the lock on line~15.
-Finally, line~17 returns a pointer to the newly allocated hash table.
-The \co{hashtab_free()} function on lines~20-23 is straightforward.
+Otherwise, lines~\lnref{set_nbck} and~\lnref{set_cmp} initialize
+the number of buckets and the pointer to key-comparison function,
+and the loop
+spanning lines~\lnref{loop:b}-\lnref{loop:e} initializes the buckets themselves,
+including the chain list header on
+line~\lnref{init_head} and the lock on line~\lnref{init_lock}.
+Finally, line~\lnref{return} returns a pointer to the newly allocated hash table.
+\end{lineref}
+\begin{lineref}[ln:datastruct:hash_bkt:alloc_free:free]
+The \co{hashtab_free()} function on
+lines~\lnref{b}-\lnref{e} is straightforward.
+\end{lineref}
\subsection{Hash-Table Performance}
\label{sec:datastruct:Hash-Table Performance}
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 07/11] datastruct: Update hashdiagram figure
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (5 preceding siblings ...)
2018-12-24 15:00 ` [PATCH 06/11] datastruct: Employ new scheme for snippets of hash_bkt.c Akira Yokosawa
@ 2018-12-24 15:01 ` Akira Yokosawa
2018-12-24 15:02 ` [PATCH 08/11] datastruct: Employ new scheme for snippets of hash_bkt_rcu and hash_resize Akira Yokosawa
` (4 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 15:01 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 075c5f2affb207010d7c5e7d5cd7ee3233fa060a Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 15:23:43 +0900
Subject: [PATCH 07/11] datastruct: Update hashdiagram figure
Add ht_cmp field to struct hashtab.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
datastruct/hashdiagram.fig | 103 +++++++++++++++++++++++----------------------
1 file changed, 53 insertions(+), 50 deletions(-)
diff --git a/datastruct/hashdiagram.fig b/datastruct/hashdiagram.fig
index bfdfdad..15e3cbb 100644
--- a/datastruct/hashdiagram.fig
+++ b/datastruct/hashdiagram.fig
@@ -1,4 +1,4 @@
-#FIG 3.2 Produced by xfig version 3.2.5b
+#FIG 3.2 Produced by xfig version 3.2.5c
Landscape
Center
Inches
@@ -8,69 +8,72 @@ Single
-2
1200 2
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+ 1650 1875 2625 1875 2625 2475 1650 2475 1650 1875
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+ 1725 2100 2625 2100 2625 2475 1725 2475 1725 2100
+2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
+ 0 0 1.00 60.00 120.00
+ 0 0 1.00 60.00 120.00
+ 1200 2250 1650 2250
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
75 225 1200 225 1200 450 75 450 75 225
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 0 0 1200 0 1200 2850 0 2850 0 0
+ 150 900 1200 900 1200 1275 150 1275 150 900
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 75 2250 1200 2250 1200 2850 75 2850 75 2250
+ 150 2700 1200 2700 1200 3075 150 3075 150 2700
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 150 2475 1200 2475 1200 2850 150 2850 150 2475
+ 75 2475 1200 2475 1200 3075 75 3075 75 2475
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 75 1650 1200 1650 1200 2250 75 2250 75 1650
+ 75 1875 1200 1875 1200 2475 75 2475 75 1875
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 150 1875 1200 1875 1200 2250 150 2250 150 1875
+ 150 2100 1200 2100 1200 2475 150 2475 150 2100
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 75 1050 1200 1050 1200 1650 75 1650 75 1050
+ 75 1275 1200 1275 1200 1875 75 1875 75 1275
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 150 1275 1200 1275 1200 1650 150 1650 150 1275
+ 150 1500 1200 1500 1200 1875 150 1875 150 1500
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 75 450 1200 450 1200 1050 75 1050 75 450
+ 75 675 1200 675 1200 1275 75 1275 75 675
2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 150 675 1200 675 1200 1050 150 1050 150 675
-2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
- 0 0 1.00 60.00 120.00
- 0 0 1.00 60.00 120.00
- 1200 825 1650 825
+ 75 450 1200 450 1200 675 75 675 75 450
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+ 0 0 1200 0 1200 3075 0 3075 0 0
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+ 1650 675 2625 675 2625 1275 1650 1275 1650 675
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+ 1725 900 2625 900 2625 1275 1725 1275 1725 900
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+ 3075 675 4050 675 4050 1275 3075 1275 3075 675
+2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+ 3150 900 4050 900 4050 1275 3150 1275 3150 900
2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
0 0 1.00 60.00 120.00
0 0 1.00 60.00 120.00
- 2625 825 3075 825
+ 1200 1050 1650 1050
2 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 1 2
0 0 1.00 60.00 120.00
0 0 1.00 60.00 120.00
- 1200 2025 1650 2025
-2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 1650 1650 2625 1650 2625 2250 1650 2250 1650 1650
-2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 1725 1875 2625 1875 2625 2250 1725 2250 1725 1875
-2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 1650 450 2625 450 2625 1050 1650 1050 1650 450
-2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 1725 675 2625 675 2625 1050 1725 1050 1725 675
-2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 3075 450 4050 450 4050 1050 3075 1050 3075 450
-2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
- 3150 675 4050 675 4050 1050 3150 1050 3150 675
+ 2625 1050 3075 1050
4 0 0 50 -1 20 9 0.0000 4 135 1260 75 150 struct hashtab\001
-4 0 0 50 -1 20 9 0.0000 4 150 1530 150 345 ->ht_nbuckets = 4\001
-4 0 0 50 -1 20 9 0.0000 4 165 990 150 2400 ->ht_bkt[3]\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 2625 ->htb_head\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 2775 ->htb_lock\001
-4 0 0 50 -1 20 9 0.0000 4 165 990 150 1800 ->ht_bkt[2]\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 2025 ->htb_head\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 2175 ->htb_lock\001
-4 0 0 50 -1 20 9 0.0000 4 165 990 150 1200 ->ht_bkt[1]\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 1425 ->htb_head\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 1575 ->htb_lock\001
-4 0 0 50 -1 20 9 0.0000 4 165 990 150 600 ->ht_bkt[0]\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 825 ->htb_head\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 225 975 ->htb_lock\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 1800 2025 ->hte_next\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 1800 2175 ->hte_hash\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 1800 825 ->hte_next\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 1800 975 ->hte_hash\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 3225 825 ->hte_next\001
-4 0 0 50 -1 20 9 0.0000 4 150 900 3225 975 ->hte_hash\001
-4 0 0 50 -1 20 9 0.0000 4 150 1260 1725 600 struct ht_elem\001
-4 0 0 50 -1 20 9 0.0000 4 150 1260 3150 600 struct ht_elem\001
-4 0 0 50 -1 20 9 0.0000 4 150 1260 1725 1800 struct ht_elem\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 1800 2400 ->hte_hash\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 1800 2250 ->hte_next\001
+4 0 0 50 -1 20 9 0.0000 4 150 1260 1725 2025 struct ht_elem\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 3000 ->htb_lock\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 2850 ->htb_head\001
+4 0 0 50 -1 20 9 0.0000 4 165 990 150 2625 ->ht_bkt[3]\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 2400 ->htb_lock\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 2250 ->htb_head\001
+4 0 0 50 -1 20 9 0.0000 4 165 990 150 2025 ->ht_bkt[2]\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 1800 ->htb_lock\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 1650 ->htb_head\001
+4 0 0 50 -1 20 9 0.0000 4 165 990 150 1425 ->ht_bkt[1]\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 1200 ->htb_lock\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 225 1050 ->htb_head\001
+4 0 0 50 -1 20 9 0.0000 4 165 990 150 825 ->ht_bkt[0]\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 1800 1200 ->hte_hash\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 1800 1050 ->hte_next\001
+4 0 0 50 -1 20 9 0.0000 4 150 1260 1725 825 struct ht_elem\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 3225 1200 ->hte_hash\001
+4 0 0 50 -1 20 9 0.0000 4 150 900 3225 1050 ->hte_next\001
+4 0 0 50 -1 20 9 0.0000 4 150 1260 3150 825 struct ht_elem\001
+4 0 0 50 -1 20 9 0.0000 4 165 720 150 600 ->ht_cmp\001
+4 0 0 50 -1 20 9 0.0000 4 150 1530 150 375 ->ht_nbuckets = 4\001
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 08/11] datastruct: Employ new scheme for snippets of hash_bkt_rcu and hash_resize
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (6 preceding siblings ...)
2018-12-24 15:01 ` [PATCH 07/11] datastruct: Update hashdiagram figure Akira Yokosawa
@ 2018-12-24 15:02 ` Akira Yokosawa
2018-12-24 15:03 ` [PATCH 09/11] Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env Akira Yokosawa
` (3 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 15:02 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From e94531367e4c5bc66a7cabe2e1e41e80dedf5a53 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
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@gmail.com>
---
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@lookup.fcv}
\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@data.fcv}
\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@access.fcv}
\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@resize.fcv}
\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
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 09/11] Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (7 preceding siblings ...)
2018-12-24 15:02 ` [PATCH 08/11] datastruct: Employ new scheme for snippets of hash_bkt_rcu and hash_resize Akira Yokosawa
@ 2018-12-24 15:03 ` Akira Yokosawa
2018-12-24 15:04 ` [PATCH 10/11] Use wider tabsize for snippet in 'listing*' Akira Yokosawa
` (2 subsequent siblings)
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 15:03 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 6267c0822e5286667e3cc0dc873e79bafd4b4bb6 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 23:45:40 +0900
Subject: [PATCH 09/11] Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
perfbook.tex | 2 ++
1 file changed, 2 insertions(+)
diff --git a/perfbook.tex b/perfbook.tex
index 6784771..ce85570 100644
--- a/perfbook.tex
+++ b/perfbook.tex
@@ -129,6 +129,8 @@
\AtBeginEnvironment{tabularx}{\renewcommand{\ttdefault}{lmtt}}
\AtBeginEnvironment{minipage}{\renewcommand{\ttdefault}{lmtt}}
\AtBeginEnvironment{listing}{\renewcommand{\ttdefault}{lmtt}}
+\AtBeginEnvironment{Verbatim}{\renewcommand{\ttdefault}{lmtt}}
+\AtBeginEnvironment{VerbatimL}{\renewcommand{\ttdefault}{lmtt}}
\AtBeginEnvironment{VerbatimN}{\renewcommand{\ttdefault}{lmtt}}
\AtBeginEnvironment{VerbatimU}{\renewcommand{\ttdefault}{lmtt}}
}{}
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 10/11] Use wider tabsize for snippet in 'listing*'
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (8 preceding siblings ...)
2018-12-24 15:03 ` [PATCH 09/11] Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env Akira Yokosawa
@ 2018-12-24 15:04 ` Akira Yokosawa
2018-12-24 15:05 ` [PATCH 11/11] datastruct: Tweak hyphenation Akira Yokosawa
2018-12-24 23:58 ` [PATCH 00/11] datastruct: Employ new scheme for code snippet Paul E. McKenney
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 15:04 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From deac40976c6104677a6ede3b13f8aa4361ecabbd Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sun, 23 Dec 2018 23:46:38 +0900
Subject: [PATCH 10/11] Use wider tabsize for snippet in 'listing*'
tabsize=6 looks good for this particular listing.
tabsize=8 is too wide for 1c layout.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/datastruct/hash/hash_resize.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index 285075e..662bb90 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -262,7 +262,7 @@ void hashtab_del(struct hashtab *htp_master, //\lnlbl{del:b}
} //\lnlbl{del:e}
//\end{snippet}
-//\begin{snippet}[labelbase=ln:datastruct:hash_resize:resize,commandchars=\\\@\$]
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:resize,commandchars=\\\@\$,tabsize=6]
/* Resize a hash table. */
int hashtab_resize(struct hashtab *htp_master,
unsigned long nbuckets, void *hash_private,
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 11/11] datastruct: Tweak hyphenation
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (9 preceding siblings ...)
2018-12-24 15:04 ` [PATCH 10/11] Use wider tabsize for snippet in 'listing*' Akira Yokosawa
@ 2018-12-24 15:05 ` Akira Yokosawa
2018-12-24 23:58 ` [PATCH 00/11] datastruct: Employ new scheme for code snippet Paul E. McKenney
11 siblings, 0 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-24 15:05 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 2d807fdaa140d87199167b78bb53e805cae5eb94 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Mon, 24 Dec 2018 20:02:14 +0900
Subject: [PATCH 11/11] datastruct: Tweak hyphenation
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
datastruct/datastruct.tex | 2 +-
pfhyphex.tex | 1 +
2 files changed, 2 insertions(+), 1 deletion(-)
diff --git a/datastruct/datastruct.tex b/datastruct/datastruct.tex
index f75b42b..f8add0b 100644
--- a/datastruct/datastruct.tex
+++ b/datastruct/datastruct.tex
@@ -1031,7 +1031,7 @@ with a resize operation.
Read-side concurrency control is provided by RCU as was shown in
Listing~\ref{lst:datastruct:RCU-Protected Hash-Table Read-Side Concurrency Control},
-but the update-side concurrency-control functions
+but the update-side concurrency\-/control functions
\co{hashtab_lock_mod()} and \co{hashtab_unlock_mod()}
must now deal with the possibility of a
concurrent resize operation as shown in
diff --git a/pfhyphex.tex b/pfhyphex.tex
index fbcae67..1f319d4 100644
--- a/pfhyphex.tex
+++ b/pfhyphex.tex
@@ -3,4 +3,5 @@
COPART
GPGPU
GPGPUs
+ Schr\"o-din-ger
}
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* Re: [PATCH 00/11] datastruct: Employ new scheme for code snippet
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
` (10 preceding siblings ...)
2018-12-24 15:05 ` [PATCH 11/11] datastruct: Tweak hyphenation Akira Yokosawa
@ 2018-12-24 23:58 ` Paul E. McKenney
2018-12-25 0:53 ` Paul E. McKenney
11 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2018-12-24 23:58 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Mon, Dec 24, 2018 at 11:46:23PM +0900, Akira Yokosawa wrote:
> Hi Paul,
>
> This patch set consists of enhancement of fcvextract.pl,
> update of snippets in datastruct, and some minor tweaks.
>
> fcvextract.pl now suppresses comment blocks in C source and
> supports alternative code for snippets in #ifndef blocks,
> which won't be affected by the suppression of comment blocks.
>
> Also, labeling of the form /* \lnlbl{label} */ is now supported
> in C snippets.
>
> Patch #1 adds comment block handling to fcvextract.pl, without
> changing the default behavior.
>
> Patch #2 adds a couple of explicit options to snippets which
> have comments to be displayed. It also converts alternative
> code fragments using "#ifndef FCV_EXCLUDE" so that they survive
> comment block suppression.
>
> Patch #3 changes the default to "keepcomment=no".
> This removes a couple of comments in Listings 4.8 and 9.5.
>
> Patch #4 removes now redundant "\fcvexclude" around comment
> blocks. It also uses "#ifndef FCV_SNIPPET" to reduce \fcvexclude
> uses.
>
> Patch #5 adds support of "/* \lnlbl{label} */" labeling.
>
> Patch #6 updates snippets of hash_bkt.c. "struct hashtab"
> now has the "ht_cmp" field and I updated the text to mention
> it. You might want to do some rewording.
Looks good to me as is.
> Patch #7 adds the "ht_cmp" field in the hashdiagram figure
> (still in .fig).
>
> Patch #8 updates the rest of snippets in datastruct. It also
> fixes typo in cross references of Listing 10.13.
> By this change, an smp_mb() appears in ht_get_bucket()
> (Listing 10.10).
>
> My guess is that the counterpart barrier is the first
> synchronize_rcu() in hashtab_resize(). It might deserve some
> explanation or a Quick Quiz. Also, Answer to Quick Quiz 10.13
> might need some expansion, since it looks as though hash_reorder.c
> used something more than the pure RCU protection. But I might be
> completely misreading here...
I think I have a bug...
So am I smarter now than when I wrote that code, or vice versa? ;-)
> Patches #9 and #10 are minor tweaks in appearance of
> Listing 10.13. As you can see, tab-space width can be
> adjusted per snippet.
>
> Patch #11 permits more chances of hyphenation.
>
> I'm thinking of globally widening tab space of snippets for
> 1C layout. Let me do some experiment.
Sounds good!
And queued and pushed the group.
Thanx, Paul
> Thanks, Akira
> --
> Akira Yokosawa (11):
> fcvextract.pl: Enhance comment block handling of C source
> CodeSamples: Add explicit 'keepcomment=yes' options
> fcvextract.pl: Make 'keepcomment=no' as default
> CodeSamples: Remove redundant \fcvexclude
> fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source
> datastruct: Employ new scheme for snippets of hash_bkt.c
> datastruct: Update hashdiagram figure
> datastruct: Employ new scheme for snippets of hash_bkt_rcu and
> hash_resize
> Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env
> Use wider tabsize for snippet in 'listing*'
> datastruct: Tweak hyphenation
>
> CodeSamples/SMPdesign/lockhdeq.c | 11 +-
> CodeSamples/SMPdesign/smpalloc.c | 8 +-
> CodeSamples/count/count_end.c | 8 +-
> CodeSamples/count/count_lim.c | 8 +-
> CodeSamples/count/count_tstat.c | 10 +-
> CodeSamples/datastruct/hash/hash_bkt.c | 96 ++--
> CodeSamples/datastruct/hash/hash_bkt_rcu.c | 33 +-
> CodeSamples/datastruct/hash/hash_resize.c | 232 +++++-----
> CodeSamples/defer/route_hazptr.c | 20 +-
> CodeSamples/defer/route_rcu.c | 36 +-
> CodeSamples/defer/route_refcnt.c | 16 +-
> CodeSamples/defer/route_seq.c | 18 +-
> CodeSamples/defer/route_seqlock.c | 14 +-
> CodeSamples/defer/seqlock.h | 12 +-
> CodeSamples/locking/locked_list.c | 6 +-
> CodeSamples/toolsoftrade/forkjoinvar.c | 2 +-
> CodeSamples/toolsoftrade/pcreate.c | 2 +-
> datastruct/datastruct.tex | 687 ++++++++---------------------
> datastruct/hashdiagram.fig | 103 ++---
> perfbook.tex | 2 +
> pfhyphex.tex | 1 +
> utilities/fcvextract.pl | 87 +++-
> 22 files changed, 627 insertions(+), 785 deletions(-)
>
> --
> 2.7.4
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH 00/11] datastruct: Employ new scheme for code snippet
2018-12-24 23:58 ` [PATCH 00/11] datastruct: Employ new scheme for code snippet Paul E. McKenney
@ 2018-12-25 0:53 ` Paul E. McKenney
2018-12-25 14:30 ` Akira Yokosawa
0 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2018-12-25 0:53 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Mon, Dec 24, 2018 at 03:58:32PM -0800, Paul E. McKenney wrote:
> On Mon, Dec 24, 2018 at 11:46:23PM +0900, Akira Yokosawa wrote:
> > Hi Paul,
> >
> > This patch set consists of enhancement of fcvextract.pl,
> > update of snippets in datastruct, and some minor tweaks.
> >
> > fcvextract.pl now suppresses comment blocks in C source and
> > supports alternative code for snippets in #ifndef blocks,
> > which won't be affected by the suppression of comment blocks.
> >
> > Also, labeling of the form /* \lnlbl{label} */ is now supported
> > in C snippets.
> >
> > Patch #1 adds comment block handling to fcvextract.pl, without
> > changing the default behavior.
> >
> > Patch #2 adds a couple of explicit options to snippets which
> > have comments to be displayed. It also converts alternative
> > code fragments using "#ifndef FCV_EXCLUDE" so that they survive
> > comment block suppression.
> >
> > Patch #3 changes the default to "keepcomment=no".
> > This removes a couple of comments in Listings 4.8 and 9.5.
> >
> > Patch #4 removes now redundant "\fcvexclude" around comment
> > blocks. It also uses "#ifndef FCV_SNIPPET" to reduce \fcvexclude
> > uses.
> >
> > Patch #5 adds support of "/* \lnlbl{label} */" labeling.
> >
> > Patch #6 updates snippets of hash_bkt.c. "struct hashtab"
> > now has the "ht_cmp" field and I updated the text to mention
> > it. You might want to do some rewording.
>
> Looks good to me as is.
>
> > Patch #7 adds the "ht_cmp" field in the hashdiagram figure
> > (still in .fig).
> >
> > Patch #8 updates the rest of snippets in datastruct. It also
> > fixes typo in cross references of Listing 10.13.
> > By this change, an smp_mb() appears in ht_get_bucket()
> > (Listing 10.10).
> >
> > My guess is that the counterpart barrier is the first
> > synchronize_rcu() in hashtab_resize(). It might deserve some
> > explanation or a Quick Quiz. Also, Answer to Quick Quiz 10.13
> > might need some expansion, since it looks as though hash_reorder.c
> > used something more than the pure RCU protection. But I might be
> > completely misreading here...
>
> I think I have a bug...
>
> So am I smarter now than when I wrote that code, or vice versa? ;-)
I believe that I am smarter now, or maybe just more deluded. Anyway,
when I changed the code, I go this from the top-level Makefile:
$ make
sh ./utilities/gen_snippet_d.sh
sh utilities/autodate.sh >autodate.tex
CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@data.fcv
utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:data > CodeSamples/datastruct/hash/hash_resize@data.fcv
CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:get_bucket > CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:lock_unlock_mod > CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@access.fcv
utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:access > CodeSamples/datastruct/hash/hash_resize@access.fcv
CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@resize.fcv
utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:resize > CodeSamples/datastruct/hash/hash_resize@resize.fcv
CodeSamples/datastruct/hash/.hash_resize.c.swp --> CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
utilities/fcvextract.pl CodeSamples/datastruct/hash/.hash_resize.c.swp hash > CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
/bin/bash: CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv: No such file or directory
make: *** [CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv] Error 1
Using "make clean" didn't fix it. Neither did reverting my change
to CodeSamples/datastruct/hash/hash_resize.c, which is shown below.
Ah, I get it now. I had CodeSamples/datastruct/hash/hash_resize.c
open in vim, and the scripting attempted to process the resulting
.hash_resize.c.swp file from vim. Things started working again after
I exited from vim.
Thanx, Paul
------------------------------------------------------------------------
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index 662bb90bff14..ccb523bb6c05 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -298,13 +298,14 @@ int hashtab_resize(struct hashtab *htp_master,
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);
spin_unlock(&htbp_new->htb_lock);
} //\lnlbl{loop_list:e}
+ smp_mb(); /* Fill new buckets before claiming them. */
+ htp->ht_resize_cur = i; //\lnlbl{update_resize}
spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
} //\lnlbl{loop:e}
rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
^ permalink raw reply related [flat|nested] 37+ messages in thread
* Re: [PATCH 00/11] datastruct: Employ new scheme for code snippet
2018-12-25 0:53 ` Paul E. McKenney
@ 2018-12-25 14:30 ` Akira Yokosawa
2018-12-26 14:17 ` Paul E. McKenney
2018-12-26 14:31 ` [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files Akira Yokosawa
0 siblings, 2 replies; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-25 14:30 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
On 2018/12/25 9:53, Paul E. McKenney wrote:
> On Mon, Dec 24, 2018 at 03:58:32PM -0800, Paul E. McKenney wrote:
>> On Mon, Dec 24, 2018 at 11:46:23PM +0900, Akira Yokosawa wrote:
>>> Hi Paul,
>>>
>>> This patch set consists of enhancement of fcvextract.pl,
>>> update of snippets in datastruct, and some minor tweaks.
>>>
>>> fcvextract.pl now suppresses comment blocks in C source and
>>> supports alternative code for snippets in #ifndef blocks,
>>> which won't be affected by the suppression of comment blocks.
>>>
>>> Also, labeling of the form /* \lnlbl{label} */ is now supported
>>> in C snippets.
>>>
>>> Patch #1 adds comment block handling to fcvextract.pl, without
>>> changing the default behavior.
>>>
>>> Patch #2 adds a couple of explicit options to snippets which
>>> have comments to be displayed. It also converts alternative
>>> code fragments using "#ifndef FCV_EXCLUDE" so that they survive
>>> comment block suppression.
>>>
>>> Patch #3 changes the default to "keepcomment=no".
>>> This removes a couple of comments in Listings 4.8 and 9.5.
>>>
>>> Patch #4 removes now redundant "\fcvexclude" around comment
>>> blocks. It also uses "#ifndef FCV_SNIPPET" to reduce \fcvexclude
>>> uses.
>>>
>>> Patch #5 adds support of "/* \lnlbl{label} */" labeling.
>>>
>>> Patch #6 updates snippets of hash_bkt.c. "struct hashtab"
>>> now has the "ht_cmp" field and I updated the text to mention
>>> it. You might want to do some rewording.
>>
>> Looks good to me as is.
>>
>>> Patch #7 adds the "ht_cmp" field in the hashdiagram figure
>>> (still in .fig).
>>>
>>> Patch #8 updates the rest of snippets in datastruct. It also
>>> fixes typo in cross references of Listing 10.13.
>>> By this change, an smp_mb() appears in ht_get_bucket()
>>> (Listing 10.10).
>>>
>>> My guess is that the counterpart barrier is the first
>>> synchronize_rcu() in hashtab_resize(). It might deserve some
>>> explanation or a Quick Quiz. Also, Answer to Quick Quiz 10.13
>>> might need some expansion, since it looks as though hash_reorder.c
>>> used something more than the pure RCU protection. But I might be
>>> completely misreading here...
>>
>> I think I have a bug...
>>
>> So am I smarter now than when I wrote that code, or vice versa? ;-)
>
> I believe that I am smarter now, or maybe just more deluded. Anyway,
> when I changed the code, I go this from the top-level Makefile:
>
> $ make
> sh ./utilities/gen_snippet_d.sh
> sh utilities/autodate.sh >autodate.tex
> CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@data.fcv
> utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:data > CodeSamples/datastruct/hash/hash_resize@data.fcv
> CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
> utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:get_bucket > CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
> CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
> utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:lock_unlock_mod > CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
> CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@access.fcv
> utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:access > CodeSamples/datastruct/hash/hash_resize@access.fcv
> CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@resize.fcv
> utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:resize > CodeSamples/datastruct/hash/hash_resize@resize.fcv
> CodeSamples/datastruct/hash/.hash_resize.c.swp --> CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> utilities/fcvextract.pl CodeSamples/datastruct/hash/.hash_resize.c.swp hash > CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> /bin/bash: CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv: No such file or directory
> make: *** [CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv] Error 1
>
> Using "make clean" didn't fix it. Neither did reverting my change
> to CodeSamples/datastruct/hash/hash_resize.c, which is shown below.
>
> Ah, I get it now. I had CodeSamples/datastruct/hash/hash_resize.c
> open in vim, and the scripting attempted to process the resulting
> .hash_resize.c.swp file from vim. Things started working again after
> I exited from vim.
I see.
I'll add rules in utilities/gen_snippet_d.pl so that those .swp files
will be excluded from the search result.
BTW, the new Quick Quiz 10.14 sounds somewhat inconsistent with
Quick Quiz 10.13 and its answer, doesn't it?
Or am I missing something?
Thanks, Akira
>
> Thanx, Paul
>
> ------------------------------------------------------------------------
>
> diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> index 662bb90bff14..ccb523bb6c05 100644
> --- a/CodeSamples/datastruct/hash/hash_resize.c
> +++ b/CodeSamples/datastruct/hash/hash_resize.c
> @@ -298,13 +298,14 @@ int hashtab_resize(struct hashtab *htp_master,
> 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);
> spin_unlock(&htbp_new->htb_lock);
> } //\lnlbl{loop_list:e}
> + smp_mb(); /* Fill new buckets before claiming them. */
> + htp->ht_resize_cur = i; //\lnlbl{update_resize}
> spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
> } //\lnlbl{loop:e}
> rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH 00/11] datastruct: Employ new scheme for code snippet
2018-12-25 14:30 ` Akira Yokosawa
@ 2018-12-26 14:17 ` Paul E. McKenney
2018-12-26 14:31 ` [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files Akira Yokosawa
1 sibling, 0 replies; 37+ messages in thread
From: Paul E. McKenney @ 2018-12-26 14:17 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Tue, Dec 25, 2018 at 11:30:44PM +0900, Akira Yokosawa wrote:
> On 2018/12/25 9:53, Paul E. McKenney wrote:
> > On Mon, Dec 24, 2018 at 03:58:32PM -0800, Paul E. McKenney wrote:
> >> On Mon, Dec 24, 2018 at 11:46:23PM +0900, Akira Yokosawa wrote:
> >>> Hi Paul,
> >>>
> >>> This patch set consists of enhancement of fcvextract.pl,
> >>> update of snippets in datastruct, and some minor tweaks.
> >>>
> >>> fcvextract.pl now suppresses comment blocks in C source and
> >>> supports alternative code for snippets in #ifndef blocks,
> >>> which won't be affected by the suppression of comment blocks.
> >>>
> >>> Also, labeling of the form /* \lnlbl{label} */ is now supported
> >>> in C snippets.
> >>>
> >>> Patch #1 adds comment block handling to fcvextract.pl, without
> >>> changing the default behavior.
> >>>
> >>> Patch #2 adds a couple of explicit options to snippets which
> >>> have comments to be displayed. It also converts alternative
> >>> code fragments using "#ifndef FCV_EXCLUDE" so that they survive
> >>> comment block suppression.
> >>>
> >>> Patch #3 changes the default to "keepcomment=no".
> >>> This removes a couple of comments in Listings 4.8 and 9.5.
> >>>
> >>> Patch #4 removes now redundant "\fcvexclude" around comment
> >>> blocks. It also uses "#ifndef FCV_SNIPPET" to reduce \fcvexclude
> >>> uses.
> >>>
> >>> Patch #5 adds support of "/* \lnlbl{label} */" labeling.
> >>>
> >>> Patch #6 updates snippets of hash_bkt.c. "struct hashtab"
> >>> now has the "ht_cmp" field and I updated the text to mention
> >>> it. You might want to do some rewording.
> >>
> >> Looks good to me as is.
> >>
> >>> Patch #7 adds the "ht_cmp" field in the hashdiagram figure
> >>> (still in .fig).
> >>>
> >>> Patch #8 updates the rest of snippets in datastruct. It also
> >>> fixes typo in cross references of Listing 10.13.
> >>> By this change, an smp_mb() appears in ht_get_bucket()
> >>> (Listing 10.10).
> >>>
> >>> My guess is that the counterpart barrier is the first
> >>> synchronize_rcu() in hashtab_resize(). It might deserve some
> >>> explanation or a Quick Quiz. Also, Answer to Quick Quiz 10.13
> >>> might need some expansion, since it looks as though hash_reorder.c
> >>> used something more than the pure RCU protection. But I might be
> >>> completely misreading here...
> >>
> >> I think I have a bug...
> >>
> >> So am I smarter now than when I wrote that code, or vice versa? ;-)
> >
> > I believe that I am smarter now, or maybe just more deluded. Anyway,
> > when I changed the code, I go this from the top-level Makefile:
> >
> > $ make
> > sh ./utilities/gen_snippet_d.sh
> > sh utilities/autodate.sh >autodate.tex
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@data.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:data > CodeSamples/datastruct/hash/hash_resize@data.fcv
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:get_bucket > CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:lock_unlock_mod > CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@access.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:access > CodeSamples/datastruct/hash/hash_resize@access.fcv
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@resize.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:resize > CodeSamples/datastruct/hash/hash_resize@resize.fcv
> > CodeSamples/datastruct/hash/.hash_resize.c.swp --> CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/.hash_resize.c.swp hash > CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> > /bin/bash: CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv: No such file or directory
> > make: *** [CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv] Error 1
> >
> > Using "make clean" didn't fix it. Neither did reverting my change
> > to CodeSamples/datastruct/hash/hash_resize.c, which is shown below.
> >
> > Ah, I get it now. I had CodeSamples/datastruct/hash/hash_resize.c
> > open in vim, and the scripting attempted to process the resulting
> > .hash_resize.c.swp file from vim. Things started working again after
> > I exited from vim.
>
> I see.
>
> I'll add rules in utilities/gen_snippet_d.pl so that those .swp files
> will be excluded from the search result.
Another alternative would be to exclude filenames beginning with ".".
But emacs and so on have other rules. :-/
> BTW, the new Quick Quiz 10.14 sounds somewhat inconsistent with
> Quick Quiz 10.13 and its answer, doesn't it?
>
> Or am I missing something?
Maybe that hashtab_lookup(), hashtab_add(), and hashtab_del() must
all be invoked within RCU read-side critical sections? These critical
sections, in conjunction with hashtab_resize()'s first synchronize_rcu(),
ensure that any "reader" seeing a non-negative value of ->ht_resize-cur
also sees non-NULL ->ht_new. Which is a bit obscure from that quiz's
question.
How about the following?
Quick Quiz 10.13:
In the hashtab_resize() function in Listing 10.13, what
guarantees that the update to ->ht_new on line 28 will be seen as
happening before the update to ->ht_resize_cur on line 42 from the
perspective of hashtab_lookup(), hashtab_add(), and hashtab_del()?
In other words, what prevents hashtab_lookup(), hashtab_add(),
and hashtab_del(), from dereferencing a NULL pointer loaded
from ->ht_new?
Answer:
The synchronize_rcu() on line 29 of Listing 10.13 ensures that
all pre-existing RCU readers have completed between the time
that we install the new hash-table reference on line 28 and the
time that we update ->ht_resize_cur on line 42. This means that
any reader that sees a non-negative value of ->ht_resize_cur
cannot have started before the assignment to ->ht_new, and
thus must be able to see the reference to the new hash table.
And this is why the update-side hashtab_add() and hashtab_del()
functions must nevertheless be enclosed in RCU read-side critical
sections, courtesy of hashtab_lock_mod() and hashtab_unlock_mod()
in Listinglst:datastruct:Resizable Hash-Table Update-Side
Concurrency Control.
Thanx, Paul
> Thanks, Akira
>
> >
> > Thanx, Paul
> >
> > ------------------------------------------------------------------------
> >
> > diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> > index 662bb90bff14..ccb523bb6c05 100644
> > --- a/CodeSamples/datastruct/hash/hash_resize.c
> > +++ b/CodeSamples/datastruct/hash/hash_resize.c
> > @@ -298,13 +298,14 @@ int hashtab_resize(struct hashtab *htp_master,
> > 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);
> > spin_unlock(&htbp_new->htb_lock);
> > } //\lnlbl{loop_list:e}
> > + smp_mb(); /* Fill new buckets before claiming them. */
> > + htp->ht_resize_cur = i; //\lnlbl{update_resize}
> > spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
> > } //\lnlbl{loop:e}
> > rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
> >
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files
2018-12-25 14:30 ` Akira Yokosawa
2018-12-26 14:17 ` Paul E. McKenney
@ 2018-12-26 14:31 ` Akira Yokosawa
2018-12-26 15:00 ` Paul E. McKenney
1 sibling, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-26 14:31 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 6c0e6e632bbf234de340bcf51acf2007d8e3ac8b Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Wed, 26 Dec 2018 23:11:26 +0900
Subject: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files
Excerpt from Paul's report:
$ make
sh ./utilities/gen_snippet_d.sh
sh utilities/autodate.sh >autodate.tex
CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@data.fcv
[...]
CodeSamples/datastruct/hash/.hash_resize.c.swp --> CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
utilities/fcvextract.pl CodeSamples/datastruct/hash/.hash_resize.c.swp hash > CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
/bin/bash: CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv: No such file or directory
make: *** [CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv] Error 1
.hash_resize.c.swp is a swap file of vim, which causes an invalid
dependency rule to be emitted.
To prevent such errors, ignore .swp files as well as emacs' backup
files ending in "~" and "#" from the search results in
gen_snippet_d.pl.
Reported-by: Paul E. McKenney <paulmck@linux.ibm.com>
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
Paul,
This should ignore .swp files in the dependency file.
Can you test "make" while opening hash_resize.c in vim?
Thanks, Akira
PS:
I'll comment on the update of Quick Quiz 10.13 later this week.
--
utilities/gen_snippet_d.pl | 16 ++++++++++------
1 file changed, 10 insertions(+), 6 deletions(-)
diff --git a/utilities/gen_snippet_d.pl b/utilities/gen_snippet_d.pl
index 8ba31b5..e07e58d 100755
--- a/utilities/gen_snippet_d.pl
+++ b/utilities/gen_snippet_d.pl
@@ -17,11 +17,19 @@ my @fcvsources_ltms;
my $snippet_key;
my $snippet_key_ltms;
my $source;
+my @ignore_re;
+my $re;
$snippet_key = '\begin{snippet}' ;
$snippet_key_ltms = '\begin[snippet]' ;
+@ignore_re = ('\.swp$', '~$', '\#$') ; # to ignore backup of vim and emacs
@fcvsources = `grep -l -r -F '$snippet_key' CodeSamples` ;
+@fcvsources = grep { not /\.ltms$/ } @fcvsources ;
@fcvsources_ltms = `grep -l -r -F '$snippet_key_ltms' CodeSamples` ;
+foreach $re (@ignore_re) {
+ @fcvsources = grep { not /$re/ } @fcvsources ;
+ @fcvsources_ltms = grep { not /$re/ } @fcvsources_ltms ;
+}
chomp @fcvsources ;
chomp @fcvsources_ltms ;
@@ -32,9 +40,6 @@ foreach $source (@fcvsources) {
my @snippet_commands1 ;
my $subdir ;
my $snippet ;
- if ($source =~ /\.ltms$/) {
- next;
- }
@snippet_commands1 = `grep -F '$snippet_key' $source` ;
chomp @snippet_commands1 ;
$source =~ m!(.*/[^/]+)/[^/]+! ;
@@ -51,6 +56,7 @@ foreach $source (@fcvsources_ltms) {
my @snippet_commands1 ;
my $subdir ;
my $snippet ;
+
@snippet_commands1 = `grep -F '$snippet_key_ltms' $source` ;
chomp @snippet_commands1 ;
$source =~ m!(.*/[^/]+)/[^/]+! ;
@@ -77,9 +83,7 @@ foreach $source (@fcvsources) {
my $src_under_sub ;
my $subdir ;
my $snippet ;
- if ($source =~ /\.ltms$/) {
- next;
- }
+
@snippet_commands2 = `grep -F '$snippet_key' $source` ;
chomp @snippet_commands2 ;
$src_under_sub = $source ;
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* Re: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files
2018-12-26 14:31 ` [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files Akira Yokosawa
@ 2018-12-26 15:00 ` Paul E. McKenney
2018-12-31 4:37 ` Sporadic SIGSEGV in hash_bkt_rcu and hash_resize (was Re: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files) Akira Yokosawa
0 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2018-12-26 15:00 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Wed, Dec 26, 2018 at 11:31:03PM +0900, Akira Yokosawa wrote:
> >From 6c0e6e632bbf234de340bcf51acf2007d8e3ac8b Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Wed, 26 Dec 2018 23:11:26 +0900
> Subject: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files
>
> Excerpt from Paul's report:
> $ make
> sh ./utilities/gen_snippet_d.sh
> sh utilities/autodate.sh >autodate.tex
> CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@data.fcv
> [...]
> CodeSamples/datastruct/hash/.hash_resize.c.swp --> CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> utilities/fcvextract.pl CodeSamples/datastruct/hash/.hash_resize.c.swp hash > CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> /bin/bash: CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv: No such file or directory
> make: *** [CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv] Error 1
>
> .hash_resize.c.swp is a swap file of vim, which causes an invalid
> dependency rule to be emitted.
>
> To prevent such errors, ignore .swp files as well as emacs' backup
> files ending in "~" and "#" from the search results in
> gen_snippet_d.pl.
>
> Reported-by: Paul E. McKenney <paulmck@linux.ibm.com>
> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> ---
> Paul,
>
> This should ignore .swp files in the dependency file.
> Can you test "make" while opening hash_resize.c in vim?
>
> Thanks, Akira
>
> PS:
>
> I'll comment on the update of Quick Quiz 10.13 later this week.
Works great, thank you!!!
It does not handle the case where you are concurrently editing the same
file with two different instances of "vim", but that could be considered
a feature rather than a bug. ;-) So no need to modify further.
Queued, will push with the QQ 10.13 update.
And have a great week, especially if this is holiday time for you!
Thanx, Paul
> --
> utilities/gen_snippet_d.pl | 16 ++++++++++------
> 1 file changed, 10 insertions(+), 6 deletions(-)
>
> diff --git a/utilities/gen_snippet_d.pl b/utilities/gen_snippet_d.pl
> index 8ba31b5..e07e58d 100755
> --- a/utilities/gen_snippet_d.pl
> +++ b/utilities/gen_snippet_d.pl
> @@ -17,11 +17,19 @@ my @fcvsources_ltms;
> my $snippet_key;
> my $snippet_key_ltms;
> my $source;
> +my @ignore_re;
> +my $re;
>
> $snippet_key = '\begin{snippet}' ;
> $snippet_key_ltms = '\begin[snippet]' ;
> +@ignore_re = ('\.swp$', '~$', '\#$') ; # to ignore backup of vim and emacs
> @fcvsources = `grep -l -r -F '$snippet_key' CodeSamples` ;
> +@fcvsources = grep { not /\.ltms$/ } @fcvsources ;
> @fcvsources_ltms = `grep -l -r -F '$snippet_key_ltms' CodeSamples` ;
> +foreach $re (@ignore_re) {
> + @fcvsources = grep { not /$re/ } @fcvsources ;
> + @fcvsources_ltms = grep { not /$re/ } @fcvsources_ltms ;
> +}
> chomp @fcvsources ;
> chomp @fcvsources_ltms ;
>
> @@ -32,9 +40,6 @@ foreach $source (@fcvsources) {
> my @snippet_commands1 ;
> my $subdir ;
> my $snippet ;
> - if ($source =~ /\.ltms$/) {
> - next;
> - }
> @snippet_commands1 = `grep -F '$snippet_key' $source` ;
> chomp @snippet_commands1 ;
> $source =~ m!(.*/[^/]+)/[^/]+! ;
> @@ -51,6 +56,7 @@ foreach $source (@fcvsources_ltms) {
> my @snippet_commands1 ;
> my $subdir ;
> my $snippet ;
> +
> @snippet_commands1 = `grep -F '$snippet_key_ltms' $source` ;
> chomp @snippet_commands1 ;
> $source =~ m!(.*/[^/]+)/[^/]+! ;
> @@ -77,9 +83,7 @@ foreach $source (@fcvsources) {
> my $src_under_sub ;
> my $subdir ;
> my $snippet ;
> - if ($source =~ /\.ltms$/) {
> - next;
> - }
> +
> @snippet_commands2 = `grep -F '$snippet_key' $source` ;
> chomp @snippet_commands2 ;
> $src_under_sub = $source ;
> --
> 2.7.4
>
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Sporadic SIGSEGV in hash_bkt_rcu and hash_resize (was Re: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files)
2018-12-26 15:00 ` Paul E. McKenney
@ 2018-12-31 4:37 ` Akira Yokosawa
2018-12-31 15:15 ` [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu Akira Yokosawa
0 siblings, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-31 4:37 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
On 2018/12/26 07:00:19 -0800, Paul E. McKenney wrote:
> On Wed, Dec 26, 2018 at 11:31:03PM +0900, Akira Yokosawa wrote:
>> >From 6c0e6e632bbf234de340bcf51acf2007d8e3ac8b Mon Sep 17 00:00:00 2001
>> From: Akira Yokosawa <akiyks@gmail.com>
>> Date: Wed, 26 Dec 2018 23:11:26 +0900
>> Subject: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files
>>
>> Excerpt from Paul's report:
>> $ make
>> sh ./utilities/gen_snippet_d.sh
>> sh utilities/autodate.sh >autodate.tex
>> CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@data.fcv
>> [...]
>> CodeSamples/datastruct/hash/.hash_resize.c.swp --> CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
>> utilities/fcvextract.pl CodeSamples/datastruct/hash/.hash_resize.c.swp hash > CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
>> /bin/bash: CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv: No such file or directory
>> make: *** [CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv] Error 1
>>
>> .hash_resize.c.swp is a swap file of vim, which causes an invalid
>> dependency rule to be emitted.
>>
>> To prevent such errors, ignore .swp files as well as emacs' backup
>> files ending in "~" and "#" from the search results in
>> gen_snippet_d.pl.
>>
>> Reported-by: Paul E. McKenney <paulmck@linux.ibm.com>
>> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
>> ---
>> Paul,
>>
>> This should ignore .swp files in the dependency file.
>> Can you test "make" while opening hash_resize.c in vim?
>>
>> Thanks, Akira
>>
>> PS:
>>
>> I'll comment on the update of Quick Quiz 10.13 later this week.
>
> Works great, thank you!!!
>
> It does not handle the case where you are concurrently editing the same
> file with two different instances of "vim", but that could be considered
> a feature rather than a bug. ;-) So no need to modify further.
>
> Queued, will push with the QQ 10.13 update.
>
> And have a great week, especially if this is holiday time for you!
Thank you!
Wish we could have a calm new year!
Before commenting on QQ 10.13, I thought I needed to grasp the whole
framework under CodeSamples/datastruct/hash/ and reviewed hashtorture.h.
Just wanted to make sure, I ran the tests with a variety of sets of arguments.
[NOTE: I ran them on Ubuntu Xenial with
liburcu-dev/xenial,now 0.9.1-3 and liburcu4/xenial,now 0.9.1-3
installed. On Trusty with liburcu-dev/trusty,now 0.7.12-0ubuntu2 and
liburcu1/trusty,now 0.7.12-0ubuntu2 installed, hash_bkt_rcu fails
differently.]
Some of them sporadically end up in SIGSEGV.
Following is a list of command lines which caused SIGSEGV in 10000 iteration each:
./hash_bkt_rcu --perftest --nreaders 1 --nupdaters 2 --duration 10
./hash_bkt_rcu --perftest --nreaders 1 --nupdaters 3 --duration 10
./hash_bkt_rcu --perftest --nreaders 1 --nupdaters 4 --duration 10
./hash_bkt_rcu --perftest --nreaders 2 --nupdaters 2 --duration 10
./hash_bkt_rcu --perftest --nreaders 2 --nupdaters 3 --duration 10
./hash_bkt_rcu --perftest --nreaders 2 --nupdaters 4 --duration 10
./bash_resize --perftest --nreaders 1 --nupdaters 2 --duration 10
./bash_resize --perftest --nreaders 1 --nupdaters 2 --resizemult 2 --duration 20
./bash_resize --schroidinger --nreaders 1 --nupdaters 1 --resizemult 2 --duration 20
bash_resize looks identical to bash_bkt_rcu as long as resizing is disabled.
So it looks like "--perftest" has some racing issue when "nupderters > 1"
in these tests.
"--schroedinger" works fine as long as resizing is disabled, but does have
issues when resizing is enabled. Is "--schroedinger" supposed to work
with resizing?
I'm not that good at multi-thread debugging, and I've not looked into
the details.
It's not at all urgent, but it would be great if you could look
into them.
Thanks, Akira
>
> Thanx, Paul
> [...]
^ permalink raw reply [flat|nested] 37+ messages in thread
* [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
2018-12-31 4:37 ` Sporadic SIGSEGV in hash_bkt_rcu and hash_resize (was Re: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files) Akira Yokosawa
@ 2018-12-31 15:15 ` Akira Yokosawa
2018-12-31 21:03 ` Paul E. McKenney
0 siblings, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2018-12-31 15:15 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 52f5d218442eb64f2798335d56a1838f90d96d5f Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Mon, 30 Dec 2018 22:54:43 +0900
Subject: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
Commit 4e22bdc905ff ("Wait at end of test for call_rcu() to finish")
added a couple of synchronize_rcu()s in perftest_update()
and zoo_reader().
However, there still remains sporadic SIGSEGV in
$ ./hash_bkt_rcu --perftest --nupdaters 3
On the other hand,
$ ./hash_bkt_rcu --schroedinger --nupdaters 3
does not show such issue. Just moving synchronize_rcu()s in
zoo_reader() to zoo_updater() does not resolve the
SIGSEGV.
This commit defines rcu_barrier() if not available,
and puts them at both before and after the final loop
of perftest_updater() and zoo_updater().
It looks like this change can fix the above mentioned
SIGSEGV in "--perftest".
[Tested on Ubuntu Xenial with liburcu-dev/xenial,now 0.9.1-3 and
liburcu4/xenial,now 0.9.1-3 installed.]
NOTE:
$ ./hash_resize --schroedinger --resizemult 2 --duration 20
still fails with SIGSEGV frequently in zoo_del(). GDB says:
(gdb) where
#0 0x0000000000402b27 in cds_list_del_rcu (elem=0x7ff8fc0138f0)
at /usr/include/urcu/rculist.h:71
#1 hashtab_del (htep=0x7ff8fc0138d0, htp_master=<optimized out>)
at hash_resize.c:261
#2 zoo_del (zhep=0x7ff8fc0138d0) at hashtorture.h:1007
#3 zoo_updater (arg=0x1e8b298) at hashtorture.h:1153
#4 0x00007ff9057d16ba in start_thread (arg=0x7ff903fed700)
at pthread_create.c:333
#5 0x00007ff9050f741d in clone ()
at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
Hi Paul,
This is a partial fix, but it resolves SIGSEGV in "--perftest" of
hash_bkt_rcu and hash_resize.
"--schroedinger" of hash_resize with resizing enabled still seg faults
as mentioned in the commit log.
By the way, what version of liburcu are you using?
Thanks, Akira
--
CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++--------
1 file changed, 16 insertions(+), 8 deletions(-)
diff --git a/CodeSamples/datastruct/hash/hashtorture.h b/CodeSamples/datastruct/hash/hashtorture.h
index 0e90220..9ae3dfa 100644
--- a/CodeSamples/datastruct/hash/hashtorture.h
+++ b/CodeSamples/datastruct/hash/hashtorture.h
@@ -55,6 +55,15 @@ void (*defer_del_done)(struct ht_elem *htep) = NULL;
#ifndef quiescent_state
#define quiescent_state() do ; while (0)
#define synchronize_rcu() do ; while (0)
+#define rcu_barrier() do ; while (0)
+#else
+#ifndef rcu_barrier
+#define rcu_barrier() do { \
+ synchronize_rcu(); \
+ poll(NULL, 0, 100); \
+ synchronize_rcu(); \
+ } while (0)
+#endif /* #ifndef rcu_barrier */
#endif /* #ifndef quiescent_state */
/*
@@ -765,6 +774,7 @@ void *perftest_reader(void *arg)
if (i >= ne)
i = i % ne + offset;
}
+
pap->nlookups = nlookups;
pap->nlookupfails = nlookupfails;
hash_unregister_thread();
@@ -839,6 +849,7 @@ void *perftest_updater(void *arg)
quiescent_state();
}
+ rcu_barrier();
/* Test over, so remove all our elements from the hash table. */
for (i = 0; i < elperupdater; i++) {
if (thep[i].in_table != 1)
@@ -846,10 +857,7 @@ void *perftest_updater(void *arg)
BUG_ON(!perftest_lookup(thep[i].data));
perftest_del(&thep[i]);
}
- /* Really want rcu_barrier(), but missing from old liburcu versions. */
- synchronize_rcu();
- poll(NULL, 0, 100);
- synchronize_rcu();
+ rcu_barrier();
hash_unregister_thread();
free(thep);
@@ -1048,10 +1056,6 @@ void *zoo_reader(void *arg)
if (i >= ne)
i = i % ne + offset;
}
- /* Really want rcu_barrier(), but missing from old liburcu versions. */
- synchronize_rcu();
- poll(NULL, 0, 100);
- synchronize_rcu();
pap->nlookups = nlookups;
pap->nlookupfails = nlookupfails;
@@ -1136,15 +1140,19 @@ void *zoo_updater(void *arg)
quiescent_state();
}
+ rcu_barrier();
/* Test over, so remove all our elements from the hash table. */
for (i = 0; i < elperupdater; i++) {
if (!zheplist[i])
continue;
zoo_del(zheplist[i]);
}
+ rcu_barrier();
+
hash_unregister_thread();
pap->nadds = nadds;
pap->ndels = ndels;
+ free(zheplist);
return NULL;
}
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
2018-12-31 15:15 ` [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu Akira Yokosawa
@ 2018-12-31 21:03 ` Paul E. McKenney
2019-01-01 0:27 ` Akira Yokosawa
0 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2018-12-31 21:03 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Tue, Jan 01, 2019 at 12:15:23AM +0900, Akira Yokosawa wrote:
> >From 52f5d218442eb64f2798335d56a1838f90d96d5f Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Mon, 30 Dec 2018 22:54:43 +0900
> Subject: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
>
> Commit 4e22bdc905ff ("Wait at end of test for call_rcu() to finish")
> added a couple of synchronize_rcu()s in perftest_update()
> and zoo_reader().
>
> However, there still remains sporadic SIGSEGV in
>
> $ ./hash_bkt_rcu --perftest --nupdaters 3
>
> On the other hand,
>
> $ ./hash_bkt_rcu --schroedinger --nupdaters 3
>
> does not show such issue. Just moving synchronize_rcu()s in
> zoo_reader() to zoo_updater() does not resolve the
> SIGSEGV.
>
>
> This commit defines rcu_barrier() if not available,
> and puts them at both before and after the final loop
> of perftest_updater() and zoo_updater().
>
> It looks like this change can fix the above mentioned
> SIGSEGV in "--perftest".
>
> [Tested on Ubuntu Xenial with liburcu-dev/xenial,now 0.9.1-3 and
> liburcu4/xenial,now 0.9.1-3 installed.]
>
> NOTE:
>
> $ ./hash_resize --schroedinger --resizemult 2 --duration 20
I get SIGSEGV and hangs from time to time, so I am looking into this.
Thank you for calling it to my attention!
> still fails with SIGSEGV frequently in zoo_del(). GDB says:
>
> (gdb) where
> #0 0x0000000000402b27 in cds_list_del_rcu (elem=0x7ff8fc0138f0)
> at /usr/include/urcu/rculist.h:71
> #1 hashtab_del (htep=0x7ff8fc0138d0, htp_master=<optimized out>)
> at hash_resize.c:261
> #2 zoo_del (zhep=0x7ff8fc0138d0) at hashtorture.h:1007
> #3 zoo_updater (arg=0x1e8b298) at hashtorture.h:1153
> #4 0x00007ff9057d16ba in start_thread (arg=0x7ff903fed700)
> at pthread_create.c:333
> #5 0x00007ff9050f741d in clone ()
> at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109
>
> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
Good catch, queue and pushed, thank you!
With one small modification -- given that liburcu has had rcu_barrier()
for some years now, I removed the "training wheels" (and unreliable)
use of the wait and pair of synchronize_rcu() calls.
> ---
> Hi Paul,
>
> This is a partial fix, but it resolves SIGSEGV in "--perftest" of
> hash_bkt_rcu and hash_resize.
>
> "--schroedinger" of hash_resize with resizing enabled still seg faults
> as mentioned in the commit log.
>
> By the way, what version of liburcu are you using?
It is about two years old, but it does have rcu_barrier().
Thanx, Paul
> Thanks, Akira
> --
> CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++--------
> 1 file changed, 16 insertions(+), 8 deletions(-)
>
> diff --git a/CodeSamples/datastruct/hash/hashtorture.h b/CodeSamples/datastruct/hash/hashtorture.h
> index 0e90220..9ae3dfa 100644
> --- a/CodeSamples/datastruct/hash/hashtorture.h
> +++ b/CodeSamples/datastruct/hash/hashtorture.h
> @@ -55,6 +55,15 @@ void (*defer_del_done)(struct ht_elem *htep) = NULL;
> #ifndef quiescent_state
> #define quiescent_state() do ; while (0)
> #define synchronize_rcu() do ; while (0)
> +#define rcu_barrier() do ; while (0)
> +#else
> +#ifndef rcu_barrier
> +#define rcu_barrier() do { \
> + synchronize_rcu(); \
> + poll(NULL, 0, 100); \
> + synchronize_rcu(); \
> + } while (0)
> +#endif /* #ifndef rcu_barrier */
> #endif /* #ifndef quiescent_state */
>
> /*
> @@ -765,6 +774,7 @@ void *perftest_reader(void *arg)
> if (i >= ne)
> i = i % ne + offset;
> }
> +
> pap->nlookups = nlookups;
> pap->nlookupfails = nlookupfails;
> hash_unregister_thread();
> @@ -839,6 +849,7 @@ void *perftest_updater(void *arg)
> quiescent_state();
> }
>
> + rcu_barrier();
> /* Test over, so remove all our elements from the hash table. */
> for (i = 0; i < elperupdater; i++) {
> if (thep[i].in_table != 1)
> @@ -846,10 +857,7 @@ void *perftest_updater(void *arg)
> BUG_ON(!perftest_lookup(thep[i].data));
> perftest_del(&thep[i]);
> }
> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
> - synchronize_rcu();
> - poll(NULL, 0, 100);
> - synchronize_rcu();
> + rcu_barrier();
>
> hash_unregister_thread();
> free(thep);
> @@ -1048,10 +1056,6 @@ void *zoo_reader(void *arg)
> if (i >= ne)
> i = i % ne + offset;
> }
> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
> - synchronize_rcu();
> - poll(NULL, 0, 100);
> - synchronize_rcu();
>
> pap->nlookups = nlookups;
> pap->nlookupfails = nlookupfails;
> @@ -1136,15 +1140,19 @@ void *zoo_updater(void *arg)
> quiescent_state();
> }
>
> + rcu_barrier();
> /* Test over, so remove all our elements from the hash table. */
> for (i = 0; i < elperupdater; i++) {
> if (!zheplist[i])
> continue;
> zoo_del(zheplist[i]);
> }
> + rcu_barrier();
> +
> hash_unregister_thread();
> pap->nadds = nadds;
> pap->ndels = ndels;
> + free(zheplist);
> return NULL;
> }
>
> --
> 2.7.4
>
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
2018-12-31 21:03 ` Paul E. McKenney
@ 2019-01-01 0:27 ` Akira Yokosawa
2019-01-01 18:00 ` Paul E. McKenney
0 siblings, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-01 0:27 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
On 2018/12/31 13:03:07 -0800, Paul E. McKenney wrote:
> On Tue, Jan 01, 2019 at 12:15:23AM +0900, Akira Yokosawa wrote:
>> >From 52f5d218442eb64f2798335d56a1838f90d96d5f Mon Sep 17 00:00:00 2001
>> From: Akira Yokosawa <akiyks@gmail.com>
>> Date: Mon, 30 Dec 2018 22:54:43 +0900
>> Subject: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
>>
>> Commit 4e22bdc905ff ("Wait at end of test for call_rcu() to finish")
>> added a couple of synchronize_rcu()s in perftest_update()
>> and zoo_reader().
>>
>> However, there still remains sporadic SIGSEGV in
>>
>> $ ./hash_bkt_rcu --perftest --nupdaters 3
>>
>> On the other hand,
>>
>> $ ./hash_bkt_rcu --schroedinger --nupdaters 3
>>
>> does not show such issue. Just moving synchronize_rcu()s in
>> zoo_reader() to zoo_updater() does not resolve the
>> SIGSEGV.
>>
>>
>> This commit defines rcu_barrier() if not available,
>> and puts them at both before and after the final loop
>> of perftest_updater() and zoo_updater().
>>
>> It looks like this change can fix the above mentioned
>> SIGSEGV in "--perftest".
>>
>> [Tested on Ubuntu Xenial with liburcu-dev/xenial,now 0.9.1-3 and
>> liburcu4/xenial,now 0.9.1-3 installed.]
>>
>> NOTE:
>>
>> $ ./hash_resize --schroedinger --resizemult 2 --duration 20
>
> I get SIGSEGV and hangs from time to time, so I am looking into this.
> Thank you for calling it to my attention!
I've found some suspicious code in hash_resize.c
hashtab_lock_mod() takes care of ongoing resizing and spin_lock()
new bucket if necessary. This is good for add, but for delete
we may still need to lock old bucket.
And hashtab_unlock_mod() doesn't care ongoing resizing, so
there can be mismatch of spin_lock() -- spin_unlock().
Also, htp_master->ht_cur can change during the
hashtab_lock_mod() -- hashtab_unlock_mod() critical section
because the update of the pointer by rcu_assign_pointer()
is ahead of synchronize_rcu().
Given the resizing is infrequent, the simplest way might be to
block hashtab_lock_mod while resizing is going on.
There can be a better way to keep concurrent add/del/resize, though.
Happy hacking! ;-)
Thanks, Akira
>
>> still fails with SIGSEGV frequently in zoo_del(). GDB says:
>>
>> (gdb) where
>> #0 0x0000000000402b27 in cds_list_del_rcu (elem=0x7ff8fc0138f0)
>> at /usr/include/urcu/rculist.h:71
>> #1 hashtab_del (htep=0x7ff8fc0138d0, htp_master=<optimized out>)
>> at hash_resize.c:261
>> #2 zoo_del (zhep=0x7ff8fc0138d0) at hashtorture.h:1007
>> #3 zoo_updater (arg=0x1e8b298) at hashtorture.h:1153
>> #4 0x00007ff9057d16ba in start_thread (arg=0x7ff903fed700)
>> at pthread_create.c:333
>> #5 0x00007ff9050f741d in clone ()
>> at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109
>>
>> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
>
> Good catch, queue and pushed, thank you!
>
> With one small modification -- given that liburcu has had rcu_barrier()
> for some years now, I removed the "training wheels" (and unreliable)
> use of the wait and pair of synchronize_rcu() calls.
>
>> ---
>> Hi Paul,
>>
>> This is a partial fix, but it resolves SIGSEGV in "--perftest" of
>> hash_bkt_rcu and hash_resize.
>>
>> "--schroedinger" of hash_resize with resizing enabled still seg faults
>> as mentioned in the commit log.
>>
>> By the way, what version of liburcu are you using?
>
> It is about two years old, but it does have rcu_barrier().
>
> Thanx, Paul
>
>> Thanks, Akira
>> --
>> CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++--------
>> 1 file changed, 16 insertions(+), 8 deletions(-)
>>
>> diff --git a/CodeSamples/datastruct/hash/hashtorture.h b/CodeSamples/datastruct/hash/hashtorture.h
>> index 0e90220..9ae3dfa 100644
>> --- a/CodeSamples/datastruct/hash/hashtorture.h
>> +++ b/CodeSamples/datastruct/hash/hashtorture.h
>> @@ -55,6 +55,15 @@ void (*defer_del_done)(struct ht_elem *htep) = NULL;
>> #ifndef quiescent_state
>> #define quiescent_state() do ; while (0)
>> #define synchronize_rcu() do ; while (0)
>> +#define rcu_barrier() do ; while (0)
>> +#else
>> +#ifndef rcu_barrier
>> +#define rcu_barrier() do { \
>> + synchronize_rcu(); \
>> + poll(NULL, 0, 100); \
>> + synchronize_rcu(); \
>> + } while (0)
>> +#endif /* #ifndef rcu_barrier */
>> #endif /* #ifndef quiescent_state */
>>
>> /*
>> @@ -765,6 +774,7 @@ void *perftest_reader(void *arg)
>> if (i >= ne)
>> i = i % ne + offset;
>> }
>> +
>> pap->nlookups = nlookups;
>> pap->nlookupfails = nlookupfails;
>> hash_unregister_thread();
>> @@ -839,6 +849,7 @@ void *perftest_updater(void *arg)
>> quiescent_state();
>> }
>>
>> + rcu_barrier();
>> /* Test over, so remove all our elements from the hash table. */
>> for (i = 0; i < elperupdater; i++) {
>> if (thep[i].in_table != 1)
>> @@ -846,10 +857,7 @@ void *perftest_updater(void *arg)
>> BUG_ON(!perftest_lookup(thep[i].data));
>> perftest_del(&thep[i]);
>> }
>> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
>> - synchronize_rcu();
>> - poll(NULL, 0, 100);
>> - synchronize_rcu();
>> + rcu_barrier();
>>
>> hash_unregister_thread();
>> free(thep);
>> @@ -1048,10 +1056,6 @@ void *zoo_reader(void *arg)
>> if (i >= ne)
>> i = i % ne + offset;
>> }
>> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
>> - synchronize_rcu();
>> - poll(NULL, 0, 100);
>> - synchronize_rcu();
>>
>> pap->nlookups = nlookups;
>> pap->nlookupfails = nlookupfails;
>> @@ -1136,15 +1140,19 @@ void *zoo_updater(void *arg)
>> quiescent_state();
>> }
>>
>> + rcu_barrier();
>> /* Test over, so remove all our elements from the hash table. */
>> for (i = 0; i < elperupdater; i++) {
>> if (!zheplist[i])
>> continue;
>> zoo_del(zheplist[i]);
>> }
>> + rcu_barrier();
>> +
>> hash_unregister_thread();
>> pap->nadds = nadds;
>> pap->ndels = ndels;
>> + free(zheplist);
>> return NULL;
>> }
>>
>> --
>> 2.7.4
>>
>>
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
2019-01-01 0:27 ` Akira Yokosawa
@ 2019-01-01 18:00 ` Paul E. McKenney
2019-01-02 15:02 ` Akira Yokosawa
0 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-01 18:00 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Tue, Jan 01, 2019 at 09:27:41AM +0900, Akira Yokosawa wrote:
> On 2018/12/31 13:03:07 -0800, Paul E. McKenney wrote:
> > On Tue, Jan 01, 2019 at 12:15:23AM +0900, Akira Yokosawa wrote:
> >> >From 52f5d218442eb64f2798335d56a1838f90d96d5f Mon Sep 17 00:00:00 2001
> >> From: Akira Yokosawa <akiyks@gmail.com>
> >> Date: Mon, 30 Dec 2018 22:54:43 +0900
> >> Subject: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
> >>
> >> Commit 4e22bdc905ff ("Wait at end of test for call_rcu() to finish")
> >> added a couple of synchronize_rcu()s in perftest_update()
> >> and zoo_reader().
> >>
> >> However, there still remains sporadic SIGSEGV in
> >>
> >> $ ./hash_bkt_rcu --perftest --nupdaters 3
> >>
> >> On the other hand,
> >>
> >> $ ./hash_bkt_rcu --schroedinger --nupdaters 3
> >>
> >> does not show such issue. Just moving synchronize_rcu()s in
> >> zoo_reader() to zoo_updater() does not resolve the
> >> SIGSEGV.
> >>
> >>
> >> This commit defines rcu_barrier() if not available,
> >> and puts them at both before and after the final loop
> >> of perftest_updater() and zoo_updater().
> >>
> >> It looks like this change can fix the above mentioned
> >> SIGSEGV in "--perftest".
> >>
> >> [Tested on Ubuntu Xenial with liburcu-dev/xenial,now 0.9.1-3 and
> >> liburcu4/xenial,now 0.9.1-3 installed.]
> >>
> >> NOTE:
> >>
> >> $ ./hash_resize --schroedinger --resizemult 2 --duration 20
> >
> > I get SIGSEGV and hangs from time to time, so I am looking into this.
> > Thank you for calling it to my attention!
>
> I've found some suspicious code in hash_resize.c
>
> hashtab_lock_mod() takes care of ongoing resizing and spin_lock()
> new bucket if necessary. This is good for add, but for delete
> we may still need to lock old bucket.
>
> And hashtab_unlock_mod() doesn't care ongoing resizing, so
> there can be mismatch of spin_lock() -- spin_unlock().
>
> Also, htp_master->ht_cur can change during the
> hashtab_lock_mod() -- hashtab_unlock_mod() critical section
> because the update of the pointer by rcu_assign_pointer()
> is ahead of synchronize_rcu().
>
> Given the resizing is infrequent, the simplest way might be to
> block hashtab_lock_mod while resizing is going on.
I do believe you have found something here, and thank you! So the
answer to my earlier question as to whether I was smarter when writing
it than now is clearly that I was equally stupid in both cases. ;-)
Well, it is conference-driven code, but still high time for me to
clean it up.
> There can be a better way to keep concurrent add/del/resize, though.
> Happy hacking! ;-)
I do believe that I can preserve concurrency between resizing and
deletion, but that is clearly for me to prove.
And thank you again!
Thanx, Paul
> Thanks, Akira
> >
> >> still fails with SIGSEGV frequently in zoo_del(). GDB says:
> >>
> >> (gdb) where
> >> #0 0x0000000000402b27 in cds_list_del_rcu (elem=0x7ff8fc0138f0)
> >> at /usr/include/urcu/rculist.h:71
> >> #1 hashtab_del (htep=0x7ff8fc0138d0, htp_master=<optimized out>)
> >> at hash_resize.c:261
> >> #2 zoo_del (zhep=0x7ff8fc0138d0) at hashtorture.h:1007
> >> #3 zoo_updater (arg=0x1e8b298) at hashtorture.h:1153
> >> #4 0x00007ff9057d16ba in start_thread (arg=0x7ff903fed700)
> >> at pthread_create.c:333
> >> #5 0x00007ff9050f741d in clone ()
> >> at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109
> >>
> >> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> >
> > Good catch, queue and pushed, thank you!
> >
> > With one small modification -- given that liburcu has had rcu_barrier()
> > for some years now, I removed the "training wheels" (and unreliable)
> > use of the wait and pair of synchronize_rcu() calls.
> >
> >> ---
> >> Hi Paul,
> >>
> >> This is a partial fix, but it resolves SIGSEGV in "--perftest" of
> >> hash_bkt_rcu and hash_resize.
> >>
> >> "--schroedinger" of hash_resize with resizing enabled still seg faults
> >> as mentioned in the commit log.
> >>
> >> By the way, what version of liburcu are you using?
> >
> > It is about two years old, but it does have rcu_barrier().
> >
> > Thanx, Paul
> >
> >> Thanks, Akira
> >> --
> >> CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++--------
> >> 1 file changed, 16 insertions(+), 8 deletions(-)
> >>
> >> diff --git a/CodeSamples/datastruct/hash/hashtorture.h b/CodeSamples/datastruct/hash/hashtorture.h
> >> index 0e90220..9ae3dfa 100644
> >> --- a/CodeSamples/datastruct/hash/hashtorture.h
> >> +++ b/CodeSamples/datastruct/hash/hashtorture.h
> >> @@ -55,6 +55,15 @@ void (*defer_del_done)(struct ht_elem *htep) = NULL;
> >> #ifndef quiescent_state
> >> #define quiescent_state() do ; while (0)
> >> #define synchronize_rcu() do ; while (0)
> >> +#define rcu_barrier() do ; while (0)
> >> +#else
> >> +#ifndef rcu_barrier
> >> +#define rcu_barrier() do { \
> >> + synchronize_rcu(); \
> >> + poll(NULL, 0, 100); \
> >> + synchronize_rcu(); \
> >> + } while (0)
> >> +#endif /* #ifndef rcu_barrier */
> >> #endif /* #ifndef quiescent_state */
> >>
> >> /*
> >> @@ -765,6 +774,7 @@ void *perftest_reader(void *arg)
> >> if (i >= ne)
> >> i = i % ne + offset;
> >> }
> >> +
> >> pap->nlookups = nlookups;
> >> pap->nlookupfails = nlookupfails;
> >> hash_unregister_thread();
> >> @@ -839,6 +849,7 @@ void *perftest_updater(void *arg)
> >> quiescent_state();
> >> }
> >>
> >> + rcu_barrier();
> >> /* Test over, so remove all our elements from the hash table. */
> >> for (i = 0; i < elperupdater; i++) {
> >> if (thep[i].in_table != 1)
> >> @@ -846,10 +857,7 @@ void *perftest_updater(void *arg)
> >> BUG_ON(!perftest_lookup(thep[i].data));
> >> perftest_del(&thep[i]);
> >> }
> >> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
> >> - synchronize_rcu();
> >> - poll(NULL, 0, 100);
> >> - synchronize_rcu();
> >> + rcu_barrier();
> >>
> >> hash_unregister_thread();
> >> free(thep);
> >> @@ -1048,10 +1056,6 @@ void *zoo_reader(void *arg)
> >> if (i >= ne)
> >> i = i % ne + offset;
> >> }
> >> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
> >> - synchronize_rcu();
> >> - poll(NULL, 0, 100);
> >> - synchronize_rcu();
> >>
> >> pap->nlookups = nlookups;
> >> pap->nlookupfails = nlookupfails;
> >> @@ -1136,15 +1140,19 @@ void *zoo_updater(void *arg)
> >> quiescent_state();
> >> }
> >>
> >> + rcu_barrier();
> >> /* Test over, so remove all our elements from the hash table. */
> >> for (i = 0; i < elperupdater; i++) {
> >> if (!zheplist[i])
> >> continue;
> >> zoo_del(zheplist[i]);
> >> }
> >> + rcu_barrier();
> >> +
> >> hash_unregister_thread();
> >> pap->nadds = nadds;
> >> pap->ndels = ndels;
> >> + free(zheplist);
> >> return NULL;
> >> }
> >>
> >> --
> >> 2.7.4
> >>
> >>
> >
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
2019-01-01 18:00 ` Paul E. McKenney
@ 2019-01-02 15:02 ` Akira Yokosawa
2019-01-02 17:18 ` Paul E. McKenney
0 siblings, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-02 15:02 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
On 2019/01/01 10:00:25 -0800, Paul E. McKenney wrote:
> On Tue, Jan 01, 2019 at 09:27:41AM +0900, Akira Yokosawa wrote:
>> On 2018/12/31 13:03:07 -0800, Paul E. McKenney wrote:
>>> On Tue, Jan 01, 2019 at 12:15:23AM +0900, Akira Yokosawa wrote:
>>>> >From 52f5d218442eb64f2798335d56a1838f90d96d5f Mon Sep 17 00:00:00 2001
>>>> From: Akira Yokosawa <akiyks@gmail.com>
>>>> Date: Mon, 30 Dec 2018 22:54:43 +0900
>>>> Subject: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
>>>>
>>>> Commit 4e22bdc905ff ("Wait at end of test for call_rcu() to finish")
>>>> added a couple of synchronize_rcu()s in perftest_update()
>>>> and zoo_reader().
>>>>
>>>> However, there still remains sporadic SIGSEGV in
>>>>
>>>> $ ./hash_bkt_rcu --perftest --nupdaters 3
>>>>
>>>> On the other hand,
>>>>
>>>> $ ./hash_bkt_rcu --schroedinger --nupdaters 3
>>>>
>>>> does not show such issue. Just moving synchronize_rcu()s in
>>>> zoo_reader() to zoo_updater() does not resolve the
>>>> SIGSEGV.
>>>>
>>>>
>>>> This commit defines rcu_barrier() if not available,
>>>> and puts them at both before and after the final loop
>>>> of perftest_updater() and zoo_updater().
>>>>
>>>> It looks like this change can fix the above mentioned
>>>> SIGSEGV in "--perftest".
>>>>
>>>> [Tested on Ubuntu Xenial with liburcu-dev/xenial,now 0.9.1-3 and
>>>> liburcu4/xenial,now 0.9.1-3 installed.]
>>>>
>>>> NOTE:
>>>>
>>>> $ ./hash_resize --schroedinger --resizemult 2 --duration 20
>>>
>>> I get SIGSEGV and hangs from time to time, so I am looking into this.
>>> Thank you for calling it to my attention!
>>
>> I've found some suspicious code in hash_resize.c
>>
>> hashtab_lock_mod() takes care of ongoing resizing and spin_lock()
>> new bucket if necessary. This is good for add, but for delete
>> we may still need to lock old bucket.
>>
>> And hashtab_unlock_mod() doesn't care ongoing resizing, so
>> there can be mismatch of spin_lock() -- spin_unlock().
>>
>> Also, htp_master->ht_cur can change during the
>> hashtab_lock_mod() -- hashtab_unlock_mod() critical section
>> because the update of the pointer by rcu_assign_pointer()
>> is ahead of synchronize_rcu().
>>
>> Given the resizing is infrequent, the simplest way might be to
>> block hashtab_lock_mod while resizing is going on.
>
> I do believe you have found something here, and thank you! So the
> answer to my earlier question as to whether I was smarter when writing
> it than now is clearly that I was equally stupid in both cases. ;-)
>
> Well, it is conference-driven code, but still high time for me to
> clean it up.
>
>> There can be a better way to keep concurrent add/del/resize, though.
>> Happy hacking! ;-)
>
> I do believe that I can preserve concurrency between resizing and
> deletion, but that is clearly for me to prove.
There is one more thing I've noticed with "hash_resize --schroedinger".
*Without* resizing enabled, it says:
$ ./hash_resize --schroedinger
nlookups: 91373 91373 ncats: 0 nadds: 5 ndels: 6 duration: 10.851
ns/read: 118.755 ns/update: 986455
This means that all the lookups failed. OTOH, hash_bkt_rcu works as expected
as follows:
$ ./hash_bkt_rcu --schroedinger
nlookups: 56064 28004 ncats: 0 nadds: 5 ndels: 5 duration: 10.373
ns/read: 185.021 ns/update: 1.0373e+06
(ns/read looks slow because compiler optimization is disabled.)
There seems to be some mismatch in hash/key handling of hash_resize.c --
hashtorture.h combination. I've not yet figured out the cause, though.
Thanks, Akira
>
> And thank you again!
>
> Thanx, Paul
>
>> Thanks, Akira
>>>
>>>> still fails with SIGSEGV frequently in zoo_del(). GDB says:
>>>>
>>>> (gdb) where
>>>> #0 0x0000000000402b27 in cds_list_del_rcu (elem=0x7ff8fc0138f0)
>>>> at /usr/include/urcu/rculist.h:71
>>>> #1 hashtab_del (htep=0x7ff8fc0138d0, htp_master=<optimized out>)
>>>> at hash_resize.c:261
>>>> #2 zoo_del (zhep=0x7ff8fc0138d0) at hashtorture.h:1007
>>>> #3 zoo_updater (arg=0x1e8b298) at hashtorture.h:1153
>>>> #4 0x00007ff9057d16ba in start_thread (arg=0x7ff903fed700)
>>>> at pthread_create.c:333
>>>> #5 0x00007ff9050f741d in clone ()
>>>> at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109
>>>>
>>>> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
>>>
>>> Good catch, queue and pushed, thank you!
>>>
>>> With one small modification -- given that liburcu has had rcu_barrier()
>>> for some years now, I removed the "training wheels" (and unreliable)
>>> use of the wait and pair of synchronize_rcu() calls.
>>>
>>>> ---
>>>> Hi Paul,
>>>>
>>>> This is a partial fix, but it resolves SIGSEGV in "--perftest" of
>>>> hash_bkt_rcu and hash_resize.
>>>>
>>>> "--schroedinger" of hash_resize with resizing enabled still seg faults
>>>> as mentioned in the commit log.
>>>>
>>>> By the way, what version of liburcu are you using?
>>>
>>> It is about two years old, but it does have rcu_barrier().
>>>
>>> Thanx, Paul
>>>
>>>> Thanks, Akira
>>>> --
>>>> CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++--------
>>>> 1 file changed, 16 insertions(+), 8 deletions(-)
>>>>
>>>> diff --git a/CodeSamples/datastruct/hash/hashtorture.h b/CodeSamples/datastruct/hash/hashtorture.h
>>>> index 0e90220..9ae3dfa 100644
>>>> --- a/CodeSamples/datastruct/hash/hashtorture.h
>>>> +++ b/CodeSamples/datastruct/hash/hashtorture.h
>>>> @@ -55,6 +55,15 @@ void (*defer_del_done)(struct ht_elem *htep) = NULL;
>>>> #ifndef quiescent_state
>>>> #define quiescent_state() do ; while (0)
>>>> #define synchronize_rcu() do ; while (0)
>>>> +#define rcu_barrier() do ; while (0)
>>>> +#else
>>>> +#ifndef rcu_barrier
>>>> +#define rcu_barrier() do { \
>>>> + synchronize_rcu(); \
>>>> + poll(NULL, 0, 100); \
>>>> + synchronize_rcu(); \
>>>> + } while (0)
>>>> +#endif /* #ifndef rcu_barrier */
>>>> #endif /* #ifndef quiescent_state */
>>>>
>>>> /*
>>>> @@ -765,6 +774,7 @@ void *perftest_reader(void *arg)
>>>> if (i >= ne)
>>>> i = i % ne + offset;
>>>> }
>>>> +
>>>> pap->nlookups = nlookups;
>>>> pap->nlookupfails = nlookupfails;
>>>> hash_unregister_thread();
>>>> @@ -839,6 +849,7 @@ void *perftest_updater(void *arg)
>>>> quiescent_state();
>>>> }
>>>>
>>>> + rcu_barrier();
>>>> /* Test over, so remove all our elements from the hash table. */
>>>> for (i = 0; i < elperupdater; i++) {
>>>> if (thep[i].in_table != 1)
>>>> @@ -846,10 +857,7 @@ void *perftest_updater(void *arg)
>>>> BUG_ON(!perftest_lookup(thep[i].data));
>>>> perftest_del(&thep[i]);
>>>> }
>>>> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
>>>> - synchronize_rcu();
>>>> - poll(NULL, 0, 100);
>>>> - synchronize_rcu();
>>>> + rcu_barrier();
>>>>
>>>> hash_unregister_thread();
>>>> free(thep);
>>>> @@ -1048,10 +1056,6 @@ void *zoo_reader(void *arg)
>>>> if (i >= ne)
>>>> i = i % ne + offset;
>>>> }
>>>> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
>>>> - synchronize_rcu();
>>>> - poll(NULL, 0, 100);
>>>> - synchronize_rcu();
>>>>
>>>> pap->nlookups = nlookups;
>>>> pap->nlookupfails = nlookupfails;
>>>> @@ -1136,15 +1140,19 @@ void *zoo_updater(void *arg)
>>>> quiescent_state();
>>>> }
>>>>
>>>> + rcu_barrier();
>>>> /* Test over, so remove all our elements from the hash table. */
>>>> for (i = 0; i < elperupdater; i++) {
>>>> if (!zheplist[i])
>>>> continue;
>>>> zoo_del(zheplist[i]);
>>>> }
>>>> + rcu_barrier();
>>>> +
>>>> hash_unregister_thread();
>>>> pap->nadds = nadds;
>>>> pap->ndels = ndels;
>>>> + free(zheplist);
>>>> return NULL;
>>>> }
>>>>
>>>> --
>>>> 2.7.4
>>>>
>>>>
>>>
>>
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
2019-01-02 15:02 ` Akira Yokosawa
@ 2019-01-02 17:18 ` Paul E. McKenney
2019-01-02 19:18 ` Paul E. McKenney
0 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-02 17:18 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Thu, Jan 03, 2019 at 12:02:56AM +0900, Akira Yokosawa wrote:
> On 2019/01/01 10:00:25 -0800, Paul E. McKenney wrote:
> > On Tue, Jan 01, 2019 at 09:27:41AM +0900, Akira Yokosawa wrote:
> >> On 2018/12/31 13:03:07 -0800, Paul E. McKenney wrote:
> >>> On Tue, Jan 01, 2019 at 12:15:23AM +0900, Akira Yokosawa wrote:
> >>>> >From 52f5d218442eb64f2798335d56a1838f90d96d5f Mon Sep 17 00:00:00 2001
> >>>> From: Akira Yokosawa <akiyks@gmail.com>
> >>>> Date: Mon, 30 Dec 2018 22:54:43 +0900
> >>>> Subject: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
> >>>>
> >>>> Commit 4e22bdc905ff ("Wait at end of test for call_rcu() to finish")
> >>>> added a couple of synchronize_rcu()s in perftest_update()
> >>>> and zoo_reader().
> >>>>
> >>>> However, there still remains sporadic SIGSEGV in
> >>>>
> >>>> $ ./hash_bkt_rcu --perftest --nupdaters 3
> >>>>
> >>>> On the other hand,
> >>>>
> >>>> $ ./hash_bkt_rcu --schroedinger --nupdaters 3
> >>>>
> >>>> does not show such issue. Just moving synchronize_rcu()s in
> >>>> zoo_reader() to zoo_updater() does not resolve the
> >>>> SIGSEGV.
> >>>>
> >>>>
> >>>> This commit defines rcu_barrier() if not available,
> >>>> and puts them at both before and after the final loop
> >>>> of perftest_updater() and zoo_updater().
> >>>>
> >>>> It looks like this change can fix the above mentioned
> >>>> SIGSEGV in "--perftest".
> >>>>
> >>>> [Tested on Ubuntu Xenial with liburcu-dev/xenial,now 0.9.1-3 and
> >>>> liburcu4/xenial,now 0.9.1-3 installed.]
> >>>>
> >>>> NOTE:
> >>>>
> >>>> $ ./hash_resize --schroedinger --resizemult 2 --duration 20
> >>>
> >>> I get SIGSEGV and hangs from time to time, so I am looking into this.
> >>> Thank you for calling it to my attention!
> >>
> >> I've found some suspicious code in hash_resize.c
> >>
> >> hashtab_lock_mod() takes care of ongoing resizing and spin_lock()
> >> new bucket if necessary. This is good for add, but for delete
> >> we may still need to lock old bucket.
> >>
> >> And hashtab_unlock_mod() doesn't care ongoing resizing, so
> >> there can be mismatch of spin_lock() -- spin_unlock().
> >>
> >> Also, htp_master->ht_cur can change during the
> >> hashtab_lock_mod() -- hashtab_unlock_mod() critical section
> >> because the update of the pointer by rcu_assign_pointer()
> >> is ahead of synchronize_rcu().
> >>
> >> Given the resizing is infrequent, the simplest way might be to
> >> block hashtab_lock_mod while resizing is going on.
> >
> > I do believe you have found something here, and thank you! So the
> > answer to my earlier question as to whether I was smarter when writing
> > it than now is clearly that I was equally stupid in both cases. ;-)
> >
> > Well, it is conference-driven code, but still high time for me to
> > clean it up.
> >
> >> There can be a better way to keep concurrent add/del/resize, though.
> >> Happy hacking! ;-)
> >
> > I do believe that I can preserve concurrency between resizing and
> > deletion, but that is clearly for me to prove.
>
> There is one more thing I've noticed with "hash_resize --schroedinger".
> *Without* resizing enabled, it says:
>
> $ ./hash_resize --schroedinger
> nlookups: 91373 91373 ncats: 0 nadds: 5 ndels: 6 duration: 10.851
> ns/read: 118.755 ns/update: 986455
>
> This means that all the lookups failed. OTOH, hash_bkt_rcu works as expected
> as follows:
>
> $ ./hash_bkt_rcu --schroedinger
> nlookups: 56064 28004 ncats: 0 nadds: 5 ndels: 5 duration: 10.373
> ns/read: 185.021 ns/update: 1.0373e+06
>
> (ns/read looks slow because compiler optimization is disabled.)
>
> There seems to be some mismatch in hash/key handling of hash_resize.c --
> hashtorture.h combination. I've not yet figured out the cause, though.
The short story is that I am working to return the locking state
from hashtab_lock_mod() for use by hashtab_add(), hashtab_del(),
and hashtab_unlock_mod(). Also, the first resize carries out some
"interesting" state changes that might need to be reflected in
initialization.
But yes, not one of my best efforts...
Thanx, Paul
> Thanks, Akira
>
> >
> > And thank you again!
> >
> > Thanx, Paul
> >
> >> Thanks, Akira
> >>>
> >>>> still fails with SIGSEGV frequently in zoo_del(). GDB says:
> >>>>
> >>>> (gdb) where
> >>>> #0 0x0000000000402b27 in cds_list_del_rcu (elem=0x7ff8fc0138f0)
> >>>> at /usr/include/urcu/rculist.h:71
> >>>> #1 hashtab_del (htep=0x7ff8fc0138d0, htp_master=<optimized out>)
> >>>> at hash_resize.c:261
> >>>> #2 zoo_del (zhep=0x7ff8fc0138d0) at hashtorture.h:1007
> >>>> #3 zoo_updater (arg=0x1e8b298) at hashtorture.h:1153
> >>>> #4 0x00007ff9057d16ba in start_thread (arg=0x7ff903fed700)
> >>>> at pthread_create.c:333
> >>>> #5 0x00007ff9050f741d in clone ()
> >>>> at ../sysdeps/unix/sysv/linux/x86_64/clone.S:109
> >>>>
> >>>> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> >>>
> >>> Good catch, queue and pushed, thank you!
> >>>
> >>> With one small modification -- given that liburcu has had rcu_barrier()
> >>> for some years now, I removed the "training wheels" (and unreliable)
> >>> use of the wait and pair of synchronize_rcu() calls.
> >>>
> >>>> ---
> >>>> Hi Paul,
> >>>>
> >>>> This is a partial fix, but it resolves SIGSEGV in "--perftest" of
> >>>> hash_bkt_rcu and hash_resize.
> >>>>
> >>>> "--schroedinger" of hash_resize with resizing enabled still seg faults
> >>>> as mentioned in the commit log.
> >>>>
> >>>> By the way, what version of liburcu are you using?
> >>>
> >>> It is about two years old, but it does have rcu_barrier().
> >>>
> >>> Thanx, Paul
> >>>
> >>>> Thanks, Akira
> >>>> --
> >>>> CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++--------
> >>>> 1 file changed, 16 insertions(+), 8 deletions(-)
> >>>>
> >>>> diff --git a/CodeSamples/datastruct/hash/hashtorture.h b/CodeSamples/datastruct/hash/hashtorture.h
> >>>> index 0e90220..9ae3dfa 100644
> >>>> --- a/CodeSamples/datastruct/hash/hashtorture.h
> >>>> +++ b/CodeSamples/datastruct/hash/hashtorture.h
> >>>> @@ -55,6 +55,15 @@ void (*defer_del_done)(struct ht_elem *htep) = NULL;
> >>>> #ifndef quiescent_state
> >>>> #define quiescent_state() do ; while (0)
> >>>> #define synchronize_rcu() do ; while (0)
> >>>> +#define rcu_barrier() do ; while (0)
> >>>> +#else
> >>>> +#ifndef rcu_barrier
> >>>> +#define rcu_barrier() do { \
> >>>> + synchronize_rcu(); \
> >>>> + poll(NULL, 0, 100); \
> >>>> + synchronize_rcu(); \
> >>>> + } while (0)
> >>>> +#endif /* #ifndef rcu_barrier */
> >>>> #endif /* #ifndef quiescent_state */
> >>>>
> >>>> /*
> >>>> @@ -765,6 +774,7 @@ void *perftest_reader(void *arg)
> >>>> if (i >= ne)
> >>>> i = i % ne + offset;
> >>>> }
> >>>> +
> >>>> pap->nlookups = nlookups;
> >>>> pap->nlookupfails = nlookupfails;
> >>>> hash_unregister_thread();
> >>>> @@ -839,6 +849,7 @@ void *perftest_updater(void *arg)
> >>>> quiescent_state();
> >>>> }
> >>>>
> >>>> + rcu_barrier();
> >>>> /* Test over, so remove all our elements from the hash table. */
> >>>> for (i = 0; i < elperupdater; i++) {
> >>>> if (thep[i].in_table != 1)
> >>>> @@ -846,10 +857,7 @@ void *perftest_updater(void *arg)
> >>>> BUG_ON(!perftest_lookup(thep[i].data));
> >>>> perftest_del(&thep[i]);
> >>>> }
> >>>> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
> >>>> - synchronize_rcu();
> >>>> - poll(NULL, 0, 100);
> >>>> - synchronize_rcu();
> >>>> + rcu_barrier();
> >>>>
> >>>> hash_unregister_thread();
> >>>> free(thep);
> >>>> @@ -1048,10 +1056,6 @@ void *zoo_reader(void *arg)
> >>>> if (i >= ne)
> >>>> i = i % ne + offset;
> >>>> }
> >>>> - /* Really want rcu_barrier(), but missing from old liburcu versions. */
> >>>> - synchronize_rcu();
> >>>> - poll(NULL, 0, 100);
> >>>> - synchronize_rcu();
> >>>>
> >>>> pap->nlookups = nlookups;
> >>>> pap->nlookupfails = nlookupfails;
> >>>> @@ -1136,15 +1140,19 @@ void *zoo_updater(void *arg)
> >>>> quiescent_state();
> >>>> }
> >>>>
> >>>> + rcu_barrier();
> >>>> /* Test over, so remove all our elements from the hash table. */
> >>>> for (i = 0; i < elperupdater; i++) {
> >>>> if (!zheplist[i])
> >>>> continue;
> >>>> zoo_del(zheplist[i]);
> >>>> }
> >>>> + rcu_barrier();
> >>>> +
> >>>> hash_unregister_thread();
> >>>> pap->nadds = nadds;
> >>>> pap->ndels = ndels;
> >>>> + free(zheplist);
> >>>> return NULL;
> >>>> }
> >>>>
> >>>> --
> >>>> 2.7.4
> >>>>
> >>>>
> >>>
> >>
> >
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
2019-01-02 17:18 ` Paul E. McKenney
@ 2019-01-02 19:18 ` Paul E. McKenney
2019-01-03 15:57 ` [PATCH] datastruct/hash: Tweak appearance of updated code in snippet Akira Yokosawa
0 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-02 19:18 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Wed, Jan 02, 2019 at 09:18:48AM -0800, Paul E. McKenney wrote:
> On Thu, Jan 03, 2019 at 12:02:56AM +0900, Akira Yokosawa wrote:
> > On 2019/01/01 10:00:25 -0800, Paul E. McKenney wrote:
[ . . . ]
> > There is one more thing I've noticed with "hash_resize --schroedinger".
> > *Without* resizing enabled, it says:
> >
> > $ ./hash_resize --schroedinger
> > nlookups: 91373 91373 ncats: 0 nadds: 5 ndels: 6 duration: 10.851
> > ns/read: 118.755 ns/update: 986455
> >
> > This means that all the lookups failed. OTOH, hash_bkt_rcu works as expected
> > as follows:
> >
> > $ ./hash_bkt_rcu --schroedinger
> > nlookups: 56064 28004 ncats: 0 nadds: 5 ndels: 5 duration: 10.373
> > ns/read: 185.021 ns/update: 1.0373e+06
> >
> > (ns/read looks slow because compiler optimization is disabled.)
> >
> > There seems to be some mismatch in hash/key handling of hash_resize.c --
> > hashtorture.h combination. I've not yet figured out the cause, though.
>
> The short story is that I am working to return the locking state
> from hashtab_lock_mod() for use by hashtab_add(), hashtab_del(),
> and hashtab_unlock_mod(). Also, the first resize carries out some
> "interesting" state changes that might need to be reflected in
> initialization.
>
> But yes, not one of my best efforts...
To be a bit less cryptic, the problem is that the non-resizable hash
tables completely delegate hashing to the caller. This is not viable
for resizable hash tables (which were indeed added later) because the
resizing is internal to the hash table, yet needs to know the hash
function. And currently hash_resize.c and hashtorture.h agree on the
hash function except for the --schroedinger case. So zoo_lookup()
and zoo_add() won't be looking at the same buckets except by accident.
And a rather low-probability accident at that.
So I remove "hash_private", which was intended to allow hash-function
perturbation, but is not used. Then I can pass the hash function into
hashtab_alloc(), where all but hash_resize can ignore it. Then I continue
the locking/bucket-selection cleanup.
And again, thank you for finding these problems!
Thanx, Paul
^ permalink raw reply [flat|nested] 37+ messages in thread
* [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
2019-01-02 19:18 ` Paul E. McKenney
@ 2019-01-03 15:57 ` Akira Yokosawa
2019-01-03 17:21 ` Paul E. McKenney
0 siblings, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-03 15:57 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From ae50debbf06ad674e4941b55764b02c776484509 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Fri, 4 Jan 2019 00:19:26 +0900
Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
Now that "[" and "]" are used within the code, "commandchars" should
avoid them.
Also wrap a line which has become too wide for the 2c layout.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
Hi Paul,
I'm in the middle of reading the updated code.
I'm sure you are working on the update of Section 10.4.2.
Because of the code change, there are quite a few broken refs
and duplicated labels at the moment.
This commit just takes care of the vanishing "[" and "]" in
Listing 10.11.
Fixing labels is left for your update.
Thanks, Akira
--
CodeSamples/datastruct/hash/hash_resize.c | 5 +++--
1 file changed, 3 insertions(+), 2 deletions(-)
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index bb0a6f4..7392455 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -154,10 +154,11 @@ 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=\\\[\]]
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:lock_unlock_mod,commandchars=\\\@\$]
/* Update-side lock/unlock functions. */
static void //\lnlbl{lock:b}
-resize_lock_mod(struct hashtab *htp_master, void *key, struct ht_bucket *ls[2])
+resize_lock_mod(struct hashtab *htp_master, void *key,
+ struct ht_bucket *ls[2])
{
long b;
struct ht *htp;
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
2019-01-03 15:57 ` [PATCH] datastruct/hash: Tweak appearance of updated code in snippet Akira Yokosawa
@ 2019-01-03 17:21 ` Paul E. McKenney
2019-01-03 23:35 ` Akira Yokosawa
0 siblings, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-03 17:21 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Fri, Jan 04, 2019 at 12:57:06AM +0900, Akira Yokosawa wrote:
> >From ae50debbf06ad674e4941b55764b02c776484509 Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Fri, 4 Jan 2019 00:19:26 +0900
> Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
>
> Now that "[" and "]" are used within the code, "commandchars" should
> avoid them.
>
> Also wrap a line which has become too wide for the 2c layout.
>
> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
Ah, the lsp[2] was a temporary state. I forgot to do a final "git push"
yesterday, apologies!
> ---
> Hi Paul,
>
> I'm in the middle of reading the updated code.
>
> I'm sure you are working on the update of Section 10.4.2.
> Because of the code change, there are quite a few broken refs
> and duplicated labels at the moment.
Yes, it is a bit of a mess at this point. I figured that if I was
going to have to modify the text and labels, I might as well do the
extra work to make the API a little less obnoxious. My first attempt to
move hash_resize.c's hashtab_add() in this direction broke very badly,
so it is back to the drawing board.
I am thinking in terms of having a single struct ht_lock_state that
contains an array or two as one part of making the API less obnoxious,
which should help avoid the brokenness.
> This commit just takes care of the vanishing "[" and "]" in
> Listing 10.11.
I am hoping that we can retain "[" and "]" -- it is normally not such
a good idea to have arrays in parameter lists.
Or do we need this commit anyway just due to array references within
the code snippet? If the latter, I will hand-apply the patch.
> Fixing labels is left for your update.
Will do, and yes, they are a bit of a mess just now. ;-)
Thanx, Paul
> Thanks, Akira
> --
> CodeSamples/datastruct/hash/hash_resize.c | 5 +++--
> 1 file changed, 3 insertions(+), 2 deletions(-)
>
> diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> index bb0a6f4..7392455 100644
> --- a/CodeSamples/datastruct/hash/hash_resize.c
> +++ b/CodeSamples/datastruct/hash/hash_resize.c
> @@ -154,10 +154,11 @@ 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=\\\[\]]
> +//\begin{snippet}[labelbase=ln:datastruct:hash_resize:lock_unlock_mod,commandchars=\\\@\$]
> /* Update-side lock/unlock functions. */
> static void //\lnlbl{lock:b}
> -resize_lock_mod(struct hashtab *htp_master, void *key, struct ht_bucket *ls[2])
> +resize_lock_mod(struct hashtab *htp_master, void *key,
> + struct ht_bucket *ls[2])
> {
> long b;
> struct ht *htp;
> --
> 2.7.4
>
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
2019-01-03 17:21 ` Paul E. McKenney
@ 2019-01-03 23:35 ` Akira Yokosawa
2019-01-04 0:52 ` Paul E. McKenney
2019-01-04 15:38 ` Akira Yokosawa
0 siblings, 2 replies; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-03 23:35 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
On 2019/01/03 09:21:45 -0800, Paul E. McKenney wrote:
> On Fri, Jan 04, 2019 at 12:57:06AM +0900, Akira Yokosawa wrote:
>> >From ae50debbf06ad674e4941b55764b02c776484509 Mon Sep 17 00:00:00 2001
>> From: Akira Yokosawa <akiyks@gmail.com>
>> Date: Fri, 4 Jan 2019 00:19:26 +0900
>> Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
>>
>> Now that "[" and "]" are used within the code, "commandchars" should
>> avoid them.
>>
>> Also wrap a line which has become too wide for the 2c layout.
>>
>> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
>
> Ah, the lsp[2] was a temporary state. I forgot to do a final "git push"
> yesterday, apologies!
>
>> ---
>> Hi Paul,
>>
>> I'm in the middle of reading the updated code.
>>
>> I'm sure you are working on the update of Section 10.4.2.
>> Because of the code change, there are quite a few broken refs
>> and duplicated labels at the moment.
>
> Yes, it is a bit of a mess at this point. I figured that if I was
> going to have to modify the text and labels, I might as well do the
> extra work to make the API a little less obnoxious. My first attempt to
> move hash_resize.c's hashtab_add() in this direction broke very badly,
> so it is back to the drawing board.
>
> I am thinking in terms of having a single struct ht_lock_state that
> contains an array or two as one part of making the API less obnoxious,
> which should help avoid the brokenness.
>
>> This commit just takes care of the vanishing "[" and "]" in
>> Listing 10.11.
>
> I am hoping that we can retain "[" and "]" -- it is normally not such
> a good idea to have arrays in parameter lists.
>
> Or do we need this commit anyway just due to array references within
> the code snippet?
Yes, we do.
> If the latter, I will hand-apply the patch.
Please do so.
Thanks, Akira
>
>> Fixing labels is left for your update.
>
> Will do, and yes, they are a bit of a mess just now. ;-)
>
> Thanx, Paul
>
>> Thanks, Akira
>> --
>> CodeSamples/datastruct/hash/hash_resize.c | 5 +++--
>> 1 file changed, 3 insertions(+), 2 deletions(-)
>>
>> diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
>> index bb0a6f4..7392455 100644
>> --- a/CodeSamples/datastruct/hash/hash_resize.c
>> +++ b/CodeSamples/datastruct/hash/hash_resize.c
>> @@ -154,10 +154,11 @@ 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=\\\[\]]
>> +//\begin{snippet}[labelbase=ln:datastruct:hash_resize:lock_unlock_mod,commandchars=\\\@\$]
>> /* Update-side lock/unlock functions. */
>> static void //\lnlbl{lock:b}
>> -resize_lock_mod(struct hashtab *htp_master, void *key, struct ht_bucket *ls[2])
>> +resize_lock_mod(struct hashtab *htp_master, void *key,
>> + struct ht_bucket *ls[2])
>> {
>> long b;
>> struct ht *htp;
>> --
>> 2.7.4
>>
>>
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
2019-01-03 23:35 ` Akira Yokosawa
@ 2019-01-04 0:52 ` Paul E. McKenney
2019-01-04 1:56 ` Akira Yokosawa
2019-01-04 15:38 ` Akira Yokosawa
1 sibling, 1 reply; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-04 0:52 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Fri, Jan 04, 2019 at 08:35:07AM +0900, Akira Yokosawa wrote:
> On 2019/01/03 09:21:45 -0800, Paul E. McKenney wrote:
> > On Fri, Jan 04, 2019 at 12:57:06AM +0900, Akira Yokosawa wrote:
> >> >From ae50debbf06ad674e4941b55764b02c776484509 Mon Sep 17 00:00:00 2001
> >> From: Akira Yokosawa <akiyks@gmail.com>
> >> Date: Fri, 4 Jan 2019 00:19:26 +0900
> >> Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
> >>
> >> Now that "[" and "]" are used within the code, "commandchars" should
> >> avoid them.
> >>
> >> Also wrap a line which has become too wide for the 2c layout.
> >>
> >> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> >
> > Ah, the lsp[2] was a temporary state. I forgot to do a final "git push"
> > yesterday, apologies!
> >
> >> ---
> >> Hi Paul,
> >>
> >> I'm in the middle of reading the updated code.
> >>
> >> I'm sure you are working on the update of Section 10.4.2.
> >> Because of the code change, there are quite a few broken refs
> >> and duplicated labels at the moment.
> >
> > Yes, it is a bit of a mess at this point. I figured that if I was
> > going to have to modify the text and labels, I might as well do the
> > extra work to make the API a little less obnoxious. My first attempt to
> > move hash_resize.c's hashtab_add() in this direction broke very badly,
> > so it is back to the drawing board.
> >
> > I am thinking in terms of having a single struct ht_lock_state that
> > contains an array or two as one part of making the API less obnoxious,
> > which should help avoid the brokenness.
> >
> >> This commit just takes care of the vanishing "[" and "]" in
> >> Listing 10.11.
> >
> > I am hoping that we can retain "[" and "]" -- it is normally not such
> > a good idea to have arrays in parameter lists.
> >
> > Or do we need this commit anyway just due to array references within
> > the code snippet?
>
> Yes, we do.
>
> > If the latter, I will hand-apply the patch.
>
> Please do so.
Like this? One reason that the patch didn't apply was that I had
already split the offending line.
Thanx, Paul
------------------------------------------------------------------------
commit d138666652d064f1ac891af7770dd220d51caa86
Author: Akira Yokosawa <akiyks@gmail.com>
Date: Thu Jan 3 16:50:25 2019 -0800
datastruct/hash: Tweak appearance of updated code in snippet
Now that "[" and "]" are used within the code, "commandchars" should
avoid them.
Also wrap a line which has become too wide for the 2c layout.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index 90ca6e57a21c..d042b2048083 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -159,7 +159,7 @@ 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=\\\[\]]
+//\begin{snippet}[labelbase=ln:datastruct:hash_resize:lock_unlock_mod,commandchars=\\\@\$]
/* Update-side lock/unlock functions. */
static void //\lnlbl{lock:b}
resize_lock_mod(struct hashtab *htp_master, void *key,
^ permalink raw reply related [flat|nested] 37+ messages in thread
* Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
2019-01-04 0:52 ` Paul E. McKenney
@ 2019-01-04 1:56 ` Akira Yokosawa
2019-01-04 3:56 ` Paul E. McKenney
0 siblings, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-04 1:56 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
On 2019/01/03 16:52:38 -0800, Paul E. McKenney wrote:
> On Fri, Jan 04, 2019 at 08:35:07AM +0900, Akira Yokosawa wrote:
>> On 2019/01/03 09:21:45 -0800, Paul E. McKenney wrote:
>>> On Fri, Jan 04, 2019 at 12:57:06AM +0900, Akira Yokosawa wrote:
>>>> >From ae50debbf06ad674e4941b55764b02c776484509 Mon Sep 17 00:00:00 2001
>>>> From: Akira Yokosawa <akiyks@gmail.com>
>>>> Date: Fri, 4 Jan 2019 00:19:26 +0900
>>>> Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
>>>>
>>>> Now that "[" and "]" are used within the code, "commandchars" should
>>>> avoid them.
>>>>
>>>> Also wrap a line which has become too wide for the 2c layout.
>>>>
>>>> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
>>>
>>> Ah, the lsp[2] was a temporary state. I forgot to do a final "git push"
>>> yesterday, apologies!
>>>
>>>> ---
>>>> Hi Paul,
>>>>
>>>> I'm in the middle of reading the updated code.
>>>>
>>>> I'm sure you are working on the update of Section 10.4.2.
>>>> Because of the code change, there are quite a few broken refs
>>>> and duplicated labels at the moment.
>>>
>>> Yes, it is a bit of a mess at this point. I figured that if I was
>>> going to have to modify the text and labels, I might as well do the
>>> extra work to make the API a little less obnoxious. My first attempt to
>>> move hash_resize.c's hashtab_add() in this direction broke very badly,
>>> so it is back to the drawing board.
>>>
>>> I am thinking in terms of having a single struct ht_lock_state that
>>> contains an array or two as one part of making the API less obnoxious,
>>> which should help avoid the brokenness.
>>>
>>>> This commit just takes care of the vanishing "[" and "]" in
>>>> Listing 10.11.
>>>
>>> I am hoping that we can retain "[" and "]" -- it is normally not such
>>> a good idea to have arrays in parameter lists.
>>>
>>> Or do we need this commit anyway just due to array references within
>>> the code snippet?
>>
>> Yes, we do.
>>
>>> If the latter, I will hand-apply the patch.
>>
>> Please do so.
>
> Like this? One reason that the patch didn't apply was that I had
> already split the offending line.
>
> Thanx, Paul
>
> ------------------------------------------------------------------------
>
> commit d138666652d064f1ac891af7770dd220d51caa86
> Author: Akira Yokosawa <akiyks@gmail.com>
> Date: Thu Jan 3 16:50:25 2019 -0800
>
> datastruct/hash: Tweak appearance of updated code in snippet
>
> Now that "[" and "]" are used within the code, "commandchars" should
> avoid them.
>
> Also wrap a line which has become too wide for the 2c layout.
This sentence can be omitted in the commit log.
The diff itself looks good to me.
Thanks, Akira
>
> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
>
> diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> index 90ca6e57a21c..d042b2048083 100644
> --- a/CodeSamples/datastruct/hash/hash_resize.c
> +++ b/CodeSamples/datastruct/hash/hash_resize.c
> @@ -159,7 +159,7 @@ 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=\\\[\]]
> +//\begin{snippet}[labelbase=ln:datastruct:hash_resize:lock_unlock_mod,commandchars=\\\@\$]
> /* Update-side lock/unlock functions. */
> static void //\lnlbl{lock:b}
> resize_lock_mod(struct hashtab *htp_master, void *key,
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
2019-01-04 1:56 ` Akira Yokosawa
@ 2019-01-04 3:56 ` Paul E. McKenney
0 siblings, 0 replies; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-04 3:56 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Fri, Jan 04, 2019 at 10:56:29AM +0900, Akira Yokosawa wrote:
> On 2019/01/03 16:52:38 -0800, Paul E. McKenney wrote:
> > On Fri, Jan 04, 2019 at 08:35:07AM +0900, Akira Yokosawa wrote:
> >> On 2019/01/03 09:21:45 -0800, Paul E. McKenney wrote:
> >>> On Fri, Jan 04, 2019 at 12:57:06AM +0900, Akira Yokosawa wrote:
> >>>> >From ae50debbf06ad674e4941b55764b02c776484509 Mon Sep 17 00:00:00 2001
> >>>> From: Akira Yokosawa <akiyks@gmail.com>
> >>>> Date: Fri, 4 Jan 2019 00:19:26 +0900
> >>>> Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
> >>>>
> >>>> Now that "[" and "]" are used within the code, "commandchars" should
> >>>> avoid them.
> >>>>
> >>>> Also wrap a line which has become too wide for the 2c layout.
> >>>>
> >>>> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> >>>
> >>> Ah, the lsp[2] was a temporary state. I forgot to do a final "git push"
> >>> yesterday, apologies!
> >>>
> >>>> ---
> >>>> Hi Paul,
> >>>>
> >>>> I'm in the middle of reading the updated code.
> >>>>
> >>>> I'm sure you are working on the update of Section 10.4.2.
> >>>> Because of the code change, there are quite a few broken refs
> >>>> and duplicated labels at the moment.
> >>>
> >>> Yes, it is a bit of a mess at this point. I figured that if I was
> >>> going to have to modify the text and labels, I might as well do the
> >>> extra work to make the API a little less obnoxious. My first attempt to
> >>> move hash_resize.c's hashtab_add() in this direction broke very badly,
> >>> so it is back to the drawing board.
> >>>
> >>> I am thinking in terms of having a single struct ht_lock_state that
> >>> contains an array or two as one part of making the API less obnoxious,
> >>> which should help avoid the brokenness.
> >>>
> >>>> This commit just takes care of the vanishing "[" and "]" in
> >>>> Listing 10.11.
> >>>
> >>> I am hoping that we can retain "[" and "]" -- it is normally not such
> >>> a good idea to have arrays in parameter lists.
> >>>
> >>> Or do we need this commit anyway just due to array references within
> >>> the code snippet?
> >>
> >> Yes, we do.
> >>
> >>> If the latter, I will hand-apply the patch.
> >>
> >> Please do so.
> >
> > Like this? One reason that the patch didn't apply was that I had
> > already split the offending line.
> >
> > Thanx, Paul
> >
> > ------------------------------------------------------------------------
> >
> > commit d138666652d064f1ac891af7770dd220d51caa86
> > Author: Akira Yokosawa <akiyks@gmail.com>
> > Date: Thu Jan 3 16:50:25 2019 -0800
> >
> > datastruct/hash: Tweak appearance of updated code in snippet
> >
> > Now that "[" and "]" are used within the code, "commandchars" should
> > avoid them.
> >
> > Also wrap a line which has become too wide for the 2c layout.
>
> This sentence can be omitted in the commit log.
> The diff itself looks good to me.
Good point, done!
Thanx, Paul
> Thanks, Akira
>
> >
> > Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
> > Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
> >
> > diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> > index 90ca6e57a21c..d042b2048083 100644
> > --- a/CodeSamples/datastruct/hash/hash_resize.c
> > +++ b/CodeSamples/datastruct/hash/hash_resize.c
> > @@ -159,7 +159,7 @@ 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=\\\[\]]
> > +//\begin{snippet}[labelbase=ln:datastruct:hash_resize:lock_unlock_mod,commandchars=\\\@\$]
> > /* Update-side lock/unlock functions. */
> > static void //\lnlbl{lock:b}
> > resize_lock_mod(struct hashtab *htp_master, void *key,
> >
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
2019-01-03 23:35 ` Akira Yokosawa
2019-01-04 0:52 ` Paul E. McKenney
@ 2019-01-04 15:38 ` Akira Yokosawa
2019-01-04 15:39 ` [PATCH 1/2] datastruct/hash: Tweak indent of folded line " Akira Yokosawa
2019-01-04 15:41 ` [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE Akira Yokosawa
1 sibling, 2 replies; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-04 15:38 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
Hi Paul,
Now I know why you needed to hand-apply the patch.
My patch used white space characters in the indent of the folded line.
You used tab characters. Hence the conflict.
For the folded line to be properly aligned with the previous line
in the resulting Listing, it should have the same number of tabs
as the previous line. Deeper indent should be represented by
space characters.
I'm submitting a patch to fix the indent of resize_lock_mod().
Also, there is some racy accesses in hash_resize.c.
2nd patch adds READ_ONCEs/WRITE_ONCEs where I think the accesses
are racy. Please have a look to see if they are really necessary.
This is not formatted as a cover letter. Sorry about that.
Thanks, Akira
^ permalink raw reply [flat|nested] 37+ messages in thread
* [PATCH 1/2] datastruct/hash: Tweak indent of folded line in snippet
2019-01-04 15:38 ` Akira Yokosawa
@ 2019-01-04 15:39 ` Akira Yokosawa
2019-01-04 22:40 ` Paul E. McKenney
2019-01-04 15:41 ` [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE Akira Yokosawa
1 sibling, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-04 15:39 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From 426fa84ef7b5c6d0200dbd79d213e02ae31badad Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Fri, 4 Jan 2019 23:40:14 +0900
Subject: [PATCH 1/2] datastruct/hash: Tweak indent of folded line in snippet
For a folded line to be properly indented in the Listing environment,
it has to have the same number of tab characters as the previous
line in the code. If the folded line has a deeper indent to align
with some construct of the previous line, remaining indent depth
should be represented by space characters.
Apply this rule to the function prototype of resize_lock_mod().
In this case, as the previous line doesn't have any tab characters,
space characters should be used for all of its indent.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/datastruct/hash/hash_resize.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index 475a2ab..57c75c1 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -163,7 +163,7 @@ static void hashtab_unlock_lookup(struct hashtab *htp_master, void *key)
/* Update-side lock/unlock functions. */
static void //\lnlbl{lock:b}
resize_lock_mod(struct hashtab *htp_master, void *key,
- struct ht_lock_state *lsp)
+ struct ht_lock_state *lsp)
{
long b;
struct ht *htp;
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE
2019-01-04 15:38 ` Akira Yokosawa
2019-01-04 15:39 ` [PATCH 1/2] datastruct/hash: Tweak indent of folded line " Akira Yokosawa
@ 2019-01-04 15:41 ` Akira Yokosawa
2019-01-05 0:10 ` Paul E. McKenney
1 sibling, 1 reply; 37+ messages in thread
From: Akira Yokosawa @ 2019-01-04 15:41 UTC (permalink / raw)
To: Paul E. McKenney; +Cc: perfbook, Akira Yokosawa
From ed528d05b7800d651ef5e36de37732a06b456462 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <akiyks@gmail.com>
Date: Sat, 5 Jan 2019 00:15:47 +0900
Subject: [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE
ht_get_bucket() runs concurrently with hash_resize().
As a defensive coding rule to survive compiler optimization,
accesses to (*htp)->ht_resize_cur, (*htp)->ht_new, and
(*htp)->ht_idx should be annotated by READ_ONCE/WRITE_ONCE.
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
---
CodeSamples/datastruct/hash/hash_resize.c | 12 ++++++------
1 file changed, 6 insertions(+), 6 deletions(-)
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index 57c75c1..e1d92a6 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -137,13 +137,13 @@ ht_get_bucket(struct ht **htp, void *key, long *b, int *i)
htbp = ht_get_bucket_single(*htp, key, b); //\lnlbl{call_single}
//\fcvexclude
- if (*b <= (*htp)->ht_resize_cur) { //\lnlbl{resized}
+ if (*b <= READ_ONCE((*htp)->ht_resize_cur)) { //\lnlbl{resized}
smp_mb(); /* order ->ht_resize_cur before ->ht_new. */
- *htp = (*htp)->ht_new; //\lnlbl{newtable}
+ *htp = READ_ONCE((*htp)->ht_new); //\lnlbl{newtable}
htbp = ht_get_bucket_single(*htp, key, b); //\lnlbl{newbucket}
}
if (i) //\lnlbl{chk_i}
- *i = (*htp)->ht_idx; //\lnlbl{set_idx}
+ *i = READ_ONCE((*htp)->ht_idx); //\lnlbl{set_idx}
return htbp; //\lnlbl{return}
} //\lnlbl{e}
//\end{snippet}
@@ -301,10 +301,10 @@ int hashtab_resize(struct hashtab *htp_master,
spin_unlock(&htp_master->ht_lock); //\lnlbl{rel_nomem}
return -ENOMEM; //\lnlbl{ret_nomem}
}
- htp->ht_new = htp_new; //\lnlbl{set_newtbl}
+ WRITE_ONCE(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;
+ WRITE_ONCE(htp_new->ht_idx, !idx);
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}
@@ -315,7 +315,7 @@ int hashtab_resize(struct hashtab *htp_master,
spin_unlock(&htbp_new->htb_lock);
} //\lnlbl{loop_list:e}
smp_mb(); /* Fill new buckets before claiming them. */
- htp->ht_resize_cur = i; //\lnlbl{update_resize}
+ WRITE_ONCE(htp->ht_resize_cur, i); //\lnlbl{update_resize}
spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
} //\lnlbl{loop:e}
rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
--
2.7.4
^ permalink raw reply related [flat|nested] 37+ messages in thread
* Re: [PATCH 1/2] datastruct/hash: Tweak indent of folded line in snippet
2019-01-04 15:39 ` [PATCH 1/2] datastruct/hash: Tweak indent of folded line " Akira Yokosawa
@ 2019-01-04 22:40 ` Paul E. McKenney
0 siblings, 0 replies; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-04 22:40 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Sat, Jan 05, 2019 at 12:39:56AM +0900, Akira Yokosawa wrote:
> >From 426fa84ef7b5c6d0200dbd79d213e02ae31badad Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Fri, 4 Jan 2019 23:40:14 +0900
> Subject: [PATCH 1/2] datastruct/hash: Tweak indent of folded line in snippet
>
> For a folded line to be properly indented in the Listing environment,
> it has to have the same number of tab characters as the previous
> line in the code. If the folded line has a deeper indent to align
> with some construct of the previous line, remaining indent depth
> should be represented by space characters.
>
> Apply this rule to the function prototype of resize_lock_mod().
> In this case, as the previous line doesn't have any tab characters,
> space characters should be used for all of its indent.
>
> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
Ah, good point, I well recall doing that by hand when creating the
old-style code displays. I applied this by hand due to an intervening
conflict and pushed it.
Thanx, Paul
> ---
> CodeSamples/datastruct/hash/hash_resize.c | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> index 475a2ab..57c75c1 100644
> --- a/CodeSamples/datastruct/hash/hash_resize.c
> +++ b/CodeSamples/datastruct/hash/hash_resize.c
> @@ -163,7 +163,7 @@ static void hashtab_unlock_lookup(struct hashtab *htp_master, void *key)
> /* Update-side lock/unlock functions. */
> static void //\lnlbl{lock:b}
> resize_lock_mod(struct hashtab *htp_master, void *key,
> - struct ht_lock_state *lsp)
> + struct ht_lock_state *lsp)
> {
> long b;
> struct ht *htp;
> --
> 2.7.4
>
>
^ permalink raw reply [flat|nested] 37+ messages in thread
* Re: [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE
2019-01-04 15:41 ` [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE Akira Yokosawa
@ 2019-01-05 0:10 ` Paul E. McKenney
0 siblings, 0 replies; 37+ messages in thread
From: Paul E. McKenney @ 2019-01-05 0:10 UTC (permalink / raw)
To: Akira Yokosawa; +Cc: perfbook
On Sat, Jan 05, 2019 at 12:41:25AM +0900, Akira Yokosawa wrote:
> >From ed528d05b7800d651ef5e36de37732a06b456462 Mon Sep 17 00:00:00 2001
> From: Akira Yokosawa <akiyks@gmail.com>
> Date: Sat, 5 Jan 2019 00:15:47 +0900
> Subject: [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE
>
> ht_get_bucket() runs concurrently with hash_resize().
> As a defensive coding rule to survive compiler optimization,
> accesses to (*htp)->ht_resize_cur, (*htp)->ht_new, and
> (*htp)->ht_idx should be annotated by READ_ONCE/WRITE_ONCE.
>
> Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
Thank you!
The trick I used to avoid having to apply this before getting the bugs
fixed was to compile with -O0. Crude, but effective. Plus handy in
that it allows gdb to actually show you the values of all the variables
instead of just saying the ones you need have been optimized out. ;-)
Responses below, and update patch after that. As always, please let
me know if I messed something up.
Thanx, Paul
> ---
> CodeSamples/datastruct/hash/hash_resize.c | 12 ++++++------
> 1 file changed, 6 insertions(+), 6 deletions(-)
>
> diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> index 57c75c1..e1d92a6 100644
> --- a/CodeSamples/datastruct/hash/hash_resize.c
> +++ b/CodeSamples/datastruct/hash/hash_resize.c
> @@ -137,13 +137,13 @@ ht_get_bucket(struct ht **htp, void *key, long *b, int *i)
>
> htbp = ht_get_bucket_single(*htp, key, b); //\lnlbl{call_single}
> //\fcvexclude
> - if (*b <= (*htp)->ht_resize_cur) { //\lnlbl{resized}
> + if (*b <= READ_ONCE((*htp)->ht_resize_cur)) { //\lnlbl{resized}
Good point, this one is needed.
> smp_mb(); /* order ->ht_resize_cur before ->ht_new. */
> - *htp = (*htp)->ht_new; //\lnlbl{newtable}
> + *htp = READ_ONCE((*htp)->ht_new); //\lnlbl{newtable}
This one needs to be rcu_dereference().
> htbp = ht_get_bucket_single(*htp, key, b); //\lnlbl{newbucket}
> }
> if (i) //\lnlbl{chk_i}
> - *i = (*htp)->ht_idx; //\lnlbl{set_idx}
> + *i = READ_ONCE((*htp)->ht_idx); //\lnlbl{set_idx}
This is -not- needed because ->ht_idx is constant once the new set of
buckets is exposed to readers. (Yes, it was exposed before the last
change when you produced this patch, but that was just me being stupid,
so it is now fixed.)
> return htbp; //\lnlbl{return}
> } //\lnlbl{e}
> //\end{snippet}
> @@ -301,10 +301,10 @@ int hashtab_resize(struct hashtab *htp_master,
> spin_unlock(&htp_master->ht_lock); //\lnlbl{rel_nomem}
> return -ENOMEM; //\lnlbl{ret_nomem}
> }
> - htp->ht_new = htp_new; //\lnlbl{set_newtbl}
> + WRITE_ONCE(htp->ht_new, htp_new); //\lnlbl{set_newtbl}
This is now an smp_store_release(). Hmmm... It really needs to instead
be rcu_assign_pointer(), doesn't it?
> synchronize_rcu(); //\lnlbl{sync_rcu}
> idx = htp->ht_idx; //\lnlbl{get_curidx}
> - htp_new->ht_idx = !idx;
> + WRITE_ONCE(htp_new->ht_idx, !idx);
Now that this is ordered before the ->ht_new update, it can just be a
plain store.
> 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}
> @@ -315,7 +315,7 @@ int hashtab_resize(struct hashtab *htp_master,
> spin_unlock(&htbp_new->htb_lock);
> } //\lnlbl{loop_list:e}
> smp_mb(); /* Fill new buckets before claiming them. */
> - htp->ht_resize_cur = i; //\lnlbl{update_resize}
> + WRITE_ONCE(htp->ht_resize_cur, i); //\lnlbl{update_resize}
Good catch, this is needed.
> spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
> } //\lnlbl{loop:e}
> rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
------------------------------------------------------------------------
commit 714422e1a98ffdf3de8bc0b87896eccec24be272
Author: Akira Yokosawa <akiyks@gmail.com>
Date: Fri Jan 4 16:07:22 2019 -0800
datastruct/hash: Annotate racy accesses
Because the resizable hash table allows adds, deletes, and lookups to
run concurrently with resizing, ht_get_bucket() can run concurrently
with hash_resize(). As a defensive coding rule to survive compiler
optimization, accesses to (*htp)->ht_resize_cur should be annotated
by rcu_dereference()/rcu_assign_pointer() and (*htp)->ht_new should be
annotated by READ_ONCE()/WRITE_ONCE().
Signed-off-by: Akira Yokosawa <akiyks@gmail.com>
[ paulmck: Adjusted based on recent changes. ]
Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com>
diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
index 37251a769212..173043a5b788 100644
--- a/CodeSamples/datastruct/hash/hash_resize.c
+++ b/CodeSamples/datastruct/hash/hash_resize.c
@@ -143,9 +143,9 @@ ht_get_bucket(struct ht **htp, void *key, long *b, int *i)
htbp = ht_get_bucket_single(*htp, key, b, NULL); //\lnlbl{call_single}
//\fcvexclude
- if (*b <= (*htp)->ht_resize_cur) { //\lnlbl{resized}
+ if (*b <= READ_ONCE((*htp)->ht_resize_cur)) { //\lnlbl{resized}
smp_mb(); /* order ->ht_resize_cur before ->ht_new. */
- *htp = (*htp)->ht_new; //\lnlbl{newtable}
+ *htp = rcu_dereference((*htp)->ht_new); //\lnlbl{newtable}
htbp = ht_get_bucket_single(*htp, key, b, NULL); //\lnlbl{newbucket}
}
if (i) //\lnlbl{chk_i}
@@ -185,7 +185,7 @@ resize_lock_mod(struct hashtab *htp_master, void *key,
lsp->hbp[0] = htbp;
lsp->hls_idx[0] = htp->ht_idx;
lsp->hls_hash[0] = h;
- if (b > htp->ht_resize_cur) { //\lnlbl{lock:chk_resz_dist}
+ if (b > READ_ONCE(htp->ht_resize_cur)) { //\lnlbl{lock:chk_resz_dist}
lsp->hbp[1] = NULL;
return; //\lnlbl{lock:fastret1}
}
@@ -303,7 +303,7 @@ int hashtab_resize(struct hashtab *htp_master,
}
idx = htp->ht_idx; //\lnlbl{get_curidx}
htp_new->ht_idx = !idx;
- smp_store_release(&htp->ht_new, htp_new); //\lnlbl{set_newtbl}
+ rcu_assign_pointer(htp->ht_new, htp_new); //\lnlbl{set_newtbl}
synchronize_rcu(); //\lnlbl{sync_rcu}
for (i = 0; i < htp->ht_nbuckets; i++) { //\lnlbl{loop:b}
htbp = &htp->ht_bkt[i]; //\lnlbl{get_oldcur}
@@ -315,7 +315,7 @@ int hashtab_resize(struct hashtab *htp_master,
spin_unlock(&htbp_new->htb_lock);
} //\lnlbl{loop_list:e}
smp_mb(); /* Fill new buckets before claiming them. */
- htp->ht_resize_cur = i; //\lnlbl{update_resize}
+ WRITE_ONCE(htp->ht_resize_cur, i); //\lnlbl{update_resize}
spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
} //\lnlbl{loop:e}
rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
^ permalink raw reply related [flat|nested] 37+ messages in thread
end of thread, other threads:[~2019-01-05 0:10 UTC | newest]
Thread overview: 37+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2018-12-24 14:46 [PATCH 00/11] datastruct: Employ new scheme for code snippet Akira Yokosawa
2018-12-24 14:53 ` [PATCH 01/11] fcvextract.pl: Enhance comment block handling of C source Akira Yokosawa
2018-12-24 14:55 ` [PATCH 02/11] CodeSamples: Add explicit 'keepcomment=yes' options Akira Yokosawa
2018-12-24 14:56 ` [PATCH 03/11] fcvextract.pl: Make 'keepcomment=no' as default Akira Yokosawa
2018-12-24 14:57 ` [PATCH 04/11] CodeSamples: Remove redundant \fcvexclude Akira Yokosawa
2018-12-24 14:59 ` [PATCH 05/11] fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source Akira Yokosawa
2018-12-24 15:00 ` [PATCH 06/11] datastruct: Employ new scheme for snippets of hash_bkt.c Akira Yokosawa
2018-12-24 15:01 ` [PATCH 07/11] datastruct: Update hashdiagram figure Akira Yokosawa
2018-12-24 15:02 ` [PATCH 08/11] datastruct: Employ new scheme for snippets of hash_bkt_rcu and hash_resize Akira Yokosawa
2018-12-24 15:03 ` [PATCH 09/11] Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env Akira Yokosawa
2018-12-24 15:04 ` [PATCH 10/11] Use wider tabsize for snippet in 'listing*' Akira Yokosawa
2018-12-24 15:05 ` [PATCH 11/11] datastruct: Tweak hyphenation Akira Yokosawa
2018-12-24 23:58 ` [PATCH 00/11] datastruct: Employ new scheme for code snippet Paul E. McKenney
2018-12-25 0:53 ` Paul E. McKenney
2018-12-25 14:30 ` Akira Yokosawa
2018-12-26 14:17 ` Paul E. McKenney
2018-12-26 14:31 ` [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files Akira Yokosawa
2018-12-26 15:00 ` Paul E. McKenney
2018-12-31 4:37 ` Sporadic SIGSEGV in hash_bkt_rcu and hash_resize (was Re: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files) Akira Yokosawa
2018-12-31 15:15 ` [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu Akira Yokosawa
2018-12-31 21:03 ` Paul E. McKenney
2019-01-01 0:27 ` Akira Yokosawa
2019-01-01 18:00 ` Paul E. McKenney
2019-01-02 15:02 ` Akira Yokosawa
2019-01-02 17:18 ` Paul E. McKenney
2019-01-02 19:18 ` Paul E. McKenney
2019-01-03 15:57 ` [PATCH] datastruct/hash: Tweak appearance of updated code in snippet Akira Yokosawa
2019-01-03 17:21 ` Paul E. McKenney
2019-01-03 23:35 ` Akira Yokosawa
2019-01-04 0:52 ` Paul E. McKenney
2019-01-04 1:56 ` Akira Yokosawa
2019-01-04 3:56 ` Paul E. McKenney
2019-01-04 15:38 ` Akira Yokosawa
2019-01-04 15:39 ` [PATCH 1/2] datastruct/hash: Tweak indent of folded line " Akira Yokosawa
2019-01-04 22:40 ` Paul E. McKenney
2019-01-04 15:41 ` [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE Akira Yokosawa
2019-01-05 0:10 ` Paul E. McKenney
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.