153 lines · plain
1.. _up_doc:2 3RCU on Uniprocessor Systems4===========================5 6A common misconception is that, on UP systems, the call_rcu() primitive7may immediately invoke its function. The basis of this misconception8is that since there is only one CPU, it should not be necessary to9wait for anything else to get done, since there are no other CPUs for10anything 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 bad13an idea this is.14 15Example 1: softirq Suicide16--------------------------17 18Suppose that an RCU-based algorithm scans a linked list containing19elements A, B, and C in process context, and can delete elements from20this same list in softirq context. Suppose that the process-context scan21is referencing element B when it is interrupted by softirq processing,22which deletes element B, and then invokes call_rcu() to free element B23after a grace period.24 25Now, if call_rcu() were to directly invoke its arguments, then upon return26from softirq, the list scan would find itself referencing a newly freed27element B. This situation can greatly decrease the life expectancy of28your kernel.29 30This same problem can occur if call_rcu() is invoked from a hardware31interrupt handler.32 33Example 2: Function-Call Fatality34---------------------------------35 36Of course, one could avert the suicide described in the preceding example37by having call_rcu() directly invoke its arguments only if it was called38from process context. However, this can fail in a similar manner.39 40Suppose that an RCU-based algorithm again scans a linked list containing41elements A, B, and C in process context, but that it invokes a function42on each element as it is scanned. Suppose further that this function43deletes element B from the list, then passes it to call_rcu() for deferred44freeing. This may be a bit unconventional, but it is perfectly legal45RCU usage, since call_rcu() must wait for a grace period to elapse.46Therefore, in this case, allowing call_rcu() to immediately invoke47its arguments would cause it to fail to make the fundamental guarantee48underlying RCU, namely that call_rcu() defers invoking its arguments until49all 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 Deadlock57----------------------------58 59Suppose that call_rcu() is invoked while holding a lock, and that the60callback function must acquire this same lock. In this case, if61call_rcu() were to directly invoke the callback, the result would62be self-deadlock *even if* this invocation occurred from a later63call_rcu() invocation a full grace period later.64 65In some cases, it would possible to restructure to code so that66the 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() within70 the same critical section, then the code would need to create71 a list of them, then traverse the list once the lock was72 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 released76 requires that the data item be passed up via a common API.77 It is far better to guarantee that callbacks are invoked78 with no locks held than to have to modify such APIs to allow79 arbitrary data items to be passed back up through them.80 81If call_rcu() directly invokes the callback, painful locking restrictions82or 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 full91grace period has elapsed since those callbacks were queued. This is92the case because some userspace environments are extremely constrained.93Nevertheless, people writing userspace RCU implementations are strongly94encouraged to avoid invoking callbacks from call_rcu(), thus obtaining95the deadlock-avoidance benefits called out above.96 97Summary98-------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 RCU102infrastructure *must* respect grace periods, and *must* invoke callbacks103from a known environment in which no locks are held.104 105Note that it *is* safe for synchronize_rcu() to return immediately on106UP systems, including PREEMPT SMP builds running on UP systems.107 108Quick Quiz #3:109 Why can't synchronize_rcu() return immediately on UP systems running110 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 linked118 list, and is therefore within an RCU read-side critical section.119 Therefore, the called function has been invoked within an RCU120 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 acquired126 elsewhere using an _bh variant of the spinlock primitive.127 For example, if "mylock" is acquired by an RCU callback, then128 a process-context acquisition of this lock must use something129 like spin_lock_bh() to acquire the lock. Please note that130 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 interrupted136 the process-context critical section. This would result in137 self-deadlock.138 139 This restriction might seem gratuitous, since very few RCU140 callbacks acquire locks directly. However, a great many RCU141 callbacks do acquire locks *indirectly*, for example, via142 the kfree() primitive.143 144Answer to Quick Quiz #3:145 Why can't synchronize_rcu() return immediately on UP systems146 running preemptible RCU?147 148 Because some other task might have been preempted in the middle149 of an RCU read-side critical section. If synchronize_rcu()150 simply immediately returned, it would prematurely signal the151 end of the grace period, which would come as a nasty shock to152 that other thread when it started running again.153