Commit | Line | Data |
---|---|---|
2a5b0c84 | 1 | .. _up_doc: |
1da177e4 | 2 | |
2a5b0c84 JC |
3 | RCU on Uniprocessor Systems |
4 | =========================== | |
1da177e4 LT |
5 | |
6 | A common misconception is that, on UP systems, the call_rcu() primitive | |
240ebbf8 | 7 | may immediately invoke its function. The basis of this misconception |
1da177e4 LT |
8 | is that since there is only one CPU, it should not be necessary to |
9 | wait for anything else to get done, since there are no other CPUs for | |
2a5b0c84 | 10 | anything else to be happening on. Although this approach will *sort of* |
1da177e4 | 11 | work a surprising amount of the time, it is a very bad idea in general. |
240ebbf8 PM |
12 | This document presents three examples that demonstrate exactly how bad |
13 | an idea this is. | |
1da177e4 | 14 | |
1da177e4 | 15 | Example 1: softirq Suicide |
2a5b0c84 | 16 | -------------------------- |
1da177e4 LT |
17 | |
18 | Suppose that an RCU-based algorithm scans a linked list containing | |
19 | elements A, B, and C in process context, and can delete elements from | |
20 | this same list in softirq context. Suppose that the process-context scan | |
21 | is referencing element B when it is interrupted by softirq processing, | |
22 | which deletes element B, and then invokes call_rcu() to free element B | |
23 | after a grace period. | |
24 | ||
25 | Now, if call_rcu() were to directly invoke its arguments, then upon return | |
26 | from softirq, the list scan would find itself referencing a newly freed | |
27 | element B. This situation can greatly decrease the life expectancy of | |
28 | your kernel. | |
29 | ||
dd81eca8 PM |
30 | This same problem can occur if call_rcu() is invoked from a hardware |
31 | interrupt handler. | |
32 | ||
1da177e4 | 33 | Example 2: Function-Call Fatality |
2a5b0c84 | 34 | --------------------------------- |
1da177e4 LT |
35 | |
36 | Of course, one could avert the suicide described in the preceding example | |
37 | by having call_rcu() directly invoke its arguments only if it was called | |
38 | from process context. However, this can fail in a similar manner. | |
39 | ||
40 | Suppose that an RCU-based algorithm again scans a linked list containing | |
c8f2310e | 41 | elements A, B, and C in process context, but that it invokes a function |
1da177e4 LT |
42 | on each element as it is scanned. Suppose further that this function |
43 | deletes element B from the list, then passes it to call_rcu() for deferred | |
44 | freeing. This may be a bit unconventional, but it is perfectly legal | |
45 | RCU usage, since call_rcu() must wait for a grace period to elapse. | |
46 | Therefore, in this case, allowing call_rcu() to immediately invoke | |
47 | its arguments would cause it to fail to make the fundamental guarantee | |
48 | underlying RCU, namely that call_rcu() defers invoking its arguments until | |
49 | all RCU read-side critical sections currently executing have completed. | |
50 | ||
2a5b0c84 JC |
51 | Quick Quiz #1: |
52 | Why is it *not* legal to invoke synchronize_rcu() in this case? | |
dd81eca8 | 53 | |
2a5b0c84 | 54 | :ref:`Answers to Quick Quiz <answer_quick_quiz_up>` |
dd81eca8 PM |
55 | |
56 | Example 3: Death by Deadlock | |
2a5b0c84 | 57 | ---------------------------- |
dd81eca8 PM |
58 | |
59 | Suppose that call_rcu() is invoked while holding a lock, and that the | |
60 | callback function must acquire this same lock. In this case, if | |
61 | call_rcu() were to directly invoke the callback, the result would | |
c8f2310e PM |
62 | be self-deadlock *even if* this invocation occurred from a later |
63 | call_rcu() invocation a full grace period later. | |
dd81eca8 PM |
64 | |
65 | In some cases, it would possible to restructure to code so that | |
66 | the call_rcu() is delayed until after the lock is released. However, | |
67 | there are cases where this can be quite ugly: | |
68 | ||
69 | 1. If a number of items need to be passed to call_rcu() within | |
70 | the same critical section, then the code would need to create | |
71 | a list of them, then traverse the list once the lock was | |
72 | released. | |
73 | ||
74 | 2. In some cases, the lock will be held across some kernel API, | |
75 | so that delaying the call_rcu() until the lock is released | |
76 | requires that the data item be passed up via a common API. | |
77 | It is far better to guarantee that callbacks are invoked | |
78 | with no locks held than to have to modify such APIs to allow | |
79 | arbitrary data items to be passed back up through them. | |
80 | ||
81 | If call_rcu() directly invokes the callback, painful locking restrictions | |
82 | or API changes would be required. | |
83 | ||
2a5b0c84 JC |
84 | Quick Quiz #2: |
85 | What locking restriction must RCU callbacks respect? | |
1da177e4 | 86 | |
2a5b0c84 | 87 | :ref:`Answers to Quick Quiz <answer_quick_quiz_up>` |
1da177e4 | 88 | |
c8f2310e PM |
89 | It is important to note that userspace RCU implementations *do* |
90 | permit call_rcu() to directly invoke callbacks, but only if a full | |
91 | grace period has elapsed since those callbacks were queued. This is | |
92 | the case because some userspace environments are extremely constrained. | |
93 | Nevertheless, people writing userspace RCU implementations are strongly | |
94 | encouraged to avoid invoking callbacks from call_rcu(), thus obtaining | |
95 | the deadlock-avoidance benefits called out above. | |
96 | ||
1da177e4 | 97 | Summary |
2a5b0c84 | 98 | ------- |
1da177e4 | 99 | |
240ebbf8 PM |
100 | Permitting call_rcu() to immediately invoke its arguments breaks RCU, |
101 | even on a UP system. So do not do it! Even on a UP system, the RCU | |
2a5b0c84 | 102 | infrastructure *must* respect grace periods, and *must* invoke callbacks |
240ebbf8 PM |
103 | from a known environment in which no locks are held. |
104 | ||
2a5b0c84 JC |
105 | Note that it *is* safe for synchronize_rcu() to return immediately on |
106 | UP systems, including PREEMPT SMP builds running on UP systems. | |
240ebbf8 | 107 | |
2a5b0c84 JC |
108 | Quick Quiz #3: |
109 | Why can't synchronize_rcu() return immediately on UP systems running | |
c4af9e00 | 110 | preemptible RCU? |
dd81eca8 | 111 | |
2a5b0c84 | 112 | .. _answer_quick_quiz_up: |
dd81eca8 PM |
113 | |
114 | Answer to Quick Quiz #1: | |
2a5b0c84 | 115 | Why is it *not* legal to invoke synchronize_rcu() in this case? |
dd81eca8 PM |
116 | |
117 | Because the calling function is scanning an RCU-protected linked | |
118 | list, and is therefore within an RCU read-side critical section. | |
119 | Therefore, the called function has been invoked within an RCU | |
120 | read-side critical section, and is not permitted to block. | |
121 | ||
122 | Answer to Quick Quiz #2: | |
123 | What locking restriction must RCU callbacks respect? | |
124 | ||
acb6258a JC |
125 | Any lock that is acquired within an RCU callback must be acquired |
126 | elsewhere using an _bh variant of the spinlock primitive. | |
127 | For example, if "mylock" is acquired by an RCU callback, then | |
128 | a process-context acquisition of this lock must use something | |
129 | like spin_lock_bh() to acquire the lock. Please note that | |
130 | it is also OK to use _irq variants of spinlocks, for example, | |
131 | spin_lock_irqsave(). | |
dd81eca8 PM |
132 | |
133 | If the process-context code were to simply use spin_lock(), | |
134 | then, since RCU callbacks can be invoked from softirq context, | |
135 | the callback might be called from a softirq that interrupted | |
136 | the process-context critical section. This would result in | |
137 | self-deadlock. | |
138 | ||
139 | This restriction might seem gratuitous, since very few RCU | |
140 | callbacks acquire locks directly. However, a great many RCU | |
2a5b0c84 | 141 | callbacks do acquire locks *indirectly*, for example, via |
dd81eca8 | 142 | the kfree() primitive. |
240ebbf8 PM |
143 | |
144 | Answer to Quick Quiz #3: | |
145 | Why can't synchronize_rcu() return immediately on UP systems | |
c4af9e00 | 146 | running preemptible RCU? |
240ebbf8 PM |
147 | |
148 | Because some other task might have been preempted in the middle | |
149 | of an RCU read-side critical section. If synchronize_rcu() | |
150 | simply immediately returned, it would prematurely signal the | |
151 | end of the grace period, which would come as a nasty shock to | |
152 | that other thread when it started running again. |