UP.rst 5.8 KB

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