To start the replacement example,
here are the last few lines of the
example shown in
Figure :
1 q = kmalloc(sizeof(*p), GFP_KERNEL); 2 *q = *p; 3 q->b = 2; 4 q->c = 3; 5 list_replace_rcu(&p->list, &q->list); 6 synchronize_rcu(); 7 kfree(p); |
The initial state of the list, including the pointer p,
is the same as for the deletion example, as shown on the
first row of
Figure .
As before, the triples in each element represent the values of fields a, b, and c, respectively. The red-shaded elements might be referenced by readers, and because readers do not synchronize directly with updaters, readers might run concurrently with this entire replacement process. Please note that we again omit the backwards pointers and the link from the tail of the list to the head for clarity.
The following text describes how to replace the 5,6,7 element with 5,2,3 in such a way that any given reader sees one of these two values.
Line 1 kmalloc()s a replacement element, as follows,
resulting in the state as shown in the second row of
Figure .
At this point, no reader can hold a reference to the newly allocated
element (as indicated by its green shading), and it is uninitialized
(as indicated by the question marks).
Line 2 copies the old element to the new one, resulting in the
state as shown in the third row of
Figure .
The newly allocated element still cannot be referenced by readers, but
it is now initialized.
Line 3 updates q->b to the value ``2'', and
line 4 updates q->c to the value ``3'', as shown on the fourth row of
Figure .
Now, line 5 does the replacement, so that the new element is
finally visible to readers, and hence is shaded red, as shown on
the fifth row of
Figure .
At this point, as shown below, we have two versions of the list.
Pre-existing readers might see the 5,6,7 element (which is
therefore now shaded yellow), but
new readers will instead see the 5,2,3 element.
But any given reader is guaranteed to see some well-defined list.
After the synchronize_rcu() on line 6 returns,
a grace period will have elapsed, and so all reads that started before the
list_replace_rcu() will have completed.
In particular, any readers that might have been holding references
to the 5,6,7 element are guaranteed to have exited
their RCU read-side critical sections, and are thus prohibited from
continuing to hold a reference.
Therefore, there can no longer be any readers holding references
to the old element, as indicated its green shading in the sixth row of
Figure .
As far as the readers are concerned, we are back to having a single version
of the list, but with the new element in place of the old.
After the kfree() on line 7 completes, the list will
appear as shown on the final row of
Figure .
Despite the fact that RCU was named after the replacement case,
the vast majority of RCU usage within the Linux kernel relies on
the simple deletion case shown in
Section .
Paul E. McKenney 2011-12-16