Skip to contentSkip to conversation

Permitting sleeping in RCU read-side critical sections

RFC PATCH New Paul E. McKenney 1 participant 1 message Jun 17, 2006

Subsystems (3)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 Permitting sleeping in RCU read-side critical sections

Over the years, a number of people have asked for the ability to block (as opposed to merely be preempted or wait for a lock) in RCU read-side critical sections. After years of saying "no way!!!", I find that it is in fact possible to build an RCU-like primitive that permits this, patch attached. Of course, the people wanting this have probably figured out some other way to solve their problem, but just in case similar needs arises again...

Passes 20 hours of rcutorture on i386 and ppc64, which constitutes a reasonable "smoke test".

This patch includes:

o Documentation updates.

o Changes to the rcutorture test that permits it to test alternative
RCU implementations. Addition of option for testing call_rcu_bh() as well, with a new torture_type module parameter selecting the RCU implementation to test. But you currently cannot test all three RCU variants on the same system at the same time. Sorry!!!

o Sleepable RCU itself, or SRCU. There are some differences from
classic and realtime RCU:

o Each use of SRCU creates its own srcu_struct, and each
srcu_struct has its own set of grace periods. This is critical, as it prevents one subsystem with a blocking reader from holding up SRCU grace periods for other subsystems.

o The SRCU primitives (srcu_read_lock(), srcu_read_unlock(),
and synchronize_srcu()) all take a pointer to a srcu_struct.

o The SRCU primitives must be called from process context.

o srcu_read_lock() returns an int that must be passed to
the matching srcu_read_unlock(). Realtime RCU avoids the need for this by storing the state in the task struct, but SRCU needs to allow a given code path to pass through multiple SRCU domains -- storing state in the task struct would therefore require either arbitrary space in the task struct or arbitrary limits on SRCU nesting. So I kicked the state-storage problem up to the caller.

o There is no call_srcu(). It would not be hard to implement
one, but it seems like too easy a way to OOM the system. (Hey, we have enough trouble with call_rcu(), which does -not- permit readers to sleep!!!) So, if you want it, please tell me why...

Other than the above differences, SRCU acts very much like RCU.

o I do -not- anticipate SRCU ever folding into the main RCU
implementation. For one thing, the API is different...

o SRCU is fairly simple as RCU implementations go -- about 200
lines for the actual implementation. That said, synchronize_srcu() is fairly simple and unoptimized.

---

 Documentation/RCU/checklist.txt |   32 ++++
 Documentation/RCU/rcu.txt       |    3 
 Documentation/RCU/torture.txt   |   44 +++++-
 Documentation/RCU/whatisRCU.txt |    3 
 include/linux/srcu.h            |   42 ++++++
 kernel/Makefile                 |    2 
 kernel/rcupdate.c               |   10 +
 kernel/rcutorture.c             |  278 ++++++++++++++++++++++++++++++++++------
 kernel/srcu.c                   |  173 ++++++++++++++++++++++++
 9 files changed, 536 insertions(+), 51 deletions(-)
Documentation/RCU/checklist.txt +32 -0
diff -urpNa -X dontdiff linux-2.6.17-rc6/Documentation/RCU/checklist.txt linux-2.6.17-rc6-srcu/Documentation/RCU/checklist.txt
@@ -183,3 +183,35 @@ over a rather long period of time, but i
 	disable irq on a given acquisition of that lock will result in
 	deadlock as soon as the RCU callback happens to interrupt that
 	acquisition's critical section.
+
+13.	SRCU (srcu_read_lock(), srcu_read_unlock(), and synchronize_srcu())
+	may only be invoked from process context.  Unlike other forms of
+	RCU, it -is- permissible to block in an SRCU read-side critical
+	section (demarked by srcu_read_lock() and srcu_read_unlock()),
+	hence the "SRCU": "sleepable RCU".
+
+	Also unlike other forms of RCU, explicit initialization
+	and cleanup is required via init_srcu_struct() and
+	cleanup_srcu_struct().	These are passed a "struct srcu_struct"
+	that defines the scope of a given SRCU domain.	Once initialized,
+	the srcu_struct is passed to srcu_read_lock(), srcu_read_unlock()
+	and synchronize_srcu().  A given synchronize_srcu() waits only
+	for SRCU read-side critical sections governed by srcu_read_lock()
+	and srcu_read_unlock() calls that have been passd the same
+	srcu_struct.  This property is what makes sleeping read-side
+	critical sections tolerable -- a given subsystem delays only
+	its own updates, not those of other subsystems using SRCU.
+
+	This benefit does not come for free.  First, corresponding
+	srcu_read_lock() and srcu_read_unlock() calls must be passed
+	the same srcu_struct.  Second, grace-period-detection overhead
+	is amortized only over those updates sharing a given srcu_struct,
+	rather than being globally amortized as they are for other forms
+	of RCU.  This means that SRCU should be used only in extremely
+	read-intensive situations if performance is the goal (of course,
+	if the goal is instead read-side deadlock avoidance or read-side
+	realtime latency, then SRCU might be applicable to less extreme
+	degrees of read intensity).
+
+	Note that, rcu_assign_pointer() and rcu_dereference() relate to
+	SRCU just as they do to other forms of RCU.
Documentation/RCU/rcu.txt +2 -1
diff -urpNa -X dontdiff linux-2.6.17-rc6/Documentation/RCU/rcu.txt linux-2.6.17-rc6-srcu/Documentation/RCU/rcu.txt
@@ -45,7 +45,8 @@ o	How can I see where RCU is currently u
 
 	Search for "rcu_read_lock", "rcu_read_unlock", "call_rcu",
 	"rcu_read_lock_bh", "rcu_read_unlock_bh", "call_rcu_bh",
-	"synchronize_rcu", and "synchronize_net".
+	"srcu_read_lock", "srcu_read_unlock", "synchronize_rcu",
+	"synchronize_net", and "synchronize_srcu".
 
 o	What guidelines should I follow when writing code that uses RCU?
 
Documentation/RCU/torture.txt +36 -8

68 lines not on this page · raw message

Documentation/RCU/whatisRCU.txt +3 -0
diff -urpNa -X dontdiff linux-2.6.17-rc6/Documentation/RCU/whatisRCU.txt linux-2.6.17-rc6-srcu/Documentation/RCU/whatisRCU.txt
@@ -767,6 +767,8 @@ Markers for RCU read-side critical secti
 	rcu_read_unlock
 	rcu_read_lock_bh
 	rcu_read_unlock_bh
+	srcu_read_lock
+	srcu_read_unlock
 
 RCU pointer/list traversal:
 
@@ -794,6 +796,7 @@ RCU grace period:
 	synchronize_net
 	synchronize_sched
 	synchronize_rcu
+	synchronize_srcu
 	call_rcu
 	call_rcu_bh
 
include/linux/srcu.h +42 -0

42 lines not on this page · raw message

kernel/Makefile +1 -1
diff -urpNa -X dontdiff linux-2.6.17-rc6/kernel/Makefile linux-2.6.17-rc6-srcu/kernel/Makefile
@@ -8,7 +8,7 @@ obj-y     = sched.o fork.o exec_domain.o
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o extable.o params.o posix-timers.o \
 	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \
-	    hrtimer.o
+	    hrtimer.o srcu.o
 
 obj-$(CONFIG_DEBUG_MUTEXES) += mutex-debug.o
 obj-$(CONFIG_FUTEX) += futex.o
kernel/rcupdate.c +10 -0
diff -urpNa -X dontdiff linux-2.6.17-rc6/kernel/rcupdate.c linux-2.6.17-rc6-srcu/kernel/rcupdate.c
@@ -182,6 +182,15 @@ long rcu_batches_completed(void)
 	return rcu_ctrlblk.completed;
 }
 
+/*
+ * Return the number of RCU batches processed thus far.  Useful
+ * for debug and statistics.
+ */
+long rcu_batches_completed_bh(void)
+{
+	return rcu_bh_ctrlblk.completed;
+}
+
 static void rcu_barrier_callback(struct rcu_head *notused)
 {
 	if (atomic_dec_and_test(&rcu_barrier_cpu_count))
@@ -627,6 +636,7 @@ module_param(qlowmark, int, 0);
 module_param(rsinterval, int, 0);
 #endif
 EXPORT_SYMBOL_GPL(rcu_batches_completed);
+EXPORT_SYMBOL_GPL(rcu_batches_completed_bh);
 EXPORT_SYMBOL_GPL_FUTURE(call_rcu);	/* WARNING: GPL-only in April 2006. */
 EXPORT_SYMBOL_GPL_FUTURE(call_rcu_bh);	/* WARNING: GPL-only in April 2006. */
 EXPORT_SYMBOL_GPL(synchronize_rcu);
kernel/rcutorture.c +237 -41

415 lines not on this page · raw message

kernel/srcu.c +173 -0

173 lines not on this page · raw message