Messages in this thread Patch in this message | | | Subject | Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide | From | Atish Patra <> | Date | Wed, 20 Sep 2017 14:36:35 -0500 |
| |
On 08/11/2017 04:45 AM, Brendan Jackman wrote: > This patch adds a parameter to select_task_rq, sibling_count_hint > allowing the caller, where it has this information, to inform the > sched_class the number of tasks that are being woken up as part of > the same event. > > The wake_q mechanism is one case where this information is available. > > select_task_rq_fair can then use the information to detect that it > needs to widen the search space for task placement in order to avoid > overloading the last-level cache domain's CPUs. > > * * * > > The reason I am investigating this change is the following use case > on ARM big.LITTLE (asymmetrical CPU capacity): 1 task per CPU, which > all repeatedly do X amount of work then > pthread_barrier_wait (i.e. sleep until the last task finishes its X > and hits the barrier).
Are all these tasks are homogeneous i.e. does exactly equal amount of work?
On big.LITTLE, the tasks which get a "big" CPU > finish faster, and then those CPUs pull over the tasks that are still > running: > > v CPU v ->time-> > > ------------- > 0 (big) 11111 /333 > ------------- > 1 (big) 22222 /444| > ------------- > 2 (LITTLE) 333333/ > ------------- > 3 (LITTLE) 444444/ > ------------- > > Now when task 4 hits the barrier (at |) and wakes the others up, > there are 4 tasks with prev_cpu=<big> and 0 tasks with > prev_cpu=<little>. want_affine therefore means that we'll only look > in CPUs 0 and 1 (sd_llc), so tasks will be unnecessarily coscheduled > on the bigs until the next load balance, something like this: > > v CPU v ->time-> > > ------------------------ > 0 (big) 11111 /333 31313\33333 > ------------------------ > 1 (big) 22222 /444|424\4444444 > ------------------------ > 2 (LITTLE) 333333/ \222222 > ------------------------ > 3 (LITTLE) 444444/ \1111 > ------------------------ > ^^^ > underutilization > > So, I'm trying to get want_affine = 0 for these tasks. > > I don't _think_ any incarnation of the wakee_flips mechanism can help > us here because which task is waker and which tasks are wakees > generally changes with each iteration. > > However pthread_barrier_wait (or more accurately FUTEX_WAKE) has the > nice property that we know exactly how many tasks are being woken, so > we can cheat. > > It might be a disadvantage that we "widen" _every_ task that's woken in > an event, while select_idle_sibling would work fine for the first > sd_llc_size - 1 tasks. > > IIUC, if wake_affine() behaves correctly this trick wouldn't be > necessary on SMP systems, so it might be best guarded by the presence > of SD_ASYM_CPUCAPACITY? > > * * * > > Final note.. > > In order to observe "perfect" behaviour for this use case, I also had > to disable the TTWU_QUEUE sched feature. Suppose during the wakeup > above we are working through the work queue and have placed tasks 3 > and 2, and are about to place task 1: > > v CPU v ->time-> > > -------------- > 0 (big) 11111 /333 3 > -------------- > 1 (big) 22222 /444|4 > -------------- > 2 (LITTLE) 333333/ 2 > -------------- > 3 (LITTLE) 444444/ <- Task 1 should go here > -------------- > > If TTWU_QUEUE is enabled, we will not yet have enqueued task > 2 (having instead sent a reschedule IPI) or attached its load to CPU > 2. So we are likely to also place task 1 on cpu 2. Disabling > TTWU_QUEUE means that we enqueue task 2 before placing task 1, > solving this issue. TTWU_QUEUE is there to minimise rq lock > contention, and I guess that this contention is less of an issue on > big.LITTLE systems since they have relatively few CPUs, which > suggests the trade-off makes sense here. > > Signed-off-by: Brendan Jackman <brendan.jackman@arm.com> > Cc: Ingo Molnar <mingo@redhat.com> > Cc: Peter Zijlstra <peterz@infradead.org> > Cc: Josef Bacik <josef@toxicpanda.com> > Cc: Joel Fernandes <joelaf@google.com> > Cc: Mike Galbraith <efault@gmx.de> > Cc: Matt Fleming <matt@codeblueprint.co.uk> > --- > include/linux/sched/wake_q.h | 2 ++ > kernel/sched/core.c | 34 +++++++++++++++++++++++----------- > kernel/sched/deadline.c | 3 ++- > kernel/sched/fair.c | 17 +++++++++++------ > kernel/sched/idle_task.c | 3 ++- > kernel/sched/rt.c | 3 ++- > kernel/sched/sched.h | 3 ++- > kernel/sched/stop_task.c | 3 ++- > 8 files changed, 46 insertions(+), 22 deletions(-) > > diff --git a/include/linux/sched/wake_q.h b/include/linux/sched/wake_q.h > index d03d8a9047dc..607a888eb35b 100644 > --- a/include/linux/sched/wake_q.h > +++ b/include/linux/sched/wake_q.h > @@ -33,6 +33,7 @@ > struct wake_q_head { > struct wake_q_node *first; > struct wake_q_node **lastp; > + int count; > }; >
Instead of passing around the head count, can we store the count in task_struct ? The patch would be lot less invasive for a single use-case.
> #define WAKE_Q_TAIL ((struct wake_q_node *) 0x01) > @@ -44,6 +45,7 @@ static inline void wake_q_init(struct wake_q_head *head) > { > head->first = WAKE_Q_TAIL; > head->lastp = &head->first; > + head->count = 0; > } > > extern void wake_q_add(struct wake_q_head *head, > diff --git a/kernel/sched/core.c b/kernel/sched/core.c > index 0869b20fba81..ddf9257b1467 100644 > --- a/kernel/sched/core.c > +++ b/kernel/sched/core.c > @@ -438,6 +438,8 @@ void wake_q_add(struct wake_q_head *head, struct task_struct *task) > if (cmpxchg(&node->next, NULL, WAKE_Q_TAIL)) > return; > > + head->count++; > + > get_task_struct(task); > > /* > @@ -447,6 +449,10 @@ void wake_q_add(struct wake_q_head *head, struct task_struct *task) > head->lastp = &node->next; > } > > +static int > +try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags, > + int sibling_count_hint); > + > void wake_up_q(struct wake_q_head *head) > { > struct wake_q_node *node = head->first; > @@ -461,10 +467,10 @@ void wake_up_q(struct wake_q_head *head) > task->wake_q.next = NULL; > > /* > - * wake_up_process() implies a wmb() to pair with the queueing > + * try_to_wake_up() implies a wmb() to pair with the queueing > * in wake_q_add() so as not to miss wakeups. > */ > - wake_up_process(task); > + try_to_wake_up(task, TASK_NORMAL, 0, head->count); > put_task_struct(task); > } > } > @@ -1527,12 +1533,14 @@ static int select_fallback_rq(int cpu, struct task_struct *p) > * The caller (fork, wakeup) owns p->pi_lock, ->cpus_allowed is stable. > */ > static inline > -int select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags) > +int select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags, > + int sibling_count_hint) > { > lockdep_assert_held(&p->pi_lock); > > if (p->nr_cpus_allowed > 1) > - cpu = p->sched_class->select_task_rq(p, cpu, sd_flags, wake_flags); > + cpu = p->sched_class->select_task_rq(p, cpu, sd_flags, wake_flags, > + sibling_count_hint); > else > cpu = cpumask_any(&p->cpus_allowed); > > @@ -1944,6 +1952,8 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags) > * @p: the thread to be awakened > * @state: the mask of task states that can be woken > * @wake_flags: wake modifier flags (WF_*) > + * @sibling_count_hint: A hint at the number of threads that are being woken up > + * in this event.
I also had the same thought as Joel about the naming. Probably wakee_count ?
> * > * If (@state & @p->state) @p->state = TASK_RUNNING. > * > @@ -1956,7 +1966,8 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags) > * %false otherwise. > */ > static int > -try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) > +try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags, > + int sibling_count_hint) > { > unsigned long flags; > int cpu, success = 0; > @@ -2042,7 +2053,8 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) > atomic_dec(&task_rq(p)->nr_iowait); > } > > - cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags); > + cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags, > + sibling_count_hint); > if (task_cpu(p) != cpu) { > wake_flags |= WF_MIGRATED; > set_task_cpu(p, cpu); > @@ -2130,13 +2142,13 @@ static void try_to_wake_up_local(struct task_struct *p, struct rq_flags *rf) > */ > int wake_up_process(struct task_struct *p) > { > - return try_to_wake_up(p, TASK_NORMAL, 0); > + return try_to_wake_up(p, TASK_NORMAL, 0, 1); > } > EXPORT_SYMBOL(wake_up_process); > > int wake_up_state(struct task_struct *p, unsigned int state) > { > - return try_to_wake_up(p, state, 0); > + return try_to_wake_up(p, state, 0, 1); > } > > /* > @@ -2442,7 +2454,7 @@ void wake_up_new_task(struct task_struct *p) > * Use __set_task_cpu() to avoid calling sched_class::migrate_task_rq, > * as we're not fully set-up yet. > */ > - __set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0)); > + __set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0, 1)); > #endif > rq = __task_rq_lock(p, &rf); > update_rq_clock(rq); > @@ -2893,7 +2905,7 @@ void sched_exec(void) > int dest_cpu; > > raw_spin_lock_irqsave(&p->pi_lock, flags); > - dest_cpu = p->sched_class->select_task_rq(p, task_cpu(p), SD_BALANCE_EXEC, 0); > + dest_cpu = p->sched_class->select_task_rq(p, task_cpu(p), SD_BALANCE_EXEC, 0, 1); > if (dest_cpu == smp_processor_id()) > goto unlock; > > @@ -3582,7 +3594,7 @@ asmlinkage __visible void __sched preempt_schedule_irq(void) > int default_wake_function(wait_queue_entry_t *curr, unsigned mode, int wake_flags, > void *key) > { > - return try_to_wake_up(curr->private, mode, wake_flags); > + return try_to_wake_up(curr->private, mode, wake_flags, 1); > } > EXPORT_SYMBOL(default_wake_function); > > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c > index 755bd3f1a1a9..69a9dd407267 100644 > --- a/kernel/sched/deadline.c > +++ b/kernel/sched/deadline.c > @@ -1516,7 +1516,8 @@ static void yield_task_dl(struct rq *rq) > static int find_later_rq(struct task_struct *task); > > static int > -select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags) > +select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags, > + int sibling_count_hint) > { > struct task_struct *curr; > struct rq *rq; > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c > index c95880e216f6..0a9d706b62bf 100644 > --- a/kernel/sched/fair.c > +++ b/kernel/sched/fair.c > @@ -5332,15 +5332,18 @@ static void record_wakee(struct task_struct *p) > * whatever is irrelevant, spread criteria is apparent partner count exceeds > * socket size. > */ > -static int wake_wide(struct task_struct *p) > +static int wake_wide(struct task_struct *p, int sibling_count_hint) > { > unsigned int master = current->wakee_flips; > unsigned int slave = p->wakee_flips; > - int factor = this_cpu_read(sd_llc_size); > + int llc_size = this_cpu_read(sd_llc_size); > + > + if (sibling_count_hint >= llc_size) > + return 1; > Since we are talking about 1 task per cpu, should it be sibling_count_hint > llc_size ?
> if (master < slave) > swap(master, slave); > - if (slave < factor || master < slave * factor) > + if (slave < llc_size || master < slave * llc_size) > return 0; > return 1; > } > @@ -5869,7 +5872,8 @@ static int wake_cap(struct task_struct *p, int cpu, int prev_cpu) > * preempt must be disabled. > */ > static int > -select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags) > +select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags, > + int sibling_count_hint) > { > struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL; > int cpu = smp_processor_id(); > @@ -5879,8 +5883,9 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f > > if (sd_flag & SD_BALANCE_WAKE) { > record_wakee(p); > - want_affine = !wake_wide(p) && !wake_cap(p, cpu, prev_cpu) > - && cpumask_test_cpu(cpu, &p->cpus_allowed); > + want_affine = !wake_wide(p, sibling_count_hint) && > + !wake_cap(p, cpu, prev_cpu) && > + cpumask_test_cpu(cpu, &p->cpus_allowed); > } > > rcu_read_lock(); > diff --git a/kernel/sched/idle_task.c b/kernel/sched/idle_task.c > index 0c00172db63e..3c343e055110 100644 > --- a/kernel/sched/idle_task.c > +++ b/kernel/sched/idle_task.c > @@ -9,7 +9,8 @@ > > #ifdef CONFIG_SMP > static int > -select_task_rq_idle(struct task_struct *p, int cpu, int sd_flag, int flags) > +select_task_rq_idle(struct task_struct *p, int cpu, int sd_flag, int flags, > + int sibling_count_hint) > { > return task_cpu(p); /* IDLE tasks as never migrated */ > } > diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c > index 45caf937ef90..b9937dccb8b3 100644 > --- a/kernel/sched/rt.c > +++ b/kernel/sched/rt.c > @@ -1387,7 +1387,8 @@ static void yield_task_rt(struct rq *rq) > static int find_lowest_rq(struct task_struct *task); > > static int > -select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags) > +select_task_rq_rt(struct task_struct *p, int cpu, int sd_flag, int flags, > + int sibling_count_hint) > { > struct task_struct *curr; > struct rq *rq; > diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h > index eeef1a3086d1..56ae525618e9 100644 > --- a/kernel/sched/sched.h > +++ b/kernel/sched/sched.h > @@ -1419,7 +1419,8 @@ struct sched_class { > void (*put_prev_task) (struct rq *rq, struct task_struct *p); > > #ifdef CONFIG_SMP > - int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags); > + int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags, > + int subling_count_hint); > void (*migrate_task_rq)(struct task_struct *p); > > void (*task_woken) (struct rq *this_rq, struct task_struct *task); > diff --git a/kernel/sched/stop_task.c b/kernel/sched/stop_task.c > index 9f69fb630853..d0ce4fbb18ef 100644 > --- a/kernel/sched/stop_task.c > +++ b/kernel/sched/stop_task.c > @@ -11,7 +11,8 @@ > > #ifdef CONFIG_SMP > static int > -select_task_rq_stop(struct task_struct *p, int cpu, int sd_flag, int flags) > +select_task_rq_stop(struct task_struct *p, int cpu, int sd_flag, int flags, > + int sibling_count_hint) > { > return task_cpu(p); /* stop tasks as never migrate */ > } >
| |