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 context, 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 *even if* this invocation occurred from a later
 63call_rcu() invocation a full grace period later.
 64
 65In some cases, it would possible to restructure to code so that
 66the call_rcu() is delayed until after the lock is released.  However,
 67there are cases where this can be quite ugly:
 68
 691.	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
 742.	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
 81If call_rcu() directly invokes the callback, painful locking restrictions
 82or API changes would be required.
 83
 84Quick Quiz #2:
 85	What locking restriction must RCU callbacks respect?
 86
 87:ref:`Answers to Quick Quiz <answer_quick_quiz_up>`
 88
 89It is important to note that userspace RCU implementations *do*
 90permit call_rcu() to directly invoke callbacks, but only if a full
 91grace period has elapsed since those callbacks were queued.  This is
 92the case because some userspace environments are extremely constrained.
 93Nevertheless, people writing userspace RCU implementations are strongly
 94encouraged to avoid invoking callbacks from call_rcu(), thus obtaining
 95the deadlock-avoidance benefits called out above.
 96
 97Summary
 98-------
 99
100Permitting call_rcu() to immediately invoke its arguments breaks RCU,
101even on a UP system.  So do not do it!  Even on a UP system, the RCU
102infrastructure *must* respect grace periods, and *must* invoke callbacks
103from a known environment in which no locks are held.
104
105Note that it *is* safe for synchronize_rcu() to return immediately on
106UP systems, including PREEMPT SMP builds running on UP systems.
107
108Quick Quiz #3:
109	Why can't synchronize_rcu() return immediately on UP systems running
110	preemptible RCU?
111
112.. _answer_quick_quiz_up:
113
114Answer to Quick Quiz #1:
115	Why is it *not* legal to invoke synchronize_rcu() in this case?
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
122Answer to Quick Quiz #2:
123	What locking restriction must RCU callbacks respect?
124
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().
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
141	callbacks do acquire locks *indirectly*, for example, via
142	the kfree() primitive.
143
144Answer to Quick Quiz #3:
145	Why can't synchronize_rcu() return immediately on UP systems
146	running preemptible RCU?
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.