Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:4 as permitted sender) client-ip=2620:137:e000::3:4;
Message-ID: <e2a42ff2-d0f9-4963-bed7-229224ee8287@bytedance.com>
Date:   Fri, 13 Oct 2023 11:46:24 +0800
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Re: [PATCH] sched/fair: fix pick_eevdf to always find the correct
 se
Content-Language: en-US
To:     Benjamin Segall <bsegall@google.com>
Cc:     Peter Zijlstra <peterz@infradead.org>, mingo@kernel.org,
        vincent.guittot@linaro.org, linux-kernel@vger.kernel.org,
        juri.lelli@redhat.com, dietmar.eggemann@arm.com,
        rostedt@goodmis.org, mgorman@suse.de, bristot@redhat.com,
        corbet@lwn.net, qyousef@layalina.io, chris.hyser@oracle.com,
        patrick.bellasi@matbug.net, pjt@google.com, pavel@ucw.cz,
        qperret@google.com, tim.c.chen@linux.intel.com, joshdon@google.com,
        timj@gnu.org, kprateek.nayak@amd.com, yu.c.chen@intel.com,
        youssefesmat@chromium.org, joel@joelfernandes.org, efault@gmx.de,
        tglx@linutronix.de
References: <20230531115839.089944915@infradead.org>
 <20230531124603.931005524@infradead.org> <xm261qego72d.fsf_-_@google.com>
 <6b606049-3412-437f-af25-a4c33139e2d8@bytedance.com>
 <xm26bkd4x5v4.fsf@bsegall-linux.svl.corp.google.com>
 <699cc8b1-f341-4af7-9c47-fee961c5c4b7@bytedance.com>
 <xm26pm1jhgpx.fsf@bsegall-linux.svl.corp.google.com>
From:   Abel Wu <wuyun.abel@bytedance.com>
In-Reply-To: <xm26pm1jhgpx.fsf@bsegall-linux.svl.corp.google.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk

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)