linux-kernel - Re: Definition of sched

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

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 08 Oct 2008 07:59:33 -0500
From:	Dave Kleikamp <shaggy@...ux.vnet.ibm.com>
To:	Jeremy Fitzhardinge <jeremy@...p.org>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	Steven Rostedt <srostedt@...hat.com>,
	Ingo Molnar <mingo@...e.hu>,
	Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Subject: Re: Definition of sched_clock broken

On Tue, 2008-09-23 at 14:04 -0700, Jeremy Fitzhardinge wrote:
> kernel/sched_clock.c has the comment:
> 
>  * The clock: sched_clock_cpu() is monotonic per cpu, and should be somewhat
>  * consistent between cpus (never more than 2 jiffies difference).
>
> The two jiffy restriction is way too restrictive.

I won't argue whether this is a good thing or a bad thing, but I did
find a problem in the current implementation.

> Historically sched_clock() is intended to measure the amount of
> schedulable time occurring on a CPU.  On a virtual cpu, that is affected
> by the amount of physical cpu time the hypervisor schedules for a vcpu,
> and can therefore advance in a very non-continuous way, depending on the
> overall load on the host system.  It is, however, the only timebase that
> gives the kernel a reasonable hope of determining how much cpu a process
> actually got scheduled.
> 
> The net result is that the sched_clock timebase is 1) monotonic, 2)
> loses arbitrary amounts of time against a system monotonic clock, 3)
> per-cpu, with 4) arbitrary drift between different cpu's sched_clocks.
> 
> Tying the sched_clocks of different cpus together in any way loses these
> properties, and just turns it into another system wide monotonic clock,
> which seems redundant given that we already have one (I understand that
> the relatively loose synchronization allows it to be implemented more
> efficiently than a normal monotonic clock).

Currently, I've found that it is quite easy to observe scd->clock, and
therefore rq->clock, running backwards, losing the monotonic quality.

This patch demonstrates the problem.  I've found it triggers often on my
laptop (Lenovo T60p) just doing everyday work.  I'll follow up with a
patch that fixes the problem.  I'll let Peter and Ingo judge if it is
the correct fix.

diff --git a/kernel/sched.c b/kernel/sched.c
index 7ea767a..b850937 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -638,7 +638,13 @@ static inline int cpu_of(struct rq *rq)
 
 static inline void update_rq_clock(struct rq *rq)
 {
-	rq->clock = sched_clock_cpu(cpu_of(rq));
+	u64 clock = sched_clock_cpu(cpu_of(rq));
+	if (clock < rq->clock) {
+		printk(KERN_ERR "TIME TURNED BACK!\n");
+		printk(KERN_ERR "new time = %llx rq->clock = %llx\n",
+				clock, rq->clock);
+	} else
+		rq->clock = clock;
 }
 
 /*


> At the moment the x86 sched_clock is hooked through paravirt_ops so that
> the underlying hypervisor can provide precise scheduled time
> information, with the hope that the scheduler will use it to make better
> decisions.  However if the scheduler needs to be lied to then I can do
> that too, but it's a pity to throw away information that's available to it.

Thanks,
Shaggy
-- 
David Kleikamp
IBM Linux Technology Center

--
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/