rcu: preemptible expedited grace periods and cleanups
cover rcu: preemptible expedited grace periods and cleanups
This patchset includes some cleanups, improved diagnostics, and an implementation of expedited preemptible RCU grace periods that is actually expedited:
1. Rename the "quiet" functions. The name rcu_quiet_cpu() was
clear enough, but now that we have four flavors of quietness with more on the way, we need more meaningful names.
2. Enable a fourth level of the rcu_node hierarchy. No, we really
don't need the ability to run on million-CPU SMP systems at the moment, but the additional level allows more vigorous stress-testing on 16-CPU systems.
3. Add an implementation of synchronize_rcu_expedited() that
actually expedites preemptible-RCU grace periods.
4. Make RCU_CPU_STALL_DETECTOR be on by default. If this works
well, the #ifdefs will eventually be removed to reduce testing load.
This patchset is intended for 2.6.34, but has passed sufficient testing that it could safely be included in 2.6.33, if desired.
b/kernel/rcutorture.c | 34 +++++-- b/kernel/rcutree.c | 66 ++++++++------- b/kernel/rcutree.h | 3 b/kernel/rcutree_plugin.h | 13 +-- b/kernel/rcutree_trace.c | 11 +- b/lib/Kconfig.debug | 3 kernel/rcutree.c | 16 ++- kernel/rcutree.h | 51 ++++++++++- kernel/rcutree_plugin.h | 198 +++++++++++++++++++++++++++++++++++++++++++--- 9 files changed, 324 insertions(+), 71 deletions(-)
PATCH 4/4 rcu: make RCU's CPU-stall detector be default
From: Paul E. McKenney <[email protected]>
The RCU_CPU_STALL_DETECTOR costs almost nothing and has located some bugs that might otherwise have been difficult to track down. Make it be default for the TREE RCU implementations. (TINY_RCU does not support CPU-stall detection, but then again it is a uniprocessor...)
--- lib/Kconfig.debug | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
lib/Kconfig.debug +1 -1
@@ -749,7 +749,7 @@ config RCU_TORTURE_TEST_RUNNABLE config RCU_CPU_STALL_DETECTOR bool "Check for stalled CPUs delaying RCU grace periods" depends on TREE_RCU || TREE_PREEMPT_RCU - default n + default y help This option causes RCU to printk information on which CPUs are delaying the current grace period, but only when
Signature · 1 line
1.5.2.5
PATCH 3/4 rcu: add expedited grace-period support for preemptible RCU
In reply to Paul E. McKenneyFrom: Paul E. McKenney <[email protected]>
Implement an synchronize_rcu_expedited() for preemptible RCU that actually is expedited. This uses synchronize_sched_expedited() to force all threads currently running in a preemptible-RCU read-side critical section onto the appropriate ->blocked_tasks[] list, then takes a snapshot of all of these lists and waits for them to drain.
--- kernel/rcutorture.c | 34 ++++++-- kernel/rcutree.c | 10 ++- kernel/rcutree.h | 35 ++++++++- kernel/rcutree_plugin.h | 198 ++++++++++++++++++++++++++++++++++++++++++++-- kernel/rcutree_trace.c | 10 ++- 5 files changed, 260 insertions(+), 27 deletions(-)
kernel/rcutorture.c +25 -9
@@ -327,6 +327,11 @@ rcu_torture_cb(struct rcu_head *p) cur_ops->deferred_free (rp); } +static int rcu_no_completed (void ) +{ +return 0 ; +} +static void rcu_torture_deferred_free (struct rcu_torture *p) {call_rcu (&p->rtort_rcu, rcu_torture_cb);
@@ -388,6 +393,21 @@ static struct rcu_torture_ops rcu_sync_ops = { .name = "rcu_sync" }; +static struct rcu_torture_ops rcu_expedited_ops = { + .init = rcu_sync_torture_init, + .cleanup =NULL , + .readlock = rcu_torture_read_lock, + .read_delay = rcu_read_delay,/* just reuse rcu's version. */ + .readunlock = rcu_torture_read_unlock, + .completed = rcu_no_completed, + .deferred_free = rcu_sync_torture_deferred_free, + .sync = synchronize_rcu_expedited, + .cb_barrier =NULL , + .stats =NULL , + .irq_capable =1 , + .name ="rcu_expedited" +}; +/* * Definitions for rcu_bh torture testing. */
@@ -581,11 +601,6 @@ static void sched_torture_read_unlock(int idx)preempt_enable (); } -static int sched_torture_completed (void ) -{ -return 0 ; -} -static void rcu_sched_torture_deferred_free (struct rcu_torture *p) {call_rcu_sched (&p->rtort_rcu, rcu_torture_cb);
@@ -602,7 +617,7 @@ static struct rcu_torture_ops sched_ops = { .readlock = sched_torture_read_lock, .read_delay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = sched_torture_read_unlock, - .completed = sched_torture_completed, + .completed = rcu_no_completed, .deferred_free = rcu_sched_torture_deferred_free, .sync = sched_torture_synchronize, .cb_barrier = rcu_barrier_sched,
@@ -617,7 +632,7 @@ static struct rcu_torture_ops sched_sync_ops = { .readlock = sched_torture_read_lock, .read_delay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = sched_torture_read_unlock, - .completed = sched_torture_completed, + .completed = rcu_no_completed, .deferred_free = rcu_sync_torture_deferred_free, .sync = sched_torture_synchronize, .cb_barrier = NULL,
@@ -631,7 +646,7 @@ static struct rcu_torture_ops sched_expedited_ops = { .readlock = sched_torture_read_lock, .read_delay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = sched_torture_read_unlock, - .completed = sched_torture_completed, + .completed = rcu_no_completed, .deferred_free = rcu_sync_torture_deferred_free, .sync = synchronize_sched_expedited, .cb_barrier = NULL,
@@ -1116,7 +1131,8 @@ rcu_torture_init(void)int cpu;int firsterr =0 ;static struct rcu_torture_ops *torture_ops[] = - { &rcu_ops, &rcu_sync_ops, &rcu_bh_ops, &rcu_bh_sync_ops, + { &rcu_ops, &rcu_sync_ops, &rcu_expedited_ops, + &rcu_bh_ops, &rcu_bh_sync_ops, &srcu_ops, &srcu_expedited_ops, &sched_ops, &sched_sync_ops, &sched_expedited_ops, };
kernel/rcutree.c +7 -3
@@ -948,7 +948,7 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp) {unsigned long flags;unsigned long mask; -int need_quiet =0 ; +int need_report =0 ;struct rcu_data *rdp = rsp->rda[cpu];struct rcu_node *rnp;
@@ -967,7 +967,7 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)break ; }if (rnp == rdp->mynode) - need_quiet =rcu_preempt_offline_tasks (rsp, rnp, rdp); + need_report =rcu_preempt_offline_tasks (rsp, rnp, rdp);else spin_unlock (&rnp->lock);/* irqs remain disabled. */ mask = rnp->grpmask;
@@ -982,10 +982,12 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)*/ spin_unlock (&rsp->onofflock);/* irqs remain disabled. */ rnp = rdp->mynode; -if (need_quiet) +if (need_report &RCU_OFL_TASKS_NORM_GP )rcu_report_unblock_qs_rnp (rnp, flags);else spin_unlock_irqrestore (&rnp->lock, flags); +if (need_report &RCU_OFL_TASKS_EXP_GP ) +rcu_report_exp_rnp (rsp, rnp);rcu_adopt_orphan_cbs (rsp); }
@@ -1843,6 +1845,8 @@ static void __init rcu_init_one(struct rcu_state *rsp) rnp->level = i;INIT_LIST_HEAD (&rnp->blocked_tasks[0 ]);INIT_LIST_HEAD (&rnp->blocked_tasks[1 ]); +INIT_LIST_HEAD (&rnp->blocked_tasks[2 ]); +INIT_LIST_HEAD (&rnp->blocked_tasks[3 ]); } } }
kernel/rcutree.h +32 -3
@@ -104,8 +104,12 @@ struct rcu_node {/* an rcu_data structure, otherwise, each */ /* bit corresponds to a child rcu_node */ /* structure. */ +unsigned long expmask;/* Groups that have ->blocked_tasks[] */ +/* elements that need to drain to allow the */ +/* current expedited grace period to */ +/* complete (only for TREE_PREEMPT_RCU). */ unsigned long qsmaskinit; -/* Per-GP initialization for qsmask. */ +/* Per-GP initial value for qsmask & expmask. */ unsigned long grpmask;/* Mask to apply to parent qsmask. */ /* Only one bit will be set in this mask. */ int grplo;/* lowest-numbered CPU or group here. */
@@ -113,7 +117,7 @@ struct rcu_node {u8 grpnum;/* CPU/group number for next level up. */ u8 level;/* root is at level 0. */ struct rcu_node *parent; -struct list_head blocked_tasks[2 ]; +struct list_head blocked_tasks[4 ];/* Tasks blocked in RCU read-side critsect. */ /* Grace period number (->gpnum) x blocked */ /* by tasks on the (x & 0x1) element of the */
@@ -128,6 +132,21 @@ struct rcu_node {for ((rnp) = &(rsp)->node[0 ]; \ (rnp) < &(rsp)->node[NUM_RCU_NODES ]; (rnp)++) +/* +* Do a breadth-first scan of the non-leaf rcu_node structures for the +* specified rcu_state structure. Note that if there is a singleton +* rcu_node tree with but one rcu_node structure, this loop is a no-op. + */ +#define rcu_for_each_nonleaf_node_breadth_first (rsp, rnp) \ + for ((rnp) = &(rsp)->node[0]; \ + (rnp) < (rsp)->level[NUM_RCU_LVLS - 1]; (rnp)++) + +/* +* Scan the leaves of the rcu_node hierarchy for the specified rcu_state +* structure. Note that if there is a singleton rcu_node tree with but +* one rcu_node structure, this loop -will- visit the rcu_node structure. +* It is still a leaf node, even if it is also the root node. +*/ #define rcu_for_each_leaf_node (rsp, rnp) \ for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \ (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)
@@ -261,7 +280,7 @@ struct rcu_state {long gpnum;/* Current gp number. */ long completed;/* # of last completed gp. */ -/* End of fields guarded by root rcu_node's lock. */ +/* End of fields guarded by root rcu_node's lock. */ spinlock_t onofflock;/* exclude on/offline and */ /* starting new GP. Also */
@@ -293,6 +312,13 @@ struct rcu_state {#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ }; +/* Return values for rcu_preempt_offline_tasks(). */ + +#define RCU_OFL_TASKS_NORM_GP 0x1/* Tasks blocking normal */ +/* GP were moved to root. */ +#define RCU_OFL_TASKS_EXP_GP 0x2/* Tasks blocking expedited */ +/* GP were moved to root. */ +#ifdef RCU_TREE_NONCORE /*
@@ -333,6 +359,9 @@ static void rcu_preempt_offline_cpu(int cpu);static void rcu_preempt_check_callbacks (int cpu);static void rcu_preempt_process_callbacks (void );void call_rcu (struct rcu_head *head,void (*func)(struct rcu_head *rcu)); +#if defined(CONFIG_HOTPLUG_CPU ) || defined(CONFIG_TREE_PREEMPT_RCU ) +static void rcu_report_exp_rnp (struct rcu_state *rsp,struct rcu_node *rnp); +#endif /* #if defined(CONFIG_HOTPLUG_CPU) || defined(CONFIG_TREE_PREEMPT_RCU) */ static int rcu_preempt_pending (int cpu);static int rcu_preempt_needs_cpu (int cpu);static void __cpuinit rcu_preempt_init_percpu_data (int cpu);
kernel/rcutree_plugin.h +189 -9
268 lines not on this page · raw message
kernel/rcutree_trace.c +7 -3
@@ -157,6 +157,7 @@ static void print_one_rcu_state(struct seq_file *m, struct rcu_state *rsp) {long gpnum;int level =0 ; +int phase;struct rcu_node *rnp; gpnum = rsp->gpnum;
@@ -173,10 +174,13 @@ static void print_one_rcu_state(struct seq_file *m, struct rcu_state *rsp)seq_puts (m,"\n" ); level = rnp->level; } -seq_printf (m,"%lx/%lx %c>%c %d:%d ^%d " , + phase = gpnum &0x1 ; +seq_printf (m,"%lx/%lx %c%c>%c%c %d:%d ^%d " , rnp->qsmask, rnp->qsmaskinit, -"T." [list_empty (&rnp->blocked_tasks[gpnum &1 ])], -"T." [list_empty (&rnp->blocked_tasks[!(gpnum &1 )])], +"T." [list_empty (&rnp->blocked_tasks[phase])], +"E." [list_empty (&rnp->blocked_tasks[phase +2 ])], +"T." [list_empty (&rnp->blocked_tasks[!phase])], +"E." [list_empty (&rnp->blocked_tasks[!phase +2 ])], rnp->grplo, rnp->grphi, rnp->grpnum); }seq_puts (m,"\n" );
Signature · 1 line
1.5.2.5
PATCH 2/4 rcu: enable fourth level of TREE_RCU hierarchy
In reply to Paul E. McKenneyFrom: Paul E. McKenney <[email protected]>
Enable a fourth level of rcu_node hierarchy for TREE_RCU and TREE_PREEMPT_RCU. This is for stress-testing and experiemental purposes only, although in theory this would enable 16,777,216 CPUs on 64-bit systems, though only 1,048,576 CPUs on 32-bit systems. Normal experimental use of this fourth level will normally set CONFIG_RCU_FANOUT=2, requiring a 16-CPU system, though the more adventurous (and more fortunate) experimenters may wish to chose CONFIG_RCU_FANOUT=3 for 81-CPU systems or even CONFIG_RCU_FANOUT=4 for 256-CPU systems.
--- kernel/rcutree.c | 6 +++++- kernel/rcutree.h | 15 +++++++++++++-- 2 files changed, 18 insertions(+), 3 deletions(-)
kernel/rcutree.c +5 -1
@@ -60,7 +60,8 @@ static struct lock_class_key rcu_node_class[NUM_RCU_LVLS];NUM_RCU_LVL_0 ,/* root of hierarchy. */ \NUM_RCU_LVL_1 , \NUM_RCU_LVL_2 , \ -NUM_RCU_LVL_3 ,/* == MAX_RCU_LVLS */ \ +NUM_RCU_LVL_3 , \ +NUM_RCU_LVL_4 ,/* == MAX_RCU_LVLS */ \ }, \ .signaled = RCU_GP_IDLE, \ .gpnum = -300, \
@@ -1877,6 +1878,9 @@ void __init rcu_init(void)#ifdef CONFIG_RCU_CPU_STALL_DETECTOR printk (KERN_INFO "RCU-based detection of stalled CPUs is enabled.\n" );#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ +#if NUM_RCU_LVL_4 !=0 +printk (KERN_INFO "Experimental four-level hierarchy is enabled.\n" ); +#endif /* #if NUM_RCU_LVL_4 != 0 */ RCU_INIT_FLAVOR (&rcu_sched_state, rcu_sched_data);RCU_INIT_FLAVOR (&rcu_bh_state, rcu_bh_data);__rcu_init_preempt ();
kernel/rcutree.h +13 -2
@@ -34,10 +34,11 @@* In practice, this has not been tested, so there is probably some * bug somewhere. */ -#define MAX_RCU_LVLS 3 +#define MAX_RCU_LVLS 4#define RCU_FANOUT (CONFIG_RCU_FANOUT)#define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT)#define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT) +#define RCU_FANOUT_FOURTH (RCU_FANOUT_CUBE * RCU_FANOUT)#if NR_CPUS <=RCU_FANOUT # define NUM_RCU_LVLS 1
@@ -45,23 +46,33 @@# define NUM_RCU_LVL_1 (NR_CPUS)# define NUM_RCU_LVL_2 0# define NUM_RCU_LVL_3 0 +# define NUM_RCU_LVL_4 0#elif NR_CPUS <=RCU_FANOUT_SQ # define NUM_RCU_LVLS 2# define NUM_RCU_LVL_0 1# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT)# define NUM_RCU_LVL_2 (NR_CPUS)# define NUM_RCU_LVL_3 0 +# define NUM_RCU_LVL_4 0#elif NR_CPUS <=RCU_FANOUT_CUBE # define NUM_RCU_LVLS 3# define NUM_RCU_LVL_0 1# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_SQ)# define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT)# define NUM_RCU_LVL_3 NR_CPUS +# define NUM_RCU_LVL_4 0 +#elif NR_CPUS <=RCU_FANOUT_FOURTH +# define NUM_RCU_LVLS 4 +# define NUM_RCU_LVL_0 1 +# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_CUBE) +# define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_SQ) +# define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT) +# define NUM_RCU_LVL_4 NR_CPUS#else # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"#endif /* #if (NR_CPUS) <= RCU_FANOUT */ -#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3) +#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3 + NUM_RCU_LVL_4)#define NUM_RCU_NODES (RCU_SUM - NR_CPUS)/*
Signature · 1 line
1.5.2.5
PATCH 1/4 rcu: rename "quiet" functions
In reply to Paul E. McKenneyThe number of "quiet" functions has grown recently, and the names are no longer very descriptive. The point of all of these functions is to do some portion of the task of reporting a quiescent state, so rename them accordingly:
o cpu_quiet() becomes rcu_report_qs_rdp(), which reports a
quiescent state to the per-CPU rcu_data structure. If this turns out to be a new quiescent state for this grace period, then rcu_report_qs_rnp() will be invoked to propagate the quiescent state up the rcu_node hierarchy.
o cpu_quiet_msk() becomes rcu_report_qs_rnp(), which reports
a quiescent state for a given CPU (or possibly a set of CPUs) up the rcu_node hierarchy.
o cpu_quiet_msk_finish() becomes rcu_report_qs_rsp(), which
reports a full set of quiescent states to the global rcu_state structure.
o task_quiet() becomes rcu_report_unblock_qs_rnp(), which reports
a quiescent state due to a task exiting an RCU read-side critical section that had previously blocked in that same critical section. As indicated by the new name, this type of quiescent state is reported up the rcu_node hierarchy (using rcu_report_qs_rnp() to do so).
--- kernel/rcutree.c | 66 ++++++++++++++++++++++++++-------------------- kernel/rcutree.h | 3 +- kernel/rcutree_plugin.h | 12 ++++---- 3 files changed, 45 insertions(+), 36 deletions(-)
kernel/rcutree.c +37 -29
@@ -740,11 +740,13 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags) }/* -* Clean up after the prior grace period and let rcu_start_gp() start up -* the next grace period if one is needed. Note that the caller must -* hold rnp->lock, as required by rcu_start_gp(), which will release it. +* Report a full set of quiescent states to the specified rcu_state +* data structure. This involves cleaning up after the prior grace +* period and letting rcu_start_gp() start up the next grace period +* if one is needed. Note that the caller must hold rnp->lock, as +* required by rcu_start_gp(), which will release it. */ -static void cpu_quiet_msk_finish (struct rcu_state *rsp,unsigned long flags) +static void rcu_report_qs_rsp (struct rcu_state *rsp,unsigned long flags) __releases(rcu_get_root(rsp)->lock) {WARN_ON_ONCE (!rcu_gp_in_progress (rsp));
@@ -754,15 +756,16 @@ static void cpu_quiet_msk_finish(struct rcu_state *rsp, unsigned long flags) }/* -* Similar to cpu_quiet(), for which it is a helper function. Allows -* a group of CPUs to be quieted at one go, though all the CPUs in the -* group must be represented by the same leaf rcu_node structure. -* That structure's lock must be held upon entry, and it is released -* before return. +* Similar to rcu_report_qs_rdp(), for which it is a helper function. +* Allows quiescent states for a group of CPUs to be reported at one go +* to the specified rcu_node structure, though all the CPUs in the group +* must be represented by the same rcu_node structure (which need not be +* a leaf rcu_node structure, though it often will be). That structure's +* lock must be held upon entry, and it is released before return. */ static void -cpu_quiet_msk (unsigned long mask,struct rcu_state *rsp,struct rcu_node *rnp, -unsigned long flags) +rcu_report_qs_rnp (unsigned long mask,struct rcu_state *rsp, +struct rcu_node *rnp,unsigned long flags) __releases(rnp->lock) {struct rcu_node *rnp_c;
@@ -798,21 +801,23 @@ cpu_quiet_msk(unsigned long mask, struct rcu_state *rsp, struct rcu_node *rnp,/* * Get here if we are the last CPU to pass through a quiescent -* state for this grace period. Invoke cpu_quiet_msk_finish() +* state for this grace period. Invoke rcu_report_qs_rsp() * to clean up and start the next grace period if one is needed. */ -cpu_quiet_msk_finish (rsp, flags);/* releases rnp->lock. */ +rcu_report_qs_rsp (rsp, flags);/* releases rnp->lock. */ }/* -* Record a quiescent state for the specified CPU, which must either be -* the current CPU. The lastcomp argument is used to make sure we are -* still in the grace period of interest. We don't want to end the current -* grace period based on quiescent states detected in an earlier grace -* period! +* Record a quiescent state for the specified CPU to that CPU's rcu_data +* structure. This must be either called from the specified CPU, or +* called when the specified CPU is known to be offline (and when it is +* also known that no other CPU is concurrently trying to help the offline +* CPU). The lastcomp argument is used to make sure we are still in the +* grace period of interest. We don't want to end the current grace period +* based on quiescent states detected in an earlier grace period! */ static void -cpu_quiet (int cpu,struct rcu_state *rsp,struct rcu_data *rdp,long lastcomp) +rcu_report_qs_rdp (int cpu,struct rcu_state *rsp,struct rcu_data *rdp,long lastcomp) {unsigned long flags;unsigned long mask;
@@ -827,8 +832,8 @@ cpu_quiet(int cpu, struct rcu_state *rsp, struct rcu_data *rdp, long lastcomp)* The race with GP start is resolved by the fact that we * hold the leaf rcu_node lock, so that the per-CPU bits * cannot yet be initialized -- so we would simply find our -* CPU's bit already cleared in cpu_quiet_msk() if this race -* occurred. +* CPU's bit already cleared in rcu_report_qs_rnp() if this +* race occurred. */ rdp->passed_quiesc =0 ;/* try again later! */ spin_unlock_irqrestore (&rnp->lock, flags);
@@ -846,7 +851,7 @@ cpu_quiet(int cpu, struct rcu_state *rsp, struct rcu_data *rdp, long lastcomp)*/ rdp->nxttail[RCU_NEXT_READY_TAIL ] = rdp->nxttail[RCU_NEXT_TAIL ]; -cpu_quiet_msk (mask, rsp, rnp, flags);/* releases rnp->lock */ +rcu_report_qs_rnp (mask, rsp, rnp, flags);/* rlses rnp->lock */ } }
@@ -877,8 +882,11 @@ rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)if (!rdp->passed_quiesc)return ; -/* Tell RCU we are done (but cpu_quiet() will be the judge of that). */ -cpu_quiet (rdp->cpu, rsp, rdp, rdp->passed_quiesc_completed); +/* +* Tell RCU we are done (but rcu_report_qs_rdp() will be the +* judge of that). +*/ +rcu_report_qs_rdp (rdp->cpu, rsp, rdp, rdp->passed_quiesc_completed); }#ifdef CONFIG_HOTPLUG_CPU
@@ -968,13 +976,13 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)/* * We still hold the leaf rcu_node structure lock here, and * irqs are still disabled. The reason for this subterfuge is -* because invoking task_quiet() with ->onofflock held leads -* to deadlock. +* because invoking rcu_report_unblock_qs_rnp() with ->onofflock +* held leads to deadlock. */ spin_unlock (&rsp->onofflock);/* irqs remain disabled. */ rnp = rdp->mynode;if (need_quiet) -task_quiet (rnp, flags); +rcu_report_unblock_qs_rnp (rnp, flags);else spin_unlock_irqrestore (&rnp->lock, flags);
@@ -1164,8 +1172,8 @@ static int rcu_process_dyntick(struct rcu_state *rsp, long lastcomp, }if (mask !=0 && rnp->completed == lastcomp) { -/* cpu_quiet_msk() releases rnp->lock. */ -cpu_quiet_msk (mask, rsp, rnp, flags); +/* rcu_report_qs_rnp() releases rnp->lock. */ +rcu_report_qs_rnp (mask, rsp, rnp, flags);continue ; }spin_unlock_irqrestore (&rnp->lock, flags);
kernel/rcutree.h +2 -1
@@ -306,7 +306,8 @@ long rcu_batches_completed(void);static void rcu_preempt_note_context_switch (int cpu);static int rcu_preempted_readers (struct rcu_node *rnp);#ifdef CONFIG_HOTPLUG_CPU -static void task_quiet (struct rcu_node *rnp,unsigned long flags); +static void rcu_report_unblock_qs_rnp (struct rcu_node *rnp, +unsigned long flags);#endif /* #ifdef CONFIG_HOTPLUG_CPU */ #ifdef CONFIG_RCU_CPU_STALL_DETECTOR static void rcu_print_task_stall (struct rcu_node *rnp);
kernel/rcutree_plugin.h +6 -6
@@ -167,7 +167,7 @@ static int rcu_preempted_readers(struct rcu_node *rnp)* irqs disabled, and this lock is released upon return, but irqs remain * disabled. */ -static void task_quiet (struct rcu_node *rnp,unsigned long flags) +static void rcu_report_unblock_qs_rnp (struct rcu_node *rnp,unsigned long flags) __releases(rnp->lock) {unsigned long mask;
@@ -185,7 +185,7 @@ static void task_quiet(struct rcu_node *rnp, unsigned long flags)* or tasks were kicked up to root rcu_node due to * CPUs going offline. */ -cpu_quiet_msk_finish (&rcu_preempt_state, flags); +rcu_report_qs_rsp (&rcu_preempt_state, flags);return ; }
@@ -193,7 +193,7 @@ static void task_quiet(struct rcu_node *rnp, unsigned long flags) mask = rnp->grpmask;spin_unlock (&rnp->lock);/* irqs remain disabled. */ spin_lock (&rnp_p->lock);/* irqs already disabled. */ -cpu_quiet_msk (mask, &rcu_preempt_state, rnp_p, flags); +rcu_report_qs_rnp (mask, &rcu_preempt_state, rnp_p, flags); }/*
@@ -253,12 +253,12 @@ static void rcu_read_unlock_special(struct task_struct *t)/* * If this was the last task on the current list, and if * we aren't waiting on any CPUs, report the quiescent state. -* Note that task_quiet() releases rnp->lock. +* Note that rcu_report_unblock_qs_rnp() releases rnp->lock. */ if (empty)spin_unlock_irqrestore (&rnp->lock, flags);else -task_quiet (rnp, flags); +rcu_report_unblock_qs_rnp (rnp, flags); }else {local_irq_restore (flags); }
@@ -566,7 +566,7 @@ static int rcu_preempted_readers(struct rcu_node *rnp)#ifdef CONFIG_HOTPLUG_CPU /* Because preemptible RCU does not exist, no quieting of tasks. */ -static void task_quiet (struct rcu_node *rnp,unsigned long flags) +static void rcu_report_unblock_qs_rnp (struct rcu_node *rnp,unsigned long flags) {spin_unlock_irqrestore (&rnp->lock, flags); }
Signature · 1 line
1.5.2.5
Re: [PATCH tip/core/rcu 1/4] rcu: rename "quiet" functions
Quoted 19 lines · Paul E. McKenney
The number of "quiet" functions has grown recently, and the names are no longer very descriptive. The point of all of these functions is to do some portion of the task of reporting a quiescent state, so rename them accordingly:
o
cpu_quiet()becomesrcu_report_qs_rdp(), which reports a
quiescent state to the per-CPUrcu_datastructure. If this turns out to be a new quiescent state for this grace period, thenrcu_report_qs_rnp()will be invoked to propagate the quiescent state up thercu_nodehierarchy.o
cpu_quiet_msk()becomesrcu_report_qs_rnp(), which reports
a quiescent state for a given CPU (or possibly a set of CPUs) up thercu_nodehierarchy.o
cpu_quiet_msk_finish()becomesrcu_report_qs_rsp(), which
reports a full set of quiescent states to the globalrcu_statestructure.
Quoted 8 lines
o
task_quiet()becomesrcu_report_unblock_qs_rnp(), which reports
a quiescent state due to a task exiting an RCU read-side critical section that had previously blocked in that same critical section. As indicated by the new name, this type of quiescent state is reported up thercu_nodehierarchy (usingrcu_report_qs_rnp()to do so).Signed-off-by Paul E. McKenney <[email protected]>
*Huge* improvement in terminology.
Re: [PATCH tip/core/rcu 2/4] rcu: enable fourth level of TREE_RCU hierarchy
In reply to Paul E. McKenneyQuoted 12 lines · Paul E. McKenney
From: Paul E. McKenney <[email protected]>
Enable a fourth level of
rcu_nodehierarchy forTREE_RCUandTREE_PREEMPT_RCU. This is for stress-testing and experiemental purposes only, although in theory this would enable 16,777,216 CPUs on 64-bit systems, though only 1,048,576 CPUs on 32-bit systems. Normal experimental use of this fourth level will normally setCONFIG_RCU_FANOUT=2, requiring a 16-CPU system, though the more adventurous (and more fortunate) experimenters may wish to choseCONFIG_RCU_FANOUT=3for 81-CPU systems or evenCONFIG_RCU_FANOUT=4for 256-CPU systems.
Quoted 1 line
Signed-off-by Paul E. McKenney <[email protected]>
I like this idea in general, but I have one suggestion on your boot-up message:
Quoted 2 lines
kernel/rcutree.c +0
-0
[...]
kernel/rcutree.c void __init rcu_init(void) · line 1883
Quoted 7 lines
kernel/rcutree.c +3
-0@@ -1877,6 +1878,9 @@ void __init rcu_init(void)#ifdef CONFIG_RCU_CPU_STALL_DETECTOR printk (KERN_INFO "RCU-based detection of stalled CPUs is enabled.\n" );#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ +#if NUM_RCU_LVL_4 !=0 +printk (KERN_INFO "Experimental four-level hierarchy is enabled.\n" ); +#endif /* #if NUM_RCU_LVL_4 != 0 */
Rather than printing a message when people use the four-level hierarchy, how about just printing a message any time someone has set CONFIG_RCU_FANOUT manually rather than automatically, and including NR_CPUS in that message? That should only occur when testing or when trying to do NUMA optimization, and either way it seems worth noting.
Either way the change seems fine to me. With or without that suggested change:
Re: [PATCH tip/core/rcu 2/4] rcu: enable fourth level of TREE_RCU hierarchy
Quoted 21 lines · Josh Triplett
Quoted 12 lines · Paul E. McKenney
From: Paul E. McKenney <[email protected]>
Enable a fourth level of
rcu_nodehierarchy forTREE_RCUandTREE_PREEMPT_RCU. This is for stress-testing and experiemental purposes only, although in theory this would enable 16,777,216 CPUs on 64-bit systems, though only 1,048,576 CPUs on 32-bit systems. Normal experimental use of this fourth level will normally setCONFIG_RCU_FANOUT=2, requiring a 16-CPU system, though the more adventurous (and more fortunate) experimenters may wish to choseCONFIG_RCU_FANOUT=3for 81-CPU systems or evenCONFIG_RCU_FANOUT=4for 256-CPU systems.Quoted 1 line
Signed-off-by Paul E. McKenney <[email protected]>I like this idea in general, but I have one suggestion on your boot-up message:
Quoted 2 lines
kernel/rcutree.c +0
-0[...]
Quoted 13 lines
kernel/rcutree.c void __init rcu_init(void) · line 1883
Quoted 7 lines
kernel/rcutree.c +3
-0@@ -1877,6 +1878,9 @@ void __init rcu_init(void)#ifdef CONFIG_RCU_CPU_STALL_DETECTOR printk (KERN_INFO "RCU-based detection of stalled CPUs is enabled.\n" );#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ +#if NUM_RCU_LVL_4 !=0 +printk (KERN_INFO "Experimental four-level hierarchy is enabled.\n" ); +#endif /* #if NUM_RCU_LVL_4 != 0 */ Rather than printing a message when people use the four-level hierarchy, how about just printing a message any time someone has set
CONFIG_RCU_FANOUTmanually rather than automatically, and includingNR_CPUSin that message? That should only occur when testing or when trying to do NUMA optimization, and either way it seems worth noting.
Good point! I will keep this patch as is, but I like the idea of having RCU note anything unusual at boot time, and so have added this to my todo list. Of course, if CONFIG_RCU_FANOUT starts getting set low as a matter of course for any (good) reason, then the definition of "anything unusual" would change, and hence the code would also change.
Quoted 4 lines
Either way the change seems fine to me. With or without that suggested change:
Acked-by Josh Triplett <[email protected]>
Thank you!
Thanx, Paul
Quoted 16 lines · Paul E. McKenney
This patchset includes some cleanups, improved diagnostics, and an implementation of expedited preemptible RCU grace periods that is actually expedited:
1. Rename the "quiet" functions. The name
rcu_quiet_cpu()was
clear enough, but now that we have four flavors of quietness with more on the way, we need more meaningful names.2. Enable a fourth level of the
rcu_nodehierarchy. No, we really
don't need the ability to run on million-CPU SMP systems at the moment, but the additional level allows more vigorous stress-testing on 16-CPU systems.3. Add an implementation of
synchronize_rcu_expedited()that
actually expedites preemptible-RCU grace periods.
Quoted 7 lines
4. Make
RCU_CPU_STALL_DETECTORbe on by default. If this works
well, the #ifdefs will eventually be removed to reduce testing load.This patchset is intended for 2.6.34, but has passed sufficient testing that it could safely be included in 2.6.33, if desired.
Ack for the whole patchset except [PATCH 3/4]
Re: [PATCH tip/core/rcu 3/4] rcu: add expedited grace-period support for preemptible RCU
In reply to Paul E. McKenneyQuoted 11 lines · Paul E. McKenney
From: Paul E. McKenney <[email protected]>
Implement an
synchronize_rcu_expedited()for preemptible RCU that actually is expedited. This usessynchronize_sched_expedited()to force all threads currently running in a preemptible-RCU read-side critical section onto the appropriate ->blocked_tasks[] list, then takes a snapshot of all of these lists and waits for them to drain.3. Add an implementation of
synchronize_rcu_expedited()that
actually expedites preemptible-RCU grace periods.
It's very nice.
But I don't understand all things.
1) Why it can be speeded up (in theory)? synchronize_sched_expedited() does speed up, it is due to migration_threads are the most highest priority threads.
But for synchronize_rcu_expedited(), some preempted tasks in ->blocked_tasks[] may be waiting at runqueue for long long time because some other higher priority threads comes.
simply comparison:synchronize_sched_expedited()
==> wake_up_process(rq->migration_thread) to force schedule on cpus.
which forces read-sides notify the end earlier, or we can say "it forces read-sides run to end faster"
synchronize_rcu_expedited()
==> Nothing to force preempted read-site run to end faster.
2) Why we introduce a API which no one use it.
I remember that Net guys request a expedited synchronize_rcu(). but currently there is still no one use it.
Beware my thinking may be wrong!
Thanks, Lai
[tip:core/rcu] rcu: Enable fourth level of TREE_RCU hierarchy
In reply to Paul E. McKenneyCommit-ID: cf244dc01bf68e1ad338b82447f8686d24ea4435 Gitweb: http://git.kernel.org/tip/cf244dc01bf68e1ad338b82447f8686d24ea4435 Author: Paul E. McKenney <[email protected]> AuthorDate: Wed, 2 Dec 2009 12:10:14 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 3 Dec 2009 11:34:53 +0100
rcu: Enable fourth level of TREE_RCU hierarchy
Enable a fourth level of rcu_node hierarchy for TREE_RCU and TREE_PREEMPT_RCU. This is for stress-testing and experiemental purposes only, although in theory this would enable 16,777,216 CPUs on 64-bit systems, though only 1,048,576 CPUs on 32-bit systems. Normal experimental use of this fourth level will normally set CONFIG_RCU_FANOUT=2, requiring a 16-CPU system, though the more adventurous (and more fortunate) experimenters may wish to chose CONFIG_RCU_FANOUT=3 for 81-CPU systems or even CONFIG_RCU_FANOUT=4 for 256-CPU systems.
LKML-Reference: <12597846161257-git-send-email->
--- kernel/rcutree.c | 6 +++++- kernel/rcutree.h | 15 +++++++++++++-- 2 files changed, 18 insertions(+), 3 deletions(-)
kernel/rcutree.c +5 -1
@@ -60,7 +60,8 @@ static struct lock_class_key rcu_node_class[NUM_RCU_LVLS];NUM_RCU_LVL_0 ,/* root of hierarchy. */ \NUM_RCU_LVL_1 , \NUM_RCU_LVL_2 , \ -NUM_RCU_LVL_3 ,/* == MAX_RCU_LVLS */ \ +NUM_RCU_LVL_3 , \ +NUM_RCU_LVL_4 ,/* == MAX_RCU_LVLS */ \ }, \ .signaled = RCU_GP_IDLE, \ .gpnum = -300, \
@@ -1877,6 +1878,9 @@ void __init rcu_init(void)#ifdef CONFIG_RCU_CPU_STALL_DETECTOR printk (KERN_INFO "RCU-based detection of stalled CPUs is enabled.\n" );#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ +#if NUM_RCU_LVL_4 !=0 +printk (KERN_INFO "Experimental four-level hierarchy is enabled.\n" ); +#endif /* #if NUM_RCU_LVL_4 != 0 */ RCU_INIT_FLAVOR (&rcu_sched_state, rcu_sched_data);RCU_INIT_FLAVOR (&rcu_bh_state, rcu_bh_data);__rcu_init_preempt ();
kernel/rcutree.h +13 -2
@@ -34,10 +34,11 @@* In practice, this has not been tested, so there is probably some * bug somewhere. */ -#define MAX_RCU_LVLS 3 +#define MAX_RCU_LVLS 4#define RCU_FANOUT (CONFIG_RCU_FANOUT)#define RCU_FANOUT_SQ (RCU_FANOUT * RCU_FANOUT)#define RCU_FANOUT_CUBE (RCU_FANOUT_SQ * RCU_FANOUT) +#define RCU_FANOUT_FOURTH (RCU_FANOUT_CUBE * RCU_FANOUT)#if NR_CPUS <=RCU_FANOUT # define NUM_RCU_LVLS 1
@@ -45,23 +46,33 @@# define NUM_RCU_LVL_1 (NR_CPUS)# define NUM_RCU_LVL_2 0# define NUM_RCU_LVL_3 0 +# define NUM_RCU_LVL_4 0#elif NR_CPUS <=RCU_FANOUT_SQ # define NUM_RCU_LVLS 2# define NUM_RCU_LVL_0 1# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT)# define NUM_RCU_LVL_2 (NR_CPUS)# define NUM_RCU_LVL_3 0 +# define NUM_RCU_LVL_4 0#elif NR_CPUS <=RCU_FANOUT_CUBE # define NUM_RCU_LVLS 3# define NUM_RCU_LVL_0 1# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_SQ)# define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT)# define NUM_RCU_LVL_3 NR_CPUS +# define NUM_RCU_LVL_4 0 +#elif NR_CPUS <=RCU_FANOUT_FOURTH +# define NUM_RCU_LVLS 4 +# define NUM_RCU_LVL_0 1 +# define NUM_RCU_LVL_1 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_CUBE) +# define NUM_RCU_LVL_2 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT_SQ) +# define NUM_RCU_LVL_3 DIV_ROUND_UP(NR_CPUS, RCU_FANOUT) +# define NUM_RCU_LVL_4 NR_CPUS#else # error "CONFIG_RCU_FANOUT insufficient for NR_CPUS"#endif /* #if (NR_CPUS) <= RCU_FANOUT */ -#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3) +#define RCU_SUM (NUM_RCU_LVL_0 + NUM_RCU_LVL_1 + NUM_RCU_LVL_2 + NUM_RCU_LVL_3 + NUM_RCU_LVL_4)#define NUM_RCU_NODES (RCU_SUM - NR_CPUS)/*
[tip:core/rcu] rcu: Rename "quiet" functions
In reply to Paul E. McKenneyCommit-ID: d3f6bad3911736e44ba11f3f3f6ac4e8c837fdfc Gitweb: http://git.kernel.org/tip/d3f6bad3911736e44ba11f3f3f6ac4e8c837fdfc Author: Paul E. McKenney <[email protected]> AuthorDate: Wed, 2 Dec 2009 12:10:13 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 3 Dec 2009 11:34:26 +0100
rcu: Rename "quiet" functions
The number of "quiet" functions has grown recently, and the names are no longer very descriptive. The point of all of these functions is to do some portion of the task of reporting a quiescent state, so rename them accordingly:
o cpu_quiet() becomes rcu_report_qs_rdp(), which reports a
quiescent state to the per-CPU rcu_data structure. If this turns out to be a new quiescent state for this grace period, then rcu_report_qs_rnp() will be invoked to propagate the quiescent state up the rcu_node hierarchy.
o cpu_quiet_msk() becomes rcu_report_qs_rnp(), which reports
a quiescent state for a given CPU (or possibly a set of CPUs) up the rcu_node hierarchy.
o cpu_quiet_msk_finish() becomes rcu_report_qs_rsp(), which
reports a full set of quiescent states to the global rcu_state structure.
o task_quiet() becomes rcu_report_unblock_qs_rnp(), which reports
a quiescent state due to a task exiting an RCU read-side critical section that had previously blocked in that same critical section. As indicated by the new name, this type of quiescent state is reported up the rcu_node hierarchy (using rcu_report_qs_rnp() to do so).
LKML-Reference: <12597846163698-git-send-email->
--- kernel/rcutree.c | 66 ++++++++++++++++++++++++++-------------------- kernel/rcutree.h | 3 +- kernel/rcutree_plugin.h | 12 ++++---- 3 files changed, 45 insertions(+), 36 deletions(-)
kernel/rcutree.c +37 -29
@@ -740,11 +740,13 @@ rcu_start_gp(struct rcu_state *rsp, unsigned long flags) }/* -* Clean up after the prior grace period and let rcu_start_gp() start up -* the next grace period if one is needed. Note that the caller must -* hold rnp->lock, as required by rcu_start_gp(), which will release it. +* Report a full set of quiescent states to the specified rcu_state +* data structure. This involves cleaning up after the prior grace +* period and letting rcu_start_gp() start up the next grace period +* if one is needed. Note that the caller must hold rnp->lock, as +* required by rcu_start_gp(), which will release it. */ -static void cpu_quiet_msk_finish (struct rcu_state *rsp,unsigned long flags) +static void rcu_report_qs_rsp (struct rcu_state *rsp,unsigned long flags) __releases(rcu_get_root(rsp)->lock) {WARN_ON_ONCE (!rcu_gp_in_progress (rsp));
@@ -754,15 +756,16 @@ static void cpu_quiet_msk_finish(struct rcu_state *rsp, unsigned long flags) }/* -* Similar to cpu_quiet(), for which it is a helper function. Allows -* a group of CPUs to be quieted at one go, though all the CPUs in the -* group must be represented by the same leaf rcu_node structure. -* That structure's lock must be held upon entry, and it is released -* before return. +* Similar to rcu_report_qs_rdp(), for which it is a helper function. +* Allows quiescent states for a group of CPUs to be reported at one go +* to the specified rcu_node structure, though all the CPUs in the group +* must be represented by the same rcu_node structure (which need not be +* a leaf rcu_node structure, though it often will be). That structure's +* lock must be held upon entry, and it is released before return. */ static void -cpu_quiet_msk (unsigned long mask,struct rcu_state *rsp,struct rcu_node *rnp, -unsigned long flags) +rcu_report_qs_rnp (unsigned long mask,struct rcu_state *rsp, +struct rcu_node *rnp,unsigned long flags) __releases(rnp->lock) {struct rcu_node *rnp_c;
@@ -798,21 +801,23 @@ cpu_quiet_msk(unsigned long mask, struct rcu_state *rsp, struct rcu_node *rnp,/* * Get here if we are the last CPU to pass through a quiescent -* state for this grace period. Invoke cpu_quiet_msk_finish() +* state for this grace period. Invoke rcu_report_qs_rsp() * to clean up and start the next grace period if one is needed. */ -cpu_quiet_msk_finish (rsp, flags);/* releases rnp->lock. */ +rcu_report_qs_rsp (rsp, flags);/* releases rnp->lock. */ }/* -* Record a quiescent state for the specified CPU, which must either be -* the current CPU. The lastcomp argument is used to make sure we are -* still in the grace period of interest. We don't want to end the current -* grace period based on quiescent states detected in an earlier grace -* period! +* Record a quiescent state for the specified CPU to that CPU's rcu_data +* structure. This must be either called from the specified CPU, or +* called when the specified CPU is known to be offline (and when it is +* also known that no other CPU is concurrently trying to help the offline +* CPU). The lastcomp argument is used to make sure we are still in the +* grace period of interest. We don't want to end the current grace period +* based on quiescent states detected in an earlier grace period! */ static void -cpu_quiet (int cpu,struct rcu_state *rsp,struct rcu_data *rdp,long lastcomp) +rcu_report_qs_rdp (int cpu,struct rcu_state *rsp,struct rcu_data *rdp,long lastcomp) {unsigned long flags;unsigned long mask;
@@ -827,8 +832,8 @@ cpu_quiet(int cpu, struct rcu_state *rsp, struct rcu_data *rdp, long lastcomp)* The race with GP start is resolved by the fact that we * hold the leaf rcu_node lock, so that the per-CPU bits * cannot yet be initialized -- so we would simply find our -* CPU's bit already cleared in cpu_quiet_msk() if this race -* occurred. +* CPU's bit already cleared in rcu_report_qs_rnp() if this +* race occurred. */ rdp->passed_quiesc =0 ;/* try again later! */ spin_unlock_irqrestore (&rnp->lock, flags);
@@ -846,7 +851,7 @@ cpu_quiet(int cpu, struct rcu_state *rsp, struct rcu_data *rdp, long lastcomp)*/ rdp->nxttail[RCU_NEXT_READY_TAIL ] = rdp->nxttail[RCU_NEXT_TAIL ]; -cpu_quiet_msk (mask, rsp, rnp, flags);/* releases rnp->lock */ +rcu_report_qs_rnp (mask, rsp, rnp, flags);/* rlses rnp->lock */ } }
@@ -877,8 +882,11 @@ rcu_check_quiescent_state(struct rcu_state *rsp, struct rcu_data *rdp)if (!rdp->passed_quiesc)return ; -/* Tell RCU we are done (but cpu_quiet() will be the judge of that). */ -cpu_quiet (rdp->cpu, rsp, rdp, rdp->passed_quiesc_completed); +/* +* Tell RCU we are done (but rcu_report_qs_rdp() will be the +* judge of that). +*/ +rcu_report_qs_rdp (rdp->cpu, rsp, rdp, rdp->passed_quiesc_completed); }#ifdef CONFIG_HOTPLUG_CPU
@@ -968,13 +976,13 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)/* * We still hold the leaf rcu_node structure lock here, and * irqs are still disabled. The reason for this subterfuge is -* because invoking task_quiet() with ->onofflock held leads -* to deadlock. +* because invoking rcu_report_unblock_qs_rnp() with ->onofflock +* held leads to deadlock. */ spin_unlock (&rsp->onofflock);/* irqs remain disabled. */ rnp = rdp->mynode;if (need_quiet) -task_quiet (rnp, flags); +rcu_report_unblock_qs_rnp (rnp, flags);else spin_unlock_irqrestore (&rnp->lock, flags);
@@ -1164,8 +1172,8 @@ static int rcu_process_dyntick(struct rcu_state *rsp, long lastcomp, }if (mask !=0 && rnp->completed == lastcomp) { -/* cpu_quiet_msk() releases rnp->lock. */ -cpu_quiet_msk (mask, rsp, rnp, flags); +/* rcu_report_qs_rnp() releases rnp->lock. */ +rcu_report_qs_rnp (mask, rsp, rnp, flags);continue ; }spin_unlock_irqrestore (&rnp->lock, flags);
kernel/rcutree.h +2 -1
@@ -306,7 +306,8 @@ long rcu_batches_completed(void);static void rcu_preempt_note_context_switch (int cpu);static int rcu_preempted_readers (struct rcu_node *rnp);#ifdef CONFIG_HOTPLUG_CPU -static void task_quiet (struct rcu_node *rnp,unsigned long flags); +static void rcu_report_unblock_qs_rnp (struct rcu_node *rnp, +unsigned long flags);#endif /* #ifdef CONFIG_HOTPLUG_CPU */ #ifdef CONFIG_RCU_CPU_STALL_DETECTOR static void rcu_print_task_stall (struct rcu_node *rnp);
kernel/rcutree_plugin.h +6 -6
@@ -167,7 +167,7 @@ static int rcu_preempted_readers(struct rcu_node *rnp)* irqs disabled, and this lock is released upon return, but irqs remain * disabled. */ -static void task_quiet (struct rcu_node *rnp,unsigned long flags) +static void rcu_report_unblock_qs_rnp (struct rcu_node *rnp,unsigned long flags) __releases(rnp->lock) {unsigned long mask;
@@ -185,7 +185,7 @@ static void task_quiet(struct rcu_node *rnp, unsigned long flags)* or tasks were kicked up to root rcu_node due to * CPUs going offline. */ -cpu_quiet_msk_finish (&rcu_preempt_state, flags); +rcu_report_qs_rsp (&rcu_preempt_state, flags);return ; }
@@ -193,7 +193,7 @@ static void task_quiet(struct rcu_node *rnp, unsigned long flags) mask = rnp->grpmask;spin_unlock (&rnp->lock);/* irqs remain disabled. */ spin_lock (&rnp_p->lock);/* irqs already disabled. */ -cpu_quiet_msk (mask, &rcu_preempt_state, rnp_p, flags); +rcu_report_qs_rnp (mask, &rcu_preempt_state, rnp_p, flags); }/*
@@ -253,12 +253,12 @@ static void rcu_read_unlock_special(struct task_struct *t)/* * If this was the last task on the current list, and if * we aren't waiting on any CPUs, report the quiescent state. -* Note that task_quiet() releases rnp->lock. +* Note that rcu_report_unblock_qs_rnp() releases rnp->lock. */ if (empty)spin_unlock_irqrestore (&rnp->lock, flags);else -task_quiet (rnp, flags); +rcu_report_unblock_qs_rnp (rnp, flags); }else {local_irq_restore (flags); }
@@ -566,7 +566,7 @@ static int rcu_preempted_readers(struct rcu_node *rnp)#ifdef CONFIG_HOTPLUG_CPU /* Because preemptible RCU does not exist, no quieting of tasks. */ -static void task_quiet (struct rcu_node *rnp,unsigned long flags) +static void rcu_report_unblock_qs_rnp (struct rcu_node *rnp,unsigned long flags) {spin_unlock_irqrestore (&rnp->lock, flags); }
[tip:core/rcu] rcu: Add expedited grace-period support for preemptible RCU
In reply to Paul E. McKenneyCommit-ID: d9a3da0699b24a589b27a61e1a5b5bd30d9db669 Gitweb: http://git.kernel.org/tip/d9a3da0699b24a589b27a61e1a5b5bd30d9db669 Author: Paul E. McKenney <[email protected]> AuthorDate: Wed, 2 Dec 2009 12:10:15 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 3 Dec 2009 11:35:25 +0100
rcu: Add expedited grace-period support for preemptible RCU
Implement an synchronize_rcu_expedited() for preemptible RCU that actually is expedited. This uses synchronize_sched_expedited() to force all threads currently running in a preemptible-RCU read-side critical section onto the appropriate ->blocked_tasks[] list, then takes a snapshot of all of these lists and waits for them to drain.
LKML-Reference: <1259784616158-git-send-email->
--- kernel/rcutorture.c | 34 ++++++-- kernel/rcutree.c | 10 ++- kernel/rcutree.h | 35 ++++++++- kernel/rcutree_plugin.h | 198 ++++++++++++++++++++++++++++++++++++++++++++-- kernel/rcutree_trace.c | 10 ++- 5 files changed, 260 insertions(+), 27 deletions(-)
kernel/rcutorture.c +25 -9
@@ -327,6 +327,11 @@ rcu_torture_cb(struct rcu_head *p) cur_ops->deferred_free (rp); } +static int rcu_no_completed (void ) +{ +return 0 ; +} +static void rcu_torture_deferred_free (struct rcu_torture *p) {call_rcu (&p->rtort_rcu, rcu_torture_cb);
@@ -388,6 +393,21 @@ static struct rcu_torture_ops rcu_sync_ops = { .name = "rcu_sync" }; +static struct rcu_torture_ops rcu_expedited_ops = { + .init = rcu_sync_torture_init, + .cleanup =NULL , + .readlock = rcu_torture_read_lock, + .read_delay = rcu_read_delay,/* just reuse rcu's version. */ + .readunlock = rcu_torture_read_unlock, + .completed = rcu_no_completed, + .deferred_free = rcu_sync_torture_deferred_free, + .sync = synchronize_rcu_expedited, + .cb_barrier =NULL , + .stats =NULL , + .irq_capable =1 , + .name ="rcu_expedited" +}; +/* * Definitions for rcu_bh torture testing. */
@@ -581,11 +601,6 @@ static void sched_torture_read_unlock(int idx)preempt_enable (); } -static int sched_torture_completed (void ) -{ -return 0 ; -} -static void rcu_sched_torture_deferred_free (struct rcu_torture *p) {call_rcu_sched (&p->rtort_rcu, rcu_torture_cb);
@@ -602,7 +617,7 @@ static struct rcu_torture_ops sched_ops = { .readlock = sched_torture_read_lock, .read_delay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = sched_torture_read_unlock, - .completed = sched_torture_completed, + .completed = rcu_no_completed, .deferred_free = rcu_sched_torture_deferred_free, .sync = sched_torture_synchronize, .cb_barrier = rcu_barrier_sched,
@@ -617,7 +632,7 @@ static struct rcu_torture_ops sched_sync_ops = { .readlock = sched_torture_read_lock, .read_delay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = sched_torture_read_unlock, - .completed = sched_torture_completed, + .completed = rcu_no_completed, .deferred_free = rcu_sync_torture_deferred_free, .sync = sched_torture_synchronize, .cb_barrier = NULL,
@@ -631,7 +646,7 @@ static struct rcu_torture_ops sched_expedited_ops = { .readlock = sched_torture_read_lock, .read_delay = rcu_read_delay, /* just reuse rcu's version. */ .readunlock = sched_torture_read_unlock, - .completed = sched_torture_completed, + .completed = rcu_no_completed, .deferred_free = rcu_sync_torture_deferred_free, .sync = synchronize_sched_expedited, .cb_barrier = NULL,
@@ -1116,7 +1131,8 @@ rcu_torture_init(void)int cpu;int firsterr =0 ;static struct rcu_torture_ops *torture_ops[] = - { &rcu_ops, &rcu_sync_ops, &rcu_bh_ops, &rcu_bh_sync_ops, + { &rcu_ops, &rcu_sync_ops, &rcu_expedited_ops, + &rcu_bh_ops, &rcu_bh_sync_ops, &srcu_ops, &srcu_expedited_ops, &sched_ops, &sched_sync_ops, &sched_expedited_ops, };
kernel/rcutree.c +7 -3
@@ -948,7 +948,7 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp) {unsigned long flags;unsigned long mask; -int need_quiet =0 ; +int need_report =0 ;struct rcu_data *rdp = rsp->rda[cpu];struct rcu_node *rnp;
@@ -967,7 +967,7 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)break ; }if (rnp == rdp->mynode) - need_quiet =rcu_preempt_offline_tasks (rsp, rnp, rdp); + need_report =rcu_preempt_offline_tasks (rsp, rnp, rdp);else spin_unlock (&rnp->lock);/* irqs remain disabled. */ mask = rnp->grpmask;
@@ -982,10 +982,12 @@ static void __rcu_offline_cpu(int cpu, struct rcu_state *rsp)*/ spin_unlock (&rsp->onofflock);/* irqs remain disabled. */ rnp = rdp->mynode; -if (need_quiet) +if (need_report &RCU_OFL_TASKS_NORM_GP )rcu_report_unblock_qs_rnp (rnp, flags);else spin_unlock_irqrestore (&rnp->lock, flags); +if (need_report &RCU_OFL_TASKS_EXP_GP ) +rcu_report_exp_rnp (rsp, rnp);rcu_adopt_orphan_cbs (rsp); }
@@ -1843,6 +1845,8 @@ static void __init rcu_init_one(struct rcu_state *rsp) rnp->level = i;INIT_LIST_HEAD (&rnp->blocked_tasks[0 ]);INIT_LIST_HEAD (&rnp->blocked_tasks[1 ]); +INIT_LIST_HEAD (&rnp->blocked_tasks[2 ]); +INIT_LIST_HEAD (&rnp->blocked_tasks[3 ]); } } }
kernel/rcutree.h +32 -3
@@ -104,8 +104,12 @@ struct rcu_node {/* an rcu_data structure, otherwise, each */ /* bit corresponds to a child rcu_node */ /* structure. */ +unsigned long expmask;/* Groups that have ->blocked_tasks[] */ +/* elements that need to drain to allow the */ +/* current expedited grace period to */ +/* complete (only for TREE_PREEMPT_RCU). */ unsigned long qsmaskinit; -/* Per-GP initialization for qsmask. */ +/* Per-GP initial value for qsmask & expmask. */ unsigned long grpmask;/* Mask to apply to parent qsmask. */ /* Only one bit will be set in this mask. */ int grplo;/* lowest-numbered CPU or group here. */
@@ -113,7 +117,7 @@ struct rcu_node {u8 grpnum;/* CPU/group number for next level up. */ u8 level;/* root is at level 0. */ struct rcu_node *parent; -struct list_head blocked_tasks[2 ]; +struct list_head blocked_tasks[4 ];/* Tasks blocked in RCU read-side critsect. */ /* Grace period number (->gpnum) x blocked */ /* by tasks on the (x & 0x1) element of the */
@@ -128,6 +132,21 @@ struct rcu_node {for ((rnp) = &(rsp)->node[0 ]; \ (rnp) < &(rsp)->node[NUM_RCU_NODES ]; (rnp)++) +/* +* Do a breadth-first scan of the non-leaf rcu_node structures for the +* specified rcu_state structure. Note that if there is a singleton +* rcu_node tree with but one rcu_node structure, this loop is a no-op. + */ +#define rcu_for_each_nonleaf_node_breadth_first (rsp, rnp) \ + for ((rnp) = &(rsp)->node[0]; \ + (rnp) < (rsp)->level[NUM_RCU_LVLS - 1]; (rnp)++) + +/* +* Scan the leaves of the rcu_node hierarchy for the specified rcu_state +* structure. Note that if there is a singleton rcu_node tree with but +* one rcu_node structure, this loop -will- visit the rcu_node structure. +* It is still a leaf node, even if it is also the root node. +*/ #define rcu_for_each_leaf_node (rsp, rnp) \ for ((rnp) = (rsp)->level[NUM_RCU_LVLS - 1]; \ (rnp) < &(rsp)->node[NUM_RCU_NODES]; (rnp)++)
@@ -261,7 +280,7 @@ struct rcu_state {long gpnum;/* Current gp number. */ long completed;/* # of last completed gp. */ -/* End of fields guarded by root rcu_node's lock. */ +/* End of fields guarded by root rcu_node's lock. */ spinlock_t onofflock;/* exclude on/offline and */ /* starting new GP. Also */
@@ -293,6 +312,13 @@ struct rcu_state {#endif /* #ifdef CONFIG_RCU_CPU_STALL_DETECTOR */ }; +/* Return values for rcu_preempt_offline_tasks(). */ + +#define RCU_OFL_TASKS_NORM_GP 0x1/* Tasks blocking normal */ +/* GP were moved to root. */ +#define RCU_OFL_TASKS_EXP_GP 0x2/* Tasks blocking expedited */ +/* GP were moved to root. */ +#ifdef RCU_TREE_NONCORE /*
@@ -333,6 +359,9 @@ static void rcu_preempt_offline_cpu(int cpu);static void rcu_preempt_check_callbacks (int cpu);static void rcu_preempt_process_callbacks (void );void call_rcu (struct rcu_head *head,void (*func)(struct rcu_head *rcu)); +#if defined(CONFIG_HOTPLUG_CPU ) || defined(CONFIG_TREE_PREEMPT_RCU ) +static void rcu_report_exp_rnp (struct rcu_state *rsp,struct rcu_node *rnp); +#endif /* #if defined(CONFIG_HOTPLUG_CPU) || defined(CONFIG_TREE_PREEMPT_RCU) */ static int rcu_preempt_pending (int cpu);static int rcu_preempt_needs_cpu (int cpu);static void __cpuinit rcu_preempt_init_percpu_data (int cpu);
kernel/rcutree_plugin.h +189 -9
268 lines not on this page · raw message
kernel/rcutree_trace.c +7 -3
@@ -157,6 +157,7 @@ static void print_one_rcu_state(struct seq_file *m, struct rcu_state *rsp) {long gpnum;int level =0 ; +int phase;struct rcu_node *rnp; gpnum = rsp->gpnum;
@@ -173,10 +174,13 @@ static void print_one_rcu_state(struct seq_file *m, struct rcu_state *rsp)seq_puts (m,"\n" ); level = rnp->level; } -seq_printf (m,"%lx/%lx %c>%c %d:%d ^%d " , + phase = gpnum &0x1 ; +seq_printf (m,"%lx/%lx %c%c>%c%c %d:%d ^%d " , rnp->qsmask, rnp->qsmaskinit, -"T." [list_empty (&rnp->blocked_tasks[gpnum &1 ])], -"T." [list_empty (&rnp->blocked_tasks[!(gpnum &1 )])], +"T." [list_empty (&rnp->blocked_tasks[phase])], +"E." [list_empty (&rnp->blocked_tasks[phase +2 ])], +"T." [list_empty (&rnp->blocked_tasks[!phase])], +"E." [list_empty (&rnp->blocked_tasks[!phase +2 ])], rnp->grplo, rnp->grphi, rnp->grpnum); }seq_puts (m,"\n" );
[tip:core/rcu] rcu: Make RCU's CPU-stall detector be default
In reply to Paul E. McKenneyCommit-ID: 8bfb2f8e655b9d0c45fde679fcd5fd97e34513db Gitweb: http://git.kernel.org/tip/8bfb2f8e655b9d0c45fde679fcd5fd97e34513db Author: Paul E. McKenney <[email protected]> AuthorDate: Wed, 2 Dec 2009 12:10:16 -0800 Committer: Ingo Molnar <[email protected]> CommitDate: Thu, 3 Dec 2009 11:35:27 +0100
rcu: Make RCU's CPU-stall detector be default
The RCU_CPU_STALL_DETECTOR costs almost nothing and has located some bugs that might otherwise have been difficult to track down. Make it be default for the TREE RCU implementations.
The vmlinux size impact is limited (on 64-bit x86 defconfig):
text data bss dec hex filename
8440248 1260076 995588 10695912 a334e8 vmlinux.before
8440774 1260060 995588 10696422 a336e6 vmlinux.after
+526 bytes - acceptable default cost.
For RAM starved systems, TINY_RCU does not support CPU-stall detection and is much smaller, but then again it is a uniprocessor...
LKML-Reference: <12597846162906-git-send-email->
--- lib/Kconfig.debug | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
lib/Kconfig.debug +1 -1
@@ -749,7 +749,7 @@ config RCU_TORTURE_TEST_RUNNABLE config RCU_CPU_STALL_DETECTOR bool "Check for stalled CPUs delaying RCU grace periods" depends on TREE_RCU || TREE_PREEMPT_RCU - default n + default y help This option causes RCU to printk information on which CPUs are delaying the current grace period, but only when
Re: [PATCH tip/core/rcu 3/4] rcu: add expedited grace-period support for preemptible RCU
In reply to Lai JiangshanQuoted 10 lines · Lai Jiangshan
Quoted 8 lines · Paul E. McKenney
From: Paul E. McKenney <[email protected]>
Implement an
synchronize_rcu_expedited()for preemptible RCU that actually is expedited. This usessynchronize_sched_expedited()to force all threads currently running in a preemptible-RCU read-side critical section onto the appropriate ->blocked_tasks[] list, then takes a snapshot of all of these lists and waits for them to drain.
Quoted 4 lines
Quoted 2 lines
3. Add an implementation of
synchronize_rcu_expedited()that
actually expedites preemptible-RCU grace periods.It's very nice.
I am glad you like it!
Quoted 10 lines
But I don't understand all things.
1) Why it can be speeded up (in theory)?
synchronize_sched_expedited()does speed up, it is due tomigration_threadsare the most highest priority threads.But for
synchronize_rcu_expedited(), some preempted tasks in ->blocked_tasks[] may be waiting at runqueue for long long time because some other higher priority threads comes.
Quoted 8 lines
simply comparison:
synchronize_sched_expedited()
==>wake_up_process(rq->migration_thread)to force schedule on cpus.
which forces read-sides notify the end earlier, or we can say "it forces read-sides run to end faster"
synchronize_rcu_expedited()
==> Nothing to force preempted read-site run to end faster.
You are quite right, and this is one reason why one of the items on my todo list is "RCU priority boosting". I am currently doing some work to prepare for this by simplifying force_quiescent_state(). The general idea will be to traverse the ->blocked_tasks[] lists to raise priorities if the grace period goes too long.
That said, the purpose of synchronize_rcu_expedited() is not to provide real-time response, but rather to provide short -average- grace-period durations. In the common case, RCU read-side critical sections do not get preempted to begin with, so in the common case, this implementation of synchronize_sched_expedited() should provide short average grace-period durations.
Quoted 3 lines
2) Why we introduce a API which no one use it.
I remember that Net guys request a expeditedsynchronize_rcu(). but currently there is still no one use it.
There have been several requests for it over the years, so I feel justified providing it. If it is still unused some years hence, it is really easy to remove it, but it is really hard to provide it on a moment's notice.
Quoted 1 line
Beware my thinking may be wrong!
That would apply to both of us! ;-)
Thanx, Paul