[PATCH 0/4] Fixup trivial nitpicks under defer/

[PATCH 0/4] Fixup trivial nitpicks under defer/

[SeongJae Park]

This patchset fixes trivial nitpicks under defer/ that found during translation
of upstream change since July, 2016.

SeongJae Park (4):
  defer/refcnt: Add missing dot
  defer: Fix typos
  defer/whichtochoose: Trim a sentence
  defer/seqlock: Fix wrong code line reference

 defer/rcuusage.tex      | 2 +-
 defer/refcnt.tex        | 2 +-
 defer/seqlock.tex       | 4 ++--
 defer/whichtochoose.tex | 2 +-
 4 files changed, 5 insertions(+), 5 deletions(-)

-- 
1.9.1

[PATCH 1/4] defer/refcnt: Add missing dot

[SeongJae Park]

Signed-off-by: SeongJae Park <sj38.park@gmail.com>
---
 defer/refcnt.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/defer/refcnt.tex b/defer/refcnt.tex
index b48ca48..ab0b9be 100644
--- a/defer/refcnt.tex
+++ b/defer/refcnt.tex
@@ -130,7 +130,7 @@ at least the early
 	used a mechanical reference-counting technique, where each
 	worker had a padlock.}
 Reference counting is thus an excellent candidate for a concurrent
-implementation of Pre-BSD routing
+implementation of Pre-BSD routing.

 To that end,
 Figure~\ref{fig:defer:Reference-Counted Pre-BSD Routing Table Lookup}
-- 
1.9.1

[PATCH 2/4] defer: Fix typos

[SeongJae Park]

Signed-off-by: SeongJae Park <sj38.park@gmail.com>
---
 defer/rcuusage.tex | 2 +-
 defer/seqlock.tex  | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/defer/rcuusage.tex b/defer/rcuusage.tex
index 7796a0d..8812c25 100644
--- a/defer/rcuusage.tex
+++ b/defer/rcuusage.tex
@@ -186,7 +186,7 @@ ideal synchronization-free workload, as desired.
 	The \co{rcu_dereference()} primitive does constrain the
 	compiler's optimizations somewhat, which can result in
 	slightly slower code.
-	This would effect would normally be insignificant, but
+	This effect would normally be insignificant, but
 	each search is taking on average about 13~nanoseconds,
 	which is short enough for small differences in code
 	generation to make their presence felt.
diff --git a/defer/seqlock.tex b/defer/seqlock.tex
index 23e69fb..f379439 100644
--- a/defer/seqlock.tex
+++ b/defer/seqlock.tex
@@ -389,7 +389,7 @@ increment of the sequence number on line~44, then releases the lock.
 So what happens when sequence locking is applied to the Pre-BSD
 routing table?
 Figure~\ref{fig:defer:Sequence-Locked Pre-BSD Routing Table Lookup}
-shows the data structures and \co{route_lookup()}, adn
+shows the data structures and \co{route_lookup()}, and
 Figure~\ref{fig:defer:Sequence-Locked Pre-BSD Routing Table Add/Delete}
 shows \co{route_add()} and \co{route_del()} (\path{route_seqlock.c}).
 This implementation is once again similar to its counterparts in earlier
-- 
1.9.1

[PATCH 3/4] defer/whichtochoose: Trim a sentence

[SeongJae Park]

Signed-off-by: SeongJae Park <sj38.park@gmail.com>
---
 defer/whichtochoose.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
index 648cdc8..884de9d 100644
--- a/defer/whichtochoose.tex
+++ b/defer/whichtochoose.tex
@@ -135,7 +135,7 @@ capable of unconditionally acquiring references.
 The entry for sequence locks is ``N/A'' because, again, sequence locks
 detect updates rather than acquiring references.
 Reference counting and hazard pointers require that traversals be
-restarted from the beginning should a given acquisition fail because
+restarted from the beginning if a given acquisition fail because
 the currrent object might be removed and all of its
 possible successsors might be not only be removed, but also freed.
 For example, when using reference counting or hazard pointers to
-- 
1.9.1

[PATCH 4/4] defer/seqlock: Fix wrong code line reference

[SeongJae Park]

Signed-off-by: SeongJae Park <sj38.park@gmail.com>
---
 defer/seqlock.tex | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/defer/seqlock.tex b/defer/seqlock.tex
index f379439..dbe2ebf 100644
--- a/defer/seqlock.tex
+++ b/defer/seqlock.tex
@@ -400,7 +400,7 @@ Figure~\ref{fig:defer:Sequence-Locked Pre-BSD Routing Table Lookup},
 line~5 adds \co{->re_freed}, which is checked on lines~29 and~30.
 Line~8 adds a sequence lock, which is used by \co{route_lookup()}
 on lines~18, 23, and~32, with lines~24 and~33 branching back to
-the \co{retry} label on line~16.
+the \co{retry} label on line~17.
 The effect is to retry any lookup that runs concurrently with an update.

 In
-- 
1.9.1

Re: [PATCH 3/4] defer/whichtochoose: Trim a sentence

[Akira Yokosawa]

Hi,

On 2016/07/16 16:58:49 +0900, SeongJae Park wrote:
> Signed-off-by: SeongJae Park <sj38.park@gmail.com>
> ---
>  defer/whichtochoose.tex | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
> index 648cdc8..884de9d 100644
> --- a/defer/whichtochoose.tex
> +++ b/defer/whichtochoose.tex
> @@ -135,7 +135,7 @@ capable of unconditionally acquiring references.
>  The entry for sequence locks is ``N/A'' because, again, sequence locks
>  detect updates rather than acquiring references.
>  Reference counting and hazard pointers require that traversals be
> -restarted from the beginning should a given acquisition fail because
> +restarted from the beginning if a given acquisition fail because

I can't get the point of this change. Original sentence seems quite natural
for me.

>  the currrent object might be removed and all of its
>  possible successsors might be not only be removed, but also freed.
>  For example, when using reference counting or hazard pointers to
>

However, there are typos here. We need to modify as follows.

-the currrent object might be removed and all of its
-possible successsors might be not only be removed, but also freed.
+the current object might be removed and all of its
+possible successors might be not only be removed, but also freed.

I'm sorry but I didn't compose in a patch format.
Paul, if you want a proper patch, feel free to ask me.
I'd rather refrain from sending patches that touch Chapter 9, which I assume
is being intensively rewritten right now.

                                                  Thanks, Akira

Re: [PATCH 3/4] defer/whichtochoose: Trim a sentence

[SeongJae Park]

On Sun, 17 Jul 2016, Akira Yokosawa wrote:

> Hi,
>
> On 2016/07/16 16:58:49 +0900, SeongJae Park wrote:
>> Signed-off-by: SeongJae Park <sj38.park@gmail.com>
>> ---
>> defer/whichtochoose.tex | 2 +-
>> 1 file changed, 1 insertion(+), 1 deletion(-)
>> 
>> diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
>> index 648cdc8..884de9d 100644
>> --- a/defer/whichtochoose.tex
>> +++ b/defer/whichtochoose.tex
>> @@ -135,7 +135,7 @@ capable of unconditionally acquiring references.
>> The entry for sequence locks is ``N/A'' because, again, sequence locks
>> detect updates rather than acquiring references.
>> Reference counting and hazard pointers require that traversals be
>> -restarted from the beginning should a given acquisition fail because
>> +restarted from the beginning if a given acquisition fail because
>
> I can't get the point of this change. Original sentence seems quite natural
> for me.

Well, I thought it would be easier to understand the meaning for poor
English speakers like me, though judging is Paul's right.  So, please feel
free to discard this patch if you think it's unnecessary, Paul.  BTW, I
think I found one trivial grammar mistake here:
`s/a given acquisition fail/a given acquisition fails/`.

>
>> the currrent object might be removed and all of its
>> possible successsors might be not only be removed, but also freed.
>> For example, when using reference counting or hazard pointers to
>> 
>
> However, there are typos here. We need to modify as follows.
>
> -the currrent object might be removed and all of its
> -possible successsors might be not only be removed, but also freed.
> +the current object might be removed and all of its
> +possible successors might be not only be removed, but also freed.

Good catch! 8D  It looks like the Many-eyeball law is working well. ;)


Thanks,
SeongJae Park

>
> I'm sorry but I didn't compose in a patch format.
> Paul, if you want a proper patch, feel free to ask me.
> I'd rather refrain from sending patches that touch Chapter 9, which I assume
> is being intensively rewritten right now.
>
>                                                Thanks, Akira

Re: [PATCH 3/4] defer/whichtochoose: Trim a sentence

[Akira Yokosawa]

On 2016/07/17 08:40:54 +0900, SeongJae Park wrote:
>
>
> On Sun, 17 Jul 2016, Akira Yokosawa wrote:
>
>> Hi,
>>
>> On 2016/07/16 16:58:49 +0900, SeongJae Park wrote:
>>> Signed-off-by: SeongJae Park <sj38.park@gmail.com>
>>> ---
>>> defer/whichtochoose.tex | 2 +-
>>> 1 file changed, 1 insertion(+), 1 deletion(-)
>>>
>>> diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
>>> index 648cdc8..884de9d 100644
>>> --- a/defer/whichtochoose.tex
>>> +++ b/defer/whichtochoose.tex
>>> @@ -135,7 +135,7 @@ capable of unconditionally acquiring references.
>>> The entry for sequence locks is ``N/A'' because, again, sequence locks
>>> detect updates rather than acquiring references.
>>> Reference counting and hazard pointers require that traversals be
>>> -restarted from the beginning should a given acquisition fail because
>>> +restarted from the beginning if a given acquisition fail because
>>
>> I can't get the point of this change. Original sentence seems quite natural
>> for me.
>
> Well, I thought it would be easier to understand the meaning for poor
> English speakers like me, though judging is Paul's right.  So, please feel
> free to discard this patch if you think it's unnecessary, Paul.  BTW, I
> think I found one trivial grammar mistake here:
> `s/a given acquisition fail/a given acquisition fails/`.
>
>>
>>> the currrent object might be removed and all of its
>>> possible successsors might be not only be removed, but also freed.
>>> For example, when using reference counting or hazard pointers to
>>>
>>
>> However, there are typos here. We need to modify as follows.
>>
>> -the currrent object might be removed and all of its
>> -possible successsors might be not only be removed, but also freed.
>> +the current object might be removed and all of its
>> +possible successors might be not only be removed, but also freed.
>

As I reread the sentence, there is an unnecessary "be" here.

-the currrent object might be removed and all of its
-possible successsors might be not only be removed, but also freed.
+the current object might be removed and all of its
+possible successors might be not only removed, but also freed.

Or we can say:

+the current object might be removed and all of its
+possible successors might not only be removed, but also be freed.

I agree with you that this sentence is fairy complicated.
There might be a better way to rephrase, for example, denoting
the end of that-clause by a comma as appended:

                                            Thanks, Akira

-------------------------------------------------------------
commit 137f7250edbd01b1eab4cbd02449228a949ac2cf
Author: Akira Yokosawa <akiyks@gmail.com>
Date:   Sun Jul 17 10:42:56 2016 +0900

     defer/whichtochoose: Rephrase a sentence
     
     This commit adds a comma to denote the end of that-clause.
     It also fixes a few typos including the entry of sequence locks
     in Table 9.6.
     
     Reported-by: SeongJae Park <sj38.park@gmail.com>
     Signed-off-by: Akira Yokosawa <akiyks@gmail.com>

diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
index 648cdc8..923c3b3 100644
--- a/defer/whichtochoose.tex
+++ b/defer/whichtochoose.tex
@@ -57,7 +57,7 @@
  	Reader Reference Acquisition
  		& Can fail (conditional)
  			& Can fail (conditional)
-				& Unsafe
+				& N/A
  					& Cannot fail (unconditional) \\
  	\hline
  	Memory Footprint
@@ -135,9 +135,9 @@ capable of unconditionally acquiring references.
  The entry for sequence locks is ``N/A'' because, again, sequence locks
  detect updates rather than acquiring references.
  Reference counting and hazard pointers require that traversals be
-restarted from the beginning should a given acquisition fail because
-the currrent object might be removed and all of its
-possible successsors might be not only be removed, but also freed.
+restarted from the beginning should a given acquisition fail, because
+the current object might be removed and all of its
+possible successors might be not only removed, but also freed.
  For example, when using reference counting or hazard pointers to
  protect a tree traversal, any reference-acquisition failure requires
  that the traversal be restarted from the root of the tree.

Re: [PATCH 3/4] defer/whichtochoose: Trim a sentence

[Paul E. McKenney]

On Sun, Jul 17, 2016 at 11:16:57AM +0900, Akira Yokosawa wrote:
> On 2016/07/17 08:40:54 +0900, SeongJae Park wrote:
> >
> >
> >On Sun, 17 Jul 2016, Akira Yokosawa wrote:
> >
> >>Hi,
> >>
> >>On 2016/07/16 16:58:49 +0900, SeongJae Park wrote:
> >>>Signed-off-by: SeongJae Park <sj38.park@gmail.com>
> >>>---
> >>>defer/whichtochoose.tex | 2 +-
> >>>1 file changed, 1 insertion(+), 1 deletion(-)
> >>>
> >>>diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
> >>>index 648cdc8..884de9d 100644
> >>>--- a/defer/whichtochoose.tex
> >>>+++ b/defer/whichtochoose.tex
> >>>@@ -135,7 +135,7 @@ capable of unconditionally acquiring references.
> >>>The entry for sequence locks is ``N/A'' because, again, sequence locks
> >>>detect updates rather than acquiring references.
> >>>Reference counting and hazard pointers require that traversals be
> >>>-restarted from the beginning should a given acquisition fail because
> >>>+restarted from the beginning if a given acquisition fail because
> >>
> >>I can't get the point of this change. Original sentence seems quite natural
> >>for me.
> >
> >Well, I thought it would be easier to understand the meaning for poor
> >English speakers like me, though judging is Paul's right.  So, please feel
> >free to discard this patch if you think it's unnecessary, Paul.  BTW, I
> >think I found one trivial grammar mistake here:
> >`s/a given acquisition fail/a given acquisition fails/`.
> >
> >>
> >>>the currrent object might be removed and all of its
> >>>possible successsors might be not only be removed, but also freed.
> >>>For example, when using reference counting or hazard pointers to
> >>>
> >>
> >>However, there are typos here. We need to modify as follows.
> >>
> >>-the currrent object might be removed and all of its
> >>-possible successsors might be not only be removed, but also freed.
> >>+the current object might be removed and all of its
> >>+possible successors might be not only be removed, but also freed.
> >
> 
> As I reread the sentence, there is an unnecessary "be" here.
> 
> -the currrent object might be removed and all of its
> -possible successsors might be not only be removed, but also freed.
> +the current object might be removed and all of its
> +possible successors might be not only removed, but also freed.
> 
> Or we can say:
> 
> +the current object might be removed and all of its
> +possible successors might not only be removed, but also be freed.
> 
> I agree with you that this sentence is fairy complicated.
> There might be a better way to rephrase, for example, denoting
> the end of that-clause by a comma as appended:

Hmmm...  That certainly was not one of my better efforts, was it?  ;-)

I reworked that paragraph and surrounding paragraphs as shown below.
Does that help?

I also applied the other three of SeongJae's patches, thank you!
And thanks to you both for your review and comments!

							Thanx, Paul

------------------------------------------------------------------------

commit 22455cae203ae6707970d0565fe70dfdc4ada1ca
Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Date:   Sun Jul 17 14:41:47 2016 -0700

    Self review of "Which to Choose" section
    
    Reported-by: SeongJae Park <sj38.park@gmail.com>
    Reported-by: Akira Yokosawa <akiyks@gmail.com>
    Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
index 648cdc88e406..11f3b0a24e87 100644
--- a/defer/whichtochoose.tex
+++ b/defer/whichtochoose.tex
@@ -132,26 +132,48 @@ instructions.

 The ``Reader Reference Acquisition'' rows indicates that only RCU is
 capable of unconditionally acquiring references.
-The entry for sequence locks is ``N/A'' because, again, sequence locks
+The entry for sequence locks is ``Unsafe'' because, again, sequence locks
 detect updates rather than acquiring references.
-Reference counting and hazard pointers require that traversals be
-restarted from the beginning should a given acquisition fail because
-the currrent object might be removed and all of its
-possible successsors might be not only be removed, but also freed.
-For example, when using reference counting or hazard pointers to
-protect a tree traversal, any reference-acquisition failure requires
-that the traversal be restarted from the root of the tree.
+Reference counting and hazard pointers both require that traversals be
+restarted from the beginning if a given acquisition fails.
+To see this, consider a linked list containing objects~A, B, C, and~D,
+in that order, and the following series of events:
+
+\begin{enumerate}
+\item	A reader acquires a reference to object~B.
+\item	An updater removes~object B, but refrains from freeing it because
+	the reader holds a reference.
+	The list now contains objects~A, C, and~D, and
+	object~B's \co{->next} pointer is set to \co{HAZPTR_POISON}.
+\item	The updater removes object~C, so that the list now contains
+	objects~A and~D.
+	Because there is no reference to object~C, it is immediately freed.
+\item	The reader tries to advance to the successor of the object
+	following the now-removed object~B, but the poisoned
+	\co{->next} pointer prevents this.
+	Which is a good thing, because object~B's \co{->next} pointer
+	would otherwise point to the freelist.
+\item	The reader must therefore restart its traversal from the head
+	of the list.
+\end{enumerate}
+
+Thus, when failing to acquire a reference, a hazard-pointer or
+reference-counter traversal must restart that traversal from the
+beginning.
+In the case of nested linked data structures, for example, a
+tree containing linked lists, the traversal must be restarted from
+the outermost data structure.
 This situation gives RCU a significant ease-of-use advantage.

 However, RCU's ease-of-use advantage does not come
 for free, as can be seen in the ``Memory Footprint'' row.
 RCU's support of unconditional reference acquisition means that
-it must avoid freeing any object visible to a given RCU reader
-until that reader completes.
-RCU therefore has an unbounded footprint, at least unless updates
-are artificially throttled.
-In contrast, reference counting and hazard pointers would retain only
-those specific data elements actually referenced by concurrent readers.
+it must avoid freeing any object reachable by a given
+RCU reader until that reader completes.
+RCU therefore has an unbounded memory footprint, at least unless updates
+are throttled.
+In contrast, reference counting and hazard pointers need to  retain only
+those data elements actually referenced by concurrent readers.

 This tension between memory footprint and acquisition
 failures is sometimes resolved within the Linux kernel by combining use
@@ -159,7 +181,7 @@ of RCU and reference counters.
 RCU is used for short-lived references, which means that RCU read-side
 critical sections can be short.
 These short RCU read-side critical sections in turn mean that the corresponding
-RCU grace periods can also be short, limiting the memory footprint.
+RCU grace periods can also be short, which limits the memory footprint.
 For the few data elements that need longer-lived references, reference
 counting is used.
 This means that the complexity of reference-acquisition failure only
@@ -181,14 +203,19 @@ a wait to free memory, which results in an situation that, for many
 purposes, is as good as non-blocking~\cite{MathieuDesnoyers2012URCU}.

 As shown in the ``Automatic Reclamation'' row, only reference
-counting can automate freeing of memory, at least assuming non-cyclic
-data structures.
+counting can automate freeing of memory, and even then only
+for non-cyclic data structures.

 Finally, the ``Lines of Code'' row shows the size of the Pre-BSD
 Routing Table implementations, giving a rough idea of relative ease of use.
 That said, it is important to note that the reference-counting and
 sequence-locking implementations are buggy, and that a correct
-reference-counting implementation is considerably more complex.
+reference-counting implementation is considerably
+more complex~\cite{Valois95a,MagedMichael95a}.
+For its part, a correct sequence-locking implementation requires
+the addition of some other synchronization mechanism, for example,
+hazard pointers or RCU, so that sequence locking detects concurrent
+updates and the other mechanism provides safe reference acquisition.

 As more experience is gained using these techniques, both separately
 and in combination, the rules of thumb laid out in this section will

Re: [PATCH 3/4] defer/whichtochoose: Trim a sentence

[SeongJae Park]

On Mon, Jul 18, 2016 at 6:44 AM, Paul E. McKenney
<paulmck@linux.vnet.ibm.com> wrote:
> On Sun, Jul 17, 2016 at 11:16:57AM +0900, Akira Yokosawa wrote:
>> On 2016/07/17 08:40:54 +0900, SeongJae Park wrote:
>> >
>> >
>> >On Sun, 17 Jul 2016, Akira Yokosawa wrote:
>> >
>> >>Hi,
>> >>
>> >>On 2016/07/16 16:58:49 +0900, SeongJae Park wrote:
>> >>>Signed-off-by: SeongJae Park <sj38.park@gmail.com>
>> >>>---
>> >>>defer/whichtochoose.tex | 2 +-
>> >>>1 file changed, 1 insertion(+), 1 deletion(-)
>> >>>
>> >>>diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
>> >>>index 648cdc8..884de9d 100644
>> >>>--- a/defer/whichtochoose.tex
>> >>>+++ b/defer/whichtochoose.tex
>> >>>@@ -135,7 +135,7 @@ capable of unconditionally acquiring references.
>> >>>The entry for sequence locks is ``N/A'' because, again, sequence locks
>> >>>detect updates rather than acquiring references.
>> >>>Reference counting and hazard pointers require that traversals be
>> >>>-restarted from the beginning should a given acquisition fail because
>> >>>+restarted from the beginning if a given acquisition fail because
>> >>
>> >>I can't get the point of this change. Original sentence seems quite natural
>> >>for me.
>> >
>> >Well, I thought it would be easier to understand the meaning for poor
>> >English speakers like me, though judging is Paul's right.  So, please feel
>> >free to discard this patch if you think it's unnecessary, Paul.  BTW, I
>> >think I found one trivial grammar mistake here:
>> >`s/a given acquisition fail/a given acquisition fails/`.
>> >
>> >>
>> >>>the currrent object might be removed and all of its
>> >>>possible successsors might be not only be removed, but also freed.
>> >>>For example, when using reference counting or hazard pointers to
>> >>>
>> >>
>> >>However, there are typos here. We need to modify as follows.
>> >>
>> >>-the currrent object might be removed and all of its
>> >>-possible successsors might be not only be removed, but also freed.
>> >>+the current object might be removed and all of its
>> >>+possible successors might be not only be removed, but also freed.
>> >
>>
>> As I reread the sentence, there is an unnecessary "be" here.
>>
>> -the currrent object might be removed and all of its
>> -possible successsors might be not only be removed, but also freed.
>> +the current object might be removed and all of its
>> +possible successors might be not only removed, but also freed.
>>
>> Or we can say:
>>
>> +the current object might be removed and all of its
>> +possible successors might not only be removed, but also be freed.
>>
>> I agree with you that this sentence is fairy complicated.
>> There might be a better way to rephrase, for example, denoting
>> the end of that-clause by a comma as appended:
>
> Hmmm...  That certainly was not one of my better efforts, was it?  ;-)
>
> I reworked that paragraph and surrounding paragraphs as shown below.
> Does that help?
>
> I also applied the other three of SeongJae's patches, thank you!
> And thanks to you both for your review and comments!

Looks much better, thanks!


Thanks,
SeongJae Park

>
>                                                         Thanx, Paul
>
> ------------------------------------------------------------------------
>
> commit 22455cae203ae6707970d0565fe70dfdc4ada1ca
> Author: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> Date:   Sun Jul 17 14:41:47 2016 -0700
>
>     Self review of "Which to Choose" section
>
>     Reported-by: SeongJae Park <sj38.park@gmail.com>
>     Reported-by: Akira Yokosawa <akiyks@gmail.com>
>     Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
>
> diff --git a/defer/whichtochoose.tex b/defer/whichtochoose.tex
> index 648cdc88e406..11f3b0a24e87 100644
> --- a/defer/whichtochoose.tex
> +++ b/defer/whichtochoose.tex
> @@ -132,26 +132,48 @@ instructions.
>
>  The ``Reader Reference Acquisition'' rows indicates that only RCU is
>  capable of unconditionally acquiring references.
> -The entry for sequence locks is ``N/A'' because, again, sequence locks
> +The entry for sequence locks is ``Unsafe'' because, again, sequence locks
>  detect updates rather than acquiring references.
> -Reference counting and hazard pointers require that traversals be
> -restarted from the beginning should a given acquisition fail because
> -the currrent object might be removed and all of its
> -possible successsors might be not only be removed, but also freed.
> -For example, when using reference counting or hazard pointers to
> -protect a tree traversal, any reference-acquisition failure requires
> -that the traversal be restarted from the root of the tree.
> +Reference counting and hazard pointers both require that traversals be
> +restarted from the beginning if a given acquisition fails.
> +To see this, consider a linked list containing objects~A, B, C, and~D,
> +in that order, and the following series of events:
> +
> +\begin{enumerate}
> +\item  A reader acquires a reference to object~B.
> +\item  An updater removes~object B, but refrains from freeing it because
> +       the reader holds a reference.
> +       The list now contains objects~A, C, and~D, and
> +       object~B's \co{->next} pointer is set to \co{HAZPTR_POISON}.
> +\item  The updater removes object~C, so that the list now contains
> +       objects~A and~D.
> +       Because there is no reference to object~C, it is immediately freed.
> +\item  The reader tries to advance to the successor of the object
> +       following the now-removed object~B, but the poisoned
> +       \co{->next} pointer prevents this.
> +       Which is a good thing, because object~B's \co{->next} pointer
> +       would otherwise point to the freelist.
> +\item  The reader must therefore restart its traversal from the head
> +       of the list.
> +\end{enumerate}
> +
> +Thus, when failing to acquire a reference, a hazard-pointer or
> +reference-counter traversal must restart that traversal from the
> +beginning.
> +In the case of nested linked data structures, for example, a
> +tree containing linked lists, the traversal must be restarted from
> +the outermost data structure.
>  This situation gives RCU a significant ease-of-use advantage.
>
>  However, RCU's ease-of-use advantage does not come
>  for free, as can be seen in the ``Memory Footprint'' row.
>  RCU's support of unconditional reference acquisition means that
> -it must avoid freeing any object visible to a given RCU reader
> -until that reader completes.
> -RCU therefore has an unbounded footprint, at least unless updates
> -are artificially throttled.
> -In contrast, reference counting and hazard pointers would retain only
> -those specific data elements actually referenced by concurrent readers.
> +it must avoid freeing any object reachable by a given
> +RCU reader until that reader completes.
> +RCU therefore has an unbounded memory footprint, at least unless updates
> +are throttled.
> +In contrast, reference counting and hazard pointers need to  retain only
> +those data elements actually referenced by concurrent readers.
>
>  This tension between memory footprint and acquisition
>  failures is sometimes resolved within the Linux kernel by combining use
> @@ -159,7 +181,7 @@ of RCU and reference counters.
>  RCU is used for short-lived references, which means that RCU read-side
>  critical sections can be short.
>  These short RCU read-side critical sections in turn mean that the corresponding
> -RCU grace periods can also be short, limiting the memory footprint.
> +RCU grace periods can also be short, which limits the memory footprint.
>  For the few data elements that need longer-lived references, reference
>  counting is used.
>  This means that the complexity of reference-acquisition failure only
> @@ -181,14 +203,19 @@ a wait to free memory, which results in an situation that, for many
>  purposes, is as good as non-blocking~\cite{MathieuDesnoyers2012URCU}.
>
>  As shown in the ``Automatic Reclamation'' row, only reference
> -counting can automate freeing of memory, at least assuming non-cyclic
> -data structures.
> +counting can automate freeing of memory, and even then only
> +for non-cyclic data structures.
>
>  Finally, the ``Lines of Code'' row shows the size of the Pre-BSD
>  Routing Table implementations, giving a rough idea of relative ease of use.
>  That said, it is important to note that the reference-counting and
>  sequence-locking implementations are buggy, and that a correct
> -reference-counting implementation is considerably more complex.
> +reference-counting implementation is considerably
> +more complex~\cite{Valois95a,MagedMichael95a}.
> +For its part, a correct sequence-locking implementation requires
> +the addition of some other synchronization mechanism, for example,
> +hazard pointers or RCU, so that sequence locking detects concurrent
> +updates and the other mechanism provides safe reference acquisition.
>
>  As more experience is gained using these techniques, both separately
>  and in combination, the rules of thumb laid out in this section will
>