Re: Re: [PATCH] sched/fair: fix pick_eevdf to always find the correct se

[Abel Wu]

On 10/12/23 5:01 AM, Benjamin Segall Wrote:
> Abel Wu <wuyun.abel@xxxxxxxxxxxxx> writes:
>
> > On 9/30/23 8:09 AM, Benjamin Segall Wrote:
> > > +	/*
> > > +	 * Now best_left and all of its children are eligible, and we are just
> > > +	 * looking for deadline == min_deadline
> > > +	 */
> > > +	node = &best_left->run_node;
> > > +	while (node) {
> > > +		struct sched_entity *se = __node_2_se(node);
> > > +
> > > +		/* min_deadline is the current node */
> > > +		if (se->deadline == se->min_deadline)
> > > +			return se;
> >
> > IMHO it would be better tiebreak on vruntime by moving this hunk to ..
> >
> > > +
> > > +		/* min_deadline is in the left branch */
> > >    		if (node->rb_left &&
> > >    		    __node_2_se(node->rb_left)->min_deadline == se->min_deadline) {
> > >    			node = node->rb_left;
> > >    			continue;
> > >    		}
> >
> > .. here, thoughts?
>
> Yeah, that should work and be better on the tiebreak (and my test code
> agrees). There's an argument that the tiebreak will never really come up
> and it's better to avoid the potential one extra cache line from
> "__node_2_se(node->rb_left)->min_deadline" though.

I see. Then probably do the same thing in the first loop?

> > >    +		/* else min_deadline is in the right branch */
> > >    		node = node->rb_right;
> > >    	}
> > > +	return NULL;
> >
> > Why not 'best'? Since ..
>
> The only time this can happen is if the tree is corrupt. We only reach
> this case if best_left is set at all (and best_left's min_deadline is
> better than "best"'s, which includes curr). In that case getting an
> error message is good, and in general I wasn't worrying about it much.

Right.

> > > +}
> > >    -	if (!best || (curr && deadline_gt(deadline, best, curr)))
> > > -		best = curr;
> > > +static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
> > > +{
> > > +	struct sched_entity *se = __pick_eevdf(cfs_rq);
> > >    -	if (unlikely(!best)) {
> > > +	if (!se) {
> > >    		struct sched_entity *left = __pick_first_entity(cfs_rq);
> >
> > .. cfs_rq->curr isn't considered here.
>
> That said, we should probably consider curr here in the error-case
> fallback, if just as a "if (!left) left = cfs_rq->curr;"

I don't think so as there must be some bugs in the scheduler, replacing
'pr_err' with 'BUG()' would be more appropriate.

> I've also attached my ugly userspace EEVDF tester as an attachment,
> hopefully I attached it in a correct mode to go through lkml.

Received. Thanks, Ben.