From: Johannes Weiner <hannes@cmpxchg.org>
To: linux-kernel@vger.kernel.org, linux-mm@kvack.org,
linux-block@vger.kernel.org, cgroups@vger.kernel.org
Cc: Ingo Molnar <mingo@redhat.com>,
Peter Zijlstra <peterz@infradead.org>,
Andrew Morton <akpm@linuxfoundation.org>,
Tejun Heo <tj@kernel.org>, Balbir Singh <bsingharora@gmail.com>,
Mike Galbraith <efault@gmx.de>, Oliver Yang <yangoliver@me.com>,
Shakeel Butt <shakeelb@google.com>, xxx xxx <x.qendo@gmail.com>,
Taras Kondratiuk <takondra@cisco.com>,
Daniel Walker <danielwa@cisco.com>,
Vinayak Menon <vinmenon@codeaurora.org>,
Ruslan Ruslichenko <rruslich@cisco.com>,
kernel-team@fb.com
Subject: [PATCH 5/7] sched: loadavg: make calc_load_n() public
Date: Mon, 7 May 2018 17:01:33 -0400 [thread overview]
Message-ID: <20180507210135.1823-6-hannes@cmpxchg.org> (raw)
In-Reply-To: <20180507210135.1823-1-hannes@cmpxchg.org>
It's going to be used in the following patch. Keep the churn separate.
Signed-off-by: Johannes Weiner <hannes@cmpxchg.org>
---
include/linux/sched/loadavg.h | 69 +++++++++++++++++++++++++++++++++++
kernel/sched/loadavg.c | 69 -----------------------------------
2 files changed, 69 insertions(+), 69 deletions(-)
diff --git a/include/linux/sched/loadavg.h b/include/linux/sched/loadavg.h
index cc9cc62bb1f8..0e4c24978751 100644
--- a/include/linux/sched/loadavg.h
+++ b/include/linux/sched/loadavg.h
@@ -37,6 +37,75 @@ calc_load(unsigned long load, unsigned long exp, unsigned long active)
return newload / FIXED_1;
}
+/**
+ * fixed_power_int - compute: x^n, in O(log n) time
+ *
+ * @x: base of the power
+ * @frac_bits: fractional bits of @x
+ * @n: power to raise @x to.
+ *
+ * By exploiting the relation between the definition of the natural power
+ * function: x^n := x*x*...*x (x multiplied by itself for n times), and
+ * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
+ * (where: n_i \elem {0, 1}, the binary vector representing n),
+ * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
+ * of course trivially computable in O(log_2 n), the length of our binary
+ * vector.
+ */
+static inline unsigned long
+fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
+{
+ unsigned long result = 1UL << frac_bits;
+
+ if (n) {
+ for (;;) {
+ if (n & 1) {
+ result *= x;
+ result += 1UL << (frac_bits - 1);
+ result >>= frac_bits;
+ }
+ n >>= 1;
+ if (!n)
+ break;
+ x *= x;
+ x += 1UL << (frac_bits - 1);
+ x >>= frac_bits;
+ }
+ }
+
+ return result;
+}
+
+/*
+ * a1 = a0 * e + a * (1 - e)
+ *
+ * a2 = a1 * e + a * (1 - e)
+ * = (a0 * e + a * (1 - e)) * e + a * (1 - e)
+ * = a0 * e^2 + a * (1 - e) * (1 + e)
+ *
+ * a3 = a2 * e + a * (1 - e)
+ * = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
+ * = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
+ *
+ * ...
+ *
+ * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
+ * = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
+ * = a0 * e^n + a * (1 - e^n)
+ *
+ * [1] application of the geometric series:
+ *
+ * n 1 - x^(n+1)
+ * S_n := \Sum x^i = -------------
+ * i=0 1 - x
+ */
+static inline unsigned long
+calc_load_n(unsigned long load, unsigned long exp,
+ unsigned long active, unsigned int n)
+{
+ return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
+}
+
#define LOAD_INT(x) ((x) >> FSHIFT)
#define LOAD_FRAC(x) LOAD_INT(((x) & (FIXED_1-1)) * 100)
diff --git a/kernel/sched/loadavg.c b/kernel/sched/loadavg.c
index 54fbdfb2d86c..0736e349a54e 100644
--- a/kernel/sched/loadavg.c
+++ b/kernel/sched/loadavg.c
@@ -210,75 +210,6 @@ static long calc_load_nohz_fold(void)
return delta;
}
-/**
- * fixed_power_int - compute: x^n, in O(log n) time
- *
- * @x: base of the power
- * @frac_bits: fractional bits of @x
- * @n: power to raise @x to.
- *
- * By exploiting the relation between the definition of the natural power
- * function: x^n := x*x*...*x (x multiplied by itself for n times), and
- * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
- * (where: n_i \elem {0, 1}, the binary vector representing n),
- * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
- * of course trivially computable in O(log_2 n), the length of our binary
- * vector.
- */
-static unsigned long
-fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
-{
- unsigned long result = 1UL << frac_bits;
-
- if (n) {
- for (;;) {
- if (n & 1) {
- result *= x;
- result += 1UL << (frac_bits - 1);
- result >>= frac_bits;
- }
- n >>= 1;
- if (!n)
- break;
- x *= x;
- x += 1UL << (frac_bits - 1);
- x >>= frac_bits;
- }
- }
-
- return result;
-}
-
-/*
- * a1 = a0 * e + a * (1 - e)
- *
- * a2 = a1 * e + a * (1 - e)
- * = (a0 * e + a * (1 - e)) * e + a * (1 - e)
- * = a0 * e^2 + a * (1 - e) * (1 + e)
- *
- * a3 = a2 * e + a * (1 - e)
- * = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
- * = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
- *
- * ...
- *
- * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
- * = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
- * = a0 * e^n + a * (1 - e^n)
- *
- * [1] application of the geometric series:
- *
- * n 1 - x^(n+1)
- * S_n := \Sum x^i = -------------
- * i=0 1 - x
- */
-static unsigned long
-calc_load_n(unsigned long load, unsigned long exp,
- unsigned long active, unsigned int n)
-{
- return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
-}
-
/*
* NO_HZ can leave us missing all per-CPU ticks calling
* calc_load_fold_active(), but since a NO_HZ CPU folds its delta into
--
2.17.0
next prev parent reply other threads:[~2018-05-07 21:00 UTC|newest]
Thread overview: 44+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-05-07 21:01 [PATCH 0/7] psi: pressure stall information for CPU, memory, and IO Johannes Weiner
2018-05-07 21:01 ` [PATCH 1/7] mm: workingset: don't drop refault information prematurely Johannes Weiner
2018-05-07 21:01 ` [PATCH 2/7] mm: workingset: tell cache transitions from workingset thrashing Johannes Weiner
2018-05-07 21:01 ` [PATCH 3/7] delayacct: track delays from thrashing cache pages Johannes Weiner
2018-05-07 21:01 ` [PATCH 4/7] sched: loadavg: consolidate LOAD_INT, LOAD_FRAC, CALC_LOAD Johannes Weiner
2018-05-07 21:01 ` Johannes Weiner [this message]
2018-05-09 9:49 ` [PATCH 5/7] sched: loadavg: make calc_load_n() public Peter Zijlstra
2018-05-10 13:46 ` Johannes Weiner
2018-05-07 21:01 ` [PATCH 6/7] psi: pressure stall information for CPU, memory, and IO Johannes Weiner
2018-05-08 0:42 ` Randy Dunlap
2018-05-08 14:06 ` Johannes Weiner
2018-05-08 1:35 ` kbuild test robot
2018-05-08 3:04 ` kbuild test robot
2018-05-08 14:05 ` Johannes Weiner
2018-05-09 9:59 ` Peter Zijlstra
2018-05-10 13:49 ` Johannes Weiner
2018-05-09 10:04 ` Peter Zijlstra
2018-05-10 14:10 ` Johannes Weiner
2018-05-09 10:05 ` Peter Zijlstra
2018-05-10 14:13 ` Johannes Weiner
2018-05-09 10:14 ` Peter Zijlstra
2018-05-10 14:18 ` Johannes Weiner
2018-05-09 10:21 ` Peter Zijlstra
2018-05-10 14:24 ` Johannes Weiner
2018-05-09 10:26 ` Peter Zijlstra
2018-05-09 10:46 ` Peter Zijlstra
2018-05-09 11:38 ` Peter Zijlstra
2018-05-10 13:41 ` Johannes Weiner
2018-05-14 8:33 ` Peter Zijlstra
2018-05-09 10:55 ` Peter Zijlstra
2018-05-09 11:03 ` Vinayak Menon
2018-05-23 13:17 ` Johannes Weiner
2018-05-23 13:19 ` Vinayak Menon
2018-06-07 0:46 ` Suren Baghdasaryan
2018-05-07 21:01 ` [PATCH 7/7] psi: cgroup support Johannes Weiner
2018-05-09 11:07 ` Peter Zijlstra
2018-05-10 14:49 ` Johannes Weiner
2018-05-14 15:39 ` [PATCH 0/7] psi: pressure stall information for CPU, memory, and IO Christopher Lameter
2018-05-14 17:35 ` Bart Van Assche
2018-05-14 18:55 ` Johannes Weiner
2018-05-14 20:15 ` Christopher Lameter
2018-05-26 0:29 ` Suren Baghdasaryan
2018-05-29 18:16 ` Johannes Weiner
2018-05-30 23:32 ` Suren Baghdasaryan
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20180507210135.1823-6-hannes@cmpxchg.org \
--to=hannes@cmpxchg.org \
--cc=akpm@linuxfoundation.org \
--cc=bsingharora@gmail.com \
--cc=cgroups@vger.kernel.org \
--cc=danielwa@cisco.com \
--cc=efault@gmx.de \
--cc=kernel-team@fb.com \
--cc=linux-block@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=rruslich@cisco.com \
--cc=shakeelb@google.com \
--cc=takondra@cisco.com \
--cc=tj@kernel.org \
--cc=vinmenon@codeaurora.org \
--cc=x.qendo@gmail.com \
--cc=yangoliver@me.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).