sched: introduce compute capacity for CPUs, groups and domains

Date	Tue, 16 Apr 2013 16:26:16 +0100

Using the per-cpu compute capacity exported from topology
when CONFIG_ARCH_SCALE_INVARIANT_CPU_CAPACITY is active, place this
information alongside cpu_power in the scheduler and combine for the
various aggregating entities.

Change-Id: I4984c335bcdc128680e7459b3f86bb05e04593cc
backported for Mako Hybrid from LKML

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: smart wake-affine

wake-affine stuff is always trying to pull wakee close to waker, by theory,
this will bring benefit if waker's cpu cached hot data for wakee, or the
extreme ping-pong case.

And testing show it could benefit hackbench 15% at most.

However, the whole stuff is somewhat blindly and time-consuming, some
workload therefore suffer.

And testing show it could damage pgbench 50% at most.

Thus, wake-affine stuff should be smarter, and realise when to stop
it's thankless effort.

This patch introduced per task 'nr_wakee_switch', which will be increased
each time the task switch it's wakee.

So a high 'nr_wakee_switch' means the task has more than one wakee, and
less the wakee number, higher the wakeup frequency.

Now when making the decision on whether to pull or not, pay attention on
the wakee with a high 'nr_wakee_switch', pull such task may benefit wakee,
but that imply waker will face cruel competition later, it could be very
crule or very fast depends on the story behind 'nr_wakee_switch', whatever,
waker therefore suffer.

Furthermore, if waker also has a high 'nr_wakee_switch', that imply multiple
tasks rely on it, waker's higher latency will damage all those tasks, pull
wakee in such cases seems to be a bad deal.

Thus, when 'waker->nr_wakee_switch / wakee->nr_wakee_switch' become higher
and higher, the deal seems to be worse and worse.

This patch therefore help wake-affine stuff to stop it's work when:

	wakee->nr_wakee_switch > factor &&
	waker->nr_wakee_switch > (factor * wakee->nr_wakee_switch)
The factor here is the online cpu number, so more cpu will lead to more pull
since the trial become more severe.

After applied the patch, pgbench show 42% improvement at most.

Test:
	Test with 12 cpu X86 server and tip 3.10.0-rc1.

				base	smart

	| db_size | clients |  tps  | |  tps  |
	+---------+---------+-------+ +-------+
	| 21 MB   |       1 | 10749 | | 10337 |
	| 21 MB   |       2 | 21382 | | 21391 |
	| 21 MB   |       4 | 41570 | | 41808 |
	| 21 MB   |       8 | 52828 | | 58792 |
	| 21 MB   |      12 | 48447 | | 54553 |
	| 21 MB   |      16 | 46246 | | 56726 |	+22.66%
	| 21 MB   |      24 | 43850 | | 56853 |	+29.65%
	| 21 MB   |      32 | 43455 | | 55846 |	+28.51%
	| 7483 MB |       1 |  9290 | |  8848 |
	| 7483 MB |       2 | 19347 | | 19351 |
	| 7483 MB |       4 | 37135 | | 37511 |
	| 7483 MB |       8 | 47310 | | 50210 |
	| 7483 MB |      12 | 42721 | | 49396 |
	| 7483 MB |      16 | 41016 | | 51826 |	+26.36%
	| 7483 MB |      24 | 37540 | | 52579 |	+40.06%
	| 7483 MB |      32 | 36756 | | 51332 |	+39.66%
	| 15 GB   |       1 |  8758 | |  8670 |
	| 15 GB   |       2 | 19204 | | 19249 |
	| 15 GB   |       4 | 36997 | | 37199 |
	| 15 GB   |       8 | 46578 | | 50681 |
	| 15 GB   |      12 | 42141 | | 48671 |
	| 15 GB   |      16 | 40518 | | 51280 |	+26.56%
	| 15 GB   |      24 | 36788 | | 52329 |	+42.24%
	| 15 GB   |      32 | 36056 | | 50350 | +39.64%

CC: Ingo Molnar <mingo@kernel.org>
CC: Peter Zijlstra <peterz@infradead.org>
CC: Mike Galbraith <efault@gmx.de>
Signed-off-by: Michael Wang <wangyun@linux.vnet.ibm.com>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Use cached value of span instead of calling sched_domain_span()

Date	Tue, 11 Jun 2013 16:32:43 +0530

In the beginning of build_sched_groups() we called sched_domain_span() and
cached its return value in span. Few statements later we are calling it again to
get the same pointer.

Lets use the cached value instead as it hasn't changed in between.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: don't call get_group() for covered cpus

Date	Tue, 11 Jun 2013 16:32:44 +0530

In build_sched_groups() we don't need to call get_group() for cpus which are
already covered in previous iterations. So, call get_group() after checking if
cpu is covered or not.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: remove WARN_ON(!sd) from init_sched_groups_power()

Date	Tue, 11 Jun 2013 16:32:45 +0530

sd can't be NULL in init_sched_groups_power() and so checking it for NULL isn't
useful. In case it is required, then also we need to rearrange the code a bit as
we already accessed invalid pointer sd to get sg: sg = sd->groups.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: reduce calculation effort in fix_small_imbalance

Date	Mon, 17 Jun 2013 21:00:22 +0800

Actually all below item could be repalced by scaled_busy_load_per_task
	(sds->busiest_load_per_task * SCHED_POWER_SCALE)
		/sds->busiest->sgp->power;

Signed-off-by: Lei Wen <leiwen@marvell.com>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: scale the busy and this queue's per-task load before compare

Date	Mon, 17 Jun 2013 21:00:23 +0800

Since for max_load and this_load, they are the value that already be
scaled. It is not reasonble to get a minimum value between the scaled
and non-scaled value, like below example.
	min(sds->busiest_load_per_task, sds->max_load);

Also add comment over in what condition, there would be cpu power gain
in move the load.

Signed-off-by: Lei Wen <leiwen@marvell.com>
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: scale cpu load for judgment of group imbalance Date Mon, 17 Jun 2013 21:00:24 +0800

We cannot compare two load directly from two cpus, since the cpu power
over two cpu may vary largely.

Suppose we meet such two kind of cpus.
CPU A:
	No real time work, and there are 3 task, with rq->load.weight
being 512.
CPU B:
	Has real time work, and it take 3/4 of the cpu power, which
makes CFS only take 1/4, that is 1024/4=256 cpu power. And over its CFS
runqueue, there is only one task with weight as 128.

Since both cpu's CFS task take for half of the CFS's cpu power, it
should be considered as balanced in such case.

But original judgment like:
        if ((max_cpu_load - min_cpu_load) >= avg_load_per_task &&
            (max_nr_running - min_nr_running) > 1)
It makes (512-128)>=((512+128)/4), and lead to imbalance conclusion...
Make the load as scaled, to avoid such case.

Signed-off-by: Lei Wen <leiwen@marvell.com>

modified for Mako kernel from LKML reference
Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Make sure to not re-read variables after validation

We could re-read rq->rt_avg after we validated it was smaller than
total, invalidating the check and resulting in an unintended negative.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: David Rientjes <rientjes@google.com>
Link: http://lkml.kernel.org/r/1337688268.9698.29.camel@twins
Signed-off-by: Ingo Molnar <mingo@kernel.org>
CRs-Fixed: 497236
Git-commit: b654f7de41b0e3903ee2b51d3b8db77fe52ce728
Git-repo: git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
(cherry picked from commit fef154fa32c5d8ef992f11e11919495979970678)

Change-Id: Ieac7a10d9f4ceb701660f8055efd7a0ed5d939ca
Signed-off-by: Sridhar Nelloru <nellos@codeaurora.org>
sched: re-calculate a cpu's next_balance point upon sched domain changes

Commit 55ddeb0f (sched: Reset rq->next_interval before going idle) reset
a cpu's rq->next_balance when pulled_task = 0, which will be true when
the cpu failed to pull any task, causing it go idle. However that patch
relied on next_balance being calculated as a result of traversing cpu's
sched domain hierarchy.

A cpu that is the only online cpu will however not be attached to any
sched domain hierarchy. When such a cpu calls into idle_balance(), we
will end up initializing next_balance to be 1sec away! Such a CPU will
defer load balance check for another 1sec, even though we may bring up
more cpus in the meantime requiring it to check for load imbalance more
frequently. This could then lead to increased scheduling latency for
some tasks.

This patch results in a cpu's next_balance being re-calculated when its
attaching to a new sched domain hierarchy.  This should let cpus call
load balance checks at the right time we expect them to!

Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
(cherry picked from commit 91b609bdd91513c37c410ffef0204f8a0578e4f8)

Change-Id: Ib457f1a357aad26e49837a01311b73e22e0cc26f
Signed-off-by: Sridhar Nelloru <nellos@codeaurora.org>
sched: Reduce overestimating rq->avg_idle

Date	Thu, 29 Aug 2013 13:05:34 -0700

When updating avg_idle, if the delta exceeds some max value, then avg_idle
gets set to the max, regardless of what the previous avg was. This can cause
avg_idle to often be overestimated.

This patch modifies the way we update avg_idle by always updating it with the
function call to update_avg() first. Then, if avg_idle exceeds the max, we set
it to the max.

Signed-off-by: Jason Low <jason.low2@hp.com>
Reviewed-by: Rik van Riel <riel@redhat.com>

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Consider max cost of idle balance per sched domain

Date	Thu, 29 Aug 2013 13:05:35 -0700

In this patch, we keep track of the max cost we spend doing idle load balancing
for each sched domain. If the avg time the CPU remains idle is less then the
time we have already spent on idle balancing + the max cost of idle balancing
in the sched domain, then we don't continue to attempt the balance. We also
keep a per rq variable, max_idle_balance_cost, which keeps track of the max
time spent on newidle load balances throughout all its domains. Additionally,
we swap sched_migration_cost used in idle_balance for rq->max_idle_balance_cost.

By using the max, we avoid overrunning the average. This further reduces the chance
we attempt balancing when the CPU is not idle for longer than the cost to balance.

I also limited the max cost of each domain to 5*sysctl_sched_migration_cost as
a way to prevent the max from becoming too inflated.

Signed-off-by: Jason Low <jason.low2@hp.com>

backported for Linux 3.4

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Periodically decay max cost of idle balance

This RFC patch builds on patch 2 and periodically decays that max value to
do idle balancing per sched domain.

Though we want to decay it fairly consistently, we may not want to lower it by
too much each time, especially since avg_idle is capped based on that value.
So I thought that decaying the value every second and lowering it by half a
percent each time appeared to be fairly reasonable.

This change would allow us to remove the limit we set on each domain's max cost
to idle balance. Also, since the max can be reduced now, we now have to
update rq->max_idle balance_cost more frequently. So after every idle balance,
we loop through the sched domain to find the max sd's newidle load balance cost
for any one domain. Then we will set rq->max_idle_balance_cost to that value.

Since we are now decaying the max cost to do idle balancing, that max cost can
also become not high enough. One possible explanation for why is that
besides the time spent on each newidle load balance, there are other costs
associated with attempting idle balancing. Idle balance also releases and
reacquires a spin lock. That cost is not counted when we keep track of each
domain's cost to do newidle load balance. Also, acquiring the rq locks can
potentially prevent other CPUs from running something useful. And after
migrating tasks, it might potentially have to pay the costs of cache misses and
refreshing tasks' cache.

Because of that, this patch also compares avg_idle with max cost to do idle
balancing + sched_migration_cost. While using the max cost helps reduce
overestimating the average idle, the sched_migration_cost can help account
for those additional costs of idle balancing.

Signed-off-by: Jason Low <jason.low2@hp.com>
[peterz: rewrote the logic, but kept the spirit]
Signed-off-by: Peter Zijlstra <peterz@infradead.org>

backport to Linxu 3.4

Signed-off-by: Paul Reioux <reioux@gmail.com>