Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | RCU Concepts |
| 2 | |
| 3 | |
| 4 | The basic idea behind RCU (read-copy update) is to split destructive |
| 5 | operations into two parts, one that prevents anyone from seeing the data |
| 6 | item being destroyed, and one that actually carries out the destruction. |
| 7 | A "grace period" must elapse between the two parts, and this grace period |
| 8 | must be long enough that any readers accessing the item being deleted have |
| 9 | since dropped their references. For example, an RCU-protected deletion |
| 10 | from a linked list would first remove the item from the list, wait for |
| 11 | a grace period to elapse, then free the element. See the listRCU.txt |
| 12 | file for more information on using RCU with linked lists. |
| 13 | |
| 14 | |
| 15 | Frequently Asked Questions |
| 16 | |
| 17 | o Why would anyone want to use RCU? |
| 18 | |
| 19 | The advantage of RCU's two-part approach is that RCU readers need |
| 20 | not acquire any locks, perform any atomic instructions, write to |
| 21 | shared memory, or (on CPUs other than Alpha) execute any memory |
| 22 | barriers. The fact that these operations are quite expensive |
| 23 | on modern CPUs is what gives RCU its performance advantages |
| 24 | in read-mostly situations. The fact that RCU readers need not |
| 25 | acquire locks can also greatly simplify deadlock-avoidance code. |
| 26 | |
| 27 | o How can the updater tell when a grace period has completed |
| 28 | if the RCU readers give no indication when they are done? |
| 29 | |
| 30 | Just as with spinlocks, RCU readers are not permitted to |
| 31 | block, switch to user-mode execution, or enter the idle loop. |
| 32 | Therefore, as soon as a CPU is seen passing through any of these |
| 33 | three states, we know that that CPU has exited any previous RCU |
| 34 | read-side critical sections. So, if we remove an item from a |
| 35 | linked list, and then wait until all CPUs have switched context, |
| 36 | executed in user mode, or executed in the idle loop, we can |
| 37 | safely free up that item. |
| 38 | |
| 39 | o If I am running on a uniprocessor kernel, which can only do one |
| 40 | thing at a time, why should I wait for a grace period? |
| 41 | |
| 42 | See the UP.txt file in this directory. |
| 43 | |
| 44 | o How can I see where RCU is currently used in the Linux kernel? |
| 45 | |
Paul E. McKenney | a83f1fe | 2005-05-01 08:59:05 -0700 | [diff] [blame] | 46 | Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu", |
| 47 | "rcu_read_lock_bh", "rcu_read_unlock_bh", "call_rcu_bh", |
| 48 | "synchronize_rcu", and "synchronize_net". |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 49 | |
| 50 | o What guidelines should I follow when writing code that uses RCU? |
| 51 | |
| 52 | See the checklist.txt file in this directory. |
| 53 | |
| 54 | o Why the name "RCU"? |
| 55 | |
| 56 | "RCU" stands for "read-copy update". The file listRCU.txt has |
| 57 | more information on where this name came from, search for |
| 58 | "read-copy update" to find it. |
| 59 | |
| 60 | o I hear that RCU is patented? What is with that? |
| 61 | |
| 62 | Yes, it is. There are several known patents related to RCU, |
| 63 | search for the string "Patent" in RTFP.txt to find them. |
| 64 | Of these, one was allowed to lapse by the assignee, and the |
| 65 | others have been contributed to the Linux kernel under GPL. |
| 66 | |
Paul E. McKenney | dd81eca | 2005-09-10 00:26:24 -0700 | [diff] [blame] | 67 | o I hear that RCU needs work in order to support realtime kernels? |
| 68 | |
| 69 | Yes, work in progress. |
| 70 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 71 | o Where can I find more information on RCU? |
| 72 | |
| 73 | See the RTFP.txt file in this directory. |
Paul E. McKenney | dd81eca | 2005-09-10 00:26:24 -0700 | [diff] [blame] | 74 | Or point your browser at http://www.rdrop.com/users/paulmck/RCU/. |
| 75 | |
| 76 | o What are all these files in this directory? |
| 77 | |
| 78 | |
| 79 | NMI-RCU.txt |
| 80 | |
| 81 | Describes how to use RCU to implement dynamic |
| 82 | NMI handlers, which can be revectored on the fly, |
| 83 | without rebooting. |
| 84 | |
| 85 | RTFP.txt |
| 86 | |
| 87 | List of RCU-related publications and web sites. |
| 88 | |
| 89 | UP.txt |
| 90 | |
| 91 | Discussion of RCU usage in UP kernels. |
| 92 | |
| 93 | arrayRCU.txt |
| 94 | |
| 95 | Describes how to use RCU to protect arrays, with |
| 96 | resizeable arrays whose elements reference other |
| 97 | data structures being of the most interest. |
| 98 | |
| 99 | checklist.txt |
| 100 | |
| 101 | Lists things to check for when inspecting code that |
| 102 | uses RCU. |
| 103 | |
| 104 | listRCU.txt |
| 105 | |
| 106 | Describes how to use RCU to protect linked lists. |
| 107 | This is the simplest and most common use of RCU |
| 108 | in the Linux kernel. |
| 109 | |
| 110 | rcu.txt |
| 111 | |
| 112 | You are reading it! |
| 113 | |
| 114 | whatisRCU.txt |
| 115 | |
| 116 | Overview of how the RCU implementation works. Along |
| 117 | the way, presents a conceptual view of RCU. |