+Please note that the "What is RCU?" LWN series is an excellent place
+to start learning about RCU:
+
+1. What is RCU, Fundamentally? http://lwn.net/Articles/262464/
+2. What is RCU? Part 2: Usage http://lwn.net/Articles/263130/
+3. RCU part 3: the RCU API http://lwn.net/Articles/264090/
+
+
What is RCU?
RCU is a synchronization mechanism that was added to the Linux kernel
blocking, it registers a function and argument which are invoked
after all ongoing RCU read-side critical sections have completed.
This callback variant is particularly useful in situations where
- it is illegal to block.
+ it is illegal to block or where update-side performance is
+ critically important.
+
+ However, the call_rcu() API should not be used lightly, as use
+ of the synchronize_rcu() API generally results in simpler code.
+ In addition, the synchronize_rcu() API has the nice property
+ of automatically limiting update rate should grace periods
+ be delayed. This property results in system resilience in face
+ of denial-of-service attacks. Code using call_rcu() should limit
+ update rate in order to gain this same sort of resilience. See
+ checklist.txt for some approaches to limiting the update rate.
rcu_assign_pointer()
the new value, and also executes any memory-barrier instructions
required for a given CPU architecture.
- Perhaps more important, it serves to document which pointers
- are protected by RCU. That said, rcu_assign_pointer() is most
- frequently used indirectly, via the _rcu list-manipulation
- primitives such as list_add_rcu().
+ Perhaps just as important, it serves to document (1) which
+ pointers are protected by RCU and (2) the point at which a
+ given structure becomes accessible to other CPUs. That said,
+ rcu_assign_pointer() is most frequently used indirectly, via
+ the _rcu list-manipulation primitives such as list_add_rcu().
rcu_dereference()
locking.
As with rcu_assign_pointer(), an important function of
- rcu_dereference() is to document which pointers are protected
- by RCU. And, again like rcu_assign_pointer(), rcu_dereference()
- is typically used indirectly, via the _rcu list-manipulation
+ rcu_dereference() is to document which pointers are protected by
+ RCU, in particular, flagging a pointer that is subject to changing
+ at any time, including immediately after the rcu_dereference().
+ And, again like rcu_assign_pointer(), rcu_dereference() is
+ typically used indirectly, via the _rcu list-manipulation
primitives, such as list_for_each_entry_rcu().
The following diagram shows how each API communicates among the
3. WHAT ARE SOME EXAMPLE USES OF CORE RCU API?
This section shows a simple use of the core RCU API to protect a
-global pointer to a dynamically allocated structure. More typical
+global pointer to a dynamically allocated structure. More-typical
uses of RCU may be found in listRCU.txt, arrayRCU.txt, and NMI-RCU.txt.
struct foo {
struct foo *new_fp;
struct foo *old_fp;
- new_fp = kmalloc(sizeof(*fp), GFP_KERNEL);
+ new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = gbl_foo;
*new_fp = *old_fp;
data item.
See checklist.txt for additional rules to follow when using RCU.
+And again, more-typical uses of RCU may be found in listRCU.txt,
+arrayRCU.txt, and NMI-RCU.txt.
4. WHAT IF MY UPDATING THREAD CANNOT BLOCK?
struct foo *new_fp;
struct foo *old_fp;
- new_fp = kmalloc(sizeof(*fp), GFP_KERNEL);
+ new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
spin_lock(&foo_mutex);
old_fp = gbl_foo;
*new_fp = *old_fp;
for papers describing the Linux kernel RCU implementation. The OLS'01
and OLS'02 papers are a good introduction, and the dissertation provides
-more details on the current implementation.
+more details on the current implementation as of early 2004.
5A. "TOY" IMPLEMENTATION #1: LOCKING
and release a global reader-writer lock. The synchronize_rcu()
primitive write-acquires this same lock, then immediately releases
it. This means that once synchronize_rcu() exits, all RCU read-side
-critical sections that were in progress before synchonize_rcu() was
+critical sections that were in progress before synchronize_rcu() was
called are guaranteed to have completed -- there is no way that
synchronize_rcu() would have been able to write-acquire the lock
otherwise.
{
int cpu;
- for_each_cpu(cpu)
+ for_each_possible_cpu(cpu)
run_on(cpu);
}
+ spin_lock(&listmutex);
list_for_each_entry(p, head, lp) {
if (p->key == key) {
- list_del(&p->list);
+ - list_del(&p->list);
- write_unlock(&listmutex);
+ + list_del_rcu(&p->list);
+ spin_unlock(&listmutex);
+ synchronize_rcu();
kfree(p);
5 write_lock(&listmutex); 5 spin_lock(&listmutex);
6 list_for_each_entry(p, head, lp) { 6 list_for_each_entry(p, head, lp) {
7 if (p->key == key) { 7 if (p->key == key) {
- 8 list_del(&p->list); 8 list_del(&p->list);
+ 8 list_del(&p->list); 8 list_del_rcu(&p->list);
9 write_unlock(&listmutex); 9 spin_unlock(&listmutex);
10 synchronize_rcu();
10 kfree(p); 11 kfree(p);
Either way, the differences are quite small. Read-side locking moves
to rcu_read_lock() and rcu_read_unlock, update-side locking moves from
-from a reader-writer lock to a simple spinlock, and a synchronize_rcu()
+a reader-writer lock to a simple spinlock, and a synchronize_rcu()
precedes the kfree().
However, there is one potential catch: the read-side and update-side
APIs, since there does not appear to be a way to categorize them
in docbook. Here is the list, by category.
-Markers for RCU read-side critical sections:
-
- rcu_read_lock
- rcu_read_unlock
- rcu_read_lock_bh
- rcu_read_unlock_bh
-
RCU pointer/list traversal:
rcu_dereference
- list_for_each_rcu (to be deprecated in favor of
- list_for_each_entry_rcu)
- list_for_each_safe_rcu (deprecated, not used)
list_for_each_entry_rcu
+ hlist_for_each_entry_rcu
+
list_for_each_continue_rcu (to be deprecated in favor of new
list_for_each_entry_continue_rcu)
- hlist_for_each_rcu (to be deprecated in favor of
- hlist_for_each_entry_rcu)
- hlist_for_each_entry_rcu
-RCU pointer update:
+RCU pointer/list update:
rcu_assign_pointer
list_add_rcu
list_del_rcu
list_replace_rcu
hlist_del_rcu
+ hlist_add_after_rcu
+ hlist_add_before_rcu
hlist_add_head_rcu
+ hlist_replace_rcu
+ list_splice_init_rcu()
+
+RCU: Critical sections Grace period Barrier
+
+ rcu_read_lock synchronize_net rcu_barrier
+ rcu_read_unlock synchronize_rcu
+ call_rcu
+
+
+bh: Critical sections Grace period Barrier
+
+ rcu_read_lock_bh call_rcu_bh rcu_barrier_bh
+ rcu_read_unlock_bh
+
+
+sched: Critical sections Grace period Barrier
+
+ [preempt_disable] synchronize_sched rcu_barrier_sched
+ [and friends] call_rcu_sched
+
+
+SRCU: Critical sections Grace period Barrier
-RCU grace period:
+ srcu_read_lock synchronize_srcu N/A
+ srcu_read_unlock
- synchronize_kernel (deprecated)
- synchronize_net
- synchronize_sched
- synchronize_rcu
- call_rcu
- call_rcu_bh
See the comment headers in the source code (or the docbook generated
from them) for more information.
Answer: Consider the following sequence of events:
1. CPU 0 acquires some unrelated lock, call it
- "problematic_lock".
+ "problematic_lock", disabling irq via
+ spin_lock_irqsave().
2. CPU 1 enters synchronize_rcu(), write-acquiring
rcu_gp_mutex.
ACKNOWLEDGEMENTS
My thanks to the people who helped make this human-readable, including
-Jon Walpole, Josh Triplett, Serge Hallyn, and Suzanne Wood.
+Jon Walpole, Josh Triplett, Serge Hallyn, Suzanne Wood, and Alan Stern.
For more information, see http://www.rdrop.com/users/paulmck/RCU.
git://ftp.safe.ca / safe / jmp / linux-2.6 / blobdiff