Gamsa et al. [GKAS99]
discuss existence guarantees and describe how a mechanism
resembling RCU can be used to provide these existence guarantees
(see section 5 on page 7 of the PDF), and
Section
discusses how to guarantee existence via locking, along with the
ensuing disadvantages of doing so.
The effect is that if any RCU-protected data element is accessed
within an RCU read-side critical section, that data element is
guaranteed to remain in existence for the duration of that RCU
read-side critical section.
Figure
demonstrates how RCU-based existence guarantees can enable
per-element locking via a function that deletes an element from
a hash table.
Line 6 computes a hash function, and line 7 enters an RCU
read-side critical section.
If line 9 finds that the corresponding bucket of the hash table is
empty or that the element present is not the one we wish to delete,
then line 10 exits the RCU read-side critical section and line 11
indicates failure.
Quick Quiz 10.17:
What if the element we need to delete is not the first element
of the list on line 9 of
Figure ?
End Quick Quiz
Otherwise, line 13 acquires the update-side spinlock, and line 14 then checks that the element is still the one that we want. If so, line 15 leaves the RCU read-side critical section, line 16 removes it from the table, line 17 releases the lock, line 18 waits for all pre-existing RCU read-side critical sections to complete, line 19 frees the newly removed element, and line 20 indicates success. If the element is no longer the one we want, line 22 releases the lock, line 23 leaves the RCU read-side critical section, and line 24 indicates failure to delete the specified key.
Quick Quiz 10.18:
Why is it OK to exit the RCU read-side critical section on
line 15 of
Figure
before releasing the lock on line 17?
End Quick Quiz
Quick Quiz 10.19:
Why not exit the RCU read-side critical section on
line 23 of
Figure
before releasing the lock on line 22?
End Quick Quiz
Alert readers will recognize this as only a slight variation on
the original "RCU is a way of waiting for things to finish" theme,
which is addressed in
Section .
They might also note the deadlock-immunity advantages over the lock-based
existence guarantees discussed in
Section
.
Paul E. McKenney 2011-12-16