path: root/Documentation/RCU/UP.txt
diff options
authorLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 15:20:36 -0700
committerLinus Torvalds <torvalds@ppc970.osdl.org>2005-04-16 15:20:36 -0700
commit1da177e4c3f41524e886b7f1b8a0c1fc7321cac2 (patch)
tree0bba044c4ce775e45a88a51686b5d9f90697ea9d /Documentation/RCU/UP.txt
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!
Diffstat (limited to 'Documentation/RCU/UP.txt')
1 files changed, 64 insertions, 0 deletions
diff --git a/Documentation/RCU/UP.txt b/Documentation/RCU/UP.txt
new file mode 100644
index 000000000000..551a803d82a8
--- /dev/null
+++ b/Documentation/RCU/UP.txt
@@ -0,0 +1,64 @@
+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_kernel
+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_kernel() in
+this case?
+Permitting call_rcu() to immediately invoke its arguments or permitting
+synchronize_kernel() 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.