Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <0e569d64-ce35-2176-5d41-faa6997480ef@bytedance.com>
Date:   Thu, 23 Mar 2023 15:01:59 +0800
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0)
 Gecko/20100101 Thunderbird/102.6.1
Subject: Re: [External] Re: [PATCH] sched/core: Minor optimize
 pick_next_task() when core-sched enable
To:     Vineeth Pillai <vineethrp@google.com>,
        Joel Fernandes <joel@joelfernandes.org>
Cc:     mingo@redhat.com, peterz@infradead.org, mingo@kernel.org,
        juri.lelli@redhat.com, vincent.guittot@linaro.org,
        dietmar.eggemann@arm.com, rostedt@goodmis.org, bsegall@google.com,
        mgorman@suse.de, bristot@redhat.com, vschneid@redhat.com,
        mgorman@techsingularity.net, linux-kernel@vger.kernel.org,
        Josh Don <joshdon@google.com>
References: <20230308100414.37114-1-jiahao.os@bytedance.com>
 <4972a8be-d300-a66e-7fac-a83f11b56fbf@bytedance.com>
 <CAEXW_YRG0Bw4U1+zOPpjRPQEeKNDMrs7x-ZE-W00aifn7heG4g@mail.gmail.com>
 <CA+HDTgT0sjt38E4-2uQs_2t1GSsYFDqz3porOx-WQbt8x9hhXw@mail.gmail.com>
From:   Hao Jia <jiahao.os@bytedance.com>
In-Reply-To: <CA+HDTgT0sjt38E4-2uQs_2t1GSsYFDqz3porOx-WQbt8x9hhXw@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Precedence: bulk


On 2023/3/23 Vineeth Pillai wrote:
> Merging two threads.
> 
> On Tue, Mar 21, 2023 at 5:40 PM Joel Fernandes <joel@joelfernandes.org> wrote:
>>>
>>> CPU0 and CPU1 are two CPUs on the same core, task0 and task2 are the
>>> highest priority tasks on rq0 and rq1 respectively, task2 is @max
>>> on the entire core.
> 
>> I'm assuming this all starts by rq0 doing a pick and getting task0.
>> Because any other selection would go down the whole !need_sync route.
>>
> I think this could also happen when rq1 starts the pick due to task2 wakeup
> while task0 was running in rq0. In this case, core->core_cookie would be set
> and we take the need_sync path I guess.
> 
>>> In the case that 'max' has a zero cookie, instead of continuing to
>>> search for a runnable task on rq0 that matches @max's cookie, we
>>> choose idle for rq0 directly.
>>> At this time, it is obviously better to choose task1 to run for rq0,
>>> which will increase the CPU utilization.
>>> Therefore, we queue tasks with zero cookies in core_tree, and record
>>> the number of non-zero cookie tasks of each rq to detect the status
>>> of the sched-core.
>>
>> I do remember this as a known issue (more of a known but unimplemented
>> optimization) which happens when you have a high priority non-cookie
>> task which is in front of several low priority ones on the same
>> thread/rq. Adding +Vineeth Pillai to see if he remembers the issue.
>>
> Yes, I remember this as one of the 2 issues we noticed, but could not get to
> fixing it. Here we have non-cookied tasks considered special as a side effect
> of implementation(non-cookied tasks not in core rbtree) and hence we force idle
> if max is non-cookied and the highest prio task on the sibling is cookied.
> 
> The other issue was - we don't update core rbtree when vruntime changes and
> this can cause starvation of cookied task if there are more than one task with
> the same cookie on an rq.
> 

If I understand correctly, when a cookied task is enqueued, the 
difference delta1 between its vruntime and min_vruntime is very large.

Another task with the same cookie is very actively dequeuing and 
enqueuing, and the difference delta2 between its vruntime and 
min_vruntime is always smaller than delta1?
I'm not sure if this is the case?

>>>   static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
>>>   {
>>> - if (sched_core_enabled(rq))
>>> - sched_core_dequeue(rq, p, flags);
>>> + sched_core_dequeue(rq, p, flags);
>>>
>>>   if (!(flags & DEQUEUE_NOCLOCK))
>>>   update_rq_clock(rq);
> 
>> Yeah, this is an absolute no-no, it makes the overhead of the second rb
>> tree unconditional.
> 
> I agree. Could we keep it conditional by enqueuing 0-cookied tasks only when
> coresched is enabled, just like what we do for cookied tasks? This is still an
> overhead where we have two trees storing all the runnable tasks but in
> different order. We would also need to populate core rbtree from cfs rbtree
> on coresched enable and empty the tree on coresched disable.
> 

I'm not sure if the other way is reasonable, I'm trying to provide a 
function for each scheduling class to find a highest priority non-cookie 
task.

For example fair_sched_class, we can use rq->cfs_tasks to traverse the 
search. But this search may take a long time, maybe we need to limit the 
number of searches.

Thanks,
Hao