Documentation/RCU/UP.txt

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