linux-kernel - Re: [PATCH] sched: Avoid side-effect of tickless idle on update_cpu

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]

Date:	Mon, 17 May 2010 10:52:50 -0700
From:	Venkatesh Pallipadi <venki@...gle.com>
To:	Peter Zijlstra <peterz@...radead.org>
Cc:	Ingo Molnar <mingo@...e.hu>, linux-kernel@...r.kernel.org,
	Ken Chen <kenchen@...gle.com>, Paul Turner <pjt@...gle.com>,
	Nikhil Rao <ncrao@...gle.com>,
	Suresh Siddha <suresh.b.siddha@...el.com>
Subject: Re: [PATCH] sched: Avoid side-effect of tickless idle on 
	update_cpu_load (v2)

On Mon, May 17, 2010 at 10:35 AM, Peter Zijlstra <peterz@...radead.org> wrote:
> On Mon, 2010-05-17 at 09:52 -0700, Venkatesh Pallipadi wrote:
>
>> >  load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * load_(i-1)
>
>> > So because we're in no_hz, current load == 0 and we could approximate
>> > the thing by:
>> >
>> >  load_i = ((2^i)-1)/(2^i) * load_i
>> >
>> > Because for i ~ 1, there is no new input, and for i >> 1 the fraction is
>> > small.
>>
>> Something like that. But, with total_updates = n and missed_updates = n - 1
>> We do this for (n - 1)
>> load_i = ((2^i)-1)/(2^i) * load_i
>> And do this once.
>> load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * cur_load
>
>> That way we do not differentiate between whether we are in tickless or
>> not and we use the same code path.
>
> But by the above, that's not the same as without, because that does
>
> load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * load_(i-1)
>
> not
>
> load_i = ((2^i)-1)/(2^i) * load_i + 1/(2^i) * cur_load

Hmm. I assumed you meant
load_(i-1) is same as cur_load when you said
>> >Where load_-1 == current load.

No? Or did I miss something?

For the updates done every tick, it is
load = degrade * load + (1-degrade) * cur_load
For updates done with missed ticks
load = degrade^(missed-1) * load
load = degrade * load + (1-degrade) * cur_load

So, cur_load is only accounted for the last tick, and zero load
assumed for all the missed ticks.

>> > But why then do we precalculate these factors? It seems to me
>> > ((2^i)-1)/(2^i) is something that is trivial to compute and doesn't
>> > warrant a lookup table?
>> >
>>
>> Yes. Initially I had a for loop running for missed_updates to calculate
>>  ((2^i)-1)/(2^i) * load_i
>> in a loop.
>
> Ah, right! So you want to calculate:
>
>  (((2^i)-1)/(2^i))^n
>
> Which ends up being a nasty binomial sum: 1/(2^ni) * \Sum_k^n (n choose
> k) * 2^k, so yeah, I don't see a fancy way to quickly compute that.
>
>
> OK, could you summarize our discussion into that comment?
>

OK. Will do.

Thanks,
Venki
--
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/