rcu: Remove list_for_each_continue_rcu()
[linux-3.10.git] / Documentation / RCU / whatisRCU.txt
index 5ed85af..9d30de0 100644 (file)
@@ -1,3 +1,12 @@
+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/
+
+
 What is RCU?
 
 RCU is a synchronization mechanism that was added to the Linux kernel
@@ -128,10 +137,10 @@ rcu_read_lock()
        Used by a reader to inform the reclaimer that the reader is
        entering an RCU read-side critical section.  It is illegal
        to block while in an RCU read-side critical section, though
-       kernels built with CONFIG_PREEMPT_RCU can preempt RCU read-side
-       critical sections.  Any RCU-protected data structure accessed
-       during an RCU read-side critical section is guaranteed to remain
-       unreclaimed for the full duration of that critical section.
+       kernels built with CONFIG_TREE_PREEMPT_RCU can preempt RCU
+       read-side critical sections.  Any RCU-protected data structure
+       accessed during an RCU read-side critical section is guaranteed to
+       remain unreclaimed for the full duration of that critical section.
        Reference counts may be used in conjunction with RCU to maintain
        longer-term references to data structures.
 
@@ -184,7 +193,17 @@ synchronize_rcu()
        blocking, it registers a function and argument which are invoked
        after all ongoing RCU read-side critical sections have completed.
        This callback variant is particularly useful in situations where
-       it is illegal to block.
+       it is illegal to block or where update-side performance is
+       critically important.
+
+       However, the call_rcu() API should not be used lightly, as use
+       of the synchronize_rcu() API generally results in simpler code.
+       In addition, the synchronize_rcu() API has the nice property
+       of automatically limiting update rate should grace periods
+       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.
 
 rcu_assign_pointer()
 
@@ -305,14 +324,17 @@ used as follows:
        Defer                   Protect
 
 a.     synchronize_rcu()       rcu_read_lock() / rcu_read_unlock()
-       call_rcu()
+       call_rcu()              rcu_dereference()
 
 b.     call_rcu_bh()           rcu_read_lock_bh() / rcu_read_unlock_bh()
+                               rcu_dereference_bh()
 
-c.     synchronize_sched()     preempt_disable() / preempt_enable()
+c.     synchronize_sched()     rcu_read_lock_sched() / rcu_read_unlock_sched()
+                               preempt_disable() / preempt_enable()
                                local_irq_save() / local_irq_restore()
                                hardirq enter / hardirq exit
                                NMI enter / NMI exit
+                               rcu_dereference_sched()
 
 These three mechanisms are used as follows:
 
@@ -360,7 +382,7 @@ uses of RCU may be found in listRCU.txt, arrayRCU.txt, and NMI-RCU.txt.
                struct foo *new_fp;
                struct foo *old_fp;
 
-               new_fp = kmalloc(sizeof(*fp), GFP_KERNEL);
+               new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
                spin_lock(&foo_mutex);
                old_fp = gbl_foo;
                *new_fp = *old_fp;
@@ -461,7 +483,7 @@ The foo_update_a() function might then be written as follows:
                struct foo *new_fp;
                struct foo *old_fp;
 
-               new_fp = kmalloc(sizeof(*fp), GFP_KERNEL);
+               new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
                spin_lock(&foo_mutex);
                old_fp = gbl_foo;
                *new_fp = *old_fp;
@@ -572,7 +594,7 @@ The rcu_read_lock() and rcu_read_unlock() primitive read-acquire
 and release a global reader-writer lock.  The synchronize_rcu()
 primitive write-acquires this same lock, then immediately releases
 it.  This means that once synchronize_rcu() exits, all RCU read-side
-critical sections that were in progress before synchonize_rcu() was
+critical sections that were in progress before synchronize_rcu() was
 called are guaranteed to have completed -- there is no way that
 synchronize_rcu() would have been able to write-acquire the lock
 otherwise.
@@ -605,7 +627,7 @@ are the same as those shown in the preceding section, so they are omitted.
        {
                int cpu;
 
-               for_each_cpu(cpu)
+               for_each_possible_cpu(cpu)
                        run_on(cpu);
        }
 
@@ -677,8 +699,9 @@ diff shows how closely related RCU and reader-writer locking can be.
        +       spin_lock(&listmutex);
                list_for_each_entry(p, head, lp) {
                        if (p->key == key) {
-                               list_del(&p->list);
+       -                       list_del(&p->list);
        -                       write_unlock(&listmutex);
+       +                       list_del_rcu(&p->list);
        +                       spin_unlock(&listmutex);
        +                       synchronize_rcu();
                                kfree(p);
@@ -726,7 +749,7 @@ Or, for those who prefer a side-by-side listing:
  5   write_lock(&listmutex);            5   spin_lock(&listmutex);
  6   list_for_each_entry(p, head, lp) { 6   list_for_each_entry(p, head, lp) {
  7     if (p->key == key) {             7     if (p->key == key) {
- 8       list_del(&p->list);            8       list_del(&p->list);
+ 8       list_del(&p->list);            8       list_del_rcu(&p->list);
  9       write_unlock(&listmutex);      9       spin_unlock(&listmutex);
                                        10       synchronize_rcu();
 10       kfree(p);                     11       kfree(p);
@@ -739,7 +762,7 @@ Or, for those who prefer a side-by-side listing:
 
 Either way, the differences are quite small.  Read-side locking moves
 to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
-from a reader-writer lock to a simple spinlock, and a synchronize_rcu()
+a reader-writer lock to a simple spinlock, and a synchronize_rcu()
 precedes the kfree().
 
 However, there is one potential catch: the read-side and update-side
@@ -761,24 +784,14 @@ Linux-kernel source code, but it helps to have a full list of the
 APIs, since there does not appear to be a way to categorize them
 in docbook.  Here is the list, by category.
 
-Markers for RCU read-side critical sections:
-
-       rcu_read_lock
-       rcu_read_unlock
-       rcu_read_lock_bh
-       rcu_read_unlock_bh
+RCU list traversal:
 
-RCU pointer/list traversal:
-
-       rcu_dereference
-       list_for_each_rcu               (to be deprecated in favor of
-                                        list_for_each_entry_rcu)
        list_for_each_entry_rcu
-       list_for_each_continue_rcu      (to be deprecated in favor of new
-                                        list_for_each_entry_continue_rcu)
        hlist_for_each_entry_rcu
+       hlist_nulls_for_each_entry_rcu
+       list_for_each_entry_continue_rcu
 
-RCU pointer update:
+RCU pointer/list update:
 
        rcu_assign_pointer
        list_add_rcu
@@ -786,20 +799,99 @@ RCU pointer update:
        list_del_rcu
        list_replace_rcu
        hlist_del_rcu
+       hlist_add_after_rcu
+       hlist_add_before_rcu
        hlist_add_head_rcu
+       hlist_replace_rcu
+       list_splice_init_rcu()
+
+RCU:   Critical sections       Grace period            Barrier
+
+       rcu_read_lock           synchronize_net         rcu_barrier
+       rcu_read_unlock         synchronize_rcu
+       rcu_dereference         synchronize_rcu_expedited
+                               call_rcu
+
+
+bh:    Critical sections       Grace period            Barrier
+
+       rcu_read_lock_bh        call_rcu_bh             rcu_barrier_bh
+       rcu_read_unlock_bh      synchronize_rcu_bh
+       rcu_dereference_bh      synchronize_rcu_bh_expedited
+
+
+sched: Critical sections       Grace period            Barrier
+
+       rcu_read_lock_sched     synchronize_sched       rcu_barrier_sched
+       rcu_read_unlock_sched   call_rcu_sched
+       [preempt_disable]       synchronize_sched_expedited
+       [and friends]
+       rcu_dereference_sched
+
 
-RCU grace period:
+SRCU:  Critical sections       Grace period            Barrier
 
-       synchronize_kernel (deprecated)
-       synchronize_net
-       synchronize_sched
-       synchronize_rcu
-       call_rcu
-       call_rcu_bh
+       srcu_read_lock          synchronize_srcu        srcu_barrier
+       srcu_read_unlock        call_srcu
+       srcu_read_lock_raw      synchronize_srcu_expedited
+       srcu_read_unlock_raw
+       srcu_dereference
+
+SRCU:  Initialization/cleanup
+       init_srcu_struct
+       cleanup_srcu_struct
+
+All:  lockdep-checked RCU-protected pointer access
+
+       rcu_dereference_check
+       rcu_dereference_protected
+       rcu_access_pointer
 
 See the comment headers in the source code (or the docbook generated
 from them) for more information.
 
+However, given that there are no fewer than four families of RCU APIs
+in the Linux kernel, how do you choose which one to use?  The following
+list can be helpful:
+
+a.     Will readers need to block?  If so, you need SRCU.
+
+b.     Is it necessary to start a read-side critical section in a
+       hardirq handler or exception handler, and then to complete
+       this read-side critical section in the task that was
+       interrupted?  If so, you need SRCU's srcu_read_lock_raw() and
+       srcu_read_unlock_raw() primitives.
+
+c.     What about the -rt patchset?  If readers would need to block
+       in an non-rt kernel, you need SRCU.  If readers would block
+       in a -rt kernel, but not in a non-rt kernel, SRCU is not
+       necessary.
+
+d.     Do you need to treat NMI handlers, hardirq handlers,
+       and code segments with preemption disabled (whether
+       via preempt_disable(), local_irq_save(), local_bh_disable(),
+       or some other mechanism) as if they were explicit RCU readers?
+       If so, RCU-sched is the only choice that will work for you.
+
+e.     Do you need RCU grace periods to complete even in the face
+       of softirq monopolization of one or more of the CPUs?  For
+       example, is your code subject to network-based denial-of-service
+       attacks?  If so, you need RCU-bh.
+
+f.     Is your workload too update-intensive for normal use of
+       RCU, but inappropriate for other synchronization mechanisms?
+       If so, consider SLAB_DESTROY_BY_RCU.  But please be careful!
+
+g.     Do you need read-side critical sections that are respected
+       even though they are in the middle of the idle loop, during
+       user-mode execution, or on an offlined CPU?  If so, SRCU is the
+       only choice that will work for you.
+
+h.     Otherwise, use RCU.
+
+Of course, this all assumes that you have determined that RCU is in fact
+the right tool for your job.
+
 
 8.  ANSWERS TO QUICK QUIZZES