srcu-3: add RCU variant that permits read-side blocking
Subsystems (3)
cover srcu-3: add RCU variant that permits read-side blocking
Version 3 of the SRCU patchset.
This patch incorporates a number of improvements, many of which came up in off-list discussions with Alan Stern. Neither of us are sure why these discussions ended up off-list, so I have summarized them below.
o Fixes some "zombie code" -- excess curly braces and the like.
o Gets rid of the double-flip in favor of an additional
synchronize_sched(). This turned out to be safe, despite my saying otherwise at http://lkml.org/lkml/2006/6/27/486.
The trick that I was missing is that synchronize_sched() forces all CPUs to execute at least one memory barrier during the synchronize_sched()'s execution, which forces all CPUs to see synchronize_srcu()'s counter increment as happening after any memory manipulations prior to the synchronize_srcu().
Upgraded comments to indicate what the synchronize_sched() calls are needed for.
o Added a barrier() to both srcu_read_lock() and srcu_read_unlock()
to prevent the compiler from performing optimizations that would cause the critical section to move outside of the enclosing srcu_read_lock() and srcu_read_unlock().
However, these barrier()s in srcu_read_lock() and srcu_read_unlock() are needed only in non-CONFIG_PREEMPT kernels, so they compile to nothing in CONFIG_PREEMPT kernels (where the preempt_disable() and preempt_enable() calls supply the needed barrier() call).
o Added a check to synchronize_srcu() that permits this primitive
to take advantage of grace periods induced by concurrent executions in other tasks. This can be useful in cases where you are using a single srcu_struct to handle all the individually-locked chains of a hash table, for example.
o cleanup_srcu_struct() now contains error checks to catch cases
where readers are still using the srcu_struct in question. It does a WARN_ON() and leaks the srcu_struct's per-CPU data in that case.
o There is an srcu_readers_active() that returns the number of
readers (approximate!) currently using the specified srcu_struct. This can be useful when terminating use of an srcu_struct, e.g., at module-unload time.
o Improved the RCU torture tests, increasing the skew on reader
times and providing implementation-specific delay functions.
PATCH 1/2 srcu-3: 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.
Of course, it is not permitted to call synchronize_srcu() while in an SRCU read-side critical section.
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 | 38 ++++++ Documentation/RCU/rcu.txt | 3 Documentation/RCU/whatisRCU.txt | 3 include/linux/srcu.h | 49 ++++++++ kernel/Makefile | 2 kernel/srcu.c | 238 ++++++++++++++++++++++++++++++++++++++++ 6 files changed, 331 insertions(+), 2 deletions(-)
Documentation/RCU/checklist.txt +38 -0
@@ -183,3 +183,41 @@ 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". Please note that if you + don't need to sleep in read-side critical sections, you should + be using RCU rather than SRCU, because RCU is almost always + faster and easier to use than is SRCU. + + 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. + Therefore, SRCU is less prone to OOM the system than RCU would + be if RCU's read-side critical sections were permitted to + sleep. + + The ability to sleep in read-side critical sections 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. + Therefore, SRCU should be used in preference to rw_semaphore + only in extremely read-intensive situations, or in situations + requiring SRCU's read-side deadlock immunity or low read-side + realtime latency. + + 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
@@ -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
@@ -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 +49 -0
49 lines not on this page · raw message
kernel/Makefile +1 -1
@@ -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 +238 -0
238 lines not on this page · raw message
A message that is not in the archive (sent off-list or not yet received): 20060709235029.GA194@oleg
Re: [PATCH 1/2] srcu-3: RCU variant permitting read-side blocking
Quoted 7 lines · Oleg Nesterov
Quoted 3 lines · Paul E. McKenney
Updated patch adding a variant of RCU that permits sleeping in read-side critical sections.
I do not see any problems with this patch, but I have a couple of questions, so your help is needed again.
Thank you for looking it over!
Quoted 12 lines
Quoted 12 lines
(quoted diff) +12
-0+void synchronize_srcu(struct srcu_struct *sp) +{ + [... snip ...] + + synchronize_sched(); /* Force memory barrier on all CPUs. */ + + /* + * The preceding synchronize_sched() forces all srcu_read_unlock() + * primitives that were executing concurrently with the preceding + * for_each_possible_cpu() loop to have completed by this point. + * More importantly, it also forces the corresponding SRCU read-side + * critical sections to have also completed, and the corresponding
Quoted 8 lines
Review
Quoted 5 lines
(quoted diff) +5
-0+ * references to SRCU-protected data items to be dropped. + */ + + mutex_unlock(&sp->mutex); +}Isn't it possible to unlock ->mutex earlier, before the last
synchronize_sched()?
It seems possible, but I would like to think carefully about this one first, and, if it still seems plausible, test it heavily. If I understand your line of reasoning, the thought is that the first synchronize_sched() at the beginning of synchronize_srcu() ensures that all of the counter updates pertaining to the last instance of synchronize_srcu() have been committed. The same reasoning might well cover the sp->completed fastpath as well.
In any case, this is a performance boost off the fastpath. A good boost, if it works, but I will be much more excited if you find a way of speeding up srcu_read_lock() or srcu_read_unlock(). ;-)
Quoted 15 lines
Another question: what is the semantics of
synchronize_sched()?I am not talking about the current implementation, it is very clear. The question is: what is the _definition_ of
synchronize_sched()(which must be valid for "any" RCU implementation) ?1) The comment in
include/linux/rcupdate.hstates that "allpreempt_disablecode sequences will have completed before this primitive returns".2)
kernel/srcu.cclaims that this primitive "forces memory barrier on all CPUs". (so the comment inrcupdate.his not complete).(I understand this so that each cpu does something which implies
mb()
semantics).
Quoted 8 lines
As I see it, 1) + 2) is NOT enough for
synchronize_srcu()to be correct (the 2-nd and 3-rdsynchronize_sched()calls). I thinksynchronize_sched()should also guarantee the completion of mem ops on all CPUs before return, not justmb()(which does not have any timing guaranties).Could you clarify this issue?
(Again, I do not see any problems with the current RCU implementation).
However, this -does- seem to be to be a problem with the comment headers and the documentation. Does the following patch make things better?
David, would it be worthwhile adding this global-memory-barrier effect of synchronize_rcu(), synchronize_sched(), and synchronize_srcu() to Documentation/memory-barriers.txt?
Thanx, Paul
---
Documentation/RCU/checklist.txt | 4 ++++ include/linux/rcupdate.h | 3 +++ kernel/rcupdate.c | 3 +++ kernel/srcu.c | 3 ++- 4 files changed, 12 insertions(+), 1 deletion(-)
Documentation/RCU/checklist.txt +4 -0
@@ -221,3 +221,7 @@ over a rather long period of time, but i Note that, rcu_assign_pointer() and rcu_dereference() relate to SRCU just as they do to other forms of RCU. + +14. The synchronize_rcu(), synchronize_sched(), and synchronize_srcu() + primitives force at least one memory barrier to be executed on + each active CPU before they return.
include/linux/rcupdate.h +3 -0
@@ -251,6 +251,9 @@ extern int rcu_needs_cpu(int cpu);* guarantees that rcu_read_lock() sections will have completed. * In "classic RCU", these two guarantees happen to be one and * the same, but can differ in realtime RCU implementations. +* +* In addition, this primitive guarantees that every active CPU has +* executed at least one memory barrier before it returns. */ #define synchronize_sched () synchronize_rcu()
kernel/rcupdate.c +3 -0
@@ -597,6 +597,9 @@ static void wakeme_after_rcu(struct rcu_* sections are delimited by rcu_read_lock() and rcu_read_unlock(), * and may be nested. * +* This primitive also causes each active CPU to execute at least one +* memory barrier before it returns. +* * If your read-side code is not protected by rcu_read_lock(), do -not- * use synchronize_rcu(). */
kernel/srcu.c +2 -1
@@ -143,7 +143,8 @@ void srcu_read_unlock(struct srcu_struct* Flip the completed counter, and wait for the old count to drain to zero. * As with classic RCU, the updater must use some separate means of * synchronizing concurrent updates. Can block; must be called from -* process context. +* process context. Has the side-effect of forcing a memory barrier on +* each active CPU before returning. * * Note that it is illegal to call synchornize_srcu() from the corresponding * SRCU read-side critical section; doing so will result in deadlock.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH 1/2] srcu-3: RCU variant permitting read-side blocking
Quoted 19 lines · Nick Piggin
Quoted 9 lines · Paul E. McKenney
Quoted 7 lines · Oleg Nesterov
As I see it, 1) + 2) is NOT enough for
synchronize_srcu()to be correct (the 2-nd and 3-rdsynchronize_sched()calls). I thinksynchronize_sched()should also guarantee the completion of mem ops on all CPUs before return, not justmb()(which does not have any timing guaranties).Could you clarify this issue?
Quoted 8 lines
Quoted 1 line
(Again, I do not see any problems with the current RCU implementation).
However, this -does- seem to be to be a problem with the comment headers and the documentation. Does the following patch make things better?
David, would it be worthwhile adding this global-memory-barrier effect of
synchronize_rcu(),synchronize_sched(), andsynchronize_srcu()to
Quoted 6 lines
And
call_rcu? (or is that already tucked away in the documentation somewhere?) ie. there is a memory barrier between thecall_rcu()call and the actual callback.This is something I needed clarification with (as you might remember), which might not be clear from an RCU API user's point of view.
Good point -- since synchronize_rcu() is just a wrapper around call_rcu(), they do have the same properties. How about the following?
Thanx, Paul
Documentation/RCU/checklist.txt | 4 +++- include/linux/srcu.h | 5 +++++ kernel/rcupdate.c | 4 ++++ 3 files changed, 12 insertions(+), 1 deletion(-)
Documentation/RCU/checklist.txt +3 -1
@@ -224,4 +224,6 @@ over a rather long period of time, but i 14. The synchronize_rcu(), synchronize_sched(), and synchronize_srcu() primitives force at least one memory barrier to be executed on - each active CPU before they return. + each active CPU before they return. Similarly, call_rcu() + forces at least one memory barrier to be executed on each active + CPU before the corresponding callback is invoked.
kernel/rcupdate.c +4 -0
@@ -116,6 +116,10 @@ static inline void force_quiescent_state* read-side critical sections have completed. RCU read-side critical * sections are delimited by rcu_read_lock() and rcu_read_unlock(), * and may be nested. +* +* There will be at least one memory barrier executed on each active +* CPU between the time call_rcu() is invoked and the time that the +* corresponding callback is invoked. */ void fastcall call_rcu(struct rcu_head *head,void (*func)(struct rcu_head *rcu))
PATCH 2/2 srcu-3: add SRCU operations to rcutorture
In reply to Paul E. McKenneyAdds SRCU operations to rcutorture and updates rcutorture documentation. Also increases the stress imposed by the rcutorture test.
---
Documentation/RCU/torture.txt | 15 +++++ kernel/rcutorture.c | 121 ++++++++++++++++++++++++++++++++++++++++-- 2 files changed, 132 insertions(+), 4 deletions(-)
Documentation/RCU/torture.txt +15 -0
@@ -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 +117 -4
176 lines not on this page · raw message