On Tue, Dec 25, 2018 at 11:30:44PM +0900, Akira Yokosawa wrote:
> On 2018/12/25 9:53, Paul E. McKenney wrote:
> > On Mon, Dec 24, 2018 at 03:58:32PM -0800, Paul E. McKenney wrote:
> >> On Mon, Dec 24, 2018 at 11:46:23PM +0900, Akira Yokosawa wrote:
> >>> Hi Paul,
> >>>
> >>> This patch set consists of enhancement of fcvextract.pl,
> >>> update of snippets in datastruct, and some minor tweaks.
> >>>
> >>> fcvextract.pl now suppresses comment blocks in C source and
> >>> supports alternative code for snippets in #ifndef blocks,
> >>> which won't be affected by the suppression of comment blocks.
> >>>
> >>> Also, labeling of the form /* \lnlbl{label} */ is now supported
> >>> in C snippets.
> >>>
> >>> Patch #1 adds comment block handling to fcvextract.pl, without
> >>> changing the default behavior.
> >>>
> >>> Patch #2 adds a couple of explicit options to snippets which
> >>> have comments to be displayed. It also converts alternative
> >>> code fragments using "#ifndef FCV_EXCLUDE" so that they survive
> >>> comment block suppression.
> >>>
> >>> Patch #3 changes the default to "keepcomment=no".
> >>> This removes a couple of comments in Listings 4.8 and 9.5.
> >>>
> >>> Patch #4 removes now redundant "\fcvexclude" around comment
> >>> blocks. It also uses "#ifndef FCV_SNIPPET" to reduce \fcvexclude
> >>> uses.
> >>>
> >>> Patch #5 adds support of "/* \lnlbl{label} */" labeling.
> >>>
> >>> Patch #6 updates snippets of hash_bkt.c. "struct hashtab"
> >>> now has the "ht_cmp" field and I updated the text to mention
> >>> it. You might want to do some rewording.
> >>
> >> Looks good to me as is.
> >>
> >>> Patch #7 adds the "ht_cmp" field in the hashdiagram figure
> >>> (still in .fig).
> >>>
> >>> Patch #8 updates the rest of snippets in datastruct. It also
> >>> fixes typo in cross references of Listing 10.13.
> >>> By this change, an smp_mb() appears in ht_get_bucket()
> >>> (Listing 10.10).
> >>>
> >>> My guess is that the counterpart barrier is the first
> >>> synchronize_rcu() in hashtab_resize(). It might deserve some
> >>> explanation or a Quick Quiz. Also, Answer to Quick Quiz 10.13
> >>> might need some expansion, since it looks as though hash_reorder.c
> >>> used something more than the pure RCU protection. But I might be
> >>> completely misreading here...
> >>
> >> I think I have a bug...
> >>
> >> So am I smarter now than when I wrote that code, or vice versa? ;-)
> >
> > I believe that I am smarter now, or maybe just more deluded. Anyway,
> > when I changed the code, I go this from the top-level Makefile:
> >
> > $ make
> > sh ./utilities/gen_snippet_d.sh
> > sh utilities/autodate.sh >autodate.tex
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@xxxxxxxx
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:data > CodeSamples/datastruct/hash/hash_resize@xxxxxxxx
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:get_bucket > CodeSamples/datastruct/hash/hash_resize@get_bucket.fcv
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:lock_unlock_mod > CodeSamples/datastruct/hash/hash_resize@lock_unlock_mod.fcv
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@xxxxxxxxxx
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:access > CodeSamples/datastruct/hash/hash_resize@xxxxxxxxxx
> > CodeSamples/datastruct/hash/hash_resize.c --> CodeSamples/datastruct/hash/hash_resize@xxxxxxxxxx
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/hash_resize.c hash_resize:resize > CodeSamples/datastruct/hash/hash_resize@xxxxxxxxxx
> > CodeSamples/datastruct/hash/.hash_resize.c.swp --> CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> > utilities/fcvextract.pl CodeSamples/datastruct/hash/.hash_resize.c.swp hash > CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv
> > /bin/bash: CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv: No such file or directory
> > make: *** [CodeSamples/datastruct/hash/CodeSamples/datastruct/hash.fcv] Error 1
> >
> > Using "make clean" didn't fix it. Neither did reverting my change
> > to CodeSamples/datastruct/hash/hash_resize.c, which is shown below.
> >
> > Ah, I get it now. I had CodeSamples/datastruct/hash/hash_resize.c
> > open in vim, and the scripting attempted to process the resulting
> > .hash_resize.c.swp file from vim. Things started working again after
> > I exited from vim.
>
> I see.
>
> I'll add rules in utilities/gen_snippet_d.pl so that those .swp files
> will be excluded from the search result.
Another alternative would be to exclude filenames beginning with ".".
But emacs and so on have other rules. :-/
> BTW, the new Quick Quiz 10.14 sounds somewhat inconsistent with
> Quick Quiz 10.13 and its answer, doesn't it?
>
> Or am I missing something?
Maybe that hashtab_lookup(), hashtab_add(), and hashtab_del() must
all be invoked within RCU read-side critical sections? These critical
sections, in conjunction with hashtab_resize()'s first synchronize_rcu(),
ensure that any "reader" seeing a non-negative value of ->ht_resize-cur
also sees non-NULL ->ht_new. Which is a bit obscure from that quiz's
question.
How about the following?
Quick Quiz 10.13:
In the hashtab_resize() function in Listing 10.13, what
guarantees that the update to ->ht_new on line 28 will be seen as
happening before the update to ->ht_resize_cur on line 42 from the
perspective of hashtab_lookup(), hashtab_add(), and hashtab_del()?
In other words, what prevents hashtab_lookup(), hashtab_add(),
and hashtab_del(), from dereferencing a NULL pointer loaded
from ->ht_new?
Answer:
The synchronize_rcu() on line 29 of Listing 10.13 ensures that
all pre-existing RCU readers have completed between the time
that we install the new hash-table reference on line 28 and the
time that we update ->ht_resize_cur on line 42. This means that
any reader that sees a non-negative value of ->ht_resize_cur
cannot have started before the assignment to ->ht_new, and
thus must be able to see the reference to the new hash table.
And this is why the update-side hashtab_add() and hashtab_del()
functions must nevertheless be enclosed in RCU read-side critical
sections, courtesy of hashtab_lock_mod() and hashtab_unlock_mod()
in Listinglst:datastruct:Resizable Hash-Table Update-Side
Concurrency Control.
Thanx, Paul
> Thanks, Akira
>
> >
> > Thanx, Paul
> >
> > ------------------------------------------------------------------------
> >
> > diff --git a/CodeSamples/datastruct/hash/hash_resize.c b/CodeSamples/datastruct/hash/hash_resize.c
> > index 662bb90bff14..ccb523bb6c05 100644
> > --- a/CodeSamples/datastruct/hash/hash_resize.c
> > +++ b/CodeSamples/datastruct/hash/hash_resize.c
> > @@ -298,13 +298,14 @@ int hashtab_resize(struct hashtab *htp_master,
> > for (i = 0; i < htp->ht_nbuckets; i++) { //\lnlbl{loop:b}
> > htbp = &htp->ht_bkt[i]; //\lnlbl{get_oldcur}
> > spin_lock(&htbp->htb_lock); //\lnlbl{acq_oldcur}
> > - htp->ht_resize_cur = i; //\lnlbl{update_resize}
> > cds_list_for_each_entry(htep, &htbp->htb_head, hte_next[idx]) { //\lnlbl{loop_list:b}
> > htbp_new = ht_get_bucket_single(htp_new, htp_new->ht_getkey(htep), &b);
> > spin_lock(&htbp_new->htb_lock);
> > cds_list_add_rcu(&htep->hte_next[!idx], &htbp_new->htb_head);
> > spin_unlock(&htbp_new->htb_lock);
> > } //\lnlbl{loop_list:e}
> > + smp_mb(); /* Fill new buckets before claiming them. */
> > + htp->ht_resize_cur = i; //\lnlbl{update_resize}
> > spin_unlock(&htbp->htb_lock); //\lnlbl{rel_oldcur}
> > } //\lnlbl{loop:e}
> > rcu_assign_pointer(htp_master->ht_cur, htp_new); //\lnlbl{rcu_assign}
> >
>
