linux-kernel - Re: [RFC PATCH] sched: Improve scalability of select_idle

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:   Wed, 20 Dec 2017 14:19:36 -0800
From:   Subhra Mazumdar <subhra.mazumdar@...cle.com>
To:     Peter Zijlstra <peterz@...radead.org>
Cc:     linux-kernel@...r.kernel.org, mingo@...hat.com
Subject: Re: [RFC PATCH] sched: Improve scalability of select_idle_sibling
 using SMT balance



On 12/19/2017 11:36 AM, Peter Zijlstra wrote:
> On Fri, Dec 08, 2017 at 12:07:54PM -0800, subhra mazumdar wrote:
>> +static inline void
>> +sd_context_switch(struct sched_domain *sd, struct rq *rq, int util)
>> +{
>> +	struct sched_group *sg_cpu;
>> +
>> +       /* atomically add/subtract the util */
>> +	sg_cpu = sd->sg_cpu;
>> +	if (util > 0)
>> +		atomic_inc(
>> +		    (atomic_t *)(&(sg_cpu->utilization)));
>> +	else
>> +		atomic_dec(
>> +		    (atomic_t *)(&(sg_cpu->utilization)));
> Whahah, lol, no!
This patch solves the scalability problem of potentially searching all
cores or cpus in current logic while scheduling a thread. It does so by
using a randomized approach. We can determine a better core to schedule by
comparing the SMT utilization (i.e. how many CPUs are busy in a core)
between the 2 cores of a llc domain. The comparison is done between the
core of the target cpu passed to select_idle_sibling and a random core.
This comparison can be done in O(1) if we have an accurate accounting. The
SMT utilization is accounted during context switch and for that the atomic
operation is needed for correctness.

The cost of atomic increment/decrement is minimal as it happens only for
levels down from llc, i.e only for cores. My data for context_switch() time
(I had sent it in the patch) shows the extra cost is minimal and mostly
within noise margin.

I am open to any suggestions on better way of doing it.
>
>> +}
>> +
>>   /*
>>    * context_switch - switch to the new MM and the new thread's register state.
>>    */
>> @@ -2751,6 +2766,51 @@ context_switch(struct rq *rq, struct task_struct *prev,
>>   	       struct task_struct *next, struct rq_flags *rf)
>>   {
>>   	struct mm_struct *mm, *oldmm;
>> +	int this_cpu = rq->cpu;
>> +	struct sched_domain *sd;
>> +	unsigned int cond;
>> +
>> +	cond = ((prev != rq->idle) << 1) | (next != rq->idle);
>> +	sd = rcu_dereference(per_cpu(sd_llc, this_cpu));
> That one is RCU, not RCU-sched protected..
Ok
>
>> +	/*
>> +	 * From sd_llc downward update the SMT utilization.
>> +	 * Skip the lowest level 0.
>> +	 */
>> +	for_each_lower_domain(sd) {
>> +		if (sd->level == 0)
>> +			break;
>> +		if (rq->initial_util == UTIL_UNINITIALIZED) {
>> +			switch (cond) {
>> +			case PREV_IDLE_NEXT_NIDLE:
>> +			case PREV_NIDLE_NEXT_NIDLE:
>> +				sd_context_switch(sd, rq, SMT_THREAD_UTIL);
>> +				break;
>> +			case PREV_NIDLE_NEXT_IDLE:
>> +			case PREV_IDLE_NEXT_IDLE:
>> +				break;
>> +			}
>> +		} else {
>> +			switch (cond) {
>> +			case PREV_IDLE_NEXT_NIDLE:
>> +				sd_context_switch(sd, rq, SMT_THREAD_UTIL);
>> +				break;
>> +			case PREV_NIDLE_NEXT_IDLE:
>> +				sd_context_switch(sd, rq, -SMT_THREAD_UTIL);
>> +				break;
>> +			case PREV_IDLE_NEXT_IDLE:
>> +			case PREV_NIDLE_NEXT_NIDLE:
>> +				break;
>> +			}
>> +		}
>> +	}
>> +
>> +	if (sd) {
>> +		if (next == rq->idle)
>> +			rq->initial_util = UTIL_IDLE;
>> +		else
>> +			rq->initial_util = UTIL_BUSY;
>> +	}
> WTH do you even think this is reasonable?
I will clean this part up.
>
>>   	prepare_task_switch(rq, prev, next);
>>   
> And I still have no idea what the patch does, but I can't be bothered to
> reverse engineer it just now.
I will improve the changelog to explain the logic better in v2.

Thanks,
Subhra