* [PATCH 0/3 v3] sched/rt: track rt rq utilization
@ 2017-11-22 14:35 Vincent Guittot
2017-11-22 14:35 ` [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file Vincent Guittot
` (2 more replies)
0 siblings, 3 replies; 7+ messages in thread
From: Vincent Guittot @ 2017-11-22 14:35 UTC (permalink / raw)
To: peterz, mingo, linux-kernel, rjw
Cc: juri.lelli, dietmar.eggemann, Morten.Rasmussen, viresh.kumar,
Vincent Guittot
When both cfs and rt tasks compete to run on a CPU, we can see some frequency
drops with schedutil governor. In such case, the cfs_rq's utilization doesn't
reflect anymore the utilization of cfs tasks but only the remaining part that
is not used by rt tasks. We should monitor the stolen utilization and take
it into account when selecting OPP.
Pathc 1 move pelt code in pelt.c file
Patch 2 tracks utilization of rt_rq.
Patch 3 adds the rt_rq's utilization when selection OPP for cfs tasks
This patchset doesn't change the OPP selection policy for RT tasks
Change since v2:
- move pelt code into a dedicated pelt.c file
- rebase on load tracking changes
Change since v1:
- Only a rebase. I have addressed the comments on previous version in
patch 1/2
Vincent Guittot (3):
sched/pelt: Move pelt related code in a dedicated file
sched/rt: add rt_rq utilization tracking
cpufreq/schedutil: add rt utilization tracking
kernel/sched/Makefile | 2 +-
kernel/sched/cpufreq_schedutil.c | 2 +-
kernel/sched/fair.c | 310 +-----------------------------------
kernel/sched/pelt.c | 331 +++++++++++++++++++++++++++++++++++++++
kernel/sched/pelt.h | 24 +++
kernel/sched/rt.c | 9 ++
kernel/sched/sched.h | 21 +++
7 files changed, 390 insertions(+), 309 deletions(-)
create mode 100644 kernel/sched/pelt.c
create mode 100644 kernel/sched/pelt.h
--
2.7.4
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file
2017-11-22 14:35 [PATCH 0/3 v3] sched/rt: track rt rq utilization Vincent Guittot
@ 2017-11-22 14:35 ` Vincent Guittot
2017-12-11 14:08 ` Quentin Perret
2017-11-22 14:35 ` [PATCH v3 2/3] sched/rt: add rt_rq utilization tracking Vincent Guittot
2017-11-22 14:35 ` [PATCH 3/3] cpufreq/schedutil: add rt " Vincent Guittot
2 siblings, 1 reply; 7+ messages in thread
From: Vincent Guittot @ 2017-11-22 14:35 UTC (permalink / raw)
To: peterz, mingo, linux-kernel, rjw
Cc: juri.lelli, dietmar.eggemann, Morten.Rasmussen, viresh.kumar,
Vincent Guittot
We want to track rt_rq's utilization as a part of the estimation of the
whole rq's utilization. This is necessary because rt tasks can steal
utilization to cfs tasks and make them lighter than they are.
As we want to use the same load tracking mecanism for both and prevent
useless dependency between cfs and rt code, pelt code is moved in a
dedicated file.
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
kernel/sched/Makefile | 2 +-
kernel/sched/fair.c | 308 +-------------------------------------------------
kernel/sched/pelt.c | 308 ++++++++++++++++++++++++++++++++++++++++++++++++++
kernel/sched/pelt.h | 17 +++
kernel/sched/sched.h | 20 ++++
5 files changed, 347 insertions(+), 308 deletions(-)
create mode 100644 kernel/sched/pelt.c
create mode 100644 kernel/sched/pelt.h
diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
index e2f9d4f..5a6d1c1 100644
--- a/kernel/sched/Makefile
+++ b/kernel/sched/Makefile
@@ -19,7 +19,7 @@ endif
obj-y += core.o loadavg.o clock.o cputime.o
obj-y += idle_task.o fair.o rt.o deadline.o
obj-y += wait.o wait_bit.o swait.o completion.o idle.o
-obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o
+obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o pelt.o
obj-$(CONFIG_SCHED_AUTOGROUP) += autogroup.o
obj-$(CONFIG_SCHEDSTATS) += stats.o
obj-$(CONFIG_SCHED_DEBUG) += debug.o
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 0989676..b88550e 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -270,9 +270,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
return cfs_rq->rq;
}
-/* An entity is a task if it doesn't "own" a runqueue */
-#define entity_is_task(se) (!se->my_q)
-
static inline struct task_struct *task_of(struct sched_entity *se)
{
SCHED_WARN_ON(!entity_is_task(se));
@@ -434,7 +431,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
return container_of(cfs_rq, struct rq, cfs);
}
-#define entity_is_task(se) 1
#define for_each_sched_entity(se) \
for (; se; se = NULL)
@@ -707,7 +703,7 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
}
#ifdef CONFIG_SMP
-
+#include "pelt.h"
#include "sched-pelt.h"
static int select_idle_sibling(struct task_struct *p, int prev_cpu, int cpu);
@@ -2723,19 +2719,6 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
} while (0)
#ifdef CONFIG_SMP
-/*
- * XXX we want to get rid of these helpers and use the full load resolution.
- */
-static inline long se_weight(struct sched_entity *se)
-{
- return scale_load_down(se->load.weight);
-}
-
-static inline long se_runnable(struct sched_entity *se)
-{
- return scale_load_down(se->runnable_weight);
-}
-
static inline void
enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
@@ -3038,289 +3021,6 @@ static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq)
}
#ifdef CONFIG_SMP
-/*
- * Approximate:
- * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
- */
-static u64 decay_load(u64 val, u64 n)
-{
- unsigned int local_n;
-
- if (unlikely(n > LOAD_AVG_PERIOD * 63))
- return 0;
-
- /* after bounds checking we can collapse to 32-bit */
- local_n = n;
-
- /*
- * As y^PERIOD = 1/2, we can combine
- * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
- * With a look-up table which covers y^n (n<PERIOD)
- *
- * To achieve constant time decay_load.
- */
- if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
- val >>= local_n / LOAD_AVG_PERIOD;
- local_n %= LOAD_AVG_PERIOD;
- }
-
- val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
- return val;
-}
-
-static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
-{
- u32 c1, c2, c3 = d3; /* y^0 == 1 */
-
- /*
- * c1 = d1 y^p
- */
- c1 = decay_load((u64)d1, periods);
-
- /*
- * p-1
- * c2 = 1024 \Sum y^n
- * n=1
- *
- * inf inf
- * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
- * n=0 n=p
- */
- c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
-
- return c1 + c2 + c3;
-}
-
-#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
-
-/*
- * Accumulate the three separate parts of the sum; d1 the remainder
- * of the last (incomplete) period, d2 the span of full periods and d3
- * the remainder of the (incomplete) current period.
- *
- * d1 d2 d3
- * ^ ^ ^
- * | | |
- * |<->|<----------------->|<--->|
- * ... |---x---|------| ... |------|-----x (now)
- *
- * p-1
- * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
- * n=1
- *
- * = u y^p + (Step 1)
- *
- * p-1
- * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
- * n=1
- */
-static __always_inline u32
-accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
- unsigned long load, unsigned long runnable, int running)
-{
- unsigned long scale_freq, scale_cpu;
- u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
- u64 periods;
-
- scale_freq = arch_scale_freq_capacity(NULL, cpu);
- scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
-
- delta += sa->period_contrib;
- periods = delta / 1024; /* A period is 1024us (~1ms) */
-
- /*
- * Step 1: decay old *_sum if we crossed period boundaries.
- */
- if (periods) {
- sa->load_sum = decay_load(sa->load_sum, periods);
- sa->runnable_load_sum =
- decay_load(sa->runnable_load_sum, periods);
- sa->util_sum = decay_load((u64)(sa->util_sum), periods);
-
- /*
- * Step 2
- */
- delta %= 1024;
- contrib = __accumulate_pelt_segments(periods,
- 1024 - sa->period_contrib, delta);
- }
- sa->period_contrib = delta;
-
- contrib = cap_scale(contrib, scale_freq);
- if (load)
- sa->load_sum += load * contrib;
- if (runnable)
- sa->runnable_load_sum += runnable * contrib;
- if (running)
- sa->util_sum += contrib * scale_cpu;
-
- return periods;
-}
-
-/*
- * We can represent the historical contribution to runnable average as the
- * coefficients of a geometric series. To do this we sub-divide our runnable
- * history into segments of approximately 1ms (1024us); label the segment that
- * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
- *
- * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
- * p0 p1 p2
- * (now) (~1ms ago) (~2ms ago)
- *
- * Let u_i denote the fraction of p_i that the entity was runnable.
- *
- * We then designate the fractions u_i as our co-efficients, yielding the
- * following representation of historical load:
- * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
- *
- * We choose y based on the with of a reasonably scheduling period, fixing:
- * y^32 = 0.5
- *
- * This means that the contribution to load ~32ms ago (u_32) will be weighted
- * approximately half as much as the contribution to load within the last ms
- * (u_0).
- *
- * When a period "rolls over" and we have new u_0`, multiplying the previous
- * sum again by y is sufficient to update:
- * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
- * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
- */
-static __always_inline int
-___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
- unsigned long load, unsigned long runnable, int running)
-{
- u64 delta;
-
- delta = now - sa->last_update_time;
- /*
- * This should only happen when time goes backwards, which it
- * unfortunately does during sched clock init when we swap over to TSC.
- */
- if ((s64)delta < 0) {
- sa->last_update_time = now;
- return 0;
- }
-
- /*
- * Use 1024ns as the unit of measurement since it's a reasonable
- * approximation of 1us and fast to compute.
- */
- delta >>= 10;
- if (!delta)
- return 0;
-
- sa->last_update_time += delta << 10;
-
- /*
- * running is a subset of runnable (weight) so running can't be set if
- * runnable is clear. But there are some corner cases where the current
- * se has been already dequeued but cfs_rq->curr still points to it.
- * This means that weight will be 0 but not running for a sched_entity
- * but also for a cfs_rq if the latter becomes idle. As an example,
- * this happens during idle_balance() which calls
- * update_blocked_averages()
- */
- if (!load)
- runnable = running = 0;
-
- /*
- * Now we know we crossed measurement unit boundaries. The *_avg
- * accrues by two steps:
- *
- * Step 1: accumulate *_sum since last_update_time. If we haven't
- * crossed period boundaries, finish.
- */
- if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
- return 0;
-
- return 1;
-}
-
-static __always_inline void
-___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
-{
- u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
-
- /*
- * Step 2: update *_avg.
- */
- sa->load_avg = div_u64(load * sa->load_sum, divider);
- sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
- sa->util_avg = sa->util_sum / divider;
-}
-
-/*
- * sched_entity:
- *
- * task:
- * se_runnable() == se_weight()
- *
- * group: [ see update_cfs_group() ]
- * se_weight() = tg->weight * grq->load_avg / tg->load_avg
- * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
- *
- * load_sum := runnable_sum
- * load_avg = se_weight(se) * runnable_avg
- *
- * runnable_load_sum := runnable_sum
- * runnable_load_avg = se_runnable(se) * runnable_avg
- *
- * XXX collapse load_sum and runnable_load_sum
- *
- * cfq_rs:
- *
- * load_sum = \Sum se_weight(se) * se->avg.load_sum
- * load_avg = \Sum se->avg.load_avg
- *
- * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
- * runnable_load_avg = \Sum se->avg.runable_load_avg
- */
-
-static int
-__update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
-{
- if (entity_is_task(se))
- se->runnable_weight = se->load.weight;
-
- if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
- ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
- return 1;
- }
-
- return 0;
-}
-
-static int
-__update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
-{
- if (entity_is_task(se))
- se->runnable_weight = se->load.weight;
-
- if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
- cfs_rq->curr == se)) {
-
- ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
- return 1;
- }
-
- return 0;
-}
-
-static int
-__update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
-{
- if (___update_load_sum(now, cpu, &cfs_rq->avg,
- scale_load_down(cfs_rq->load.weight),
- scale_load_down(cfs_rq->runnable_weight),
- cfs_rq->curr != NULL)) {
-
- ___update_load_avg(&cfs_rq->avg, 1, 1);
- return 1;
- }
-
- return 0;
-}
-
#ifdef CONFIG_FAIR_GROUP_SCHED
/**
* update_tg_load_avg - update the tg's load avg
@@ -3831,12 +3531,6 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf);
#else /* CONFIG_SMP */
-static inline int
-update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
-{
- return 0;
-}
-
#define UPDATE_TG 0x0
#define SKIP_AGE_LOAD 0x0
#define DO_ATTACH 0x0
diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
new file mode 100644
index 0000000..da6d84f
--- /dev/null
+++ b/kernel/sched/pelt.c
@@ -0,0 +1,308 @@
+/*
+ * Per Entity Load Tracking
+ *
+ * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
+ *
+ * Interactivity improvements by Mike Galbraith
+ * (C) 2007 Mike Galbraith <efault@gmx.de>
+ *
+ * Various enhancements by Dmitry Adamushko.
+ * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
+ *
+ * Group scheduling enhancements by Srivatsa Vaddagiri
+ * Copyright IBM Corporation, 2007
+ * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
+ *
+ * Scaled math optimizations by Thomas Gleixner
+ * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
+ *
+ * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
+ * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
+ *
+ * Move PELT related code from fair.c into this pelt.c file
+ * Author: Vincent Guittot <vincent.guittot@linaro.org>
+ */
+
+#include <linux/sched.h>
+#include "sched.h"
+#include "sched-pelt.h"
+
+/*
+ * Approximate:
+ * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
+ */
+static u64 decay_load(u64 val, u64 n)
+{
+ unsigned int local_n;
+
+ if (unlikely(n > LOAD_AVG_PERIOD * 63))
+ return 0;
+
+ /* after bounds checking we can collapse to 32-bit */
+ local_n = n;
+
+ /*
+ * As y^PERIOD = 1/2, we can combine
+ * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
+ * With a look-up table which covers y^n (n<PERIOD)
+ *
+ * To achieve constant time decay_load.
+ */
+ if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
+ val >>= local_n / LOAD_AVG_PERIOD;
+ local_n %= LOAD_AVG_PERIOD;
+ }
+
+ val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
+ return val;
+}
+
+static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
+{
+ u32 c1, c2, c3 = d3; /* y^0 == 1 */
+
+ /*
+ * c1 = d1 y^p
+ */
+ c1 = decay_load((u64)d1, periods);
+
+ /*
+ * p-1
+ * c2 = 1024 \Sum y^n
+ * n=1
+ *
+ * inf inf
+ * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
+ * n=0 n=p
+ */
+ c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
+
+ return c1 + c2 + c3;
+}
+
+#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
+
+/*
+ * Accumulate the three separate parts of the sum; d1 the remainder
+ * of the last (incomplete) period, d2 the span of full periods and d3
+ * the remainder of the (incomplete) current period.
+ *
+ * d1 d2 d3
+ * ^ ^ ^
+ * | | |
+ * |<->|<----------------->|<--->|
+ * ... |---x---|------| ... |------|-----x (now)
+ *
+ * p-1
+ * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
+ * n=1
+ *
+ * = u y^p + (Step 1)
+ *
+ * p-1
+ * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
+ * n=1
+ */
+static __always_inline u32
+accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
+ unsigned long load, unsigned long runnable, int running)
+{
+ unsigned long scale_freq, scale_cpu;
+ u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
+ u64 periods;
+
+ scale_freq = arch_scale_freq_capacity(NULL, cpu);
+ scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
+
+ delta += sa->period_contrib;
+ periods = delta / 1024; /* A period is 1024us (~1ms) */
+
+ /*
+ * Step 1: decay old *_sum if we crossed period boundaries.
+ */
+ if (periods) {
+ sa->load_sum = decay_load(sa->load_sum, periods);
+ sa->runnable_load_sum =
+ decay_load(sa->runnable_load_sum, periods);
+ sa->util_sum = decay_load((u64)(sa->util_sum), periods);
+
+ /*
+ * Step 2
+ */
+ delta %= 1024;
+ contrib = __accumulate_pelt_segments(periods,
+ 1024 - sa->period_contrib, delta);
+ }
+ sa->period_contrib = delta;
+
+ contrib = cap_scale(contrib, scale_freq);
+ if (load)
+ sa->load_sum += load * contrib;
+ if (runnable)
+ sa->runnable_load_sum += runnable * contrib;
+ if (running)
+ sa->util_sum += contrib * scale_cpu;
+
+ return periods;
+}
+
+/*
+ * We can represent the historical contribution to runnable average as the
+ * coefficients of a geometric series. To do this we sub-divide our runnable
+ * history into segments of approximately 1ms (1024us); label the segment that
+ * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
+ *
+ * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
+ * p0 p1 p2
+ * (now) (~1ms ago) (~2ms ago)
+ *
+ * Let u_i denote the fraction of p_i that the entity was runnable.
+ *
+ * We then designate the fractions u_i as our co-efficients, yielding the
+ * following representation of historical load:
+ * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
+ *
+ * We choose y based on the with of a reasonably scheduling period, fixing:
+ * y^32 = 0.5
+ *
+ * This means that the contribution to load ~32ms ago (u_32) will be weighted
+ * approximately half as much as the contribution to load within the last ms
+ * (u_0).
+ *
+ * When a period "rolls over" and we have new u_0`, multiplying the previous
+ * sum again by y is sufficient to update:
+ * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
+ * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
+ */
+static __always_inline int
+___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
+ unsigned long load, unsigned long runnable, int running)
+{
+ u64 delta;
+
+ delta = now - sa->last_update_time;
+ /*
+ * This should only happen when time goes backwards, which it
+ * unfortunately does during sched clock init when we swap over to TSC.
+ */
+ if ((s64)delta < 0) {
+ sa->last_update_time = now;
+ return 0;
+ }
+
+ /*
+ * Use 1024ns as the unit of measurement since it's a reasonable
+ * approximation of 1us and fast to compute.
+ */
+ delta >>= 10;
+ if (!delta)
+ return 0;
+
+ sa->last_update_time += delta << 10;
+
+ /*
+ * running is a subset of runnable (weight) so running can't be set if
+ * runnable is clear. But there are some corner cases where the current
+ * se has been already dequeued but cfs_rq->curr still points to it.
+ * This means that weight will be 0 but not running for a sched_entity
+ * but also for a cfs_rq if the latter becomes idle. As an example,
+ * this happens during idle_balance() which calls
+ * update_blocked_averages()
+ */
+ if (!load)
+ runnable = running = 0;
+
+ /*
+ * Now we know we crossed measurement unit boundaries. The *_avg
+ * accrues by two steps:
+ *
+ * Step 1: accumulate *_sum since last_update_time. If we haven't
+ * crossed period boundaries, finish.
+ */
+ if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
+ return 0;
+
+ return 1;
+}
+
+static __always_inline void
+___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
+{
+ u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
+
+ /*
+ * Step 2: update *_avg.
+ */
+ sa->load_avg = div_u64(load * sa->load_sum, divider);
+ sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
+ sa->util_avg = sa->util_sum / divider;
+}
+
+/*
+ * sched_entity:
+ *
+ * task:
+ * se_runnable() == se_weight()
+ *
+ * group: [ see update_cfs_group() ]
+ * se_weight() = tg->weight * grq->load_avg / tg->load_avg
+ * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
+ *
+ * load_sum := runnable_sum
+ * load_avg = se_weight(se) * runnable_avg
+ *
+ * runnable_load_sum := runnable_sum
+ * runnable_load_avg = se_runnable(se) * runnable_avg
+ *
+ * XXX collapse load_sum and runnable_load_sum
+ *
+ * cfq_rs:
+ *
+ * load_sum = \Sum se_weight(se) * se->avg.load_sum
+ * load_avg = \Sum se->avg.load_avg
+ *
+ * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
+ * runnable_load_avg = \Sum se->avg.runable_load_avg
+ */
+
+int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
+{
+ if (entity_is_task(se))
+ se->runnable_weight = se->load.weight;
+
+ if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
+ ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
+ return 1;
+ }
+
+ return 0;
+}
+
+int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+ if (entity_is_task(se))
+ se->runnable_weight = se->load.weight;
+
+ if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
+ cfs_rq->curr == se)) {
+
+ ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
+ return 1;
+ }
+
+ return 0;
+}
+
+int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
+{
+ if (___update_load_sum(now, cpu, &cfs_rq->avg,
+ scale_load_down(cfs_rq->load.weight),
+ scale_load_down(cfs_rq->runnable_weight),
+ cfs_rq->curr != NULL)) {
+
+ ___update_load_avg(&cfs_rq->avg, 1, 1);
+ return 1;
+ }
+
+ return 0;
+}
diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
new file mode 100644
index 0000000..c312d8c
--- /dev/null
+++ b/kernel/sched/pelt.h
@@ -0,0 +1,17 @@
+#ifdef CONFIG_SMP
+
+int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se);
+int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se);
+int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq);
+
+#else
+
+static inline int
+update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
+{
+ return 0;
+}
+
+#endif
+
+
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 45ab0bf..6fefef6 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -528,6 +528,7 @@ struct rt_rq {
unsigned long rt_nr_total;
int overloaded;
struct plist_head pushable_tasks;
+
#endif /* CONFIG_SMP */
int rt_queued;
@@ -602,7 +603,26 @@ struct dl_rq {
u64 bw_ratio;
};
+#ifdef CONFIG_FAIR_GROUP_SCHED
+/* An entity is a task if it doesn't "own" a runqueue */
+#define entity_is_task(se) (!se->my_q)
+#else
+#define entity_is_task(se) 1
+#endif
+
#ifdef CONFIG_SMP
+/*
+ * XXX we want to get rid of these helpers and use the full load resolution.
+ */
+static inline long se_weight(struct sched_entity *se)
+{
+ return scale_load_down(se->load.weight);
+}
+
+static inline long se_runnable(struct sched_entity *se)
+{
+ return scale_load_down(se->runnable_weight);
+}
static inline bool sched_asym_prefer(int a, int b)
{
--
2.7.4
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v3 2/3] sched/rt: add rt_rq utilization tracking
2017-11-22 14:35 [PATCH 0/3 v3] sched/rt: track rt rq utilization Vincent Guittot
2017-11-22 14:35 ` [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file Vincent Guittot
@ 2017-11-22 14:35 ` Vincent Guittot
2017-11-22 14:35 ` [PATCH 3/3] cpufreq/schedutil: add rt " Vincent Guittot
2 siblings, 0 replies; 7+ messages in thread
From: Vincent Guittot @ 2017-11-22 14:35 UTC (permalink / raw)
To: peterz, mingo, linux-kernel, rjw
Cc: juri.lelli, dietmar.eggemann, Morten.Rasmussen, viresh.kumar,
Vincent Guittot
schedutil governor relies on cfs_rq's util_avg to choose the OPP when cfs
tasks are running. When the CPU is overloaded by cfs and rt tasks, cfs tasks
are preempted by rt tasks and in this case util_avg reflects the remaining
capacity that is used by cfs task but not what cfs want to use. In such case,
schedutil can select a lower OPP whereas the CPU is overloaded. In order to
have a more accurate view of the utilization of the CPU, we track
the utilization that is "stolen" by RT tasks.
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
kernel/sched/fair.c | 2 ++
kernel/sched/pelt.c | 23 +++++++++++++++++++++++
kernel/sched/pelt.h | 7 +++++++
kernel/sched/rt.c | 9 +++++++++
kernel/sched/sched.h | 1 +
5 files changed, 42 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index b88550e..57d486a 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7029,6 +7029,7 @@ static void update_blocked_averages(int cpu)
if (cfs_rq_is_decayed(cfs_rq))
list_del_leaf_cfs_rq(cfs_rq);
}
+ update_rt_rq_load_avg(rq_clock_task(rq), cpu, &rq->rt, 0);
rq_unlock_irqrestore(rq, &rf);
}
@@ -7088,6 +7089,7 @@ static inline void update_blocked_averages(int cpu)
rq_lock_irqsave(rq, &rf);
update_rq_clock(rq);
update_cfs_rq_load_avg(cfs_rq_clock_task(cfs_rq), cfs_rq);
+ update_rt_rq_load_avg(rq_clock_task(rq), cpu, &rq->rt, 0);
rq_unlock_irqrestore(rq, &rf);
}
diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
index da6d84f..c8b5d23 100644
--- a/kernel/sched/pelt.c
+++ b/kernel/sched/pelt.c
@@ -306,3 +306,26 @@ int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
return 0;
}
+
+/*
+ * rt_rq:
+ *
+ * util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked
+ * util_sum = cpu_scale * load_sum
+ * runnable_load_sum = load_sum
+ *
+ */
+
+int update_rt_rq_load_avg(u64 now, int cpu, struct rt_rq *rt_rq, int running)
+{
+ if (___update_load_sum(now, cpu, &rt_rq->avg,
+ running,
+ running,
+ running)) {
+
+ ___update_load_avg(&rt_rq->avg, 1, 1);
+ return 1;
+ }
+
+ return 0;
+}
diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
index c312d8c..78a2107 100644
--- a/kernel/sched/pelt.h
+++ b/kernel/sched/pelt.h
@@ -3,6 +3,7 @@
int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se);
int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se);
int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq);
+int update_rt_rq_load_avg(u64 now, int cpu, struct rt_rq *rt_rq, int running);
#else
@@ -12,6 +13,12 @@ update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
return 0;
}
+static inline int
+update_rt_rq_load_avg(u64 now, int cpu, struct rt_rq *rt_rq, int running)
+{
+ return 0;
+}
+
#endif
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index d8c43d7..2ddcc27 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -9,6 +9,8 @@
#include <linux/slab.h>
#include <linux/irq_work.h>
+#include "pelt.h"
+
int sched_rr_timeslice = RR_TIMESLICE;
int sysctl_sched_rr_timeslice = (MSEC_PER_SEC / HZ) * RR_TIMESLICE;
@@ -1569,6 +1571,10 @@ pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
queue_push_tasks(rq);
+ if (p)
+ update_rt_rq_load_avg(rq_clock_task(rq), cpu_of(rq), rt_rq,
+ rq->curr->sched_class == &rt_sched_class);
+
return p;
}
@@ -1576,6 +1582,8 @@ static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
{
update_curr_rt(rq);
+ update_rt_rq_load_avg(rq_clock_task(rq), cpu_of(rq), &rq->rt, 1);
+
/*
* The previous task needs to be made eligible for pushing
* if it is still active
@@ -2283,6 +2291,7 @@ static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
struct sched_rt_entity *rt_se = &p->rt;
update_curr_rt(rq);
+ update_rt_rq_load_avg(rq_clock_task(rq), cpu_of(rq), &rq->rt, 1);
watchdog(rq, p);
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 6fefef6..c7bd5dd 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -529,6 +529,7 @@ struct rt_rq {
int overloaded;
struct plist_head pushable_tasks;
+ struct sched_avg avg;
#endif /* CONFIG_SMP */
int rt_queued;
--
2.7.4
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH 3/3] cpufreq/schedutil: add rt utilization tracking
2017-11-22 14:35 [PATCH 0/3 v3] sched/rt: track rt rq utilization Vincent Guittot
2017-11-22 14:35 ` [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file Vincent Guittot
2017-11-22 14:35 ` [PATCH v3 2/3] sched/rt: add rt_rq utilization tracking Vincent Guittot
@ 2017-11-22 14:35 ` Vincent Guittot
2 siblings, 0 replies; 7+ messages in thread
From: Vincent Guittot @ 2017-11-22 14:35 UTC (permalink / raw)
To: peterz, mingo, linux-kernel, rjw
Cc: juri.lelli, dietmar.eggemann, Morten.Rasmussen, viresh.kumar,
Vincent Guittot
add both cfs and rt utilization when selecting an OPP as rt can preempt and
steal cfs's running time
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
kernel/sched/cpufreq_schedutil.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/kernel/sched/cpufreq_schedutil.c b/kernel/sched/cpufreq_schedutil.c
index 9209d83..d06a41e 100644
--- a/kernel/sched/cpufreq_schedutil.c
+++ b/kernel/sched/cpufreq_schedutil.c
@@ -183,7 +183,7 @@ static void sugov_get_util(unsigned long *util, unsigned long *max, int cpu)
cfs_max = arch_scale_cpu_capacity(NULL, cpu);
- *util = min(rq->cfs.avg.util_avg, cfs_max);
+ *util = min(rq->cfs.avg.util_avg + rq->rt.avg.util_avg, cfs_max);
*max = cfs_max;
}
--
2.7.4
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file
2017-11-22 14:35 ` [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file Vincent Guittot
@ 2017-12-11 14:08 ` Quentin Perret
2017-12-12 11:21 ` Vincent Guittot
0 siblings, 1 reply; 7+ messages in thread
From: Quentin Perret @ 2017-12-11 14:08 UTC (permalink / raw)
To: Vincent Guittot
Cc: peterz, mingo, linux-kernel, rjw, juri.lelli, dietmar.eggemann,
Morten.Rasmussen, viresh.kumar
Hi Vincent,
Although I agree that moving the PELT code in a dedicated file is
probably the cleanest way to achieve what you want, I was wondering if
you were able no measure any overhead due to moving the __update_load_avg_*()
functions in a different translation unit ? This is introducing function calls
in latency sensitive paths (wakeup for ex) so I'm just wondering what's
the impact in practice.
Thanks,
Quentin
On Wednesday 22 Nov 2017 at 15:35:53 (+0100), Vincent Guittot wrote:
> We want to track rt_rq's utilization as a part of the estimation of the
> whole rq's utilization. This is necessary because rt tasks can steal
> utilization to cfs tasks and make them lighter than they are.
> As we want to use the same load tracking mecanism for both and prevent
> useless dependency between cfs and rt code, pelt code is moved in a
> dedicated file.
>
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
> kernel/sched/Makefile | 2 +-
> kernel/sched/fair.c | 308 +-------------------------------------------------
> kernel/sched/pelt.c | 308 ++++++++++++++++++++++++++++++++++++++++++++++++++
> kernel/sched/pelt.h | 17 +++
> kernel/sched/sched.h | 20 ++++
> 5 files changed, 347 insertions(+), 308 deletions(-)
> create mode 100644 kernel/sched/pelt.c
> create mode 100644 kernel/sched/pelt.h
>
> diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
> index e2f9d4f..5a6d1c1 100644
> --- a/kernel/sched/Makefile
> +++ b/kernel/sched/Makefile
> @@ -19,7 +19,7 @@ endif
> obj-y += core.o loadavg.o clock.o cputime.o
> obj-y += idle_task.o fair.o rt.o deadline.o
> obj-y += wait.o wait_bit.o swait.o completion.o idle.o
> -obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o
> +obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o pelt.o
> obj-$(CONFIG_SCHED_AUTOGROUP) += autogroup.o
> obj-$(CONFIG_SCHEDSTATS) += stats.o
> obj-$(CONFIG_SCHED_DEBUG) += debug.o
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 0989676..b88550e 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -270,9 +270,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
> return cfs_rq->rq;
> }
>
> -/* An entity is a task if it doesn't "own" a runqueue */
> -#define entity_is_task(se) (!se->my_q)
> -
> static inline struct task_struct *task_of(struct sched_entity *se)
> {
> SCHED_WARN_ON(!entity_is_task(se));
> @@ -434,7 +431,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
> return container_of(cfs_rq, struct rq, cfs);
> }
>
> -#define entity_is_task(se) 1
>
> #define for_each_sched_entity(se) \
> for (; se; se = NULL)
> @@ -707,7 +703,7 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
> }
>
> #ifdef CONFIG_SMP
> -
> +#include "pelt.h"
> #include "sched-pelt.h"
>
> static int select_idle_sibling(struct task_struct *p, int prev_cpu, int cpu);
> @@ -2723,19 +2719,6 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
> } while (0)
>
> #ifdef CONFIG_SMP
> -/*
> - * XXX we want to get rid of these helpers and use the full load resolution.
> - */
> -static inline long se_weight(struct sched_entity *se)
> -{
> - return scale_load_down(se->load.weight);
> -}
> -
> -static inline long se_runnable(struct sched_entity *se)
> -{
> - return scale_load_down(se->runnable_weight);
> -}
> -
> static inline void
> enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> @@ -3038,289 +3021,6 @@ static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq)
> }
>
> #ifdef CONFIG_SMP
> -/*
> - * Approximate:
> - * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
> - */
> -static u64 decay_load(u64 val, u64 n)
> -{
> - unsigned int local_n;
> -
> - if (unlikely(n > LOAD_AVG_PERIOD * 63))
> - return 0;
> -
> - /* after bounds checking we can collapse to 32-bit */
> - local_n = n;
> -
> - /*
> - * As y^PERIOD = 1/2, we can combine
> - * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
> - * With a look-up table which covers y^n (n<PERIOD)
> - *
> - * To achieve constant time decay_load.
> - */
> - if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
> - val >>= local_n / LOAD_AVG_PERIOD;
> - local_n %= LOAD_AVG_PERIOD;
> - }
> -
> - val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
> - return val;
> -}
> -
> -static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
> -{
> - u32 c1, c2, c3 = d3; /* y^0 == 1 */
> -
> - /*
> - * c1 = d1 y^p
> - */
> - c1 = decay_load((u64)d1, periods);
> -
> - /*
> - * p-1
> - * c2 = 1024 \Sum y^n
> - * n=1
> - *
> - * inf inf
> - * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
> - * n=0 n=p
> - */
> - c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
> -
> - return c1 + c2 + c3;
> -}
> -
> -#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
> -
> -/*
> - * Accumulate the three separate parts of the sum; d1 the remainder
> - * of the last (incomplete) period, d2 the span of full periods and d3
> - * the remainder of the (incomplete) current period.
> - *
> - * d1 d2 d3
> - * ^ ^ ^
> - * | | |
> - * |<->|<----------------->|<--->|
> - * ... |---x---|------| ... |------|-----x (now)
> - *
> - * p-1
> - * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
> - * n=1
> - *
> - * = u y^p + (Step 1)
> - *
> - * p-1
> - * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
> - * n=1
> - */
> -static __always_inline u32
> -accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
> - unsigned long load, unsigned long runnable, int running)
> -{
> - unsigned long scale_freq, scale_cpu;
> - u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
> - u64 periods;
> -
> - scale_freq = arch_scale_freq_capacity(NULL, cpu);
> - scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
> -
> - delta += sa->period_contrib;
> - periods = delta / 1024; /* A period is 1024us (~1ms) */
> -
> - /*
> - * Step 1: decay old *_sum if we crossed period boundaries.
> - */
> - if (periods) {
> - sa->load_sum = decay_load(sa->load_sum, periods);
> - sa->runnable_load_sum =
> - decay_load(sa->runnable_load_sum, periods);
> - sa->util_sum = decay_load((u64)(sa->util_sum), periods);
> -
> - /*
> - * Step 2
> - */
> - delta %= 1024;
> - contrib = __accumulate_pelt_segments(periods,
> - 1024 - sa->period_contrib, delta);
> - }
> - sa->period_contrib = delta;
> -
> - contrib = cap_scale(contrib, scale_freq);
> - if (load)
> - sa->load_sum += load * contrib;
> - if (runnable)
> - sa->runnable_load_sum += runnable * contrib;
> - if (running)
> - sa->util_sum += contrib * scale_cpu;
> -
> - return periods;
> -}
> -
> -/*
> - * We can represent the historical contribution to runnable average as the
> - * coefficients of a geometric series. To do this we sub-divide our runnable
> - * history into segments of approximately 1ms (1024us); label the segment that
> - * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
> - *
> - * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
> - * p0 p1 p2
> - * (now) (~1ms ago) (~2ms ago)
> - *
> - * Let u_i denote the fraction of p_i that the entity was runnable.
> - *
> - * We then designate the fractions u_i as our co-efficients, yielding the
> - * following representation of historical load:
> - * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
> - *
> - * We choose y based on the with of a reasonably scheduling period, fixing:
> - * y^32 = 0.5
> - *
> - * This means that the contribution to load ~32ms ago (u_32) will be weighted
> - * approximately half as much as the contribution to load within the last ms
> - * (u_0).
> - *
> - * When a period "rolls over" and we have new u_0`, multiplying the previous
> - * sum again by y is sufficient to update:
> - * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
> - * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
> - */
> -static __always_inline int
> -___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
> - unsigned long load, unsigned long runnable, int running)
> -{
> - u64 delta;
> -
> - delta = now - sa->last_update_time;
> - /*
> - * This should only happen when time goes backwards, which it
> - * unfortunately does during sched clock init when we swap over to TSC.
> - */
> - if ((s64)delta < 0) {
> - sa->last_update_time = now;
> - return 0;
> - }
> -
> - /*
> - * Use 1024ns as the unit of measurement since it's a reasonable
> - * approximation of 1us and fast to compute.
> - */
> - delta >>= 10;
> - if (!delta)
> - return 0;
> -
> - sa->last_update_time += delta << 10;
> -
> - /*
> - * running is a subset of runnable (weight) so running can't be set if
> - * runnable is clear. But there are some corner cases where the current
> - * se has been already dequeued but cfs_rq->curr still points to it.
> - * This means that weight will be 0 but not running for a sched_entity
> - * but also for a cfs_rq if the latter becomes idle. As an example,
> - * this happens during idle_balance() which calls
> - * update_blocked_averages()
> - */
> - if (!load)
> - runnable = running = 0;
> -
> - /*
> - * Now we know we crossed measurement unit boundaries. The *_avg
> - * accrues by two steps:
> - *
> - * Step 1: accumulate *_sum since last_update_time. If we haven't
> - * crossed period boundaries, finish.
> - */
> - if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
> - return 0;
> -
> - return 1;
> -}
> -
> -static __always_inline void
> -___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
> -{
> - u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
> -
> - /*
> - * Step 2: update *_avg.
> - */
> - sa->load_avg = div_u64(load * sa->load_sum, divider);
> - sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
> - sa->util_avg = sa->util_sum / divider;
> -}
> -
> -/*
> - * sched_entity:
> - *
> - * task:
> - * se_runnable() == se_weight()
> - *
> - * group: [ see update_cfs_group() ]
> - * se_weight() = tg->weight * grq->load_avg / tg->load_avg
> - * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
> - *
> - * load_sum := runnable_sum
> - * load_avg = se_weight(se) * runnable_avg
> - *
> - * runnable_load_sum := runnable_sum
> - * runnable_load_avg = se_runnable(se) * runnable_avg
> - *
> - * XXX collapse load_sum and runnable_load_sum
> - *
> - * cfq_rs:
> - *
> - * load_sum = \Sum se_weight(se) * se->avg.load_sum
> - * load_avg = \Sum se->avg.load_avg
> - *
> - * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
> - * runnable_load_avg = \Sum se->avg.runable_load_avg
> - */
> -
> -static int
> -__update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
> -{
> - if (entity_is_task(se))
> - se->runnable_weight = se->load.weight;
> -
> - if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> - return 1;
> - }
> -
> - return 0;
> -}
> -
> -static int
> -__update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
> -{
> - if (entity_is_task(se))
> - se->runnable_weight = se->load.weight;
> -
> - if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
> - cfs_rq->curr == se)) {
> -
> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> - return 1;
> - }
> -
> - return 0;
> -}
> -
> -static int
> -__update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
> -{
> - if (___update_load_sum(now, cpu, &cfs_rq->avg,
> - scale_load_down(cfs_rq->load.weight),
> - scale_load_down(cfs_rq->runnable_weight),
> - cfs_rq->curr != NULL)) {
> -
> - ___update_load_avg(&cfs_rq->avg, 1, 1);
> - return 1;
> - }
> -
> - return 0;
> -}
> -
> #ifdef CONFIG_FAIR_GROUP_SCHED
> /**
> * update_tg_load_avg - update the tg's load avg
> @@ -3831,12 +3531,6 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf);
>
> #else /* CONFIG_SMP */
>
> -static inline int
> -update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
> -{
> - return 0;
> -}
> -
> #define UPDATE_TG 0x0
> #define SKIP_AGE_LOAD 0x0
> #define DO_ATTACH 0x0
> diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
> new file mode 100644
> index 0000000..da6d84f
> --- /dev/null
> +++ b/kernel/sched/pelt.c
> @@ -0,0 +1,308 @@
> +/*
> + * Per Entity Load Tracking
> + *
> + * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
> + *
> + * Interactivity improvements by Mike Galbraith
> + * (C) 2007 Mike Galbraith <efault@gmx.de>
> + *
> + * Various enhancements by Dmitry Adamushko.
> + * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
> + *
> + * Group scheduling enhancements by Srivatsa Vaddagiri
> + * Copyright IBM Corporation, 2007
> + * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
> + *
> + * Scaled math optimizations by Thomas Gleixner
> + * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
> + *
> + * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
> + * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
> + *
> + * Move PELT related code from fair.c into this pelt.c file
> + * Author: Vincent Guittot <vincent.guittot@linaro.org>
> + */
> +
> +#include <linux/sched.h>
> +#include "sched.h"
> +#include "sched-pelt.h"
> +
> +/*
> + * Approximate:
> + * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
> + */
> +static u64 decay_load(u64 val, u64 n)
> +{
> + unsigned int local_n;
> +
> + if (unlikely(n > LOAD_AVG_PERIOD * 63))
> + return 0;
> +
> + /* after bounds checking we can collapse to 32-bit */
> + local_n = n;
> +
> + /*
> + * As y^PERIOD = 1/2, we can combine
> + * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
> + * With a look-up table which covers y^n (n<PERIOD)
> + *
> + * To achieve constant time decay_load.
> + */
> + if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
> + val >>= local_n / LOAD_AVG_PERIOD;
> + local_n %= LOAD_AVG_PERIOD;
> + }
> +
> + val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
> + return val;
> +}
> +
> +static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
> +{
> + u32 c1, c2, c3 = d3; /* y^0 == 1 */
> +
> + /*
> + * c1 = d1 y^p
> + */
> + c1 = decay_load((u64)d1, periods);
> +
> + /*
> + * p-1
> + * c2 = 1024 \Sum y^n
> + * n=1
> + *
> + * inf inf
> + * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
> + * n=0 n=p
> + */
> + c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
> +
> + return c1 + c2 + c3;
> +}
> +
> +#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
> +
> +/*
> + * Accumulate the three separate parts of the sum; d1 the remainder
> + * of the last (incomplete) period, d2 the span of full periods and d3
> + * the remainder of the (incomplete) current period.
> + *
> + * d1 d2 d3
> + * ^ ^ ^
> + * | | |
> + * |<->|<----------------->|<--->|
> + * ... |---x---|------| ... |------|-----x (now)
> + *
> + * p-1
> + * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
> + * n=1
> + *
> + * = u y^p + (Step 1)
> + *
> + * p-1
> + * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
> + * n=1
> + */
> +static __always_inline u32
> +accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
> + unsigned long load, unsigned long runnable, int running)
> +{
> + unsigned long scale_freq, scale_cpu;
> + u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
> + u64 periods;
> +
> + scale_freq = arch_scale_freq_capacity(NULL, cpu);
> + scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
> +
> + delta += sa->period_contrib;
> + periods = delta / 1024; /* A period is 1024us (~1ms) */
> +
> + /*
> + * Step 1: decay old *_sum if we crossed period boundaries.
> + */
> + if (periods) {
> + sa->load_sum = decay_load(sa->load_sum, periods);
> + sa->runnable_load_sum =
> + decay_load(sa->runnable_load_sum, periods);
> + sa->util_sum = decay_load((u64)(sa->util_sum), periods);
> +
> + /*
> + * Step 2
> + */
> + delta %= 1024;
> + contrib = __accumulate_pelt_segments(periods,
> + 1024 - sa->period_contrib, delta);
> + }
> + sa->period_contrib = delta;
> +
> + contrib = cap_scale(contrib, scale_freq);
> + if (load)
> + sa->load_sum += load * contrib;
> + if (runnable)
> + sa->runnable_load_sum += runnable * contrib;
> + if (running)
> + sa->util_sum += contrib * scale_cpu;
> +
> + return periods;
> +}
> +
> +/*
> + * We can represent the historical contribution to runnable average as the
> + * coefficients of a geometric series. To do this we sub-divide our runnable
> + * history into segments of approximately 1ms (1024us); label the segment that
> + * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
> + *
> + * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
> + * p0 p1 p2
> + * (now) (~1ms ago) (~2ms ago)
> + *
> + * Let u_i denote the fraction of p_i that the entity was runnable.
> + *
> + * We then designate the fractions u_i as our co-efficients, yielding the
> + * following representation of historical load:
> + * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
> + *
> + * We choose y based on the with of a reasonably scheduling period, fixing:
> + * y^32 = 0.5
> + *
> + * This means that the contribution to load ~32ms ago (u_32) will be weighted
> + * approximately half as much as the contribution to load within the last ms
> + * (u_0).
> + *
> + * When a period "rolls over" and we have new u_0`, multiplying the previous
> + * sum again by y is sufficient to update:
> + * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
> + * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
> + */
> +static __always_inline int
> +___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
> + unsigned long load, unsigned long runnable, int running)
> +{
> + u64 delta;
> +
> + delta = now - sa->last_update_time;
> + /*
> + * This should only happen when time goes backwards, which it
> + * unfortunately does during sched clock init when we swap over to TSC.
> + */
> + if ((s64)delta < 0) {
> + sa->last_update_time = now;
> + return 0;
> + }
> +
> + /*
> + * Use 1024ns as the unit of measurement since it's a reasonable
> + * approximation of 1us and fast to compute.
> + */
> + delta >>= 10;
> + if (!delta)
> + return 0;
> +
> + sa->last_update_time += delta << 10;
> +
> + /*
> + * running is a subset of runnable (weight) so running can't be set if
> + * runnable is clear. But there are some corner cases where the current
> + * se has been already dequeued but cfs_rq->curr still points to it.
> + * This means that weight will be 0 but not running for a sched_entity
> + * but also for a cfs_rq if the latter becomes idle. As an example,
> + * this happens during idle_balance() which calls
> + * update_blocked_averages()
> + */
> + if (!load)
> + runnable = running = 0;
> +
> + /*
> + * Now we know we crossed measurement unit boundaries. The *_avg
> + * accrues by two steps:
> + *
> + * Step 1: accumulate *_sum since last_update_time. If we haven't
> + * crossed period boundaries, finish.
> + */
> + if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
> + return 0;
> +
> + return 1;
> +}
> +
> +static __always_inline void
> +___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
> +{
> + u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
> +
> + /*
> + * Step 2: update *_avg.
> + */
> + sa->load_avg = div_u64(load * sa->load_sum, divider);
> + sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
> + sa->util_avg = sa->util_sum / divider;
> +}
> +
> +/*
> + * sched_entity:
> + *
> + * task:
> + * se_runnable() == se_weight()
> + *
> + * group: [ see update_cfs_group() ]
> + * se_weight() = tg->weight * grq->load_avg / tg->load_avg
> + * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
> + *
> + * load_sum := runnable_sum
> + * load_avg = se_weight(se) * runnable_avg
> + *
> + * runnable_load_sum := runnable_sum
> + * runnable_load_avg = se_runnable(se) * runnable_avg
> + *
> + * XXX collapse load_sum and runnable_load_sum
> + *
> + * cfq_rs:
> + *
> + * load_sum = \Sum se_weight(se) * se->avg.load_sum
> + * load_avg = \Sum se->avg.load_avg
> + *
> + * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
> + * runnable_load_avg = \Sum se->avg.runable_load_avg
> + */
> +
> +int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
> +{
> + if (entity_is_task(se))
> + se->runnable_weight = se->load.weight;
> +
> + if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
> + ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> + return 1;
> + }
> +
> + return 0;
> +}
> +
> +int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
> +{
> + if (entity_is_task(se))
> + se->runnable_weight = se->load.weight;
> +
> + if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
> + cfs_rq->curr == se)) {
> +
> + ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> + return 1;
> + }
> +
> + return 0;
> +}
> +
> +int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
> +{
> + if (___update_load_sum(now, cpu, &cfs_rq->avg,
> + scale_load_down(cfs_rq->load.weight),
> + scale_load_down(cfs_rq->runnable_weight),
> + cfs_rq->curr != NULL)) {
> +
> + ___update_load_avg(&cfs_rq->avg, 1, 1);
> + return 1;
> + }
> +
> + return 0;
> +}
> diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
> new file mode 100644
> index 0000000..c312d8c
> --- /dev/null
> +++ b/kernel/sched/pelt.h
> @@ -0,0 +1,17 @@
> +#ifdef CONFIG_SMP
> +
> +int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se);
> +int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se);
> +int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq);
> +
> +#else
> +
> +static inline int
> +update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
> +{
> + return 0;
> +}
> +
> +#endif
> +
> +
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 45ab0bf..6fefef6 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -528,6 +528,7 @@ struct rt_rq {
> unsigned long rt_nr_total;
> int overloaded;
> struct plist_head pushable_tasks;
> +
> #endif /* CONFIG_SMP */
> int rt_queued;
>
> @@ -602,7 +603,26 @@ struct dl_rq {
> u64 bw_ratio;
> };
>
> +#ifdef CONFIG_FAIR_GROUP_SCHED
> +/* An entity is a task if it doesn't "own" a runqueue */
> +#define entity_is_task(se) (!se->my_q)
> +#else
> +#define entity_is_task(se) 1
> +#endif
> +
> #ifdef CONFIG_SMP
> +/*
> + * XXX we want to get rid of these helpers and use the full load resolution.
> + */
> +static inline long se_weight(struct sched_entity *se)
> +{
> + return scale_load_down(se->load.weight);
> +}
> +
> +static inline long se_runnable(struct sched_entity *se)
> +{
> + return scale_load_down(se->runnable_weight);
> +}
>
> static inline bool sched_asym_prefer(int a, int b)
> {
> --
> 2.7.4
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file
2017-12-11 14:08 ` Quentin Perret
@ 2017-12-12 11:21 ` Vincent Guittot
2017-12-12 12:35 ` Quentin Perret
0 siblings, 1 reply; 7+ messages in thread
From: Vincent Guittot @ 2017-12-12 11:21 UTC (permalink / raw)
To: Quentin Perret
Cc: Peter Zijlstra, Ingo Molnar, linux-kernel, rjw, Juri Lelli,
Dietmar Eggemann, Morten Rasmussen, viresh kumar
Hi Quentin,
On 11 December 2017 at 15:08, Quentin Perret <quentin.perret@arm.com> wrote:
> Hi Vincent,
>
> Although I agree that moving the PELT code in a dedicated file is
> probably the cleanest way to achieve what you want, I was wondering if
> you were able no measure any overhead due to moving the __update_load_avg_*()
> functions in a different translation unit ? This is introducing function calls
> in latency sensitive paths (wakeup for ex) so I'm just wondering what's
> the impact in practice.
To answer your question, I haven't seen any performance difference
with perf bench sched pipe on a hikey board with the patchset
Then, where do you think that this will explicitly introduce function
call ? It's not obvious for me that the patch that moves pelt code,
will generate such changes. size vmlinux gives me the exact same
results with and without the patch that moves pelt code.
size vmlinux of latest tip/sched/core sha1 a555e9d86ee3
$ size vmlinux
text data bss dec hex filename
10677259 5931388 402104 17010751 103903f vmlinux_orig
size vmlinux with patch 1 rebased on latest tip/sched/core
$ size vmlinux
text data bss dec hex filename
10677259 5931388 402104 17010751 103903f vmlinux_patch_rt
>
> Thanks,
> Quentin
>
> On Wednesday 22 Nov 2017 at 15:35:53 (+0100), Vincent Guittot wrote:
>> We want to track rt_rq's utilization as a part of the estimation of the
>> whole rq's utilization. This is necessary because rt tasks can steal
>> utilization to cfs tasks and make them lighter than they are.
>> As we want to use the same load tracking mecanism for both and prevent
>> useless dependency between cfs and rt code, pelt code is moved in a
>> dedicated file.
>>
>> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
>> ---
>> kernel/sched/Makefile | 2 +-
>> kernel/sched/fair.c | 308 +-------------------------------------------------
>> kernel/sched/pelt.c | 308 ++++++++++++++++++++++++++++++++++++++++++++++++++
>> kernel/sched/pelt.h | 17 +++
>> kernel/sched/sched.h | 20 ++++
>> 5 files changed, 347 insertions(+), 308 deletions(-)
>> create mode 100644 kernel/sched/pelt.c
>> create mode 100644 kernel/sched/pelt.h
>>
>> diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
>> index e2f9d4f..5a6d1c1 100644
>> --- a/kernel/sched/Makefile
>> +++ b/kernel/sched/Makefile
>> @@ -19,7 +19,7 @@ endif
>> obj-y += core.o loadavg.o clock.o cputime.o
>> obj-y += idle_task.o fair.o rt.o deadline.o
>> obj-y += wait.o wait_bit.o swait.o completion.o idle.o
>> -obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o
>> +obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o pelt.o
>> obj-$(CONFIG_SCHED_AUTOGROUP) += autogroup.o
>> obj-$(CONFIG_SCHEDSTATS) += stats.o
>> obj-$(CONFIG_SCHED_DEBUG) += debug.o
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index 0989676..b88550e 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -270,9 +270,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
>> return cfs_rq->rq;
>> }
>>
>> -/* An entity is a task if it doesn't "own" a runqueue */
>> -#define entity_is_task(se) (!se->my_q)
>> -
>> static inline struct task_struct *task_of(struct sched_entity *se)
>> {
>> SCHED_WARN_ON(!entity_is_task(se));
>> @@ -434,7 +431,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
>> return container_of(cfs_rq, struct rq, cfs);
>> }
>>
>> -#define entity_is_task(se) 1
>>
>> #define for_each_sched_entity(se) \
>> for (; se; se = NULL)
>> @@ -707,7 +703,7 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
>> }
>>
>> #ifdef CONFIG_SMP
>> -
>> +#include "pelt.h"
>> #include "sched-pelt.h"
>>
>> static int select_idle_sibling(struct task_struct *p, int prev_cpu, int cpu);
>> @@ -2723,19 +2719,6 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
>> } while (0)
>>
>> #ifdef CONFIG_SMP
>> -/*
>> - * XXX we want to get rid of these helpers and use the full load resolution.
>> - */
>> -static inline long se_weight(struct sched_entity *se)
>> -{
>> - return scale_load_down(se->load.weight);
>> -}
>> -
>> -static inline long se_runnable(struct sched_entity *se)
>> -{
>> - return scale_load_down(se->runnable_weight);
>> -}
>> -
>> static inline void
>> enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
>> {
>> @@ -3038,289 +3021,6 @@ static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq)
>> }
>>
>> #ifdef CONFIG_SMP
>> -/*
>> - * Approximate:
>> - * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
>> - */
>> -static u64 decay_load(u64 val, u64 n)
>> -{
>> - unsigned int local_n;
>> -
>> - if (unlikely(n > LOAD_AVG_PERIOD * 63))
>> - return 0;
>> -
>> - /* after bounds checking we can collapse to 32-bit */
>> - local_n = n;
>> -
>> - /*
>> - * As y^PERIOD = 1/2, we can combine
>> - * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
>> - * With a look-up table which covers y^n (n<PERIOD)
>> - *
>> - * To achieve constant time decay_load.
>> - */
>> - if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
>> - val >>= local_n / LOAD_AVG_PERIOD;
>> - local_n %= LOAD_AVG_PERIOD;
>> - }
>> -
>> - val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
>> - return val;
>> -}
>> -
>> -static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
>> -{
>> - u32 c1, c2, c3 = d3; /* y^0 == 1 */
>> -
>> - /*
>> - * c1 = d1 y^p
>> - */
>> - c1 = decay_load((u64)d1, periods);
>> -
>> - /*
>> - * p-1
>> - * c2 = 1024 \Sum y^n
>> - * n=1
>> - *
>> - * inf inf
>> - * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
>> - * n=0 n=p
>> - */
>> - c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
>> -
>> - return c1 + c2 + c3;
>> -}
>> -
>> -#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
>> -
>> -/*
>> - * Accumulate the three separate parts of the sum; d1 the remainder
>> - * of the last (incomplete) period, d2 the span of full periods and d3
>> - * the remainder of the (incomplete) current period.
>> - *
>> - * d1 d2 d3
>> - * ^ ^ ^
>> - * | | |
>> - * |<->|<----------------->|<--->|
>> - * ... |---x---|------| ... |------|-----x (now)
>> - *
>> - * p-1
>> - * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
>> - * n=1
>> - *
>> - * = u y^p + (Step 1)
>> - *
>> - * p-1
>> - * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
>> - * n=1
>> - */
>> -static __always_inline u32
>> -accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
>> - unsigned long load, unsigned long runnable, int running)
>> -{
>> - unsigned long scale_freq, scale_cpu;
>> - u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
>> - u64 periods;
>> -
>> - scale_freq = arch_scale_freq_capacity(NULL, cpu);
>> - scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
>> -
>> - delta += sa->period_contrib;
>> - periods = delta / 1024; /* A period is 1024us (~1ms) */
>> -
>> - /*
>> - * Step 1: decay old *_sum if we crossed period boundaries.
>> - */
>> - if (periods) {
>> - sa->load_sum = decay_load(sa->load_sum, periods);
>> - sa->runnable_load_sum =
>> - decay_load(sa->runnable_load_sum, periods);
>> - sa->util_sum = decay_load((u64)(sa->util_sum), periods);
>> -
>> - /*
>> - * Step 2
>> - */
>> - delta %= 1024;
>> - contrib = __accumulate_pelt_segments(periods,
>> - 1024 - sa->period_contrib, delta);
>> - }
>> - sa->period_contrib = delta;
>> -
>> - contrib = cap_scale(contrib, scale_freq);
>> - if (load)
>> - sa->load_sum += load * contrib;
>> - if (runnable)
>> - sa->runnable_load_sum += runnable * contrib;
>> - if (running)
>> - sa->util_sum += contrib * scale_cpu;
>> -
>> - return periods;
>> -}
>> -
>> -/*
>> - * We can represent the historical contribution to runnable average as the
>> - * coefficients of a geometric series. To do this we sub-divide our runnable
>> - * history into segments of approximately 1ms (1024us); label the segment that
>> - * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
>> - *
>> - * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
>> - * p0 p1 p2
>> - * (now) (~1ms ago) (~2ms ago)
>> - *
>> - * Let u_i denote the fraction of p_i that the entity was runnable.
>> - *
>> - * We then designate the fractions u_i as our co-efficients, yielding the
>> - * following representation of historical load:
>> - * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
>> - *
>> - * We choose y based on the with of a reasonably scheduling period, fixing:
>> - * y^32 = 0.5
>> - *
>> - * This means that the contribution to load ~32ms ago (u_32) will be weighted
>> - * approximately half as much as the contribution to load within the last ms
>> - * (u_0).
>> - *
>> - * When a period "rolls over" and we have new u_0`, multiplying the previous
>> - * sum again by y is sufficient to update:
>> - * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
>> - * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
>> - */
>> -static __always_inline int
>> -___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
>> - unsigned long load, unsigned long runnable, int running)
>> -{
>> - u64 delta;
>> -
>> - delta = now - sa->last_update_time;
>> - /*
>> - * This should only happen when time goes backwards, which it
>> - * unfortunately does during sched clock init when we swap over to TSC.
>> - */
>> - if ((s64)delta < 0) {
>> - sa->last_update_time = now;
>> - return 0;
>> - }
>> -
>> - /*
>> - * Use 1024ns as the unit of measurement since it's a reasonable
>> - * approximation of 1us and fast to compute.
>> - */
>> - delta >>= 10;
>> - if (!delta)
>> - return 0;
>> -
>> - sa->last_update_time += delta << 10;
>> -
>> - /*
>> - * running is a subset of runnable (weight) so running can't be set if
>> - * runnable is clear. But there are some corner cases where the current
>> - * se has been already dequeued but cfs_rq->curr still points to it.
>> - * This means that weight will be 0 but not running for a sched_entity
>> - * but also for a cfs_rq if the latter becomes idle. As an example,
>> - * this happens during idle_balance() which calls
>> - * update_blocked_averages()
>> - */
>> - if (!load)
>> - runnable = running = 0;
>> -
>> - /*
>> - * Now we know we crossed measurement unit boundaries. The *_avg
>> - * accrues by two steps:
>> - *
>> - * Step 1: accumulate *_sum since last_update_time. If we haven't
>> - * crossed period boundaries, finish.
>> - */
>> - if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
>> - return 0;
>> -
>> - return 1;
>> -}
>> -
>> -static __always_inline void
>> -___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
>> -{
>> - u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
>> -
>> - /*
>> - * Step 2: update *_avg.
>> - */
>> - sa->load_avg = div_u64(load * sa->load_sum, divider);
>> - sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
>> - sa->util_avg = sa->util_sum / divider;
>> -}
>> -
>> -/*
>> - * sched_entity:
>> - *
>> - * task:
>> - * se_runnable() == se_weight()
>> - *
>> - * group: [ see update_cfs_group() ]
>> - * se_weight() = tg->weight * grq->load_avg / tg->load_avg
>> - * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
>> - *
>> - * load_sum := runnable_sum
>> - * load_avg = se_weight(se) * runnable_avg
>> - *
>> - * runnable_load_sum := runnable_sum
>> - * runnable_load_avg = se_runnable(se) * runnable_avg
>> - *
>> - * XXX collapse load_sum and runnable_load_sum
>> - *
>> - * cfq_rs:
>> - *
>> - * load_sum = \Sum se_weight(se) * se->avg.load_sum
>> - * load_avg = \Sum se->avg.load_avg
>> - *
>> - * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
>> - * runnable_load_avg = \Sum se->avg.runable_load_avg
>> - */
>> -
>> -static int
>> -__update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
>> -{
>> - if (entity_is_task(se))
>> - se->runnable_weight = se->load.weight;
>> -
>> - if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
>> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
>> - return 1;
>> - }
>> -
>> - return 0;
>> -}
>> -
>> -static int
>> -__update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
>> -{
>> - if (entity_is_task(se))
>> - se->runnable_weight = se->load.weight;
>> -
>> - if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
>> - cfs_rq->curr == se)) {
>> -
>> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
>> - return 1;
>> - }
>> -
>> - return 0;
>> -}
>> -
>> -static int
>> -__update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
>> -{
>> - if (___update_load_sum(now, cpu, &cfs_rq->avg,
>> - scale_load_down(cfs_rq->load.weight),
>> - scale_load_down(cfs_rq->runnable_weight),
>> - cfs_rq->curr != NULL)) {
>> -
>> - ___update_load_avg(&cfs_rq->avg, 1, 1);
>> - return 1;
>> - }
>> -
>> - return 0;
>> -}
>> -
>> #ifdef CONFIG_FAIR_GROUP_SCHED
>> /**
>> * update_tg_load_avg - update the tg's load avg
>> @@ -3831,12 +3531,6 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf);
>>
>> #else /* CONFIG_SMP */
>>
>> -static inline int
>> -update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
>> -{
>> - return 0;
>> -}
>> -
>> #define UPDATE_TG 0x0
>> #define SKIP_AGE_LOAD 0x0
>> #define DO_ATTACH 0x0
>> diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
>> new file mode 100644
>> index 0000000..da6d84f
>> --- /dev/null
>> +++ b/kernel/sched/pelt.c
>> @@ -0,0 +1,308 @@
>> +/*
>> + * Per Entity Load Tracking
>> + *
>> + * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
>> + *
>> + * Interactivity improvements by Mike Galbraith
>> + * (C) 2007 Mike Galbraith <efault@gmx.de>
>> + *
>> + * Various enhancements by Dmitry Adamushko.
>> + * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
>> + *
>> + * Group scheduling enhancements by Srivatsa Vaddagiri
>> + * Copyright IBM Corporation, 2007
>> + * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
>> + *
>> + * Scaled math optimizations by Thomas Gleixner
>> + * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
>> + *
>> + * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
>> + * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
>> + *
>> + * Move PELT related code from fair.c into this pelt.c file
>> + * Author: Vincent Guittot <vincent.guittot@linaro.org>
>> + */
>> +
>> +#include <linux/sched.h>
>> +#include "sched.h"
>> +#include "sched-pelt.h"
>> +
>> +/*
>> + * Approximate:
>> + * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
>> + */
>> +static u64 decay_load(u64 val, u64 n)
>> +{
>> + unsigned int local_n;
>> +
>> + if (unlikely(n > LOAD_AVG_PERIOD * 63))
>> + return 0;
>> +
>> + /* after bounds checking we can collapse to 32-bit */
>> + local_n = n;
>> +
>> + /*
>> + * As y^PERIOD = 1/2, we can combine
>> + * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
>> + * With a look-up table which covers y^n (n<PERIOD)
>> + *
>> + * To achieve constant time decay_load.
>> + */
>> + if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
>> + val >>= local_n / LOAD_AVG_PERIOD;
>> + local_n %= LOAD_AVG_PERIOD;
>> + }
>> +
>> + val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
>> + return val;
>> +}
>> +
>> +static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
>> +{
>> + u32 c1, c2, c3 = d3; /* y^0 == 1 */
>> +
>> + /*
>> + * c1 = d1 y^p
>> + */
>> + c1 = decay_load((u64)d1, periods);
>> +
>> + /*
>> + * p-1
>> + * c2 = 1024 \Sum y^n
>> + * n=1
>> + *
>> + * inf inf
>> + * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
>> + * n=0 n=p
>> + */
>> + c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
>> +
>> + return c1 + c2 + c3;
>> +}
>> +
>> +#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
>> +
>> +/*
>> + * Accumulate the three separate parts of the sum; d1 the remainder
>> + * of the last (incomplete) period, d2 the span of full periods and d3
>> + * the remainder of the (incomplete) current period.
>> + *
>> + * d1 d2 d3
>> + * ^ ^ ^
>> + * | | |
>> + * |<->|<----------------->|<--->|
>> + * ... |---x---|------| ... |------|-----x (now)
>> + *
>> + * p-1
>> + * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
>> + * n=1
>> + *
>> + * = u y^p + (Step 1)
>> + *
>> + * p-1
>> + * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
>> + * n=1
>> + */
>> +static __always_inline u32
>> +accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
>> + unsigned long load, unsigned long runnable, int running)
>> +{
>> + unsigned long scale_freq, scale_cpu;
>> + u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
>> + u64 periods;
>> +
>> + scale_freq = arch_scale_freq_capacity(NULL, cpu);
>> + scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
>> +
>> + delta += sa->period_contrib;
>> + periods = delta / 1024; /* A period is 1024us (~1ms) */
>> +
>> + /*
>> + * Step 1: decay old *_sum if we crossed period boundaries.
>> + */
>> + if (periods) {
>> + sa->load_sum = decay_load(sa->load_sum, periods);
>> + sa->runnable_load_sum =
>> + decay_load(sa->runnable_load_sum, periods);
>> + sa->util_sum = decay_load((u64)(sa->util_sum), periods);
>> +
>> + /*
>> + * Step 2
>> + */
>> + delta %= 1024;
>> + contrib = __accumulate_pelt_segments(periods,
>> + 1024 - sa->period_contrib, delta);
>> + }
>> + sa->period_contrib = delta;
>> +
>> + contrib = cap_scale(contrib, scale_freq);
>> + if (load)
>> + sa->load_sum += load * contrib;
>> + if (runnable)
>> + sa->runnable_load_sum += runnable * contrib;
>> + if (running)
>> + sa->util_sum += contrib * scale_cpu;
>> +
>> + return periods;
>> +}
>> +
>> +/*
>> + * We can represent the historical contribution to runnable average as the
>> + * coefficients of a geometric series. To do this we sub-divide our runnable
>> + * history into segments of approximately 1ms (1024us); label the segment that
>> + * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
>> + *
>> + * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
>> + * p0 p1 p2
>> + * (now) (~1ms ago) (~2ms ago)
>> + *
>> + * Let u_i denote the fraction of p_i that the entity was runnable.
>> + *
>> + * We then designate the fractions u_i as our co-efficients, yielding the
>> + * following representation of historical load:
>> + * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
>> + *
>> + * We choose y based on the with of a reasonably scheduling period, fixing:
>> + * y^32 = 0.5
>> + *
>> + * This means that the contribution to load ~32ms ago (u_32) will be weighted
>> + * approximately half as much as the contribution to load within the last ms
>> + * (u_0).
>> + *
>> + * When a period "rolls over" and we have new u_0`, multiplying the previous
>> + * sum again by y is sufficient to update:
>> + * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
>> + * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
>> + */
>> +static __always_inline int
>> +___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
>> + unsigned long load, unsigned long runnable, int running)
>> +{
>> + u64 delta;
>> +
>> + delta = now - sa->last_update_time;
>> + /*
>> + * This should only happen when time goes backwards, which it
>> + * unfortunately does during sched clock init when we swap over to TSC.
>> + */
>> + if ((s64)delta < 0) {
>> + sa->last_update_time = now;
>> + return 0;
>> + }
>> +
>> + /*
>> + * Use 1024ns as the unit of measurement since it's a reasonable
>> + * approximation of 1us and fast to compute.
>> + */
>> + delta >>= 10;
>> + if (!delta)
>> + return 0;
>> +
>> + sa->last_update_time += delta << 10;
>> +
>> + /*
>> + * running is a subset of runnable (weight) so running can't be set if
>> + * runnable is clear. But there are some corner cases where the current
>> + * se has been already dequeued but cfs_rq->curr still points to it.
>> + * This means that weight will be 0 but not running for a sched_entity
>> + * but also for a cfs_rq if the latter becomes idle. As an example,
>> + * this happens during idle_balance() which calls
>> + * update_blocked_averages()
>> + */
>> + if (!load)
>> + runnable = running = 0;
>> +
>> + /*
>> + * Now we know we crossed measurement unit boundaries. The *_avg
>> + * accrues by two steps:
>> + *
>> + * Step 1: accumulate *_sum since last_update_time. If we haven't
>> + * crossed period boundaries, finish.
>> + */
>> + if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
>> + return 0;
>> +
>> + return 1;
>> +}
>> +
>> +static __always_inline void
>> +___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
>> +{
>> + u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
>> +
>> + /*
>> + * Step 2: update *_avg.
>> + */
>> + sa->load_avg = div_u64(load * sa->load_sum, divider);
>> + sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
>> + sa->util_avg = sa->util_sum / divider;
>> +}
>> +
>> +/*
>> + * sched_entity:
>> + *
>> + * task:
>> + * se_runnable() == se_weight()
>> + *
>> + * group: [ see update_cfs_group() ]
>> + * se_weight() = tg->weight * grq->load_avg / tg->load_avg
>> + * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
>> + *
>> + * load_sum := runnable_sum
>> + * load_avg = se_weight(se) * runnable_avg
>> + *
>> + * runnable_load_sum := runnable_sum
>> + * runnable_load_avg = se_runnable(se) * runnable_avg
>> + *
>> + * XXX collapse load_sum and runnable_load_sum
>> + *
>> + * cfq_rs:
>> + *
>> + * load_sum = \Sum se_weight(se) * se->avg.load_sum
>> + * load_avg = \Sum se->avg.load_avg
>> + *
>> + * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
>> + * runnable_load_avg = \Sum se->avg.runable_load_avg
>> + */
>> +
>> +int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
>> +{
>> + if (entity_is_task(se))
>> + se->runnable_weight = se->load.weight;
>> +
>> + if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
>> + ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
>> + return 1;
>> + }
>> +
>> + return 0;
>> +}
>> +
>> +int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
>> +{
>> + if (entity_is_task(se))
>> + se->runnable_weight = se->load.weight;
>> +
>> + if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
>> + cfs_rq->curr == se)) {
>> +
>> + ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
>> + return 1;
>> + }
>> +
>> + return 0;
>> +}
>> +
>> +int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
>> +{
>> + if (___update_load_sum(now, cpu, &cfs_rq->avg,
>> + scale_load_down(cfs_rq->load.weight),
>> + scale_load_down(cfs_rq->runnable_weight),
>> + cfs_rq->curr != NULL)) {
>> +
>> + ___update_load_avg(&cfs_rq->avg, 1, 1);
>> + return 1;
>> + }
>> +
>> + return 0;
>> +}
>> diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
>> new file mode 100644
>> index 0000000..c312d8c
>> --- /dev/null
>> +++ b/kernel/sched/pelt.h
>> @@ -0,0 +1,17 @@
>> +#ifdef CONFIG_SMP
>> +
>> +int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se);
>> +int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se);
>> +int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq);
>> +
>> +#else
>> +
>> +static inline int
>> +update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
>> +{
>> + return 0;
>> +}
>> +
>> +#endif
>> +
>> +
>> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
>> index 45ab0bf..6fefef6 100644
>> --- a/kernel/sched/sched.h
>> +++ b/kernel/sched/sched.h
>> @@ -528,6 +528,7 @@ struct rt_rq {
>> unsigned long rt_nr_total;
>> int overloaded;
>> struct plist_head pushable_tasks;
>> +
>> #endif /* CONFIG_SMP */
>> int rt_queued;
>>
>> @@ -602,7 +603,26 @@ struct dl_rq {
>> u64 bw_ratio;
>> };
>>
>> +#ifdef CONFIG_FAIR_GROUP_SCHED
>> +/* An entity is a task if it doesn't "own" a runqueue */
>> +#define entity_is_task(se) (!se->my_q)
>> +#else
>> +#define entity_is_task(se) 1
>> +#endif
>> +
>> #ifdef CONFIG_SMP
>> +/*
>> + * XXX we want to get rid of these helpers and use the full load resolution.
>> + */
>> +static inline long se_weight(struct sched_entity *se)
>> +{
>> + return scale_load_down(se->load.weight);
>> +}
>> +
>> +static inline long se_runnable(struct sched_entity *se)
>> +{
>> + return scale_load_down(se->runnable_weight);
>> +}
>>
>> static inline bool sched_asym_prefer(int a, int b)
>> {
>> --
>> 2.7.4
>>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file
2017-12-12 11:21 ` Vincent Guittot
@ 2017-12-12 12:35 ` Quentin Perret
0 siblings, 0 replies; 7+ messages in thread
From: Quentin Perret @ 2017-12-12 12:35 UTC (permalink / raw)
To: Vincent Guittot
Cc: Peter Zijlstra, Ingo Molnar, linux-kernel, rjw, Juri Lelli,
Dietmar Eggemann, Morten Rasmussen, viresh kumar
On Tuesday 12 Dec 2017 at 12:21:39 (+0100), Vincent Guittot wrote:
> Hi Quentin,
>
> On 11 December 2017 at 15:08, Quentin Perret <quentin.perret@arm.com> wrote:
> > Hi Vincent,
> >
> > Although I agree that moving the PELT code in a dedicated file is
> > probably the cleanest way to achieve what you want, I was wondering if
> > you were able no measure any overhead due to moving the __update_load_avg_*()
> > functions in a different translation unit ? This is introducing function calls
> > in latency sensitive paths (wakeup for ex) so I'm just wondering what's
> > the impact in practice.
>
> To answer your question, I haven't seen any performance difference
> with perf bench sched pipe on a hikey board with the patchset
> Then, where do you think that this will explicitly introduce function
> call ?
For example, without the patch, __update_load_avg_blocked_se() was static
and the compiler had the opportunity to inline it where appropriate. With
the patch, the function is now in a different translation unit so I think
an actual function call is always needed. I'm not saying it's a big deal,
I was just wondering if that might have a noticeable impact.
The only alternative I see is to put the rt rq load update functions in
fair.c but that doesn't quiet feel like the right thing to do anyway ...
> It's not obvious for me that the patch that moves pelt code,
> will generate such changes. size vmlinux gives me the exact same
> results with and without the patch that moves pelt code.
> size vmlinux of latest tip/sched/core sha1 a555e9d86ee3
> $ size vmlinux
> text data bss dec hex filename
> 10677259 5931388 402104 17010751 103903f vmlinux_orig
>
> size vmlinux with patch 1 rebased on latest tip/sched/core
> $ size vmlinux
> text data bss dec hex filename
> 10677259 5931388 402104 17010751 103903f vmlinux_patch_rt
>
> >
> > Thanks,
> > Quentin
> >
> > On Wednesday 22 Nov 2017 at 15:35:53 (+0100), Vincent Guittot wrote:
> >> We want to track rt_rq's utilization as a part of the estimation of the
> >> whole rq's utilization. This is necessary because rt tasks can steal
> >> utilization to cfs tasks and make them lighter than they are.
> >> As we want to use the same load tracking mecanism for both and prevent
> >> useless dependency between cfs and rt code, pelt code is moved in a
> >> dedicated file.
> >>
> >> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> >> ---
> >> kernel/sched/Makefile | 2 +-
> >> kernel/sched/fair.c | 308 +-------------------------------------------------
> >> kernel/sched/pelt.c | 308 ++++++++++++++++++++++++++++++++++++++++++++++++++
> >> kernel/sched/pelt.h | 17 +++
> >> kernel/sched/sched.h | 20 ++++
> >> 5 files changed, 347 insertions(+), 308 deletions(-)
> >> create mode 100644 kernel/sched/pelt.c
> >> create mode 100644 kernel/sched/pelt.h
> >>
> >> diff --git a/kernel/sched/Makefile b/kernel/sched/Makefile
> >> index e2f9d4f..5a6d1c1 100644
> >> --- a/kernel/sched/Makefile
> >> +++ b/kernel/sched/Makefile
> >> @@ -19,7 +19,7 @@ endif
> >> obj-y += core.o loadavg.o clock.o cputime.o
> >> obj-y += idle_task.o fair.o rt.o deadline.o
> >> obj-y += wait.o wait_bit.o swait.o completion.o idle.o
> >> -obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o
> >> +obj-$(CONFIG_SMP) += cpupri.o cpudeadline.o topology.o stop_task.o pelt.o
> >> obj-$(CONFIG_SCHED_AUTOGROUP) += autogroup.o
> >> obj-$(CONFIG_SCHEDSTATS) += stats.o
> >> obj-$(CONFIG_SCHED_DEBUG) += debug.o
> >> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> >> index 0989676..b88550e 100644
> >> --- a/kernel/sched/fair.c
> >> +++ b/kernel/sched/fair.c
> >> @@ -270,9 +270,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
> >> return cfs_rq->rq;
> >> }
> >>
> >> -/* An entity is a task if it doesn't "own" a runqueue */
> >> -#define entity_is_task(se) (!se->my_q)
> >> -
> >> static inline struct task_struct *task_of(struct sched_entity *se)
> >> {
> >> SCHED_WARN_ON(!entity_is_task(se));
> >> @@ -434,7 +431,6 @@ static inline struct rq *rq_of(struct cfs_rq *cfs_rq)
> >> return container_of(cfs_rq, struct rq, cfs);
> >> }
> >>
> >> -#define entity_is_task(se) 1
> >>
> >> #define for_each_sched_entity(se) \
> >> for (; se; se = NULL)
> >> @@ -707,7 +703,7 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
> >> }
> >>
> >> #ifdef CONFIG_SMP
> >> -
> >> +#include "pelt.h"
> >> #include "sched-pelt.h"
> >>
> >> static int select_idle_sibling(struct task_struct *p, int prev_cpu, int cpu);
> >> @@ -2723,19 +2719,6 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
> >> } while (0)
> >>
> >> #ifdef CONFIG_SMP
> >> -/*
> >> - * XXX we want to get rid of these helpers and use the full load resolution.
> >> - */
> >> -static inline long se_weight(struct sched_entity *se)
> >> -{
> >> - return scale_load_down(se->load.weight);
> >> -}
> >> -
> >> -static inline long se_runnable(struct sched_entity *se)
> >> -{
> >> - return scale_load_down(se->runnable_weight);
> >> -}
> >> -
> >> static inline void
> >> enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
> >> {
> >> @@ -3038,289 +3021,6 @@ static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq)
> >> }
> >>
> >> #ifdef CONFIG_SMP
> >> -/*
> >> - * Approximate:
> >> - * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
> >> - */
> >> -static u64 decay_load(u64 val, u64 n)
> >> -{
> >> - unsigned int local_n;
> >> -
> >> - if (unlikely(n > LOAD_AVG_PERIOD * 63))
> >> - return 0;
> >> -
> >> - /* after bounds checking we can collapse to 32-bit */
> >> - local_n = n;
> >> -
> >> - /*
> >> - * As y^PERIOD = 1/2, we can combine
> >> - * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
> >> - * With a look-up table which covers y^n (n<PERIOD)
> >> - *
> >> - * To achieve constant time decay_load.
> >> - */
> >> - if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
> >> - val >>= local_n / LOAD_AVG_PERIOD;
> >> - local_n %= LOAD_AVG_PERIOD;
> >> - }
> >> -
> >> - val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
> >> - return val;
> >> -}
> >> -
> >> -static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
> >> -{
> >> - u32 c1, c2, c3 = d3; /* y^0 == 1 */
> >> -
> >> - /*
> >> - * c1 = d1 y^p
> >> - */
> >> - c1 = decay_load((u64)d1, periods);
> >> -
> >> - /*
> >> - * p-1
> >> - * c2 = 1024 \Sum y^n
> >> - * n=1
> >> - *
> >> - * inf inf
> >> - * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
> >> - * n=0 n=p
> >> - */
> >> - c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
> >> -
> >> - return c1 + c2 + c3;
> >> -}
> >> -
> >> -#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
> >> -
> >> -/*
> >> - * Accumulate the three separate parts of the sum; d1 the remainder
> >> - * of the last (incomplete) period, d2 the span of full periods and d3
> >> - * the remainder of the (incomplete) current period.
> >> - *
> >> - * d1 d2 d3
> >> - * ^ ^ ^
> >> - * | | |
> >> - * |<->|<----------------->|<--->|
> >> - * ... |---x---|------| ... |------|-----x (now)
> >> - *
> >> - * p-1
> >> - * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
> >> - * n=1
> >> - *
> >> - * = u y^p + (Step 1)
> >> - *
> >> - * p-1
> >> - * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
> >> - * n=1
> >> - */
> >> -static __always_inline u32
> >> -accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
> >> - unsigned long load, unsigned long runnable, int running)
> >> -{
> >> - unsigned long scale_freq, scale_cpu;
> >> - u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
> >> - u64 periods;
> >> -
> >> - scale_freq = arch_scale_freq_capacity(NULL, cpu);
> >> - scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
> >> -
> >> - delta += sa->period_contrib;
> >> - periods = delta / 1024; /* A period is 1024us (~1ms) */
> >> -
> >> - /*
> >> - * Step 1: decay old *_sum if we crossed period boundaries.
> >> - */
> >> - if (periods) {
> >> - sa->load_sum = decay_load(sa->load_sum, periods);
> >> - sa->runnable_load_sum =
> >> - decay_load(sa->runnable_load_sum, periods);
> >> - sa->util_sum = decay_load((u64)(sa->util_sum), periods);
> >> -
> >> - /*
> >> - * Step 2
> >> - */
> >> - delta %= 1024;
> >> - contrib = __accumulate_pelt_segments(periods,
> >> - 1024 - sa->period_contrib, delta);
> >> - }
> >> - sa->period_contrib = delta;
> >> -
> >> - contrib = cap_scale(contrib, scale_freq);
> >> - if (load)
> >> - sa->load_sum += load * contrib;
> >> - if (runnable)
> >> - sa->runnable_load_sum += runnable * contrib;
> >> - if (running)
> >> - sa->util_sum += contrib * scale_cpu;
> >> -
> >> - return periods;
> >> -}
> >> -
> >> -/*
> >> - * We can represent the historical contribution to runnable average as the
> >> - * coefficients of a geometric series. To do this we sub-divide our runnable
> >> - * history into segments of approximately 1ms (1024us); label the segment that
> >> - * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
> >> - *
> >> - * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
> >> - * p0 p1 p2
> >> - * (now) (~1ms ago) (~2ms ago)
> >> - *
> >> - * Let u_i denote the fraction of p_i that the entity was runnable.
> >> - *
> >> - * We then designate the fractions u_i as our co-efficients, yielding the
> >> - * following representation of historical load:
> >> - * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
> >> - *
> >> - * We choose y based on the with of a reasonably scheduling period, fixing:
> >> - * y^32 = 0.5
> >> - *
> >> - * This means that the contribution to load ~32ms ago (u_32) will be weighted
> >> - * approximately half as much as the contribution to load within the last ms
> >> - * (u_0).
> >> - *
> >> - * When a period "rolls over" and we have new u_0`, multiplying the previous
> >> - * sum again by y is sufficient to update:
> >> - * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
> >> - * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
> >> - */
> >> -static __always_inline int
> >> -___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
> >> - unsigned long load, unsigned long runnable, int running)
> >> -{
> >> - u64 delta;
> >> -
> >> - delta = now - sa->last_update_time;
> >> - /*
> >> - * This should only happen when time goes backwards, which it
> >> - * unfortunately does during sched clock init when we swap over to TSC.
> >> - */
> >> - if ((s64)delta < 0) {
> >> - sa->last_update_time = now;
> >> - return 0;
> >> - }
> >> -
> >> - /*
> >> - * Use 1024ns as the unit of measurement since it's a reasonable
> >> - * approximation of 1us and fast to compute.
> >> - */
> >> - delta >>= 10;
> >> - if (!delta)
> >> - return 0;
> >> -
> >> - sa->last_update_time += delta << 10;
> >> -
> >> - /*
> >> - * running is a subset of runnable (weight) so running can't be set if
> >> - * runnable is clear. But there are some corner cases where the current
> >> - * se has been already dequeued but cfs_rq->curr still points to it.
> >> - * This means that weight will be 0 but not running for a sched_entity
> >> - * but also for a cfs_rq if the latter becomes idle. As an example,
> >> - * this happens during idle_balance() which calls
> >> - * update_blocked_averages()
> >> - */
> >> - if (!load)
> >> - runnable = running = 0;
> >> -
> >> - /*
> >> - * Now we know we crossed measurement unit boundaries. The *_avg
> >> - * accrues by two steps:
> >> - *
> >> - * Step 1: accumulate *_sum since last_update_time. If we haven't
> >> - * crossed period boundaries, finish.
> >> - */
> >> - if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
> >> - return 0;
> >> -
> >> - return 1;
> >> -}
> >> -
> >> -static __always_inline void
> >> -___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
> >> -{
> >> - u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
> >> -
> >> - /*
> >> - * Step 2: update *_avg.
> >> - */
> >> - sa->load_avg = div_u64(load * sa->load_sum, divider);
> >> - sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
> >> - sa->util_avg = sa->util_sum / divider;
> >> -}
> >> -
> >> -/*
> >> - * sched_entity:
> >> - *
> >> - * task:
> >> - * se_runnable() == se_weight()
> >> - *
> >> - * group: [ see update_cfs_group() ]
> >> - * se_weight() = tg->weight * grq->load_avg / tg->load_avg
> >> - * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
> >> - *
> >> - * load_sum := runnable_sum
> >> - * load_avg = se_weight(se) * runnable_avg
> >> - *
> >> - * runnable_load_sum := runnable_sum
> >> - * runnable_load_avg = se_runnable(se) * runnable_avg
> >> - *
> >> - * XXX collapse load_sum and runnable_load_sum
> >> - *
> >> - * cfq_rs:
> >> - *
> >> - * load_sum = \Sum se_weight(se) * se->avg.load_sum
> >> - * load_avg = \Sum se->avg.load_avg
> >> - *
> >> - * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
> >> - * runnable_load_avg = \Sum se->avg.runable_load_avg
> >> - */
> >> -
> >> -static int
> >> -__update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
> >> -{
> >> - if (entity_is_task(se))
> >> - se->runnable_weight = se->load.weight;
> >> -
> >> - if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
> >> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> >> - return 1;
> >> - }
> >> -
> >> - return 0;
> >> -}
> >> -
> >> -static int
> >> -__update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
> >> -{
> >> - if (entity_is_task(se))
> >> - se->runnable_weight = se->load.weight;
> >> -
> >> - if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
> >> - cfs_rq->curr == se)) {
> >> -
> >> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> >> - return 1;
> >> - }
> >> -
> >> - return 0;
> >> -}
> >> -
> >> -static int
> >> -__update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
> >> -{
> >> - if (___update_load_sum(now, cpu, &cfs_rq->avg,
> >> - scale_load_down(cfs_rq->load.weight),
> >> - scale_load_down(cfs_rq->runnable_weight),
> >> - cfs_rq->curr != NULL)) {
> >> -
> >> - ___update_load_avg(&cfs_rq->avg, 1, 1);
> >> - return 1;
> >> - }
> >> -
> >> - return 0;
> >> -}
> >> -
> >> #ifdef CONFIG_FAIR_GROUP_SCHED
> >> /**
> >> * update_tg_load_avg - update the tg's load avg
> >> @@ -3831,12 +3531,6 @@ static int idle_balance(struct rq *this_rq, struct rq_flags *rf);
> >>
> >> #else /* CONFIG_SMP */
> >>
> >> -static inline int
> >> -update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
> >> -{
> >> - return 0;
> >> -}
> >> -
> >> #define UPDATE_TG 0x0
> >> #define SKIP_AGE_LOAD 0x0
> >> #define DO_ATTACH 0x0
> >> diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
> >> new file mode 100644
> >> index 0000000..da6d84f
> >> --- /dev/null
> >> +++ b/kernel/sched/pelt.c
> >> @@ -0,0 +1,308 @@
> >> +/*
> >> + * Per Entity Load Tracking
> >> + *
> >> + * Copyright (C) 2007 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
> >> + *
> >> + * Interactivity improvements by Mike Galbraith
> >> + * (C) 2007 Mike Galbraith <efault@gmx.de>
> >> + *
> >> + * Various enhancements by Dmitry Adamushko.
> >> + * (C) 2007 Dmitry Adamushko <dmitry.adamushko@gmail.com>
> >> + *
> >> + * Group scheduling enhancements by Srivatsa Vaddagiri
> >> + * Copyright IBM Corporation, 2007
> >> + * Author: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
> >> + *
> >> + * Scaled math optimizations by Thomas Gleixner
> >> + * Copyright (C) 2007, Thomas Gleixner <tglx@linutronix.de>
> >> + *
> >> + * Adaptive scheduling granularity, math enhancements by Peter Zijlstra
> >> + * Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra
> >> + *
> >> + * Move PELT related code from fair.c into this pelt.c file
> >> + * Author: Vincent Guittot <vincent.guittot@linaro.org>
> >> + */
> >> +
> >> +#include <linux/sched.h>
> >> +#include "sched.h"
> >> +#include "sched-pelt.h"
> >> +
> >> +/*
> >> + * Approximate:
> >> + * val * y^n, where y^32 ~= 0.5 (~1 scheduling period)
> >> + */
> >> +static u64 decay_load(u64 val, u64 n)
> >> +{
> >> + unsigned int local_n;
> >> +
> >> + if (unlikely(n > LOAD_AVG_PERIOD * 63))
> >> + return 0;
> >> +
> >> + /* after bounds checking we can collapse to 32-bit */
> >> + local_n = n;
> >> +
> >> + /*
> >> + * As y^PERIOD = 1/2, we can combine
> >> + * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
> >> + * With a look-up table which covers y^n (n<PERIOD)
> >> + *
> >> + * To achieve constant time decay_load.
> >> + */
> >> + if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
> >> + val >>= local_n / LOAD_AVG_PERIOD;
> >> + local_n %= LOAD_AVG_PERIOD;
> >> + }
> >> +
> >> + val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
> >> + return val;
> >> +}
> >> +
> >> +static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
> >> +{
> >> + u32 c1, c2, c3 = d3; /* y^0 == 1 */
> >> +
> >> + /*
> >> + * c1 = d1 y^p
> >> + */
> >> + c1 = decay_load((u64)d1, periods);
> >> +
> >> + /*
> >> + * p-1
> >> + * c2 = 1024 \Sum y^n
> >> + * n=1
> >> + *
> >> + * inf inf
> >> + * = 1024 ( \Sum y^n - \Sum y^n - y^0 )
> >> + * n=0 n=p
> >> + */
> >> + c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
> >> +
> >> + return c1 + c2 + c3;
> >> +}
> >> +
> >> +#define cap_scale(v, s) ((v)*(s) >> SCHED_CAPACITY_SHIFT)
> >> +
> >> +/*
> >> + * Accumulate the three separate parts of the sum; d1 the remainder
> >> + * of the last (incomplete) period, d2 the span of full periods and d3
> >> + * the remainder of the (incomplete) current period.
> >> + *
> >> + * d1 d2 d3
> >> + * ^ ^ ^
> >> + * | | |
> >> + * |<->|<----------------->|<--->|
> >> + * ... |---x---|------| ... |------|-----x (now)
> >> + *
> >> + * p-1
> >> + * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
> >> + * n=1
> >> + *
> >> + * = u y^p + (Step 1)
> >> + *
> >> + * p-1
> >> + * d1 y^p + 1024 \Sum y^n + d3 y^0 (Step 2)
> >> + * n=1
> >> + */
> >> +static __always_inline u32
> >> +accumulate_sum(u64 delta, int cpu, struct sched_avg *sa,
> >> + unsigned long load, unsigned long runnable, int running)
> >> +{
> >> + unsigned long scale_freq, scale_cpu;
> >> + u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
> >> + u64 periods;
> >> +
> >> + scale_freq = arch_scale_freq_capacity(NULL, cpu);
> >> + scale_cpu = arch_scale_cpu_capacity(NULL, cpu);
> >> +
> >> + delta += sa->period_contrib;
> >> + periods = delta / 1024; /* A period is 1024us (~1ms) */
> >> +
> >> + /*
> >> + * Step 1: decay old *_sum if we crossed period boundaries.
> >> + */
> >> + if (periods) {
> >> + sa->load_sum = decay_load(sa->load_sum, periods);
> >> + sa->runnable_load_sum =
> >> + decay_load(sa->runnable_load_sum, periods);
> >> + sa->util_sum = decay_load((u64)(sa->util_sum), periods);
> >> +
> >> + /*
> >> + * Step 2
> >> + */
> >> + delta %= 1024;
> >> + contrib = __accumulate_pelt_segments(periods,
> >> + 1024 - sa->period_contrib, delta);
> >> + }
> >> + sa->period_contrib = delta;
> >> +
> >> + contrib = cap_scale(contrib, scale_freq);
> >> + if (load)
> >> + sa->load_sum += load * contrib;
> >> + if (runnable)
> >> + sa->runnable_load_sum += runnable * contrib;
> >> + if (running)
> >> + sa->util_sum += contrib * scale_cpu;
> >> +
> >> + return periods;
> >> +}
> >> +
> >> +/*
> >> + * We can represent the historical contribution to runnable average as the
> >> + * coefficients of a geometric series. To do this we sub-divide our runnable
> >> + * history into segments of approximately 1ms (1024us); label the segment that
> >> + * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
> >> + *
> >> + * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
> >> + * p0 p1 p2
> >> + * (now) (~1ms ago) (~2ms ago)
> >> + *
> >> + * Let u_i denote the fraction of p_i that the entity was runnable.
> >> + *
> >> + * We then designate the fractions u_i as our co-efficients, yielding the
> >> + * following representation of historical load:
> >> + * u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
> >> + *
> >> + * We choose y based on the with of a reasonably scheduling period, fixing:
> >> + * y^32 = 0.5
> >> + *
> >> + * This means that the contribution to load ~32ms ago (u_32) will be weighted
> >> + * approximately half as much as the contribution to load within the last ms
> >> + * (u_0).
> >> + *
> >> + * When a period "rolls over" and we have new u_0`, multiplying the previous
> >> + * sum again by y is sufficient to update:
> >> + * load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
> >> + * = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
> >> + */
> >> +static __always_inline int
> >> +___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
> >> + unsigned long load, unsigned long runnable, int running)
> >> +{
> >> + u64 delta;
> >> +
> >> + delta = now - sa->last_update_time;
> >> + /*
> >> + * This should only happen when time goes backwards, which it
> >> + * unfortunately does during sched clock init when we swap over to TSC.
> >> + */
> >> + if ((s64)delta < 0) {
> >> + sa->last_update_time = now;
> >> + return 0;
> >> + }
> >> +
> >> + /*
> >> + * Use 1024ns as the unit of measurement since it's a reasonable
> >> + * approximation of 1us and fast to compute.
> >> + */
> >> + delta >>= 10;
> >> + if (!delta)
> >> + return 0;
> >> +
> >> + sa->last_update_time += delta << 10;
> >> +
> >> + /*
> >> + * running is a subset of runnable (weight) so running can't be set if
> >> + * runnable is clear. But there are some corner cases where the current
> >> + * se has been already dequeued but cfs_rq->curr still points to it.
> >> + * This means that weight will be 0 but not running for a sched_entity
> >> + * but also for a cfs_rq if the latter becomes idle. As an example,
> >> + * this happens during idle_balance() which calls
> >> + * update_blocked_averages()
> >> + */
> >> + if (!load)
> >> + runnable = running = 0;
> >> +
> >> + /*
> >> + * Now we know we crossed measurement unit boundaries. The *_avg
> >> + * accrues by two steps:
> >> + *
> >> + * Step 1: accumulate *_sum since last_update_time. If we haven't
> >> + * crossed period boundaries, finish.
> >> + */
> >> + if (!accumulate_sum(delta, cpu, sa, load, runnable, running))
> >> + return 0;
> >> +
> >> + return 1;
> >> +}
> >> +
> >> +static __always_inline void
> >> +___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
> >> +{
> >> + u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
> >> +
> >> + /*
> >> + * Step 2: update *_avg.
> >> + */
> >> + sa->load_avg = div_u64(load * sa->load_sum, divider);
> >> + sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
> >> + sa->util_avg = sa->util_sum / divider;
> >> +}
> >> +
> >> +/*
> >> + * sched_entity:
> >> + *
> >> + * task:
> >> + * se_runnable() == se_weight()
> >> + *
> >> + * group: [ see update_cfs_group() ]
> >> + * se_weight() = tg->weight * grq->load_avg / tg->load_avg
> >> + * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
> >> + *
> >> + * load_sum := runnable_sum
> >> + * load_avg = se_weight(se) * runnable_avg
> >> + *
> >> + * runnable_load_sum := runnable_sum
> >> + * runnable_load_avg = se_runnable(se) * runnable_avg
> >> + *
> >> + * XXX collapse load_sum and runnable_load_sum
> >> + *
> >> + * cfq_rs:
> >> + *
> >> + * load_sum = \Sum se_weight(se) * se->avg.load_sum
> >> + * load_avg = \Sum se->avg.load_avg
> >> + *
> >> + * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
> >> + * runnable_load_avg = \Sum se->avg.runable_load_avg
> >> + */
> >> +
> >> +int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
> >> +{
> >> + if (entity_is_task(se))
> >> + se->runnable_weight = se->load.weight;
> >> +
> >> + if (___update_load_sum(now, cpu, &se->avg, 0, 0, 0)) {
> >> + ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> >> + return 1;
> >> + }
> >> +
> >> + return 0;
> >> +}
> >> +
> >> +int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
> >> +{
> >> + if (entity_is_task(se))
> >> + se->runnable_weight = se->load.weight;
> >> +
> >> + if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq, !!se->on_rq,
> >> + cfs_rq->curr == se)) {
> >> +
> >> + ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> >> + return 1;
> >> + }
> >> +
> >> + return 0;
> >> +}
> >> +
> >> +int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
> >> +{
> >> + if (___update_load_sum(now, cpu, &cfs_rq->avg,
> >> + scale_load_down(cfs_rq->load.weight),
> >> + scale_load_down(cfs_rq->runnable_weight),
> >> + cfs_rq->curr != NULL)) {
> >> +
> >> + ___update_load_avg(&cfs_rq->avg, 1, 1);
> >> + return 1;
> >> + }
> >> +
> >> + return 0;
> >> +}
> >> diff --git a/kernel/sched/pelt.h b/kernel/sched/pelt.h
> >> new file mode 100644
> >> index 0000000..c312d8c
> >> --- /dev/null
> >> +++ b/kernel/sched/pelt.h
> >> @@ -0,0 +1,17 @@
> >> +#ifdef CONFIG_SMP
> >> +
> >> +int __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se);
> >> +int __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se);
> >> +int __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq);
> >> +
> >> +#else
> >> +
> >> +static inline int
> >> +update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
> >> +{
> >> + return 0;
> >> +}
> >> +
> >> +#endif
> >> +
> >> +
> >> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> >> index 45ab0bf..6fefef6 100644
> >> --- a/kernel/sched/sched.h
> >> +++ b/kernel/sched/sched.h
> >> @@ -528,6 +528,7 @@ struct rt_rq {
> >> unsigned long rt_nr_total;
> >> int overloaded;
> >> struct plist_head pushable_tasks;
> >> +
> >> #endif /* CONFIG_SMP */
> >> int rt_queued;
> >>
> >> @@ -602,7 +603,26 @@ struct dl_rq {
> >> u64 bw_ratio;
> >> };
> >>
> >> +#ifdef CONFIG_FAIR_GROUP_SCHED
> >> +/* An entity is a task if it doesn't "own" a runqueue */
> >> +#define entity_is_task(se) (!se->my_q)
> >> +#else
> >> +#define entity_is_task(se) 1
> >> +#endif
> >> +
> >> #ifdef CONFIG_SMP
> >> +/*
> >> + * XXX we want to get rid of these helpers and use the full load resolution.
> >> + */
> >> +static inline long se_weight(struct sched_entity *se)
> >> +{
> >> + return scale_load_down(se->load.weight);
> >> +}
> >> +
> >> +static inline long se_runnable(struct sched_entity *se)
> >> +{
> >> + return scale_load_down(se->runnable_weight);
> >> +}
> >>
> >> static inline bool sched_asym_prefer(int a, int b)
> >> {
> >> --
> >> 2.7.4
> >>
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2017-12-12 12:35 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-11-22 14:35 [PATCH 0/3 v3] sched/rt: track rt rq utilization Vincent Guittot
2017-11-22 14:35 ` [PATCH v3 1/3] sched/pelt: Move pelt related code in a dedicated file Vincent Guittot
2017-12-11 14:08 ` Quentin Perret
2017-12-12 11:21 ` Vincent Guittot
2017-12-12 12:35 ` Quentin Perret
2017-11-22 14:35 ` [PATCH v3 2/3] sched/rt: add rt_rq utilization tracking Vincent Guittot
2017-11-22 14:35 ` [PATCH 3/3] cpufreq/schedutil: add rt " Vincent Guittot
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®