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 \ --subject='Re: [PATCH 5/7] sched: loadavg: make calc_load_n() public' \ /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
This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.