Documentation updates for 3.8
Subsystems (3)
cover Documentation updates for 3.8
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(-)
PATCH 1/4 Documentation: Fix memory-barriers.txt example
From: "Paul E. McKenney" <[email protected]>
This commit fixes a broken example of overlapping stores in the Documentation/memory-barriers.txt file.
--- Documentation/memory-barriers.txt | 9 +++++---- 1 files changed, 5 insertions(+), 4 deletions(-)
Documentation/memory-barriers.txt +5 -4
@@ -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}; =========================
Signature · 1 line
1.7.8
PATCH 2/4 rcu: Correct the name of a reference in list of RCU papers
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
--- Documentation/RCU/RTFP.txt | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
Documentation/RCU/RTFP.txt +1 -1
@@ -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"
Signature · 1 line
1.7.8
PATCH 3/4 RCU: Update docs to include kfree_rcu()
In reply to Paul E. McKenneyFrom: 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.
--- Documentation/RCU/listRCU.txt | 2 +- Documentation/RCU/whatisRCU.txt | 13 +++++++++++-- 2 files changed, 12 insertions(+), 3 deletions(-)
Documentation/RCU/listRCU.txt +1 -1
@@ -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; }
Documentation/RCU/whatisRCU.txt +11 -2
@@ -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
Signature · 1 line
1.7.8
PATCH 4/4 rcu: Document alternative RCU/reference-count algorithms
In reply to Paul E. McKenneyFrom: "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.
--- Documentation/RCU/rcuref.txt | 61 ++++++++++++++++++++++++++++++++++++++++- 1 files changed, 59 insertions(+), 2 deletions(-)
Documentation/RCU/rcuref.txt +59 -2
@@ -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); + ... +}
Signature · 1 line
1.7.8
Re: [PATCH tip/core/rcu 4/4] rcu: Document alternative RCU/reference-count algorithms
Quoted 47 lines · * 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(-)Documentation/RCU/rcuref.txt +8
-2@@ -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: +
Documentation/RCU/rcuref.txt Sometimes, a reference to the element needs to be obtained in the · line 82
Quoted 10 lines
Documentation/RCU/rcuref.txt +10
-0+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
Quoted 44 lines
Documentation/RCU/rcuref.txt +41
-0+ 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); + ... +}Signature · 1 line
1.7.8
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Re: [PATCH tip/core/rcu 4/4] rcu: Document alternative RCU/reference-count algorithms
Quoted 53 lines · Mathieu Desnoyers
Quoted 52 lines · * 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(-)Documentation/RCU/rcuref.txt +13
-2@@ -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
Quoted 8 lines
Documentation/RCU/rcuref.txt Sometimes, a reference to the element needs to be obtained in the · line 82
Quoted 5 lines
Documentation/RCU/rcuref.txt +5
-0+ 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
Quoted 58 lines
Otherwise, it looks good to me,
Thanks,
Mathieu
Quoted 44 lines
Documentation/RCU/rcuref.txt +41
-0+ 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); + ... +}Signature · 1 line
1.7.8Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com