linux-kernel - Re: [patch] CFS scheduler, -v8

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]

Message-ID: <20070506082911.GA32644@elte.hu>
Date:	Sun, 6 May 2007 10:29:11 +0200
From:	Ingo Molnar <mingo@...e.hu>
To:	Linus Torvalds <torvalds@...ux-foundation.org>
Cc:	Esben Nielsen <nielsen.esben@...glemail.com>,
	Balbir Singh <balbir@...ux.vnet.ibm.com>,
	linux-kernel@...r.kernel.org,
	Andrew Morton <akpm@...ux-foundation.org>,
	Con Kolivas <kernel@...ivas.org>,
	Nick Piggin <npiggin@...e.de>, Mike Galbraith <efault@....de>,
	Arjan van de Ven <arjan@...radead.org>,
	Peter Williams <pwil3058@...pond.net.au>,
	Thomas Gleixner <tglx@...utronix.de>, caglar@...dus.org.tr,
	Willy Tarreau <w@....eu>,
	Gene Heskett <gene.heskett@...il.com>, Mark Lord <lkml@....ca>,
	Zach Carter <linux@...hcarter.com>,
	buddabrod <buddabrod@...il.com>
Subject: Re: [patch] CFS scheduler, -v8

* Linus Torvalds <torvalds@...ux-foundation.org> wrote:

> So the _only_ valid way to handle timers is to
>  - either not allow wrapping at all (in which case "unsigned" is better, 
>    since it is bigger)
>  - or use wrapping explicitly, and use unsigned arithmetic (which is 
>    well-defined in C) and do something like "(long)(a-b) > 0".

hm, there is a corner-case in CFS where a fix like this is necessary.

CFS uses 64-bit values for almost everything, and the majority of values 
are of 'relative' nature with no danger of overflow. (They are signed 
because they are relative values that center around zero and can be 
negative or positive.)

there is one value that is of 'absolute' nature though: the 'fair clock' 
(which is the same as the normal system clock when load is 1.0, and it 
slows down in a load-proportional way as load increases), which has 
units of nanoseconds - and the 'keys' in the rbtree are derived from 
such clock values. That particular clock could produce an s64 overflow 
at around 292 years after bootup (a bit later if the system is also used 
for something in that timeframe). While i dont think that's realistic to 
worry about, the fix below should solve that theoretical problem too.

	Ingo

Index: linux/kernel/sched_fair.c
===================================================================
--- linux.orig/kernel/sched_fair.c
+++ linux/kernel/sched_fair.c
@@ -60,7 +60,7 @@ static inline void __enqueue_task_fair(s
 		 * We dont care about collisions. Nodes with
 		 * the same key stay together.
 		 */
-		if (key < entry->fair_key) {
+		if ((s64)(entry->fair_key - key) > 0) {
 			link = &parent->rb_left;
 		} else {
 			link = &parent->rb_right;
-
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/