smart: define and build per-core data structures

First, this patch introduces the smart_core_data structure.
This structure contains following fields:
cpu_core_id - per-cpu core id (first SMT thread on this core)
core_next - id of next core on local node
core_node_sibling - id of corresponding core on next node
core_locked - per-core lock used for synchronizing core selection

The following macros/functions are introduced to access smart data:
cpu_core_id(cpu) - returns core id of CPU
smart_data(cpu) - returns per-core smart_data (macro)
core_next(cpu) - returns next core id of CPU
core_node_sibling(cpu) - returns id of sibling core on next node

Also, this patch introduces build_smart_topology() function,
which fills smart_core_data for each cpu.
Below is the illustration of how it's should look on 2-nodes CPU
with 8 physical cores and 16 SMT threads.

cpu    cpu_core_id
0,8              0
1,9              1
2,10             2
3,11             3
4,12             4
5,13             5
6,14             6
7,15             7

           node 0                              node 1
------------------------------      ------------------------------
core         0  core         1      core         4  core         5
core_next    1  core_next    2      core_next    5  core_next    6
node_sibling 4  node_sibling 5      node_sibling 0  node_sibling 1

core         2  core         3      core         6  core         7
core_next    3  core_next    0      core_next    7  core_next    4
node_sibling 6  node_sibling 7      node_sibling 2  node_sibling 3
------------------------------      ------------------------------

build_smart_topology() uses sched_domains data and is called
each time sched domains are rebuilt. If smart topology is built
successfully (checked by check_smart_data()),
__smart_initialized static key is set to true.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: add config option for SMART-related code

All the SMART-related code will use CONFIG_SMART config option.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: introduce smart_enabled()

This patch introduces __smart_enabled static key and smart_enabled()
function, which will be used to check if smart functionality
is enabled.
An ability to turn it on/off will be added later.
By default, __smart_enabled is set to true.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: helper functions for smart_data manipulations

This commit adds the following helper functions:
acquire_core() - acquires per-core lock
release_core() - releases per-core lock
core_acquired() - checks if per-core lock is acquired
core_is_rt_free() - checks if there are no rt tasks on specified core
core_rt_free_thread() - finds free SMT thread on specified core
find_rt_free_core() - finds free core starting with specified core

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: CPU selection logic

This commit contains the most important code: CPU selection logic.
It's implemented by smart_find_lowest_rq() function and some helper
functions.

The logic is relatively simple:
1) try to find free core on local node (starting with previous task's CPU)
2) try to find free core on next remote node
3) try to find free SMT thread on local node
4) try to find free SMT thread on remote node
5) try to find SMT thread with minimum rt tasks

If we find free CPU on any step we try to acquire it and if it's successful we
stop further processing and quit; otherwise, if CPU is locked, we restart the
search.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: use CPU selection logic if smart is enabled

This patch causes rt scheduler to use smart CPU selection logic,
if smart_enabled() returns true.

Also, release_core() should be called every time rt-task is actually
enqueued on the runqueue or it's clear, that it will never be enqueued
on selected CPU.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: balance load between nodes

Although previously introduced CPU selection logic isn't limited by
local node, if the number of rt tasks is smaller than the number of
physical cores per node, significant load imbalance can occur.

Modern CPUs tends to scale their's frequency depending on the number
of loaded CPUs, so such imbalance can lead to decreased per-CPU
performance on the more loaded node.

To solve this problem, this commit adds the following logic to CPU
selection logic: if the number of running rt processes on current node
is greater than on a remote node and the difference is more than 1/4 of
the number of rt tasks on local node, start search with corresponding
core on the remote node.

The number of rt tasks on each node is tracked with per-node atomic count.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: smart pull

This patch implements migration of running rt tasks (aka "smart pull").
The idea is quite simple: if there are free cores, there is no reason to
suffer from hyper-threading.

The implementation is a bit trickier:
in pre_schedule() we check, if we are switching from rt task to
non-rt (CFS or idle), and if so, we schedule a delayed work. This work
searches for a rt tasks, which is the best candidate for migrating (has
maximal smart_score). If there is a such candidate, migration occurs.
Such migration always occurs from non-first SMT thread on source core to
first SMT thread on destination core.

Smart score are counting in the following way: for each running rt task
on each scheduler tick we check if there are tasks concurrently running
on the same core. If so, we add this number to smart score.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: throttle CFS tasks by affinning to first SMT thread

Normal ("CFS") tasks can affect the performance of rt tasks by loading
other SMT threads on the same core. If we want to have a guaranteed
performance for rt tasks, it's unacceptable.
So, this patch denies enqueuing of CFS tasks if there are running rt
tasks on the same core.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: smart gathering

Previous patch denies starting new CFS tasks on a core with running rt
tasks. The problem still exists if there are already running CFS tasks
at the moment rt task starts.
This patch introduces smart gathering - migration of running CFS tasks
from all other CPUs to the CPU with rt task.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: smart debug

This patch introduces debug infrastructure for smart.
The infrastructure contains a number of per-cpu counters,
smart_event() function to register smart-related events and procfs
interface to read and reset these counters.

The following events are counting:
pull - smart pull
balance_local - local cpu selection
balance_remote - remote cpu selection
select_core - free local core selected
select_rcore - free remote core selected
select_thread - free local cpu selected
select_rthread - free remote cpu selected
select_busy - busy cpu selected
select_busy_curr - current busy cpu selected
select_fallback - select_fallback_rq() called
rt_pull - rt push
rt_push - rt pull

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: cgroup interface for smart

This patch extends cpu cgroup controller to provide convenient interface
for using smart.
The interface contains one simple knob: smart. If it's set to 1,
SCHED_RR scheduling policy (with priority 10) is assigned to all non-rt
tasks in the group. If it's set to 0, scheduling policy of all rt tasks
is reset to SCHED_NORMAL.
Global enabling/disabling smart doesn't affect per-cgroup smart knob
state, but tasks in the smart cgroup will actually scheduled by CFS if
smart is disabled globally. In other words, tasks in a cgroup with smart
knob set are scheduled by real-time scheduler only if smart is enabled.
If smart is temporarily disabled globally (due to cpu hotplug, for
instance), all tasks in smart cgroups will be temporarily scheduled by
CFS and than rt scheduling policy will be restored. Such behavior
guarantees graceful degradation if something is wrong with smart.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: nosmart boot option

This patch introduces nosmart boot option, that is intended to disable
smart globally at boot time.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: smart-related sysctl's

This patch introduces sysctl interface for smart configuration (default
values are given in brackets):
sched_smart_enable (1) - enable/disable smart globally
sched_smart_prio (10) - rt priority of tasks in a cgroup with smart set
sched_smart_gathering (1) - enable/disable smart gathering
sched_smart_throttle (1) - enable/disable throttling of CFS tasks

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: decrease default rt_period/rt_runtime values

By default, rt_period is 1s and rt_runtime is 0.95s. These values
are to high to achieve acceptable system responsibility under high
rt load. Decrease it to 100ms and 99ms respectively.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: change default RR timeslice to 5ms

By default, SCHED_RR timeslice is 100ms. Change it to 5ms to achieve
better responsibility.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
smart: disable RT runtime sharing

This patch disables runtime sharing for rt tasks (RT_RUNTIME_SHARE).
It's necessary to guarantee that CFS tasks (including system threads
like rcu workers) will get time slice regularly on each cpu even when
system is heavily loaded with rt tasks.

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>
hrtimers: calculate expires_next after all timers are executed

I think I'm hitting particularly subtle issue with NOHZ_IDLE kernel.

The sequence is as follows:
- CPU enters idle, we disable tick
- hrtimer interrupt fires (for hrtimer_wakeup)
- for clock base #1 (REALTIME) we wake up SCHED_RT thread and
  start RT period timer (from start_rt_bandwidth) for clock base #0 (MONOTONIC)
- because we already checked expiry time for clock base #0
  we end up programming wrong wake up time (minutes, from tick_sched_timer)
- then, we exit idle loop and restart tick;
  but because tick_sched_timer is not leftmost (the leftmost one
  is RT period timer) we don't program it

So in the end, I see working CPU without tick interrupt.
This eventually leads to RCU stall on that CPU: rcu_gp_kthread
is not woken up because there is no tick (this is the reason
I started digging this up).

The proposed fix runs expired timers first and only then tries to find
next expiry time for all clocks.

Signed-off-by: Stanislav Fomichev <stfomichev@yandex-team.ru>
smart: add description to the README file

Signed-off-by: Roman Gushchin <klamm@yandex-team.ru>