Provide infrastructure for full-system idle
cover Provide infrastructure for full-system idle
Whenever there is at least one non-idle CPU, it is necessary to periodically update timekeeping information. Before NO_HZ_FULL, this updating was carried out by the scheduling-clock tick, which ran on every non-idle CPU. With the advent of NO_HZ_FULL, it is possible to have non-idle CPUs that are not receiving scheduling-clock ticks. This possibility is handled by assigning a timekeeping CPU that continues taking scheduling-clock ticks.
Unfortunately, timekeeping CPU continues taking scheduling-clock interrupts even when all other CPUs are completely idle, which is not so good for energy efficiency and battery lifetime. Clearly, it would be good to turn off the timekeeping CPU's scheduling-clock tick when all CPUs are completely idle. This is conceptually simple, but we also need good performance and scalability on large systems, which rules out implementations based on frequently updated global counts of non-idle CPUs as well as implementations that frequently scan all CPUs. Nevertheless, we need a single global indicator in order to keep the overhead of checking acceptably low.
The chosen approach is to enforce hysteresis on the non-idle to full-system-idle transition, with the amount of hysteresis increasing linearly with the number of CPUs, thus keeping contention acceptably low. This approach piggybacks on RCU's existing force-quiescent-state scanning of idle CPUs, which has the advantage of avoiding the scan entirely on busy systems that have high levels of multiprogramming. This scan take per-CPU idleness information and feeds it into a state machine that applies the level of hysteresis required to arrive at a single full-system-idle indicator.
Note that this version pays attention to CPUs that have taken an NMI from idle. It is not clear to me that NMI handlers can safely access the time on a system that is long-term idle. Unless someone tells me that it is somehow safe to access time from an NMI from idle, I will remove NMI support in the next version.
Thanx, Paul
------------------------------------------------------------------------
b/include/linux/rcupdate.h | 18 + b/kernel/rcutree.c | 56 ++++- b/kernel/rcutree.h | 20 ++ b/kernel/rcutree_plugin.h | 427 ++++++++++++++++++++++++++++++++++++++++++++- b/kernel/time/Kconfig | 23 ++ 5 files changed, 527 insertions(+), 17 deletions(-)
RFC PATCH 3/8 nohz_full: Add per-CPU idle-state tracking
In reply to Paul E. McKenneyFrom: "Paul E. McKenney" <[email protected]>
This commit adds the code that updates the rcu_dyntick structure's new fields to track the per-CPU idle state based on interrupts and transitions into and out of the idle loop (NMIs will be handled separately). This code is similar to the code that maintains RCU's idea of per-CPU idleness, but differs in that RCU treats CPUs running in user mode as idle, where this new code does not.
--- kernel/rcutree.c | 4 +++ kernel/rcutree.h | 2 ++ kernel/rcutree_plugin.h | 79 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 85 insertions(+)
kernel/rcutree.c +4 -0
@@ -416,6 +416,7 @@ void rcu_idle_enter(void)local_irq_save (flags);rcu_eqs_enter (false); +rcu_sysidle_enter (&__get_cpu_var (rcu_dynticks),0 );local_irq_restore (flags); }EXPORT_SYMBOL_GPL (rcu_idle_enter);
@@ -466,6 +467,7 @@ void rcu_irq_exit(void)trace_rcu_dyntick ("--=" , oldval, rdtp->dynticks_nesting); elsercu_eqs_enter_common (rdtp ,oldval ,true ); +rcu_sysidle_enter (rdtp,1 );local_irq_restore (flags); }
@@ -534,6 +536,7 @@ void rcu_idle_exit(void)local_irq_save (flags);rcu_eqs_exit (false); +rcu_sysidle_exit (&__get_cpu_var (rcu_dynticks),0 );local_irq_restore (flags); }EXPORT_SYMBOL_GPL (rcu_idle_exit);
@@ -585,6 +588,7 @@ void rcu_irq_enter(void)trace_rcu_dyntick ("++=" , oldval, rdtp->dynticks_nesting); elsercu_eqs_exit_common (rdtp ,oldval ,true ); +rcu_sysidle_exit (rdtp,1 );local_irq_restore (flags); }
kernel/rcutree.h +2 -0
@@ -555,6 +555,8 @@ static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);static void rcu_spawn_nocb_kthreads (struct rcu_state *rsp);static void rcu_kick_nohz_cpu (int cpu);static bool init_nocb_callback_list (struct rcu_data *rdp); +static void rcu_sysidle_enter (struct rcu_dynticks *rdtp,int irq); +static void rcu_sysidle_exit (struct rcu_dynticks *rdtp,int irq);static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp);#endif /* #ifndef RCU_TREE_NONCORE */
kernel/rcutree_plugin.h +79 -0
91 lines not on this page · raw message
Signature · 1 line
1.8.1.5
RFC PATCH 4/8 nohz_full: Add per-CPU idle-state tracking for NMIs
In reply to Paul E. McKenneyFrom: "Paul E. McKenney" <[email protected]>
It turns out that we can reuse RCU's ->dynticks counter to identify CPUs that are non-idle due to NMIs from idle, in combination with the new full-system idle ->dynticks_idle counter. The reason this works can be seen from the following table:
->dynticks ->dynticks_idle union
NMI from idle: non-idle idle non-idle NMI from user: non-idle non-idle non-idle NMI from non-idle kernel: non-idle non-idle non-idle idle: idle idle idle user: idle non-idle non-idle non-idle kernel: non-idle non-idle non-idle
Note that the final "union" column gets us what we need: A non-idle indication in all cases except when the CPU really is in the idle loop. (But what about interrupt handlers? They are treated the same as non-idle kernel.)
Therefore, if both ->dynticks and ->dynticks_idle say that the corresponding CPU is idle (in other words, both have odd values), then the CPU really is idle.
The only additional thing that this commit needs to supply is the time that the last NMI either started or ended for the corresponding CPU. This is used to determine whether or not this CPU has been idle long enough to justify updating the global full-system idle state.
Final caveat: This approach assumes that NMI handlers do not access system time, an assumption that the existing dyntick-idle code also makes. To see this, suppose that the system has been idle for an extended period of time, so that the clock values are obsolete, and that an NMI arrives. The NMI handler has no safe way to update the clock values, and thus must do without.
--- kernel/rcutree.c | 7 +++++-- kernel/rcutree.h | 1 + kernel/rcutree_plugin.h | 9 +++++++++ 3 files changed, 15 insertions(+), 2 deletions(-)
kernel/rcutree.c +5 -2
@@ -607,6 +607,7 @@ void rcu_nmi_enter(void) (atomic_read(&rdtp->dynticks) & 0x1))return ; rdtp->dynticks_nmi_nesting++; +rcu_sysidle_nmi_jiffies (rdtp);smp_mb__before_atomic_inc ();/* Force delay from prior write. */ atomic_inc (&rdtp->dynticks);/* CPUs seeing atomic_inc() must see later RCU read-side crit sects */
@@ -625,8 +626,10 @@ void rcu_nmi_exit(void) {struct rcu_dynticks *rdtp = &__get_cpu_var (rcu_dynticks); -if (rdtp->dynticks_nmi_nesting ==0 || - --rdtp->dynticks_nmi_nesting !=0 ) +if (rdtp->dynticks_nmi_nesting ==0 ) +return ; +rcu_sysidle_nmi_jiffies (rdtp); +if (--rdtp->dynticks_nmi_nesting !=0 )return ;/* CPUs seeing atomic_inc() must see prior RCU read-side crit sects */ smp_mb__before_atomic_inc ();/* See above. */
kernel/rcutree.h +1 -0
@@ -557,6 +557,7 @@ static void rcu_kick_nohz_cpu(int cpu);static bool init_nocb_callback_list (struct rcu_data *rdp);static void rcu_sysidle_enter (struct rcu_dynticks *rdtp,int irq);static void rcu_sysidle_exit (struct rcu_dynticks *rdtp,int irq); +static void rcu_sysidle_nmi_jiffies (struct rcu_dynticks *rdtp);static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp);#endif /* #ifndef RCU_TREE_NONCORE */
kernel/rcutree_plugin.h +9 -0
@@ -2450,6 +2450,11 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)WARN_ON_ONCE (!(atomic_read (&rdtp->dynticks_idle) &0x1 )); } +static inline void rcu_sysidle_nmi_jiffies (struct rcu_dynticks *rdtp) +{ + rdtp->dynticks_nmi_jiffies = jiffies; +} +/* * Initialize dynticks sysidle state for CPUs coming online. */
@@ -2468,6 +2473,10 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq) { } +static inline void rcu_sysidle_nmi_jiffies (struct rcu_dynticks *rdtp) +{ +} +static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp) { }
Signature · 1 line
1.8.1.5
RFC PATCH 8/8 nohz_full: Force RCU's grace-period kthreads onto timekeeping CPU
In reply to Paul E. McKenneyFrom: "Paul E. McKenney" <[email protected]>
Because RCU's quiescent-state-forcing mechanism is used to drive the full-system-idle state machine, and because this mechanism is executed by RCU's grace-period kthreads, this commit forces these kthreads to run on the timekeeping CPU (tick_do_timer_cpu). To do otherwise would mean that the RCU grace-period kthreads would force the system into non-idle state every time they drove the state machine, which would be just a bit on the futile side.
--- kernel/rcutree.c | 1 + kernel/rcutree.h | 1 + kernel/rcutree_plugin.h | 20 +++++++++++++++++++- 3 files changed, 21 insertions(+), 1 deletion(-)
kernel/rcutree.c +1 -0
@@ -1289,6 +1289,7 @@ static int rcu_gp_init(struct rcu_state *rsp)struct rcu_data *rdp;struct rcu_node *rnp =rcu_get_root (rsp); +rcu_bind_gp_kthread ();raw_spin_lock_irq (&rnp->lock); rsp->gp_flags =0 ;/* Clear all flags: New grace period. */
kernel/rcutree.h +1 -0
@@ -561,6 +561,7 @@ static void rcu_sysidle_nmi_jiffies(struct rcu_dynticks *rdtp);static void rcu_sysidle_check_cpu (struct rcu_data *rdp,bool *isidle,unsigned long *maxj);static bool is_sysidle_rcu_state (struct rcu_state *rsp); +static void rcu_bind_gp_kthread (void );static void rcu_sysidle_report (struct rcu_state *rsp,int isidle,unsigned long maxj);static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp);
kernel/rcutree_plugin.h +19 -1
@@ -2553,7 +2553,7 @@ static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,if (!*isidle || rdp->rsp != rcu_sysidle_state ||cpu_is_offline (rdp->cpu) || rdp->cpu == tick_do_timer_cpu)return ; -/* WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu); */ +WARN_ON_ONCE (smp_processor_id () != tick_do_timer_cpu);/* * Pick up current idle and NMI-nesting counters, check. We check
@@ -2593,6 +2593,20 @@ static bool is_sysidle_rcu_state(struct rcu_state *rsp) }/* +* Bind the grace-period kthread for the sysidle flavor of RCU to the +* timekeeping CPU. +*/ +static void rcu_bind_gp_kthread (void ) +{ +int cpu =ACCESS_ONCE (tick_do_timer_cpu); + +if (cpu <0 || cpu >= nr_cpu_ids) +return ; +if (raw_smp_processor_id () != cpu) +set_cpus_allowed_ptr (current,cpumask_of (cpu)); +} + +/* * Return a delay in jiffies based on the number of CPUs, rcu_node * leaf fanout, and jiffies tick rate. The idea is to allow larger * systems more time to transition to full-idle state in order to
@@ -2764,6 +2778,10 @@ static bool is_sysidle_rcu_state(struct rcu_state *rsp)return false; } +static void rcu_bind_gp_kthread (void ) +{ +} +static void rcu_sysidle_report (struct rcu_state *rsp,int isidle,unsigned long maxj) {
Signature · 1 line
1.8.1.5
RFC PATCH 7/8 nohz_full: Add full-system-idle state machine
In reply to Paul E. McKenneyFrom: "Paul E. McKenney" <[email protected]>
This commit adds the state machine that takes the per-CPU idle data as input and produces a full-system-idle indication as output. This state machine is driven out of RCU's quiescent-state-forcing mechanism, which invokes rcu_sysidle_check_cpu() to collect per-CPU idle state and then rcu_sysidle_report() to drive the state machine.
The full-system-idle state is sampled using rcu_sys_is_idle(), which also drives the state machine if RCU is idle (and does so by forcing RCU to become non-idle). This function returns true if all but the timekeeping CPU (tick_do_timer_cpu) are idle and have been idle long enough to avoid memory contention on the full_sysidle_state state variable. The rcu_sysidle_force_exit() may be called externally to reset the state machine back into non-idle state.
--- include/linux/rcupdate.h | 18 ++++ kernel/rcutree.c | 16 ++- kernel/rcutree.h | 5 + kernel/rcutree_plugin.h | 273 ++++++++++++++++++++++++++++++++++++++++++++++- 4 files changed, 305 insertions(+), 7 deletions(-)
include/linux/rcupdate.h +18 -0
@@ -1011,4 +1011,22 @@ static inline bool rcu_is_nocb_cpu(int cpu) { return false; }#endif /* #else #ifdef CONFIG_RCU_NOCB_CPU */ +/* Only for use by adaptive-ticks code. */ +#ifdef CONFIG_NO_HZ_FULL_SYSIDLE +extern bool rcu_sys_is_idle (void ); +extern void rcu_sysidle_force_exit (void ); +#else /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */ + +static inline bool rcu_sys_is_idle (void ) +{ +return false; +} + +static inline void rcu_sysidle_force_exit (void ) +{ +} + +#endif /* #else #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */ + +#endif /* __LINUX_RCUPDATE_H */
kernel/rcutree.c +13 -3
@@ -721,6 +721,7 @@ static int dyntick_save_progress_counter(struct rcu_data *rdp, bool *isidle, unsigned long *maxj) { rdp->dynticks_snap = atomic_add_return(0, &rdp->dynticks->dynticks); +rcu_sysidle_check_cpu (rdp, isidle, maxj);return (rdp->dynticks_snap &0x1 ) ==0 ; }
@@ -1359,11 +1360,17 @@ int rcu_gp_fqs(struct rcu_state *rsp, int fqs_state_in) rsp->n_force_qs++;if (fqs_state ==RCU_SAVE_DYNTICK ) {/* Collect dyntick-idle snapshots. */ +if (is_sysidle_rcu_state (rsp)) { + isidle =1 ; + maxj = jiffies -ULONG_MAX /4 ; + }force_qs_rnp (rsp, dyntick_save_progress_counter, &isidle, &maxj); +rcu_sysidle_report (rsp, isidle, maxj); fqs_state =RCU_FORCE_QS ; }else {/* Handle dyntick-idle and offline CPUs. */ + isidle =0 ;force_qs_rnp (rsp, rcu_implicit_dynticks_qs, &isidle, &maxj); }/* Clear flag to prevent immediate re-entry. */
@@ -2090,9 +2097,12 @@ static void force_qs_rnp(struct rcu_state *rsp, cpu = rnp->grplo; bit =1 ;for (; cpu <= rnp->grphi; cpu++, bit <<=1 ) { -if ((rnp->qsmask & bit) !=0 && -f (per_cpu_ptr (rsp->rda, cpu), isidle, maxj)) - mask |= bit; +if ((rnp->qsmask & bit) !=0 ) { +if ((rnp->qsmaskinit & bit) !=0 ) + *isidle =0 ; +if (f (per_cpu_ptr (rsp->rda, cpu), isidle, maxj)) + mask |= bit; + } }if (mask !=0 ) {
kernel/rcutree.h +5 -0
@@ -558,6 +558,11 @@ static bool init_nocb_callback_list(struct rcu_data *rdp);static void rcu_sysidle_enter (struct rcu_dynticks *rdtp,int irq);static void rcu_sysidle_exit (struct rcu_dynticks *rdtp,int irq);static void rcu_sysidle_nmi_jiffies (struct rcu_dynticks *rdtp); +static void rcu_sysidle_check_cpu (struct rcu_data *rdp,bool *isidle, +unsigned long *maxj); +static bool is_sysidle_rcu_state (struct rcu_state *rsp); +static void rcu_sysidle_report (struct rcu_state *rsp,int isidle, +unsigned long maxj);static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp);#endif /* #ifndef RCU_TREE_NONCORE */
kernel/rcutree_plugin.h +269 -4
314 lines not on this page · raw message
Signature · 1 line
1.8.1.5
RFC PATCH 2/8 nohz_full: Add rcu_dyntick data for scalable detection of all-idle state
In reply to Paul E. McKenneyFrom: "Paul E. McKenney" <[email protected]>
This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy. The handling of these new fields is otherwise quite similar to that for the exiting fields. This commit also adds the initialization required for these fields.
--- kernel/rcutree.c | 5 +++++ kernel/rcutree.h | 11 +++++++++++ kernel/rcutree_plugin.h | 19 +++++++++++++++++++ 3 files changed, 35 insertions(+)
kernel/rcutree.c +5 -0
@@ -209,6 +209,10 @@ EXPORT_SYMBOL_GPL(rcu_note_context_switch); DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = { .dynticks_nesting =DYNTICK_TASK_EXIT_IDLE , .dynticks =ATOMIC_INIT (1 ), +#ifdef CONFIG_NO_HZ_FULL_SYSIDLE + .dynticks_idle_nesting =DYNTICK_TASK_NEST_VALUE , + .dynticks_idle =ATOMIC_INIT (1 ), +#endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */ };static long blimit =10 ;/* Maximum callbacks per rcu_do_batch. */
@@ -2902,6 +2906,7 @@ rcu_init_percpu_data(int cpu, struct rcu_state *rsp, int preemptible) rdp->blimit = blimit;init_callback_list (rdp);/* Re-enable callbacks on this CPU. */ rdp->dynticks->dynticks_nesting =DYNTICK_TASK_EXIT_IDLE ; +rcu_sysidle_init_percpu_data (rdp->dynticks);atomic_set (&rdp->dynticks->dynticks, (atomic_read (&rdp->dynticks->dynticks) & ~0x1 ) +1 );raw_spin_unlock (&rnp->lock);/* irqs remain disabled. */
kernel/rcutree.h +11 -0
@@ -88,6 +88,16 @@ struct rcu_dynticks {/* Process level is worth LLONG_MAX/2. */ int dynticks_nmi_nesting;/* Track NMI nesting level. */ atomic_t dynticks;/* Even value for idle, else odd. */ +#ifdef CONFIG_NO_HZ_FULL_SYSIDLE +long long dynticks_idle_nesting; +/* irq/process nesting level from idle. */ +atomic_t dynticks_idle;/* Even value for idle, else odd. */ +/* "Idle" excludes userspace execution. */ +unsigned long dynticks_idle_jiffies; +/* End of last non-NMI non-idle period. */ +unsigned long dynticks_nmi_jiffies; +/* End of last NMI non-idle period. */ +#endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */ #ifdef CONFIG_RCU_FAST_NO_HZ bool all_lazy;/* Are all CPU's CBs lazy? */ unsigned long nonlazy_posted;
@@ -545,6 +555,7 @@ static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);static void rcu_spawn_nocb_kthreads (struct rcu_state *rsp);static void rcu_kick_nohz_cpu (int cpu);static bool init_nocb_callback_list (struct rcu_data *rdp); +static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp);#endif /* #ifndef RCU_TREE_NONCORE */
kernel/rcutree_plugin.h +19 -0
@@ -2375,3 +2375,22 @@ static void rcu_kick_nohz_cpu(int cpu)smp_send_reschedule (cpu);#endif /* #ifdef CONFIG_NO_HZ_FULL */ } + + +#ifdef CONFIG_NO_HZ_FULL_SYSIDLE + +/* +* Initialize dynticks sysidle state for CPUs coming online. +*/ +static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp) +{ + rdtp->dynticks_idle_nesting =DYNTICK_TASK_NEST_VALUE ; +} + +#else /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */ + +static void rcu_sysidle_init_percpu_data (struct rcu_dynticks *rdtp) +{ +} + +#endif /* #else #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
Signature · 1 line
1.8.1.5
RFC PATCH 1/8 nohz_full: Add Kconfig parameter for scalable detection of all-idle state
In reply to Paul E. McKenneyFrom: "Paul E. McKenney" <[email protected]>
At least one CPU must keep the scheduling-clock tick running for timekeeping purposes whenever there is a non-idle CPU. However, with the new nohz_full adaptive-idle machinery, it is difficult to distinguish between all CPUs really being idle as opposed to all non-idle CPUs being in adaptive-ticks mode. This commit therefore adds a Kconfig parameter as a first step towards enabling a scalable detection of full-system idle state.
--- kernel/time/Kconfig | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+)
kernel/time/Kconfig +23 -0
@@ -134,6 +134,29 @@ config NO_HZ_FULL_ALL Note the boot CPU will still be kept outside the range to handle the timekeeping duty. +config NO_HZ_FULL_SYSIDLE + bool "Detect full-system idle state for full dynticks system" + depends on NO_HZ_FULL + default n + help + At least one CPU must keep the scheduling-clock tick running + for timekeeping purposes whenever there is a non-idle CPU, + where "non-idle" includes CPUs with a single runnable task + in adaptive-idle mode. Because the underlying adaptive-tick + support cannot distinguish between all CPUs being idle and + all CPUs each running a single task in adaptive-idle mode, + the underlying support simply ensures that there is always + a CPU handling the scheduling-clock tick, whether or not all + CPUs are idle. This Kconfig option enables scalable detection + of the all-CPUs-idle state, thus allowing the scheduling-clock + tick to be disabled when all CPUs are idle. Note that scalable + detection of the all-CPUs-idle state means that larger systems + will be slower to declare the all-CPUs-idle state. + + Say Y if you would like to help debug all-CPUs-idle detection. + + Say N if you are unsure. + config NO_HZ bool "Old Idle dynticks config" depends on !ARCH_USES_GETTIMEOFFSET && GENERIC_CLOCKEVENTS
Signature · 1 line
1.8.1.5
RFC PATCH 6/8 nohz_full: Add full-system-idle arguments to API
From: "Paul E. McKenney" <[email protected]>
This commit adds an isidle and jiffies argument to force_qs_rnp(), dyntick_save_progress_counter(), and rcu_implicit_dynticks_qs() to enable RCU's force-quiescent-state process to check for full-system idle.
--- kernel/rcutree.c | 23 ++++++++++++++++------- 1 file changed, 16 insertions(+), 7 deletions(-)
kernel/rcutree.c +16 -7
@@ -231,7 +231,9 @@ module_param(jiffies_till_next_fqs, ulong, 0644);static void rcu_start_gp_advanced (struct rcu_state *rsp,struct rcu_node *rnp,struct rcu_data *rdp); -static void force_qs_rnp (struct rcu_state *rsp,int (*f)(struct rcu_data *)); +static void force_qs_rnp (struct rcu_state *rsp, +int (*f)(struct rcu_data *,bool *,unsigned long *), +bool *isidle,unsigned long *maxj);static void force_quiescent_state (struct rcu_state *rsp);static int rcu_pending (int cpu);
@@ -715,7 +717,8 @@ static int rcu_is_cpu_rrupt_from_idle(void)* credit them with an implicit quiescent state. Return 1 if this CPU * is in dynticks idle mode, which is an extended quiescent state. */ -static int dyntick_save_progress_counter (struct rcu_data *rdp) +static int dyntick_save_progress_counter (struct rcu_data *rdp, +bool *isidle,unsigned long *maxj) { rdp->dynticks_snap =atomic_add_return (0 , &rdp->dynticks->dynticks);return (rdp->dynticks_snap &0x1 ) ==0 ;
@@ -727,7 +730,8 @@ static int dyntick_save_progress_counter(struct rcu_data *rdp)* idle state since the last call to dyntick_save_progress_counter() * for this same CPU, or by virtue of having been offline. */ -static int rcu_implicit_dynticks_qs (struct rcu_data *rdp) +static int rcu_implicit_dynticks_qs (struct rcu_data *rdp, +bool *isidle,unsigned long *maxj) {unsigned int curr;unsigned int snap;
@@ -1348,16 +1352,19 @@ static int rcu_gp_init(struct rcu_state *rsp)int rcu_gp_fqs (struct rcu_state *rsp,int fqs_state_in) {int fqs_state = fqs_state_in; +bool isidle =0 ; +unsigned long maxj;struct rcu_node *rnp =rcu_get_root (rsp); rsp->n_force_qs++;if (fqs_state ==RCU_SAVE_DYNTICK ) {/* Collect dyntick-idle snapshots. */ -force_qs_rnp (rsp, dyntick_save_progress_counter); +force_qs_rnp (rsp, dyntick_save_progress_counter, + &isidle, &maxj); fqs_state =RCU_FORCE_QS ; }else {/* Handle dyntick-idle and offline CPUs. */ -force_qs_rnp (rsp, rcu_implicit_dynticks_qs); +force_qs_rnp (rsp, rcu_implicit_dynticks_qs, &isidle, &maxj); }/* Clear flag to prevent immediate re-entry. */ if (ACCESS_ONCE (rsp->gp_flags) &RCU_GP_FLAG_FQS ) {
@@ -2058,7 +2065,9 @@ void rcu_check_callbacks(int cpu, int user)* * The caller must have suppressed start of new grace periods. */ -static void force_qs_rnp (struct rcu_state *rsp,int (*f)(struct rcu_data *)) +static void force_qs_rnp (struct rcu_state *rsp, +int (*f)(struct rcu_data *,bool *,unsigned long *), +bool *isidle,unsigned long *maxj) {unsigned long bit;int cpu;
@@ -2082,7 +2091,7 @@ static void force_qs_rnp(struct rcu_state *rsp, int (*f)(struct rcu_data *)) bit =1 ;for (; cpu <= rnp->grphi; cpu++, bit <<=1 ) {if ((rnp->qsmask & bit) !=0 && -f (per_cpu_ptr (rsp->rda, cpu))) +f (per_cpu_ptr (rsp->rda, cpu), isidle, maxj)) mask |= bit; }if (mask !=0 ) {
Signature · 1 line
1.8.1.5
RFC PATCH 5/8 nohz_full: Add full-system idle states and variables
In reply to Paul E. McKenneyFrom: "Paul E. McKenney" <[email protected]>
This commit adds control variables and states for full-system idle. The system will progress through the states in numerical order when the system is fully idle (other than the timekeeping CPU), and reset down to the initial state if any non-timekeeping CPU goes non-idle. The current state is kept in full_sysidle_state.
A RCU_SYSIDLE_SMALL macro is defined, and systems with this number of CPUs or fewer move through the states more aggressively. The idea is that the resulting memory contention is less of a problem on small systems. Architectures can adjust this value (which defaults to 8) using CONFIG_ARCH_RCU_SYSIDLE_SMALL.
One flavor of RCU will be in charge of driving the state machine, defined by rcu_sysidle_state. This should be the busiest flavor of RCU.
--- kernel/rcutree_plugin.h | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+)
kernel/rcutree_plugin.h +27 -0
@@ -2380,6 +2380,33 @@ static void rcu_kick_nohz_cpu(int cpu)#ifdef CONFIG_NO_HZ_FULL_SYSIDLE /* +* Handle small systems specially, accelerating their transition into +* full idle state. Allow arches to override this code's idea of +* what constitutes a "small" system. +*/ +#ifdef CONFIG_ARCH_RCU_SYSIDLE_SMALL +#define RCU_SYSIDLE_SMALL CONFIG_ARCH_RCU_SYSIDLE_SMALL +#else /* #ifdef CONFIG_ARCH_RCU_SYSIDLE_SMALL */ +#define RCU_SYSIDLE_SMALL 8 +#endif + +/* +* Define RCU flavor that holds sysidle state. This needs to be the +* most active flavor of RCU. +*/ +#ifdef CONFIG_PREEMPT_RCU +static struct rcu_state __maybe_unused *rcu_sysidle_state = &rcu_preempt_state; +#else /* #ifdef CONFIG_PREEMPT_RCU */ +static struct rcu_state __maybe_unused *rcu_sysidle_state = &rcu_sched_state; +#endif /* #else #ifdef CONFIG_PREEMPT_RCU */ + +static int __maybe_unused full_sysidle_state;/* Current system-idle state. */ +#define RCU_SYSIDLE_NOT 0/* Some CPU is not idle. */ +#define RCU_SYSIDLE_SHORT 1/* All CPUs idle for brief period. */ +#define RCU_SYSIDLE_FULL 2/* All CPUs idle, ready for sysidle. */ +#define RCU_SYSIDLE_FULL_NOTED 3/* Actually entered sysidle state. */ + +/* * Invoked to note exit from irq or task transition to idle. Note that * usermode execution does -not- count as idle here! The caller must * have disabled interrupts.
Signature · 1 line
1.8.1.5
Quoted 5 lines · Paul E. McKenney
Note that this version pays attention to CPUs that have taken an NMI from idle. It is not clear to me that NMI handlers can safely access the time on a system that is long-term idle. Unless someone tells me that it is somehow safe to access time from an NMI from idle, I will remove NMI support in the next version.
NMI cannot access any time related functions independent of NOHZ, long term idle or whatever you come up with:
write_seqcount_begin(&timekeeper_seq);
---> NMI
...
do {
seq = read_seqcount_begin(&timekeeper_seq);
} while (read_seqcount_retry(&timekeeper_seq, seq));Guess how well that works ....
Thanks,
tglx
Quoted 12 lines · Thomas Gleixner
Quoted 5 lines · Paul E. McKenney
Note that this version pays attention to CPUs that have taken an NMI from idle. It is not clear to me that NMI handlers can safely access the time on a system that is long-term idle. Unless someone tells me that it is somehow safe to access time from an NMI from idle, I will remove NMI support in the next version.
NMI cannot access any time related functions independent of NOHZ, long term idle or whatever you come up with:
write_seqcount_begin(&timekeeper_seq);
Quoted 7 lines
---> NMI
... do { seq = read_seqcount_begin(&timekeeper_seq); } while (read_seqcount_retry(&timekeeper_seq, seq));Guess how well that works ....
Woo-hoo!!! I will yank the NMI support on the next version. Thank you for the info!
Thanx, Paul
Quoted 18 lines · Thomas Gleixner
Quoted 5 lines · Paul E. McKenney
Note that this version pays attention to CPUs that have taken an NMI from idle. It is not clear to me that NMI handlers can safely access the time on a system that is long-term idle. Unless someone tells me that it is somehow safe to access time from an NMI from idle, I will remove NMI support in the next version.
NMI cannot access any time related functions independent of NOHZ, long term idle or whatever you come up with:
write_seqcount_begin(&timekeeper_seq);---> NMI
... do { seq = read_seqcount_begin(&timekeeper_seq); } while (read_seqcount_retry(&timekeeper_seq, seq));
Quoted 6 lines
Guess how well that works ....
Thanks,
tglx
Is this something worth fixing? One of the things on my infinitely long todo list is to replace that seqcount with a wait-free data structure, in which case this would be okay. I don't care about NMIs, but this would mean that clock_gettime would never stall just because the timekeeping code was running somewhere -- at worse you'd get a couple extra cache misses.
The data structure is described here:
http://link.springer.com/chapter/10.1007%2F978-3-540-92221-6_40
(Sorry, this was my first paper and is therefore not so well written. Also, it costs $30, although I think I'm allowed to email copies out and probably even host them on a website somewhere.)
The main downside would be a possible loss of monotonicity, like this:
Thread a: read the timekeeping data
Thread b: update the timekeeping data
Thread c: start and finish reading the time (using new data) Thread a: read new raw clock value but compute using old timekeeping data
This would be fixable.
The data structure is essentially an array of copies of the protected data, which can be called bin 0, 1, 2, ..., N. The data is versioned, just like with seqcount. Bin i contains the most recent copy of the data that had a version number that's a multiple of 2^i, but any bin can also be marked as invalid if it's being written.
To write: update all bins that need updating (that is 1 + num trailing zeros in the new version number), starting at the highest number.
To read starting at bin i: try to read bin i (just like with a seqcount). If that fails, then recursively read starting at bin i+1. As a double-check, re-try bin i. If the retry fails but the recursive read succeeded, return the value from the recursive read.
The only way this can fail is if you race with ~2^N writes. You can try to read in a loop to avoid this problem.
Unlike a seqcount, you need to race with more than 1 write, which eliminates this deadlock -- writers have to make continuous progress for readers to get stuck. But it's extremely unlikely that a reader ever has to loop.
--Andy
Quoted 29 lines · Paul E. McKenney
Whenever there is at least one non-idle CPU, it is necessary to periodically update timekeeping information. Before
NO_HZ_FULL, this updating was carried out by the scheduling-clock tick, which ran on every non-idle CPU. With the advent ofNO_HZ_FULL, it is possible to have non-idle CPUs that are not receiving scheduling-clock ticks. This possibility is handled by assigning a timekeeping CPU that continues taking scheduling-clock ticks.Unfortunately, timekeeping CPU continues taking scheduling-clock interrupts even when all other CPUs are completely idle, which is not so good for energy efficiency and battery lifetime. Clearly, it would be good to turn off the timekeeping CPU's scheduling-clock tick when all CPUs are completely idle. This is conceptually simple, but we also need good performance and scalability on large systems, which rules out implementations based on frequently updated global counts of non-idle CPUs as well as implementations that frequently scan all CPUs. Nevertheless, we need a single global indicator in order to keep the overhead of checking acceptably low.
The chosen approach is to enforce hysteresis on the non-idle to full-system-idle transition, with the amount of hysteresis increasing linearly with the number of CPUs, thus keeping contention acceptably low. This approach piggybacks on RCU's existing force-quiescent-state scanning of idle CPUs, which has the advantage of avoiding the scan entirely on busy systems that have high levels of multiprogramming. This scan take per-CPU idleness information and feeds it into a state machine that applies the level of hysteresis required to arrive at a single full-system-idle indicator.
Quoted 5 lines
Note that this version pays attention to CPUs that have taken an NMI from idle. It is not clear to me that NMI handlers can safely access the time on a system that is long-term idle. Unless someone tells me that it is somehow safe to access time from an NMI from idle, I will remove NMI support in the next version.
Using perf it is 'possible' to come near; we use local_clock() from NMI context. It will do a TSC read.
On systems where the TSC is usable we'll end up with a sane timestamp; on systems where we need the whole kernel/sched/clock.c song and dance routine we'll return a stable time-stamp when called from long idle.
I don't think there's anything we can do better there.
Quoted 48 lines · Andy Lutomirski
Quoted 18 lines · Thomas Gleixner
Quoted 5 lines · Paul E. McKenney
Note that this version pays attention to CPUs that have taken an NMI from idle. It is not clear to me that NMI handlers can safely access the time on a system that is long-term idle. Unless someone tells me that it is somehow safe to access time from an NMI from idle, I will remove NMI support in the next version.
NMI cannot access any time related functions independent of NOHZ, long term idle or whatever you come up with:
write_seqcount_begin(&timekeeper_seq);---> NMI
... do { seq = read_seqcount_begin(&timekeeper_seq); } while (read_seqcount_retry(&timekeeper_seq, seq));Quoted 6 lines
Guess how well that works ....
Thanks,
tglx
Is this something worth fixing? One of the things on my infinitely long todo list is to replace that seqcount with a wait-free data structure, in which case this would be okay. I don't care about NMIs, but this would mean that
clock_gettimewould never stall just because the timekeeping code was running somewhere -- at worse you'd get a couple extra cache misses.The data structure is described here:
http://link.springer.com/chapter/10.1007%2F978-3-540-92221-6_40
(Sorry, this was my first paper and is therefore not so well written. Also, it costs $30, although I think I'm allowed to email copies out and probably even host them on a website somewhere.)
The main downside would be a possible loss of monotonicity, like this:
Thread a: read the timekeeping data
Thread b: update the timekeeping data
Thread c: start and finish reading the time (using new data) Thread a: read new raw clock value but compute using old timekeeping data
Quoted 7 lines
This would be fixable.
The data structure is essentially an array of copies of the protected data, which can be called bin 0, 1, 2, ..., N. The data is versioned, just like with seqcount. Bin i contains the most recent copy of the data that had a version number that's a multiple of 2^i, but any bin can also be marked as invalid if it's being written.
If I remember correctly, something like this was proposed some years back, but was rejected because it was not possible to set a bound on how long a given thread would be using a given array element, which could result in all elements being both in use and out of date.
It is possible to avoid this, but the only way I can see to do so re-introduces retries.
Quoted 8 lines
To write: update all bins that need updating (that is 1 + num trailing zeros in the new version number), starting at the highest number.
To read starting at bin i: try to read bin i (just like with a seqcount). If that fails, then recursively read starting at bin i+1. As a double-check, re-try bin i. If the retry fails but the recursive read succeeded, return the value from the recursive read.
Quoted 7 lines
The only way this can fail is if you race with ~2^N writes. You can try to read in a loop to avoid this problem.
Unlike a seqcount, you need to race with more than 1 write, which eliminates this deadlock -- writers have to make continuous progress for readers to get stuck. But it's extremely unlikely that a reader ever has to loop.
Unless I am missing something, you still have to have readers loop, but reduce the probability of them having to do so. Assuming that you were willing to reuse old entries, you could avoid the deadlock that Thomas pointed out, but at the cost of reusing an arbitrarily old entry in the case where the NMI happened at the end of a long full-system idle period. Which might not be such a good thing!
Therefore, I still intend to remove the NMI detection.
Thanx, Paul
Quoted 36 lines · Peter Zijlstra
Quoted 29 lines · Paul E. McKenney
Whenever there is at least one non-idle CPU, it is necessary to periodically update timekeeping information. Before
NO_HZ_FULL, this updating was carried out by the scheduling-clock tick, which ran on every non-idle CPU. With the advent ofNO_HZ_FULL, it is possible to have non-idle CPUs that are not receiving scheduling-clock ticks. This possibility is handled by assigning a timekeeping CPU that continues taking scheduling-clock ticks.Unfortunately, timekeeping CPU continues taking scheduling-clock interrupts even when all other CPUs are completely idle, which is not so good for energy efficiency and battery lifetime. Clearly, it would be good to turn off the timekeeping CPU's scheduling-clock tick when all CPUs are completely idle. This is conceptually simple, but we also need good performance and scalability on large systems, which rules out implementations based on frequently updated global counts of non-idle CPUs as well as implementations that frequently scan all CPUs. Nevertheless, we need a single global indicator in order to keep the overhead of checking acceptably low.
The chosen approach is to enforce hysteresis on the non-idle to full-system-idle transition, with the amount of hysteresis increasing linearly with the number of CPUs, thus keeping contention acceptably low. This approach piggybacks on RCU's existing force-quiescent-state scanning of idle CPUs, which has the advantage of avoiding the scan entirely on busy systems that have high levels of multiprogramming. This scan take per-CPU idleness information and feeds it into a state machine that applies the level of hysteresis required to arrive at a single full-system-idle indicator.
Quoted 5 lines
Note that this version pays attention to CPUs that have taken an NMI from idle. It is not clear to me that NMI handlers can safely access the time on a system that is long-term idle. Unless someone tells me that it is somehow safe to access time from an NMI from idle, I will remove NMI support in the next version.
Quoted 8 lines
Using perf it is 'possible' to come near; we use
local_clock()from NMI context. It will do a TSC read.On systems where the TSC is usable we'll end up with a sane timestamp; on systems where we need the whole
kernel/sched/clock.csong and dance routine we'll return a stable time-stamp when called from long idle.I don't think there's anything we can do better there.
Just to make sure I understand... You are saying that it is OK for NO_HZ_FULL to shut down timekeeping if all CPUs are idle, even if some of them are taking NMIs from time to time, right?
Thanx, Paul
Quoted 3 lines · Paul E. McKenney
Just to make sure I understand... You are saying that it is OK for
NO_HZ_FULLto shut down timekeeping if all CPUs are idle, even if some of them are taking NMIs from time to time, right?
Yeah.. its what we currently do and I don't see any reason to have NO_HZ_FULL behave differently there.
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Paul E. McKenney
Just to make sure I understand... You are saying that it is OK for
NO_HZ_FULLto shut down timekeeping if all CPUs are idle, even if some of them are taking NMIs from time to time, right?Yeah.. its what we currently do and I don't see any reason to have
NO_HZ_FULLbehave differently there.
Whew!!! ;-)
Thanx, Paul