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: <20170327142633.nubm5saddpitylot@hirez.programming.kicks-ass.net>
Date:   Mon, 27 Mar 2017 16:26:33 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     luca abeni <luca.abeni@...tannapisa.it>
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 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.

> 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


> + * 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.

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?



#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?