aboutsummaryrefslogtreecommitdiffstats
path: root/Documentation
diff options
context:
space:
mode:
Diffstat (limited to 'Documentation')
-rw-r--r--Documentation/ABI/removed/devfs2
-rw-r--r--Documentation/ABI/stable/sysfs-driver-usb-usbtmc10
-rw-r--r--Documentation/ABI/testing/sysfs-class2
-rw-r--r--Documentation/ABI/testing/sysfs-devices2
-rw-r--r--Documentation/ABI/testing/sysfs-devices-soc58
-rw-r--r--Documentation/ABI/testing/sysfs-driver-samsung-laptop2
-rw-r--r--Documentation/RCU/RTFP.txt1784
-rw-r--r--Documentation/RCU/checklist.txt14
-rw-r--r--Documentation/RCU/stallwarn.txt87
-rw-r--r--Documentation/RCU/torture.txt33
-rw-r--r--Documentation/RCU/trace.txt36
-rw-r--r--Documentation/devicetree/bindings/tty/serial/efm32-uart.txt14
-rw-r--r--Documentation/dynamic-debug-howto.txt30
-rw-r--r--Documentation/filesystems/debugfs.txt5
-rw-r--r--Documentation/hwmon/w83627ehf9
-rw-r--r--Documentation/hwmon/zl610014
-rw-r--r--Documentation/ioctl/ioctl-number.txt2
-rw-r--r--Documentation/ko_KR/HOWTO2
-rw-r--r--Documentation/kobject.txt2
-rw-r--r--Documentation/lockup-watchdogs.txt63
-rw-r--r--Documentation/nmi_watchdog.txt83
-rw-r--r--Documentation/scheduler/sched-stats.txt3
-rw-r--r--Documentation/static-keys.txt286
-rw-r--r--Documentation/trace/ftrace.txt7
-rw-r--r--Documentation/zh_CN/HOWTO2
25 files changed, 2298 insertions, 254 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 @@
1What: devfs 1What: devfs
2Date: July 2005 (scheduled), finally removed in kernel v2.6.18 2Date: July 2005 (scheduled), finally removed in kernel v2.6.18
3Contact: Greg Kroah-Hartman <gregkh@suse.de> 3Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
4Description: 4Description:
5 devfs has been unmaintained for a number of years, has unfixable 5 devfs has been unmaintained for a number of years, has unfixable
6 races, contains a naming policy within the kernel that is 6 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 @@
1What: /sys/bus/usb/drivers/usbtmc/devices/*/interface_capabilities 1What: /sys/bus/usb/drivers/usbtmc/devices/*/interface_capabilities
2What: /sys/bus/usb/drivers/usbtmc/devices/*/device_capabilities 2What: /sys/bus/usb/drivers/usbtmc/devices/*/device_capabilities
3Date: August 2008 3Date: August 2008
4Contact: Greg Kroah-Hartman <gregkh@suse.de> 4Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
5Description: 5Description:
6 These files show the various USB TMC capabilities as described 6 These files show the various USB TMC capabilities as described
7 by the device itself. The full description of the bitfields 7 by the device itself. The full description of the bitfields
@@ -15,7 +15,7 @@ Description:
15What: /sys/bus/usb/drivers/usbtmc/devices/*/usb488_interface_capabilities 15What: /sys/bus/usb/drivers/usbtmc/devices/*/usb488_interface_capabilities
16What: /sys/bus/usb/drivers/usbtmc/devices/*/usb488_device_capabilities 16What: /sys/bus/usb/drivers/usbtmc/devices/*/usb488_device_capabilities
17Date: August 2008 17Date: August 2008
18Contact: Greg Kroah-Hartman <gregkh@suse.de> 18Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
19Description: 19Description:
20 These files show the various USB TMC capabilities as described 20 These files show the various USB TMC capabilities as described
21 by the device itself. The full description of the bitfields 21 by the device itself. The full description of the bitfields
@@ -29,7 +29,7 @@ Description:
29 29
30What: /sys/bus/usb/drivers/usbtmc/devices/*/TermChar 30What: /sys/bus/usb/drivers/usbtmc/devices/*/TermChar
31Date: August 2008 31Date: August 2008
32Contact: Greg Kroah-Hartman <gregkh@suse.de> 32Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
33Description: 33Description:
34 This file is the TermChar value to be sent to the USB TMC 34 This file is the TermChar value to be sent to the USB TMC
35 device as described by the document, "Universal Serial Bus Test 35 device as described by the document, "Universal Serial Bus Test
@@ -42,7 +42,7 @@ Description:
42 42
43What: /sys/bus/usb/drivers/usbtmc/devices/*/TermCharEnabled 43What: /sys/bus/usb/drivers/usbtmc/devices/*/TermCharEnabled
44Date: August 2008 44Date: August 2008
45Contact: Greg Kroah-Hartman <gregkh@suse.de> 45Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
46Description: 46Description:
47 This file determines if the TermChar is to be sent to the 47 This file determines if the TermChar is to be sent to the
48 device on every transaction or not. For more details about 48 device on every transaction or not. For more details about
@@ -53,7 +53,7 @@ Description:
53 53
54What: /sys/bus/usb/drivers/usbtmc/devices/*/auto_abort 54What: /sys/bus/usb/drivers/usbtmc/devices/*/auto_abort
55Date: August 2008 55Date: August 2008
56Contact: Greg Kroah-Hartman <gregkh@suse.de> 56Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
57Description: 57Description:
58 This file determines if the the transaction of the USB TMC 58 This file determines if the the transaction of the USB TMC
59 device is to be automatically aborted if there is any error. 59 device is to be automatically aborted if there is any error.
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 @@
1What: /sys/class/ 1What: /sys/class/
2Date: Febuary 2006 2Date: Febuary 2006
3Contact: Greg Kroah-Hartman <gregkh@suse.de> 3Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
4Description: 4Description:
5 The /sys/class directory will consist of a group of 5 The /sys/class directory will consist of a group of
6 subdirectories describing individual classes of devices 6 subdirectories describing individual classes of devices
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 @@
1What: /sys/devices 1What: /sys/devices
2Date: February 2006 2Date: February 2006
3Contact: Greg Kroah-Hartman <gregkh@suse.de> 3Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
4Description: 4Description:
5 The /sys/devices tree contains a snapshot of the 5 The /sys/devices tree contains a snapshot of the
6 internal state of the kernel device tree. Devices will 6 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 @@
1What: /sys/devices/socX
2Date: January 2012
3contact: Lee Jones <lee.jones@linaro.org>
4Description:
5 The /sys/devices/ directory contains a sub-directory for each
6 System-on-Chip (SoC) device on a running platform. Information
7 regarding each SoC can be obtained by reading sysfs files. This
8 functionality is only available if implemented by the platform.
9
10 The directory created for each SoC will also house information
11 about devices which are commonly contained in /sys/devices/platform.
12 It has been agreed that if an SoC device exists, its supported
13 devices would be better suited to appear as children of that SoC.
14
15What: /sys/devices/socX/machine
16Date: January 2012
17contact: Lee Jones <lee.jones@linaro.org>
18Description:
19 Read-only attribute common to all SoCs. Contains the SoC machine
20 name (e.g. Ux500).
21
22What: /sys/devices/socX/family
23Date: January 2012
24contact: Lee Jones <lee.jones@linaro.org>
25Description:
26 Read-only attribute common to all SoCs. Contains SoC family name
27 (e.g. DB8500).
28
29What: /sys/devices/socX/soc_id
30Date: January 2012
31contact: Lee Jones <lee.jones@linaro.org>
32Description:
33 Read-only attribute supported by most SoCs. In the case of
34 ST-Ericsson's chips this contains the SoC serial number.
35
36What: /sys/devices/socX/revision
37Date: January 2012
38contact: Lee Jones <lee.jones@linaro.org>
39Description:
40 Read-only attribute supported by most SoCs. Contains the SoC's
41 manufacturing revision number.
42
43What: /sys/devices/socX/process
44Date: January 2012
45contact: Lee Jones <lee.jones@linaro.org>
46Description:
47 Read-only attribute supported ST-Ericsson's silicon. Contains the
48 the process by which the silicon chip was manufactured.
49
50What: /sys/bus/soc
51Date: January 2012
52contact: Lee Jones <lee.jones@linaro.org>
53Description:
54 The /sys/bus/soc/ directory contains the usual sub-folders
55 expected under most buses. /sys/bus/soc/devices is of particular
56 interest, as it contains a symlink for each SoC device found on
57 the system. Each symlink points back into the aforementioned
58 /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 @@
1What: /sys/devices/platform/samsung/performance_level 1What: /sys/devices/platform/samsung/performance_level
2Date: January 1, 2010 2Date: January 1, 2010
3KernelVersion: 2.6.33 3KernelVersion: 2.6.33
4Contact: Greg Kroah-Hartman <gregkh@suse.de> 4Contact: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
5Description: Some Samsung laptops have different "performance levels" 5Description: Some Samsung laptops have different "performance levels"
6 that are can be modified by a function key, and by this 6 that are can be modified by a function key, and by this
7 sysfs file. These values don't always make a whole lot 7 sysfs file. These values don't always make a whole lot
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 @@
1Read the F-ing Papers! 1Read the Fscking Papers!
2 2
3 3
4This document describes RCU-related publications, and is followed by 4This document describes RCU-related publications, and is followed by
5the corresponding bibtex entries. A number of the publications may 5the corresponding bibtex entries. A number of the publications may
6be found at http://www.rdrop.com/users/paulmck/RCU/. 6be found at http://www.rdrop.com/users/paulmck/RCU/. For others, browsers
7and search engines will usually find what you are looking for.
7 8
8The first thing resembling RCU was published in 1980, when Kung and Lehman 9The first thing resembling RCU was published in 1980, when Kung and Lehman
9[Kung80] recommended use of a garbage collector to defer destruction 10[Kung80] recommended use of a garbage collector to defer destruction
@@ -160,7 +161,26 @@ which Mathieu Desnoyers is now maintaining [MathieuDesnoyers2009URCU]
160[MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made 161[MathieuDesnoyersPhD]. TINY_RCU [PaulEMcKenney2009BloatWatchRCU] made
161its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU]. 162its appearance, as did expedited RCU [PaulEMcKenney2009expeditedRCU].
162The problem of resizeable RCU-protected hash tables may now be on a path 163The problem of resizeable RCU-protected hash tables may now be on a path
163to a solution [JoshTriplett2009RPHash]. 164to a solution [JoshTriplett2009RPHash]. A few academic researchers are now
165using RCU to solve their parallel problems [HariKannan2009DynamicAnalysisRCU].
166
1672010 produced a simpler preemptible-RCU implementation
168based on TREE_RCU [PaulEMcKenney2010SimpleOptRCU], lockdep-RCU
169[PaulEMcKenney2010LockdepRCU], another resizeable RCU-protected hash
170table [HerbertXu2010RCUResizeHash] (this one consuming more memory,
171but allowing arbitrary changes in hash function, as required for DoS
172avoidance in the networking code), realization of the 2009 RCU-protected
173hash table with atomic node move [JoshTriplett2010RPHash], an update on
174the RCU API [PaulEMcKenney2010RCUAPI].
175
1762011 marked the inclusion of Nick Piggin's fully lockless dentry search
177[LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS], an RCU-protected red-black
178tree using software transactional memory to protect concurrent updates
179(strange, but true!) [PhilHoward2011RCUTMRBTree], yet another variant of
180RCU-protected resizeable hash tables [Triplett:2011:RPHash], the 3.0 RCU
181trainwreck [PaulEMcKenney2011RCU3.0trainwreck], and Neil Brown's "Meet the
182Lockers" LWN article [NeilBrown2011MeetTheLockers].
183
164 184
165Bibtex Entries 185Bibtex Entries
166 186
@@ -173,6 +193,14 @@ Bibtex Entries
173,volume="5" 193,volume="5"
174,number="3" 194,number="3"
175,pages="354-382" 195,pages="354-382"
196,note="Available:
197\url{http://portal.acm.org/citation.cfm?id=320619&dl=GUIDE,}
198[Viewed December 3, 2007]"
199,annotation={
200 Use garbage collector to clean up data after everyone is done with it.
201 .
202 Oldest use of something vaguely resembling RCU that I have found.
203}
176} 204}
177 205
178@techreport{Manber82 206@techreport{Manber82
@@ -184,6 +212,31 @@ Bibtex Entries
184,number="82-01-01" 212,number="82-01-01"
185,month="January" 213,month="January"
186,pages="28" 214,pages="28"
215,annotation={
216 .
217 Superseded by Manber84.
218 .
219 Describes concurrent AVL tree implementation. Uses a
220 garbage-collection mechanism to handle concurrent use and deletion
221 of nodes in the tree, but lacks the summary-of-execution-history
222 concept of read-copy locking.
223 .
224 Keeps full list of processes that were active when a given
225 node was to be deleted, and waits until all such processes have
226 -terminated- before allowing this node to be reused. This is
227 not described in great detail -- one could imagine using process
228 IDs for this if the ID space was large enough that overlapping
229 never occurred.
230 .
231 This restriction makes this algorithm unsuitable for use in
232 systems comprised of long-lived processes. It also produces
233 completely unacceptable overhead in systems with large numbers
234 of processes. Finally, it is specific to AVL trees.
235 .
236 Cites Kung80, so not an independent invention, but the first
237 RCU-like usage that does not rely on an automatic garbage
238 collector.
239}
187} 240}
188 241
189@article{Manber84 242@article{Manber84
@@ -195,6 +248,74 @@ Bibtex Entries
195,volume="9" 248,volume="9"
196,number="3" 249,number="3"
197,pages="439-455" 250,pages="439-455"
251,annotation={
252 Describes concurrent AVL tree implementation. Uses a
253 garbage-collection mechanism to handle concurrent use and deletion
254 of nodes in the tree, but lacks the summary-of-execution-history
255 concept of read-copy locking.
256 .
257 Keeps full list of processes that were active when a given
258 node was to be deleted, and waits until all such processes have
259 -terminated- before allowing this node to be reused. This is
260 not described in great detail -- one could imagine using process
261 IDs for this if the ID space was large enough that overlapping
262 never occurred.
263 .
264 This restriction makes this algorithm unsuitable for use in
265 systems comprised of long-lived processes. It also produces
266 completely unacceptable overhead in systems with large numbers
267 of processes. Finally, it is specific to AVL trees.
268}
269}
270
271@Conference{RichardRashid87a
272,Author="Richard Rashid and Avadis Tevanian and Michael Young and
273David Golub and Robert Baron and David Black and William Bolosky and
274Jonathan Chew"
275,Title="Machine-Independent Virtual Memory Management for Paged
276Uniprocessor and Multiprocessor Architectures"
277,Booktitle="{2\textsuperscript{nd} Symposium on Architectural Support
278for Programming Languages and Operating Systems}"
279,Publisher="Association for Computing Machinery"
280,Month="October"
281,Year="1987"
282,pages="31-39"
283,Address="Palo Alto, CA"
284,note="Available:
285\url{http://www.cse.ucsc.edu/~randal/221/rashid-machvm.pdf}
286[Viewed February 17, 2005]"
287,annotation={
288 Describes lazy TLB flush, where one waits for each CPU to pass
289 through a scheduling-clock interrupt before reusing a given range
290 of virtual address. Does not describe how one determines that
291 all CPUs have in fact taken such an interrupt, though there are
292 no shortage of straightforward methods for accomplishing this.
293 .
294 Note that it does not make sense to just wait a fixed amount of
295 time, since a given CPU might have interrupts disabled for an
296 extended amount of time.
297}
298}
299
300@article{BarbaraLiskov1988ArgusCACM
301,author = {Barbara Liskov}
302,title = {Distributed programming in {Argus}}
303,journal = {Commun. ACM}
304,volume = {31}
305,number = {3}
306,year = {1988}
307,issn = {0001-0782}
308,pages = {300--312}
309,doi = {http://doi.acm.org/10.1145/42392.42399}
310,publisher = {ACM}
311,address = {New York, NY, USA}
312,annotation= {
313 At the top of page 307: "Conflicts with deposits and withdrawals
314 are necessary if the reported total is to be up to date. They
315 could be avoided by having total return a sum that is slightly
316 out of date." Relies on semantics -- approximate numerical
317 values sometimes OK.
318}
198} 319}
199 320
200@techreport{Hennessy89 321@techreport{Hennessy89
@@ -216,6 +337,13 @@ Bibtex Entries
216,year="1990" 337,year="1990"
217,number="CS-TR-2222.1" 338,number="CS-TR-2222.1"
218,month="June" 339,month="June"
340,annotation={
341 Concurrent access to skip lists. Has both weak and strong search.
342 Uses concept of ``garbage queue'', but has no real way of cleaning
343 the garbage efficiently.
344 .
345 Appears to be an independent invention of an RCU-like mechanism.
346}
219} 347}
220 348
221@Book{Adams91 349@Book{Adams91
@@ -223,20 +351,15 @@ Bibtex Entries
223,title="Concurrent Programming, Principles, and Practices" 351,title="Concurrent Programming, Principles, and Practices"
224,Publisher="Benjamin Cummins" 352,Publisher="Benjamin Cummins"
225,Year="1991" 353,Year="1991"
354,annotation={
355 Has a few paragraphs describing ``chaotic relaxation'', a
356 numerical analysis technique that allows multiprocessors to
357 avoid synchronization overhead by using possibly-stale data.
358 .
359 Seems like this is descended from yet another independent
360 invention of RCU-like function -- but this is restricted
361 in that reclamation is not necessary.
226} 362}
227
228@phdthesis{HMassalinPhD
229,author="H. Massalin"
230,title="Synthesis: An Efficient Implementation of Fundamental Operating
231System Services"
232,school="Columbia University"
233,address="New York, NY"
234,year="1992"
235,annotation="
236 Mondo optimizing compiler.
237 Wait-free stuff.
238 Good advice: defer work to avoid synchronization.
239"
240} 363}
241 364
242@unpublished{Jacobson93 365@unpublished{Jacobson93
@@ -244,7 +367,13 @@ System Services"
244,title="Avoid Read-Side Locking Via Delayed Free" 367,title="Avoid Read-Side Locking Via Delayed Free"
245,year="1993" 368,year="1993"
246,month="September" 369,month="September"
247,note="Verbal discussion" 370,note="private communication"
371,annotation={
372 Use fixed time delay to approximate grace period. Very simple,
373 but subject to random memory corruption under heavy load.
374 .
375 Independent invention of RCU-like mechanism.
376}
248} 377}
249 378
250@Conference{AjuJohn95 379@Conference{AjuJohn95
@@ -256,6 +385,17 @@ System Services"
256,Year="1995" 385,Year="1995"
257,pages="11-23" 386,pages="11-23"
258,Address="New Orleans, LA" 387,Address="New Orleans, LA"
388,note="Available:
389\url{https://www.usenix.org/publications/library/proceedings/neworl/full_papers/john.a}
390[Viewed October 1, 2010]"
391,annotation={
392 Age vnodes out of the cache, and have a fixed time set by a kernel
393 parameter. Not clear that all races were in fact correctly handled.
394 Used a 20-minute time by default, which would most definitely not
395 be suitable during DoS attacks or virus scans.
396 .
397 Apparently independent invention of RCU-like mechanism.
398}
259} 399}
260 400
261@conference{Pu95a, 401@conference{Pu95a,
@@ -301,31 +441,47 @@ Utilizing Execution History and Thread Monitoring"
301,institution="US Patent and Trademark Office" 441,institution="US Patent and Trademark Office"
302,address="Washington, DC" 442,address="Washington, DC"
303,year="1995" 443,year="1995"
304,number="US Patent 5,442,758 (contributed under GPL)" 444,number="US Patent 5,442,758"
305,month="August" 445,month="August"
446,annotation={
447 Describes the parallel RCU infrastructure. Includes NUMA aspect
448 (structure of bitmap can reflect bus structure of computer system).
449 .
450 Another independent invention of an RCU-like mechanism, but the
451 "real" RCU this time!
452}
306} 453}
307 454
308@techreport{Slingwine97 455@techreport{Slingwine97
309,author="John D. Slingwine and Paul E. McKenney" 456,author="John D. Slingwine and Paul E. McKenney"
310,title="Method for maintaining data coherency using thread 457,title="Method for Maintaining Data Coherency Using Thread Activity
311activity summaries in a multicomputer system" 458Summaries in a Multicomputer System"
312,institution="US Patent and Trademark Office" 459,institution="US Patent and Trademark Office"
313,address="Washington, DC" 460,address="Washington, DC"
314,year="1997" 461,year="1997"
315,number="US Patent 5,608,893 (contributed under GPL)" 462,number="US Patent 5,608,893"
316,month="March" 463,month="March"
464,pages="19"
465,annotation={
466 Describes use of RCU to synchronize data between a pair of
467 SMP/NUMA computer systems.
468}
317} 469}
318 470
319@techreport{Slingwine98 471@techreport{Slingwine98
320,author="John D. Slingwine and Paul E. McKenney" 472,author="John D. Slingwine and Paul E. McKenney"
321,title="Apparatus and method for achieving reduced overhead 473,title="Apparatus and Method for Achieving Reduced Overhead Mutual
322mutual exclusion and maintaining coherency in a multiprocessor 474Exclusion and Maintaining Coherency in a Multiprocessor System
323system utilizing execution history and thread monitoring" 475Utilizing Execution History and Thread Monitoring"
324,institution="US Patent and Trademark Office" 476,institution="US Patent and Trademark Office"
325,address="Washington, DC" 477,address="Washington, DC"
326,year="1998" 478,year="1998"
327,number="US Patent 5,727,209 (contributed under GPL)" 479,number="US Patent 5,727,209"
328,month="March" 480,month="March"
481,annotation={
482 Describes doing an atomic update by copying the data item and
483 then substituting it into the data structure.
484}
329} 485}
330 486
331@Conference{McKenney98 487@Conference{McKenney98
@@ -337,6 +493,15 @@ Problems"
337,Year="1998" 493,Year="1998"
338,pages="509-518" 494,pages="509-518"
339,Address="Las Vegas, NV" 495,Address="Las Vegas, NV"
496,note="Available:
497\url{http://www.rdrop.com/users/paulmck/RCU/rclockpdcsproof.pdf}
498[Viewed December 3, 2007]"
499,annotation={
500 Describes and analyzes RCU mechanism in DYNIX/ptx. Describes
501 application to linked list update and log-buffer flushing.
502 Defines 'quiescent state'. Includes both measured and analytic
503 evaluation.
504}
340} 505}
341 506
342@Conference{Gamsa99 507@Conference{Gamsa99
@@ -349,18 +514,76 @@ Operating System Design and Implementation}"
349,Year="1999" 514,Year="1999"
350,pages="87-100" 515,pages="87-100"
351,Address="New Orleans, LA" 516,Address="New Orleans, LA"
517,note="Available:
518\url{http://www.usenix.org/events/osdi99/full_papers/gamsa/gamsa.pdf}
519[Viewed August 30, 2006]"
520,annotation={
521 Use of RCU-like facility in K42/Tornado. Another independent
522 invention of RCU.
523 See especially pages 7-9 (Section 5).
524}
525}
526
527@unpublished{RustyRussell2000a
528,Author="Rusty Russell"
529,Title="Re: modular net drivers"
530,month="June"
531,year="2000"
532,day="23"
533,note="Available:
534\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00250.html}
535[Viewed April 10, 2006]"
536,annotation={
537 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
538 Yet another independent invention of RCU.
539 Outline of algorithm to unload modules...
540 .
541 Appeared on net-dev mailing list.
542}
543}
544
545@unpublished{RustyRussell2000b
546,Author="Rusty Russell"
547,Title="Re: modular net drivers"
548,month="June"
549,year="2000"
550,day="24"
551,note="Available:
552\url{http://oss.sgi.com/projects/netdev/archive/2000-06/msg00254.html}
553[Viewed April 10, 2006]"
554,annotation={
555 Proto-RCU proposal from Phil Rumpf and Rusty Russell.
556 .
557 Appeared on net-dev mailing list.
558}
559}
560
561@unpublished{McKenney01b
562,Author="Paul E. McKenney and Dipankar Sarma"
563,Title="Read-Copy Update Mutual Exclusion in {Linux}"
564,month="February"
565,year="2001"
566,note="Available:
567\url{http://lse.sourceforge.net/locking/rcu/rcupdate_doc.html}
568[Viewed October 18, 2004]"
569,annotation={
570 Prototypical Linux documentation for RCU.
571}
352} 572}
353 573
354@techreport{Slingwine01 574@techreport{Slingwine01
355,author="John D. Slingwine and Paul E. McKenney" 575,author="John D. Slingwine and Paul E. McKenney"
356,title="Apparatus and method for achieving reduced overhead 576,title="Apparatus and Method for Achieving Reduced Overhead Mutual
357mutual exclusion and maintaining coherency in a multiprocessor 577Exclusion and Maintaining Coherency in a Multiprocessor System
358system utilizing execution history and thread monitoring" 578Utilizing Execution History and Thread Monitoring"
359,institution="US Patent and Trademark Office" 579,institution="US Patent and Trademark Office"
360,address="Washington, DC" 580,address="Washington, DC"
361,year="2001" 581,year="2001"
362,number="US Patent 5,219,690 (contributed under GPL)" 582,number="US Patent 6,219,690"
363,month="April" 583,month="April"
584,annotation={
585 'Change in mode' aspect of RCU. Can be thought of as a lazy barrier.
586}
364} 587}
365 588
366@Conference{McKenney01a 589@Conference{McKenney01a
@@ -372,14 +595,61 @@ Orran Krieger and Rusty Russell and Dipankar Sarma and Maneesh Soni"
372,Year="2001" 595,Year="2001"
373,note="Available: 596,note="Available:
374\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php} 597\url{http://www.linuxsymposium.org/2001/abstracts/readcopy.php}
375\url{http://www.rdrop.com/users/paulmck/rclock/rclock_OLS.2001.05.01c.pdf} 598\url{http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf}
376[Viewed June 23, 2004]" 599[Viewed June 23, 2004]"
377annotation=" 600,annotation={
378Described RCU, and presented some patches implementing and using it in 601 Described RCU, and presented some patches implementing and using
379the Linux kernel. 602 it in the Linux kernel.
603}
604}
605
606@unpublished{McKenney01f
607,Author="Paul E. McKenney"
608,Title="{RFC:} patch to allow lock-free traversal of lists with insertion"
609,month="October"
610,year="2001"
611,note="Available:
612\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100259266316456&w=2}
613[Viewed June 23, 2004]"
614,annotation="
615 Memory-barrier and Alpha thread. 100 messages, not too bad...
616"
617}
618
619@unpublished{Spraul01
620,Author="Manfred Spraul"
621,Title="Re: {RFC:} patch to allow lock-free traversal of lists with insertion"
622,month="October"
623,year="2001"
624,note="Available:
625\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=100264675012867&w=2}
626[Viewed June 23, 2004]"
627,annotation="
628 Suggested burying memory barriers in Linux's list-manipulation
629 primitives.
380" 630"
381} 631}
382 632
633@unpublished{LinusTorvalds2001a
634,Author="Linus Torvalds"
635,Title="{Re:} {[Lse-tech]} {Re:} {RFC:} patch to allow lock-free traversal of lists with insertion"
636,month="October"
637,year="2001"
638,note="Available:
639\url{http://lkml.org/lkml/2001/10/13/105}
640[Viewed August 21, 2004]"
641}
642
643@unpublished{Blanchard02a
644,Author="Anton Blanchard"
645,Title="some RCU dcache and ratcache results"
646,month="March"
647,year="2002"
648,note="Available:
649\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=101637107412972&w=2}
650[Viewed October 18, 2004]"
651}
652
383@Conference{Linder02a 653@Conference{Linder02a
384,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni" 654,Author="Hanna Linder and Dipankar Sarma and Maneesh Soni"
385,Title="Scalability of the Directory Entry Cache" 655,Title="Scalability of the Directory Entry Cache"
@@ -387,6 +657,10 @@ the Linux kernel.
387,Month="June" 657,Month="June"
388,Year="2002" 658,Year="2002"
389,pages="289-300" 659,pages="289-300"
660,annotation="
661 Measured scalability of Linux 2.4 kernel's directory-entry cache
662 (dcache), and measured some scalability enhancements.
663"
390} 664}
391 665
392@Conference{McKenney02a 666@Conference{McKenney02a
@@ -400,49 +674,76 @@ Andrea Arcangeli and Andi Kleen and Orran Krieger and Rusty Russell"
400,note="Available: 674,note="Available:
401\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz} 675\url{http://www.linux.org.uk/~ajh/ols2002_proceedings.pdf.gz}
402[Viewed June 23, 2004]" 676[Viewed June 23, 2004]"
677,annotation="
678 Presented and compared a number of RCU implementations for the
679 Linux kernel.
680"
403} 681}
404 682
405@conference{Michael02a 683@unpublished{Sarma02a
406,author="Maged M. Michael" 684,Author="Dipankar Sarma"
407,title="Safe Memory Reclamation for Dynamic Lock-Free Objects Using Atomic 685,Title="specweb99: dcache scalability results"
408Reads and Writes" 686,month="July"
409,Year="2002" 687,year="2002"
410,Month="August" 688,note="Available:
411,booktitle="{Proceedings of the 21\textsuperscript{st} Annual ACM 689\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=102645767914212&w=2}
412Symposium on Principles of Distributed Computing}" 690[Viewed June 23, 2004]"
413,pages="21-30"
414,annotation=" 691,annotation="
415 Each thread keeps an array of pointers to items that it is 692 Compare fastwalk and RCU for dcache. RCU won.
416 currently referencing. Sort of an inside-out garbage collection
417 mechanism, but one that requires the accessing code to explicitly
418 state its needs. Also requires read-side memory barriers on
419 most architectures.
420" 693"
421} 694}
422 695
423@conference{Michael02b 696@unpublished{Barbieri02
424,author="Maged M. Michael" 697,Author="Luca Barbieri"
425,title="High Performance Dynamic Lock-Free Hash Tables and List-Based Sets" 698,Title="Re: {[PATCH]} Initial support for struct {vfs\_cred}"
426,Year="2002" 699,month="August"
427,Month="August" 700,year="2002"
428,booktitle="{Proceedings of the 14\textsuperscript{th} Annual ACM 701,note="Available:
429Symposium on Parallel 702\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103082050621241&w=2}
430Algorithms and Architecture}" 703[Viewed: June 23, 2004]"
431,pages="73-82"
432,annotation=" 704,annotation="
433 Like the title says... 705 Suggested RCU for vfs\_shared\_cred.
434" 706"
435} 707}
436 708
437@InProceedings{HerlihyLM02 709@unpublished{Dickins02a
438,author={Maurice Herlihy and Victor Luchangco and Mark Moir} 710,author="Hugh Dickins"
439,title="The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, 711,title="Use RCU for System-V IPC"
440Lock-Free Data Structures" 712,year="2002"
441,booktitle={Proceedings of 16\textsuperscript{th} International 713,month="October"
442Symposium on Distributed Computing} 714,note="private communication"
443,year=2002 715}
716
717@unpublished{Sarma02b
718,Author="Dipankar Sarma"
719,Title="Some dcache\_rcu benchmark numbers"
444,month="October" 720,month="October"
445,pages="339-353" 721,year="2002"
722,note="Available:
723\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=103462075416638&w=2}
724[Viewed June 23, 2004]"
725,annotation="
726 Performance of dcache RCU on kernbench for 16x NUMA-Q and 1x,
727 2x, and 4x systems. RCU does no harm, and helps on 16x.
728"
729}
730
731@unpublished{LinusTorvalds2003a
732,Author="Linus Torvalds"
733,Title="Re: {[PATCH]} small fixes in brlock.h"
734,month="March"
735,year="2003"
736,note="Available:
737\url{http://lkml.org/lkml/2003/3/9/205}
738[Viewed March 13, 2006]"
739,annotation="
740 Linus suggests replacing brlock with RCU and/or seqlocks:
741 .
742 'It's entirely possible that the current user could be replaced
743 by RCU and/or seqlocks, and we could get rid of brlocks entirely.'
744 .
745 Steve Hemminger responds by replacing them with RCU.
746"
446} 747}
447 748
448@article{Appavoo03a 749@article{Appavoo03a
@@ -457,6 +758,20 @@ B. Rosenburg and M. Stumm and J. Xenidis"
457,volume="42" 758,volume="42"
458,number="1" 759,number="1"
459,pages="60-76" 760,pages="60-76"
761,annotation="
762 Use of RCU to enable hot-swapping for autonomic behavior in K42.
763"
764}
765
766@unpublished{Seigh03
767,author="Joseph W. {Seigh II}"
768,title="Read Copy Update"
769,Year="2003"
770,Month="March"
771,note="email correspondence"
772,annotation="
773 Described the relationship of the VM/XA passive serialization to RCU.
774"
460} 775}
461 776
462@Conference{Arcangeli03 777@Conference{Arcangeli03
@@ -470,6 +785,27 @@ Dipankar Sarma"
470,year="2003" 785,year="2003"
471,month="June" 786,month="June"
472,pages="297-310" 787,pages="297-310"
788,note="Available:
789\url{http://www.rdrop.com/users/paulmck/RCU/rcu.FREENIX.2003.06.14.pdf}
790[Viewed November 21, 2007]"
791,annotation="
792 Compared updated RCU implementations for the Linux kernel, and
793 described System V IPC use of RCU, including order-of-magnitude
794 performance improvements.
795"
796}
797
798@Conference{Soules03a
799,Author="Craig A. N. Soules and Jonathan Appavoo and Kevin Hui and
800Dilma {Da Silva} and Gregory R. Ganger and Orran Krieger and
801Michael Stumm and Robert W. Wisniewski and Marc Auslander and
802Michal Ostrowski and Bryan Rosenburg and Jimi Xenidis"
803,Title="System Support for Online Reconfiguration"
804,Booktitle="Proceedings of the 2003 USENIX Annual Technical Conference"
805,Publisher="USENIX Association"
806,year="2003"
807,month="June"
808,pages="141-154"
473} 809}
474 810
475@article{McKenney03a 811@article{McKenney03a
@@ -481,6 +817,22 @@ Dipankar Sarma"
481,volume="1" 817,volume="1"
482,number="114" 818,number="114"
483,pages="18-26" 819,pages="18-26"
820,note="Available:
821\url{http://www.linuxjournal.com/article/6993}
822[Viewed November 14, 2007]"
823,annotation="
824 Reader-friendly intro to RCU, with the infamous old-man-and-brat
825 cartoon.
826"
827}
828
829@unpublished{Sarma03a
830,Author="Dipankar Sarma"
831,Title="RCU low latency patches"
832,month="December"
833,year="2003"
834,note="Message ID: 20031222180114.GA2248@in.ibm.com"
835,annotation="dipankar/ct.2004.03.27/RCUll.2003.12.22.patch"
484} 836}
485 837
486@techreport{Friedberg03a 838@techreport{Friedberg03a
@@ -489,9 +841,14 @@ Dipankar Sarma"
489,institution="US Patent and Trademark Office" 841,institution="US Patent and Trademark Office"
490,address="Washington, DC" 842,address="Washington, DC"
491,year="2003" 843,year="2003"
492,number="US Patent 6,662,184 (contributed under GPL)" 844,number="US Patent 6,662,184"
493,month="December" 845,month="December"
494,pages="112" 846,pages="112"
847,annotation="
848 Applies RCU to a wildcard-search Patricia tree in order to permit
849 synchronization-free lookup. RCU is used to retain removed nodes
850 for a grace period before freeing them.
851"
495} 852}
496 853
497@article{McKenney04a 854@article{McKenney04a
@@ -503,6 +860,12 @@ Dipankar Sarma"
503,volume="1" 860,volume="1"
504,number="118" 861,number="118"
505,pages="38-46" 862,pages="38-46"
863,note="Available:
864\url{http://www.linuxjournal.com/node/7124}
865[Viewed December 26, 2010]"
866,annotation="
867 Reader friendly intro to dcache and RCU.
868"
506} 869}
507 870
508@Conference{McKenney04b 871@Conference{McKenney04b
@@ -514,8 +877,83 @@ Dipankar Sarma"
514,Address="Adelaide, Australia" 877,Address="Adelaide, Australia"
515,note="Available: 878,note="Available:
516\url{http://www.linux.org.au/conf/2004/abstracts.html#90} 879\url{http://www.linux.org.au/conf/2004/abstracts.html#90}
517\url{http://www.rdrop.com/users/paulmck/rclock/lockperf.2004.01.17a.pdf} 880\url{http://www.rdrop.com/users/paulmck/RCU/lockperf.2004.01.17a.pdf}
518[Viewed June 23, 2004]" 881[Viewed June 23, 2004]"
882,annotation="
883 Compares performance of RCU to that of other locking primitives
884 over a number of CPUs (x86, Opteron, Itanium, and PPC).
885"
886}
887
888@unpublished{Sarma04a
889,Author="Dipankar Sarma"
890,Title="{[PATCH]} {RCU} for low latency (experimental)"
891,month="March"
892,year="2004"
893,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108003746402892&w=2}"
894,annotation="Head of thread: dipankar/2004.03.23/rcu-low-lat.1.patch"
895}
896
897@unpublished{Sarma04b
898,Author="Dipankar Sarma"
899,Title="Re: {[PATCH]} {RCU} for low latency (experimental)"
900,month="March"
901,year="2004"
902,note="\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108016474829546&w=2}"
903,annotation="dipankar/rcuth.2004.03.24/rcu-throttle.patch"
904}
905
906@unpublished{Spraul04a
907,Author="Manfred Spraul"
908,Title="[RFC] 0/5 rcu lock update"
909,month="May"
910,year="2004"
911,note="Available:
912\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108546407726602&w=2}
913[Viewed June 23, 2004]"
914,annotation="
915 Hierarchical-bitmap patch for RCU infrastructure.
916"
917}
918
919@unpublished{Steiner04a
920,Author="Jack Steiner"
921,Title="Re: [Lse-tech] [RFC, PATCH] 1/5 rcu lock update:
922Add per-cpu batch counter"
923,month="May"
924,year="2004"
925,note="Available:
926\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=108551764515332&w=2}
927[Viewed June 23, 2004]"
928,annotation={
929 RCU runs reasonably on a 512-CPU SGI using Manfred Spraul's patches,
930 which may be found at:
931 https://lkml.org/lkml/2004/5/20/49 (split vars into cachelines)
932 https://lkml.org/lkml/2004/5/22/114 (cpu_quiet() patch)
933 https://lkml.org/lkml/2004/5/25/24 (0/5)
934 https://lkml.org/lkml/2004/5/25/23 (1/5)
935 https://lkml.org/lkml/2004/5/25/265 (works for Jack)
936 https://lkml.org/lkml/2004/5/25/20 (2/5)
937 https://lkml.org/lkml/2004/5/25/22 (3/5)
938 https://lkml.org/lkml/2004/5/25/19 (4/5)
939 https://lkml.org/lkml/2004/5/25/21 (5/5)
940}
941}
942
943@Conference{Sarma04c
944,Author="Dipankar Sarma and Paul E. McKenney"
945,Title="Making {RCU} Safe for Deep Sub-Millisecond Response
946Realtime Applications"
947,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference
948(FREENIX Track)"
949,Publisher="USENIX Association"
950,year="2004"
951,month="June"
952,pages="182-191"
953,annotation="
954 Describes and compares a number of modifications to the Linux RCU
955 implementation that make it friendly to realtime applications.
956"
519} 957}
520 958
521@phdthesis{PaulEdwardMcKenneyPhD 959@phdthesis{PaulEdwardMcKenneyPhD
@@ -529,17 +967,118 @@ Oregon Health and Sciences University"
529,note="Available: 967,note="Available:
530\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf} 968\url{http://www.rdrop.com/users/paulmck/RCU/RCUdissertation.2004.07.14e1.pdf}
531[Viewed October 15, 2004]" 969[Viewed October 15, 2004]"
970,annotation="
971 Describes RCU implementations and presents design patterns
972 corresponding to common uses of RCU in several operating-system
973 kernels.
974"
532} 975}
533 976
534@Conference{Sarma04c 977@unpublished{PaulEMcKenney2004rcu:dereference
535,Author="Dipankar Sarma and Paul E. McKenney" 978,Author="Dipankar Sarma"
536,Title="Making RCU Safe for Deep Sub-Millisecond Response Realtime Applications" 979,Title="{Re: RCU : Abstracted RCU dereferencing [5/5]}"
537,Booktitle="Proceedings of the 2004 USENIX Annual Technical Conference 980,month="August"
538(FREENIX Track)"
539,Publisher="USENIX Association"
540,year="2004" 981,year="2004"
541,month="June" 982,note="Available:
542,pages="182-191" 983\url{http://lkml.org/lkml/2004/8/6/237}
984[Viewed June 8, 2010]"
985,annotation="
986 Introduce rcu_dereference().
987"
988}
989
990@unpublished{JimHouston04a
991,Author="Jim Houston"
992,Title="{[RFC\&PATCH] Alternative {RCU} implementation}"
993,month="August"
994,year="2004"
995,note="Available:
996\url{http://lkml.org/lkml/2004/8/30/87}
997[Viewed February 17, 2005]"
998,annotation="
999 Uses active code in rcu_read_lock() and rcu_read_unlock() to
1000 make RCU happen, allowing RCU to function on CPUs that do not
1001 receive a scheduling-clock interrupt.
1002"
1003}
1004
1005@unpublished{TomHart04a
1006,Author="Thomas E. Hart"
1007,Title="Master's Thesis: Applying Lock-free Techniques to the {Linux} Kernel"
1008,month="October"
1009,year="2004"
1010,note="Available:
1011\url{http://www.cs.toronto.edu/~tomhart/masters_thesis.html}
1012[Viewed October 15, 2004]"
1013,annotation="
1014 Proposes comparing RCU to lock-free methods for the Linux kernel.
1015"
1016}
1017
1018@unpublished{Vaddagiri04a
1019,Author="Srivatsa Vaddagiri"
1020,Title="Subject: [RFC] Use RCU for tcp\_ehash lookup"
1021,month="October"
1022,year="2004"
1023,note="Available:
1024\url{http://marc.theaimsgroup.com/?t=109395731700004&r=1&w=2}
1025[Viewed October 18, 2004]"
1026,annotation="
1027 Srivatsa's RCU patch for tcp_ehash lookup.
1028"
1029}
1030
1031@unpublished{Thirumalai04a
1032,Author="Ravikiran Thirumalai"
1033,Title="Subject: [patchset] Lockfree fd lookup 0 of 5"
1034,month="October"
1035,year="2004"
1036,note="Available:
1037\url{http://marc.theaimsgroup.com/?t=109144217400003&r=1&w=2}
1038[Viewed October 18, 2004]"
1039,annotation="
1040 Ravikiran's lockfree FD patch.
1041"
1042}
1043
1044@unpublished{Thirumalai04b
1045,Author="Ravikiran Thirumalai"
1046,Title="Subject: Re: [patchset] Lockfree fd lookup 0 of 5"
1047,month="October"
1048,year="2004"
1049,note="Available:
1050\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=109152521410459&w=2}
1051[Viewed October 18, 2004]"
1052,annotation="
1053 Ravikiran's lockfree FD patch.
1054"
1055}
1056
1057@unpublished{PaulEMcKenney2004rcu:assign:pointer
1058,Author="Paul E. McKenney"
1059,Title="{[PATCH 1/3] RCU: \url{rcu_assign_pointer()} removal of memory barriers}"
1060,month="October"
1061,year="2004"
1062,note="Available:
1063\url{http://lkml.org/lkml/2004/10/23/241}
1064[Viewed June 8, 2010]"
1065,annotation="
1066 Introduce rcu_assign_pointer().
1067"
1068}
1069
1070@unpublished{JamesMorris04a
1071,Author="James Morris"
1072,Title="{[PATCH 2/3] SELinux} scalability - convert {AVC} to {RCU}"
1073,day="15"
1074,month="November"
1075,year="2004"
1076,note="Available:
1077\url{http://marc.theaimsgroup.com/?l=linux-kernel&m=110054979416004&w=2}
1078[Viewed December 10, 2004]"
1079,annotation="
1080 James Morris posts Kaigai Kohei's patch to LKML.
1081"
543} 1082}
544 1083
545@unpublished{JamesMorris04b 1084@unpublished{JamesMorris04b
@@ -550,6 +1089,85 @@ Oregon Health and Sciences University"
550,note="Available: 1089,note="Available:
551\url{http://www.livejournal.com/users/james_morris/2153.html} 1090\url{http://www.livejournal.com/users/james_morris/2153.html}
552[Viewed December 10, 2004]" 1091[Viewed December 10, 2004]"
1092,annotation="
1093 RCU helps SELinux performance. ;-) Made LWN.
1094"
1095}
1096
1097@unpublished{PaulMcKenney2005RCUSemantics
1098,Author="Paul E. McKenney and Jonathan Walpole"
1099,Title="{RCU} Semantics: A First Attempt"
1100,month="January"
1101,year="2005"
1102,day="30"
1103,note="Available:
1104\url{http://www.rdrop.com/users/paulmck/RCU/rcu-semantics.2005.01.30a.pdf}
1105[Viewed December 6, 2009]"
1106,annotation="
1107 Early derivation of RCU semantics.
1108"
1109}
1110
1111@unpublished{PaulMcKenney2005e
1112,Author="Paul E. McKenney"
1113,Title="Real-Time Preemption and {RCU}"
1114,month="March"
1115,year="2005"
1116,day="17"
1117,note="Available:
1118\url{http://lkml.org/lkml/2005/3/17/199}
1119[Viewed September 5, 2005]"
1120,annotation="
1121 First posting showing how RCU can be safely adapted for
1122 preemptable RCU read side critical sections.
1123"
1124}
1125
1126@unpublished{EsbenNeilsen2005a
1127,Author="Esben Neilsen"
1128,Title="Re: Real-Time Preemption and {RCU}"
1129,month="March"
1130,year="2005"
1131,day="18"
1132,note="Available:
1133\url{http://lkml.org/lkml/2005/3/18/122}
1134[Viewed March 30, 2006]"
1135,annotation="
1136 Esben Neilsen suggests read-side suppression of grace-period
1137 processing for crude-but-workable realtime RCU. The downside
1138 is indefinite grace periods...But this is OK for experimentation
1139 and testing.
1140"
1141}
1142
1143@unpublished{TomHart05a
1144,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown"
1145,Title="Efficient Memory Reclamation is Necessary for Fast Lock-Free
1146Data Structures"
1147,month="March"
1148,year="2005"
1149,note="Available:
1150\url{ftp://ftp.cs.toronto.edu/csrg-technical-reports/515/}
1151[Viewed March 4, 2005]"
1152,annotation="
1153 Comparison of RCU, QBSR, and EBSR. RCU wins for read-mostly
1154 workloads. ;-)
1155"
1156}
1157
1158@unpublished{JonCorbet2005DeprecateSyncKernel
1159,Author="Jonathan Corbet"
1160,Title="API change: synchronize_kernel() deprecated"
1161,month="May"
1162,day="3"
1163,year="2005"
1164,note="Available:
1165\url{http://lwn.net/Articles/134484/}
1166[Viewed May 3, 2005]"
1167,annotation="
1168 Jon Corbet describes deprecation of synchronize_kernel()
1169 in favor of synchronize_rcu() and synchronize_sched().
1170"
553} 1171}
554 1172
555@unpublished{PaulMcKenney05a 1173@unpublished{PaulMcKenney05a
@@ -568,7 +1186,7 @@ Oregon Health and Sciences University"
568 1186
569@conference{PaulMcKenney05b 1187@conference{PaulMcKenney05b
570,Author="Paul E. McKenney and Dipankar Sarma" 1188,Author="Paul E. McKenney and Dipankar Sarma"
571,Title="Towards Hard Realtime Response from the Linux Kernel on SMP Hardware" 1189,Title="Towards Hard Realtime Response from the {Linux} Kernel on {SMP} Hardware"
572,Booktitle="linux.conf.au 2005" 1190,Booktitle="linux.conf.au 2005"
573,month="April" 1191,month="April"
574,year="2005" 1192,year="2005"
@@ -578,6 +1196,103 @@ Oregon Health and Sciences University"
578[Viewed May 13, 2005]" 1196[Viewed May 13, 2005]"
579,annotation=" 1197,annotation="
580 Realtime turns into making RCU yet more realtime friendly. 1198 Realtime turns into making RCU yet more realtime friendly.
1199 http://lca2005.linux.org.au/Papers/Paul%20McKenney/Towards%20Hard%20Realtime%20Response%20from%20the%20Linux%20Kernel/LKS.2005.04.22a.pdf
1200"
1201}
1202
1203@unpublished{PaulEMcKenneyHomePage
1204,Author="Paul E. McKenney"
1205,Title="{Paul} {E.} {McKenney}"
1206,month="May"
1207,year="2005"
1208,note="Available:
1209\url{http://www.rdrop.com/users/paulmck/}
1210[Viewed May 25, 2005]"
1211,annotation="
1212 Paul McKenney's home page.
1213"
1214}
1215
1216@unpublished{PaulEMcKenneyRCUPage
1217,Author="Paul E. McKenney"
1218,Title="Read-Copy Update {(RCU)}"
1219,month="May"
1220,year="2005"
1221,note="Available:
1222\url{http://www.rdrop.com/users/paulmck/RCU}
1223[Viewed May 25, 2005]"
1224,annotation="
1225 Paul McKenney's RCU page.
1226"
1227}
1228
1229@unpublished{JosephSeigh2005a
1230,Author="Joseph Seigh"
1231,Title="{RCU}+{SMR} (hazard pointers)"
1232,month="July"
1233,year="2005"
1234,note="Personal communication"
1235,annotation="
1236 Joe Seigh announcing his atomic-ptr-plus project.
1237 http://sourceforge.net/projects/atomic-ptr-plus/
1238"
1239}
1240
1241@unpublished{JosephSeigh2005b
1242,Author="Joseph Seigh"
1243,Title="Lock-free synchronization primitives"
1244,month="July"
1245,day="6"
1246,year="2005"
1247,note="Available:
1248\url{http://sourceforge.net/projects/atomic-ptr-plus/}
1249[Viewed August 8, 2005]"
1250,annotation="
1251 Joe Seigh's atomic-ptr-plus project.
1252"
1253}
1254
1255@unpublished{PaulMcKenney2005c
1256,Author="Paul E.McKenney"
1257,Title="{[RFC,PATCH] RCU} and {CONFIG\_PREEMPT\_RT} sane patch"
1258,month="August"
1259,day="1"
1260,year="2005"
1261,note="Available:
1262\url{http://lkml.org/lkml/2005/8/1/155}
1263[Viewed March 14, 2006]"
1264,annotation="
1265 First operating counter-based realtime RCU patch posted to LKML.
1266"
1267}
1268
1269@unpublished{PaulMcKenney2005d
1270,Author="Paul E. McKenney"
1271,Title="Re: [Fwd: Re: [patch] Real-Time Preemption, -RT-2.6.13-rc4-V0.7.52-01]"
1272,month="August"
1273,day="8"
1274,year="2005"
1275,note="Available:
1276\url{http://lkml.org/lkml/2005/8/8/108}
1277[Viewed March 14, 2006]"
1278,annotation="
1279 First operating counter-based realtime RCU patch posted to LKML,
1280 but fixed so that various unusual combinations of configuration
1281 parameters all function properly.
1282"
1283}
1284
1285@unpublished{PaulMcKenney2005rcutorture
1286,Author="Paul E. McKenney"
1287,Title="{[PATCH]} {RCU} torture testing"
1288,month="October"
1289,day="1"
1290,year="2005"
1291,note="Available:
1292\url{http://lkml.org/lkml/2005/10/1/70}
1293[Viewed March 14, 2006]"
1294,annotation="
1295 First rcutorture patch.
581" 1296"
582} 1297}
583 1298
@@ -591,22 +1306,39 @@ Distributed Processing Symposium"
591,year="2006" 1306,year="2006"
592,day="25-29" 1307,day="25-29"
593,address="Rhodes, Greece" 1308,address="Rhodes, Greece"
1309,note="Available:
1310\url{http://www.rdrop.com/users/paulmck/RCU/hart_ipdps06.pdf}
1311[Viewed April 28, 2008]"
1312,annotation="
1313 Compares QSBR, HPBR, EBR, and lock-free reference counting.
1314 http://www.cs.toronto.edu/~tomhart/perflab/ipdps06.tgz
1315"
1316}
1317
1318@unpublished{NickPiggin2006radixtree
1319,Author="Nick Piggin"
1320,Title="[patch 3/3] radix-tree: {RCU} lockless readside"
1321,month="June"
1322,day="20"
1323,year="2006"
1324,note="Available:
1325\url{http://lkml.org/lkml/2006/6/20/238}
1326[Viewed March 25, 2008]"
594,annotation=" 1327,annotation="
595 Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free 1328 RCU-protected radix tree.
596 reference counting.
597" 1329"
598} 1330}
599 1331
600@Conference{PaulEMcKenney2006b 1332@Conference{PaulEMcKenney2006b
601,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and 1333,Author="Paul E. McKenney and Dipankar Sarma and Ingo Molnar and
602Suparna Bhattacharya" 1334Suparna Bhattacharya"
603,Title="Extending RCU for Realtime and Embedded Workloads" 1335,Title="Extending {RCU} for Realtime and Embedded Workloads"
604,Booktitle="{Ottawa Linux Symposium}" 1336,Booktitle="{Ottawa Linux Symposium}"
605,Month="July" 1337,Month="July"
606,Year="2006" 1338,Year="2006"
607,pages="v2 123-138" 1339,pages="v2 123-138"
608,note="Available: 1340,note="Available:
609\url{http://www.linuxsymposium.org/2006/index_2006.php} 1341\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
610\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf} 1342\url{http://www.rdrop.com/users/paulmck/RCU/OLSrtRCU.2006.08.11a.pdf}
611[Viewed January 1, 2007]" 1343[Viewed January 1, 2007]"
612,annotation=" 1344,annotation="
@@ -614,6 +1346,37 @@ Suparna Bhattacharya"
614" 1346"
615} 1347}
616 1348
1349@unpublished{WikipediaRCU
1350,Author="Paul E. McKenney and Chris Purcell and Algae and Ben Schumin and
1351Gaius Cornelius and Qwertyus and Neil Conway and Sbw and Blainster and
1352Canis Rufus and Zoicon5 and Anome and Hal Eisen"
1353,Title="Read-Copy Update"
1354,month="July"
1355,day="8"
1356,year="2006"
1357,note="Available:
1358\url{http://en.wikipedia.org/wiki/Read-copy-update}
1359[Viewed August 21, 2006]"
1360,annotation="
1361 Wikipedia RCU page as of July 8 2006.
1362"
1363}
1364
1365@Conference{NickPiggin2006LocklessPageCache
1366,Author="Nick Piggin"
1367,Title="A Lockless Pagecache in Linux---Introduction, Progress, Performance"
1368,Booktitle="{Ottawa Linux Symposium}"
1369,Month="July"
1370,Year="2006"
1371,pages="v2 249-254"
1372,note="Available:
1373\url{http://www.linuxsymposium.org/2006/view_abstract.php?content_key=184}
1374[Viewed January 11, 2009]"
1375,annotation="
1376 Uses RCU-protected radix tree for a lockless page cache.
1377"
1378}
1379
617@unpublished{PaulEMcKenney2006c 1380@unpublished{PaulEMcKenney2006c
618,Author="Paul E. McKenney" 1381,Author="Paul E. McKenney"
619,Title="Sleepable {RCU}" 1382,Title="Sleepable {RCU}"
@@ -637,29 +1400,301 @@ Revised:
637,day="18" 1400,day="18"
638,year="2006" 1401,year="2006"
639,note="Available: 1402,note="Available:
640\url{http://www.nada.kth.se/~snilsson/public/papers/trash/trash.pdf} 1403\url{http://www.nada.kth.se/~snilsson/publications/TRASH/trash.pdf}
641[Viewed February 24, 2007]" 1404[Viewed March 4, 2011]"
642,annotation=" 1405,annotation="
643 RCU-protected dynamic trie-hash combination. 1406 RCU-protected dynamic trie-hash combination.
644" 1407"
645} 1408}
646 1409
647@unpublished{ThomasEHart2007a 1410@unpublished{ChristophHellwig2006RCU2SRCU
648,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole" 1411,Author="Christoph Hellwig"
649,Title="Performance of memory reclamation for lockless synchronization" 1412,Title="Re: {[-mm PATCH 1/4]} {RCU}: split classic rcu"
650,journal="J. Parallel Distrib. Comput." 1413,month="September"
1414,day="28"
1415,year="2006"
1416,note="Available:
1417\url{http://lkml.org/lkml/2006/9/28/160}
1418[Viewed March 27, 2008]"
1419}
1420
1421@unpublished{PaulEMcKenneyRCUusagePage
1422,Author="Paul E. McKenney"
1423,Title="{RCU} {Linux} Usage"
1424,month="October"
1425,year="2006"
1426,note="Available:
1427\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage.html}
1428[Viewed January 14, 2007]"
1429,annotation="
1430 Paul McKenney's RCU page showing graphs plotting Linux-kernel
1431 usage of RCU.
1432"
1433}
1434
1435@unpublished{PaulEMcKenneyRCUusageRawDataPage
1436,Author="Paul E. McKenney"
1437,Title="Read-Copy Update {(RCU)} Usage in {Linux} Kernel"
1438,month="October"
1439,year="2006"
1440,note="Available:
1441\url{http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html}
1442[Viewed January 14, 2007]"
1443,annotation="
1444 Paul McKenney's RCU page showing Linux usage of RCU in tabular
1445 form, with links to corresponding cscope databases.
1446"
1447}
1448
1449@unpublished{GauthamShenoy2006RCUrwlock
1450,Author="Gautham R. Shenoy"
1451,Title="[PATCH 4/5] lock\_cpu\_hotplug: Redesign - Lightweight implementation of lock\_cpu\_hotplug"
1452,month="October"
1453,year="2006"
1454,day=26
1455,note="Available:
1456\url{http://lkml.org/lkml/2006/10/26/73}
1457[Viewed January 26, 2009]"
1458,annotation="
1459 RCU-based reader-writer lock that allows readers to proceed with
1460 no memory barriers or atomic instruction in absence of writers.
1461 If writer do show up, readers must of course wait as required by
1462 the semantics of reader-writer locking. This is a recursive
1463 lock.
1464"
1465}
1466
1467@unpublished{JensAxboe2006SlowSRCU
1468,Author="Jens Axboe"
1469,Title="Re: [patch] cpufreq: mark \url{cpufreq_tsc()} as
1470\url{core_initcall_sync}"
1471,month="November"
1472,year="2006"
1473,day=17
1474,note="Available:
1475\url{http://lkml.org/lkml/2006/11/17/56}
1476[Viewed May 28, 2007]"
1477,annotation="
1478 SRCU's grace periods are too slow for Jens, even after a
1479 factor-of-three speedup.
1480 Sped-up version of SRCU at http://lkml.org/lkml/2006/11/17/359.
1481"
1482}
1483
1484@unpublished{OlegNesterov2006QRCU
1485,Author="Oleg Nesterov"
1486,Title="Re: [patch] cpufreq: mark {\tt cpufreq\_tsc()} as
1487{\tt core\_initcall\_sync}"
1488,month="November"
1489,year="2006"
1490,day=19
1491,note="Available:
1492\url{http://lkml.org/lkml/2006/11/19/69}
1493[Viewed May 28, 2007]"
1494,annotation="
1495 First cut of QRCU. Expanded/corrected versions followed.
1496 Used to be OlegNesterov2007QRCU, now time-corrected.
1497"
1498}
1499
1500@unpublished{OlegNesterov2006aQRCU
1501,Author="Oleg Nesterov"
1502,Title="Re: [RFC, PATCH 1/2] qrcu: {"quick"} srcu implementation"
1503,month="November"
1504,year="2006"
1505,day=30
1506,note="Available:
1507\url{http://lkml.org/lkml/2006/11/29/330}
1508[Viewed November 26, 2008]"
1509,annotation="
1510 Expanded/corrected version of QRCU.
1511 Used to be OlegNesterov2007aQRCU, now time-corrected.
1512"
1513}
1514
1515@unpublished{EvgeniyPolyakov2006RCUslowdown
1516,Author="Evgeniy Polyakov"
1517,Title="Badness in postponing work"
1518,month="December"
1519,year="2006"
1520,day=05
1521,note="Available:
1522\url{http://www.ioremap.net/node/41}
1523[Viewed October 28, 2008]"
1524,annotation="
1525 Using RCU as a pure delay leads to a 2.5x slowdown in skbs in
1526 the Linux kernel.
1527"
1528}
1529
1530@inproceedings{ChrisMatthews2006ClusteredObjectsRCU
1531,author = {Matthews, Chris and Coady, Yvonne and Appavoo, Jonathan}
1532,title = {Portability events: a programming model for scalable system infrastructures}
1533,booktitle = {PLOS '06: Proceedings of the 3rd workshop on Programming languages and operating systems}
1534,year = {2006}
1535,isbn = {1-59593-577-0}
1536,pages = {11}
1537,location = {San Jose, California}
1538,doi = {http://doi.acm.org/10.1145/1215995.1216006}
1539,publisher = {ACM}
1540,address = {New York, NY, USA}
1541,annotation={
1542 Uses K42's RCU-like functionality to manage clustered-object
1543 lifetimes.
1544}}
1545
1546@article{DilmaDaSilva2006K42
1547,author = {Silva, Dilma Da and Krieger, Orran and Wisniewski, Robert W. and Waterland, Amos and Tam, David and Baumann, Andrew}
1548,title = {K42: an infrastructure for operating system research}
1549,journal = {SIGOPS Oper. Syst. Rev.}
1550,volume = {40}
1551,number = {2}
1552,year = {2006}
1553,issn = {0163-5980}
1554,pages = {34--42}
1555,doi = {http://doi.acm.org/10.1145/1131322.1131333}
1556,publisher = {ACM}
1557,address = {New York, NY, USA}
1558,annotation={
1559 Describes relationship of K42 generations to RCU.
1560}}
1561
1562# CoreyMinyard2007list_splice_rcu
1563@unpublished{CoreyMinyard2007list:splice:rcu
1564,Author="Corey Minyard and Paul E. McKenney"
1565,Title="{[PATCH]} add an {RCU} version of list splicing"
1566,month="January"
1567,year="2007"
1568,day=3
1569,note="Available:
1570\url{http://lkml.org/lkml/2007/1/3/112}
1571[Viewed May 28, 2007]"
1572,annotation="
1573 Patch for list_splice_rcu().
1574"
1575}
1576
1577@unpublished{PaulEMcKenney2007rcubarrier
1578,Author="Paul E. McKenney"
1579,Title="{RCU} and Unloadable Modules"
1580,month="January"
1581,day="14"
1582,year="2007"
1583,note="Available:
1584\url{http://lwn.net/Articles/217484/}
1585[Viewed November 22, 2007]"
1586,annotation="
1587 LWN article introducing the rcu_barrier() primitive.
1588"
1589}
1590
1591@unpublished{PeterZijlstra2007SyncBarrier
1592,Author="Peter Zijlstra and Ingo Molnar"
1593,Title="{[PATCH 3/7]} barrier: a scalable synchonisation barrier"
1594,month="January"
1595,year="2007"
1596,day=28
1597,note="Available:
1598\url{http://lkml.org/lkml/2007/1/28/34}
1599[Viewed March 27, 2008]"
1600,annotation="
1601 RCU-like implementation for frequent updaters and rare readers(!).
1602 Subsumed into QRCU. Maybe...
1603"
1604}
1605
1606@unpublished{PaulEMcKenney2007BoostRCU
1607,Author="Paul E. McKenney"
1608,Title="Priority-Boosting {RCU} Read-Side Critical Sections"
1609,month="February"
1610,day="5"
1611,year="2007"
1612,note="Available:
1613\url{http://lwn.net/Articles/220677/}
1614Revised:
1615\url{http://www.rdrop.com/users/paulmck/RCU/RCUbooststate.2007.04.16a.pdf}
1616[Viewed September 7, 2007]"
1617,annotation="
1618 LWN article introducing RCU priority boosting.
1619"
1620}
1621
1622@unpublished{PaulMcKenney2007QRCUpatch
1623,Author="Paul E. McKenney"
1624,Title="{[PATCH]} {QRCU} with lockless fastpath"
1625,month="February"
1626,year="2007"
1627,day=24
1628,note="Available:
1629\url{http://lkml.org/lkml/2007/2/25/18}
1630[Viewed March 27, 2008]"
1631,annotation="
1632 Patch for QRCU supplying lock-free fast path.
1633"
1634}
1635
1636@article{JonathanAppavoo2007K42RCU
1637,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}
1638,title = {Experience distributing objects in an SMMP OS}
1639,journal = {ACM Trans. Comput. Syst.}
1640,volume = {25}
1641,number = {3}
1642,year = {2007}
1643,issn = {0734-2071}
1644,pages = {6/1--6/52}
1645,doi = {http://doi.acm.org/10.1145/1275517.1275518}
1646,publisher = {ACM}
1647,address = {New York, NY, USA}
1648,annotation={
1649 Role of RCU in K42.
1650}}
1651
1652@conference{RobertOlsson2007Trash
1653,Author="Robert Olsson and Stefan Nilsson"
1654,Title="{TRASH}: A dynamic {LC}-trie and hash data structure"
1655,booktitle="Workshop on High Performance Switching and Routing (HPSR'07)"
1656,month="May"
1657,year="2007"
1658,note="Available:
1659\url{http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4281239}
1660[Viewed October 1, 2010]"
1661,annotation="
1662 RCU-protected dynamic trie-hash combination.
1663"
1664}
1665
1666@conference{PeterZijlstra2007ConcurrentPagecacheRCU
1667,Author="Peter Zijlstra"
1668,Title="Concurrent Pagecache"
1669,Booktitle="Linux Symposium"
1670,month="June"
651,year="2007" 1671,year="2007"
652,note="To appear in J. Parallel Distrib. Comput. 1672,address="Ottawa, Canada"
653 \url{doi=10.1016/j.jpdc.2007.04.010}" 1673,note="Available:
1674\url{http://ols.108.redhat.com/2007/Reprints/zijlstra-Reprint.pdf}
1675[Viewed April 14, 2008]"
1676,annotation="
1677 Page-cache modifications permitting RCU readers and concurrent
1678 updates.
1679"
1680}
1681
1682@unpublished{PaulEMcKenney2007whatisRCU
1683,Author="Paul E. McKenney"
1684,Title="What is {RCU}?"
1685,year="2007"
1686,month="07"
1687,note="Available:
1688\url{http://www.rdrop.com/users/paulmck/RCU/whatisRCU.html}
1689[Viewed July 6, 2007]"
654,annotation={ 1690,annotation={
655 Compares QSBR (AKA "classic RCU"), HPBR, EBR, and lock-free 1691 Describes RCU in Linux kernel.
656 reference counting. Journal version of ThomasEHart2006a.
657} 1692}
658} 1693}
659 1694
660@unpublished{PaulEMcKenney2007QRCUspin 1695@unpublished{PaulEMcKenney2007QRCUspin
661,Author="Paul E. McKenney" 1696,Author="Paul E. McKenney"
662,Title="Using Promela and Spin to verify parallel algorithms" 1697,Title="Using {Promela} and {Spin} to verify parallel algorithms"
663,month="August" 1698,month="August"
664,day="1" 1699,day="1"
665,year="2007" 1700,year="2007"
@@ -669,6 +1704,50 @@ Revised:
669,annotation=" 1704,annotation="
670 LWN article describing Promela and spin, and also using Oleg 1705 LWN article describing Promela and spin, and also using Oleg
671 Nesterov's QRCU as an example (with Paul McKenney's fastpath). 1706 Nesterov's QRCU as an example (with Paul McKenney's fastpath).
1707 Merged patch at: http://lkml.org/lkml/2007/2/25/18
1708"
1709}
1710
1711@unpublished{PaulEMcKenney2007WG21DDOatomics
1712,Author="Paul E. McKenney and Hans-J. Boehm and Lawrence Crowl"
1713,Title="C++ Data-Dependency Ordering: Atomics and Memory Model"
1714,month="August"
1715,day="3"
1716,year="2007"
1717,note="Preprint:
1718\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2664.htm}
1719[Viewed December 7, 2009]"
1720,annotation="
1721 RCU for C++, parts 1 and 2.
1722"
1723}
1724
1725@unpublished{PaulEMcKenney2007WG21DDOannotation
1726,Author="Paul E. McKenney and Lawrence Crowl"
1727,Title="C++ Data-Dependency Ordering: Function Annotation"
1728,month="September"
1729,day="18"
1730,year="2008"
1731,note="Preprint:
1732\url{http://open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2782.htm}
1733[Viewed December 7, 2009]"
1734,annotation="
1735 RCU for C++, part 2, updated many times.
1736"
1737}
1738
1739@unpublished{PaulEMcKenney2007PreemptibleRCUPatch
1740,Author="Paul E. McKenney"
1741,Title="[PATCH RFC 0/9] {RCU}: Preemptible {RCU}"
1742,month="September"
1743,day="10"
1744,year="2007"
1745,note="Available:
1746\url{http://lkml.org/lkml/2007/9/10/213}
1747[Viewed October 25, 2007]"
1748,annotation="
1749 Final patch for preemptable RCU to -rt. (Later patches were
1750 to mainline, eventually incorporated.)
672" 1751"
673} 1752}
674 1753
@@ -686,10 +1765,46 @@ Revised:
686" 1765"
687} 1766}
688 1767
1768@article{ThomasEHart2007a
1769,Author="Thomas E. Hart and Paul E. McKenney and Angela Demke Brown and Jonathan Walpole"
1770,Title="Performance of memory reclamation for lockless synchronization"
1771,journal="J. Parallel Distrib. Comput."
1772,volume={67}
1773,number="12"
1774,year="2007"
1775,issn="0743-7315"
1776,pages="1270--1285"
1777,doi="http://dx.doi.org/10.1016/j.jpdc.2007.04.010"
1778,publisher="Academic Press, Inc."
1779,address="Orlando, FL, USA"
1780,annotation={
1781 Compares QSBR, HPBR, EBR, and lock-free reference counting.
1782 Journal version of ThomasEHart2006a.
1783}
1784}
1785
1786@unpublished{MathieuDesnoyers2007call:rcu:schedNeeded
1787,Author="Mathieu Desnoyers"
1788,Title="Re: [patch 1/2] {Linux} Kernel Markers - Support Multiple Probes"
1789,month="December"
1790,day="20"
1791,year="2007"
1792,note="Available:
1793\url{http://lkml.org/lkml/2007/12/20/244}
1794[Viewed March 27, 2008]"
1795,annotation="
1796 Request for call_rcu_sched() and rcu_barrier_sched().
1797"
1798}
1799
1800
689######################################################################## 1801########################################################################
690# 1802#
691# "What is RCU?" LWN series. 1803# "What is RCU?" LWN series.
692# 1804#
1805# http://lwn.net/Articles/262464/ (What is RCU, Fundamentally?)
1806# http://lwn.net/Articles/263130/ (What is RCU's Usage?)
1807# http://lwn.net/Articles/264090/ (What is RCU's API?)
693 1808
694@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally 1809@unpublished{PaulEMcKenney2007WhatIsRCUFundamentally
695,Author="Paul E. McKenney and Jonathan Walpole" 1810,Author="Paul E. McKenney and Jonathan Walpole"
@@ -723,7 +1838,7 @@ Revised:
723 3. RCU is a Bulk Reference-Counting Mechanism 1838 3. RCU is a Bulk Reference-Counting Mechanism
724 4. RCU is a Poor Man's Garbage Collector 1839 4. RCU is a Poor Man's Garbage Collector
725 5. RCU is a Way of Providing Existence Guarantees 1840 5. RCU is a Way of Providing Existence Guarantees
726 6. RCU is a Way of Waiting for Things to Finish 1841 6. RCU is a Way of Waiting for Things to Finish
727" 1842"
728} 1843}
729 1844
@@ -747,20 +1862,96 @@ Revised:
747# 1862#
748######################################################################## 1863########################################################################
749 1864
1865
1866@unpublished{SteveRostedt2008dyntickRCUpatch
1867,Author="Steven Rostedt and Paul E. McKenney"
1868,Title="{[PATCH]} add support for dynamic ticks and preempt rcu"
1869,month="January"
1870,day="29"
1871,year="2008"
1872,note="Available:
1873\url{http://lkml.org/lkml/2008/1/29/208}
1874[Viewed March 27, 2008]"
1875,annotation="
1876 Patch that prevents preemptible RCU from unnecessarily waking
1877 up dynticks-idle CPUs.
1878"
1879}
1880
1881@unpublished{PaulEMcKenney2008LKMLDependencyOrdering
1882,Author="Paul E. McKenney"
1883,Title="Re: [PATCH 02/22 -v7] Add basic support for gcc profiler instrumentation"
1884,month="February"
1885,day="1"
1886,year="2008"
1887,note="Available:
1888\url{http://lkml.org/lkml/2008/2/2/255}
1889[Viewed October 18, 2008]"
1890,annotation="
1891 Explanation of compilers violating dependency ordering.
1892"
1893}
1894
1895@Conference{PaulEMcKenney2008Beijing
1896,Author="Paul E. McKenney"
1897,Title="Introducing Technology Into {Linux} Or:
1898Introducing your technology Into {Linux} will require introducing a
1899lot of {Linux} into your technology!!!"
1900,Booktitle="2008 Linux Developer Symposium - China"
1901,Publisher="OSS China"
1902,Month="February"
1903,Year="2008"
1904,Address="Beijing, China"
1905,note="Available:
1906\url{http://www.rdrop.com/users/paulmck/RCU/TechIntroLinux.2008.02.19a.pdf}
1907[Viewed August 12, 2008]"
1908}
1909
1910@unpublished{PaulEMcKenney2008dynticksRCU
1911,Author="Paul E. McKenney and Steven Rostedt"
1912,Title="Integrating and Validating dynticks and Preemptable RCU"
1913,month="April"
1914,day="24"
1915,year="2008"
1916,note="Available:
1917\url{http://lwn.net/Articles/279077/}
1918[Viewed April 24, 2008]"
1919,annotation="
1920 Describes use of Promela and Spin to validate (and fix!) the
1921 dynticks/RCU interface.
1922"
1923}
1924
750@article{DinakarGuniguntala2008IBMSysJ 1925@article{DinakarGuniguntala2008IBMSysJ
751,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole" 1926,author="D. Guniguntala and P. E. McKenney and J. Triplett and J. Walpole"
752,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}" 1927,title="The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with {Linux}"
753,Year="2008" 1928,Year="2008"
754,Month="April" 1929,Month="April-June"
755,journal="IBM Systems Journal" 1930,journal="IBM Systems Journal"
756,volume="47" 1931,volume="47"
757,number="2" 1932,number="2"
758,pages="@@-@@" 1933,pages="221-236"
759,annotation=" 1934,annotation="
760 RCU, realtime RCU, sleepable RCU, performance. 1935 RCU, realtime RCU, sleepable RCU, performance.
761" 1936"
762} 1937}
763 1938
1939@unpublished{LaiJiangshan2008NewClassicAlgorithm
1940,Author="Lai Jiangshan"
1941,Title="[{RFC}][{PATCH}] rcu classic: new algorithm for callbacks-processing"
1942,month="June"
1943,day="3"
1944,year="2008"
1945,note="Available:
1946\url{http://lkml.org/lkml/2008/6/2/539}
1947[Viewed December 10, 2008]"
1948,annotation="
1949 Updated RCU classic algorithm. Introduced multi-tailed list
1950 for RCU callbacks and also pulling common code into
1951 __call_rcu().
1952"
1953}
1954
764@article{PaulEMcKenney2008RCUOSR 1955@article{PaulEMcKenney2008RCUOSR
765,author="Paul E. McKenney and Jonathan Walpole" 1956,author="Paul E. McKenney and Jonathan Walpole"
766,title="Introducing technology into the {Linux} kernel: a case study" 1957,title="Introducing technology into the {Linux} kernel: a case study"
@@ -778,6 +1969,52 @@ Revised:
778} 1969}
779} 1970}
780 1971
1972@unpublished{ManfredSpraul2008StateMachineRCU
1973,Author="Manfred Spraul"
1974,Title="[{RFC}, {PATCH}] state machine based rcu"
1975,month="August"
1976,day="21"
1977,year="2008"
1978,note="Available:
1979\url{http://lkml.org/lkml/2008/8/21/336}
1980[Viewed December 8, 2008]"
1981,annotation="
1982 State-based RCU. One key thing that this patch does is to
1983 separate the dynticks handling of NMIs and IRQs.
1984"
1985}
1986
1987@unpublished{ManfredSpraul2008dyntickIRQNMI
1988,Author="Manfred Spraul"
1989,Title="Re: [{RFC}, {PATCH}] v4 scalable classic {RCU} implementation"
1990,month="September"
1991,day="6"
1992,year="2008"
1993,note="Available:
1994\url{http://lkml.org/lkml/2008/9/6/86}
1995[Viewed December 8, 2008]"
1996,annotation="
1997 Manfred notes a fix required to my attempt to separate irq
1998 and NMI processing for hierarchical RCU's dynticks interface.
1999"
2000}
2001
2002@techreport{PaulEMcKenney2008cyclicRCU
2003,author="Paul E. McKenney"
2004,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update"
2005,institution="US Patent and Trademark Office"
2006,address="Washington, DC"
2007,year="2008"
2008,number="US Patent 7,426,511"
2009,month="September"
2010,pages="23"
2011,annotation="
2012 Maintains an additional level of indirection to allow
2013 readers to confine themselves to the desired snapshot of the
2014 data structure. Only permits one update at a time.
2015"
2016}
2017
781@unpublished{PaulEMcKenney2008HierarchicalRCU 2018@unpublished{PaulEMcKenney2008HierarchicalRCU
782,Author="Paul E. McKenney" 2019,Author="Paul E. McKenney"
783,Title="Hierarchical {RCU}" 2020,Title="Hierarchical {RCU}"
@@ -793,6 +2030,21 @@ Revised:
793" 2030"
794} 2031}
795 2032
2033@unpublished{PaulEMcKenney2009BloatwatchRCU
2034,Author="Paul E. McKenney"
2035,Title="Re: [PATCH fyi] RCU: the bloatwatch edition"
2036,month="January"
2037,day="14"
2038,year="2009"
2039,note="Available:
2040\url{http://lkml.org/lkml/2009/1/14/449}
2041[Viewed January 15, 2009]"
2042,annotation="
2043 Small-footprint implementation of RCU for uniprocessor
2044 embedded applications -- and also for exposition purposes.
2045"
2046}
2047
796@conference{PaulEMcKenney2009MaliciousURCU 2048@conference{PaulEMcKenney2009MaliciousURCU
797,Author="Paul E. McKenney" 2049,Author="Paul E. McKenney"
798,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms" 2050,Title="Using a Malicious User-Level {RCU} to Torture {RCU}-Based Algorithms"
@@ -816,15 +2068,17 @@ Revised:
816,year="2009" 2068,year="2009"
817,note="Available: 2069,note="Available:
818\url{http://lkml.org/lkml/2009/2/5/572} 2070\url{http://lkml.org/lkml/2009/2/5/572}
819\url{git://lttng.org/userspace-rcu.git} 2071\url{http://lttng.org/urcu}
820[Viewed February 20, 2009]" 2072[Viewed February 20, 2009]"
821,annotation=" 2073,annotation="
822 Mathieu Desnoyers's user-space RCU implementation. 2074 Mathieu Desnoyers's user-space RCU implementation.
823 git://lttng.org/userspace-rcu.git 2075 git://lttng.org/userspace-rcu.git
2076 http://lttng.org/cgi-bin/gitweb.cgi?p=userspace-rcu.git
2077 http://lttng.org/urcu
824" 2078"
825} 2079}
826 2080
827@unpublished{PaulEMcKenney2009BloatWatchRCU 2081@unpublished{PaulEMcKenney2009LWNBloatWatchRCU
828,Author="Paul E. McKenney" 2082,Author="Paul E. McKenney"
829,Title="{RCU}: The {Bloatwatch} Edition" 2083,Title="{RCU}: The {Bloatwatch} Edition"
830,month="March" 2084,month="March"
@@ -852,14 +2106,29 @@ Revised:
852" 2106"
853} 2107}
854 2108
855@unpublished{JoshTriplett2009RPHash 2109@unpublished{PaulEMcKenney2009fastRTRCU
2110,Author="Paul E. McKenney"
2111,Title="[{PATCH} {RFC} -tip 0/4] {RCU} cleanups and simplified preemptable {RCU}"
2112,month="July"
2113,day="23"
2114,year="2009"
2115,note="Available:
2116\url{http://lkml.org/lkml/2009/7/23/294}
2117[Viewed August 15, 2009]"
2118,annotation="
2119 First posting of simple and fast preemptable RCU.
2120"
2121}
2122
2123@InProceedings{JoshTriplett2009RPHash
856,Author="Josh Triplett" 2124,Author="Josh Triplett"
857,Title="Scalable concurrent hash tables via relativistic programming" 2125,Title="Scalable concurrent hash tables via relativistic programming"
858,month="September" 2126,month="September"
859,year="2009" 2127,year="2009"
860,note="Linux Plumbers Conference presentation" 2128,booktitle="Linux Plumbers Conference 2009"
861,annotation=" 2129,annotation="
862 RP fun with hash tables. 2130 RP fun with hash tables.
2131 See also JoshTriplett2010RPHash
863" 2132"
864} 2133}
865 2134
@@ -872,4 +2141,323 @@ Revised:
872,note="Available: 2141,note="Available:
873\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf} 2142\url{http://www.lttng.org/pub/thesis/desnoyers-dissertation-2009-12.pdf}
874[Viewed December 9, 2009]" 2143[Viewed December 9, 2009]"
2144,annotation={
2145 Chapter 6 (page 97) covers user-level RCU.
2146}
2147}
2148
2149@unpublished{RelativisticProgrammingWiki
2150,Author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
2151,Title="Relativistic Programming"
2152,month="September"
2153,year="2009"
2154,note="Available:
2155\url{http://wiki.cs.pdx.edu/rp/}
2156[Viewed December 9, 2009]"
2157,annotation="
2158 Main Relativistic Programming Wiki.
2159"
2160}
2161
2162@conference{PaulEMcKenney2009DeterministicRCU
2163,Author="Paul E. McKenney"
2164,Title="Deterministic Synchronization in Multicore Systems: the Role of {RCU}"
2165,Booktitle="Eleventh Real Time Linux Workshop"
2166,month="September"
2167,year="2009"
2168,address="Dresden, Germany"
2169,note="Available:
2170\url{http://www.rdrop.com/users/paulmck/realtime/paper/DetSyncRCU.2009.08.18a.pdf}
2171[Viewed January 14, 2009]"
2172}
2173
2174@unpublished{PaulEMcKenney2009HuntingHeisenbugs
2175,Author="Paul E. McKenney"
2176,Title="Hunting Heisenbugs"
2177,month="November"
2178,year="2009"
2179,day="1"
2180,note="Available:
2181\url{http://paulmck.livejournal.com/14639.html}
2182[Viewed June 4, 2010]"
2183,annotation="
2184 Day-one bug in Tree RCU that took forever to track down.
2185"
2186}
2187
2188@unpublished{MathieuDesnoyers2009defer:rcu
2189,Author="Mathieu Desnoyers"
2190,Title="Kernel RCU: shrink the size of the struct rcu\_head"
2191,month="December"
2192,year="2009"
2193,note="Available:
2194\url{http://lkml.org/lkml/2009/10/18/129}
2195[Viewed December 29, 2009]"
2196,annotation="
2197 Mathieu proposed defer_rcu() with fixed-size per-thread pool
2198 of RCU callbacks.
2199"
2200}
2201
2202@unpublished{MathieuDesnoyers2009VerifPrePub
2203,Author="Mathieu Desnoyers and Paul E. McKenney and Michel R. Dagenais"
2204,Title="Multi-Core Systems Modeling for Formal Verification of Parallel Algorithms"
2205,month="December"
2206,year="2009"
2207,note="Submitted to IEEE TPDS"
2208,annotation="
2209 OOMem model for Mathieu's user-level RCU mechanical proof of
2210 correctness.
2211"
2212}
2213
2214@unpublished{MathieuDesnoyers2009URCUPrePub
2215,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
2216,Title="User-Level Implementations of Read-Copy Update"
2217,month="December"
2218,year="2010"
2219,url=\url{http://www.computer.org/csdl/trans/td/2012/02/ttd2012020375-abs.html}
2220,annotation="
2221 RCU overview, desiderata, semi-formal semantics, user-level RCU
2222 usage scenarios, three classes of RCU implementation, wait-free
2223 RCU updates, RCU grace-period batching, update overhead,
2224 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2225 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
2226 Superseded by MathieuDesnoyers2012URCU.
2227"
2228}
2229
2230@inproceedings{HariKannan2009DynamicAnalysisRCU
2231,author = {Kannan, Hari}
2232,title = {Ordering decoupled metadata accesses in multiprocessors}
2233,booktitle = {MICRO 42: Proceedings of the 42nd Annual IEEE/ACM International Symposium on Microarchitecture}
2234,year = {2009}
2235,isbn = {978-1-60558-798-1}
2236,pages = {381--390}
2237,location = {New York, New York}
2238,doi = {http://doi.acm.org/10.1145/1669112.1669161}
2239,publisher = {ACM}
2240,address = {New York, NY, USA}
2241,annotation={
2242 Uses RCU to protect metadata used in dynamic analysis.
2243}}
2244
2245@conference{PaulEMcKenney2010SimpleOptRCU
2246,Author="Paul E. McKenney"
2247,Title="Simplicity Through Optimization"
2248,Booktitle="linux.conf.au 2010"
2249,month="January"
2250,year="2010"
2251,address="Wellington, New Zealand"
2252,note="Available:
2253\url{http://www.rdrop.com/users/paulmck/RCU/SimplicityThruOptimization.2010.01.21f.pdf}
2254[Viewed October 10, 2010]"
2255,annotation="
2256 TREE_PREEMPT_RCU optimizations greatly simplified the old
2257 PREEMPT_RCU implementation.
2258"
2259}
2260
2261@unpublished{PaulEMcKenney2010LockdepRCU
2262,Author="Paul E. McKenney"
2263,Title="Lockdep-{RCU}"
2264,month="February"
2265,year="2010"
2266,day="1"
2267,note="Available:
2268\url{https://lwn.net/Articles/371986/}
2269[Viewed June 4, 2010]"
2270,annotation="
2271 CONFIG_PROVE_RCU, or at least an early version.
2272"
2273}
2274
2275@unpublished{AviKivity2010KVM2RCU
2276,Author="Avi Kivity"
2277,Title="[{PATCH} 37/40] {KVM}: Bump maximum vcpu count to 64"
2278,month="February"
2279,year="2010"
2280,note="Available:
2281\url{http://www.mail-archive.com/kvm@vger.kernel.org/msg28640.html}
2282[Viewed March 20, 2010]"
2283,annotation="
2284 Use of RCU permits KVM to increase the size of guest OSes from
2285 16 CPUs to 64 CPUs.
2286"
2287}
2288
2289@unpublished{HerbertXu2010RCUResizeHash
2290,Author="Herbert Xu"
2291,Title="bridge: Add core IGMP snooping support"
2292,month="February"
2293,year="2010"
2294,note="Available:
2295\url{http://kerneltrap.com/mailarchive/linux-netdev/2010/2/26/6270589}
2296[Viewed March 20, 2011]"
2297,annotation={
2298 Use a pair of list_head structures to support RCU-protected
2299 resizable hash tables.
2300}}
2301
2302@article{JoshTriplett2010RPHash
2303,author="Josh Triplett and Paul E. McKenney and Jonathan Walpole"
2304,title="Scalable Concurrent Hash Tables via Relativistic Programming"
2305,journal="ACM Operating Systems Review"
2306,year=2010
2307,volume=44
2308,number=3
2309,month="July"
2310,annotation={
2311 RP fun with hash tables.
2312 http://portal.acm.org/citation.cfm?id=1842733.1842750
2313}}
2314
2315@unpublished{PaulEMcKenney2010RCUAPI
2316,Author="Paul E. McKenney"
2317,Title="The {RCU} {API}, 2010 Edition"
2318,month="December"
2319,day="8"
2320,year="2010"
2321,note="Available:
2322\url{http://lwn.net/Articles/418853/}
2323[Viewed December 8, 2010]"
2324,annotation="
2325 Includes updated software-engineering features.
2326"
2327}
2328
2329@mastersthesis{AndrejPodzimek2010masters
2330,author="Andrej Podzimek"
2331,title="Read-Copy-Update for OpenSolaris"
2332,school="Charles University in Prague"
2333,year="2010"
2334,note="Available:
2335\url{https://andrej.podzimek.org/thesis.pdf}
2336[Viewed January 31, 2011]"
2337,annotation={
2338 Reviews RCU implementations and creates a few for OpenSolaris.
2339 Drives quiescent-state detection from RCU read-side primitives,
2340 in a manner roughly similar to that of Jim Houston.
2341}}
2342
2343@unpublished{LinusTorvalds2011Linux2:6:38:rc1:NPigginVFS
2344,Author="Linus Torvalds"
2345,Title="Linux 2.6.38-rc1"
2346,month="January"
2347,year="2011"
2348,note="Available:
2349\url{https://lkml.org/lkml/2011/1/18/322}
2350[Viewed March 4, 2011]"
2351,annotation={
2352 "The RCU-based name lookup is at the other end of the spectrum - the
2353 absolute anti-gimmick. It's some seriously good stuff, and gets rid of
2354 the last main global lock that really tends to hurt some kernel loads.
2355 The dentry lock is no longer a big serializing issue. What's really
2356 nice about it is that it actually improves performance a lot even for
2357 single-threaded loads (on an SMP kernel), because it gets rid of some
2358 of the most expensive parts of path component lookup, which was the
2359 d_lock on every component lookup. So I'm seeing improvements of 30-50%
2360 on some seriously pathname-lookup intensive loads."
2361}}
2362
2363@techreport{JoshTriplett2011RPScalableCorrectOrdering
2364,author = {Josh Triplett and Philip W. Howard and Paul E. McKenney and Jonathan Walpole}
2365,title = {Scalable Correct Memory Ordering via Relativistic Programming}
2366,year = {2011}
2367,number = {11-03}
2368,institution = {Portland State University}
2369,note = {\url{http://www.cs.pdx.edu/pdfs/tr1103.pdf}}
2370}
2371
2372@inproceedings{PhilHoward2011RCUTMRBTree
2373,author = {Philip W. Howard and Jonathan Walpole}
2374,title = {A Relativistic Enhancement to Software Transactional Memory}
2375,booktitle = {Proceedings of the 3rd USENIX conference on Hot topics in parallelism}
2376,series = {HotPar'11}
2377,year = {2011}
2378,location = {Berkeley, CA}
2379,pages = {1--6}
2380,numpages = {6}
2381,url = {http://www.usenix.org/event/hotpar11/tech/final_files/Howard.pdf}
2382,publisher = {USENIX Association}
2383,address = {Berkeley, CA, USA}
2384}
2385
2386@techreport{PaulEMcKenney2011cyclicparallelRCU
2387,author="Paul E. McKenney and Jonathan Walpole"
2388,title="Efficient Support of Consistent Cyclic Search With Read-Copy Update and Parallel Updates"
2389,institution="US Patent and Trademark Office"
2390,address="Washington, DC"
2391,year="2011"
2392,number="US Patent 7,953,778"
2393,month="May"
2394,pages="34"
2395,annotation="
2396 Maintains an array of generation numbers to track in-flight
2397 updates and keeps an additional level of indirection to allow
2398 readers to confine themselves to the desired snapshot of the
2399 data structure.
2400"
2401}
2402
2403@inproceedings{Triplett:2011:RPHash
2404,author = {Triplett, Josh and McKenney, Paul E. and Walpole, Jonathan}
2405,title = {Resizable, Scalable, Concurrent Hash Tables via Relativistic Programming}
2406,booktitle = {Proceedings of the 2011 USENIX Annual Technical Conference}
2407,month = {June}
2408,year = {2011}
2409,pages = {145--158}
2410,numpages = {14}
2411,url={http://www.usenix.org/event/atc11/tech/final_files/atc11_proceedings.pdf}
2412,publisher = {The USENIX Association}
2413,address = {Portland, OR USA}
2414}
2415
2416@unpublished{PaulEMcKenney2011RCU3.0trainwreck
2417,Author="Paul E. McKenney"
2418,Title="3.0 and {RCU:} what went wrong"
2419,month="July"
2420,day="27"
2421,year="2011"
2422,note="Available:
2423\url{http://lwn.net/Articles/453002/}
2424[Viewed July 27, 2011]"
2425,annotation="
2426 Analysis of the RCU trainwreck in Linux kernel 3.0.
2427"
2428}
2429
2430@unpublished{NeilBrown2011MeetTheLockers
2431,Author="Neil Brown"
2432,Title="Meet the Lockers"
2433,month="August"
2434,day="3"
2435,year="2011"
2436,note="Available:
2437\url{http://lwn.net/Articles/453685/}
2438[Viewed September 2, 2011]"
2439,annotation="
2440 The Locker family as an analogy for locking, reference counting,
2441 RCU, and seqlock.
2442"
2443}
2444
2445@article{MathieuDesnoyers2012URCU
2446,Author="Mathieu Desnoyers and Paul E. McKenney and Alan Stern and Michel R. Dagenais and Jonathan Walpole"
2447,Title="User-Level Implementations of Read-Copy Update"
2448,journal="IEEE Transactions on Parallel and Distributed Systems"
2449,volume={23}
2450,year="2012"
2451,issn="1045-9219"
2452,pages="375-382"
2453,doi="http://doi.ieeecomputersociety.org/10.1109/TPDS.2011.159"
2454,publisher="IEEE Computer Society"
2455,address="Los Alamitos, CA, USA"
2456,annotation={
2457 RCU overview, desiderata, semi-formal semantics, user-level RCU
2458 usage scenarios, three classes of RCU implementation, wait-free
2459 RCU updates, RCU grace-period batching, update overhead,
2460 http://www.rdrop.com/users/paulmck/RCU/urcu-main-accepted.2011.08.30a.pdf
2461 http://www.rdrop.com/users/paulmck/RCU/urcu-supp-accepted.2011.08.30a.pdf
2462}
875} 2463}
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!
180 operations that would not normally be undertaken while a real-time 180 operations that would not normally be undertaken while a real-time
181 workload is running. 181 workload is running.
182 182
183 In particular, if you find yourself invoking one of the expedited
184 primitives repeatedly in a loop, please do everyone a favor:
185 Restructure your code so that it batches the updates, allowing
186 a single non-expedited primitive to cover the entire batch.
187 This will very likely be faster than the loop containing the
188 expedited primitive, and will be much much easier on the rest
189 of the system, especially to real-time workloads running on
190 the rest of the system.
191
192 In addition, it is illegal to call the expedited forms from
193 a CPU-hotplug notifier, or while holding a lock that is acquired
194 by a CPU-hotplug notifier. Failing to observe this restriction
195 will result in deadlock.
196
1837. If the updater uses call_rcu() or synchronize_rcu(), then the 1977. If the updater uses call_rcu() or synchronize_rcu(), then the
184 corresponding readers must use rcu_read_lock() and 198 corresponding readers must use rcu_read_lock() and
185 rcu_read_unlock(). If the updater uses call_rcu_bh() or 199 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
12 This kernel configuration parameter defines the period of time 12 This kernel configuration parameter defines the period of time
13 that RCU will wait from the beginning of a grace period until it 13 that RCU will wait from the beginning of a grace period until it
14 issues an RCU CPU stall warning. This time period is normally 14 issues an RCU CPU stall warning. This time period is normally
15 ten seconds. 15 sixty seconds.
16 16
17RCU_SECONDS_TILL_STALL_RECHECK 17 This configuration parameter may be changed at runtime via the
18 /sys/module/rcutree/parameters/rcu_cpu_stall_timeout, however
19 this parameter is checked only at the beginning of a cycle.
20 So if you are 30 seconds into a 70-second stall, setting this
21 sysfs parameter to (say) five will shorten the timeout for the
22 -next- stall, or the following warning for the current stall
23 (assuming the stall lasts long enough). It will not affect the
24 timing of the next warning for the current stall.
18 25
19 This macro defines the period of time that RCU will wait after 26 Stall-warning messages may be enabled and disabled completely via
20 issuing a stall warning until it issues another stall warning 27 /sys/module/rcutree/parameters/rcu_cpu_stall_suppress.
21 for the same stall. This time period is normally set to three 28
22 times the check interval plus thirty seconds. 29CONFIG_RCU_CPU_STALL_VERBOSE
30
31 This kernel configuration parameter causes the stall warning to
32 also dump the stacks of any tasks that are blocking the current
33 RCU-preempt grace period.
34
35RCU_CPU_STALL_INFO
36
37 This kernel configuration parameter causes the stall warning to
38 print out additional per-CPU diagnostic information, including
39 information on scheduling-clock ticks and RCU's idle-CPU tracking.
40
41RCU_STALL_DELAY_DELTA
42
43 Although the lockdep facility is extremely useful, it does add
44 some overhead. Therefore, under CONFIG_PROVE_RCU, the
45 RCU_STALL_DELAY_DELTA macro allows five extra seconds before
46 giving an RCU CPU stall warning message.
23 47
24RCU_STALL_RAT_DELAY 48RCU_STALL_RAT_DELAY
25 49
@@ -64,6 +88,54 @@ INFO: rcu_bh_state detected stalls on CPUs/tasks: { } (detected by 4, 2502 jiffi
64 88
65This is rare, but does happen from time to time in real life. 89This is rare, but does happen from time to time in real life.
66 90
91If the CONFIG_RCU_CPU_STALL_INFO kernel configuration parameter is set,
92more information is printed with the stall-warning message, for example:
93
94 INFO: rcu_preempt detected stall on CPU
95 0: (63959 ticks this GP) idle=241/3fffffffffffffff/0
96 (t=65000 jiffies)
97
98In kernels with CONFIG_RCU_FAST_NO_HZ, even more information is
99printed:
100
101 INFO: rcu_preempt detected stall on CPU
102 0: (64628 ticks this GP) idle=dd5/3fffffffffffffff/0 drain=0 . timer=-1
103 (t=65000 jiffies)
104
105The "(64628 ticks this GP)" indicates that this CPU has taken more
106than 64,000 scheduling-clock interrupts during the current stalled
107grace period. If the CPU was not yet aware of the current grace
108period (for example, if it was offline), then this part of the message
109indicates how many grace periods behind the CPU is.
110
111The "idle=" portion of the message prints the dyntick-idle state.
112The hex number before the first "/" is the low-order 12 bits of the
113dynticks counter, which will have an even-numbered value if the CPU is
114in dyntick-idle mode and an odd-numbered value otherwise. The hex
115number between the two "/"s is the value of the nesting, which will
116be a small positive number if in the idle loop and a very large positive
117number (as shown above) otherwise.
118
119For CONFIG_RCU_FAST_NO_HZ kernels, the "drain=0" indicates that the
120CPU is not in the process of trying to force itself into dyntick-idle
121state, the "." indicates that the CPU has not given up forcing RCU
122into dyntick-idle mode (it would be "H" otherwise), and the "timer=-1"
123indicates that the CPU has not recented forced RCU into dyntick-idle
124mode (it would otherwise indicate the number of microseconds remaining
125in this forced state).
126
127
128Multiple Warnings From One Stall
129
130If a stall lasts long enough, multiple stall-warning messages will be
131printed for it. The second and subsequent messages are printed at
132longer intervals, so that the time between (say) the first and second
133message will be about three times the interval between the beginning
134of the stall and the first message.
135
136
137What Causes RCU CPU Stall Warnings?
138
67So your kernel printed an RCU CPU stall warning. The next question is 139So your kernel printed an RCU CPU stall warning. The next question is
68"What caused it?" The following problems can result in RCU CPU stall 140"What caused it?" The following problems can result in RCU CPU stall
69warnings: 141warnings:
@@ -128,4 +200,5 @@ is occurring, which will usually be in the function nearest the top of
128that portion of the stack which remains the same from trace to trace. 200that portion of the stack which remains the same from trace to trace.
129If you can reliably trigger the stall, ftrace can be quite helpful. 201If you can reliably trigger the stall, ftrace can be quite helpful.
130 202
131RCU bugs can often be debugged with the help of CONFIG_RCU_TRACE. 203RCU bugs can often be debugged with the help of CONFIG_RCU_TRACE
204and 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
69 CPU-hotplug operations regardless of what value is 69 CPU-hotplug operations regardless of what value is
70 specified for onoff_interval. 70 specified for onoff_interval.
71 71
72onoff_holdoff The number of seconds to wait until starting CPU-hotplug
73 operations. This would normally only be used when
74 rcutorture was built into the kernel and started
75 automatically at boot time, in which case it is useful
76 in order to avoid confusing boot-time code with CPUs
77 coming and going.
78
72shuffle_interval 79shuffle_interval
73 The number of seconds to keep the test threads affinitied 80 The number of seconds to keep the test threads affinitied
74 to a particular subset of the CPUs, defaults to 3 seconds. 81 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
79 zero, which disables test termination and system shutdown. 86 zero, which disables test termination and system shutdown.
80 This capability is useful for automated testing. 87 This capability is useful for automated testing.
81 88
89stall_cpu The number of seconds that a CPU should be stalled while
90 within both an rcu_read_lock() and a preempt_disable().
91 This stall happens only once per rcutorture run.
92 If you need multiple stalls, use modprobe and rmmod to
93 repeatedly run rcutorture. The default for stall_cpu
94 is zero, which prevents rcutorture from stalling a CPU.
95
96 Note that attempts to rmmod rcutorture while the stall
97 is ongoing will hang, so be careful what value you
98 choose for this module parameter! In addition, too-large
99 values for stall_cpu might well induce failures and
100 warnings in other parts of the kernel. You have been
101 warned!
102
103stall_cpu_holdoff
104 The number of seconds to wait after rcutorture starts
105 before stalling a CPU. Defaults to 10 seconds.
106
82stat_interval The number of seconds between output of torture 107stat_interval The number of seconds between output of torture
83 statistics (via printk()). Regardless of the interval, 108 statistics (via printk()). Regardless of the interval,
84 statistics are printed when the module is unloaded. 109 statistics are printed when the module is unloaded.
@@ -271,11 +296,13 @@ The following script may be used to torture RCU:
271 #!/bin/sh 296 #!/bin/sh
272 297
273 modprobe rcutorture 298 modprobe rcutorture
274 sleep 100 299 sleep 3600
275 rmmod rcutorture 300 rmmod rcutorture
276 dmesg | grep torture: 301 dmesg | grep torture:
277 302
278The output can be manually inspected for the error flag of "!!!". 303The output can be manually inspected for the error flag of "!!!".
279One could of course create a more elaborate script that automatically 304One could of course create a more elaborate script that automatically
280checked for such errors. The "rmmod" command forces a "SUCCESS" or 305checked for such errors. The "rmmod" command forces a "SUCCESS",
281"FAILURE" indication to be printk()ed. 306"FAILURE", or "RCU_HOTPLUG" indication to be printk()ed. The first
307two are self-explanatory, while the last indicates that while there
308were 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:
33The output of "cat rcu/rcudata" looks as follows: 33The output of "cat rcu/rcudata" looks as follows:
34 34
35rcu_sched: 35rcu_sched:
36 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 36 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
37 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 37 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
38 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 38 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
39 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 39 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
40 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 40 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
41 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 41 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
42 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 42 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
43 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 43 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
44rcu_bh: 44rcu_bh:
45 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 45 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
46 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 46 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
47 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 47 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
48 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 48 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
49 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 49 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
50 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 50 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
51 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 51 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
52 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 52 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
53 53
54The first section lists the rcu_data structures for rcu_sched, the second 54The first section lists the rcu_data structures for rcu_sched, the second
55for rcu_bh. Note that CONFIG_TREE_PREEMPT_RCU kernels will have an 55for 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
119 CPU is offline when it is really alive and kicking) is a fatal 119 CPU is offline when it is really alive and kicking) is a fatal
120 error, so it makes sense to err conservatively. 120 error, so it makes sense to err conservatively.
121 121
122o "ri" is the number of times that RCU has seen fit to send a
123 reschedule IPI to this CPU in order to get it to report a
124 quiescent state.
125
126o "ql" is the number of RCU callbacks currently residing on 122o "ql" is the number of RCU callbacks currently residing on
127 this CPU. This is the total number of callbacks, regardless 123 this CPU. This is the total number of callbacks, regardless
128 of what state they are in (new, waiting for grace period to 124 of what state they are in (new, waiting for grace period to
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 @@
1* Energymicro efm32 UART
2
3Required properties:
4- compatible : Should be "efm32,uart"
5- reg : Address and length of the register set
6- interrupts : Should contain uart interrupt
7
8Example:
9
10uart@0x4000c400 {
11 compatible = "efm32,uart";
12 reg = <0x4000c400 0x400>;
13 interrupts = <15>;
14};
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.
12Dynamic debug has even more useful features: 12Dynamic debug has even more useful features:
13 13
14 * Simple query language allows turning on and off debugging statements by 14 * Simple query language allows turning on and off debugging statements by
15 matching any combination of: 15 matching any combination of 0 or 1 of:
16 16
17 - source filename 17 - source filename
18 - function name 18 - function name
@@ -79,31 +79,24 @@ Command Language Reference
79========================== 79==========================
80 80
81At the lexical level, a command comprises a sequence of words separated 81At the lexical level, a command comprises a sequence of words separated
82by whitespace characters. Note that newlines are treated as word 82by spaces or tabs. So these are all equivalent:
83separators and do *not* end a command or allow multiple commands to
84be done together. So these are all equivalent:
85 83
86nullarbor:~ # echo -c 'file svcsock.c line 1603 +p' > 84nullarbor:~ # echo -c 'file svcsock.c line 1603 +p' >
87 <debugfs>/dynamic_debug/control 85 <debugfs>/dynamic_debug/control
88nullarbor:~ # echo -c ' file svcsock.c line 1603 +p ' > 86nullarbor:~ # echo -c ' file svcsock.c line 1603 +p ' >
89 <debugfs>/dynamic_debug/control 87 <debugfs>/dynamic_debug/control
90nullarbor:~ # echo -c 'file svcsock.c\nline 1603 +p' >
91 <debugfs>/dynamic_debug/control
92nullarbor:~ # echo -n 'file svcsock.c line 1603 +p' > 88nullarbor:~ # echo -n 'file svcsock.c line 1603 +p' >
93 <debugfs>/dynamic_debug/control 89 <debugfs>/dynamic_debug/control
94 90
95Commands are bounded by a write() system call. If you want to do 91Command submissions are bounded by a write() system call.
96multiple commands you need to do a separate "echo" for each, like: 92Multiple commands can be written together, separated by ';' or '\n'.
97 93
98nullarbor:~ # echo 'file svcsock.c line 1603 +p' > /proc/dprintk ;\ 94 ~# echo "func pnpacpi_get_resources +p; func pnp_assign_mem +p" \
99> echo 'file svcsock.c line 1563 +p' > /proc/dprintk 95 > <debugfs>/dynamic_debug/control
100 96
101or even like: 97If your query set is big, you can batch them too:
102 98
103nullarbor:~ # ( 99 ~# cat query-batch-file > <debugfs>/dynamic_debug/control
104> echo 'file svcsock.c line 1603 +p' ;\
105> echo 'file svcsock.c line 1563 +p' ;\
106> ) > /proc/dprintk
107 100
108At the syntactical level, a command comprises a sequence of match 101At the syntactical level, a command comprises a sequence of match
109specifications, followed by a flags change specification. 102specifications, followed by a flags change specification.
@@ -144,11 +137,12 @@ func
144 func svc_tcp_accept 137 func svc_tcp_accept
145 138
146file 139file
147 The given string is compared against either the full 140 The given string is compared against either the full pathname, the
148 pathname or the basename of the source file of each 141 src-root relative pathname, or the basename of the source file of
149 callsite. Examples: 142 each callsite. Examples:
150 143
151 file svcsock.c 144 file svcsock.c
145 file kernel/freezer.c
152 file /usr/src/packages/BUILD/sgi-enhancednfs-1.4/default/net/sunrpc/svcsock.c 146 file /usr/src/packages/BUILD/sgi-enhancednfs-1.4/default/net/sunrpc/svcsock.c
153 147
154module 148module
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:
14 14
15 mount -t debugfs none /sys/kernel/debug 15 mount -t debugfs none /sys/kernel/debug
16 16
17(Or an equivalent /etc/fstab line). 17(Or an equivalent /etc/fstab line).
18The debugfs root directory is accessible by anyone by default. To
19restrict access to the tree the "uid", "gid" and "mode" mount
20options can be used.
18 21
19Note that the debugfs API is exported GPL-only to modules. 22Note that the debugfs API is exported GPL-only to modules.
20 23
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
50(NCT6775F), and NCT6776F super I/O chips. We will refer to them collectively 50(NCT6775F), and NCT6776F super I/O chips. We will refer to them collectively
51as Winbond chips. 51as Winbond chips.
52 52
53The chips implement 2 to 4 temperature sensors (9 for NCT6775F and NCT6776F), 53The chips implement 3 to 4 temperature sensors (9 for NCT6775F and NCT6776F),
542 to 5 fan rotation speed sensors, 8 to 10 analog voltage sensors, one VID 542 to 5 fan rotation speed sensors, 8 to 10 analog voltage sensors, one VID
55(except for 627UHG), alarms with beep warnings (control unimplemented), 55(except for 627UHG), alarms with beep warnings (control unimplemented),
56and some automatic fan regulation strategies (plus manual fan control mode). 56and 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
143pwm[1-4]_stop_time - how many milliseconds [ms] must elapse to switch 143pwm[1-4]_stop_time - how many milliseconds [ms] must elapse to switch
144 corresponding fan off. (when the temperature was below 144 corresponding fan off. (when the temperature was below
145 defined range). 145 defined range).
146pwm[1-4]_start_output-minimum fan speed (range 1 - 255) when spinning up
147pwm[1-4]_step_output- rate of fan speed change (1 - 255)
148pwm[1-4]_stop_output- minimum fan speed (range 1 - 255) when spinning down
149pwm[1-4]_max_output - maximum fan speed (range 1 - 255), when the temperature
150 is above defined range.
146 151
147Note: last two functions are influenced by other control bits, not yet exported 152Note: last six functions are influenced by other control bits, not yet exported
148 by the driver, so a change might not have any effect. 153 by the driver, so a change might not have any effect.
149 154
150Implementation Details 155Implementation Details
diff --git a/Documentation/hwmon/zl6100 b/Documentation/hwmon/zl6100
index 51f76a189fee..a4e8d90f59f6 100644
--- a/Documentation/hwmon/zl6100
+++ b/Documentation/hwmon/zl6100
@@ -88,14 +88,12 @@ Module parameters
88delay 88delay
89----- 89-----
90 90
91Some Intersil/Zilker Labs DC-DC controllers require a minimum interval between 91Intersil/Zilker Labs DC-DC controllers require a minimum interval between I2C
92I2C bus accesses. According to Intersil, the minimum interval is 2 ms, though 92bus accesses. According to Intersil, the minimum interval is 2 ms, though 1 ms
931 ms appears to be sufficient and has not caused any problems in testing. 93appears to be sufficient and has not caused any problems in testing. The problem
94The problem is known to affect ZL6100, ZL2105, and ZL2008. It is known not to 94is known to affect all currently supported chips. For manual override, the
95affect ZL2004 and ZL6105. The driver automatically sets the interval to 1 ms 95driver provides a writeable module parameter, 'delay', which can be used to set
96except for ZL2004 and ZL6105. To enable manual override, the driver provides a 96the interval to a value between 0 and 65,535 microseconds.
97writeable module parameter, 'delay', which can be used to set the interval to
98a value between 0 and 65,535 microseconds.
99 97
100 98
101Sysfs entries 99Sysfs entries
diff --git a/Documentation/ioctl/ioctl-number.txt b/Documentation/ioctl/ioctl-number.txt
index 4840334ea97b..5dbd9066ed16 100644
--- a/Documentation/ioctl/ioctl-number.txt
+++ b/Documentation/ioctl/ioctl-number.txt
@@ -189,7 +189,7 @@ Code Seq#(hex) Include File Comments
189'Y' all linux/cyclades.h 189'Y' all linux/cyclades.h
190'Z' 14-15 drivers/message/fusion/mptctl.h 190'Z' 14-15 drivers/message/fusion/mptctl.h
191'[' 00-07 linux/usb/tmc.h USB Test and Measurement Devices 191'[' 00-07 linux/usb/tmc.h USB Test and Measurement Devices
192 <mailto:gregkh@suse.de> 192 <mailto:gregkh@linuxfoundation.org>
193'a' all linux/atm*.h, linux/sonet.h ATM on linux 193'a' all linux/atm*.h, linux/sonet.h ATM on linux
194 <http://lrcwww.epfl.ch/> 194 <http://lrcwww.epfl.ch/>
195'b' 00-FF conflict! bit3 vme host bridge 195'b' 00-FF conflict! bit3 vme host bridge
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는
354 git.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6.git 354 git.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6.git
355 355
356 quilt trees: 356 quilt trees:
357 - USB, PCI, Driver Core, and I2C, Greg Kroah-Hartman < gregkh@suse.de> 357 - USB, PCI, Driver Core, and I2C, Greg Kroah-Hartman < gregkh@linuxfoundation.org>
358 kernel.org/pub/linux/kernel/people/gregkh/gregkh-2.6/ 358 kernel.org/pub/linux/kernel/people/gregkh/gregkh-2.6/
359 - x86-64, partly i386, Andi Kleen < ak@suse.de> 359 - x86-64, partly i386, Andi Kleen < ak@suse.de>
360 ftp.firstfloor.org:/pub/ak/x86_64/quilt/ 360 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 @@
1Everything you never wanted to know about kobjects, ksets, and ktypes 1Everything you never wanted to know about kobjects, ksets, and ktypes
2 2
3Greg Kroah-Hartman <gregkh@suse.de> 3Greg Kroah-Hartman <gregkh@linuxfoundation.org>
4 4
5Based on an original article by Jon Corbet for lwn.net written October 1, 5Based on an original article by Jon Corbet for lwn.net written October 1,
62003 and located at http://lwn.net/Articles/51437/ 62003 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 @@
1===============================================================
2Softlockup detector and hardlockup detector (aka nmi_watchdog)
3===============================================================
4
5The Linux kernel can act as a watchdog to detect both soft and hard
6lockups.
7
8A 'softlockup' is defined as a bug that causes the kernel to loop in
9kernel mode for more than 20 seconds (see "Implementation" below for
10details), without giving other tasks a chance to run. The current
11stack trace is displayed upon detection and, by default, the system
12will stay locked up. Alternatively, the kernel can be configured to
13panic; a sysctl, "kernel.softlockup_panic", a kernel parameter,
14"softlockup_panic" (see "Documentation/kernel-parameters.txt" for
15details), and a compile option, "BOOTPARAM_HARDLOCKUP_PANIC", are
16provided for this.
17
18A 'hardlockup' is defined as a bug that causes the CPU to loop in
19kernel mode for more than 10 seconds (see "Implementation" below for
20details), without letting other interrupts have a chance to run.
21Similarly to the softlockup case, the current stack trace is displayed
22upon detection and the system will stay locked up unless the default
23behavior is changed, which can be done through a compile time knob,
24"BOOTPARAM_HARDLOCKUP_PANIC", and a kernel parameter, "nmi_watchdog"
25(see "Documentation/kernel-parameters.txt" for details).
26
27The panic option can be used in combination with panic_timeout (this
28timeout is set through the confusingly named "kernel.panic" sysctl),
29to cause the system to reboot automatically after a specified amount
30of time.
31
32=== Implementation ===
33
34The soft and hard lockup detectors are built on top of the hrtimer and
35perf subsystems, respectively. A direct consequence of this is that,
36in principle, they should work in any architecture where these
37subsystems are present.
38
39A periodic hrtimer runs to generate interrupts and kick the watchdog
40task. An NMI perf event is generated every "watchdog_thresh"
41(compile-time initialized to 10 and configurable through sysctl of the
42same name) seconds to check for hardlockups. If any CPU in the system
43does not receive any hrtimer interrupt during that time the
44'hardlockup detector' (the handler for the NMI perf event) will
45generate a kernel warning or call panic, depending on the
46configuration.
47
48The watchdog task is a high priority kernel thread that updates a
49timestamp every time it is scheduled. If that timestamp is not updated
50for 2*watchdog_thresh seconds (the softlockup threshold) the
51'softlockup detector' (coded inside the hrtimer callback function)
52will dump useful debug information to the system log, after which it
53will call panic if it was instructed to do so or resume execution of
54other kernel code.
55
56The period of the hrtimer is 2*watchdog_thresh/5, which means it has
57two or three chances to generate an interrupt before the hardlockup
58detector kicks in.
59
60As explained above, a kernel knob is provided that allows
61administrators to configure the period of the hrtimer and the perf
62event. The right value for a particular environment is a trade-off
63between fast response to lockups and detection overhead.
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 @@
1
2[NMI watchdog is available for x86 and x86-64 architectures]
3
4Is your system locking up unpredictably? No keyboard activity, just
5a frustrating complete hard lockup? Do you want to help us debugging
6such lockups? If all yes then this document is definitely for you.
7
8On many x86/x86-64 type hardware there is a feature that enables
9us to generate 'watchdog NMI interrupts'. (NMI: Non Maskable Interrupt
10which get executed even if the system is otherwise locked up hard).
11This can be used to debug hard kernel lockups. By executing periodic
12NMI interrupts, the kernel can monitor whether any CPU has locked up,
13and print out debugging messages if so.
14
15In order to use the NMI watchdog, you need to have APIC support in your
16kernel. For SMP kernels, APIC support gets compiled in automatically. For
17UP, enable either CONFIG_X86_UP_APIC (Processor type and features -> Local
18APIC support on uniprocessors) or CONFIG_X86_UP_IOAPIC (Processor type and
19features -> IO-APIC support on uniprocessors) in your kernel config.
20CONFIG_X86_UP_APIC is for uniprocessor machines without an IO-APIC.
21CONFIG_X86_UP_IOAPIC is for uniprocessor with an IO-APIC. [Note: certain
22kernel debugging options, such as Kernel Stack Meter or Kernel Tracer,
23may implicitly disable the NMI watchdog.]
24
25For x86-64, the needed APIC is always compiled in.
26
27Using local APIC (nmi_watchdog=2) needs the first performance register, so
28you can't use it for other purposes (such as high precision performance
29profiling.) However, at least oprofile and the perfctr driver disable the
30local APIC NMI watchdog automatically.
31
32To actually enable the NMI watchdog, use the 'nmi_watchdog=N' boot
33parameter. Eg. the relevant lilo.conf entry:
34
35 append="nmi_watchdog=1"
36
37For SMP machines and UP machines with an IO-APIC use nmi_watchdog=1.
38For UP machines without an IO-APIC use nmi_watchdog=2, this only works
39for some processor types. If in doubt, boot with nmi_watchdog=1 and
40check the NMI count in /proc/interrupts; if the count is zero then
41reboot with nmi_watchdog=2 and check the NMI count. If it is still
42zero then log a problem, you probably have a processor that needs to be
43added to the nmi code.
44
45A 'lockup' is the following scenario: if any CPU in the system does not
46execute the period local timer interrupt for more than 5 seconds, then
47the NMI handler generates an oops and kills the process. This
48'controlled crash' (and the resulting kernel messages) can be used to
49debug the lockup. Thus whenever the lockup happens, wait 5 seconds and
50the oops will show up automatically. If the kernel produces no messages
51then the system has crashed so hard (eg. hardware-wise) that either it
52cannot even accept NMI interrupts, or the crash has made the kernel
53unable to print messages.
54
55Be aware that when using local APIC, the frequency of NMI interrupts
56it generates, depends on the system load. The local APIC NMI watchdog,
57lacking a better source, uses the "cycles unhalted" event. As you may
58guess it doesn't tick when the CPU is in the halted state (which happens
59when the system is idle), but if your system locks up on anything but the
60"hlt" processor instruction, the watchdog will trigger very soon as the
61"cycles unhalted" event will happen every clock tick. If it locks up on
62"hlt", then you are out of luck -- the event will not happen at all and the
63watchdog won't trigger. This is a shortcoming of the local APIC watchdog
64-- unfortunately there is no "clock ticks" event that would work all the
65time. The I/O APIC watchdog is driven externally and has no such shortcoming.
66But its NMI frequency is much higher, resulting in a more significant hit
67to the overall system performance.
68
69On x86 nmi_watchdog is disabled by default so you have to enable it with
70a boot time parameter.
71
72It's possible to disable the NMI watchdog in run-time by writing "0" to
73/proc/sys/kernel/nmi_watchdog. Writing "1" to the same file will re-enable
74the NMI watchdog. Notice that you still need to use "nmi_watchdog=" parameter
75at boot time.
76
77NOTE: In kernels prior to 2.4.2-ac18 the NMI-oopser is enabled unconditionally
78on x86 SMP boxes.
79
80[ feel free to send bug reports, suggestions and patches to
81 Ingo Molnar <mingo@redhat.com> or the Linux SMP mailing
82 list at <linux-smp@vger.kernel.org> ]
83
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:
38 1) # of times sched_yield() was called 38 1) # of times sched_yield() was called
39 39
40Next three are schedule() statistics: 40Next three are schedule() statistics:
41 2) # of times we switched to the expired queue and reused it 41 2) This field is a legacy array expiration count field used in the O(1)
42 scheduler. We kept it for ABI compatibility, but it is always set to zero.
42 3) # of times schedule() was called 43 3) # of times schedule() was called
43 4) # of times schedule() left the processor idle 44 4) # of times schedule() left the processor idle
44 45
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 @@
1 Static Keys
2 -----------
3
4By: Jason Baron <jbaron@redhat.com>
5
60) Abstract
7
8Static keys allows the inclusion of seldom used features in
9performance-sensitive fast-path kernel code, via a GCC feature and a code
10patching technique. A quick example:
11
12 struct static_key key = STATIC_KEY_INIT_FALSE;
13
14 ...
15
16 if (static_key_false(&key))
17 do unlikely code
18 else
19 do likely code
20
21 ...
22 static_key_slow_inc();
23 ...
24 static_key_slow_inc();
25 ...
26
27The static_key_false() branch will be generated into the code with as little
28impact to the likely code path as possible.
29
30
311) Motivation
32
33
34Currently, tracepoints are implemented using a conditional branch. The
35conditional check requires checking a global variable for each tracepoint.
36Although the overhead of this check is small, it increases when the memory
37cache comes under pressure (memory cache lines for these global variables may
38be shared with other memory accesses). As we increase the number of tracepoints
39in the kernel this overhead may become more of an issue. In addition,
40tracepoints are often dormant (disabled) and provide no direct kernel
41functionality. Thus, it is highly desirable to reduce their impact as much as
42possible. Although tracepoints are the original motivation for this work, other
43kernel code paths should be able to make use of the static keys facility.
44
45
462) Solution
47
48
49gcc (v4.5) adds a new 'asm goto' statement that allows branching to a label:
50
51http://gcc.gnu.org/ml/gcc-patches/2009-07/msg01556.html
52
53Using the 'asm goto', we can create branches that are either taken or not taken
54by default, without the need to check memory. Then, at run-time, we can patch
55the branch site to change the branch direction.
56
57For example, if we have a simple branch that is disabled by default:
58
59 if (static_key_false(&key))
60 printk("I am the true branch\n");
61
62Thus, by default the 'printk' will not be emitted. And the code generated will
63consist of a single atomic 'no-op' instruction (5 bytes on x86), in the
64straight-line code path. When the branch is 'flipped', we will patch the
65'no-op' in the straight-line codepath with a 'jump' instruction to the
66out-of-line true branch. Thus, changing branch direction is expensive but
67branch selection is basically 'free'. That is the basic tradeoff of this
68optimization.
69
70This lowlevel patching mechanism is called 'jump label patching', and it gives
71the basis for the static keys facility.
72
733) Static key label API, usage and examples:
74
75
76In order to make use of this optimization you must first define a key:
77
78 struct static_key key;
79
80Which is initialized as:
81
82 struct static_key key = STATIC_KEY_INIT_TRUE;
83
84or:
85
86 struct static_key key = STATIC_KEY_INIT_FALSE;
87
88If the key is not initialized, it is default false. The 'struct static_key',
89must be a 'global'. That is, it can't be allocated on the stack or dynamically
90allocated at run-time.
91
92The key is then used in code as:
93
94 if (static_key_false(&key))
95 do unlikely code
96 else
97 do likely code
98
99Or:
100
101 if (static_key_true(&key))
102 do likely code
103 else
104 do unlikely code
105
106A key that is initialized via 'STATIC_KEY_INIT_FALSE', must be used in a
107'static_key_false()' construct. Likewise, a key initialized via
108'STATIC_KEY_INIT_TRUE' must be used in a 'static_key_true()' construct. A
109single key can be used in many branches, but all the branches must match the
110way that the key has been initialized.
111
112The branch(es) can then be switched via:
113
114 static_key_slow_inc(&key);
115 ...
116 static_key_slow_dec(&key);
117
118Thus, 'static_key_slow_inc()' means 'make the branch true', and
119'static_key_slow_dec()' means 'make the the branch false' with appropriate
120reference counting. For example, if the key is initialized true, a
121static_key_slow_dec(), will switch the branch to false. And a subsequent
122static_key_slow_inc(), will change the branch back to true. Likewise, if the
123key is initialized false, a 'static_key_slow_inc()', will change the branch to
124true. And then a 'static_key_slow_dec()', will again make the branch false.
125
126An example usage in the kernel is the implementation of tracepoints:
127
128 static inline void trace_##name(proto) \
129 { \
130 if (static_key_false(&__tracepoint_##name.key)) \
131 __DO_TRACE(&__tracepoint_##name, \
132 TP_PROTO(data_proto), \
133 TP_ARGS(data_args), \
134 TP_CONDITION(cond)); \
135 }
136
137Tracepoints are disabled by default, and can be placed in performance critical
138pieces of the kernel. Thus, by using a static key, the tracepoints can have
139absolutely minimal impact when not in use.
140
141
1424) Architecture level code patching interface, 'jump labels'
143
144
145There are a few functions and macros that architectures must implement in order
146to take advantage of this optimization. If there is no architecture support, we
147simply fall back to a traditional, load, test, and jump sequence.
148
149* select HAVE_ARCH_JUMP_LABEL, see: arch/x86/Kconfig
150
151* #define JUMP_LABEL_NOP_SIZE, see: arch/x86/include/asm/jump_label.h
152
153* __always_inline bool arch_static_branch(struct static_key *key), see:
154 arch/x86/include/asm/jump_label.h
155
156* void arch_jump_label_transform(struct jump_entry *entry, enum jump_label_type type),
157 see: arch/x86/kernel/jump_label.c
158
159* __init_or_module void arch_jump_label_transform_static(struct jump_entry *entry, enum jump_label_type type),
160 see: arch/x86/kernel/jump_label.c
161
162
163* struct jump_entry, see: arch/x86/include/asm/jump_label.h
164
165
1665) Static keys / jump label analysis, results (x86_64):
167
168
169As an example, let's add the following branch to 'getppid()', such that the
170system call now looks like:
171
172SYSCALL_DEFINE0(getppid)
173{
174 int pid;
175
176+ if (static_key_false(&key))
177+ printk("I am the true branch\n");
178
179 rcu_read_lock();
180 pid = task_tgid_vnr(rcu_dereference(current->real_parent));
181 rcu_read_unlock();
182
183 return pid;
184}
185
186The resulting instructions with jump labels generated by GCC is:
187
188ffffffff81044290 <sys_getppid>:
189ffffffff81044290: 55 push %rbp
190ffffffff81044291: 48 89 e5 mov %rsp,%rbp
191ffffffff81044294: e9 00 00 00 00 jmpq ffffffff81044299 <sys_getppid+0x9>
192ffffffff81044299: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
193ffffffff810442a0: 00 00
194ffffffff810442a2: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
195ffffffff810442a9: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
196ffffffff810442b0: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
197ffffffff810442b7: e8 f4 d9 00 00 callq ffffffff81051cb0 <pid_vnr>
198ffffffff810442bc: 5d pop %rbp
199ffffffff810442bd: 48 98 cltq
200ffffffff810442bf: c3 retq
201ffffffff810442c0: 48 c7 c7 e3 54 98 81 mov $0xffffffff819854e3,%rdi
202ffffffff810442c7: 31 c0 xor %eax,%eax
203ffffffff810442c9: e8 71 13 6d 00 callq ffffffff8171563f <printk>
204ffffffff810442ce: eb c9 jmp ffffffff81044299 <sys_getppid+0x9>
205
206Without the jump label optimization it looks like:
207
208ffffffff810441f0 <sys_getppid>:
209ffffffff810441f0: 8b 05 8a 52 d8 00 mov 0xd8528a(%rip),%eax # ffffffff81dc9480 <key>
210ffffffff810441f6: 55 push %rbp
211ffffffff810441f7: 48 89 e5 mov %rsp,%rbp
212ffffffff810441fa: 85 c0 test %eax,%eax
213ffffffff810441fc: 75 27 jne ffffffff81044225 <sys_getppid+0x35>
214ffffffff810441fe: 65 48 8b 04 25 c0 b6 mov %gs:0xb6c0,%rax
215ffffffff81044205: 00 00
216ffffffff81044207: 48 8b 80 80 02 00 00 mov 0x280(%rax),%rax
217ffffffff8104420e: 48 8b 80 b0 02 00 00 mov 0x2b0(%rax),%rax
218ffffffff81044215: 48 8b b8 e8 02 00 00 mov 0x2e8(%rax),%rdi
219ffffffff8104421c: e8 2f da 00 00 callq ffffffff81051c50 <pid_vnr>
220ffffffff81044221: 5d pop %rbp
221ffffffff81044222: 48 98 cltq
222ffffffff81044224: c3 retq
223ffffffff81044225: 48 c7 c7 13 53 98 81 mov $0xffffffff81985313,%rdi
224ffffffff8104422c: 31 c0 xor %eax,%eax
225ffffffff8104422e: e8 60 0f 6d 00 callq ffffffff81715193 <printk>
226ffffffff81044233: eb c9 jmp ffffffff810441fe <sys_getppid+0xe>
227ffffffff81044235: 66 66 2e 0f 1f 84 00 data32 nopw %cs:0x0(%rax,%rax,1)
228ffffffff8104423c: 00 00 00 00
229
230Thus, the disable jump label case adds a 'mov', 'test' and 'jne' instruction
231vs. the jump label case just has a 'no-op' or 'jmp 0'. (The jmp 0, is patched
232to a 5 byte atomic no-op instruction at boot-time.) Thus, the disabled jump
233label case adds:
234
2356 (mov) + 2 (test) + 2 (jne) = 10 - 5 (5 byte jump 0) = 5 addition bytes.
236
237If we then include the padding bytes, the jump label code saves, 16 total bytes
238of instruction memory for this small fucntion. In this case the non-jump label
239function is 80 bytes long. Thus, we have have saved 20% of the instruction
240footprint. We can in fact improve this even further, since the 5-byte no-op
241really can be a 2-byte no-op since we can reach the branch with a 2-byte jmp.
242However, we have not yet implemented optimal no-op sizes (they are currently
243hard-coded).
244
245Since there are a number of static key API uses in the scheduler paths,
246'pipe-test' (also known as 'perf bench sched pipe') can be used to show the
247performance improvement. Testing done on 3.3.0-rc2:
248
249jump label disabled:
250
251 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
252
253 855.700314 task-clock # 0.534 CPUs utilized ( +- 0.11% )
254 200,003 context-switches # 0.234 M/sec ( +- 0.00% )
255 0 CPU-migrations # 0.000 M/sec ( +- 39.58% )
256 487 page-faults # 0.001 M/sec ( +- 0.02% )
257 1,474,374,262 cycles # 1.723 GHz ( +- 0.17% )
258 <not supported> stalled-cycles-frontend
259 <not supported> stalled-cycles-backend
260 1,178,049,567 instructions # 0.80 insns per cycle ( +- 0.06% )
261 208,368,926 branches # 243.507 M/sec ( +- 0.06% )
262 5,569,188 branch-misses # 2.67% of all branches ( +- 0.54% )
263
264 1.601607384 seconds time elapsed ( +- 0.07% )
265
266jump label enabled:
267
268 Performance counter stats for 'bash -c /tmp/pipe-test' (50 runs):
269
270 841.043185 task-clock # 0.533 CPUs utilized ( +- 0.12% )
271 200,004 context-switches # 0.238 M/sec ( +- 0.00% )
272 0 CPU-migrations # 0.000 M/sec ( +- 40.87% )
273 487 page-faults # 0.001 M/sec ( +- 0.05% )
274 1,432,559,428 cycles # 1.703 GHz ( +- 0.18% )
275 <not supported> stalled-cycles-frontend
276 <not supported> stalled-cycles-backend
277 1,175,363,994 instructions # 0.82 insns per cycle ( +- 0.04% )
278 206,859,359 branches # 245.956 M/sec ( +- 0.04% )
279 4,884,119 branch-misses # 2.36% of all branches ( +- 0.85% )
280
281 1.579384366 seconds time elapsed
282
283The percentage of saved branches is .7%, and we've saved 12% on
284'branch-misses'. This is where we would expect to get the most savings, since
285this optimization is about reducing the number of branches. In addition, we've
286saved .2% on instructions, and 2.8% on cycles and 1.4% on elapsed time.
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.
226 Traces and records the max latency that it takes for 226 Traces and records the max latency that it takes for
227 the highest priority task to get scheduled after 227 the highest priority task to get scheduled after
228 it has been woken up. 228 it has been woken up.
229 Traces all tasks as an average developer would expect.
230
231 "wakeup_rt"
232
233 Traces and records the max latency that it takes for just
234 RT tasks (as the current "wakeup" does). This is useful
235 for those interested in wake up timings of RT tasks.
229 236
230 "hw-branch-tracer" 237 "hw-branch-tracer"
231 238
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邮件列表中提供反馈,告诉大家你遇到了问题还是
316 git.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6.git 316 git.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6.git
317 317
318 使用quilt管理的补丁集: 318 使用quilt管理的补丁集:
319 - USB, PCI, 驱动程序核心和I2C, Greg Kroah-Hartman <gregkh@suse.de> 319 - USB, PCI, 驱动程序核心和I2C, Greg Kroah-Hartman <gregkh@linuxfoundation.org>
320 kernel.org/pub/linux/kernel/people/gregkh/gregkh-2.6/ 320 kernel.org/pub/linux/kernel/people/gregkh/gregkh-2.6/
321 - x86-64, 部分i386, Andi Kleen <ak@suse.de> 321 - x86-64, 部分i386, Andi Kleen <ak@suse.de>
322 ftp.firstfloor.org:/pub/ak/x86_64/quilt/ 322 ftp.firstfloor.org:/pub/ak/x86_64/quilt/