[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <xm26pm1jhgpx.fsf@bsegall-linux.svl.corp.google.com>
Date: Thu, 12 Oct 2023 10:51:22 -0700
From: Benjamin Segall <bsegall@...gle.com>
To: Abel Wu <wuyun.abel@...edance.com>
Cc: Peter Zijlstra <peterz@...radead.org>, 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] sched/fair: fix pick_eevdf to always find the correct se
Abel Wu <wuyun.abel@...edance.com> writes:
> On 10/12/23 5:01 AM, Benjamin Segall Wrote:
>> Abel Wu <wuyun.abel@...edance.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.
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)
Powered by blists - more mailing lists