linux-kernel - Re: [PATCH 08/17] 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: <20230329080646.GL4253@hirez.programming.kicks-ass.net>
Date:   Wed, 29 Mar 2023 10:06:46 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Josh Don <joshdon@...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, bsegall@...gle.com,
        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, timj@....org,
        kprateek.nayak@....com, yu.c.chen@...el.com,
        youssefesmat@...omium.org, joel@...lfernandes.org, efault@....de
Subject: Re: [PATCH 08/17] sched/fair: Implement an EEVDF like policy

On Tue, Mar 28, 2023 at 06:26:51PM -0700, Josh Don 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;
> 
> Isn't it possible to have a child with less vruntime (ie. rb->left)
> but with the same deadline? Wouldn't it be preferable to choose the
> child instead since the deadlines are equivalent but the child has
> received less service time?

Possible, yes I suppose. But given this is ns granular virtual time,
somewhat unlikely. You can modify the last (validation) patch and have
it detect the case, see if you can trigger it.

Doing that will make the pick always do a full decent of the tree
through, which is a little more expensive. Not sure it's worth the
effort.

> > +               }
> > +
> > +               /*
> > +                * 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;
> > +       }
> > +
> > +       if (!best || (curr && deadline_gt(deadline, best, curr)))
> > +               best = curr;
> > +
> > +       if (unlikely(!best)) {
> > +               struct sched_entity *left = __pick_first_entity(cfs_rq);
> > +               if (left) {
> > +                       pr_err("EEVDF scheduling fail, picking leftmost\n");
> > +                       return left;
> > +               }
> > +       }
> > +
> > +       return best;
> > +}