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

2017-03-02 22:10 GMT+08:00 Daniel Bristot de Oliveira <bristot@...hat.com>:
> From: "Steven Rostedt (VMware)" <rostedt@...dmis.org>
>
> 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
>
> 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>
> Reviewed-by: Daniel Bristot de Oliveira <bristot@...hat.com>
> Cc: Ingo Molnar <mingo@...hat.com>
> Cc: Peter Zijlstra <peterz@...radead.org>
> Cc: Juri Lelli <juri.lelli@....com>
> Cc: Tommaso Cucinotta <tommaso.cucinotta@...up.it>
> Cc: Luca Abeni <luca.abeni@...tannapisa.it>
> Cc: Steven Rostedt <rostedt@...dmis.org>
> Cc: Mike Galbraith <efault@....de>
> Cc: Romulo Silva de Oliveira <romulo.deoliveira@...c.br>
> Cc: Daniel Bristot de Oliveira <bristot@...hat.com>
> Cc: linux-kernel@...r.kernel.org
> ---

Reviewed-by: Wanpeng Li <wanpeng.li@...mail.com>

>  kernel/sched/deadline.c | 8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> index b669f7f..f7403e5 100644
> --- a/kernel/sched/deadline.c
> +++ b/kernel/sched/deadline.c
> @@ -445,13 +445,13 @@ static void replenish_dl_entity(struct sched_dl_entity *dl_se,
>   *
>   * 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 sched_dl_entity *dl_se,
>          * 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);
>
> --
> 2.9.3
>