Parallelize and economize NOCB kthread wakeups
Subsystems (2)
RFC PATCH 1/1 Parallelize and economize NOCB kthread wakeups
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Documentation/kernel-parameters.txt +7 -0
@@ -2796,6 +2796,13 @@ bytes respectively. Such letter suffixes can also be entirely omitted. quiescent states. Units are jiffies, minimum value is one, and maximum value is HZ. + rcutree.rcu_nocb_leader_stride= [KNL] + Set the number of NOCB kthread groups, which + defaults to the square root of the number of + CPUs. Larger numbers reduces the wakeup overhead + on the per-CPU grace-period kthreads, but increases + that same overhead on each group's leader. + rcutree.qhimark= [KNL] Set threshold of queued RCU callbacks beyond which batch limiting is disabled.
kernel/rcu/tree.h +26 -2
@@ -331,11 +331,29 @@ struct rcu_data {struct rcu_head **nocb_tail;atomic_long_t nocb_q_count;/* # CBs waiting for kthread */ atomic_long_t nocb_q_count_lazy;/* (approximate). */ +struct rcu_head *nocb_follower_head;/* CBs ready to invoke. */ +struct rcu_head **nocb_follower_tail; +atomic_long_t nocb_follower_count;/* # CBs ready to invoke. */ +atomic_long_t nocb_follower_count_lazy;/* (approximate). */ int nocb_p_count;/* # CBs being invoked by kthread */ int nocb_p_count_lazy;/* (approximate). */ wait_queue_head_t nocb_wq;/* For nocb kthreads to sleep on. */ struct task_struct *nocb_kthread;bool nocb_defer_wakeup;/* Defer wakeup of nocb_kthread. */ + +/* The following fields are used by the leader, hence own cacheline. */ +struct rcu_head *nocb_gp_head____cacheline_internodealigned_in_smp ; +/* CBs waiting for GP. */ +struct rcu_head **nocb_gp_tail; +long nocb_gp_count; +long nocb_gp_count_lazy; +bool nocb_leader_wake;/* Is the nocb leader thread awake? */ +struct rcu_data *nocb_next_follower; +/* Next follower in wakeup chain. */ + +/* The following fields are used by the follower, hence new cachline. */ +struct rcu_data *nocb_leader____cacheline_internodealigned_in_smp ; +/* Leader CPU takes GP-end wakeups. */ #endif /* #ifdef CONFIG_RCU_NOCB_CPU */ /* 8) RCU CPU stall data. */
@@ -583,8 +601,14 @@ static bool rcu_nohz_full_cpu(struct rcu_state *rsp);/* Sum up queue lengths for tracing. */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll) { - *ql =atomic_long_read (&rdp->nocb_q_count) + rdp->nocb_p_count; - *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + rdp->nocb_p_count_lazy; + *ql =atomic_long_read (&rdp->nocb_q_count) + + rdp->nocb_p_count + +atomic_long_read (&rdp->nocb_follower_count) + + rdp->nocb_p_count + rdp->nocb_gp_count; + *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + + rdp->nocb_p_count_lazy + +atomic_long_read (&rdp->nocb_follower_count_lazy) + + rdp->nocb_p_count_lazy + rdp->nocb_gp_count_lazy; }#else /* #ifdef CONFIG_RCU_NOCB_CPU */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll)
kernel/rcu/tree_plugin.h +211 -41
311 lines not on this page · raw message
Mathieu Desnoyers
reviewer----- Original Message -----
Quoted 29 lines
From: "Paul E. McKenney" <[email protected]>
To: [email protected], [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], "mathieu desnoyers" <[email protected]>, [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Sent: Friday, June 27, 2014 10:20:38 AM
Subject: [PATCH RFC tip/core/rcu] Parallelize and economize NOCB kthread wakeupsAn 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
If I understand your approach correctly, it looks like the callbacks are moved from the follower threads (per CPU) to leader threads (for a group of CPUs). I'm concerned that moving those callbacks to leader threads would increase cache trashing, since the callbacks would be often executed from a different CPU than the CPU which enqueued the work. In a case where cgroups/affinity are used to pin kthreads to specific CPUs to minimize cache trashing, I'm concerned that this approach could degrade performance.
Would there be another way to distribute the wake up that would keep callbacks local to their enqueuing CPU ?
Or am I missing something important ?
Thanks,
Mathieu
Quoted 406 lines
Reported-by Rik van Riel <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Documentation/kernel-parameters.txt +0
-0@@ -2796,6 +2796,13 @@ bytes respectively. Such letter suffixes can also beentirely omitted.
Documentation/kernel-parameters.txt +7
-0quiescent states. Units are jiffies, minimum value is one, and maximum value is HZ. + rcutree.rcu_nocb_leader_stride= [KNL] + Set the number of NOCB kthread groups, which + defaults to the square root of the number of + CPUs. Larger numbers reduces the wakeup overhead + on the per-CPU grace-period kthreads, but increases + that same overhead on each group's leader. + rcutree.qhimark= [KNL] Set threshold of queued RCU callbacks beyond which batch limiting is disabled.kernel/rcu/tree.h +26
-2@@ -331,11 +331,29 @@ struct rcu_data {struct rcu_head **nocb_tail;atomic_long_t nocb_q_count;/* # CBs waiting for kthread */ atomic_long_t nocb_q_count_lazy;/* (approximate). */ +struct rcu_head *nocb_follower_head;/* CBs ready to invoke. */ +struct rcu_head **nocb_follower_tail; +atomic_long_t nocb_follower_count;/* # CBs ready to invoke. */ +atomic_long_t nocb_follower_count_lazy;/* (approximate). */ int nocb_p_count;/* # CBs being invoked by kthread */ int nocb_p_count_lazy;/* (approximate). */ wait_queue_head_t nocb_wq;/* For nocb kthreads to sleep on. */ struct task_struct *nocb_kthread;bool nocb_defer_wakeup;/* Defer wakeup of nocb_kthread. */ + +/* The following fields are used by the leader, hence own cacheline. */ +struct rcu_head *nocb_gp_head____cacheline_internodealigned_in_smp ; +/* CBs waiting for GP. */ +struct rcu_head **nocb_gp_tail; +long nocb_gp_count; +long nocb_gp_count_lazy; +bool nocb_leader_wake;/* Is the nocb leader thread awake? */ +struct rcu_data *nocb_next_follower; +/* Next follower in wakeup chain. */ + +/* The following fields are used by the follower, hence new cachline. */ +struct rcu_data *nocb_leader____cacheline_internodealigned_in_smp ; +/* Leader CPU takes GP-end wakeups. */ #endif /* #ifdef CONFIG_RCU_NOCB_CPU */ /* 8) RCU CPU stall data. */ @@ -583,8 +601,14 @@ static bool rcu_nohz_full_cpu(struct rcu_state *rsp);/* Sum up queue lengths for tracing. */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll) { - *ql =atomic_long_read (&rdp->nocb_q_count) + rdp->nocb_p_count; - *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + rdp->nocb_p_count_lazy; + *ql =atomic_long_read (&rdp->nocb_q_count) + + rdp->nocb_p_count + +atomic_long_read (&rdp->nocb_follower_count) + + rdp->nocb_p_count + rdp->nocb_gp_count; + *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + + rdp->nocb_p_count_lazy + +atomic_long_read (&rdp->nocb_follower_count_lazy) + + rdp->nocb_p_count_lazy + rdp->nocb_gp_count_lazy; }#else /* #ifdef CONFIG_RCU_NOCB_CPU */ static inline void
rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)kernel/rcu/tree_plugin.h +18
-1@@ -2060,6 +2060,22 @@ bool rcu_is_nocb_cpu(int cpu)#endif /* #ifndef CONFIG_RCU_NOCB_CPU_ALL */ /* +* Kick the leader kthread for this NOCB group. +*/ +static void wake_nocb_leader (struct rcu_data *rdp,bool force) +{ +struct rcu_data *rdp_leader = rdp->nocb_leader; + +if (!ACCESS_ONCE (rdp_leader->nocb_kthread)) +return ; +if (!ACCESS_ONCE (rdp_leader->nocb_leader_wake) || force) { +/* Prior xchg orders against prior callback enqueue. */ +ACCESS_ONCE (rdp_leader->nocb_leader_wake) = true; +wake_up (&rdp_leader->nocb_wq); + } +} + +/* * Enqueue the specified string of rcu_head structures onto the specified * CPU's no-CBs lists. The CPU is specified by rdp, the head of the * string by rhp, and the tail of the string by rhtp. The non-lazy/lazy @@ -2093,7 +2109,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, len =atomic_long_read (&rdp->nocb_q_count);if (old_rhpp == &rdp->nocb_head) {if (!irqs_disabled_flags (flags)) { -wake_up (&rdp->nocb_wq);/* ... if queue was empty ... */ +/* ... if queue was empty ... */ +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeEmpty" ));kernel/rcu/tree_plugin.h +2
-1}else {@@ -2103,7 +2120,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, } rdp->qlen_last_fqs_check =0 ; }else if (len > rdp->qlen_last_fqs_check + qhimark) { -wake_up_process (t);/* ... or if many callbacks queued. */ +/* ... or if many callbacks queued. */ +wake_nocb_leader (rdp, true); rdp->qlen_last_fqs_check =LONG_MAX /2 ;trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeOvf" ));kernel/rcu/tree_plugin.h +158
-39}else {@@ -2213,13 +2231,150 @@ static void rcu_nocb_wait_gp(struct rcu_data *rdp) }/* +* Leaders come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_leader_wait (struct rcu_data *my_rdp) +{ +bool firsttime = true; +bool gotcbs; +struct rcu_data *rdp; +struct rcu_head **tail; + +wait_again: + +/* Wait for callbacks to appear. */ +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Sleep" ); +wait_event_interruptible (my_rdp->nocb_wq, +ACCESS_ONCE (my_rdp->nocb_leader_wake)); +/* Memory barrier handled by smp_mb() calls below and repoll. */ + }else if (firsttime) { + firsttime = false;/* Don't drown trace log with "Poll"! */ +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Poll" ); + } + +/* +* Each pass through the following loop checks a follower for CBs. +* We are our own first follower. Any CBs found are moved to +* nocb_gp_head, where they await a grace period. +*/ + gotcbs = false; +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { + rdp->nocb_gp_head =ACCESS_ONCE (rdp->nocb_head); +if (!rdp->nocb_gp_head) +continue ;/* No CBs here, try next follower. */ + +/* Move callbacks to wait-for-GP list, which is empty. */ +ACCESS_ONCE (rdp->nocb_head) =NULL ; + rdp->nocb_gp_tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); + rdp->nocb_gp_count =atomic_xchg (&rdp->nocb_q_count,0 ); + rdp->nocb_gp_count_lazy = +atomic_xchg (&rdp->nocb_q_count_lazy,0 ); + gotcbs = true; + } + +/* +* If there were no callbacks, sleep a bit, rescan after a +* memory barrier, and go retry. +*/ +if (unlikely (!gotcbs)) { +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + +/* Rescan in case we were a victim of memory ordering. */ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) +if (ACCESS_ONCE (rdp->nocb_head)) { +/* Found CB, so short-circuit next wait. */ + my_rdp->nocb_leader_wake = true; +break ; + } + goto wait_again; + } + +/* Wait for one grace period. */ +rcu_nocb_wait_gp (my_rdp); + +/* +* We left ->nocb_leader_wake set to reduce cache thrashing. +* We clear it now, but recheck for new callbacks while +* traversing our follower list. +*/ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan of ->nocb_head. */ + +/* Each pass through the following loop wakes a follower, if needed. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { +if (ACCESS_ONCE (rdp->nocb_head)) + my_rdp->nocb_leader_wake = true;/* No need to wait. */ +if (!rdp->nocb_gp_head) +continue ;/* No CBs, so no need to wake follower. */ + +/* Append callbacks to follower's "done" list. */ + tail =xchg (&rdp->nocb_follower_tail, rdp->nocb_gp_tail); + *tail = rdp->nocb_gp_head; +atomic_long_add (rdp->nocb_gp_count, &rdp->nocb_follower_count); +atomic_long_add (rdp->nocb_gp_count_lazy, + &rdp->nocb_follower_count_lazy); +if (rdp != my_rdp && tail == &rdp->nocb_follower_head) { +/* +* List was empty, wake up the follower. +* Memory barriers supplied by atomic_long_add(). +*/ +wake_up (&rdp->nocb_wq); + } + } + +/* If we (the leader) don't have CBs, go wait some more. */ +if (!my_rdp->nocb_follower_head) + goto wait_again; +} + +/* +* Followers come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_follower_wait (struct rcu_data *rdp) +{ +bool firsttime = true; + +for (;;) { +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"FollowerSleep" ); +wait_event_interruptible (rdp->nocb_wq, +ACCESS_ONCE (rdp->nocb_follower_head)); + }else if (firsttime) { +/* Don't drown trace log with "Poll"! */ + firsttime = false; +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"Poll" ); + } +if (smp_load_acquire (&rdp->nocb_follower_head)) { +/* ^^^ Ensure CB invocation follows _head test. */ +return ; + } +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + } +} + +/* * Per-rcu_data kthread, but only for no-CBs CPUs. Each kthread invokes -* callbacks queued by the corresponding no-CBs CPU. +* callbacks queued by the corresponding no-CBs CPU, however, there is +* an optional leader-follower relationship so that the grace-period +* kthreads don't have to do quite so many wakeups. */ static int rcu_nocb_kthread (void *arg) {int c, cl; -bool firsttime =1 ;struct rcu_head *list;struct rcu_head *next;struct rcu_head **tail;@@ -2227,41 +2382,22 @@ static int rcu_nocb_kthread(void *arg)/* Each pass through this loop invokes one batch of callbacks */ for (;;) { -/* If not polling, wait for next batch of callbacks. */ -if (!rcu_nocb_poll) { -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Sleep" )); -wait_event_interruptible (rdp->nocb_wq, rdp->nocb_head); -/* Memory barrier provide by xchg() below. */ - }else if (firsttime) { - firsttime =0 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Poll" )); - } - list =ACCESS_ONCE (rdp->nocb_head); -if (!list) { -if (!rcu_nocb_poll) -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeEmpty" )); -schedule_timeout_interruptible (1 ); -flush_signals (current); -continue ; - } - firsttime =1 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeNonEmpty" )); - -/* -* Extract queued callbacks, update counts, and wait -* for a grace period to elapse. -*/ -ACCESS_ONCE (rdp->nocb_head) =NULL ; - tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); - c =atomic_long_xchg (&rdp->nocb_q_count,0 ); - cl =atomic_long_xchg (&rdp->nocb_q_count_lazy,0 ); -ACCESS_ONCE (rdp->nocb_p_count) += c; -ACCESS_ONCE (rdp->nocb_p_count_lazy) += cl; -rcu_nocb_wait_gp (rdp); +/* Wait for callbacks. */ +if (rdp->nocb_leader == rdp) +nocb_leader_wait (rdp); +else +nocb_follower_wait (rdp); + +/* Pull the ready-to-invoke callbacks onto local list. */ + list =ACCESS_ONCE (rdp->nocb_follower_head); +BUG_ON (!list); +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"WokeNonEmpty" ); +ACCESS_ONCE (rdp->nocb_follower_head) =NULL ; + tail =xchg (&rdp->nocb_follower_tail, &rdp->nocb_follower_head); + c =atomic_long_xchg (&rdp->nocb_follower_count,0 ); + cl =atomic_long_xchg (&rdp->nocb_follower_count_lazy,0 ); + rdp->nocb_p_count += c; + rdp->nocb_p_count_lazy += cl;/* Each pass through the following loop invokes a callback. */ trace_rcu_batch_start (rdp->rsp->name, cl, c,-1 );@@ -2305,7 +2441,7 @@ static void do_nocb_deferred_wakeup(struct rcu_data *rdp)if (!rcu_nocb_need_deferred_wakeup (rdp))return ;ACCESS_ONCE (rdp->nocb_defer_wakeup) = false; -wake_up (&rdp->nocb_wq); +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("DeferredWakeEmpty" )); }@@ -2314,19 +2450,53 @@ static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp) { rdp->nocb_tail = &rdp->nocb_head;init_waitqueue_head (&rdp->nocb_wq); + rdp->nocb_follower_tail = &rdp->nocb_follower_head; } -/* Create a kthread for each RCU flavor for each no-CBs CPU. */ +/* How many follower CPU IDs per leader? Default of -1 for
sqrt(nr_cpu_ids). */kernel/rcu/tree_plugin.h +33
-0+static int rcu_nocb_leader_stride =-1 ; +module_param (rcu_nocb_leader_stride, int,0444 ); + +/* +* Create a kthread for each RCU flavor for each no-CBs CPU. +* Also initialize leader-follower relationships. +*/ static void __init rcu_spawn_nocb_kthreads (struct rcu_state *rsp) {int cpu; +int ls = rcu_nocb_leader_stride; +int nl =0 ;/* Next leader. */ struct rcu_data *rdp; +struct rcu_data *rdp_leader =NULL ;/* Suppress misguided gcc warn. */ +struct rcu_data *rdp_prev =NULL ;struct task_struct *t;if (rcu_nocb_mask ==NULL )return ; +if (ls ==-1 ) { + ls =int_sqrt (nr_cpu_ids); + rcu_nocb_leader_stride = ls; + } + +/* +* Each pass through this loop sets up one rcu_data structure and +* spawns one rcu_nocb_kthread(). +*/ for_each_cpu (cpu, rcu_nocb_mask) { rdp =per_cpu_ptr (rsp->rda, cpu); +if (rdp->cpu >= nl) { +/* New leader, set up for followers & next leader. */ + nl =DIV_ROUND_UP (rdp->cpu +1 , ls) * ls; + rdp->nocb_leader = rdp; + rdp_leader = rdp; + }else { +/* Another follower, link to previous leader. */ + rdp->nocb_leader = rdp_leader; + rdp_prev->nocb_next_follower = rdp; + } + rdp_prev = rdp; + +/* Spawn the kthread for this CPU. */ t =kthread_run (rcu_nocb_kthread, rdp,"rcuo%c/%d" , rsp->abbr, cpu);BUG_ON (IS_ERR (t));
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Mathieu Desnoyers
reviewer----- Original Message -----
Quoted 57 lines
From: "Mathieu Desnoyers" <[email protected]>
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Sent: Friday, June 27, 2014 11:01:27 AM
Subject: Re: [PATCH RFC tip/core/rcu] Parallelize and economize NOCB kthread wakeups----- Original Message -----
Quoted 33 lines
From: "Paul E. McKenney" <[email protected]>
To: [email protected], [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], "mathieu desnoyers" <[email protected]>, [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected],
[email protected], [email protected]
Sent: Friday, June 27, 2014 10:20:38 AM
Subject: [PATCH RFC tip/core/rcu] Parallelize and economize NOCB kthread wakeupsAn 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
If I understand your approach correctly, it looks like the callbacks are moved from the follower threads (per CPU) to leader threads (for a group of CPUs). I'm concerned that moving those callbacks to leader threads would increase cache trashing, since the callbacks would be often executed from a different CPU than the CPU which enqueued the work. In a case where cgroups/affinity are used to pin kthreads to specific CPUs to minimize cache trashing, I'm concerned that this approach could degrade performance.
Quoted 4 lines
Would there be another way to distribute the wake up that would keep callbacks local to their enqueuing CPU ?
Or am I missing something important ?
What I appear to have missed is that the leader moves the callbacks from the follower's structure _to_ another list within that same follower's structure, which ensures that callbacks are executed locally by the follower.
Sorry for the noise. ;-)
Thanks,
Mathieu
Quoted 418 lines
Thanks,
Mathieu
Quoted 397 lines
Reported-by Rik van Riel <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Documentation/kernel-parameters.txt +0
-0@@ -2796,6 +2796,13 @@ bytes respectively. Such letter suffixes can also beentirely omitted.
Documentation/kernel-parameters.txt +7
-0quiescent states. Units are jiffies, minimum value is one, and maximum value is HZ. + rcutree.rcu_nocb_leader_stride= [KNL] + Set the number of NOCB kthread groups, which + defaults to the square root of the number of + CPUs. Larger numbers reduces the wakeup overhead + on the per-CPU grace-period kthreads, but increases + that same overhead on each group's leader. + rcutree.qhimark= [KNL] Set threshold of queued RCU callbacks beyond which batch limiting is disabled.kernel/rcu/tree.h +26
-2@@ -331,11 +331,29 @@ struct rcu_data {struct rcu_head **nocb_tail;atomic_long_t nocb_q_count;/* # CBs waiting for kthread */ atomic_long_t nocb_q_count_lazy;/* (approximate). */ +struct rcu_head *nocb_follower_head;/* CBs ready to invoke. */ +struct rcu_head **nocb_follower_tail; +atomic_long_t nocb_follower_count;/* # CBs ready to invoke. */ +atomic_long_t nocb_follower_count_lazy;/* (approximate). */ int nocb_p_count;/* # CBs being invoked by kthread */ int nocb_p_count_lazy;/* (approximate). */ wait_queue_head_t nocb_wq;/* For nocb kthreads to sleep on. */ struct task_struct *nocb_kthread;bool nocb_defer_wakeup;/* Defer wakeup of nocb_kthread. */ + +/* The following fields are used by the leader, hence own cacheline. */ +struct rcu_head *nocb_gp_head____cacheline_internodealigned_in_smp ; +/* CBs waiting for GP. */ +struct rcu_head **nocb_gp_tail; +long nocb_gp_count; +long nocb_gp_count_lazy; +bool nocb_leader_wake;/* Is the nocb leader thread awake? */ +struct rcu_data *nocb_next_follower; +/* Next follower in wakeup chain. */ + +/* The following fields are used by the follower, hence new cachline. */ +struct rcu_data *nocb_leader____cacheline_internodealigned_in_smp ; +/* Leader CPU takes GP-end wakeups. */ #endif /* #ifdef CONFIG_RCU_NOCB_CPU */ /* 8) RCU CPU stall data. */ @@ -583,8 +601,14 @@ static bool rcu_nohz_full_cpu(struct rcu_state *rsp);/* Sum up queue lengths for tracing. */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll) { - *ql =atomic_long_read (&rdp->nocb_q_count) + rdp->nocb_p_count; - *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + rdp->nocb_p_count_lazy; + *ql =atomic_long_read (&rdp->nocb_q_count) + + rdp->nocb_p_count + +atomic_long_read (&rdp->nocb_follower_count) + + rdp->nocb_p_count + rdp->nocb_gp_count; + *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + + rdp->nocb_p_count_lazy + +atomic_long_read (&rdp->nocb_follower_count_lazy) + + rdp->nocb_p_count_lazy + rdp->nocb_gp_count_lazy; }#else /* #ifdef
CONFIG_RCU_NOCB_CPU*/
static inline voidrcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)kernel/rcu/tree_plugin.h +18
-1@@ -2060,6 +2060,22 @@ bool rcu_is_nocb_cpu(int cpu)#endif /* #ifndef CONFIG_RCU_NOCB_CPU_ALL */ /* +* Kick the leader kthread for this NOCB group. +*/ +static void wake_nocb_leader (struct rcu_data *rdp,bool force) +{ +struct rcu_data *rdp_leader = rdp->nocb_leader; + +if (!ACCESS_ONCE (rdp_leader->nocb_kthread)) +return ; +if (!ACCESS_ONCE (rdp_leader->nocb_leader_wake) || force) { +/* Prior xchg orders against prior callback enqueue. */ +ACCESS_ONCE (rdp_leader->nocb_leader_wake) = true; +wake_up (&rdp_leader->nocb_wq); + } +} + +/* * Enqueue the specified string of rcu_head structures onto the specified * CPU's no-CBs lists. The CPU is specified by rdp, the head of the * string by rhp, and the tail of the string by rhtp. The non-lazy/lazy @@ -2093,7 +2109,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, len =atomic_long_read (&rdp->nocb_q_count);if (old_rhpp == &rdp->nocb_head) {if (!irqs_disabled_flags (flags)) { -wake_up (&rdp->nocb_wq);/* ... if queue was empty ... */ +/* ... if queue was empty ... */ +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeEmpty" ));kernel/rcu/tree_plugin.h +2
-1}else {@@ -2103,7 +2120,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, } rdp->qlen_last_fqs_check =0 ; }else if (len > rdp->qlen_last_fqs_check + qhimark) { -wake_up_process (t);/* ... or if many callbacks queued. */ +/* ... or if many callbacks queued. */ +wake_nocb_leader (rdp, true); rdp->qlen_last_fqs_check =LONG_MAX /2 ;trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeOvf" ));kernel/rcu/tree_plugin.h +158
-39}else {@@ -2213,13 +2231,150 @@ static void rcu_nocb_wait_gp(struct rcu_data *rdp) }/* +* Leaders come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_leader_wait (struct rcu_data *my_rdp) +{ +bool firsttime = true; +bool gotcbs; +struct rcu_data *rdp; +struct rcu_head **tail; + +wait_again: + +/* Wait for callbacks to appear. */ +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Sleep" ); +wait_event_interruptible (my_rdp->nocb_wq, +ACCESS_ONCE (my_rdp->nocb_leader_wake)); +/* Memory barrier handled by smp_mb() calls below and repoll. */ + }else if (firsttime) { + firsttime = false;/* Don't drown trace log with "Poll"! */ +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Poll" ); + } + +/* +* Each pass through the following loop checks a follower for CBs. +* We are our own first follower. Any CBs found are moved to +* nocb_gp_head, where they await a grace period. +*/ + gotcbs = false; +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { + rdp->nocb_gp_head =ACCESS_ONCE (rdp->nocb_head); +if (!rdp->nocb_gp_head) +continue ;/* No CBs here, try next follower. */ + +/* Move callbacks to wait-for-GP list, which is empty. */ +ACCESS_ONCE (rdp->nocb_head) =NULL ; + rdp->nocb_gp_tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); + rdp->nocb_gp_count =atomic_xchg (&rdp->nocb_q_count,0 ); + rdp->nocb_gp_count_lazy = +atomic_xchg (&rdp->nocb_q_count_lazy,0 ); + gotcbs = true; + } + +/* +* If there were no callbacks, sleep a bit, rescan after a +* memory barrier, and go retry. +*/ +if (unlikely (!gotcbs)) { +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + +/* Rescan in case we were a victim of memory ordering. */ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) +if (ACCESS_ONCE (rdp->nocb_head)) { +/* Found CB, so short-circuit next wait. */ + my_rdp->nocb_leader_wake = true; +break ; + } + goto wait_again; + } + +/* Wait for one grace period. */ +rcu_nocb_wait_gp (my_rdp); + +/* +* We left ->nocb_leader_wake set to reduce cache thrashing. +* We clear it now, but recheck for new callbacks while +* traversing our follower list. +*/ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan of ->nocb_head. */ + +/* Each pass through the following loop wakes a follower, if needed. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { +if (ACCESS_ONCE (rdp->nocb_head)) + my_rdp->nocb_leader_wake = true;/* No need to wait. */ +if (!rdp->nocb_gp_head) +continue ;/* No CBs, so no need to wake follower. */ + +/* Append callbacks to follower's "done" list. */ + tail =xchg (&rdp->nocb_follower_tail, rdp->nocb_gp_tail); + *tail = rdp->nocb_gp_head; +atomic_long_add (rdp->nocb_gp_count, &rdp->nocb_follower_count); +atomic_long_add (rdp->nocb_gp_count_lazy, + &rdp->nocb_follower_count_lazy); +if (rdp != my_rdp && tail == &rdp->nocb_follower_head) { +/* +* List was empty, wake up the follower. +* Memory barriers supplied by atomic_long_add(). +*/ +wake_up (&rdp->nocb_wq); + } + } + +/* If we (the leader) don't have CBs, go wait some more. */ +if (!my_rdp->nocb_follower_head) + goto wait_again; +} + +/* +* Followers come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_follower_wait (struct rcu_data *rdp) +{ +bool firsttime = true; + +for (;;) { +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"FollowerSleep" ); +wait_event_interruptible (rdp->nocb_wq, +ACCESS_ONCE (rdp->nocb_follower_head)); + }else if (firsttime) { +/* Don't drown trace log with "Poll"! */ + firsttime = false; +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"Poll" ); + } +if (smp_load_acquire (&rdp->nocb_follower_head)) { +/* ^^^ Ensure CB invocation follows _head test. */ +return ; + } +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + } +} + +/* * Per-rcu_data kthread, but only for no-CBs CPUs. Each kthread invokes -* callbacks queued by the corresponding no-CBs CPU. +* callbacks queued by the corresponding no-CBs CPU, however, there is +* an optional leader-follower relationship so that the grace-period +* kthreads don't have to do quite so many wakeups. */ static int rcu_nocb_kthread (void *arg) {int c, cl; -bool firsttime =1 ;struct rcu_head *list;struct rcu_head *next;struct rcu_head **tail;@@ -2227,41 +2382,22 @@ static int rcu_nocb_kthread(void *arg)/* Each pass through this loop invokes one batch of callbacks */ for (;;) { -/* If not polling, wait for next batch of callbacks. */ -if (!rcu_nocb_poll) { -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Sleep" )); -wait_event_interruptible (rdp->nocb_wq, rdp->nocb_head); -/* Memory barrier provide by xchg() below. */ - }else if (firsttime) { - firsttime =0 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Poll" )); - } - list =ACCESS_ONCE (rdp->nocb_head); -if (!list) { -if (!rcu_nocb_poll) -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeEmpty" )); -schedule_timeout_interruptible (1 ); -flush_signals (current); -continue ; - } - firsttime =1 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeNonEmpty" )); - -/* -* Extract queued callbacks, update counts, and wait -* for a grace period to elapse. -*/ -ACCESS_ONCE (rdp->nocb_head) =NULL ; - tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); - c =atomic_long_xchg (&rdp->nocb_q_count,0 ); - cl =atomic_long_xchg (&rdp->nocb_q_count_lazy,0 ); -ACCESS_ONCE (rdp->nocb_p_count) += c; -ACCESS_ONCE (rdp->nocb_p_count_lazy) += cl; -rcu_nocb_wait_gp (rdp); +/* Wait for callbacks. */ +if (rdp->nocb_leader == rdp) +nocb_leader_wait (rdp); +else +nocb_follower_wait (rdp); + +/* Pull the ready-to-invoke callbacks onto local list. */ + list =ACCESS_ONCE (rdp->nocb_follower_head); +BUG_ON (!list); +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"WokeNonEmpty" ); +ACCESS_ONCE (rdp->nocb_follower_head) =NULL ; + tail =xchg (&rdp->nocb_follower_tail, &rdp->nocb_follower_head); + c =atomic_long_xchg (&rdp->nocb_follower_count,0 ); + cl =atomic_long_xchg (&rdp->nocb_follower_count_lazy,0 ); + rdp->nocb_p_count += c; + rdp->nocb_p_count_lazy += cl;/* Each pass through the following loop invokes a callback. */ trace_rcu_batch_start (rdp->rsp->name, cl, c,-1 );@@ -2305,7 +2441,7 @@ static void do_nocb_deferred_wakeup(struct rcu_data *rdp)if (!rcu_nocb_need_deferred_wakeup (rdp))return ;ACCESS_ONCE (rdp->nocb_defer_wakeup) = false; -wake_up (&rdp->nocb_wq); +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("DeferredWakeEmpty" )); }@@ -2314,19 +2450,53 @@ static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp) { rdp->nocb_tail = &rdp->nocb_head;init_waitqueue_head (&rdp->nocb_wq); + rdp->nocb_follower_tail = &rdp->nocb_follower_head; } -/* Create a kthread for each RCU flavor for each no-CBs CPU. */ +/* How many follower CPU IDs per leader? Default of -1 for
sqrt(nr_cpu_ids). */kernel/rcu/tree_plugin.h +26
-0+static int rcu_nocb_leader_stride =-1 ; +module_param (rcu_nocb_leader_stride, int,0444 ); + +/* +* Create a kthread for each RCU flavor for each no-CBs CPU. +* Also initialize leader-follower relationships. +*/ static void __init rcu_spawn_nocb_kthreads (struct rcu_state *rsp) {int cpu; +int ls = rcu_nocb_leader_stride; +int nl =0 ;/* Next leader. */ struct rcu_data *rdp; +struct rcu_data *rdp_leader =NULL ;/* Suppress misguided gcc warn. */ +struct rcu_data *rdp_prev =NULL ;struct task_struct *t;if (rcu_nocb_mask ==NULL )return ; +if (ls ==-1 ) { + ls =int_sqrt (nr_cpu_ids); + rcu_nocb_leader_stride = ls; + } + +/* +* Each pass through this loop sets up one rcu_data structure and +* spawns one rcu_nocb_kthread(). +*/ for_each_cpu (cpu, rcu_nocb_mask) { rdp =per_cpu_ptr (rsp->rda, cpu); +if (rdp->cpu >= nl) { +/* New leader, set up for followers & next leader. */ + nl =DIV_ROUND_UP (rdp->cpu +1 , ls) * ls; + rdp->nocb_leader = rdp; + rdp_leader = rdp; + }else {kernel/rcu/tree_plugin.h static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp) · line 2502
Quoted 10 lines
kernel/rcu/tree_plugin.h +7
-0+/* Another follower, link to previous leader. */ + rdp->nocb_leader = rdp_leader; + rdp_prev->nocb_next_follower = rdp; + } + rdp_prev = rdp; + +/* Spawn the kthread for this CPU. */ t =kthread_run (rcu_nocb_kthread, rdp,"rcuo%c/%d" , rsp->abbr, cpu);BUG_ON (IS_ERR (t));--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 61 lines · Mathieu Desnoyers
----- Original Message -----
Quoted 60 lines
From: "Mathieu Desnoyers" <[email protected]>
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Sent: Friday, June 27, 2014 11:01:27 AM
Subject: Re: [PATCH RFC tip/core/rcu] Parallelize and economize NOCB kthread wakeups----- Original Message -----
Quoted 33 lines
From: "Paul E. McKenney" <[email protected]>
To: [email protected], [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], "mathieu desnoyers" <[email protected]>, [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected],
[email protected], [email protected]
Sent: Friday, June 27, 2014 10:20:38 AM
Subject: [PATCH RFC tip/core/rcu] Parallelize and economize NOCB kthread wakeupsAn 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
If I understand your approach correctly, it looks like the callbacks are moved from the follower threads (per CPU) to leader threads (for a group of CPUs). I'm concerned that moving those callbacks to leader threads would increase cache trashing, since the callbacks would be often executed from a different CPU than the CPU which enqueued the work. In a case where cgroups/affinity are used to pin kthreads to specific CPUs to minimize cache trashing, I'm concerned that this approach could degrade performance.
Would there be another way to distribute the wake up that would keep callbacks local to their enqueuing CPU ?
Quoted 8 lines
Quoted 1 line
Or am I missing something important ?
What I appear to have missed is that the leader moves the callbacks from the follower's structure _to_ another list within that same follower's structure, which ensures that callbacks are executed locally by the follower.
Sorry for the noise. ;-)
Not a problem, and thank you for looking at the patch!
Thanx, Paul
Quoted 428 lines
Thanks,
Mathieu
Quoted 418 lines
Thanks,
Mathieu
Quoted 397 lines
Reported-by Rik van Riel <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Documentation/kernel-parameters.txt +0
-0@@ -2796,6 +2796,13 @@ bytes respectively. Such letter suffixes can also beentirely omitted.
Documentation/kernel-parameters.txt +7
-0quiescent states. Units are jiffies, minimum value is one, and maximum value is HZ. + rcutree.rcu_nocb_leader_stride= [KNL] + Set the number of NOCB kthread groups, which + defaults to the square root of the number of + CPUs. Larger numbers reduces the wakeup overhead + on the per-CPU grace-period kthreads, but increases + that same overhead on each group's leader. + rcutree.qhimark= [KNL] Set threshold of queued RCU callbacks beyond which batch limiting is disabled.kernel/rcu/tree.h +26
-2@@ -331,11 +331,29 @@ struct rcu_data {struct rcu_head **nocb_tail;atomic_long_t nocb_q_count;/* # CBs waiting for kthread */ atomic_long_t nocb_q_count_lazy;/* (approximate). */ +struct rcu_head *nocb_follower_head;/* CBs ready to invoke. */ +struct rcu_head **nocb_follower_tail; +atomic_long_t nocb_follower_count;/* # CBs ready to invoke. */ +atomic_long_t nocb_follower_count_lazy;/* (approximate). */ int nocb_p_count;/* # CBs being invoked by kthread */ int nocb_p_count_lazy;/* (approximate). */ wait_queue_head_t nocb_wq;/* For nocb kthreads to sleep on. */ struct task_struct *nocb_kthread;bool nocb_defer_wakeup;/* Defer wakeup of nocb_kthread. */ + +/* The following fields are used by the leader, hence own cacheline. */ +struct rcu_head *nocb_gp_head____cacheline_internodealigned_in_smp ; +/* CBs waiting for GP. */ +struct rcu_head **nocb_gp_tail; +long nocb_gp_count; +long nocb_gp_count_lazy; +bool nocb_leader_wake;/* Is the nocb leader thread awake? */ +struct rcu_data *nocb_next_follower; +/* Next follower in wakeup chain. */ + +/* The following fields are used by the follower, hence new cachline. */ +struct rcu_data *nocb_leader____cacheline_internodealigned_in_smp ; +/* Leader CPU takes GP-end wakeups. */ #endif /* #ifdef CONFIG_RCU_NOCB_CPU */ /* 8) RCU CPU stall data. */ @@ -583,8 +601,14 @@ static bool rcu_nohz_full_cpu(struct rcu_state *rsp);/* Sum up queue lengths for tracing. */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll) { - *ql =atomic_long_read (&rdp->nocb_q_count) + rdp->nocb_p_count; - *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + rdp->nocb_p_count_lazy; + *ql =atomic_long_read (&rdp->nocb_q_count) + + rdp->nocb_p_count + +atomic_long_read (&rdp->nocb_follower_count) + + rdp->nocb_p_count + rdp->nocb_gp_count; + *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + + rdp->nocb_p_count_lazy + +atomic_long_read (&rdp->nocb_follower_count_lazy) + + rdp->nocb_p_count_lazy + rdp->nocb_gp_count_lazy; }#else /* #ifdef
CONFIG_RCU_NOCB_CPU*/
static inline voidrcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)kernel/rcu/tree_plugin.h +18
-1@@ -2060,6 +2060,22 @@ bool rcu_is_nocb_cpu(int cpu)#endif /* #ifndef CONFIG_RCU_NOCB_CPU_ALL */ /* +* Kick the leader kthread for this NOCB group. +*/ +static void wake_nocb_leader (struct rcu_data *rdp,bool force) +{ +struct rcu_data *rdp_leader = rdp->nocb_leader; + +if (!ACCESS_ONCE (rdp_leader->nocb_kthread)) +return ; +if (!ACCESS_ONCE (rdp_leader->nocb_leader_wake) || force) { +/* Prior xchg orders against prior callback enqueue. */ +ACCESS_ONCE (rdp_leader->nocb_leader_wake) = true; +wake_up (&rdp_leader->nocb_wq); + } +} + +/* * Enqueue the specified string of rcu_head structures onto the specified * CPU's no-CBs lists. The CPU is specified by rdp, the head of the * string by rhp, and the tail of the string by rhtp. The non-lazy/lazy @@ -2093,7 +2109,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, len =atomic_long_read (&rdp->nocb_q_count);if (old_rhpp == &rdp->nocb_head) {if (!irqs_disabled_flags (flags)) { -wake_up (&rdp->nocb_wq);/* ... if queue was empty ... */ +/* ... if queue was empty ... */ +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeEmpty" ));kernel/rcu/tree_plugin.h +2
-1}else {@@ -2103,7 +2120,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, } rdp->qlen_last_fqs_check =0 ; }else if (len > rdp->qlen_last_fqs_check + qhimark) { -wake_up_process (t);/* ... or if many callbacks queued. */ +/* ... or if many callbacks queued. */ +wake_nocb_leader (rdp, true); rdp->qlen_last_fqs_check =LONG_MAX /2 ;trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeOvf" ));kernel/rcu/tree_plugin.h +158
-39}else {@@ -2213,13 +2231,150 @@ static void rcu_nocb_wait_gp(struct rcu_data *rdp) }/* +* Leaders come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_leader_wait (struct rcu_data *my_rdp) +{ +bool firsttime = true; +bool gotcbs; +struct rcu_data *rdp; +struct rcu_head **tail; + +wait_again: + +/* Wait for callbacks to appear. */ +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Sleep" ); +wait_event_interruptible (my_rdp->nocb_wq, +ACCESS_ONCE (my_rdp->nocb_leader_wake)); +/* Memory barrier handled by smp_mb() calls below and repoll. */ + }else if (firsttime) { + firsttime = false;/* Don't drown trace log with "Poll"! */ +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Poll" ); + } + +/* +* Each pass through the following loop checks a follower for CBs. +* We are our own first follower. Any CBs found are moved to +* nocb_gp_head, where they await a grace period. +*/ + gotcbs = false; +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { + rdp->nocb_gp_head =ACCESS_ONCE (rdp->nocb_head); +if (!rdp->nocb_gp_head) +continue ;/* No CBs here, try next follower. */ + +/* Move callbacks to wait-for-GP list, which is empty. */ +ACCESS_ONCE (rdp->nocb_head) =NULL ; + rdp->nocb_gp_tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); + rdp->nocb_gp_count =atomic_xchg (&rdp->nocb_q_count,0 ); + rdp->nocb_gp_count_lazy = +atomic_xchg (&rdp->nocb_q_count_lazy,0 ); + gotcbs = true; + } + +/* +* If there were no callbacks, sleep a bit, rescan after a +* memory barrier, and go retry. +*/ +if (unlikely (!gotcbs)) { +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + +/* Rescan in case we were a victim of memory ordering. */ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) +if (ACCESS_ONCE (rdp->nocb_head)) { +/* Found CB, so short-circuit next wait. */ + my_rdp->nocb_leader_wake = true; +break ; + } + goto wait_again; + } + +/* Wait for one grace period. */ +rcu_nocb_wait_gp (my_rdp); + +/* +* We left ->nocb_leader_wake set to reduce cache thrashing. +* We clear it now, but recheck for new callbacks while +* traversing our follower list. +*/ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan of ->nocb_head. */ + +/* Each pass through the following loop wakes a follower, if needed. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { +if (ACCESS_ONCE (rdp->nocb_head)) + my_rdp->nocb_leader_wake = true;/* No need to wait. */ +if (!rdp->nocb_gp_head) +continue ;/* No CBs, so no need to wake follower. */ + +/* Append callbacks to follower's "done" list. */ + tail =xchg (&rdp->nocb_follower_tail, rdp->nocb_gp_tail); + *tail = rdp->nocb_gp_head; +atomic_long_add (rdp->nocb_gp_count, &rdp->nocb_follower_count); +atomic_long_add (rdp->nocb_gp_count_lazy, + &rdp->nocb_follower_count_lazy); +if (rdp != my_rdp && tail == &rdp->nocb_follower_head) { +/* +* List was empty, wake up the follower. +* Memory barriers supplied by atomic_long_add(). +*/ +wake_up (&rdp->nocb_wq); + } + } + +/* If we (the leader) don't have CBs, go wait some more. */ +if (!my_rdp->nocb_follower_head) + goto wait_again; +} + +/* +* Followers come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_follower_wait (struct rcu_data *rdp) +{ +bool firsttime = true; + +for (;;) { +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"FollowerSleep" ); +wait_event_interruptible (rdp->nocb_wq, +ACCESS_ONCE (rdp->nocb_follower_head)); + }else if (firsttime) { +/* Don't drown trace log with "Poll"! */ + firsttime = false; +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"Poll" ); + } +if (smp_load_acquire (&rdp->nocb_follower_head)) { +/* ^^^ Ensure CB invocation follows _head test. */ +return ; + } +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + } +} + +/* * Per-rcu_data kthread, but only for no-CBs CPUs. Each kthread invokes -* callbacks queued by the corresponding no-CBs CPU. +* callbacks queued by the corresponding no-CBs CPU, however, there is +* an optional leader-follower relationship so that the grace-period +* kthreads don't have to do quite so many wakeups. */ static int rcu_nocb_kthread (void *arg) {int c, cl; -bool firsttime =1 ;struct rcu_head *list;struct rcu_head *next;struct rcu_head **tail;@@ -2227,41 +2382,22 @@ static int rcu_nocb_kthread(void *arg)/* Each pass through this loop invokes one batch of callbacks */ for (;;) { -/* If not polling, wait for next batch of callbacks. */ -if (!rcu_nocb_poll) { -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Sleep" )); -wait_event_interruptible (rdp->nocb_wq, rdp->nocb_head); -/* Memory barrier provide by xchg() below. */ - }else if (firsttime) { - firsttime =0 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Poll" )); - } - list =ACCESS_ONCE (rdp->nocb_head); -if (!list) { -if (!rcu_nocb_poll) -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeEmpty" )); -schedule_timeout_interruptible (1 ); -flush_signals (current); -continue ; - } - firsttime =1 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeNonEmpty" )); - -/* -* Extract queued callbacks, update counts, and wait -* for a grace period to elapse. -*/ -ACCESS_ONCE (rdp->nocb_head) =NULL ; - tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); - c =atomic_long_xchg (&rdp->nocb_q_count,0 ); - cl =atomic_long_xchg (&rdp->nocb_q_count_lazy,0 ); -ACCESS_ONCE (rdp->nocb_p_count) += c; -ACCESS_ONCE (rdp->nocb_p_count_lazy) += cl; -rcu_nocb_wait_gp (rdp); +/* Wait for callbacks. */ +if (rdp->nocb_leader == rdp) +nocb_leader_wait (rdp); +else +nocb_follower_wait (rdp); + +/* Pull the ready-to-invoke callbacks onto local list. */ + list =ACCESS_ONCE (rdp->nocb_follower_head); +BUG_ON (!list); +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"WokeNonEmpty" ); +ACCESS_ONCE (rdp->nocb_follower_head) =NULL ; + tail =xchg (&rdp->nocb_follower_tail, &rdp->nocb_follower_head); + c =atomic_long_xchg (&rdp->nocb_follower_count,0 ); + cl =atomic_long_xchg (&rdp->nocb_follower_count_lazy,0 ); + rdp->nocb_p_count += c; + rdp->nocb_p_count_lazy += cl;/* Each pass through the following loop invokes a callback. */ trace_rcu_batch_start (rdp->rsp->name, cl, c,-1 );@@ -2305,7 +2441,7 @@ static void do_nocb_deferred_wakeup(struct rcu_data *rdp)if (!rcu_nocb_need_deferred_wakeup (rdp))return ;ACCESS_ONCE (rdp->nocb_defer_wakeup) = false; -wake_up (&rdp->nocb_wq); +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("DeferredWakeEmpty" )); }@@ -2314,19 +2450,53 @@ static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp) { rdp->nocb_tail = &rdp->nocb_head;init_waitqueue_head (&rdp->nocb_wq); + rdp->nocb_follower_tail = &rdp->nocb_follower_head; } -/* Create a kthread for each RCU flavor for each no-CBs CPU. */ +/* How many follower CPU IDs per leader? Default of -1 for
sqrt(nr_cpu_ids). */kernel/rcu/tree_plugin.h +26
-0+static int rcu_nocb_leader_stride =-1 ; +module_param (rcu_nocb_leader_stride, int,0444 ); + +/* +* Create a kthread for each RCU flavor for each no-CBs CPU. +* Also initialize leader-follower relationships. +*/ static void __init rcu_spawn_nocb_kthreads (struct rcu_state *rsp) {int cpu; +int ls = rcu_nocb_leader_stride; +int nl =0 ;/* Next leader. */ struct rcu_data *rdp; +struct rcu_data *rdp_leader =NULL ;/* Suppress misguided gcc warn. */ +struct rcu_data *rdp_prev =NULL ;struct task_struct *t;if (rcu_nocb_mask ==NULL )return ; +if (ls ==-1 ) { + ls =int_sqrt (nr_cpu_ids); + rcu_nocb_leader_stride = ls; + } + +/* +* Each pass through this loop sets up one rcu_data structure and +* spawns one rcu_nocb_kthread(). +*/ for_each_cpu (cpu, rcu_nocb_mask) { rdp =per_cpu_ptr (rsp->rda, cpu); +if (rdp->cpu >= nl) { +/* New leader, set up for followers & next leader. */ + nl =DIV_ROUND_UP (rdp->cpu +1 , ls) * ls; + rdp->nocb_leader = rdp; + rdp_leader = rdp; + }else {kernel/rcu/tree_plugin.h static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp) · line 2502
Quoted 10 lines
kernel/rcu/tree_plugin.h +7
-0+/* Another follower, link to previous leader. */ + rdp->nocb_leader = rdp_leader; + rdp_prev->nocb_next_follower = rdp; + } + rdp_prev = rdp; + +/* Spawn the kthread for this CPU. */ t =kthread_run (rcu_nocb_kthread, rdp,"rcuo%c/%d" , rsp->abbr, cpu);BUG_ON (IS_ERR (t));--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.comSignature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 30 lines · Mathieu Desnoyers
----- Original Message -----
Quoted 29 lines
From: "Paul E. McKenney" <[email protected]>
To: [email protected], [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], "mathieu desnoyers" <[email protected]>, [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Sent: Friday, June 27, 2014 10:20:38 AM
Subject: [PATCH RFC tip/core/rcu] Parallelize and economize NOCB kthread wakeupsAn 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 8 lines
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
If I understand your approach correctly, it looks like the callbacks are moved from the follower threads (per CPU) to leader threads (for a group of CPUs).
Not quite. The leader thread does the moving, but the callbacks live on the follower's data structure. There probably are some added cache misses, but I believe that this is more than made up for by the decrease in wakeups -- the followers are normally awakened only once rather than twice per grace period.
Quoted 11 lines
I'm concerned that moving those callbacks to leader
threads would increase cache trashing, since the callbacks would be often executed from a different CPU than the CPU which enqueued the work. In a case where cgroups/affinity are used to pin kthreads to specific CPUs to minimize cache trashing, I'm concerned that this approach could degrade performance.Would there be another way to distribute the wake up that would keep callbacks local to their enqueuing CPU ?
Or am I missing something important ?
One problem is that each leader must look at its followers' state in order to determine who needs to be awakened. So there are some added cache misses no matter how you redistribute the wakeups.
Thanx, Paul
Quoted 416 lines
Thanks,
Mathieu
Quoted 406 lines
Reported-by Rik van Riel <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Documentation/kernel-parameters.txt +0
-0@@ -2796,6 +2796,13 @@ bytes respectively. Such letter suffixes can also beentirely omitted.
Documentation/kernel-parameters.txt +7
-0quiescent states. Units are jiffies, minimum value is one, and maximum value is HZ. + rcutree.rcu_nocb_leader_stride= [KNL] + Set the number of NOCB kthread groups, which + defaults to the square root of the number of + CPUs. Larger numbers reduces the wakeup overhead + on the per-CPU grace-period kthreads, but increases + that same overhead on each group's leader. + rcutree.qhimark= [KNL] Set threshold of queued RCU callbacks beyond which batch limiting is disabled.kernel/rcu/tree.h +26
-2@@ -331,11 +331,29 @@ struct rcu_data {struct rcu_head **nocb_tail;atomic_long_t nocb_q_count;/* # CBs waiting for kthread */ atomic_long_t nocb_q_count_lazy;/* (approximate). */ +struct rcu_head *nocb_follower_head;/* CBs ready to invoke. */ +struct rcu_head **nocb_follower_tail; +atomic_long_t nocb_follower_count;/* # CBs ready to invoke. */ +atomic_long_t nocb_follower_count_lazy;/* (approximate). */ int nocb_p_count;/* # CBs being invoked by kthread */ int nocb_p_count_lazy;/* (approximate). */ wait_queue_head_t nocb_wq;/* For nocb kthreads to sleep on. */ struct task_struct *nocb_kthread;bool nocb_defer_wakeup;/* Defer wakeup of nocb_kthread. */ + +/* The following fields are used by the leader, hence own cacheline. */ +struct rcu_head *nocb_gp_head____cacheline_internodealigned_in_smp ; +/* CBs waiting for GP. */ +struct rcu_head **nocb_gp_tail; +long nocb_gp_count; +long nocb_gp_count_lazy; +bool nocb_leader_wake;/* Is the nocb leader thread awake? */ +struct rcu_data *nocb_next_follower; +/* Next follower in wakeup chain. */ + +/* The following fields are used by the follower, hence new cachline. */ +struct rcu_data *nocb_leader____cacheline_internodealigned_in_smp ; +/* Leader CPU takes GP-end wakeups. */ #endif /* #ifdef CONFIG_RCU_NOCB_CPU */ /* 8) RCU CPU stall data. */ @@ -583,8 +601,14 @@ static bool rcu_nohz_full_cpu(struct rcu_state *rsp);/* Sum up queue lengths for tracing. */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll) { - *ql =atomic_long_read (&rdp->nocb_q_count) + rdp->nocb_p_count; - *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + rdp->nocb_p_count_lazy; + *ql =atomic_long_read (&rdp->nocb_q_count) + + rdp->nocb_p_count + +atomic_long_read (&rdp->nocb_follower_count) + + rdp->nocb_p_count + rdp->nocb_gp_count; + *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + + rdp->nocb_p_count_lazy + +atomic_long_read (&rdp->nocb_follower_count_lazy) + + rdp->nocb_p_count_lazy + rdp->nocb_gp_count_lazy; }#else /* #ifdef CONFIG_RCU_NOCB_CPU */ static inline void
rcu_nocb_q_lengths(struct rcu_data *rdp, long *ql, long *qll)kernel/rcu/tree_plugin.h +18
-1@@ -2060,6 +2060,22 @@ bool rcu_is_nocb_cpu(int cpu)#endif /* #ifndef CONFIG_RCU_NOCB_CPU_ALL */ /* +* Kick the leader kthread for this NOCB group. +*/ +static void wake_nocb_leader (struct rcu_data *rdp,bool force) +{ +struct rcu_data *rdp_leader = rdp->nocb_leader; + +if (!ACCESS_ONCE (rdp_leader->nocb_kthread)) +return ; +if (!ACCESS_ONCE (rdp_leader->nocb_leader_wake) || force) { +/* Prior xchg orders against prior callback enqueue. */ +ACCESS_ONCE (rdp_leader->nocb_leader_wake) = true; +wake_up (&rdp_leader->nocb_wq); + } +} + +/* * Enqueue the specified string of rcu_head structures onto the specified * CPU's no-CBs lists. The CPU is specified by rdp, the head of the * string by rhp, and the tail of the string by rhtp. The non-lazy/lazy @@ -2093,7 +2109,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, len =atomic_long_read (&rdp->nocb_q_count);if (old_rhpp == &rdp->nocb_head) {if (!irqs_disabled_flags (flags)) { -wake_up (&rdp->nocb_wq);/* ... if queue was empty ... */ +/* ... if queue was empty ... */ +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeEmpty" ));kernel/rcu/tree_plugin.h +2
-1}else {@@ -2103,7 +2120,8 @@ static void __call_rcu_nocb_enqueue(struct rcu_data *rdp, } rdp->qlen_last_fqs_check =0 ; }else if (len > rdp->qlen_last_fqs_check + qhimark) { -wake_up_process (t);/* ... or if many callbacks queued. */ +/* ... or if many callbacks queued. */ +wake_nocb_leader (rdp, true); rdp->qlen_last_fqs_check =LONG_MAX /2 ;trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("WakeOvf" ));kernel/rcu/tree_plugin.h +158
-39}else {@@ -2213,13 +2231,150 @@ static void rcu_nocb_wait_gp(struct rcu_data *rdp) }/* +* Leaders come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_leader_wait (struct rcu_data *my_rdp) +{ +bool firsttime = true; +bool gotcbs; +struct rcu_data *rdp; +struct rcu_head **tail; + +wait_again: + +/* Wait for callbacks to appear. */ +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Sleep" ); +wait_event_interruptible (my_rdp->nocb_wq, +ACCESS_ONCE (my_rdp->nocb_leader_wake)); +/* Memory barrier handled by smp_mb() calls below and repoll. */ + }else if (firsttime) { + firsttime = false;/* Don't drown trace log with "Poll"! */ +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu,"Poll" ); + } + +/* +* Each pass through the following loop checks a follower for CBs. +* We are our own first follower. Any CBs found are moved to +* nocb_gp_head, where they await a grace period. +*/ + gotcbs = false; +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { + rdp->nocb_gp_head =ACCESS_ONCE (rdp->nocb_head); +if (!rdp->nocb_gp_head) +continue ;/* No CBs here, try next follower. */ + +/* Move callbacks to wait-for-GP list, which is empty. */ +ACCESS_ONCE (rdp->nocb_head) =NULL ; + rdp->nocb_gp_tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); + rdp->nocb_gp_count =atomic_xchg (&rdp->nocb_q_count,0 ); + rdp->nocb_gp_count_lazy = +atomic_xchg (&rdp->nocb_q_count_lazy,0 ); + gotcbs = true; + } + +/* +* If there were no callbacks, sleep a bit, rescan after a +* memory barrier, and go retry. +*/ +if (unlikely (!gotcbs)) { +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (my_rdp->rsp->name, my_rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + +/* Rescan in case we were a victim of memory ordering. */ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) +if (ACCESS_ONCE (rdp->nocb_head)) { +/* Found CB, so short-circuit next wait. */ + my_rdp->nocb_leader_wake = true; +break ; + } + goto wait_again; + } + +/* Wait for one grace period. */ +rcu_nocb_wait_gp (my_rdp); + +/* +* We left ->nocb_leader_wake set to reduce cache thrashing. +* We clear it now, but recheck for new callbacks while +* traversing our follower list. +*/ + my_rdp->nocb_leader_wake = false; +smp_mb ();/* Ensure _wake false before scan of ->nocb_head. */ + +/* Each pass through the following loop wakes a follower, if needed. */ +for (rdp = my_rdp; rdp; rdp = rdp->nocb_next_follower) { +if (ACCESS_ONCE (rdp->nocb_head)) + my_rdp->nocb_leader_wake = true;/* No need to wait. */ +if (!rdp->nocb_gp_head) +continue ;/* No CBs, so no need to wake follower. */ + +/* Append callbacks to follower's "done" list. */ + tail =xchg (&rdp->nocb_follower_tail, rdp->nocb_gp_tail); + *tail = rdp->nocb_gp_head; +atomic_long_add (rdp->nocb_gp_count, &rdp->nocb_follower_count); +atomic_long_add (rdp->nocb_gp_count_lazy, + &rdp->nocb_follower_count_lazy); +if (rdp != my_rdp && tail == &rdp->nocb_follower_head) { +/* +* List was empty, wake up the follower. +* Memory barriers supplied by atomic_long_add(). +*/ +wake_up (&rdp->nocb_wq); + } + } + +/* If we (the leader) don't have CBs, go wait some more. */ +if (!my_rdp->nocb_follower_head) + goto wait_again; +} + +/* +* Followers come here to wait for additional callbacks to show up. +* This function does not return until callbacks appear. +*/ +static void nocb_follower_wait (struct rcu_data *rdp) +{ +bool firsttime = true; + +for (;;) { +if (!rcu_nocb_poll) { +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"FollowerSleep" ); +wait_event_interruptible (rdp->nocb_wq, +ACCESS_ONCE (rdp->nocb_follower_head)); + }else if (firsttime) { +/* Don't drown trace log with "Poll"! */ + firsttime = false; +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"Poll" ); + } +if (smp_load_acquire (&rdp->nocb_follower_head)) { +/* ^^^ Ensure CB invocation follows _head test. */ +return ; + } +if (!rcu_nocb_poll) +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, +"WokeEmpty" ); +flush_signals (current); +schedule_timeout_interruptible (1 ); + } +} + +/* * Per-rcu_data kthread, but only for no-CBs CPUs. Each kthread invokes -* callbacks queued by the corresponding no-CBs CPU. +* callbacks queued by the corresponding no-CBs CPU, however, there is +* an optional leader-follower relationship so that the grace-period +* kthreads don't have to do quite so many wakeups. */ static int rcu_nocb_kthread (void *arg) {int c, cl; -bool firsttime =1 ;struct rcu_head *list;struct rcu_head *next;struct rcu_head **tail;@@ -2227,41 +2382,22 @@ static int rcu_nocb_kthread(void *arg)/* Each pass through this loop invokes one batch of callbacks */ for (;;) { -/* If not polling, wait for next batch of callbacks. */ -if (!rcu_nocb_poll) { -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Sleep" )); -wait_event_interruptible (rdp->nocb_wq, rdp->nocb_head); -/* Memory barrier provide by xchg() below. */ - }else if (firsttime) { - firsttime =0 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("Poll" )); - } - list =ACCESS_ONCE (rdp->nocb_head); -if (!list) { -if (!rcu_nocb_poll) -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeEmpty" )); -schedule_timeout_interruptible (1 ); -flush_signals (current); -continue ; - } - firsttime =1 ; -trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu, -TPS ("WokeNonEmpty" )); - -/* -* Extract queued callbacks, update counts, and wait -* for a grace period to elapse. -*/ -ACCESS_ONCE (rdp->nocb_head) =NULL ; - tail =xchg (&rdp->nocb_tail, &rdp->nocb_head); - c =atomic_long_xchg (&rdp->nocb_q_count,0 ); - cl =atomic_long_xchg (&rdp->nocb_q_count_lazy,0 ); -ACCESS_ONCE (rdp->nocb_p_count) += c; -ACCESS_ONCE (rdp->nocb_p_count_lazy) += cl; -rcu_nocb_wait_gp (rdp); +/* Wait for callbacks. */ +if (rdp->nocb_leader == rdp) +nocb_leader_wait (rdp); +else +nocb_follower_wait (rdp); + +/* Pull the ready-to-invoke callbacks onto local list. */ + list =ACCESS_ONCE (rdp->nocb_follower_head); +BUG_ON (!list); +trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,"WokeNonEmpty" ); +ACCESS_ONCE (rdp->nocb_follower_head) =NULL ; + tail =xchg (&rdp->nocb_follower_tail, &rdp->nocb_follower_head); + c =atomic_long_xchg (&rdp->nocb_follower_count,0 ); + cl =atomic_long_xchg (&rdp->nocb_follower_count_lazy,0 ); + rdp->nocb_p_count += c; + rdp->nocb_p_count_lazy += cl;/* Each pass through the following loop invokes a callback. */ trace_rcu_batch_start (rdp->rsp->name, cl, c,-1 );@@ -2305,7 +2441,7 @@ static void do_nocb_deferred_wakeup(struct rcu_data *rdp)if (!rcu_nocb_need_deferred_wakeup (rdp))return ;ACCESS_ONCE (rdp->nocb_defer_wakeup) = false; -wake_up (&rdp->nocb_wq); +wake_nocb_leader (rdp, false);trace_rcu_nocb_wake (rdp->rsp->name, rdp->cpu,TPS ("DeferredWakeEmpty" )); }@@ -2314,19 +2450,53 @@ static void __init rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp) { rdp->nocb_tail = &rdp->nocb_head;init_waitqueue_head (&rdp->nocb_wq); + rdp->nocb_follower_tail = &rdp->nocb_follower_head; } -/* Create a kthread for each RCU flavor for each no-CBs CPU. */ +/* How many follower CPU IDs per leader? Default of -1 for
sqrt(nr_cpu_ids). */kernel/rcu/tree_plugin.h +33
-0+static int rcu_nocb_leader_stride =-1 ; +module_param (rcu_nocb_leader_stride, int,0444 ); + +/* +* Create a kthread for each RCU flavor for each no-CBs CPU. +* Also initialize leader-follower relationships. +*/ static void __init rcu_spawn_nocb_kthreads (struct rcu_state *rsp) {int cpu; +int ls = rcu_nocb_leader_stride; +int nl =0 ;/* Next leader. */ struct rcu_data *rdp; +struct rcu_data *rdp_leader =NULL ;/* Suppress misguided gcc warn. */ +struct rcu_data *rdp_prev =NULL ;struct task_struct *t;if (rcu_nocb_mask ==NULL )return ; +if (ls ==-1 ) { + ls =int_sqrt (nr_cpu_ids); + rcu_nocb_leader_stride = ls; + } + +/* +* Each pass through this loop sets up one rcu_data structure and +* spawns one rcu_nocb_kthread(). +*/ for_each_cpu (cpu, rcu_nocb_mask) { rdp =per_cpu_ptr (rsp->rda, cpu); +if (rdp->cpu >= nl) { +/* New leader, set up for followers & next leader. */ + nl =DIV_ROUND_UP (rdp->cpu +1 , ls) * ls; + rdp->nocb_leader = rdp; + rdp_leader = rdp; + }else { +/* Another follower, link to previous leader. */ + rdp->nocb_leader = rdp_leader; + rdp_prev->nocb_next_follower = rdp; + } + rdp_prev = rdp; + +/* Spawn the kthread for this CPU. */ t =kthread_run (rcu_nocb_kthread, rdp,"rcuo%c/%d" , rsp->abbr, cpu);BUG_ON (IS_ERR (t));Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 20 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 23 lines · Peter Zijlstra
Quoted 22 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 8 lines
Quoted 5 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Some observations.
First, the rcuos/N threads are NOT bound to CPU N at all, but are free to float through the system.
Second, the number of RCU callbacks at the end of each grace period is quite likely to be small most of the time.
This suggests that on a system with N CPUs, it may be perfectly sufficient to have a much smaller number of rcuos threads.
One thread can probably handle the RCU callbacks for as many as 16, or even 64 CPUs...
- --
All rights reversed
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJTtA0rAAoJEM553pKExN6D3IkIAKFZjAWhopcwPppzGWsT7OA/ 3y7fnAvBcJ6AEwE1igzbJyCPjdOJECY/9iUdvuB9CbBD82kyfm4qnuREpdt+hqQp Vi8EDB9UdyI2I42hbfRVOS4NgAl8ZYsDVQ+QiEM1cMp+LqEKPg7adwoNTPQL4eZn ANcNh3B3eSpxnZ+ZbEBYJmQXIVP2S5t5M/EMizqUJEBI2/2zB68eeFkgvuW1yg1a /J4L9w+Iqbu+is+6JK9ibQAR/tTS6Exmuc6RnKDH/nkj1jefKdH1z2p+r69u4AK1 JVDl40lra4n6XHsfjDWDHDXBsiD/JDJJ6Zxf77NWwg1aRT77HZPiMOu98hpFxWs= =OSUn
-----END PGP SIGNATURE-----
Quoted 33 lines · Rik van Riel
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Quoted 29 lines · Peter Zijlstra
Quoted 27 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Quoted 7 lines
Quoted 2 lines
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Some observations.
First, the rcuos/N threads are NOT bound to CPU N at all, but are free to float through the system.
I could easily bind each to its home CPU by default for CONFIG_NO_HZ_FULL=n. For CONFIG_NO_HZ_FULL=y, they get bound to the non-nohz_full= CPUs.
Quoted 8 lines
Second, the number of RCU callbacks at the end of each grace period is quite likely to be small most of the time.
This suggests that on a system with N CPUs, it may be perfectly sufficient to have a much smaller number of rcuos threads.
One thread can probably handle the RCU callbacks for as many as 16, or even 64 CPUs...
In many cases, one thread could handle the RCU callbacks for way more than that. In other cases, a single CPU could keep a single rcuo kthread quite busy. So something dynamic ends up being required.
But I suspect that the real solution here is to adjust the Kconfig setup between NO_HZ_FULL and RCU_NOCB_CPU_ALL so that you have to specify boot parameters to get callback offloading on systems built with NO_HZ_FULL. Then add some boot-time code so that any CPU that has nohz_full= is forced to also have rcu_nocbs= set. This would have the good effect of applying callback offloading only to those workloads for which it was specifically designed, but allowing those workloads to gain the latency-reduction benefits of callback offloading.
I do freely confess that I was hoping that callback offloading might one day completely replace RCU_SOFTIRQ, but that hope now appears to be at best premature.
Something like the attached patch. Untested, probably does not even build.
Thanx, Paul
------------------------------------------------------------------------
rcu: Don't offload callbacks unless specifically requested
<more here soon>
init/Kconfig +2 -2
@@ -737,7 +737,7 @@ choice config RCU_NOCB_CPU_NONE bool "No build_forced no-CBs CPUs" - depends on RCU_NOCB_CPU && !NO_HZ_FULL + depends on RCU_NOCB_CPU && !NO_HZ_FULL_ALL help This option does not force any of the CPUs to be no-CBs CPUs. Only CPUs designated by the rcu_nocbs= boot parameter will be
@@ -751,7 +751,7 @@ config RCU_NOCB_CPU_NONE config RCU_NOCB_CPU_ZERO bool "CPU 0 is a build_forced no-CBs CPU" - depends on RCU_NOCB_CPU && !NO_HZ_FULL + depends on RCU_NOCB_CPU && !NO_HZ_FULL_ALL help This option forces CPU 0 to be a no-CBs CPU, so that its RCU callbacks are invoked by a per-CPU kthread whose name begins
kernel/rcu/tree_plugin.h +3 -0
@@ -2473,6 +2473,9 @@ static void __init rcu_spawn_nocb_kthreads(struct rcu_state *rsp)if (rcu_nocb_mask ==NULL )return ; +#ifdef CONFIG_NO_HZ_FULL +cpumask_or (rcu_nocb_mask, rcu_nocb_mask, tick_nohz_full_mask); +#endif /* #ifdef CONFIG_NO_HZ_FULL */ if (ls ==-1 ) { ls =int_sqrt (nr_cpu_ids); rcu_nocb_leader_stride = ls;
Quoted 67 lines · Paul E. McKenney
Quoted 33 lines · Rik van Riel
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Quoted 29 lines · Peter Zijlstra
Quoted 27 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Quoted 7 lines
Quoted 2 lines
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Some observations.
First, the rcuos/N threads are NOT bound to CPU N at all, but are free to float through the system.
I could easily bind each to its home CPU by default for
CONFIG_NO_HZ_FULL=n. ForCONFIG_NO_HZ_FULL=y, they get bound to the non-nohz_full= CPUs.Quoted 8 lines
Second, the number of RCU callbacks at the end of each grace period is quite likely to be small most of the time.
This suggests that on a system with N CPUs, it may be perfectly sufficient to have a much smaller number of rcuos threads.
One thread can probably handle the RCU callbacks for as many as 16, or even 64 CPUs...
In many cases, one thread could handle the RCU callbacks for way more than that. In other cases, a single CPU could keep a single rcuo kthread quite busy. So something dynamic ends up being required.
But I suspect that the real solution here is to adjust the
Kconfigsetup betweenNO_HZ_FULLandRCU_NOCB_CPU_ALLso that you have to specify boot parameters to get callback offloading on systems built withNO_HZ_FULL. Then add some boot-time code so that any CPU that has nohz_full= is forced to also have rcu_nocbs= set. This would have the good effect of applying callback offloading only to those workloads for which it was specifically designed, but allowing those workloads to gain the latency-reduction benefits of callback offloading.
Quoted 5 lines
I do freely confess that I was hoping that callback offloading might one day completely replace
RCU_SOFTIRQ, but that hope now appears to be at best premature.Something like the attached patch. Untested, probably does not even build.
Against all odds, it builds and passes moderate rcutorture testing.
Although this doesn't satisfy the desire to wean RCU of softirq, it does allow NO_HZ_FULL kernels to maintain better compatibility with earlier kernel versions, which appears to be more important for the time being.
Thanx, Paul
Quoted 44 lines
------------------------------------------------------------------------
rcu: Don't offload callbacks unless specifically requested
<more here soon>
Not-yet-signed-off-by Paul E. McKenney <[email protected]>init/Kconfig +2
-2@@ -737,7 +737,7 @@ choice config RCU_NOCB_CPU_NONE bool "No build_forced no-CBs CPUs" - depends on RCU_NOCB_CPU && !NO_HZ_FULL + depends on RCU_NOCB_CPU && !NO_HZ_FULL_ALL help This option does not force any of the CPUs to be no-CBs CPUs. Only CPUs designated by the rcu_nocbs= boot parameter will be@@ -751,7 +751,7 @@ config RCU_NOCB_CPU_NONE config RCU_NOCB_CPU_ZERO bool "CPU 0 is a build_forced no-CBs CPU" - depends on RCU_NOCB_CPU && !NO_HZ_FULL + depends on RCU_NOCB_CPU && !NO_HZ_FULL_ALL help This option forces CPU 0 to be a no-CBs CPU, so that its RCU callbacks are invoked by a per-CPU kthread whose name beginskernel/rcu/tree_plugin.h +3
-0@@ -2473,6 +2473,9 @@ static void __init rcu_spawn_nocb_kthreads(struct rcu_state *rsp)if (rcu_nocb_mask ==NULL )return ; +#ifdef CONFIG_NO_HZ_FULL +cpumask_or (rcu_nocb_mask, rcu_nocb_mask, tick_nohz_full_mask); +#endif /* #ifdef CONFIG_NO_HZ_FULL */ if (ls ==-1 ) { ls =int_sqrt (nr_cpu_ids); rcu_nocb_leader_stride = ls;
Quoted 21 lines · Peter Zijlstra
Quoted 20 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 7 lines
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Sure thing, Peter.
Thanx, Paul
Quoted 27 lines · Paul E. McKenney
Quoted 26 lines · Peter Zijlstra
Quoted 24 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Quoted 4 lines
Quoted 2 lines
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Sure thing, Peter.
So you don't think this has gotten a little out of hand? The NOCB stuff has lead to these masses of rcu threads and now you're adding extra cache misses to the perfectly sane and normal code paths just to deal with so many threads.
And all to support a feature that nearly nobody uses. And you were talking about making nocb the default rcu...
Quoted 31 lines · Peter Zijlstra
Quoted 30 lines · Paul E. McKenney
Quoted 28 lines · Peter Zijlstra
Quoted 20 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Quoted 6 lines
Quoted 1 line
Sure thing, Peter.
So you don't think this has gotten a little out of hand? The NOCB stuff has lead to these masses of rcu threads and now you're adding extra cache misses to the perfectly sane and normal code paths just to deal with so many threads.
Indeed it appears to have gotten a bit out of hand. But let's please attack the real problem rather than the immediate irritant.
And in this case, the real problem is that users are getting callback offloading even when there is no reason for it.
Quoted 2 lines
And all to support a feature that nearly nobody uses. And you were talking about making nocb the default rcu...
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Please see my patch in reply to Rik's email. The idea is to neither rip callback offloading from the kernel nor to keep callback offloading as the default, but instead do callback offloading only for those CPUs specifically marked as NO_HZ_FULL CPUs, or when specifically requested at build time or at boot time. In other words, only do it when it is needed.
Thanx, Paul
Quoted 4 lines · Paul E. McKenney
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Nah, softirqs are still totally annoying :-)
So I've lost detail again, but it seems to me that on all CPUs that are actually getting ticks, waking tasks to process the RCU state is entirely over doing it. Might as well keep processing their RCU state from the tick as was previously done.
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Quoted 6 lines
Nah, softirqs are still totally annoying :-)
So I've lost detail again, but it seems to me that on all CPUs that are actually getting ticks, waking tasks to process the RCU state is entirely over doing it. Might as well keep processing their RCU state from the tick as was previously done.
For CPUs that are not getting ticks (eg. because they are idle), is it worth waking up anything on that CPU, or would it make more sense to simply process their RCU callbacks on a different CPU, if there aren't too many pending?
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/
iQEcBAEBAgAGBQJTtEGCAAoJEM553pKExN6D7t4IALdymyu0+/SdaXG73dfkzNKd yJ3WJtJl1TV6JyejV747IRdKYfkuliZJ+99JZHtJ9dWvOoTtw19GqXXXVANlFpNE 8dQ4UTR6gDE1fRHnWKCdi0p8s3JwgZYdyhr0fKq7k09EXs+eJvDUTVVptBwLj36P oaENzeONv5xkn3LS9cZVQATX1ZjpYiXjFUxblWoi/NJfSIlq81IkPj8ujaZ4f/6Q 6QLqymNbUGnF5n8v5gs8UqsP+fM3phsIJsT5m42hqnS9eKVwcw4T7UZ8UMFie+mC hzy7vA0ClcdMWOMlRCSRbJMq0lDA0ej8acYpnj4Yz13wY2DIdTYVU38BbUE+iNA= =Ia0S
-----END PGP SIGNATURE-----
Quoted 18 lines · Rik van Riel
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Quoted 6 lines
Nah, softirqs are still totally annoying :-)
So I've lost detail again, but it seems to me that on all CPUs that are actually getting ticks, waking tasks to process the RCU state is entirely over doing it. Might as well keep processing their RCU state from the tick as was previously done.
Quoted 4 lines
For CPUs that are not getting ticks (eg. because they are idle), is it worth waking up anything on that CPU, or would it make more sense to simply process their RCU callbacks on a different CPU, if there aren't too many pending?
Give or take the number of wakeups generated... ;-)
Thanx, Paul
Quoted 18 lines · Rik van Riel
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1Quoted 7 lines · Peter Zijlstra
Quoted 5 lines · Paul E. McKenney
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Quoted 6 lines
Nah, softirqs are still totally annoying :-)
So I've lost detail again, but it seems to me that on all CPUs that are actually getting ticks, waking tasks to process the RCU state is entirely over doing it. Might as well keep processing their RCU state from the tick as was previously done.
Quoted 4 lines
For CPUs that are not getting ticks (eg. because they are idle), is it worth waking up anything on that CPU, or would it make more sense to simply process their RCU callbacks on a different CPU, if there aren't too many pending?
If they're idle, RCU 'should' know this and exclude them from the state machine, the tricky part, and where all this nocb nonsense started with, its the NOHZ_FULL stuff where a cpu can be !idle but still not get ticks.
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Nah, softirqs are still totally annoying :-)
Name me one thing that isn't annoying. ;-)
Quoted 4 lines
So I've lost detail again, but it seems to me that on all CPUs that are actually getting ticks, waking tasks to process the RCU state is entirely over doing it. Might as well keep processing their RCU state from the tick as was previously done.
And that is in fact the approach taken by my patch. For which I just kicked off testing, so expect an update later today. (And that -is- optimistic! A pessimistic viewpoint would hold that the patch would turn out to be so broken that it would take -weeks- to get a fix!)
Thanx, Paul
Quoted 16 lines · Paul E. McKenney
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Nah, softirqs are still totally annoying :-)
Name me one thing that isn't annoying. ;-)
Quoted 4 lines
So I've lost detail again, but it seems to me that on all CPUs that are actually getting ticks, waking tasks to process the RCU state is entirely over doing it. Might as well keep processing their RCU state from the tick as was previously done.
Quoted 4 lines
And that is in fact the approach taken by my patch. For which I just kicked off testing, so expect an update later today. (And that -is- optimistic! A pessimistic viewpoint would hold that the patch would turn out to be so broken that it would take -weeks- to get a fix!)
Right, but as you told Mike its not really dynamic, but of course we can work on that.
That said; I'm somewhat confused on the whole nocb thing. So the way I see things there's two things that need doing:
1) push the state machine
2) run callbacks
It seems to me the nocb threads do both, and somehow some of this is getting conflated. Because afaik RCU only uses softirqs for (2), since
(1) is fully done from the tick -- well, it used to be, before all this.
Now, IIRC rcu callbacks are not guaranteed to run on whatever cpu they're queued on, so we can 'easily' splice the actual callback list into some other CPUs callback list. Which leaves only (1) to actually 'do'.
Yet the whole thing is called after the 'no-callback' thing, even though the most important part is pushing the state machine remotely.
Now I can see we'd probably don't want to actually push remote cpu's their rcu state from IRQ context, but we could, I think, drive the state machine remotely. And we want to avoid overloading one CPU with the work of all others, which is I think still a fundamental issue with the whole nohz_full thing, it reverts to the _one_ timekeeper cpu, but on big enough systems that'll be a problem.
Quoted 17 lines · Peter Zijlstra
Quoted 16 lines · Paul E. McKenney
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines · Paul E. McKenney
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Nah, softirqs are still totally annoying :-)
Name me one thing that isn't annoying. ;-)
Quoted 4 lines
So I've lost detail again, but it seems to me that on all CPUs that are actually getting ticks, waking tasks to process the RCU state is entirely over doing it. Might as well keep processing their RCU state from the tick as was previously done.
Quoted 7 lines
Quoted 4 lines
And that is in fact the approach taken by my patch. For which I just kicked off testing, so expect an update later today. (And that -is- optimistic! A pessimistic viewpoint would hold that the patch would turn out to be so broken that it would take -weeks- to get a fix!)
Right, but as you told Mike its not really dynamic, but of course we can work on that.
If it is actually needed by someone, then I would be happy to work on it. But all I see now is people asserting that it should be provided, without any real justification.
Quoted 9 lines
That said; I'm somewhat confused on the whole nocb thing. So the way I see things there's two things that need doing:
1) push the state machine
2) run callbacksIt seems to me the nocb threads do both, and somehow some of this is getting conflated. Because afaik RCU only uses softirqs for (2), since
(1) is fully done from the tick -- well, it used to be, before all this.
Well, you do need a finer-grained view of the RCU state machine:
1a. Registering the need for a future grace period.
1b. Self-reporting of quiescent states (softirq).
1c. Reporting of other CPUs' quiescent states (grace-period kthread).
This includes idle CPUs, userspace nohz_full CPUs, and CPUs that just now transitioned to offline.
1d. Kicking CPUs that have not yet reported a quiescent state
(also grace-period kthread).
2. Running callbacks (softirq, or, for RCU_NOCB_CPU, rcuo kthread).
And here (1a) is done via softirq in the non-nocb case and via the rcuo kthreads on the nocb case.
And yes, RCU's softirq processing is normally done from the tick.
Quoted 4 lines
Now, IIRC rcu callbacks are not guaranteed to run on whatever cpu they're queued on, so we can 'easily' splice the actual callback list into some other CPUs callback list. Which leaves only (1) to actually 'do'.
True, although the 'easily' part needs to take into account the fact that the RCU callbacks from an given CPU must be invoked in order. Or rcu_barrier() needs to find a different way to guarantee that all previously registered callbacks have been invoked, as the case may be.
Quoted 2 lines
Yet the whole thing is called after the 'no-callback' thing, even though the most important part is pushing the state machine remotely.
Well, you do have to do both. Pushing the state machine doesn't help unless you also invoke the RCU callbacks.
Quoted 6 lines
Now I can see we'd probably don't want to actually push remote cpu's their rcu state from IRQ context, but we could, I think, drive the state machine remotely. And we want to avoid overloading one CPU with the work of all others, which is I think still a fundamental issue with the whole
nohz_fullthing, it reverts to the _one_ timekeeper cpu, but on big enough systems that'll be a problem.
Well, RCU already pushes the remote CPU's RCU state remotely via RCU's dynticks setup. But you are quite right, dumping all of the RCU processing onto one CPU can be a bottleneck on large systems (which Fengguang's tests noted, by the way), and this is the reason for patch 11/17 in the fixes series (https://lkml.org/lkml/2014/7/7/990). This patch allows housekeeping kthreads like the grace-period kthreads to use a new housekeeping_affine() function to bind themselves onto the non-nohz_full CPUs. The system can be booted with the desired number of housekeeping CPUs using the nohz_full= boot parameter.
However, it is not clear to me that having only one timekeeping CPU (as opposed to having only one housekeeping CPU) is a real problem, even for very large systems. If it does turn out to be a real problem, the sysidle code will probably need to change as well.
Thanx, Paul
Quoted 1 line · Paul E. McKenney
Name me one thing that isn't annoying. ;-)
A cold beverage on a warm day :-)
Quoted 4 lines · Peter Zijlstra
Quoted 1 line · Paul E. McKenney
Name me one thing that isn't annoying. ;-)
A cold beverage on a warm day :-)
Fair point... Not clear how to work that into the RCU implementation, though. I suppose I could add comments instructing the reader to consume a cold beverage. Or I could consume a cold beverage while working on RCU. ;-)
Thanx, Paul
Quoted 53 lines · Paul E. McKenney
Quoted 31 lines · Peter Zijlstra
Quoted 30 lines · Paul E. McKenney
Quoted 28 lines · Peter Zijlstra
Quoted 20 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Quoted 6 lines
Quoted 1 line
Sure thing, Peter.
So you don't think this has gotten a little out of hand? The NOCB stuff has lead to these masses of rcu threads and now you're adding extra cache misses to the perfectly sane and normal code paths just to deal with so many threads.
Indeed it appears to have gotten a bit out of hand. But let's please attack the real problem rather than the immediate irritant.
And in this case, the real problem is that users are getting callback offloading even when there is no reason for it.
Quoted 2 lines
And all to support a feature that nearly nobody uses. And you were talking about making nocb the default rcu...
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Quoted 6 lines
Please see my patch in reply to Rik's email. The idea is to neither rip callback offloading from the kernel nor to keep callback offloading as the default, but instead do callback offloading only for those CPUs specifically marked as
NO_HZ_FULLCPUs, or when specifically requested at build time or at boot time. In other words, only do it when it is needed.
Exactly! Like dynamically, when the user isolates CPUs via the cpuset interface, none of it making much sense without that particular property of a set of CPUs, and cpuset being the manager of CPU set properties.
NO_HZ_FULL is a property of a set of CPUs. isolcpus is supposed to go away as being a redundant interface to manage a single property of a set of CPUs, but it's perfectly fine for NO_HZ_FULL to add an interface to manage a single property of a set of CPUs. What am I missing?
-Mike
Quoted 61 lines · Mike Galbraith
Quoted 53 lines · Paul E. McKenney
Quoted 31 lines · Peter Zijlstra
Quoted 30 lines · Paul E. McKenney
Quoted 28 lines · Peter Zijlstra
Quoted 20 lines · Paul E. McKenney
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
Quoted 4 lines
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Urgh, how about we kill the entire nocb nonsense and try again? This is getting quite rediculous.
Quoted 6 lines
Quoted 1 line
Sure thing, Peter.
So you don't think this has gotten a little out of hand? The NOCB stuff has lead to these masses of rcu threads and now you're adding extra cache misses to the perfectly sane and normal code paths just to deal with so many threads.
Indeed it appears to have gotten a bit out of hand. But let's please attack the real problem rather than the immediate irritant.
And in this case, the real problem is that users are getting callback offloading even when there is no reason for it.
Quoted 2 lines
And all to support a feature that nearly nobody uses. And you were talking about making nocb the default rcu...
As were others, not that long ago. Today is the first hint that I got that you feel otherwise. But it does look like the softirq approach to callback processing needs to stick around for awhile longer. Nice to hear that softirq is now "sane and normal" again, I guess. ;-)
Quoted 6 lines
Please see my patch in reply to Rik's email. The idea is to neither rip callback offloading from the kernel nor to keep callback offloading as the default, but instead do callback offloading only for those CPUs specifically marked as
NO_HZ_FULLCPUs, or when specifically requested at build time or at boot time. In other words, only do it when it is needed.
Quoted 3 lines
Exactly! Like dynamically, when the user isolates CPUs via the cpuset interface, none of it making much sense without that particular property of a set of CPUs, and cpuset being the manager of CPU set properties.
Glad you like it! ;-)
Quoted 4 lines
NO_HZ_FULLis a property of a set of CPUs. isolcpus is supposed to go away as being a redundant interface to manage a single property of a set of CPUs, but it's perfectly fine forNO_HZ_FULLto add an interface to manage a single property of a set of CPUs. What am I missing?
Well, for now, it can only be specified at build time or at boot time. In theory, it is possible to change a CPU from being callback-offloaded to not at runtime, but there would need to be an extremely good reason for adding that level of complexity. Lots of "fun" races in there...
Thanx, Paul
Quoted 11 lines · Paul E. McKenney
Quoted 4 lines · Mike Galbraith
NO_HZ_FULLis a property of a set of CPUs. isolcpus is supposed to go away as being a redundant interface to manage a single property of a set of CPUs, but it's perfectly fine forNO_HZ_FULLto add an interface to manage a single property of a set of CPUs. What am I missing?Well, for now, it can only be specified at build time or at boot time. In theory, it is possible to change a CPU from being callback-offloaded to not at runtime, but there would need to be an extremely good reason for adding that level of complexity. Lots of "fun" races in there...
Yeah, understood.
(still it's a NO_HZ_FULL wart though IMHO, would be prettier and more usable if it eventually became unified with cpuset and learned how to tap-dance properly;)
-Mike
Quoted 13 lines · Mike Galbraith
Quoted 11 lines · Paul E. McKenney
Quoted 4 lines · Mike Galbraith
NO_HZ_FULLis a property of a set of CPUs. isolcpus is supposed to go away as being a redundant interface to manage a single property of a set of CPUs, but it's perfectly fine forNO_HZ_FULLto add an interface to manage a single property of a set of CPUs. What am I missing?Well, for now, it can only be specified at build time or at boot time. In theory, it is possible to change a CPU from being callback-offloaded to not at runtime, but there would need to be an extremely good reason for adding that level of complexity. Lots of "fun" races in there...
Quoted 5 lines
Yeah, understood.
(still it's a
NO_HZ_FULLwart though IMHO, would be prettier and more usable if it eventually became unified with cpuset and learned how to tap-dance properly;)
Agreed, it would in some sense be nice. What specifically do you need it for? Are you really running workloads that generate large numbers of callbacks spread across most of the CPUs? It was this sort of workload that caused Rik's system to show scary CPU-time accumulation, due to the high overhead of frequent one-to-many wakeups.
If your systems aren't running that kind of high-callback-rate workload, just set CONFIG_RCU_NOCB_CPU_ALL=y and don't worry about it.
If your systems -are- running that kind of high-callback-rate workload, but your system has fewer than 200 CPUs, ensure that you have enough housekeeping CPUs to allow the grace-period kthread sufficient CPU time, set CONFIG_RCU_NOCB_CPU_ALL=y and don't worry about it.
If your systems -are- running that kind of high-callback-rate workload, and your system has more than 200 CPUs, apply the following patch, set CONFIG_RCU_NOCB_CPU_ALL=y and once again don't worry about it. ;-)
Thanx, Paul
------------------------------------------------------------------------
rcu: Parallelize and economize NOCB kthread wakeups
An 80-CPU system with a context-switch-heavy workload can require so many NOCB kthread wakeups that the RCU grace-period kthreads spend several tens of percent of a CPU just awakening things. This clearly will not scale well: If you add enough CPUs, the RCU grace-period kthreads would get behind, increasing grace-period latency.
To avoid this problem, this commit divides the NOCB kthreads into leaders and followers, where the grace-period kthreads awaken the leaders each of whom in turn awakens its followers. By default, the number of groups of kthreads is the square root of the number of CPUs, but this default may be overridden using the rcutree.rcu_nocb_leader_stride boot parameter. This reduces the number of wakeups done per grace period by the RCU grace-period kthread by the square root of the number of CPUs, but of course by shifting those wakeups to the leaders. In addition, because the leaders do grace periods on behalf of their respective followers, the number of wakeups of the followers decreases by up to a factor of two. Instead of being awakened once when new callbacks arrive and again at the end of the grace period, the followers are awakened only at the end of the grace period.
For a numerical example, in a 4096-CPU system, the grace-period kthread would awaken 64 leaders, each of which would awaken its 63 followers at the end of the grace period. This compares favorably with the 79 wakeups for the grace-period kthread on an 80-CPU system.
Documentation/kernel-parameters.txt +7 -0
@@ -2796,6 +2796,13 @@ bytes respectively. Such letter suffixes can also be entirely omitted. quiescent states. Units are jiffies, minimum value is one, and maximum value is HZ. + rcutree.rcu_nocb_leader_stride= [KNL] + Set the number of NOCB kthread groups, which + defaults to the square root of the number of + CPUs. Larger numbers reduces the wakeup overhead + on the per-CPU grace-period kthreads, but increases + that same overhead on each group's leader. + rcutree.qhimark= [KNL] Set threshold of queued RCU callbacks beyond which batch limiting is disabled.
kernel/rcu/tree.h +26 -2
@@ -331,11 +331,29 @@ struct rcu_data {struct rcu_head **nocb_tail;atomic_long_t nocb_q_count;/* # CBs waiting for kthread */ atomic_long_t nocb_q_count_lazy;/* (approximate). */ +struct rcu_head *nocb_follower_head;/* CBs ready to invoke. */ +struct rcu_head **nocb_follower_tail; +atomic_long_t nocb_follower_count;/* # CBs ready to invoke. */ +atomic_long_t nocb_follower_count_lazy;/* (approximate). */ int nocb_p_count;/* # CBs being invoked by kthread */ int nocb_p_count_lazy;/* (approximate). */ wait_queue_head_t nocb_wq;/* For nocb kthreads to sleep on. */ struct task_struct *nocb_kthread;bool nocb_defer_wakeup;/* Defer wakeup of nocb_kthread. */ + +/* The following fields are used by the leader, hence own cacheline. */ +struct rcu_head *nocb_gp_head____cacheline_internodealigned_in_smp ; +/* CBs waiting for GP. */ +struct rcu_head **nocb_gp_tail; +long nocb_gp_count; +long nocb_gp_count_lazy; +bool nocb_leader_wake;/* Is the nocb leader thread awake? */ +struct rcu_data *nocb_next_follower; +/* Next follower in wakeup chain. */ + +/* The following fields are used by the follower, hence new cachline. */ +struct rcu_data *nocb_leader____cacheline_internodealigned_in_smp ; +/* Leader CPU takes GP-end wakeups. */ #endif /* #ifdef CONFIG_RCU_NOCB_CPU */ /* 8) RCU CPU stall data. */
@@ -583,8 +601,14 @@ static bool rcu_nohz_full_cpu(struct rcu_state *rsp);/* Sum up queue lengths for tracing. */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll) { - *ql =atomic_long_read (&rdp->nocb_q_count) + rdp->nocb_p_count; - *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + rdp->nocb_p_count_lazy; + *ql =atomic_long_read (&rdp->nocb_q_count) + + rdp->nocb_p_count + +atomic_long_read (&rdp->nocb_follower_count) + + rdp->nocb_p_count + rdp->nocb_gp_count; + *qll =atomic_long_read (&rdp->nocb_q_count_lazy) + + rdp->nocb_p_count_lazy + +atomic_long_read (&rdp->nocb_follower_count_lazy) + + rdp->nocb_p_count_lazy + rdp->nocb_gp_count_lazy; }#else /* #ifdef CONFIG_RCU_NOCB_CPU */ static inline void rcu_nocb_q_lengths (struct rcu_data *rdp,long *ql,long *qll)
kernel/rcu/tree_plugin.h +211 -41
311 lines not on this page · raw message
Quoted 14 lines · Paul E. McKenney
Quoted 13 lines · Mike Galbraith
Quoted 11 lines · Paul E. McKenney
Quoted 4 lines · Mike Galbraith
NO_HZ_FULLis a property of a set of CPUs. isolcpus is supposed to go away as being a redundant interface to manage a single property of a set of CPUs, but it's perfectly fine forNO_HZ_FULLto add an interface to manage a single property of a set of CPUs. What am I missing?Well, for now, it can only be specified at build time or at boot time. In theory, it is possible to change a CPU from being callback-offloaded to not at runtime, but there would need to be an extremely good reason for adding that level of complexity. Lots of "fun" races in there...
Quoted 8 lines
Quoted 5 lines
Yeah, understood.
(still it's a
NO_HZ_FULLwart though IMHO, would be prettier and more usable if it eventually became unified with cpuset and learned how to tap-dance properly;)Agreed, it would in some sense be nice. What specifically do you need it for?
I personally have zero use for the thing (git/vi aren't particularly perturbation sensitive;). I'm just doing occasional drive-by testing from a distro perspective, how well does it work, what does it cost etc.
Quoted 8 lines
Are you really running workloads that generate large numbers of
callbacks spread across most of the CPUs? It was this sort of workload that caused Rik's system to show scary CPU-time accumulation, due to the high overhead of frequent one-to-many wakeups.If your systems aren't running that kind of high-callback-rate workload, just set
CONFIG_RCU_NOCB_CPU_ALL=yand don't worry about it.
Quoted 8 lines
If your systems -are- running that kind of high-callback-rate workload, but your system has fewer than 200 CPUs, ensure that you have enough housekeeping CPUs to allow the grace-period kthread sufficient CPU time, set
CONFIG_RCU_NOCB_CPU_ALL=yand don't worry about it.If your systems -are- running that kind of high-callback-rate workload, and your system has more than 200 CPUs, apply the following patch, set
CONFIG_RCU_NOCB_CPU_ALL=yand once again don't worry about it. ;-)
Turn it on and don't worry about it is exactly what distros want the obscure feature with very few users to be. Last time I did a drive-by, my boxen said I should continue to worry about it ;-)
-Mike
Quoted 41 lines · Mike Galbraith
Quoted 14 lines · Paul E. McKenney
Quoted 13 lines · Mike Galbraith
Quoted 11 lines · Paul E. McKenney
Quoted 4 lines · Mike Galbraith
NO_HZ_FULLis a property of a set of CPUs. isolcpus is supposed to go away as being a redundant interface to manage a single property of a set of CPUs, but it's perfectly fine forNO_HZ_FULLto add an interface to manage a single property of a set of CPUs. What am I missing?Well, for now, it can only be specified at build time or at boot time. In theory, it is possible to change a CPU from being callback-offloaded to not at runtime, but there would need to be an extremely good reason for adding that level of complexity. Lots of "fun" races in there...
Quoted 8 lines
Quoted 5 lines
Yeah, understood.
(still it's a
NO_HZ_FULLwart though IMHO, would be prettier and more usable if it eventually became unified with cpuset and learned how to tap-dance properly;)Agreed, it would in some sense be nice. What specifically do you need it for?
I personally have zero use for the thing (git/vi aren't particularly perturbation sensitive;). I'm just doing occasional drive-by testing from a distro perspective, how well does it work, what does it cost etc.
Quoted 13 lines
Are you really running workloads that generate large numbers of
callbacks spread across most of the CPUs? It was this sort of workload that caused Rik's system to show scary CPU-time accumulation, due to the high overhead of frequent one-to-many wakeups.If your systems aren't running that kind of high-callback-rate workload, just set
CONFIG_RCU_NOCB_CPU_ALL=yand don't worry about it.If your systems -are- running that kind of high-callback-rate workload, but your system has fewer than 200 CPUs, ensure that you have enough housekeeping CPUs to allow the grace-period kthread sufficient CPU time, set
CONFIG_RCU_NOCB_CPU_ALL=yand don't worry about it.
Quoted 7 lines
Quoted 3 lines
If your systems -are- running that kind of high-callback-rate workload, and your system has more than 200 CPUs, apply the following patch, set
CONFIG_RCU_NOCB_CPU_ALL=yand once again don't worry about it. ;-)Turn it on and don't worry about it is exactly what distros want the obscure feature with very few users to be. Last time I did a drive-by, my boxen said I should continue to worry about it ;-)
Yep, which is the reason for the patch on the last email.
Then again, exactly which feature and which reason for worry?
Thanx, Paul
Quoted 9 lines · Paul E. McKenney
Quoted 3 lines · Mike Galbraith
Turn it on and don't worry about it is exactly what distros want the obscure feature with very few users to be. Last time I did a drive-by, my boxen said I should continue to worry about it ;-)
Yep, which is the reason for the patch on the last email.
Then again, exactly which feature and which reason for worry?
NO_HZ_FULL. I tried ALL a while back, box instantly called me an idiot. Maybe that has improved since, dunno.
Last drive-by I didn't do much overhead measurement, stuck mostly functionality, and it still had rough edges that enterprise users may not fully appreciate. Trying to let 60 of 64 cores do 100% compute showed some cores having a hard time entering tickless at all, and ~200us spikes that I think are due to tick losing skew.. told Frederic I'd take a peek at that, but haven't had time yet. There were other known things as well, like timers and workqueues for which there are patches floating around. All in all, it was waving the men at work sign, pointing at the "Say N" by the config option, and suggesting that ignoring that would not be the cleverest of moves.
-Mike
Quoted 7 lines · Mike Galbraith
Quoted 6 lines · Paul E. McKenney
Quoted 3 lines · Mike Galbraith
Turn it on and don't worry about it is exactly what distros want the obscure feature with very few users to be. Last time I did a drive-by, my boxen said I should continue to worry about it ;-)
Quoted 6 lines
Quoted 3 lines
Yep, which is the reason for the patch on the last email.
Then again, exactly which feature and which reason for worry?
NO_HZ_FULL. I tried ALL a while back, box instantly called me an idiot. Maybe that has improved since, dunno.
Ah, I was thinking in terms of RCU_CPU_NOCB.
Quoted 10 lines
Last drive-by I didn't do much overhead measurement, stuck mostly functionality, and it still had rough edges that enterprise users may not fully appreciate. Trying to let 60 of 64 cores do 100% compute showed some cores having a hard time entering tickless at all, and ~200us spikes that I think are due to tick losing skew.. told Frederic I'd take a peek at that, but haven't had time yet. There were other known things as well, like timers and workqueues for which there are patches floating around. All in all, it was waving the men at work sign, pointing at the "Say N" by the config option, and suggesting that ignoring that would not be the cleverest of moves.
Well, I am not going to join a debate on Kconfig default selection. ;-) I will say that two years ago, setting NO_HZ_FULL=y by default would have been insane. Perhaps soon it will be a no-brainer, and I am of course trying to bring that day closer. Right now it is of course a judgment call.
Thanx, Paul
Quoted 13 lines · Mike Galbraith
Quoted 11 lines · Paul E. McKenney
Quoted 4 lines · Mike Galbraith
NO_HZ_FULLis a property of a set of CPUs. isolcpus is supposed to go away as being a redundant interface to manage a single property of a set of CPUs, but it's perfectly fine forNO_HZ_FULLto add an interface to manage a single property of a set of CPUs. What am I missing?Well, for now, it can only be specified at build time or at boot time. In theory, it is possible to change a CPU from being callback-offloaded to not at runtime, but there would need to be an extremely good reason for adding that level of complexity. Lots of "fun" races in there...
Quoted 5 lines
Yeah, understood.
(still it's a
NO_HZ_FULLwart though IMHO, would be prettier and more usable if it eventually became unified with cpuset and learned how to tap-dance properly;)
Well, the exact same goes for NO_HZ_FULL, quoting Paul (just replacing RCU things with dynticks) it becomes:
"it can only be specified at build time or at boot time.
In theory, it is possible to change a CPU from being idle-dynticks to full-dynticks at runtime, but there would need to be an extremely good reason for adding that level of complexity. Lots of "fun" races in there..."
And I'm not even sure that somebody actually uses full dynticks today. I only know that some financial institutions are considering it, which is not cheering me up much...
So we are very far from that day when we'll migrate to a runtime interface.