192:, colored red to indicate that it might be accessed by a reader at any time, thus requiring updaters to take care. Allocating memory for a new structure transitions to the second state. This structure has indeterminate state (indicated by the question marks) but is inaccessible to readers (indicated by the green color). Because the structure is inaccessible to readers, the updater may carry out any desired operation without fear of disrupting concurrent readers. Initializing this new structure transitions to the third state, which shows the initialized values of the structure's fields. Assigning a reference to this new structure to
396:
from deleting the data structure out from under them. The reason is that lock-based updaters typically update data in place and must therefore exclude readers. In contrast, RCU-based updaters typically take advantage of the fact that writes to single aligned pointers are atomic on modern CPUs, allowing atomic insertion, removal, and replacement of data in a linked structure without disrupting readers. Concurrent RCU readers can then continue accessing the old versions and can dispense with the atomic read-modify-write instructions, memory barriers, and cache misses that are so expensive on modern
4915:
317:. By definition, any RCU read-side critical section in existence at the beginning of a given grace period must complete before the end of that grace period, which constitutes the fundamental guarantee provided by RCU. In addition, the wait-for-readers operation must wait for at least one grace period to elapse. It turns out that this guarantee can be provided with extremely small read-side overheads, in fact, in the limiting case that is actually realized by server-class Linux-kernel builds, the read-side overhead is exactly zero.
169:
212:
4927:
3570:
2213:
4901:
580:
944:
within an RCU read-side critical section. Therefore, if a given CPU executes a context switch (to schedule another process), we know that this CPU must have completed all preceding RCU read-side critical sections. Once all CPUs have executed a context switch, then all preceding RCU read-side critical sections will have completed.
3352:
329:
readers is the semantics of modern CPUs guarantee that readers will see either the old or the new version of the data structure rather than a partially updated reference. Once a grace period has elapsed, there can no longer be any readers referencing the old version, so it is then safe for the reclamation phase to free (
523:
CPU 0 CPU 1 CPU 2 ----------------- ------------------------- --------------- 1. rcu_read_lock() 2. enters synchronize_rcu() 3. rcu_read_lock() 4. rcu_read_unlock() 5.
357:
In the above procedure (which matches the earlier diagram), the updater is performing both the removal and the reclamation step, but it is often helpful for an entirely different thread to do the reclamation. Reference counting can be used to let the reader perform removal so, even if the same thread
412:
Of course, RCU also has disadvantages. For example, RCU is a specialized technique that works best in situations with mostly reads and few updates but is often less applicable to update-only workloads. For another example, although the fact that RCU readers and updaters may execute concurrently is
328:
phases. The removal phase removes references to data items within a data structure (possibly by replacing them with references to new versions of these data items) and can run concurrently with RCU read-side critical sections. The reason that it is safe to run the removal phase concurrently with RCU
180:
A key property of RCU is that readers can access a data structure even when it is in the process of being updated: RCU updaters cannot block readers or force them to retry their accesses. This overview starts by showing how data can be safely inserted into and deleted from linked structures despite
2356:
Ilan
Frenkel, Roman Geller, Yoram Ramberg, and Yoram Snir were granted US Patent 7,099,932 in 2006. This patent describes an RCU-like mechanism for retrieving and storing quality of service policy management information using a directory service in a manner that enforces read/write consistency and
562:
to fetch an RCU-protected pointer, which returns a value that may then be safely dereferenced. It also executes any directives required by the compiler or the CPU, for example, a volatile cast for gcc, a memory_order_consume load for C/C++11 or the memory-barrier instruction required by the old DEC
395:
The ability to wait until all readers are done allows RCU readers to use much lighter-weight synchronization—in some cases, absolutely no synchronization at all. In contrast, in more conventional lock-based schemes, readers must use heavy-weight synchronization in order to prevent an updater
219:
This procedure demonstrates how new data may be inserted into a linked data structure even though readers are concurrently traversing the data structure before, during, and after the insertion. The second diagram on the right depicts a four-state deletion procedure, again with time advancing from
2175:
However, there is one potential catch: the read-side and update-side critical sections can now run concurrently. In many cases, this will not be a problem, but it is necessary to check carefully regardless. For example, if multiple independent list updates must be seen as a single atomic update,
943:
moves the caller of synchronize_cpu to each CPU, thus blocking until all CPUs have been able to perform the context switch. Recall that this is a non-preemptive environment and that blocking within an RCU read-side critical section is illegal, which imply that there can be no preemption points
374:
By early 2008, there were almost 2,000 uses of the RCU API within the Linux kernel including the networking protocol stacks and the memory-management system. As of March 2014, there were more than 9,000 uses. Since 2006, researchers have applied RCU and similar techniques to a number of
293:
This procedure demonstrates how old data may be removed from a linked data structure even though readers are concurrently traversing the data structure before, during, and after the deletion. Given insertion and deletion, a wide variety of data structures can be implemented using RCU.
3568:, Frenkel, Ilan; Geller, Roman & Ramberg, Yoram et al., "Method and apparatus for retrieving network quality of service policy information from a directory in a quality of service policy management system", published 2006-08-29, assigned to Cisco Tech Inc.
365:
for a shared data structure. RCU is completely wait-free for any number of readers. Single-writer implementations RCU are also lock-free for the writer. Some multi-writer implementations of RCU are lock-free. Other multi-writer implementations of RCU serialize writers with a lock.
313:, and such statements are not permitted to hold references to RCU-protected data structures, nor is the wait-for-readers operation required to wait for threads in quiescent states. Any time period during which each thread resides at least once in a quiescent state is called a
336:
Splitting an update into removal and reclamation phases allows the updater to perform the removal phase immediately, and to defer the reclamation phase until all readers active during the removal phase have completed, in other words, until a grace period has elapsed.
3295:
400:
computer systems, even in absence of lock contention. The lightweight nature of RCU's read-side primitives provides additional advantages beyond excellent performance, scalability, and real-time response. For example, they provide immunity to most
550:
rcu_assign_pointer(): The updater uses this function to assign a new value to an RCU-protected pointer, in order to safely communicate the change in value from the updater to the reader. This function returns the new value, and also executes any
2431:
Only readers that are active during the removal phase need be considered, because any reader starting after the removal phase will be unable to gain a reference to the removed data items, and therefore cannot be disrupted by the reclamation
282:. In other words, RCU provides coordination in space (different versions of the list) as well as in time (different states in the deletion procedures). This is in stark contrast with more traditional synchronization primitives such as
2271:
and
Richard Ladner extended Kung's and Lehman's work to non-garbage-collected environments by deferring reclamation until all threads running at removal time have terminated, which works in environments that do not have long-lived
2302:
Aju John proposed an RCU-like implementation where updaters simply wait for a fixed period of time, under the assumption that readers would all complete within that fixed time, as might be appropriate in a hard real-time system.
267:, new readers have no way to obtain a reference. A wait-for-readers operation transitions to the third state. Note that this wait-for-readers operation need only wait for pre-existing readers, but not new readers. Element
2869:
Appavoo, Jonathan; Da Silva, Dilma; Krieger, Orran; Auslander, Mark; Ostrowski, Michal; Rosenburg, Bryan; Waterland, Amos; Wisniewski, Robert W.; Xenidis, Jimi (August 2007). "Experience distributing objects in an SMMP OS".
2501:
Guniguntala, Dinakar; McKenney, Paul E.; Triplett, Joshua; Walpole, Jonathan (April–June 2008). "The read-copy-update mechanism for supporting real-time applications on shared-memory multiprocessor systems with Linux".
952:
Although RCU can be used in many different ways, a very common use of RCU is analogous to reader–writer locking. The following side-by-side code display shows how closely related reader–writer locking and RCU can be.
3350:, Slingwine, John D. & McKenney, Paul E., "Apparatus and Method for Achieving Reduced Overhead Mutual Exclusion and Maintaining Coherency in a Multiprocessor System", published August 1995
496:
The implementation of RCU in version 2.6 of the Linux kernel is among the better-known RCU implementations and will be used as an inspiration for the RCU API in the remainder of this article. The core API
350:
Wait for a grace period to elapse, so that all previous readers (which might still have pointers to the data structure removed in the prior step) will have completed their RCU read-side critical sections.
508:
rcu_read_unlock(): Used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Note that RCU read-side critical sections may be nested and/or overlapping.
2285:
James P. Hennessy, Damian L. Osisek, and Joseph W. Seigh, II were granted US Patent 4,809,168 in 1989 (since lapsed). This patent describes an RCU-like mechanism that was apparently used in
3267:
541:
Alternatively, instead of blocking, synchronize_rcu may register a callback to be invoked after all ongoing RCU read-side critical sections have completed. This callback variant is called
614:
callbacks may be invoked. Efficient implementations of the RCU infrastructure make heavy use of batching in order to amortize their overhead over many uses of the corresponding APIs.
3654:(1995) "Apparatus and method for achieving reduced overhead mutual exclusion and maintaining coherency in a multiprocessor system utilizing execution history and thread monitoring"
4477:
3766:
3293:, Hennessy, James P.; Osisek, Damian L. & Seigh II, Joseph W., "Passive Serialization in a Multitasking Environment", published February 1989
2453:
RCU-based deadlocks are still possible, for example by executing a statement that blocks until a grace period completes within an RCU read-side critical section.
854:
can be ignored without missing much. However, they are needed in order to suppress harmful compiler optimization and to prevent CPUs from reordering accesses.
243:
from this list transitions to the second state. Note that the link from element B to C is left intact in order to allow readers currently referencing element
2999:
Hart, Thomas E.; McKenney, Paul E.; Demke Brown, Angela; Walpole, Jonathan (December 2007). "Performance of memory reclamation for lockless synchronization".
2282:(TLB) implementation that deferred reclaiming virtual-address space until all CPUs flushed their TLB, which is similar in spirit to some RCU implementations.
936:. However, in this toy RCU implementation, blocking within an RCU read-side critical section is illegal, just as is blocking while holding a pure spinlock.
532:
is the API that must figure out when readers are done, its implementation is key to RCU. For RCU to be useful in all but the most read-intensive situations,
136:, hence the name "read-copy update". The abbreviation "RCU" was one of many contributions by the Linux community. Other names for similar techniques include
2834:; Krieger, Orran; Wisniewski, Robert W.; Waterland, Amos; Tam, David; Baumann, Andrew (April 2006). "K42: an infrastructure for operating system research".
4566:
4561:
622:
RCU has extremely simple "toy" implementations that can aid understanding of RCU. This section presents one such "toy" implementation that works in a
425:
113:
sleep until the operating system kernel determines that there are no readers left using the old structure, for example, in the Linux kernel, by using
278:
It is important to reiterate that in the second state different readers can see two different versions of the list, either with or without element
375:
problems, including management of metadata used in dynamic analysis, managing the lifetime of clustered objects, managing object lifetime in the
200:
primitive is used to carry out this assignment and ensures that the assignment is atomic in the sense that concurrent readers will either see a
70:, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e.g., dereferencing
3691:
3417:
3391:
2975:
2815:
2770:
2694:
2441:
4953:
4919:
358:
performs both the update step (step (2) above) and the reclamation step (step (4) above), it is often helpful to think of them separately.
353:
At this point, there cannot be any readers still holding references to the data structure, so it now may safely be reclaimed (e.g., freed).
2950:
Porter, Donald E.; Hofmann, Owen S.; Rossbach, Christopher J.; Benn, Alexander; Witchel, Emmett (2009). "Operating systems transactions".
271:
is now colored green to indicate that readers can no longer be referencing it. Therefore, it is now safe for the updater to free element
93:
The name comes from the way that RCU is used to update a linked structure in place. A thread wishing to do this uses the following steps:
3315:(Technical report). Institute of Advanced Computer Science Studies, Department of Computer Science, University of Maryland. CS-TR-2222.1.
555:
instructions required for a given CPU architecture. Perhaps more importantly, it serves to document which pointers are protected by RCU.
344:
Ensure that all readers accessing RCU-protected data structures carry out their references from within an RCU read-side critical section.
519:
necessarily wait for any subsequent RCU read-side critical sections to complete. For example, consider the following sequence of events:
2382:
196:
transitions to the fourth and final state. In this state, the structure is accessible to readers, and is therefore colored red. The
181:
concurrent readers. The first diagram on the right depicts a four-state insertion procedure, with time advancing from left to right.
82:
32:
4298:
4066:
2485:
2296:
505:
rcu_read_lock(): Marks an RCU-protected data structure so that it won't be reclaimed for the full duration of that critical section.
498:
413:
what enables the lightweight nature of RCU's read-side primitives, some algorithms may not be amenable to read/update concurrency.
3266:
Rashid, Richard; Tevanian, Avadis; Young, Michael; Golub, David; Baron, Robert; Bolosky, William; Chew, Jonathan (October 1987).
2387:
3796:
3443:
3102:
McKenney, Paul E.; Appavoo, Jonathan; Kleen, Andi; Krieger, Orran; Russell, Rusty; Sarma, Dipankar; Soni, Maneesh (July 2001).
4408:
101:
44:
3736:
908:
do nothing. This is the great strength of classic RCU in a non-preemptive kernel: read-side overhead is precisely zero, as
4842:
380:
2604:
4958:
4723:
3771:
2279:
511:
synchronize_rcu(): Blocks until all pre-existing RCU read-side critical sections on all CPUs have completed. Note that
4125:
925:
402:
235:. All three elements are colored red to indicate that an RCU reader might reference any of them at any time. Using
172:
Read-copy-update insertion procedure. A thread allocates a structure with three fields, then sets the global pointer
3327:
416:
Despite well over a decade of experience with RCU, the exact extent of its applicability is still a research topic.
4824:
4638:
3756:
3684:
2616:
2321:
2310:
J. Slingwine and P. E. McKenney received US Patent 5,442,758 in August 1995, which describes RCU as implemented in
283:
204:
pointer or a valid pointer to the new structure, but not some mash-up of the two values. Additional properties of
157:
4829:
4471:
3807:
397:
2642:
McKenney, Paul E.; Walpole, Jonathan (July 2008). "Introducing technology into the Linux kernel: a case study".
4392:
4377:
4293:
4081:
3886:
2575:
2392:
623:
437:
78:
4735:
4534:
4170:
4058:
4013:
3963:
3947:
3924:
3474:
3473:
Desnoyers, Mathieu; McKenney, Paul E.; Stern, Alan; Dagenais, Michel R.; Walpole, Jonathan (February 2012).
2377:
933:
36:
3746:
4880:
4857:
4852:
4687:
4653:
4643:
4515:
4460:
4337:
3876:
3211:
3179:
2914:
362:
263:
is now colored yellow to indicate that while pre-existing readers might still have a reference to element
168:
3581:
3580:
Bauer, R.T., (June 2009), "Operational
Verification of a Relativistic Program" PSU Tech Report TR-09-04 (
387:
uses a technique similar to RCU that most closely resembles Linux's
Sleepable RCU (SRCU) implementation.
81:, enabling fast operations at the cost of more space. This makes all readers proceed as if there were no
4931:
4834:
3677:
2318:
2286:
211:
145:
56:
3247:
Manber, Udi; Ladner, Richard E. (September 1984). "Concurrency
Control in a Dynamic Search Structure".
2719:
2265:
and Q. Lehman described use of garbage collectors to implement RCU-like access to a binary search tree.
3565:
3347:
3290:
4864:
4466:
4028:
3726:
3269:
Machine-Independent
Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures
3053:
2347:
Robert Colvin et al. formally verified a lazy concurrent list-based set algorithm that resembles RCU.
3216:
3103:
2919:
4660:
4139:
3998:
3932:
3421:
3395:
2566:
2407:
2402:
2397:
2367:
920:
macro is a volatile cast that generates no additional code in most cases. And there is no way that
587:
The diagram on the right shows how each API communicates among the reader, updater, and reclaimer.
3367:
4814:
4648:
4234:
4134:
4071:
3993:
3988:
3776:
3542:
3497:
3229:
2981:
2932:
2887:
2851:
2776:
2700:
2659:
2629:
929:
287:
40:
2341:
3369:
Tornado: Maximizing
Locality and Concurrency in a Shared Memory Multiprocessor Operating System
2755:
Proceedings of the 42nd Annual IEEE/ACM International
Symposium on Microarchitecture - Micro-42
2677:
Olsson, Robert; Nilsson, Stefan (May 2007). "TRASH a dynamic LC-trie and hash data structure".
4785:
4433:
4403:
4398:
4249:
3904:
3866:
3662:
3618:
3598:
3520:
3081:
3031:
2971:
2811:
2766:
2690:
2534:
2481:
524:
exits synchronize_rcu() 6. rcu_read_unlock()
347:
Remove pointers to a data structure, so that subsequent readers cannot gain a reference to it.
2556:
259:, but either way, each reader will see a valid and correctly formatted linked list. Element
4539:
3822:
3812:
3721:
3489:
3221:
3008:
2963:
2955:
2924:
2879:
2843:
2803:
2758:
2682:
2651:
2511:
2337:
and Phil Rumpf described RCU-like techniques for handling unloading of Linux kernel modules.
20:
3637:
3202:
Kung, H. T.; Lehman, Q. (September 1980). "Concurrent
Maintenance of Binary Search Trees".
2317:
B. Gamsa, O. Krieger, J. Appavoo, and M. Stumm described an RCU-like mechanism used in the
4775:
4443:
4224:
3632:
3131:
2590:
2412:
2258:
Techniques and mechanisms resembling RCU have been independently invented multiple times:
428:
3310:
3277:
Second
Symposium on Architectural Support for Programming Languages and Operating Systems
2739:
2632:. quote: "To manage write–write conflicts, most RCU data structures use regular locking."
309:. Any statement that is not within an RCU read-side critical section is said to be in a
2800:
PLOS '06: Proceedings of the 3rd Workshop on Programming Languages and Operating Systems
2156:
The differences between the two approaches are quite small. Read-side locking moves to
4805:
4710:
4621:
4498:
4493:
4488:
4483:
4266:
4091:
4086:
3731:
2952:
Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles - SOSP '09
2831:
2275:
552:
48:
4947:
4740:
4556:
4362:
4352:
4111:
3983:
3861:
3157:
3127:
2372:
2334:
2290:
384:
67:
3633:
Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation
3456:
3233:
2967:
2704:
2663:
4905:
4626:
4544:
4438:
4382:
3741:
3700:
3640:
comparing RCU's performance to that of other lockless synchronization mechanisms.
2936:
2780:
2325:
2304:
2238:
486:
71:
52:
3501:
2891:
2855:
2164:, update-side locking moves from a reader-writer lock to a simple spinlock, and a
2985:
4631:
4524:
4106:
4003:
3642:
3377:
Proceedings of the Third Symposium on Operating System Design and Implementation
2753:
Kannan, Hari (2009). "Ordering decoupled metadata accesses in multiprocessors".
2299:
described an RCU-like mechanism that relied on explicit flag-setting by readers.
247:
to traverse the remainder of the list. Readers accessing the link from element
3366:
Gamsa, Ben; Krieger, Orran; Appavoo, Jonathan; Stumm, Michael (February 1999).
3012:
4718:
4693:
4680:
4585:
4573:
4503:
4413:
3899:
3802:
3761:
3650:
3442:
Colvin, Robert; Groves, Lindsay; Luchangco, Victor; Moir, Mark (August 2006).
3189:
OGI School of Science and Engineering at Oregon Health and Sciences University
2686:
2268:
2262:
471:
470:
covers a closely related technique. RCU is also the topic of one claim in the
466:
460:
454:
448:
442:
432:
60:
2353:
A. Gotsman et al. derived formal semantics for RCU based on separation logic.
928:
cycle, cause a realtime process to miss its scheduling deadline, precipitate
4580:
4549:
4418:
4254:
4043:
3914:
3871:
2959:
2928:
2883:
2847:
2807:
2762:
2655:
2311:
2227:
913:
567:
is valid only within the enclosing RCU read-side critical section. As with
3515:
McKenney, Paul E.; Desnoyers, Mathieu; Jiangshan, Lai (November 13, 2013).
3181:
Exploiting Deferred Destruction: An Analysis of Read-Copy-Update Techniques
3153:
2796:
Portability events: a programming model for scalable system infrastructures
85:
involved, hence they will be fast, but also making updates more difficult.
3493:
3225:
2905:
Fraser, Keir; Harris, Tim (2007). "Concurrent programming without locks".
66:
Whenever a thread is inserting or deleting elements of data structures in
4698:
4519:
4508:
4428:
4372:
4367:
4313:
4261:
4150:
4076:
3625:
2223:
406:
2515:
4780:
4765:
4675:
4665:
4605:
4529:
4423:
4347:
4288:
4202:
4165:
4096:
4038:
4033:
3937:
3894:
2558:
Read-Copy Update: Using Execution History to Solve Concurrency Problems
485:
RCU is available in a number of operating systems and was added to the
474:
340:
So, the typical RCU update sequence goes something like the following:
3594:
Paul E. McKenney, Mathieu Desnoyers, and Lai Jiangshan: User-space RCU
3582:
http://www.pdx.edu/sites/www.pdx.edu.computer-science/files/tr0904.pdf
4770:
4755:
4745:
4600:
4595:
4357:
4308:
4281:
4244:
4214:
4181:
4160:
3909:
3856:
3751:
3541:
Gotsman, Alexey; Rinetzky, Noam; Yang, Hongseok (March 16–24, 2013).
2199:. This is especially useful in combination with reference counting.
77:
It is used when performance of reads is crucial and is an example of
3657:
3613:
3609:
3605:
3593:
3516:
3077:
3027:
2721:
A Lockless Pagecache in Linux---Introduction, Progress, Performance
2530:
579:
4900:
4590:
4453:
4387:
4342:
4303:
4271:
4239:
4197:
4192:
4155:
4023:
4018:
3978:
3973:
3606:
Paul E. McKenney and Jonathan Walpole: What is RCU, Fundamentally?
578:
320:
RCU's fundamental guarantee may be used by splitting updates into
210:
167:
100:
copy the data from the old structure into the new one, and save a
3445:
Formal Verification of a Lazy Concurrent List-Based Set Algorithm
583:
RCU API communications between the reader, updater, and reclaimer
4670:
4448:
4276:
4207:
3851:
3673:
3669:
916:
CPUs; such memory barriers are not needed on modern CPUs. The
4750:
4728:
2350:
M. Desnoyers et al. published a description of user-space RCU.
2328:
2206:
376:
153:
43:
concurrently read and update elements that are linked through
3544:
Verifying concurrent memory reclamation algorithms with grace
2794:
Matthews, Chris; Coady, Yvonne; Appavoo, Jonathan (2009).
2603:
Naama Ben-David; Guy E. Blelloch; Yihan Sun; Yuanhao Wei.
2529:
McKenney, Paul E.; Walpole, Jonathan (December 17, 2007).
120:
once awakened by the kernel, deallocate the old structure.
2307:
proposed a similar scheme in 1993 (verbal communication).
490:
223:
The first state shows a linked list containing elements
110:
update the global pointer to refer to the new structure,
2679:
2007 Workshop on High Performance Switching and Routing
2234:
2555:
McKenney, Paul E.; Slingwine, John D. (October 1998).
3482:
IEEE Transactions on Parallel and Distributed Systems
590:
The RCU infrastructure observes the time sequence of
489:
in October 2002. User-level implementations such as
3128:"Shared Memory, Threads, Interprocess Communication"
2444:, where available, may be used to perform this step.
275:, thus transitioning to the fourth and final state.
4873:
4813:
4804:
4709:
4614:
4330:
4223:
4133:
4124:
4057:
3962:
3955:
3946:
3923:
3885:
3844:
3837:
3785:
3714:
3707:
575:
is to document which pointers are protected by RCU.
2617:"Lock-free multithreading with atomic operations"
464:(expired 2009-05-25). The now-expired US Patent
3475:"User-Level Implementations of Read-Copy Update"
3329:Dynamic vnodes — design and implementation
610:invocations may return to their callers and (2)
333:) the data items that made up that old version.
2567:Parallel and Distributed Computing and Systems
3685:
2176:converting to RCU will require special care.
184:The first state shows a global pointer named
8:
2480:(4th ed.). USA: Pearson. p. 148.
606:invocations in order to determine when (1)
290:that coordinate in time, but not in space.
4810:
4706:
4130:
3959:
3952:
3841:
3711:
3692:
3678:
3670:
3552:ESOP'13: European Symposium on Programming
436:, issued August 15, 1995, and assigned to
379:research operating system, and optimizing
251:will either obtain a reference to element
3215:
2918:
4920:Free and open-source software portal
4478:Earliest eligible virtual deadline first
3630:Hart, McKenney, and Demke Brown (2006).
3154:"Using {RCU} in the {Linux} 2.5 Kernel"
2465:
2424:
3279:. Association for Computing Machinery.
3076:McKenney, Paul E. (January 17, 2008).
2585:
2584:
2573:
3026:McKenney, Paul E. (January 4, 2008).
2605:"Efficient Single Writer Concurrency"
2187:can now block. If this is a problem,
859:#define rcu_assign_pointer(p, v) ({ \
536:'s overhead must also be quite small.
208:are described later in this article.
7:
3312:Concurrent Maintenance of Skip Lists
3249:ACM Transactions on Database Systems
3204:ACM Transactions on Database Systems
3052:Desnoyers, Mathieu (December 2009).
2907:ACM Transactions on Computer Systems
2872:ACM Transactions on Computer Systems
2471:
2469:
880:typeof(p) _value = ACCESS_ONCE(p); \
3055:Low-Impact Operating System Tracing
2740:"Paul E. McKenney: RCU Linux Usage"
558:rcu_dereference(): The reader uses
215:Read-copy-update deletion procedure
3152:McKenney, Paul E. (October 2003).
2383:Lock-free and wait-free algorithms
2342:version 2.5.43 of the Linux kernel
948:Analogy with reader–writer locking
724:// add callback/arg pair to a list
563:Alpha CPU. The value returned by
301:, which are normally delimited by
107:modify the new, copied, structure,
14:
2322:Tornado research operating system
499:Application Programming Interface
35:mechanism that avoids the use of
4926:
4925:
4913:
4899:
3767:Supported computer architectures
2388:Multiversion concurrency control
2211:
3797:The Linux Programming Interface
3626:Paul E. McKenney's RCU web page
3178:McKenney, Paul E. (July 2004).
3063:École Polytechnique de Montreal
2357:enables read/write concurrency.
886:/* nop on most architectures */
877:#define rcu_dereference(p) ({ \
361:RCU is perhaps the most common
3646:(including Walpole as author).
2314:and later in the Linux kernel.
2226:format but may read better as
2183:means that the RCU version of
1:
2531:"What is RCU, Fundamentally?"
912:is an empty macro on all but
381:software transactional memory
297:RCU's readers execute within
3658:Paul McKenney: Sleepable RCU
3416:Russell, Rusty (June 2000).
3390:Russell, Rusty (June 2000).
2280:translation lookaside buffer
883:smp_read_barrier_depends();
865:/* Order previous writes. */
424:The technique is covered by
391:Advantages and disadvantages
4954:Operating system technology
3453:Computer Aided Verification
3309:Pugh, William (June 1990).
3126:Wizard, The (August 2001).
3001:J. Parallel Distrib. Comput
2630:"Notes on Read-Copy Update"
2331:research operating systems.
958:/* reader-writer locking */
571:, an important function of
299:read-side critical sections
176:to point to this structure.
128:concurrently with a thread
4975:
4639:High-performance computing
4461:Process and I/O schedulers
3610:What is RCU? Part 2: Usage
3326:John, Aju (January 1995).
3013:10.1016/j.jpdc.2007.04.010
2718:Piggin, Nick (July 2006).
2476:Tanenbaum, Andrew (2015).
910:smp_read_barrier_depends()
624:non-preemptive environment
458:(expired 2009-05-18), and
47:and that belong to shared
39:primitives while multiple
4893:
4472:Completely Fair Scheduler
3737:Tanenbaum–Torvalds debate
3418:"Re: modular net drivers"
3392:"Re: modular net drivers"
3078:"RCU part 3: the RCU API"
2687:10.1109/HPSR.2007.4281239
16:Synchronization mechanism
4393:Kernel same-page merging
2968:2152/ETD-UT-2010-12-2488
2478:Modern Operating Systems
2393:Pre-emptive multitasking
2324:and the closely related
2278:et al. described a lazy
955:
856:
784:schedule_current_task_to
628:
438:Sequent Computer Systems
4736:OS-level virtualization
3614:RCU part 3: the RCU API
2960:10.1145/1629575.1629591
2929:10.1145/1233307.1233309
2884:10.1145/1275517.1275518
2848:10.1145/1131322.1131333
2808:10.1145/1215995.1216006
2763:10.1145/1669112.1669161
2656:10.1145/1400097.1400099
2378:Lock (computer science)
2235:converting this section
1362:list_for_each_entry_rcu
1099:/* Other data fields */
1093:/* Other data fields */
871:ACCESS_ONCE(p) = (v); \
97:create a new structure,
4881:List of Linux adopters
3823:Linux User Group (LUG)
3113:Ottawa Linux Symposium
2836:SIGOPS Oper. Syst. Rev
2726:Ottawa Linux Symposium
2644:SIGOPS Oper. Syst. Rev
2340:D. Sarma added RCU to
2179:Also, the presence of
939:The implementation of
584:
452:(expired 2010-04-05),
446:(expired 2009-03-30),
363:non-blocking algorithm
216:
177:
3651:U.S. patent 5,442,758
3638:IPDPS 2006 Best Paper
3494:10.1109/TPDS.2011.159
3226:10.1145/320613.320619
2802:. San Jose, CA, USA.
2319:University of Toronto
924:can participate in a
618:Simple implementation
582:
467:U.S. patent 4,809,168
461:U.S. patent 6,886,162
455:U.S. patent 6,219,690
449:U.S. patent 5,727,209
443:U.S. patent 5,608,893
433:U.S. patent 5,442,758
214:
171:
138:passive serialization
104:to the old structure,
4467:Brain Fuck Scheduler
3727:Linux Mark Institute
2757:. pp. 381–390.
932:, or result in high
846:In the code sample,
545:in the Linux kernel.
493:are also available.
481:Sample RCU interface
164:Detailed description
124:So the structure is
4959:Concurrency control
4661:Real-time computing
3933:Linux Standard Base
3028:"RCU part 2: Usage"
2570:. pp. 509–518.
2516:10.1147/sj.472.0221
2504:IBM Systems Journal
2408:Resource starvation
2403:Resource contention
2398:Real-time computing
2368:Concurrency control
2193:call_rcu (kfree, p)
2191:could be used like
1813:list_for_each_entry
1780:list_for_each_entry
1329:list_for_each_entry
79:space–time tradeoff
4649:Compute Node Linux
4235:C standard library
3334:USENIX Winter 1995
2442:Garbage collectors
2237:, if appropriate.
930:priority inversion
848:rcu_assign_pointer
585:
569:rcu_assign_pointer
501:) is quite small:
383:implementations.
239:to remove element
217:
206:rcu_assign_pointer
198:rcu_assign_pointer
188:that is initially
178:
132:in order to do an
4941:
4940:
4889:
4888:
4800:
4799:
4796:
4795:
4434:Network scheduler
4326:
4325:
4322:
4321:
4120:
4119:
3867:Linux kernel oops
3833:
3832:
3813:Linux conferences
3663:Linux Weekly News
3619:Linux Weekly News
3599:Linux Weekly News
3521:Linux Weekly News
3082:Linux Weekly News
3032:Linux Weekly News
3007:(12): 1270–1285.
2977:978-1-60558-752-3
2817:978-1-59593-577-9
2772:978-1-60558-798-1
2696:978-1-4244-1205-1
2583:External link in
2535:Linux Weekly News
2256:
2255:
115:synchronize_rcu()
89:Name and overview
4966:
4929:
4928:
4918:
4917:
4916:
4906:Linux portal
4904:
4903:
4811:
4707:
4516:Security Modules
4131:
3960:
3953:
3842:
3722:Linux Foundation
3712:
3694:
3687:
3680:
3671:
3653:
3575:
3574:
3573:
3569:
3562:
3556:
3555:
3549:
3538:
3532:
3531:
3529:
3527:
3517:"User-space RCU"
3512:
3506:
3505:
3479:
3470:
3464:
3463:
3461:
3455:. Archived from
3450:
3439:
3433:
3432:
3430:
3429:
3420:. Archived from
3413:
3407:
3406:
3404:
3403:
3394:. Archived from
3387:
3381:
3380:
3374:
3363:
3357:
3356:
3355:
3351:
3344:
3338:
3337:
3323:
3317:
3316:
3306:
3300:
3299:
3298:
3294:
3287:
3281:
3280:
3274:
3263:
3257:
3256:
3244:
3238:
3237:
3219:
3199:
3193:
3192:
3186:
3175:
3169:
3168:
3166:
3164:
3149:
3143:
3142:
3140:
3138:
3123:
3117:
3116:
3110:
3105:Read-Copy Update
3099:
3093:
3092:
3090:
3088:
3073:
3067:
3066:
3060:
3049:
3043:
3042:
3040:
3038:
3023:
3017:
3016:
2996:
2990:
2989:
2947:
2941:
2940:
2922:
2902:
2896:
2895:
2866:
2860:
2859:
2828:
2822:
2821:
2791:
2785:
2784:
2750:
2744:
2743:
2736:
2730:
2729:
2715:
2709:
2708:
2681:. pp. 1–6.
2674:
2668:
2667:
2639:
2633:
2626:
2620:
2614:
2608:
2601:
2595:
2594:
2588:
2587:
2581:
2579:
2571:
2563:
2552:
2546:
2545:
2543:
2541:
2526:
2520:
2519:
2498:
2492:
2491:
2473:
2454:
2451:
2445:
2439:
2433:
2429:
2344:in October 2002.
2251:
2248:
2242:
2233:You can help by
2215:
2214:
2207:
2198:
2194:
2190:
2186:
2182:
2171:
2167:
2163:
2159:
2152:
2149:
2146:
2143:
2140:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2115:
2112:
2109:
2106:
2103:
2100:
2097:
2094:
2091:
2088:
2085:
2082:
2078:
2075:
2072:
2069:
2066:
2063:
2060:
2057:
2054:
2051:
2048:
2045:
2042:
2039:
2036:
2033:
2030:
2027:
2024:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1999:
1996:
1993:
1989:
1988:
1985:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1961:
1958:
1955:
1951:
1950:
1947:
1944:
1941:
1938:
1935:
1932:
1929:
1926:
1923:
1920:
1917:
1914:
1911:
1908:
1905:
1901:
1898:
1895:
1892:
1889:
1886:
1883:
1880:
1877:
1874:
1871:
1868:
1865:
1862:
1859:
1856:
1853:
1850:
1847:
1844:
1841:
1838:
1835:
1832:
1829:
1826:
1823:
1820:
1817:
1814:
1811:
1808:
1805:
1802:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1778:
1775:
1774:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1750:
1747:
1744:
1741:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1710:
1707:
1704:
1701:
1698:
1695:
1692:
1689:
1686:
1683:
1680:
1677:
1674:
1671:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1647:
1644:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1583:
1580:
1576:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1552:
1549:
1546:
1543:
1540:
1537:
1534:
1531:
1528:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1409:
1406:
1403:
1400:
1397:
1394:
1391:
1390:
1387:
1384:
1381:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1323:
1322:
1319:
1316:
1313:
1310:
1307:
1304:
1301:
1298:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1273:
1270:
1267:
1264:
1261:
1258:
1255:
1252:
1249:
1246:
1243:
1240:
1237:
1234:
1231:
1228:
1225:
1222:
1219:
1216:
1213:
1210:
1207:
1204:
1201:
1198:
1195:
1192:
1189:
1186:
1183:
1180:
1177:
1174:
1171:
1168:
1165:
1162:
1159:
1156:
1153:
1150:
1147:
1144:
1143:
1140:
1137:
1134:
1131:
1128:
1125:
1122:
1119:
1116:
1112:
1109:
1106:
1103:
1100:
1097:
1094:
1091:
1088:
1085:
1082:
1079:
1076:
1073:
1070:
1067:
1064:
1061:
1058:
1055:
1052:
1049:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
1019:
1016:
1013:
1010:
1007:
1004:
1001:
998:
995:
992:
989:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
942:
923:
919:
911:
907:
903:
896:
893:
890:
887:
884:
881:
878:
875:
872:
869:
866:
863:
860:
853:
849:
842:
839:
836:
833:
830:
827:
824:
821:
818:
815:
812:
809:
806:
803:
800:
797:
794:
791:
788:
785:
782:
779:
776:
773:
770:
767:
764:
761:
758:
755:
752:
749:
746:
743:
740:
737:
734:
731:
728:
725:
722:
719:
716:
713:
710:
707:
704:
701:
698:
695:
692:
689:
686:
683:
680:
677:
674:
671:
668:
665:
662:
659:
656:
653:
650:
647:
644:
641:
638:
635:
632:
613:
609:
605:
601:
597:
593:
574:
570:
566:
561:
544:
535:
531:
514:
469:
463:
457:
451:
445:
440:, as well as by
435:
308:
304:
281:
274:
270:
266:
262:
258:
254:
250:
246:
242:
238:
234:
230:
226:
207:
203:
199:
195:
191:
187:
175:
148:programmers and
116:
25:read-copy-update
21:computer science
4974:
4973:
4969:
4968:
4967:
4965:
4964:
4963:
4944:
4943:
4942:
4937:
4914:
4912:
4898:
4885:
4869:
4816:
4792:
4776:User-mode Linux
4705:
4610:
4318:
4226:
4219:
4138:
4116:
4053:
3965:
3942:
3919:
3881:
3829:
3781:
3772:Version history
3703:
3698:
3649:
3643:Journal version
3590:
3578:
3571:
3564:
3563:
3559:
3547:
3540:
3539:
3535:
3525:
3523:
3514:
3513:
3509:
3477:
3472:
3471:
3467:
3459:
3448:
3441:
3440:
3436:
3427:
3425:
3415:
3414:
3410:
3401:
3399:
3389:
3388:
3384:
3372:
3365:
3364:
3360:
3353:
3346:
3345:
3341:
3325:
3324:
3320:
3308:
3307:
3303:
3296:
3289:
3288:
3284:
3272:
3265:
3264:
3260:
3246:
3245:
3241:
3217:10.1.1.639.8357
3201:
3200:
3196:
3184:
3177:
3176:
3172:
3162:
3160:
3151:
3150:
3146:
3136:
3134:
3132:Hewlett-Packard
3125:
3124:
3120:
3108:
3101:
3100:
3096:
3086:
3084:
3075:
3074:
3070:
3058:
3051:
3050:
3046:
3036:
3034:
3025:
3024:
3020:
2998:
2997:
2993:
2978:
2954:. p. 161.
2949:
2948:
2944:
2920:10.1.1.532.5050
2904:
2903:
2899:
2878:(3): 6/1–6/52.
2868:
2867:
2863:
2832:Da Silva, Dilma
2830:
2829:
2825:
2818:
2793:
2792:
2788:
2773:
2752:
2751:
2747:
2738:
2737:
2733:
2717:
2716:
2712:
2697:
2676:
2675:
2671:
2641:
2640:
2636:
2627:
2623:
2615:
2611:
2602:
2598:
2582:
2576:cite conference
2572:
2561:
2554:
2553:
2549:
2539:
2537:
2528:
2527:
2523:
2500:
2499:
2495:
2488:
2475:
2474:
2467:
2463:
2458:
2457:
2452:
2448:
2440:
2436:
2430:
2426:
2421:
2413:Synchronization
2364:
2252:
2246:
2243:
2232:
2216:
2212:
2205:
2197:synchronize_rcu
2196:
2192:
2188:
2184:
2181:synchronize_rcu
2180:
2169:
2166:synchronize_rcu
2165:
2162:rcu_read_unlock
2161:
2157:
2154:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2080:
2079:
2076:
2073:
2070:
2067:
2064:
2061:
2058:
2055:
2052:
2049:
2046:
2043:
2040:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2013:
2010:
2007:
2004:
2001:
1997:
1995:synchronize_rcu
1994:
1991:
1990:
1986:
1983:
1980:
1977:
1974:
1971:
1968:
1965:
1962:
1959:
1956:
1953:
1952:
1948:
1945:
1942:
1939:
1936:
1933:
1930:
1927:
1924:
1921:
1918:
1915:
1912:
1909:
1906:
1903:
1902:
1899:
1896:
1893:
1890:
1887:
1884:
1881:
1878:
1875:
1872:
1869:
1866:
1863:
1860:
1857:
1854:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1800:
1797:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1606:
1602:
1600:rcu_read_unlock
1599:
1596:
1593:
1590:
1587:
1584:
1581:
1578:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1525:
1523:rcu_read_unlock
1522:
1519:
1516:
1513:
1510:
1507:
1504:
1501:
1500:
1497:
1494:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1388:
1385:
1382:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1337:
1334:
1331:
1328:
1325:
1324:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1151:
1148:
1145:
1141:
1138:
1135:
1133:DEFINE_SPINLOCK
1132:
1129:
1126:
1123:
1120:
1117:
1114:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1080:
1077:
1074:
1071:
1068:
1065:
1062:
1059:
1056:
1053:
1050:
1047:
1044:
1041:
1038:
1035:
1032:
1029:
1026:
1023:
1020:
1017:
1014:
1011:
1008:
1005:
1002:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
950:
941:synchronize_rcu
940:
934:lock contention
921:
917:
909:
906:rcu_read_unlock
905:
901:
898:
897:
894:
891:
888:
885:
882:
879:
876:
873:
870:
867:
864:
861:
858:
852:rcu_dereference
851:
847:
844:
843:
840:
837:
834:
831:
828:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
786:
783:
780:
777:
774:
771:
768:
765:
762:
759:
756:
753:
750:
747:
744:
741:
738:
735:
733:synchronize_rcu
732:
729:
726:
723:
720:
717:
714:
711:
708:
705:
702:
699:
696:
693:
690:
687:
684:
681:
678:
675:
672:
669:
666:
663:
660:
657:
655:rcu_read_unlock
654:
651:
648:
645:
642:
639:
636:
633:
630:
620:
611:
608:synchronize_rcu
607:
603:
600:synchronize_rcu
599:
596:rcu_read_unlock
595:
591:
573:rcu_dereference
572:
568:
565:rcu_dereference
564:
560:rcu_dereference
559:
542:
534:synchronize_rcu
533:
530:synchronize_rcu
529:
525:
513:synchronize_rcu
512:
483:
465:
459:
453:
447:
441:
431:
429:software patent
422:
393:
372:
311:quiescent state
307:rcu_read_unlock
306:
302:
279:
272:
268:
264:
260:
256:
252:
248:
244:
240:
236:
232:
228:
224:
220:left to right.
205:
201:
197:
193:
189:
185:
173:
166:
114:
91:
83:synchronization
49:data structures
33:synchronization
17:
12:
11:
5:
4972:
4970:
4962:
4961:
4956:
4946:
4945:
4939:
4938:
4936:
4935:
4923:
4909:
4894:
4891:
4890:
4887:
4886:
4884:
4883:
4877:
4875:
4871:
4870:
4868:
4867:
4862:
4861:
4860:
4855:
4847:
4846:
4845:
4837:
4832:
4827:
4821:
4819:
4808:
4802:
4801:
4798:
4797:
4794:
4793:
4791:
4790:
4789:
4788:
4783:
4778:
4773:
4768:
4760:
4759:
4758:
4753:
4748:
4743:
4733:
4732:
4731:
4726:
4715:
4713:
4711:Virtualization
4704:
4703:
4702:
4701:
4696:
4685:
4684:
4683:
4678:
4673:
4668:
4658:
4657:
4656:
4651:
4646:
4636:
4635:
4634:
4629:
4618:
4616:
4612:
4611:
4609:
4608:
4603:
4598:
4593:
4588:
4583:
4577:
4576:
4571:
4570:
4569:
4564:
4557:Device drivers
4553:
4552:
4547:
4542:
4537:
4532:
4527:
4522:
4512:
4511:
4506:
4501:
4499:SCHED_DEADLINE
4496:
4494:O(1) scheduler
4491:
4489:O(n) scheduler
4486:
4484:Noop scheduler
4481:
4475:
4469:
4464:
4457:
4456:
4451:
4446:
4441:
4436:
4431:
4426:
4421:
4416:
4411:
4406:
4401:
4396:
4390:
4385:
4380:
4375:
4370:
4365:
4360:
4355:
4350:
4345:
4340:
4338:Kernel modules
4334:
4332:
4328:
4327:
4324:
4323:
4320:
4319:
4317:
4316:
4311:
4306:
4301:
4296:
4291:
4286:
4285:
4284:
4279:
4274:
4269:
4264:
4259:
4258:
4257:
4247:
4242:
4231:
4229:
4221:
4220:
4218:
4217:
4212:
4211:
4210:
4200:
4195:
4190:
4187:
4184:
4179:
4176:
4173:
4168:
4163:
4158:
4153:
4148:
4144:
4142:
4128:
4122:
4121:
4118:
4117:
4115:
4114:
4109:
4104:
4099:
4094:
4092:Memory barrier
4089:
4084:
4079:
4074:
4069:
4063:
4061:
4055:
4054:
4052:
4051:
4050:
4049:
4046:
4041:
4036:
4031:
4026:
4021:
4011:
4010:
4009:
4006:
4001:
3996:
3991:
3986:
3981:
3970:
3968:
3957:
3950:
3944:
3943:
3941:
3940:
3935:
3929:
3927:
3921:
3920:
3918:
3917:
3912:
3907:
3902:
3897:
3891:
3889:
3883:
3882:
3880:
3879:
3874:
3869:
3864:
3859:
3854:
3848:
3846:
3839:
3835:
3834:
3831:
3830:
3828:
3827:
3826:
3825:
3817:
3816:
3815:
3810:
3805:
3800:
3789:
3787:
3783:
3782:
3780:
3779:
3774:
3769:
3764:
3759:
3754:
3749:
3744:
3739:
3734:
3729:
3724:
3718:
3716:
3709:
3705:
3704:
3699:
3697:
3696:
3689:
3682:
3674:
3668:
3667:
3655:
3647:
3628:
3623:
3603:
3589:
3588:External links
3586:
3577:
3576:
3557:
3533:
3507:
3488:(2): 375–382.
3465:
3462:on 2009-07-17.
3434:
3408:
3382:
3358:
3339:
3318:
3301:
3282:
3258:
3239:
3194:
3170:
3144:
3118:
3094:
3068:
3044:
3018:
2991:
2976:
2942:
2897:
2861:
2823:
2816:
2786:
2771:
2745:
2731:
2710:
2695:
2669:
2634:
2628:Eddie Kohler.
2621:
2609:
2596:
2586:|journal=
2547:
2521:
2510:(2): 221–236.
2493:
2486:
2464:
2462:
2459:
2456:
2455:
2446:
2434:
2423:
2422:
2420:
2417:
2416:
2415:
2410:
2405:
2400:
2395:
2390:
2385:
2380:
2375:
2370:
2363:
2360:
2359:
2358:
2354:
2351:
2348:
2345:
2338:
2332:
2315:
2308:
2300:
2294:
2291:IBM mainframes
2283:
2276:Richard Rashid
2273:
2266:
2254:
2253:
2219:
2217:
2210:
2204:
2201:
956:
949:
946:
857:
629:
619:
616:
577:
576:
556:
553:memory barrier
547:
546:
538:
537:
522:
521:
520:
509:
506:
482:
479:
421:
418:
392:
389:
371:
368:
355:
354:
351:
348:
345:
165:
162:
122:
121:
118:
111:
108:
105:
98:
90:
87:
15:
13:
10:
9:
6:
4:
3:
2:
4971:
4960:
4957:
4955:
4952:
4951:
4949:
4934:
4933:
4924:
4922:
4921:
4910:
4908:
4907:
4902:
4896:
4895:
4892:
4882:
4879:
4878:
4876:
4872:
4866:
4863:
4859:
4856:
4854:
4851:
4850:
4848:
4844:
4841:
4840:
4839:Thin client:
4838:
4836:
4833:
4831:
4828:
4826:
4823:
4822:
4820:
4818:
4812:
4809:
4807:
4803:
4787:
4784:
4782:
4779:
4777:
4774:
4772:
4769:
4767:
4764:
4763:
4761:
4757:
4754:
4752:
4749:
4747:
4744:
4742:
4741:Linux-VServer
4739:
4738:
4737:
4734:
4730:
4727:
4725:
4722:
4721:
4720:
4717:
4716:
4714:
4712:
4708:
4700:
4697:
4695:
4692:
4691:
4689:
4686:
4682:
4679:
4677:
4674:
4672:
4669:
4667:
4664:
4663:
4662:
4659:
4655:
4652:
4650:
4647:
4645:
4642:
4641:
4640:
4637:
4633:
4630:
4628:
4625:
4624:
4623:
4620:
4619:
4617:
4613:
4607:
4604:
4602:
4599:
4597:
4594:
4592:
4589:
4587:
4584:
4582:
4579:
4578:
4575:
4572:
4568:
4565:
4563:
4560:
4559:
4558:
4555:
4554:
4551:
4548:
4546:
4543:
4541:
4538:
4536:
4533:
4531:
4528:
4526:
4523:
4521:
4517:
4514:
4513:
4510:
4507:
4505:
4502:
4500:
4497:
4495:
4492:
4490:
4487:
4485:
4482:
4479:
4476:
4473:
4470:
4468:
4465:
4462:
4459:
4458:
4455:
4452:
4450:
4447:
4445:
4442:
4440:
4437:
4435:
4432:
4430:
4427:
4425:
4422:
4420:
4417:
4415:
4412:
4410:
4407:
4405:
4402:
4400:
4397:
4394:
4391:
4389:
4386:
4384:
4381:
4379:
4376:
4374:
4371:
4369:
4366:
4364:
4363:Device mapper
4361:
4359:
4356:
4354:
4351:
4349:
4346:
4344:
4341:
4339:
4336:
4335:
4333:
4329:
4315:
4312:
4310:
4307:
4305:
4302:
4300:
4297:
4295:
4292:
4290:
4287:
4283:
4280:
4278:
4275:
4273:
4270:
4268:
4265:
4263:
4260:
4256:
4253:
4252:
4251:
4248:
4246:
4243:
4241:
4238:
4237:
4236:
4233:
4232:
4230:
4228:
4222:
4216:
4213:
4209:
4206:
4205:
4204:
4201:
4199:
4196:
4194:
4191:
4188:
4185:
4183:
4180:
4177:
4174:
4172:
4169:
4167:
4164:
4162:
4159:
4157:
4154:
4152:
4149:
4146:
4145:
4143:
4141:
4136:
4132:
4129:
4127:
4123:
4113:
4110:
4108:
4105:
4103:
4100:
4098:
4095:
4093:
4090:
4088:
4085:
4083:
4080:
4078:
4075:
4073:
4070:
4068:
4065:
4064:
4062:
4060:
4056:
4047:
4045:
4042:
4040:
4037:
4035:
4032:
4030:
4027:
4025:
4022:
4020:
4017:
4016:
4015:
4012:
4007:
4005:
4002:
4000:
3997:
3995:
3992:
3990:
3987:
3985:
3982:
3980:
3977:
3976:
3975:
3972:
3971:
3969:
3967:
3961:
3958:
3954:
3951:
3949:
3945:
3939:
3936:
3934:
3931:
3930:
3928:
3926:
3922:
3916:
3913:
3911:
3908:
3906:
3903:
3901:
3898:
3896:
3893:
3892:
3890:
3888:
3884:
3878:
3875:
3873:
3870:
3868:
3865:
3863:
3860:
3858:
3855:
3853:
3850:
3849:
3847:
3843:
3840:
3836:
3824:
3821:
3820:
3818:
3814:
3811:
3809:
3806:
3804:
3801:
3799:
3798:
3794:
3793:
3791:
3790:
3788:
3784:
3778:
3775:
3773:
3770:
3768:
3765:
3763:
3760:
3758:
3755:
3753:
3750:
3748:
3745:
3743:
3740:
3738:
3735:
3733:
3730:
3728:
3725:
3723:
3720:
3719:
3717:
3713:
3710:
3706:
3702:
3695:
3690:
3688:
3683:
3681:
3676:
3675:
3672:
3666:
3664:
3659:
3656:
3652:
3648:
3645:
3644:
3639:
3635:
3634:
3629:
3627:
3624:
3622:
3620:
3615:
3611:
3607:
3604:
3602:
3600:
3595:
3592:
3591:
3587:
3585:
3583:
3567:
3561:
3558:
3553:
3546:
3545:
3537:
3534:
3522:
3518:
3511:
3508:
3503:
3499:
3495:
3491:
3487:
3483:
3476:
3469:
3466:
3458:
3454:
3447:
3446:
3438:
3435:
3424:on 2012-03-31
3423:
3419:
3412:
3409:
3398:on 2012-03-31
3397:
3393:
3386:
3383:
3378:
3371:
3370:
3362:
3359:
3349:
3343:
3340:
3335:
3331:
3330:
3322:
3319:
3314:
3313:
3305:
3302:
3292:
3286:
3283:
3278:
3271:
3270:
3262:
3259:
3254:
3250:
3243:
3240:
3235:
3231:
3227:
3223:
3218:
3213:
3209:
3205:
3198:
3195:
3190:
3183:
3182:
3174:
3171:
3163:September 24,
3159:
3158:Linux Journal
3155:
3148:
3145:
3133:
3129:
3122:
3119:
3114:
3107:
3106:
3098:
3095:
3087:September 24,
3083:
3079:
3072:
3069:
3064:
3057:
3056:
3048:
3045:
3037:September 24,
3033:
3029:
3022:
3019:
3014:
3010:
3006:
3002:
2995:
2992:
2987:
2983:
2979:
2973:
2969:
2965:
2961:
2957:
2953:
2946:
2943:
2938:
2934:
2930:
2926:
2921:
2916:
2912:
2908:
2901:
2898:
2893:
2889:
2885:
2881:
2877:
2873:
2865:
2862:
2857:
2853:
2849:
2845:
2841:
2837:
2833:
2827:
2824:
2819:
2813:
2809:
2805:
2801:
2797:
2790:
2787:
2782:
2778:
2774:
2768:
2764:
2760:
2756:
2749:
2746:
2741:
2735:
2732:
2727:
2723:
2722:
2714:
2711:
2706:
2702:
2698:
2692:
2688:
2684:
2680:
2673:
2670:
2665:
2661:
2657:
2653:
2649:
2645:
2638:
2635:
2631:
2625:
2622:
2618:
2613:
2610:
2606:
2600:
2597:
2592:
2577:
2569:
2568:
2560:
2559:
2551:
2548:
2540:September 24,
2536:
2532:
2525:
2522:
2517:
2513:
2509:
2505:
2497:
2494:
2489:
2487:9781292061429
2483:
2479:
2472:
2470:
2466:
2460:
2450:
2447:
2443:
2438:
2435:
2428:
2425:
2418:
2414:
2411:
2409:
2406:
2404:
2401:
2399:
2396:
2394:
2391:
2389:
2386:
2384:
2381:
2379:
2376:
2374:
2373:Copy-on-write
2371:
2369:
2366:
2365:
2361:
2355:
2352:
2349:
2346:
2343:
2339:
2336:
2335:Rusty Russell
2333:
2330:
2327:
2323:
2320:
2316:
2313:
2309:
2306:
2301:
2298:
2295:
2292:
2288:
2284:
2281:
2277:
2274:
2270:
2267:
2264:
2261:
2260:
2259:
2250:
2241:is available.
2240:
2236:
2230:
2229:
2225:
2220:This section
2218:
2209:
2208:
2202:
2200:
2177:
2173:
2168:precedes the
2158:rcu_read_lock
1318:rcu_read_lock
1118:DEFINE_RWLOCK
954:
947:
945:
937:
935:
931:
927:
922:rcu_read_lock
918:ACCESS_ONCE()
915:
902:rcu_read_lock
855:
634:rcu_read_lock
627:
625:
617:
615:
592:rcu_read_lock
588:
581:
557:
554:
549:
548:
540:
539:
527:
526:
518:
510:
507:
504:
503:
502:
500:
494:
492:
488:
480:
478:
476:
473:
468:
462:
456:
450:
444:
439:
434:
430:
427:
419:
417:
414:
410:
408:
404:
399:
390:
388:
386:
385:Dragonfly BSD
382:
378:
369:
367:
364:
359:
352:
349:
346:
343:
342:
341:
338:
334:
332:
327:
323:
318:
316:
312:
303:rcu_read_lock
300:
295:
291:
289:
285:
276:
221:
213:
209:
182:
170:
163:
161:
160:programmers.
159:
155:
151:
147:
143:
139:
135:
131:
127:
119:
112:
109:
106:
103:
99:
96:
95:
94:
88:
86:
84:
80:
75:
73:
72:null pointers
69:
68:shared memory
64:
62:
58:
54:
50:
46:
42:
38:
34:
30:
26:
22:
4930:
4911:
4897:
4627:Linux kernel
4545:Tomoyo Linux
4140:File systems
4101:
3795:
3747:SCO disputes
3708:Organization
3701:Linux kernel
3661:
3641:
3631:
3617:
3597:
3579:
3560:
3551:
3543:
3536:
3526:November 17,
3524:. Retrieved
3510:
3485:
3481:
3468:
3457:the original
3452:
3444:
3437:
3426:. Retrieved
3422:the original
3411:
3400:. Retrieved
3396:the original
3385:
3376:
3368:
3361:
3342:
3333:
3328:
3321:
3311:
3304:
3285:
3276:
3268:
3261:
3252:
3248:
3242:
3207:
3203:
3197:
3188:
3180:
3173:
3161:. Retrieved
3147:
3137:December 26,
3135:. Retrieved
3121:
3112:
3104:
3097:
3085:. Retrieved
3071:
3062:
3054:
3047:
3035:. Retrieved
3021:
3004:
3000:
2994:
2951:
2945:
2913:(2): 34–42.
2910:
2906:
2900:
2875:
2871:
2864:
2842:(2): 34–42.
2839:
2835:
2826:
2799:
2795:
2789:
2754:
2748:
2734:
2725:
2720:
2713:
2678:
2672:
2647:
2643:
2637:
2624:
2612:
2599:
2565:
2557:
2550:
2538:. Retrieved
2524:
2507:
2503:
2496:
2477:
2449:
2437:
2427:
2326:IBM Research
2305:Van Jacobson
2297:William Pugh
2257:
2244:
2239:Editing help
2221:
2195:in place of
2178:
2174:
2155:
2084:write_unlock
1957:write_unlock
1931:list_del_rcu
951:
938:
899:
845:
621:
589:
586:
516:
495:
487:Linux kernel
484:
423:
415:
411:
409:conditions.
394:
373:
360:
356:
339:
335:
330:
325:
321:
319:
315:grace period
314:
310:
298:
296:
292:
288:transactions
277:
237:list_del_rcu
222:
218:
183:
179:
149:
141:
137:
133:
129:
125:
123:
92:
76:
65:
53:linked lists
28:
24:
18:
4632:Linux-libre
4525:Exec Shield
4404:Framebuffer
4107:Video4Linux
3964:System Call
3792:Developers
3732:Linus's law
2650:(5): 4–17.
2102:spin_unlock
1975:spin_unlock
1582:read_unlock
1505:read_unlock
892:(_value); \
862:smp_wmb();
326:reclamation
255:or element
150:generations
61:hash tables
4948:Categories
4719:Hypervisor
4681:PREEMPT_RT
4586:KernelCare
4574:Raw device
4504:SCHED_FIFO
4414:KMS driver
4331:Components
4186:securityfs
4072:Crypto API
4014:Linux-only
3900:System.map
3803:kernel.org
3762:menuconfig
3757:GNU GPL v2
3566:US 7099932
3428:2010-10-01
3402:2010-10-01
3348:US 5442758
3291:US 4809168
3210:(3): 354.
2461:References
2269:Udi Manber
2263:H. T. Kung
1743:write_lock
1057:spinlock_t
1045:spinlock_t
900:Note that
472:SCO v. IBM
4858:LYME-LYCE
4581:initramfs
4550:Linux PAM
4419:Netfilter
4289:libcgroup
4255:libhybris
4227:libraries
4175:hugetlbfs
4126:Userspace
4059:In-kernel
4044:readahead
3966:Interface
3915:initramfs
3872:SystemTap
3845:Debugging
3838:Technical
3777:Criticism
3212:CiteSeerX
3191:(Thesis).
3065:(Thesis).
2915:CiteSeerX
2312:DYNIX/ptx
2111:listmutex
2093:listmutex
1984:listmutex
1966:listmutex
1770:listmutex
1761:spin_lock
1752:listmutex
1591:listmutex
1514:listmutex
1309:listmutex
1300:read_lock
1164:LIST_HEAD
1149:LIST_HEAD
1139:listmutex
1124:listmutex
1009:list_head
994:list_head
961:/* RCU */
914:DEC Alpha
4932:Category
4874:Adopters
4849:Server:
4830:Embedded
4806:Adoption
4699:PSXLinux
4622:Mainline
4615:Variants
4567:graphics
4520:AppArmor
4509:SCHED_RR
4429:nftables
4373:dm-crypt
4368:dm-cache
4314:liburing
4304:libevdev
4262:dietlibc
4151:configfs
4077:io uring
3234:13007648
2705:17493674
2664:12748421
2362:See also
2272:threads.
2247:May 2014
2189:call_rcu
1907:list_del
926:deadlock
823:callback
811:call_rcu
772:each_cpu
691:callback
676:call_rcu
612:call_rcu
604:call_rcu
543:call_rcu
407:livelock
403:deadlock
142:MP defer
45:pointers
4865:Devices
4825:Desktop
4786:coLinux
4781:MkLinux
4766:L4Linux
4694:ÎĽClinux
4676:Xenomai
4666:RTLinux
4606:Ksplice
4535:SELinux
4530:seccomp
4480:(EEVDF)
4424:Netlink
4353:Console
4348:cgroups
4299:libalsa
4225:Wrapper
4203:systemd
4166:debugfs
4135:Daemons
4097:New API
4039:inotify
4034:dnotify
3938:x32 ABI
3895:vmlinux
3887:Startup
3786:Support
2937:3030814
2781:2465311
2203:History
491:liburcu
475:lawsuit
420:Patents
331:reclaim
322:removal
284:locking
158:Tornado
130:copying
102:pointer
51:(e.g.,
41:threads
31:) is a
4835:Gaming
4817:of use
4771:ELinOS
4762:Other
4756:OpenVZ
4746:Lguest
4690:-less
4601:kpatch
4596:kGraft
4562:802.11
4358:bcache
4309:libusb
4294:libdrm
4282:Newlib
4267:EGLIBC
4250:Bionic
4245:uClibc
4215:Kmscon
4189:sockfs
4182:procfs
4178:pipefs
4161:devpts
4087:kernfs
4029:splice
3984:select
3956:Kernel
3910:initrd
3905:dracut
3857:ftrace
3819:Users
3752:Linaro
3715:Kernel
3612:, and
3572:
3502:832767
3500:
3354:
3297:
3232:
3214:
2984:
2974:
2935:
2917:
2892:931202
2890:
2856:669053
2854:
2814:
2779:
2769:
2703:
2693:
2662:
2484:
2432:phase.
2222:is in
2185:delete
2133:return
2121:return
2047:return
2035:return
1718:struct
1700:struct
1670:delete
1649:delete
1622:return
1610:return
1545:return
1533:return
1483:result
1459:result
1275:struct
1257:struct
1236:result
1215:search
1203:result
1182:search
1006:struct
991:struct
979:struct
967:struct
602:, and
528:Since
231:, and
134:update
4815:Range
4654:SLURM
4591:kexec
4540:Smack
4474:(CFS)
4454:zswap
4395:(KSM)
4388:evdev
4343:BlueZ
4272:klibc
4240:glibc
4198:tmpfs
4193:sysfs
4156:devfs
4147:bpffs
4024:epoll
4019:futex
3999:close
3979:ioctl
3974:POSIX
3862:kdump
3548:(PDF)
3498:S2CID
3478:(PDF)
3460:(PDF)
3449:(PDF)
3373:(PDF)
3273:(PDF)
3230:S2CID
3185:(PDF)
3109:(PDF)
3059:(PDF)
2986:28504
2982:S2CID
2933:S2CID
2888:S2CID
2852:S2CID
2777:S2CID
2701:S2CID
2660:S2CID
2562:(PDF)
2419:Notes
2287:VM/XA
2228:prose
2170:kfree
2108:&
2090:&
2020:kfree
2005:kfree
1981:&
1963:&
1943:->
1937:&
1919:->
1913:&
1885:->
1855:->
1825:&
1792:&
1767:&
1749:&
1588:&
1511:&
1492:->
1468:->
1435:->
1405:->
1374:&
1341:&
1306:&
1060:mutex
1048:mutex
832:->
829:entry
820:->
817:entry
802:entry
757:ncpus
515:will
146:VM/XA
57:trees
4853:LAMP
4843:LTSP
4671:RTAI
4449:zram
4444:SLUB
4439:perf
4383:EDAC
4277:musl
4208:udev
4171:FUSE
4067:ALSA
4004:sync
3994:read
3989:open
3948:APIs
3925:ABIs
3852:CRIU
3808:LKML
3528:2013
3255:(3).
3165:2010
3139:2010
3089:2010
3039:2010
2972:ISBN
2812:ISBN
2767:ISBN
2691:ISBN
2591:help
2542:2010
2482:ISBN
2224:list
2160:and
1828:head
1795:head
1676:long
1655:long
1495:data
1471:data
1377:head
1344:head
1221:long
1188:long
1170:head
1155:head
1084:data
1072:data
1033:long
1021:long
904:and
850:and
814:list
799:each
739:void
730:void
709:void
700:void
682:void
673:void
661:void
652:void
640:void
631:void
426:U.S.
405:and
370:Uses
324:and
305:and
202:NULL
194:gptr
190:NULL
186:gptr
174:gptr
156:and
140:and
126:read
37:lock
4751:LXC
4729:Xen
4724:KVM
4688:MMU
4644:INK
4409:LVM
4399:LIO
4378:DRM
4112:IIO
4102:RCU
4082:DRM
3877:BPF
3742:Tux
3636:An
3490:doi
3222:doi
3009:doi
2964:hdl
2956:doi
2925:doi
2880:doi
2844:doi
2804:doi
2759:doi
2683:doi
2652:doi
2512:doi
2329:K42
2289:on
1998:();
1894:key
1888:key
1864:key
1858:key
1679:key
1667:int
1658:key
1646:int
1603:();
1526:();
1444:key
1438:key
1414:key
1408:key
1321:();
1230:int
1224:key
1212:int
1197:int
1191:key
1179:int
1081:int
1069:int
1036:key
1024:key
835:arg
808:the
796:for
790:cpu
778:cpu
769:for
751:cpu
748:int
715:arg
517:not
398:SMP
377:K42
286:or
154:K42
152:by
144:by
74:).
63:).
29:RCU
19:In
4950::
4518::
3660:.
3616:.
3608:,
3596:.
3584:)
3550:.
3519:.
3496:.
3486:23
3484:.
3480:.
3451:.
3375:.
3332:.
3275:.
3251:.
3228:.
3220:.
3206:.
3187:.
3156:.
3130:.
3111:.
3080:.
3061:.
3030:.
3005:67
3003:.
2980:.
2970:.
2962:.
2931:.
2923:.
2911:25
2909:.
2886:.
2876:25
2874:.
2850:.
2840:40
2838:.
2810:.
2798:.
2775:.
2765:.
2724:.
2699:.
2689:.
2658:.
2648:42
2646:.
2580::
2578:}}
2574:{{
2564:.
2533:.
2508:47
2506:.
2468:^
2172:.
2148:17
2142:16
2130:16
2118:15
2114:);
2099:15
2096:);
2081:14
2074:14
2068:13
2062:13
2056:12
2044:12
2032:11
2029:);
2017:11
2014:);
2002:10
1992:10
1987:);
1969:);
1949:);
1946:lp
1925:);
1922:lp
1891:==
1876:if
1861:==
1846:if
1834:lp
1801:lp
1773:);
1755:);
1721:el
1703:el
1637:15
1631:15
1619:14
1607:14
1597:13
1594:);
1579:13
1572:12
1566:12
1560:11
1554:11
1542:10
1530:10
1517:);
1441:==
1426:if
1411:==
1396:if
1383:lp
1350:lp
1312:);
1278:el
1260:el
1173:);
1158:);
1142:);
1127:);
1111:};
1105:};
1012:lp
997:lp
982:el
970:el
895:})
874:})
838:);
805:in
793:);
706:),
626:.
598:,
594:,
477:.
227:,
59:,
55:,
23:,
4463::
4137:,
4048:…
4008:…
3693:e
3686:t
3679:v
3665:.
3621:.
3601:.
3554:.
3530:.
3504:.
3492::
3431:.
3405:.
3379:.
3336:.
3253:9
3236:.
3224::
3208:5
3167:.
3141:.
3115:.
3091:.
3041:.
3015:.
3011::
2988:.
2966::
2958::
2939:.
2927::
2894:.
2882::
2858:.
2846::
2820:.
2806::
2783:.
2761::
2742:.
2728:.
2707:.
2685::
2666:.
2654::
2619:.
2607:.
2593:)
2589:(
2544:.
2518:.
2514::
2490:.
2293:.
2249:)
2245:(
2231:.
2151:}
2145:}
2139:;
2136:0
2127:;
2124:0
2105:(
2087:(
2077:}
2071:}
2065:}
2059:}
2053:;
2050:1
2041:;
2038:1
2026:p
2023:(
2011:p
2008:(
1978:(
1972:9
1960:(
1954:9
1940:p
1934:(
1928:8
1916:p
1910:(
1904:8
1900:{
1897:)
1882:p
1879:(
1873:7
1870:{
1867:)
1852:p
1849:(
1843:7
1840:{
1837:)
1831:,
1822:,
1819:p
1816:(
1810:6
1807:{
1804:)
1798:,
1789:,
1786:p
1783:(
1777:6
1764:(
1758:5
1746:(
1740:5
1736:4
1733:4
1730:;
1727:p
1724:*
1715:3
1712:;
1709:p
1706:*
1697:3
1694:{
1691:2
1688:{
1685:2
1682:)
1673:(
1664:1
1661:)
1652:(
1643:1
1640:}
1634:}
1628:;
1625:0
1616:;
1613:0
1585:(
1575:}
1569:}
1563:}
1557:}
1551:;
1548:1
1539:;
1536:1
1520:9
1508:(
1502:9
1498:;
1489:p
1486:=
1480:*
1477:8
1474:;
1465:p
1462:=
1456:*
1453:8
1450:{
1447:)
1432:p
1429:(
1423:7
1420:{
1417:)
1402:p
1399:(
1393:7
1389:{
1386:)
1380:,
1371:,
1368:p
1365:(
1359:6
1356:{
1353:)
1347:,
1338:,
1335:p
1332:(
1326:6
1315:5
1303:(
1297:5
1293:4
1290:4
1287:;
1284:p
1281:*
1272:3
1269:;
1266:p
1263:*
1254:3
1251:{
1248:2
1245:{
1242:2
1239:)
1233:*
1227:,
1218:(
1209:1
1206:)
1200:*
1194:,
1185:(
1176:1
1167:(
1161:9
1152:(
1146:9
1136:(
1130:8
1121:(
1115:8
1108:7
1102:7
1096:6
1090:6
1087:;
1078:5
1075:;
1066:5
1063:;
1054:4
1051:;
1042:4
1039:;
1030:3
1027:;
1018:3
1015:;
1003:2
1000:;
988:2
985:{
976:1
973:{
964:1
889:\
868:\
841:}
826:(
787:(
781:)
775:(
766:;
763:0
760:=
754:,
745:{
742:)
736:(
727:}
721:{
718:)
712:*
703:*
697:(
694:)
688:*
685:(
679:(
670:}
667:{
664:)
658:(
649:}
646:{
643:)
637:(
497:(
280:B
273:B
269:B
265:B
261:B
257:C
253:B
249:A
245:B
241:B
233:C
229:B
225:A
117:,
27:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
