linux-kernel - Re: Bug in AC?

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: <20160517160749.39b0d880@utopia>
Date:	Tue, 17 May 2016 16:07:49 +0200
From:	luca abeni <luca.abeni@...tn.it>
To:	Steven Rostedt <rostedt@...dmis.org>
Cc:	Juri Lelli <juri.lelli@....com>,
	LKML <linux-kernel@...r.kernel.org>,
	Peter Zijlstra <peterz@...radead.org>
Subject: Re: Bug in AC?

Hi all,

a quick reply because I am in hurry... I'll write a longer reply this
evening or tomorrow

On Tue, 17 May 2016 09:46:46 -0400
Steven Rostedt <rostedt@...dmis.org> wrote:
[...]
> And I still don't see how this is a SMP vs UP situation.
Well, on UP if the sum of the sum of the tasks' densities is <= 1 then
all the deadlines are guaranteed to be respected; on SMP, there is no
similar guarantee based on tasks' densities (or utilisations): due to
the Dhall's effect, you can respect all of the deadlines only if the
sum of the densities is <= 1 (as in the UP case), independently from
the number of CPUs.

In other words: on UP a density-based (or utilisation-based) admission
control can guarantee the respect of deadlines, on SMP it cannot (you
have to use more advanced and complex admission control techniques).

> As I
> mentioned on IRC, what about the case with two CPUs and this:
> 
> Two tasks with:       R:10us D: 15us P:100us
> and two tasks with:   R:6us  D: 14us P:14us
> 
> If the period of the first two tasks line up on two different CPUs
> then there's no way the other two tasks will make their deadlines.
I agree this taskset is not schedulable on 2 CPUs. The problem is that
it is possible to generate tasksets with sum of densities < 2 that are
not schedulable on 2 CPUs.


				Luca
> 
> -- Steve
> 
> 
> > 
> > 
> > 
> > 				Luca
> >   
> > > 
> > > Highlights from his reply follow (translated :-)):
> > > 
> > >  - SCHED_DEADLINE, as the documentation says, does AC using
> > > utilization
> > >  - it is true that a sufficient (but not necessary) test on UP
> > > for D_i != P_i cases is the one of my patch below
> > >  - we have agreed in the past that the kernel should only check
> > > that we don't cause "overload" in the system (which is still the
> > > case if we consider utilizations), not "hard schedulability"
> > >  - also because on SMP systems "sum(WCET_i / min{D_i, P_i}) <= M"
> > >    doesn't guarantee much more than the test base on P_i only
> > > (there not seem to be many/any papers around considering the
> > > D_i != P_i case on SMP actually)
> > >  - basically the patch below would only matter for the
> > > UP/partitioned cases
> > > 
> > >  Luca please correct me if I misunderstood something.
> > > 
> > >  Steve, does this better answer your question?
> > > 
> > > - Juri
> > > 
> > > From 6cd9b6f3c2b9f144828aa09ad2a355b00a153348 Mon Sep 17 00:00:00
> > > 2001 From: Juri Lelli <juri.lelli@....com>
> > > Date: Fri, 4 Sep 2015 15:41:42 +0100
> > > Subject: [PATCH] sched/core: fix SCHED_DEADLINE admission control
> > > 
> > > As Documentation/sched/sched-deadline.txt says, a new task can
> > > pass through admission control if sum(WCET_i / min{D_i, P_i}) <=
> > > 1. However, if the user specifies both sched_period and
> > > sched_deadline, we actually check that sum(WCET_i / P_i) <= 1;
> > > and this is a less restrictive check w.r.t. the former.
> > > 
> > > Fix this by always using sched_deadline parameter to compute
> > > new_bw, as we also impose that runtime <= deadline <= period (if
> > > period != 0) and deadline != 0.
> > > 
> > > Fixes: 4df1638cfaf9 ("sched/deadline: Fix overflow to handle
> > > period==0 and deadline!=0") Signed-off-by: Juri Lelli
> > > <juri.lelli@....com> ---
> > >  kernel/sched/core.c | 4 ++--
> > >  1 file changed, 2 insertions(+), 2 deletions(-)
> > > 
> > > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > > index 096b73b..56bc449 100644
> > > --- a/kernel/sched/core.c
> > > +++ b/kernel/sched/core.c
> > > @@ -2302,9 +2302,9 @@ static int dl_overflow(struct task_struct
> > > *p, int policy, {
> > >  
> > >  	struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
> > > -	u64 period = attr->sched_period ?: attr->sched_deadline;
> > > +	u64 deadline = attr->sched_deadline;
> > >  	u64 runtime = attr->sched_runtime;
> > > -	u64 new_bw = dl_policy(policy) ? to_ratio(period,
> > > runtime) : 0;
> > > +	u64 new_bw = dl_policy(policy) ? to_ratio(deadline,
> > > runtime) : 0; int cpus, err = -1;
> > >  
> > >  	if (new_bw == p->dl.dl_bw)    
>