linux-kernel - Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when calculating overflow

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:   Wed, 15 Feb 2017 08:40:03 +0100
From:   Luca Abeni <luca.abeni@...tannapisa.it>
To:     Steven Rostedt <rostedt@...dmis.org>
Cc:     linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Daniel Bristot de Oliveira <bristot@...hat.com>,
        Juri Lelli <juri.lelli@....com>,
        Tommaso Cucinotta <tommaso.cucinotta@...up.it>,
        Mike Galbraith <efault@....de>,
        Romulo Silva de Oliveira <romulo.deoliveira@...c.br>
Subject: Re: [PATCH 3/2] sched/deadline: Use deadline instead of period when
 calculating overflow

Hi Steven,

On Tue, 14 Feb 2017 19:14:17 -0500
Steven Rostedt <rostedt@...dmis.org> wrote:
[...]
> > I am not sure about the correct fix (wouldn't
> > "runtime / (deadline - t) > dl_runtime / dl_deadline" allow the
> > task to use a fraction of CPU time equal to dl_runtime /
> > dl_deadline?)
> > 
> > The current code is clearly wrong (as shown by Daniel), but I do not
> > understand how the current check can allow the task to consume more
> > than dl_runtime / dl_period... I need some more time to think about
> > this issue. 
> >   
> 
> This is in dl_entity_overflow() which is called by update_dl_entity()
> which has this:
> 
> 	if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
> 	    dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
> 		dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
> 		dl_se->runtime = pi_se->dl_runtime;
> 	}
> 
> 
> The comments in this code state:
> 
>  * The policy here is that we update the deadline of the entity only
> if:
>  *  - the current deadline is in the past,
>  *  - using the remaining runtime with the current deadline would make
>  *    the entity exceed its bandwidth.
> 
> That second comment is saying that when this task woke up, if the
> percentage left to run will exceed its bandwidth with the rest of the
> system then reset its deadline and its runtime.

Right; this is the problem. When the relative deadline is different
from the period, the term "bandwidth" is ambiguous... We can consider
the utilisation (maximum runtime / period), or the density (maximum
runtime / relative deadline). In some sense, the two approaches are
both correct (if we use density, we are more pessimistic but we try to
respect deadlines in a hard way; if we use utilisation, we allow more
tasks to be admitted but we can only provide bounded tardiness).

What the current code is doing is to mix the two approaches (resulting
in a wrong runtime/deadline assignment).

> What happens in the current logic, is that overflow() check says, when
> the deadline is much smaller than the period, "yeah, we're going to
> exceed our percentage!" so give us more, even though it wont exceed
> its percentage if we compared runtime with deadline.
> 
> The relative-runtime / relative-period is a tiny percentage, which
> does not reflect the percentage that the task is allowed to have
> before the deadline is hit. The tasks bandwidth should be calculated
> by the relative-runtime / relative-deadline, as runtime <= deadline
> <= period, and the runtime should happen within the deadline.
> 
> When the task wakes up, it currently looks at how much time is left
> absolute-deadline - t, and compares it to the amount of runtime left.
> The percentage allowed should still be compared with the percentage
> between relative-runtime and relative-deadline. The relative-period or
> even absolute-period, should have no influence in this decision.

Ok, thanks; I think I can now see why this can result in a task
consuming more than the reserved utilisation. I still need some time to
convince me that "runtime / (deadline - t) > dl_runtime / dl_deadline"
is the correct check to use (in this case, shouldn't we also change the
admission test to use densities instead of utilisations?)



			Thanks,
				Luca