Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::3:5 as permitted sender) client-ip=2620:137:e000::3:5;
Message-ID: <699cc8b1-f341-4af7-9c47-fee961c5c4b7@bytedance.com>
Date:   Thu, 12 Oct 2023 18:25:06 +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>
From:   Abel Wu <wuyun.abel@bytedance.com>
In-Reply-To: <xm26bkd4x5v4.fsf@bsegall-linux.svl.corp.google.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: bulk

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?

> 
>>
>>>    +		/* 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.