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]

Message-ID: <20170214234926.6b415428@sweethome>
Date:   Tue, 14 Feb 2017 23:49:26 +0100
From:   luca abeni <luca.abeni@...tannapisa.it>
To:     "Steven Rostedt (VMware)" <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 14:28:48 -0500
"Steven Rostedt (VMware)" <rostedt@...dmis.org> wrote:

> I was testing Daniel's changes with his test case, and tweaked it a
> little. Instead of having the runtime equal to the deadline, I
> increased the deadline ten fold.
> 
> Daniel's test case had:
> 
> 	attr.sched_runtime  = 2 * 1000 * 1000;		/* 2 ms
> */ attr.sched_deadline = 2 * 1000 * 1000;		/* 2 ms */
> 	attr.sched_period   = 2 * 1000 * 1000 * 1000;	/* 2 s */
> 
> To make it more interesting, I changed it to:
> 
> 	attr.sched_runtime  =  2 * 1000 * 1000;		/* 2
> ms */ attr.sched_deadline = 20 * 1000 * 1000;		/* 20 ms
> */ attr.sched_period   =  2 * 1000 * 1000 * 1000;	/* 2 s */
> 
> 
> The results were rather surprising. The behavior that Daniel's patch
> was fixing came back. The task started using much more than .1% of the
> CPU. More like 20%.
> 
> Looking into this I found that it was due to the dl_entity_overflow()
> constantly returning true. That's because it uses the relative period
> against relative runtime vs the absolute deadline against absolute
> runtime.
> 
>   runtime / (deadline - t) > dl_runtime / dl_period

I agree that there is an inconsistency here (again, using equations
from the "period=deadline" case with a relative deadline different from
period).

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. 


				Luca
> 
> There's even a comment mentioning this, and saying that when relative
> deadline equals relative period, that the equation is the same as
> using deadline instead of period. That comment is backwards! What we
> really want is:
> 
>   runtime / (deadline - t) > dl_runtime / dl_deadline
> 
> We care about if the runtime can make its deadline, not its period.
> And then we can say "when the deadline equals the period, the
> equation is the same as using dl_period instead of dl_deadline".
> 
> After correcting this, now when the task gets enqueued, it can
> throttle correctly, and Daniel's fix to the throttling of sleeping
> deadline tasks works even when the runtime and deadline are not the
> same.
> 
> Signed-off-by: Steven Rostedt (VMware) <rostedt@...dmis.org>
> ---
> Index: linux-trace.git/kernel/sched/deadline.c
> ===================================================================
> --- linux-trace.git.orig/kernel/sched/deadline.c
> +++ linux-trace.git/kernel/sched/deadline.c
> @@ -445,13 +445,13 @@ static void replenish_dl_entity(struct s
>   *
>   * This function returns true if:
>   *
> - *   runtime / (deadline - t) > dl_runtime / dl_period ,
> + *   runtime / (deadline - t) > dl_runtime / dl_deadline ,
>   *
>   * IOW we can't recycle current parameters.
>   *
> - * Notice that the bandwidth check is done against the period. For
> + * Notice that the bandwidth check is done against the deadline. For
>   * task with deadline equal to period this is the same of using
> - * dl_deadline instead of dl_period in the equation above.
> + * dl_period instead of dl_deadline in the equation above.
>   */
>  static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
>  			       struct sched_dl_entity *pi_se, u64 t)
> @@ -476,7 +476,7 @@ static bool dl_entity_overflow(struct sc
>  	 * of anything below microseconds resolution is actually
> fiction
>  	 * (but still we want to give the user that illusion >;).
>  	 */
> -	left = (pi_se->dl_period >> DL_SCALE) * (dl_se->runtime >>
> DL_SCALE);
> +	left = (pi_se->dl_deadline >> DL_SCALE) * (dl_se->runtime >>
> DL_SCALE); right = ((dl_se->deadline - t) >> DL_SCALE) *
>  		(pi_se->dl_runtime >> DL_SCALE);
>