datastruct: Employ new scheme for code snippet
cover datastruct: Employ new scheme for code snippet
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(-)
Signature · 1 line
2.7.4
PATCH 1/11 fcvextract.pl: Enhance comment block handling of C source
From b7193f419457aff8b34c4d293f6b747770d1a911 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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>
#endifNOTE 1: "#else" is optional.
NOTE 2: FCV_SNIPPET should never be defined.
--- utilities/fcvextract.pl | 82 ++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 77 insertions(+), 5 deletions(-)
utilities/fcvextract.pl +77 -5
@@ -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 <[email protected]>
@@ -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/,$// ;
Signature · 1 line
2.7.4
PATCH 2/11 CodeSamples: Add explicit 'keepcomment=yes' options
In reply to Akira YokosawaFrom f3f0bb0be7ce81a418aed0fe56e6bad06c36aaca Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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".
--- 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(-)
CodeSamples/SMPdesign/lockhdeq.c +4 -3
@@ -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}
CodeSamples/count/count_tstat.c +1 -1
@@ -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 ;
CodeSamples/defer/route_rcu.c +6 -5
@@ -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
CodeSamples/toolsoftrade/forkjoinvar.c +1 -1
@@ -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[])
CodeSamples/toolsoftrade/pcreate.c +1 -1
@@ -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)
Signature · 1 line
2.7.4
PATCH 3/11 fcvextract.pl: Make 'keepcomment=no' as default
In reply to Akira YokosawaFrom e9d75e866a39a9c9af9bf4c2da7c64225b302d42 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.
--- utilities/fcvextract.pl | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-)
utilities/fcvextract.pl +5 -5
@@ -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=[^,\]]+,?// ;
Signature · 1 line
2.7.4
PATCH 4/11 CodeSamples: Remove redundant \fcvexclude
In reply to Akira YokosawaFrom 426d265864aa5865da6a331493d22996bfddd4a8 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.
--- 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(-)
CodeSamples/SMPdesign/lockhdeq.c +2 -2
@@ -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}
CodeSamples/SMPdesign/smpalloc.c +5 -3
@@ -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;
CodeSamples/count/count_end.c +5 -3
@@ -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} {
CodeSamples/count/count_lim.c +5 -3
@@ -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} {
CodeSamples/count/count_tstat.c +5 -3
@@ -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) {
CodeSamples/defer/route_hazptr.c +10 -10
@@ -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;
CodeSamples/defer/route_rcu.c +13 -12
@@ -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;
CodeSamples/defer/route_refcnt.c +8 -8
@@ -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;
CodeSamples/defer/route_seq.c +9 -9
@@ -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;
CodeSamples/defer/route_seqlock.c +7 -7
@@ -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;
CodeSamples/defer/seqlock.h +7 -5
@@ -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 ;
CodeSamples/locking/locked_list.c +4 -2
@@ -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) {
Signature · 1 line
2.7.4
PATCH 5/11 fcvextract.pl: Support '/* \lnlbl{...} */' style label in C source
In reply to Akira YokosawaFrom f5a7cdba0ffb249111f4cf0d83896c0ce368e736 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.
--- utilities/fcvextract.pl | 5 +++++ 1 file changed, 5 insertions(+)
utilities/fcvextract.pl +5 -0
@@ -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 =~ /\*\/(.*$)/) {
Signature · 1 line
2.7.4
PATCH 6/11 datastruct: Employ new scheme for snippets of hash_bkt.c
In reply to Akira YokosawaFrom 4e71dc2a3c253e78785f5320f8dd9419d968bf25 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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").
--- CodeSamples/datastruct/hash/hash_bkt.c | 96 +++++++++------- datastruct/datastruct.tex | 193 +++++++++------------------------ 2 files changed, 111 insertions(+), 178 deletions(-)
CodeSamples/datastruct/hash/hash_bkt.c +57 -39
@@ -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"
datastruct/datastruct.tex +54 -139
284 lines not on this page · raw message
Signature · 1 line
2.7.4
PATCH 7/11 datastruct: Update hashdiagram figure
In reply to Akira YokosawaFrom 075c5f2affb207010d7c5e7d5cd7ee3233fa060a Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 23 Dec 2018 15:23:43 +0900
Subject: [PATCH 07/11] datastruct: Update hashdiagram figure
Add ht_cmp field to struct hashtab.
--- datastruct/hashdiagram.fig | 103 +++++++++++++++++++++++---------------------- 1 file changed, 53 insertions(+), 50 deletions(-)
datastruct/hashdiagram.fig +53 -50
@@ -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
Signature · 1 line
2.7.4
PATCH 8/11 datastruct: Employ new scheme for snippets of hash_bkt_rcu and hash_resize
In reply to Akira YokosawaFrom e94531367e4c5bc66a7cabe2e1e41e80dedf5a53 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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().
--- 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(-)
CodeSamples/datastruct/hash/hash_bkt_rcu.c +24 -9
@@ -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.
CodeSamples/datastruct/hash/hash_resize.c +128 -104
331 lines not on this page · raw message
datastruct/datastruct.tex +132 -360
698 lines not on this page · raw message
Signature · 1 line
2.7.4
PATCH 9/11 Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env
In reply to Akira YokosawaFrom 6267c0822e5286667e3cc0dc873e79bafd4b4bb6 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Sun, 23 Dec 2018 23:45:40 +0900
Subject: [PATCH 09/11] Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env
--- perfbook.tex | 2 ++ 1 file changed, 2 insertions(+)
perfbook.tex +2 -0
@@ -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}} }{}
Signature · 1 line
2.7.4
PATCH 10/11 Use wider tabsize for snippet in 'listing*'
In reply to Akira YokosawaFrom deac40976c6104677a6ede3b13f8aa4361ecabbd Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.
--- CodeSamples/datastruct/hash/hash_resize.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
CodeSamples/datastruct/hash/hash_resize.c +1 -1
@@ -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,
Signature · 1 line
2.7.4
PATCH 11/11 datastruct: Tweak hyphenation
In reply to Akira YokosawaFrom 2d807fdaa140d87199167b78bb53e805cae5eb94 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
Date: Mon, 24 Dec 2018 20:02:14 +0900
Subject: [PATCH 11/11] datastruct: Tweak hyphenation
--- datastruct/datastruct.tex | 2 +- pfhyphex.tex | 1 + 2 files changed, 2 insertions(+), 1 deletion(-)
datastruct/datastruct.tex +1 -1
@@ -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
pfhyphex.tex +1 -0
@@ -3,4 +3,5 @@ COPART GPGPU GPGPUs + Schr\"o-din-ger }
Signature · 1 line
2.7.4
Quoted 27 lines · 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.
Quoted 5 lines
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.
Quoted 8 lines
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 inht_get_bucket()(Listing 10.10).
Quoted 6 lines
My guess is that the counterpart barrier is the first
synchronize_rcu()inhashtab_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 thoughhash_reorder.cused 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? ;-)
Quoted 8 lines
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
Quoted 43 lines
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 ofhash_bkt.c
datastruct: Update hashdiagram figure
datastruct: Employ new scheme for snippets ofhash_bkt_rcuand
hash_resize
Make sure lmtt font is used in 'VerbatimL' and 'Verbatim' env Use wider tabsize for snippet in 'listing*'
datastruct: Tweak hyphenationCodeSamples/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(-)Signature · 1 line
2.7.4
Quoted 51 lines · Paul E. McKenney
Quoted 27 lines · 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.Quoted 5 lines
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.
Quoted 8 lines
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 inht_get_bucket()(Listing 10.10).Quoted 6 lines
My guess is that the counterpart barrier is the first
synchronize_rcu()inhashtab_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 thoughhash_reorder.cused something more than the pure RCU protection. But I might be completely misreading here...
Quoted 3 lines
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/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:data > CodeSamples/datastruct/hash/[email protected] 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/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:access > CodeSamples/datastruct/hash/[email protected] CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:resize > CodeSamples/datastruct/hash/[email protected] 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
------------------------------------------------------------------------
CodeSamples/datastruct/hash/hash_resize.c +2 -1
@@ -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}
Quoted 77 lines · Paul E. McKenney
Quoted 51 lines · Paul E. McKenney
Quoted 27 lines · 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.Quoted 5 lines
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.
Quoted 8 lines
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 inht_get_bucket()(Listing 10.10).Quoted 6 lines
My guess is that the counterpart barrier is the first
synchronize_rcu()inhashtab_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 thoughhash_reorder.cused something more than the pure RCU protection. But I might be completely misreading here...Quoted 3 lines
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/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:data > CodeSamples/datastruct/hash/[email protected] 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/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:access > CodeSamples/datastruct/hash/[email protected] CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:resize > CodeSamples/datastruct/hash/[email protected] 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
Quoted 7 lines
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.copen 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
Quoted 26 lines
Thanx, Paul
------------------------------------------------------------------------
CodeSamples/datastruct/hash/hash_resize.c +2
-1@@ -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}
Quoted 86 lines · Akira Yokosawa
Quoted 77 lines · Paul E. McKenney
Quoted 51 lines · Paul E. McKenney
Quoted 27 lines · 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.Quoted 5 lines
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.
Quoted 8 lines
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 inht_get_bucket()(Listing 10.10).Quoted 6 lines
My guess is that the counterpart barrier is the first
synchronize_rcu()inhashtab_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 thoughhash_reorder.cused something more than the pure RCU protection. But I might be completely misreading here...Quoted 3 lines
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/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:data > CodeSamples/datastruct/hash/[email protected] 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/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:access > CodeSamples/datastruct/hash/[email protected] CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/[email protected] utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:resize > CodeSamples/datastruct/hash/[email protected] 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 1Quoted 7 lines
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.copen 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.
Quoted 4 lines
I see.
I'll add rules in
utilities/gen_snippet_d.plso 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. :-/
Quoted 4 lines
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
Quoted 29 lines
Thanks, Akira
Quoted 26 lines
Thanx, Paul
------------------------------------------------------------------------
CodeSamples/datastruct/hash/hash_resize.c +2
-1@@ -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}
PATCH 1/1 gen_snippet_d.pl: Add rules to ignore editor's backup files
In reply to Akira YokosawaFrom 6c0e6e632bbf234de340bcf51acf2007d8e3ac8b Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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/[email protected]
[...]
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.
---
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(-)
utilities/gen_snippet_d.pl +10 -6
@@ -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 ;
Signature · 1 line
2.7.4
Re: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files
Quoted 28 lines · Akira Yokosawa
Quoted 1 line
From
6c0e6e632bbf234de340bcf51acf2007d8e3ac8bMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Wed, 26 Dec 2018 23:11:26 +0900
Subject: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup filesExcerpt 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/[email protected] [...] 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 <[email protected]>Signed-off-by Akira Yokosawa <[email protected]>---
Paul,
Quoted 8 lines
This should ignore .swp files in the dependency file. Can you test "make" while opening
hash_resize.cin 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
Quoted 61 lines
--
utilities/gen_snippet_d.pl | 16 ++++++++++------ 1 file changed, 10 insertions(+), 6 deletions(-)utilities/gen_snippet_d.pl +10
-6@@ -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 ;Signature · 1 line
2.7.4
Sporadic SIGSEGV in hash_bkt_rcu and hash_resize (was Re: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup files)
Quoted 40 lines · Paul E. McKenney
Quoted 28 lines · Akira Yokosawa
Quoted 1 line
From
6c0e6e632bbf234de340bcf51acf2007d8e3ac8bMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Wed, 26 Dec 2018 23:11:26 +0900
Subject: [PATCH] gen_snippet_d.pl: Add rules to ignore editor's backup filesExcerpt 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/[email protected] [...] 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 <[email protected]>Signed-off-by Akira Yokosawa <[email protected]>---
Paul,Quoted 8 lines
This should ignore .swp files in the dependency file. Can you test "make" while opening
hash_resize.cin vim?Thanks, Akira
PS:
I'll comment on the update of Quick Quiz 10.13 later this week.
Works great, thank you!!!
Quoted 7 lines
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
Quoted 3 lines
Thanx, Paul
[...]
PATCH 1/1 EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
From 52f5d218442eb64f2798335d56a1838f90d96d5f Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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---
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(-)
CodeSamples/datastruct/hash/hashtorture.h +16 -8
@@ -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 ; }
Signature · 1 line
2.7.4
Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
Quoted 29 lines · Akira Yokosawa
Quoted 1 line
From
52f5d218442eb64f2798335d56a1838f90d96d5fMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 30 Dec 2018 22:54:43 +0900
Subject: [PATCH] EXPhashtorture.h: Avoid sporadic SIGSEGV inhash_bkt_rcuCommit
4e22bdc905ff("Wait at end of test forcall_rcu()to finish") added a couple of synchronize_rcu()s inperftest_update()andzoo_reader().However, there still remains sporadic SIGSEGV in
$ ./hash_bkt_rcu --perftest --nupdaters 3On the other hand,
$ ./hash_bkt_rcu --schroedinger --nupdaters 3does not show such issue. Just moving synchronize_rcu()s in
zoo_reader()tozoo_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 ofperftest_updater()andzoo_updater().It looks like this change can fix the above mentioned SIGSEGV in "--perftest".
Quoted 6 lines
[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!
Quoted 14 lines
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
Quoted 1 line
Signed-off-by Akira Yokosawa <[email protected]>
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.
Quoted 10 lines
---
Hi Paul,This is a partial fix, but it resolves SIGSEGV in "--perftest" of
hash_bkt_rcuandhash_resize."--schroedinger" of
hash_resizewith 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
Quoted 88 lines
Thanks, Akira
--CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-)CodeSamples/datastruct/hash/hashtorture.h +16
-8@@ -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 ; }Signature · 1 line
2.7.4
Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
Quoted 33 lines · Paul E. McKenney
Quoted 32 lines · Akira Yokosawa
Quoted 1 line
From
52f5d218442eb64f2798335d56a1838f90d96d5fMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 30 Dec 2018 22:54:43 +0900
Subject: [PATCH] EXPhashtorture.h: Avoid sporadic SIGSEGV inhash_bkt_rcuCommit
4e22bdc905ff("Wait at end of test forcall_rcu()to finish") added a couple of synchronize_rcu()s inperftest_update()andzoo_reader().However, there still remains sporadic SIGSEGV in
$ ./hash_bkt_rcu --perftest --nupdaters 3On the other hand,
$ ./hash_bkt_rcu --schroedinger --nupdaters 3does not show such issue. Just moving synchronize_rcu()s in
zoo_reader()tozoo_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 ofperftest_updater()andzoo_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.]
Quoted 6 lines
Quoted 3 lines
NOTE:
$ ./hash_resize --schroedinger --resizemult 2 --duration 20I 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
Quoted 127 lines
Quoted 15 lines
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:109Quoted 1 line
Signed-off-by Akira Yokosawa <[email protected]>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 ofsynchronize_rcu()calls.Quoted 10 lines
---
Hi Paul,This is a partial fix, but it resolves SIGSEGV in "--perftest" of
hash_bkt_rcuandhash_resize."--schroedinger" of
hash_resizewith 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
Quoted 88 lines
Thanks, Akira
--CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-)CodeSamples/datastruct/hash/hashtorture.h +16
-8@@ -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 ; }Signature · 1 line
2.7.4
Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
Quoted 50 lines · Akira Yokosawa
Quoted 33 lines · Paul E. McKenney
Quoted 32 lines · Akira Yokosawa
Quoted 1 line
From
52f5d218442eb64f2798335d56a1838f90d96d5fMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 30 Dec 2018 22:54:43 +0900
Subject: [PATCH] EXPhashtorture.h: Avoid sporadic SIGSEGV inhash_bkt_rcuCommit
4e22bdc905ff("Wait at end of test forcall_rcu()to finish") added a couple of synchronize_rcu()s inperftest_update()andzoo_reader().However, there still remains sporadic SIGSEGV in
$ ./hash_bkt_rcu --perftest --nupdaters 3On the other hand,
$ ./hash_bkt_rcu --schroedinger --nupdaters 3does not show such issue. Just moving synchronize_rcu()s in
zoo_reader()tozoo_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 ofperftest_updater()andzoo_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.]
Quoted 6 lines
Quoted 3 lines
NOTE:
$ ./hash_resize --schroedinger --resizemult 2 --duration 20I 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 andspin_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 ofspin_lock()--spin_unlock().
Quoted 7 lines
Also,
htp_master->ht_curcan change during thehashtab_lock_mod()--hashtab_unlock_mod()critical section because the update of the pointer byrcu_assign_pointer()is ahead ofsynchronize_rcu().Given the resizing is infrequent, the simplest way might be to block
hashtab_lock_modwhile 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.
Quoted 2 lines
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
Quoted 129 lines
Thanks, Akira
Quoted 127 lines
Quoted 15 lines
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:109Quoted 1 line
Signed-off-by Akira Yokosawa <[email protected]>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 ofsynchronize_rcu()calls.Quoted 10 lines
---
Hi Paul,This is a partial fix, but it resolves SIGSEGV in "--perftest" of
hash_bkt_rcuandhash_resize."--schroedinger" of
hash_resizewith 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
Quoted 88 lines
Thanks, Akira
--CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-)CodeSamples/datastruct/hash/hashtorture.h +16
-8@@ -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 ; }Signature · 1 line
2.7.4
Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
Quoted 63 lines · Paul E. McKenney
Quoted 50 lines · Akira Yokosawa
Quoted 33 lines · Paul E. McKenney
Quoted 32 lines · Akira Yokosawa
Quoted 1 line
From
52f5d218442eb64f2798335d56a1838f90d96d5fMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 30 Dec 2018 22:54:43 +0900
Subject: [PATCH] EXPhashtorture.h: Avoid sporadic SIGSEGV inhash_bkt_rcuCommit
4e22bdc905ff("Wait at end of test forcall_rcu()to finish") added a couple of synchronize_rcu()s inperftest_update()andzoo_reader().However, there still remains sporadic SIGSEGV in
$ ./hash_bkt_rcu --perftest --nupdaters 3On the other hand,
$ ./hash_bkt_rcu --schroedinger --nupdaters 3does not show such issue. Just moving synchronize_rcu()s in
zoo_reader()tozoo_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 ofperftest_updater()andzoo_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.]
Quoted 6 lines
Quoted 3 lines
NOTE:
$ ./hash_resize --schroedinger --resizemult 2 --duration 20I 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 andspin_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 ofspin_lock()--spin_unlock().Quoted 7 lines
Also,
htp_master->ht_curcan change during thehashtab_lock_mod()--hashtab_unlock_mod()critical section because the update of the pointer byrcu_assign_pointer()is ahead ofsynchronize_rcu().Given the resizing is infrequent, the simplest way might be to block
hashtab_lock_modwhile 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. ;-)
Quoted 8 lines
Well, it is conference-driven code, but still high time for me to clean it up.
Quoted 2 lines
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: 986455This 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
Quoted 135 lines
And thank you again!
Thanx, Paul
Quoted 129 lines
Thanks, Akira
Quoted 127 lines
Quoted 15 lines
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:109Quoted 1 line
Signed-off-by Akira Yokosawa <[email protected]>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 ofsynchronize_rcu()calls.Quoted 10 lines
---
Hi Paul,This is a partial fix, but it resolves SIGSEGV in "--perftest" of
hash_bkt_rcuandhash_resize."--schroedinger" of
hash_resizewith 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
Quoted 88 lines
Thanks, Akira
--CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-)CodeSamples/datastruct/hash/hashtorture.h +16
-8@@ -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 ; }Signature · 1 line
2.7.4
Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
Quoted 83 lines · Akira Yokosawa
Quoted 63 lines · Paul E. McKenney
Quoted 50 lines · Akira Yokosawa
Quoted 33 lines · Paul E. McKenney
Quoted 32 lines · Akira Yokosawa
Quoted 1 line
From
52f5d218442eb64f2798335d56a1838f90d96d5fMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Mon, 30 Dec 2018 22:54:43 +0900
Subject: [PATCH] EXPhashtorture.h: Avoid sporadic SIGSEGV inhash_bkt_rcuCommit
4e22bdc905ff("Wait at end of test forcall_rcu()to finish") added a couple of synchronize_rcu()s inperftest_update()andzoo_reader().However, there still remains sporadic SIGSEGV in
$ ./hash_bkt_rcu --perftest --nupdaters 3On the other hand,
$ ./hash_bkt_rcu --schroedinger --nupdaters 3does not show such issue. Just moving synchronize_rcu()s in
zoo_reader()tozoo_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 ofperftest_updater()andzoo_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.]
Quoted 6 lines
Quoted 3 lines
NOTE:
$ ./hash_resize --schroedinger --resizemult 2 --duration 20I 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 andspin_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 ofspin_lock()--spin_unlock().Quoted 7 lines
Also,
htp_master->ht_curcan change during thehashtab_lock_mod()--hashtab_unlock_mod()critical section because the update of the pointer byrcu_assign_pointer()is ahead ofsynchronize_rcu().Given the resizing is infrequent, the simplest way might be to block
hashtab_lock_modwhile 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. ;-)
Quoted 8 lines
Well, it is conference-driven code, but still high time for me to clean it up.
Quoted 2 lines
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: 986455This means that all the lookups failed. OTOH,
hash_bkt_rcuworks as expected as follows:
Quoted 8 lines
$ ./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.hcombination. 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
Quoted 138 lines
Thanks, Akira
Quoted 135 lines
And thank you again!
Thanx, Paul
Quoted 129 lines
Thanks, Akira
Quoted 127 lines
Quoted 15 lines
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:109Quoted 1 line
Signed-off-by Akira Yokosawa <[email protected]>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 ofsynchronize_rcu()calls.Quoted 10 lines
---
Hi Paul,This is a partial fix, but it resolves SIGSEGV in "--perftest" of
hash_bkt_rcuandhash_resize."--schroedinger" of
hash_resizewith 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
Quoted 88 lines
Thanks, Akira
--CodeSamples/datastruct/hash/hashtorture.h | 24 ++++++++++++++++-------- 1 file changed, 16 insertions(+), 8 deletions(-)CodeSamples/datastruct/hash/hashtorture.h +16
-8@@ -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 ; }Signature · 1 line
2.7.4
Re: [PATCH] EXP hashtorture.h: Avoid sporadic SIGSEGV in hash_bkt_rcu
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Akira Yokosawa
On 2019/01/01 10:00:25 -0800, Paul E. McKenney wrote:
[ . . . ]
Quoted 19 lines
Quoted 10 lines
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: 986455This means that all the lookups failed. OTOH,
hash_bkt_rcuworks as expected as follows:Quoted 8 lines
$ ./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.hcombination. I've not yet figured out the cause, though.
Quoted 7 lines
The short story is that I am working to return the locking state from
hashtab_lock_mod()for use byhashtab_add(),hashtab_del(), andhashtab_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
PATCH 1/1 datastruct/hash: Tweak appearance of updated code in snippet
From ae50debbf06ad674e4941b55764b02c776484509 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.
---
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(-)
CodeSamples/datastruct/hash/hash_resize.c +3 -2
@@ -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;
Signature · 1 line
2.7.4
Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
Quoted 11 lines · Akira Yokosawa
Quoted 1 line
From
ae50debbf06ad674e4941b55764b02c776484509Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Fri, 4 Jan 2019 00:19:26 +0900
Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippetNow 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 <[email protected]>
Ah, the lsp[2] was a temporary state. I forgot to do a final "git push" yesterday, apologies!
Quoted 8 lines
---
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.
Quoted 2 lines
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.
Quoted 1 line
Fixing labels is left for your update.
Will do, and yes, they are a bit of a mess just now. ;-)
Thanx, Paul
Quoted 27 lines
Thanks, Akira
--CodeSamples/datastruct/hash/hash_resize.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)CodeSamples/datastruct/hash/hash_resize.c +3
-2@@ -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;Signature · 1 line
2.7.4
Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
Quoted 35 lines · Paul E. McKenney
Quoted 11 lines · Akira Yokosawa
Quoted 1 line
From
ae50debbf06ad674e4941b55764b02c776484509Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Fri, 4 Jan 2019 00:19:26 +0900
Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippetNow 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 <[email protected]>Ah, the lsp[2] was a temporary state. I forgot to do a final "git push" yesterday, apologies!
Quoted 8 lines
---
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_statethat contains an array or two as one part of making the API less obnoxious, which should help avoid the brokenness.
Quoted 8 lines
Quoted 2 lines
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.
Quoted 1 line
If the latter, I will hand-apply the patch.
Please do so.
Thanks, Akira
Quoted 35 lines
Quoted 2 lines
Fixing labels is left for your update.
Will do, and yes, they are a bit of a mess just now. ;-)
Thanx, Paul
Quoted 27 lines
Thanks, Akira
--CodeSamples/datastruct/hash/hash_resize.c | 5 +++-- 1 file changed, 3 insertions(+), 2 deletions(-)CodeSamples/datastruct/hash/hash_resize.c +3
-2@@ -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;Signature · 1 line
2.7.4
Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
Quoted 42 lines · Akira Yokosawa
Quoted 41 lines · Paul E. McKenney
Quoted 11 lines · Akira Yokosawa
Quoted 1 line
From
ae50debbf06ad674e4941b55764b02c776484509Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Fri, 4 Jan 2019 00:19:26 +0900
Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippetNow 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 <[email protected]>Ah, the lsp[2] was a temporary state. I forgot to do a final "git push" yesterday, apologies!
Quoted 8 lines
---
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_statethat contains an array or two as one part of making the API less obnoxious, which should help avoid the brokenness.Quoted 2 lines
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.
Quoted 8 lines
Quoted 2 lines
Or do we need this commit anyway just due to array references within the code snippet?
Yes, we do.
Quoted 1 line
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 <[email protected]> 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.
CodeSamples/datastruct/hash/hash_resize.c +1 -1
@@ -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,
Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
Quoted 63 lines · Paul E. McKenney
Quoted 42 lines · Akira Yokosawa
Quoted 41 lines · Paul E. McKenney
Quoted 11 lines · Akira Yokosawa
Quoted 1 line
From
ae50debbf06ad674e4941b55764b02c776484509Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Fri, 4 Jan 2019 00:19:26 +0900
Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippetNow 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 <[email protected]>Ah, the lsp[2] was a temporary state. I forgot to do a final "git push" yesterday, apologies!
Quoted 8 lines
---
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_statethat contains an array or two as one part of making the API less obnoxious, which should help avoid the brokenness.Quoted 2 lines
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.
Quoted 8 lines
Quoted 2 lines
Or do we need this commit anyway just due to array references within the code snippet?
Yes, we do.
Quoted 1 line
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
d138666652d064f1ac891af7770dd220d51caa86Author: Akira Yokosawa <[email protected]> Date: Thu Jan 3 16:50:25 2019 -0800
Quoted 6 lines
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
Quoted 18 lines
Signed-off-by Akira Yokosawa <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>CodeSamples/datastruct/hash/hash_resize.c +1
-1@@ -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,
Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
Quoted 66 lines · Akira Yokosawa
Quoted 65 lines · Paul E. McKenney
Quoted 42 lines · Akira Yokosawa
Quoted 41 lines · Paul E. McKenney
Quoted 11 lines · Akira Yokosawa
Quoted 1 line
From
ae50debbf06ad674e4941b55764b02c776484509Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Fri, 4 Jan 2019 00:19:26 +0900
Subject: [PATCH] datastruct/hash: Tweak appearance of updated code in snippetNow 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 <[email protected]>Ah, the lsp[2] was a temporary state. I forgot to do a final "git push" yesterday, apologies!
Quoted 8 lines
---
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_statethat contains an array or two as one part of making the API less obnoxious, which should help avoid the brokenness.Quoted 2 lines
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.
Quoted 8 lines
Quoted 2 lines
Or do we need this commit anyway just due to array references within the code snippet?
Yes, we do.
Quoted 1 line
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
d138666652d064f1ac891af7770dd220d51caa86Author: Akira Yokosawa <[email protected]> Date: Thu Jan 3 16:50:25 2019 -0800datastruct/hash: Tweak appearance of updated code in snippet
Quoted 7 lines
Quoted 4 lines
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
Quoted 21 lines
Thanks, Akira
Quoted 18 lines
Signed-off-by Akira Yokosawa <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>CodeSamples/datastruct/hash/hash_resize.c +1
-1@@ -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,
Re: [PATCH] datastruct/hash: Tweak appearance of updated code in snippet
In reply to Akira YokosawaHi 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
PATCH 1/2 datastruct/hash: Tweak indent of folded line in snippet
From 426fa84ef7b5c6d0200dbd79d213e02ae31badad Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.
--- CodeSamples/datastruct/hash/hash_resize.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
CodeSamples/datastruct/hash/hash_resize.c +1 -1
@@ -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;
Signature · 1 line
2.7.4
Re: [PATCH 1/2] datastruct/hash: Tweak indent of folded line in snippet
Quoted 11 lines · Akira Yokosawa
Quoted 1 line
From
426fa84ef7b5c6d0200dbd79d213e02ae31badadMon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
Date: Fri, 4 Jan 2019 23:40:14 +0900
Subject: [PATCH 1/2] datastruct/hash: Tweak indent of folded line in snippetFor 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.
Quoted 5 lines
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 <[email protected]>
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
Quoted 21 lines
--- CodeSamples/datastruct/hash/hash_resize.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)CodeSamples/datastruct/hash/hash_resize.c +1
-1@@ -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;Signature · 1 line
2.7.4
PATCH 2/2 datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE
In reply to Akira YokosawaFrom ed528d05b7800d651ef5e36de37732a06b456462 Mon Sep 17 00:00:00 2001
From: Akira Yokosawa <[email protected]>
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.
--- CodeSamples/datastruct/hash/hash_resize.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)
CodeSamples/datastruct/hash/hash_resize.c +6 -6
@@ -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}
Signature · 1 line
2.7.4
Re: [PATCH 2/2] datastruct/hash: Annotate racy accesses with READ_ONCE/WRITE_ONCE
Quoted 11 lines · Akira Yokosawa
Quoted 1 line
From
ed528d05b7800d651ef5e36de37732a06b456462Mon Sep 17 00:00:00 2001From: Akira Yokosawa <[email protected]>
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 withhash_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 <[email protected]>
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
Quoted 9 lines
--- CodeSamples/datastruct/hash/hash_resize.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-)CodeSamples/datastruct/hash/hash_resize.c +0
-0
CodeSamples/datastruct/hash/hash_resize.c ht_get_bucket(struct ht **htp, void *key, long *b, int *i) · line 140
Quoted 5 lines
CodeSamples/datastruct/hash/hash_resize.c +1
-1@@ -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.
CodeSamples/datastruct/hash/hash_resize.c ht_get_bucket(struct ht **htp, void *key, long *b, int *i) · line 142
Quoted 3 lines
CodeSamples/datastruct/hash/hash_resize.c +1
-1smp_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().
CodeSamples/datastruct/hash/hash_resize.c ht_get_bucket(struct ht **htp, void *key, long *b, int *i) · line 146
Quoted 5 lines
CodeSamples/datastruct/hash/hash_resize.c +1
-1htbp =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.)
CodeSamples/datastruct/hash/hash_resize.c int hashtab_resize(struct hashtab *htp_master, · line 304
Quoted 9 lines
CodeSamples/datastruct/hash/hash_resize.c +1
-1return 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?
CodeSamples/datastruct/hash/hash_resize.c int hashtab_resize(struct hashtab *htp_master, · line 307
Quoted 4 lines
CodeSamples/datastruct/hash/hash_resize.c +1
-1synchronize_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.
CodeSamples/datastruct/hash/hash_resize.c int hashtab_resize(struct hashtab *htp_master, · line 318
Quoted 9 lines
CodeSamples/datastruct/hash/hash_resize.c +1
-1for (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.
CodeSamples/datastruct/hash/hash_resize.c int hashtab_resize(struct hashtab *htp_master, · line 321
Quoted 3 lines
CodeSamples/datastruct/hash/hash_resize.c +0
-0spin_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 <[email protected]> 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().
CodeSamples/datastruct/hash/hash_resize.c +5 -5
@@ -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}