1f93a3e4eSJiunn Chang.. _rcu_doc: 2f93a3e4eSJiunn Chang 3f93a3e4eSJiunn ChangRCU Concepts 4f93a3e4eSJiunn Chang============ 5f93a3e4eSJiunn Chang 6f93a3e4eSJiunn ChangThe basic idea behind RCU (read-copy update) is to split destructive 7f93a3e4eSJiunn Changoperations into two parts, one that prevents anyone from seeing the data 8f93a3e4eSJiunn Changitem being destroyed, and one that actually carries out the destruction. 9f93a3e4eSJiunn ChangA "grace period" must elapse between the two parts, and this grace period 10f93a3e4eSJiunn Changmust be long enough that any readers accessing the item being deleted have 11f93a3e4eSJiunn Changsince dropped their references. For example, an RCU-protected deletion 12f93a3e4eSJiunn Changfrom a linked list would first remove the item from the list, wait for 13404147faSAkira Yokosawaa grace period to elapse, then free the element. See listRCU.rst for more 14404147faSAkira Yokosawainformation on using RCU with linked lists. 15f93a3e4eSJiunn Chang 16f93a3e4eSJiunn ChangFrequently Asked Questions 17f93a3e4eSJiunn Chang-------------------------- 18f93a3e4eSJiunn Chang 19f93a3e4eSJiunn Chang- Why would anyone want to use RCU? 20f93a3e4eSJiunn Chang 21f93a3e4eSJiunn Chang The advantage of RCU's two-part approach is that RCU readers need 22f93a3e4eSJiunn Chang not acquire any locks, perform any atomic instructions, write to 23f93a3e4eSJiunn Chang shared memory, or (on CPUs other than Alpha) execute any memory 24f93a3e4eSJiunn Chang barriers. The fact that these operations are quite expensive 25f93a3e4eSJiunn Chang on modern CPUs is what gives RCU its performance advantages 26f93a3e4eSJiunn Chang in read-mostly situations. The fact that RCU readers need not 27f93a3e4eSJiunn Chang acquire locks can also greatly simplify deadlock-avoidance code. 28f93a3e4eSJiunn Chang 29f93a3e4eSJiunn Chang- How can the updater tell when a grace period has completed 30f93a3e4eSJiunn Chang if the RCU readers give no indication when they are done? 31f93a3e4eSJiunn Chang 32f93a3e4eSJiunn Chang Just as with spinlocks, RCU readers are not permitted to 33f93a3e4eSJiunn Chang block, switch to user-mode execution, or enter the idle loop. 34f93a3e4eSJiunn Chang Therefore, as soon as a CPU is seen passing through any of these 35f93a3e4eSJiunn Chang three states, we know that that CPU has exited any previous RCU 36f93a3e4eSJiunn Chang read-side critical sections. So, if we remove an item from a 37f93a3e4eSJiunn Chang linked list, and then wait until all CPUs have switched context, 38f93a3e4eSJiunn Chang executed in user mode, or executed in the idle loop, we can 39f93a3e4eSJiunn Chang safely free up that item. 40f93a3e4eSJiunn Chang 41f93a3e4eSJiunn Chang Preemptible variants of RCU (CONFIG_PREEMPT_RCU) get the 42f93a3e4eSJiunn Chang same effect, but require that the readers manipulate CPU-local 43f93a3e4eSJiunn Chang counters. These counters allow limited types of blocking within 44f93a3e4eSJiunn Chang RCU read-side critical sections. SRCU also uses CPU-local 45f93a3e4eSJiunn Chang counters, and permits general blocking within RCU read-side 46f93a3e4eSJiunn Chang critical sections. These variants of RCU detect grace periods 47f93a3e4eSJiunn Chang by sampling these counters. 48f93a3e4eSJiunn Chang 49f93a3e4eSJiunn Chang- If I am running on a uniprocessor kernel, which can only do one 50f93a3e4eSJiunn Chang thing at a time, why should I wait for a grace period? 51f93a3e4eSJiunn Chang 52404147faSAkira Yokosawa See UP.rst for more information. 53f93a3e4eSJiunn Chang 54f93a3e4eSJiunn Chang- How can I see where RCU is currently used in the Linux kernel? 55f93a3e4eSJiunn Chang 56f93a3e4eSJiunn Chang Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu", 57f93a3e4eSJiunn Chang "rcu_read_lock_bh", "rcu_read_unlock_bh", "srcu_read_lock", 58f93a3e4eSJiunn Chang "srcu_read_unlock", "synchronize_rcu", "synchronize_net", 59f93a3e4eSJiunn Chang "synchronize_srcu", and the other RCU primitives. Or grab one 60f93a3e4eSJiunn Chang of the cscope databases from: 61f93a3e4eSJiunn Chang 62f93a3e4eSJiunn Chang (http://www.rdrop.com/users/paulmck/RCU/linuxusage/rculocktab.html). 63f93a3e4eSJiunn Chang 64f93a3e4eSJiunn Chang- What guidelines should I follow when writing code that uses RCU? 65f93a3e4eSJiunn Chang 66404147faSAkira Yokosawa See checklist.rst. 67f93a3e4eSJiunn Chang 68f93a3e4eSJiunn Chang- Why the name "RCU"? 69f93a3e4eSJiunn Chang 70be289568SSeongJae Park "RCU" stands for "read-copy update". 71404147faSAkira Yokosawa listRCU.rst has more information on where this name came from, search 72404147faSAkira Yokosawa for "read-copy update" to find it. 73f93a3e4eSJiunn Chang 74f93a3e4eSJiunn Chang- I hear that RCU is patented? What is with that? 75f93a3e4eSJiunn Chang 76f93a3e4eSJiunn Chang Yes, it is. There are several known patents related to RCU, 776a534b29SSeongJae Park search for the string "Patent" in Documentation/RCU/RTFP.txt to find them. 78f93a3e4eSJiunn Chang Of these, one was allowed to lapse by the assignee, and the 79f93a3e4eSJiunn Chang others have been contributed to the Linux kernel under GPL. 80647dd4cdSPaul E. McKenney Many (but not all) have long since expired. 81f93a3e4eSJiunn Chang There are now also LGPL implementations of user-level RCU 8206a649b3SSeongJae Park available (https://liburcu.org/). 83f93a3e4eSJiunn Chang 84f93a3e4eSJiunn Chang- I hear that RCU needs work in order to support realtime kernels? 85f93a3e4eSJiunn Chang 86647dd4cdSPaul E. McKenney Realtime-friendly RCU are enabled via the CONFIG_PREEMPTION 87f93a3e4eSJiunn Chang kernel configuration parameter. 88f93a3e4eSJiunn Chang 89f93a3e4eSJiunn Chang- Where can I find more information on RCU? 90f93a3e4eSJiunn Chang 916a534b29SSeongJae Park See the Documentation/RCU/RTFP.txt file. 92*3f58c55eSPaul E. McKenney Or point your browser at (https://docs.google.com/document/d/1X0lThx8OK0ZgLMqVoXiR4ZrGURHrXK6NyLRbeXe3Xac/edit) 93*3f58c55eSPaul E. McKenney or (https://docs.google.com/document/d/1GCdQC8SDbb54W1shjEXqGZ0Rq8a6kIeYutdSIajfpLA/edit?usp=sharing). 94