linux-kernel - Re: [PATCH v2] sched/fair: update scale invariance of PELT

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: <20170411130920.GB22895@linaro.org>
Date:   Tue, 11 Apr 2017 15:09:20 +0200
From:   Vincent Guittot <vincent.guittot@...aro.org>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     mingo@...nel.org, linux-kernel@...r.kernel.org,
        dietmar.eggemann@....com, Morten.Rasmussen@....com,
        yuyang.du@...el.com, pjt@...gle.com, bsegall@...gle.com
Subject: Re: [PATCH v2] sched/fair: update scale invariance of PELT

Le Tuesday 11 Apr 2017 à 12:49:49 (+0200), Peter Zijlstra a écrit :
> 
> Lets go back to the unscaled version:
> 
>     running   idle
>    |*********|---------|
> 
> With the current code, that would effectively end up like (again
> assuming 50%):
> 
>     running   idle
>    |*_*_*_*_*|---------|
> 
> 
> Time stays the same, but we add extra idle cycles.

In fact it's not really like that because this doesn't reflect the impact of
the decay window which is not linear with time

For a task that run at max freq

(1) |-------|-------|-------|----
       ****            ****
    ---****------------****------

The same task running at half frequency, will run twice longer
    |-------|-------|-------|----
       ********        ********                          
    ---********--------********--

With the current implementation, we are not inserting idle cycle but
dividing the contribution by half in order to compensate the fact that the task
will run twice longer:

(2) |-------|-------|-------|----

    ---********--------********--  

But the final result is neither equal to

    |-------|-------|-------|----
       * * * *         * * * *                
    ---*_*_*_*---------*_*_*_*---

nor to (1) as described below:

Let assume all durations are aligned with decay window. This will simplify the
formula for the explanation and will not change the demonstration. We can come back
on the full equation later on.

For (1), we have the equation that you write previously:

     util_sum' = utilsum * y^p +
                                  p-1
               d1 * y^p + 1024 * \Sum y^n + d3 * y^0
 	                              n=1

Which becomes like below when we are aligned to decay window (d1 and d3 are null)
(A)  util_sum' = utilsum * y^p +
                       p-1
			   1024 * \Sum y^n
 	                   n=1

The running time at max frequency is d and p is the number of decay window period
In this case p = d/1024us and l = 0

For (2), task runs at half frequency so the duration d' is twice longer than
d and p'=2*p. In current implementation, we compensate the increase of running
duration (and lost idle time) by dividing the contribution by 2:
     util_sum' = utilsum * y^p' +
                       p'-1
                512 * \Sum y^n
 	                   n=1

(B)  util_sum' = utilsum * y^(2*p) +
                       2*p-1
                512 * \Sum y^n
                       n=1

With the new scale invariance, we have the following pattern before scaling
time:

    |-------|-------|-------|--
       ********        ********
    ---********--------********

Task still runs at half frequency so the duration d' is twice longer than
d and p': p'=2*p just like for (2).
But before computing util_sum', we change the temporal referencial to reflect
what would have been done at max frequency: we scale the running time (divide it by 2)
in order to have something like:

    |-------|-------|-------|--
       ****            ****
    ---****____--------****____

so we now have a duration d'' that is half d'and a number of period p'' that
is half p' so p'' = 1/2 * p' == p
     util_sum' = utilsum * y^p'' +
                       p''-1
               1024 * \Sum y^n
 	                   n=1
     util_sum' = utilsum * y^p +
                       p-1
                512 * \Sum y^n
 	                   n=1

Then l = p' - p''. The lost idle time is tracked to apply the same amount of decay
window when the task is sleeping

so at the end we have a number of decay window of p''+l = p'' so we still have
the same amount of decay window than previously.


>