Messages in this thread Patch in this message | | | Date | Fri, 13 Oct 2023 11:46:24 +0800 | Subject | Re: Re: [PATCH] sched/fair: fix pick_eevdf to always find the correct se | From | Abel Wu <> |
| |
On 10/13/23 1:51 AM, Benjamin Segall Wrote: > Abel Wu <wuyun.abel@bytedance.com> writes: > >> On 10/12/23 5:01 AM, Benjamin Segall Wrote: >>> Abel Wu <wuyun.abel@bytedance.com> 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? >> > > We effectively do that already sorta by accident almost always - > computing best and best_left via deadline_gt rather than gte prioritizes > earlier elements, which always have a better vruntime.
Sorry for not clarifying clearly about the 'same thing'. What I meant was to avoid touch left if the node itself has the min deadline.
@@ -894,6 +894,9 @@ static struct sched_entity *__pick_eevdf(struct cfs_rq *cfs_rq) if (!best || deadline_gt(deadline, best, se)) best = se;
+ if (se->deadline == se->min_deadline) + break; + /* * Every se in a left branch is eligible, keep track of the * branch with the best min_deadline @@ -913,10 +916,6 @@ static struct sched_entity *__pick_eevdf(struct cfs_rq *cfs_rq) break; }
- /* min_deadline is at this node, no need to look right */ - if (se->deadline == se->min_deadline) - break; - /* else min_deadline is in the right branch. */ node = node->rb_right; } (But still thanks for the convincing explanation on fairness.)
Best, Abel
> > Then when we do the best_left->min_deadline vs best->deadline > computation, we prioritize best_left, which is the one case it can be > wrong, we'd need an additional > "if (se->min_deadline == best->deadline && > (s64)(se->vruntime - best->vruntime) > 0) return best;" check at the end > of the second loop. > > (Though again I don't know how much this sort of never-going-to-happen > slight fairness improvement is worth compared to the extra bit of > overhead)
| |