Hello!
This patch series contains documentation updates as follows:
1. Fix a broken example in memory-barriers.txt.
2. Fix a paper title in RTFP.txt. (Courtesy of Dhaval Giani.)
3. Mention kfree_rcu() in the whatisRCU.txt section covering
call_rcu(), and fix example code. (Courtesy of Kees Cook.)
4. Add two more ways of combining RCU and reference counting
in rcuref.txt.
Thanx, Paul
b/Documentation/RCU/RTFP.txt | 2 -
b/Documentation/RCU/listRCU.txt | 2 -
b/Documentation/RCU/rcuref.txt | 61 ++++++++++++++++++++++++++++++++++--
b/Documentation/RCU/whatisRCU.txt | 13 ++++++-
b/Documentation/memory-barriers.txt | 9 ++---
5 files changed, 77 insertions(+), 10 deletions(-)
From: Kees Cook <[email protected]>
Mention kfree_rcu() in the call_rcu() section. Additionally fix the
example code for list replacement that used the wrong structure element.
Signed-off-by: Kees Cook <[email protected]>
Signed-off-by: Paul E. McKenney <[email protected]>
---
Documentation/RCU/listRCU.txt | 2 +-
Documentation/RCU/whatisRCU.txt | 13 +++++++++++--
2 files changed, 12 insertions(+), 3 deletions(-)
diff --git a/Documentation/RCU/listRCU.txt b/Documentation/RCU/listRCU.txt
index 4349c14..adb5a37 100644
--- a/Documentation/RCU/listRCU.txt
+++ b/Documentation/RCU/listRCU.txt
@@ -205,7 +205,7 @@ RCU ("read-copy update") its name. The RCU code is as follows:
audit_copy_rule(&ne->rule, &e->rule);
ne->rule.action = newaction;
ne->rule.file_count = newfield_count;
- list_replace_rcu(e, ne);
+ list_replace_rcu(&e->list, &ne->list);
call_rcu(&e->rcu, audit_free_rule);
return 0;
}
diff --git a/Documentation/RCU/whatisRCU.txt b/Documentation/RCU/whatisRCU.txt
index bf0f6de..160ac55 100644
--- a/Documentation/RCU/whatisRCU.txt
+++ b/Documentation/RCU/whatisRCU.txt
@@ -499,6 +499,8 @@ The foo_reclaim() function might appear as follows:
{
struct foo *fp = container_of(rp, struct foo, rcu);
+ foo_cleanup(fp->a);
+
kfree(fp);
}
@@ -521,6 +523,12 @@ o Use call_rcu() -after- removing a data element from an
read-side critical sections that might be referencing that
data item.
+If the callback for call_rcu() is not doing anything more than calling
+kfree() on the structure, you can use kfree_rcu() instead of call_rcu()
+to avoid having to write your own callback:
+
+ kfree_rcu(old_fp, rcu);
+
Again, see checklist.txt for additional rules governing the use of RCU.
@@ -773,8 +781,8 @@ a single atomic update, converting to RCU will require special care.
Also, the presence of synchronize_rcu() means that the RCU version of
delete() can now block. If this is a problem, there is a callback-based
-mechanism that never blocks, namely call_rcu(), that can be used in
-place of synchronize_rcu().
+mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can
+be used in place of synchronize_rcu().
7. FULL LIST OF RCU APIs
@@ -813,6 +821,7 @@ RCU: Critical sections Grace period Barrier
rcu_read_unlock synchronize_rcu
rcu_dereference synchronize_rcu_expedited
call_rcu
+ kfree_rcu
bh: Critical sections Grace period Barrier
--
1.7.8
From: "Paul E. McKenney" <[email protected]>
This commit fixes a broken example of overlapping stores in the
Documentation/memory-barriers.txt file.
Reported-by: Nikunj A Dadhania <[email protected]>
Signed-off-by: Paul E. McKenney <[email protected]>
---
Documentation/memory-barriers.txt | 9 +++++----
1 files changed, 5 insertions(+), 4 deletions(-)
diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 2759f7c..3c4e1b3 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -251,12 +251,13 @@ And there are a number of things that _must_ or _must_not_ be assumed:
And for:
- *A = X; Y = *A;
+ *A = X; *(A + 4) = Y;
- we may get either of:
+ we may get any of:
- STORE *A = X; Y = LOAD *A;
- STORE *A = Y = X;
+ STORE *A = X; STORE *(A + 4) = Y;
+ STORE *(A + 4) = Y; STORE *A = X;
+ STORE {*A, *(A + 4) } = {X, Y};
=========================
--
1.7.8
From: "Paul E. McKenney" <[email protected]>
The approach for mixing RCU and reference counting listed in the RCU
documentation only describes one possible approach. This approach can
result in failure on the read side, which is nice if you want fresh data,
but not so good if you want simple code. This commit therefore adds
two additional approaches that feature unconditional reference-count
acquisition by RCU readers. These approaches are very similar to that
used in the security code.
Signed-off-by: Paul E. McKenney <[email protected]>
---
Documentation/RCU/rcuref.txt | 61 ++++++++++++++++++++++++++++++++++++++++-
1 files changed, 59 insertions(+), 2 deletions(-)
diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
index 4202ad0..99ca662 100644
--- a/Documentation/RCU/rcuref.txt
+++ b/Documentation/RCU/rcuref.txt
@@ -20,7 +20,7 @@ release_referenced() delete()
{ {
... write_lock(&list_lock);
atomic_dec(&el->rc, relfunc) ...
- ... delete_element
+ ... remove_element
} write_unlock(&list_lock);
...
if (atomic_dec_and_test(&el->rc))
@@ -52,7 +52,7 @@ release_referenced() delete()
{ {
... spin_lock(&list_lock);
if (atomic_dec_and_test(&el->rc)) ...
- call_rcu(&el->head, el_free); delete_element
+ call_rcu(&el->head, el_free); remove_element
... spin_unlock(&list_lock);
} ...
if (atomic_dec_and_test(&el->rc))
@@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the
update (write) stream. In such cases, atomic_inc_not_zero() might be
overkill, since we hold the update-side spinlock. One might instead
use atomic_inc() in such cases.
+
+It is not always convenient to deal with "FAIL" in the
+search_and_reference() code path. In such cases, the
+atomic_dec_and_test() may be moved from delete() to el_free()
+as follows:
+
+1. 2.
+add() search_and_reference()
+{ {
+ alloc_object rcu_read_lock();
+ ... search_for_element
+ atomic_set(&el->rc, 1); atomic_inc(&el->rc);
+ spin_lock(&list_lock); ...
+
+ add_element rcu_read_unlock();
+ ... }
+ spin_unlock(&list_lock); 4.
+} delete()
+3. {
+release_referenced() spin_lock(&list_lock);
+{ ...
+ ... remove_element
+ if (atomic_dec_and_test(&el->rc)) spin_unlock(&list_lock);
+ kfree(el); ...
+ ... call_rcu(&el->head, el_free);
+} ...
+5. }
+void el_free(struct rcu_head *rhp)
+{
+ release_referenced();
+}
+
+The key point is that the initial reference added by add() is not removed
+until after a grace period has elapsed following removal. This means that
+search_and_reference() cannot find this element, which means that the value
+of el->rc cannot increase. Thus, once it reaches zero, there are no
+readers that can or ever will be able to reference the element. The
+element can therefore safely be freed. This in turn guarantees that if
+any reader finds the element, that reader may safely acquire a reference
+without checking the value of the reference counter.
+
+In cases where delete() can sleep, synchronize_rcu() can be called from
+delete(), so that el_free() can be subsumed into delete as follows:
+
+4.
+delete()
+{
+ spin_lock(&list_lock);
+ ...
+ remove_element
+ spin_unlock(&list_lock);
+ ...
+ synchronize_rcu();
+ if (atomic_dec_and_test(&el->rc))
+ kfree(el);
+ ...
+}
--
1.7.8
From: Dhaval Giani <[email protected]>
Trying to go through the history of RCU (not for the weak
minded) led me to search for a non-existent paper.
Correct it to the actual reference
Signed-off-by: Dhaval Giani <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Signed-off-by: Paul E. McKenney <[email protected]>
---
Documentation/RCU/RTFP.txt | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt
index 7c1dfb1..7f40c72 100644
--- a/Documentation/RCU/RTFP.txt
+++ b/Documentation/RCU/RTFP.txt
@@ -186,7 +186,7 @@ Bibtex Entries
@article{Kung80
,author="H. T. Kung and Q. Lehman"
-,title="Concurrent Maintenance of Binary Search Trees"
+,title="Concurrent Manipulation of Binary Search Trees"
,Year="1980"
,Month="September"
,journal="ACM Transactions on Database Systems"
--
1.7.8
* Paul E. McKenney ([email protected]) wrote:
> From: "Paul E. McKenney" <[email protected]>
>
> The approach for mixing RCU and reference counting listed in the RCU
> documentation only describes one possible approach. This approach can
> result in failure on the read side, which is nice if you want fresh data,
> but not so good if you want simple code. This commit therefore adds
> two additional approaches that feature unconditional reference-count
> acquisition by RCU readers. These approaches are very similar to that
> used in the security code.
>
> Signed-off-by: Paul E. McKenney <[email protected]>
> ---
> Documentation/RCU/rcuref.txt | 61 ++++++++++++++++++++++++++++++++++++++++-
> 1 files changed, 59 insertions(+), 2 deletions(-)
>
> diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
> index 4202ad0..99ca662 100644
> --- a/Documentation/RCU/rcuref.txt
> +++ b/Documentation/RCU/rcuref.txt
> @@ -20,7 +20,7 @@ release_referenced() delete()
> { {
> ... write_lock(&list_lock);
> atomic_dec(&el->rc, relfunc) ...
> - ... delete_element
> + ... remove_element
> } write_unlock(&list_lock);
> ...
> if (atomic_dec_and_test(&el->rc))
> @@ -52,7 +52,7 @@ release_referenced() delete()
> { {
> ... spin_lock(&list_lock);
> if (atomic_dec_and_test(&el->rc)) ...
> - call_rcu(&el->head, el_free); delete_element
> + call_rcu(&el->head, el_free); remove_element
> ... spin_unlock(&list_lock);
> } ...
> if (atomic_dec_and_test(&el->rc))
> @@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the
> update (write) stream. In such cases, atomic_inc_not_zero() might be
> overkill, since we hold the update-side spinlock. One might instead
> use atomic_inc() in such cases.
> +
> +It is not always convenient to deal with "FAIL" in the
> +search_and_reference() code path. In such cases, the
> +atomic_dec_and_test() may be moved from delete() to el_free()
> +as follows:
> +
> +1. 2.
> +add() search_and_reference()
> +{ {
> + alloc_object rcu_read_lock();
> + ... search_for_element
> + atomic_set(&el->rc, 1); atomic_inc(&el->rc);
> + spin_lock(&list_lock); ...
> +
> + add_element rcu_read_unlock();
> + ... }
indentation looks wrong in my mail client for the two lines above (for
the 2. block).
Otherwise, it looks good to me,
Thanks,
Mathieu
> + spin_unlock(&list_lock); 4.
> +} delete()
> +3. {
> +release_referenced() spin_lock(&list_lock);
> +{ ...
> + ... remove_element
> + if (atomic_dec_and_test(&el->rc)) spin_unlock(&list_lock);
> + kfree(el); ...
> + ... call_rcu(&el->head, el_free);
> +} ...
> +5. }
> +void el_free(struct rcu_head *rhp)
> +{
> + release_referenced();
> +}
> +
> +The key point is that the initial reference added by add() is not removed
> +until after a grace period has elapsed following removal. This means that
> +search_and_reference() cannot find this element, which means that the value
> +of el->rc cannot increase. Thus, once it reaches zero, there are no
> +readers that can or ever will be able to reference the element. The
> +element can therefore safely be freed. This in turn guarantees that if
> +any reader finds the element, that reader may safely acquire a reference
> +without checking the value of the reference counter.
> +
> +In cases where delete() can sleep, synchronize_rcu() can be called from
> +delete(), so that el_free() can be subsumed into delete as follows:
> +
> +4.
> +delete()
> +{
> + spin_lock(&list_lock);
> + ...
> + remove_element
> + spin_unlock(&list_lock);
> + ...
> + synchronize_rcu();
> + if (atomic_dec_and_test(&el->rc))
> + kfree(el);
> + ...
> +}
> --
> 1.7.8
>
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
On Tue, Oct 30, 2012 at 12:21:03PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney ([email protected]) wrote:
> > From: "Paul E. McKenney" <[email protected]>
> >
> > The approach for mixing RCU and reference counting listed in the RCU
> > documentation only describes one possible approach. This approach can
> > result in failure on the read side, which is nice if you want fresh data,
> > but not so good if you want simple code. This commit therefore adds
> > two additional approaches that feature unconditional reference-count
> > acquisition by RCU readers. These approaches are very similar to that
> > used in the security code.
> >
> > Signed-off-by: Paul E. McKenney <[email protected]>
> > ---
> > Documentation/RCU/rcuref.txt | 61 ++++++++++++++++++++++++++++++++++++++++-
> > 1 files changed, 59 insertions(+), 2 deletions(-)
> >
> > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
> > index 4202ad0..99ca662 100644
> > --- a/Documentation/RCU/rcuref.txt
> > +++ b/Documentation/RCU/rcuref.txt
> > @@ -20,7 +20,7 @@ release_referenced() delete()
> > { {
> > ... write_lock(&list_lock);
> > atomic_dec(&el->rc, relfunc) ...
> > - ... delete_element
> > + ... remove_element
> > } write_unlock(&list_lock);
> > ...
> > if (atomic_dec_and_test(&el->rc))
> > @@ -52,7 +52,7 @@ release_referenced() delete()
> > { {
> > ... spin_lock(&list_lock);
> > if (atomic_dec_and_test(&el->rc)) ...
> > - call_rcu(&el->head, el_free); delete_element
> > + call_rcu(&el->head, el_free); remove_element
> > ... spin_unlock(&list_lock);
> > } ...
> > if (atomic_dec_and_test(&el->rc))
> > @@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the
> > update (write) stream. In such cases, atomic_inc_not_zero() might be
> > overkill, since we hold the update-side spinlock. One might instead
> > use atomic_inc() in such cases.
> > +
> > +It is not always convenient to deal with "FAIL" in the
> > +search_and_reference() code path. In such cases, the
> > +atomic_dec_and_test() may be moved from delete() to el_free()
> > +as follows:
> > +
> > +1. 2.
> > +add() search_and_reference()
> > +{ {
> > + alloc_object rcu_read_lock();
> > + ... search_for_element
> > + atomic_set(&el->rc, 1); atomic_inc(&el->rc);
> > + spin_lock(&list_lock); ...
> > +
> > + add_element rcu_read_unlock();
> > + ... }
>
> indentation looks wrong in my mail client for the two lines above (for
> the 2. block).
Ah, the "+" characters offset the tab stops. Looks OK in the actual
file when the patch is applied. (Though it would not hurt to check.)
Thanx, Paul
> Otherwise, it looks good to me,
>
> Thanks,
>
> Mathieu
>
>
> > + spin_unlock(&list_lock); 4.
> > +} delete()
> > +3. {
> > +release_referenced() spin_lock(&list_lock);
> > +{ ...
> > + ... remove_element
> > + if (atomic_dec_and_test(&el->rc)) spin_unlock(&list_lock);
> > + kfree(el); ...
> > + ... call_rcu(&el->head, el_free);
> > +} ...
> > +5. }
> > +void el_free(struct rcu_head *rhp)
> > +{
> > + release_referenced();
> > +}
> > +
> > +The key point is that the initial reference added by add() is not removed
> > +until after a grace period has elapsed following removal. This means that
> > +search_and_reference() cannot find this element, which means that the value
> > +of el->rc cannot increase. Thus, once it reaches zero, there are no
> > +readers that can or ever will be able to reference the element. The
> > +element can therefore safely be freed. This in turn guarantees that if
> > +any reader finds the element, that reader may safely acquire a reference
> > +without checking the value of the reference counter.
> > +
> > +In cases where delete() can sleep, synchronize_rcu() can be called from
> > +delete(), so that el_free() can be subsumed into delete as follows:
> > +
> > +4.
> > +delete()
> > +{
> > + spin_lock(&list_lock);
> > + ...
> > + remove_element
> > + spin_unlock(&list_lock);
> > + ...
> > + synchronize_rcu();
> > + if (atomic_dec_and_test(&el->rc))
> > + kfree(el);
> > + ...
> > +}
> > --
> > 1.7.8
> >
>
> --
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
>