]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | Review Checklist for RCU Patches |
2 | ||
3 | ||
4 | This document contains a checklist for producing and reviewing patches | |
5 | that make use of RCU. Violating any of the rules listed below will | |
6 | result in the same sorts of problems that leaving out a locking primitive | |
7 | would cause. This list is based on experiences reviewing such patches | |
8 | over a rather long period of time, but improvements are always welcome! | |
9 | ||
10 | 0. Is RCU being applied to a read-mostly situation? If the data | |
11 | structure is updated more than about 10% of the time, then | |
12 | you should strongly consider some other approach, unless | |
13 | detailed performance measurements show that RCU is nonetheless | |
14 | the right tool for the job. | |
15 | ||
16 | The other exception would be where performance is not an issue, | |
17 | and RCU provides a simpler implementation. An example of this | |
18 | situation is the dynamic NMI code in the Linux 2.6 kernel, | |
19 | at least on architectures where NMIs are rare. | |
20 | ||
21 | 1. Does the update code have proper mutual exclusion? | |
22 | ||
23 | RCU does allow -readers- to run (almost) naked, but -writers- must | |
24 | still use some sort of mutual exclusion, such as: | |
25 | ||
26 | a. locking, | |
27 | b. atomic operations, or | |
28 | c. restricting updates to a single task. | |
29 | ||
30 | If you choose #b, be prepared to describe how you have handled | |
31 | memory barriers on weakly ordered machines (pretty much all of | |
32 | them -- even x86 allows reads to be reordered), and be prepared | |
33 | to explain why this added complexity is worthwhile. If you | |
34 | choose #c, be prepared to explain how this single task does not | |
a83f1fe2 PM |
35 | become a major bottleneck on big multiprocessor machines (for |
36 | example, if the task is updating information relating to itself | |
37 | that other tasks can read, there by definition can be no | |
38 | bottleneck). | |
1da177e4 LT |
39 | |
40 | 2. Do the RCU read-side critical sections make proper use of | |
41 | rcu_read_lock() and friends? These primitives are needed | |
42 | to suppress preemption (or bottom halves, in the case of | |
43 | rcu_read_lock_bh()) in the read-side critical sections, | |
44 | and are also an excellent aid to readability. | |
45 | ||
dd81eca8 PM |
46 | As a rough rule of thumb, any dereference of an RCU-protected |
47 | pointer must be covered by rcu_read_lock() or rcu_read_lock_bh() | |
48 | or by the appropriate update-side lock. | |
49 | ||
1da177e4 LT |
50 | 3. Does the update code tolerate concurrent accesses? |
51 | ||
52 | The whole point of RCU is to permit readers to run without | |
53 | any locks or atomic operations. This means that readers will | |
54 | be running while updates are in progress. There are a number | |
55 | of ways to handle this concurrency, depending on the situation: | |
56 | ||
57 | a. Make updates appear atomic to readers. For example, | |
58 | pointer updates to properly aligned fields will appear | |
59 | atomic, as will individual atomic primitives. Operations | |
60 | performed under a lock and sequences of multiple atomic | |
61 | primitives will -not- appear to be atomic. | |
62 | ||
63 | This is almost always the best approach. | |
64 | ||
65 | b. Carefully order the updates and the reads so that | |
66 | readers see valid data at all phases of the update. | |
67 | This is often more difficult than it sounds, especially | |
68 | given modern CPUs' tendency to reorder memory references. | |
69 | One must usually liberally sprinkle memory barriers | |
70 | (smp_wmb(), smp_rmb(), smp_mb()) through the code, | |
71 | making it difficult to understand and to test. | |
72 | ||
73 | It is usually better to group the changing data into | |
74 | a separate structure, so that the change may be made | |
75 | to appear atomic by updating a pointer to reference | |
76 | a new structure containing updated values. | |
77 | ||
78 | 4. Weakly ordered CPUs pose special challenges. Almost all CPUs | |
79 | are weakly ordered -- even i386 CPUs allow reads to be reordered. | |
80 | RCU code must take all of the following measures to prevent | |
81 | memory-corruption problems: | |
82 | ||
83 | a. Readers must maintain proper ordering of their memory | |
84 | accesses. The rcu_dereference() primitive ensures that | |
85 | the CPU picks up the pointer before it picks up the data | |
86 | that the pointer points to. This really is necessary | |
87 | on Alpha CPUs. If you don't believe me, see: | |
88 | ||
89 | http://www.openvms.compaq.com/wizard/wiz_2637.html | |
90 | ||
91 | The rcu_dereference() primitive is also an excellent | |
92 | documentation aid, letting the person reading the code | |
93 | know exactly which pointers are protected by RCU. | |
94 | ||
95 | The rcu_dereference() primitive is used by the various | |
96 | "_rcu()" list-traversal primitives, such as the | |
dd81eca8 PM |
97 | list_for_each_entry_rcu(). Note that it is perfectly |
98 | legal (if redundant) for update-side code to use | |
99 | rcu_dereference() and the "_rcu()" list-traversal | |
100 | primitives. This is particularly useful in code | |
101 | that is common to readers and updaters. | |
1da177e4 | 102 | |
a83f1fe2 PM |
103 | b. If the list macros are being used, the list_add_tail_rcu() |
104 | and list_add_rcu() primitives must be used in order | |
105 | to prevent weakly ordered machines from misordering | |
106 | structure initialization and pointer planting. | |
1da177e4 | 107 | Similarly, if the hlist macros are being used, the |
a83f1fe2 | 108 | hlist_add_head_rcu() primitive is required. |
1da177e4 | 109 | |
a83f1fe2 PM |
110 | c. If the list macros are being used, the list_del_rcu() |
111 | primitive must be used to keep list_del()'s pointer | |
112 | poisoning from inflicting toxic effects on concurrent | |
113 | readers. Similarly, if the hlist macros are being used, | |
114 | the hlist_del_rcu() primitive is required. | |
115 | ||
116 | The list_replace_rcu() primitive may be used to | |
117 | replace an old structure with a new one in an | |
118 | RCU-protected list. | |
119 | ||
120 | d. Updates must ensure that initialization of a given | |
1da177e4 LT |
121 | structure happens before pointers to that structure are |
122 | publicized. Use the rcu_assign_pointer() primitive | |
123 | when publicizing a pointer to a structure that can | |
124 | be traversed by an RCU read-side critical section. | |
125 | ||
1da177e4 LT |
126 | 5. If call_rcu(), or a related primitive such as call_rcu_bh(), |
127 | is used, the callback function must be written to be called | |
128 | from softirq context. In particular, it cannot block. | |
129 | ||
a83f1fe2 | 130 | 6. Since synchronize_rcu() can block, it cannot be called from |
1da177e4 LT |
131 | any sort of irq context. |
132 | ||
133 | 7. If the updater uses call_rcu(), then the corresponding readers | |
134 | must use rcu_read_lock() and rcu_read_unlock(). If the updater | |
135 | uses call_rcu_bh(), then the corresponding readers must use | |
136 | rcu_read_lock_bh() and rcu_read_unlock_bh(). Mixing things up | |
137 | will result in confusion and broken kernels. | |
138 | ||
139 | One exception to this rule: rcu_read_lock() and rcu_read_unlock() | |
140 | may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() | |
141 | in cases where local bottom halves are already known to be | |
142 | disabled, for example, in irq or softirq context. Commenting | |
143 | such cases is a must, of course! And the jury is still out on | |
144 | whether the increased speed is worth it. | |
145 | ||
a83f1fe2 | 146 | 8. Although synchronize_rcu() is a bit slower than is call_rcu(), |
1da177e4 | 147 | it usually results in simpler code. So, unless update performance |
a83f1fe2 | 148 | is important or the updaters cannot block, synchronize_rcu() |
1da177e4 LT |
149 | should be used in preference to call_rcu(). |
150 | ||
151 | 9. All RCU list-traversal primitives, which include | |
152 | list_for_each_rcu(), list_for_each_entry_rcu(), | |
153 | list_for_each_continue_rcu(), and list_for_each_safe_rcu(), | |
154 | must be within an RCU read-side critical section. RCU | |
155 | read-side critical sections are delimited by rcu_read_lock() | |
156 | and rcu_read_unlock(), or by similar primitives such as | |
157 | rcu_read_lock_bh() and rcu_read_unlock_bh(). | |
158 | ||
159 | Use of the _rcu() list-traversal primitives outside of an | |
160 | RCU read-side critical section causes no harm other than | |
dd81eca8 PM |
161 | a slight performance degradation on Alpha CPUs. It can |
162 | also be quite helpful in reducing code bloat when common | |
163 | code is shared between readers and updaters. | |
1da177e4 LT |
164 | |
165 | 10. Conversely, if you are in an RCU read-side critical section, | |
166 | you -must- use the "_rcu()" variants of the list macros. | |
167 | Failing to do so will break Alpha and confuse people reading | |
168 | your code. | |
a83f1fe2 PM |
169 | |
170 | 11. Note that synchronize_rcu() -only- guarantees to wait until | |
171 | all currently executing rcu_read_lock()-protected RCU read-side | |
172 | critical sections complete. It does -not- necessarily guarantee | |
173 | that all currently running interrupts, NMIs, preempt_disable() | |
174 | code, or idle loops will complete. Therefore, if you do not have | |
175 | rcu_read_lock()-protected read-side critical sections, do -not- | |
176 | use synchronize_rcu(). | |
177 | ||
178 | If you want to wait for some of these other things, you might | |
179 | instead need to use synchronize_irq() or synchronize_sched(). |