[PATCH 1/3] sched: limit "all_pinned" balance attempts to sd->span

[PATCH 1/3] sched: limit "all_pinned" balance attempts to sd->span

[Gregory Haskins]

Load-balancing will never terminate if all cpus are "all_pinned" with
the current algorithm.  This would be pretty unlikely to occur, but we
should protect against it nonetheless.

Signed-off-by: Gregory Haskins <ghaskins@novell.com>
---

 kernel/sched.c |   19 ++++++++++---------
 1 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index 31f91d9..54b27b4 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -3178,7 +3178,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 	struct sched_group *group;
 	unsigned long imbalance;
 	struct rq *busiest;
-	cpumask_t cpus = CPU_MASK_ALL;
+	cpumask_t cpus = sd->span;
+	int remain = cpus_weight(sd->span) - 1;
 	unsigned long flags;
 
 	/*
@@ -3237,11 +3238,10 @@ redo:
 			resched_cpu(this_cpu);
 
 		/* All tasks on this runqueue were pinned by CPU affinity */
-		if (unlikely(all_pinned)) {
+		if (unlikely(all_pinned && remain)) {
 			cpu_clear(cpu_of(busiest), cpus);
-			if (!cpus_empty(cpus))
-				goto redo;
-			goto out_balanced;
+			remain--;
+			goto redo;
 		}
 	}
 
@@ -3332,7 +3332,8 @@ load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
 	int ld_moved = 0;
 	int sd_idle = 0;
 	int all_pinned = 0;
-	cpumask_t cpus = CPU_MASK_ALL;
+	cpumask_t cpus = sd->span;
+	int remain = cpus_weight(sd->span) - 1;
 
 	/*
 	 * When power savings policy is enabled for the parent domain, idle
@@ -3375,10 +3376,10 @@ redo:
 					&all_pinned);
 		spin_unlock(&busiest->lock);
 
-		if (unlikely(all_pinned)) {
+		if (unlikely(all_pinned && remain)) {
 			cpu_clear(cpu_of(busiest), cpus);
-			if (!cpus_empty(cpus))
-				goto redo;
+			remain--;
+			goto redo;
 		}
 	}
 

[PATCH 0/3] RT: scheduler newidle enhancements v2

[Gregory Haskins]

Hi All,

 Here is v2 of the newidle patches I sent out yesterday:

http://lkml.org/lkml/2008/6/23/392

Changes since v1:

1) Added a new patch (1/3) for limiting balance operations to sd->span
2) Updated prologue to 2/3 according to comments from PeterZ.
3) Enhanced 2/3 by reducing the amount of unlock/lock cycles
4) Enhanced 2/3 by checking for need_resched() before taking the double-lock

Comments/feedback/bug-fixes welcome.

Regards,
-Greg

[PATCH 1/3] sched: limit "all_pinned" balance attempts to sd->span

[Gregory Haskins]

Load-balancing will never terminate if all cpus are "all_pinned" with
the current algorithm.  This would be pretty unlikely to occur, but we
should protect against it nonetheless.

Signed-off-by: Gregory Haskins <ghaskins@novell.com>
---

 kernel/sched.c |   19 ++++++++++---------
 1 files changed, 10 insertions(+), 9 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index 31f91d9..54b27b4 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -3178,7 +3178,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 	struct sched_group *group;
 	unsigned long imbalance;
 	struct rq *busiest;
-	cpumask_t cpus = CPU_MASK_ALL;
+	cpumask_t cpus = sd->span;
+	int remain = cpus_weight(sd->span) - 1;
 	unsigned long flags;
 
 	/*
@@ -3237,11 +3238,10 @@ redo:
 			resched_cpu(this_cpu);
 
 		/* All tasks on this runqueue were pinned by CPU affinity */
-		if (unlikely(all_pinned)) {
+		if (unlikely(all_pinned && remain)) {
 			cpu_clear(cpu_of(busiest), cpus);
-			if (!cpus_empty(cpus))
-				goto redo;
-			goto out_balanced;
+			remain--;
+			goto redo;
 		}
 	}
 
@@ -3332,7 +3332,8 @@ load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
 	int ld_moved = 0;
 	int sd_idle = 0;
 	int all_pinned = 0;
-	cpumask_t cpus = CPU_MASK_ALL;
+	cpumask_t cpus = sd->span;
+	int remain = cpus_weight(sd->span) - 1;
 
 	/*
 	 * When power savings policy is enabled for the parent domain, idle
@@ -3375,10 +3376,10 @@ redo:
 					&all_pinned);
 		spin_unlock(&busiest->lock);
 
-		if (unlikely(all_pinned)) {
+		if (unlikely(all_pinned && remain)) {
 			cpu_clear(cpu_of(busiest), cpus);
-			if (!cpus_empty(cpus))
-				goto redo;
+			remain--;
+			goto redo;
 		}
 	}
 

[PATCH 2/3] sched: enable interrupts and drop rq-lock during newidle balancing

[Gregory Haskins]

Oprofile data shows that the system may spend a significant amount of
time (60%+) in find_busiest_groups as a result of newidle balancing.  This
entire operation is a critical section since it occurs inline with
a schedule().  Since we do find_busiest_groups() et. al. without locks
held for normal balancing, lets do it for newidle as well.  It will
at least allow other cpus and interrupts to make forward progress
(against our RQ) while we try to balance.

Additionally, we abort the newidle processing if we are preempted.

This patch should both improve latency response, as well as increase
throughput.  It has shown to significantly contribute to a 6-12%
increase in network peformance.

Signed-off-by: Gregory Haskins <ghaskins@novell.com>
---

 kernel/sched.c |   40 +++++++++++++++++++++++++++++++++-------
 1 files changed, 33 insertions(+), 7 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index 54b27b4..e40c575 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -3335,6 +3335,15 @@ load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
 	cpumask_t cpus = sd->span;
 	int remain = cpus_weight(sd->span) - 1;
 
+	schedstat_inc(sd, lb_count[CPU_NEWLY_IDLE]);
+
+	/*
+	 * We are in a preempt-disabled section, so dropping the lock/irq
+	 * here simply means that other cores may acquire the lock,
+	 * and interrupts may occur.
+	 */
+	spin_unlock_irq(&this_rq->lock);
+
 	/*
 	 * When power savings policy is enabled for the parent domain, idle
 	 * sibling can pick up load irrespective of busy siblings. In this case,
@@ -3345,7 +3354,6 @@ load_balance_newidle(int this_cpu, struct rq *this_rq, struct sched_domain *sd)
 	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))
 		sd_idle = 1;
 
-	schedstat_inc(sd, lb_count[CPU_NEWLY_IDLE]);
 redo:
 	group = find_busiest_group(sd, this_cpu, &imbalance, CPU_NEWLY_IDLE,
 				   &sd_idle, &cpus, NULL);
@@ -3366,22 +3374,37 @@ redo:
 	schedstat_add(sd, lb_imbalance[CPU_NEWLY_IDLE], imbalance);
 
 	ld_moved = 0;
-	if (busiest->nr_running > 1) {
+	if (!need_resched() && busiest->nr_running > 1) {
 		/* Attempt to move tasks */
-		double_lock_balance(this_rq, busiest);
-		/* this_rq->clock is already updated */
-		update_rq_clock(busiest);
+		local_irq_disable();
+		double_rq_lock(this_rq, busiest);
+
+		BUG_ON(this_cpu != smp_processor_id());
+
+		/*
+		 * Checking rq->nr_running covers both the case where
+		 * newidle-balancing pulls a task, as well as if something
+		 * else issued a NEEDS_RESCHED (since we would only need
+		 * a reschedule if something was moved to us)
+		 */
+		if (this_rq->nr_running) {
+			spin_unlock(&busiest->lock);
+			goto out_balanced_locked;
+		}
+
 		ld_moved = move_tasks(this_rq, this_cpu, busiest,
 					imbalance, sd, CPU_NEWLY_IDLE,
 					&all_pinned);
 		spin_unlock(&busiest->lock);
 
-		if (unlikely(all_pinned && remain)) {
+		if (unlikely(all_pinned && remain && !this_rq->nr_running)) {
+			spin_unlock_irq(&this_rq->lock);
 			cpu_clear(cpu_of(busiest), cpus);
 			remain--;
 			goto redo;
 		}
-	}
+	} else
+		spin_lock_irq(&this_rq->lock);
 
 	if (!ld_moved) {
 		schedstat_inc(sd, lb_failed[CPU_NEWLY_IDLE]);
@@ -3394,6 +3417,9 @@ redo:
 	return ld_moved;
 
 out_balanced:
+	spin_lock_irq(&this_rq->lock);
+
+out_balanced_locked:
 	schedstat_inc(sd, lb_balanced[CPU_NEWLY_IDLE]);
 	if (!sd_idle && sd->flags & SD_SHARE_CPUPOWER &&
 	    !test_sd_parent(sd, SD_POWERSAVINGS_BALANCE))

[PATCH 3/3] sched: terminate newidle balancing once at least one task has moved over

[Gregory Haskins]

Inspired by Peter Zijlstra.

Signed-off-by: Gregory Haskins <ghaskins@novell.com>
---

 kernel/sched.c |    4 ++++
 1 files changed, 4 insertions(+), 0 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index e40c575..094a84b 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -2774,6 +2774,10 @@ static int move_tasks(struct rq *this_rq, int this_cpu, struct rq *busiest,
 				max_load_move - total_load_moved,
 				sd, idle, all_pinned, &this_best_prio);
 		class = class->next;
+
+		if (idle == CPU_NEWLY_IDLE && this_rq->nr_running)
+			break;
+
 	} while (class && max_load_move > total_load_moved);
 
 	return total_load_moved > 0;

Re: [PATCH 1/3] sched: limit "all_pinned" balance attempts to sd->span

[Gregory Haskins]

>>> On Tue, Jun 24, 2008 at 10:16 AM, in message
<20080624141602.28487.81775.stgit@lsg.lsg.lab.novell.com>, Gregory Haskins
<ghaskins@novell.com> wrote: 
> Load-balancing will never terminate if all cpus are "all_pinned" with
> the current algorithm.  This would be pretty unlikely to occur, but we
> should protect against it nonetheless.

Hmm...after thinking about this some more, I think I was wrong and this is unfounded.

The code would eventually terminate when the f_b_g()/f_b_q() cant find a good target.

Pls ignore this patch.

Regards,
-Greg

> 
> Signed-off-by: Gregory Haskins <ghaskins@novell.com>
> ---
> 
>  kernel/sched.c |   19 ++++++++++---------
>  1 files changed, 10 insertions(+), 9 deletions(-)
> 
> diff --git a/kernel/sched.c b/kernel/sched.c
> index 31f91d9..54b27b4 100644
> --- a/kernel/sched.c
> +++ b/kernel/sched.c
> @@ -3178,7 +3178,8 @@ static int load_balance(int this_cpu, struct rq 
> *this_rq,
>  	struct sched_group *group;
>  	unsigned long imbalance;
>  	struct rq *busiest;
> -	cpumask_t cpus = CPU_MASK_ALL;
> +	cpumask_t cpus = sd->span;
> +	int remain = cpus_weight(sd->span) - 1;
>  	unsigned long flags;
>  
>  	/*
> @@ -3237,11 +3238,10 @@ redo:
>  			resched_cpu(this_cpu);
>  
>  		/* All tasks on this runqueue were pinned by CPU affinity */
> -		if (unlikely(all_pinned)) {
> +		if (unlikely(all_pinned && remain)) {
>  			cpu_clear(cpu_of(busiest), cpus);
> -			if (!cpus_empty(cpus))
> -				goto redo;
> -			goto out_balanced;
> +			remain--;
> +			goto redo;
>  		}
>  	}
>  
> @@ -3332,7 +3332,8 @@ load_balance_newidle(int this_cpu, struct rq *this_rq, 
> struct sched_domain *sd)
>  	int ld_moved = 0;
>  	int sd_idle = 0;
>  	int all_pinned = 0;
> -	cpumask_t cpus = CPU_MASK_ALL;
> +	cpumask_t cpus = sd->span;
> +	int remain = cpus_weight(sd->span) - 1;
>  
>  	/*
>  	 * When power savings policy is enabled for the parent domain, idle
> @@ -3375,10 +3376,10 @@ redo:
>  					&all_pinned);
>  		spin_unlock(&busiest->lock);
>  
> -		if (unlikely(all_pinned)) {
> +		if (unlikely(all_pinned && remain)) {
>  			cpu_clear(cpu_of(busiest), cpus);
> -			if (!cpus_empty(cpus))
> -				goto redo;
> +			remain--;
> +			goto redo;
>  		}
>  	}
>  
> 
> --
> To unsubscribe from this list: send the line "unsubscribe linux-rt-users" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html