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 } |
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