aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAlan Stern <stern@rowland.harvard.edu>2006-10-04 05:17:04 -0400
committerLinus Torvalds <torvalds@g5.osdl.org>2006-10-04 10:55:30 -0400
commiteabc069401bcf45bcc3f19e643017bf761780aa8 (patch)
tree1175b8bed2d88cc9f437edbc239d7681f13b8a7d
parentb2896d2e75c87ea6a842c088db730b03c91db737 (diff)
[PATCH] Add SRCU-based notifier chains
This patch (as751) adds a new type of notifier chain, based on the SRCU (Sleepable Read-Copy Update) primitives recently added to the kernel. An SRCU notifier chain is much like a blocking notifier chain, in that it must be called in process context and its callout routines are allowed to sleep. The difference is that the chain's links are protected by the SRCU mechanism rather than by an rw-semaphore, so calling the chain has extremely low overhead: no memory barriers and no cache-line bouncing. On the other hand, unregistering from the chain is expensive and the chain head requires special runtime initialization (plus cleanup if it is to be deallocated). SRCU notifiers are appropriate for notifiers that will be called very frequently and for which unregistration occurs very seldom. The proposed "task notifier" scheme qualifies, as may some of the network notifiers. Signed-off-by: Alan Stern <stern@rowland.harvard.edu> Acked-by: Paul E. McKenney <paulmck@us.ibm.com> Acked-by: Chandra Seetharaman <sekharan@us.ibm.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
-rw-r--r--include/linux/notifier.h43
-rw-r--r--include/linux/srcu.h6
-rw-r--r--kernel/sys.c124
3 files changed, 166 insertions, 7 deletions
diff --git a/include/linux/notifier.h b/include/linux/notifier.h
index 7ff386a6ae87..10a43ed0527e 100644
--- a/include/linux/notifier.h
+++ b/include/linux/notifier.h
@@ -12,9 +12,10 @@
12#include <linux/errno.h> 12#include <linux/errno.h>
13#include <linux/mutex.h> 13#include <linux/mutex.h>
14#include <linux/rwsem.h> 14#include <linux/rwsem.h>
15#include <linux/srcu.h>
15 16
16/* 17/*
17 * Notifier chains are of three types: 18 * Notifier chains are of four types:
18 * 19 *
19 * Atomic notifier chains: Chain callbacks run in interrupt/atomic 20 * Atomic notifier chains: Chain callbacks run in interrupt/atomic
20 * context. Callouts are not allowed to block. 21 * context. Callouts are not allowed to block.
@@ -23,13 +24,27 @@
23 * Raw notifier chains: There are no restrictions on callbacks, 24 * Raw notifier chains: There are no restrictions on callbacks,
24 * registration, or unregistration. All locking and protection 25 * registration, or unregistration. All locking and protection
25 * must be provided by the caller. 26 * must be provided by the caller.
27 * SRCU notifier chains: A variant of blocking notifier chains, with
28 * the same restrictions.
26 * 29 *
27 * atomic_notifier_chain_register() may be called from an atomic context, 30 * atomic_notifier_chain_register() may be called from an atomic context,
28 * but blocking_notifier_chain_register() must be called from a process 31 * but blocking_notifier_chain_register() and srcu_notifier_chain_register()
29 * context. Ditto for the corresponding _unregister() routines. 32 * must be called from a process context. Ditto for the corresponding
33 * _unregister() routines.
30 * 34 *
31 * atomic_notifier_chain_unregister() and blocking_notifier_chain_unregister() 35 * atomic_notifier_chain_unregister(), blocking_notifier_chain_unregister(),
32 * _must not_ be called from within the call chain. 36 * and srcu_notifier_chain_unregister() _must not_ be called from within
37 * the call chain.
38 *
39 * SRCU notifier chains are an alternative form of blocking notifier chains.
40 * They use SRCU (Sleepable Read-Copy Update) instead of rw-semaphores for
41 * protection of the chain links. This means there is _very_ low overhead
42 * in srcu_notifier_call_chain(): no cache bounces and no memory barriers.
43 * As compensation, srcu_notifier_chain_unregister() is rather expensive.
44 * SRCU notifier chains should be used when the chain will be called very
45 * often but notifier_blocks will seldom be removed. Also, SRCU notifier
46 * chains are slightly more difficult to use because they require special
47 * runtime initialization.
33 */ 48 */
34 49
35struct notifier_block { 50struct notifier_block {
@@ -52,6 +67,12 @@ struct raw_notifier_head {
52 struct notifier_block *head; 67 struct notifier_block *head;
53}; 68};
54 69
70struct srcu_notifier_head {
71 struct mutex mutex;
72 struct srcu_struct srcu;
73 struct notifier_block *head;
74};
75
55#define ATOMIC_INIT_NOTIFIER_HEAD(name) do { \ 76#define ATOMIC_INIT_NOTIFIER_HEAD(name) do { \
56 spin_lock_init(&(name)->lock); \ 77 spin_lock_init(&(name)->lock); \
57 (name)->head = NULL; \ 78 (name)->head = NULL; \
@@ -64,6 +85,11 @@ struct raw_notifier_head {
64 (name)->head = NULL; \ 85 (name)->head = NULL; \
65 } while (0) 86 } while (0)
66 87
88/* srcu_notifier_heads must be initialized and cleaned up dynamically */
89extern void srcu_init_notifier_head(struct srcu_notifier_head *nh);
90#define srcu_cleanup_notifier_head(name) \
91 cleanup_srcu_struct(&(name)->srcu);
92
67#define ATOMIC_NOTIFIER_INIT(name) { \ 93#define ATOMIC_NOTIFIER_INIT(name) { \
68 .lock = __SPIN_LOCK_UNLOCKED(name.lock), \ 94 .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
69 .head = NULL } 95 .head = NULL }
@@ -72,6 +98,7 @@ struct raw_notifier_head {
72 .head = NULL } 98 .head = NULL }
73#define RAW_NOTIFIER_INIT(name) { \ 99#define RAW_NOTIFIER_INIT(name) { \
74 .head = NULL } 100 .head = NULL }
101/* srcu_notifier_heads cannot be initialized statically */
75 102
76#define ATOMIC_NOTIFIER_HEAD(name) \ 103#define ATOMIC_NOTIFIER_HEAD(name) \
77 struct atomic_notifier_head name = \ 104 struct atomic_notifier_head name = \
@@ -91,6 +118,8 @@ extern int blocking_notifier_chain_register(struct blocking_notifier_head *,
91 struct notifier_block *); 118 struct notifier_block *);
92extern int raw_notifier_chain_register(struct raw_notifier_head *, 119extern int raw_notifier_chain_register(struct raw_notifier_head *,
93 struct notifier_block *); 120 struct notifier_block *);
121extern int srcu_notifier_chain_register(struct srcu_notifier_head *,
122 struct notifier_block *);
94 123
95extern int atomic_notifier_chain_unregister(struct atomic_notifier_head *, 124extern int atomic_notifier_chain_unregister(struct atomic_notifier_head *,
96 struct notifier_block *); 125 struct notifier_block *);
@@ -98,6 +127,8 @@ extern int blocking_notifier_chain_unregister(struct blocking_notifier_head *,
98 struct notifier_block *); 127 struct notifier_block *);
99extern int raw_notifier_chain_unregister(struct raw_notifier_head *, 128extern int raw_notifier_chain_unregister(struct raw_notifier_head *,
100 struct notifier_block *); 129 struct notifier_block *);
130extern int srcu_notifier_chain_unregister(struct srcu_notifier_head *,
131 struct notifier_block *);
101 132
102extern int atomic_notifier_call_chain(struct atomic_notifier_head *, 133extern int atomic_notifier_call_chain(struct atomic_notifier_head *,
103 unsigned long val, void *v); 134 unsigned long val, void *v);
@@ -105,6 +136,8 @@ extern int blocking_notifier_call_chain(struct blocking_notifier_head *,
105 unsigned long val, void *v); 136 unsigned long val, void *v);
106extern int raw_notifier_call_chain(struct raw_notifier_head *, 137extern int raw_notifier_call_chain(struct raw_notifier_head *,
107 unsigned long val, void *v); 138 unsigned long val, void *v);
139extern int srcu_notifier_call_chain(struct srcu_notifier_head *,
140 unsigned long val, void *v);
108 141
109#define NOTIFY_DONE 0x0000 /* Don't care */ 142#define NOTIFY_DONE 0x0000 /* Don't care */
110#define NOTIFY_OK 0x0001 /* Suits me */ 143#define NOTIFY_OK 0x0001 /* Suits me */
diff --git a/include/linux/srcu.h b/include/linux/srcu.h
index 947fdab2ddb0..8a45367b5f3a 100644
--- a/include/linux/srcu.h
+++ b/include/linux/srcu.h
@@ -24,6 +24,9 @@
24 * 24 *
25 */ 25 */
26 26
27#ifndef _LINUX_SRCU_H
28#define _LINUX_SRCU_H
29
27struct srcu_struct_array { 30struct srcu_struct_array {
28 int c[2]; 31 int c[2];
29}; 32};
@@ -46,4 +49,5 @@ int srcu_read_lock(struct srcu_struct *sp) __acquires(sp);
46void srcu_read_unlock(struct srcu_struct *sp, int idx) __releases(sp); 49void srcu_read_unlock(struct srcu_struct *sp, int idx) __releases(sp);
47void synchronize_srcu(struct srcu_struct *sp); 50void synchronize_srcu(struct srcu_struct *sp);
48long srcu_batches_completed(struct srcu_struct *sp); 51long srcu_batches_completed(struct srcu_struct *sp);
49void cleanup_srcu_struct(struct srcu_struct *sp); 52
53#endif
diff --git a/kernel/sys.c b/kernel/sys.c
index 2314867ae34f..fd5c71006775 100644
--- a/kernel/sys.c
+++ b/kernel/sys.c
@@ -153,7 +153,7 @@ static int __kprobes notifier_call_chain(struct notifier_block **nl,
153 153
154/* 154/*
155 * Atomic notifier chain routines. Registration and unregistration 155 * Atomic notifier chain routines. Registration and unregistration
156 * use a mutex, and call_chain is synchronized by RCU (no locks). 156 * use a spinlock, and call_chain is synchronized by RCU (no locks).
157 */ 157 */
158 158
159/** 159/**
@@ -401,6 +401,128 @@ int raw_notifier_call_chain(struct raw_notifier_head *nh,
401 401
402EXPORT_SYMBOL_GPL(raw_notifier_call_chain); 402EXPORT_SYMBOL_GPL(raw_notifier_call_chain);
403 403
404/*
405 * SRCU notifier chain routines. Registration and unregistration
406 * use a mutex, and call_chain is synchronized by SRCU (no locks).
407 */
408
409/**
410 * srcu_notifier_chain_register - Add notifier to an SRCU notifier chain
411 * @nh: Pointer to head of the SRCU notifier chain
412 * @n: New entry in notifier chain
413 *
414 * Adds a notifier to an SRCU notifier chain.
415 * Must be called in process context.
416 *
417 * Currently always returns zero.
418 */
419
420int srcu_notifier_chain_register(struct srcu_notifier_head *nh,
421 struct notifier_block *n)
422{
423 int ret;
424
425 /*
426 * This code gets used during boot-up, when task switching is
427 * not yet working and interrupts must remain disabled. At
428 * such times we must not call mutex_lock().
429 */
430 if (unlikely(system_state == SYSTEM_BOOTING))
431 return notifier_chain_register(&nh->head, n);
432
433 mutex_lock(&nh->mutex);
434 ret = notifier_chain_register(&nh->head, n);
435 mutex_unlock(&nh->mutex);
436 return ret;
437}
438
439EXPORT_SYMBOL_GPL(srcu_notifier_chain_register);
440
441/**
442 * srcu_notifier_chain_unregister - Remove notifier from an SRCU notifier chain
443 * @nh: Pointer to head of the SRCU notifier chain
444 * @n: Entry to remove from notifier chain
445 *
446 * Removes a notifier from an SRCU notifier chain.
447 * Must be called from process context.
448 *
449 * Returns zero on success or %-ENOENT on failure.
450 */
451int srcu_notifier_chain_unregister(struct srcu_notifier_head *nh,
452 struct notifier_block *n)
453{
454 int ret;
455
456 /*
457 * This code gets used during boot-up, when task switching is
458 * not yet working and interrupts must remain disabled. At
459 * such times we must not call mutex_lock().
460 */
461 if (unlikely(system_state == SYSTEM_BOOTING))
462 return notifier_chain_unregister(&nh->head, n);
463
464 mutex_lock(&nh->mutex);
465 ret = notifier_chain_unregister(&nh->head, n);
466 mutex_unlock(&nh->mutex);
467 synchronize_srcu(&nh->srcu);
468 return ret;
469}
470
471EXPORT_SYMBOL_GPL(srcu_notifier_chain_unregister);
472
473/**
474 * srcu_notifier_call_chain - Call functions in an SRCU notifier chain
475 * @nh: Pointer to head of the SRCU notifier chain
476 * @val: Value passed unmodified to notifier function
477 * @v: Pointer passed unmodified to notifier function
478 *
479 * Calls each function in a notifier chain in turn. The functions
480 * run in a process context, so they are allowed to block.
481 *
482 * If the return value of the notifier can be and'ed
483 * with %NOTIFY_STOP_MASK then srcu_notifier_call_chain
484 * will return immediately, with the return value of
485 * the notifier function which halted execution.
486 * Otherwise the return value is the return value
487 * of the last notifier function called.
488 */
489
490int srcu_notifier_call_chain(struct srcu_notifier_head *nh,
491 unsigned long val, void *v)
492{
493 int ret;
494 int idx;
495
496 idx = srcu_read_lock(&nh->srcu);
497 ret = notifier_call_chain(&nh->head, val, v);
498 srcu_read_unlock(&nh->srcu, idx);
499 return ret;
500}
501
502EXPORT_SYMBOL_GPL(srcu_notifier_call_chain);
503
504/**
505 * srcu_init_notifier_head - Initialize an SRCU notifier head
506 * @nh: Pointer to head of the srcu notifier chain
507 *
508 * Unlike other sorts of notifier heads, SRCU notifier heads require
509 * dynamic initialization. Be sure to call this routine before
510 * calling any of the other SRCU notifier routines for this head.
511 *
512 * If an SRCU notifier head is deallocated, it must first be cleaned
513 * up by calling srcu_cleanup_notifier_head(). Otherwise the head's
514 * per-cpu data (used by the SRCU mechanism) will leak.
515 */
516
517void srcu_init_notifier_head(struct srcu_notifier_head *nh)
518{
519 mutex_init(&nh->mutex);
520 init_srcu_struct(&nh->srcu);
521 nh->head = NULL;
522}
523
524EXPORT_SYMBOL_GPL(srcu_init_notifier_head);
525
404/** 526/**
405 * register_reboot_notifier - Register function to be called at reboot time 527 * register_reboot_notifier - Register function to be called at reboot time
406 * @nb: Info about notifier function to be called 528 * @nb: Info about notifier function to be called