diff options
29 files changed, 2906 insertions, 583 deletions
diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt index c43460dade0f..7c1dfb19fc40 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" |