Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | RCU on Uniprocessor Systems |
2 | ||
3 | ||
4 | A common misconception is that, on UP systems, the call_rcu() primitive | |
a83f1fe2 | 5 | may immediately invoke its function, and that the synchronize_rcu() |
1da177e4 LT |
6 | primitive may return immediately. The basis of this misconception |
7 | is that since there is only one CPU, it should not be necessary to | |
8 | wait for anything else to get done, since there are no other CPUs for | |
a83f1fe2 | 9 | anything else to be happening on. Although this approach will -sort- -of- |
1da177e4 | 10 | work a surprising amount of the time, it is a very bad idea in general. |
dd81eca8 | 11 | This document presents three examples that demonstrate exactly how bad an |
1da177e4 LT |
12 | idea this is. |
13 | ||
14 | ||
15 | Example 1: softirq Suicide | |
16 | ||
17 | Suppose that an RCU-based algorithm scans a linked list containing | |
18 | elements A, B, and C in process context, and can delete elements from | |
19 | this same list in softirq context. Suppose that the process-context scan | |
20 | is referencing element B when it is interrupted by softirq processing, | |
21 | which deletes element B, and then invokes call_rcu() to free element B | |
22 | after a grace period. | |
23 | ||
24 | Now, if call_rcu() were to directly invoke its arguments, then upon return | |
25 | from softirq, the list scan would find itself referencing a newly freed | |
26 | element B. This situation can greatly decrease the life expectancy of | |
27 | your kernel. | |
28 | ||
dd81eca8 PM |
29 | This same problem can occur if call_rcu() is invoked from a hardware |
30 | interrupt handler. | |
31 | ||
1da177e4 LT |
32 | |
33 | Example 2: Function-Call Fatality | |
34 | ||
35 | Of course, one could avert the suicide described in the preceding example | |
36 | by having call_rcu() directly invoke its arguments only if it was called | |
37 | from process context. However, this can fail in a similar manner. | |
38 | ||
39 | Suppose that an RCU-based algorithm again scans a linked list containing | |
40 | elements A, B, and C in process contexts, but that it invokes a function | |
41 | on each element as it is scanned. Suppose further that this function | |
42 | deletes element B from the list, then passes it to call_rcu() for deferred | |
43 | freeing. This may be a bit unconventional, but it is perfectly legal | |
44 | RCU usage, since call_rcu() must wait for a grace period to elapse. | |
45 | Therefore, in this case, allowing call_rcu() to immediately invoke | |
46 | its arguments would cause it to fail to make the fundamental guarantee | |
47 | underlying RCU, namely that call_rcu() defers invoking its arguments until | |
48 | all RCU read-side critical sections currently executing have completed. | |
49 | ||
dd81eca8 PM |
50 | Quick Quiz #1: why is it -not- legal to invoke synchronize_rcu() in |
51 | this case? | |
52 | ||
53 | ||
54 | Example 3: Death by Deadlock | |
55 | ||
56 | Suppose that call_rcu() is invoked while holding a lock, and that the | |
57 | callback function must acquire this same lock. In this case, if | |
58 | call_rcu() were to directly invoke the callback, the result would | |
59 | be self-deadlock. | |
60 | ||
61 | In some cases, it would possible to restructure to code so that | |
62 | the call_rcu() is delayed until after the lock is released. However, | |
63 | there are cases where this can be quite ugly: | |
64 | ||
65 | 1. If a number of items need to be passed to call_rcu() within | |
66 | the same critical section, then the code would need to create | |
67 | a list of them, then traverse the list once the lock was | |
68 | released. | |
69 | ||
70 | 2. In some cases, the lock will be held across some kernel API, | |
71 | so that delaying the call_rcu() until the lock is released | |
72 | requires that the data item be passed up via a common API. | |
73 | It is far better to guarantee that callbacks are invoked | |
74 | with no locks held than to have to modify such APIs to allow | |
75 | arbitrary data items to be passed back up through them. | |
76 | ||
77 | If call_rcu() directly invokes the callback, painful locking restrictions | |
78 | or API changes would be required. | |
79 | ||
80 | Quick Quiz #2: What locking restriction must RCU callbacks respect? | |
1da177e4 LT |
81 | |
82 | ||
83 | Summary | |
84 | ||
85 | Permitting call_rcu() to immediately invoke its arguments or permitting | |
a83f1fe2 | 86 | synchronize_rcu() to immediately return breaks RCU, even on a UP system. |
1da177e4 | 87 | So do not do it! Even on a UP system, the RCU infrastructure -must- |
dd81eca8 PM |
88 | respect grace periods, and -must- invoke callbacks from a known environment |
89 | in which no locks are held. | |
90 | ||
91 | ||
92 | Answer to Quick Quiz #1: | |
93 | Why is it -not- legal to invoke synchronize_rcu() in this case? | |
94 | ||
95 | Because the calling function is scanning an RCU-protected linked | |
96 | list, and is therefore within an RCU read-side critical section. | |
97 | Therefore, the called function has been invoked within an RCU | |
98 | read-side critical section, and is not permitted to block. | |
99 | ||
100 | Answer to Quick Quiz #2: | |
101 | What locking restriction must RCU callbacks respect? | |
102 | ||
103 | Any lock that is acquired within an RCU callback must be | |
104 | acquired elsewhere using an _irq variant of the spinlock | |
105 | primitive. For example, if "mylock" is acquired by an | |
106 | RCU callback, then a process-context acquisition of this | |
107 | lock must use something like spin_lock_irqsave() to | |
108 | acquire the lock. | |
109 | ||
110 | If the process-context code were to simply use spin_lock(), | |
111 | then, since RCU callbacks can be invoked from softirq context, | |
112 | the callback might be called from a softirq that interrupted | |
113 | the process-context critical section. This would result in | |
114 | self-deadlock. | |
115 | ||
116 | This restriction might seem gratuitous, since very few RCU | |
117 | callbacks acquire locks directly. However, a great many RCU | |
118 | callbacks do acquire locks -indirectly-, for example, via | |
119 | the kfree() primitive. |