RCU on Uniprocessor Systems


A common misconception is that, on UP systems, the call_rcu() primitive
may immediately invoke its function, and that the synchronize_rcu()
primitive may return immediately.  The basis of this misconception
is that since there is only one CPU, it should not be necessary to
wait for anything else to get done, since there are no other CPUs for
anything else to be happening on.  Although this approach will -sort- -of-
work a surprising amount of the time, it is a very bad idea in general.
This document presents two examples that demonstrate exactly how bad an
idea this is.


Example 1: softirq Suicide

Suppose that an RCU-based algorithm scans a linked list containing
elements A, B, and C in process context, and can delete elements from
this same list in softirq context.  Suppose that the process-context scan
is referencing element B when it is interrupted by softirq processing,
which deletes element B, and then invokes call_rcu() to free element B
after a grace period.

Now, if call_rcu() were to directly invoke its arguments, then upon return
from softirq, the list scan would find itself referencing a newly freed
element B.  This situation can greatly decrease the life expectancy of
your kernel.


Example 2: Function-Call Fatality

Of course, one could avert the suicide described in the preceding example
by having call_rcu() directly invoke its arguments only if it was called
from process context.  However, this can fail in a similar manner.

Suppose that an RCU-based algorithm again scans a linked list containing
elements A, B, and C in process contexts, but that it invokes a function
on each element as it is scanned.  Suppose further that this function
deletes element B from the list, then passes it to call_rcu() for deferred
freeing.  This may be a bit unconventional, but it is perfectly legal
RCU usage, since call_rcu() must wait for a grace period to elapse.
Therefore, in this case, allowing call_rcu() to immediately invoke
its arguments would cause it to fail to make the fundamental guarantee
underlying RCU, namely that call_rcu() defers invoking its arguments until
all RCU read-side critical sections currently executing have completed.

Quick Quiz: why is it -not- legal to invoke synchronize_rcu() in
this case?


Summary

Permitting call_rcu() to immediately invoke its arguments or permitting
synchronize_rcu() to immediately return breaks RCU, even on a UP system.
So do not do it!  Even on a UP system, the RCU infrastructure -must-
respect grace periods.


Answer to Quick Quiz

The calling function is scanning an RCU-protected linked list, and
is therefore within an RCU read-side critical section.  Therefore,
the called function has been invoked within an RCU read-side critical
section, and is not permitted to block.