aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation
diff options
context:
space:
mode:
authorPaul E. McKenney <paulmck@us.ibm.com>2006-02-01 06:06:42 -0500
committerLinus Torvalds <torvalds@g5.osdl.org>2006-02-01 11:53:25 -0500
commitd19720a909b4443f78cbb03f4f090180e143ad9d (patch)
tree56e579612d82f4b30d5cb943df1079b0b5f4700a /Documentation
parent53d8be5c144ece5d48745810b14248968e73eaf2 (diff)
[PATCH] RCU documentation fixes (January 2006 update)
Updates to in-tree RCU documentation based on comments over the past few months. Signed-off-by: "Paul E. McKenney" <paulmck@us.ibm.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'Documentation')
-rw-r--r--Documentation/RCU/RTFP.txt25
-rw-r--r--Documentation/RCU/checklist.txt6
-rw-r--r--Documentation/RCU/listRCU.txt21
-rw-r--r--Documentation/RCU/rcu.txt5
-rw-r--r--Documentation/RCU/rcuref.txt31
-rw-r--r--Documentation/RCU/whatisRCU.txt29
6 files changed, 69 insertions, 48 deletions
diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt
index fcbcbc35b122..6221464d1a7e 100644
--- a/Documentation/RCU/RTFP.txt
+++ b/Documentation/RCU/RTFP.txt
@@ -90,16 +90,20 @@ at OLS. The resulting abundance of RCU patches was presented the
90following year [McKenney02a], and use of RCU in dcache was first 90following year [McKenney02a], and use of RCU in dcache was first
91described that same year [Linder02a]. 91described that same year [Linder02a].
92 92
93Also in 2002, Michael [Michael02b,Michael02a] presented techniques 93Also in 2002, Michael [Michael02b,Michael02a] presented "hazard-pointer"
94that defer the destruction of data structures to simplify non-blocking 94techniques that defer the destruction of data structures to simplify
95synchronization (wait-free synchronization, lock-free synchronization, 95non-blocking synchronization (wait-free synchronization, lock-free
96and obstruction-free synchronization are all examples of non-blocking 96synchronization, and obstruction-free synchronization are all examples of
97synchronization). In particular, this technique eliminates locking, 97non-blocking synchronization). In particular, this technique eliminates
98reduces contention, reduces memory latency for readers, and parallelizes 98locking, reduces contention, reduces memory latency for readers, and
99pipeline stalls and memory latency for writers. However, these 99parallelizes pipeline stalls and memory latency for writers. However,
100techniques still impose significant read-side overhead in the form of 100these techniques still impose significant read-side overhead in the
101memory barriers. Researchers at Sun worked along similar lines in the 101form of memory barriers. Researchers at Sun worked along similar lines
102same timeframe [HerlihyLM02,HerlihyLMS03]. 102in the same timeframe [HerlihyLM02,HerlihyLMS03]. These techniques
103can be thought of as inside-out reference counts, where the count is
104represented by the number of hazard pointers referencing a given data
105structure (rather than the more conventional counter field within the
106data structure itself).
103 107
104In 2003, the K42 group described how RCU could be used to create 108In 2003, the K42 group described how RCU could be used to create
105hot-pluggable implementations of operating-system functions. Later that 109hot-pluggable implementations of operating-system functions. Later that
@@ -113,7 +117,6 @@ number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
113describing how to make RCU safe for soft-realtime applications [Sarma04c], 117describing how to make RCU safe for soft-realtime applications [Sarma04c],
114and a paper describing SELinux performance with RCU [JamesMorris04b]. 118and a paper describing SELinux performance with RCU [JamesMorris04b].
115 119
116
1172005 has seen further adaptation of RCU to realtime use, permitting 1202005 has seen further adaptation of RCU to realtime use, permitting
118preemption of RCU realtime critical sections [PaulMcKenney05a, 121preemption of RCU realtime critical sections [PaulMcKenney05a,
119PaulMcKenney05b]. 122PaulMcKenney05b].
diff --git a/Documentation/RCU/checklist.txt b/Documentation/RCU/checklist.txt
index e118a7c1a092..49e27cc19385 100644
--- a/Documentation/RCU/checklist.txt
+++ b/Documentation/RCU/checklist.txt
@@ -177,3 +177,9 @@ over a rather long period of time, but improvements are always welcome!
177 177
178 If you want to wait for some of these other things, you might 178 If you want to wait for some of these other things, you might
179 instead need to use synchronize_irq() or synchronize_sched(). 179 instead need to use synchronize_irq() or synchronize_sched().
180
18112. Any lock acquired by an RCU callback must be acquired elsewhere
182 with irq disabled, e.g., via spin_lock_irqsave(). Failing to
183 disable irq on a given acquisition of that lock will result in
184 deadlock as soon as the RCU callback happens to interrupt that
185 acquisition's critical section.
diff --git a/Documentation/RCU/listRCU.txt b/Documentation/RCU/listRCU.txt
index f8a54fa0d8ab..1fd175368a87 100644
--- a/Documentation/RCU/listRCU.txt
+++ b/Documentation/RCU/listRCU.txt
@@ -232,7 +232,7 @@ entry does not exist. For this to be helpful, the search function must
232return holding the per-entry spinlock, as ipc_lock() does in fact do. 232return holding the per-entry spinlock, as ipc_lock() does in fact do.
233 233
234Quick Quiz: Why does the search function need to return holding the 234Quick Quiz: Why does the search function need to return holding the
235per-entry lock for this deleted-flag technique to be helpful? 235 per-entry lock for this deleted-flag technique to be helpful?
236 236
237If the system-call audit module were to ever need to reject stale data, 237If the system-call audit module were to ever need to reject stale data,
238one way to accomplish this would be to add a "deleted" flag and a "lock" 238one way to accomplish this would be to add a "deleted" flag and a "lock"
@@ -275,8 +275,8 @@ flag under the spinlock as follows:
275 { 275 {
276 struct audit_entry *e; 276 struct audit_entry *e;
277 277
278 /* Do not use the _rcu iterator here, since this is the only 278 /* Do not need to use the _rcu iterator here, since this
279 * deletion routine. */ 279 * is the only deletion routine. */
280 list_for_each_entry(e, list, list) { 280 list_for_each_entry(e, list, list) {
281 if (!audit_compare_rule(rule, &e->rule)) { 281 if (!audit_compare_rule(rule, &e->rule)) {
282 spin_lock(&e->lock); 282 spin_lock(&e->lock);
@@ -304,9 +304,12 @@ function to reject newly deleted data.
304 304
305 305
306Answer to Quick Quiz 306Answer to Quick Quiz
307 307 Why does the search function need to return holding the per-entry
308If the search function drops the per-entry lock before returning, then 308 lock for this deleted-flag technique to be helpful?
309the caller will be processing stale data in any case. If it is really 309
310OK to be processing stale data, then you don't need a "deleted" flag. 310 If the search function drops the per-entry lock before returning,
311If processing stale data really is a problem, then you need to hold the 311 then the caller will be processing stale data in any case. If it
312per-entry lock across all of the code that uses the value looked up. 312 is really OK to be processing stale data, then you don't need a
313 "deleted" flag. If processing stale data really is a problem,
314 then you need to hold the per-entry lock across all of the code
315 that uses the value that was returned.
diff --git a/Documentation/RCU/rcu.txt b/Documentation/RCU/rcu.txt
index 6fa092251586..02e27bf1d365 100644
--- a/Documentation/RCU/rcu.txt
+++ b/Documentation/RCU/rcu.txt
@@ -111,6 +111,11 @@ o What are all these files in this directory?
111 111
112 You are reading it! 112 You are reading it!
113 113
114 rcuref.txt
115
116 Describes how to combine use of reference counts
117 with RCU.
118
114 whatisRCU.txt 119 whatisRCU.txt
115 120
116 Overview of how the RCU implementation works. Along 121 Overview of how the RCU implementation works. Along
diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
index 3f60db41b2f0..451de2ad8329 100644
--- a/Documentation/RCU/rcuref.txt
+++ b/Documentation/RCU/rcuref.txt
@@ -1,7 +1,7 @@
1Refcounter design for elements of lists/arrays protected by RCU. 1Reference-count design for elements of lists/arrays protected by RCU.
2 2
3Refcounting on elements of lists which are protected by traditional 3Reference counting on elements of lists which are protected by traditional
4reader/writer spinlocks or semaphores are straight forward as in: 4reader/writer spinlocks or semaphores are straightforward:
5 5
61. 2. 61. 2.
7add() search_and_reference() 7add() search_and_reference()
@@ -28,12 +28,12 @@ release_referenced() delete()
28 ... 28 ...
29 } 29 }
30 30
31If this list/array is made lock free using rcu as in changing the 31If this list/array is made lock free using RCU as in changing the
32write_lock in add() and delete() to spin_lock and changing read_lock 32write_lock() in add() and delete() to spin_lock and changing read_lock
33in search_and_reference to rcu_read_lock(), the atomic_get in 33in search_and_reference to rcu_read_lock(), the atomic_get in
34search_and_reference could potentially hold reference to an element which 34search_and_reference could potentially hold reference to an element which
35has already been deleted from the list/array. atomic_inc_not_zero takes 35has already been deleted from the list/array. Use atomic_inc_not_zero()
36care of this scenario. search_and_reference should look as; 36in this scenario as follows:
37 37
381. 2. 381. 2.
39add() search_and_reference() 39add() search_and_reference()
@@ -51,17 +51,16 @@ add() search_and_reference()
51release_referenced() delete() 51release_referenced() delete()
52{ { 52{ {
53 ... write_lock(&list_lock); 53 ... write_lock(&list_lock);
54 atomic_dec(&el->rc, relfunc) ... 54 if (atomic_dec_and_test(&el->rc)) ...
55 ... delete_element 55 call_rcu(&el->head, el_free); delete_element
56} write_unlock(&list_lock); 56 ... write_unlock(&list_lock);
57 ... 57} ...
58 if (atomic_dec_and_test(&el->rc)) 58 if (atomic_dec_and_test(&el->rc))
59 call_rcu(&el->head, el_free); 59 call_rcu(&el->head, el_free);
60 ... 60 ...
61 } 61 }
62 62
63Sometimes, reference to the element need to be obtained in the 63Sometimes, a reference to the element needs to be obtained in the
64update (write) stream. In such cases, atomic_inc_not_zero might be an 64update (write) stream. In such cases, atomic_inc_not_zero() might be
65overkill since the spinlock serialising list updates are held. atomic_inc 65overkill, since we hold the update-side spinlock. One might instead
66is to be used in such cases. 66use atomic_inc() in such cases.
67
diff --git a/Documentation/RCU/whatisRCU.txt b/Documentation/RCU/whatisRCU.txt
index 15da16861fa3..5ed85af88789 100644
--- a/Documentation/RCU/whatisRCU.txt
+++ b/Documentation/RCU/whatisRCU.txt
@@ -200,10 +200,11 @@ rcu_assign_pointer()
200 the new value, and also executes any memory-barrier instructions 200 the new value, and also executes any memory-barrier instructions
201 required for a given CPU architecture. 201 required for a given CPU architecture.
202 202
203 Perhaps more important, it serves to document which pointers 203 Perhaps just as important, it serves to document (1) which
204 are protected by RCU. That said, rcu_assign_pointer() is most 204 pointers are protected by RCU and (2) the point at which a
205 frequently used indirectly, via the _rcu list-manipulation 205 given structure becomes accessible to other CPUs. That said,
206 primitives such as list_add_rcu(). 206 rcu_assign_pointer() is most frequently used indirectly, via
207 the _rcu list-manipulation primitives such as list_add_rcu().
207 208
208rcu_dereference() 209rcu_dereference()
209 210
@@ -258,9 +259,11 @@ rcu_dereference()
258 locking. 259 locking.
259 260
260 As with rcu_assign_pointer(), an important function of 261 As with rcu_assign_pointer(), an important function of
261 rcu_dereference() is to document which pointers are protected 262 rcu_dereference() is to document which pointers are protected by
262 by RCU. And, again like rcu_assign_pointer(), rcu_dereference() 263 RCU, in particular, flagging a pointer that is subject to changing
263 is typically used indirectly, via the _rcu list-manipulation 264 at any time, including immediately after the rcu_dereference().
265 And, again like rcu_assign_pointer(), rcu_dereference() is
266 typically used indirectly, via the _rcu list-manipulation
264 primitives, such as list_for_each_entry_rcu(). 267 primitives, such as list_for_each_entry_rcu().
265 268
266The following diagram shows how each API communicates among the 269The following diagram shows how each API communicates among the
@@ -327,7 +330,7 @@ for specialized uses, but are relatively uncommon.
3273. WHAT ARE SOME EXAMPLE USES OF CORE RCU API? 3303. WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
328 331
329This section shows a simple use of the core RCU API to protect a 332This section shows a simple use of the core RCU API to protect a
330global pointer to a dynamically allocated structure. More typical 333global pointer to a dynamically allocated structure. More-typical
331uses of RCU may be found in listRCU.txt, arrayRCU.txt, and NMI-RCU.txt. 334uses of RCU may be found in listRCU.txt, arrayRCU.txt, and NMI-RCU.txt.
332 335
333 struct foo { 336 struct foo {
@@ -410,6 +413,8 @@ o Use synchronize_rcu() -after- removing a data element from an
410 data item. 413 data item.
411 414
412See checklist.txt for additional rules to follow when using RCU. 415See checklist.txt for additional rules to follow when using RCU.
416And again, more-typical uses of RCU may be found in listRCU.txt,
417arrayRCU.txt, and NMI-RCU.txt.
413 418
414 419
4154. WHAT IF MY UPDATING THREAD CANNOT BLOCK? 4204. WHAT IF MY UPDATING THREAD CANNOT BLOCK?
@@ -513,7 +518,7 @@ production-quality implementation, and see:
513 518
514for papers describing the Linux kernel RCU implementation. The OLS'01 519for papers describing the Linux kernel RCU implementation. The OLS'01
515and OLS'02 papers are a good introduction, and the dissertation provides 520and OLS'02 papers are a good introduction, and the dissertation provides
516more details on the current implementation. 521more details on the current implementation as of early 2004.
517 522
518 523
5195A. "TOY" IMPLEMENTATION #1: LOCKING 5245A. "TOY" IMPLEMENTATION #1: LOCKING
@@ -768,7 +773,6 @@ RCU pointer/list traversal:
768 rcu_dereference 773 rcu_dereference
769 list_for_each_rcu (to be deprecated in favor of 774 list_for_each_rcu (to be deprecated in favor of
770 list_for_each_entry_rcu) 775 list_for_each_entry_rcu)
771 list_for_each_safe_rcu (deprecated, not used)
772 list_for_each_entry_rcu 776 list_for_each_entry_rcu
773 list_for_each_continue_rcu (to be deprecated in favor of new 777 list_for_each_continue_rcu (to be deprecated in favor of new
774 list_for_each_entry_continue_rcu) 778 list_for_each_entry_continue_rcu)
@@ -807,7 +811,8 @@ Quick Quiz #1: Why is this argument naive? How could a deadlock
807Answer: Consider the following sequence of events: 811Answer: Consider the following sequence of events:
808 812
809 1. CPU 0 acquires some unrelated lock, call it 813 1. CPU 0 acquires some unrelated lock, call it
810 "problematic_lock". 814 "problematic_lock", disabling irq via
815 spin_lock_irqsave().
811 816
812 2. CPU 1 enters synchronize_rcu(), write-acquiring 817 2. CPU 1 enters synchronize_rcu(), write-acquiring
813 rcu_gp_mutex. 818 rcu_gp_mutex.
@@ -894,7 +899,7 @@ Answer: Just as PREEMPT_RT permits preemption of spinlock
894ACKNOWLEDGEMENTS 899ACKNOWLEDGEMENTS
895 900
896My thanks to the people who helped make this human-readable, including 901My thanks to the people who helped make this human-readable, including
897Jon Walpole, Josh Triplett, Serge Hallyn, and Suzanne Wood. 902Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern.
898 903
899 904
900For more information, see http://www.rdrop.com/users/paulmck/RCU. 905For more information, see http://www.rdrop.com/users/paulmck/RCU.