You are viewing paulmck

Previous Entry | Next Entry

RCU
Al Viro came up with an example similar to this gem, where A and B are both initially zero:

CPU 0CPU 1
rcu_read_lock();
B = 1;
r1 = A;
rcu_read_unlock();   
A = 1;
synchronize_rcu();
r2 = B;


Al's question is whether the outcome r1 == 0 && r2 == 0 is possible after both code fragments complete and all the dust settles.

To answer this question, we will use the fundamental property of RCU, which guarantees that an RCU read-side critical section cannot span a grace period. In the above example, the RCU read-side critical section is the code between rcu_read_lock() and rcu_read_unlock(), and the RCU grace period is provide by synchronize_rcu(). It turns out that this rather weak guarantee is actually quite powerful, as we will see in this example.

Now we know that if r1 == 0, then CPU 0's load from A must have preceded CPU 1's store to A, and thus also have preceded the grace period provided by synchronize_rcu(). Then RCU guarantees that CPU 0's store to B also preceded that same grace period. Because CPU 1's load from B follows the grace period, it must see the results of CPU 0's store, which means that if r1 == 0 we know that r2 == 1. Therefore, RCU prohibits Al's outcome of r1 == 0 && r2 == 0, as Linus Torvalds surmised.

You can also start by assuming that r2 == 0, but this is left as an exercise for the reader.

Let us instead proceed to a more elaborate example:

CPU 0CPU 1CPU 2CPU 3
rcu_read_lock();
r1 = A;
r2 = B;
rcu_read_unlock();    
r3 = B;
synchronize_rcu();    
r4 = A;
A = 1;    B = 1;


Is the result r1 == 1 && r2 == 0 && r3 == 1 && r4 == 0 possible? Why or why not?

Comments