Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1734657 > unrolled thread
| Started by | Joel Fernandes <joelaf@google.com> |
|---|---|
| First post | 2017-09-19 07:20 +0200 |
| Last post | 2017-09-20 11:50 +0200 |
| Articles | 10 — 3 participants |
Back to article view | Back to linux.kernel
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Joel Fernandes <joelaf@google.com> - 2017-09-19 07:20 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Brendan Jackman <brendan.jackman@arm.com> - 2017-09-19 12:10 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Joel Fernandes <joelaf@google.com> - 2017-09-20 06:50 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Joel Fernandes <joelaf@google.com> - 2017-09-20 07:10 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Brendan Jackman <brendan.jackman@arm.com> - 2017-09-20 11:40 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Joel Fernandes <joelaf@google.com> - 2017-09-20 22:30 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Atish Patra <atish.patra@oracle.com> - 2017-09-20 23:20 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Joel Fernandes <joelaf@google.com> - 2017-09-21 08:00 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Atish Patra <atish.patra@oracle.com> - 2017-09-21 19:00 +0200
Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide Brendan Jackman <brendan.jackman@arm.com> - 2017-09-20 11:50 +0200
| From | Joel Fernandes <joelaf@google.com> |
|---|---|
| Date | 2017-09-19 07:20 +0200 |
| Subject | Re: [RFC] sched/fair: Use wake_q length as a hint for wake_wide |
| Message-ID | <urj6W-8lb-3@gated-at.bofh.it> |
Hi Brendan,
On Fri, Aug 11, 2017 at 2:45 AM, Brendan Jackman
<brendan.jackman@arm.com> 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). 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/
> -------------
This is because of the newly idle balancing right?
>
> 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
I wonder if this problem can be better solved by not having the first
newly-idle-balance pull happen based on some condition, only to be
corrected later by another balancing act?
>
> 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
Actually wake_affine doesn't check for balance if previous/next cpu
are within the same shared cache domain. The difference is some time
ago it would return true for shared cache but now it returns false as
of 4.14-rc1:
http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
Since it would return false in the above wake up cases for task 1 and
2, it would then run select_idle_sibling on the previous CPU which is
also within the big cluster, so I don't think it will make a
difference in this case... Infact what it returns probably doesn't
matter.
> 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.
Yeah, OTOH probably once those IPIs are sent, the select path should I
feel be smart enough to factor those pending enqueues, not sure how
hard or meaningful it is to implement something like that..
>
> 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;
> };
>
> #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);
Shouldn't you reset head->count after all the tasks have been woken up?
> }
> }
> @@ -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)
This variable seems a bit long to me, how about just sibling_count?
> {
> 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);
same.
<snip>
>
> 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);
s/subling/sibling/
thanks,
- Joel
[toc] | [next] | [standalone]
| From | Brendan Jackman <brendan.jackman@arm.com> |
|---|---|
| Date | 2017-09-19 12:10 +0200 |
| Message-ID | <urnDA-3YD-17@gated-at.bofh.it> |
| In reply to | #1734657 |
On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
> Hi Brendan,
Hi Joel,
Thanks for taking a look :)
> On Fri, Aug 11, 2017 at 2:45 AM, Brendan Jackman
> <brendan.jackman@arm.com> 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). 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/
>> -------------
>
> This is because of the newly idle balancing right?
Probably not: before CPUs 0 and 1 will pull tasks their utilization
(tasks 1 and 2's blocked load) needs to decay enough that they have more
spare capacity than CPUs 2 and 3 (with imbalance_pct etc), so it's more
likely to be a nohz idle balance. We also need need_active_balance to be
satisfied (assuming 3 and 4 are running constantly) - in Android this is
hastened by a special case [1], in mainline it takes longer.
[1] https://android.googlesource.com/kernel/common/+/android-4.4/kernel/sched/fair.c#8865
>>
>> 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
>
> I wonder if this problem can be better solved by not having the first
> newly-idle-balance pull happen based on some condition, only to be
> corrected later by another balancing act?
Well the fact that CPUs 0 and 1 pull 3 and 4 is desirable - we want to
use the big CPUs as much as possible for these always-running
tasks. Moving load back to the LITTLE CPUs is not "correcting" a
previous mistake, it's responding to a change in conditions (i.e. we
have more runnable tasks than big CPUs now) and this patch is about
trying to do that response ASAP.
>>
>> 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
>
> Actually wake_affine doesn't check for balance if previous/next cpu
> are within the same shared cache domain. The difference is some time
> ago it would return true for shared cache but now it returns false as
> of 4.14-rc1:
> http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>
> Since it would return false in the above wake up cases for task 1 and
> 2, it would then run select_idle_sibling on the previous CPU which is
> also within the big cluster, so I don't think it will make a
> difference in this case... Infact what it returns probably doesn't
> matter.
So my paragraph here was making a leap in reasoning, let me try to fill
the gap: On SMP these tasks never need to move around. If by some chance
they did get coscheduled, the first load balance would spread them out and
then every time they wake up from then on, prev_cpu is the sensible
choice. So it will look something like:
v CPU v ->time->
-------------
{ 0 (SAME) 11111111111
cache { -------------
{ 1 (SAME) 222222222222|
-------------
{ 2 (SAME) 33333333333
cache { -------------
{ 3 (SAME) 44444444444
-------------
So here, task 2 wakes up the other guys and when it's doing tasks 3 and
4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
basically wake_affine's job to decide between prev_cpu and
smp_processor_id(). So "if wake_affine is behaving correctly" the
problem that this patch aims to solve (i.e. the fact that we overload
the waker's LLC domain because of bias towards prev_cpu) does not arise
on SMP.
>> 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.
>
> Yeah, OTOH probably once those IPIs are sent, the select path should I
> feel be smart enough to factor those pending enqueues, not sure how
> hard or meaningful it is to implement something like that..
Yeah that should be possible - in fact I've just noticed that
find_idlest_cpu already checks idle_cpu() which takes pending enqueues
(rq->wake_list) into account, and I think find_idlest_cpu should be used
in the case I'm talking about here.. I must have been doing something
wrong when testing.
Cheers,
Brendan
>>
>> 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;
>> };
>>
>> #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);
>
> Shouldn't you reset head->count after all the tasks have been woken up?
>
>> }
>> }
>> @@ -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)
>
> This variable seems a bit long to me, how about just sibling_count?
>
>> {
>> 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);
>
> same.
>
> <snip>
>
>>
>> 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);
>
> s/subling/sibling/
>
>
> thanks,
>
> - Joel
[toc] | [prev] | [next] | [standalone]
| From | Joel Fernandes <joelaf@google.com> |
|---|---|
| Date | 2017-09-20 06:50 +0200 |
| Message-ID | <urF7r-6xD-13@gated-at.bofh.it> |
| In reply to | #1734789 |
On Tue, Sep 19, 2017 at 3:05 AM, Brendan Jackman
<brendan.jackman@arm.com> wrote:
> On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
>> Hi Brendan,
> Hi Joel,
>
> Thanks for taking a look :)
>
>> On Fri, Aug 11, 2017 at 2:45 AM, Brendan Jackman
>> <brendan.jackman@arm.com> 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). 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/
>>> -------------
>>
>> This is because of the newly idle balancing right?
>
> Probably not: before CPUs 0 and 1 will pull tasks their utilization
> (tasks 1 and 2's blocked load) needs to decay enough that they have more
> spare capacity than CPUs 2 and 3 (with imbalance_pct etc), so it's more
> likely to be a nohz idle balance. We also need need_active_balance to be
> satisfied (assuming 3 and 4 are running constantly) - in Android this is
> hastened by a special case [1], in mainline it takes longer.
>
> [1] https://android.googlesource.com/kernel/common/+/android-4.4/kernel/sched/fair.c#8865
Ok, I agree.
>
>>>
>>> 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
>>
>> I wonder if this problem can be better solved by not having the first
>> newly-idle-balance pull happen based on some condition, only to be
>> corrected later by another balancing act?
>
> Well the fact that CPUs 0 and 1 pull 3 and 4 is desirable - we want to
> use the big CPUs as much as possible for these always-running
> tasks. Moving load back to the LITTLE CPUs is not "correcting" a
> previous mistake, it's responding to a change in conditions (i.e. we
> have more runnable tasks than big CPUs now) and this patch is about
> trying to do that response ASAP.
Agreed.
>>>
>>> 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
>>
>> Actually wake_affine doesn't check for balance if previous/next cpu
>> are within the same shared cache domain. The difference is some time
>> ago it would return true for shared cache but now it returns false as
>> of 4.14-rc1:
>> http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>>
>> Since it would return false in the above wake up cases for task 1 and
>> 2, it would then run select_idle_sibling on the previous CPU which is
>> also within the big cluster, so I don't think it will make a
>> difference in this case... Infact what it returns probably doesn't
>> matter.
>
> So my paragraph here was making a leap in reasoning, let me try to fill
> the gap: On SMP these tasks never need to move around. If by some chance
> they did get coscheduled, the first load balance would spread them out and
> then every time they wake up from then on, prev_cpu is the sensible
> choice. So it will look something like:
>
> v CPU v ->time->
>
> -------------
> { 0 (SAME) 11111111111
> cache { -------------
> { 1 (SAME) 222222222222|
> -------------
> { 2 (SAME) 33333333333
> cache { -------------
> { 3 (SAME) 44444444444
> -------------
>
> So here, task 2 wakes up the other guys and when it's doing tasks 3 and
> 4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
> basically wake_affine's job to decide between prev_cpu and
> smp_processor_id(). So "if wake_affine is behaving correctly" the
> problem that this patch aims to solve (i.e. the fact that we overload
> the waker's LLC domain because of bias towards prev_cpu) does not arise
> on SMP.
>
Yes SMP, but your patch is for solving a problem for non-SMP. So your
original statement about wake_affine solving any problem for SMP is
not relevant I feel :-P. I guess you can just kill this para from the
commit message to prevent confusion.
>>> 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.
>>
>> Yeah, OTOH probably once those IPIs are sent, the select path should I
>> feel be smart enough to factor those pending enqueues, not sure how
>> hard or meaningful it is to implement something like that..
>
> Yeah that should be possible - in fact I've just noticed that
> find_idlest_cpu already checks idle_cpu() which takes pending enqueues
> (rq->wake_list) into account, and I think find_idlest_cpu should be used
> in the case I'm talking about here.. I must have been doing something
> wrong when testing.
Oh ok!
thanks,
- Joel
[..]
[toc] | [prev] | [next] | [standalone]
| From | Joel Fernandes <joelaf@google.com> |
|---|---|
| Date | 2017-09-20 07:10 +0200 |
| Message-ID | <urFqN-6Vo-7@gated-at.bofh.it> |
| In reply to | #1735442 |
> On Tue, Sep 19, 2017 at 3:05 AM, Brendan Jackman
> <brendan.jackman@arm.com> wrote:
>> On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
[..]
>>>> IIUC, if wake_affine() behaves correctly this trick wouldn't be
>>>> necessary on SMP systems, so it might be best guarded by the presence
>>>
>>> Actually wake_affine doesn't check for balance if previous/next cpu
>>> are within the same shared cache domain. The difference is some time
>>> ago it would return true for shared cache but now it returns false as
>>> of 4.14-rc1:
>>> http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>>>
>>> Since it would return false in the above wake up cases for task 1 and
>>> 2, it would then run select_idle_sibling on the previous CPU which is
>>> also within the big cluster, so I don't think it will make a
>>> difference in this case... Infact what it returns probably doesn't
>>> matter.
>>
>> So my paragraph here was making a leap in reasoning, let me try to fill
>> the gap: On SMP these tasks never need to move around. If by some chance
>> they did get coscheduled, the first load balance would spread them out and
>> then every time they wake up from then on, prev_cpu is the sensible
>> choice. So it will look something like:
>>
>> v CPU v ->time->
>>
>> -------------
>> { 0 (SAME) 11111111111
>> cache { -------------
>> { 1 (SAME) 222222222222|
>> -------------
>> { 2 (SAME) 33333333333
>> cache { -------------
>> { 3 (SAME) 44444444444
>> -------------
>>
>> So here, task 2 wakes up the other guys and when it's doing tasks 3 and
>> 4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
>> basically wake_affine's job to decide between prev_cpu and
>> smp_processor_id(). So "if wake_affine is behaving correctly" the
>> problem that this patch aims to solve (i.e. the fact that we overload
>> the waker's LLC domain because of bias towards prev_cpu) does not arise
>> on SMP.
>>
>
> Yes SMP, but your patch is for solving a problem for non-SMP. So your
> original statement about wake_affine solving any problem for SMP is
> not relevant I feel :-P. I guess you can just kill this para from the
> commit message to prevent confusion.
Ok I take that back, you were talking about guarding this feature by
the SD_ASYM_CPUCAPACITY flag.
I don't think that protection would be helpful because you can have
the same issue if the tasks do different amount of work on SMP. So in
that case some threads might still complete before the others and you
run into the same thing.
thanks,
- Joel
[toc] | [prev] | [next] | [standalone]
| From | Brendan Jackman <brendan.jackman@arm.com> |
|---|---|
| Date | 2017-09-20 11:40 +0200 |
| Message-ID | <urJE5-19d-5@gated-at.bofh.it> |
| In reply to | #1735499 |
On Wed, Sep 20 2017 at 05:06, Joel Fernandes wrote:
>> On Tue, Sep 19, 2017 at 3:05 AM, Brendan Jackman
>> <brendan.jackman@arm.com> wrote:
>>> On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
> [..]
>>>>> IIUC, if wake_affine() behaves correctly this trick wouldn't be
>>>>> necessary on SMP systems, so it might be best guarded by the presence
>>>>
>>>> Actually wake_affine doesn't check for balance if previous/next cpu
>>>> are within the same shared cache domain. The difference is some time
>>>> ago it would return true for shared cache but now it returns false as
>>>> of 4.14-rc1:
>>>> http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>>>>
>>>> Since it would return false in the above wake up cases for task 1 and
>>>> 2, it would then run select_idle_sibling on the previous CPU which is
>>>> also within the big cluster, so I don't think it will make a
>>>> difference in this case... Infact what it returns probably doesn't
>>>> matter.
>>>
>>> So my paragraph here was making a leap in reasoning, let me try to fill
>>> the gap: On SMP these tasks never need to move around. If by some chance
>>> they did get coscheduled, the first load balance would spread them out and
>>> then every time they wake up from then on, prev_cpu is the sensible
>>> choice. So it will look something like:
>>>
>>> v CPU v ->time->
>>>
>>> -------------
>>> { 0 (SAME) 11111111111
>>> cache { -------------
>>> { 1 (SAME) 222222222222|
>>> -------------
>>> { 2 (SAME) 33333333333
>>> cache { -------------
>>> { 3 (SAME) 44444444444
>>> -------------
>>>
>>> So here, task 2 wakes up the other guys and when it's doing tasks 3 and
>>> 4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
>>> basically wake_affine's job to decide between prev_cpu and
>>> smp_processor_id(). So "if wake_affine is behaving correctly" the
>>> problem that this patch aims to solve (i.e. the fact that we overload
>>> the waker's LLC domain because of bias towards prev_cpu) does not arise
>>> on SMP.
>>>
>>
>> Yes SMP, but your patch is for solving a problem for non-SMP. So your
>> original statement about wake_affine solving any problem for SMP is
>> not relevant I feel :-P. I guess you can just kill this para from the
>> commit message to prevent confusion.
>
> Ok I take that back, you were talking about guarding this feature by
> the SD_ASYM_CPUCAPACITY flag.
>
> I don't think that protection would be helpful because you can have
> the same issue if the tasks do different amount of work on SMP. So in
> that case some threads might still complete before the others and you
> run into the same thing.
Well assuming we're still talking about one task per CPU, if you have
tasks doing different amount of work there's still no reason to move the
longer-running threads around. The only reason that happens in my
example is because of the asym capacity.
There might be a case on SMP where this would have a benefit, but the
reason I suggested disabling it for SMP is because the cost of this
patch is that we use the slow path a whole load more for certain usage
patterns. On big.LITTLE etc. my thinking is that's the price we have to
pay to get task placement right; on SMP I don't think we'd want to pay
that price unless we see a good reason.
[toc] | [prev] | [next] | [standalone]
| From | Joel Fernandes <joelaf@google.com> |
|---|---|
| Date | 2017-09-20 22:30 +0200 |
| Message-ID | <urTN8-7TQ-21@gated-at.bofh.it> |
| In reply to | #1735666 |
On Wed, Sep 20, 2017 at 2:33 AM, Brendan Jackman
<brendan.jackman@arm.com> wrote:
>
> On Wed, Sep 20 2017 at 05:06, Joel Fernandes wrote:
>>> On Tue, Sep 19, 2017 at 3:05 AM, Brendan Jackman
>>> <brendan.jackman@arm.com> wrote:
>>>> On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
>> [..]
>>>>>> IIUC, if wake_affine() behaves correctly this trick wouldn't be
>>>>>> necessary on SMP systems, so it might be best guarded by the presence
>>>>>
>>>>> Actually wake_affine doesn't check for balance if previous/next cpu
>>>>> are within the same shared cache domain. The difference is some time
>>>>> ago it would return true for shared cache but now it returns false as
>>>>> of 4.14-rc1:
>>>>> http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>>>>>
>>>>> Since it would return false in the above wake up cases for task 1 and
>>>>> 2, it would then run select_idle_sibling on the previous CPU which is
>>>>> also within the big cluster, so I don't think it will make a
>>>>> difference in this case... Infact what it returns probably doesn't
>>>>> matter.
>>>>
>>>> So my paragraph here was making a leap in reasoning, let me try to fill
>>>> the gap: On SMP these tasks never need to move around. If by some chance
>>>> they did get coscheduled, the first load balance would spread them out and
>>>> then every time they wake up from then on, prev_cpu is the sensible
>>>> choice. So it will look something like:
>>>>
>>>> v CPU v ->time->
>>>>
>>>> -------------
>>>> { 0 (SAME) 11111111111
>>>> cache { -------------
>>>> { 1 (SAME) 222222222222|
>>>> -------------
>>>> { 2 (SAME) 33333333333
>>>> cache { -------------
>>>> { 3 (SAME) 44444444444
>>>> -------------
>>>>
>>>> So here, task 2 wakes up the other guys and when it's doing tasks 3 and
>>>> 4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
>>>> basically wake_affine's job to decide between prev_cpu and
>>>> smp_processor_id(). So "if wake_affine is behaving correctly" the
>>>> problem that this patch aims to solve (i.e. the fact that we overload
>>>> the waker's LLC domain because of bias towards prev_cpu) does not arise
>>>> on SMP.
>>>>
>>>
>>> Yes SMP, but your patch is for solving a problem for non-SMP. So your
>>> original statement about wake_affine solving any problem for SMP is
>>> not relevant I feel :-P. I guess you can just kill this para from the
>>> commit message to prevent confusion.
>>
>> Ok I take that back, you were talking about guarding this feature by
>> the SD_ASYM_CPUCAPACITY flag.
>>
>> I don't think that protection would be helpful because you can have
>> the same issue if the tasks do different amount of work on SMP. So in
>> that case some threads might still complete before the others and you
>> run into the same thing.
>
> Well assuming we're still talking about one task per CPU, if you have
> tasks doing different amount of work there's still no reason to move the
> longer-running threads around. The only reason that happens in my
> example is because of the asym capacity.
Yes but you can very well have RT pressure and things that temporarily
change the capacity equality. Also this is a simple benchmark and for
any reason you have more than 1 task running on those other CPUs and
then the idle CPUs run some of the tasks and you run into a similar
situation that might need your patch..
Also one more note, the SD_ASYM_CPUCAPACITY protection is still not
needed because SD_BALANCE_WAKE isn't turned on for
!SD_ASYM_CPUCAPACITY from what I learnt from discussions with Mike, I
believe its this piece of code in sd_init that actually enables it:
if (sd->flags & SD_ASYM_CPUCAPACITY) {
struct sched_domain *t = sd;
for_each_lower_domain(t)
t->flags |= SD_BALANCE_WAKE;
}
thanks,
- Joel
[toc] | [prev] | [next] | [standalone]
| From | Atish Patra <atish.patra@oracle.com> |
|---|---|
| Date | 2017-09-20 23:20 +0200 |
| Message-ID | <urUzx-8sm-37@gated-at.bofh.it> |
| In reply to | #1736088 |
On 09/20/2017 03:23 PM, Joel Fernandes wrote:
> On Wed, Sep 20, 2017 at 2:33 AM, Brendan Jackman
> <brendan.jackman@arm.com> wrote:
>>
>> On Wed, Sep 20 2017 at 05:06, Joel Fernandes wrote:
>>>> On Tue, Sep 19, 2017 at 3:05 AM, Brendan Jackman
>>>> <brendan.jackman@arm.com> wrote:
>>>>> On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
>>> [..]
>>>>>>> IIUC, if wake_affine() behaves correctly this trick wouldn't be
>>>>>>> necessary on SMP systems, so it might be best guarded by the presence
>>>>>>
>>>>>> Actually wake_affine doesn't check for balance if previous/next cpu
>>>>>> are within the same shared cache domain. The difference is some time
>>>>>> ago it would return true for shared cache but now it returns false as
>>>>>> of 4.14-rc1:
>>>>>> http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>>>>>>
>>>>>> Since it would return false in the above wake up cases for task 1 and
>>>>>> 2, it would then run select_idle_sibling on the previous CPU which is
>>>>>> also within the big cluster, so I don't think it will make a
>>>>>> difference in this case... Infact what it returns probably doesn't
>>>>>> matter.
>>>>>
>>>>> So my paragraph here was making a leap in reasoning, let me try to fill
>>>>> the gap: On SMP these tasks never need to move around. If by some chance
>>>>> they did get coscheduled, the first load balance would spread them out and
>>>>> then every time they wake up from then on, prev_cpu is the sensible
>>>>> choice. So it will look something like:
>>>>>
>>>>> v CPU v ->time->
>>>>>
>>>>> -------------
>>>>> { 0 (SAME) 11111111111
>>>>> cache { -------------
>>>>> { 1 (SAME) 222222222222|
>>>>> -------------
>>>>> { 2 (SAME) 33333333333
>>>>> cache { -------------
>>>>> { 3 (SAME) 44444444444
>>>>> -------------
>>>>>
>>>>> So here, task 2 wakes up the other guys and when it's doing tasks 3 and
>>>>> 4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
>>>>> basically wake_affine's job to decide between prev_cpu and
>>>>> smp_processor_id(). So "if wake_affine is behaving correctly" the
>>>>> problem that this patch aims to solve (i.e. the fact that we overload
>>>>> the waker's LLC domain because of bias towards prev_cpu) does not arise
>>>>> on SMP.
>>>>>
>>>>
>>>> Yes SMP, but your patch is for solving a problem for non-SMP. So your
>>>> original statement about wake_affine solving any problem for SMP is
>>>> not relevant I feel :-P. I guess you can just kill this para from the
>>>> commit message to prevent confusion.
>>>
>>> Ok I take that back, you were talking about guarding this feature by
>>> the SD_ASYM_CPUCAPACITY flag.
>>>
>>> I don't think that protection would be helpful because you can have
>>> the same issue if the tasks do different amount of work on SMP. So in
>>> that case some threads might still complete before the others and you
>>> run into the same thing.
>>
>> Well assuming we're still talking about one task per CPU, if you have
>> tasks doing different amount of work there's still no reason to move the
>> longer-running threads around. The only reason that happens in my
>> example is because of the asym capacity.
>
> Yes but you can very well have RT pressure and things that temporarily
> change the capacity equality. Also this is a simple benchmark and for
> any reason you have more than 1 task running on those other CPUs and
> then the idle CPUs run some of the tasks and you run into a similar
> situation that might need your patch..
>
The patch would be helpful only if it doesn't cross NUMA boundary. right ?
If NUMA comes into picture, not sure searching across NUMA may hurt more
than help, especially in this case.
> Also one more note, the SD_ASYM_CPUCAPACITY protection is still not
> needed because SD_BALANCE_WAKE isn't turned on for
> !SD_ASYM_CPUCAPACITY from what I learnt from discussions with Mike, I
> believe its this piece of code in sd_init that actually enables it:
>
> if (sd->flags & SD_ASYM_CPUCAPACITY) {
> struct sched_domain *t = sd;
>
> for_each_lower_domain(t)
> t->flags |= SD_BALANCE_WAKE;
> }
>
>
But it will always try to search within LLC group if want_affine is set
irrespective of the SD_BALANCE_WAKE flag.
if (affine_sd) {
sd = NULL; /* Prefer wake_affine over balance flags */
if (cpu == prev_cpu)
goto pick_cpu;
if (wake_affine(affine_sd, p, prev_cpu, sync))
new_cpu = cpu;
}
if (!sd) {
pick_cpu:
if (sd_flag & SD_BALANCE_WAKE) /* XXX always ? */
new_cpu = select_idle_sibling(p, prev_cpu, new_cpu);
SD_ASYM_CPUCAPACITY protection may still be required if it is a
non-issue for big SMP servers.
Regards,
Atish
> thanks,
>
> - Joel
>
[toc] | [prev] | [next] | [standalone]
| From | Joel Fernandes <joelaf@google.com> |
|---|---|
| Date | 2017-09-21 08:00 +0200 |
| Message-ID | <us2GK-59P-7@gated-at.bofh.it> |
| In reply to | #1736155 |
On Wed, Sep 20, 2017 at 2:17 PM, Atish Patra <atish.patra@oracle.com> wrote:
> On 09/20/2017 03:23 PM, Joel Fernandes wrote:
>>
>> On Wed, Sep 20, 2017 at 2:33 AM, Brendan Jackman
>> <brendan.jackman@arm.com> wrote:
>>>
>>>
>>> On Wed, Sep 20 2017 at 05:06, Joel Fernandes wrote:
>>>>>
>>>>> On Tue, Sep 19, 2017 at 3:05 AM, Brendan Jackman
>>>>> <brendan.jackman@arm.com> wrote:
>>>>>>
>>>>>> On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
>>>>
>>>> [..]
>>>>>>>>
>>>>>>>> IIUC, if wake_affine() behaves correctly this trick wouldn't be
>>>>>>>> necessary on SMP systems, so it might be best guarded by the
>>>>>>>> presence
>>>>>>>
>>>>>>>
>>>>>>> Actually wake_affine doesn't check for balance if previous/next cpu
>>>>>>> are within the same shared cache domain. The difference is some time
>>>>>>> ago it would return true for shared cache but now it returns false
as
>>>>>>> of 4.14-rc1:
>>>>>>>
>>>>>>>
http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>>>>>>>
>>>>>>> Since it would return false in the above wake up cases for task 1
and
>>>>>>> 2, it would then run select_idle_sibling on the previous CPU which
is
>>>>>>> also within the big cluster, so I don't think it will make a
>>>>>>> difference in this case... Infact what it returns probably doesn't
>>>>>>> matter.
>>>>>>
>>>>>>
>>>>>> So my paragraph here was making a leap in reasoning, let me try to
>>>>>> fill
>>>>>> the gap: On SMP these tasks never need to move around. If by some
>>>>>> chance
>>>>>> they did get coscheduled, the first load balance would spread them
out
>>>>>> and
>>>>>> then every time they wake up from then on, prev_cpu is the sensible
>>>>>> choice. So it will look something like:
>>>>>>
>>>>>> v CPU v ->time->
>>>>>>
>>>>>> -------------
>>>>>> { 0 (SAME) 11111111111
>>>>>> cache { -------------
>>>>>> { 1 (SAME) 222222222222|
>>>>>> -------------
>>>>>> { 2 (SAME) 33333333333
>>>>>> cache { -------------
>>>>>> { 3 (SAME) 44444444444
>>>>>> -------------
>>>>>>
>>>>>> So here, task 2 wakes up the other guys and when it's doing tasks 3
>>>>>> and
>>>>>> 4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
>>>>>> basically wake_affine's job to decide between prev_cpu and
>>>>>> smp_processor_id(). So "if wake_affine is behaving correctly" the
>>>>>> problem that this patch aims to solve (i.e. the fact that we overload
>>>>>> the waker's LLC domain because of bias towards prev_cpu) does not
>>>>>> arise
>>>>>> on SMP.
>>>>>>
>>>>>
>>>>> Yes SMP, but your patch is for solving a problem for non-SMP. So your
>>>>> original statement about wake_affine solving any problem for SMP is
>>>>> not relevant I feel :-P. I guess you can just kill this para from the
>>>>> commit message to prevent confusion.
>>>>
>>>>
>>>> Ok I take that back, you were talking about guarding this feature by
>>>> the SD_ASYM_CPUCAPACITY flag.
>>>>
>>>> I don't think that protection would be helpful because you can have
>>>> the same issue if the tasks do different amount of work on SMP. So in
>>>> that case some threads might still complete before the others and you
>>>> run into the same thing.
>>>
>>>
>>> Well assuming we're still talking about one task per CPU, if you have
>>> tasks doing different amount of work there's still no reason to move the
>>> longer-running threads around. The only reason that happens in my
>>> example is because of the asym capacity.
>>
>>
>> Yes but you can very well have RT pressure and things that temporarily
>> change the capacity equality. Also this is a simple benchmark and for
>> any reason you have more than 1 task running on those other CPUs and
>> then the idle CPUs run some of the tasks and you run into a similar
>> situation that might need your patch..
>>
> The patch would be helpful only if it doesn't cross NUMA boundary. right ?
>
> If NUMA comes into picture, not sure searching across NUMA may hurt more
> than help, especially in this case.
I don't understand what you mean by "searching across NUMA", :-(, do you
mean the slow path?
As I said, if the SD_BALANCE_WAKE flag for the sched domain flag is not
set, then a full wide search isn't done anyway. You have this code that
sets the sd variable:
if (tmp->flags & sd_flag)
sd = tmp;
Since sd = NULL if the sched domain (tmp->flags) isn't set, you will
always have select_idle_sibling running and not doing the full search
if I understand correctly.
Further adding the ASYM protection isn't sensible if capacities are
affected by RT and IRQ time etc anyway. Does that make sense?
I am glad I understand the code a bit better now after staring at it
for quite some time but I think some more staring is needed.
- Joel
[toc] | [prev] | [next] | [standalone]
| From | Atish Patra <atish.patra@oracle.com> |
|---|---|
| Date | 2017-09-21 19:00 +0200 |
| Message-ID | <uscZs-3vW-29@gated-at.bofh.it> |
| In reply to | #1736371 |
On 09/21/2017 12:50 AM, Joel Fernandes wrote:
> On Wed, Sep 20, 2017 at 2:17 PM, Atish Patra <atish.patra@oracle.com> wrote:
>> On 09/20/2017 03:23 PM, Joel Fernandes wrote:
>>>
>>> On Wed, Sep 20, 2017 at 2:33 AM, Brendan Jackman
>>> <brendan.jackman@arm.com> wrote:
>>>>
>>>>
>>>> On Wed, Sep 20 2017 at 05:06, Joel Fernandes wrote:
>>>>>>
>>>>>> On Tue, Sep 19, 2017 at 3:05 AM, Brendan Jackman
>>>>>> <brendan.jackman@arm.com> wrote:
>>>>>>>
>>>>>>> On Mon, Sep 18 2017 at 22:15, Joel Fernandes wrote:
>>>>>
>>>>> [..]
>>>>>>>>>
>>>>>>>>> IIUC, if wake_affine() behaves correctly this trick wouldn't be
>>>>>>>>> necessary on SMP systems, so it might be best guarded by the
>>>>>>>>> presence
>>>>>>>>
>>>>>>>>
>>>>>>>> Actually wake_affine doesn't check for balance if previous/next cpu
>>>>>>>> are within the same shared cache domain. The difference is some time
>>>>>>>> ago it would return true for shared cache but now it returns false
> as
>>>>>>>> of 4.14-rc1:
>>>>>>>>
>>>>>>>>
> http://elixir.free-electrons.com/linux/v4.14-rc1/source/kernel/sched/fair.c#L5466
>>>>>>>>
>>>>>>>> Since it would return false in the above wake up cases for task 1
> and
>>>>>>>> 2, it would then run select_idle_sibling on the previous CPU which
> is
>>>>>>>> also within the big cluster, so I don't think it will make a
>>>>>>>> difference in this case... Infact what it returns probably doesn't
>>>>>>>> matter.
>>>>>>>
>>>>>>>
>>>>>>> So my paragraph here was making a leap in reasoning, let me try to
>>>>>>> fill
>>>>>>> the gap: On SMP these tasks never need to move around. If by some
>>>>>>> chance
>>>>>>> they did get coscheduled, the first load balance would spread them
> out
>>>>>>> and
>>>>>>> then every time they wake up from then on, prev_cpu is the sensible
>>>>>>> choice. So it will look something like:
>>>>>>>
>>>>>>> v CPU v ->time->
>>>>>>>
>>>>>>> -------------
>>>>>>> { 0 (SAME) 11111111111
>>>>>>> cache { -------------
>>>>>>> { 1 (SAME) 222222222222|
>>>>>>> -------------
>>>>>>> { 2 (SAME) 33333333333
>>>>>>> cache { -------------
>>>>>>> { 3 (SAME) 44444444444
>>>>>>> -------------
>>>>>>>
>>>>>>> So here, task 2 wakes up the other guys and when it's doing tasks 3
>>>>>>> and
>>>>>>> 4, prev_cpu and smp_processor_id() don't share a cache, so IIUC its'
>>>>>>> basically wake_affine's job to decide between prev_cpu and
>>>>>>> smp_processor_id(). So "if wake_affine is behaving correctly" the
>>>>>>> problem that this patch aims to solve (i.e. the fact that we overload
>>>>>>> the waker's LLC domain because of bias towards prev_cpu) does not
>>>>>>> arise
>>>>>>> on SMP.
>>>>>>>
>>>>>>
>>>>>> Yes SMP, but your patch is for solving a problem for non-SMP. So your
>>>>>> original statement about wake_affine solving any problem for SMP is
>>>>>> not relevant I feel :-P. I guess you can just kill this para from the
>>>>>> commit message to prevent confusion.
>>>>>
>>>>>
>>>>> Ok I take that back, you were talking about guarding this feature by
>>>>> the SD_ASYM_CPUCAPACITY flag.
>>>>>
>>>>> I don't think that protection would be helpful because you can have
>>>>> the same issue if the tasks do different amount of work on SMP. So in
>>>>> that case some threads might still complete before the others and you
>>>>> run into the same thing.
>>>>
>>>>
>>>> Well assuming we're still talking about one task per CPU, if you have
>>>> tasks doing different amount of work there's still no reason to move the
>>>> longer-running threads around. The only reason that happens in my
>>>> example is because of the asym capacity.
>>>
>>>
>>> Yes but you can very well have RT pressure and things that temporarily
>>> change the capacity equality. Also this is a simple benchmark and for
>>> any reason you have more than 1 task running on those other CPUs and
>>> then the idle CPUs run some of the tasks and you run into a similar
>>> situation that might need your patch..
>>>
>> The patch would be helpful only if it doesn't cross NUMA boundary. right ?
>>
>> If NUMA comes into picture, not sure searching across NUMA may hurt more
>> than help, especially in this case.
>
> I don't understand what you mean by "searching across NUMA", :-(, do you
> mean the slow path?
>
> As I said, if the SD_BALANCE_WAKE flag for the sched domain flag is not
> set, then a full wide search isn't done anyway. You have this code that
> sets the sd variable:
>
> if (tmp->flags & sd_flag)
> sd = tmp;
>
> Since sd = NULL if the sched domain (tmp->flags) isn't set, you will
> always have select_idle_sibling running and not doing the full search
> if I understand correctly.
>
Correct. I was under the impression that the above logic is going
to changed to fix the possible issue raised by Brendan for big SMP
server as well. I guess that was not the case.
> Further adding the ASYM protection isn't sensible if capacities are
> affected by RT and IRQ time etc anyway. Does that make sense?
>
Yup. We won't need ASYM protection.
Regards,
Atish
> I am glad I understand the code a bit better now after staring at it
> for quite some time but I think some more staring is needed.
>
> - Joel
>
[toc] | [prev] | [next] | [standalone]
| From | Brendan Jackman <brendan.jackman@arm.com> |
|---|---|
| Date | 2017-09-20 11:50 +0200 |
| Message-ID | <urJNN-1dj-33@gated-at.bofh.it> |
| In reply to | #1734657 |
Hi Joel,
Sorry I didn't see your comments on the code before, I think it's
orthoganal to the other thread about the overall design so I'll just
respond here.
On Tue, Sep 19 2017 at 05:15, Joel Fernandes wrote:
> Hi Brendan,
>
> On Fri, Aug 11, 2017 at 2:45 AM, Brendan Jackman
[snip]
>>
>> 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;
>> };
>>
>> #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);
>
> Shouldn't you reset head->count after all the tasks have been woken up?
That's done in wake_q_init, which should be enough as you only use a
wake_q once per init [1]
[1] http://elixir.free-electrons.com/linux/latest/source/include/linux/sched/wake_q.h#L33
>
>> }
>> }
>> @@ -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)
>
> This variable seems a bit long to me, how about just sibling_count?
Yeah, shortening sounds good. Coming back with fresh eyes I think
'sibling' is a bad description, I was thinking of siblings in the
waker/wakee graph of tasks actually but I don't think that's obvious at
all. This is just an RFC so if it ever makes it to PATCH I'll try and
think of something better.
>> {
>> 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);
>
> same.
>
> <snip>
>
>>
>> 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);
>
> s/subling/sibling/
Yup :|
Thanks,
Brendan
[toc] | [prev] | [standalone]
Back to top | Article view | linux.kernel
csiph-web