Re: [patch] CFS scheduler, -v8

[Ingo Molnar <mingo@elte.hu>]

* Linus Torvalds <torvalds@linux-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;