linux-kernel - Re: CFS review

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: <1185979796.12034.92.camel@twins>
Date:	Wed, 01 Aug 2007 16:49:56 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Roman Zippel <zippel@...ux-m68k.org>
Cc:	Mike Galbraith <efault@....de>,
	Linus Torvalds <torvalds@...ux-foundation.org>,
	Ingo Molnar <mingo@...e.hu>,
	Andrew Morton <akpm@...ux-foundation.org>,
	linux-kernel@...r.kernel.org
Subject: Re: CFS review

Hi Roman,

Took me most of today trying to figure out WTH you did in fs2.c, more
math and fundamental explanations would have been good. So please bear
with me as I try to recap this thing. (No, your code was very much _not_
obvious, a few comments and broken out functions would have made a world
of a difference)

So, for each task we keep normalised time

 normalised time := time/weight

using Bresenham's algorithm we can do this prefectly (up until a renice
- where you'd get errors)

        avg_frac += weight_inv

        weight_inv = X / weight

        avg = avg_frac / weight0_inv

        weight0_inv = X / weight0

        avg = avg_frac / (X / weight0) 
            = (X / weight) / (X / weight0) 
            = X / weight * weight0 / X 
            = weight0 / weight

So avg ends up being in units of [weight0/weight].

Then, in order to allow sleeping, we need to have a global clock to sync
with. Its this global clock that gave me headaches to reconstruct.

We're looking for a time like this:

  rq_time := sum(time)/sum(weight)

And you commented that the /sum(weight) part is where CFS obtained its
accumulating rounding error? (I'm inclined to believe the error will
statistically be 0, but I'll readily accept otherwise if you can show a
practical 'exploit')

Its not obvious how to do this using modulo logic like Bresenham because
that would involve using a gcm of all possible weights.

What you ended up with is quite interesting if correct.

	sum_avg_frac += weight_inv_{i}

however by virtue of the scheduler minimising:

  avg_{i} - avg_{j} | i != j

this gets a factor of:

  weight_{i}/sum_{j}^{N}(weight_{j})

 ( seems correct, needs more analysis though, this is very much a
   statistical step based on the previous constraint. this might
   very well introduce some errors )

resulting in:

        sum_avg_frac += sum_{i}^{N}(weight_inv_{i} *
        weight_{i}/sum_{j}^{N}(weight_{j}))

        weight_inv = X / weight

        sum_avg = sum_avg_frac / sum(weight0_inv)
                = sum_avg_frac / N*weight0_inv

        weight0_inv = X / weight0

        sum_avg = sum_avg_frac / N*weight0_inv
                = sum_{i}^{N}(weight_inv_{i} *
        weight_{i}/sum_{j}^{N}(weight_{j})) / N*weight0_inv
                = sum_{i}^{N}(X/weight_{i} *
        weight_{i}/sum_{j}^{N}(weight_{j})) / N*(X/weight0)
                = N*X / sum_{j}(weight_{j}) * weight0/N*X
                = weight0 / sum_{j}(weight_{j})

Exactly the unit we were looking for [weight0/sum(weight)]

 ( the extra weight0 matching the one we had in the per task normalised
   time )

I'm not sure all this is less complex than CFS, I'd be inclined to say
it is more so.

Also, I think you have an accumulating error on wakeup where you sync
with the global clock but fully discard the fraction.

Anyway, as said a more detailed explanation and certainly a proof of
your math would be nice. Is this something along the lines of what you
intended to convey?

If so, in the future please use more understandable language, we were
taught math for a reason :-)

Regards,
Peter

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