blob: 3bfb84b3b7dbc5120bbcbf14c52ed95fb2a72507 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001RCU on Uniprocessor Systems
2
3
4A common misconception is that, on UP systems, the call_rcu() primitive
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -07005may immediately invoke its function, and that the synchronize_rcu()
Linus Torvalds1da177e2005-04-16 15:20:36 -07006primitive may return immediately. The basis of this misconception
7is that since there is only one CPU, it should not be necessary to
8wait for anything else to get done, since there are no other CPUs for
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -07009anything else to be happening on. Although this approach will -sort- -of-
Linus Torvalds1da177e2005-04-16 15:20:36 -070010work a surprising amount of the time, it is a very bad idea in general.
11This document presents two examples that demonstrate exactly how bad an
12idea this is.
13
14
15Example 1: softirq Suicide
16
17Suppose that an RCU-based algorithm scans a linked list containing
18elements A, B, and C in process context, and can delete elements from
19this same list in softirq context. Suppose that the process-context scan
20is referencing element B when it is interrupted by softirq processing,
21which deletes element B, and then invokes call_rcu() to free element B
22after a grace period.
23
24Now, if call_rcu() were to directly invoke its arguments, then upon return
25from softirq, the list scan would find itself referencing a newly freed
26element B. This situation can greatly decrease the life expectancy of
27your kernel.
28
29
30Example 2: Function-Call Fatality
31
32Of course, one could avert the suicide described in the preceding example
33by having call_rcu() directly invoke its arguments only if it was called
34from process context. However, this can fail in a similar manner.
35
36Suppose that an RCU-based algorithm again scans a linked list containing
37elements A, B, and C in process contexts, but that it invokes a function
38on each element as it is scanned. Suppose further that this function
39deletes element B from the list, then passes it to call_rcu() for deferred
40freeing. This may be a bit unconventional, but it is perfectly legal
41RCU usage, since call_rcu() must wait for a grace period to elapse.
42Therefore, in this case, allowing call_rcu() to immediately invoke
43its arguments would cause it to fail to make the fundamental guarantee
44underlying RCU, namely that call_rcu() defers invoking its arguments until
45all RCU read-side critical sections currently executing have completed.
46
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -070047Quick Quiz: why is it -not- legal to invoke synchronize_rcu() in
Linus Torvalds1da177e2005-04-16 15:20:36 -070048this case?
49
50
51Summary
52
53Permitting call_rcu() to immediately invoke its arguments or permitting
Paul E. McKenneya83f1fe2005-05-01 08:59:05 -070054synchronize_rcu() to immediately return breaks RCU, even on a UP system.
Linus Torvalds1da177e2005-04-16 15:20:36 -070055So do not do it! Even on a UP system, the RCU infrastructure -must-
56respect grace periods.
57
58
59Answer to Quick Quiz
60
61The calling function is scanning an RCU-protected linked list, and
62is therefore within an RCU read-side critical section. Therefore,
63the called function has been invoked within an RCU read-side critical
64section, and is not permitted to block.