10.3.1.3.1 Example 1: Maintaining Multiple Versions During Deletion

To start the ``deletion'' example, we will modify lines 11-21 in Figure [*] to read as follows:



  1 p = search(head, key);
  2 if (p != NULL) {
  3   list_del_rcu(&p->list);
  4   synchronize_rcu();
  5   kfree(p);
  6 }


Figure: RCU Deletion From Linked List
\resizebox{3in}{!}{\includegraphics{defer/RCUDeletion}}

This code will update the list as shown in Figure [*]. The triples in each element represent the values of fields a, b, and c, respectively. The red-shaded elements indicate that RCU readers might be holding references to them. Please note that we have omitted the backwards pointers and the link from the tail of the list to the head for clarity.

After the list_del_rcu() on line 3 has completed, the 5,6,7 element has been removed from the list, as shown in the second row of Figure [*]. Since readers do not synchronize directly with updaters, readers might be concurrently scanning this list. These concurrent readers might or might not see the newly removed element, depending on timing. However, readers that were delayed (e.g., due to interrupts, ECC memory errors, or, in CONFIG_PREEMPT_RT kernels, preemption) just after fetching a pointer to the newly removed element might see the old version of the list for quite some time after the removal. Therefore, we now have two versions of the list, one with element 5,6,7 and one without. The 5,6,7 element is shaded yellow, indicating that old readers might still be referencing it, but that new readers cannot obtain a reference to it.

Please note that readers are not permitted to maintain references to element 5,6,7 after exiting from their RCU read-side critical sections. Therefore, once the synchronize_rcu() on line 4 completes, so that all pre-existing readers are guaranteed to have completed, there can be no more readers referencing this element, as indicated by its green shading on the third row of Figure [*]. We are thus back to a single version of the list.

At this point, the 5,6,7 element may safely be freed, as shown on the final row of Figure [*]. At this point, we have completed the deletion of element 5,6,7. The following section covers replacement.

Paul E. McKenney 2011-12-16