You are viewing paulmck

Previous Entry | Next Entry

Stupid RCU Tricks: RCU-Protected Deletion

RCU
Consider the following code fragment:

 

 

  1 rcu_read_lock();
  2 p = rcu_dereference(gp);
  3 if (must_delete(p)) {
  4   spin_lock(&my_lock);
  5   if (must_delete(p)) {
  6     kfree_rcu(p);
  7     rcu_assign_pointer(gp, q);
  8     already_deleted(p);
  9   }
 10   spin_unlock(&my_lock);
 11 } else {
 12   do_something_with(p);
 13 }
 14 rcu_read_unlock();

Note that the whole fragment is enclosed in an RCU read-side critical section. Line 2 picks up a local pointer to the global RCU-protected pointer gp, which we assume is never NULL. Line 3 checks to see if it is necessary to delete the structure referenced by gp, and, if so, lines 4-10 do the deleting. Otherwise, line 12 does something with the just-accessed structure.

If the structure must be deleted, we first acquire a spinlock on line 4, and then line 5 re-checks whether it is still necessary to delete the structure, but this time under the lock. If the structure still needs to be deleted, then line 6 frees it (but only after an RCU grace period has elapsed) and line 7 makes gp point to some replacement structure q. Clearly this replacement structure must have been allocated somehow, but the details of exactly how that happens are not important to this example. Next, line 8 marks the old structure as having already been deleted, which resolves races when multiple CPUs concurrently notice that the structure needs deleting, and is also the reason that line 5 rechecks under the lock. Finally, line 10 releases the spinlock.

This code fragment is a bit unconventional: Normally lines 6 and 7 would be interchanged. But the RCU read-side critical section will prevent the structure from being freed until after the global pointer is updated, right? Why or why not?

Comments

Alex Nikiforov
Mar. 20th, 2012 09:03 am (UTC)
maybe I'm late, but...
Hi, maybe I'm late with this topic, but I have a question.

I'm really sorry, but I dont quite understand answer on this quiz.
You wrote

The moral of this story: Always prevent readers from obtaining new references to the structure before starting the grace period. Always!

Is it means that at first one must hold spin_lock() and then rcu_dereference() bcoz rcu_dereference() will starts grace period or I miss something.

Edited at 2012-03-20 09:55 am (UTC)
paulmck
Mar. 31st, 2012 05:25 pm (UTC)
No read-side spinlocks, just careful updates
The moral is that lines 6 and 7 must be interchanged: You must always always always remove any read-side access to the data element that is to be deleted (the rcu_assign_pointer() statement on line 7) before starting the grace period (the kfree_rcu() on line 6). That way, any reader that acquires a reference to the data item is guaranteed to be waited on by the corresponding grace period.
Alex Nikiforov
Apr. 3rd, 2012 07:04 am (UTC)
Re: No read-side spinlocks, just careful updates
Thx Paul