Re: [PATCH v3 0/7] sched: Implement shared runqueue in CFS

[K Prateek Nayak <kprateek.nayak@amd.com>]

Hello David,

Thank you for taking a look at the report.

On 8/31/2023 8:02 AM, David Vernet wrote:
> On Wed, Aug 30, 2023 at 03:26:40PM +0530, K Prateek Nayak wrote:
>> Hello David,
> 
> Hello Prateek,
> 
>>
>> Short update based on some of my experimentation.
>>
>> Disclaimer: I've been only looking at tbench 128 client case on a dual
>> socket 3rd Generation EPYC system (2x 64C/128T). Wider results may
>> vary but I have some information that may help with the debug and to
>> proceed further.
>>
>> On 8/25/2023 4:21 AM, David Vernet wrote:
>>> On Thu, Aug 24, 2023 at 04:44:19PM +0530, Gautham R. Shenoy wrote:
>>>> Hello David,
>>>>
>>>> On Fri, Aug 18, 2023 at 02:19:03PM +0530, Gautham R. Shenoy wrote:
>>>>> Hello David,
>>>>>
>>>>> On Fri, Aug 18, 2023 at 12:03:55AM -0500, David Vernet wrote:
>>>>>> On Thu, Aug 17, 2023 at 02:12:03PM +0530, Gautham R. Shenoy wrote:
>>>>>>> Hello David,
>>>>>>
>>>>>> Hello Gautham,
>>>>>>
>>>>>> Thanks a lot as always for running some benchmarks and analyzing these
>>>>>> changes.
>>>>>>
>>>>>>> On Wed, Aug 09, 2023 at 05:12:11PM -0500, David Vernet wrote:
>>>>>>>> Changes
>>>>>>>> -------
>>>>>>>>
>>>>>>>> This is v3 of the shared runqueue patchset. This patch set is based off
>>>>>>>> of commit 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs
>>>>>>>> bandwidth in use") on the sched/core branch of tip.git.
>>>>>>>
>>>>>>>
>>>>>>> I tested the patches on Zen3 and Zen4 EPYC Servers like last time. I
>>>>>>> notice that apart from hackbench, every other bechmark is showing
>>>>>>> regressions with this patch series. Quick summary of my observations:
>>>>>>
>>>>>> Just to verify per our prior conversation [0], was this latest set of
>>>>>> benchmarks run with boost disabled?
>>>>>
>>>>> Boost is enabled by default. I will queue a run tonight with boost
>>>>> disabled.
>>>>
>>>> Apologies for the delay. I didn't see any changes with boost-disabled
>>>> and with reverting the optimization to bail out of the
>>>> newidle_balance() for SMT and MC domains when there was no task to be
>>>> pulled from the shared-runq. I reran the whole thing once again, just
>>>> to rule out any possible variance. The results came out the same.
>>>
>>> Thanks a lot for taking the time to run more benchmarks.
>>>
>>>> With the boost disabled, and the optimization reverted, the results
>>>> don't change much.
>>>
>>> Hmmm, I see. So, that was the only real substantive "change" between v2
>>> -> v3. The other changes were supporting hotplug / domain recreation,
>>> optimizing locking a bit, and fixing small bugs like the return value
>>> from shared_runq_pick_next_task(), draining the queue when the feature
>>> is disabled, and fixing the lkp errors.
>>>
>>> With all that said, it seems very possible that the regression is due to
>>> changes in sched/core between commit ebb83d84e49b ("sched/core: Avoid
>>> multiple calling update_rq_clock() in __cfsb_csd_unthrottle()") in v2,
>>> and commit 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when cfs
>>> bandwidth in use") in v3. EEVDF was merged in that window, so that could
>>> be one explanation for the context switch rate being so much higher.
>>>
>>>> It doesn't appear that the optimization is the cause for increase in
>>>> the number of load-balancing attempts at the DIE and the NUMA
>>>> domains. I have shared the counts of the newidle_balance with and
>>>> without SHARED_RUNQ below for tbench and it can be noticed that the
>>>> counts are significantly higher for the 64 clients and 128 clients. I
>>>> also captured the counts/s of find_busiest_group() using funccount.py
>>>> which tells the same story. So the drop in the performance for tbench
>>>> with your patches strongly correlates with the increase in
>>>> load-balancing attempts.
>>>>
>>>> newidle balance is undertaken only if the overload flag is set and the
>>>> expected idle duration is greater than the avg load balancing cost. It
>>>> is hard to imagine why should the shared runq cause the overload flag
>>>> to be set!
>>>
>>> Yeah, I'm not sure either about how or why woshared_runq uld cause this
>>> This is purely hypothetical, but is it possible that shared_runq causes
>>> idle cores to on average _stay_ idle longer due to other cores pulling
>>> tasks that would have otherwise been load balanced to those cores?
>>>
>>> Meaning -- say CPU0 is idle, and there are tasks on other rqs which
>>> could be load balanced. Without shared_runq, CPU0 might be woken up to
>>> run a task from a periodic load balance. With shared_runq, any active
>>> core that would otherwise have gone idle could pull the task, keeping
>>> CPU0 idle.
>>>
>>> What do you think? I could be totally off here.
>>>
>>> From my perspective, I'm not too worried about this given that we're
>>> seeing gains in other areas such as kernel compile as I showed in [0],
>>> though I definitely would like to better understand it.
>>
>> Let me paste a cumulative diff containing everything I've tried since
>> it'll be easy to explain.
>>
>> o Performance numbers for tbench 128 clients:
>>
>> tip			: 1.00 (Var: 0.57%)
>> tip + vanilla v3	: 0.39 (var: 1.15%) (%diff: -60.74%)
>> tip + v3 + diff		: 0.99 (var: 0.61%) (%diff: -00.24%)
>>
>> tip is at commit 88c56cfeaec4 ("sched/fair: Block nohz tick_stop when
>> cfs bandwidth in use"), same as what Gautham used, so no EEVDF yet.
>>
>> o Cumulative Diff
>>
>> Should apply cleanly on top of tip at above commit + this series as is.
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -198,7 +198,7 @@ struct shared_runq_shard {
>>  } ____cacheline_aligned;
>>  
>>  /* This would likely work better as a configurable knob via debugfs */
>> -#define SHARED_RUNQ_SHARD_SZ 6
>> +#define SHARED_RUNQ_SHARD_SZ 16
>>  #define SHARED_RUNQ_MAX_SHARDS \
>>  	((NR_CPUS / SHARED_RUNQ_SHARD_SZ) + (NR_CPUS % SHARED_RUNQ_SHARD_SZ != 0))
>>  
>> @@ -322,20 +322,36 @@ void shared_runq_toggle(bool enabling)
>>  }
>>  
>>  static struct task_struct *
>> -shared_runq_pop_task(struct shared_runq_shard *shard, int target)
>> +shared_runq_pop_task(struct shared_runq_shard *shard, struct rq *rq)
>>  {
>> +	int target = cpu_of(rq);
>>  	struct task_struct *p;
>>  
>>  	if (list_empty(&shard->list))
>>  		return NULL;
>>  
>>  	raw_spin_lock(&shard->lock);
>> +again:
>>  	p = list_first_entry_or_null(&shard->list, struct task_struct,
>>  				     shared_runq_node);
>> -	if (p && is_cpu_allowed(p, target))
>> +
>> +	/* If we find a task, delete if from list regardless */
>> +	if (p) {
>>  		list_del_init(&p->shared_runq_node);
>> -	else
>> -		p = NULL;
>> +
>> +		if (!task_on_rq_queued(p) ||
>> +		    task_on_cpu(task_rq(p), p) ||
> 
> Have you observed !task_on_rq_queued() or task_on_cpu() returning true
> here? The task should have removed itself from the shard when
> __dequeue_entity() is called from set_next_entity() when it's scheduled
> in pick_next_task_fair(). The reason we have to check in
> shared_runq_pick_next_task() is that between dequeuing the task from the
> shared_runq and getting its rq lock, it could have been scheduled on its
> current rq. But if the task was scheduled first, it should have removed
> itself from the shard.

Ah! Thank you for clarifying. This is just a copy-paste of the bailout
in shared_runq_pick_next_task(). I see "!task_on_rq_queued()" cannot be
true here since this is with the shared rq lock held. Thank you for
pointing this out.

> 
>> +		    !is_cpu_allowed(p, target)) {
>> +			if (rq->ttwu_pending) {
>> +				p = NULL;
>> +				goto out;
>> +			}
> 
> Have you observed this as well? If the task is enqueued on the ttwu
> queue wakelist, it isn't enqueued on the waking CPU, so it shouldn't be
> added to the shared_runq right?

This is a bailout on the retry logic. Since the shared_rq could contain
many tasks, I did not want to retry until the queue goes empty with a
possible pending wakeup. ... [1]

> 
>> +
>> +			goto again;
>> +		}
>> +	}
>> +
>> +out:
>>  	raw_spin_unlock(&shard->lock);
>>  
>>  	return p;
>> @@ -380,9 +396,12 @@ static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
>>  		curr_idx = (starting_idx + i) % num_shards;
>>  		shard = &shared_runq->shards[curr_idx];
>>  
>> -		p = shared_runq_pop_task(shard, cpu_of(rq));
>> +		p = shared_runq_pop_task(shard, rq);
>>  		if (p)
>>  			break;
>> +
>> +		if (rq->ttwu_pending)
>> +			return 0;
> 
> Same here r.e. rq->ttwu_pending. This should be handled in the
> 
> if (task_on_rq_queued(p) && !task_on_cpu(src_rq, p))
> 
> check below, no? Note that task_on_rq_queued(p) should only return true
> if the task has made it to ttwu_do_activate(), and if it hasn't, I don't
> think it should be in the shard in the first place.

Noted! Thank you for clarifying again. 

> 
>>  	}
>>  	if (!p)
>>  		return 0;
>> @@ -395,17 +414,16 @@ static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
>>  	if (task_on_rq_queued(p) && !task_on_cpu(src_rq, p)) {
>>  		update_rq_clock(src_rq);
>>  		src_rq = move_queued_task(src_rq, &src_rf, p, cpu_of(rq));
>> -		ret = 1;
>>  	}
>>  
>>  	if (src_rq != rq) {
>>  		task_rq_unlock(src_rq, p, &src_rf);
>>  		raw_spin_rq_lock(rq);
>>  	} else {
>> +		ret = 1;
>>  		rq_unpin_lock(rq, &src_rf);
>>  		raw_spin_unlock_irqrestore(&p->pi_lock, src_rf.flags);
>>  	}
>> -	rq_repin_lock(rq, rf);
> 
> Huh, wouldn't this cause a WARN to be issued the next time we invoke
> rq_clock() in newidle_balance() if we weren't able to find a task? Or
> was it because we moved the SHARED_RUNQ logic to below where we check
> rq_clock()? In general though, I don't think this should be removed. At
> the very least, it should be tested with lockdep.

So beyond this point, ret != 0, which will now jump to "out_swq" label
in newidle_balance()  which does a "rq_repin_lock(this_rq, rf)" just
before returning.

I'll check if my surgery is right with lockdep enabled.

> 
>>  	return ret;
>>  }
>> @@ -12344,50 +12362,59 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
>>  	if (!cpu_active(this_cpu))
>>  		return 0;
>>  
>> -	if (sched_feat(SHARED_RUNQ)) {
>> -		pulled_task = shared_runq_pick_next_task(this_rq, rf);
>> -		if (pulled_task)
>> -			return pulled_task;
>> -	}
>> -
>>  	/*
>>  	 * We must set idle_stamp _before_ calling idle_balance(), such that we
>>  	 * measure the duration of idle_balance() as idle time.
>>  	 */
>>  	this_rq->idle_stamp = rq_clock(this_rq);
>>  
>> -	/*
>> -	 * This is OK, because current is on_cpu, which avoids it being picked
>> -	 * for load-balance and preemption/IRQs are still disabled avoiding
>> -	 * further scheduler activity on it and we're being very careful to
>> -	 * re-start the picking loop.
>> -	 */
>> -	rq_unpin_lock(this_rq, rf);
>> -
>>  	rcu_read_lock();
>> -	sd = rcu_dereference_check_sched_domain(this_rq->sd);
>> -
>> -	/*
>> -	 * Skip <= LLC domains as they likely won't have any tasks if the
>> -	 * shared runq is empty.
>> -	 */
>> -	if (sched_feat(SHARED_RUNQ)) {
>> +	if (sched_feat(SHARED_RUNQ))
>>  		sd = rcu_dereference(*this_cpu_ptr(&sd_llc));
>> -		if (likely(sd))
>> -			sd = sd->parent;
>> -	}
>> +	else
>> +		sd = rcu_dereference_check_sched_domain(this_rq->sd);
>>  
>>  	if (!READ_ONCE(this_rq->rd->overload) ||
>>  	    (sd && this_rq->avg_idle < sd->max_newidle_lb_cost)) {
>>  
>> -		if (sd)
>> +		while (sd) {
>>  			update_next_balance(sd, &next_balance);
>> +			sd = sd->child;
>> +		}
>> +
>>  		rcu_read_unlock();
>>  
>>  		goto out;
>>  	}
>>  	rcu_read_unlock();
>>  
>> +	t0 = sched_clock_cpu(this_cpu);
>> +	if (sched_feat(SHARED_RUNQ)) {
>> +		pulled_task = shared_runq_pick_next_task(this_rq, rf);
>> +		if (pulled_task) {
>> +			curr_cost = sched_clock_cpu(this_cpu) - t0;
>> +			update_newidle_cost(sd, curr_cost);
>> +			goto out_swq;
>> +		}
>> +	}
> 
> Hmmm, why did you move this further down in newidle_balance()? We don't
> want to skip trying to get a task from the shared_runq if rq->avg_idle <
> sd->max_newidle_lb_cost.

I'll check if only rd->overload check is sufficient.

> 
>> +
>> +	/* Check again for pending wakeups */
>> +	if (this_rq->ttwu_pending)
>> +		return 0;
>> +
>> +	t1 = sched_clock_cpu(this_cpu);
>> +	curr_cost += t1 - t0;
>> +
>> +	if (sd)
>> +		update_newidle_cost(sd, curr_cost);
>> +
>> +	/*
>> +	 * This is OK, because current is on_cpu, which avoids it being picked
>> +	 * for load-balance and preemption/IRQs are still disabled avoiding
>> +	 * further scheduler activity on it and we're being very careful to
>> +	 * re-start the picking loop.
>> +	 */
>> +	rq_unpin_lock(this_rq, rf);
>>  	raw_spin_rq_unlock(this_rq);
>>  
>>  	t0 = sched_clock_cpu(this_cpu);
>> @@ -12400,6 +12427,13 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
>>  
>>  		update_next_balance(sd, &next_balance);
>>  
>> +		/*
>> +		 * Skip <= LLC domains as they likely won't have any tasks if the
>> +		 * shared runq is empty.
>> +		 */
>> +		if (sched_feat(SHARED_RUNQ) && (sd->flags & SD_SHARE_PKG_RESOURCES))
>> +			continue;
> 
> This makes sense to me, good call.
> 
>> +
>>  		if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
>>  			break;
>>  
>> @@ -12429,6 +12463,7 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
>>  
>>  	raw_spin_rq_lock(this_rq);
>>  
>> +out_swq:
>>  	if (curr_cost > this_rq->max_idle_balance_cost)
>>  		this_rq->max_idle_balance_cost = curr_cost;
>>  
>> --
>>
>> o Breakdown
>>
>> I'll proceed to annotate a copy of diff with reasoning behind the changes:
> 
> Ah, ok, you provided explanations :-) I'll leave my questions above
> regardless for posterity.

And I'll refer to answers above ;)

> 
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -198,7 +198,7 @@ struct shared_runq_shard {
>>  } ____cacheline_aligned;
>>  
>>  /* This would likely work better as a configurable knob via debugfs */
>> -#define SHARED_RUNQ_SHARD_SZ 6
>> +#define SHARED_RUNQ_SHARD_SZ 16
>>  #define SHARED_RUNQ_MAX_SHARDS \
>>  	((NR_CPUS / SHARED_RUNQ_SHARD_SZ) + (NR_CPUS % SHARED_RUNQ_SHARD_SZ != 0))
>>
>> --
>>
>> 	Here I'm setting the SHARED_RUNQ_SHARD_SZ to sd_llc_size for
>> 	my machine. I played around with this and did not see any
>> 	contention for shared_rq lock while running tbench.
> 
> I don't really mind making the shard bigger because it will never be one
> size fits all, but for what it's worth, I saw less contention in netperf
> with a size of 6, but everything else performed fine with a larger
> shard. This is one of those "there's no right answer" things, I'm
> afraid. I think it will be inevitable to make this configurable at some
> point, if we find that it's really causing inefficiencies.

Agreed! For tbench at least, this did not lead to any problems.

> 
>> --
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -322,20 +322,36 @@ void shared_runq_toggle(bool enabling)
>>  }
>>  
>>  static struct task_struct *
>> -shared_runq_pop_task(struct shared_runq_shard *shard, int target)
>> +shared_runq_pop_task(struct shared_runq_shard *shard, struct rq *rq)
>>  {
>> +	int target = cpu_of(rq);
>>  	struct task_struct *p;
>>  
>>  	if (list_empty(&shard->list))
>>  		return NULL;
>>  
>>  	raw_spin_lock(&shard->lock);
>> +again:
>>  	p = list_first_entry_or_null(&shard->list, struct task_struct,
>>  				     shared_runq_node);
>> -	if (p && is_cpu_allowed(p, target))
>> +
>> +	/* If we find a task, delete if from list regardless */
> 
> As I mentioned in my other reply [0], I don't think we should always
> have to delete here. Let me know if I'm missing something.

I overlooked that condition at enqueue. I'll go back to original
implementation here.

> 
> [0]: https://lore.kernel.org/all/20230831013435.GB506447@maniforge/
> 
>> +	if (p) {
>>  		list_del_init(&p->shared_runq_node);
>> -	else
>> -		p = NULL;
>> +
>> +		if (!task_on_rq_queued(p) ||
>> +		    task_on_cpu(task_rq(p), p) ||
>> +		    !is_cpu_allowed(p, target)) {
>> +			if (rq->ttwu_pending) {
>> +				p = NULL;
>> +				goto out;
>> +			}
>> +
>> +			goto again;
>> +		}
>> +	}
>> +
>> +out:
>>  	raw_spin_unlock(&shard->lock);
>>  
>>  	return p;
>> --
>>
>> 	Context: When running perf with IBS, I saw following lock
>> 	contention:
>>
>> -   12.17%  swapper          [kernel.vmlinux]          [k] native_queued_spin_lock_slowpath
>>    - 10.48% native_queued_spin_lock_slowpath
>>       - 10.30% _raw_spin_lock
>>          - 9.11% __schedule
>>               schedule_idle
>>               do_idle
>>             + cpu_startup_entry
>>          - 0.86% task_rq_lock
>>               newidle_balance
>>               pick_next_task_fair
>>               __schedule
>>               schedule_idle
>>               do_idle
>>             + cpu_startup_entry
>>
>> 	So I imagined the newidle_balance is contending with another
>> 	run_queue going idle when pulling task. Hence, I moved some
>> 	checks in shared_runq_pick_next_task() to here.
> 
> Hmm, so the idea was to avoid contending on the rq lock? As I mentioned
> above, I'm not sure these checks actually buy us anything.

Yup! I think skipping newidle_balance() when rd->overload is not set
itself reduces this contention.

> 
>> 	I was not sure if the task's rq lock needs to be held to do this
>> 	to get an accurate result so I've left the original checks in
>> 	shared_runq_pick_next_task() as it is.
> 
> Yep, we need to have the rq lock held for these functions to return
> consistent data.

Noted! Will fall back to your implementation. Also I did not see
any perf improvement for tbench with this alone.

> 
>> 	Since retry may be costly, I'm using "rq->ttwu_pending" as a
>> 	bail out threshold. Maybe there are better alternates with
>> 	the lb_cost and rq->avg_idle but this was simpler for now.
> 
> Hmm, not sure I'm quite understanding this one. As I mentioned above, I
> don't _think_ this should ever be set for a task enqueued in a shard.
> Were you observing that?

Explained in [1] above. Let me get rid of that whole retry logic
because I see it leading to shared_rq lock contention at enqueue and
dequeue already.

> 
>> 	(Realizing as I write this that this will cause more contention
>> 	with enqueue/dequeue in a busy system. I'll check if that is the
>> 	case)
>>
>> 	P.S. This did not affect the ~60% regression I was seeing one
>> 	bit so the problem was deeper.
>>
>> --
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -380,9 +396,12 @@ static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
>>  		curr_idx = (starting_idx + i) % num_shards;
>>  		shard = &shared_runq->shards[curr_idx];
>>  
>> -		p = shared_runq_pop_task(shard, cpu_of(rq));
>> +		p = shared_runq_pop_task(shard, rq);
>>  		if (p)
>>  			break;
>> +
>> +		if (rq->ttwu_pending)
>> +			return 0;
>>  	}
>>  	if (!p)
>>  		return 0;
>> --
>>
>> 	More bailout logic.
>>
>> --
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -395,17 +414,16 @@ static int shared_runq_pick_next_task(struct rq *rq, struct rq_flags *rf)
>>  	if (task_on_rq_queued(p) && !task_on_cpu(src_rq, p)) {
>>  		update_rq_clock(src_rq);
>>  		src_rq = move_queued_task(src_rq, &src_rf, p, cpu_of(rq));
>> -		ret = 1;
>>  	}
>>  
>>  	if (src_rq != rq) {
>>  		task_rq_unlock(src_rq, p, &src_rf);
>>  		raw_spin_rq_lock(rq);
>>  	} else {
>> +		ret = 1;
>>  		rq_unpin_lock(rq, &src_rf);
>>  		raw_spin_unlock_irqrestore(&p->pi_lock, src_rf.flags);
>>  	}
>> -	rq_repin_lock(rq, rf);
>>  
>>  	return ret;
>>  }
>> --
>>
>> 	Only return 1 is task is actually pulled else return -1
>> 	signifying the path has released and re-aquired the lock.
> 
> Not sure I'm following. If we migrate the task to the current rq, we
> want to return 1 to signify that there are new fair tasks present in the
> rq don't we? It doesn't need to have started there originally for it to
> be present after we move it.

Above move_queued_task(), I see the following comment

	Returns (locked) new rq. Old rq's lock is released.

so wouldn't "src_rq != rq" signify a failed migration? I'm probably
missing something here.

> 
>>
>> 	Also leave the rq_repin_lock() part to caller, i.e.,
>> 	newidle_balance() since it makes up for a nice flow (see
>> 	below).
>>
>> --
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -12344,50 +12362,59 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
>>  	if (!cpu_active(this_cpu))
>>  		return 0;
>>  
>> -	if (sched_feat(SHARED_RUNQ)) {
>> -		pulled_task = shared_runq_pick_next_task(this_rq, rf);
>> -		if (pulled_task)
>> -			return pulled_task;
>> -	}
>> -
>>  	/*
>>  	 * We must set idle_stamp _before_ calling idle_balance(), such that we
>>  	 * measure the duration of idle_balance() as idle time.
>>  	 */
>>  	this_rq->idle_stamp = rq_clock(this_rq);
>>  
>> -	/*
>> -	 * This is OK, because current is on_cpu, which avoids it being picked
>> -	 * for load-balance and preemption/IRQs are still disabled avoiding
>> -	 * further scheduler activity on it and we're being very careful to
>> -	 * re-start the picking loop.
>> -	 */
>> -	rq_unpin_lock(this_rq, rf);
>> -
>>  	rcu_read_lock();
>> -	sd = rcu_dereference_check_sched_domain(this_rq->sd);
>> -
>> -	/*
>> -	 * Skip <= LLC domains as they likely won't have any tasks if the
>> -	 * shared runq is empty.
>> -	 */
>> -	if (sched_feat(SHARED_RUNQ)) {
>> +	if (sched_feat(SHARED_RUNQ))
>>  		sd = rcu_dereference(*this_cpu_ptr(&sd_llc));
>> -		if (likely(sd))
>> -			sd = sd->parent;
>> -	}
>> +	else
>> +		sd = rcu_dereference_check_sched_domain(this_rq->sd);
>>  
>>  	if (!READ_ONCE(this_rq->rd->overload) ||
>>  	    (sd && this_rq->avg_idle < sd->max_newidle_lb_cost)) {
>>  
>> -		if (sd)
>> +		while (sd) {
>>  			update_next_balance(sd, &next_balance);
>> +			sd = sd->child;
>> +		}
>> +
>>  		rcu_read_unlock();
>>  
>>  		goto out;
>>  	}
>>  	rcu_read_unlock();
>>  
>> +	t0 = sched_clock_cpu(this_cpu);
>> +	if (sched_feat(SHARED_RUNQ)) {
>> +		pulled_task = shared_runq_pick_next_task(this_rq, rf);
>> +		if (pulled_task) {
>> +			curr_cost = sched_clock_cpu(this_cpu) - t0;
>> +			update_newidle_cost(sd, curr_cost);
>> +			goto out_swq;
>> +		}
>> +	}
>> +
>> +	/* Check again for pending wakeups */
>> +	if (this_rq->ttwu_pending)
>> +		return 0;
>> +
>> +	t1 = sched_clock_cpu(this_cpu);
>> +	curr_cost += t1 - t0;
>> +
>> +	if (sd)
>> +		update_newidle_cost(sd, curr_cost);
>> +
>> +	/*
>> +	 * This is OK, because current is on_cpu, which avoids it being picked
>> +	 * for load-balance and preemption/IRQs are still disabled avoiding
>> +	 * further scheduler activity on it and we're being very careful to
>> +	 * re-start the picking loop.
>> +	 */
>> +	rq_unpin_lock(this_rq, rf);
>>  	raw_spin_rq_unlock(this_rq);
>>  
>>  	t0 = sched_clock_cpu(this_cpu);
>> --
>>
>> 	This hunk does a few things:
>>
>> 	1. If a task is successfully pulled from shared rq, or if the rq
>> 	   lock had been released and re-acquired with, jump to the
>> 	   very end where we check a bunch of conditions and return
>> 	   accordingly.
>>
>> 	2. Move the shared rq picking after the "rd->overload" and
>> 	   checks against "rq->avg_idle".
>>
>> 	   P.S. This recovered half the performance that was lost.
> 
> Sorry, which performance are you referring to? I'm not thrilled about
> this part because it's another heuristic for users to have to reason
> about. _Maybe_ it makes sense to keep the rd->overload check? I don't
> think we should keep the rq->avg_idle check though unless it's
> absolutely necessary, and I'd have to think more about the rq->overload
> check.

Performance everywhere is tbench-128 clients on test machine since I was
very focused on that alone. I understand why you are "not thrilled"
here. Let me go check which one of those conditions is more relevant.

(P.S. Anna-Maria did some experiments around avg_idle and tbench in
https://lore.kernel.org/lkml/80956e8f-761e-b74-1c7a-3966f9e8d934@linutronix.de/) 

> 
>> 	3. Update the newidle_balance_cost via update_newidle_cost()
>> 	   since that is also used to determine the previous bailout
>> 	   threshold.
> 
> I think this makes sense as well, but need to think about it more.
> 
>> 	4. A bunch of update_next_balance().
> 
> I guess this should be OK, though I would expect us to have to load
> balance less with SHARED_RUNQ.
> 
>> 	5. Move rq_unpin_lock() below. I do not know the implication of
>> 	   this the kernel is not complaining so far (mind you I'm on
>> 	   x86 and I do not have lockdep enabled)
> 
> If you move rq_unpin_lock(), you should probably run with lockdep to see
> what happens :-) There are also implications for tracking whether it's
> safe to look at the rq clock.

Yup! I traced the path in code and it looked okay but this is just me
doing naive experiments. Lockdep should set me straight :)

> 
>>
>> 	A combination of 3 and 4 seemed to give back the other half of
>> 	tbench performance.
>>
>> --
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -12400,6 +12427,13 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
>>  
>>  		update_next_balance(sd, &next_balance);
>>  
>> +		/*
>> +		 * Skip <= LLC domains as they likely won't have any tasks if the
>> +		 * shared runq is empty.
>> +		 */
>> +		if (sched_feat(SHARED_RUNQ) && (sd->flags & SD_SHARE_PKG_RESOURCES))
>> +			continue;
>> +
> 
> Agreed on this.
> 
>>  		if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost)
>>  			break;
>>  
>> --
>>
>> 	This was based on my suggestion in the parallel thread.
>>
>> 	P.S. This alone, without the changes in previous hunk showed no
>> 	difference in performance with results same as vanilla v3.
>>
>> --
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d67d86d3bfdf..f1e64412fd48 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -12429,6 +12463,7 @@ static int newidle_balance(struct rq *this_rq, struct rq_flags *rf)
>>  
>>  	raw_spin_rq_lock(this_rq);
>>  
>> +out_swq:
>>  	if (curr_cost > this_rq->max_idle_balance_cost)
>>  		this_rq->max_idle_balance_cost = curr_cost;
>>  
>> --
>>
>> 	The last part of newidle_balance() does a bunch of accounting
>> 	which is relevant after the above changes. Also the
>> 	rq_repin_lock() I had removed now happens here.
>>
>> --
>>
>> Again most of this is lightly tested with just one workload but I would
>> like to hear your thoughts, especially with the significance of
>> "rd->overload", "max_newidle_lb_cost", and "update_next_balance()".
>> however, I'm afraid these may be the bits that led to the drop in
>> utilization you mentioned in the first place.
> 
> Exactly :-( I think your proposal to fix how we skip load balancing on
> the LLC if SHARED_RUNQ is enabled makes sense, but I'd really prefer to
> avoid adding these heuristics to avoid contention for specific
> workloads. The goal of SHARED_RUNQ is really to drive up CPU util. I
> don't think we're really doing the user many favors if we try to guess
> for them when they actually want that to happen.
> 
> If there's a time where we _really_ don't want or need to do it then
> absolutely, let's skip it. But I would really like to see this go in
> without checks on max_newidle_lb_cost, etc. The whole point of
> SHARED_RUNQ is that it should be less costly than iterating over O(n)
> cores to find tasks, so we _want_ to be more aggressive in doing so.

Agreed! I'll try to get a more palatable diff by the time you are
back from vacation.

> 
>> Most of the experimentation (except for rq lock contention using IBS)
>> was done by reading the newidle_balance() code.
> 
> And kudos for doing so!
> 
>> Finally a look at newidle_balance counts (tip vs tip + v3 + diff) for
>> 128-clients of tbench on the test machine:
>>
>>
>> < ----------------------------------------  Category:  newidle (SMT)  ---------------------------------------- >
>> load_balance cnt on cpu newly idle                         :     921871,   0	(diff: -100.00%)
>> --
>> < ----------------------------------------  Category:  newidle (MC)   ---------------------------------------- >
>> load_balance cnt on cpu newly idle                         :     472412,   0	(diff: -100.00%)
>> --
>> < ----------------------------------------  Category:  newidle (DIE)  ---------------------------------------- >
>> load_balance cnt on cpu newly idle                         :        114, 279	(diff: +144.74%)
>> --
>> < ----------------------------------------  Category:  newidle (NUMA) ---------------------------------------- >
>> load_balance cnt on cpu newly idle                         :          9,   9	(diff: +00.00%)
>> --
>>
>> Let me know if you have any queries. I'll go back and try to bisect the
>> diff to see if only a couple of changes that I thought were important
>> are good enought to yield back the lost performance. I'll do wider
>> testing post hearing your thoughts.
> 
> Hopefully my feedback above should give you enough context to bisect and
> find the changes that we really think are most helpful? To reiterate: I
> definitely think your change to avoid iterating over the LLC sd is
> correct and makes sense. Others possibly do as well such as checking
> rd->overload (though not 100% sure), but others such as the
> max_newidle_lb_cost checks I would strongly prefer to avoid.
> 
> Prateek -- thank you for doing all of this work, it's very much
> appreciated.

And thank you for patiently going through it all and clarifying all the
bits I have been missing :)

> 
> As I mentioned on the other email, I'll be on vacation for about a week
> and a half starting tomorrow afternoon, so I may be slow to respond in
> that time.

Enjoy your vacation! I'll keep the tread updated for you to read when
you get back :)

> 
> Thanks,
> David

--
Thanks and Regards,
Prateek