[v4,11/11] sched/fair: rework find_idlest_group
diff mbox series

Message ID 1571405198-27570-12-git-send-email-vincent.guittot@linaro.org
State New, archived
Headers show
Series
  • sched/fair: rework the CFS load balance
Related show

Commit Message

Vincent Guittot Oct. 18, 2019, 1:26 p.m. UTC
The slow wake up path computes per sched_group statisics to select the
idlest group, which is quite similar to what load_balance() is doing
for selecting busiest group. Rework find_idlest_group() to classify the
sched_group and select the idlest one following the same steps as
load_balance().

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 384 ++++++++++++++++++++++++++++++++++------------------
 1 file changed, 256 insertions(+), 128 deletions(-)

Comments

Qais Yousef Nov. 20, 2019, 11:58 a.m. UTC | #1
Hi Vincent

On 10/18/19 15:26, Vincent Guittot wrote:
> The slow wake up path computes per sched_group statisics to select the
> idlest group, which is quite similar to what load_balance() is doing
> for selecting busiest group. Rework find_idlest_group() to classify the
> sched_group and select the idlest one following the same steps as
> load_balance().
> 
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---

LTP test has caught a regression in perf_event_open02 test on linux-next and I
bisected it to this patch.

That is checking out next-20191119 tag and reverting this patch on top the test
passes. Without the revert the test fails.

I think this patch disturbs this part of the test:

	https://github.com/linux-test-project/ltp/blob/master/testcases/kernel/syscalls/perf_event_open/perf_event_open02.c#L209

When I revert this patch count_hardware_counters() returns a non zero value.
But with it applied it returns 0 which indicates that the condition terminates
earlier than what the test expects.

I'm failing to see the connection yet, but since I spent enough time bisecting
it I thought I'll throw this out before I continue to bottom it out in hope it
rings a bell for you or someone else.

The problem was consistently reproducible on Juno-r2.

LTP was compiled from 20190930 tag using

	./configure --host=aarch64-linux-gnu --prefix=~/arm64-ltp/
	make && make install



*** Output of the test when it fails ***

	# ./perf_event_open02 -v
	at iteration:0 value:254410384 time_enabled:195570320 time_running:156044100
	perf_event_open02    0  TINFO  :  overall task clock: 166935520
	perf_event_open02    0  TINFO  :  hw sum: 1200812256, task clock sum: 667703360
	hw counters: 300202518 300202881 300203246 300203611
	task clock counters: 166927400 166926780 166925660 166923520
	perf_event_open02    0  TINFO  :  ratio: 3.999768
	perf_event_open02    0  TINFO  :  nhw: 0.000100     /* I added this extra line for debug */
	perf_event_open02    1  TFAIL  :  perf_event_open02.c:370: test failed (ratio was greater than )



*** Output of the test when it passes (this patch reverted) ***

	# ./perf_event_open02 -v
	at iteration:0 value:300271482 time_enabled:177756080 time_running:177756080
	at iteration:1 value:300252655 time_enabled:166939100 time_running:166939100
	at iteration:2 value:300252877 time_enabled:166924920 time_running:166924920
	at iteration:3 value:300242545 time_enabled:166909620 time_running:166909620
	at iteration:4 value:300250779 time_enabled:166918540 time_running:166918540
	at iteration:5 value:300250660 time_enabled:166922180 time_running:166922180
	at iteration:6 value:258369655 time_enabled:167388920 time_running:143996600
	perf_event_open02    0  TINFO  :  overall task clock: 167540640
	perf_event_open02    0  TINFO  :  hw sum: 1801473873, task clock sum: 1005046160
	hw counters: 177971955 185132938 185488818 185488199 185480943 185477118 179657001 172499668 172137672 172139561
	task clock counters: 99299900 103293440 103503840 103502040 103499020 103496160 100224320 96227620 95999400 96000420
	perf_event_open02    0  TINFO  :  ratio: 5.998820
	perf_event_open02    0  TINFO  :  nhw: 6.000100     /* I added this extra line for debug */
	perf_event_open02    1  TPASS  :  test passed

Thanks

--
Qais Yousef
Vincent Guittot Nov. 20, 2019, 1:21 p.m. UTC | #2
Hi Qais,

On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
>
> Hi Vincent
>
> On 10/18/19 15:26, Vincent Guittot wrote:
> > The slow wake up path computes per sched_group statisics to select the
> > idlest group, which is quite similar to what load_balance() is doing
> > for selecting busiest group. Rework find_idlest_group() to classify the
> > sched_group and select the idlest one following the same steps as
> > load_balance().
> >
> > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > ---
>
> LTP test has caught a regression in perf_event_open02 test on linux-next and I
> bisected it to this patch.
>
> That is checking out next-20191119 tag and reverting this patch on top the test
> passes. Without the revert the test fails.
>
> I think this patch disturbs this part of the test:
>
>         https://github.com/linux-test-project/ltp/blob/master/testcases/kernel/syscalls/perf_event_open/perf_event_open02.c#L209
>
> When I revert this patch count_hardware_counters() returns a non zero value.
> But with it applied it returns 0 which indicates that the condition terminates
> earlier than what the test expects.

Thanks for the report and starting analysing it

>
> I'm failing to see the connection yet, but since I spent enough time bisecting
> it I thought I'll throw this out before I continue to bottom it out in hope it
> rings a bell for you or someone else.

I will try to reproduce the problem and understand why it's failing
because i don't have any clue of the relation between both for now

>
> The problem was consistently reproducible on Juno-r2.
>
> LTP was compiled from 20190930 tag using
>
>         ./configure --host=aarch64-linux-gnu --prefix=~/arm64-ltp/
>         make && make install
>
>
>
> *** Output of the test when it fails ***
>
>         # ./perf_event_open02 -v
>         at iteration:0 value:254410384 time_enabled:195570320 time_running:156044100
>         perf_event_open02    0  TINFO  :  overall task clock: 166935520
>         perf_event_open02    0  TINFO  :  hw sum: 1200812256, task clock sum: 667703360
>         hw counters: 300202518 300202881 300203246 300203611
>         task clock counters: 166927400 166926780 166925660 166923520
>         perf_event_open02    0  TINFO  :  ratio: 3.999768
>         perf_event_open02    0  TINFO  :  nhw: 0.000100     /* I added this extra line for debug */
>         perf_event_open02    1  TFAIL  :  perf_event_open02.c:370: test failed (ratio was greater than )
>
>
>
> *** Output of the test when it passes (this patch reverted) ***
>
>         # ./perf_event_open02 -v
>         at iteration:0 value:300271482 time_enabled:177756080 time_running:177756080
>         at iteration:1 value:300252655 time_enabled:166939100 time_running:166939100
>         at iteration:2 value:300252877 time_enabled:166924920 time_running:166924920
>         at iteration:3 value:300242545 time_enabled:166909620 time_running:166909620
>         at iteration:4 value:300250779 time_enabled:166918540 time_running:166918540
>         at iteration:5 value:300250660 time_enabled:166922180 time_running:166922180
>         at iteration:6 value:258369655 time_enabled:167388920 time_running:143996600
>         perf_event_open02    0  TINFO  :  overall task clock: 167540640
>         perf_event_open02    0  TINFO  :  hw sum: 1801473873, task clock sum: 1005046160
>         hw counters: 177971955 185132938 185488818 185488199 185480943 185477118 179657001 172499668 172137672 172139561
>         task clock counters: 99299900 103293440 103503840 103502040 103499020 103496160 100224320 96227620 95999400 96000420
>         perf_event_open02    0  TINFO  :  ratio: 5.998820
>         perf_event_open02    0  TINFO  :  nhw: 6.000100     /* I added this extra line for debug */
>         perf_event_open02    1  TPASS  :  test passed
>
> Thanks
>
> --
> Qais Yousef
Vincent Guittot Nov. 20, 2019, 4:53 p.m. UTC | #3
On Wed, 20 Nov 2019 at 14:21, Vincent Guittot
<vincent.guittot@linaro.org> wrote:
>
> Hi Qais,
>
> On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
> >
> > Hi Vincent
> >
> > On 10/18/19 15:26, Vincent Guittot wrote:
> > > The slow wake up path computes per sched_group statisics to select the
> > > idlest group, which is quite similar to what load_balance() is doing
> > > for selecting busiest group. Rework find_idlest_group() to classify the
> > > sched_group and select the idlest one following the same steps as
> > > load_balance().
> > >
> > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > ---
> >
> > LTP test has caught a regression in perf_event_open02 test on linux-next and I
> > bisected it to this patch.
> >
> > That is checking out next-20191119 tag and reverting this patch on top the test
> > passes. Without the revert the test fails.

I haven't tried linux-next yet but LTP test is passed with
tip/sched/core, which includes this patch, on hikey960 which is arm64
too.

Have you tried tip/sched/core on your juno ? this could help to
understand if it's only for juno or if this patch interact with
another branch merged in linux next

Thanks
Vincent

> >
> > I think this patch disturbs this part of the test:
> >
> >         https://github.com/linux-test-project/ltp/blob/master/testcases/kernel/syscalls/perf_event_open/perf_event_open02.c#L209
> >
> > When I revert this patch count_hardware_counters() returns a non zero value.
> > But with it applied it returns 0 which indicates that the condition terminates
> > earlier than what the test expects.
>
> Thanks for the report and starting analysing it
>
> >
> > I'm failing to see the connection yet, but since I spent enough time bisecting
> > it I thought I'll throw this out before I continue to bottom it out in hope it
> > rings a bell for you or someone else.
>
> I will try to reproduce the problem and understand why it's failing
> because i don't have any clue of the relation between both for now
>
> >
> > The problem was consistently reproducible on Juno-r2.
> >
> > LTP was compiled from 20190930 tag using
> >
> >         ./configure --host=aarch64-linux-gnu --prefix=~/arm64-ltp/
> >         make && make install
> >
> >
> >
> > *** Output of the test when it fails ***
> >
> >         # ./perf_event_open02 -v
> >         at iteration:0 value:254410384 time_enabled:195570320 time_running:156044100
> >         perf_event_open02    0  TINFO  :  overall task clock: 166935520
> >         perf_event_open02    0  TINFO  :  hw sum: 1200812256, task clock sum: 667703360
> >         hw counters: 300202518 300202881 300203246 300203611
> >         task clock counters: 166927400 166926780 166925660 166923520
> >         perf_event_open02    0  TINFO  :  ratio: 3.999768
> >         perf_event_open02    0  TINFO  :  nhw: 0.000100     /* I added this extra line for debug */
> >         perf_event_open02    1  TFAIL  :  perf_event_open02.c:370: test failed (ratio was greater than )
> >
> >
> >
> > *** Output of the test when it passes (this patch reverted) ***
> >
> >         # ./perf_event_open02 -v
> >         at iteration:0 value:300271482 time_enabled:177756080 time_running:177756080
> >         at iteration:1 value:300252655 time_enabled:166939100 time_running:166939100
> >         at iteration:2 value:300252877 time_enabled:166924920 time_running:166924920
> >         at iteration:3 value:300242545 time_enabled:166909620 time_running:166909620
> >         at iteration:4 value:300250779 time_enabled:166918540 time_running:166918540
> >         at iteration:5 value:300250660 time_enabled:166922180 time_running:166922180
> >         at iteration:6 value:258369655 time_enabled:167388920 time_running:143996600
> >         perf_event_open02    0  TINFO  :  overall task clock: 167540640
> >         perf_event_open02    0  TINFO  :  hw sum: 1801473873, task clock sum: 1005046160
> >         hw counters: 177971955 185132938 185488818 185488199 185480943 185477118 179657001 172499668 172137672 172139561
> >         task clock counters: 99299900 103293440 103503840 103502040 103499020 103496160 100224320 96227620 95999400 96000420
> >         perf_event_open02    0  TINFO  :  ratio: 5.998820
> >         perf_event_open02    0  TINFO  :  nhw: 6.000100     /* I added this extra line for debug */
> >         perf_event_open02    1  TPASS  :  test passed
> >
> > Thanks
> >
> > --
> > Qais Yousef
Qais Yousef Nov. 20, 2019, 5:34 p.m. UTC | #4
On 11/20/19 17:53, Vincent Guittot wrote:
> On Wed, 20 Nov 2019 at 14:21, Vincent Guittot
> <vincent.guittot@linaro.org> wrote:
> >
> > Hi Qais,
> >
> > On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
> > >
> > > Hi Vincent
> > >
> > > On 10/18/19 15:26, Vincent Guittot wrote:
> > > > The slow wake up path computes per sched_group statisics to select the
> > > > idlest group, which is quite similar to what load_balance() is doing
> > > > for selecting busiest group. Rework find_idlest_group() to classify the
> > > > sched_group and select the idlest one following the same steps as
> > > > load_balance().
> > > >
> > > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > > ---
> > >
> > > LTP test has caught a regression in perf_event_open02 test on linux-next and I
> > > bisected it to this patch.
> > >
> > > That is checking out next-20191119 tag and reverting this patch on top the test
> > > passes. Without the revert the test fails.
> 
> I haven't tried linux-next yet but LTP test is passed with
> tip/sched/core, which includes this patch, on hikey960 which is arm64
> too.
> 
> Have you tried tip/sched/core on your juno ? this could help to
> understand if it's only for juno or if this patch interact with
> another branch merged in linux next

Okay will give it a go. But out of curiosity, what is the output of your run?

While bisecting on linux-next I noticed that at some point the test was
passing but all the read values were 0. At some point I started seeing
none-zero values.

--
Qais Yousef
Vincent Guittot Nov. 20, 2019, 5:43 p.m. UTC | #5
On Wed, 20 Nov 2019 at 18:34, Qais Yousef <qais.yousef@arm.com> wrote:
>
> On 11/20/19 17:53, Vincent Guittot wrote:
> > On Wed, 20 Nov 2019 at 14:21, Vincent Guittot
> > <vincent.guittot@linaro.org> wrote:
> > >
> > > Hi Qais,
> > >
> > > On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
> > > >
> > > > Hi Vincent
> > > >
> > > > On 10/18/19 15:26, Vincent Guittot wrote:
> > > > > The slow wake up path computes per sched_group statisics to select the
> > > > > idlest group, which is quite similar to what load_balance() is doing
> > > > > for selecting busiest group. Rework find_idlest_group() to classify the
> > > > > sched_group and select the idlest one following the same steps as
> > > > > load_balance().
> > > > >
> > > > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > > > ---
> > > >
> > > > LTP test has caught a regression in perf_event_open02 test on linux-next and I
> > > > bisected it to this patch.
> > > >
> > > > That is checking out next-20191119 tag and reverting this patch on top the test
> > > > passes. Without the revert the test fails.
> >
> > I haven't tried linux-next yet but LTP test is passed with
> > tip/sched/core, which includes this patch, on hikey960 which is arm64
> > too.
> >
> > Have you tried tip/sched/core on your juno ? this could help to
> > understand if it's only for juno or if this patch interact with
> > another branch merged in linux next
>
> Okay will give it a go. But out of curiosity, what is the output of your run?
>
> While bisecting on linux-next I noticed that at some point the test was
> passing but all the read values were 0. At some point I started seeing
> none-zero values.

for tip/sched/core
linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
sudo ./perf_event_open02
perf_event_open02    0  TINFO  :  overall task clock: 63724479
perf_event_open02    0  TINFO  :  hw sum: 1800900992, task clock sum: 382170311
perf_event_open02    0  TINFO  :  ratio: 5.997229
perf_event_open02    1  TPASS  :  test passed

for next-2019119
~/ltp/testcases/kernel/syscalls/perf_event_open$ sudo ./perf_event_open02 -v
at iteration:0 value:0 time_enabled:69795312 time_running:0
perf_event_open02    0  TINFO  :  overall task clock: 63582292
perf_event_open02    0  TINFO  :  hw sum: 0, task clock sum: 0
hw counters: 0 0 0 0
task clock counters: 0 0 0 0
perf_event_open02    0  TINFO  :  ratio: 0.000000
perf_event_open02    1  TPASS  :  test passed

>
> --
> Qais Yousef
Qais Yousef Nov. 20, 2019, 6:10 p.m. UTC | #6
On 11/20/19 18:43, Vincent Guittot wrote:
> On Wed, 20 Nov 2019 at 18:34, Qais Yousef <qais.yousef@arm.com> wrote:
> >
> > On 11/20/19 17:53, Vincent Guittot wrote:
> > > On Wed, 20 Nov 2019 at 14:21, Vincent Guittot
> > > <vincent.guittot@linaro.org> wrote:
> > > >
> > > > Hi Qais,
> > > >
> > > > On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
> > > > >
> > > > > Hi Vincent
> > > > >
> > > > > On 10/18/19 15:26, Vincent Guittot wrote:
> > > > > > The slow wake up path computes per sched_group statisics to select the
> > > > > > idlest group, which is quite similar to what load_balance() is doing
> > > > > > for selecting busiest group. Rework find_idlest_group() to classify the
> > > > > > sched_group and select the idlest one following the same steps as
> > > > > > load_balance().
> > > > > >
> > > > > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > > > > ---
> > > > >
> > > > > LTP test has caught a regression in perf_event_open02 test on linux-next and I
> > > > > bisected it to this patch.
> > > > >
> > > > > That is checking out next-20191119 tag and reverting this patch on top the test
> > > > > passes. Without the revert the test fails.
> > >
> > > I haven't tried linux-next yet but LTP test is passed with
> > > tip/sched/core, which includes this patch, on hikey960 which is arm64
> > > too.
> > >
> > > Have you tried tip/sched/core on your juno ? this could help to
> > > understand if it's only for juno or if this patch interact with
> > > another branch merged in linux next
> >
> > Okay will give it a go. But out of curiosity, what is the output of your run?
> >
> > While bisecting on linux-next I noticed that at some point the test was
> > passing but all the read values were 0. At some point I started seeing
> > none-zero values.
> 
> for tip/sched/core
> linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
> sudo ./perf_event_open02
> perf_event_open02    0  TINFO  :  overall task clock: 63724479
> perf_event_open02    0  TINFO  :  hw sum: 1800900992, task clock sum: 382170311
> perf_event_open02    0  TINFO  :  ratio: 5.997229
> perf_event_open02    1  TPASS  :  test passed
> 
> for next-2019119
> ~/ltp/testcases/kernel/syscalls/perf_event_open$ sudo ./perf_event_open02 -v
> at iteration:0 value:0 time_enabled:69795312 time_running:0
> perf_event_open02    0  TINFO  :  overall task clock: 63582292
> perf_event_open02    0  TINFO  :  hw sum: 0, task clock sum: 0
> hw counters: 0 0 0 0
> task clock counters: 0 0 0 0
> perf_event_open02    0  TINFO  :  ratio: 0.000000
> perf_event_open02    1  TPASS  :  test passed

Okay that is weird. But ratio, hw sum, task clock sum are all 0 in your
next-20191119. I'm not sure why the counters return 0 sometimes - is it
dependent on some option or a bug somewhere.

I just did another run and it failed for me (building with defconfig)

# uname -a
Linux buildroot 5.4.0-rc8-next-20191119 #72 SMP PREEMPT Wed Nov 20 17:57:48 GMT 2019 aarch64 GNU/Linux

# ./perf_event_open02 -v
at iteration:0 value:260700250 time_enabled:172739760 time_running:144956600
perf_event_open02    0  TINFO  :  overall task clock: 166915220
perf_event_open02    0  TINFO  :  hw sum: 1200718268, task clock sum: 667621320
hw counters: 300179051 300179395 300179739 300180083
task clock counters: 166906620 166906200 166905160 166903340
perf_event_open02    0  TINFO  :  ratio: 3.999763
perf_event_open02    0  TINFO  :  nhw: 0.000100
perf_event_open02    1  TFAIL  :  perf_event_open02.c:370: test failed (ratio was greater than )

It is a funny one for sure. I haven't tried tip/sched/core yet.

Thanks

--
Qais Yousef
Vincent Guittot Nov. 20, 2019, 6:20 p.m. UTC | #7
On Wed, 20 Nov 2019 at 19:10, Qais Yousef <qais.yousef@arm.com> wrote:
>
> On 11/20/19 18:43, Vincent Guittot wrote:
> > On Wed, 20 Nov 2019 at 18:34, Qais Yousef <qais.yousef@arm.com> wrote:
> > >
> > > On 11/20/19 17:53, Vincent Guittot wrote:
> > > > On Wed, 20 Nov 2019 at 14:21, Vincent Guittot
> > > > <vincent.guittot@linaro.org> wrote:
> > > > >
> > > > > Hi Qais,
> > > > >
> > > > > On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
> > > > > >
> > > > > > Hi Vincent
> > > > > >
> > > > > > On 10/18/19 15:26, Vincent Guittot wrote:
> > > > > > > The slow wake up path computes per sched_group statisics to select the
> > > > > > > idlest group, which is quite similar to what load_balance() is doing
> > > > > > > for selecting busiest group. Rework find_idlest_group() to classify the
> > > > > > > sched_group and select the idlest one following the same steps as
> > > > > > > load_balance().
> > > > > > >
> > > > > > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > > > > > ---
> > > > > >
> > > > > > LTP test has caught a regression in perf_event_open02 test on linux-next and I
> > > > > > bisected it to this patch.
> > > > > >
> > > > > > That is checking out next-20191119 tag and reverting this patch on top the test
> > > > > > passes. Without the revert the test fails.
> > > >
> > > > I haven't tried linux-next yet but LTP test is passed with
> > > > tip/sched/core, which includes this patch, on hikey960 which is arm64
> > > > too.
> > > >
> > > > Have you tried tip/sched/core on your juno ? this could help to
> > > > understand if it's only for juno or if this patch interact with
> > > > another branch merged in linux next
> > >
> > > Okay will give it a go. But out of curiosity, what is the output of your run?
> > >
> > > While bisecting on linux-next I noticed that at some point the test was
> > > passing but all the read values were 0. At some point I started seeing
> > > none-zero values.
> >
> > for tip/sched/core
> > linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
> > sudo ./perf_event_open02
> > perf_event_open02    0  TINFO  :  overall task clock: 63724479
> > perf_event_open02    0  TINFO  :  hw sum: 1800900992, task clock sum: 382170311
> > perf_event_open02    0  TINFO  :  ratio: 5.997229
> > perf_event_open02    1  TPASS  :  test passed
> >
> > for next-2019119
> > ~/ltp/testcases/kernel/syscalls/perf_event_open$ sudo ./perf_event_open02 -v
> > at iteration:0 value:0 time_enabled:69795312 time_running:0
> > perf_event_open02    0  TINFO  :  overall task clock: 63582292
> > perf_event_open02    0  TINFO  :  hw sum: 0, task clock sum: 0
> > hw counters: 0 0 0 0
> > task clock counters: 0 0 0 0
> > perf_event_open02    0  TINFO  :  ratio: 0.000000
> > perf_event_open02    1  TPASS  :  test passed
>
> Okay that is weird. But ratio, hw sum, task clock sum are all 0 in your
> next-20191119. I'm not sure why the counters return 0 sometimes - is it
> dependent on some option or a bug somewhere.
>
> I just did another run and it failed for me (building with defconfig)
>
> # uname -a
> Linux buildroot 5.4.0-rc8-next-20191119 #72 SMP PREEMPT Wed Nov 20 17:57:48 GMT 2019 aarch64 GNU/Linux
>
> # ./perf_event_open02 -v
> at iteration:0 value:260700250 time_enabled:172739760 time_running:144956600
> perf_event_open02    0  TINFO  :  overall task clock: 166915220
> perf_event_open02    0  TINFO  :  hw sum: 1200718268, task clock sum: 667621320
> hw counters: 300179051 300179395 300179739 300180083
> task clock counters: 166906620 166906200 166905160 166903340
> perf_event_open02    0  TINFO  :  ratio: 3.999763
> perf_event_open02    0  TINFO  :  nhw: 0.000100
> perf_event_open02    1  TFAIL  :  perf_event_open02.c:370: test failed (ratio was greater than )
>
> It is a funny one for sure. I haven't tried tip/sched/core yet.

I confirm that on next-20191119, hw counters always return 0
but on tip/sched/core which has this patch and v5.4-rc7 which has not,
the hw counters are always different from 0

on v5.4-rc7 i have got the same ratio :
linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
sudo ./perf_event_open02 -v
at iteration:0 value:300157088 time_enabled:80641145 time_running:80641145
at iteration:1 value:300100129 time_enabled:63572917 time_running:63572917
at iteration:2 value:300100885 time_enabled:63569271 time_running:63569271
at iteration:3 value:300103998 time_enabled:63573437 time_running:63573437
at iteration:4 value:300101477 time_enabled:63571875 time_running:63571875
at iteration:5 value:300100698 time_enabled:63569791 time_running:63569791
at iteration:6 value:245252526 time_enabled:63650520 time_running:52012500
perf_event_open02    0  TINFO  :  overall task clock: 63717187
perf_event_open02    0  TINFO  :  hw sum: 1800857435, task clock sum: 382156248
hw counters: 149326575 150152481 169006047 187845928 206684169
224693333 206543358 187716226 168865909 150023409
task clock counters: 31694792 31870834 35868749 39866666 43863541
47685936 43822396 39826042 35828125 31829167
perf_event_open02    0  TINFO  :  ratio: 5.997695
perf_event_open02    1  TPASS  :  test passed

Thanks

>
> Thanks
>
> --
> Qais Yousef
Qais Yousef Nov. 20, 2019, 6:27 p.m. UTC | #8
On 11/20/19 19:20, Vincent Guittot wrote:
> On Wed, 20 Nov 2019 at 19:10, Qais Yousef <qais.yousef@arm.com> wrote:
> >
> > On 11/20/19 18:43, Vincent Guittot wrote:
> > > On Wed, 20 Nov 2019 at 18:34, Qais Yousef <qais.yousef@arm.com> wrote:
> > > >
> > > > On 11/20/19 17:53, Vincent Guittot wrote:
> > > > > On Wed, 20 Nov 2019 at 14:21, Vincent Guittot
> > > > > <vincent.guittot@linaro.org> wrote:
> > > > > >
> > > > > > Hi Qais,
> > > > > >
> > > > > > On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
> > > > > > >
> > > > > > > Hi Vincent
> > > > > > >
> > > > > > > On 10/18/19 15:26, Vincent Guittot wrote:
> > > > > > > > The slow wake up path computes per sched_group statisics to select the
> > > > > > > > idlest group, which is quite similar to what load_balance() is doing
> > > > > > > > for selecting busiest group. Rework find_idlest_group() to classify the
> > > > > > > > sched_group and select the idlest one following the same steps as
> > > > > > > > load_balance().
> > > > > > > >
> > > > > > > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > > > > > > ---
> > > > > > >
> > > > > > > LTP test has caught a regression in perf_event_open02 test on linux-next and I
> > > > > > > bisected it to this patch.
> > > > > > >
> > > > > > > That is checking out next-20191119 tag and reverting this patch on top the test
> > > > > > > passes. Without the revert the test fails.
> > > > >
> > > > > I haven't tried linux-next yet but LTP test is passed with
> > > > > tip/sched/core, which includes this patch, on hikey960 which is arm64
> > > > > too.
> > > > >
> > > > > Have you tried tip/sched/core on your juno ? this could help to
> > > > > understand if it's only for juno or if this patch interact with
> > > > > another branch merged in linux next
> > > >
> > > > Okay will give it a go. But out of curiosity, what is the output of your run?
> > > >
> > > > While bisecting on linux-next I noticed that at some point the test was
> > > > passing but all the read values were 0. At some point I started seeing
> > > > none-zero values.
> > >
> > > for tip/sched/core
> > > linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
> > > sudo ./perf_event_open02
> > > perf_event_open02    0  TINFO  :  overall task clock: 63724479
> > > perf_event_open02    0  TINFO  :  hw sum: 1800900992, task clock sum: 382170311
> > > perf_event_open02    0  TINFO  :  ratio: 5.997229
> > > perf_event_open02    1  TPASS  :  test passed
> > >
> > > for next-2019119
> > > ~/ltp/testcases/kernel/syscalls/perf_event_open$ sudo ./perf_event_open02 -v
> > > at iteration:0 value:0 time_enabled:69795312 time_running:0
> > > perf_event_open02    0  TINFO  :  overall task clock: 63582292
> > > perf_event_open02    0  TINFO  :  hw sum: 0, task clock sum: 0
> > > hw counters: 0 0 0 0
> > > task clock counters: 0 0 0 0
> > > perf_event_open02    0  TINFO  :  ratio: 0.000000
> > > perf_event_open02    1  TPASS  :  test passed
> >
> > Okay that is weird. But ratio, hw sum, task clock sum are all 0 in your
> > next-20191119. I'm not sure why the counters return 0 sometimes - is it
> > dependent on some option or a bug somewhere.
> >
> > I just did another run and it failed for me (building with defconfig)
> >
> > # uname -a
> > Linux buildroot 5.4.0-rc8-next-20191119 #72 SMP PREEMPT Wed Nov 20 17:57:48 GMT 2019 aarch64 GNU/Linux
> >
> > # ./perf_event_open02 -v
> > at iteration:0 value:260700250 time_enabled:172739760 time_running:144956600
> > perf_event_open02    0  TINFO  :  overall task clock: 166915220
> > perf_event_open02    0  TINFO  :  hw sum: 1200718268, task clock sum: 667621320
> > hw counters: 300179051 300179395 300179739 300180083
> > task clock counters: 166906620 166906200 166905160 166903340
> > perf_event_open02    0  TINFO  :  ratio: 3.999763
> > perf_event_open02    0  TINFO  :  nhw: 0.000100
> > perf_event_open02    1  TFAIL  :  perf_event_open02.c:370: test failed (ratio was greater than )
> >
> > It is a funny one for sure. I haven't tried tip/sched/core yet.
> 
> I confirm that on next-20191119, hw counters always return 0
> but on tip/sched/core which has this patch and v5.4-rc7 which has not,
> the hw counters are always different from 0

It's the other way around for me. tip/sched/core returns 0 hw counters. I tried
enabling coresight; that had no effect. Nor copying the .config that failed
from linux-next to tip/sched/core. I'm not sure what's the dependency/breakage
:-/

--
Qais Yousef

> 
> on v5.4-rc7 i have got the same ratio :
> linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
> sudo ./perf_event_open02 -v
> at iteration:0 value:300157088 time_enabled:80641145 time_running:80641145
> at iteration:1 value:300100129 time_enabled:63572917 time_running:63572917
> at iteration:2 value:300100885 time_enabled:63569271 time_running:63569271
> at iteration:3 value:300103998 time_enabled:63573437 time_running:63573437
> at iteration:4 value:300101477 time_enabled:63571875 time_running:63571875
> at iteration:5 value:300100698 time_enabled:63569791 time_running:63569791
> at iteration:6 value:245252526 time_enabled:63650520 time_running:52012500
> perf_event_open02    0  TINFO  :  overall task clock: 63717187
> perf_event_open02    0  TINFO  :  hw sum: 1800857435, task clock sum: 382156248
> hw counters: 149326575 150152481 169006047 187845928 206684169
> 224693333 206543358 187716226 168865909 150023409
> task clock counters: 31694792 31870834 35868749 39866666 43863541
> 47685936 43822396 39826042 35828125 31829167
> perf_event_open02    0  TINFO  :  ratio: 5.997695
> perf_event_open02    1  TPASS  :  test passed
Vincent Guittot Nov. 20, 2019, 7:28 p.m. UTC | #9
On Wed, 20 Nov 2019 at 19:27, Qais Yousef <qais.yousef@arm.com> wrote:
>
> On 11/20/19 19:20, Vincent Guittot wrote:
> > On Wed, 20 Nov 2019 at 19:10, Qais Yousef <qais.yousef@arm.com> wrote:
> > >
> > > On 11/20/19 18:43, Vincent Guittot wrote:
> > > > On Wed, 20 Nov 2019 at 18:34, Qais Yousef <qais.yousef@arm.com> wrote:
> > > > >
> > > > > On 11/20/19 17:53, Vincent Guittot wrote:
> > > > > > On Wed, 20 Nov 2019 at 14:21, Vincent Guittot
> > > > > > <vincent.guittot@linaro.org> wrote:
> > > > > > >
> > > > > > > Hi Qais,
> > > > > > >
> > > > > > > On Wed, 20 Nov 2019 at 12:58, Qais Yousef <qais.yousef@arm.com> wrote:
> > > > > > > >
> > > > > > > > Hi Vincent
> > > > > > > >
> > > > > > > > On 10/18/19 15:26, Vincent Guittot wrote:
> > > > > > > > > The slow wake up path computes per sched_group statisics to select the
> > > > > > > > > idlest group, which is quite similar to what load_balance() is doing
> > > > > > > > > for selecting busiest group. Rework find_idlest_group() to classify the
> > > > > > > > > sched_group and select the idlest one following the same steps as
> > > > > > > > > load_balance().
> > > > > > > > >
> > > > > > > > > Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> > > > > > > > > ---
> > > > > > > >
> > > > > > > > LTP test has caught a regression in perf_event_open02 test on linux-next and I
> > > > > > > > bisected it to this patch.
> > > > > > > >
> > > > > > > > That is checking out next-20191119 tag and reverting this patch on top the test
> > > > > > > > passes. Without the revert the test fails.
> > > > > >
> > > > > > I haven't tried linux-next yet but LTP test is passed with
> > > > > > tip/sched/core, which includes this patch, on hikey960 which is arm64
> > > > > > too.
> > > > > >
> > > > > > Have you tried tip/sched/core on your juno ? this could help to
> > > > > > understand if it's only for juno or if this patch interact with
> > > > > > another branch merged in linux next
> > > > >
> > > > > Okay will give it a go. But out of curiosity, what is the output of your run?
> > > > >
> > > > > While bisecting on linux-next I noticed that at some point the test was
> > > > > passing but all the read values were 0. At some point I started seeing
> > > > > none-zero values.
> > > >
> > > > for tip/sched/core
> > > > linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
> > > > sudo ./perf_event_open02
> > > > perf_event_open02    0  TINFO  :  overall task clock: 63724479
> > > > perf_event_open02    0  TINFO  :  hw sum: 1800900992, task clock sum: 382170311
> > > > perf_event_open02    0  TINFO  :  ratio: 5.997229
> > > > perf_event_open02    1  TPASS  :  test passed
> > > >
> > > > for next-2019119
> > > > ~/ltp/testcases/kernel/syscalls/perf_event_open$ sudo ./perf_event_open02 -v
> > > > at iteration:0 value:0 time_enabled:69795312 time_running:0
> > > > perf_event_open02    0  TINFO  :  overall task clock: 63582292
> > > > perf_event_open02    0  TINFO  :  hw sum: 0, task clock sum: 0
> > > > hw counters: 0 0 0 0
> > > > task clock counters: 0 0 0 0
> > > > perf_event_open02    0  TINFO  :  ratio: 0.000000
> > > > perf_event_open02    1  TPASS  :  test passed
> > >
> > > Okay that is weird. But ratio, hw sum, task clock sum are all 0 in your
> > > next-20191119. I'm not sure why the counters return 0 sometimes - is it
> > > dependent on some option or a bug somewhere.
> > >
> > > I just did another run and it failed for me (building with defconfig)
> > >
> > > # uname -a
> > > Linux buildroot 5.4.0-rc8-next-20191119 #72 SMP PREEMPT Wed Nov 20 17:57:48 GMT 2019 aarch64 GNU/Linux
> > >
> > > # ./perf_event_open02 -v
> > > at iteration:0 value:260700250 time_enabled:172739760 time_running:144956600
> > > perf_event_open02    0  TINFO  :  overall task clock: 166915220
> > > perf_event_open02    0  TINFO  :  hw sum: 1200718268, task clock sum: 667621320
> > > hw counters: 300179051 300179395 300179739 300180083
> > > task clock counters: 166906620 166906200 166905160 166903340
> > > perf_event_open02    0  TINFO  :  ratio: 3.999763
> > > perf_event_open02    0  TINFO  :  nhw: 0.000100
> > > perf_event_open02    1  TFAIL  :  perf_event_open02.c:370: test failed (ratio was greater than )
> > >
> > > It is a funny one for sure. I haven't tried tip/sched/core yet.
> >
> > I confirm that on next-20191119, hw counters always return 0
> > but on tip/sched/core which has this patch and v5.4-rc7 which has not,
> > the hw counters are always different from 0
>
> It's the other way around for me. tip/sched/core returns 0 hw counters. I tried
> enabling coresight; that had no effect. Nor copying the .config that failed
> from linux-next to tip/sched/core. I'm not sure what's the dependency/breakage
> :-/

I run few more tests and i can get either hw counter with 0 or not.
The main difference is on which CPU it runs: either big or little
little return always 0 and big always non-zero value

on v5.4-rc7 and tip/sched/core, cpu0-3 return 0 and other non zeroa
but on next, it's the opposite cpu0-3 return non zero ratio

Could you try to run the test with taskset to run it on big or little ?

>
> --
> Qais Yousef
>
> >
> > on v5.4-rc7 i have got the same ratio :
> > linaro@linaro-developer:~/ltp/testcases/kernel/syscalls/perf_event_open$
> > sudo ./perf_event_open02 -v
> > at iteration:0 value:300157088 time_enabled:80641145 time_running:80641145
> > at iteration:1 value:300100129 time_enabled:63572917 time_running:63572917
> > at iteration:2 value:300100885 time_enabled:63569271 time_running:63569271
> > at iteration:3 value:300103998 time_enabled:63573437 time_running:63573437
> > at iteration:4 value:300101477 time_enabled:63571875 time_running:63571875
> > at iteration:5 value:300100698 time_enabled:63569791 time_running:63569791
> > at iteration:6 value:245252526 time_enabled:63650520 time_running:52012500
> > perf_event_open02    0  TINFO  :  overall task clock: 63717187
> > perf_event_open02    0  TINFO  :  hw sum: 1800857435, task clock sum: 382156248
> > hw counters: 149326575 150152481 169006047 187845928 206684169
> > 224693333 206543358 187716226 168865909 150023409
> > task clock counters: 31694792 31870834 35868749 39866666 43863541
> > 47685936 43822396 39826042 35828125 31829167
> > perf_event_open02    0  TINFO  :  ratio: 5.997695
> > perf_event_open02    1  TPASS  :  test passed
Qais Yousef Nov. 20, 2019, 7:55 p.m. UTC | #10
On 11/20/19 20:28, Vincent Guittot wrote:
> I run few more tests and i can get either hw counter with 0 or not.
> The main difference is on which CPU it runs: either big or little
> little return always 0 and big always non-zero value
> 
> on v5.4-rc7 and tip/sched/core, cpu0-3 return 0 and other non zeroa
> but on next, it's the opposite cpu0-3 return non zero ratio
> 
> Could you try to run the test with taskset to run it on big or little ?

Nice catch!

Yes indeed using taskset and forcing it to run on the big cpus it passes even
on linux-next/next-20191119.

So the relation to your patch is that it just biased where this test is likely
to run in my case and highlighted the breakage in the counters, probably?

FWIW, if I use taskset to force always big it passes. Always small, the counters
are always 0 and it passes too. But if I have mixed I see what I pasted before,
the counters have valid value but nhw is 0.

So the questions are, why little counters aren't working. And whether we should
run the test with taskset generally as it can't handle the asymmetry correctly.

Let me first try to find out why the little counters aren't working.

Thanks

--
Qais Yousef
Qais Yousef Nov. 21, 2019, 2:58 p.m. UTC | #11
On 11/20/19 19:55, Qais Yousef wrote:
> On 11/20/19 20:28, Vincent Guittot wrote:
> > I run few more tests and i can get either hw counter with 0 or not.
> > The main difference is on which CPU it runs: either big or little
> > little return always 0 and big always non-zero value
> > 
> > on v5.4-rc7 and tip/sched/core, cpu0-3 return 0 and other non zeroa
> > but on next, it's the opposite cpu0-3 return non zero ratio
> > 
> > Could you try to run the test with taskset to run it on big or little ?
> 
> Nice catch!
> 
> Yes indeed using taskset and forcing it to run on the big cpus it passes even
> on linux-next/next-20191119.
> 
> So the relation to your patch is that it just biased where this test is likely
> to run in my case and highlighted the breakage in the counters, probably?
> 
> FWIW, if I use taskset to force always big it passes. Always small, the counters
> are always 0 and it passes too. But if I have mixed I see what I pasted before,
> the counters have valid value but nhw is 0.
> 
> So the questions are, why little counters aren't working. And whether we should
> run the test with taskset generally as it can't handle the asymmetry correctly.
> 
> Let me first try to find out why the little counters aren't working.

So it turns out there's a caveat on usage of perf counters on big.LITTLE
systems.

Mark on CC can explain this better than me so I'll leave the details to him.

Sorry about the noise Vincent - it seems your patch was shifting things
slightly to cause migrating the task to another CPU, hence trigger the failure
on reading the perf counters, and the test in return.

Thanks

--
Qais Yousef
Valentin Schneider Nov. 22, 2019, 2:34 p.m. UTC | #12
Hi Vincent,

Apologies for the delayed review on that one. I have a few comments inline,
otherwise for the misfit part, if at all still relevant:

Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>

On 18/10/2019 14:26, Vincent Guittot wrote:
>  static struct sched_group *
>  find_idlest_group(struct sched_domain *sd, struct task_struct *p,
> +		  int this_cpu, int sd_flag);
                                    ^^^^^^^
That parameter is now unused. AFAICT it was only used to special-case fork
events (sd flag & SD_BALANCE_FORK). I didn't see any explicit handling of
this case in the rework, I assume the new group type classification makes
it possible to forgo?

> @@ -8241,6 +8123,252 @@ static inline enum fbq_type fbq_classify_rq(struct rq *rq)
>  }
>  #endif /* CONFIG_NUMA_BALANCING */
>  
> +
> +struct sg_lb_stats;
> +
> +/*
> + * update_sg_wakeup_stats - Update sched_group's statistics for wakeup.
> + * @denv: The ched_domain level to look for idlest group.
> + * @group: sched_group whose statistics are to be updated.
> + * @sgs: variable to hold the statistics for this group.
> + */
> +static inline void update_sg_wakeup_stats(struct sched_domain *sd,
> +					  struct sched_group *group,
> +					  struct sg_lb_stats *sgs,
> +					  struct task_struct *p)
> +{
> +	int i, nr_running;
> +
> +	memset(sgs, 0, sizeof(*sgs));
> +
> +	for_each_cpu(i, sched_group_span(group)) {
> +		struct rq *rq = cpu_rq(i);
> +
> +		sgs->group_load += cpu_load(rq);
> +		sgs->group_util += cpu_util_without(i, p);
> +		sgs->sum_h_nr_running += rq->cfs.h_nr_running;
> +
> +		nr_running = rq->nr_running;
> +		sgs->sum_nr_running += nr_running;
> +
> +		/*
> +		 * No need to call idle_cpu() if nr_running is not 0
> +		 */
> +		if (!nr_running && idle_cpu(i))
> +			sgs->idle_cpus++;
> +
> +
> +	}
> +
> +	/* Check if task fits in the group */
> +	if (sd->flags & SD_ASYM_CPUCAPACITY &&
> +	    !task_fits_capacity(p, group->sgc->max_capacity)) {
> +		sgs->group_misfit_task_load = 1;
> +	}
> +
> +	sgs->group_capacity = group->sgc->capacity;
> +
> +	sgs->group_type = group_classify(sd->imbalance_pct, group, sgs);
> +
> +	/*
> +	 * Computing avg_load makes sense only when group is fully busy or
> +	 * overloaded
> +	 */
> +	if (sgs->group_type < group_fully_busy)
> +		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
> +				sgs->group_capacity;
> +}
> +
> +static bool update_pick_idlest(struct sched_group *idlest,

Nit: could we name this update_sd_pick_idlest() to follow
update_sd_pick_busiest()? It's the kind of thing where if I typed
"update_sd" in gtags I'd like to see both listed, seeing as they are
*very* similar. And we already have update_sg_{wakeup, lb}_stats().

> +			       struct sg_lb_stats *idlest_sgs,
> +			       struct sched_group *group,
> +			       struct sg_lb_stats *sgs)
> +{
> +	if (sgs->group_type < idlest_sgs->group_type)
> +		return true;
> +
> +	if (sgs->group_type > idlest_sgs->group_type)
> +		return false;
> +
> +	/*
> +	 * The candidate and the current idles group are the same type of
> +	 * group. Let check which one is the idlest according to the type.
> +	 */
> +
> +	switch (sgs->group_type) {
> +	case group_overloaded:
> +	case group_fully_busy:
> +		/* Select the group with lowest avg_load. */
> +		if (idlest_sgs->avg_load <= sgs->avg_load)
> +			return false;
> +		break;
> +
> +	case group_imbalanced:
> +	case group_asym_packing:
> +		/* Those types are not used in the slow wakeup path */
> +		return false;
> +
> +	case group_misfit_task:
> +		/* Select group with the highest max capacity */
> +		if (idlest->sgc->max_capacity >= group->sgc->max_capacity)
> +			return false;
> +		break;
> +
> +	case group_has_spare:
> +		/* Select group with most idle CPUs */
> +		if (idlest_sgs->idle_cpus >= sgs->idle_cpus)
> +			return false;
> +		break;
> +	}
> +
> +	return true;
> +}
> +
> +/*
> + * find_idlest_group finds and returns the least busy CPU group within the
> + * domain.
> + *
> + * Assumes p is allowed on at least one CPU in sd.
> + */
> +static struct sched_group *
> +find_idlest_group(struct sched_domain *sd, struct task_struct *p,
> +		  int this_cpu, int sd_flag)
> +{
> +	struct sched_group *idlest = NULL, *local = NULL, *group = sd->groups;
> +	struct sg_lb_stats local_sgs, tmp_sgs;
> +	struct sg_lb_stats *sgs;
> +	unsigned long imbalance;
> +	struct sg_lb_stats idlest_sgs = {
> +			.avg_load = UINT_MAX,
> +			.group_type = group_overloaded,
> +	};
> +
> +	imbalance = scale_load_down(NICE_0_LOAD) *
> +				(sd->imbalance_pct-100) / 100;
> +
> +	do {
> +		int local_group;
> +
> +		/* Skip over this group if it has no CPUs allowed */
> +		if (!cpumask_intersects(sched_group_span(group),
> +					p->cpus_ptr))
> +			continue;
> +
> +		local_group = cpumask_test_cpu(this_cpu,
> +					       sched_group_span(group));
> +
> +		if (local_group) {
> +			sgs = &local_sgs;
> +			local = group;
> +		} else {
> +			sgs = &tmp_sgs;
> +		}
> +
> +		update_sg_wakeup_stats(sd, group, sgs, p);
> +
> +		if (!local_group && update_pick_idlest(idlest, &idlest_sgs, group, sgs)) {
> +			idlest = group;
> +			idlest_sgs = *sgs;
> +		}
> +
> +	} while (group = group->next, group != sd->groups);
> +
> +
> +	/* There is no idlest group to push tasks to */
> +	if (!idlest)
> +		return NULL;
> +
> +	/*
> +	 * If the local group is idler than the selected idlest group
> +	 * don't try and push the task.
> +	 */
> +	if (local_sgs.group_type < idlest_sgs.group_type)
> +		return NULL;
> +
> +	/*
> +	 * If the local group is busier than the selected idlest group
> +	 * try and push the task.
> +	 */
> +	if (local_sgs.group_type > idlest_sgs.group_type)
> +		return idlest;
> +
> +	switch (local_sgs.group_type) {
> +	case group_overloaded:
> +	case group_fully_busy:
> +		/*
> +		 * When comparing groups across NUMA domains, it's possible for
> +		 * the local domain to be very lightly loaded relative to the
> +		 * remote domains but "imbalance" skews the comparison making
> +		 * remote CPUs look much more favourable. When considering
> +		 * cross-domain, add imbalance to the load on the remote node
> +		 * and consider staying local.
> +		 */
> +
> +		if ((sd->flags & SD_NUMA) &&
> +		    ((idlest_sgs.avg_load + imbalance) >= local_sgs.avg_load))
> +			return NULL;
> +
> +		/*
> +		 * If the local group is less loaded than the selected
> +		 * idlest group don't try and push any tasks.
> +		 */
> +		if (idlest_sgs.avg_load >= (local_sgs.avg_load + imbalance))
> +			return NULL;
> +
> +		if (100 * local_sgs.avg_load <= sd->imbalance_pct * idlest_sgs.avg_load)
> +			return NULL;
> +		break;
> +
> +	case group_imbalanced:
> +	case group_asym_packing:
> +		/* Those type are not used in the slow wakeup path */
> +		return NULL;

I suppose group_asym_packing could be handled similarly to misfit, right?
i.e. make the group type group_asym_packing if

  !sched_asym_prefer(sg.asym_prefer_cpu, local.asym_prefer_cpu)

> +
> +	case group_misfit_task:
> +		/* Select group with the highest max capacity */
> +		if (local->sgc->max_capacity >= idlest->sgc->max_capacity)
> +			return NULL;

Got confused a bit here due to the naming; in this case 'group_misfit_task'
only means 'if placed on this group, the task will be misfit'. If the
idlest group will cause us to remain misfit, but can give us some extra
capacity, I think it makes sense to move.

> +		break;
> +
> +	case group_has_spare:
> +		if (sd->flags & SD_NUMA) {
> +#ifdef CONFIG_NUMA_BALANCING
> +			int idlest_cpu;
> +			/*
> +			 * If there is spare capacity at NUMA, try to select
> +			 * the preferred node
> +			 */
> +			if (cpu_to_node(this_cpu) == p->numa_preferred_nid)
> +				return NULL;
> +
> +			idlest_cpu = cpumask_first(sched_group_span(idlest));
> +			if (cpu_to_node(idlest_cpu) == p->numa_preferred_nid)
> +				return idlest;
> +#endif
> +			/*
> +			 * Otherwise, keep the task on this node to stay close
> +			 * its wakeup source and improve locality. If there is
> +			 * a real need of migration, periodic load balance will
> +			 * take care of it.
> +			 */
> +			if (local_sgs.idle_cpus)
> +				return NULL;
> +		}
> +
> +		/*
> +		 * Select group with highest number of idle cpus. We could also
> +		 * compare the utilization which is more stable but it can end
> +		 * up that the group has less spare capacity but finally more
> +		 * idle cpus which means more opportunity to run task.
> +		 */
> +		if (local_sgs.idle_cpus >= idlest_sgs.idle_cpus)
> +			return NULL;
> +		break;
> +	}
> +
> +	return idlest;
> +}
> +
>  /**
>   * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
>   * @env: The load balancing environment.
>
Vincent Guittot Nov. 25, 2019, 9:59 a.m. UTC | #13
On Fri, 22 Nov 2019 at 15:34, Valentin Schneider
<valentin.schneider@arm.com> wrote:
>
> Hi Vincent,
>
> Apologies for the delayed review on that one. I have a few comments inline,
> otherwise for the misfit part, if at all still relevant:
>
> Reviewed-by: Valentin Schneider <valentin.schneider@arm.com>
>
> On 18/10/2019 14:26, Vincent Guittot wrote:
> >  static struct sched_group *
> >  find_idlest_group(struct sched_domain *sd, struct task_struct *p,
> > +               int this_cpu, int sd_flag);
>                                     ^^^^^^^
> That parameter is now unused. AFAICT it was only used to special-case fork
> events (sd flag & SD_BALANCE_FORK). I didn't see any explicit handling of
> this case in the rework, I assume the new group type classification makes
> it possible to forgo?
>
> > @@ -8241,6 +8123,252 @@ static inline enum fbq_type fbq_classify_rq(struct rq *rq)
> >  }
> >  #endif /* CONFIG_NUMA_BALANCING */
> >
> > +
> > +struct sg_lb_stats;
> > +
> > +/*
> > + * update_sg_wakeup_stats - Update sched_group's statistics for wakeup.
> > + * @denv: The ched_domain level to look for idlest group.
> > + * @group: sched_group whose statistics are to be updated.
> > + * @sgs: variable to hold the statistics for this group.
> > + */
> > +static inline void update_sg_wakeup_stats(struct sched_domain *sd,
> > +                                       struct sched_group *group,
> > +                                       struct sg_lb_stats *sgs,
> > +                                       struct task_struct *p)
> > +{
> > +     int i, nr_running;
> > +
> > +     memset(sgs, 0, sizeof(*sgs));
> > +
> > +     for_each_cpu(i, sched_group_span(group)) {
> > +             struct rq *rq = cpu_rq(i);
> > +
> > +             sgs->group_load += cpu_load(rq);
> > +             sgs->group_util += cpu_util_without(i, p);
> > +             sgs->sum_h_nr_running += rq->cfs.h_nr_running;
> > +
> > +             nr_running = rq->nr_running;
> > +             sgs->sum_nr_running += nr_running;
> > +
> > +             /*
> > +              * No need to call idle_cpu() if nr_running is not 0
> > +              */
> > +             if (!nr_running && idle_cpu(i))
> > +                     sgs->idle_cpus++;
> > +
> > +
> > +     }
> > +
> > +     /* Check if task fits in the group */
> > +     if (sd->flags & SD_ASYM_CPUCAPACITY &&
> > +         !task_fits_capacity(p, group->sgc->max_capacity)) {
> > +             sgs->group_misfit_task_load = 1;
> > +     }
> > +
> > +     sgs->group_capacity = group->sgc->capacity;
> > +
> > +     sgs->group_type = group_classify(sd->imbalance_pct, group, sgs);
> > +
> > +     /*
> > +      * Computing avg_load makes sense only when group is fully busy or
> > +      * overloaded
> > +      */
> > +     if (sgs->group_type < group_fully_busy)
> > +             sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
> > +                             sgs->group_capacity;
> > +}
> > +
> > +static bool update_pick_idlest(struct sched_group *idlest,
>
> Nit: could we name this update_sd_pick_idlest() to follow
> update_sd_pick_busiest()? It's the kind of thing where if I typed
> "update_sd" in gtags I'd like to see both listed, seeing as they are
> *very* similar. And we already have update_sg_{wakeup, lb}_stats().
>
> > +                            struct sg_lb_stats *idlest_sgs,
> > +                            struct sched_group *group,
> > +                            struct sg_lb_stats *sgs)
> > +{
> > +     if (sgs->group_type < idlest_sgs->group_type)
> > +             return true;
> > +
> > +     if (sgs->group_type > idlest_sgs->group_type)
> > +             return false;
> > +
> > +     /*
> > +      * The candidate and the current idles group are the same type of
> > +      * group. Let check which one is the idlest according to the type.
> > +      */
> > +
> > +     switch (sgs->group_type) {
> > +     case group_overloaded:
> > +     case group_fully_busy:
> > +             /* Select the group with lowest avg_load. */
> > +             if (idlest_sgs->avg_load <= sgs->avg_load)
> > +                     return false;
> > +             break;
> > +
> > +     case group_imbalanced:
> > +     case group_asym_packing:
> > +             /* Those types are not used in the slow wakeup path */
> > +             return false;
> > +
> > +     case group_misfit_task:
> > +             /* Select group with the highest max capacity */
> > +             if (idlest->sgc->max_capacity >= group->sgc->max_capacity)
> > +                     return false;
> > +             break;
> > +
> > +     case group_has_spare:
> > +             /* Select group with most idle CPUs */
> > +             if (idlest_sgs->idle_cpus >= sgs->idle_cpus)
> > +                     return false;
> > +             break;
> > +     }
> > +
> > +     return true;
> > +}
> > +
> > +/*
> > + * find_idlest_group finds and returns the least busy CPU group within the
> > + * domain.
> > + *
> > + * Assumes p is allowed on at least one CPU in sd.
> > + */
> > +static struct sched_group *
> > +find_idlest_group(struct sched_domain *sd, struct task_struct *p,
> > +               int this_cpu, int sd_flag)
> > +{
> > +     struct sched_group *idlest = NULL, *local = NULL, *group = sd->groups;
> > +     struct sg_lb_stats local_sgs, tmp_sgs;
> > +     struct sg_lb_stats *sgs;
> > +     unsigned long imbalance;
> > +     struct sg_lb_stats idlest_sgs = {
> > +                     .avg_load = UINT_MAX,
> > +                     .group_type = group_overloaded,
> > +     };
> > +
> > +     imbalance = scale_load_down(NICE_0_LOAD) *
> > +                             (sd->imbalance_pct-100) / 100;
> > +
> > +     do {
> > +             int local_group;
> > +
> > +             /* Skip over this group if it has no CPUs allowed */
> > +             if (!cpumask_intersects(sched_group_span(group),
> > +                                     p->cpus_ptr))
> > +                     continue;
> > +
> > +             local_group = cpumask_test_cpu(this_cpu,
> > +                                            sched_group_span(group));
> > +
> > +             if (local_group) {
> > +                     sgs = &local_sgs;
> > +                     local = group;
> > +             } else {
> > +                     sgs = &tmp_sgs;
> > +             }
> > +
> > +             update_sg_wakeup_stats(sd, group, sgs, p);
> > +
> > +             if (!local_group && update_pick_idlest(idlest, &idlest_sgs, group, sgs)) {
> > +                     idlest = group;
> > +                     idlest_sgs = *sgs;
> > +             }
> > +
> > +     } while (group = group->next, group != sd->groups);
> > +
> > +
> > +     /* There is no idlest group to push tasks to */
> > +     if (!idlest)
> > +             return NULL;
> > +
> > +     /*
> > +      * If the local group is idler than the selected idlest group
> > +      * don't try and push the task.
> > +      */
> > +     if (local_sgs.group_type < idlest_sgs.group_type)
> > +             return NULL;
> > +
> > +     /*
> > +      * If the local group is busier than the selected idlest group
> > +      * try and push the task.
> > +      */
> > +     if (local_sgs.group_type > idlest_sgs.group_type)
> > +             return idlest;
> > +
> > +     switch (local_sgs.group_type) {
> > +     case group_overloaded:
> > +     case group_fully_busy:
> > +             /*
> > +              * When comparing groups across NUMA domains, it's possible for
> > +              * the local domain to be very lightly loaded relative to the
> > +              * remote domains but "imbalance" skews the comparison making
> > +              * remote CPUs look much more favourable. When considering
> > +              * cross-domain, add imbalance to the load on the remote node
> > +              * and consider staying local.
> > +              */
> > +
> > +             if ((sd->flags & SD_NUMA) &&
> > +                 ((idlest_sgs.avg_load + imbalance) >= local_sgs.avg_load))
> > +                     return NULL;
> > +
> > +             /*
> > +              * If the local group is less loaded than the selected
> > +              * idlest group don't try and push any tasks.
> > +              */
> > +             if (idlest_sgs.avg_load >= (local_sgs.avg_load + imbalance))
> > +                     return NULL;
> > +
> > +             if (100 * local_sgs.avg_load <= sd->imbalance_pct * idlest_sgs.avg_load)
> > +                     return NULL;
> > +             break;
> > +
> > +     case group_imbalanced:
> > +     case group_asym_packing:
> > +             /* Those type are not used in the slow wakeup path */
> > +             return NULL;
>
> I suppose group_asym_packing could be handled similarly to misfit, right?
> i.e. make the group type group_asym_packing if
>
>   !sched_asym_prefer(sg.asym_prefer_cpu, local.asym_prefer_cpu)

Unlike group_misfit_task that was somehow already taken into account
through the comparison of spare capacity, group_asym_packing was not
considered at all in find_idlest_group so I prefer to stay
conservative and wait for users of asym_packing to come with a need
before adding this new mechanism.

>
> > +
> > +     case group_misfit_task:
> > +             /* Select group with the highest max capacity */
> > +             if (local->sgc->max_capacity >= idlest->sgc->max_capacity)
> > +                     return NULL;
>
> Got confused a bit here due to the naming; in this case 'group_misfit_task'
> only means 'if placed on this group, the task will be misfit'. If the
> idlest group will cause us to remain misfit, but can give us some extra
> capacity, I think it makes sense to move.
>
> > +             break;
> > +
> > +     case group_has_spare:
> > +             if (sd->flags & SD_NUMA) {
> > +#ifdef CONFIG_NUMA_BALANCING
> > +                     int idlest_cpu;
> > +                     /*
> > +                      * If there is spare capacity at NUMA, try to select
> > +                      * the preferred node
> > +                      */
> > +                     if (cpu_to_node(this_cpu) == p->numa_preferred_nid)
> > +                             return NULL;
> > +
> > +                     idlest_cpu = cpumask_first(sched_group_span(idlest));
> > +                     if (cpu_to_node(idlest_cpu) == p->numa_preferred_nid)
> > +                             return idlest;
> > +#endif
> > +                     /*
> > +                      * Otherwise, keep the task on this node to stay close
> > +                      * its wakeup source and improve locality. If there is
> > +                      * a real need of migration, periodic load balance will
> > +                      * take care of it.
> > +                      */
> > +                     if (local_sgs.idle_cpus)
> > +                             return NULL;
> > +             }
> > +
> > +             /*
> > +              * Select group with highest number of idle cpus. We could also
> > +              * compare the utilization which is more stable but it can end
> > +              * up that the group has less spare capacity but finally more
> > +              * idle cpus which means more opportunity to run task.
> > +              */
> > +             if (local_sgs.idle_cpus >= idlest_sgs.idle_cpus)
> > +                     return NULL;
> > +             break;
> > +     }
> > +
> > +     return idlest;
> > +}
> > +
> >  /**
> >   * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
> >   * @env: The load balancing environment.
> >
Valentin Schneider Nov. 25, 2019, 11:13 a.m. UTC | #14
On 25/11/2019 09:59, Vincent Guittot wrote:
>>> +     case group_imbalanced:
>>> +     case group_asym_packing:
>>> +             /* Those type are not used in the slow wakeup path */
>>> +             return NULL;
>>
>> I suppose group_asym_packing could be handled similarly to misfit, right?
>> i.e. make the group type group_asym_packing if
>>
>>   !sched_asym_prefer(sg.asym_prefer_cpu, local.asym_prefer_cpu)
> 
> Unlike group_misfit_task that was somehow already taken into account
> through the comparison of spare capacity, group_asym_packing was not
> considered at all in find_idlest_group so I prefer to stay
> conservative and wait for users of asym_packing to come with a need
> before adding this new mechanism.
> 

Right, makes sense.

Patch
diff mbox series

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index ed1800d..fbaafae 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5541,127 +5541,9 @@  static int wake_affine(struct sched_domain *sd, struct task_struct *p,
 	return target;
 }
 
-static unsigned long cpu_util_without(int cpu, struct task_struct *p);
-
-static unsigned long capacity_spare_without(int cpu, struct task_struct *p)
-{
-	return max_t(long, capacity_of(cpu) - cpu_util_without(cpu, p), 0);
-}
-
-/*
- * find_idlest_group finds and returns the least busy CPU group within the
- * domain.
- *
- * Assumes p is allowed on at least one CPU in sd.
- */
 static struct sched_group *
 find_idlest_group(struct sched_domain *sd, struct task_struct *p,
-		  int this_cpu, int sd_flag)
-{
-	struct sched_group *idlest = NULL, *group = sd->groups;
-	struct sched_group *most_spare_sg = NULL;
-	unsigned long min_load = ULONG_MAX, this_load = ULONG_MAX;
-	unsigned long most_spare = 0, this_spare = 0;
-	int imbalance_scale = 100 + (sd->imbalance_pct-100)/2;
-	unsigned long imbalance = scale_load_down(NICE_0_LOAD) *
-				(sd->imbalance_pct-100) / 100;
-
-	do {
-		unsigned long load;
-		unsigned long spare_cap, max_spare_cap;
-		int local_group;
-		int i;
-
-		/* Skip over this group if it has no CPUs allowed */
-		if (!cpumask_intersects(sched_group_span(group),
-					p->cpus_ptr))
-			continue;
-
-		local_group = cpumask_test_cpu(this_cpu,
-					       sched_group_span(group));
-
-		/*
-		 * Tally up the load of all CPUs in the group and find
-		 * the group containing the CPU with most spare capacity.
-		 */
-		load = 0;
-		max_spare_cap = 0;
-
-		for_each_cpu(i, sched_group_span(group)) {
-			load += cpu_load(cpu_rq(i));
-
-			spare_cap = capacity_spare_without(i, p);
-
-			if (spare_cap > max_spare_cap)
-				max_spare_cap = spare_cap;
-		}
-
-		/* Adjust by relative CPU capacity of the group */
-		load = (load * SCHED_CAPACITY_SCALE) /
-					group->sgc->capacity;
-
-		if (local_group) {
-			this_load = load;
-			this_spare = max_spare_cap;
-		} else {
-			if (load < min_load) {
-				min_load = load;
-				idlest = group;
-			}
-
-			if (most_spare < max_spare_cap) {
-				most_spare = max_spare_cap;
-				most_spare_sg = group;
-			}
-		}
-	} while (group = group->next, group != sd->groups);
-
-	/*
-	 * The cross-over point between using spare capacity or least load
-	 * is too conservative for high utilization tasks on partially
-	 * utilized systems if we require spare_capacity > task_util(p),
-	 * so we allow for some task stuffing by using
-	 * spare_capacity > task_util(p)/2.
-	 *
-	 * Spare capacity can't be used for fork because the utilization has
-	 * not been set yet, we must first select a rq to compute the initial
-	 * utilization.
-	 */
-	if (sd_flag & SD_BALANCE_FORK)
-		goto skip_spare;
-
-	if (this_spare > task_util(p) / 2 &&
-	    imbalance_scale*this_spare > 100*most_spare)
-		return NULL;
-
-	if (most_spare > task_util(p) / 2)
-		return most_spare_sg;
-
-skip_spare:
-	if (!idlest)
-		return NULL;
-
-	/*
-	 * When comparing groups across NUMA domains, it's possible for the
-	 * local domain to be very lightly loaded relative to the remote
-	 * domains but "imbalance" skews the comparison making remote CPUs
-	 * look much more favourable. When considering cross-domain, add
-	 * imbalance to the load on the remote node and consider staying
-	 * local.
-	 */
-	if ((sd->flags & SD_NUMA) &&
-	     min_load + imbalance >= this_load)
-		return NULL;
-
-	if (min_load >= this_load + imbalance)
-		return NULL;
-
-	if ((this_load < (min_load + imbalance)) &&
-	    (100*this_load < imbalance_scale*min_load))
-		return NULL;
-
-	return idlest;
-}
+		  int this_cpu, int sd_flag);
 
 /*
  * find_idlest_group_cpu - find the idlest CPU among the CPUs in the group.
@@ -5734,7 +5616,7 @@  static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p
 		return prev_cpu;
 
 	/*
-	 * We need task's util for capacity_spare_without, sync it up to
+	 * We need task's util for cpu_util_without, sync it up to
 	 * prev_cpu's last_update_time.
 	 */
 	if (!(sd_flag & SD_BALANCE_FORK))
@@ -7915,13 +7797,13 @@  static inline int sg_imbalanced(struct sched_group *group)
  * any benefit for the load balance.
  */
 static inline bool
-group_has_capacity(struct lb_env *env, struct sg_lb_stats *sgs)
+group_has_capacity(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
 {
 	if (sgs->sum_nr_running < sgs->group_weight)
 		return true;
 
 	if ((sgs->group_capacity * 100) >
-			(sgs->group_util * env->sd->imbalance_pct))
+			(sgs->group_util * imbalance_pct))
 		return true;
 
 	return false;
@@ -7936,13 +7818,13 @@  group_has_capacity(struct lb_env *env, struct sg_lb_stats *sgs)
  *  false.
  */
 static inline bool
-group_is_overloaded(struct lb_env *env, struct sg_lb_stats *sgs)
+group_is_overloaded(unsigned int imbalance_pct, struct sg_lb_stats *sgs)
 {
 	if (sgs->sum_nr_running <= sgs->group_weight)
 		return false;
 
 	if ((sgs->group_capacity * 100) <
-			(sgs->group_util * env->sd->imbalance_pct))
+			(sgs->group_util * imbalance_pct))
 		return true;
 
 	return false;
@@ -7969,11 +7851,11 @@  group_smaller_max_cpu_capacity(struct sched_group *sg, struct sched_group *ref)
 }
 
 static inline enum
-group_type group_classify(struct lb_env *env,
+group_type group_classify(unsigned int imbalance_pct,
 			  struct sched_group *group,
 			  struct sg_lb_stats *sgs)
 {
-	if (group_is_overloaded(env, sgs))
+	if (group_is_overloaded(imbalance_pct, sgs))
 		return group_overloaded;
 
 	if (sg_imbalanced(group))
@@ -7985,7 +7867,7 @@  group_type group_classify(struct lb_env *env,
 	if (sgs->group_misfit_task_load)
 		return group_misfit_task;
 
-	if (!group_has_capacity(env, sgs))
+	if (!group_has_capacity(imbalance_pct, sgs))
 		return group_fully_busy;
 
 	return group_has_spare;
@@ -8086,7 +7968,7 @@  static inline void update_sg_lb_stats(struct lb_env *env,
 
 	sgs->group_weight = group->group_weight;
 
-	sgs->group_type = group_classify(env, group, sgs);
+	sgs->group_type = group_classify(env->sd->imbalance_pct, group, sgs);
 
 	/* Computing avg_load makes sense only when group is overloaded */
 	if (sgs->group_type == group_overloaded)
@@ -8241,6 +8123,252 @@  static inline enum fbq_type fbq_classify_rq(struct rq *rq)
 }
 #endif /* CONFIG_NUMA_BALANCING */
 
+
+struct sg_lb_stats;
+
+/*
+ * update_sg_wakeup_stats - Update sched_group's statistics for wakeup.
+ * @denv: The ched_domain level to look for idlest group.
+ * @group: sched_group whose statistics are to be updated.
+ * @sgs: variable to hold the statistics for this group.
+ */
+static inline void update_sg_wakeup_stats(struct sched_domain *sd,
+					  struct sched_group *group,
+					  struct sg_lb_stats *sgs,
+					  struct task_struct *p)
+{
+	int i, nr_running;
+
+	memset(sgs, 0, sizeof(*sgs));
+
+	for_each_cpu(i, sched_group_span(group)) {
+		struct rq *rq = cpu_rq(i);
+
+		sgs->group_load += cpu_load(rq);
+		sgs->group_util += cpu_util_without(i, p);
+		sgs->sum_h_nr_running += rq->cfs.h_nr_running;
+
+		nr_running = rq->nr_running;
+		sgs->sum_nr_running += nr_running;
+
+		/*
+		 * No need to call idle_cpu() if nr_running is not 0
+		 */
+		if (!nr_running && idle_cpu(i))
+			sgs->idle_cpus++;
+
+
+	}
+
+	/* Check if task fits in the group */
+	if (sd->flags & SD_ASYM_CPUCAPACITY &&
+	    !task_fits_capacity(p, group->sgc->max_capacity)) {
+		sgs->group_misfit_task_load = 1;
+	}
+
+	sgs->group_capacity = group->sgc->capacity;
+
+	sgs->group_type = group_classify(sd->imbalance_pct, group, sgs);
+
+	/*
+	 * Computing avg_load makes sense only when group is fully busy or
+	 * overloaded
+	 */
+	if (sgs->group_type < group_fully_busy)
+		sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) /
+				sgs->group_capacity;
+}
+
+static bool update_pick_idlest(struct sched_group *idlest,
+			       struct sg_lb_stats *idlest_sgs,
+			       struct sched_group *group,
+			       struct sg_lb_stats *sgs)
+{
+	if (sgs->group_type < idlest_sgs->group_type)
+		return true;
+
+	if (sgs->group_type > idlest_sgs->group_type)
+		return false;
+
+	/*
+	 * The candidate and the current idles group are the same type of
+	 * group. Let check which one is the idlest according to the type.
+	 */
+
+	switch (sgs->group_type) {
+	case group_overloaded:
+	case group_fully_busy:
+		/* Select the group with lowest avg_load. */
+		if (idlest_sgs->avg_load <= sgs->avg_load)
+			return false;
+		break;
+
+	case group_imbalanced:
+	case group_asym_packing:
+		/* Those types are not used in the slow wakeup path */
+		return false;
+
+	case group_misfit_task:
+		/* Select group with the highest max capacity */
+		if (idlest->sgc->max_capacity >= group->sgc->max_capacity)
+			return false;
+		break;
+
+	case group_has_spare:
+		/* Select group with most idle CPUs */
+		if (idlest_sgs->idle_cpus >= sgs->idle_cpus)
+			return false;
+		break;
+	}
+
+	return true;
+}
+
+/*
+ * find_idlest_group finds and returns the least busy CPU group within the
+ * domain.
+ *
+ * Assumes p is allowed on at least one CPU in sd.
+ */
+static struct sched_group *
+find_idlest_group(struct sched_domain *sd, struct task_struct *p,
+		  int this_cpu, int sd_flag)
+{
+	struct sched_group *idlest = NULL, *local = NULL, *group = sd->groups;
+	struct sg_lb_stats local_sgs, tmp_sgs;
+	struct sg_lb_stats *sgs;
+	unsigned long imbalance;
+	struct sg_lb_stats idlest_sgs = {
+			.avg_load = UINT_MAX,
+			.group_type = group_overloaded,
+	};
+
+	imbalance = scale_load_down(NICE_0_LOAD) *
+				(sd->imbalance_pct-100) / 100;
+
+	do {
+		int local_group;
+
+		/* Skip over this group if it has no CPUs allowed */
+		if (!cpumask_intersects(sched_group_span(group),
+					p->cpus_ptr))
+			continue;
+
+		local_group = cpumask_test_cpu(this_cpu,
+					       sched_group_span(group));
+
+		if (local_group) {
+			sgs = &local_sgs;
+			local = group;
+		} else {
+			sgs = &tmp_sgs;
+		}
+
+		update_sg_wakeup_stats(sd, group, sgs, p);
+
+		if (!local_group && update_pick_idlest(idlest, &idlest_sgs, group, sgs)) {
+			idlest = group;
+			idlest_sgs = *sgs;
+		}
+
+	} while (group = group->next, group != sd->groups);
+
+
+	/* There is no idlest group to push tasks to */
+	if (!idlest)
+		return NULL;
+
+	/*
+	 * If the local group is idler than the selected idlest group
+	 * don't try and push the task.
+	 */
+	if (local_sgs.group_type < idlest_sgs.group_type)
+		return NULL;
+
+	/*
+	 * If the local group is busier than the selected idlest group
+	 * try and push the task.
+	 */
+	if (local_sgs.group_type > idlest_sgs.group_type)
+		return idlest;
+
+	switch (local_sgs.group_type) {
+	case group_overloaded:
+	case group_fully_busy:
+		/*
+		 * When comparing groups across NUMA domains, it's possible for
+		 * the local domain to be very lightly loaded relative to the
+		 * remote domains but "imbalance" skews the comparison making
+		 * remote CPUs look much more favourable. When considering
+		 * cross-domain, add imbalance to the load on the remote node
+		 * and consider staying local.
+		 */
+
+		if ((sd->flags & SD_NUMA) &&
+		    ((idlest_sgs.avg_load + imbalance) >= local_sgs.avg_load))
+			return NULL;
+
+		/*
+		 * If the local group is less loaded than the selected
+		 * idlest group don't try and push any tasks.
+		 */
+		if (idlest_sgs.avg_load >= (local_sgs.avg_load + imbalance))
+			return NULL;
+
+		if (100 * local_sgs.avg_load <= sd->imbalance_pct * idlest_sgs.avg_load)
+			return NULL;
+		break;
+
+	case group_imbalanced:
+	case group_asym_packing:
+		/* Those type are not used in the slow wakeup path */
+		return NULL;
+
+	case group_misfit_task:
+		/* Select group with the highest max capacity */
+		if (local->sgc->max_capacity >= idlest->sgc->max_capacity)
+			return NULL;
+		break;
+
+	case group_has_spare:
+		if (sd->flags & SD_NUMA) {
+#ifdef CONFIG_NUMA_BALANCING
+			int idlest_cpu;
+			/*
+			 * If there is spare capacity at NUMA, try to select
+			 * the preferred node
+			 */
+			if (cpu_to_node(this_cpu) == p->numa_preferred_nid)
+				return NULL;
+
+			idlest_cpu = cpumask_first(sched_group_span(idlest));
+			if (cpu_to_node(idlest_cpu) == p->numa_preferred_nid)
+				return idlest;
+#endif
+			/*
+			 * Otherwise, keep the task on this node to stay close
+			 * its wakeup source and improve locality. If there is
+			 * a real need of migration, periodic load balance will
+			 * take care of it.
+			 */
+			if (local_sgs.idle_cpus)
+				return NULL;
+		}
+
+		/*
+		 * Select group with highest number of idle cpus. We could also
+		 * compare the utilization which is more stable but it can end
+		 * up that the group has less spare capacity but finally more
+		 * idle cpus which means more opportunity to run task.
+		 */
+		if (local_sgs.idle_cpus >= idlest_sgs.idle_cpus)
+			return NULL;
+		break;
+	}
+
+	return idlest;
+}
+
 /**
  * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
  * @env: The load balancing environment.