1f93a3e4eSJiunn Chang.. _up_doc: 2f93a3e4eSJiunn Chang 3f93a3e4eSJiunn ChangRCU on Uniprocessor Systems 4f93a3e4eSJiunn Chang=========================== 5f93a3e4eSJiunn Chang 6f93a3e4eSJiunn ChangA common misconception is that, on UP systems, the call_rcu() primitive 7f93a3e4eSJiunn Changmay immediately invoke its function. The basis of this misconception 8f93a3e4eSJiunn Changis that since there is only one CPU, it should not be necessary to 9f93a3e4eSJiunn Changwait for anything else to get done, since there are no other CPUs for 10f93a3e4eSJiunn Changanything else to be happening on. Although this approach will *sort of* 11f93a3e4eSJiunn Changwork a surprising amount of the time, it is a very bad idea in general. 12f93a3e4eSJiunn ChangThis document presents three examples that demonstrate exactly how bad 13f93a3e4eSJiunn Changan idea this is. 14f93a3e4eSJiunn Chang 15f93a3e4eSJiunn ChangExample 1: softirq Suicide 16f93a3e4eSJiunn Chang-------------------------- 17f93a3e4eSJiunn Chang 18f93a3e4eSJiunn ChangSuppose that an RCU-based algorithm scans a linked list containing 19f93a3e4eSJiunn Changelements A, B, and C in process context, and can delete elements from 20f93a3e4eSJiunn Changthis same list in softirq context. Suppose that the process-context scan 21f93a3e4eSJiunn Changis referencing element B when it is interrupted by softirq processing, 22f93a3e4eSJiunn Changwhich deletes element B, and then invokes call_rcu() to free element B 23f93a3e4eSJiunn Changafter a grace period. 24f93a3e4eSJiunn Chang 25f93a3e4eSJiunn ChangNow, if call_rcu() were to directly invoke its arguments, then upon return 26f93a3e4eSJiunn Changfrom softirq, the list scan would find itself referencing a newly freed 27f93a3e4eSJiunn Changelement B. This situation can greatly decrease the life expectancy of 28f93a3e4eSJiunn Changyour kernel. 29f93a3e4eSJiunn Chang 30f93a3e4eSJiunn ChangThis same problem can occur if call_rcu() is invoked from a hardware 31f93a3e4eSJiunn Changinterrupt handler. 32f93a3e4eSJiunn Chang 33f93a3e4eSJiunn ChangExample 2: Function-Call Fatality 34f93a3e4eSJiunn Chang--------------------------------- 35f93a3e4eSJiunn Chang 36f93a3e4eSJiunn ChangOf course, one could avert the suicide described in the preceding example 37f93a3e4eSJiunn Changby having call_rcu() directly invoke its arguments only if it was called 38f93a3e4eSJiunn Changfrom process context. However, this can fail in a similar manner. 39f93a3e4eSJiunn Chang 40f93a3e4eSJiunn ChangSuppose that an RCU-based algorithm again scans a linked list containing 41c8f2310eSPaul E. McKenneyelements A, B, and C in process context, but that it invokes a function 42f93a3e4eSJiunn Changon each element as it is scanned. Suppose further that this function 43f93a3e4eSJiunn Changdeletes element B from the list, then passes it to call_rcu() for deferred 44f93a3e4eSJiunn Changfreeing. This may be a bit unconventional, but it is perfectly legal 45f93a3e4eSJiunn ChangRCU usage, since call_rcu() must wait for a grace period to elapse. 46f93a3e4eSJiunn ChangTherefore, in this case, allowing call_rcu() to immediately invoke 47f93a3e4eSJiunn Changits arguments would cause it to fail to make the fundamental guarantee 48f93a3e4eSJiunn Changunderlying RCU, namely that call_rcu() defers invoking its arguments until 49f93a3e4eSJiunn Changall RCU read-side critical sections currently executing have completed. 50f93a3e4eSJiunn Chang 51f93a3e4eSJiunn ChangQuick Quiz #1: 52f93a3e4eSJiunn Chang Why is it *not* legal to invoke synchronize_rcu() in this case? 53f93a3e4eSJiunn Chang 54f93a3e4eSJiunn Chang:ref:`Answers to Quick Quiz <answer_quick_quiz_up>` 55f93a3e4eSJiunn Chang 56f93a3e4eSJiunn ChangExample 3: Death by Deadlock 57f93a3e4eSJiunn Chang---------------------------- 58f93a3e4eSJiunn Chang 59f93a3e4eSJiunn ChangSuppose that call_rcu() is invoked while holding a lock, and that the 60f93a3e4eSJiunn Changcallback function must acquire this same lock. In this case, if 61f93a3e4eSJiunn Changcall_rcu() were to directly invoke the callback, the result would 62c8f2310eSPaul E. McKenneybe self-deadlock *even if* this invocation occurred from a later 63c8f2310eSPaul E. McKenneycall_rcu() invocation a full grace period later. 64f93a3e4eSJiunn Chang 65f93a3e4eSJiunn ChangIn some cases, it would possible to restructure to code so that 66f93a3e4eSJiunn Changthe call_rcu() is delayed until after the lock is released. However, 67f93a3e4eSJiunn Changthere are cases where this can be quite ugly: 68f93a3e4eSJiunn Chang 69f93a3e4eSJiunn Chang1. If a number of items need to be passed to call_rcu() within 70f93a3e4eSJiunn Chang the same critical section, then the code would need to create 71f93a3e4eSJiunn Chang a list of them, then traverse the list once the lock was 72f93a3e4eSJiunn Chang released. 73f93a3e4eSJiunn Chang 74f93a3e4eSJiunn Chang2. In some cases, the lock will be held across some kernel API, 75f93a3e4eSJiunn Chang so that delaying the call_rcu() until the lock is released 76f93a3e4eSJiunn Chang requires that the data item be passed up via a common API. 77f93a3e4eSJiunn Chang It is far better to guarantee that callbacks are invoked 78f93a3e4eSJiunn Chang with no locks held than to have to modify such APIs to allow 79f93a3e4eSJiunn Chang arbitrary data items to be passed back up through them. 80f93a3e4eSJiunn Chang 81f93a3e4eSJiunn ChangIf call_rcu() directly invokes the callback, painful locking restrictions 82f93a3e4eSJiunn Changor API changes would be required. 83f93a3e4eSJiunn Chang 84f93a3e4eSJiunn ChangQuick Quiz #2: 85f93a3e4eSJiunn Chang What locking restriction must RCU callbacks respect? 86f93a3e4eSJiunn Chang 87f93a3e4eSJiunn Chang:ref:`Answers to Quick Quiz <answer_quick_quiz_up>` 88f93a3e4eSJiunn Chang 89c8f2310eSPaul E. McKenneyIt is important to note that userspace RCU implementations *do* 90c8f2310eSPaul E. McKenneypermit call_rcu() to directly invoke callbacks, but only if a full 91c8f2310eSPaul E. McKenneygrace period has elapsed since those callbacks were queued. This is 92c8f2310eSPaul E. McKenneythe case because some userspace environments are extremely constrained. 93c8f2310eSPaul E. McKenneyNevertheless, people writing userspace RCU implementations are strongly 94c8f2310eSPaul E. McKenneyencouraged to avoid invoking callbacks from call_rcu(), thus obtaining 95c8f2310eSPaul E. McKenneythe deadlock-avoidance benefits called out above. 96c8f2310eSPaul E. McKenney 97f93a3e4eSJiunn ChangSummary 98f93a3e4eSJiunn Chang------- 99f93a3e4eSJiunn Chang 100f93a3e4eSJiunn ChangPermitting call_rcu() to immediately invoke its arguments breaks RCU, 101f93a3e4eSJiunn Changeven on a UP system. So do not do it! Even on a UP system, the RCU 102f93a3e4eSJiunn Changinfrastructure *must* respect grace periods, and *must* invoke callbacks 103f93a3e4eSJiunn Changfrom a known environment in which no locks are held. 104f93a3e4eSJiunn Chang 105f93a3e4eSJiunn ChangNote that it *is* safe for synchronize_rcu() to return immediately on 106f93a3e4eSJiunn ChangUP systems, including PREEMPT SMP builds running on UP systems. 107f93a3e4eSJiunn Chang 108f93a3e4eSJiunn ChangQuick Quiz #3: 109f93a3e4eSJiunn Chang Why can't synchronize_rcu() return immediately on UP systems running 110*c4af9e00SRandy Dunlap preemptible RCU? 111f93a3e4eSJiunn Chang 112f93a3e4eSJiunn Chang.. _answer_quick_quiz_up: 113f93a3e4eSJiunn Chang 114f93a3e4eSJiunn ChangAnswer to Quick Quiz #1: 115f93a3e4eSJiunn Chang Why is it *not* legal to invoke synchronize_rcu() in this case? 116f93a3e4eSJiunn Chang 117f93a3e4eSJiunn Chang Because the calling function is scanning an RCU-protected linked 118f93a3e4eSJiunn Chang list, and is therefore within an RCU read-side critical section. 119f93a3e4eSJiunn Chang Therefore, the called function has been invoked within an RCU 120f93a3e4eSJiunn Chang read-side critical section, and is not permitted to block. 121f93a3e4eSJiunn Chang 122f93a3e4eSJiunn ChangAnswer to Quick Quiz #2: 123f93a3e4eSJiunn Chang What locking restriction must RCU callbacks respect? 124f93a3e4eSJiunn Chang 125acb6258aSJiunn Chang Any lock that is acquired within an RCU callback must be acquired 126acb6258aSJiunn Chang elsewhere using an _bh variant of the spinlock primitive. 127acb6258aSJiunn Chang For example, if "mylock" is acquired by an RCU callback, then 128acb6258aSJiunn Chang a process-context acquisition of this lock must use something 129acb6258aSJiunn Chang like spin_lock_bh() to acquire the lock. Please note that 130acb6258aSJiunn Chang it is also OK to use _irq variants of spinlocks, for example, 131acb6258aSJiunn Chang spin_lock_irqsave(). 132f93a3e4eSJiunn Chang 133f93a3e4eSJiunn Chang If the process-context code were to simply use spin_lock(), 134f93a3e4eSJiunn Chang then, since RCU callbacks can be invoked from softirq context, 135f93a3e4eSJiunn Chang the callback might be called from a softirq that interrupted 136f93a3e4eSJiunn Chang the process-context critical section. This would result in 137f93a3e4eSJiunn Chang self-deadlock. 138f93a3e4eSJiunn Chang 139f93a3e4eSJiunn Chang This restriction might seem gratuitous, since very few RCU 140f93a3e4eSJiunn Chang callbacks acquire locks directly. However, a great many RCU 141f93a3e4eSJiunn Chang callbacks do acquire locks *indirectly*, for example, via 142f93a3e4eSJiunn Chang the kfree() primitive. 143f93a3e4eSJiunn Chang 144f93a3e4eSJiunn ChangAnswer to Quick Quiz #3: 145f93a3e4eSJiunn Chang Why can't synchronize_rcu() return immediately on UP systems 146*c4af9e00SRandy Dunlap running preemptible RCU? 147f93a3e4eSJiunn Chang 148f93a3e4eSJiunn Chang Because some other task might have been preempted in the middle 149f93a3e4eSJiunn Chang of an RCU read-side critical section. If synchronize_rcu() 150f93a3e4eSJiunn Chang simply immediately returned, it would prematurely signal the 151f93a3e4eSJiunn Chang end of the grace period, which would come as a nasty shock to 152f93a3e4eSJiunn Chang that other thread when it started running again. 153