Skip to contentSkip to conversation

srcu-2: add RCU variant that permits read-side blocking

PATCH In review Paul E. McKenney 1 participant 4 messages Jun 27, 2006 – Jun 28, 2006

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

cover srcu-2: add RCU variant that permits read-side blocking

Updated based on review comments from Andrew and Oleg (thank you!).

Oleg's bug did turn out to be real (thank you, Oleg!!!), so this patch contains an alleged fix. It passes a short rcutorture run on x86 and ppc64, but so did the previous one (more intense testing in the offing). This patchset depends on the earlier ops-ization of the rcutorture infrastructure.

As before, series includes:

o Addition of SRCU primitives and documentation.

o Addition of SRCU operations to rcutorture.

Thanx, Paul

#1 lore raw

PATCH 1/2 srcu-2: RCU variant permitting read-side blocking

Updated patch adding a variant of RCU that permits sleeping in read-side critical sections. SRCU is as follows:

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...

---

 Documentation/RCU/checklist.txt |   32 ++++++
 Documentation/RCU/rcu.txt       |    3 
 Documentation/RCU/whatisRCU.txt |    3 
 include/linux/srcu.h            |   42 ++++++++
 kernel/Makefile                 |    2 
 kernel/srcu.c                   |  188 ++++++++++++++++++++++++++++++++++++++++
 6 files changed, 268 insertions(+), 2 deletions(-)
Documentation/RCU/checklist.txt +32 -0
diff -urpNa -X dontdiff linux-2.6.17-torturercu_bh/Documentation/RCU/checklist.txt linux-2.6.17-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-torturercu_bh/Documentation/RCU/rcu.txt linux-2.6.17-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/whatisRCU.txt +3 -0
diff -urpNa -X dontdiff linux-2.6.17-torturercu_bh/Documentation/RCU/whatisRCU.txt linux-2.6.17-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-torturercu_bh/kernel/Makefile linux-2.6.17-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/srcu.c +188 -0

188 lines not on this page · raw message

#2 lore raw

PATCH 2/2 srcu-2: add SRCU operations to rcutorture

In reply to Paul E. McKenney

Adds SRCU operations to rcutorture and updates rcutorture documentation.

---

 Documentation/RCU/torture.txt |   15 +++++++
 kernel/rcutorture.c           |   89 ++++++++++++++++++++++++++++++++++++++++--
 2 files changed, 101 insertions(+), 3 deletions(-)
Documentation/RCU/torture.txt +15 -0
diff -urpNa -X dontdiff linux-2.6.17-srcu/Documentation/RCU/torture.txt linux-2.6.17-torturesrcu/Documentation/RCU/torture.txt
@@ -118,6 +118,21 @@ o	"Free-Block Circulation": Shows the nu
 	as it is only incremented if a torture structure's counter
 	somehow gets incremented farther than it should.
 
+Different implementations of RCU can provide implementation-specific
+additional information.  For example, SRCU provides the following:
+
+	srcu-torture: rtc: f8cf46a8 ver: 355 tfle: 0 rta: 356 rtaf: 0 rtf: 346 rtmbe: 0
+	srcu-torture: Reader Pipe:  559738 939 0 0 0 0 0 0 0 0 0
+	srcu-torture: Reader Batch:  560434 243 0 0 0 0 0 0 0 0
+	srcu-torture: Free-Block Circulation:  355 354 353 352 351 350 349 348 347 346 0
+	srcu-torture: per-CPU(idx=1): 0(0,1) 1(0,1) 2(0,0) 3(0,1)
+
+The first four lines are similar to those for RCU.  The last line shows
+the per-CPU counter state.  The numbers in parentheses are the values
+of the "old" and "current" counters for the corresponding CPU.  The
+"idx" value maps the "old" and "current" values to the underlying array,
+and is useful for debugging.
+
 
 USAGE
 
kernel/rcutorture.c +86 -3

114 lines not on this page · raw message

#3 lore raw
In reply to Paul E. McKenney
Quoted 7 lines · Paul E. McKenney

Updated based on review comments from Andrew and Oleg (thank you!).

Oleg's bug did turn out to be real (thank you, Oleg!!!), so this patch contains an alleged fix. It passes a short rcutorture run on x86 and ppc64, but so did the previous one (more intense testing in the offing). This patchset depends on the earlier ops-ization of the rcutorture infrastructure.

Oh, and it passed on s390 as well.

Thanx, Paul