linux-kernel - Re: [PATCH 6/7] RT: Select tasks based on relative affinity

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]

Message-Id: <1192478925.4067.89.camel@ghaskins-t60p.haskins.net>
Date:	Mon, 15 Oct 2007 16:08:45 -0400
From:	Gregory Haskins <ghaskins@...ell.com>
To:	Steven Rostedt <rostedt@...dmis.org>
Cc:	Peter Zijlstra <a.p.zijlstra@...llo.nl>,
	RT <linux-rt-users@...r.kernel.org>, Ingo Molnar <mingo@...e.hu>,
	LKML <linux-kernel@...r.kernel.org>
Subject: Re: [PATCH 6/7] RT: Select tasks based on relative affinity

On Fri, 2007-10-12 at 20:16 -0400, Gregory Haskins wrote:
> In theory, tasks will be most efficient if they are allowed to re-wake to
> the CPU that they last ran on due to cache affinity.  Short of that, it is
> cheaper to wake up the current CPU.  If neither of those two are options,
> than the lowest CPU will do. 
> 
> Signed-off-by: Gregory Haskins <ghaskins@...ell.com>
> ---
> 
>  kernel/sched.c |   72 +++++++++++++++++++++++++++++++++++++++++---------------
>  1 files changed, 53 insertions(+), 19 deletions(-)
> 
> diff --git a/kernel/sched.c b/kernel/sched.c
> index 3c71156..b79b968 100644
> --- a/kernel/sched.c
> +++ b/kernel/sched.c
> @@ -1511,6 +1511,15 @@ static int double_lock_balance(struct rq *this_rq, struct rq *busiest);
>  /* Only try this algorithm three times */
>  #define RT_PUSH_MAX_TRIES 3
>  
> +static int non_rt_cpu(cpumask_t *mask, int cpu)
> +{
> +	if (!rt_prio(cpu_rq(cpu)->curr_prio) &&
> +	    cpu_isset(cpu, *mask))
> +		return 1;
> +
> +	return 0;
> +}
> +
>  /* Will lock the rq it finds */
>  static int find_lowest_cpu(cpumask_t *cpu_mask, struct task_struct *task,
>  				 struct rq *this_rq)
> @@ -1519,32 +1528,57 @@ static int find_lowest_cpu(cpumask_t *cpu_mask, struct task_struct *task,
>  	int dst_cpu = -1;
>  	int cpu;
>  	int tries;
> +	int this_cpu = smp_processor_id();
>  
>  	for (tries = 0; tries < RT_PUSH_MAX_TRIES; tries++) {
> +
>  		/*
> -		 * Scan each rq for the lowest prio.
> +		 * We select a CPU in the following priority:
> +		 *
> +		 *       task_cpu, this_cpu, first_cpu
> +		 *
> +		 * for efficiency.
> +		 *
> +		 * - task_cpu preserves cache affinity

After thinking about this over the weekend, the task_cpu optimization
doesn't make sense.  It made sense in my original design before I
integrated with Steve's series, but not here.  I think the second
optimization (this_cpu) still makes sense though, so I will update this
patch for the next drop.

> +		 * - this_cpu is (presumably) cheaper to preempt
> +		 *   (note that sometimes task_cpu and this_cpu
> +		 *   are the same).
> +		 * - Finally, we will take whatever is available
> +		 *   if the first two don't pan out by scanning.
>  		 */
> -		for_each_cpu_mask(cpu, *cpu_mask) {
> -			struct rq *rq = &per_cpu(runqueues, cpu);
> -
> -			if (cpu == smp_processor_id())
> -				continue;
> -
> -			/* We look for lowest RT prio or non-rt CPU */
> -			if (rq->curr_prio >= MAX_RT_PRIO) {
> -				lowest_rq = rq;
> -				dst_cpu = cpu;
> -				break;
> -			}
> +		if (non_rt_cpu(cpu_mask, task_cpu(task))) {
> +			lowest_rq = task_rq(task);	
> +			dst_cpu = lowest_rq->cpu;
> +		} else if (non_rt_cpu(cpu_mask, this_cpu)) {
> +			dst_cpu = this_cpu;
> +			lowest_rq = cpu_rq(this_cpu);	
> +		} else {
>  
> -			/* no locking for now */
> -			if (rq->curr_prio > task->prio &&
> -			    (!lowest_rq || rq->curr_prio < lowest_rq->curr_prio)) {
> -				dst_cpu = cpu;
> -				lowest_rq = rq;
> +			/*
> +			 * Scan each rq for the lowest prio.
> +			 */
> +			for_each_cpu_mask(cpu, *cpu_mask) {
> +				struct rq *rq = &per_cpu(runqueues, cpu);
> +				
> +				if (cpu == this_cpu)
> +					continue;
> +				
> +				/* We look for lowest RT prio or non-rt CPU */
> +				if (rq->curr_prio >= MAX_RT_PRIO) {
> +					lowest_rq = rq;
> +					dst_cpu = cpu;
> +					break;
> +				}
> +				
> +				/* no locking for now */
> +				if (rq->curr_prio > task->prio &&
> +				    (!lowest_rq || rq->curr_prio < lowest_rq->curr_prio)) {
> +					dst_cpu = cpu;
> +					lowest_rq = rq;
> +				}
>  			}
>  		}
> -
> +			
>  		if (!lowest_rq) {
>  			dst_cpu = -1;
>  			break;
> 

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/