Update RCU documentation

diff -urpN -X dontdiff linux-2.6.12-rc1/Documentation/RCU/RTFP.txt linux-2.6.12-rc1-bettersk/Documentation/RCU/RTFP.txt
@@ -108,8 +108,9 @@ year saw a paper describing an RCU imple
 2004 has seen a Linux-Journal article on use of RCU in dcache
 [McKenney04a], a performance comparison of locking to RCU on several
 different CPUs [McKenney04b], a dissertation describing use of RCU in a
-number of operating-system kernels [PaulEdwardMcKenneyPhD], and a paper
-describing how to make RCU safe for soft-realtime applications [Sarma04c].
+number of operating-system kernels [PaulEdwardMcKenneyPhD], a paper
+describing how to make RCU safe for soft-realtime applications [Sarma04c],
+and a paper describing SELinux performance with RCU [JamesMorris04b].
 
 
 Bibtex Entries

@@ -341,6 +342,17 @@ Dipankar Sarma"
 ,pages="18-26"
 }
 
+@techreport{Friedberg03a
+,author="Stuart A. Friedberg"
+,title="Lock-Free Wild Card Search Data Structure and Method"
+,institution="US Patent and Trademark Office"
+,address="Washington, DC"
+,year="2003"
+,number="US Patent 6,662,184 (contributed under GPL)"
+,month="December"
+,pages="112"
+}
+
 @article{McKenney04a
 ,author="Paul E. McKenney and Dipankar Sarma and Maneesh Soni"
 ,title="Scaling dcache with {RCU}"

@@ -373,6 +385,9 @@ in Operating System Kernels"
 ,school="OGI School of Science and Engineering at
 Oregon Health and Sciences University"
 ,year="2004"
+,note="Available:
+\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
+[Viewed October 15, 2004]"
 }
 
 @Conference{Sarma04c

@@ -384,4 +399,14 @@ Oregon Health and Sciences University"
 ,year="2004"
 ,month="June"
 ,pages="182-191"
+}
+
+@unpublished{JamesMorris04b
+,Author="James Morris"
+,Title="Recent Developments in {SELinux} Kernel Performance"
+,month="December"
+,year="2004"
+,note="Available:
+\url{http://www.livejournal.com/users/james_morris/2153.html}
+[Viewed December 10, 2004]"
 }

diff -urpN -X dontdiff linux-2.6.12-rc1/Documentation/RCU/UP.txt linux-2.6.12-rc1-bettersk/Documentation/RCU/UP.txt
@@ -2,11 +2,11 @@ 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
+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
+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.

@@ -44,14 +44,14 @@ its arguments would cause it to fail to 
 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
+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_kernel() to immediately return breaks RCU, even on a UP system.
+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.
 

80 lines not on this page · raw message

diff -urpN -X dontdiff linux-2.6.12-rc1/Documentation/RCU/listRCU.txt linux-2.6.12-rc1-bettersk/Documentation/RCU/listRCU.txt
@@ -32,6 +32,7 @@ implementation of audit_filter_task() mi
 		enum audit_state   state;
 
 		read_lock(&auditsc_lock);
+		/* Note: audit_netlink_sem held by caller. */
 		list_for_each_entry(e, &audit_tsklist, list) {
 			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
 				read_unlock(&auditsc_lock);

@@ -55,6 +56,7 @@ This means that RCU can be easily applie
 		enum audit_state   state;
 
 		rcu_read_lock();
+		/* Note: audit_netlink_sem held by caller. */
 		list_for_each_entry_rcu(e, &audit_tsklist, list) {
 			if (audit_filter_rules(tsk, &e->rule, NULL, &state)) {
 				rcu_read_unlock();

@@ -139,12 +141,15 @@ Normally, the write_lock() and write_unl
 a spin_lock() and a spin_unlock(), but in this case, all callers hold
 audit_netlink_sem, so no additional locking is required.  The auditsc_lock
 can therefore be eliminated, since use of RCU eliminates the need for
-writers to exclude readers.
+writers to exclude readers.  Normally, the write_lock() calls would
+be converted into spin_lock() calls.
 
 The list_del(), list_add(), and list_add_tail() primitives have been
 replaced by list_del_rcu(), list_add_rcu(), and list_add_tail_rcu().
 The _rcu() list-manipulation primitives add memory barriers that are
-needed on weakly ordered CPUs (most of them!).
+needed on weakly ordered CPUs (most of them!).  The list_del_rcu()
+primitive omits the pointer poisoning debug-assist code that would
+otherwise cause concurrent readers to fail spectacularly.
 
 So, when readers can tolerate stale data and when entries are either added
 or deleted, without in-place modification, it is very easy to use RCU!

@@ -166,6 +171,7 @@ otherwise, the added fields would need t
 		struct audit_newentry *ne;
 
 		write_lock(&auditsc_lock);
+		/* Note: audit_netlink_sem held by caller. */
 		list_for_each_entry(e, list, list) {
 			if (!audit_compare_rule(rule, &e->rule)) {
 				e->rule.action = newaction;

@@ -199,8 +205,7 @@ RCU ("read-copy update") its name.  The 
 				audit_copy_rule(&ne->rule, &e->rule);
 				ne->rule.action = newaction;
 				ne->rule.file_count = newfield_count;
-				list_add_rcu(ne, e);
-				list_del(e);
+				list_replace_rcu(e, ne);
 				call_rcu(&e->rcu, audit_free_rule, e);
 				return 0;
 			}

diff -urpN -X dontdiff linux-2.6.12-rc1/Documentation/RCU/rcu.txt linux-2.6.12-rc1-bettersk/Documentation/RCU/rcu.txt
@@ -43,7 +43,9 @@ o	If I am running on a uniprocessor kern
 
 o	How can I see where RCU is currently used in the Linux kernel?
 
-	Search for "rcu_read_lock", "call_rcu", and "synchronize_kernel".
+	Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu",
+	"rcu_read_lock_bh", "rcu_read_unlock_bh", "call_rcu_bh",
+	"synchronize_rcu", and "synchronize_net".
 
 o	What guidelines should I follow when writing code that uses RCU?