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