| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Fri, 29 Oct 2010 21:42:23 +0200
From: Peter Zijlstra <peterz@...radead.org>
To: Venkatesh Pallipadi <venki@...gle.com>
Cc: Damien Wyart <damien.wyart@...e.fr>,
Chase Douglas <chase.douglas@...onical.com>,
Ingo Molnar <mingo@...e.hu>, tmhikaru@...il.com,
Thomas Gleixner <tglx@...utronix.de>,
linux-kernel@...r.kernel.org
Subject: Re: High CPU load when machine is idle (related to PROBLEM:
Unusually high load average when idle in 2.6.35, 2.6.35.1 and later)
On Tue, 2010-10-26 at 16:05 +0200, Peter Zijlstra wrote:
>
> 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)
> = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
> = a0 * e^n + a * (1 - e^n)
not tested other than compile, but how does that look...?
---
include/linux/sched.h | 2 +-
kernel/sched.c | 74 +++++++++++++++++++++++++++++++++++++++++++++---
kernel/timer.c | 2 +-
3 files changed, 71 insertions(+), 7 deletions(-)
diff --git a/include/linux/sched.h b/include/linux/sched.h
index b3d07df..f878db3 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -143,7 +143,7 @@ extern unsigned long nr_iowait_cpu(int cpu);
extern unsigned long this_cpu_load(void);
-extern void calc_global_load(void);
+extern void calc_global_load(int ticks);
extern unsigned long get_parent_ip(unsigned long addr);
diff --git a/kernel/sched.c b/kernel/sched.c
index 41f1869..125417e 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -3168,10 +3168,64 @@ calc_load(unsigned long load, unsigned long exp, unsigned long active)
}
/*
+ * 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.
+ */
+static unsigned long
+fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
+{
+ unsigned long result = 1UL << frac_bits;
+
+ while (n) {
+ if (n & 1) {
+ result *= x;
+ result += 1UL << (frac_bits - 1);
+ result >>= frac_bits;
+ }
+ n >>= 1;
+ x *= x;
+ 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)
+ * = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
+ * = a0 * e^n + a * (1 - e^n)
+ */
+static unsigned long
+calc_load_n(unsigned long load, unsigned long exp,
+ unsigned long active, unsigned int n)
+{
+ unsigned long en = fixed_power_int(exp, FSHIFT, n);
+
+ load *= en;
+ load += active * (FIXED_1 - en);
+ load += 1UL << (FSHIFT - 1);
+ load >>= FSHIFT;
+
+ return load;
+}
+
+/*
* calc_load - update the avenrun load estimates 10 ticks after the
* CPUs have updated calc_load_tasks.
*/
-void calc_global_load(void)
+void calc_global_load(int ticks)
{
unsigned long upd = calc_load_update + 10;
long active;
@@ -3182,11 +3236,21 @@ void calc_global_load(void)
active = atomic_long_read(&calc_load_tasks);
active = active > 0 ? active * FIXED_1 : 0;
- avenrun[0] = calc_load(avenrun[0], EXP_1, active);
- avenrun[1] = calc_load(avenrun[1], EXP_5, active);
- avenrun[2] = calc_load(avenrun[2], EXP_15, active);
+ if (ticks > LOAD_FREQ) {
+ int n = (jiffies - upd) / LOAD_FREQ;
+
+ avenrun[0] = calc_load_n(avenrun[0], EXP_1, active, n);
+ avenrun[1] = calc_load_n(avenrun[1], EXP_5, active, n);
+ avenrun[2] = calc_load_n(avenrun[2], EXP_15, active, n);
- calc_load_update += LOAD_FREQ;
+ calc_load_update += n * LOAD_FREQ;
+ } else {
+ avenrun[0] = calc_load(avenrun[0], EXP_1, active);
+ avenrun[1] = calc_load(avenrun[1], EXP_5, active);
+ avenrun[2] = calc_load(avenrun[2], EXP_15, active);
+
+ calc_load_update += LOAD_FREQ;
+ }
}
/*
diff --git a/kernel/timer.c b/kernel/timer.c
index d6ccb90..9f82b2a 100644
--- a/kernel/timer.c
+++ b/kernel/timer.c
@@ -1297,7 +1297,7 @@ void do_timer(unsigned long ticks)
{
jiffies_64 += ticks;
update_wall_time();
- calc_global_load();
+ calc_global_load(ticks);
}
#ifdef __ARCH_WANT_SYS_ALARM
--
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