Re: [patch] CFS scheduler, -v8

Ingo Molnar
2007-05-06T08:30:05Z

* 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;