Date:	Mon, 12 May 2014 02:16:52 +0800
From:	Yuyang Du <yuyang.du@...el.com>
To:	mingo@...hat.com, peterz@...radead.org, rafael.j.wysocki@...el.com,
	linux-kernel@...r.kernel.org, linux-pm@...r.kernel.org
Cc:	arjan.van.de.ven@...el.com, len.brown@...el.com,
	alan.cox@...el.com, mark.gross@...el.com, morten.rasmussen@....com,
	vincent.guittot@...aro.org, rajeev.d.muralidhar@...el.com,
	vishwesh.m.rudramuni@...el.com, nicole.chalhoub@...el.com,
	ajaya.durg@...el.com, harinarayanan.seshadri@...el.com,
	jacob.jun.pan@...ux.intel.com, fengguang.wu@...el.com,
	yuyang.du@...el.com
Subject: [RFC PATCH 03/12 v2] CPU ConCurrency calculation

It is natural to use task concurrency (running tasks in the rq) as load
indicator. We calculate CC from task concurrency by two steps:

1) Divide continuous time into periods of time, and average task concurrency
in period, for tolerating the transient bursts:

a = sum(concurrency * time) / period

2) Exponentially decay past periods, and synthesize them all, for hysteresis
to load drops or resilience to load rises (let f be decaying factor, and a_x
the xth period average since period 0):

s = a_n + f^1 * a_n-1 + f^2 * a_n-2 +, ..., + f^(n-1) * a_1 + f^n * a_0

Signed-off-by: Yuyang Du <yuyang.du@...el.com>
---
 include/linux/sched/sysctl.h |    8 +
 kernel/sched/concurrency.c   |  344 ++++++++++++++++++++++++++++++++++++++++++
 kernel/sched/sched.h         |    2 +
 kernel/sysctl.c              |   16 ++
 4 files changed, 370 insertions(+)

diff --git a/include/linux/sched/sysctl.h b/include/linux/sched/sysctl.h
index 8045a55..ec52b3f 100644
--- a/include/linux/sched/sysctl.h
+++ b/include/linux/sched/sysctl.h
@@ -36,6 +36,14 @@ extern unsigned int sysctl_sched_min_granularity;
 extern unsigned int sysctl_sched_wakeup_granularity;
 extern unsigned int sysctl_sched_child_runs_first;
 
+#ifdef CONFIG_CPU_CONCURRENCY
+extern unsigned int sysctl_concurrency_sum_period;
+extern unsigned int sysctl_concurrency_decay_rate;
+extern int concurrency_decay_rate_handler(struct ctl_table *table, int write,
+					void __user *buffer,
+					size_t *lenp, loff_t *ppos);
+#endif
+
 enum sched_tunable_scaling {
 	SCHED_TUNABLESCALING_NONE,
 	SCHED_TUNABLESCALING_LOG,
diff --git a/kernel/sched/concurrency.c b/kernel/sched/concurrency.c
index 50e08a2..da26dd7 100644
--- a/kernel/sched/concurrency.c
+++ b/kernel/sched/concurrency.c
@@ -10,6 +10,331 @@
 
 #include "sched.h"
 
+/*
+ * the sum period of time is 2^26 ns (~64) by default
+ */
+unsigned int sysctl_concurrency_sum_period = 26UL;
+
+/*
+ * the number of sum periods, after which the original
+ * will be reduced/decayed to half
+ */
+unsigned int sysctl_concurrency_decay_rate = 1UL;
+
+/*
+ * the contrib period of time is 2^10 (~1us) by default,
+ * us has better precision than ms, and
+ * 1024 makes use of faster shift than div
+ */
+static unsigned int cc_contrib_period = 10UL;
+
+/*
+ * the concurrency is scaled up for decaying,
+ * thus, concurrency 1 is effectively 2^cc_resolution (1024),
+ * which can be halved by 10 half-life periods
+ */
+static unsigned int cc_resolution = 10UL;
+
+/*
+ * after this number of half-life periods, even
+ * (1>>32)-1 (which is sufficiently large) is less than 1
+ */
+static unsigned int cc_decay_max_pds = 32UL;
+
+static inline u32 cc_scale_up(unsigned int c)
+{
+	return c << cc_resolution;
+}
+
+static inline u32 cc_scale_down(unsigned int c)
+{
+	return c >> cc_resolution;
+}
+
+/* from nanoseconds to sum periods */
+static inline u64 cc_sum_pds(u64 n)
+{
+	return n >> sysctl_concurrency_sum_period;
+}
+
+/* from sum period to timestamp in ns */
+static inline u64 cc_timestamp(u64 p)
+{
+	return p << sysctl_concurrency_sum_period;
+}
+
+/*
+ * from nanoseconds to contrib periods, because
+ * ns so risky that can overflow cc->contrib
+ */
+static inline u64 cc_contrib_pds(u64 n)
+{
+	return n >> cc_contrib_period;
+}
+
+/*
+ * cc_decay_factor only works for 32bit integer,
+ * cc_decay_factor_x, x indicates the number of periods
+ * as half-life (sysctl_concurrency_decay_rate)
+ */
+static const u32 cc_decay_factor_1[] = {
+	0xFFFFFFFF,
+};
+
+static const u32 cc_decay_factor_2[] = {
+	0xFFFFFFFF, 0xB504F333,
+};
+
+static const u32 cc_decay_factor_4[] = {
+	0xFFFFFFFF, 0xD744FCCA, 0xB504F333, 0x9837F051,
+};
+
+static const u32 cc_decay_factor_8[] = {
+	0xFFFFFFFF, 0xEAC0C6E7, 0xD744FCCA, 0xC5672A11,
+	0xB504F333, 0xA5FED6A9, 0x9837F051, 0x8B95C1E3,
+};
+
+/* by default sysctl_concurrency_decay_rate */
+static const u32 *cc_decay_factor =
+	cc_decay_factor_1;
+
+/*
+ * cc_decayed_sum depends on cc_resolution (fixed 10),
+ * cc_decayed_sum_x, x indicates the number of periods
+ * as half-life (sysctl_concurrency_decay_rate)
+ */
+static const u32 cc_decayed_sum_1[] = {
+	0, 512, 768, 896, 960, 992,
+	1008, 1016, 1020, 1022, 1023,
+};
+
+static const u32 cc_decayed_sum_2[] = {
+	0, 724, 1235, 1597, 1853, 2034, 2162, 2252,
+	2316, 2361, 2393, 2416, 2432, 2443, 2451,
+	2457, 2461, 2464, 2466, 2467, 2468, 2469,
+};
+
+static const u32 cc_decayed_sum_4[] = {
+	0, 861, 1585, 2193, 2705, 3135, 3497, 3801, 4057,
+	4272, 4453, 4605, 4733, 4840, 4930, 5006, 5070,
+	5124, 5169, 5207, 5239, 5266, 5289, 5308, 5324,
+	5337, 5348, 5358, 5366, 5373, 5379, 5384, 5388,
+	5391, 5394, 5396, 5398, 5400, 5401, 5402, 5403,
+	5404, 5405, 5406,
+};
+
+static const u32 cc_decayed_sum_8[] = {
+	0, 939, 1800, 2589, 3313, 3977, 4585, 5143,
+	5655, 6124, 6554, 6949, 7311, 7643, 7947, 8226,
+	8482, 8717, 8932, 9129, 9310, 9476, 9628, 9767,
+	9895, 10012, 10120, 10219, 10309, 10392, 10468, 10538,
+	10602, 10661, 10715, 10764, 10809, 10850, 10888, 10923,
+	10955, 10984, 11011, 11036, 11059, 11080, 11099, 11116,
+	11132, 11147, 11160, 11172, 11183, 11193, 11203, 11212,
+	11220, 11227, 11234, 11240, 11246, 11251, 11256, 11260,
+	11264, 11268, 11271, 11274, 11277, 11280, 11282, 11284,
+	11286, 11288, 11290, 11291, 11292, 11293, 11294, 11295,
+	11296, 11297, 11298, 11299, 11300, 11301, 11302,
+};
+
+/* by default sysctl_concurrency_decay_rate */
+static const u32 *cc_decayed_sum = cc_decayed_sum_1;
+
+/*
+ * the last index of cc_decayed_sum array
+ */
+static u32 cc_decayed_sum_len =
+	sizeof(cc_decayed_sum_1) / sizeof(cc_decayed_sum_1[0]) - 1;
+
+/*
+ * sysctl handler to update decay rate
+ */
+int concurrency_decay_rate_handler(struct ctl_table *table, int write,
+		void __user *buffer, size_t *lenp, loff_t *ppos)
+{
+	int ret = proc_dointvec(table, write, buffer, lenp, ppos);
+
+	if (ret || !write)
+		return ret;
+
+	switch (sysctl_concurrency_decay_rate) {
+	case 1:
+		cc_decay_factor = cc_decay_factor_1;
+		cc_decayed_sum = cc_decayed_sum_1;
+		cc_decayed_sum_len = sizeof(cc_decayed_sum_1) /
+			sizeof(cc_decayed_sum_1[0]) - 1;
+		break;
+	case 2:
+		cc_decay_factor = cc_decay_factor_2;
+		cc_decayed_sum = cc_decayed_sum_2;
+		cc_decayed_sum_len = sizeof(cc_decayed_sum_2) /
+			sizeof(cc_decayed_sum_2[0]) - 1;
+		break;
+	case 4:
+		cc_decay_factor = cc_decay_factor_4;
+		cc_decayed_sum = cc_decayed_sum_4;
+		cc_decayed_sum_len = sizeof(cc_decayed_sum_4) /
+			sizeof(cc_decayed_sum_4[0]) - 1;
+		break;
+	case 8:
+		cc_decay_factor = cc_decay_factor_8;
+		cc_decayed_sum = cc_decayed_sum_8;
+		cc_decayed_sum_len = sizeof(cc_decayed_sum_8) /
+			sizeof(cc_decayed_sum_8[0]) - 1;
+		break;
+	default:
+		return -EINVAL;
+	}
+
+	cc_decay_max_pds *= sysctl_concurrency_decay_rate;
+
+	return 0;
+}
+
+/*
+ * decay concurrency at some decay rate
+ */
+static inline u64 decay_cc(u64 cc, u64 periods)
+{
+	u32 periods_l;
+
+	if (periods <= 0)
+		return cc;
+
+	if (unlikely(periods >= cc_decay_max_pds))
+		return 0;
+
+	/* now period is not too large */
+	periods_l = (u32)periods;
+	if (periods_l >= sysctl_concurrency_decay_rate) {
+		cc >>= periods_l / sysctl_concurrency_decay_rate;
+		periods_l %= sysctl_concurrency_decay_rate;
+	}
+
+	if (!periods_l)
+		return cc;
+
+	cc *= cc_decay_factor[periods_l];
+
+	return cc >> 32;
+}
+
+/*
+ * add missed periods by predefined constants
+ */
+static inline u64 cc_missed_pds(u64 periods)
+{
+	if (periods <= 0)
+		return 0;
+
+	if (periods > cc_decayed_sum_len)
+		periods = cc_decayed_sum_len;
+
+	return cc_decayed_sum[periods];
+}
+
+/*
+ * scale up nr_running, because we decay
+ */
+static inline u32 cc_weight(unsigned int nr_running)
+{
+	/*
+	 * scaling factor, this should be tunable
+	 */
+	return cc_scale_up(nr_running);
+}
+
+static inline void
+__update_concurrency(struct rq *rq, u64 now, struct cpu_concurrency_t *cc)
+{
+	u64 sum_pds, sum_pds_s, sum_pds_e;
+	u64 contrib_pds, ts_contrib, contrib_pds_one;
+	u64 sum_now = 0;
+	u32 weight;
+	int updated = 0;
+
+	/*
+	 * guarantee contrib_timestamp always >= sum_timestamp,
+	 * and sum_timestamp is at period boundary
+	 */
+	if (now <= cc->sum_timestamp) {
+		cc->sum_timestamp = cc_timestamp(cc_sum_pds(now));
+		cc->contrib_timestamp = now;
+		return;
+	}
+
+	weight = cc_weight(cc->nr_running);
+
+	/* start and end of sum periods */
+	sum_pds_s = cc_sum_pds(cc->sum_timestamp);
+	sum_pds_e = cc_sum_pds(now);
+	sum_pds = sum_pds_e - sum_pds_s;
+	/* number of contrib periods in one sum period */
+	contrib_pds_one = cc_contrib_pds(cc_timestamp(1));
+
+	/*
+	 * if we have passed at least one period,
+	 * we need to do four things:
+	 */
+	if (sum_pds) {
+		/* 1) complete the last period */
+		ts_contrib = cc_timestamp(sum_pds_s + 1);
+		contrib_pds = cc_contrib_pds(ts_contrib);
+		contrib_pds -= cc_contrib_pds(cc->contrib_timestamp);
+
+		if (likely(contrib_pds))
+			cc->contrib += weight * contrib_pds;
+
+		cc->contrib = div64_u64(cc->contrib, contrib_pds_one);
+
+		cc->sum += cc->contrib;
+		cc->contrib = 0;
+
+		/* 2) update/decay them */
+		cc->sum = decay_cc(cc->sum, sum_pds);
+		sum_now = decay_cc(cc->sum, sum_pds - 1);
+
+		/* 3) compensate missed periods if any */
+		sum_pds -= 1;
+		cc->sum += cc->nr_running * cc_missed_pds(sum_pds);
+		sum_now += cc->nr_running * cc_missed_pds(sum_pds - 1);
+		updated = 1;
+
+		/* 4) update contrib timestamp to period boundary */
+		ts_contrib = cc_timestamp(sum_pds_e);
+
+		cc->sum_timestamp = ts_contrib;
+		cc->contrib_timestamp = ts_contrib;
+	}
+
+	/* current period */
+	contrib_pds = cc_contrib_pds(now);
+	contrib_pds -= cc_contrib_pds(cc->contrib_timestamp);
+
+	if (likely(contrib_pds))
+		cc->contrib += weight * contrib_pds;
+
+	/* new nr_running for next update */
+	cc->nr_running = rq->nr_running;
+
+	/*
+	 * we need to account for the current sum period,
+	 * if now has passed 1/2 of sum period, we contribute,
+	 * otherwise, we use the last complete sum period
+	 */
+	contrib_pds = cc_contrib_pds(now - cc->sum_timestamp);
+
+	if (contrib_pds > contrib_pds_one / 2) {
+		sum_now = div64_u64(cc->contrib, contrib_pds);
+		sum_now += cc->sum;
+		updated = 1;
+	}
+
+	if (updated == 1)
+		cc->sum_now = sum_now;
+	cc->contrib_timestamp = now;
+}
+
 void init_cpu_concurrency(struct rq *rq)
 {
 	rq->concurrency.sum = 0;
@@ -19,4 +344,23 @@ void init_cpu_concurrency(struct rq *rq)
 	rq->concurrency.sum_timestamp = ULLONG_MAX;
 	rq->concurrency.contrib_timestamp = ULLONG_MAX;
 }
+
+/*
+ * we update cpu concurrency at:
+ * 1) enqueue task, which increases concurrency
+ * 2) dequeue task, which decreases concurrency
+ * 3) periodic scheduler tick, in case no en/dequeue for long
+ * 4) enter and exit idle
+ */
+void update_cpu_concurrency(struct rq *rq)
+{
+	/*
+	 * protected under rq->lock
+	 */
+	struct cpu_concurrency_t *cc = &rq->concurrency;
+	u64 now = rq->clock;
+
+	__update_concurrency(rq, now, cc);
+}
+
 #endif
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index f1c9235..a4043ed 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1220,8 +1220,10 @@ extern void resched_cpu(int cpu);
 
 #ifdef CONFIG_CPU_CONCURRENCY
 extern void init_cpu_concurrency(struct rq *rq);
+extern void update_cpu_concurrency(struct rq *rq);
 #else
 static inline void init_cpu_concurrency(struct rq *rq) {}
+static inline void update_cpu_concurrency(struct rq *rq) {}
 #endif
 
 extern struct rt_bandwidth def_rt_bandwidth;
diff --git a/kernel/sysctl.c b/kernel/sysctl.c
index 74f5b58..91ba467 100644
--- a/kernel/sysctl.c
+++ b/kernel/sysctl.c
@@ -1090,6 +1090,22 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 #endif
+#ifdef CONFIG_CPU_CONCURRENCY
+	{
+		.procname	= "concurrency_sum_period",
+		.data		= &sysctl_concurrency_sum_period,
+		.maxlen		= sizeof(sysctl_concurrency_sum_period),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+	{
+		.procname	= "concurrency_decay_rate",
+		.data		= &sysctl_concurrency_decay_rate,
+		.maxlen		= sizeof(sysctl_concurrency_decay_rate),
+		.mode		= 0644,
+		.proc_handler	= concurrency_decay_rate_handler,
+	},
+#endif
 	{ }
 };
 
-- 
1.7.9.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists