sched: accurate user accounting

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

Review

Quoted 6 lines

(quoted diff) +6 -0

+/*
+ * Some helpers for converting nanosecond timing to jiffy resolution
+ */
+#define NS_TO_JIFFIES(TIME)   ((TIME) / (1000000000 / HZ))
+#define JIFFIES_TO_NS(TIME)   ((TIME) * (1000000000 / HZ))
+

This hunk is already in mainline so it will be double defined now.

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

Quoted 7 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

[..snip..]

Compilation failed with:
kernel/built-in.o(.sched.text+0x564): more undefined references to `__udivdi3' follow

$ gcc --version | head -1
gcc (GCC) 3.4.6

$ cat /proc/cpuinfo | grep cpu
cpu             : 7447A, altivec supported

Can't say i really understand why 64bit arithmetics suddenly became an issue here.

Am i supposed to run the testcase and see if numbers in /proc/stat' now match the reality closer? To be really accurate /proc/stat' should be left alone methinks, because no matter how good you try the fundamential fact that time(and consequently load percentage) is not really devided in USER_HZ intervals will interfere with ones quest for accurate statistics. (Wonder what this patch will do to slightly modified hog that produced this: http://www.boblycat.org/~malc/apc/load-c2d-hog.png
but this will have to wait till i get to the PC at work)

Quoted 15 lines · malc

Quoted 7 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

[..snip..]

Compilation failed with:
kernel/built-in.o(.sched.text+0x564): more undefined references to `__udivdi3' follow

Quoted 8 lines

$ gcc --version | head -1
gcc (GCC) 3.4.6

$ cat /proc/cpuinfo | grep cpu
cpu             : 7447A, altivec supported

Can't say i really understand why 64bit arithmetics suddenly became an issue here.

Probably due to use of:

#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))

Excuse our 64bit world while we strive to correct our 32bit blindness and fix this bug.

Quoted 26 lines · Con Kolivas

Quoted 16 lines · malc

Quoted 8 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

[..snip..]

Compilation failed with:
kernel/built-in.o(.sched.text+0x564): more undefined references to `__udivdi3' follow

Quoted 8 lines

$ gcc --version | head -1
gcc (GCC) 3.4.6

$ cat /proc/cpuinfo | grep cpu
cpu             : 7447A, altivec supported

Can't say i really understand why 64bit arithmetics suddenly became an issue here.

Quoted 7 lines

Probably due to use of:

#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))

Excuse our 64bit world while we strive to correct our 32bit blindness and fix this bug.

Please try this (akpm please don't include till we confirm it builds on ppc, sorry). For 2.6.21-rc4

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

Signed-off-by Con Kolivas <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

---

include/linux/kernel_stat.h |    3 ++
include/linux/sched.h       |    2 -
kernel/sched.c              |   46
+++++++++++++++++++++++++++++++++++++++++--- kernel/timer.c            
 |    5 +---
4 files changed, 49 insertions(+), 7 deletions(-)

Index: linux-2.6.21-rc4-acct/include/linux/kernel_stat.h
===================================================================
--- linux-2.6.21-rc4-acct.orig/include/linux/kernel_stat.h 2006-09-21
19:54:58.000000000 +1000 +++
linux-2.6.21-rc4-acct/include/linux/kernel_stat.h 2007-03-25
21:51:49.000000000 +1000 @@ -16,11 +16,14 @@

struct cpu_usage_stat {
	cputime64_t user;

include/linux/kernel_stat.h +1 -0

+	cputime64_t user_ns;

	cputime64_t nice;

include/linux/kernel_stat.h +1 -0

+	cputime64_t nice_ns;

	cputime64_t system;
	cputime64_t softirq;
	cputime64_t irq;
	cputime64_t idle;

include/linux/kernel_stat.h +1 -0

+	cputime64_t idle_ns;

	cputime64_t iowait;
	cputime64_t steal;
};

Index: linux-2.6.21-rc4-acct/include/linux/sched.h
===================================================================
--- linux-2.6.21-rc4-acct.orig/include/linux/sched.h 2007-03-21
12:53:00.000000000 +1100 +++
linux-2.6.21-rc4-acct/include/linux/sched.h 2007-03-25

21:51:49.000000000 +1000 @@ -882,7 +882,7 @@ struct task_struct {
	int __user *clear_child_tid;		/* CLONE_CHILD_CLEARTID */

	unsigned long rt_priority;

include/linux/sched.h +1 -1

-	cputime_t utime, stime;
+	cputime_t utime, utime_ns, stime;

	unsigned long nvcsw, nivcsw; /* context switch counts */
	struct timespec start_time;

/* mm fault and swap info: this can arguably be seen as either mm-specific or thread-specific */ Index:
linux-2.6.21-rc4-acct/kernel/sched.c
===================================================================

--- linux-2.6.21-rc4-acct.orig/kernel/sched.c 2007-03-21
12:53:00.000000000 +1100 +++
linux-2.6.21-rc4-acct/kernel/sched.c 2007-03-25 21:58:27.000000000
+1000 @@ -89,6 +89,7 @@ unsigned long long __attribute__((weak))
*/
#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))
+#define JIFFY_NS JIFFIES_TO_NS(1)

/*
* These are the 'tuning knobs' of the scheduler:

(quoted diff) +0 -0

@@ -3017,8 +3018,49 @@ EXPORT_PER_CPU_SYMBOL(kstat);

static inline void
update_cpu_clock(struct task_struct *p, struct rq *rq, unsigned long long now) {

kernel/sched.c +4 -1

-	p->sched_time += now - p->last_ran;
+	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+	cputime64_t time_diff = now - p->last_ran;
+
+	p->sched_time += time_diff;

	p->last_ran = rq->most_recent_timestamp = now;

kernel/sched.c +38 -0

+	if (p != rq->idle) {
+		cputime_t utime_diff = time_diff;
+
+		if (TASK_NICE(p) > 0) {
+			cpustat->nice_ns = cputime64_add(cpustat->nice_ns,
+							 time_diff);
+			if (cpustat->nice_ns > JIFFY_NS) {
+				cpustat->nice_ns =
+					cputime64_sub(cpustat->nice_ns,
+					JIFFY_NS);
+				cpustat->nice =
+					cputime64_add(cpustat->nice, 1);
+			}
+		} else {
+			cpustat->user_ns = cputime64_add(cpustat->user_ns,
+							 time_diff);
+			if (cpustat->user_ns > JIFFY_NS) {
+				cpustat->user_ns =
+					cputime64_sub(cpustat->user_ns,
+					JIFFY_NS);
+				cpustat ->user =
+					cputime64_add(cpustat->user, 1);
+			}
+		}
+		p->utime_ns = cputime_add(p->utime_ns, utime_diff);
+		if (p->utime_ns > JIFFY_NS) {
+			p->utime_ns = cputime_sub(p->utime_ns, JIFFY_NS);
+			p->utime = cputime_add(p->utime,
+					       jiffies_to_cputime(1));
+		}
+	} else {
+		cpustat->idle_ns = cputime64_add(cpustat->idle_ns, time_diff);
+		if (cpustat->idle_ns > JIFFY_NS) {
+			cpustat->idle_ns = cputime64_sub(cpustat->idle_ns,
+							 JIFFY_NS);
+			cpustat->idle = cputime64_add(cpustat->idle, 1);
+		}
+	}

}

/*

kernel/sched.c +0 -2

@@ -3104,8 +3146,6 @@ void account_system_time(struct task_str
 		cpustat->system = cputime64_add(cpustat->system, tmp);
 	else if (atomic_read(&rq->nr_iowait) > 0)
 		cpustat->iowait = cputime64_add(cpustat->iowait, tmp);
-	else
-		cpustat->idle = cputime64_add(cpustat->idle, tmp);
 	/* Account for system time used */
 	acct_update_integrals(p);
 }

Index: linux-2.6.21-rc4-acct/kernel/timer.c
===================================================================
--- linux-2.6.21-rc4-acct.orig/kernel/timer.c 2007-03-21
12:53:00.000000000 +1100 +++
linux-2.6.21-rc4-acct/kernel/timer.c 2007-03-25 21:51:49.000000000
+1000 @@ -1196,10 +1196,9 @@ void update_process_times(int user_tick) int cpu = smp_processor_id();

	/* Note: this timer irq context must be accounted for as well. */

kernel/timer.c +1 -3

-	if (user_tick)
-		account_user_time(p, jiffies_to_cputime(1));
-	else
+	if (!user_tick)

		account_system_time(p, HARDIRQ_OFFSET, jiffies_to_cputime(1));

kernel/timer.c +1 -0

+	/* User time is accounted for in update_cpu_clock in sched.c */

	run_local_timers();
	if (rcu_pending(cpu))
		rcu_check_callbacks(cpu, user_tick);

Quoted 38 lines · Con Kolivas

Quoted 26 lines · Con Kolivas

Quoted 16 lines · malc

Quoted 8 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

[..snip..]

Compilation failed with:
kernel/built-in.o(.sched.text+0x564): more undefined references to `__udivdi3' follow

Quoted 8 lines

$ gcc --version | head -1
gcc (GCC) 3.4.6

$ cat /proc/cpuinfo | grep cpu
cpu             : 7447A, altivec supported

Can't say i really understand why 64bit arithmetics suddenly became an issue here.

Quoted 7 lines

Probably due to use of:

#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))

Excuse our 64bit world while we strive to correct our 32bit blindness and fix this bug.

Please try this (akpm please don't include till we confirm it builds on ppc, sorry). For 2.6.21-rc4

Quoted 8 lines

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

I'm playing again because the final 2.6.20.4 does NOT break amanda, where 2.6.20.4-rc1 did.

Quoted 27 lines · Con Kolivas

Quoted 15 lines · malc

Quoted 7 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

[..snip..]

Compilation failed with:
kernel/built-in.o(.sched.text+0x564): more undefined references to `__udivdi3' follow

Quoted 8 lines

$ gcc --version | head -1
gcc (GCC) 3.4.6

$ cat /proc/cpuinfo | grep cpu
cpu             : 7447A, altivec supported

Can't say i really understand why 64bit arithmetics suddenly became an issue here.

Probably due to use of:

Quoted 5 lines

#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))

Excuse our 64bit world while we strive to correct our 32bit blindness and fix this bug.

Please try this (akpm please don't include till we confirm it builds on ppc, sorry). For 2.6.21-rc4

Quoted 4 lines · Con Kolivas

Quoted 3 lines · malc

Quoted 2 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

Signed-off-by Con Kolivas <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

Quoted 49 lines · Gene Heskett

Quoted 47 lines · Con Kolivas

Quoted 26 lines · Con Kolivas

Quoted 16 lines · malc

Quoted 8 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

we want to do this - and we should do this to the vanilla scheduler first and check the results. I've back-merged the patch to before RSDL and have tested it - find the patch below. Vale, could you try this patch against a 2.6.21-rc4-ish kernel and re-test your testcase?

[..snip..]

Compilation failed with:
kernel/built-in.o(.sched.text+0x564): more undefined references to `__udivdi3' follow

Quoted 8 lines

$ gcc --version | head -1
gcc (GCC) 3.4.6

$ cat /proc/cpuinfo | grep cpu
cpu             : 7447A, altivec supported

Can't say i really understand why 64bit arithmetics suddenly became an issue here.

Quoted 7 lines

Probably due to use of:

#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))

Excuse our 64bit world while we strive to correct our 32bit blindness and fix this bug.

Please try this (akpm please don't include till we confirm it builds on ppc, sorry). For 2.6.21-rc4

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

Quoted 2 lines

I'm playing again because the final 2.6.20.4 does NOT break amanda, where 2.6.20.4-rc1 did.

Yes only the original version I posted on this email thread was for an RSDL 0.33 patched kernel. That original patch should build fine on i386 and x86_64 (where I tried it). This version I sent out following Ingo's lead has 2.6.21-rc4 in mind (without rsdl).

Quoted 5 lines · Con Kolivas

Quoted 4 lines · Con Kolivas

Quoted 3 lines · malc

Quoted 2 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

[..snip..]

Quoted 9 lines

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

Quoted 2 lines

Signed-off-by Con Kolivas <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

[..snip..]

Forgot to mention. Given that this goes into the kernel, shouldn't Documentation/cpu-load.txt be amended/removed?

Quoted 23 lines · malc

Quoted 5 lines · Con Kolivas

Quoted 4 lines · Con Kolivas

Quoted 3 lines · malc

Quoted 2 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

[..snip..]

Quoted 11 lines

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

Signed-off-by Con Kolivas <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

[..snip..]

Quoted 2 lines

Forgot to mention. Given that this goes into the kernel, shouldn't Documentation/cpu-load.txt be amended/removed?

Yes that's a good idea. Also there should be a sanity check because sometimes for some reason noone's been able to explain to me sched_clock gives a value which doesn't make sense (time appears to have gone backwards) and that will completely ruin the accounting from then on.

Quoted 25 lines · Con Kolivas

Quoted 24 lines · malc

Quoted 5 lines · Con Kolivas

Quoted 4 lines · Con Kolivas

Quoted 3 lines · malc

Quoted 2 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

[..snip..]

Quoted 12 lines

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

Signed-off-by Con Kolivas <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

[..snip..]

Quoted 7 lines

Quoted 2 lines

Forgot to mention. Given that this goes into the kernel, shouldn't Documentation/cpu-load.txt be amended/removed?

Yes that's a good idea. Also there should be a sanity check because sometimes for some reason noone's been able to explain to me sched_clock gives a value which doesn't make sense (time appears to have gone backwards) and that will completely ruin the accounting from then on.

After running this new kernel for a while i guess i have hit this issue:
http://www.boblycat.org/~malc/apc/bad-load.png

Top and icewm's monitor do show incredibly huge load while in reality nothing like that is really happening. Both ad-hoc and `/proc/stat' (idle) show normal CPU utilization (7% since i'm doing some A/V stuff in the background)

Quoted 34 lines · malc

Quoted 25 lines · Con Kolivas

Quoted 24 lines · malc

Quoted 5 lines · Con Kolivas

Quoted 4 lines · Con Kolivas

Quoted 3 lines · malc

Quoted 2 lines · Ingo Molnar

Quoted 1 line · Con Kolivas

For an rsdl 0.33 patched kernel. Comments? Overhead worth it?

[..snip..]

Quoted 12 lines

---
Currently we only do cpu accounting to userspace based on what is actually happening precisely on each tick. The accuracy of that accounting gets progressively worse the lower HZ is. As we already keep accounting of nanosecond resolution we can accurately track user cpu, nice cpu and idle cpu if we move the accounting to update_cpu_clock with a nanosecond cpu_usage_stat entry. This increases overhead slightly but avoids the problem of tick aliasing errors making accounting unreliable.

Signed-off-by Con Kolivas <[email protected]>

Signed-off-by Ingo Molnar <[email protected]>

[..snip..]

Quoted 7 lines

Quoted 2 lines

Forgot to mention. Given that this goes into the kernel, shouldn't Documentation/cpu-load.txt be amended/removed?

Yes that's a good idea. Also there should be a sanity check because sometimes for some reason noone's been able to explain to me sched_clock gives a value which doesn't make sense (time appears to have gone backwards) and that will completely ruin the accounting from then on.

Quoted 7 lines

After running this new kernel for a while i guess i have hit this issue:
http://www.boblycat.org/~malc/apc/bad-load.png

Top and icewm's monitor do show incredibly huge load while in reality nothing like that is really happening. Both ad-hoc and `/proc/stat' (idle) show normal CPU utilization (7% since i'm doing some A/V stuff in the background)

Yes I'd say you hit the problem I described earlier. When playing with sched_clock() I found it gave some "interesting" results fairly infrequently. They could lead to ridiculous accounting mistakes.

So before we go any further with this patch, can you try the following one and see if this simple sanity check is enough?

* These are the 'tuning knobs' of the scheduler:

(quoted diff) +0 -0

@@ -3017,8 +3018,53 @@ EXPORT_PER_CPU_SYMBOL(kstat);

static inline void
update_cpu_clock(struct task_struct *p, struct rq *rq, unsigned long long now) {

kernel/sched.c +3 -1

-	p->sched_time += now - p->last_ran;
+	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+	cputime64_t time_diff;
+

	p->last_ran = rq->most_recent_timestamp = now;

Quoted 2 lines · Con Kolivas

So before we go any further with this patch, can you try the following one and see if this simple sanity check is enough?

Sure (compiling the kernel now), too bad old axiom that testing can not confirm absence of bugs holds.

I have one nit and one request from clarification. Question first (i admit i haven't looked at the surroundings of the patch maybe things would have been are self evident if i did):

What this patch amounts to is that the accounting logic is moved from timer interrupt to the place where scheduler switches task (or something to that effect)?

[..snip..]

Quoted 10 lines

* These are the 'tuning knobs' of the scheduler:

(quoted diff) +0 -0

@@ -3017,8 +3018,53 @@ EXPORT_PER_CPU_SYMBOL(kstat);

static inline void
update_cpu_clock(struct task_struct *p, struct rq *rq, unsigned long long now) {

kernel/sched.c +3 -1

-	p->sched_time += now - p->last_ran;
+	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+	cputime64_t time_diff;
+

	p->last_ran = rq->most_recent_timestamp = now;

kernel/sched.c EXPORT_PER_CPU_SYMBOL(kstat); · line 3028

Quoted 4 lines

kernel/sched.c +4 -0

+	/* Sanity check. It should never go backwards or ruin accounting */
+	if (unlikely(now < p->last_ran))
+		return;
+	time_diff = now - p->last_ran;

A nit. Anything wrong with:

time_diff = now - p->last_ran;
if (unlikeley (LESS_THAN_ZERO (time_diff))

         return;

Quoted 7 lines · malc

Quoted 2 lines · Con Kolivas

So before we go any further with this patch, can you try the following one and see if this simple sanity check is enough?

Sure (compiling the kernel now), too bad old axiom that testing can not confirm absence of bugs holds.

Quoted 7 lines

I have one nit and one request from clarification. Question first (i admit i haven't looked at the surroundings of the patch maybe things would have been are self evident if i did):

What this patch amounts to is that the accounting logic is moved from timer interrupt to the place where scheduler switches task (or something to that effect)?

Both the scheduler tick and context switch now. So yes it adds overhead as I said, although we already do update_cpu_clock on context switch, but it's not this complex.

Quoted 19 lines

[..snip..]

Quoted 10 lines

* These are the 'tuning knobs' of the scheduler:

(quoted diff) +0 -0

@@ -3017,8 +3018,53 @@ EXPORT_PER_CPU_SYMBOL(kstat);

static inline void
update_cpu_clock(struct task_struct *p, struct rq *rq, unsigned long long now) {

kernel/sched.c +3 -1

-	p->sched_time += now - p->last_ran;
+	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+	cputime64_t time_diff;
+

	p->last_ran = rq->most_recent_timestamp = now;

kernel/sched.c EXPORT_PER_CPU_SYMBOL(kstat); · line 3028

Quoted 4 lines

kernel/sched.c +4 -0

+	/* Sanity check. It should never go backwards or ruin accounting */
+	if (unlikely(now < p->last_ran))
+		return;
+	time_diff = now - p->last_ran;

A nit. Anything wrong with:

Quoted 3 lines

time_diff = now - p->last_ran;
if (unlikeley (LESS_THAN_ZERO (time_diff))

         return;

Does LESS_THAN_ZERO work on a cputime64_t on all arches? I can't figure that out just by looking myself which is why I did it the other way.

Quoted 39 lines · Con Kolivas

Quoted 7 lines · malc

Quoted 2 lines · Con Kolivas

So before we go any further with this patch, can you try the following one and see if this simple sanity check is enough?

Sure (compiling the kernel now), too bad old axiom that testing can not confirm absence of bugs holds.

Quoted 7 lines

I have one nit and one request from clarification. Question first (i admit i haven't looked at the surroundings of the patch maybe things would have been are self evident if i did):

What this patch amounts to is that the accounting logic is moved from timer interrupt to the place where scheduler switches task (or something to that effect)?

Both the scheduler tick and context switch now. So yes it adds overhead as I said, although we already do update_cpu_clock on context switch, but it's not this complex.

Quoted 19 lines

[..snip..]

Quoted 10 lines

* These are the 'tuning knobs' of the scheduler:

(quoted diff) +0 -0

@@ -3017,8 +3018,53 @@ EXPORT_PER_CPU_SYMBOL(kstat);

static inline void
update_cpu_clock(struct task_struct *p, struct rq *rq, unsigned long long now) {

kernel/sched.c +3 -1

-	p->sched_time += now - p->last_ran;
+	struct cpu_usage_stat *cpustat = &kstat_this_cpu.cpustat;
+	cputime64_t time_diff;
+

	p->last_ran = rq->most_recent_timestamp = now;

kernel/sched.c EXPORT_PER_CPU_SYMBOL(kstat); · line 3028

Quoted 4 lines

kernel/sched.c +4 -0

+	/* Sanity check. It should never go backwards or ruin accounting */
+	if (unlikely(now < p->last_ran))
+		return;
+	time_diff = now - p->last_ran;

A nit. Anything wrong with:

Quoted 6 lines

Quoted 3 lines

time_diff = now - p->last_ran;
if (unlikeley (LESS_THAN_ZERO (time_diff))

         return;

Does LESS_THAN_ZERO work on a cputime64_t on all arches? I can't figure that out just by looking myself which is why I did it the other way.

I have no idea what type cputime64_t really is, so used this imaginary LESS_THAN_ZERO thing.

Erm... i just looked at the code and suddenly it stopped making any sense at all:

         p->last_ran = rq->most_recent_timestamp = now;
         /* Sanity check. It should never go backwards or ruin accounting
*/ if (unlikely(now < p->last_ran))
                 return;
         time_diff = now - p->last_ran;

First now' is assigned to p->last_ran' and the very next line compares those two values, and then the difference is taken.. I quite frankly am either very tired or fail to see the point.. time_diff is either always zero or there's always a race here.

Quoted 11 lines · malc

Quoted 1 line · Con Kolivas

On Monday 26 March 2007 01:19, malc wrote:

Erm... i just looked at the code and suddenly it stopped making any sense at all:

         p->last_ran = rq->most_recent_timestamp = now;
         /* Sanity check. It should never go backwards or ruin accounting
*/ if (unlikely(now < p->last_ran))
                 return;
         time_diff = now - p->last_ran;

Quoted 4 lines

First now' is assigned to p->last_ran' and the very next line compares those two values, and then the difference is taken.. I quite frankly am either very tired or fail to see the point.. time_diff is either always zero or there's always a race here.

Bah major thinko error on my part! That will teach me to post patches untested at 1:30 am. I'll try again shortly sorry.

Quoted 17 lines · Con Kolivas

Quoted 15 lines · malc

Quoted 1 line · Con Kolivas

On Monday 26 March 2007 01:19, malc wrote:

Erm... i just looked at the code and suddenly it stopped making any sense at all:

         p->last_ran = rq->most_recent_timestamp = now;
         /* Sanity check. It should never go backwards or ruin accounting
*/ if (unlikely(now < p->last_ran))
                 return;
         time_diff = now - p->last_ran;

First now' is assigned to p->last_ran' and the very next line compares those two values, and then the difference is taken.. I quite frankly am either very tired or fail to see the point.. time_diff is either always zero or there's always a race here.

Quoted 2 lines

Bah major thinko error on my part! That will teach me to post patches untested at 1:30 am. I'll try again shortly sorry.

Ok this one is heavily tested. Please try it when you find the time.

This situation is harder to write a hog-like testcase for. Anyhow it seems the difference in percentage stems from the intr' field of /proc/stat', which fits. And following patch (which should be applied on top of yours) seems to help. I wouldn't really know what to do with softirq and the rest of counts touched by this function, so i left them alone.

Comments?

Hello Ingo and others,

After reading http://lwn.net/Articles/236485/ and noticing few refernces to accounting i decided to give CFS a try. With sched-cfs-v2.6.21.4-16 i get pretty weird results, it seems like scheduler is dead set on trying to move the processes to different CPUs/cores all the time. And with hog (manually tweaking the amount iterations) i get fairly strange resuls, first of all the process is split between two cores, secondly while integral load provided by the kernel looks correct, it's off by good 20 percent on each idividial core.

(http://www.boblycat.org/~malc/apc/hog-cfs-v16.png)

Thought this information might be of some interest.

P.S. How come the /proc/stat information is much closer to reality
now? Something like what Con Kolivas suggested was added to sched.c?

Quoted 12 lines · Vassili Karpov

Hello Ingo and others,

After reading http://lwn.net/Articles/236485/ and noticing few refernces to accounting i decided to give CFS a try. With sched-cfs-v2.6.21.4-16 i get pretty weird results, it seems like scheduler is dead set on trying to move the processes to different CPUs/cores all the time. And with hog (manually tweaking the amount iterations) i get fairly strange resuls, first of all the process is split between two cores, secondly while integral load provided by the kernel looks correct, it's off by good 20 percent on each idividial core.

Quoted 3 lines

(http://www.boblycat.org/~malc/apc/hog-cfs-v16.png)

Thought this information might be of some interest.

hm - what does 'hog' do, can i download hog.c from somewhere?

the alternating balancing might be due to an uneven number of tasks perhaps? If you have 3 tasks on 2 cores then there's no other solution to achieve even performance of each task but to rotate them amongst the cores.

Quoted 3 lines

P.S. How come the /proc/stat information is much closer to reality
now? Something like what Con Kolivas suggested was added to sched.c?

well, precise/finegrained accounting patches have been available for years, the thing with CFS is that there we get them 'for free', because CFS needs those metrics for its own logic. That's why this information is much closer to reality now. But note: right now what is affected by the changes in the CFS patches is /proc/PID/stat (i.e. the per-task information that 'top' and 'ps' displays, _not_ /proc/stat) - but more accurate /proc/stat could certainly come later on too.

Quoted 4 lines

the alternating balancing might be due to an uneven number of tasks perhaps? If you have 3 tasks on 2 cores then there's no other solution to achieve even performance of each task but to rotate them amongst the cores.

One task, one thread. I have also tried to watch fairly demanding video (Elephants Dream in 1920x1080/MPEG4) with mplayer, and CFS moves the only task between cores almost every second.

Quoted 8 lines

well, precise/finegrained accounting patches have been available for years, the thing with CFS is that there we get them 'for free', because CFS needs those metrics for its own logic. That's why this information is much closer to reality now. But note: right now what is affected by the changes in the CFS patches is /proc/PID/stat (i.e. the per-task information that 'top' and 'ps' displays, _not_ /proc/stat) - but more accurate /proc/stat could certainly come later on too.

Aha. I see, it's just that integral load for hog is vastly improved compared to vanilla 2.6.21 [...]

Quoted 5 lines · malc

Quoted 4 lines

the alternating balancing might be due to an uneven number of tasks perhaps? If you have 3 tasks on 2 cores then there's no other solution to achieve even performance of each task but to rotate them amongst the cores.

Quoted 3 lines

One task, one thread. I have also tried to watch fairly demanding video (Elephants Dream in 1920x1080/MPEG4) with mplayer, and CFS moves the only task between cores almost every second.

hm, mplayer is not running alone when it does video playback: Xorg is also pretty active. Furthermore, the task you are using to monitor mplayer counts too. The Core2Duo has a shared L2 cache between cores, so it is pretty cheap to move tasks between the cores.

Quoted 9 lines

Quoted 8 lines

well, precise/finegrained accounting patches have been available for years, the thing with CFS is that there we get them 'for free', because CFS needs those metrics for its own logic. That's why this information is much closer to reality now. But note: right now what is affected by the changes in the CFS patches is /proc/PID/stat (i.e. the per-task information that 'top' and 'ps' displays, _not_ /proc/stat) - but more accurate /proc/stat could certainly come later on too.

Quoted 2 lines

Aha. I see, it's just that integral load for hog is vastly improved compared to vanilla 2.6.21 [...]

hm, which ones are improved? Could this be due to some other property of CFS? If your app relies on /proc/stat then there's no extra precision in those cpustat values yet.

i've Cc:-ed Balbir Singh and Dmitry Adamushko who are the main authors of the current precise accounting code in CFS. Maybe i missed some detail :-)

Quoted 8 lines · Ingo Molnar

Quoted 5 lines · malc

Quoted 4 lines

the alternating balancing might be due to an uneven number of tasks perhaps? If you have 3 tasks on 2 cores then there's no other solution to achieve even performance of each task but to rotate them amongst the cores.

Quoted 9 lines

Quoted 3 lines

One task, one thread. I have also tried to watch fairly demanding video (Elephants Dream in 1920x1080/MPEG4) with mplayer, and CFS moves the only task between cores almost every second.

hm, mplayer is not running alone when it does video playback: Xorg is also pretty active. Furthermore, the task you are using to monitor mplayer counts too. The Core2Duo has a shared L2 cache between cores, so it is pretty cheap to move tasks between the cores.

Well just to be sure i reran the test with `-vo null' (and fwiw i tried few completely different output drivers) the behavior is the same. I'm not running Core2Duo but X2, but guess that does not really matter here.

As for the task that monitors, i've written it myself (there are two monitoring methods, one(the accurate) does not depend on contets of `/proc/stat' at all), so it can be cheaply (for me) changed in any way one wants. Sources are available at the same place where screenshot was found.

Quoted 9 lines

Quoted 9 lines

Quoted 8 lines

well, precise/finegrained accounting patches have been available for years, the thing with CFS is that there we get them 'for free', because CFS needs those metrics for its own logic. That's why this information is much closer to reality now. But note: right now what is affected by the changes in the CFS patches is /proc/PID/stat (i.e. the per-task information that 'top' and 'ps' displays, _not_ /proc/stat) - but more accurate /proc/stat could certainly come later on too.

Quoted 6 lines

Quoted 2 lines

Aha. I see, it's just that integral load for hog is vastly improved compared to vanilla 2.6.21 [...]

hm, which ones are improved? Could this be due to some other property of CFS? If your app relies on /proc/stat then there's no extra precision in those cpustat values yet.

This is what it looked like before:
http://www.boblycat.org/~malc/apc/load-x2-hog.png

Now integral load matches the one obtained via the "accurate" method. However the report for individual cores are of by around 20% percent.

Though i'm not quite sure what you mean by "which ones are improved".

Quoted 3 lines

i've Cc:-ed Balbir Singh and Dmitry Adamushko who are the main authors of the current precise accounting code in CFS. Maybe i missed some detail :-)

Oh, the famous "With enough eyeballs, all bugs are shallow." in action.

Quoted 2 lines · malc

On Thu, 14 Jun 2007, Ingo Molnar wrote:

Quoted 4 lines

Now integral load matches the one obtained via the "accurate" method. However the report for individual cores are of by around 20% percent.

I think I missed some of the context, is the accounting of individual tasks or cpustat values off by 20%? I'll try and reproduce this problem.

Could you provide more details on the APC tool that you are using -- I do not understand the orange and yellow lines, do they represent system and user time?

NOTE: There is some inconsistency in the values reported by /usr/bin/time (getrusage) and values reported in /proc or through delay accounting.

Quoted 3 lines · Balbir Singh

Quoted 2 lines · malc

On Thu, 14 Jun 2007, Ingo Molnar wrote:

[..snip..]

Quoted 5 lines

Quoted 4 lines

Now integral load matches the one obtained via the "accurate" method. However the report for individual cores are of by around 20% percent.

Quoted 3 lines

I think I missed some of the context, is the accounting of individual tasks
or cpustat values off by 20%? I'll try and reproduce this problem.

Neither actually, the individual core idle times reported via `/proc/stat' are off by 20 percent, one over estimates and the other under estimates and the sum is right on the mark.

Quoted 4 lines

Could you provide more details on the APC tool that you are using -- I do not understand the orange and yellow lines, do they represent system and user time?

It's somewhat documented on the page: http://www.boblycat.org/~malc/apc
Anyway the left bar is based on information from /proc/stat' the right one is derived from the kernel module that just times how much time was spent in idle handler. The graphs: red - /proc/stat', yellow - module.

Quoted 2 lines

NOTE: There is some inconsistency in the values reported by /usr/bin/time (getrusage) and values reported in /proc or through delay accounting.

I don't really use `getrusage'.

Quoted 17 lines · malc

Quoted 3 lines · Balbir Singh

Quoted 2 lines · malc

On Thu, 14 Jun 2007, Ingo Molnar wrote:

[..snip..]

Quoted 8 lines

Quoted 4 lines

Now integral load matches the one obtained via the "accurate" method. However the report for individual cores are of by around 20% percent.

I think I missed some of the context, is the accounting of individual tasks
or cpustat values off by 20%? I'll try and reproduce this problem.

Quoted 4 lines

Neither actually, the individual core idle times reported via `/proc/stat' are off by 20 percent, one over estimates and the other under estimates and the sum is right on the mark.

Interesting, the idle time accounting (done from account_system_time()) has not changed. Has your .config changed? Could you please send it across. I've downloaded apc and I am trying to reproduce your problem.

Quoted 4 lines

Interesting, the idle time accounting (done from account_system_time()) has not changed. Has your .config changed? Could you please send it across. I've downloaded apc and I am trying to reproduce your problem.

http://www.boblycat.org/~malc/apc/cfs/ has config for 2.6.21 an the diff against 2.6.21.4-cfs-v16.

Quoted 7 lines · malc

Quoted 4 lines

Interesting, the idle time accounting (done from account_system_time()) has not changed. Has your .config changed? Could you please send it across. I've downloaded apc and I am trying to reproduce your problem.

http://www.boblycat.org/~malc/apc/cfs/ has config for 2.6.21 an the diff against 2.6.21.4-cfs-v16.

hm. Could you add this to your kernel boot command line:

highres=off nohz=off

and retest, to inquire whether this problem is independent of any timer-events effects?