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