Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753437AbdC0O55 (ORCPT ); Mon, 27 Mar 2017 10:57:57 -0400 Received: from mail.santannapisa.it ([193.205.80.99]:35252 "EHLO mail.santannapisa.it" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752336AbdC0O52 (ORCPT ); Mon, 27 Mar 2017 10:57:28 -0400 Date: Mon, 27 Mar 2017 16:56:51 +0200 From: Luca Abeni To: Peter Zijlstra Cc: linux-kernel@vger.kernel.org, Ingo Molnar , Juri Lelli , Claudio Scordino , Steven Rostedt , Tommaso Cucinotta , Daniel Bristot de Oliveira , Joel Fernandes , Mathieu Poirier 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> X-Mailer: Claws Mail 3.13.2 (GTK+ 2.24.30; x86_64-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3938 Lines: 122 On Mon, 27 Mar 2017 16:26:33 +0200 Peter Zijlstra wrote: > On Fri, Mar 24, 2017 at 04:53:01AM +0100, luca abeni wrote: > > From: Luca Abeni > > > > 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 > > Tested-by: Daniel Bristot de Oliveira > > --- > > 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?