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 context, 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 *even if* this invocation occurred from a later
63 call_rcu() invocation a full grace period late 63 call_rcu() invocation a full grace period later.
64 64
65 In some cases, it would possible to restructur 65 In some cases, it would possible to restructure to code so that
66 the call_rcu() is delayed until after the lock 66 the call_rcu() is delayed until after the lock is released. However,
67 there are cases where this can be quite ugly: 67 there are cases where this can be quite ugly:
68 68
69 1. If a number of items need to be passed 69 1. If a number of items need to be passed to call_rcu() within
70 the same critical section, then the co 70 the same critical section, then the code would need to create
71 a list of them, then traverse the list 71 a list of them, then traverse the list once the lock was
72 released. 72 released.
73 73
74 2. In some cases, the lock will be held a 74 2. In some cases, the lock will be held across some kernel API,
75 so that delaying the call_rcu() until 75 so that delaying the call_rcu() until the lock is released
76 requires that the data item be passed 76 requires that the data item be passed up via a common API.
77 It is far better to guarantee that cal 77 It is far better to guarantee that callbacks are invoked
78 with no locks held than to have to mod 78 with no locks held than to have to modify such APIs to allow
79 arbitrary data items to be passed back 79 arbitrary data items to be passed back up through them.
80 80
81 If call_rcu() directly invokes the callback, p 81 If call_rcu() directly invokes the callback, painful locking restrictions
82 or API changes would be required. 82 or API changes would be required.
83 83
84 Quick Quiz #2: 84 Quick Quiz #2:
85 What locking restriction must RCU call 85 What locking restriction must RCU callbacks respect?
86 86
87 :ref:`Answers to Quick Quiz <answer_quick_quiz 87 :ref:`Answers to Quick Quiz <answer_quick_quiz_up>`
88 88
89 It is important to note that userspace RCU imp 89 It is important to note that userspace RCU implementations *do*
90 permit call_rcu() to directly invoke callbacks 90 permit call_rcu() to directly invoke callbacks, but only if a full
91 grace period has elapsed since those callbacks 91 grace period has elapsed since those callbacks were queued. This is
92 the case because some userspace environments a 92 the case because some userspace environments are extremely constrained.
93 Nevertheless, people writing userspace RCU imp 93 Nevertheless, people writing userspace RCU implementations are strongly
94 encouraged to avoid invoking callbacks from ca 94 encouraged to avoid invoking callbacks from call_rcu(), thus obtaining
95 the deadlock-avoidance benefits called out abo 95 the deadlock-avoidance benefits called out above.
96 96
97 Summary 97 Summary
98 ------- 98 -------
99 99
100 Permitting call_rcu() to immediately invoke it 100 Permitting call_rcu() to immediately invoke its arguments breaks RCU,
101 even on a UP system. So do not do it! Even o 101 even on a UP system. So do not do it! Even on a UP system, the RCU
102 infrastructure *must* respect grace periods, a 102 infrastructure *must* respect grace periods, and *must* invoke callbacks
103 from a known environment in which no locks are 103 from a known environment in which no locks are held.
104 104
105 Note that it *is* safe for synchronize_rcu() t 105 Note that it *is* safe for synchronize_rcu() to return immediately on
106 UP systems, including PREEMPT SMP builds runni 106 UP systems, including PREEMPT SMP builds running on UP systems.
107 107
108 Quick Quiz #3: 108 Quick Quiz #3:
109 Why can't synchronize_rcu() return imm 109 Why can't synchronize_rcu() return immediately on UP systems running
110 preemptible RCU? !! 110 preemptable RCU?
111 111
112 .. _answer_quick_quiz_up: 112 .. _answer_quick_quiz_up:
113 113
114 Answer to Quick Quiz #1: 114 Answer to Quick Quiz #1:
115 Why is it *not* legal to invoke synchr 115 Why is it *not* legal to invoke synchronize_rcu() in this case?
116 116
117 Because the calling function is scanni 117 Because the calling function is scanning an RCU-protected linked
118 list, and is therefore within an RCU r 118 list, and is therefore within an RCU read-side critical section.
119 Therefore, the called function has bee 119 Therefore, the called function has been invoked within an RCU
120 read-side critical section, and is not 120 read-side critical section, and is not permitted to block.
121 121
122 Answer to Quick Quiz #2: 122 Answer to Quick Quiz #2:
123 What locking restriction must RCU call 123 What locking restriction must RCU callbacks respect?
124 124
125 Any lock that is acquired within an RC 125 Any lock that is acquired within an RCU callback must be acquired
126 elsewhere using an _bh variant of the 126 elsewhere using an _bh variant of the spinlock primitive.
127 For example, if "mylock" is acquired b 127 For example, if "mylock" is acquired by an RCU callback, then
128 a process-context acquisition of this 128 a process-context acquisition of this lock must use something
129 like spin_lock_bh() to acquire the loc 129 like spin_lock_bh() to acquire the lock. Please note that
130 it is also OK to use _irq variants of 130 it is also OK to use _irq variants of spinlocks, for example,
131 spin_lock_irqsave(). 131 spin_lock_irqsave().
132 132
133 If the process-context code were to si 133 If the process-context code were to simply use spin_lock(),
134 then, since RCU callbacks can be invok 134 then, since RCU callbacks can be invoked from softirq context,
135 the callback might be called from a so 135 the callback might be called from a softirq that interrupted
136 the process-context critical section. 136 the process-context critical section. This would result in
137 self-deadlock. 137 self-deadlock.
138 138
139 This restriction might seem gratuitous 139 This restriction might seem gratuitous, since very few RCU
140 callbacks acquire locks directly. How 140 callbacks acquire locks directly. However, a great many RCU
141 callbacks do acquire locks *indirectly 141 callbacks do acquire locks *indirectly*, for example, via
142 the kfree() primitive. 142 the kfree() primitive.
143 143
144 Answer to Quick Quiz #3: 144 Answer to Quick Quiz #3:
145 Why can't synchronize_rcu() return imm 145 Why can't synchronize_rcu() return immediately on UP systems
146 running preemptible RCU? !! 146 running preemptable RCU?
147 147
148 Because some other task might have bee 148 Because some other task might have been preempted in the middle
149 of an RCU read-side critical section. 149 of an RCU read-side critical section. If synchronize_rcu()
150 simply immediately returned, it would 150 simply immediately returned, it would prematurely signal the
151 end of the grace period, which would c 151 end of the grace period, which would come as a nasty shock to
152 that other thread when it started runn 152 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.