sched: use EDF to schedule groups

Modify sched_rt in order to implement throttling using EDF among groups;
this allows the user to specify groups with different periods, with an
improved control over the bandwidth reservation on RT tasks.

This patch:
  - adds a deadline to rt_rq's (and removes the scheduling entity from
    it, as the new two-level compression of the full cgroup hierarchy does
    not use it for intermediates nodes anymore);
  - moves the rt_period_timer from struct rt_bandwidth to struct rt_rq,
    since periods and replenishments are no more synchronized among rt_rq's
    belonging to the same task_group;
  - adds a new struct rt_bandwidth to each task_group; the old one is
    used only for admission control, on a full cgroup hierarchy, while the
    new one is used to contain the parameters used to reserve bandwidth
    to tasks;
  - introduces a per-rq rt_edf_tree structure, to keep all the rt_rq's
    belonging to the same cpu ordered by their dynamic priority (i.e.,
    their deadline, if they are not boosted, or the static priority of
    their highest priority task if they are);
  - updates the admission control code, to take into account the bandwidth
    assigned to tasks via the new cgroup attributes rt_task_period_us and
    rt_task_runtime_us (this bandwidth is not available for lower-level
    cgroups);
  - removes highest_prio tracking for non-root rt_rq's and flattens the
    arbitrary task_group hierarchy to a two-level one, transparently to
    the users, who still see the full cgroup hierarchy.  The push/pull
    logic is altered a bit after this change, as the toplevel
    rt_nr_running is not meaningful anymore, we use rt_nr_total instead
    (the reasoning behind this is that tasks should be pushed/pulled
     without taking into account the fact that they are throttled or not).
    The toplevel runqueue, containing both the rt_edf_tree and the
    highest_prio data is no more a rt_rq, but it has its own type,
    rt_root_rq.

Signed-off-by: Fabio Checconi <fchecconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>

Conflicts:

	kernel/sched/rt.c
	kernel/sched/sched.h

Signed-off-by: Luis Cruz <ljc2491@gmail.com>
sched: enforce per-cpu utilization limits on runtime balancing

Enforce utilization constraints on the bandwidth assignments produced
by the runtime balancing code. The underlying EDF scheduler requires,
in order to work reliably, that the utilization on each cpu does not
exceed 100%; this patch adds per-cpu utilization tracking and does not
allow the balancer to exceed the global RT bandwidth assignment on any
cpu.

Whenever the bandwidth assigments change (i.e., the user writes an
RT-scheduler cgroup attribute, or a task_group disappears, the bandwidth
assignment is reset to a symmetric assignment, and the balancing restarts
from a safe startpoint.  This requires iterating on all the rt_rq's in the
system (N_cpu * N_groups), and it is surely suboptimal, but it is
conceptually simple and safe.

Synchronization needs a couple of words: a per-rq flag disables runtime
balancing to/from single rq's; the flag relies on spinlock acquire
barriers to ensure that all the balancing operations starting after the
flag has been set see the its correct value. To protect the per-rq
free bandwidth counter we use per-rq locks, that can nest like rq->lock;
reusing existing locks proved not to be easy, as the various
rt_runtime_locks act on a per-group or per-rt_rq basis.

Signed-off-by: Fabio Checconi <fchecconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
sched: make runtime balancing code more EDF-friendly

The old runtime balancing code logic does not work too well when using
EDF to schedule runqueues. One of the problems is that the old throttling
code had only one timer to handle budget replenishments; EDF needs per-cpu
timers, not in sync among themselves.

This patch changes balance_runtime() to work in push or pull mode: 1) when
an rt_rq needs extra runtime, it tries to borrow it from its siblings, and
2) when an rt_rq has some borroewed runtime, it tries to distribute it
among the rt_rq's needing it. This change improves things a little bit,
making easier to redistribute bandwidth when the load on the various
rt_rq's changes; anyway this is far from being an optimal solution.
I think we need (intependently from this patchset) to make the balancing
logic cooperate with (or at least aware of) task push/pulls and define
more formally the objectives of the runtime migration policy.

Signed-off-by: Fabio Checconi <f.checconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
sched: avoid ksoftirqd wakeups when starting the hrtick timer

Calling hrtimer_start() to start the hrtick timer is not safe, as it
may wake up ksoftirqd.  Use __hrtimer_start_range_ns() instead.

Signed-off-by: Fabio Checconi <f.checconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>

Conflicts:

	kernel/sched/core.c

Signed-off-by: Luis Cruz <ljc2491@gmail.com>
sched: improve the rt-throttling interface

The EDF-throttling interface as it is is quite unusable.  Add support
for '-1' as a special value for the rt_task_runtime_us cgroup attribute,
assigning to the tasks of the group the same period as their parent group
and all the free runtime available within that group.

Signed-off-by: Fabio Checconi <fchecconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
sched: another attempt at runtime balancing

Signed-off-by: Fabio Checconi <fchecconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
sched: improve timer resync

Signed-off-by: Fabio Checconi <fchecconi@gmail.com>
Signed-off-by: Juri Lelli <juri.lelli@gmail.com>
sched: fix invalid pointer in dec_rt_prio().

rt_rq was invalidated by the call to for_each_leaf_rt_rq(); add an
iterator rt_rq.
Merge branch 'rebase-onto-edft' into jb-mr1

Conflicts:
	kernel/sched/core.c
	kernel/sched/sched.h