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@xxxxxxxxx>
> >>>---
> >>>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@xxxxxxxxxxxxxxxxxx>
Date: Sun Jul 17 14:41:47 2016 -0700
Self review of "Which to Choose" section
Reported-by: SeongJae Park <sj38.park@xxxxxxxxx>
Reported-by: Akira Yokosawa <akiyks@xxxxxxxxx>
Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>
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
--
To unsubscribe from this list: send the line "unsubscribe perfbook" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
