RCU documentation
Subsystems (2)
RFC PATCH 1/1 RCU documentation
Hello!
Attached is a patch to place some RCU documentation in the Documentation directory. Patch should apply to pretty much any kernel version. ;-)
Thoughts?
Thanx, Paul
RTFP.txt | 352 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ UP.txt | 64 ++++++++++ checklist.txt | 157 +++++++++++++++++++++++++ listRCU.txt | 301 +++++++++++++++++++++++++++++++++++++++++++++++++ rcu.txt | 56 +++++++++ 5 files changed, 930 insertions(+)
Documentation/RCU/UP.txt +64 -0
@@ -0,0 +1,64 @@ +RCU on Uniprocessor Systems + + +A common misconception is that, on UP systems, the call_rcu() primitive +may immediately invoke its function, and that the synchronize_kernel +primitive may return immediately. The basis of this misconception +is that since there is only one CPU, it should not be necessary to +wait for anything else to get done, since there are no other CPUs for +anything else to be happening on. Although this approach will sort of +work a surprising amount of the time, it is a very bad idea in general. +This document presents two examples that demonstrate exactly how bad an +idea this is. + + +Example 1: softirq Suicide + +Suppose that an RCU-based algorithm scans a linked list containing +elements A, B, and C in process context, and can delete elements from +this same list in softirq context. Suppose that the process-context scan +is referencing element B when it is interrupted by softirq processing, +which deletes element B, and then invokes call_rcu() to free element B +after a grace period. + +Now, if call_rcu() were to directly invoke its arguments, then upon return +from softirq, the list scan would find itself referencing a newly freed +element B. This situation can greatly decrease the life expectancy of +your kernel. + + +Example 2: Function-Call Fatality + +Of course, one could avert the suicide described in the preceding example +by having call_rcu() directly invoke its arguments only if it was called +from process context. However, this can fail in a similar manner. + +Suppose that an RCU-based algorithm again scans a linked list containing +elements A, B, and C in process contexts, but that it invokes a function +on each element as it is scanned. Suppose further that this function +deletes element B from the list, then passes it to call_rcu() for deferred +freeing. This may be a bit unconventional, but it is perfectly legal +RCU usage, since call_rcu() must wait for a grace period to elapse. +Therefore, in this case, allowing call_rcu() to immediately invoke +its arguments would cause it to fail to make the fundamental guarantee +underlying RCU, namely that call_rcu() defers invoking its arguments until +all RCU read-side critical sections currently executing have completed. + +Quick Quiz: why is it -not- legal to invoke synchronize_kernel() in +this case? + + +Summary + +Permitting call_rcu() to immediatly invoke its arguments or permitting +synchronize_kernel() to immediatly return breaks RCU, even on a UP system. +So do not do it! Even on a UP system, the RCU infrastructure -must- +respect grace periods. + + +Answer to Quick Quiz + +The calling function is scanning an RCU-protected linked list, and +is therefore within an RCU read-side critical section. Therefore, +the called function has been invoked within an RCU read-side critical +section, and is not permitted to block.
Documentation/RCU/checklist.txt +157 -0
157 lines not on this page · raw message
Documentation/RCU/listRCU.txt +301 -0
301 lines not on this page · raw message
Documentation/RCU/rcu.txt +56 -0
56 lines not on this page · raw message
Documentation/RCU/RTFP.txt +352 -0
352 lines not on this page · raw message
Quoted 4 lines · On Tue, 7 Sep 2004 16:28:55 -0700 "Paul E. McKenney" <[email protected]> wrote:
Attached is a patch to place some RCU documentation in the Documentation directory. Patch should apply to pretty much any kernel version. ;-)
Thoughts?
Looks nice :)
Quoted 1 line · Paul E. McKenney
Hello!
Hello Paul,
[...]
Quoted 4 lines
Documentation/RCU/listRCU.txt +3
-0+ static inline int audit_upd_rule(struct audit_rule *rule, + struct list_head *list, + __u32 newaction,
Documentation/RCU/listRCU.txt line 198
Quoted 10 lines
Documentation/RCU/listRCU.txt +10
-0+ __u32 newfield_count) + { + struct audit_entry *e; + struct audit_newentry *ne; + + list_for_each_entry(e, list, list) { + if (!audit_compare_rule(rule, &e->rule)) { + ne = kmalloc(sizeof(*entry), GFP_ATOMIC); + if (ne == NULL) + return _ENOMEM;
-ENOMEM;
Quoted 2 lines
Documentation/RCU/listRCU.txt +2
-0+ audit_copy_rule(&ne->rule, &e->rule); + ne->rule.action = newaction;
[...]
Documentation/RCU/listRCU.txt line 249
Quoted 13 lines
Documentation/RCU/listRCU.txt +13
-0+ static enum audit_state audit_filter_task(struct task_struct *tsk) + { + struct audit_entry *e; + enum audit_state state; + + rcu_read_lock(); + list_for_each_entry_rcu(e, &audit_tsklist, list) { + if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { + spin_lock(&e->lock); + if (e->deleted) { + spin_unlock(&e->lock); + rcu_read_unlock(); + return AUDIT_BUILD_CONTEXT;
Shouldn't this be "continue", to work correctly in the face of mutators similar to audit_upd_rule(), that at some point leave both old (marked ->deleted) and new versions on the list?
Also, RCU used instead of existential lock is so typical, that it probably deserves dedicated example.
Review
Quoted 1 line
(quoted diff) +1
-0+ }
[...]
Nikita.
Quoted 4 lines · Nikita Danilov
Quoted 1 line · Paul E. McKenney
Hello!
Hello Paul,
Hello, Nikita!
Quoted 18 lines
[...]
Quoted 4 lines
Documentation/RCU/listRCU.txt +3
-0+ static inline int audit_upd_rule(struct audit_rule *rule, + struct list_head *list, + __u32 newaction,Documentation/RCU/listRCU.txt line 198
Quoted 10 lines
Documentation/RCU/listRCU.txt +10
-0+ __u32 newfield_count) + { + struct audit_entry *e; + struct audit_newentry *ne; + + list_for_each_entry(e, list, list) { + if (!audit_compare_rule(rule, &e->rule)) { + ne = kmalloc(sizeof(*entry), GFP_ATOMIC); + if (ne == NULL) + return _ENOMEM;
-ENOMEM;
Good catch!
Quoted 14 lines
Quoted 2 lines
Documentation/RCU/listRCU.txt +2
-0+ audit_copy_rule(&ne->rule, &e->rule); + ne->rule.action = newaction;[...]
Quoted 9 lines
Documentation/RCU/listRCU.txt +9
-0+ static enum audit_state audit_filter_task(struct task_struct *tsk) + { + struct audit_entry *e; + enum audit_state state; + + rcu_read_lock(); + list_for_each_entry_rcu(e, &audit_tsklist, list) { + if (audit_filter_rules(tsk, &e->rule, NULL, &state)) { + spin_lock(&e->lock);
Quoted 8 lines
Documentation/RCU/listRCU.txt line 249
Quoted 4 lines
Documentation/RCU/listRCU.txt +4
-0+ if (e->deleted) { + spin_unlock(&e->lock); + rcu_read_unlock(); + return AUDIT_BUILD_CONTEXT;Shouldn't this be "continue", to work correctly in the face of mutators similar to
audit_upd_rule(), that at some point leave both old (marked ->deleted) and new versions on the list?
Interesting point -- update-in-place combined with the ->deleted flag does require some additional mechanism. In some cases, the approach you call out works (give or take the need for added memory barriers in order to guarantee that the list_add_rcu() happends before the list_del_rcu()). In other cases, such as in dcache, it is necessary to restart the search from the beginning.
My thought would be to add some words saying that this example is not cumulative with the _upd_ example. I do need to keep the simple deleted-flag example, since this is a common usage.
Thoughts?
Quoted 2 lines
Also, RCU used instead of existential lock is so typical, that it probably deserves dedicated example.
Excellent point, will add this. Any favorite example code? ;-)
Thanx, Paul
Quoted 6 lines
Review
Quoted 1 line
(quoted diff) +1
-0+ }[...]
Nikita.