Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | RCU Concepts |
2 | ||
3 | ||
4 | The basic idea behind RCU (read-copy update) is to split destructive | |
5 | operations into two parts, one that prevents anyone from seeing the data | |
6 | item being destroyed, and one that actually carries out the destruction. | |
7 | A "grace period" must elapse between the two parts, and this grace period | |
8 | must be long enough that any readers accessing the item being deleted have | |
9 | since dropped their references. For example, an RCU-protected deletion | |
10 | from a linked list would first remove the item from the list, wait for | |
11 | a grace period to elapse, then free the element. See the listRCU.txt | |
12 | file for more information on using RCU with linked lists. | |
13 | ||
14 | ||
15 | Frequently Asked Questions | |
16 | ||
17 | o Why would anyone want to use RCU? | |
18 | ||
19 | The advantage of RCU's two-part approach is that RCU readers need | |
20 | not acquire any locks, perform any atomic instructions, write to | |
21 | shared memory, or (on CPUs other than Alpha) execute any memory | |
22 | barriers. The fact that these operations are quite expensive | |
23 | on modern CPUs is what gives RCU its performance advantages | |
24 | in read-mostly situations. The fact that RCU readers need not | |
25 | acquire locks can also greatly simplify deadlock-avoidance code. | |
26 | ||
27 | o How can the updater tell when a grace period has completed | |
28 | if the RCU readers give no indication when they are done? | |
29 | ||
30 | Just as with spinlocks, RCU readers are not permitted to | |
31 | block, switch to user-mode execution, or enter the idle loop. | |
32 | Therefore, as soon as a CPU is seen passing through any of these | |
33 | three states, we know that that CPU has exited any previous RCU | |
34 | read-side critical sections. So, if we remove an item from a | |
35 | linked list, and then wait until all CPUs have switched context, | |
36 | executed in user mode, or executed in the idle loop, we can | |
37 | safely free up that item. | |
38 | ||
f85d6c71 PM |
39 | Preemptible variants of RCU (CONFIG_PREEMPT_RCU) get the |
40 | same effect, but require that the readers manipulate CPU-local | |
41 | counters. These counters allow limited types of blocking | |
42 | within RCU read-side critical sections. SRCU also uses | |
43 | CPU-local counters, and permits general blocking within | |
44 | RCU read-side critical sections. These two variants of | |
45 | RCU detect grace periods by sampling these counters. | |
46 | ||
1da177e4 LT |
47 | o If I am running on a uniprocessor kernel, which can only do one |
48 | thing at a time, why should I wait for a grace period? | |
49 | ||
50 | See the UP.txt file in this directory. | |
51 | ||
52 | o How can I see where RCU is currently used in the Linux kernel? | |
53 | ||
a83f1fe2 PM |
54 | Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu", |
55 | "rcu_read_lock_bh", "rcu_read_unlock_bh", "call_rcu_bh", | |
621934ee | 56 | "srcu_read_lock", "srcu_read_unlock", "synchronize_rcu", |
f85d6c71 PM |
57 | "synchronize_net", "synchronize_srcu", and the other RCU |
58 | primitives. Or grab one of the cscope databases from: | |
59 | ||
60 | http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html | |
1da177e4 LT |
61 | |
62 | o What guidelines should I follow when writing code that uses RCU? | |
63 | ||
64 | See the checklist.txt file in this directory. | |
65 | ||
66 | o Why the name "RCU"? | |
67 | ||
68 | "RCU" stands for "read-copy update". The file listRCU.txt has | |
69 | more information on where this name came from, search for | |
70 | "read-copy update" to find it. | |
71 | ||
72 | o I hear that RCU is patented? What is with that? | |
73 | ||
74 | Yes, it is. There are several known patents related to RCU, | |
75 | search for the string "Patent" in RTFP.txt to find them. | |
76 | Of these, one was allowed to lapse by the assignee, and the | |
77 | others have been contributed to the Linux kernel under GPL. | |
78 | ||
dd81eca8 PM |
79 | o I hear that RCU needs work in order to support realtime kernels? |
80 | ||
f85d6c71 PM |
81 | This work is largely completed. Realtime-friendly RCU can be |
82 | enabled via the CONFIG_PREEMPT_RCU kernel configuration parameter. | |
83 | However, work is in progress for enabling priority boosting of | |
84 | preempted RCU read-side critical sections.This is needed if you | |
85 | have CPU-bound realtime threads. | |
dd81eca8 | 86 | |
1da177e4 LT |
87 | o Where can I find more information on RCU? |
88 | ||
89 | See the RTFP.txt file in this directory. | |
dd81eca8 PM |
90 | Or point your browser at http://www.rdrop.com/users/paulmck/RCU/. |
91 | ||
92 | o What are all these files in this directory? | |
93 | ||
94 | ||
95 | NMI-RCU.txt | |
96 | ||
97 | Describes how to use RCU to implement dynamic | |
98 | NMI handlers, which can be revectored on the fly, | |
99 | without rebooting. | |
100 | ||
101 | RTFP.txt | |
102 | ||
103 | List of RCU-related publications and web sites. | |
104 | ||
105 | UP.txt | |
106 | ||
107 | Discussion of RCU usage in UP kernels. | |
108 | ||
109 | arrayRCU.txt | |
110 | ||
111 | Describes how to use RCU to protect arrays, with | |
112 | resizeable arrays whose elements reference other | |
113 | data structures being of the most interest. | |
114 | ||
115 | checklist.txt | |
116 | ||
117 | Lists things to check for when inspecting code that | |
118 | uses RCU. | |
119 | ||
120 | listRCU.txt | |
121 | ||
122 | Describes how to use RCU to protect linked lists. | |
123 | This is the simplest and most common use of RCU | |
124 | in the Linux kernel. | |
125 | ||
126 | rcu.txt | |
127 | ||
128 | You are reading it! | |
129 | ||
d19720a9 PM |
130 | rcuref.txt |
131 | ||
132 | Describes how to combine use of reference counts | |
133 | with RCU. | |
134 | ||
dd81eca8 PM |
135 | whatisRCU.txt |
136 | ||
137 | Overview of how the RCU implementation works. Along | |
138 | the way, presents a conceptual view of RCU. |