linux-kernel - Re: [PATCH 05/15] sched/fair: Implement an EEVDF like policy

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: <20231002173904.GA27267@noisy.programming.kicks-ass.net>
Date:   Mon, 2 Oct 2023 19:39:04 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Benjamin Segall <bsegall@...gle.com>
Cc:     mingo@...nel.org, vincent.guittot@...aro.org,
        linux-kernel@...r.kernel.org, juri.lelli@...hat.com,
        dietmar.eggemann@....com, rostedt@...dmis.org, mgorman@...e.de,
        bristot@...hat.com, corbet@....net, qyousef@...alina.io,
        chris.hyser@...cle.com, patrick.bellasi@...bug.net, pjt@...gle.com,
        pavel@....cz, qperret@...gle.com, tim.c.chen@...ux.intel.com,
        joshdon@...gle.com, timj@....org, kprateek.nayak@....com,
        yu.c.chen@...el.com, youssefesmat@...omium.org,
        joel@...lfernandes.org, efault@....de, tglx@...utronix.de
Subject: Re: [PATCH 05/15] sched/fair: Implement an EEVDF like policy

On Fri, Sep 29, 2023 at 02:40:31PM -0700, Benjamin Segall wrote:

> > +static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
> > +{
> > +	struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
> > +	struct sched_entity *curr = cfs_rq->curr;
> > +	struct sched_entity *best = NULL;
> > +
> > +	if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
> > +		curr = NULL;
> > +
> > +	while (node) {
> > +		struct sched_entity *se = __node_2_se(node);
> > +
> > +		/*
> > +		 * If this entity is not eligible, try the left subtree.
> > +		 */
> > +		if (!entity_eligible(cfs_rq, se)) {
> > +			node = node->rb_left;
> > +			continue;
> > +		}
> > +
> > +		/*
> > +		 * If this entity has an earlier deadline than the previous
> > +		 * best, take this one. If it also has the earliest deadline
> > +		 * of its subtree, we're done.
> > +		 */
> > +		if (!best || deadline_gt(deadline, best, se)) {
> > +			best = se;
> > +			if (best->deadline == best->min_deadline)
> > +				break;
> > +		}
> > +
> > +		/*
> > +		 * If the earlest deadline in this subtree is in the fully
> > +		 * eligible left half of our space, go there.
> > +		 */
> > +		if (node->rb_left &&
> > +		    __node_2_se(node->rb_left)->min_deadline == se->min_deadline) {
> > +			node = node->rb_left;
> > +			continue;
> > +		}
> > +
> > +		node = node->rb_right;
> > +	}
> 
> I believe that this can fail to actually find the earliest eligible
> deadline, because the earliest deadline (min_deadline) can be in the
> right branch, but that se isn't eligible, and the actual target se is in
> the left branch. A trivial 3-se example with the nodes represented by
> (vruntime, deadline, min_deadline):
> 
>    (5,9,7)
>  /        \
> (4,8,8)  (6,7,7)
> 
> AIUI, here the EEVDF pick should be (4,8,8), but pick_eevdf() will
> instead pick (5,9,7), because it goes into the right branch and then
> fails eligibility.
> 
> I'm not sure how much of a problem this is in practice, either in
> frequency or severity, but it probably should be mentioned if it's
> an intentional tradeoff.

Well, that is embarrassing :-(

You're quite right -- and I *SHOULD* have double checked my decade old
patches, but alas.

Re-reading the paper, your proposal is fairly close to what they have.
Let me go stare at your patch in more detail.