Merge branch 'core-rcu-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip

Pull RCU changes for v3.4 from Ingo Molnar.  The major features of this
series are:

 - making RCU more aggressive about entering dyntick-idle mode in order
   to improve energy efficiency

 - converting a few more call_rcu()s to kfree_rcu()s

 - applying a number of rcutree fixes and cleanups to rcutiny

 - removing CONFIG_SMP #ifdefs from treercu

 - allowing RCU CPU stall times to be set via sysfs

 - adding CPU-stall capability to rcutorture

 - adding more RCU-abuse diagnostics

 - updating documentation

 - fixing yet more issues located by the still-ongoing top-to-bottom
   inspection of RCU, this time with a special focus on the CPU-hotplug
   code path.

* 'core-rcu-for-linus' of git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip: (48 commits)
  rcu: Stop spurious warnings from synchronize_sched_expedited
  rcu: Hold off RCU_FAST_NO_HZ after timer posted
  rcu: Eliminate softirq-mediated RCU_FAST_NO_HZ idle-entry loop
  rcu: Add RCU_NONIDLE() for idle-loop RCU read-side critical sections
  rcu: Allow nesting of rcu_idle_enter() and rcu_idle_exit()
  rcu: Remove redundant check for rcu_head misalignment
  PTR_ERR should be called before its argument is cleared.
  rcu: Convert WARN_ON_ONCE() in rcu_lock_acquire() to lockdep
  rcu: Trace only after NULL-pointer check
  rcu: Call out dangers of expedited RCU primitives
  rcu: Rework detection of use of RCU by offline CPUs
  lockdep: Add CPU-idle/offline warning to lockdep-RCU splat
  rcu: No interrupt disabling for rcu_prepare_for_idle()
  rcu: Move synchronize_sched_expedited() to rcutree.c
  rcu: Check for illegal use of RCU from offlined CPUs
  rcu: Update stall-warning documentation
  rcu: Add CPU-stall capability to rcutorture
  rcu: Make documentation give more realistic rcutorture duration
  rcutorture: Permit holding off CPU-hotplug operations during boot
  rcu: Print scheduling-clock information on RCU CPU stall-warning messages
  ...

5 files changed, 1826 insertions, 128 deletions

diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt
index c43460dade0..7c1dfb19fc4 100644
--- a/Documentation/RCU/RTFP.txt
+++ b/Documentation/RCU/RTFP.txt
@@ -1,9 +1,10 @@
-Read the F-ing Papers!
+Read the Fscking Papers!
 
 
 This document describes RCU-related publications, and is followed by
 the corresponding bibtex entries.  A number of the publications may
-be found at http://www.rdrop.com/users/paulmck/RCU/.
+be found at http://www.rdrop.com/users/paulmck/RCU/.  For others, browsers
+and search engines will usually find what you are looking for.
 
 The first thing resembling RCU was published in 1980, when Kung and Lehman
 [Kung80] recommended use of a garbage collector to defer destruction
@@ -160,7 +161,26 @@ which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
 [MathieuDesnoyersPhD].  TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
 its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
 The problem of resizeable RCU-protected hash tables may now be on a path
-to a solution [JoshTriplett2009RPHash].
+to a solution [JoshTriplett2009RPHash].  A few academic researchers are now
+using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].
+
+2010 produced a simpler preemptible-RCU implementation
+based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
+[PaulEMcKenney2010LockdepRCU], another resizeable RCU-protected hash
+table [HerbertXu2010RCUResizeHash] (this one consuming more memory,
+but allowing arbitrary changes in hash function, as required for DoS
+avoidance in the networking code), realization of the 2009 RCU-protected
+hash table with atomic node move [JoshTriplett2010RPHash], an update on
+the RCU API [PaulEMcKenney2010RCUAPI].
+
+2011 marked the inclusion of Nick Piggin's fully lockless dentry search
+[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
+tree using software transactional memory to protect concurrent updates
+(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of
+RCU-protected resizeable hash tables [Triplett:2011:RPHash], the 3.0 RCU
+trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the
+Lockers" LWN article [NeilBrown2011MeetTheLockers].
+
 
 Bibtex Entries
 
@@ -173,6 +193,14 @@ Bibtex Entries
 ,volume="5"
 ,number="3"
 ,pages="354-382"
+,note="Available:
+\url{http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,}
+[Viewed December 3, 2007]"
+,annotation={
+	Use garbage collector to clean up data after everyone is done with it.
+	.
+	Oldest use of something vaguely resembling RCU that I have found.
+}
 }
 
 @techreport{Manber82
@@ -184,6 +212,31 @@ Bibtex Entries
 ,number="82-01-01"
 ,month="January"
 ,pages="28"
+,annotation={
+	.
+	Superseded by Manber84.
+	.
+	Describes concurrent AVL tree implementation.  Uses a
+	garbage-collection mechanism to handle concurrent use and deletion
+	of nodes in the tree, but lacks the summary-of-execution-history
+	concept of read-copy locking.
+	.
+	Keeps full list of processes that were active when a given
+	node was to be deleted, and waits until all such processes have
+	-terminated- before allowing this node to be reused.  This is
+	not described in great detail -- one could imagine using process
+	IDs for this if the ID space was large enough that overlapping
+	never occurred.
+	.
+	This restriction makes this algorithm unsuitable for use in
+	systems comprised of long-lived processes.  It also produces
+	completely unacceptable overhead in systems with large numbers
+	of processes.  Finally, it is specific to AVL trees.
+	.
+	Cites Kung80, so not an independent invention, but the first
+	RCU-like usage that does not rely on an automatic garbage
+	collector.
+}
 }
 
 @article{Manber84
@@ -195,6 +248,74 @@ Bibtex Entries
 ,volume="9"
 ,number="3"
 ,pages="439-455"
+,annotation={
+	Describes concurrent AVL tree implementation.  Uses a
+	garbage-collection mechanism to handle concurrent use and deletion
+	of nodes in the tree, but lacks the summary-of-execution-history
+	concept of read-copy locking.
+	.
+	Keeps full list of processes that were active when a given
+	node was to be deleted, and waits until all such processes have
+	-terminated- before allowing this node to be reused.  This is
+	not described in great detail -- one could imagine using process
+	IDs for this if the ID space was large enough that overlapping
+	never occurred.
+	.
+	This restriction makes this algorithm unsuitable for use in
+	systems comprised of long-lived processes.  It also produces
+	completely unacceptable overhead in systems with large numbers
+	of processes.  Finally, it is specific to AVL trees.
+}
+}
+
+@Conference{RichardRashid87a
+,Author="Richard Rashid and Avadis Tevanian and Michael Young and
+David Golub and Robert Baron and David Black and William Bolosky and
+Jonathan Chew"
+,Title="Machine-Independent Virtual Memory Management for Paged
+Uniprocessor and Multiprocessor Architectures"
+,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support
+for Programming Languages and Operating Systems}"
+,Publisher="Association for Computing Machinery"
+,Month="October"
+,Year="1987"
+,pages="31-39"
+,Address="Palo Alto, CA"
+,note="Available:
+\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}
+[Viewed February 17, 2005]"
+,annotation={
+	Describes lazy TLB flush, where one waits for each CPU to pass
+	through a scheduling-clock interrupt before reusing a given range
+	of virtual address.  Does not describe how one determines that
+	all CPUs have in fact taken such an interrupt, though there are
+	no shortage of straightforward methods for accomplishing this.
+	.
+	Note that it does not make sense to just wait a fixed amount of
+	time, since a given CPU might have interrupts disabled for an
+	extended amount of time.
+}
+}
+
+@article{BarbaraLiskov1988ArgusCACM
+,author = {Barbara Liskov}
+,title = {Distributed programming in {Argus}}
+,journal = {Commun. ACM}
+,volume = {31}
+,number = {3}
+,year = {1988}
+,issn = {0001-0782}
+,pages = {300--312}
+,doi = {http://doi.acm.org/10.1145/42392.42399}
+,publisher = {ACM}
+,address = {New York, NY, USA}
+,annotation= {
+	At the top of page 307: "Conflicts with deposits and withdrawals
+	are necessary if the reported total is to be up to date.  They
+	could be avoided by having total return a sum that is slightly
+	out of date."  Relies on semantics -- approximate numerical
+	values sometimes OK.
+}
 }
 
 @techreport{Hennessy89
@@ -216,6 +337,13 @@ Bibtex Entries
 ,year="1990"
 ,number="CS-TR-2222.1"
 ,month="June"
+,annotation={
+	Concurrent access to skip lists.  Has both weak and strong search.
+	Uses concept of ``garbage queue'', but has no real way of cleaning
+	the garbage efficiently.
+	.
+	Appears to be an independent invention of an RCU-like mechanism.
+}
 }
 
 @Book{Adams91
@@ -223,20 +351,15 @@ Bibtex Entries
 ,title="Concurrent Programming, Principles, and Practices"
 ,Publisher="Benjamin Cummins"
 ,Year="1991"
+,annotation={
+	Has a few paragraphs describing ``chaotic relaxation'', a
+	numerical analysis technique that allows multiprocessors to
+	avoid synchronization overhead by using possibly-stale data.
+	.
+	Seems like this is descended from yet another independent
+	invention of RCU-like function -- but this is restricted
+	in that reclamation is not necessary.
 }
-
-@phdthesis{HMassalinPhD
-,author="H. Massalin"
-,title="Synthesis: An Efficient Implementation of Fundamental Operating
-System Services"
-,school="Columbia University"
-,address="New York, NY"
-,year="1992"
-,annotation="
-	Mondo optimizing compiler.
-	Wait-free stuff.
-	Good advice: defer work to avoid synchronization.
-"
 }
 
 @unpublished{Jacobson93
@@ -244,7 +367,13 @@ System Services"
 ,title="Avoid Read-Side Locking Via Delayed Free"
 ,year="1993"
 ,month="September"
-,note="Verbal discussion"
+,note="private communication"
+,annotation={
+	Use fixed time delay to approximate grace period.  Very simple,
+	but subject to random memory corruption under heavy load.
+	.
+	Independent invention of RCU-like mechanism.
+}
 }
 
 @Conference{AjuJohn95
@@ -256,6 +385,17 @@ System Services"
 ,Year="1995"
 ,pages="11-23"
 ,Address="New Orleans, LA"
+,note="Available:
+\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}
+[Viewed October 1, 2010]"
+,annotation={
+	Age vnodes out of the cache, and have a fixed time set by a kernel
+	parameter.  Not clear that all races were in fact correctly handled.
+	Used a 20-minute time by default, which would most definitely not
+	be suitable during DoS attacks or virus scans.
+	.
+	Apparently independent invention of RCU-like mechanism.
+}
 }
 
 @conference{Pu95a,
@@ -301,31 +441,47 @@ Utilizing Execution History and Thread Monitoring"
 ,institution="US Patent and Trademark Office"
 ,address="Washington, DC"
 ,year="1995"
-,number="US Patent 5,442,758 (contributed under GPL)"
+,number="US Patent 5,442,758"
 ,month="August"
+,annotation={
+	Describes the parallel RCU infrastructure.  Includes NUMA aspect
+	(structure of bitmap can reflect bus structure of computer system).
+	.
+	Another independent invention of an RCU-like mechanism, but the
+	"real" RCU this time!
+}
 }
 
 @techreport{Slingwine97
 ,author="John D. Slingwine and Paul E. McKenney"
-,title="Method for maintaining data coherency using thread
-activity summaries in a multicomputer system"
+,title="Method for Maintaining Data Coherency Using Thread Activity
+Summaries in a Multicomputer System"
 ,institution="US Patent and Trademark Office"
 ,address="Washington, DC"
 ,year="1997"
-,number="US Patent 5,608,893 (contributed under GPL)"
+,number="US Patent 5,608,893"
 ,month="March"
+,pages="19"
+,annotation={
+	Describes use of RCU to synchronize data between a pair of
+	SMP/NUMA computer systems.
+}
 }
 
 @techreport{Slingwine98
 ,author="John D. Slingwine and Paul E. McKenney"
-,title="Apparatus and method for achieving reduced overhead
-mutual exclusion and maintaining coherency in a multiprocessor
-system utilizing execution history and thread monitoring"
+,title="Apparatus and Method for Achieving Reduced Overhead Mutual
+Exclusion and Maintaining Coherency in a Multiprocessor System
+Utilizing Execution History and Thread Monitoring"
 ,institution="US Patent and Trademark Office"
 ,address="Washington, DC"
 ,year="1998"
-,number="US Patent 5,727,209 (contributed under GPL)"
+,number="US Patent 5,727,209"
 ,month="March"
+,annotation={
+	Describes doing an atomic update by copying the data item and
+	then substituting it into the data structure.
+}
 }
 
 @Conference{McKenney98
@@ -337,6 +493,15 @@ Problems"
 ,Year="1998"
 ,pages="509-518"
 ,Address="Las Vegas, NV"
+,note="Available:
+\url{http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf}
+[Viewed December 3, 2007]"
+,annotation={
+	Describes and analyzes RCU mechanism in DYNIX/ptx.  Describes
+	application to linked list update and log-buffer flushing.
+	Defines 'quiescent state'.  Includes both measured and analytic
+	evaluation.
+}
 }
 
 @Conference{Gamsa99
@@ -349,18 +514,76 @@ Operating System Design and Implementation}"
 ,Year="1999"
 ,pages="87-100"
 ,Address="New Orleans, LA"
+,note="Available:
+\url{http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf}
+[Viewed August 30, 2006]"
+,annotation={
+	Use of RCU-like facility in K42/Tornado.  Another independent
+	invention of RCU.
+	See especially pages 7-9 (Section 5).
+}
+}
+
+@unpublished{RustyRussell2000a
+,Author="Rusty Russell"
+,Title="Re: modular net drivers"
+,month="June"
+,year="2000"
+,day="23"
+,note="Available:
+\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}
+[Viewed April 10, 2006]"
+,annotation={
+	Proto-RCU proposal from Phil Rumpf and Rusty Russell.
+	Yet another independent invention of RCU.
+	Outline of algorithm to unload modules...
+	.
+	Appeared on net-dev mailing list.
+}
+}
+
+@unpublished{RustyRussell2000b
+,Author="Rusty Russell"
+,Title="Re: modular net drivers"
+,month="June"
+,year="2000"
+,day="24"
+,note="Available:
+\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}
+[Viewed April 10, 2006]"
+,annotation={
+	Proto-RCU proposal from Phil Rumpf and Rusty Russell.
+	.
+	Appeared on net-dev mailing list.
+}
+}
+
+@unpublished{McKenney01b
+,Author="Paul E. McKenney and Dipankar Sarma"
+,Title="Read-Copy Update Mutual Exclusion in {Linux}"
+,month="February"
+,year="2001"
+,note="Available:
+\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}
+[Viewed October 18, 2004]"
+,annotation={
+	Prototypical Linux documentation for RCU.
+}
 }
 
 @techreport{Slingwine01
 ,author="John D. Slingwine and Paul E. McKenney"
-,title="Apparatus and method for achieving reduced overhead
-mutual exclusion and maintaining coherency in a multiprocessor
-system utilizing execution history and thread monitoring"
+,title="Apparatus and Method for Achieving Reduced Overhead Mutual
+Exclusion and Maintaining Coherency in a Multiprocessor System
+Utilizing Execution History and Thread Monitoring"
 ,institution="US Patent and Trademark Office"
 ,address="Washington, DC"
 ,year="2001"
-,number="US Patent 5,219,690 (contributed under GPL)"
+,number="US Patent 6,219,690"
 ,month="April"
+,annotation={
+	'Change in mode' aspect of RCU.  Can be thought of as a lazy barrier.
+}
 }
 
 @Conference{McKenney01a
@@ -372,14 +595,61 @@ Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
 ,Year="2001"
 ,note="Available:
 \url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
-\url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf}
+\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}
 [Viewed June 23, 2004]"
-annotation="
-Described RCU, and presented some patches implementing and using it in
-the Linux kernel.
+,annotation={
+	Described RCU, and presented some patches implementing and using
+	it in the Linux kernel.
+}
+}
+
+@unpublished{McKenney01f
+,Author="Paul E. McKenney"
+,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"
+,month="October"
+,year="2001"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}
+[Viewed June 23, 2004]"
+,annotation="
+	Memory-barrier and Alpha thread.  100 messages, not too bad...
+"
+}
+
+@unpublished{Spraul01
+,Author="Manfred Spraul"
+,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"
+,month="October"
+,year="2001"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}
+[Viewed June 23, 2004]"
+,annotation="
+	Suggested burying memory barriers in Linux's list-manipulation
+	primitives.
 "
 }
 
+@unpublished{LinusTorvalds2001a
+,Author="Linus Torvalds"
+,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"
+,month="October"
+,year="2001"
+,note="Available:
+\url{http://lkml.org/lkml/2001/10/13/105}
+[Viewed August 21, 2004]"
+}
+
+@unpublished{Blanchard02a
+,Author="Anton Blanchard"
+,Title="some RCU dcache and ratcache results"
+,month="March"
+,year="2002"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}
+[Viewed October 18, 2004]"
+}
+
 @Conference{Linder02a
 ,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
 ,Title="Scalability of the Directory Entry Cache"
@@ -387,6 +657,10 @@ the Linux kernel.
 ,Month="June"
 ,Year="2002"
 ,pages="289-300"
+,annotation="
+	Measured scalability of Linux 2.4 kernel's directory-entry cache
+	(dcache), and measured some scalability enhancements.
+"
 }
 
 @Conference{McKenney02a
@@ -400,49 +674,76 @@ Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
 ,note="Available:
 \url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
 [Viewed June 23, 2004]"
+,annotation="
+	Presented and compared a number of RCU implementations for the
+	Linux kernel.
+"
 }
 
-@conference{Michael02a
-,author="Maged M. Michael"
-,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic
-Reads and Writes"
-,Year="2002"
-,Month="August"
-,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM
-Symposium on Principles of Distributed Computing}"
-,pages="21-30"
+@unpublished{Sarma02a
+,Author="Dipankar Sarma"
+,Title="specweb99: dcache scalability results"
+,month="July"
+,year="2002"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}
+[Viewed June 23, 2004]"
 ,annotation="
-	Each thread keeps an array of pointers to items that it is
-	currently referencing.	Sort of an inside-out garbage collection
-	mechanism, but one that requires the accessing code to explicitly
-	state its needs.  Also requires read-side memory barriers on
-	most architectures.
+	Compare fastwalk and RCU for dcache.  RCU won.
 "
 }
 
-@conference{Michael02b
-,author="Maged M. Michael"
-,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets"
-,Year="2002"
-,Month="August"
-,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM
-Symposium on Parallel
-Algorithms and Architecture}"
-,pages="73-82"
+@unpublished{Barbieri02
+,Author="Luca Barbieri"
+,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"
+,month="August"
+,year="2002"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}
+[Viewed: June 23, 2004]"
 ,annotation="
-	Like the title says...
+	Suggested RCU for vfs\_shared\_cred.
 "
 }
 
-@InProceedings{HerlihyLM02
-,author={Maurice Herlihy and Victor Luchangco and Mark Moir}
-,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized,
-Lock-Free Data Structures"
-,booktitle={Proceedings of 16\textsuperscript{th} International
-Symposium on Distributed Computing}
-,year=2002
+@unpublished{Dickins02a
+,author="Hugh Dickins"
+,title="Use RCU for System-V IPC"
+,year="2002"
+,month="October"
+,note="private communication"
+}
+
+@unpublished{Sarma02b
+,Author="Dipankar Sarma"
+,Title="Some dcache\_rcu benchmark numbers"
 ,month="October"
-,pages="339-353"
+,year="2002"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}
+[Viewed June 23, 2004]"
+,annotation="
+	Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,
+	2x, and 4x systems.  RCU does no harm, and helps on 16x.
+"
+}
+
+@unpublished{LinusTorvalds2003a
+,Author="Linus Torvalds"
+,Title="Re: {[PATCH]} small fixes in brlock.h"
+,month="March"
+,year="2003"
+,note="Available:
+\url{http://lkml.org/lkml/2003/3/9/205}
+[Viewed March 13, 2006]"
+,annotation="
+	Linus suggests replacing brlock with RCU and/or seqlocks:
+	.
+	'It's entirely possible that the current user could be replaced
+	by RCU and/or seqlocks, and we could get rid of brlocks entirely.'
+	.
+	Steve Hemminger responds by replacing them with RCU.
+"
 }
 
 @article{Appavoo03a
@@ -457,6 +758,20 @@ B. Rosenburg and M. Stumm and J. Xenidis"
 ,volume="42"
 ,number="1"
 ,pages="60-76"
+,annotation="
+	Use of RCU to enable hot-swapping for autonomic behavior in K42.
+"
+}
+
+@unpublished{Seigh03
+,author="Joseph W. {Seigh II}"
+,title="Read Copy Update"
+,Year="2003"
+,Month="March"
+,note="email correspondence"
+,annotation="
+	Described the relationship of the VM/XA passive serialization to RCU.
+"
 }
 
 @Conference{Arcangeli03
@@ -470,6 +785,27 @@ Dipankar Sarma"
 ,year="2003"
 ,month="June"
 ,pages="297-310"
+,note="Available:
+\url{http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf}
+[Viewed November 21, 2007]"
+,annotation="
+	Compared updated RCU implementations for the Linux kernel, and
+	described System V IPC use of RCU, including order-of-magnitude
+	performance improvements.
+"
+}
+
+@Conference{Soules03a
+,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and
+Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and
+Michael Stumm and Robert W. Wisniewski and Marc Auslander and
+Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"
+,Title="System Support for Online Reconfiguration"
+,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"
+,Publisher="USENIX Association"
+,year="2003"
+,month="June"
+,pages="141-154"
 }
 
 @article{McKenney03a
@@ -481,6 +817,22 @@ Dipankar Sarma"
 ,volume="1"
 ,number="114"
 ,pages="18-26"
+,note="Available:
+\url{http://www.linuxjournal.com/article/6993}
+[Viewed November 14, 2007]"
+,annotation="
+	Reader-friendly intro to RCU, with the infamous old-man-and-brat
+	cartoon.
+"
+}
+
+@unpublished{Sarma03a
+,Author="Dipankar Sarma"
+,Title="RCU low latency patches"
+,month="December"
+,year="2003"
+,note="Message ID: 20031222180114.GA2248@in.ibm.com"
+,annotation="dipankar/ct.2004.03.27/RCUll.2003.12.22.patch"
 }
 
 @techreport{Friedberg03a
@@ -489,9 +841,14 @@ Dipankar Sarma"
 ,institution="US Patent and Trademark Office"
 ,address="Washington, DC"
 ,year="2003"
-,number="US Patent 6,662,184 (contributed under GPL)"
+,number="US Patent 6,662,184"
 ,month="December"
 ,pages="112"
+,annotation="
+	Applies RCU to a wildcard-search Patricia tree in order to permit
+	synchronization-free lookup.  RCU is used to retain removed nodes
+	for a grace period before freeing them.
+"
 }
 
 @article{McKenney04a
@@ -503,6 +860,12 @@ Dipankar Sarma"
 ,volume="1"
 ,number="118"
 ,pages="38-46"
+,note="Available:
+\url{http://www.linuxjournal.com/node/7124}
+[Viewed December 26, 2010]"
+,annotation="
+	Reader friendly intro to dcache and RCU.
+"
 }
 
 @Conference{McKenney04b
@@ -514,8 +877,83 @@ Dipankar Sarma"
 ,Address="Adelaide, Australia"
 ,note="Available:
 \url{http://www.linux.org.au/conf/2004/abstracts.html#90}
-\url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf}
+\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}
 [Viewed June 23, 2004]"
+,annotation="
+	Compares performance of RCU to that of other locking primitives
+	over a number of CPUs (x86, Opteron, Itanium, and PPC).
+"
+}
+
+@unpublished{Sarma04a
+,Author="Dipankar Sarma"
+,Title="{[PATCH]} {RCU} for low latency (experimental)"
+,month="March"
+,year="2004"
+,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"
+,annotation="Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch"
+}
+
+@unpublished{Sarma04b
+,Author="Dipankar Sarma"
+,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"
+,month="March"
+,year="2004"
+,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"
+,annotation="dipankar/rcuth.2004.03.24/rcu-throttle.patch"
+}
+
+@unpublished{Spraul04a
+,Author="Manfred Spraul"
+,Title="[RFC] 0/5 rcu lock update"
+,month="May"
+,year="2004"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}
+[Viewed June 23, 2004]"
+,annotation="
+	Hierarchical-bitmap patch for RCU infrastructure.
+"
+}
+
+@unpublished{Steiner04a
+,Author="Jack Steiner"
+,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:
+Add per-cpu batch counter"
+,month="May"
+,year="2004"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}
+[Viewed June 23, 2004]"
+,annotation={
+	RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,
+	which may be found at:
+	https://lkml.org/lkml/2004/5/20/49 (split vars into cachelines)
+	https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch)
+	https://lkml.org/lkml/2004/5/25/24 (0/5)
+	https://lkml.org/lkml/2004/5/25/23 (1/5)
+		https://lkml.org/lkml/2004/5/25/265 (works for Jack)
+	https://lkml.org/lkml/2004/5/25/20 (2/5)
+	https://lkml.org/lkml/2004/5/25/22 (3/5)
+	https://lkml.org/lkml/2004/5/25/19 (4/5)
+	https://lkml.org/lkml/2004/5/25/21 (5/5)
+}
+}
+
+@Conference{Sarma04c
+,Author="Dipankar Sarma and Paul E. McKenney"
+,Title="Making {RCU} Safe for Deep Sub-Millisecond Response
+Realtime Applications"
+,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
+(FREENIX Track)"
+,Publisher="USENIX Association"
+,year="2004"
+,month="June"
+,pages="182-191"
+,annotation="
+	Describes and compares a number of modifications to the Linux RCU
+	implementation that make it friendly to realtime applications.
+"
 }
 
 @phdthesis{PaulEdwardMcKenneyPhD
@@ -529,17 +967,118 @@ Oregon Health and Sciences University"
 ,note="Available:
 \url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
 [Viewed October 15, 2004]"
+,annotation="
+	Describes RCU implementations and presents design patterns
+	corresponding to common uses of RCU in several operating-system
+	kernels.
+"
 }
 
-@Conference{Sarma04c
-,Author="Dipankar Sarma and Paul E. McKenney"
-,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications"
-,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
-(FREENIX Track)"
-,Publisher="USENIX Association"
+@unpublished{PaulEMcKenney2004rcu:dereference
+,Author="Dipankar Sarma"
+,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"
+,month="August"
 ,year="2004"
-,month="June"
-,pages="182-191"
+,note="Available:
+\url{http://lkml.org/lkml/2004/8/6/237}
+[Viewed June 8, 2010]"
+,annotation="
+	Introduce rcu_dereference().
+"
+}
+
+@unpublished{JimHouston04a
+,Author="Jim Houston"
+,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"
+,month="August"
+,year="2004"
+,note="Available:
+\url{http://lkml.org/lkml/2004/8/30/87}
+[Viewed February 17, 2005]"
+,annotation="
+	Uses active code in rcu_read_lock() and rcu_read_unlock() to
+	make RCU happen, allowing RCU to function on CPUs that do not
+	receive a scheduling-clock interrupt.
+"
+}
+
+@unpublished{TomHart04a
+,Author="Thomas E. Hart"
+,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"
+,month="October"
+,year="2004"
+,note="Available:
+\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}
+[Viewed October 15, 2004]"
+,annotation="
+	Proposes comparing RCU to lock-free methods for the Linux kernel.
+"
+}
+
+@unpublished{Vaddagiri04a
+,Author="Srivatsa Vaddagiri"
+,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"
+,month="October"
+,year="2004"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}
+[Viewed October 18, 2004]"
+,annotation="
+	Srivatsa's RCU patch for tcp_ehash lookup.
+"
+}
+
+@unpublished{Thirumalai04a
+,Author="Ravikiran Thirumalai"
+,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"
+,month="October"
+,year="2004"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}
+[Viewed October 18, 2004]"
+,annotation="
+	Ravikiran's lockfree FD patch.
+"
+}
+
+@unpublished{Thirumalai04b
+,Author="Ravikiran Thirumalai"
+,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"
+,month="October"
+,year="2004"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}
+[Viewed October 18, 2004]"
+,annotation="
+	Ravikiran's lockfree FD patch.
+"
+}
+
+@unpublished{PaulEMcKenney2004rcu:assign:pointer
+,Author="Paul E. McKenney"
+,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"
+,month="October"
+,year="2004"
+,note="Available:
+\url{http://lkml.org/lkml/2004/10/23/241}
+[Viewed June 8, 2010]"
+,annotation="
+	Introduce rcu_assign_pointer().
+"
+}
+
+@unpublished{JamesMorris04a
+,Author="James Morris"
+,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"
+,day="15"
+,month="November"
+,year="2004"
+,note="Available:
+\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}
+[Viewed December 10, 2004]"
+,annotation="
+	James Morris posts Kaigai Kohei's patch to LKML.
+"
 }
 
 @unpublished{JamesMorris04b
@@ -550,6 +1089,85 @@ Oregon Health and Sciences University"
 ,note="Available:
 \url{http://www.livejournal.com/users/james_morris/2153.html}
 [Viewed December 10, 2004]"
+,annotation="
+	RCU helps SELinux performance.  ;-)  Made LWN.
+"
+}
+
+@unpublished{PaulMcKenney2005RCUSemantics
+,Author="Paul E. McKenney and Jonathan Walpole"
+,Title="{RCU} Semantics: A First Attempt"
+,month="January"
+,year="2005"
+,day="30"
+,note="Available:
+\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}
+[Viewed December 6, 2009]"
+,annotation="
+	Early derivation of RCU semantics.
+"
+}
+
+@unpublished{PaulMcKenney2005e
+,Author="Paul E. McKenney"
+,Title="Real-Time Preemption and {RCU}"
+,month="March"
+,year="2005"
+,day="17"
+,note="Available:
+\url{http://lkml.org/lkml/2005/3/17/199}
+[Viewed September 5, 2005]"
+,annotation="
+	First posting showing how RCU can be safely adapted for
+	preemptable RCU read side critical sections.
+"
+}
+
+@unpublished{EsbenNeilsen2005a
+,Author="Esben Neilsen"
+,Title="Re: Real-Time Preemption and {RCU}"
+,month="March"
+,year="2005"
+,day="18"
+,note="Available:
+\url{http://lkml.org/lkml/2005/3/18/122}
+[Viewed March 30, 2006]"
+,annotation="
+	Esben Neilsen suggests read-side suppression of grace-period
+	processing for crude-but-workable realtime RCU.  The downside
+	is indefinite grace periods...But this is OK for experimentation
+	and testing.
+"
+}
+
+@unpublished{TomHart05a
+,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
+,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free
+Data Structures"
+,month="March"
+,year="2005"
+,note="Available:
+\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}
+[Viewed March 4, 2005]"
+,annotation="
+	Comparison of RCU, QBSR, and EBSR.  RCU wins for read-mostly
+	workloads.  ;-)
+"
+}
+
+@unpublished{JonCorbet2005DeprecateSyncKernel
+,Author="Jonathan Corbet"
+,Title="API change: synchronize_kernel() deprecated"
+,month="May"
+,day="3"
+,year="2005"
+,note="Available:
+\url{http://lwn.net/Articles/134484/}
+[Viewed May 3, 2005]"
+,annotation="
+	Jon Corbet describes deprecation of synchronize_kernel()
+	in favor of synchronize_rcu() and synchronize_sched().
+"
 }
 
 @unpublished{PaulMcKenney05a
@@ -568,7 +1186,7 @@ Oregon Health and Sciences University"
 
 @conference{PaulMcKenney05b
 ,Author="Paul E. McKenney and Dipankar Sarma"
-,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware"
+,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware"
 ,Booktitle="linux.conf.au 2005"
 ,month="April"
 ,year="2005"
@@ -578,6 +1196,103 @@ Oregon Health and Sciences University"
 [Viewed May 13, 2005]"
 ,annotation="
 	Realtime turns into making RCU yet more realtime friendly.
+	http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf
+"
+}
+
+@unpublished{PaulEMcKenneyHomePage
+,Author="Paul E. McKenney"
+,Title="{Paul} {E.} {McKenney}"
+,month="May"
+,year="2005"
+,note="Available:
+\url{http://www.rdrop.com/users/paulmck/}
+[Viewed May 25, 2005]"
+,annotation="
+	Paul McKenney's home page.
+"
+}
+
+@unpublished{PaulEMcKenneyRCUPage
+,Author="Paul E. McKenney"
+,Title="Read-Copy Update {(RCU)}"
+,month="May"
+,year="2005"
+,note="Available:
+\url{http://www.rdrop.com/users/paulmck/RCU}
+[Viewed May 25, 2005]"
+,annotation="
+	Paul McKenney's RCU page.
+"
+}
+
+@unpublished{JosephSeigh2005a
+,Author="Joseph Seigh"
+,Title="{RCU}+{SMR} (hazard pointers)"
+,month="July"
+,year="2005"
+,note="Personal communication"
+,annotation="
+	Joe Seigh announcing his atomic-ptr-plus project.
+	http://sourceforge.net/projects/atomic-ptr-plus/
+"
+}
+
+@unpublished{JosephSeigh2005b
+,Author="Joseph Seigh"
+,Title="Lock-free synchronization primitives"
+,month="July"
+,day="6"
+,year="2005"
+,note="Available:
+\url{http://sourceforge.net/projects/atomic-ptr-plus/}
+[Viewed August 8, 2005]"
+,annotation="
+	Joe Seigh's atomic-ptr-plus project.
+"
+}
+