diff options
Diffstat (limited to 'Documentation')
47 files changed, 2873 insertions, 342 deletions
diff --git a/Documentation/ABI/removed/devfs b/Documentation/ABI/removed/devfs index 8ffd28bf6598..0020c49933c4 100644 --- a/Documentation/ABI/removed/devfs +++ b/Documentation/ABI/removed/devfs @@ -1,6 +1,6 @@ What: devfs Date: July 2005 (scheduled), finally removed in kernel v2.6.18 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: devfs has been unmaintained for a number of years, has unfixable races, contains a naming policy within the kernel that is diff --git a/Documentation/ABI/stable/sysfs-driver-usb-usbtmc b/Documentation/ABI/stable/sysfs-driver-usb-usbtmc index 9a75fb22187d..23a43b8207e6 100644 --- a/Documentation/ABI/stable/sysfs-driver-usb-usbtmc +++ b/Documentation/ABI/stable/sysfs-driver-usb-usbtmc @@ -1,7 +1,7 @@ What: /sys/bus/usb/drivers/usbtmc/devices/*/interface_capabilities What: /sys/bus/usb/drivers/usbtmc/devices/*/device_capabilities Date: August 2008 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: These files show the various USB TMC capabilities as described by the device itself. The full description of the bitfields @@ -15,7 +15,7 @@ Description: What: /sys/bus/usb/drivers/usbtmc/devices/*/usb488_interface_capabilities What: /sys/bus/usb/drivers/usbtmc/devices/*/usb488_device_capabilities Date: August 2008 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: These files show the various USB TMC capabilities as described by the device itself. The full description of the bitfields @@ -29,7 +29,7 @@ Description: What: /sys/bus/usb/drivers/usbtmc/devices/*/TermChar Date: August 2008 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: This file is the TermChar value to be sent to the USB TMC device as described by the document, "Universal Serial Bus Test @@ -42,7 +42,7 @@ Description: What: /sys/bus/usb/drivers/usbtmc/devices/*/TermCharEnabled Date: August 2008 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: This file determines if the TermChar is to be sent to the device on every transaction or not. For more details about @@ -53,7 +53,7 @@ Description: What: /sys/bus/usb/drivers/usbtmc/devices/*/auto_abort Date: August 2008 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: This file determines if the the transaction of the USB TMC device is to be automatically aborted if there is any error. diff --git a/Documentation/ABI/testing/sysfs-bus-usb b/Documentation/ABI/testing/sysfs-bus-usb index b4f548792e32..7c22a532fdfb 100644 --- a/Documentation/ABI/testing/sysfs-bus-usb +++ b/Documentation/ABI/testing/sysfs-bus-usb @@ -182,3 +182,14 @@ Description: USB2 hardware LPM is enabled for the device. Developer can write y/Y/1 or n/N/0 to the file to enable/disable the feature. + +What: /sys/bus/usb/devices/.../removable +Date: February 2012 +Contact: Matthew Garrett <mjg@redhat.com> +Description: + Some information about whether a given USB device is + physically fixed to the platform can be inferred from a + combination of hub decriptor bits and platform-specific data + such as ACPI. This file will read either "removable" or + "fixed" if the information is available, and "unknown" + otherwise.
\ No newline at end of file diff --git a/Documentation/ABI/testing/sysfs-class b/Documentation/ABI/testing/sysfs-class index 4b0cb891e46e..676530fcf747 100644 --- a/Documentation/ABI/testing/sysfs-class +++ b/Documentation/ABI/testing/sysfs-class @@ -1,6 +1,6 @@ What: /sys/class/ Date: Febuary 2006 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: The /sys/class directory will consist of a group of subdirectories describing individual classes of devices diff --git a/Documentation/ABI/testing/sysfs-class-net-mesh b/Documentation/ABI/testing/sysfs-class-net-mesh index b02001488eef..b218e0f8bdb3 100644 --- a/Documentation/ABI/testing/sysfs-class-net-mesh +++ b/Documentation/ABI/testing/sysfs-class-net-mesh @@ -65,6 +65,13 @@ Description: Defines the penalty which will be applied to an originator message's tq-field on every hop. +What: /sys/class/net/<mesh_iface>/mesh/routing_algo +Date: Dec 2011 +Contact: Marek Lindner <lindner_marek@yahoo.de> +Description: + Defines the routing procotol this mesh instance + uses to find the optimal paths through the mesh. + What: /sys/class/net/<mesh_iface>/mesh/vis_mode Date: May 2010 Contact: Marek Lindner <lindner_marek@yahoo.de> diff --git a/Documentation/ABI/testing/sysfs-devices b/Documentation/ABI/testing/sysfs-devices index 6a25671ee5f6..5fcc94358b8d 100644 --- a/Documentation/ABI/testing/sysfs-devices +++ b/Documentation/ABI/testing/sysfs-devices @@ -1,6 +1,6 @@ What: /sys/devices Date: February 2006 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: The /sys/devices tree contains a snapshot of the internal state of the kernel device tree. Devices will diff --git a/Documentation/ABI/testing/sysfs-devices-soc b/Documentation/ABI/testing/sysfs-devices-soc new file mode 100644 index 000000000000..6d9cc253f2b2 --- /dev/null +++ b/Documentation/ABI/testing/sysfs-devices-soc @@ -0,0 +1,58 @@ +What: /sys/devices/socX +Date: January 2012 +contact: Lee Jones <lee.jones@linaro.org> +Description: + The /sys/devices/ directory contains a sub-directory for each + System-on-Chip (SoC) device on a running platform. Information + regarding each SoC can be obtained by reading sysfs files. This + functionality is only available if implemented by the platform. + + The directory created for each SoC will also house information + about devices which are commonly contained in /sys/devices/platform. + It has been agreed that if an SoC device exists, its supported + devices would be better suited to appear as children of that SoC. + +What: /sys/devices/socX/machine +Date: January 2012 +contact: Lee Jones <lee.jones@linaro.org> +Description: + Read-only attribute common to all SoCs. Contains the SoC machine + name (e.g. Ux500). + +What: /sys/devices/socX/family +Date: January 2012 +contact: Lee Jones <lee.jones@linaro.org> +Description: + Read-only attribute common to all SoCs. Contains SoC family name + (e.g. DB8500). + +What: /sys/devices/socX/soc_id +Date: January 2012 +contact: Lee Jones <lee.jones@linaro.org> +Description: + Read-only attribute supported by most SoCs. In the case of + ST-Ericsson's chips this contains the SoC serial number. + +What: /sys/devices/socX/revision +Date: January 2012 +contact: Lee Jones <lee.jones@linaro.org> +Description: + Read-only attribute supported by most SoCs. Contains the SoC's + manufacturing revision number. + +What: /sys/devices/socX/process +Date: January 2012 +contact: Lee Jones <lee.jones@linaro.org> +Description: + Read-only attribute supported ST-Ericsson's silicon. Contains the + the process by which the silicon chip was manufactured. + +What: /sys/bus/soc +Date: January 2012 +contact: Lee Jones <lee.jones@linaro.org> +Description: + The /sys/bus/soc/ directory contains the usual sub-folders + expected under most buses. /sys/bus/soc/devices is of particular + interest, as it contains a symlink for each SoC device found on + the system. Each symlink points back into the aforementioned + /sys/devices/socX devices. diff --git a/Documentation/ABI/testing/sysfs-driver-samsung-laptop b/Documentation/ABI/testing/sysfs-driver-samsung-laptop index 0a810231aad4..e82e7c2b8f80 100644 --- a/Documentation/ABI/testing/sysfs-driver-samsung-laptop +++ b/Documentation/ABI/testing/sysfs-driver-samsung-laptop @@ -1,7 +1,7 @@ What: /sys/devices/platform/samsung/performance_level Date: January 1, 2010 KernelVersion: 2.6.33 -Contact: Greg Kroah-Hartman <gregkh@suse.de> +Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Description: Some Samsung laptops have different "performance levels" that are can be modified by a function key, and by this sysfs file. These values don't always make a whole lot diff --git a/Documentation/DocBook/80211.tmpl b/Documentation/DocBook/80211.tmpl index 2014155c899d..c5ac6929c41c 100644 --- a/Documentation/DocBook/80211.tmpl +++ b/Documentation/DocBook/80211.tmpl @@ -129,7 +129,6 @@ !Finclude/net/cfg80211.h cfg80211_pmksa !Finclude/net/cfg80211.h cfg80211_send_rx_auth !Finclude/net/cfg80211.h cfg80211_send_auth_timeout -!Finclude/net/cfg80211.h __cfg80211_auth_canceled !Finclude/net/cfg80211.h cfg80211_send_rx_assoc !Finclude/net/cfg80211.h cfg80211_send_assoc_timeout !Finclude/net/cfg80211.h cfg80211_send_deauth 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" +,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. +" +} + +@unpublished{PaulMcKenney2005c +,Author="Paul E.McKenney" +,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch" +,month="August" +,day="1" +,year="2005" +,note="Available: +\url{http://lkml.org/lkml/2005/8/1/155} +[Viewed March 14, 2006]" +,annotation=" + First operating counter-based realtime RCU patch posted to LKML. +" +} + +@unpublished{PaulMcKenney2005d +,Author="Paul E. McKenney" +,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]" +,month="August" +,day="8" +,year="2005" +,note="Available: +\url{http://lkml.org/lkml/2005/8/8/108} +[Viewed March 14, 2006]" +,annotation=" + First operating counter-based realtime RCU patch posted to LKML, + but fixed so that various unusual combinations of configuration + parameters all function properly. +" +} + +@unpublished{PaulMcKenney2005rcutorture +,Author="Paul E. McKenney" +,Title="{[PATCH]} {RCU} torture testing" +,month="October" +,day="1" +,year="2005" +,note="Available: +\url{http://lkml.org/lkml/2005/10/1/70} +[Viewed March 14, 2006]" +,annotation=" + First rcutorture patch. " } @@ -591,22 +1306,39 @@ Distributed Processing Symposium" ,year="2006" ,day="25-29" ,address="Rhodes, Greece" +,note="Available: +\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf} +[Viewed April 28, 2008]" +,annotation=" + Compares QSBR, HPBR, EBR, and lock-free reference counting. + http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz +" +} + +@unpublished{NickPiggin2006radixtree +,Author="Nick Piggin" +,Title="[patch 3/3] radix-tree: {RCU} lockless readside" +,month="June" +,day="20" +,year="2006" +,note="Available: +\url{http://lkml.org/lkml/2006/6/20/238} +[Viewed March 25, 2008]" ,annotation=" - Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free - reference counting. + RCU-protected radix tree. " } @Conference{PaulEMcKenney2006b ,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and Suparna Bhattacharya" -,Title="Extending RCU for Realtime and Embedded Workloads" +,Title="Extending {RCU} for Realtime and Embedded Workloads" ,Booktitle="{Ottawa Linux Symposium}" ,Month="July" ,Year="2006" ,pages="v2 123-138" ,note="Available: -\url{http://www.linuxsymposium.org/2006/index_2006.php} +\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} \url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf} [Viewed January 1, 2007]" ,annotation=" @@ -614,6 +1346,37 @@ Suparna Bhattacharya" " } +@unpublished{WikipediaRCU +,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and +Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and +Canis Rufus and Zoicon5 and Anome and Hal Eisen" +,Title="Read-Copy Update" +,month="July" +,day="8" +,year="2006" +,note="Available: +\url{http://en.wikipedia.org/wiki/Read-copy-update} +[Viewed August 21, 2006]" +,annotation=" + Wikipedia RCU page as of July 8 2006. +" +} + +@Conference{NickPiggin2006LocklessPageCache +,Author="Nick Piggin" +,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance" +,Booktitle="{Ottawa Linux Symposium}" +,Month="July" +,Year="2006" +,pages="v2 249-254" +,note="Available: +\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184} +[Viewed January 11, 2009]" +,annotation=" + Uses RCU-protected radix tree for a lockless page cache. +" +} + @unpublished{PaulEMcKenney2006c ,Author="Paul E. McKenney" ,Title="Sleepable {RCU}" @@ -637,29 +1400,301 @@ Revised: ,day="18" ,year="2006" ,note="Available: -\url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf} -[Viewed February 24, 2007]" +\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf} +[Viewed March 4, 2011]" ,annotation=" RCU-protected dynamic trie-hash combination. " } -@unpublished{ThomasEHart2007a -,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole" -,Title="Performance of memory reclamation for lockless synchronization" -,journal="J. Parallel Distrib. Comput." +@unpublished{ChristophHellwig2006RCU2SRCU +,Author="Christoph Hellwig" +,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu" +,month="September" +,day="28" +,year="2006" +,note="Available: +\url{http://lkml.org/lkml/2006/9/28/160} +[Viewed March 27, 2008]" +} + +@unpublished{PaulEMcKenneyRCUusagePage +,Author="Paul E. McKenney" +,Title="{RCU} {Linux} Usage" +,month="October" +,year="2006" +,note="Available: +\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html} +[Viewed January 14, 2007]" +,annotation=" + Paul McKenney's RCU page showing graphs plotting Linux-kernel + usage of RCU. +" +} + +@unpublished{PaulEMcKenneyRCUusageRawDataPage +,Author="Paul E. McKenney" +,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel" +,month="October" +,year="2006" +,note="Available: +\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html} +[Viewed January 14, 2007]" +,annotation=" + Paul McKenney's RCU page showing Linux usage of RCU in tabular + form, with links to corresponding cscope databases. +" +} + +@unpublished{GauthamShenoy2006RCUrwlock +,Author="Gautham R. Shenoy" +,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug" +,month="October" +,year="2006" +,day=26 +,note="Available: +\url{http://lkml.org/lkml/2006/10/26/73} +[Viewed January 26, 2009]" +,annotation=" + RCU-based reader-writer lock that allows readers to proceed with + no memory barriers or atomic instruction in absence of writers. + If writer do show up, readers must of course wait as required by + the semantics of reader-writer locking. This is a recursive + lock. +" +} + +@unpublished{JensAxboe2006SlowSRCU +,Author="Jens Axboe" +,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as +\url{core_initcall_sync}" +,month="November" +,year="2006" +,day=17 +,note="Available: +\url{http://lkml.org/lkml/2006/11/17/56} +[Viewed May 28, 2007]" +,annotation=" + SRCU's grace periods are too slow for Jens, even after a + factor-of-three speedup. + Sped-up version of SRCU at http://lkml.org/lkml/2006/11/17/359. +" +} + +@unpublished{OlegNesterov2006QRCU +,Author="Oleg Nesterov" +,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as +{\tt core\_initcall\_sync}" +,month="November" +,year="2006" +,day=19 +,note="Available: +\url{http://lkml.org/lkml/2006/11/19/69} +[Viewed May 28, 2007]" +,annotation=" + First cut of QRCU. Expanded/corrected versions followed. + Used to be OlegNesterov2007QRCU, now time-corrected. +" +} + +@unpublished{OlegNesterov2006aQRCU +,Author="Oleg Nesterov" +,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation" +,month="November" +,year="2006" +,day=30 +,note="Available: +\url{http://lkml.org/lkml/2006/11/29/330} +[Viewed November 26, 2008]" +,annotation=" + Expanded/corrected version of QRCU. + Used to be OlegNesterov2007aQRCU, now time-corrected. +" +} + +@unpublished{EvgeniyPolyakov2006RCUslowdown +,Author="Evgeniy Polyakov" +,Title="Badness in postponing work" +,month="December" +,year="2006" +,day=05 +,note="Available: +\url{http://www.ioremap.net/node/41} +[Viewed October 28, 2008]" +,annotation=" + Using RCU as a pure delay leads to a 2.5x slowdown in skbs in + the Linux kernel. +" +} + +@inproceedings{ChrisMatthews2006ClusteredObjectsRCU +,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan} +,title = {Portability events: a programming model for scalable system infrastructures} +,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems} +,year = {2006} +,isbn = {1-59593-577-0} +,pages = {11} +,location = {San Jose, California} +,doi = {http://doi.acm.org/10.1145/1215995.1216006} +,publisher = {ACM} +,address = {New York, NY, USA} +,annotation={ + Uses K42's RCU-like functionality to manage clustered-object + lifetimes. +}} + +@article{DilmaDaSilva2006K42 +,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew} +,title = {K42: an infrastructure for operating system research} +,journal = {SIGOPS Oper. Syst. Rev.} +,volume = {40} +,number = {2} +,year = {2006} +,issn = {0163-5980} +,pages = {34--42} +,doi = {http://doi.acm.org/10.1145/1131322.1131333} +,publisher = {ACM} +,address = {New York, NY, USA} +,annotation={ + Describes relationship of K42 generations to RCU. +}} + +# CoreyMinyard2007list_splice_rcu +@unpublished{CoreyMinyard2007list:splice:rcu +,Author="Corey Minyard and Paul E. McKenney" +,Title="{[PATCH]} add an {RCU} version of list splicing" +,month="January" +,year="2007" +,day=3 +,note="Available: +\url{http://lkml.org/lkml/2007/1/3/112} +[Viewed May 28, 2007]" +,annotation=" + Patch for list_splice_rcu(). +" +} + +@unpublished{PaulEMcKenney2007rcubarrier +,Author="Paul E. McKenney" +,Title="{RCU} and Unloadable Modules" +,month="January" +,day="14" +,year="2007" +,note="Available: +\url{http://lwn.net/Articles/217484/} +[Viewed November 22, 2007]" +,annotation=" + LWN article introducing the rcu_barrier() primitive. +" +} + +@unpublished{PeterZijlstra2007SyncBarrier +,Author="Peter Zijlstra and Ingo Molnar" +,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier" +,month="January" +,year="2007" +,day=28 +,note="Available: +\url{http://lkml.org/lkml/2007/1/28/34} +[Viewed March 27, 2008]" +,annotation=" + RCU-like implementation for frequent updaters and rare readers(!). + Subsumed into QRCU. Maybe... +" +} + +@unpublished{PaulEMcKenney2007BoostRCU +,Author="Paul E. McKenney" +,Title="Priority-Boosting {RCU} Read-Side Critical Sections" +,month="February" +,day="5" +,year="2007" +,note="Available: +\url{http://lwn.net/Articles/220677/} +Revised: +\url{http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf} +[Viewed September 7, 2007]" +,annotation=" + LWN article introducing RCU priority boosting. +" +} + +@unpublished{PaulMcKenney2007QRCUpatch +,Author="Paul E. McKenney" +,Title="{[PATCH]} {QRCU} with lockless fastpath" +,month="February" +,year="2007" +,day=24 +,note="Available: +\url{http://lkml.org/lkml/2007/2/25/18} +[Viewed March 27, 2008]" +,annotation=" + Patch for QRCU supplying lock-free fast path. +" +} + +@article{JonathanAppavoo2007K42RCU +,author = {Appavoo, Jonathan and Silva, Dilma Da and Krieger, Orran and Auslander, Marc and Ostrowski, Michal and Rosenburg, Bryan and Waterland, Amos and Wisniewski, Robert W. and Xenidis, Jimi and Stumm, Michael and Soares, Livio} +,title = {Experience distributing objects in an SMMP OS} +,journal = {ACM Trans. Comput. Syst.} +,volume = {25} +,number = {3} +,year = {2007} +,issn = {0734-2071} +,pages = {6/1--6/52} +,doi = {http://doi.acm.org/10.1145/1275517.1275518} +,publisher = {ACM} +,address = {New York, NY, USA} +,annotation={ + Role of RCU in K42. +}} + +@conference{RobertOlsson2007Trash +,Author="Robert Olsson and Stefan Nilsson" +,Title="{TRASH}: A dynamic {LC}-trie and hash data structure" +,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)" +,month="May" +,year="2007" +,note="Available: +\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239} +[Viewed October 1, 2010]" +,annotation=" + RCU-protected dynamic trie-hash combination. +" +} + +@conference{PeterZijlstra2007ConcurrentPagecacheRCU +,Author="Peter Zijlstra" +,Title="Concurrent Pagecache" +,Booktitle="Linux Symposium" +,month="June" ,year="2007" -,note="To appear in J. Parallel Distrib. Comput. - \url{doi=10.1016/j.jpdc.2007.04.010}" +,address="Ottawa, Canada" +,note="Available: +\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf} +[Viewed April 14, 2008]" +,annotation=" + Page-cache modifications permitting RCU readers and concurrent + updates. +" +} + +@unpublished{PaulEMcKenney2007whatisRCU +,Author="Paul E. McKenney" +,Title="What is {RCU}?" +,year="2007" +,month="07" +,note="Available: +\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html} +[Viewed July 6, 2007]" ,annotation={ - Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free - reference counting. Journal version of ThomasEHart2006a. + Describes RCU in Linux kernel. } } @unpublished{PaulEMcKenney2007QRCUspin ,Author="Paul E. McKenney" -,Title="Using Promela and Spin to verify parallel algorithms" +,Title="Using {Promela} and {Spin} to verify parallel algorithms" ,month="August" ,day="1" ,year="2007" @@ -669,6 +1704,50 @@ Revised: ,annotation=" LWN article describing Promela and spin, and also using Oleg Nesterov's QRCU as an example (with Paul McKenney's fastpath). + Merged patch at: http://lkml.org/lkml/2007/2/25/18 +" +} + +@unpublished{PaulEMcKenney2007WG21DDOatomics +,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl" +,Title="C++ Data-Dependency Ordering: Atomics and Memory Model" +,month="August" +,day="3" +,year="2007" +,note="Preprint: +\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm} +[Viewed December 7, 2009]" +,annotation=" + RCU for C++, parts 1 and 2. +" +} + +@unpublished{PaulEMcKenney2007WG21DDOannotation +,Author="Paul E. McKenney and Lawrence Crowl" +,Title="C++ Data-Dependency Ordering: Function Annotation" +,month="September" +,day="18" +,year="2008" +,note="Preprint: +\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm} +[Viewed December 7, 2009]" +,annotation=" + RCU for C++, part 2, updated many times. +" +} + +@unpublished{PaulEMcKenney2007PreemptibleRCUPatch +,Author="Paul E. McKenney" +,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}" +,month="September" +,day="10" +,year="2007" +,note="Available: +\url{http://lkml.org/lkml/2007/9/10/213} +[Viewed October 25, 2007]" +,annotation=" + Final patch for preemptable RCU to -rt. (Later patches were + to mainline, eventually incorporated.) " } @@ -686,10 +1765,46 @@ Revised: " } +@article{ThomasEHart2007a +,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole" +,Title="Performance of memory reclamation for lockless synchronization" +,journal="J. Parallel Distrib. Comput." +,volume={67} +,number="12" +,year="2007" +,issn="0743-7315" +,pages="1270--1285" +,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010" +,publisher="Academic Press, Inc." +,address="Orlando, FL, USA" +,annotation={ + Compares QSBR, HPBR, EBR, and lock-free reference counting. + Journal version of ThomasEHart2006a. +} +} + +@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded +,Author="Mathieu Desnoyers" +,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes" +,month="December" +,day="20" +,year="2007" +,note="Available: +\url{http://lkml.org/lkml/2007/12/20/244} +[Viewed March 27, 2008]" +,annotation=" + Request for call_rcu_sched() and rcu_barrier_sched(). +" +} + + ######################################################################## # # "What is RCU?" LWN series. # +# http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?) +# http://lwn.net/Articles/263130/ (What is RCU's Usage?) +# http://lwn.net/Articles/264090/ (What is RCU's API?) @unpublished{PaulEMcKenney2007WhatIsRCUFundamentally ,Author="Paul E. McKenney and Jonathan Walpole" @@ -723,7 +1838,7 @@ Revised: 3. RCU is a Bulk Reference-Counting Mechanism 4. RCU is a Poor Man's Garbage Collector 5. RCU is a Way of Providing Existence Guarantees - 6. RCU is a Way of Waiting for Things to Finish + 6. RCU is a Way of Waiting for Things to Finish " } @@ -747,20 +1862,96 @@ Revised: # ######################################################################## + +@unpublished{SteveRostedt2008dyntickRCUpatch +,Author="Steven Rostedt and Paul E. McKenney" +,Title="{[PATCH]} add support for dynamic ticks and preempt rcu" +,month="January" +,day="29" +,year="2008" +,note="Available: +\url{http://lkml.org/lkml/2008/1/29/208} +[Viewed March 27, 2008]" +,annotation=" + Patch that prevents preemptible RCU from unnecessarily waking + up dynticks-idle CPUs. +" +} + +@unpublished{PaulEMcKenney2008LKMLDependencyOrdering +,Author="Paul E. McKenney" +,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation" +,month="February" +,day="1" +,year="2008" +,note="Available: +\url{http://lkml.org/lkml/2008/2/2/255} +[Viewed October 18, 2008]" +,annotation=" + Explanation of compilers violating dependency ordering. +" +} + +@Conference{PaulEMcKenney2008Beijing +,Author="Paul E. McKenney" +,Title="Introducing Technology Into {Linux} Or: +Introducing your technology Into {Linux} will require introducing a +lot of {Linux} into your technology!!!" +,Booktitle="2008 Linux Developer Symposium - China" +,Publisher="OSS China" +,Month="February" +,Year="2008" +,Address="Beijing, China" +,note="Available: +\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf} +[Viewed August 12, 2008]" +} + +@unpublished{PaulEMcKenney2008dynticksRCU +,Author="Paul E. McKenney and Steven Rostedt" +,Title="Integrating and Validating dynticks and Preemptable RCU" +,month="April" +,day="24" +,year="2008" +,note="Available: +\url{http://lwn.net/Articles/279077/} +[Viewed April 24, 2008]" +,annotation=" + Describes use of Promela and Spin to validate (and fix!) the + dynticks/RCU interface. +" +} + @article{DinakarGuniguntala2008IBMSysJ ,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole" ,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}" ,Year="2008" -,Month="April" +,Month="April-June" ,journal="IBM Systems Journal" ,volume="47" ,number="2" -,pages="@@-@@" +,pages="221-236" ,annotation=" RCU, realtime RCU, sleepable RCU, performance. " } +@unpublished{LaiJiangshan2008NewClassicAlgorithm +,Author="Lai Jiangshan" +,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing" +,month="June" +,day="3" +,year="2008" +,note="Available: +\url{http://lkml.org/lkml/2008/6/2/539} +[Viewed December 10, 2008]" +,annotation=" + Updated RCU classic algorithm. Introduced multi-tailed list + for RCU callbacks and also pulling common code into + __call_rcu(). +" +} + @article{PaulEMcKenney2008RCUOSR ,author="Paul E. McKenney and Jonathan Walpole" ,title="Introducing technology into the {Linux} kernel: a case study" @@ -778,6 +1969,52 @@ Revised: } } +@unpublished{ManfredSpraul2008StateMachineRCU +,Author="Manfred Spraul" +,Title="[{RFC}, {PATCH}] state machine based rcu" +,month="August" +,day="21" +,year="2008" +,note="Available: +\url{http://lkml.org/lkml/2008/8/21/336} +[Viewed December 8, 2008]" +,annotation=" + State-based RCU. One key thing that this patch does is to + separate the dynticks handling of NMIs and IRQs. +" +} + +@unpublished{ManfredSpraul2008dyntickIRQNMI +,Author="Manfred Spraul" +,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation" +,month="September" +,day="6" +,year="2008" +,note="Available: +\url{http://lkml.org/lkml/2008/9/6/86} +[Viewed December 8, 2008]" +,annotation=" + Manfred notes a fix required to my attempt to separate irq + and NMI processing for hierarchical RCU's dynticks interface. +" +} + +@techreport{PaulEMcKenney2008cyclicRCU +,author="Paul E. McKenney" +,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update" +,institution="US Patent and Trademark Office" +,address="Washington, DC" +,year="2008" +,number="US Patent 7,426,511" +,month="September" +,pages="23" +,annotation=" + Maintains an additional level of indirection to allow + readers to confine themselves to the desired snapshot of the + data structure. Only permits one update at a time. +" +} + @unpublished{PaulEMcKenney2008HierarchicalRCU ,Author="Paul E. McKenney" ,Title="Hierarchical {RCU}" @@ -793,6 +2030,21 @@ Revised: " } +@unpublished{PaulEMcKenney2009BloatwatchRCU +,Author="Paul E. McKenney" +,Title="Re: [PATCH fyi] RCU: the bloatwatch edition" +,month="January" +,day="14" +,year="2009" +,note="Available: +\url{http://lkml.org/lkml/2009/1/14/449} +[Viewed January 15, 2009]" +,annotation=" + Small-footprint implementation of RCU for uniprocessor + embedded applications -- and also for exposition purposes. +" +} + @conference{PaulEMcKenney2009MaliciousURCU ,Author="Paul E. McKenney" ,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms" @@ -816,15 +2068,17 @@ Revised: ,year="2009" ,note="Available: \url{http://lkml.org/lkml/2009/2/5/572} -\url{git://lttng.org/userspace-rcu.git} +\url{http://lttng.org/urcu} [Viewed February 20, 2009]" ,annotation=" Mathieu Desnoyers's user-space RCU implementation. git://lttng.org/userspace-rcu.git + http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git + http://lttng.org/urcu " } -@unpublished{PaulEMcKenney2009BloatWatchRCU +@unpublished{PaulEMcKenney2009LWNBloatWatchRCU ,Author="Paul E. McKenney" ,Title="{RCU}: The {Bloatwatch} Edition" ,month="March" @@ -852,14 +2106,29 @@ Revised: " } -@unpublished{JoshTriplett2009RPHash +@unpublished{PaulEMcKenney2009fastRTRCU +,Author="Paul E. McKenney" +,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}" +,month="July" +,day="23" +,year="2009" +,note="Available: +\url{http://lkml.org/lkml/2009/7/23/294} +[Viewed August 15, 2009]" +,annotation=" + First posting of simple and fast preemptable RCU. +" +} + +@InProceedings{JoshTriplett2009RPHash ,Author="Josh Triplett" ,Title="Scalable concurrent hash tables via relativistic programming" ,month="September" ,year="2009" -,note="Linux Plumbers Conference presentation" +,booktitle="Linux Plumbers Conference 2009" ,annotation=" RP fun with hash tables. + See also JoshTriplett2010RPHash " } @@ -872,4 +2141,323 @@ Revised: ,note="Available: \url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf} [Viewed December 9, 2009]" +,annotation={ + Chapter 6 (page 97) covers user-level RCU. +} +} + +@unpublished{RelativisticProgrammingWiki +,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole" +,Title="Relativistic Programming" +,month="September" +,year="2009" +,note="Available: +\url{http://wiki.cs.pdx.edu/rp/} +[Viewed December 9, 2009]" +,annotation=" + Main Relativistic Programming Wiki. +" +} + +@conference{PaulEMcKenney2009DeterministicRCU +,Author="Paul E. McKenney" +,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}" +,Booktitle="Eleventh Real Time Linux Workshop" +,month="September" +,year="2009" +,address="Dresden, Germany" +,note="Available: +\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf} +[Viewed January 14, 2009]" +} + +@unpublished{PaulEMcKenney2009HuntingHeisenbugs +,Author="Paul E. McKenney" +,Title="Hunting Heisenbugs" +,month="November" +,year="2009" +,day="1" +,note="Available: +\url{http://paulmck.livejournal.com/14639.html} +[Viewed June 4, 2010]" +,annotation=" + Day-one bug in Tree RCU that took forever to track down. +" +} + +@unpublished{MathieuDesnoyers2009defer:rcu +,Author="Mathieu Desnoyers" +,Title="Kernel RCU: shrink the size of the struct rcu\_head" +,month="December" +,year="2009" +,note="Available: +\url{http://lkml.org/lkml/2009/10/18/129} +[Viewed December 29, 2009]" +,annotation=" + Mathieu proposed defer_rcu() with fixed-size per-thread pool + of RCU callbacks. +" +} + +@unpublished{MathieuDesnoyers2009VerifPrePub +,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais" +,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms" +,month="December" +,year="2009" +,note="Submitted to IEEE TPDS" +,annotation=" + OOMem model for Mathieu's user-level RCU mechanical proof of + correctness. +" +} + +@unpublished{MathieuDesnoyers2009URCUPrePub +,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole" +,Title="User-Level Implementations of Read-Copy Update" +,month="December" +,year="2010" +,url=\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html} +,annotation=" + RCU overview, desiderata, semi-formal semantics, user-level RCU + usage scenarios, three classes of RCU implementation, wait-free + RCU updates, RCU grace-period batching, update overhead, + http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf + http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf + Superseded by MathieuDesnoyers2012URCU. +" +} + +@inproceedings{HariKannan2009DynamicAnalysisRCU +,author = {Kannan, Hari} +,title = {Ordering decoupled metadata accesses in multiprocessors} +,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture} +,year = {2009} +,isbn = {978-1-60558-798-1} +,pages = {381--390} +,location = {New York, New York} +,doi = {http://doi.acm.org/10.1145/1669112.1669161} +,publisher = {ACM} +,address = {New York, NY, USA} +,annotation={ + Uses RCU to protect metadata used in dynamic analysis. +}} + +@conference{PaulEMcKenney2010SimpleOptRCU +,Author="Paul E. McKenney" +,Title="Simplicity Through Optimization" +,Booktitle="linux.conf.au 2010" +,month="January" +,year="2010" +,address="Wellington, New Zealand" +,note="Available: +\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf} +[Viewed October 10, 2010]" +,annotation=" + TREE_PREEMPT_RCU optimizations greatly simplified the old + PREEMPT_RCU implementation. +" +} + +@unpublished{PaulEMcKenney2010LockdepRCU +,Author="Paul E. McKenney" +,Title="Lockdep-{RCU}" +,month="February" +,year="2010" +,day="1" +,note="Available: +\url{https://lwn.net/Articles/371986/} +[Viewed June 4, 2010]" +,annotation=" + CONFIG_PROVE_RCU, or at least an early version. +" +} + +@unpublished{AviKivity2010KVM2RCU +,Author="Avi Kivity" +,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64" +,month="February" +,year="2010" +,note="Available: +\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html} +[Viewed March 20, 2010]" +,annotation=" + Use of RCU permits KVM to increase the size of guest OSes from + 16 CPUs to 64 CPUs. +" +} + +@unpublished{HerbertXu2010RCUResizeHash +,Author="Herbert Xu" +,Title="bridge: Add core IGMP snooping support" +,month="February" +,year="2010" +,note="Available: +\url{http://kerneltrap.com/mailarchive/linux-netdev/2010/2/26/6270589} +[Viewed March 20, 2011]" +,annotation={ + Use a pair of list_head structures to support RCU-protected + resizable hash tables. +}} + +@article{JoshTriplett2010RPHash +,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole" +,title="Scalable Concurrent Hash Tables via Relativistic Programming" +,journal="ACM Operating Systems Review" +,year=2010 +,volume=44 +,number=3 +,month="July" +,annotation={ + RP fun with hash tables. + http://portal.acm.org/citation.cfm?id=1842733.1842750 +}} + +@unpublished{PaulEMcKenney2010RCUAPI +,Author="Paul E. McKenney" +,Title="The {RCU} {API}, 2010 Edition" +,month="December" +,day="8" +,year="2010" +,note="Available: +\url{http://lwn.net/Articles/418853/} +[Viewed December 8, 2010]" +,annotation=" + Includes updated software-engineering features. +" +} + +@mastersthesis{AndrejPodzimek2010masters +,author="Andrej Podzimek" +,title="Read-Copy-Update for OpenSolaris" +,school="Charles University in Prague" +,year="2010" +,note="Available: +\url{https://andrej.podzimek.org/thesis.pdf} +[Viewed January 31, 2011]" +,annotation={ + Reviews RCU implementations and creates a few for OpenSolaris. + Drives quiescent-state detection from RCU read-side primitives, + in a manner roughly similar to that of Jim Houston. +}} + +@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS +,Author="Linus Torvalds" +,Title="Linux 2.6.38-rc1" +,month="January" +,year="2011" +,note="Available: +\url{https://lkml.org/lkml/2011/1/18/322} +[Viewed March 4, 2011]" +,annotation={ + "The RCU-based name lookup is at the other end of the spectrum - the + absolute anti-gimmick. It's some seriously good stuff, and gets rid of + the last main global lock that really tends to hurt some kernel loads. + The dentry lock is no longer a big serializing issue. What's really + nice about it is that it actually improves performance a lot even for + single-threaded loads (on an SMP kernel), because it gets rid of some + of the most expensive parts of path component lookup, which was the + d_lock on every component lookup. So I'm seeing improvements of 30-50% + on some seriously pathname-lookup intensive loads." +}} + +@techreport{JoshTriplett2011RPScalableCorrectOrdering +,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole} +,title = {Scalable Correct Memory Ordering via Relativistic Programming} +,year = {2011} +,number = {11-03} +,institution = {Portland State University} +,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}} +} + +@inproceedings{PhilHoward2011RCUTMRBTree +,author = {Philip W. Howard and Jonathan Walpole} +,title = {A Relativistic Enhancement to Software Transactional Memory} +,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism} +,series = {HotPar'11} +,year = {2011} +,location = {Berkeley, CA} +,pages = {1--6} +,numpages = {6} +,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf} +,publisher = {USENIX Association} +,address = {Berkeley, CA, USA} +} + +@techreport{PaulEMcKenney2011cyclicparallelRCU +,author="Paul E. McKenney and Jonathan Walpole" +,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates" +,institution="US Patent and Trademark Office" +,address="Washington, DC" +,year="2011" +,number="US Patent 7,953,778" +,month="May" +,pages="34" +,annotation=" + Maintains an array of generation numbers to track in-flight + updates and keeps an additional level of indirection to allow + readers to confine themselves to the desired snapshot of the + data structure. +" +} + +@inproceedings{Triplett:2011:RPHash +,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan} +,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming} +,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference} +,month = {June} +,year = {2011} +,pages = {145--158} +,numpages = {14} +,url={http://www.usenix.org/event/atc11/tech/final_files/atc11_proceedings.pdf} +,publisher = {The USENIX Association} +,address = {Portland, OR USA} +} + +@unpublished{PaulEMcKenney2011RCU3.0trainwreck +,Author="Paul E. McKenney" +,Title="3.0 and {RCU:} what went wrong" +,month="July" +,day="27" +,year="2011" +,note="Available: +\url{http://lwn.net/Articles/453002/} +[Viewed July 27, 2011]" +,annotation=" + Analysis of the RCU trainwreck in Linux kernel 3.0. +" +} + +@unpublished{NeilBrown2011MeetTheLockers +,Author="Neil Brown" +,Title="Meet the Lockers" +,month="August" +,day="3" +,year="2011" +,note="Available: +\url{http://lwn.net/Articles/453685/} +[Viewed September 2, 2011]" +,annotation=" + The Locker family as an analogy for locking, reference counting, + RCU, and seqlock. +" +} + +@article{MathieuDesnoyers2012URCU +,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole" +,Title="User-Level Implementations of Read-Copy Update" +,journal="IEEE Transactions on Parallel and Distributed Systems" +,volume={23} +,year="2012" +,issn="1045-9219" +,pages="375-382" +,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159" +,publisher="IEEE Computer Society" +,address="Los Alamitos, CA, USA" +,annotation={ + RCU overview, desiderata, semi-formal semantics, user-level RCU + usage scenarios, three classes of RCU implementation, wait-free + RCU updates, RCU grace-period batching, update overhead, + http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf + http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf +} } diff --git a/Documentation/RCU/checklist.txt b/Documentation/RCU/checklist.txt index bff2d8be1e18..5c8d74968090 100644 --- a/Documentation/RCU/checklist.txt +++ b/Documentation/RCU/checklist.txt @@ -180,6 +180,20 @@ over a rather long period of time, but improvements are always welcome! operations that would not normally be undertaken while a real-time workload is running. + In particular, if you find yourself invoking one of the expedited + primitives repeatedly in a loop, please do everyone a favor: + Restructure your code so that it batches the updates, allowing + a single non-expedited primitive to cover the entire batch. + This will very likely be faster than the loop containing the + expedited primitive, and will be much much easier on the rest + of the system, especially to real-time workloads running on + the rest of the system. + + In addition, it is illegal to call the expedited forms from + a CPU-hotplug notifier, or while holding a lock that is acquired + by a CPU-hotplug notifier. Failing to observe this restriction + will result in deadlock. + 7. If the updater uses call_rcu() or synchronize_rcu(), then the corresponding readers must use rcu_read_lock() and rcu_read_unlock(). If the updater uses call_rcu_bh() or diff --git a/Documentation/RCU/stallwarn.txt b/Documentation/RCU/stallwarn.txt index 083d88cbc089..523364e4e1f1 100644 --- a/Documentation/RCU/stallwarn.txt +++ b/Documentation/RCU/stallwarn.txt @@ -12,14 +12,38 @@ CONFIG_RCU_CPU_STALL_TIMEOUT This kernel configuration parameter defines the period of time that RCU will wait from the beginning of a grace period until it issues an RCU CPU stall warning. This time period is normally - ten seconds. + sixty seconds. -RCU_SECONDS_TILL_STALL_RECHECK + This configuration parameter may be changed at runtime via the + /sys/module/rcutree/parameters/rcu_cpu_stall_timeout, however + this parameter is checked only at the beginning of a cycle. + So if you are 30 seconds into a 70-second stall, setting this + sysfs parameter to (say) five will shorten the timeout for the + -next- stall, or the following warning for the current stall + (assuming the stall lasts long enough). It will not affect the + timing of the next warning for the current stall. - This macro defines the period of time that RCU will wait after - issuing a stall warning until it issues another stall warning - for the same stall. This time period is normally set to three - times the check interval plus thirty seconds. + Stall-warning messages may be enabled and disabled completely via + /sys/module/rcutree/parameters/rcu_cpu_stall_suppress. + +CONFIG_RCU_CPU_STALL_VERBOSE + + This kernel configuration parameter causes the stall warning to + also dump the stacks of any tasks that are blocking the current + RCU-preempt grace period. + +RCU_CPU_STALL_INFO + + This kernel configuration parameter causes the stall warning to + print out additional per-CPU diagnostic information, including + information on scheduling-clock ticks and RCU's idle-CPU tracking. + +RCU_STALL_DELAY_DELTA + + Although the lockdep facility is extremely useful, it does add + some overhead. Therefore, under CONFIG_PROVE_RCU, the + RCU_STALL_DELAY_DELTA macro allows five extra seconds before + giving an RCU CPU stall warning message. RCU_STALL_RAT_DELAY @@ -64,6 +88,54 @@ INFO: rcu_bh_state detected stalls on CPUs/tasks: { } (detected by 4, 2502 jiffi This is rare, but does happen from time to time in real life. +If the CONFIG_RCU_CPU_STALL_INFO kernel configuration parameter is set, +more information is printed with the stall-warning message, for example: + + INFO: rcu_preempt detected stall on CPU + 0: (63959 ticks this GP) idle=241/3fffffffffffffff/0 + (t=65000 jiffies) + +In kernels with CONFIG_RCU_FAST_NO_HZ, even more information is +printed: + + INFO: rcu_preempt detected stall on CPU + 0: (64628 ticks this GP) idle=dd5/3fffffffffffffff/0 drain=0 . timer=-1 + (t=65000 jiffies) + +The "(64628 ticks this GP)" indicates that this CPU has taken more +than 64,000 scheduling-clock interrupts during the current stalled +grace period. If the CPU was not yet aware of the current grace +period (for example, if it was offline), then this part of the message +indicates how many grace periods behind the CPU is. + +The "idle=" portion of the message prints the dyntick-idle state. +The hex number before the first "/" is the low-order 12 bits of the +dynticks counter, which will have an even-numbered value if the CPU is +in dyntick-idle mode and an odd-numbered value otherwise. The hex +number between the two "/"s is the value of the nesting, which will +be a small positive number if in the idle loop and a very large positive +number (as shown above) otherwise. + +For CONFIG_RCU_FAST_NO_HZ kernels, the "drain=0" indicates that the +CPU is not in the process of trying to force itself into dyntick-idle +state, the "." indicates that the CPU has not given up forcing RCU +into dyntick-idle mode (it would be "H" otherwise), and the "timer=-1" +indicates that the CPU has not recented forced RCU into dyntick-idle +mode (it would otherwise indicate the number of microseconds remaining +in this forced state). + + +Multiple Warnings From One Stall + +If a stall lasts long enough, multiple stall-warning messages will be +printed for it. The second and subsequent messages are printed at +longer intervals, so that the time between (say) the first and second +message will be about three times the interval between the beginning +of the stall and the first message. + + +What Causes RCU CPU Stall Warnings? + So your kernel printed an RCU CPU stall warning. The next question is "What caused it?" The following problems can result in RCU CPU stall warnings: @@ -128,4 +200,5 @@ is occurring, which will usually be in the function nearest the top of that portion of the stack which remains the same from trace to trace. If you can reliably trigger the stall, ftrace can be quite helpful. -RCU bugs can often be debugged with the help of CONFIG_RCU_TRACE. +RCU bugs can often be debugged with the help of CONFIG_RCU_TRACE +and with RCU's event tracing. diff --git a/Documentation/RCU/torture.txt b/Documentation/RCU/torture.txt index d67068d0d2b9..375d3fb71437 100644 --- a/Documentation/RCU/torture.txt +++ b/Documentation/RCU/torture.txt @@ -69,6 +69,13 @@ onoff_interval CPU-hotplug operations regardless of what value is specified for onoff_interval. +onoff_holdoff The number of seconds to wait until starting CPU-hotplug + operations. This would normally only be used when + rcutorture was built into the kernel and started + automatically at boot time, in which case it is useful + in order to avoid confusing boot-time code with CPUs + coming and going. + shuffle_interval The number of seconds to keep the test threads affinitied to a particular subset of the CPUs, defaults to 3 seconds. @@ -79,6 +86,24 @@ shutdown_secs The number of seconds to run the test before terminating zero, which disables test termination and system shutdown. This capability is useful for automated testing. +stall_cpu The number of seconds that a CPU should be stalled while + within both an rcu_read_lock() and a preempt_disable(). + This stall happens only once per rcutorture run. + If you need multiple stalls, use modprobe and rmmod to + repeatedly run rcutorture. The default for stall_cpu + is zero, which prevents rcutorture from stalling a CPU. + + Note that attempts to rmmod rcutorture while the stall + is ongoing will hang, so be careful what value you + choose for this module parameter! In addition, too-large + values for stall_cpu might well induce failures and + warnings in other parts of the kernel. You have been + warned! + +stall_cpu_holdoff + The number of seconds to wait after rcutorture starts + before stalling a CPU. Defaults to 10 seconds. + stat_interval The number of seconds between output of torture statistics (via printk()). Regardless of the interval, statistics are printed when the module is unloaded. @@ -271,11 +296,13 @@ The following script may be used to torture RCU: #!/bin/sh modprobe rcutorture - sleep 100 + sleep 3600 rmmod rcutorture dmesg | grep torture: The output can be manually inspected for the error flag of "!!!". One could of course create a more elaborate script that automatically -checked for such errors. The "rmmod" command forces a "SUCCESS" or -"FAILURE" indication to be printk()ed. +checked for such errors. The "rmmod" command forces a "SUCCESS", +"FAILURE", or "RCU_HOTPLUG" indication to be printk()ed. The first +two are self-explanatory, while the last indicates that while there +were no RCU failures, CPU-hotplug problems were detected. diff --git a/Documentation/RCU/trace.txt b/Documentation/RCU/trace.txt index 49587abfc2f7..f6f15ce39903 100644 --- a/Documentation/RCU/trace.txt +++ b/Documentation/RCU/trace.txt @@ -33,23 +33,23 @@ rcu/rcuboost: The output of "cat rcu/rcudata" looks as follows: rcu_sched: - 0 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=545/1/0 df=50 of=0 ri=0 ql=163 qs=NRW. kt=0/W/0 ktl=ebc3 b=10 ci=153737 co=0 ca=0 - 1 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=967/1/0 df=58 of=0 ri=0 ql=634 qs=NRW. kt=0/W/1 ktl=58c b=10 ci=191037 co=0 ca=0 - 2 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=1081/1/0 df=175 of=0 ri=0 ql=74 qs=N.W. kt=0/W/2 ktl=da94 b=10 ci=75991 co=0 ca=0 - 3 c=20942 g=20943 pq=1 pgp=20942 qp=1 dt=1846/0/0 df=404 of=0 ri=0 ql=0 qs=.... kt=0/W/3 ktl=d1cd b=10 ci=72261 co=0 ca=0 - 4 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=369/1/0 df=83 of=0 ri=0 ql=48 qs=N.W. kt=0/W/4 ktl=e0e7 b=10 ci=128365 co=0 ca=0 - 5 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=381/1/0 df=64 of=0 ri=0 ql=169 qs=NRW. kt=0/W/5 ktl=fb2f b=10 ci=164360 co=0 ca=0 - 6 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=1037/1/0 df=183 of=0 ri=0 ql=62 qs=N.W. kt=0/W/6 ktl=d2ad b=10 ci=65663 co=0 ca=0 - 7 c=20897 g=20897 pq=1 pgp=20896 qp=0 dt=1572/0/0 df=382 of=0 ri=0 ql=0 qs=.... kt=0/W/7 ktl=cf15 b=10 ci=75006 co=0 ca=0 + 0 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=545/1/0 df=50 of=0 ql=163 qs=NRW. kt=0/W/0 ktl=ebc3 b=10 ci=153737 co=0 ca=0 + 1 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=967/1/0 df=58 of=0 ql=634 qs=NRW. kt=0/W/1 ktl=58c b=10 ci=191037 co=0 ca=0 + 2 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=1081/1/0 df=175 of=0 ql=74 qs=N.W. kt=0/W/2 ktl=da94 b=10 ci=75991 co=0 ca=0 + 3 c=20942 g=20943 pq=1 pgp=20942 qp=1 dt=1846/0/0 df=404 of=0 ql=0 qs=.... kt=0/W/3 ktl=d1cd b=10 ci=72261 co=0 ca=0 + 4 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=369/1/0 df=83 of=0 ql=48 qs=N.W. kt=0/W/4 ktl=e0e7 b=10 ci=128365 co=0 ca=0 + 5 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=381/1/0 df=64 of=0 ql=169 qs=NRW. kt=0/W/5 ktl=fb2f b=10 ci=164360 co=0 ca=0 + 6 c=20972 g=20973 pq=1 pgp=20973 qp=0 dt=1037/1/0 df=183 of=0 ql=62 qs=N.W. kt=0/W/6 ktl=d2ad b=10 ci=65663 co=0 ca=0 + 7 c=20897 g=20897 pq=1 pgp=20896 qp=0 dt=1572/0/0 df=382 of=0 ql=0 qs=.... kt=0/W/7 ktl=cf15 b=10 ci=75006 co=0 ca=0 rcu_bh: - 0 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=545/1/0 df=6 of=0 ri=1 ql=0 qs=.... kt=0/W/0 ktl=ebc3 b=10 ci=0 co=0 ca=0 - 1 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=967/1/0 df=3 of=0 ri=1 ql=0 qs=.... kt=0/W/1 ktl=58c b=10 ci=151 co=0 ca=0 - 2 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=1081/1/0 df=6 of=0 ri=1 ql=0 qs=.... kt=0/W/2 ktl=da94 b=10 ci=0 co=0 ca=0 - 3 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=1846/0/0 df=8 of=0 ri=1 ql=0 qs=.... kt=0/W/3 ktl=d1cd b=10 ci=0 co=0 ca=0 - 4 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=369/1/0 df=6 of=0 ri=1 ql=0 qs=.... kt=0/W/4 ktl=e0e7 b=10 ci=0 co=0 ca=0 - 5 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=381/1/0 df=4 of=0 ri=1 ql=0 qs=.... kt=0/W/5 ktl=fb2f b=10 ci=0 co=0 ca=0 - 6 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=1037/1/0 df=6 of=0 ri=1 ql=0 qs=.... kt=0/W/6 ktl=d2ad b=10 ci=0 co=0 ca=0 - 7 c=1474 g=1474 pq=1 pgp=1473 qp=0 dt=1572/0/0 df=8 of=0 ri=1 ql=0 qs=.... kt=0/W/7 ktl=cf15 b=10 ci=0 co=0 ca=0 + 0 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=545/1/0 df=6 of=0 ql=0 qs=.... kt=0/W/0 ktl=ebc3 b=10 ci=0 co=0 ca=0 + 1 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=967/1/0 df=3 of=0 ql=0 qs=.... kt=0/W/1 ktl=58c b=10 ci=151 co=0 ca=0 + 2 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=1081/1/0 df=6 of=0 ql=0 qs=.... kt=0/W/2 ktl=da94 b=10 ci=0 co=0 ca=0 + 3 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=1846/0/0 df=8 of=0 ql=0 qs=.... kt=0/W/3 ktl=d1cd b=10 ci=0 co=0 ca=0 + 4 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=369/1/0 df=6 of=0 ql=0 qs=.... kt=0/W/4 ktl=e0e7 b=10 ci=0 co=0 ca=0 + 5 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=381/1/0 df=4 of=0 ql=0 qs=.... kt=0/W/5 ktl=fb2f b=10 ci=0 co=0 ca=0 + 6 c=1480 g=1480 pq=1 pgp=1480 qp=0 dt=1037/1/0 df=6 of=0 ql=0 qs=.... kt=0/W/6 ktl=d2ad b=10 ci=0 co=0 ca=0 + 7 c=1474 g=1474 pq=1 pgp=1473 qp=0 dt=1572/0/0 df=8 of=0 ql=0 qs=.... kt=0/W/7 ktl=cf15 b=10 ci=0 co=0 ca=0 The first section lists the rcu_data structures for rcu_sched, the second for rcu_bh. Note that CONFIG_TREE_PREEMPT_RCU kernels will have an @@ -119,10 +119,6 @@ o "of" is the number of times that some other CPU has forced a CPU is offline when it is really alive and kicking) is a fatal error, so it makes sense to err conservatively. -o "ri" is the number of times that RCU has seen fit to send a - reschedule IPI to this CPU in order to get it to report a - quiescent state. - o "ql" is the number of RCU callbacks currently residing on this CPU. This is the total number of callbacks, regardless of what state they are in (new, waiting for grace period to diff --git a/Documentation/cgroups/cgroups.txt b/Documentation/cgroups/cgroups.txt index a7c96ae5557c..8e74980ab385 100644 --- a/Documentation/cgroups/cgroups.txt +++ b/Documentation/cgroups/cgroups.txt @@ -558,8 +558,7 @@ Each subsystem may export the following methods. The only mandatory methods are create/destroy. Any others that are null are presumed to be successful no-ops. -struct cgroup_subsys_state *create(struct cgroup_subsys *ss, - struct cgroup *cgrp) +struct cgroup_subsys_state *create(struct cgroup *cgrp) (cgroup_mutex held by caller) Called to create a subsystem state object for a cgroup. The @@ -574,7 +573,7 @@ identified by the passed cgroup object having a NULL parent (since it's the root of the hierarchy) and may be an appropriate place for initialization code. -void destroy(struct cgroup_subsys *ss, struct cgroup *cgrp) +void destroy(struct cgroup *cgrp) (cgroup_mutex held by caller) The cgroup system is about to destroy the passed cgroup; the subsystem @@ -585,7 +584,7 @@ cgroup->parent is still valid. (Note - can also be called for a newly-created cgroup if an error occurs after this subsystem's create() method has been called for the new cgroup). -int pre_destroy(struct cgroup_subsys *ss, struct cgroup *cgrp); +int pre_destroy(struct cgroup *cgrp); Called before checking the reference count on each subsystem. This may be useful for subsystems which have some extra references even if @@ -593,8 +592,7 @@ there are not tasks in the cgroup. If pre_destroy() returns error code, rmdir() will fail with it. From this behavior, pre_destroy() can be called multiple times against a cgroup. -int can_attach(struct cgroup_subsys *ss, struct cgroup *cgrp, - struct cgroup_taskset *tset) +int can_attach(struct cgroup *cgrp, struct cgroup_taskset *tset) (cgroup_mutex held by caller) Called prior to moving one or more tasks into a cgroup; if the @@ -615,8 +613,7 @@ fork. If this method returns 0 (success) then this should remain valid while the caller holds cgroup_mutex and it is ensured that either attach() or cancel_attach() will be called in future. -void cancel_attach(struct cgroup_subsys *ss, struct cgroup *cgrp, - struct cgroup_taskset *tset) +void cancel_attach(struct cgroup *cgrp, struct cgroup_taskset *tset) (cgroup_mutex held by caller) Called when a task attach operation has failed after can_attach() has succeeded. @@ -625,23 +622,22 @@ function, so that the subsystem can implement a rollback. If not, not necessary. This will be called only about subsystems whose can_attach() operation have succeeded. The parameters are identical to can_attach(). -void attach(struct cgroup_subsys *ss, struct cgroup *cgrp, - struct cgroup_taskset *tset) +void attach(struct cgroup *cgrp, struct cgroup_taskset *tset) (cgroup_mutex held by caller) Called after the task has been attached to the cgroup, to allow any post-attachment activity that requires memory allocations or blocking. The parameters are identical to can_attach(). -void fork(struct cgroup_subsy *ss, struct task_struct *task) +void fork(struct task_struct *task) Called when a task is forked into a cgroup. -void exit(struct cgroup_subsys *ss, struct task_struct *task) +void exit(struct task_struct *task) Called during task exit. -int populate(struct cgroup_subsys *ss, struct cgroup *cgrp) +int populate(struct cgroup *cgrp) (cgroup_mutex held by caller) Called after creation of a cgroup to allow a subsystem to populate @@ -651,7 +647,7 @@ include/linux/cgroup.h for details). Note that although this method can return an error code, the error code is currently not always handled well. -void post_clone(struct cgroup_subsys *ss, struct cgroup *cgrp) +void post_clone(struct cgroup *cgrp) (cgroup_mutex held by caller) Called during cgroup_create() to do any parameter @@ -659,7 +655,7 @@ initialization which might be required before a task could attach. For example in cpusets, no task may attach before 'cpus' and 'mems' are set up. -void bind(struct cgroup_subsys *ss, struct cgroup *root) +void bind(struct cgroup *root) (cgroup_mutex and ss->hierarchy_mutex held by caller) Called when a cgroup subsystem is rebound to a different hierarchy diff --git a/Documentation/devicetree/bindings/gpio/led.txt b/Documentation/devicetree/bindings/gpio/led.txt index 141087cf3107..fd2bd56e7195 100644 --- a/Documentation/devicetree/bindings/gpio/led.txt +++ b/Documentation/devicetree/bindings/gpio/led.txt @@ -7,9 +7,9 @@ Each LED is represented as a sub-node of the gpio-leds device. Each node's name represents the name of the corresponding LED. LED sub-node properties: -- gpios : Should specify the LED's GPIO, see "Specifying GPIO information - for devices" in Documentation/devicetree/booting-without-of.txt. Active - low LEDs should be indicated using flags in the GPIO specifier. +- gpios : Should specify the LED's GPIO, see "gpios property" in + Documentation/devicetree/gpio.txt. Active low LEDs should be + indicated using flags in the GPIO specifier. - label : (optional) The label for this LED. If omitted, the label is taken from the node name (excluding the unit address). - linux,default-trigger : (optional) This parameter, if present, is a diff --git a/Documentation/devicetree/bindings/net/stmmac.txt b/Documentation/devicetree/bindings/net/stmmac.txt new file mode 100644 index 000000000000..1f62623f8c3f --- /dev/null +++ b/Documentation/devicetree/bindings/net/stmmac.txt @@ -0,0 +1,28 @@ +* STMicroelectronics 10/100/1000 Ethernet driver (GMAC) + +Required properties: +- compatible: Should be "st,spear600-gmac" +- reg: Address and length of the register set for the device +- interrupt-parent: Should be the phandle for the interrupt controller + that services interrupts for this device +- interrupts: Should contain the STMMAC interrupts +- interrupt-names: Should contain the interrupt names "macirq" + "eth_wake_irq" if this interrupt is supported in the "interrupts" + property +- phy-mode: String, operation mode of the PHY interface. + Supported values are: "mii", "rmii", "gmii", "rgmii". + +Optional properties: +- mac-address: 6 bytes, mac address + +Examples: + + gmac0: ethernet@e0800000 { + compatible = "st,spear600-gmac"; + reg = <0xe0800000 0x8000>; + interrupt-parent = <&vic1>; + interrupts = <24 23>; + interrupt-names = "macirq", "eth_wake_irq"; + mac-address = [000000000000]; /* Filled in by U-Boot */ + phy-mode = "gmii"; + }; diff --git a/Documentation/devicetree/bindings/tty/serial/efm32-uart.txt b/Documentation/devicetree/bindings/tty/serial/efm32-uart.txt new file mode 100644 index 000000000000..6588b6950a7f --- /dev/null +++ b/Documentation/devicetree/bindings/tty/serial/efm32-uart.txt @@ -0,0 +1,14 @@ +* Energymicro efm32 UART + +Required properties: +- compatible : Should be "efm32,uart" +- reg : Address and length of the register set +- interrupts : Should contain uart interrupt + +Example: + +uart@0x4000c400 { + compatible = "efm32,uart"; + reg = <0x4000c400 0x400>; + interrupts = <15>; +}; diff --git a/Documentation/devicetree/bindings/vendor-prefixes.txt b/Documentation/devicetree/bindings/vendor-prefixes.txt index ecc6a6cd26c1..a20008ab319a 100644 --- a/Documentation/devicetree/bindings/vendor-prefixes.txt +++ b/Documentation/devicetree/bindings/vendor-prefixes.txt @@ -30,6 +30,7 @@ national National Semiconductor nintendo Nintendo nvidia NVIDIA nxp NXP Semiconductors +picochip Picochip Ltd powervr Imagination Technologies qcom Qualcomm, Inc. ramtron Ramtron International diff --git a/Documentation/dynamic-debug-howto.txt b/Documentation/dynamic-debug-howto.txt index f959909d7154..74e6c7782678 100644 --- a/Documentation/dynamic-debug-howto.txt +++ b/Documentation/dynamic-debug-howto.txt @@ -12,7 +12,7 @@ dynamically enabled per-callsite. Dynamic debug has even more useful features: * Simple query language allows turning on and off debugging statements by - matching any combination of: + matching any combination of 0 or 1 of: - source filename - function name @@ -79,31 +79,24 @@ Command Language Reference ========================== At the lexical level, a command comprises a sequence of words separated -by whitespace characters. Note that newlines are treated as word -separators and do *not* end a command or allow multiple commands to -be done together. So these are all equivalent: +by spaces or tabs. So these are all equivalent: nullarbor:~ # echo -c 'file svcsock.c line 1603 +p' > <debugfs>/dynamic_debug/control nullarbor:~ # echo -c ' file svcsock.c line 1603 +p ' > <debugfs>/dynamic_debug/control -nullarbor:~ # echo -c 'file svcsock.c\nline 1603 +p' > - <debugfs>/dynamic_debug/control nullarbor:~ # echo -n 'file svcsock.c line 1603 +p' > <debugfs>/dynamic_debug/control -Commands are bounded by a write() system call. If you want to do -multiple commands you need to do a separate "echo" for each, like: +Command submissions are bounded by a write() system call. +Multiple commands can be written together, separated by ';' or '\n'. -nullarbor:~ # echo 'file svcsock.c line 1603 +p' > /proc/dprintk ;\ -> echo 'file svcsock.c line 1563 +p' > /proc/dprintk + ~# echo "func pnpacpi_get_resources +p; func pnp_assign_mem +p" \ + > <debugfs>/dynamic_debug/control -or even like: +If your query set is big, you can batch them too: -nullarbor:~ # ( -> echo 'file svcsock.c line 1603 +p' ;\ -> echo 'file svcsock.c line 1563 +p' ;\ -> ) > /proc/dprintk + ~# cat query-batch-file > <debugfs>/dynamic_debug/control At the syntactical level, a command comprises a sequence of match specifications, followed by a flags change specification. @@ -144,11 +137,12 @@ func func svc_tcp_accept file - The given string is compared against either the full - pathname or the basename of the source file of each - callsite. Examples: + The given string is compared against either the full pathname, the + src-root relative pathname, or the basename of the source file of + each callsite. Examples: file svcsock.c + file kernel/freezer.c file /usr/src/packages/BUILD/sgi-enhancednfs-1.4/default/net/sunrpc/svcsock.c module diff --git a/Documentation/feature-removal-schedule.txt b/Documentation/feature-removal-schedule.txt index a0ffac029a0d..d5dc80f30352 100644 --- a/Documentation/feature-removal-schedule.txt +++ b/Documentation/feature-removal-schedule.txt @@ -524,3 +524,14 @@ Files: arch/arm/mach-at91/at91cap9.c Why: The code is not actively maintained and platforms are now hard to find. Who: Nicolas Ferre <nicolas.ferre@atmel.com> Jean-Christophe PLAGNIOL-VILLARD <plagnioj@jcrosoft.com> + +---------------------------- + +What: Low Performance USB Block driver ("CONFIG_BLK_DEV_UB") +When: 3.6 +Why: This driver provides support for USB storage devices like "USB + sticks". As of now, it is deactivated in Debian, Fedora and + Ubuntu. All current users can switch over to usb-storage + (CONFIG_USB_STORAGE) which only drawback is the additional SCSI + stack. +Who: Sebastian Andrzej Siewior <sebastian@breakpoint.cc> diff --git a/Documentation/filesystems/debugfs.txt b/Documentation/filesystems/debugfs.txt index 6872c91bce35..4e2575873187 100644 --- a/Documentation/filesystems/debugfs.txt +++ b/Documentation/filesystems/debugfs.txt @@ -14,7 +14,10 @@ Debugfs is typically mounted with a command like: mount -t debugfs none /sys/kernel/debug -(Or an equivalent /etc/fstab line). +(Or an equivalent /etc/fstab line). +The debugfs root directory is accessible by anyone by default. To +restrict access to the tree the "uid", "gid" and "mode" mount +options can be used. Note that the debugfs API is exported GPL-only to modules. diff --git a/Documentation/hwmon/jc42 b/Documentation/hwmon/jc42 index a22ecf48f255..52729a756c1b 100644 --- a/Documentation/hwmon/jc42 +++ b/Documentation/hwmon/jc42 @@ -7,21 +7,29 @@ Supported chips: Addresses scanned: I2C 0x18 - 0x1f Datasheets: http://www.analog.com/static/imported-files/data_sheets/ADT7408.pdf - * IDT TSE2002B3, TS3000B3 - Prefix: 'tse2002b3', 'ts3000b3' + * Atmel AT30TS00 + Prefix: 'at30ts00' Addresses scanned: I2C 0x18 - 0x1f Datasheets: - http://www.idt.com/products/getdoc.cfm?docid=18715691 - http://www.idt.com/products/getdoc.cfm?docid=18715692 + http://www.atmel.com/Images/doc8585.pdf + * IDT TSE2002B3, TSE2002GB2, TS3000B3, TS3000GB2 + Prefix: 'tse2002', 'ts3000' + Addresses scanned: I2C 0x18 - 0x1f + Datasheets: + http://www.idt.com/sites/default/files/documents/IDT_TSE2002B3C_DST_20100512_120303152056.pdf + http://www.idt.com/sites/default/files/documents/IDT_TSE2002GB2A1_DST_20111107_120303145914.pdf + http://www.idt.com/sites/default/files/documents/IDT_TS3000B3A_DST_20101129_120303152013.pdf + http://www.idt.com/sites/default/files/documents/IDT_TS3000GB2A1_DST_20111104_120303151012.pdf * Maxim MAX6604 Prefix: 'max6604' Addresses scanned: I2C 0x18 - 0x1f Datasheets: http://datasheets.maxim-ic.com/en/ds/MAX6604.pdf - * Microchip MCP9805, MCP98242, MCP98243, MCP9843 - Prefixes: 'mcp9805', 'mcp98242', 'mcp98243', 'mcp9843' + * Microchip MCP9804, MCP9805, MCP98242, MCP98243, MCP9843 + Prefixes: 'mcp9804', 'mcp9805', 'mcp98242', 'mcp98243', 'mcp9843' Addresses scanned: I2C 0x18 - 0x1f Datasheets: + http://ww1.microchip.com/downloads/en/DeviceDoc/22203C.pdf http://ww1.microchip.com/downloads/en/DeviceDoc/21977b.pdf http://ww1.microchip.com/downloads/en/DeviceDoc/21996a.pdf http://ww1.microchip.com/downloads/en/DeviceDoc/22153c.pdf @@ -48,6 +56,12 @@ Supported chips: Datasheets: http://www.st.com/stonline/products/literature/ds/13447/stts424.pdf http://www.st.com/stonline/products/literature/ds/13448/stts424e02.pdf + * ST Microelectronics STTS2002, STTS3000 + Prefix: 'stts2002', 'stts3000' + Addresses scanned: I2C 0x18 - 0x1f + Datasheets: + http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATASHEET/CD00225278.pdf + http://www.st.com/internet/com/TECHNICAL_RESOURCES/TECHNICAL_LITERATURE/DATA_BRIEF/CD00270920.pdf * JEDEC JC 42.4 compliant temperature sensor chips Prefix: 'jc42' Addresses scanned: I2C 0x18 - 0x1f diff --git a/Documentation/hwmon/w83627ehf b/Documentation/hwmon/w83627ehf index 3f44dbdfda70..ceaf6f652b00 100644 --- a/Documentation/hwmon/w83627ehf +++ b/Documentation/hwmon/w83627ehf @@ -50,7 +50,7 @@ W83627DHG, W83627DHG-P, W83627UHG, W83667HG, W83667HG-B, W83667HG-I (NCT6775F), and NCT6776F super I/O chips. We will refer to them collectively as Winbond chips. -The chips implement 2 to 4 temperature sensors (9 for NCT6775F and NCT6776F), +The chips implement 3 to 4 temperature sensors (9 for NCT6775F and NCT6776F), 2 to 5 fan rotation speed sensors, 8 to 10 analog voltage sensors, one VID (except for 627UHG), alarms with beep warnings (control unimplemented), and some automatic fan regulation strategies (plus manual fan control mode). @@ -143,8 +143,13 @@ pwm[1-4]_min_output - minimum fan speed (range 1 - 255), when the temperature pwm[1-4]_stop_time - how many milliseconds [ms] must elapse to switch corresponding fan off. (when the temperature was below defined range). +pwm[1-4]_start_output-minimum fan speed (range 1 - 255) when spinning up +pwm[1-4]_step_output- rate of fan speed change (1 - 255) +pwm[1-4]_stop_output- minimum fan speed (range 1 - 255) when spinning down +pwm[1-4]_max_output - maximum fan speed (range 1 - 255), when the temperature + is above defined range. -Note: last two functions are influenced by other control bits, not yet exported +Note: last six functions are influenced by other control bits, not yet exported by the driver, so a change might not have any effect. Implementation Details diff --git a/Documentation/hwmon/zl6100 b/Documentation/hwmon/zl6100 index 5865a2470d4a..98ebacbdd8d9 100644 --- a/Documentation/hwmon/zl6100 +++ b/Documentation/hwmon/zl6100 @@ -88,14 +88,12 @@ Module parameters delay ----- -Some Intersil/Zilker Labs DC-DC controllers require a minimum interval between -I2C bus accesses. According to Intersil, the minimum interval is 2 ms, though -1 ms appears to be sufficient and has not caused any problems in testing. -The problem is known to affect ZL6100, ZL2105, and ZL2008. It is known not to -affect ZL2004 and ZL6105. The driver automatically sets the interval to 1 ms -except for ZL2004 and ZL6105. To enable manual override, the driver provides a -writeable module parameter, 'delay', which can be used to set the interval to -a value between 0 and 65,535 microseconds. +Intersil/Zilker Labs DC-DC controllers require a minimum interval between I2C +bus accesses. According to Intersil, the minimum interval is 2 ms, though 1 ms +appears to be sufficient and has not caused any problems in testing. The problem +is known to affect all currently supported chips. For manual override, the +driver provides a writeable module parameter, 'delay', which can be used to set +the interval to a value between 0 and 65,535 microseconds. Sysfs entries diff --git a/Documentation/i2c/instantiating-devices b/Documentation/i2c/instantiating-devices index 9edb75d8c9b9..abf63615ee05 100644 --- a/Documentation/i2c/instantiating-devices +++ b/Documentation/i2c/instantiating-devices @@ -87,11 +87,11 @@ it may have different addresses from one board to the next (manufacturer changing its design without notice). In this case, you can call i2c_new_probed_device() instead of i2c_new_device(). -Example (from the pnx4008 OHCI driver): +Example (from the nxp OHCI driver): static const unsigned short normal_i2c[] = { 0x2c, 0x2d, I2C_CLIENT_END }; -static int __devinit usb_hcd_pnx4008_probe(struct platform_device *pdev) +static int __devinit usb_hcd_nxp_probe(struct platform_device *pdev) { (...) struct i2c_adapter *i2c_adap; @@ -100,7 +100,7 @@ static int __devinit usb_hcd_pnx4008_probe(struct platform_device *pdev) (...) i2c_adap = i2c_get_adapter(2); memset(&i2c_info, 0, sizeof(struct i2c_board_info)); - strlcpy(i2c_info.type, "isp1301_pnx", I2C_NAME_SIZE); + strlcpy(i2c_info.type, "isp1301_nxp", I2C_NAME_SIZE); isp1301_i2c_client = i2c_new_probed_device(i2c_adap, &i2c_info, normal_i2c, NULL); i2c_put_adapter(i2c_adap); diff --git a/Documentation/input/alps.txt b/Documentation/input/alps.txt index 9c407f01d74f..ae8ba9a74ce1 100644 --- a/Documentation/input/alps.txt +++ b/Documentation/input/alps.txt @@ -13,7 +13,8 @@ Detection All ALPS touchpads should respond to the "E6 report" command sequence: E8-E6-E6-E6-E9. An ALPS touchpad should respond with either 00-00-0A or -00-00-64. +00-00-64 if no buttons are pressed. The bits 0-2 of the first byte will be 1s +if some buttons are pressed. If the E6 report is successful, the touchpad model is identified using the "E7 report" sequence: E8-E7-E7-E7-E9. The response is the model signature and is diff --git a/Documentation/input/event-codes.txt b/Documentation/input/event-codes.txt index 23fcb05175be..53305bd08182 100644 --- a/Documentation/input/event-codes.txt +++ b/Documentation/input/event-codes.txt @@ -17,11 +17,11 @@ reports supported by a device are also provided by sysfs in class/input/event*/device/capabilities/, and the properties of a device are provided in class/input/event*/device/properties. -Types: -========== -Types are groupings of codes under a logical input construct. Each type has a -set of applicable codes to be used in generating events. See the Codes section -for details on valid codes for each type. +Event types: +=========== +Event types are groupings of codes under a logical input construct. Each +type has a set of applicable codes to be used in generating events. See the +Codes section for details on valid codes for each type. * EV_SYN: - Used as markers to separate events. Events may be separated in time or in @@ -63,9 +63,9 @@ for details on valid codes for each type. * EV_FF_STATUS: - Used to receive force feedback device status. -Codes: -========== -Codes define the precise type of event. +Event codes: +=========== +Event codes define the precise type of event. EV_SYN: ---------- @@ -220,6 +220,56 @@ EV_PWR: EV_PWR events are a special type of event used specifically for power mangement. Its usage is not well defined. To be addressed later. +Device properties: +================= +Normally, userspace sets up an input device based on the data it emits, +i.e., the event types. In the case of two devices emitting the same event +types, additional information can be provided in the form of device +properties. + +INPUT_PROP_DIRECT + INPUT_PROP_POINTER: +-------------------------------------- +The INPUT_PROP_DIRECT property indicates that device coordinates should be +directly mapped to screen coordinates (not taking into account trivial +transformations, such as scaling, flipping and rotating). Non-direct input +devices require non-trivial transformation, such as absolute to relative +transformation for touchpads. Typical direct input devices: touchscreens, +drawing tablets; non-direct devices: touchpads, mice. + +The INPUT_PROP_POINTER property indicates that the device is not transposed +on the screen and thus requires use of an on-screen pointer to trace user's +movements. Typical pointer devices: touchpads, tablets, mice; non-pointer +device: touchscreen. + +If neither INPUT_PROP_DIRECT or INPUT_PROP_POINTER are set, the property is +considered undefined and the device type should be deduced in the +traditional way, using emitted event types. + +INPUT_PROP_BUTTONPAD: +-------------------- +For touchpads where the button is placed beneath the surface, such that +pressing down on the pad causes a button click, this property should be +set. Common in clickpad notebooks and macbooks from 2009 and onwards. + +Originally, the buttonpad property was coded into the bcm5974 driver +version field under the name integrated button. For backwards +compatibility, both methods need to be checked in userspace. + +INPUT_PROP_SEMI_MT: +------------------ +Some touchpads, most common between 2008 and 2011, can detect the presence +of multiple contacts without resolving the individual positions; only the +number of contacts and a rectangular shape is known. For such +touchpads, the semi-mt property should be set. + +Depending on the device, the rectangle may enclose all touches, like a +bounding box, or just some of them, for instance the two most recent +touches. The diversity makes the rectangle of limited use, but some +gestures can normally be extracted from it. + +If INPUT_PROP_SEMI_MT is not set, the device is assumed to be a true MT +device. + Guidelines: ========== The guidelines below ensure proper single-touch and multi-finger functionality. @@ -240,6 +290,8 @@ used to report when a touch is active on the screen. BTN_{MOUSE,LEFT,MIDDLE,RIGHT} must not be reported as the result of touch contact. BTN_TOOL_<name> events should be reported where possible. +For new hardware, INPUT_PROP_DIRECT should be set. + Trackpads: ---------- Legacy trackpads that only provide relative position information must report @@ -250,6 +302,8 @@ location of the touch. BTN_TOUCH should be used to report when a touch is active on the trackpad. Where multi-finger support is available, BTN_TOOL_<name> should be used to report the number of touches active on the trackpad. +For new hardware, INPUT_PROP_POINTER should be set. + Tablets: ---------- BTN_TOOL_<name> events must be reported when a stylus or other tool is active on @@ -260,3 +314,5 @@ button may be used for buttons on the tablet except BTN_{MOUSE,LEFT}. BTN_{0,1,2,etc} are good generic codes for unlabeled buttons. Do not use meaningful buttons, like BTN_FORWARD, unless the button is labeled for that purpose on the device. + +For new hardware, both INPUT_PROP_DIRECT and INPUT_PROP_POINTER should be set. diff --git a/Documentation/ioctl/ioctl-number.txt b/Documentation/ioctl/ioctl-number.txt index 4840334ea97b..68fbfb6529eb 100644 --- a/Documentation/ioctl/ioctl-number.txt +++ b/Documentation/ioctl/ioctl-number.txt @@ -189,7 +189,7 @@ Code Seq#(hex) Include File Comments 'Y' all linux/cyclades.h 'Z' 14-15 drivers/message/fusion/mptctl.h '[' 00-07 linux/usb/tmc.h USB Test and Measurement Devices - <mailto:gregkh@suse.de> + <mailto:gregkh@linuxfoundation.org> 'a' all linux/atm*.h, linux/sonet.h ATM on linux <http://lrcwww.epfl.ch/> 'b' 00-FF conflict! bit3 vme host bridge @@ -255,7 +255,7 @@ Code Seq#(hex) Include File Comments linux/ixjuser.h <http://web.archive.org/web/*/http://www.quicknet.net> 'r' 00-1F linux/msdos_fs.h and fs/fat/dir.c 's' all linux/cdk.h -'t' 00-7F linux/if_ppp.h +'t' 00-7F linux/ppp-ioctl.h 't' 80-8F linux/isdn_ppp.h 't' 90 linux/toshiba.h 'u' 00-1F linux/smb_fs.h gone diff --git a/Documentation/kernel-parameters.txt b/Documentation/kernel-parameters.txt index cfcc73f2b822..8cadb7551fca 100644 --- a/Documentation/kernel-parameters.txt +++ b/Documentation/kernel-parameters.txt @@ -2211,6 +2211,12 @@ bytes respectively. Such letter suffixes can also be entirely omitted. default: off. + printk.always_kmsg_dump= + Trigger kmsg_dump for cases other than kernel oops or + panics + Format: <bool> (1/Y/y=enable, 0/N/n=disable) + default: disabled + printk.time= Show timing data prefixed to each printk message line Format: <bool> (1/Y/y=enable, 0/N/n=disable) diff --git a/Documentation/ko_KR/HOWTO b/Documentation/ko_KR/HOWTO index ab5189ae3428..2f48f205fedc 100644 --- a/Documentation/ko_KR/HOWTO +++ b/Documentation/ko_KR/HOWTO @@ -354,7 +354,7 @@ Andrew Morton에 의해 배포된 실험적인 커널 패치들이다. Andrew는 git.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6.git quilt trees: - - USB, PCI, Driver Core, and I2C, Greg Kroah-Hartman < gregkh@suse.de> + - USB, PCI, Driver Core, and I2C, Greg Kroah-Hartman < gregkh@linuxfoundation.org> kernel.org/pub/linux/kernel/people/gregkh/gregkh-2.6/ - x86-64, partly i386, Andi Kleen < ak@suse.de> ftp.firstfloor.org:/pub/ak/x86_64/quilt/ diff --git a/Documentation/kobject.txt b/Documentation/kobject.txt index 3ab2472509cb..49578cf1aea5 100644 --- a/Documentation/kobject.txt +++ b/Documentation/kobject.txt @@ -1,6 +1,6 @@ Everything you never wanted to know about kobjects, ksets, and ktypes -Greg Kroah-Hartman <gregkh@suse.de> +Greg Kroah-Hartman <gregkh@linuxfoundation.org> Based on an original article by Jon Corbet for lwn.net written October 1, 2003 and located at http://lwn.net/Articles/51437/ diff --git a/Documentation/lockup-watchdogs.txt b/Documentation/lockup-watchdogs.txt new file mode 100644 index 000000000000..d2a36602ca8d --- /dev/null +++ b/Documentation/lockup-watchdogs.txt @@ -0,0 +1,63 @@ +=============================================================== +Softlockup detector and hardlockup detector (aka nmi_watchdog) +=============================================================== + +The Linux kernel can act as a watchdog to detect both soft and hard +lockups. + +A 'softlockup' is defined as a bug that causes the kernel to loop in +kernel mode for more than 20 seconds (see "Implementation" below for +details), without giving other tasks a chance to run. The current +stack trace is displayed upon detection and, by default, the system +will stay locked up. Alternatively, the kernel can be configured to +panic; a sysctl, "kernel.softlockup_panic", a kernel parameter, +"softlockup_panic" (see "Documentation/kernel-parameters.txt" for +details), and a compile option, "BOOTPARAM_HARDLOCKUP_PANIC", are +provided for this. + +A 'hardlockup' is defined as a bug that causes the CPU to loop in +kernel mode for more than 10 seconds (see "Implementation" below for +details), without letting other interrupts have a chance to run. +Similarly to the softlockup case, the current stack trace is displayed +upon detection and the system will stay locked up unless the default +behavior is changed, which can be done through a compile time knob, +"BOOTPARAM_HARDLOCKUP_PANIC", and a kernel parameter, "nmi_watchdog" +(see "Documentation/kernel-parameters.txt" for details). + +The panic option can be used in combination with panic_timeout (this +timeout is set through the confusingly named "kernel.panic" sysctl), +to cause the system to reboot automatically after a specified amount +of time. + +=== Implementation === + +The soft and hard lockup detectors are built on top of the hrtimer and +perf subsystems, respectively. A direct consequence of this is that, +in principle, they should work in any architecture where these +subsystems are present. + +A periodic hrtimer runs to generate interrupts and kick the watchdog +task. An NMI perf event is generated every "watchdog_thresh" +(compile-time initialized to 10 and configurable through sysctl of the +same name) seconds to check for hardlockups. If any CPU in the system +does not receive any hrtimer interrupt during that time the +'hardlockup detector' (the handler for the NMI perf event) will +generate a kernel warning or call panic, depending on the +configuration. + +The watchdog task is a high priority kernel thread that updates a +timestamp every time it is scheduled. If that timestamp is not updated +for 2*watchdog_thresh seconds (the softlockup threshold) the +'softlockup detector' (coded inside the hrtimer callback function) +will dump useful debug information to the system log, after which it +will call panic if it was instructed to do so or resume execution of +other kernel code. + +The period of the hrtimer is 2*watchdog_thresh/5, which means it has +two or three chances to generate an interrupt before the hardlockup +detector kicks in. + +As explained above, a kernel knob is provided that allows +administrators to configure the period of the hrtimer and the perf +event. The right value for a particular environment is a trade-off +between fast response to lockups and detection overhead. diff --git a/Documentation/magic-number.txt b/Documentation/magic-number.txt index abf481f780ec..82761a31d64d 100644 --- a/Documentation/magic-number.txt +++ b/Documentation/magic-number.txt @@ -89,7 +89,7 @@ TTY_DRIVER_MAGIC 0x5402 tty_driver include/linux/tty_driver.h MGSLPC_MAGIC 0x5402 mgslpc_info drivers/char/pcmcia/synclink_cs.c TTY_LDISC_MAGIC 0x5403 tty_ldisc include/linux/tty_ldisc.h USB_SERIAL_MAGIC 0x6702 usb_serial drivers/usb/serial/usb-serial.h -FULL_DUPLEX_MAGIC 0x6969 drivers/net/tulip/de2104x.c +FULL_DUPLEX_MAGIC 0x6969 drivers/net/ethernet/dec/tulip/de2104x.c USB_BLUETOOTH_MAGIC 0x6d02 usb_bluetooth drivers/usb/class/bluetty.c RFCOMM_TTY_MAGIC 0x6d02 net/bluetooth/rfcomm/tty.c USB_SERIAL_PORT_MAGIC 0x7301 usb_serial_port drivers/usb/serial/usb-serial.h diff --git a/Documentation/networking/LICENSE.qlge b/Documentation/networking/LICENSE.qlge index 123b6edd7f18..ce64e4d15b21 100644 --- a/Documentation/networking/LICENSE.qlge +++ b/Documentation/networking/LICENSE.qlge @@ -1,46 +1,288 @@ -Copyright (c) 2003-2008 QLogic Corporation -QLogic Linux Networking HBA Driver +Copyright (c) 2003-2011 QLogic Corporation +QLogic Linux qlge NIC Driver -This program includes a device driver for Linux 2.6 that may be -distributed with QLogic hardware specific firmware binary file. You may modify and redistribute the device driver code under the -GNU General Public License as published by the Free Software -Foundation (version 2 or a later version). - -You may redistribute the hardware specific firmware binary file -under the following terms: - - 1. Redistribution of source code (only if applicable), - must retain the above copyright notice, this list of - conditions and the following disclaimer. - - 2. Redistribution in binary form must reproduce the above - copyright notice, this list of conditions and the - following disclaimer in the documentation and/or other - materials provided with the distribution. - - 3. The name of QLogic Corporation may not be used to - endorse or promote products derived from this software - without specific prior written permission - -REGARDLESS OF WHAT LICENSING MECHANISM IS USED OR APPLICABLE, -THIS PROGRAM IS PROVIDED BY QLOGIC CORPORATION "AS IS'' AND ANY -EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A -PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR -BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, -EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED -TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, -DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON -ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, -OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE -POSSIBILITY OF SUCH DAMAGE. - -USER ACKNOWLEDGES AND AGREES THAT USE OF THIS PROGRAM WILL NOT -CREATE OR GIVE GROUNDS FOR A LICENSE BY IMPLICATION, ESTOPPEL, OR -OTHERWISE IN ANY INTELLECTUAL PROPERTY RIGHTS (PATENT, COPYRIGHT, -TRADE SECRET, MASK WORK, OR OTHER PROPRIETARY RIGHT) EMBODIED IN -ANY OTHER QLOGIC HARDWARE OR SOFTWARE EITHER SOLELY OR IN -COMBINATION WITH THIS PROGRAM. +GNU General Public License (a copy of which is attached hereto as +Exhibit A) published by the Free Software Foundation (version 2). + +EXHIBIT A + + GNU GENERAL PUBLIC LICENSE + Version 2, June 1991 + + Copyright (C) 1989, 1991 Free Software Foundation, Inc. + 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + Everyone is permitted to copy and distribute verbatim copies + of this license document, but changing it is not allowed. + + Preamble + + The licenses for most software are designed to take away your +freedom to share and change it. By contrast, the GNU General Public +License is intended to guarantee your freedom to share and change free +software--to make sure the software is free for all its users. This +General Public License applies to most of the Free Software +Foundation's software and to any other program whose authors commit to +using it. (Some other Free Software Foundation software is covered by +the GNU Lesser General Public License instead.) You can apply it to +your programs, too. + + When we speak of free software, we are referring to freedom, not +price. Our General Public Licenses are designed to make sure that you +have the freedom to distribute copies of free software (and charge for +this service if you wish), that you receive source code or can get it +if you want it, that you can change the software or use pieces of it +in new free programs; and that you know you can do these things. + + To protect your rights, we need to make restrictions that forbid +anyone to deny you these rights or to ask you to surrender the rights. +These restrictions translate to certain responsibilities for you if you +distribute copies of the software, or if you modify it. + + For example, if you distribute copies of such a program, whether +gratis or for a fee, you must give the recipients all the rights that +you have. You must make sure that they, too, receive or can get the +source code. And you must show them these terms so they know their +rights. + + We protect your rights with two steps: (1) copyright the software, and +(2) offer you this license which gives you legal permission to copy, +distribute and/or modify the software. + + Also, for each author's protection and ours, we want to make certain +that everyone understands that there is no warranty for this free +software. If the software is modified by someone else and passed on, we +want its recipients to know that what they have is not the original, so +that any problems introduced by others will not reflect on the original +authors' reputations. + + Finally, any free program is threatened constantly by software +patents. We wish to avoid the danger that redistributors of a free +program will individually obtain patent licenses, in effect making the +program proprietary. To prevent this, we have made it clear that any +patent must be licensed for everyone's free use or not licensed at all. + + The precise terms and conditions for copying, distribution and +modification follow. + + GNU GENERAL PUBLIC LICENSE + TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION + + 0. This License applies to any program or other work which contains +a notice placed by the copyright holder saying it may be distributed +under the terms of this General Public License. The "Program", below, +refers to any such program or work, and a "work based on the Program" +means either the Program or any derivative work under copyright law: +that is to say, a work containing the Program or a portion of it, +either verbatim or with modifications and/or translated into another +language. (Hereinafter, translation is included without limitation in +the term "modification".) Each licensee is addressed as "you". + +Activities other than copying, distribution and modification are not +covered by this License; they are outside its scope. The act of +running the Program is not restricted, and the output from the Program +is covered only if its contents constitute a work based on the +Program (independent of having been made by running the Program). +Whether that is true depends on what the Program does. + + 1. You may copy and distribute verbatim copies of the Program's +source code as you receive it, in any medium, provided that you +conspicuously and appropriately publish on each copy an appropriate +copyright notice and disclaimer of warranty; keep intact all the +notices that refer to this License and to the absence of any warranty; +and give any other recipients of the Program a copy of this License +along with the Program. + +You may charge a fee for the physical act of transferring a copy, and +you may at your option offer warranty protection in exchange for a fee. + + 2. You may modify your copy or copies of the Program or any portion +of it, thus forming a work based on the Program, and copy and +distribute such modifications or work under the terms of Section 1 +above, provided that you also meet all of these conditions: + + a) You must cause the modified files to carry prominent notices + stating that you changed the files and the date of any change. + + b) You must cause any work that you distribute or publish, that in + whole or in part contains or is derived from the Program or any + part thereof, to be licensed as a whole at no charge to all third + parties under the terms of this License. + + c) If the modified program normally reads commands interactively + when run, you must cause it, when started running for such + interactive use in the most ordinary way, to print or display an + announcement including an appropriate copyright notice and a + notice that there is no warranty (or else, saying that you provide + a warranty) and that users may redistribute the program under + these conditions, and telling the user how to view a copy of this + License. (Exception: if the Program itself is interactive but + does not normally print such an announcement, your work based on + the Program is not required to print an announcement.) + +These requirements apply to the modified work as a whole. If +identifiable sections of that work are not derived from the Program, +and can be reasonably considered independent and separate works in +themselves, then this License, and its terms, do not apply to those +sections when you distribute them as separate works. But when you +distribute the same sections as part of a whole which is a work based +on the Program, the distribution of the whole must be on the terms of +this License, whose permissions for other licensees extend to the +entire whole, and thus to each and every part regardless of who wrote it. + +Thus, it is not the intent of this section to claim rights or contest +your rights to work written entirely by you; rather, the intent is to +exercise the right to control the distribution of derivative or +collective works based on the Program. + +In addition, mere aggregation of another work not based on the Program +with the Program (or with a work based on the Program) on a volume of +a storage or distribution medium does not bring the other work under +the scope of this License. + + 3. You may copy and distribute the Program (or a work based on it, +under Section 2) in object code or executable form under the terms of +Sections 1 and 2 above provided that you also do one of the following: + + a) Accompany it with the complete corresponding machine-readable + source code, which must be distributed under the terms of Sections + 1 and 2 above on a medium customarily used for software interchange; or, + + b) Accompany it with a written offer, valid for at least three + years, to give any third party, for a charge no more than your + cost of physically performing source distribution, a complete + machine-readable copy of the corresponding source code, to be + distributed under the terms of Sections 1 and 2 above on a medium + customarily used for software interchange; or, + + c) Accompany it with the information you received as to the offer + to distribute corresponding source code. (This alternative is + allowed only for noncommercial distribution and only if you + received the program in object code or executable form with such + an offer, in accord with Subsection b above.) + +The source code for a work means the preferred form of the work for +making modifications to it. For an executable work, complete source +code means all the source code for all modules it contains, plus any +associated interface definition files, plus the scripts used to +control compilation and installation of the executable. However, as a +special exception, the source code distributed need not include +anything that is normally distributed (in either source or binary +form) with the major components (compiler, kernel, and so on) of the +operating system on which the executable runs, unless that component +itself accompanies the executable. + +If distribution of executable or object code is made by offering +access to copy from a designated place, then offering equivalent +access to copy the source code from the same place counts as +distribution of the source code, even though third parties are not +compelled to copy the source along with the object code. + + 4. You may not copy, modify, sublicense, or distribute the Program +except as expressly provided under this License. Any attempt +otherwise to copy, modify, sublicense or distribute the Program is +void, and will automatically terminate your rights under this License. +However, parties who have received copies, or rights, from you under +this License will not have their licenses terminated so long as such +parties remain in full compliance. + + 5. You are not required to accept this License, since you have not +signed it. However, nothing else grants you permission to modify or +distribute the Program or its derivative works. These actions are +prohibited by law if you do not accept this License. Therefore, by +modifying or distributing the Program (or any work based on the +Program), you indicate your acceptance of this License to do so, and +all its terms and conditions for copying, distributing or modifying +the Program or works based on it. + + 6. Each time you redistribute the Program (or any work based on the +Program), the recipient automatically receives a license from the +original licensor to copy, distribute or modify the Program subject to +these terms and conditions. You may not impose any further +restrictions on the recipients' exercise of the rights granted herein. +You are not responsible for enforcing compliance by third parties to +this License. + + 7. If, as a consequence of a court judgment or allegation of patent +infringement or for any other reason (not limited to patent issues), +conditions are imposed on you (whether by court order, agreement or +otherwise) that contradict the conditions of this License, they do not +excuse you from the conditions of this License. If you cannot +distribute so as to satisfy simultaneously your obligations under this +License and any other pertinent obligations, then as a consequence you +may not distribute the Program at all. For example, if a patent +license would not permit royalty-free redistribution of the Program by +all those who receive copies directly or indirectly through you, then +the only way you could satisfy both it and this License would be to +refrain entirely from distribution of the Program. + +If any portion of this section is held invalid or unenforceable under +any particular circumstance, the balance of the section is intended to +apply and the section as a whole is intended to apply in other +circumstances. + +It is not the purpose of this section to induce you to infringe any +patents or other property right claims or to contest validity of any +such claims; this section has the sole purpose of protecting the +integrity of the free software distribution system, which is +implemented by public license practices. Many people have made +generous contributions to the wide range of software distributed +through that system in reliance on consistent application of that +system; it is up to the author/donor to decide if he or she is willing +to distribute software through any other system and a licensee cannot +impose that choice. + +This section is intended to make thoroughly clear what is believed to +be a consequence of the rest of this License. + + 8. If the distribution and/or use of the Program is restricted in +certain countries either by patents or by copyrighted interfaces, the +original copyright holder who places the Program under this License +may add an explicit geographical distribution limitation excluding +those countries, so that distribution is permitted only in or among +countries not thus excluded. In such case, this License incorporates +the limitation as if written in the body of this License. + + 9. The Free Software Foundation may publish revised and/or new versions +of the General Public License from time to time. Such new versions will +be similar in spirit to the present version, but may differ in detail to +address new problems or concerns. + +Each version is given a distinguishing version number. If the Program +specifies a version number of this License which applies to it and "any +later version", you have the option of following the terms and conditions +either of that version or of any later version published by the Free +Software Foundation. If the Program does not specify a version number of +this License, you may choose any version ever published by the Free Software +Foundation. + + 10. If you wish to incorporate parts of the Program into other free +programs whose distribution conditions are different, write to the author +to ask for permission. For software which is copyrighted by the Free +Software Foundation, write to the Free Software Foundation; we sometimes +make exceptions for this. Our decision will be guided by the two goals +of preserving the free status of all derivatives of our free software and +of promoting the sharing and reuse of software generally. + + NO WARRANTY + + 11. BECAUSE THE PROGRAM IS LICENSED FREE OF CHARGE, THERE IS NO WARRANTY +FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW. EXCEPT WHEN +OTHERWISE STATED IN WRITING THE COPYRIGHT HOLDERS AND/OR OTHER PARTIES +PROVIDE THE PROGRAM "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED +OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF +MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE ENTIRE RISK AS +TO THE QUALITY AND PERFORMANCE OF THE PROGRAM IS WITH YOU. SHOULD THE +PROGRAM PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, +REPAIR OR CORRECTION. + + 12. IN NO EVENT UNLESS REQUIRED BY APPLICABLE LAW OR AGREED TO IN WRITING +WILL ANY COPYRIGHT HOLDER, OR ANY OTHER PARTY WHO MAY MODIFY AND/OR +REDISTRIBUTE THE PROGRAM AS PERMITTED ABOVE, BE LIABLE TO YOU FOR DAMAGES, +INCLUDING ANY GENERAL, SPECIAL, INCIDENTAL OR CONSEQUENTIAL DAMAGES ARISING +OUT OF THE USE OR INABILITY TO USE THE PROGRAM (INCLUDING BUT NOT LIMITED +TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE OR LOSSES SUSTAINED BY +YOU OR THIRD PARTIES OR A FAILURE OF THE PROGRAM TO OPERATE WITH ANY OTHER +PROGRAMS), EVEN IF SUCH HOLDER OR OTHER PARTY HAS BEEN ADVISED OF THE +POSSIBILITY OF SUCH DAMAGES. diff --git a/Documentation/networking/l2tp.txt b/Documentation/networking/l2tp.txt index e7bf3979facb..e63fc1f7bf87 100644 --- a/Documentation/networking/l2tp.txt +++ b/Documentation/networking/l2tp.txt @@ -111,7 +111,7 @@ When creating PPPoL2TP sockets, the application provides information to the driver about the socket in a socket connect() call. Source and destination tunnel and session ids are provided, as well as the file descriptor of a UDP socket. See struct pppol2tp_addr in -include/linux/if_ppp.h. Note that zero tunnel / session ids are +include/linux/if_pppol2tp.h. Note that zero tunnel / session ids are treated specially. When creating the per-tunnel PPPoL2TP management socket in Step 2 above, zero source and destination session ids are specified, which tells the driver to prepare the supplied UDP file diff --git a/Documentation/networking/mac80211-auth-assoc-deauth.txt b/Documentation/networking/mac80211-auth-assoc-deauth.txt new file mode 100644 index 000000000000..e0a2aa585ca3 --- /dev/null +++ b/Documentation/networking/mac80211-auth-assoc-deauth.txt @@ -0,0 +1,99 @@ +# +# This outlines the Linux authentication/association and +# deauthentication/disassociation flows. +# +# This can be converted into a diagram using the service +# at http://www.websequencediagrams.com/ +# + +participant userspace +participant mac80211 +participant driver + +alt authentication needed (not FT) +userspace->mac80211: authenticate + +alt authenticated/authenticating already +mac80211->driver: sta_state(AP, not-exists) +mac80211->driver: bss_info_changed(clear BSSID) +else associated +note over mac80211,driver +like deauth/disassoc, without sending the +BA session stop & deauth/disassoc frames +end note +end + +mac80211->driver: config(channel, non-HT) +mac80211->driver: bss_info_changed(set BSSID, basic rate bitmap) +mac80211->driver: sta_state(AP, exists) + +alt no probe request data known +mac80211->driver: TX directed probe request +driver->mac80211: RX probe response +end + +mac80211->driver: TX auth frame +driver->mac80211: RX auth frame + +alt WEP shared key auth +mac80211->driver: TX auth frame +driver->mac80211: RX auth frame +end + +mac80211->driver: sta_state(AP, authenticated) +mac80211->userspace: RX auth frame + +end + +userspace->mac80211: associate +alt authenticated or associated +note over mac80211,driver: cleanup like for authenticate +end + +alt not previously authenticated (FT) +mac80211->driver: config(channel, non-HT) +mac80211->driver: bss_info_changed(set BSSID, basic rate bitmap) +mac80211->driver: sta_state(AP, exists) +mac80211->driver: sta_state(AP, authenticated) +end +mac80211->driver: TX assoc +driver->mac80211: RX assoc response +note over mac80211: init rate control +mac80211->driver: sta_state(AP, associated) + +alt not using WPA +mac80211->driver: sta_state(AP, authorized) +end + +mac80211->driver: set up QoS parameters + +alt is HT channel +mac80211->driver: config(channel, HT params) +end + +mac80211->driver: bss_info_changed(QoS, HT, associated with AID) +mac80211->userspace: associated + +note left of userspace: associated now + +alt using WPA +note over userspace +do 4-way-handshake +(data frames) +end note +userspace->mac80211: authorized +mac80211->driver: sta_state(AP, authorized) +end + +userspace->mac80211: deauthenticate/disassociate +mac80211->driver: stop BA sessions +mac80211->driver: TX deauth/disassoc +mac80211->driver: flush frames +mac80211->driver: sta_state(AP,associated) +mac80211->driver: sta_state(AP,authenticated) +mac80211->driver: sta_state(AP,exists) +mac80211->driver: sta_state(AP,not-exists) +mac80211->driver: turn off powersave +mac80211->driver: bss_info_changed(clear BSSID, not associated, no QoS, ...) +mac80211->driver: config(non-HT channel type) +mac80211->userspace: disconnected diff --git a/Documentation/networking/netdev-features.txt b/Documentation/networking/netdev-features.txt index 4b1c0dcef84c..4164f5c02e4b 100644 --- a/Documentation/networking/netdev-features.txt +++ b/Documentation/networking/netdev-features.txt @@ -152,3 +152,16 @@ NETIF_F_VLAN_CHALLENGED should be set for devices which can't cope with VLAN headers. Some drivers set this because the cards can't handle the bigger MTU. [FIXME: Those cases could be fixed in VLAN code by allowing only reduced-MTU VLANs. This may be not useful, though.] + +* rx-fcs + +This requests that the NIC append the Ethernet Frame Checksum (FCS) +to the end of the skb data. This allows sniffers and other tools to +read the CRC recorded by the NIC on receipt of the packet. + +* rx-all + +This requests that the NIC receive all possible frames, including errored +frames (such as bad FCS, etc). This can be helpful when sniffing a link with +bad packets on it. Some NICs may receive more packets if also put into normal +PROMISC mdoe. diff --git a/Documentation/networking/phy.txt b/Documentation/networking/phy.txt index 9eb1ba52013d..95e5f5985a2a 100644 --- a/Documentation/networking/phy.txt +++ b/Documentation/networking/phy.txt @@ -62,7 +62,8 @@ The MDIO bus 5) The bus must also be declared somewhere as a device, and registered. As an example for how one driver implemented an mdio bus driver, see - drivers/net/gianfar_mii.c and arch/ppc/syslib/mpc85xx_devices.c + drivers/net/ethernet/freescale/fsl_pq_mdio.c and an associated DTS file + for one of the users. (e.g. "git grep fsl,.*-mdio arch/powerpc/boot/dts/") Connecting to a PHY diff --git a/Documentation/networking/ppp_generic.txt b/Documentation/networking/ppp_generic.txt index 15b5172fbb98..091d20273dcb 100644 --- a/Documentation/networking/ppp_generic.txt +++ b/Documentation/networking/ppp_generic.txt @@ -342,7 +342,7 @@ an interface unit are: numbers on received multilink fragments SC_MP_XSHORTSEQ transmit short multilink sequence nos. - The values of these flags are defined in <linux/if_ppp.h>. Note + The values of these flags are defined in <linux/ppp-ioctl.h>. Note that the values of the SC_MULTILINK, SC_MP_SHORTSEQ and SC_MP_XSHORTSEQ bits are ignored if the CONFIG_PPP_MULTILINK option is not selected. @@ -358,7 +358,7 @@ an interface unit are: * PPPIOCSCOMPRESS sets the parameters for packet compression or decompression. The argument should point to a ppp_option_data - structure (defined in <linux/if_ppp.h>), which contains a + structure (defined in <linux/ppp-ioctl.h>), which contains a pointer/length pair which should describe a block of memory containing a CCP option specifying a compression method and its parameters. The ppp_option_data struct also contains a `transmit' @@ -395,7 +395,7 @@ an interface unit are: * PPPIOCSNPMODE sets the network-protocol mode for a given network protocol. The argument should point to an npioctl struct (defined - in <linux/if_ppp.h>). The `protocol' field gives the PPP protocol + in <linux/ppp-ioctl.h>). The `protocol' field gives the PPP protocol number for the protocol to be affected, and the `mode' field specifies what to do with packets for that protocol: diff --git a/Documentation/nmi_watchdog.txt b/Documentation/nmi_watchdog.txt deleted file mode 100644 index bf9f80a98282..000000000000 --- a/Documentation/nmi_watchdog.txt +++ /dev/null @@ -1,83 +0,0 @@ - -[NMI watchdog is available for x86 and x86-64 architectures] - -Is your system locking up unpredictably? No keyboard activity, just -a frustrating complete hard lockup? Do you want to help us debugging -such lockups? If all yes then this document is definitely for you. - -On many x86/x86-64 type hardware there is a feature that enables -us to generate 'watchdog NMI interrupts'. (NMI: Non Maskable Interrupt -which get executed even if the system is otherwise locked up hard). -This can be used to debug hard kernel lockups. By executing periodic -NMI interrupts, the kernel can monitor whether any CPU has locked up, -and print out debugging messages if so. - -In order to use the NMI watchdog, you need to have APIC support in your -kernel. For SMP kernels, APIC support gets compiled in automatically. For -UP, enable either CONFIG_X86_UP_APIC (Processor type and features -> Local -APIC support on uniprocessors) or CONFIG_X86_UP_IOAPIC (Processor type and -features -> IO-APIC support on uniprocessors) in your kernel config. -CONFIG_X86_UP_APIC is for uniprocessor machines without an IO-APIC. -CONFIG_X86_UP_IOAPIC is for uniprocessor with an IO-APIC. [Note: certain -kernel debugging options, such as Kernel Stack Meter or Kernel Tracer, -may implicitly disable the NMI watchdog.] - -For x86-64, the needed APIC is always compiled in. - -Using local APIC (nmi_watchdog=2) needs the first performance register, so -you can't use it for other purposes (such as high precision performance -profiling.) However, at least oprofile and the perfctr driver disable the -local APIC NMI watchdog automatically. - -To actually enable the NMI watchdog, use the 'nmi_watchdog=N' boot -parameter. Eg. the relevant lilo.conf entry: - - append="nmi_watchdog=1" - -For SMP machines and UP machines with an IO-APIC use nmi_watchdog=1. -For UP machines without an IO-APIC use nmi_watchdog=2, this only works -for some processor types. If in doubt, boot with nmi_watchdog=1 and -check the NMI count in /proc/interrupts; if the count is zero then -reboot with nmi_watchdog=2 and check the NMI count. If it is still -zero then log a problem, you probably have a processor that needs to be -added to the nmi code. - -A 'lockup' is the following scenario: if any CPU in the system does not -execute the period local timer interrupt for more than 5 seconds, then -the NMI handler generates an oops and kills the process. This -'controlled crash' (and the resulting kernel messages) can be used to -debug the lockup. Thus whenever the lockup happens, wait 5 seconds and -the oops will show up automatically. If the kernel produces no messages -then the system has crashed so hard (eg. hardware-wise) that either it -cannot even accept NMI interrupts, or the crash has made the kernel -unable to print messages. - -Be aware that when using local APIC, the frequency of NMI interrupts -it generates, depends on the system load. The local APIC NMI watchdog, -lacking a better source, uses the "cycles unhalted" event. As you may -guess it doesn't tick when the CPU is in the halted state (which happens -when the system is idle), but if your system locks up on anything but the -"hlt" processor instruction, the watchdog will trigger very soon as the -"cycles unhalted" event will happen every clock tick. If it locks up on -"hlt", then you are out of luck -- the event will not happen at all and the -watchdog won't trigger. This is a shortcoming of the local APIC watchdog --- unfortunately there is no "clock ticks" event that would work all the -time. The I/O APIC watchdog is driven externally and has no such shortcoming. -But its NMI frequency is much higher, resulting in a more significant hit -to the overall system performance. - -On x86 nmi_watchdog is disabled by default so you have to enable it with -a boot time parameter. - -It's possible to disable the NMI watchdog in run-time by writing "0" to -/proc/sys/kernel/nmi_watchdog. Writing "1" to the same file will re-enable -the NMI watchdog. Notice that you still need to use "nmi_watchdog=" parameter -at boot time. - -NOTE: In kernels prior to 2.4.2-ac18 the NMI-oopser is enabled unconditionally -on x86 SMP boxes. - -[ feel free to send bug reports, suggestions and patches to - Ingo Molnar <mingo@redhat.com> or the Linux SMP mailing - list at <linux-smp@vger.kernel.org> ] - diff --git a/Documentation/scheduler/sched-stats.txt b/Documentation/scheduler/sched-stats.txt index 1cd5d51bc761..8259b34a66ae 100644 --- a/Documentation/scheduler/sched-stats.txt +++ b/Documentation/scheduler/sched-stats.txt @@ -38,7 +38,8 @@ First field is a sched_yield() statistic: 1) # of times sched_yield() was called Next three are schedule() statistics: - 2) # of times we switched to the expired queue and reused it + 2) This field is a legacy array expiration count field used in the O(1) + scheduler. We kept it for ABI compatibility, but it is always set to zero. 3) # of times schedule() was called 4) # of times schedule() left the processor idle diff --git a/Documentation/static-keys.txt b/Documentation/static-keys.txt new file mode 100644 index 000000000000..d93f3c00f245 --- /dev/null +++ b/Documentation/static-keys.txt @@ -0,0 +1,286 @@ + Static Keys + ----------- + +By: Jason Baron <jbaron@redhat.com> + +0) Abstract + +Static keys allows the inclusion of seldom used features in +performance-sensitive fast-path kernel code, via a GCC feature and a code +patching technique. A quick example: + + struct static_key key = STATIC_KEY_INIT_FALSE; + + ... + + if (static_key_false(&key)) + do unlikely code + else + do likely code + + ... + static_key_slow_inc(); + ... + static_key_slow_inc(); + ... + +The static_key_false() branch will be generated into the code with as little +impact to the likely code path as possible. + + +1) Motivation + + +Currently, tracepoints are implemented using a conditional branch. The +conditional check requires checking a global variable for each tracepoint. +Although the overhead of this check is small, it increases when the memory +cache comes under pressure (memory cache lines for these global variables may +be shared with other memory accesses). As we increase the number of tracepoints +in the kernel this overhead may become more of an issue. In addition, +tracepoints are often dormant (disabled) and provide no direct kernel +functionality. Thus, it is highly desirable to reduce their impact as much as +possible. Although tracepoints are the original motivation for this work, other +kernel code paths should be able to make use of the static keys facility. + + +2) Solution + + +gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label: + +http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html + +Using the 'asm goto', we can create branches that are either taken or not taken +by default, without the need to check memory. Then, at run-time, we can patch +the branch site to change the branch direction. + +For example, if we have a simple branch that is disabled by default: + + if (static_key_false(&key)) + printk("I am the true branch\n"); + +Thus, by default the 'printk' will not be emitted. And the code generated will +consist of a single atomic 'no-op' instruction (5 bytes on x86), in the +straight-line code path. When the branch is 'flipped', we will patch the +'no-op' in the straight-line codepath with a 'jump' instruction to the +out-of-line true branch. Thus, changing branch direction is expensive but +branch selection is basically 'free'. That is the basic tradeoff of this +optimization. + +This lowlevel patching mechanism is called 'jump label patching', and it gives +the basis for the static keys facility. + +3) Static key label API, usage and examples: + + +In order to make use of this optimization you must first define a key: + + struct static_key key; + +Which is initialized as: + + struct static_key key = STATIC_KEY_INIT_TRUE; + +or: + + struct static_key key = STATIC_KEY_INIT_FALSE; + +If the key is not initialized, it is default false. The 'struct static_key', +must be a 'global'. That is, it can't be allocated on the stack or dynamically +allocated at run-time. + +The key is then used in code as: + + if (static_key_false(&key)) + do unlikely code + else + do likely code + +Or: + + if (static_key_true(&key)) + do likely code + else + do unlikely code + +A key that is initialized via 'STATIC_KEY_INIT_FALSE', must be used in a +'static_key_false()' construct. Likewise, a key initialized via +'STATIC_KEY_INIT_TRUE' must be used in a 'static_key_true()' construct. A +single key can be used in many branches, but all the branches must match the +way that the key has been initialized. + +The branch(es) can then be switched via: + + static_key_slow_inc(&key); + ... + static_key_slow_dec(&key); + +Thus, 'static_key_slow_inc()' means 'make the branch true', and +'static_key_slow_dec()' means 'make the the branch false' with appropriate +reference counting. For example, if the key is initialized true, a +static_key_slow_dec(), will switch the branch to false. And a subsequent +static_key_slow_inc(), will change the branch back to true. Likewise, if the +key is initialized false, a 'static_key_slow_inc()', will change the branch to +true. And then a 'static_key_slow_dec()', will again make the branch false. + +An example usage in the kernel is the implementation of tracepoints: + + static inline void trace_##name(proto) \ + { \ + if (static_key_false(&__tracepoint_##name.key)) \ + __DO_TRACE(&__tracepoint_##name, \ + TP_PROTO(data_proto), \ + TP_ARGS(data_args), \ + TP_CONDITION(cond)); \ + } + +Tracepoints are disabled by default, and can be placed in performance critical +pieces of the kernel. Thus, by using a static key, the tracepoints can have +absolutely minimal impact when not in use. + + +4) Architecture level code patching interface, 'jump labels' + + +There are a few functions and macros that architectures must implement in order +to take advantage of this optimization. If there is no architecture support, we +simply fall back to a traditional, load, test, and jump sequence. + +* select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig + +* #define JUMP_LABEL_NOP_SIZE, see: arch/x86/include/asm/jump_label.h + +* __always_inline bool arch_static_branch(struct static_key *key), see: + arch/x86/include/asm/jump_label.h + +* void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type), + see: arch/x86/kernel/jump_label.c + +* __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type), + see: arch/x86/kernel/jump_label.c + + +* struct jump_entry, see: arch/x86/include/asm/jump_label.h + + +5) Static keys / jump label analysis, results (x86_64): + + +As an example, let's add the following branch to 'getppid()', such that the +system call now looks like: + +SYSCALL_DEFINE0(getppid) +{ + int pid; + ++ if (static_key_false(&key)) ++ printk("I am the true branch\n"); + + rcu_read_lock(); + pid = task_tgid_vnr(rcu_dereference(current->real_parent)); + rcu_read_unlock(); + + return pid; +} + +The resulting instructions with jump labels generated by GCC is: + +ffffffff81044290 <sys_getppid>: +ffffffff81044290: 55 push %rbp +ffffffff81044291: 48 89 e5 mov %rsp,%rbp +ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9> +ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax +ffffffff810442a0: 00 00 +ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax +ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax +ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi +ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr> +ffffffff810442bc: 5d pop %rbp +ffffffff810442bd: 48 98 cltq +ffffffff810442bf: c3 retq +ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi +ffffffff810442c7: 31 c0 xor %eax,%eax +ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk> +ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9> + +Without the jump label optimization it looks like: + +ffffffff810441f0 <sys_getppid>: +ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key> +ffffffff810441f6: 55 push %rbp +ffffffff810441f7: 48 89 e5 mov %rsp,%rbp +ffffffff810441fa: 85 c0 test %eax,%eax +ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35> +ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax +ffffffff81044205: 00 00 +ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax +ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax +ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi +ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr> +ffffffff81044221: 5d pop %rbp +ffffffff81044222: 48 98 cltq +ffffffff81044224: c3 retq +ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi +ffffffff8104422c: 31 c0 xor %eax,%eax +ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk> +ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe> +ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1) +ffffffff8104423c: 00 00 00 00 + +Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction +vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched +to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump +label case adds: + +6 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes. + +If we then include the padding bytes, the jump label code saves, 16 total bytes +of instruction memory for this small fucntion. In this case the non-jump label +function is 80 bytes long. Thus, we have have saved 20% of the instruction +footprint. We can in fact improve this even further, since the 5-byte no-op +really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp. +However, we have not yet implemented optimal no-op sizes (they are currently +hard-coded). + +Since there are a number of static key API uses in the scheduler paths, +'pipe-test' (also known as 'perf bench sched pipe') can be used to show the +performance improvement. Testing done on 3.3.0-rc2: + +jump label disabled: + + Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs): + + 855.700314 task-clock # 0.534 CPUs utilized ( +- 0.11% ) + 200,003 context-switches # 0.234 M/sec ( +- 0.00% ) + 0 CPU-migrations # 0.000 M/sec ( +- 39.58% ) + 487 page-faults # 0.001 M/sec ( +- 0.02% ) + 1,474,374,262 cycles # 1.723 GHz ( +- 0.17% ) + <not supported> stalled-cycles-frontend + <not supported> stalled-cycles-backend + 1,178,049,567 instructions # 0.80 insns per cycle ( +- 0.06% ) + 208,368,926 branches # 243.507 M/sec ( +- 0.06% ) + 5,569,188 branch-misses # 2.67% of all branches ( +- 0.54% ) + + 1.601607384 seconds time elapsed ( +- 0.07% ) + +jump label enabled: + + Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs): + + 841.043185 task-clock # 0.533 CPUs utilized ( +- 0.12% ) + 200,004 context-switches # 0.238 M/sec ( +- 0.00% ) + 0 CPU-migrations # 0.000 M/sec ( +- 40.87% ) + 487 page-faults # 0.001 M/sec ( +- 0.05% ) + 1,432,559,428 cycles # 1.703 GHz ( +- 0.18% ) + <not supported> stalled-cycles-frontend + <not supported> stalled-cycles-backend + 1,175,363,994 instructions # 0.82 insns per cycle ( +- 0.04% ) + 206,859,359 branches # 245.956 M/sec ( +- 0.04% ) + 4,884,119 branch-misses # 2.36% of all branches ( +- 0.85% ) + + 1.579384366 seconds time elapsed + +The percentage of saved branches is .7%, and we've saved 12% on +'branch-misses'. This is where we would expect to get the most savings, since +this optimization is about reducing the number of branches. In addition, we've +saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time. diff --git a/Documentation/sysctl/kernel.txt b/Documentation/sysctl/kernel.txt index 8c20fbd8b42d..6d78841fd416 100644 --- a/Documentation/sysctl/kernel.txt +++ b/Documentation/sysctl/kernel.txt @@ -601,6 +601,8 @@ can be ORed together: instead of using the one provided by the hardware. 512 - A kernel warning has occurred. 1024 - A module from drivers/staging was loaded. +2048 - The system is working around a severe firmware bug. +4096 - An out-of-tree module has been loaded. ============================================================== diff --git a/Documentation/trace/ftrace.txt b/Documentation/trace/ftrace.txt index 1ebc24cf9a55..6f51fed45f2d 100644 --- a/Documentation/trace/ftrace.txt +++ b/Documentation/trace/ftrace.txt @@ -226,6 +226,13 @@ Here is the list of current tracers that may be configured. Traces and records the max latency that it takes for the highest priority task to get scheduled after it has been woken up. + Traces all tasks as an average developer would expect. + + "wakeup_rt" + + Traces and records the max latency that it takes for just + RT tasks (as the current "wakeup" does). This is useful + for those interested in wake up timings of RT tasks. "hw-branch-tracer" diff --git a/Documentation/zh_CN/HOWTO b/Documentation/zh_CN/HOWTO index faf976c0c731..7fba5aab9ef9 100644 --- a/Documentation/zh_CN/HOWTO +++ b/Documentation/zh_CN/HOWTO @@ -316,7 +316,7 @@ linux-kernel邮件列表中提供反馈，告诉大家你遇到了问题还是 git.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6.git 使用quilt管理的补丁集： - - USB, PCI, 驱动程序核心和I2C, Greg Kroah-Hartman <gregkh@suse.de> + - USB, PCI, 驱动程序核心和I2C, Greg Kroah-Hartman <gregkh@linuxfoundation.org> kernel.org/pub/linux/kernel/people/gregkh/gregkh-2.6/ - x86-64, 部分i386, Andi Kleen <ak@suse.de> ftp.firstfloor.org:/pub/ak/x86_64/quilt/ diff --git a/Documentation/zh_CN/magic-number.txt b/Documentation/zh_CN/magic-number.txt index c278f412dc65..f606ba8598cf 100644 --- a/Documentation/zh_CN/magic-number.txt +++ b/Documentation/zh_CN/magic-number.txt @@ -89,7 +89,7 @@ TTY_DRIVER_MAGIC 0x5402 tty_driver include/linux/tty_driver.h MGSLPC_MAGIC 0x5402 mgslpc_info drivers/char/pcmcia/synclink_cs.c TTY_LDISC_MAGIC 0x5403 tty_ldisc include/linux/tty_ldisc.h USB_SERIAL_MAGIC 0x6702 usb_serial drivers/usb/serial/usb-serial.h -FULL_DUPLEX_MAGIC 0x6969 drivers/net/tulip/de2104x.c +FULL_DUPLEX_MAGIC 0x6969 drivers/net/ethernet/dec/tulip/de2104x.c USB_BLUETOOTH_MAGIC 0x6d02 usb_bluetooth drivers/usb/class/bluetty.c RFCOMM_TTY_MAGIC 0x6d02 net/bluetooth/rfcomm/tty.c USB_SERIAL_PORT_MAGIC 0x7301 usb_serial_port drivers/usb/serial/usb-serial.h |