10.3.2.5 RCU is a Way of Providing Existence Guarantees

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: Existence Guarantees Enable Per-Element Locking
\begin{figure}{ \scriptsize
\begin{verbatim}1 int delete(int key)
2 {
3 str...
...>lock);
23 rcu_read_unlock();
24 return 0;
25 }\end{verbatim}
}\end{figure}

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