10.3.1.3.2 Example 2: Maintaining Multiple Versions During Replacement

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);


Figure: RCU Replacement in Linked List
\resizebox{2.7in}{!}{\includegraphics{defer/RCUReplacement}}

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