sched: Basic global balancing support for HMP

This patch introduces an extra-check at task up-migration to
prevent overloading the cpus in the faster hmp_domain while the
slower hmp_domain is not fully utilized. The patch also introduces
a periodic balance check that can down-migrate tasks if the faster
domain is oversubscribed and the slower is under-utilized.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: cfs.nr_running does not contain the intended metric

rq->nr_running is the actual number of runnable tasks we wish to use
to determine if a task is alone on a CPU.

Change-Id: Icaf3022e02924ecdc94e14d4146c6fadd9580e2b
Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Use unweighted load for hmp migration decisions

Normal task and runqueue loading is scaled according to priority
to end up with a weighted load, known as the contribution.

We want the CPU time to be allotted according to priority, but
we also want to make big/little decisions based upon raw load.

It is common, for example, for Android apps following the dev
guide to end up with all their long-running or async action
threads as low priority unless they override the AsyncThread
constructor. All these threads are such low priority that they
become invisible to the hmp_offload routine.

Using unweighted load here allows us to maximise CPU usage in busy
situations.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Select least-loaded CPU when performing HMP Migrations

The reference patch set always selects the first CPU in an HMP
domain as a migration target. In busy situations, this means that
the migrated thread cannot make immediate use of an idle CPU but
must share a busy one until the load balancer runs across the big
domain.

This patch uses the hmp_domain_min_load function introduced in
global balancing to figure out which of the CPUs is the least busy
and selects that as a migration target - in both directions.

This essentially implements a task-spread strategy and is intended
to maximise performance of migrated threads but is likely
to use more power than the packing strategy previously employed.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Avoid multiple calls to hmp_domain_min_load in fast path

When evaluating a migration we make two calls to hmp_domain_min_load.
This is unnecessary if we pass on the target CPU information from the
hmp_up_migration path.

In hmp_down_migration, we don't consider the load of the target CPUS.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Force new non-kernel tasks onto big CPUs until load stabilises

Initialise the load stats for new tasks so that they do not
see the instability in early task life which makes it so hard to
decide which CPU is appropriate.

Also, change the fork balance algorithm so that the least loaded of
the CPUs in the big cluster is chosen regardless of the bigness of
the parent task.

This is intended to help performance for applications which use
many short-lived tasks. Although best practise is usually to use
a thread pool, apps which do not do this should not be subject to
the randomness of the early stats.

We should ignore real-time threads for forking on big CPUs, but
it is not possible to figure out if a new thread is real-time or
not at the fork stage. Instead, we prevent kernel threads from
getting the initial boost - when they later become real-time they
will only be on big if their compute requirements demand it.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Restrict nohz balance kicks to stay in the HMP domain

There is little point in doing a nohz balance kick on a CPU from a
different HMP domain, since the unset SD_LOAD_BALANCE flag on the CPU
domain level prevents tasks from being balanced across clusters
except through the per-task load driven hmp_migrate/hmp_offload paths.

Further, the nohz balance kick is actively harmful to power usage if
all the tasks fit into the little domain since it causes the big
domain to wake up and do a lot of calculation to determine that
there is nothing to do.

A more generic solution is to walk the sched domain tree and determine
the intersection of potential idle balance cpus with visibility of
tasks on the current CPU, however HMP domains are more easily
accessible.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: experimental: Force all rt tasks to start on little domain.

This patch restricts the allowed cpu mask for rt tasks initially started
with a full cpu mask to the little domain.

An rt task is specified as real time in __setscheduler() which is finally
called for all rt tasks (kernel and user land). In this function we
restrict the allowed cpu mask to the little domain.

This also prevents that a rt tasks can later be pushed to the big domain
because the function find_lowest_rq() will only recognize the allowed cpu
mask of a task to find the new cpu the task runs on.

Current kludges of the patch:

* Since we do not have an API to get the cpu mask of the A7 cluster,
hmp_slow_cpu_mask is made global in arm/kernel/topology.c for now.

* The watchdog_enable() function calls sched_setscheduler() before
kthread_bind() for the cpu specific watchdog kernel threads. The order of
these two calls has to be changed to make this patch work.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Check the system has little cpus before forcing rt tasks onto them

It is sometimes desirable to run a kernel with HMP scheduling enabled
on a system which is not big.LITTLE, e.g. when building a multi-platform
kernel, or when testing a big.LITTLE system with one cluster disabled.

We should therefore allow for the situation where is no little domain.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: select 'best' task for migration rather than 'current'

When we are looking for a task to migrate up, select the heaviest
one in the first 5 runnable on the runqueue.

Likewise, when looking for a task to offload, select the lightest
one in the first 5 runnable on the runqueue.

Ensure task selected is runnable in the target domain.

This change is necessary in order to implement idle pull in a
sensible manner, but here is used in up-migration and offload to
select the correct target task.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Liviu Dudau <liviu.dudau@arm.com>
Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: HMP fix traversing the rb-tree from the curr pointer

The hmp_get_{lightest,heaviest}_task() need to use
__pick_first_entity() to get a pointer to a sched_entity on the rq.
The current is not kept on the rq while running, so its rb-tree node
pointers are no longer valid.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Liviu Dudau <liviu.dudau@arm.com>
Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: track per-rq 'last migration time'

Track when migrations were performed to runqueues.

Use this to decide between runqueues as migration targets when run
queues in an hmp domain have equal load.

Intention is to spread migration load amongst CPUs more fairly.

When all CPUs in an hmp domain are fully loaded, the existing code
always selects the last CPU as a migration target - this is unfair
and little better than doing no selection.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Liviu Dudau <liviu.dudau@arm.com>
Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Modify the runqueue stats to add a new child stat

The original intent here was to track unweighted runqueue load
with less resolution so we could use the least-recently-disturbed
runqueue to choose between 'closely related' load levels.

However, after experimenting with the resolution it turns out
that the following algorithm is highly beneficial for mobile
workloads.

In hmp_domain_min_load:

  * If any CPU is zero, the overall load is zero
  * If no CPUs are idle, the domain is 'fully loaded'

Additionally, the time since last migration count is used to
discriminate between idle CPUs.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Explicitly implement all-load-is-max-load policy for HMP targets

Experimentally, one of the best policies for HMP migration CPU
selection is to completely ignore part-loaded CPUs and only look
for idle ones. If there are no idle ones, we will choose the one
which was least-recently-disturbed.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: HMP change nr_running offload metric

rq->nr_running was better than cfs.nr_running, since it includes
all tasks actually on the CPU. However, it includes RT tasks which
we would rather ignore at this point.

Switching to cfs.h_nr_running includes all the CFS tasks but no
RT tasks.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Liviu Dudau <liviu.dudau@arm.com>
Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Implement idle pull for HMP

When an A15 goes idle, we should up-migrate anything which is
above the threshold and running on an A7.

Reuses the HMP force-migration spinlock, but adds its own new
cpu stopper client.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Access runqueue task clocks directly.

Avoids accesses through cfs_rq going bad when the cpu_rq doesn't
have a cfs member.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Liviu Dudau <liviu.dudau@arm.com>
Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
HMP: Update migration timer when we fork-migrate

Prevents fork-migration adversely interacting with normal
migration (i.e. runqueues containing forked tasks being
selected as migration targets when there is a better
choice available)

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Liviu Dudau <liviu.dudau@arm.com>
Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: HMP: Change default HMP thresholds

When the up-threshold is at 512 on TC2, behaviour looks OK since
the graphic-related tasks are very heavy due to lack of a GPU.
Increasing the up-threshold does not reduce power consumption.

When a GPU is present, graphic tasks are much less CPU-heavy and
so additional power may be saved by having a higher threshold.

Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Liviu Dudau <Liviu.Dudau@arm.com>
Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: HMP: Additional trace points for debugging HMP behaviour

1. Replace magic numbers in code for migration trace.
   Trace points still emit a number as force=<n> field:
     force=0 : wakeup migration
     force=1 : forced migration
     force=2 : offload migration
     force=3 : idle pull migration

2. Add trace to expose offload decision-making.
   Also adds tracing rq->nr_running so that you can
   look back to see what state the RQ was in at the time.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>