rcu-state
RFC PATCH 1/1 rcu-state
Hi,
Just to keep you updated:
I've fixed further bugs.
The code survived concurrent kernel compiles and cpu online/offline on a 4-cpu system.
The code tries to minimize the operations between call_rcu() and the final rcu destruction callback. It should achieve a lower latency than the current rcu backends, but I haven't written a benchmark yet.
Comments are welcome.
--
Manfred
Quoted 1 line
From
4cdf838ed978c5791aa66785b9ed4e32bbf7351aMon Sep 17 00:00:00 2001
From: Manfred Spraul <[email protected]>
Date: Sat, 25 Oct 2008 16:51:19 +0200
Subject: [PATCH] kernel/rcustate.c: state machine based rcu implementation
I've updated the state machine based rcu code.
The main new point is a rewritten rcu_irq_exit() code, it should now scale (no more write accesses to global memory).
Main changes:
- modified handling of call_rcu() from within irqs on nohz cpus:
call_rcu() not first marks the cpu as online, before adding the callbacks. This prevents any races and fixes the case that all cpus are in nohz mode.
- debug code added to the rcucpumask: it now tracks which cpus are marked as online.
- Added documentation.
- bugfixes
- checkpatch.pl fixes
Main points:
- As previously a state machine with system wide states: Either accumulate further call_rcu() callbacks, or collect the callbacks for the next grace period, or wait for a quiescent state.
Rational:
The rules for the state transistions are different for each state, thus a system wide state allows simpler/faster quiescent cycles. All other existing rcu backends do not have a global state, thus they do not advance until all cpus were quiet.
But: e.g.: nohz cpus never have pending call_rcu() callbacks. Thus they can be skipped entirely for the "collect" stage.
- Improved latency: There is only one for_each_cpu() loop per grace period, and even that loop is from schedule_work() with enabled local interrupts.
Rational:
for_each_cpu() loops with disabled local interrupts will cause latency problems.
- Experimental: it boots, nohz works, cpu offline works.
What do you think?
The patch depends on CPU_STARTING, the CPU_DYING change, it's against 2.6.28-rc1.
--- include/linux/hardirq.h | 27 +- include/linux/rcuclassic.h | 2 - include/linux/rcucpumask.h | 146 ++++++ include/linux/rcupdate.h | 19 +- include/linux/rcupreempt.h | 14 - include/linux/rcustate.h | 291 +++++++++++ init/Kconfig | 12 +- kernel/Makefile | 1 + kernel/rcuclassic.c | 18 + kernel/rcucpumask.c | 101 ++++ kernel/rcupreempt.c | 6 +- kernel/rcustate.c | 1211 ++++++++++++++++++++++++++++++++++++++++++++ kernel/softirq.c | 2 +- 13 files changed, 1816 insertions(+), 34 deletions(-) create mode 100644 include/linux/rcucpumask.h create mode 100644 include/linux/rcustate.h create mode 100644 kernel/rcucpumask.c create mode 100644 kernel/rcustate.c
include/linux/hardirq.h +15 -12
@@ -118,13 +118,13 @@ static inline void account_system_vtime(struct task_struct *tsk) }#endif -#if defined(CONFIG_PREEMPT_RCU ) && defined(CONFIG_NO_HZ ) -extern void rcu_irq_enter (void ); -extern void rcu_irq_exit (void ); +#ifdef CONFIG_NO_HZ +extern void rcu_irq_enter (int in_nmi); +extern void rcu_irq_exit (int in_nmi);#else -# define rcu_irq_enter () do { } while (0) -# define rcu_irq_exit () do { } while (0) -#endif /* CONFIG_PREEMPT_RCU */ +# define rcu_irq_enter (in_nmi) do { } while (0) +# define rcu_irq_exit (in_nmi) do { } while (0) +#endif /* CONFIG_NO_HZ */ /* * It is safe to do non-atomic ops on ->hardirq_context,
@@ -132,14 +132,17 @@ extern void rcu_irq_exit(void);* always balanced, so the interrupted value of ->hardirq_context * will always be restored. */ -#define __irq_enter () \ +#define ____irq_enter (in_nmi) \ do { \ - rcu_irq_enter(); \ + rcu_irq_enter(in_nmi); \ account_system_vtime(current); \ add_preempt_count(HARDIRQ_OFFSET); \ trace_hardirq_enter(); \ } while (0) +#define __irq_enter () ____irq_enter(0) +#define __irq_exit () ____irq_exit(0) +/* * Enter irq context (on NO_HZ, update jiffies): */
@@ -148,12 +151,12 @@ extern void irq_enter(void);/* * Exit irq context without processing softirqs: */ -#define __irq_exit () \ +#define ____irq_exit (in_nmi) \ do { \ trace_hardirq_exit(); \ account_system_vtime(current); \ sub_preempt_count(HARDIRQ_OFFSET); \ - rcu_irq_exit(); \ + rcu_irq_exit(in_nmi); \ } while (0)/*
@@ -161,7 +164,7 @@ extern void irq_enter(void);*/ extern void irq_exit (void ); -#define nmi_enter () do { lockdep_off(); __irq_enter(); } while (0) -#define nmi_exit () do { __irq_exit(); lockdep_on(); } while (0) +#define nmi_enter () do { lockdep_off(); ____irq_enter(1); } while (0) +#define nmi_exit () do { ____irq_exit(1); lockdep_on(); } while (0)#endif /* LINUX_HARDIRQ_H */
include/linux/rcuclassic.h +0 -2
@@ -168,8 +168,6 @@ extern struct lockdep_map rcu_lock_map;#define __synchronize_sched () synchronize_rcu() -#define call_rcu_sched (head, func) call_rcu(head, func) -extern void __rcu_init (void );#define rcu_init_sched () do { } while (0)extern void rcu_check_callbacks (int cpu,int user);
include/linux/rcucpumask.h new file +146 -0
146 lines not on this page · raw message
include/linux/rcupdate.h +18 -1
@@ -52,7 +52,9 @@ struct rcu_head {void (*func)(struct rcu_head *head); }; -#ifdef CONFIG_CLASSIC_RCU +#ifdef CONFIG_STATE_RCU +#include <linux/rcustate.h> +#elif CONFIG_CLASSIC_RCU #include <linux/rcuclassic.h> #else /* #ifdef CONFIG_CLASSIC_RCU */ #include <linux/rcupreempt.h>
@@ -263,6 +265,21 @@ extern void call_rcu(struct rcu_head *head,extern void call_rcu_bh (struct rcu_head *head,void (*func)(struct rcu_head *head)); +/** +* call_rcu_sched - Queue RCU callback for invocation after sched grace period. +* @head: structure to be used for queueing the RCU updates. +* @func: actual update function to be invoked after the grace period +* +* The update function will be invoked some time after a full +* synchronize_sched()-style grace period elapses, in other words after +* all currently executing preempt-disabled sections of code (including +* hardirq handlers, NMI handlers, and local_irq_save() blocks) have +* completed. +*/ +extern void call_rcu_sched (struct rcu_head *head, +void (*func)(struct rcu_head *head)); + +/* Exported common interfaces */ extern void synchronize_rcu (void );extern void rcu_barrier (void );
include/linux/rcupreempt.h +0 -14
@@ -65,20 +65,6 @@ static inline void rcu_qsctr_inc(int cpu)*/ #define call_rcu_bh call_rcu -/** -* call_rcu_sched - Queue RCU callback for invocation after sched grace period. -* @head: structure to be used for queueing the RCU updates. -* @func: actual update function to be invoked after the grace period -* -* The update function will be invoked some time after a full -* synchronize_sched()-style grace period elapses, in other words after -* all currently executing preempt-disabled sections of code (including -* hardirq handlers, NMI handlers, and local_irq_save() blocks) have -* completed. -*/ -extern void call_rcu_sched (struct rcu_head *head, -void (*func)(struct rcu_head *head)); - extern void __rcu_read_lock(void) __acquires(RCU); extern void __rcu_read_unlock(void) __releases(RCU);extern int rcu_pending (int cpu);
include/linux/rcustate.h new file +291 -0
291 lines not on this page · raw message
init/Kconfig +11 -1
@@ -924,10 +924,20 @@ source "block/Kconfig" config PREEMPT_NOTIFIERS bool +config STATE_RCU + bool + default y + help + This option selects a state machine based RCU implementation. + It's a replacement for the "classic" rcu implementation that + aims simpler code and better scalability. + If unsure, say N. + config CLASSIC_RCU - def_bool !PREEMPT_RCU + def_bool !PREEMPT_RCU && !STATE_RCU help This option selects the classic RCU implementation that is designed for best read-side performance on non-realtime systems. Classic RCU is the default. Note that the PREEMPT_RCU symbol is used to select/deselect this option. +
kernel/Makefile +1 -0
@@ -76,6 +76,7 @@ obj-$(CONFIG_GENERIC_HARDIRQS) += irq/ obj-$(CONFIG_SECCOMP) += seccomp.o obj-$(CONFIG_RCU_TORTURE_TEST) += rcutorture.o obj-$(CONFIG_CLASSIC_RCU) += rcuclassic.o +obj-$(CONFIG_STATE_RCU) += rcustate.o rcucpumask.o obj-$(CONFIG_PREEMPT_RCU) += rcupreempt.o ifeq ($(CONFIG_PREEMPT_RCU),y) obj-$(CONFIG_RCU_TRACE) += rcupreempt_trace.o
kernel/rcuclassic.c +18 -0
@@ -296,6 +296,13 @@ void call_rcu_bh(struct rcu_head *head, }EXPORT_SYMBOL_GPL (call_rcu_bh); +void call_rcu_sched (struct rcu_head *head, +void (*func)(struct rcu_head *rcu)) +{ +call_rcu (head, func); +} +EXPORT_SYMBOL_GPL (call_rcu_sched); +/* * Return the number of RCU batches processed thus far. Useful * for debug and statistics.
@@ -764,6 +771,17 @@ static struct notifier_block __cpuinitdata rcu_nb = { .notifier_call = rcu_cpu_notify, }; +#ifdef CONFIG_NO_HZ + +void rcu_irq_enter (int in_nmi) +{ +} + +void rcu_irq_exit (int in_nmi) +{ +} +#endif +/* * Initializes rcu mechanism. Assumed to be called early. * That is before local timer(SMP) or jiffie timer (uniproc) is setup.
kernel/rcucpumask.c new file +101 -0
101 lines not on this page · raw message
kernel/rcupreempt.c +3 -3
@@ -434,13 +434,13 @@ DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_dyntick_sched, rcu_dyntick_sched) = { static DEFINE_PER_CPU(int, rcu_update_flag);/** -* rcu_irq_enter - Called from Hard irq handlers and NMI/SMI. +* __rcu_irq_enter - Called from Hard irq handlers and NMI/SMI. * * If the CPU was idle with dynamic ticks active, this updates the * rcu_dyntick_sched.dynticks to let the RCU handling know that the * CPU is active. */ -void rcu_irq_enter (void ) +void __rcu_irq_enter (int in_nmi) {int cpu =smp_processor_id ();struct rcu_dyntick_sched *rdssp = &per_cpu (rcu_dyntick_sched, cpu);
@@ -510,7 +510,7 @@ void rcu_irq_enter(void)* rcu_dyntick_sched.dynticks to put let the RCU handling be * aware that the CPU is going back to idle with no ticks. */ -void rcu_irq_exit (void ) +void __rcu_irq_exit (int in_nmi) {int cpu =smp_processor_id ();struct rcu_dyntick_sched *rdssp = &per_cpu (rcu_dyntick_sched, cpu);
kernel/rcustate.c new file +1211 -0
1,211 lines not on this page · raw message
kernel/softirq.c +1 -1
@@ -293,10 +293,10 @@ void irq_exit(void)invoke_softirq ();#ifdef CONFIG_NO_HZ +rcu_irq_exit (0 );/* Make sure that timer wheel updates are propagated */ if (!in_interrupt () &&idle_cpu (smp_processor_id ()) && !need_resched ())tick_nohz_stop_sched_tick (0 ); -rcu_irq_exit ();#endif preempt_enable_no_resched (); }
Signature · 1 line
1.5.6.5