diff options
Diffstat (limited to 'Documentation/RCU/whatisRCU.rst')
-rw-r--r-- | Documentation/RCU/whatisRCU.rst | 141 |
1 files changed, 113 insertions, 28 deletions
diff --git a/Documentation/RCU/whatisRCU.rst b/Documentation/RCU/whatisRCU.rst index 17e95ab2a201..1c747ac3f2c8 100644 --- a/Documentation/RCU/whatisRCU.rst +++ b/Documentation/RCU/whatisRCU.rst @@ -6,13 +6,15 @@ What is RCU? -- "Read, Copy, Update" Please note that the "What is RCU?" LWN series is an excellent place to start learning about RCU: -| 1. What is RCU, Fundamentally? http://lwn.net/Articles/262464/ -| 2. What is RCU? Part 2: Usage http://lwn.net/Articles/263130/ -| 3. RCU part 3: the RCU API http://lwn.net/Articles/264090/ -| 4. The RCU API, 2010 Edition http://lwn.net/Articles/418853/ -| 2010 Big API Table http://lwn.net/Articles/419086/ -| 5. The RCU API, 2014 Edition http://lwn.net/Articles/609904/ -| 2014 Big API Table http://lwn.net/Articles/609973/ +| 1. What is RCU, Fundamentally? https://lwn.net/Articles/262464/ +| 2. What is RCU? Part 2: Usage https://lwn.net/Articles/263130/ +| 3. RCU part 3: the RCU API https://lwn.net/Articles/264090/ +| 4. The RCU API, 2010 Edition https://lwn.net/Articles/418853/ +| 2010 Big API Table https://lwn.net/Articles/419086/ +| 5. The RCU API, 2014 Edition https://lwn.net/Articles/609904/ +| 2014 Big API Table https://lwn.net/Articles/609973/ +| 6. The RCU API, 2019 Edition https://lwn.net/Articles/777036/ +| 2019 Big API Table https://lwn.net/Articles/777165/ What is RCU? @@ -39,9 +41,11 @@ different paths, as follows: :ref:`6. ANALOGY WITH READER-WRITER LOCKING <6_whatisRCU>` -:ref:`7. FULL LIST OF RCU APIs <7_whatisRCU>` +:ref:`7. ANALOGY WITH REFERENCE COUNTING <7_whatisRCU>` -:ref:`8. ANSWERS TO QUICK QUIZZES <8_whatisRCU>` +:ref:`8. FULL LIST OF RCU APIs <8_whatisRCU>` + +:ref:`9. ANSWERS TO QUICK QUIZZES <9_whatisRCU>` People who prefer starting with a conceptual overview should focus on Section 1, though most readers will profit by reading this section at @@ -222,7 +226,7 @@ synchronize_rcu() be delayed. This property results in system resilience in face of denial-of-service attacks. Code using call_rcu() should limit update rate in order to gain this same sort of resilience. See - checklist.txt for some approaches to limiting the update rate. + checklist.rst for some approaches to limiting the update rate. rcu_assign_pointer() ^^^^^^^^^^^^^^^^^^^^ @@ -316,7 +320,7 @@ rcu_dereference() must prohibit. The rcu_dereference_protected() variant takes a lockdep expression to indicate which locks must be acquired by the caller. If the indicated protection is not provided, - a lockdep splat is emitted. See Documentation/RCU/Design/Requirements/Requirements.rst + a lockdep splat is emitted. See Design/Requirements/Requirements.rst and the API's code comments for more details and example usage. .. [2] If the list_for_each_entry_rcu() instance might be used by @@ -397,8 +401,7 @@ for specialized uses, but are relatively uncommon. This section shows a simple use of the core RCU API to protect a global pointer to a dynamically allocated structure. More-typical -uses of RCU may be found in :ref:`listRCU.rst <list_rcu_doc>`, -:ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst <NMI_rcu_doc>`. +uses of RCU may be found in listRCU.rst, arrayRCU.rst, and NMI-RCU.rst. :: struct foo { @@ -480,10 +483,9 @@ So, to sum up: RCU read-side critical sections that might be referencing that data item. -See checklist.txt for additional rules to follow when using RCU. -And again, more-typical uses of RCU may be found in :ref:`listRCU.rst -<list_rcu_doc>`, :ref:`arrayRCU.rst <array_rcu_doc>`, and :ref:`NMI-RCU.rst -<NMI_rcu_doc>`. +See checklist.rst for additional rules to follow when using RCU. +And again, more-typical uses of RCU may be found in listRCU.rst, +arrayRCU.rst, and NMI-RCU.rst. .. _4_whatisRCU: @@ -577,7 +579,7 @@ to avoid having to write your own callback:: kfree_rcu(old_fp, rcu); -Again, see checklist.txt for additional rules governing the use of RCU. +Again, see checklist.rst for additional rules governing the use of RCU. .. _5_whatisRCU: @@ -661,7 +663,7 @@ been able to write-acquire the lock otherwise. The smp_mb__after_spinlock() promotes synchronize_rcu() to a full memory barrier in compliance with the "Memory-Barrier Guarantees" listed in: - Documentation/RCU/Design/Requirements/Requirements.rst + Design/Requirements/Requirements.rst It is possible to nest rcu_read_lock(), since reader-writer locks may be recursively acquired. Note also that rcu_read_lock() is immune @@ -677,7 +679,7 @@ Quick Quiz #1: occur when using this algorithm in a real-world Linux kernel? How could this deadlock be avoided? -:ref:`Answers to Quick Quiz <8_whatisRCU>` +:ref:`Answers to Quick Quiz <9_whatisRCU>` 5B. "TOY" EXAMPLE #2: CLASSIC RCU ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ @@ -732,7 +734,7 @@ Quick Quiz #2: Give an example where Classic RCU's read-side overhead is **negative**. -:ref:`Answers to Quick Quiz <8_whatisRCU>` +:ref:`Answers to Quick Quiz <9_whatisRCU>` .. _quiz_3: @@ -741,7 +743,7 @@ Quick Quiz #3: critical section, what the heck do you do in CONFIG_PREEMPT_RT, where normal spinlocks can block??? -:ref:`Answers to Quick Quiz <8_whatisRCU>` +:ref:`Answers to Quick Quiz <9_whatisRCU>` .. _6_whatisRCU: @@ -872,7 +874,84 @@ be used in place of synchronize_rcu(). .. _7_whatisRCU: -7. FULL LIST OF RCU APIs +7. ANALOGY WITH REFERENCE COUNTING +----------------------------------- + +The reader-writer analogy (illustrated by the previous section) is not +always the best way to think about using RCU. Another helpful analogy +considers RCU an effective reference count on everything which is +protected by RCU. + +A reference count typically does not prevent the referenced object's +values from changing, but does prevent changes to type -- particularly the +gross change of type that happens when that object's memory is freed and +re-allocated for some other purpose. Once a type-safe reference to the +object is obtained, some other mechanism is needed to ensure consistent +access to the data in the object. This could involve taking a spinlock, +but with RCU the typical approach is to perform reads with SMP-aware +operations such as smp_load_acquire(), to perform updates with atomic +read-modify-write operations, and to provide the necessary ordering. +RCU provides a number of support functions that embed the required +operations and ordering, such as the list_for_each_entry_rcu() macro +used in the previous section. + +A more focused view of the reference counting behavior is that, +between rcu_read_lock() and rcu_read_unlock(), any reference taken with +rcu_dereference() on a pointer marked as ``__rcu`` can be treated as +though a reference-count on that object has been temporarily increased. +This prevents the object from changing type. Exactly what this means +will depend on normal expectations of objects of that type, but it +typically includes that spinlocks can still be safely locked, normal +reference counters can be safely manipulated, and ``__rcu`` pointers +can be safely dereferenced. + +Some operations that one might expect to see on an object for +which an RCU reference is held include: + + - Copying out data that is guaranteed to be stable by the object's type. + - Using kref_get_unless_zero() or similar to get a longer-term + reference. This may fail of course. + - Acquiring a spinlock in the object, and checking if the object still + is the expected object and if so, manipulating it freely. + +The understanding that RCU provides a reference that only prevents a +change of type is particularly visible with objects allocated from a +slab cache marked ``SLAB_TYPESAFE_BY_RCU``. RCU operations may yield a +reference to an object from such a cache that has been concurrently freed +and the memory reallocated to a completely different object, though of +the same type. In this case RCU doesn't even protect the identity of the +object from changing, only its type. So the object found may not be the +one expected, but it will be one where it is safe to take a reference +(and then potentially acquiring a spinlock), allowing subsequent code +to check whether the identity matches expectations. It is tempting +to simply acquire the spinlock without first taking the reference, but +unfortunately any spinlock in a ``SLAB_TYPESAFE_BY_RCU`` object must be +initialized after each and every call to kmem_cache_alloc(), which renders +reference-free spinlock acquisition completely unsafe. Therefore, when +using ``SLAB_TYPESAFE_BY_RCU``, make proper use of a reference counter. + +With traditional reference counting -- such as that implemented by the +kref library in Linux -- there is typically code that runs when the last +reference to an object is dropped. With kref, this is the function +passed to kref_put(). When RCU is being used, such finalization code +must not be run until all ``__rcu`` pointers referencing the object have +been updated, and then a grace period has passed. Every remaining +globally visible pointer to the object must be considered to be a +potential counted reference, and the finalization code is typically run +using call_rcu() only after all those pointers have been changed. + +To see how to choose between these two analogies -- of RCU as a +reader-writer lock and RCU as a reference counting system -- it is useful +to reflect on the scale of the thing being protected. The reader-writer +lock analogy looks at larger multi-part objects such as a linked list +and shows how RCU can facilitate concurrency while elements are added +to, and removed from, the list. The reference-count analogy looks at +the individual objects and looks at how they can be accessed safely +within whatever whole they are a part of. + +.. _8_whatisRCU: + +8. FULL LIST OF RCU APIs ------------------------- The RCU APIs are documented in docbook-format header comments in the @@ -985,14 +1064,20 @@ SRCU: Initialization/cleanup:: init_srcu_struct cleanup_srcu_struct -All: lockdep-checked RCU-protected pointer access:: +All: lockdep-checked RCU utility APIs:: - rcu_access_pointer - rcu_dereference_raw RCU_LOCKDEP_WARN rcu_sleep_check RCU_NONIDLE +All: Unchecked RCU-protected pointer access:: + + rcu_dereference_raw + +All: Unchecked RCU-protected pointer access with dereferencing prohibited:: + + rcu_access_pointer + See the comment headers in the source code (or the docbook generated from them) for more information. @@ -1035,9 +1120,9 @@ g. Otherwise, use RCU. Of course, this all assumes that you have determined that RCU is in fact the right tool for your job. -.. _8_whatisRCU: +.. _9_whatisRCU: -8. ANSWERS TO QUICK QUIZZES +9. ANSWERS TO QUICK QUIZZES ---------------------------- Quick Quiz #1: |