CFS scheduler, -v8
in [Kernel]
|
Prev: Bug in current -git tree causing dbus and gnome to chew up cpu time
Next: Introduce O_CLOEXEC (take >2)
From: Ingo Molnar on 6 May 2007 05:00 * Willy Tarreau <w(a)1wt.eu> wrote: > Just a hint: while your code here is correct, it is a good practise to > check against < 0 instead, so that if for any reason you sometimes > forget to cast to signed, the compiler will emit a warning stating > that the condition is always false. This would simply become : > > - if (key < entry->fair_key) { > + if ((s64)(key - entry->fair_key) < 0) { done :-) (Btw., the key is still s64 so the cast is technically unnecessary - but now the code would be correct with the key being u64 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)(key - entry->fair_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(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Linus Torvalds on 6 May 2007 14:00 On Sun, 6 May 2007, Ingo Molnar wrote: > > * Linus Torvalds <torvalds(a)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.) Well, I'd like to just worry about that for a while. You say there is "no danger of overflow", and I mostly agree that once we're talking about 64-bit values, the overflow issue simply doesn't exist, and furthermore the difference between 63 and 64 bits is not really relevant, so there's no major reason to actively avoid signed entries. So in that sense, it all sounds perfectly sane. And I'm definitely not sure your "292 years after bootup" worry is really worth even considering. When we're really so well off that we expect the hardware and software stack to be stable over a hundred years, I'd start to think about issues like that, in the meantime, to me worrying about those kinds of issues just means that you're worrying about the wrong things. BUT. There's a fundamental reason relative timestamps are difficult and almost always have overflow issues: the "long long in the future" case as an approximation of "infinite timeout" is almost always relevant. So rather than worry about the system staying up 292 years, I'd worry about whether people pass in big numbers (like some MAX_S64 approximation) as an approximation for "infinite", and once you have things like that, the "64 bits never overflows" argument is totally bogus. There's a damn good reason for using only *absolute* time. The whole "signed values of relative time" may _sound_ good, but it really sucks in subtle and horrible ways! Linus - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Bill Davidsen on 6 May 2007 20:10 Damien Wyart wrote: > Hello, > > * Ingo Molnar <mingo(a)elte.hu> [2007-05-03 15:02]: >> great! So it seems -v8 does improve OpenGL handling too :-) > > What are your thoughts/plans concerning merging CFS into mainline ? Is > it a bit premature to get it into 2.6.22 ? I remember Linus was ok to > change the default scheduler rapidly (the discussion was about sd at > that time) to get more testing than in -mm. > It would seem that a number of us are testing the variants and reporting results (I now have to pull all the new versions and redo stuff, but I have a new test I'm going to run as well). Given that and the fact that there is another idea which can be tested from Tong Li, I think that decision can be postponed, Linus willing. There appear to be enough testers to be driving evolution now, authors may disagree, of course. Several folks added to cc list... -- Bill Davidsen <davidsen(a)tmr.com> "We have more to fear from the bungling of the incompetent than from the machinations of the wicked." - from Slashdot - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Esben Nielsen on 7 May 2007 07:20 On Sat, 5 May 2007, Linus Torvalds wrote: > > > On Sat, 5 May 2007, Esben Nielsen wrote: >> >> I have been wondering why you use usigned for timers anyway. It is also like >> that in hrtimers. Why not use signed and avoid (almost) all worries about wrap >> around issues. The trick is that when all >> a < b >> is be replaced by >> a - b < 0 >> the code will work on all 2-complement machines even if the (signed!) integers >> a and b wrap around. > > No. BOTH of the above are buggy. > > The C language definition doesn't allow signed integers to wrap (ie it's > undefined behaviour), so "a-b < 0" can be rewritten by the compiler as a > simple signed "a < b". > > And the unsigned (or signed) "a < b" is just broken wrt any kind of > wrap-around (whether wrapping around zero or the sign bit). > > 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". > > Notice? The signed variant is basically _never_ correct. > What is (long)(a-b) ? I have tried to look it up in the C99 standeard but I can't find it. Maybe it is in the referred LIA-1 standeard, which I can't find with google. I think the best would be to use "a-b > ULONG_MAX/2" when you mean "a<b" as that should be completely portable. According to C99 Appendix H2.2 (http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) an implementation can choose to do modulo signed integers as it is mandatory for unsigned integers. If an implementation have choosen to do that it must be a bug to to do the "a-b < 0" -> "a<b" optimization. I have never experienced a compiler/architecture combination _not_ doing wrapped signed integers. Esben > Linus > - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Esben Nielsen on 7 May 2007 07:40
On Sun, 6 May 2007, Linus Torvalds wrote: > > > On Sun, 6 May 2007, Ingo Molnar wrote: >> >> * Linus Torvalds <torvalds(a)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.) > > Well, I'd like to just worry about that for a while. > > You say there is "no danger of overflow", and I mostly agree that once > we're talking about 64-bit values, the overflow issue simply doesn't > exist, and furthermore the difference between 63 and 64 bits is not really > relevant, so there's no major reason to actively avoid signed entries. > > So in that sense, it all sounds perfectly sane. And I'm definitely not > sure your "292 years after bootup" worry is really worth even considering. > I would hate to tell mission control for Mankind's first mission to another star to reboot every 200 years because "there is no need to worry about it." As a matter of principle an OS should never need a reboot (with exception for upgrading). If you say you have to reboot every 200 years, why not every 100? Every 50? .... Every 45 days (you know what I am referring to :-) ? > When we're really so well off that we expect the hardware and software > stack to be stable over a hundred years, I'd start to think about issues > like that, in the meantime, to me worrying about those kinds of issues > just means that you're worrying about the wrong things. > > BUT. > > There's a fundamental reason relative timestamps are difficult and almost > always have overflow issues: the "long long in the future" case as an > approximation of "infinite timeout" is almost always relevant. > > So rather than worry about the system staying up 292 years, I'd worry > about whether people pass in big numbers (like some MAX_S64 approximation) > as an approximation for "infinite", and once you have things like that, > the "64 bits never overflows" argument is totally bogus. > > There's a damn good reason for using only *absolute* time. The whole > "signed values of relative time" may _sound_ good, but it really sucks in > subtle and horrible ways! > I think you are wrong here. The only place you need absolute time is a for the clock (CLOCK_REALTIME). You waste CPU using a 64 bit representation when you could have used a 32 bit. With a 32 bit implementation you are forced to handle the corner cases with wrap around and too big arguments up front. With a 64 bit you hide those problems. I think CFS would be best off using a 32 bit timer counting in micro seconds. That would wrap around in 72 minuttes. But as the timers are relative you will never be able to specify a timer larger than 36 minuttes in the future. But 36 minuttes is redicolously long for a scheduler and a simple test limiting time values to that value would not break anything. Esben > Linus > - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |