tjh.dev
Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
kernel
os
linux
1RCU on Uniprocessor Systems
2
3
4A common misconception is that, on UP systems, the call_rcu() primitive
5may immediately invoke its function, and that the synchronize_rcu()
6primitive may return immediately. The basis of this misconception
7is that since there is only one CPU, it should not be necessary to
8wait for anything else to get done, since there are no other CPUs for
9anything else to be happening on. Although this approach will -sort- -of-
10work a surprising amount of the time, it is a very bad idea in general.
11This document presents three examples that demonstrate exactly how bad an
12idea this is.
13
14
15Example 1: softirq Suicide
16
17Suppose that an RCU-based algorithm scans a linked list containing
18elements A, B, and C in process context, and can delete elements from
19this same list in softirq context. Suppose that the process-context scan
20is referencing element B when it is interrupted by softirq processing,
21which deletes element B, and then invokes call_rcu() to free element B
22after a grace period.
23
24Now, if call_rcu() were to directly invoke its arguments, then upon return
25from softirq, the list scan would find itself referencing a newly freed
26element B. This situation can greatly decrease the life expectancy of
27your kernel.
28
29This same problem can occur if call_rcu() is invoked from a hardware
30interrupt handler.
31
32
33Example 2: Function-Call Fatality
34
35Of course, one could avert the suicide described in the preceding example
36by having call_rcu() directly invoke its arguments only if it was called
37from process context. However, this can fail in a similar manner.
38
39Suppose that an RCU-based algorithm again scans a linked list containing
40elements A, B, and C in process contexts, but that it invokes a function
41on each element as it is scanned. Suppose further that this function
42deletes element B from the list, then passes it to call_rcu() for deferred
43freeing. This may be a bit unconventional, but it is perfectly legal
44RCU usage, since call_rcu() must wait for a grace period to elapse.
45Therefore, in this case, allowing call_rcu() to immediately invoke
46its arguments would cause it to fail to make the fundamental guarantee
47underlying RCU, namely that call_rcu() defers invoking its arguments until
48all RCU read-side critical sections currently executing have completed.
49
50Quick Quiz #1: why is it -not- legal to invoke synchronize_rcu() in
51 this case?
52
53
54Example 3: Death by Deadlock
55
56Suppose that call_rcu() is invoked while holding a lock, and that the
57callback function must acquire this same lock. In this case, if
58call_rcu() were to directly invoke the callback, the result would
59be self-deadlock.
60
61In some cases, it would possible to restructure to code so that
62the call_rcu() is delayed until after the lock is released. However,
63there are cases where this can be quite ugly:
64
651. 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
702. 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
77If call_rcu() directly invokes the callback, painful locking restrictions
78or API changes would be required.
79
80Quick Quiz #2: What locking restriction must RCU callbacks respect?
81
82
83Summary
84
85Permitting call_rcu() to immediately invoke its arguments or permitting
86synchronize_rcu() to immediately return breaks RCU, even on a UP system.
87So do not do it! Even on a UP system, the RCU infrastructure -must-
88respect grace periods, and -must- invoke callbacks from a known environment
89in which no locks are held.
90
91
92Answer 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
100Answer 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.