Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > linux.kernel > #1607855 > unrolled thread
| Started by | luca abeni <luca.abeni@santannapisa.it> |
|---|---|
| First post | 2017-03-23 21:00 +0100 |
| Last post | 2017-03-23 21:00 +0100 |
| Articles | 3 on this page of 23 — 7 participants |
Back to article view | Back to linux.kernel
[RFC v5 0/9] CPU reclaiming for SCHED_DEADLINE luca abeni <luca.abeni@santannapisa.it> - 2017-03-23 21:00 +0100
[RFC v5 8/9] sched/deadline: base GRUB reclaiming on the inactive utilization luca abeni <luca.abeni@santannapisa.it> - 2017-03-23 21:00 +0100
Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the inactive utilization Peter Zijlstra <peterz@infradead.org> - 2017-03-27 16:30 +0200
Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the inactive utilization Luca Abeni <luca.abeni@santannapisa.it> - 2017-03-27 17:00 +0200
Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the inactive utilization Peter Zijlstra <peterz@infradead.org> - 2017-03-27 18:20 +0200
Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the inactive utilization luca abeni <luca.abeni@santannapisa.it> - 2017-03-27 19:10 +0200
[RFC v5 2/9] sched/deadline: improve the tracking of active utilization luca abeni <luca.abeni@santannapisa.it> - 2017-03-23 21:00 +0100
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Peter Zijlstra <peterz@infradead.org> - 2017-03-24 14:30 +0100
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Peter Zijlstra <peterz@infradead.org> - 2017-03-24 14:30 +0100
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization luca abeni <luca.abeni@santannapisa.it> - 2017-03-24 22:50 +0100
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Steven Rostedt <rostedt@goodmis.org> - 2017-03-25 03:40 +0100
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Luca Abeni <luca.abeni@santannapisa.it> - 2017-03-27 10:30 +0200
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Claudio Scordino <claudio@evidence.eu.com> - 2017-03-27 11:00 +0200
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Juri Lelli <juri.lelli@arm.com> - 2017-03-27 09:20 +0200
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Luca Abeni <luca.abeni@santannapisa.it> - 2017-03-27 10:10 +0200
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Juri Lelli <juri.lelli@arm.com> - 2017-03-27 10:50 +0200
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Luca Abeni <luca.abeni@santannapisa.it> - 2017-03-27 09:40 +0200
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization Mathieu Poirier <mathieu.poirier@linaro.org> - 2017-03-26 19:40 +0200
Re: [RFC v5 2/9] sched/deadline: improve the tracking of active utilization luca abeni <luca.abeni@santannapisa.it> - 2017-03-26 23:10 +0200
[RFC v5 6/9] sched/deadline: make GRUB a task's flag luca abeni <luca.abeni@santannapisa.it> - 2017-03-23 21:00 +0100
[RFC v5 7/9] sched/deadline: track the "total rq utilization" too luca abeni <luca.abeni@santannapisa.it> - 2017-03-23 21:00 +0100
[RFC v5 4/9] sched/deadline: implement GRUB accounting luca abeni <luca.abeni@santannapisa.it> - 2017-03-23 21:00 +0100
[RFC v5 3/9] sched/deadline: fix the update of the total -deadline utilization luca abeni <luca.abeni@santannapisa.it> - 2017-03-23 21:00 +0100
Page 2 of 2 — ← Prev page 1 [2]
| From | luca abeni <luca.abeni@santannapisa.it> |
|---|---|
| Date | 2017-03-23 21:00 +0100 |
| Subject | [RFC v5 7/9] sched/deadline: track the "total rq utilization" too |
| Message-ID | <toh3Q-72e-23@gated-at.bofh.it> |
| In reply to | #1607855 |
From: Luca Abeni <luca.abeni@santannapisa.it>
The total rq utilization is defined as the sum of the utilisations of
tasks that are "assigned" to a runqueue, independently from their state
(TASK_RUNNING or blocked)
Signed-off-by: Luca Abeni <luca.abeni@santannapisa.it>
Signed-off-by: Claudio Scordino <claudio@evidence.eu.com>
Tested-by: Daniel Bristot de Oliveira <bristot@redhat.com>
---
kernel/sched/deadline.c | 87 +++++++++++++++++++++++++++++++++++++------------
kernel/sched/sched.h | 11 +++++++
2 files changed, 78 insertions(+), 20 deletions(-)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 1951379..d70a7b9 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -51,6 +51,7 @@ void add_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
dl_rq->running_bw += dl_bw;
SCHED_WARN_ON(dl_rq->running_bw < old); /* overflow */
+ SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw);
}
static inline
@@ -65,6 +66,29 @@ void sub_running_bw(u64 dl_bw, struct dl_rq *dl_rq)
dl_rq->running_bw = 0;
}
+static inline
+void add_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
+{
+ u64 old = dl_rq->this_bw;
+
+ lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
+ dl_rq->this_bw += dl_bw;
+ SCHED_WARN_ON(dl_rq->this_bw < old); /* overflow */
+}
+
+static inline
+void sub_rq_bw(u64 dl_bw, struct dl_rq *dl_rq)
+{
+ u64 old = dl_rq->this_bw;
+
+ lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock);
+ dl_rq->this_bw -= dl_bw;
+ SCHED_WARN_ON(dl_rq->this_bw > old); /* underflow */
+ if (dl_rq->this_bw > old)
+ dl_rq->this_bw = 0;
+ SCHED_WARN_ON(dl_rq->running_bw > dl_rq->this_bw);
+}
+
void dl_change_utilization(struct task_struct *p, u64 new_bw)
{
if (!task_on_rq_queued(p)) {
@@ -83,6 +107,8 @@ void dl_change_utilization(struct task_struct *p, u64 new_bw)
if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
put_task_struct(p);
}
+ sub_rq_bw(p->dl.dl_bw, &rq->dl);
+ add_rq_bw(new_bw, &rq->dl);
}
}
@@ -124,6 +150,8 @@ static void task_non_contending(struct task_struct *p)
if (!dl_task(p) || p->state == TASK_DEAD) {
struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
+ if (p->state == TASK_DEAD)
+ sub_rq_bw(p->dl.dl_bw, &rq->dl);
raw_spin_lock(&dl_b->lock);
__dl_clear(dl_b, p->dl.dl_bw);
__dl_clear_params(p);
@@ -138,7 +166,7 @@ static void task_non_contending(struct task_struct *p)
hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL);
}
-static void task_contending(struct sched_dl_entity *dl_se)
+static void task_contending(struct sched_dl_entity *dl_se, int flags)
{
struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
@@ -149,6 +177,9 @@ static void task_contending(struct sched_dl_entity *dl_se)
if (dl_se->dl_runtime == 0)
return;
+ if (flags & ENQUEUE_MIGRATED)
+ add_rq_bw(dl_se->dl_bw, dl_rq);
+
if (dl_se->dl_non_contending) {
/*
* If the timer handler is currently running and the
@@ -978,6 +1009,7 @@ static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
if (p->state == TASK_DEAD && dl_se->dl_non_contending) {
sub_running_bw(p->dl.dl_bw, dl_rq_of_se(&p->dl));
+ sub_rq_bw(p->dl.dl_bw, dl_rq_of_se(&p->dl));
dl_se->dl_non_contending = 0;
}
@@ -1143,7 +1175,7 @@ enqueue_dl_entity(struct sched_dl_entity *dl_se,
* we want a replenishment of its runtime.
*/
if (flags & ENQUEUE_WAKEUP) {
- task_contending(dl_se);
+ task_contending(dl_se, flags);
update_dl_entity(dl_se, pi_se);
}
else if (flags & ENQUEUE_REPLENISH)
@@ -1196,8 +1228,10 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
if (!p->dl.dl_throttled && dl_is_constrained(&p->dl))
dl_check_constrained_dl(&p->dl);
- if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & ENQUEUE_RESTORE)
+ if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & ENQUEUE_RESTORE) {
+ add_rq_bw(p->dl.dl_bw, &rq->dl);
add_running_bw(p->dl.dl_bw, &rq->dl);
+ }
/*
* If p is throttled, we do not enqueue it. In fact, if it exhausted
@@ -1213,7 +1247,7 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
*/
if (p->dl.dl_throttled && !(flags & ENQUEUE_REPLENISH)) {
if (flags & ENQUEUE_WAKEUP)
- task_contending(&p->dl);
+ task_contending(&p->dl, flags);
return;
}
@@ -1235,8 +1269,10 @@ static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
update_curr_dl(rq);
__dequeue_task_dl(rq, p, flags);
- if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & DEQUEUE_SAVE)
+ if (p->on_rq == TASK_ON_RQ_MIGRATING || flags & DEQUEUE_SAVE) {
sub_running_bw(p->dl.dl_bw, &rq->dl);
+ sub_rq_bw(p->dl.dl_bw, &rq->dl);
+ }
/*
* This check allows to start the inactive timer (or to immediately
@@ -1328,22 +1364,24 @@ select_task_rq_dl(struct task_struct *p, int cpu, int sd_flag, int flags)
static void migrate_task_rq_dl(struct task_struct *p)
{
- if ((p->state == TASK_WAKING) && (p->dl.dl_non_contending)) {
+ if (p->state == TASK_WAKING) {
struct rq *rq = task_rq(p);
raw_spin_lock(&rq->lock);
- sub_running_bw(p->dl.dl_bw, &rq->dl);
- p->dl.dl_non_contending = 0;
- /*
- * If the timer handler is currently running and the
- * timer cannot be cancelled, inactive_task_timer()
- * will see that dl_not_contending is not set, and
- * will not touch the rq's active utilization,
- * so we are still safe.
- */
- if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
- put_task_struct(p);
-
+ if (p->dl.dl_non_contending) {
+ sub_running_bw(p->dl.dl_bw, &rq->dl);
+ p->dl.dl_non_contending = 0;
+ /*
+ * If the timer handler is currently running and the
+ * timer cannot be cancelled, inactive_task_timer()
+ * will see that dl_not_contending is not set, and
+ * will not touch the rq's active utilization,
+ * so we are still safe.
+ */
+ if (hrtimer_try_to_cancel(&p->dl.inactive_timer) == 1)
+ put_task_struct(p);
+ }
+ sub_rq_bw(p->dl.dl_bw, &rq->dl);
raw_spin_unlock(&rq->lock);
}
}
@@ -1791,7 +1829,9 @@ static int push_dl_task(struct rq *rq)
deactivate_task(rq, next_task, 0);
sub_running_bw(next_task->dl.dl_bw, &rq->dl);
+ sub_rq_bw(next_task->dl.dl_bw, &rq->dl);
set_task_cpu(next_task, later_rq->cpu);
+ add_rq_bw(next_task->dl.dl_bw, &later_rq->dl);
add_running_bw(next_task->dl.dl_bw, &later_rq->dl);
activate_task(later_rq, next_task, 0);
ret = 1;
@@ -1881,7 +1921,9 @@ static void pull_dl_task(struct rq *this_rq)
deactivate_task(src_rq, p, 0);
sub_running_bw(p->dl.dl_bw, &src_rq->dl);
+ sub_rq_bw(p->dl.dl_bw, &src_rq->dl);
set_task_cpu(p, this_cpu);
+ add_rq_bw(p->dl.dl_bw, &this_rq->dl);
add_running_bw(p->dl.dl_bw, &this_rq->dl);
activate_task(this_rq, p, 0);
dmin = p->dl.deadline;
@@ -1990,6 +2032,9 @@ static void switched_from_dl(struct rq *rq, struct task_struct *p)
if (task_on_rq_queued(p) && p->dl.dl_runtime)
task_non_contending(p);
+ if (!task_on_rq_queued(p))
+ sub_rq_bw(p->dl.dl_bw, &rq->dl);
+
/*
* We cannot use inactive_task_timer() to invoke sub_running_bw()
* at the 0-lag time, because the task could have been migrated
@@ -2019,9 +2064,11 @@ static void switched_to_dl(struct rq *rq, struct task_struct *p)
put_task_struct(p);
/* If p is not queued we will update its parameters at next wakeup. */
- if (!task_on_rq_queued(p))
- return;
+ if (!task_on_rq_queued(p)) {
+ add_rq_bw(p->dl.dl_bw, &rq->dl);
+ return;
+ }
/*
* If p is boosted we already updated its params in
* rt_mutex_setprio()->enqueue_task(..., ENQUEUE_REPLENISH),
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 141549b..3818b3c 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -567,6 +567,17 @@ struct dl_rq {
u64 running_bw;
/*
+ * Utilization of the tasks "assigned" to this runqueue (including
+ * the tasks that are in runqueue and the tasks that executed on this
+ * CPU and blocked). Increased when a task moves to this runqueue, and
+ * decreased when the task moves away (migrates, changes scheduling
+ * policy, or terminates).
+ * This is needed to compute the "inactive utilization" for the
+ * runqueue (inactive utilization = this_bw - running_bw).
+ */
+ u64 this_bw;
+
+ /*
* Inverse of the fraction of CPU utilization that can be reclaimed
* by the GRUB algorithm.
*/
--
2.7.4
[toc] | [prev] | [next] | [standalone]
| From | luca abeni <luca.abeni@santannapisa.it> |
|---|---|
| Date | 2017-03-23 21:00 +0100 |
| Subject | [RFC v5 4/9] sched/deadline: implement GRUB accounting |
| Message-ID | <toh3Q-72e-31@gated-at.bofh.it> |
| In reply to | #1607855 |
From: Luca Abeni <luca.abeni@santannapisa.it>
According to the GRUB (Greedy Reclaimation of Unused Bandwidth)
reclaiming algorithm, the runtime is not decreased as "dq = -dt",
but as "dq = -Uact dt" (where Uact is the per-runqueue active
utilization).
Hence, this commit modifies the runtime accounting rule in
update_curr_dl() to implement the GRUB rule.
Signed-off-by: Luca Abeni <luca.abeni@santannapisa.it>
Tested-by: Daniel Bristot de Oliveira <bristot@redhat.com>
---
kernel/sched/deadline.c | 14 ++++++++++++++
1 file changed, 14 insertions(+)
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 238713e..6035311 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -862,6 +862,19 @@ int dl_runtime_exceeded(struct sched_dl_entity *dl_se)
extern bool sched_rt_bandwidth_account(struct rt_rq *rt_rq);
/*
+ * This function implements the GRUB accounting rule:
+ * according to the GRUB reclaiming algorithm, the runtime is
+ * not decreased as "dq = -dt", but as "dq = -Uact dt", where
+ * Uact is the (per-runqueue) active utilization.
+ * Since rq->dl.running_bw contains Uact * 2^20, the result
+ * has to be shifted right by 20.
+ */
+u64 grub_reclaim(u64 delta, struct rq *rq)
+{
+ return (delta * rq->dl.running_bw) >> 20;
+}
+
+/*
* Update the current task's runtime statistics (provided it is still
* a -deadline task and has not been removed from the dl_rq).
*/
@@ -903,6 +916,7 @@ static void update_curr_dl(struct rq *rq)
sched_rt_avg_update(rq, delta_exec);
+ delta_exec = grub_reclaim(delta_exec, rq);
dl_se->runtime -= delta_exec;
throttle:
--
2.7.4
[toc] | [prev] | [next] | [standalone]
| From | luca abeni <luca.abeni@santannapisa.it> |
|---|---|
| Date | 2017-03-23 21:00 +0100 |
| Subject | [RFC v5 3/9] sched/deadline: fix the update of the total -deadline utilization |
| Message-ID | <toh3Q-72e-25@gated-at.bofh.it> |
| In reply to | #1607855 |
From: Luca Abeni <luca.abeni@santannapisa.it>
Now that the inactive timer can be armed to fire at the 0-lag time,
it is possible to use inactive_task_timer() to update the total
-deadline utilization (dl_b->total_bw) at the correct time, fixing
dl_overflow() and __setparam_dl().
Signed-off-by: Luca Abeni <luca.abeni@santannapisa.it>
Tested-by: Daniel Bristot de Oliveira <bristot@redhat.com>
---
kernel/sched/core.c | 38 ++++++++++++++------------------------
kernel/sched/deadline.c | 23 +++++++++++++----------
2 files changed, 27 insertions(+), 34 deletions(-)
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index bf0b0b9..20c62e7 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2487,9 +2487,6 @@ static inline int dl_bw_cpus(int i)
* allocated bandwidth to reflect the new situation.
*
* This function is called while holding p's rq->lock.
- *
- * XXX we should delay bw change until the task's 0-lag point, see
- * __setparam_dl().
*/
static int dl_overflow(struct task_struct *p, int policy,
const struct sched_attr *attr)
@@ -2514,16 +2511,29 @@ static int dl_overflow(struct task_struct *p, int policy,
cpus = dl_bw_cpus(task_cpu(p));
if (dl_policy(policy) && !task_has_dl_policy(p) &&
!__dl_overflow(dl_b, cpus, 0, new_bw)) {
+ if (hrtimer_active(&p->dl.inactive_timer))
+ __dl_clear(dl_b, p->dl.dl_bw);
__dl_add(dl_b, new_bw);
err = 0;
} else if (dl_policy(policy) && task_has_dl_policy(p) &&
!__dl_overflow(dl_b, cpus, p->dl.dl_bw, new_bw)) {
+ /*
+ * XXX this is slightly incorrect: when the task
+ * utilization decreases, we should delay the total
+ * utilization change until the task's 0-lag point.
+ * But this would require to set the task's "inactive
+ * timer" when the task is not inactive.
+ */
__dl_clear(dl_b, p->dl.dl_bw);
__dl_add(dl_b, new_bw);
dl_change_utilization(p, new_bw);
err = 0;
} else if (!dl_policy(policy) && task_has_dl_policy(p)) {
- __dl_clear(dl_b, p->dl.dl_bw);
+ /*
+ * Do not decrease the total deadline utilization here,
+ * switched_from_dl() will take care to do it at the correct
+ * (0-lag) time.
+ */
err = 0;
}
raw_spin_unlock(&dl_b->lock);
@@ -3964,26 +3974,6 @@ __setparam_dl(struct task_struct *p, const struct sched_attr *attr)
dl_se->dl_period = attr->sched_period ?: dl_se->dl_deadline;
dl_se->flags = attr->sched_flags;
dl_se->dl_bw = to_ratio(dl_se->dl_period, dl_se->dl_runtime);
-
- /*
- * Changing the parameters of a task is 'tricky' and we're not doing
- * the correct thing -- also see task_dead_dl() and switched_from_dl().
- *
- * What we SHOULD do is delay the bandwidth release until the 0-lag
- * point. This would include retaining the task_struct until that time
- * and change dl_overflow() to not immediately decrement the current
- * amount.
- *
- * Instead we retain the current runtime/deadline and let the new
- * parameters take effect after the current reservation period lapses.
- * This is safe (albeit pessimistic) because the 0-lag point is always
- * before the current scheduling deadline.
- *
- * We can still have temporary overloads because we do not delay the
- * change in bandwidth until that time; so admission control is
- * not on the safe side. It does however guarantee tasks will never
- * consume more than promised.
- */
}
/*
diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
index 86aed82..238713e 100644
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -121,8 +121,14 @@ static void task_non_contending(struct task_struct *p)
if (zerolag_time < 0) {
if (dl_task(p))
sub_running_bw(dl_se->dl_bw, dl_rq);
- if (!dl_task(p) || p->state == TASK_DEAD)
+ if (!dl_task(p) || p->state == TASK_DEAD) {
+ struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
+
+ raw_spin_lock(&dl_b->lock);
+ __dl_clear(dl_b, p->dl.dl_bw);
__dl_clear_params(p);
+ raw_spin_unlock(&dl_b->lock);
+ }
return;
}
@@ -948,10 +954,16 @@ static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
rq = task_rq_lock(p, &rf);
if (!dl_task(p) || p->state == TASK_DEAD) {
+ struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
+
if (p->state == TASK_DEAD && dl_se->dl_non_contending) {
sub_running_bw(p->dl.dl_bw, dl_rq_of_se(&p->dl));
dl_se->dl_non_contending = 0;
}
+
+ raw_spin_lock(&dl_b->lock);
+ __dl_clear(dl_b, p->dl.dl_bw);
+ raw_spin_unlock(&dl_b->lock);
__dl_clear_params(p);
goto unlock;
@@ -1473,15 +1485,6 @@ static void task_fork_dl(struct task_struct *p)
static void task_dead_dl(struct task_struct *p)
{
- struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
-
- /*
- * Since we are TASK_DEAD we won't slip out of the domain!
- */
- raw_spin_lock_irq(&dl_b->lock);
- /* XXX we should retain the bw until 0-lag */
- dl_b->total_bw -= p->dl.dl_bw;
- raw_spin_unlock_irq(&dl_b->lock);
}
static void set_curr_task_dl(struct rq *rq)
--
2.7.4
[toc] | [prev] | [standalone]
Page 2 of 2 — ← Prev page 1 [2]
Back to top | Article view | linux.kernel
csiph-web