Documentation/RCU/UP.rst

   1 .. _up_doc:
   2
   3 RCU on Uniprocessor Systems
   4 ===========================
   5
   6 A common misconception is that, on UP systems, the call_rcu() primitive
   7 may immediately invoke its function.  The basis of this misconception
   8 is that since there is only one CPU, it should not be necessary to
   9 wait for anything else to get done, since there are no other CPUs for
  10 anything else to be happening on.  Although this approach will *sort of*
  11 work a surprising amount of the time, it is a very bad idea in general.
  12 This document presents three examples that demonstrate exactly how bad
  13 an idea this is.
  14
  15 Example 1: softirq Suicide
  16 --------------------------
  17
  18 Suppose that an RCU-based algorithm scans a linked list containing
  19 elements A, B, and C in process context, and can delete elements from
  20 this same list in softirq context.  Suppose that the process-context scan
  21 is referencing element B when it is interrupted by softirq processing,
  22 which deletes element B, and then invokes call_rcu() to free element B
  23 after a grace period.
  24
  25 Now, if call_rcu() were to directly invoke its arguments, then upon return
  26 from softirq, the list scan would find itself referencing a newly freed
  27 element B.  This situation can greatly decrease the life expectancy of
  28 your kernel.
  29
  30 This same problem can occur if call_rcu() is invoked from a hardware
  31 interrupt handler.
  32
  33 Example 2: Function-Call Fatality
  34 ---------------------------------
  35
  36 Of course, one could avert the suicide described in the preceding example
  37 by having call_rcu() directly invoke its arguments only if it was called
  38 from process context.  However, this can fail in a similar manner.
  39
  40 Suppose that an RCU-based algorithm again scans a linked list containing
  41 elements A, B, and C in process context, but that it invokes a function
  42 on each element as it is scanned.  Suppose further that this function
  43 deletes element B from the list, then passes it to call_rcu() for deferred
  44 freeing.  This may be a bit unconventional, but it is perfectly legal
  45 RCU usage, since call_rcu() must wait for a grace period to elapse.
  46 Therefore, in this case, allowing call_rcu() to immediately invoke
  47 its arguments would cause it to fail to make the fundamental guarantee
  48 underlying RCU, namely that call_rcu() defers invoking its arguments until
  49 all RCU read-side critical sections currently executing have completed.
  50
  51 Quick 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
  56 Example 3: Death by Deadlock
  57 ----------------------------
  58
  59 Suppose that call_rcu() is invoked while holding a lock, and that the
  60 callback function must acquire this same lock.  In this case, if
  61 call_rcu() were to directly invoke the callback, the result would
  62 be self-deadlock *even if* this invocation occurred from a later
  63 call_rcu() invocation a full grace period later.
  64
  65 In some cases, it would possible to restructure to code so that
  66 the call_rcu() is delayed until after the lock is released.  However,
  67 there are cases where this can be quite ugly:
  68
  69 1.      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
  74 2.      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
  81 If call_rcu() directly invokes the callback, painful locking restrictions
  82 or API changes would be required.
  83
  84 Quick Quiz #2:
  85         What locking restriction must RCU callbacks respect?
  86
  87 :ref:`Answers to Quick Quiz <answer_quick_quiz_up>`
  88
  89 It is important to note that userspace RCU implementations *do*
  90 permit call_rcu() to directly invoke callbacks, but only if a full
  91 grace period has elapsed since those callbacks were queued.  This is
  92 the case because some userspace environments are extremely constrained.
  93 Nevertheless, people writing userspace RCU implementations are strongly
  94 encouraged to avoid invoking callbacks from call_rcu(), thus obtaining
  95 the deadlock-avoidance benefits called out above.
  96
  97 Summary
  98 -------
  99
 100 Permitting call_rcu() to immediately invoke its arguments breaks RCU,
 101 even on a UP system.  So do not do it!  Even on a UP system, the RCU
 102 infrastructure *must* respect grace periods, and *must* invoke callbacks
 103 from a known environment in which no locks are held.
 104
 105 Note that it *is* safe for synchronize_rcu() to return immediately on
 106 UP systems, including PREEMPT SMP builds running on UP systems.
 107
 108 Quick Quiz #3:
 109         Why can't synchronize_rcu() return immediately on UP systems running
 110         preemptible RCU?
 111
 112 .. _answer_quick_quiz_up:
 113
 114 Answer 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
 122 Answer 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
 144 Answer 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.