Re: [PATCH 08/17] sched/fair: Implement an EEVDF like policy

[Peter Zijlstra]

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;
> > +}