linux-kernel - Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the inactive utilization

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: <20170327165651.2d09b00d@luca>
Date:   Mon, 27 Mar 2017 16:56:51 +0200
From:   Luca Abeni <luca.abeni@...tannapisa.it>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     linux-kernel@...r.kernel.org, Ingo Molnar <mingo@...hat.com>,
        Juri Lelli <juri.lelli@....com>,
        Claudio Scordino <claudio@...dence.eu.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Tommaso Cucinotta <tommaso.cucinotta@...up.it>,
        Daniel Bristot de Oliveira <bristot@...hat.com>,
        Joel Fernandes <joelaf@...gle.com>,
        Mathieu Poirier <mathieu.poirier@...aro.org>
Subject: Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the
 inactive utilization

On Mon, 27 Mar 2017 16:26:33 +0200
Peter Zijlstra <peterz@...radead.org> wrote:

> On Fri, Mar 24, 2017 at 04:53:01AM +0100, luca abeni wrote:
> > From: Luca Abeni <luca.abeni@...tannapisa.it>
> > 
> > Instead of decreasing the runtime as "dq = -Uact dt" (eventually
> > divided by the maximum utilization available for deadline tasks),
> > decrease it as "dq = -(1 - Uinact) dt", where Uinact is the
> > "inactive utilization".  
> 
> > In this way, the maximum fraction of CPU time that can be reclaimed
> > is given by the total utilization of deadline tasks.
> > This approach solves some fairness issues that have been noticed
> > with "traditional" global GRUB reclaiming.  
> 
> I think the Changelog could do with explicit enumeration of what
> "some" is.

Sorry, when writing the changelog I've been lazy; I'll add a link to
Daniel's email showing the problem in action.


> > Signed-off-by: Luca Abeni <luca.abeni@...tannapisa.it>
> > Tested-by: Daniel Bristot de Oliveira <bristot@...hat.com>
> > ---
> >  kernel/sched/deadline.c | 23 ++++++++++++++++-------
> >  1 file changed, 16 insertions(+), 7 deletions(-)
> > 
> > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c
> > index d70a7b9..c393c3d 100644
> > --- a/kernel/sched/deadline.c
> > +++ b/kernel/sched/deadline.c
> > @@ -900,14 +900,23 @@ extern bool sched_rt_bandwidth_account(struct
> > rt_rq *rt_rq); /*
> >   * This function implements the GRUB accounting rule:
> >   * according to the GRUB reclaiming algorithm, the runtime is
> > + * not decreased as "dq = -dt", but as "dq = (1 - Uinact) dt",
> > where  
> 
> Changelog had it right I think: dq = -(1 - Uinact) dt

Sorry about the typo... I'll fix it


> > + * Uinact is the (per-runqueue) inactive utilization, computed as
> > the
> > + * difference between the "total runqueue utilization" and the
> > runqueue
> > + * active utilization.
> > + * Since rq->dl.running_bw and rq->dl.this_bw contain utilizations
> > + * multiplied by 2^20, the result has to be shifted right by 20.
> >   */
> > -u64 grub_reclaim(u64 delta, struct rq *rq)
> > +u64 grub_reclaim(u64 delta, struct rq *rq, u64 u)
> >  {
> > +	u64 u_act;
> > +
> > +	if (rq->dl.this_bw - rq->dl.running_bw > (1 << 20) - u)
> > +		u_act = u;
> > +	else
> > +		u_act = (1 << 20) - rq->dl.this_bw +
> > rq->dl.running_bw; +
> > +	return (delta * u_act) >> 20;  
> 
> But that's not what is done here I think, something like this instead:
> 
> 	Uinact = Utot - Uact
> 
> 		-t_u dt ; Uinact > (1 - t_u)
> 	dq = {
> 		-(1 - Uinact) dt
> 
> 
> And nowhere do we have an explanation for that.

Sorry about this confusion... The accounting should be
	dq = -(1 - Uinact)dt
but if (1 - Uinact) is too large (larger than the task's utilization)
then we use the task's utilization instead (otherwise, we end up
reclaiming other runqueues' time). I realized that this check was
needed after writing the comments, and I forgot to update the comments
when I fixed the code :(

> Now, I suspect we can write that like: dq = -max{ t_u, (1 - Uinact) }
> dt, which would suggest this is a sanity check on Utot, which I
> suspect can be over 1. Is this what is happening?

Right... I'll fix the code and comments according to your suggestion.


			Thanks,
				Luca


> #define BW_SHIFT	20
> #define BW_UNIT		(1 << BW_SHIFT)
> 
> static inline
> u64 grub_reclaim(u64 delta, struct rq *rq, struct sched_dl_entity
> *dl_se) {
> 	u64 u_inact = rq->dl.this_bw - rq->dl.running_bw; /* Utot -
> Uact */ u64 u_act;
> 
> 	/*
>          * What we want to write is:
> 	 *
> 	 *   max(BW_UNIT - u_inact, dl_se->dl_bw)
> 	 *
> 	 * but we cannot do that since Utot can be larger than 1,
> 	 * which means u_inact can be larger than 1, which would
> 	 * have the above result in negative values.
> 	 */
> 	if (u_inact > (BW_UNIT - dl_se->dl_bw))
> 		u_act = dl_se->dl_bw;
> 	else
> 		u_act = BW_UNIT - u_inact;
> 
> 	return (delta * u_act) >> BW_SHIFT;
> }
> 
> Hmm?