Contents of /alx-src/trunk/kernel26-alx/linux/Documentation/RCU/checklist.txt
Parent Directory | Revision Log
Revision 628 -
(show annotations)
(download)
Wed Mar 4 10:48:58 2009 UTC (15 years, 1 month ago) by niro
File MIME type: text/plain
File size: 7953 byte(s)
Wed Mar 4 10:48:58 2009 UTC (15 years, 1 month ago) by niro
File MIME type: text/plain
File size: 7953 byte(s)
import linux sources based on 2.6.12-alx-r9: -using linux-2.6.12.6 -using 2.6.12-ck6 patch set -using fbsplash-0.9.2-r3 -using vesafb-tng-0.9-rc7 -using squashfs-2.2 -added cddvd-cmdfilter-drop.patch as ck dropped it -added via-epia-dri (cle266) patch -added zd1211-svn-32 wlan driver (http://zd1211.ath.cx/download/) -added debian patches to zd1211 for wep256 etc
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 |
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). |
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 | |
46 | 3. Does the update code tolerate concurrent accesses? |
47 | |
48 | The whole point of RCU is to permit readers to run without |
49 | any locks or atomic operations. This means that readers will |
50 | be running while updates are in progress. There are a number |
51 | of ways to handle this concurrency, depending on the situation: |
52 | |
53 | a. Make updates appear atomic to readers. For example, |
54 | pointer updates to properly aligned fields will appear |
55 | atomic, as will individual atomic primitives. Operations |
56 | performed under a lock and sequences of multiple atomic |
57 | primitives will -not- appear to be atomic. |
58 | |
59 | This is almost always the best approach. |
60 | |
61 | b. Carefully order the updates and the reads so that |
62 | readers see valid data at all phases of the update. |
63 | This is often more difficult than it sounds, especially |
64 | given modern CPUs' tendency to reorder memory references. |
65 | One must usually liberally sprinkle memory barriers |
66 | (smp_wmb(), smp_rmb(), smp_mb()) through the code, |
67 | making it difficult to understand and to test. |
68 | |
69 | It is usually better to group the changing data into |
70 | a separate structure, so that the change may be made |
71 | to appear atomic by updating a pointer to reference |
72 | a new structure containing updated values. |
73 | |
74 | 4. Weakly ordered CPUs pose special challenges. Almost all CPUs |
75 | are weakly ordered -- even i386 CPUs allow reads to be reordered. |
76 | RCU code must take all of the following measures to prevent |
77 | memory-corruption problems: |
78 | |
79 | a. Readers must maintain proper ordering of their memory |
80 | accesses. The rcu_dereference() primitive ensures that |
81 | the CPU picks up the pointer before it picks up the data |
82 | that the pointer points to. This really is necessary |
83 | on Alpha CPUs. If you don't believe me, see: |
84 | |
85 | http://www.openvms.compaq.com/wizard/wiz_2637.html |
86 | |
87 | The rcu_dereference() primitive is also an excellent |
88 | documentation aid, letting the person reading the code |
89 | know exactly which pointers are protected by RCU. |
90 | |
91 | The rcu_dereference() primitive is used by the various |
92 | "_rcu()" list-traversal primitives, such as the |
93 | list_for_each_entry_rcu(). |
94 | |
95 | b. If the list macros are being used, the list_add_tail_rcu() |
96 | and list_add_rcu() primitives must be used in order |
97 | to prevent weakly ordered machines from misordering |
98 | structure initialization and pointer planting. |
99 | Similarly, if the hlist macros are being used, the |
100 | hlist_add_head_rcu() primitive is required. |
101 | |
102 | c. If the list macros are being used, the list_del_rcu() |
103 | primitive must be used to keep list_del()'s pointer |
104 | poisoning from inflicting toxic effects on concurrent |
105 | readers. Similarly, if the hlist macros are being used, |
106 | the hlist_del_rcu() primitive is required. |
107 | |
108 | The list_replace_rcu() primitive may be used to |
109 | replace an old structure with a new one in an |
110 | RCU-protected list. |
111 | |
112 | d. Updates must ensure that initialization of a given |
113 | structure happens before pointers to that structure are |
114 | publicized. Use the rcu_assign_pointer() primitive |
115 | when publicizing a pointer to a structure that can |
116 | be traversed by an RCU read-side critical section. |
117 | |
118 | 5. If call_rcu(), or a related primitive such as call_rcu_bh(), |
119 | is used, the callback function must be written to be called |
120 | from softirq context. In particular, it cannot block. |
121 | |
122 | 6. Since synchronize_rcu() can block, it cannot be called from |
123 | any sort of irq context. |
124 | |
125 | 7. If the updater uses call_rcu(), then the corresponding readers |
126 | must use rcu_read_lock() and rcu_read_unlock(). If the updater |
127 | uses call_rcu_bh(), then the corresponding readers must use |
128 | rcu_read_lock_bh() and rcu_read_unlock_bh(). Mixing things up |
129 | will result in confusion and broken kernels. |
130 | |
131 | One exception to this rule: rcu_read_lock() and rcu_read_unlock() |
132 | may be substituted for rcu_read_lock_bh() and rcu_read_unlock_bh() |
133 | in cases where local bottom halves are already known to be |
134 | disabled, for example, in irq or softirq context. Commenting |
135 | such cases is a must, of course! And the jury is still out on |
136 | whether the increased speed is worth it. |
137 | |
138 | 8. Although synchronize_rcu() is a bit slower than is call_rcu(), |
139 | it usually results in simpler code. So, unless update performance |
140 | is important or the updaters cannot block, synchronize_rcu() |
141 | should be used in preference to call_rcu(). |
142 | |
143 | 9. All RCU list-traversal primitives, which include |
144 | list_for_each_rcu(), list_for_each_entry_rcu(), |
145 | list_for_each_continue_rcu(), and list_for_each_safe_rcu(), |
146 | must be within an RCU read-side critical section. RCU |
147 | read-side critical sections are delimited by rcu_read_lock() |
148 | and rcu_read_unlock(), or by similar primitives such as |
149 | rcu_read_lock_bh() and rcu_read_unlock_bh(). |
150 | |
151 | Use of the _rcu() list-traversal primitives outside of an |
152 | RCU read-side critical section causes no harm other than |
153 | a slight performance degradation on Alpha CPUs and some |
154 | confusion on the part of people trying to read the code. |
155 | |
156 | Another way of thinking of this is "If you are holding the |
157 | lock that prevents the data structure from changing, why do |
158 | you also need RCU-based protection?" That said, there may |
159 | well be situations where use of the _rcu() list-traversal |
160 | primitives while the update-side lock is held results in |
161 | simpler and more maintainable code. The jury is still out |
162 | on this question. |
163 | |
164 | 10. Conversely, if you are in an RCU read-side critical section, |
165 | you -must- use the "_rcu()" variants of the list macros. |
166 | Failing to do so will break Alpha and confuse people reading |
167 | your code. |
168 | |
169 | 11. Note that synchronize_rcu() -only- guarantees to wait until |
170 | all currently executing rcu_read_lock()-protected RCU read-side |
171 | critical sections complete. It does -not- necessarily guarantee |
172 | that all currently running interrupts, NMIs, preempt_disable() |
173 | code, or idle loops will complete. Therefore, if you do not have |
174 | rcu_read_lock()-protected read-side critical sections, do -not- |
175 | use synchronize_rcu(). |
176 | |
177 | If you want to wait for some of these other things, you might |
178 | instead need to use synchronize_irq() or synchronize_sched(). |