sched: implement usage tracking

With the frame-work for runnable tracking now fully in place.  Per-entity usage
tracking is a simple and low-overhead addition.

Signed-off-by: Paul Turner <pjt@google.com>
Reviewed-by: Ben Segall <bsegall@google.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: entity load-tracking load_avg_ratio

This patch adds load_avg_ratio to each task. The load_avg_ratio is a
variant of load_avg_contrib which is not scaled by the task priority. It
is calculated like this:

runnable_avg_sum * NICE_0_LOAD / (runnable_avg_period + 1).

Signed-off-by: Morten Rasmussen <Morten.Rasmussen@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Task placement for heterogeneous systems based on task load-tracking

This patch introduces the basic SCHED_HMP infrastructure. Each class of
cpus is represented by a hmp_domain and tasks will only be moved between
these domains when their load profiles suggest it is beneficial.

SCHED_HMP relies heavily on the task load-tracking introduced in Paul
Turners fair group scheduling patch set:

<https://lkml.org/lkml/2012/8/23/267>

SCHED_HMP requires that the platform implements arch_get_hmp_domains()
which should set up the platform specific list of hmp_domains. It is
also assumed that the platform disables SD_LOAD_BALANCE for the
appropriate sched_domains.
Tasks placement takes place every time a task is to be inserted into
a runqueue based on its load history. The task placement decision is
based on load thresholds.

There are no restrictions on the number of hmp_domains, however,
multiple (>2) has not been tested and the up/down migration policy is
rather simple.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Forced task migration on heterogeneous systems

This patch introduces forced task migration for moving suitable
currently running tasks between hmp_domains. Task behaviour is likely
to change over time. Tasks running in a less capable hmp_domain may
change to become more demanding and should therefore be migrated up.
They are unlikely go through the select_task_rq_fair() path anytime
soon and therefore need special attention.

This patch introduces a period check (SCHED_TICK) of the currently
running task on all runqueues and sets up a forced migration using
stop_machine_no_wait() if the task needs to be migrated.

Ideally, this should not be implemented by polling all runqueues.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Introduce priority-based task migration filter

Introduces a priority threshold which prevents low priority task
from migrating to faster hmp_domains (cpus). This is useful for
user-space software which assigns lower task priority to background
task.

Signed-off-by: Morten Rasmussen <Morten.Rasmussen@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
ARM: Add HMP scheduling support for ARM architecture

Adds Kconfig entries to enable HMP scheduling on ARM platforms.
Currently, it disables CPU level sched_domain load-balacing in order
to simplify things. This needs fixing in a later revision. HMP
scheduling will do the load-balancing at this level instead.

Signed-off-by: Morten Rasmussen <Morten.Rasmussen@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
ARM: sched: Use device-tree to provide fast/slow CPU list for HMP

We can't rely on Kconfig options to set the fast and slow CPU lists for
HMP scheduling if we want a single kernel binary to support multiple
devices with different CPU topology. E.g. TC2 (ARM's Test-Chip-2
big.LITTLE system), Fast Models, or even non big.LITTLE devices.

This patch adds the function arch_get_fast_and_slow_cpus() to generate
the lists at run-time by parsing the CPU nodes in device-tree; it
assumes slow cores are A7s and everything else is fast. The function
still supports the old Kconfig options as this is useful for testing the
HMP scheduler on devices without big.LITTLE.

This patch is reuse of a patch by Jon Medhurst <tixy@linaro.org> with a
few bits left out.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
ARM: sched: Setup SCHED_HMP domains

SCHED_HMP requires the different cpu types to be represented by an
ordered list of hmp_domains. Each hmp_domain represents all cpus of
a particular type using a cpumask.

The list is platform specific and therefore must be generated by
platform code by implementing arch_get_hmp_domains().

Signed-off-by: Morten Rasmussen <Morten.Rasmussen@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Add ftrace events for entity load-tracking

Adds ftrace events for key variables related to the entity
load-tracking to help debugging scheduler behaviour. Allows tracing
of load contribution and runqueue residency ratio for both entities
and runqueues as well as entity CPU usage ratio.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Add HMP task migration ftrace event

Adds ftrace event for tracing task migrations using HMP
optimized scheduling.

Signed-off-by: Morten Rasmussen <Morten.Rasmussen@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: SCHED_HMP multi-domain task migration control

We need a way to prevent tasks that are migrating up and down the
hmp_domains from migrating straight on through before the load has
adapted to the new compute capacity of the CPU on the new hmp_domain.
This patch adds a next up/down migration delay that prevents the task
from doing another migration in the same direction until the delay
has expired.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
ARM: sched: Avoid empty 'slow' HMP domain

On homogeneous (non-heterogeneous) systems all CPUs will be declared
'fast' and the slow cpu list will be empty. In this situation we need to
avoid adding an empty slow HMP domain otherwise the scheduler code will
blow up when it attempts to move a task to the slow domain.

Signed-off-by: Jon Medhurst <tixy@linaro.org>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Only down migrate low priority tasks if allowed by affinity mask

Adds an extra check intersection of the task affinity mask and the slower
hmp_domain cpumask before down migrating low priority tasks.

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: fix arch_get_fast_and_slow_cpus to get logical cpumask correctly

The patch "sched: Use device-tree to provide fast/slow CPU list for HMP"
depends on the ordering of CPU's in the device tree. It breaks to determine
the logical mask correctly if the logical mask of the CPUs differ from
physical ordering in the device tree.

This patch fix the logic by depending on the mpidr in the device tree
and mapping that mpidr to the logical cpu.

Signed-off-by: Sudeep KarkadaNagesha <sudeep.karkadanagesha@arm.com>
Signed-off-by: Liviu Dudau <Liviu.Dudau@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Do not ignore grouped tasks during HMP forced migration.

If the entity is not a task, it is a cfs group rq. Iterate up to
find the task entity.

Change-Id: I7cab7aba0798f6f14e38ad32e566d90e5937ffbc
Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
sched: Ignore offline CPUs in HMP migration & load stats

Previously, an offline CPU would always appear to have a zero load
and this would distort the offload functionality used for balancing
big and little domains.

Maintain a mask of online CPUs in each domain and use this instead.

Change-Id: I639b564b2f40cb659af8ceb8bd37f84b8a1fe323

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
ARM: Change load tracking scale using sysfs

These functions allow to change the load average period used
in the task load average computation through
/sys/kernel/hmp/load_avg_period_ms. This period is the time
in ms to go from 0 to 0.5 load average while running or the
time from 1 to 0.5 while sleeping.

The default one used is 32 and gives the same load_avg_ratio
computation than without this patch. These functions also allow
to change the up and down threshold of HMP using
/sys/kernel/hmp/{up,down}_threshold. Both must be between 0 and
1024. The thresholds are divided by 1024 before being compared
to the load_avg_ratio.

If /sys/kernel/hmp/load_avg_period_ms is 128 and
/sys/kernel/hmp/up_threshold is 512, a task will be migrated
to a bigger cluster after running for 128ms. Because after
load_avg_period_ms the load average is 0.5 and real up_threshold
us 512 / 1024 = 0.5.

Signed-off-by: Olivier Cozette <olivier.cozette@arm.com>
Signed-off-by: Chris Redpath <chris.redpath@arm.com>
Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
ARM: Experimental Frequency-Invariant Load Scaling Patch

Evaluation Patch to investigate using load as a representation of the
amount of POTENTIAL cpu compute capacity used rather than a representation
of the CURRENT cpu compute capacity.

If CPUFreq is enabled, scales load in accordance with frequency.

Powersave/performance CPUFreq governors are detected and scaling is
disabled while these governors are in use. This is because when a
single-frequency governor is in use, potential CPU capacity is static.

So long as the governors and CPUFreq subsystem correctly report the
frequencies available, the scaling should self tune.

Adds an additional file to sysfs to allow this feature to be disabled
for experimentation.

/sys/kernel/hmp/frequency_invariant_load_scale

write 0 to disable, 1 to enable.

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
ARM: Fix build breakage when big.LITTLE.conf is not used.

Change-Id: I8641f5e930c65b5672130bd4a18d9868bb3ca594

Signed-off-by: Abhijeet Dev <abhijeet@abhijeet-dev.net>
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>