linux-kernel - [PATCH V3 0/3] sched/deadline: Fixes for constrained deadline tasks

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-next>] [day] [month] [year] [list]

Message-Id: <cover.1488271007.git.bristot@redhat.com>
Date:   Tue, 28 Feb 2017 11:07:52 +0100
From:   Daniel Bristot de Oliveira <bristot@...hat.com>
To:     linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>
Cc:     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: [PATCH V3 0/3] sched/deadline: Fixes for constrained deadline tasks

While reading sched deadline code, I find out that a constrained
deadline task could be replenished before the next period if
activated after the deadline, opening the window to run for more
than Q/P. The patch [2] explains and fixes this problem.

Furthermore, while fixing this issue, I found that the replenishment
timer was being fired at the deadline of the task. This works fine
for implicit deadline tasks (deadline == period) because the deadline
is at the same point in time of the next period. But that is not true
for constrained deadline tasks (deadline < period). This problem is
not as visible as the first because the runtime leakage takes
place only in the second activation. Next activations receive the
correct bandwidth. However, after the 2nd activation, tasks are
activated in the (period - dl_deadline) instant, which is before
the expected activation. This problem is explained in the fix
description as well.

While testing these fixes, Rostedt tweaked the test case a little.
Instead of having the runtime equal to the deadline, he increased
the deadline ten fold. Then, the task started using much more than
.1% of the CPU. More like 20%. Looking into this he 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. As we care about if the
runtime can make its deadline, not its period, we need to use the
task's density in the check, not the task's utilization. After
correcting this, now when the task gets enqueued, it can throttle
correctly.

Changes from V2:
 - Fixes dl_entity_overflow(): (Steven Rostedt)
   Patch 3/3 fixes the dl_entity_overflow() for constrained deadline
   tasks by using the density, not the utilization.
   (as deadline <= period, deadline is always == min(deadline, period))
Changes from V1:
 - Fix a broken comment style. (Peter Zijlstra)
 - Fixes dl_is_constrained(). (Steven Rostedt)
    A constrained deadline task has dl_deadline < dl_period; so
	"dl_runtime < dl_period"; s/runtime/deadline/

Daniel Bristot de Oliveira (2):
  sched/deadline: Replenishment timer should fire in the next period
  sched/deadline: Throttle a constrained deadline task activated after
    the deadline

Steven Rostedt (VMware) (1):
  sched/deadline: Use deadline instead of period when calculating
    overflow

 kernel/sched/deadline.c | 62 ++++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 56 insertions(+), 6 deletions(-)

-- 
2.9.3