Date: Mon, 27 Mar 2017 16:56:51 +0200
From: Luca Abeni <luca.abeni@santannapisa.it>
To: Peter Zijlstra <peterz@infradead.org>
Cc: linux-kernel@vger.kernel.org, Ingo Molnar <mingo@redhat.com>,
        Juri Lelli <juri.lelli@arm.com>,
        Claudio Scordino <claudio@evidence.eu.com>,
        Steven Rostedt <rostedt@goodmis.org>,
        Tommaso Cucinotta <tommaso.cucinotta@sssup.it>,
        Daniel Bristot de Oliveira <bristot@redhat.com>,
        Joel Fernandes <joelaf@google.com>,
        Mathieu Poirier <mathieu.poirier@linaro.org>
Subject: Re: [RFC v5 8/9] sched/deadline: base GRUB reclaiming on the
 inactive utilization
Message-ID: <20170327165651.2d09b00d@luca>
In-Reply-To: <20170327142633.nubm5saddpitylot@hirez.programming.kicks-ass.net>
References: <1490327582-4376-1-git-send-email-luca.abeni@santannapisa.it>
        <1490327582-4376-9-git-send-email-luca.abeni@santannapisa.it>
        <20170327142633.nubm5saddpitylot@hirez.programming.kicks-ass.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 3938
Lines: 122

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

> On Fri, Mar 24, 2017 at 04:53:01AM +0100, luca abeni wrote:
> > From: Luca Abeni <luca.abeni@santannapisa.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@santannapisa.it>
> > Tested-by: Daniel Bristot de Oliveira <bristot@redhat.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?