Skip to contentSkip to conversation

smt nice introduces significant lock contention

RFC PATCH In review Chris Mason 4 participants 41 messages Jun 1, 2006 – Jun 3, 2006

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 smt nice introduces significant lock contention

Hello everyone,

Recent benchmarks showed some performance regressions between 2.6.16 and 2.6.5. We tracked down one of the regressions to lock contention in schedule heavy workloads (~70,000 context switches per second)

kernel/sched.c:dependent_sleeper() was responsible for most of the lock contention, hammering on the run queue locks. The patch below is more of a discussion point than a suggested fix (although it does reduce lock contention significantly). The dependent_sleeper code looks very expensive to me, especially for using a spinlock to bounce control between two different siblings in the same cpu.

kernel/sched.c +26 -12
@@ -2630,6 +2630,27 @@ static inline void wakeup_busy_runqueue(
 		resched_task(rq->idle);
 }
 
+static int trylock_smt_cpus(cpumask_t sibling_map)
+{
+	int ret = 1;
+	int numlocked = 0;
+	int i;
+	for_each_cpu_mask(i, sibling_map) {
+		ret = spin_trylock(&cpu_rq(i)->lock);
+		if (!ret)
+			break;
+		numlocked++;
+	}
+	if (ret || !numlocked)
+		return ret;
+	for_each_cpu_mask(i, sibling_map) {
+		spin_unlock(&cpu_rq(i)->lock);
+		if (--numlocked == 0)
+			break;
+	}
+	return 0;
+}
+
 static void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
 {
 	struct sched_domain *tmp, *sd = NULL;
@@ -2643,22 +2664,16 @@ static void wake_sleeping_dependent(int 
 	if (!sd)
 		return;
 
-	/*
-	 * Unlock the current runqueue because we have to lock in
-	 * CPU order to avoid deadlocks. Caller knows that we might
-	 * unlock. We keep IRQs disabled.
-	 */
-	spin_unlock(&this_rq->lock);
-
 	sibling_map = sd->span;
 
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
 	/*
 	 * We clear this CPU from the mask. This both simplifies the
 	 * inner loop and keps this_rq locked when we exit:
 	 */
 	cpu_clear(this_cpu, sibling_map);
+
+	if (!trylock_smt_cpus(sibling_map))
+		return;
 
 	for_each_cpu_mask(i, sibling_map) {
 		runqueue_t *smt_rq = cpu_rq(i);
@@ -2703,11 +2718,10 @@ static int dependent_sleeper(int this_cp
 	 * The same locking rules and details apply as for
 	 * wake_sleeping_dependent():
 	 */
-	spin_unlock(&this_rq->lock);
 	sibling_map = sd->span;
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
 	cpu_clear(this_cpu, sibling_map);
+	if (!trylock_smt_cpus(sibling_map))
+		return 0;
 
 	/*
 	 * Establish next task to be run - it might have gone away because
#1 lore raw

Chris Mason wrote on Thursday, June 01, 2006 3:56 PM

Quoted 6 lines

Hello everyone,

Recent benchmarks showed some performance regressions between 2.6.16 and 2.6.5. We tracked down one of the regressions to lock contention in schedule heavy workloads (~70,000 context switches per second)

Quoted 6 lines

kernel/sched.c:dependent_sleeper() was responsible for most of the lock contention, hammering on the run queue locks. The patch below is more of a discussion point than a suggested fix (although it does reduce lock contention significantly). The dependent_sleeper code looks very expensive to me, especially for using a spinlock to bounce control between two different siblings in the same cpu.

Yeah, this also sort of echo a recent discovery on one of our benchmarks that schedule() is red hot in the kernel. I was just scratching my head not sure what's going on. This dependent_sleeper could be the culprit considering it is called almost at every context switch. I don't think we are hitting on lock contention, but by the large amount of code it executes. It really needs to be cut down ....

- Ken

#2 lore raw
Quoted 15 lines · Kenneth W

Chris Mason wrote on Thursday, June 01, 2006 3:56 PM

Quoted 6 lines

Hello everyone,

Recent benchmarks showed some performance regressions between 2.6.16 and 2.6.5. We tracked down one of the regressions to lock contention in schedule heavy workloads (~70,000 context switches per second)

Quoted 6 lines

kernel/sched.c:dependent_sleeper() was responsible for most of the lock contention, hammering on the run queue locks. The patch below is more of a discussion point than a suggested fix (although it does reduce lock contention significantly). The dependent_sleeper code looks very expensive to me, especially for using a spinlock to bounce control between two different siblings in the same cpu.

Quoted 6 lines

Yeah, this also sort of echo a recent discovery on one of our benchmarks that schedule() is red hot in the kernel. I was just scratching my head not sure what's going on. This dependent_sleeper could be the culprit considering it is called almost at every context switch. I don't think we are hitting on lock contention, but by the large amount of code it executes. It really needs to be cut down ....

Thanks for the suggestion. How about something like this which takes your idea and further expands on it. Compiled, boot and runtime tests ok.

---
It is not critical to functioning that dependent_sleeper() succeeds every time. We can significantly reduce the locking overhead and contention of dependent_sleeper by only doing trylock on the smt sibling runqueues. As we're only doing trylock it means we do not need to observe the normal locking order and we can get away without unlocking this_rq in schedule(). This provides us with an opportunity to simplify the code further.

---
 kernel/sched.c |   58 +++++++++++++++++++++++++++++++++++----------------------
 1 files changed, 36 insertions(+), 22 deletions(-)
kernel/sched.c +36 -22
Index: linux-2.6.17-rc5/kernel/sched.c
===================================================================
@@ -1687,7 +1687,7 @@ unsigned long nr_active(void)
  * double_rq_lock - safely lock two runqueues
  *
  * We must take them in cpu order to match code in
- * dependent_sleeper and wake_dependent_sleeper.
+ * wake_dependent_sleeper.
  *
  * Note this does not disable interrupts like task_rq_lock,
  * you need to do so manually before calling.
@@ -2731,6 +2731,32 @@ static void wake_sleeping_dependent(int 
 }
 
 /*
+ * Try to lock all the siblings of a cpu that is already locked. As we're
+ * only doing trylock the order is not important.
+ */
+static int trylock_smt_siblings(cpumask_t sibling_map)
+{
+	cpumask_t locked_siblings;
+	int i;
+
+	cpus_clear(locked_siblings);
+	for_each_cpu_mask(i, sibling_map) {
+		if (!spin_trylock(&cpu_rq(i)->lock))
+			break;
+		cpu_set(i, locked_siblings);
+
+	}
+
+	/* Did we lock all the siblings? */
+	if (cpus_equal(sibling_map, locked_siblings))
+		return 1;
+
+	for_each_cpu_mask(i, locked_siblings)
+		spin_unlock(&cpu_rq(i)->lock);
+	return 0;
+}
+
+/*
  * number of 'lost' timeslices this task wont be able to fully
  * utilize, if another task runs on a sibling. This models the
  * slowdown effect of other tasks running on siblings:
@@ -2740,7 +2766,11 @@ static inline unsigned long smt_slice(ta
 	return p->time_slice * (100 - sd->per_cpu_gain) / 100;
 }
 
-static int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
+/*
+ * To minimise lock contention and to have to drop this_rq's runlock we only
+ * trylock the sibling runqueues and give up if we can't acquire the locks.
+ */
+static int dependent_sleeper(int this_cpu, struct runqueue *this_rq)
 {
 	struct sched_domain *tmp, *sd = NULL;
 	cpumask_t sibling_map;
@@ -2755,22 +2785,14 @@ static int dependent_sleeper(int this_cp
 	if (!sd)
 		return 0;
 
-	/*
-	 * The same locking rules and details apply as for
-	 * wake_sleeping_dependent():
-	 */
-	spin_unlock(&this_rq->lock);
 	sibling_map = sd->span;
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
 	cpu_clear(this_cpu, sibling_map);
+	if (!trylock_smt_siblings(sibling_map))
+		return 0;
 
 	/*
-	 * Establish next task to be run - it might have gone away because
-	 * we released the runqueue lock above:
+	 * Establish next task to be run.
 	 */
-	if (!this_rq->nr_running)
-		goto out_unlock;
 	array = this_rq->active;
 	if (!array->nr_active)
 		array = this_rq->expired;
@@ -2835,7 +2857,7 @@ check_smt_task:
 				wakeup_busy_runqueue(smt_rq);
 		}
 	}
-out_unlock:
+
 	for_each_cpu_mask(i, sibling_map)
 		spin_unlock(&cpu_rq(i)->lock);
 	return ret;
@@ -2967,7 +2989,6 @@ need_resched_nonpreemptible:
 
 	cpu = smp_processor_id();
 	if (unlikely(!rq->nr_running)) {
-go_idle:
 		idle_balance(cpu, rq);
 		if (!rq->nr_running) {
 			next = rq->idle;
@@ -2986,13 +3007,6 @@ go_idle:
 			next = rq->idle;
 			goto switch_tasks;
 		}
-		/*
-		 * dependent_sleeper() releases and reacquires the runqueue
-		 * lock, hence go into the idle loop if the rq went
-		 * empty meanwhile:
-		 */
-		if (unlikely(!rq->nr_running))
-			goto go_idle;
 	}
 
 	array = rq->active;
Signature · 1 line
-ck
#3 lore raw
Quoted 26 lines · Con Kolivas
Quoted 15 lines · Kenneth W

Chris Mason wrote on Thursday, June 01, 2006 3:56 PM

Quoted 6 lines

Hello everyone,

Recent benchmarks showed some performance regressions between 2.6.16 and 2.6.5. We tracked down one of the regressions to lock contention in schedule heavy workloads (~70,000 context switches per second)

Quoted 6 lines

kernel/sched.c:dependent_sleeper() was responsible for most of the lock contention, hammering on the run queue locks. The patch below is more of a discussion point than a suggested fix (although it does reduce lock contention significantly). The dependent_sleeper code looks very expensive to me, especially for using a spinlock to bounce control between two different siblings in the same cpu.

Quoted 6 lines

Yeah, this also sort of echo a recent discovery on one of our benchmarks that schedule() is red hot in the kernel. I was just scratching my head not sure what's going on. This dependent_sleeper could be the culprit considering it is called almost at every context switch. I don't think we are hitting on lock contention, but by the large amount of code it executes. It really needs to be cut down ....

Thanks for the suggestion. How about something like this which takes your idea and further expands on it. Compiled, boot and runtime tests ok.

Quoted 7 lines

---
It is not critical to functioning that dependent_sleeper() succeeds every time. We can significantly reduce the locking overhead and contention of dependent_sleeper by only doing trylock on the smt sibling runqueues. As we're only doing trylock it means we do not need to observe the normal locking order and we can get away without unlocking this_rq in schedule(). This provides us with an opportunity to simplify the code further.

Actually looking even further, we only introduced the extra lookup of the next task when we started unlocking the runqueue in schedule(). Since we can get by without locking this_rq in schedule with this approach we can simplify dependent_sleeper even further by doing the dependent sleeper check after we have discovered what next is in schedule and avoid looking it up twice. I'll hack something up to do that soon.

Signature · 1 line
-ck
#38 lore raw
In reply to Con Kolivas

Con Kolivas wrote on Thursday, June 01, 2006 6:59 PM

Quoted 41 lines · Kenneth W
Quoted 15 lines

Chris Mason wrote on Thursday, June 01, 2006 3:56 PM

Quoted 6 lines

Hello everyone,

Recent benchmarks showed some performance regressions between 2.6.16 and 2.6.5. We tracked down one of the regressions to lock contention in schedule heavy workloads (~70,000 context switches per second)

Quoted 6 lines

kernel/sched.c:dependent_sleeper() was responsible for most of the lock contention, hammering on the run queue locks. The patch below is more of a discussion point than a suggested fix (although it does reduce lock contention significantly). The dependent_sleeper code looks very expensive to me, especially for using a spinlock to bounce control between two different siblings in the same cpu.

Quoted 6 lines

Yeah, this also sort of echo a recent discovery on one of our benchmarks that schedule() is red hot in the kernel. I was just scratching my head not sure what's going on. This dependent_sleeper could be the culprit considering it is called almost at every context switch. I don't think we are hitting on lock contention, but by the large amount of code it executes. It really needs to be cut down ....

Thanks for the suggestion. How about something like this which takes your idea and further expands on it. Compiled, boot and runtime tests ok.

/*
+ * Try to lock all the siblings of a cpu that is already locked. As we're
+ * only doing trylock the order is not important.
+ */

kernel/sched.c +11 -0
+static int trylock_smt_siblings(cpumask_t sibling_map)
+{
+	cpumask_t locked_siblings;
+	int i;
+
+	cpus_clear(locked_siblings);
+	for_each_cpu_mask(i, sibling_map) {
+		if (!spin_trylock(&cpu_rq(i)->lock))
+			break;
+		cpu_set(i, locked_siblings);
+

kernel/sched.c static void wake_sleeping_dependent(int · line 2757

Quoted 10 lines
kernel/sched.c +10 -0
+	}
+
+	/* Did we lock all the siblings? */
+	if (cpus_equal(sibling_map, locked_siblings))
+		return 1;
+
+	for_each_cpu_mask(i, locked_siblings)
+		spin_unlock(&cpu_rq(i)->lock);
+	return 0;
+}

I like Chris's version of trylock_smt_siblings(). Why create all that local variables? sibling_map is passed by value, so the whole thing is duplicated on the stack (I think it should be pass by pointer), then there is another locked_siblings mask declared followed by a bitmask compare. The big iron people who set CONFIG_NR_CPUS=1024 won't be amused because of all that bitmask copying.

Let me hack up something too, so we can compare notes etc.

- Ken

#39 lore raw
Quoted 48 lines · Kenneth W

Con Kolivas wrote on Thursday, June 01, 2006 6:59 PM

Quoted 46 lines · Kenneth W
Quoted 15 lines

Chris Mason wrote on Thursday, June 01, 2006 3:56 PM

Quoted 6 lines

Hello everyone,

Recent benchmarks showed some performance regressions between 2.6.16 and 2.6.5. We tracked down one of the regressions to lock contention in schedule heavy workloads (~70,000 context switches per second)

Quoted 6 lines

kernel/sched.c:dependent_sleeper() was responsible for most of the lock contention, hammering on the run queue locks. The patch below is more of a discussion point than a suggested fix (although it does reduce lock contention significantly). The dependent_sleeper code looks very expensive to me, especially for using a spinlock to bounce control between two different siblings in the same cpu.

Quoted 6 lines

Yeah, this also sort of echo a recent discovery on one of our benchmarks that schedule() is red hot in the kernel. I was just scratching my head not sure what's going on. This dependent_sleeper could be the culprit considering it is called almost at every context switch. I don't think we are hitting on lock contention, but by the large amount of code it executes. It really needs to be cut down ....

Thanks for the suggestion. How about something like this which takes your idea and further expands on it. Compiled, boot and runtime tests ok.

/*
+ * Try to lock all the siblings of a cpu that is already locked. As we're + * only doing trylock the order is not important.
+ */

kernel/sched.c +16 -0
+static int trylock_smt_siblings(cpumask_t sibling_map)
+{
+	cpumask_t locked_siblings;
+	int i;
+
+	cpus_clear(locked_siblings);
+	for_each_cpu_mask(i, sibling_map) {
+		if (!spin_trylock(&cpu_rq(i)->lock))
+			break;
+		cpu_set(i, locked_siblings);
+
+	}
+
+	/* Did we lock all the siblings? */
+	if (cpus_equal(sibling_map, locked_siblings))
+		return 1;
Quoted 8 lines

kernel/sched.c static void wake_sleeping_dependent(int · line 2757

Quoted 5 lines
kernel/sched.c +5 -0
+
+	for_each_cpu_mask(i, locked_siblings)
+		spin_unlock(&cpu_rq(i)->lock);
+	return 0;
+}

I like Chris's version of trylock_smt_siblings(). Why create all that local variables?

Because cpumasks are so pretty.

Quoted 5 lines

sibling_map is passed by value, so the whole thing is duplicated on the stack (I think it should be pass by pointer), then there is another locked_siblings mask declared followed by a bitmask compare. The big iron people who set CONFIG_NR_CPUS=1024 won't be amused because of all that bitmask copying.

Good point.

Quoted 2 lines

Let me hack up something too, so we can compare notes etc.

Sure, you have the hack lock. Actually we can just trylock and if it fails remove it from the sibling_map and go to out_unlock without a separate trylock_smt_cpus function entirely...

Signature · 1 line
-ck
#40 lore raw
Quoted 3 lines · Con Kolivas

Sure, you have the hack lock. Actually we can just trylock and if it fails remove it from the sibling_map and go to out_unlock without a separate trylock_smt_cpus function entirely...

I mean go to out_unlock if the sibling_map is empty sorry.

Signature · 1 line
-ck
#4 lore raw
In reply to Con Kolivas
Quoted 6 lines · Con Kolivas

Actually looking even further, we only introduced the extra lookup of the next task when we started unlocking the runqueue in schedule(). Since we can get by without locking this_rq in schedule with this approach we can simplify dependent_sleeper even further by doing the dependent sleeper check after we have discovered what next is in schedule and avoid looking it up twice. I'll hack something up to do that soon.

Something like this (sorry I couldn't help but keep hacking on it).
---
It is not critical to functioning that dependent_sleeper() succeeds every time. We can significantly reduce the locking overhead and contention of dependent_sleeper by only doing trylock on the smt sibling runqueues. As we're only doing trylock it means we do not need to observe the normal locking order and we can get away without unlocking this_rq in schedule(). This provides us with an opportunity to simplify the code further.

---
 kernel/sched.c |   58 +++++++++++++++++----------------------------------------
 1 files changed, 18 insertions(+), 40 deletions(-)
kernel/sched.c +18 -40
Index: linux-2.6.17-rc5/kernel/sched.c
===================================================================
@@ -1687,7 +1687,7 @@ unsigned long nr_active(void)
  * double_rq_lock - safely lock two runqueues
  *
  * We must take them in cpu order to match code in
- * dependent_sleeper and wake_dependent_sleeper.
+ * wake_dependent_sleeper.
  *
  * Note this does not disable interrupts like task_rq_lock,
  * you need to do so manually before calling.
@@ -2740,13 +2740,18 @@ static inline unsigned long smt_slice(ta
 	return p->time_slice * (100 - sd->per_cpu_gain) / 100;
 }
 
-static int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
+/*
+ * To minimise lock contention and not have to drop this_rq's runlock we only
+ * trylock the sibling runqueues and bypass those runqueues if we fail to
+ * acquire their lock. As we only trylock the normal locking order does not
+ * need to be obeyed.
+ */
+static int dependent_sleeper(int this_cpu, struct runqueue *this_rq,
+	struct task_struct *p)
 {
 	struct sched_domain *tmp, *sd = NULL;
 	cpumask_t sibling_map;
-	prio_array_t *array;
 	int ret = 0, i;
-	task_t *p;
 
 	for_each_domain(this_cpu, tmp)
 		if (tmp->flags & SD_SHARE_CPUPOWER)
@@ -2755,29 +2760,12 @@ static int dependent_sleeper(int this_cp
 	if (!sd)
 		return 0;
 
-	/*
-	 * The same locking rules and details apply as for
-	 * wake_sleeping_dependent():
-	 */
-	spin_unlock(&this_rq->lock);
 	sibling_map = sd->span;
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
 	cpu_clear(this_cpu, sibling_map);
-
-	/*
-	 * Establish next task to be run - it might have gone away because
-	 * we released the runqueue lock above:
-	 */
-	if (!this_rq->nr_running)
-		goto out_unlock;
-	array = this_rq->active;
-	if (!array->nr_active)
-		array = this_rq->expired;
-	BUG_ON(!array->nr_active);
-
-	p = list_entry(array->queue[sched_find_first_bit(array->bitmap)].next,
-		task_t, run_list);
+	for_each_cpu_mask(i, sibling_map) {
+		if (unlikely(!spin_trylock(&cpu_rq(i)->lock)))
+			cpu_clear(i, sibling_map);
+	}
 
 	for_each_cpu_mask(i, sibling_map) {
 		runqueue_t *smt_rq = cpu_rq(i);
@@ -2835,7 +2823,7 @@ check_smt_task:
 				wakeup_busy_runqueue(smt_rq);
 		}
 	}
-out_unlock:
+
 	for_each_cpu_mask(i, sibling_map)
 		spin_unlock(&cpu_rq(i)->lock);
 	return ret;
@@ -2845,7 +2833,8 @@ static inline void wake_sleeping_depende
 {
 }
 
-static inline int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
+static inline int dependent_sleeper(int this_cpu, struct runqueue *this_rq,
+	struct task_struct *p)
 {
 	return 0;
 }
@@ -2967,7 +2956,6 @@ need_resched_nonpreemptible:
 
 	cpu = smp_processor_id();
 	if (unlikely(!rq->nr_running)) {
-go_idle:
 		idle_balance(cpu, rq);
 		if (!rq->nr_running) {
 			next = rq->idle;
@@ -2981,18 +2969,6 @@ go_idle:
 			if (!rq->nr_running)
 				goto switch_tasks;
 		}
-	} else {
-		if (dependent_sleeper(cpu, rq)) {
-			next = rq->idle;
-			goto switch_tasks;
-		}
-		/*
-		 * dependent_sleeper() releases and reacquires the runqueue
-		 * lock, hence go into the idle loop if the rq went
-		 * empty meanwhile:
-		 */
-		if (unlikely(!rq->nr_running))
-			goto go_idle;
 	}
 
 	array = rq->active;
@@ -3030,6 +3006,8 @@ go_idle:
 		}
 	}
 	next->sleep_type = SLEEP_NORMAL;
+	if (dependent_sleeper(cpu, rq, next))
+		next = rq->idle;
 switch_tasks:
 	if (next == rq->idle)
 		schedstat_inc(rq, sched_goidle);
Signature · 1 line
-ck
#5 lore raw
Quoted 11 lines · Con Kolivas
Quoted 6 lines · Con Kolivas

Actually looking even further, we only introduced the extra lookup of the next task when we started unlocking the runqueue in schedule(). Since we can get by without locking this_rq in schedule with this approach we can simplify dependent_sleeper even further by doing the dependent sleeper check after we have discovered what next is in schedule and avoid looking it up twice. I'll hack something up to do that soon.

Something like this (sorry I couldn't help but keep hacking on it).

Looking pretty good. Nice to acknowledge Chris's idea for trylocks in your changelog when you submit a final patch.

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#6 lore raw
Quoted 9 lines · Nick Piggin
Quoted 8 lines · Con Kolivas
Quoted 6 lines · Con Kolivas

Actually looking even further, we only introduced the extra lookup of the next task when we started unlocking the runqueue in schedule(). Since we can get by without locking this_rq in schedule with this approach we can simplify dependent_sleeper even further by doing the dependent sleeper check after we have discovered what next is in schedule and avoid looking it up twice. I'll hack something up to do that soon.

Quoted 3 lines
Quoted 1 line

Something like this (sorry I couldn't help but keep hacking on it).

Looking pretty good.

Thanks

Quoted 2 lines

Nice to acknowledge Chris's idea for
trylocks in your changelog when you submit a final patch.

I absolutely would and I would ask for him to sign off on it as well, once we agreed on a final form.

Signature · 1 line
-ck
#7 lore raw
Quoted 4 lines · Con Kolivas
Quoted 1 line

Nice to acknowledge Chris's idea for trylocks in your changelog when you submit a final patch.

I absolutely would and I would ask for him to sign off on it as well, once we agreed on a final form.

No worries, I thought you would ;)

This is a small micro-optimisation / cleanup we can do after smtnice gets converted to use trylocks. Might result in a little less cacheline footprint in some cases.

Signature · 1 line
SUSE Labs, Novell Inc.
kernel/sched.c +2 -4
Index: linux-2.6/kernel/sched.c
===================================================================
@@ -239,7 +239,6 @@ struct runqueue {
 
 	task_t *migration_thread;
 	struct list_head migration_queue;
-	int cpu;
 #endif
 
 #ifdef CONFIG_SCHEDSTATS
@@ -1700,7 +1699,7 @@ static void double_rq_lock(runqueue_t *r
 		spin_lock(&rq1->lock);
 		__acquire(rq2->lock);	/* Fake it out ;) */
 	} else {
-		if (rq1->cpu < rq2->cpu) {
+		if (rq1 < rq2) {
 			spin_lock(&rq1->lock);
 			spin_lock(&rq2->lock);
 		} else {
@@ -1736,7 +1735,7 @@ static void double_lock_balance(runqueue
 	__acquires(this_rq->lock)
 {
 	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest->cpu < this_rq->cpu) {
+		if (busiest < this_rq) {
 			spin_unlock(&this_rq->lock);
 			spin_lock(&busiest->lock);
 			spin_lock(&this_rq->lock);
@@ -6104,7 +6103,6 @@ void __init sched_init(void)
 		rq->push_cpu = 0;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
-		rq->cpu = i;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
 
#8 lore raw
Quoted 3 lines · Nick Piggin

This is a small micro-optimisation / cleanup we can do after smtnice gets converted to use trylocks. Might result in a little less cacheline footprint in some cases.

It's only dependent_sleeper that is being converted in these patches. The wake_sleeping_dependent component still locks all runqueues and needs to succeed in order to ensure a task doesn't keep sleeping indefinitely. That one doesn't get called from schedule() so is far less expensive. This means I don't think we can change that cpu based locking order which I believe was introduce to prevent a deadlock (?DaveJ disovered it iirc).

Signature · 1 line
-ck
#35 lore raw
In reply to Nick Piggin

Nick Piggin wrote on Thursday, June 01, 2006 9:19 PM

Quoted 11 lines
Quoted 10 lines · Con Kolivas
Quoted 6 lines · Con Kolivas

Actually looking even further, we only introduced the extra lookup of the next task when we started unlocking the runqueue in schedule(). Since we can get by without locking this_rq in schedule with this approach we can simplify dependent_sleeper even further by doing the dependent sleeper check after we have discovered what next is in schedule and avoid looking it up twice. I'll hack something up to do that soon.

Quoted 4 lines
Quoted 1 line

Something like this (sorry I couldn't help but keep hacking on it).

Looking pretty good. Nice to acknowledge Chris's idea for trylocks in your changelog when you submit a final patch.

Yes, as far as the lock is concerned in dependent_sleeper(), it looks pretty good. I do have other comments that I will follow up in another thread.

- Ken

#9 lore raw
In reply to Con Kolivas
Quoted 8 lines · Con Kolivas
Quoted 3 lines · Nick Piggin

This is a small micro-optimisation / cleanup we can do after smtnice gets converted to use trylocks. Might result in a little less cacheline footprint in some cases.

It's only dependent_sleeper that is being converted in these patches. The wake_sleeping_dependent component still locks all runqueues and needs to

Oh I missed that.

Quoted 1 line

succeed in order to ensure a task doesn't keep sleeping indefinitely. That

Let's make it use trylocks as well. wake_priority_sleeper should ensure things don't sleep forever I think? We should be optimising for the most common case, and in many workloads, the runqueue does go idle frequently.

Quoted 2 lines

one doesn't get called from schedule() so is far less expensive. This means I don't think we can change that cpu based locking order which I believe was introduce to prevent a deadlock (?DaveJ disovered it iirc).

AntonB, I think.

Signature · 1 line
SUSE Labs, Novell Inc.
kernel/sched.c +8 -25
Index: linux-2.6/kernel/sched.c
===================================================================
@@ -2686,6 +2686,9 @@ static inline void wakeup_busy_runqueue(
 		resched_task(rq->idle);
 }
 
+/*
+ * Called with interrupts disabled and this_rq's runqueue locked.
+ */
 static void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
 {
 	struct sched_domain *tmp, *sd = NULL;
@@ -2699,22 +2702,13 @@ static void wake_sleeping_dependent(int 
 	if (!sd)
 		return;
 
-	/*
-	 * Unlock the current runqueue because we have to lock in
-	 * CPU order to avoid deadlocks. Caller knows that we might
-	 * unlock. We keep IRQs disabled.
-	 */
-	spin_unlock(&this_rq->lock);
-
 	sibling_map = sd->span;
-
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
-	/*
-	 * We clear this CPU from the mask. This both simplifies the
-	 * inner loop and keps this_rq locked when we exit:
-	 */
 	cpu_clear(this_cpu, sibling_map);
+	for_each_cpu_mask(i, sibling_map) {
+		if (unlikely(!spin_trylock(&cpu_rq(i)->lock)))
+			cpu_clear(i, sibling_map);
+	}
+
 
 	for_each_cpu_mask(i, sibling_map) {
 		runqueue_t *smt_rq = cpu_rq(i);
@@ -2724,10 +2718,6 @@ static void wake_sleeping_dependent(int 
 
 	for_each_cpu_mask(i, sibling_map)
 		spin_unlock(&cpu_rq(i)->lock);
-	/*
-	 * We exit with this_cpu's rq still held and IRQs
-	 * still disabled:
-	 */
 }
 
 /*
@@ -2961,13 +2951,6 @@ need_resched_nonpreemptible:
 			next = rq->idle;
 			rq->expired_timestamp = 0;
 			wake_sleeping_dependent(cpu, rq);
-			/*
-			 * wake_sleeping_dependent() might have released
-			 * the runqueue, so break out if we got new
-			 * tasks meanwhile:
-			 */
-			if (!rq->nr_running)
-				goto switch_tasks;
 		}
 	}
 
#36 lore raw
In reply to Con Kolivas

Con Kolivas wrote on Thursday, June 01, 2006 8:55 PM

Quoted 8 lines · Con Kolivas
Quoted 6 lines

Actually looking even further, we only introduced the extra lookup of the next task when we started unlocking the runqueue in schedule(). Since we can get by without locking this_rq in schedule with this approach we can simplify dependent_sleeper even further by doing the dependent sleeper check after we have discovered what next is in schedule and avoid looking it up twice. I'll hack something up to do that soon.

Quoted 8 lines

Something like this (sorry I couldn't help but keep hacking on it).
---
It is not critical to functioning that dependent_sleeper() succeeds every time. We can significantly reduce the locking overhead and contention of dependent_sleeper by only doing trylock on the smt sibling runqueues. As we're only doing trylock it means we do not need to observe the normal locking order and we can get away without unlocking this_rq in schedule(). This provides us with an opportunity to simplify the code further.

The code in wake_sleeping_dependent() is also quite wacky: it unlocks current runqueue, then re-acquires ALL the sibling runqueue lock, only to call wakeup_busy_runqueue() against the smt sibling runqueue other than itself. AFAICT, wakeup_busy_runqueue() does not require *ALL* sibling lock to be held.

kernel/sched.c renamed from kernel/sched.c.orig +14 -32
@@ -2712,44 +2712,32 @@ static inline void wakeup_busy_runqueue(
 		resched_task(rq->idle);
 }
 
-static void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
+static void wake_sleeping_dependent(int this_cpu)
 {
 	struct sched_domain *tmp, *sd = NULL;
-	cpumask_t sibling_map;
 	int i;
 
 	for_each_domain(this_cpu, tmp)
-		if (tmp->flags & SD_SHARE_CPUPOWER)
+		if (tmp->flags & SD_SHARE_CPUPOWER) {
 			sd = tmp;
+			break;
+		}
 
 	if (!sd)
 		return;
 
-	/*
-	 * Unlock the current runqueue because we have to lock in
-	 * CPU order to avoid deadlocks. Caller knows that we might
-	 * unlock. We keep IRQs disabled.
-	 */
-	spin_unlock(&this_rq->lock);
-
-	sibling_map = sd->span;
-
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
-	/*
-	 * We clear this CPU from the mask. This both simplifies the
-	 * inner loop and keps this_rq locked when we exit:
-	 */
-	cpu_clear(this_cpu, sibling_map);
+	for_each_cpu_mask(i, sd->span) {
+		runqueue_t *smt_rq;
 
-	for_each_cpu_mask(i, sibling_map) {
-		runqueue_t *smt_rq = cpu_rq(i);
+		if (i == this_cpu)
+			continue;
 
+		smt_rq = cpu_rq(i);
+		spin_lock(&smt_rq->lock);
 		wakeup_busy_runqueue(smt_rq);
+		spin_unlock(&smt_rq->lock);
 	}
 
-	for_each_cpu_mask(i, sibling_map)
-		spin_unlock(&cpu_rq(i)->lock);
 	/*
 	 * We exit with this_cpu's rq still held and IRQs
 	 * still disabled:
@@ -2857,7 +2845,7 @@ check_smt_task:
 	return ret;
 }
 #else
-static inline void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
+static inline void wake_sleeping_dependent(int this_cpu)
 {
 }
 
@@ -2988,14 +2976,8 @@ need_resched_nonpreemptible:
 		if (!rq->nr_running) {
 			next = rq->idle;
 			rq->expired_timestamp = 0;
-			wake_sleeping_dependent(cpu, rq);
-			/*
-			 * wake_sleeping_dependent() might have released
-			 * the runqueue, so break out if we got new
-			 * tasks meanwhile:
-			 */
-			if (!rq->nr_running)
-				goto switch_tasks;
+			wake_sleeping_dependent(cpu);
+			goto switch_tasks;
 		}
 	}
 
#10 lore raw
In reply to Nick Piggin

Nick Piggin wrote on Friday, June 02, 2006 1:29 AM

Quoted 11 lines
Quoted 9 lines · Con Kolivas
Quoted 3 lines · Nick Piggin

This is a small micro-optimisation / cleanup we can do after smtnice gets converted to use trylocks. Might result in a little less cacheline footprint in some cases.

It's only dependent_sleeper that is being converted in these patches. The wake_sleeping_dependent component still locks all runqueues and needs to

Quoted 8 lines

Oh I missed that.

Quoted 1 line

succeed in order to ensure a task doesn't keep sleeping indefinitely. That

Let's make it use trylocks as well. wake_priority_sleeper should ensure things don't sleep forever I think? We should be optimising for the most common case, and in many workloads, the runqueue does go idle frequently.

Ha, you beat me by one minute. It did cross my mind to use try lock there as well, take a look at my version, I think I have a better inner loop.

- Ken

#34 lore raw
In reply to Nick Piggin

Nick Piggin wrote on Friday, June 02, 2006 12:53 AM

Quoted 6 lines
Quoted 4 lines · Con Kolivas
Quoted 2 lines

Nice to acknowledge Chris's idea for
trylocks in your changelog when you submit a final patch.

Quoted 6 lines
Quoted 2 lines

I absolutely would and I would ask for him to sign off on it as well, once we agreed on a final form.

This is a small micro-optimisation / cleanup we can do after smtnice gets converted to use trylocks. Might result in a little less cacheline footprint in some cases.

Just to pile up more micro-optimization: kernel can break out of the for_each_domain loop when it hits first SD_SHARE_CPUPOWER.

- Ken

kernel/sched.c renamed from kernel/sched.c.orig +3 -1
@@ -2780,8 +2780,10 @@ static int dependent_sleeper(int this_cp
 	int ret = 0, i;
 
 	for_each_domain(this_cpu, tmp)
-		if (tmp->flags & SD_SHARE_CPUPOWER)
+		if (tmp->flags & SD_SHARE_CPUPOWER) {
 			sd = tmp;
+			break;
+		}
 
 	if (!sd)
 		return 0;
#37 lore raw
In reply to Con Kolivas

Con Kolivas wrote on Thursday, June 01, 2006 8:55 PM

Quoted 8 lines · Con Kolivas
Quoted 6 lines

Actually looking even further, we only introduced the extra lookup of the next task when we started unlocking the runqueue in schedule(). Since we can get by without locking this_rq in schedule with this approach we can simplify dependent_sleeper even further by doing the dependent sleeper check after we have discovered what next is in schedule and avoid looking it up twice. I'll hack something up to do that soon.

Quoted 8 lines

Something like this (sorry I couldn't help but keep hacking on it).
---
It is not critical to functioning that dependent_sleeper() succeeds every time. We can significantly reduce the locking overhead and contention of dependent_sleeper by only doing trylock on the smt sibling runqueues. As we're only doing trylock it means we do not need to observe the normal locking order and we can get away without unlocking this_rq in schedule(). This provides us with an opportunity to simplify the code further.

Why does dependent_sleeper() has to be so bully that it actively kick off the poor little guy on the smt sibling? Can't it just wait for the less fortunate process to finish off its time slice and then it can have more physical resource to spare?

kernel/sched.c renamed from kernel/sched.c.orig +1 -27
@@ -2789,7 +2789,7 @@ static int dependent_sleeper(int this_cp
 
 		/* Kernel threads do not participate in dependent sleeping */
 		if (!p->mm || !smt_curr->mm || rt_task(p))
-			goto check_smt_task;
+			continue;
 
 		/*
 		 * If a user task with lower static priority than the
@@ -2812,32 +2812,6 @@ static int dependent_sleeper(int this_cp
 				!TASK_PREEMPTS_CURR(p, smt_rq) &&
 				smt_slice(smt_curr, sd) > task_timeslice(p))
 					ret = 1;
-
-check_smt_task:
-		if ((!smt_curr->mm && smt_curr != smt_rq->idle) ||
-			rt_task(smt_curr))
-				continue;
-		if (!p->mm) {
-			wakeup_busy_runqueue(smt_rq);
-			continue;
-		}
-
-		/*
-		 * Reschedule a lower priority task on the SMT sibling for
-		 * it to be put to sleep, or wake it up if it has been put to
-		 * sleep for priority reasons to see if it should run now.
-		 */
-		if (rt_task(p)) {
-			if ((jiffies % DEF_TIMESLICE) >
-				(sd->per_cpu_gain * DEF_TIMESLICE / 100))
-					resched_task(smt_curr);
-		} else {
-			if (TASK_PREEMPTS_CURR(p, smt_rq) &&
-				smt_slice(p, sd) > task_timeslice(smt_curr))
-					resched_task(smt_curr);
-			else
-				wakeup_busy_runqueue(smt_rq);
-		}
 	}
 
 	for_each_cpu_mask(i, sibling_map)
#11 lore raw
In reply to Chen, Kenneth W
Quoted 2 lines · Kenneth W

Ha, you beat me by one minute. It did cross my mind to use try lock there as well, take a look at my version, I think I have a better inner loop.

Actually you *have* to use trylocks I think, because the current runqueue is already locked.

And why do we lock all siblings in the other case, for that matter? (not that it makes much difference except on niagara today).

Rolled up patch with everyone's changes attached.

Signature · 1 line
SUSE Labs, Novell Inc.
kernel/sched.c +38 -80
Index: linux-2.6/kernel/sched.c
===================================================================
@@ -239,7 +239,6 @@ struct runqueue {
 
 	task_t *migration_thread;
 	struct list_head migration_queue;
-	int cpu;
 #endif
 
 #ifdef CONFIG_SCHEDSTATS
@@ -1687,7 +1686,7 @@ unsigned long nr_active(void)
  * double_rq_lock - safely lock two runqueues
  *
  * We must take them in cpu order to match code in
- * dependent_sleeper and wake_dependent_sleeper.
+ * wake_dependent_sleeper.
  *
  * Note this does not disable interrupts like task_rq_lock,
  * you need to do so manually before calling.
@@ -1700,7 +1699,7 @@ static void double_rq_lock(runqueue_t *r
 		spin_lock(&rq1->lock);
 		__acquire(rq2->lock);	/* Fake it out ;) */
 	} else {
-		if (rq1->cpu < rq2->cpu) {
+		if (rq1 < rq2) {
 			spin_lock(&rq1->lock);
 			spin_lock(&rq2->lock);
 		} else {
@@ -1736,7 +1735,7 @@ static void double_lock_balance(runqueue
 	__acquires(this_rq->lock)
 {
 	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest->cpu < this_rq->cpu) {
+		if (busiest < this_rq) {
 			spin_unlock(&this_rq->lock);
 			spin_lock(&busiest->lock);
 			spin_lock(&this_rq->lock);
@@ -2686,6 +2685,9 @@ static inline void wakeup_busy_runqueue(
 		resched_task(rq->idle);
 }
 
+/*
+ * Called with interrupts disabled and this_rq's runqueue locked.
+ */
 static void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
 {
 	struct sched_domain *tmp, *sd = NULL;
@@ -2693,41 +2695,24 @@ static void wake_sleeping_dependent(int 
 	int i;
 
 	for_each_domain(this_cpu, tmp)
-		if (tmp->flags & SD_SHARE_CPUPOWER)
+		if (tmp->flags & SD_SHARE_CPUPOWER) {
 			sd = tmp;
-
+			break;
+		}
 	if (!sd)
 		return;
 
-	/*
-	 * Unlock the current runqueue because we have to lock in
-	 * CPU order to avoid deadlocks. Caller knows that we might
-	 * unlock. We keep IRQs disabled.
-	 */
-	spin_unlock(&this_rq->lock);
-
 	sibling_map = sd->span;
-
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
-	/*
-	 * We clear this CPU from the mask. This both simplifies the
-	 * inner loop and keps this_rq locked when we exit:
-	 */
 	cpu_clear(this_cpu, sibling_map);
-
 	for_each_cpu_mask(i, sibling_map) {
 		runqueue_t *smt_rq = cpu_rq(i);
+		if (unlikely(!spin_trylock(&smt_rq->lock)))
+			continue;
 
 		wakeup_busy_runqueue(smt_rq);
-	}
 
-	for_each_cpu_mask(i, sibling_map)
-		spin_unlock(&cpu_rq(i)->lock);
-	/*
-	 * We exit with this_cpu's rq still held and IRQs
-	 * still disabled:
-	 */
+		spin_unlock(&smt_rq->lock);
+	}
 }
 
 /*
@@ -2740,48 +2725,38 @@ static inline unsigned long smt_slice(ta
 	return p->time_slice * (100 - sd->per_cpu_gain) / 100;
 }
 
-static int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
+/*
+ * To minimise lock contention and not have to drop this_rq's runlock we only
+ * trylock the sibling runqueues and bypass those runqueues if we fail to
+ * acquire their lock. As we only trylock the normal locking order does not
+ * need to be obeyed.
+ */
+static int dependent_sleeper(int this_cpu, struct runqueue *this_rq,
+	struct task_struct *p)
 {
 	struct sched_domain *tmp, *sd = NULL;
 	cpumask_t sibling_map;
-	prio_array_t *array;
 	int ret = 0, i;
-	task_t *p;
 
 	for_each_domain(this_cpu, tmp)
-		if (tmp->flags & SD_SHARE_CPUPOWER)
+		if (tmp->flags & SD_SHARE_CPUPOWER) {
 			sd = tmp;
-
+			break;
+		}
 	if (!sd)
 		return 0;
 
-	/*
-	 * The same locking rules and details apply as for
-	 * wake_sleeping_dependent():
-	 */
-	spin_unlock(&this_rq->lock);
 	sibling_map = sd->span;
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
 	cpu_clear(this_cpu, sibling_map);
+	for_each_cpu_mask(i, sibling_map) {
+		runqueue_t *smt_rq;
+		task_t *smt_curr;
 
-	/*
-	 * Establish next task to be run - it might have gone away because
-	 * we released the runqueue lock above:
-	 */
-	if (!this_rq->nr_running)
-		goto out_unlock;
-	array = this_rq->active;
-	if (!array->nr_active)
-		array = this_rq->expired;
-	BUG_ON(!array->nr_active);
-
-	p = list_entry(array->queue[sched_find_first_bit(array->bitmap)].next,
-		task_t, run_list);
+		smt_rq = cpu_rq(i);
+		if (unlikely(!spin_trylock(&smt_rq->lock)))
+			continue;
 
-	for_each_cpu_mask(i, sibling_map) {
-		runqueue_t *smt_rq = cpu_rq(i);
-		task_t *smt_curr = smt_rq->curr;
+		smt_curr = smt_rq->curr;
 
 		/* Kernel threads do not participate in dependent sleeping */
 		if (!p->mm || !smt_curr->mm || rt_task(p))
@@ -2834,10 +2809,10 @@ check_smt_task:
 			else
 				wakeup_busy_runqueue(smt_rq);
 		}
+
+		spin_unlock(&smt_rq->lock);
 	}
-out_unlock:
-	for_each_cpu_mask(i, sibling_map)
-		spin_unlock(&cpu_rq(i)->lock);
+
 	return ret;
 }
 #else
@@ -2845,7 +2820,8 @@ static inline void wake_sleeping_depende
 {
 }
 
-static inline int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
+static inline int dependent_sleeper(int this_cpu, struct runqueue *this_rq,
+	struct task_struct *p)
 {
 	return 0;
 }
@@ -2967,32 +2943,13 @@ need_resched_nonpreemptible:
 
 	cpu = smp_processor_id();
 	if (unlikely(!rq->nr_running)) {
-go_idle:
 		idle_balance(cpu, rq);
 		if (!rq->nr_running) {
 			next = rq->idle;
 			rq->expired_timestamp = 0;
 			wake_sleeping_dependent(cpu, rq);
-			/*
-			 * wake_sleeping_dependent() might have released
-			 * the runqueue, so break out if we got new
-			 * tasks meanwhile:
-			 */
-			if (!rq->nr_running)
-				goto switch_tasks;
-		}
-	} else {
-		if (dependent_sleeper(cpu, rq)) {
-			next = rq->idle;
 			goto switch_tasks;
 		}
-		/*
-		 * dependent_sleeper() releases and reacquires the runqueue
-		 * lock, hence go into the idle loop if the rq went
-		 * empty meanwhile:
-		 */
-		if (unlikely(!rq->nr_running))
-			goto go_idle;
 	}
 
 	array = rq->active;
@@ -3030,6 +2987,8 @@ go_idle:
 		}
 	}
 	next->sleep_type = SLEEP_NORMAL;
+	if (dependent_sleeper(cpu, rq, next))
+		next = rq->idle;
 switch_tasks:
 	if (next == rq->idle)
 		schedstat_inc(rq, sched_goidle);
@@ -6126,7 +6085,6 @@ void __init sched_init(void)
 		rq->push_cpu = 0;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
-		rq->cpu = i;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
 
#12 lore raw

Nick Piggin wrote on Friday, June 02, 2006 1:56 AM

Quoted 7 lines
Quoted 2 lines · Kenneth W

Ha, you beat me by one minute. It did cross my mind to use try lock there as well, take a look at my version, I think I have a better inner loop.

Actually you *have* to use trylocks I think, because the current runqueue is already locked.

You are absolutely correct. I forgot about the lock ordering.

Quoted 4 lines

And why do we lock all siblings in the other case, for that matter? (not that it makes much difference except on niagara today).

Rolled up patch with everyone's changes attached.

What about the part in dependent_sleeper() being so bully and actively resched other low priority sibling tasks? I think it would be better to just let the tasks running on sibling CPU to finish its current time slice and then let the backoff logic to kick in.

- Ken

#13 lore raw
Quoted 4 lines · Kenneth W

What about the part in dependent_sleeper() being so bully and actively resched other low priority sibling tasks? I think it would be better to just let the tasks running on sibling CPU to finish its current time slice and then let the backoff logic to kick in.

That would defeat the purpose of smt nice if the higher priority task starts after the lower priority task is running on its sibling cpu.

Signature · 1 line
-ck
#14 lore raw

Con Kolivas wrote on Friday, June 02, 2006 2:25 AM

Quoted 8 lines · Kenneth W
Quoted 4 lines

What about the part in dependent_sleeper() being so bully and actively resched other low priority sibling tasks? I think it would be better to just let the tasks running on sibling CPU to finish its current time slice and then let the backoff logic to kick in.

That would defeat the purpose of smt nice if the higher priority task starts after the lower priority task is running on its sibling cpu.

But only for the duration of lower priority tasks' time slice. When lower priority tasks time slice is used up, a resched is force from scheduler_tick(), isn't it? And at that time, it is delayed to run because of smt_nice. You are saying user can't tolerate that short period of time that CPU resource is shared? It's hard to believe.

- Ken

#15 lore raw
Quoted 8 lines · Kenneth W

Con Kolivas wrote on Friday, June 02, 2006 2:25 AM

Quoted 6 lines · Kenneth W
Quoted 4 lines

What about the part in dependent_sleeper() being so bully and actively resched other low priority sibling tasks? I think it would be better to just let the tasks running on sibling CPU to finish its current time slice and then let the backoff logic to kick in.

Quoted 8 lines
Quoted 2 lines

That would defeat the purpose of smt nice if the higher priority task starts after the lower priority task is running on its sibling cpu.

But only for the duration of lower priority tasks' time slice. When lower priority tasks time slice is used up, a resched is force from scheduler_tick(), isn't it? And at that time, it is delayed to run because of smt_nice. You are saying user can't tolerate that short period of time that CPU resource is shared? It's hard to believe.

nice -20 vs nice 0 is 800ms vs 100ms. That's a long time to me.

Signature · 1 line
-ck
#26 lore raw
In reply to Nick Piggin

Nick Piggin wrote on Friday, June 02, 2006 1:56 AM

Quoted 5 lines
Quoted 2 lines · Kenneth W

Ha, you beat me by one minute. It did cross my mind to use try lock there as well, take a look at my version, I think I have a better inner loop.

Quoted 7 lines

Actually you *have* to use trylocks I think, because the current runqueue is already locked.

And why do we lock all siblings in the other case, for that matter? (not that it makes much difference except on niagara today).

Rolled up patch with everyone's changes attached.

OK, it's down to nit-picking now:

Remove this_rq argument from wake_sleeping_dependent() since it is not used. Nick, you had that in your earlier version, but it got lost in the woods.

I don't like cpumask being declared on the stack. Here is my version to rid it out in wake_sleeping_dependent() and dependent_sleeper().

- Ken

kernel/sched.c renamed from kernel/sched.c.orig +11 -11
@@ -2714,10 +2714,9 @@ static inline void wakeup_busy_runqueue(
 /*
  * Called with interrupts disabled and this_rq's runqueue locked.
  */
-static void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
+static void wake_sleeping_dependent(int this_cpu)
 {
 	struct sched_domain *tmp, *sd = NULL;
-	cpumask_t sibling_map;
 	int i;
 
 	for_each_domain(this_cpu, tmp)
@@ -2728,10 +2727,11 @@ static void wake_sleeping_dependent(int 
 	if (!sd)
 		return;
 
-	sibling_map = sd->span;
-	cpu_clear(this_cpu, sibling_map);
-	for_each_cpu_mask(i, sibling_map) {
+	for_each_cpu_mask(i, sd->span) {
 		runqueue_t *smt_rq = cpu_rq(i);
+
+		if (i == this_cpu)
+			continue;
 		if (unlikely(!spin_trylock(&smt_rq->lock)))
 			continue;
 
@@ -2761,7 +2761,6 @@ static int dependent_sleeper(int this_cp
 	struct task_struct *p)
 {
 	struct sched_domain *tmp, *sd = NULL;
-	cpumask_t sibling_map;
 	int ret = 0, i;
 
 	for_each_domain(this_cpu, tmp)
@@ -2772,12 +2771,13 @@ static int dependent_sleeper(int this_cp
 	if (!sd)
 		return 0;
 
-	sibling_map = sd->span;
-	cpu_clear(this_cpu, sibling_map);
-	for_each_cpu_mask(i, sibling_map) {
+	for_each_cpu_mask(i, sd->span) {
 		runqueue_t *smt_rq;
 		task_t *smt_curr;
 
+		if (i == this_cpu)
+			continue;
+
 		smt_rq = cpu_rq(i);
 		if (unlikely(!spin_trylock(&smt_rq->lock)))
 			continue;
@@ -2842,7 +2842,7 @@ check_smt_task:
 	return ret;
 }
 #else
-static inline void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
+static inline void wake_sleeping_dependent(int this_cpu)
 {
 }
 
@@ -2973,7 +2973,7 @@ need_resched_nonpreemptible:
 		if (!rq->nr_running) {
 			next = rq->idle;
 			rq->expired_timestamp = 0;
-			wake_sleeping_dependent(cpu, rq);
+			wake_sleeping_dependent(cpu);
 			goto switch_tasks;
 		}
 	}
#16 lore raw
In reply to Con Kolivas

Con Kolivas wrote on Friday, June 02, 2006 2:34 AM

Quoted 12 lines · Kenneth W
Quoted 11 lines

Con Kolivas wrote on Friday, June 02, 2006 2:25 AM

Quoted 8 lines · Kenneth W
Quoted 4 lines

What about the part in dependent_sleeper() being so bully and actively resched other low priority sibling tasks? I think it would be better to just let the tasks running on sibling CPU to finish its current time slice and then let the backoff logic to kick in.

That would defeat the purpose of smt nice if the higher priority task starts after the lower priority task is running on its sibling cpu.

Quoted 7 lines
Quoted 5 lines

But only for the duration of lower priority tasks' time slice. When lower priority tasks time slice is used up, a resched is force from scheduler_tick(), isn't it? And at that time, it is delayed to run because of smt_nice. You are saying user can't tolerate that short period of time that CPU resource is shared? It's hard to believe.

nice -20 vs nice 0 is 800ms vs 100ms. That's a long time to me.

Yeah, but that is the worst case though. Average would probably be a lot lower than worst case. Also, on smt it's not like the current logical cpu is getting blocked because of another task is running on its sibling CPU. The hardware still guarantees equal share of hardware resources for both logical CPUs.

- Ken

#17 lore raw
Quoted 5 lines · Kenneth W

Yeah, but that is the worst case though. Average would probably be a lot lower than worst case. Also, on smt it's not like the current logical cpu is getting blocked because of another task is running on its sibling CPU. The hardware still guarantees equal share of hardware resources for both logical CPUs.

"Equal share of hardware resources" is exactly the problem; they shouldn't have equal share since they're sharing one physical cpu's resources. It's a relative breakage of the imposed nice support and I disagree with your conclusion.

Signature · 1 line
-ck
#32 lore raw
In reply to Nick Piggin
Quoted 9 lines · Nick Piggin
Quoted 7 lines · Con Kolivas
Quoted 3 lines · Nick Piggin

This is a small micro-optimisation / cleanup we can do after smtnice gets converted to use trylocks. Might result in a little less cacheline footprint in some cases.

It's only dependent_sleeper that is being converted in these patches. The wake_sleeping_dependent component still locks all runqueues and needs to

Quoted 8 lines

Oh I missed that.

Quoted 2 lines

succeed in order to ensure a task doesn't keep sleeping indefinitely. That

Let's make it use trylocks as well. wake_priority_sleeper should ensure things don't sleep forever I think? We should be optimising for the most common case, and in many workloads, the runqueue does go idle frequently.

wake_priority_sleeper is only called per tick which can be 10ms at 100HZ. I don't think that's fast enough. It could even be possible for a lower priority task to always just miss the wakeup if it's (very) unlucky.

Signature · 1 line
-ck
#27 lore raw
In reply to Nick Piggin
Quoted 9 lines · Nick Piggin
Quoted 2 lines · Kenneth W

Ha, you beat me by one minute. It did cross my mind to use try lock there as well, take a look at my version, I think I have a better inner loop.

Actually you *have* to use trylocks I think, because the current runqueue is already locked.

And why do we lock all siblings in the other case, for that matter? (not that it makes much difference except on niagara today).

If we spinlock (and don't trylock as you're proposing) we'd have to do a double rq lock for each sibling. I guess half the time double_rq_lock will only be locking one runqueue... with 32 runqueues we either try to lock all 32 or lock 1.5 runqueues 32 times... ugh both are ugly.

Quoted 1 line

Rolled up patch with everyone's changes attached.

I'm still not sure that only doing trylock is adequate, and wake_sleeping_dependent is only called when a runqueue falls idle in schedule, not when it's busy so its cost (in my mind) is far less than dependent_sleeper.

Signature · 1 line
-ck
#28 lore raw
Quoted 8 lines · Con Kolivas
Quoted 2 lines · Nick Piggin

And why do we lock all siblings in the other case, for that matter? (not that it makes much difference except on niagara today).

If we spinlock (and don't trylock as you're proposing) we'd have to do a double rq lock for each sibling. I guess half the time double_rq_lock will only be locking one runqueue... with 32 runqueues we either try to lock all 32 or lock 1.5 runqueues 32 times... ugh both are ugly.

Thinking some more on this it is also clear that the concept of per_cpu_gain for smt is basically wrong once we get beyond straight forward 2 thread hyperthreading. If we have more than 2 thread units per physical core, the per cpu gain per logical core will decrease the more threads are running on it. While it's always been obvious the gain per logical core is entirely dependant on the type of workload and wont be a simple 25% increase in cpu power, it is clear that even if we assume an "overall" increase in cpu for each logical core added, there will be some non linear function relating power increase to thread units used. :-|

Signature · 1 line
-ck
#18 lore raw
In reply to Con Kolivas

Con Kolivas wrote on Friday, June 02, 2006 3:13 AM

Quoted 11 lines · Kenneth W
Quoted 5 lines

Yeah, but that is the worst case though. Average would probably be a lot lower than worst case. Also, on smt it's not like the current logical cpu is getting blocked because of another task is running on its sibling CPU. The hardware still guarantees equal share of hardware resources for both logical CPUs.

"Equal share of hardware resources" is exactly the problem; they shouldn't have equal share since they're sharing one physical cpu's resources. It's a relative breakage of the imposed nice support and I disagree with your conclusion.

But you keep on missing the point that this only happens in the initial stage of tasks competing for CPU resources.

If this is broken, then current smt nice is equally broken with the same
reasoning: once the low priority task gets scheduled, there is nothing to kick it off the CPU until its entire time slice get used up. They compete equally with a high priority task running on the sibling CPU.

- Ken

#33 lore raw
In reply to Con Kolivas

Con Kolivas wrote on Friday, June 02, 2006 3:19 AM

Quoted 15 lines · Nick Piggin
Quoted 14 lines
Quoted 7 lines · Con Kolivas
Quoted 3 lines · Nick Piggin

This is a small micro-optimisation / cleanup we can do after smtnice gets converted to use trylocks. Might result in a little less cacheline footprint in some cases.

It's only dependent_sleeper that is being converted in these patches. The wake_sleeping_dependent component still locks all runqueues and needs to

Oh I missed that.

Quoted 2 lines

succeed in order to ensure a task doesn't keep sleeping indefinitely. That

Quoted 7 lines
Quoted 3 lines

Let's make it use trylocks as well. wake_priority_sleeper should ensure things don't sleep forever I think? We should be optimising for the most common case, and in many workloads, the runqueue does go idle frequently.

wake_priority_sleeper is only called per tick which can be 10ms at 100HZ. I don't think that's fast enough. It could even be possible for a lower priority task to always just miss the wakeup if it's (very) unlucky.

I see inconsistency here: in dependent_sleeper() function, you argued dearly that it is important to be bully for the high priority task to kick off low priority task on the sibling CPU. Here you are arguing dearly to put the delayed low priority sleeper back onto the CPU as early as possible (and it would possibly competing with the other high priority task). Having such biased opposite treatment in different path doesn't look correct to me.

#29 lore raw
In reply to Con Kolivas

Con Kolivas wrote on Friday, June 02, 2006 6:17 AM

Quoted 10 lines · Con Kolivas
Quoted 8 lines · Nick Piggin
Quoted 2 lines

And why do we lock all siblings in the other case, for that matter? (not that it makes much difference except on niagara today).

If we spinlock (and don't trylock as you're proposing) we'd have to do a double rq lock for each sibling. I guess half the time double_rq_lock will only be locking one runqueue... with 32 runqueues we either try to lock all 32 or lock 1.5 runqueues 32 times... ugh both are ugly.

Quoted 9 lines

Thinking some more on this it is also clear that the concept of per_cpu_gain for smt is basically wrong once we get beyond straight forward 2 thread hyperthreading. If we have more than 2 thread units per physical core, the per cpu gain per logical core will decrease the more threads are running on it. While it's always been obvious the gain per logical core is entirely dependant on the type of workload and wont be a simple 25% increase in cpu power, it is clear that even if we assume an "overall" increase in cpu for each logical core added, there will be some non linear function relating power increase to thread units used. :-|

In the context of having more than 2 sibling CPUs in a domain, doesn't the current code also suffer from thunder hurd problem as well? When high priority task goes to sleep, it will wake up *all* sibling sleepers and then they will all fight for CPU resource, but potentially only one will win?

#30 lore raw
Quoted 11 lines · Kenneth W

Con Kolivas wrote on Friday, June 02, 2006 6:17 AM

Quoted 9 lines

Thinking some more on this it is also clear that the concept of per_cpu_gain for smt is basically wrong once we get beyond straight forward 2 thread hyperthreading. If we have more than 2 thread units per physical core, the per cpu gain per logical core will decrease the more threads are running on it. While it's always been obvious the gain per logical core is entirely dependant on the type of workload and wont be a simple 25% increase in cpu power, it is clear that even if we assume an "overall" increase in cpu for each logical core added, there will be some non linear function relating power increase to thread units used. :-|

Quoted 5 lines

In the context of having more than 2 sibling CPUs in a domain, doesn't the current code also suffer from thunder hurd problem as well? When high priority task goes to sleep, it will wake up *all* sibling sleepers and then they will all fight for CPU resource, but potentially only one will win?

Yes. The smt nice code was never designed with that many threads in mind. This is why I'm bringing it up for discussion.

Signature · 1 line
-ck
#31 lore raw
In reply to Nick Piggin

Nick Piggin wrote on Friday, June 02, 2006 1:56 AM

Quoted 5 lines
Quoted 2 lines · Kenneth W

Ha, you beat me by one minute. It did cross my mind to use try lock there as well, take a look at my version, I think I have a better inner loop.

Quoted 7 lines

Actually you *have* to use trylocks I think, because the current runqueue is already locked.

And why do we lock all siblings in the other case, for that matter? (not that it makes much difference except on niagara today).

Rolled up patch with everyone's changes attached.

Rolled up patch on top of Nick's. This version doesn't have the change that removes the bully-ness in dependent_sleeper(), which is under debate right now (I still think it should be removed).

kernel/sched.c renamed from kernel/sched.c.orig +44 -91
@@ -239,7 +239,6 @@ struct runqueue {
 
 	task_t *migration_thread;
 	struct list_head migration_queue;
-	int cpu;
 #endif
 
 #ifdef CONFIG_SCHEDSTATS
@@ -1728,9 +1727,6 @@ unsigned long nr_active(void)
 /*
  * double_rq_lock - safely lock two runqueues
  *
- * We must take them in cpu order to match code in
- * dependent_sleeper and wake_dependent_sleeper.
- *
  * Note this does not disable interrupts like task_rq_lock,
  * you need to do so manually before calling.
  */
@@ -1742,7 +1738,7 @@ static void double_rq_lock(runqueue_t *r
 		spin_lock(&rq1->lock);
 		__acquire(rq2->lock);	/* Fake it out ;) */
 	} else {
-		if (rq1->cpu < rq2->cpu) {
+		if (rq1 < rq2) {
 			spin_lock(&rq1->lock);
 			spin_lock(&rq2->lock);
 		} else {
@@ -1778,7 +1774,7 @@ static void double_lock_balance(runqueue
 	__acquires(this_rq->lock)
 {
 	if (unlikely(!spin_trylock(&busiest->lock))) {
-		if (busiest->cpu < this_rq->cpu) {
+		if (busiest < this_rq) {
 			spin_unlock(&this_rq->lock);
 			spin_lock(&busiest->lock);
 			spin_lock(&this_rq->lock);
@@ -2712,48 +2708,33 @@ static inline void wakeup_busy_runqueue(
 		resched_task(rq->idle);
 }
 
-static void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
+/*
+ * Called with interrupts disabled and this_rq's runqueue locked.
+ */
+static void wake_sleeping_dependent(int this_cpu)
 {
 	struct sched_domain *tmp, *sd = NULL;
-	cpumask_t sibling_map;
 	int i;
 
 	for_each_domain(this_cpu, tmp)
-		if (tmp->flags & SD_SHARE_CPUPOWER)
+		if (tmp->flags & SD_SHARE_CPUPOWER) {
 			sd = tmp;
-
+			break;
+		}
 	if (!sd)
 		return;
 
-	/*
-	 * Unlock the current runqueue because we have to lock in
-	 * CPU order to avoid deadlocks. Caller knows that we might
-	 * unlock. We keep IRQs disabled.
-	 */
-	spin_unlock(&this_rq->lock);
-
-	sibling_map = sd->span;
-
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
-	/*
-	 * We clear this CPU from the mask. This both simplifies the
-	 * inner loop and keps this_rq locked when we exit:
-	 */
-	cpu_clear(this_cpu, sibling_map);
-
-	for_each_cpu_mask(i, sibling_map) {
+	for_each_cpu_mask(i, sd->span) {
 		runqueue_t *smt_rq = cpu_rq(i);
 
+		if (i == this_cpu)
+			continue;
+		if (unlikely(!spin_trylock(&smt_rq->lock)))
+			continue;
+
 		wakeup_busy_runqueue(smt_rq);
+		spin_unlock(&smt_rq->lock);
 	}
-
-	for_each_cpu_mask(i, sibling_map)
-		spin_unlock(&cpu_rq(i)->lock);
-	/*
-	 * We exit with this_cpu's rq still held and IRQs
-	 * still disabled:
-	 */
 }
 
 /*
@@ -2766,48 +2747,38 @@ static inline unsigned long smt_slice(ta
 	return p->time_slice * (100 - sd->per_cpu_gain) / 100;
 }
 
-static int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
+/*
+ * To minimise lock contention and not have to drop this_rq's runlock we only
+ * trylock the sibling runqueues and bypass those runqueues if we fail to
+ * acquire their lock. As we only trylock the normal locking order does not
+ * need to be obeyed.
+ */
+static int dependent_sleeper(int this_cpu, struct runqueue *this_rq,
+	struct task_struct *p)
 {
 	struct sched_domain *tmp, *sd = NULL;
-	cpumask_t sibling_map;
-	prio_array_t *array;
 	int ret = 0, i;
-	task_t *p;
 
 	for_each_domain(this_cpu, tmp)
-		if (tmp->flags & SD_SHARE_CPUPOWER)
+		if (tmp->flags & SD_SHARE_CPUPOWER) {
 			sd = tmp;
-
+			break;
+		}
 	if (!sd)
 		return 0;
 
-	/*
-	 * The same locking rules and details apply as for
-	 * wake_sleeping_dependent():
-	 */
-	spin_unlock(&this_rq->lock);
-	sibling_map = sd->span;
-	for_each_cpu_mask(i, sibling_map)
-		spin_lock(&cpu_rq(i)->lock);
-	cpu_clear(this_cpu, sibling_map);
+	for_each_cpu_mask(i, sd->span) {
+		runqueue_t *smt_rq;
+		task_t *smt_curr;
 
-	/*
-	 * Establish next task to be run - it might have gone away because
-	 * we released the runqueue lock above:
-	 */
-	if (!this_rq->nr_running)
-		goto out_unlock;
-	array = this_rq->active;
-	if (!array->nr_active)
-		array = this_rq->expired;
-	BUG_ON(!array->nr_active);
+		if (i == this_cpu)
+			continue;
 
-	p = list_entry(array->queue[sched_find_first_bit(array->bitmap)].next,
-		task_t, run_list);
+		smt_rq = cpu_rq(i);
+		if (unlikely(!spin_trylock(&smt_rq->lock)))
+			continue;
 
-	for_each_cpu_mask(i, sibling_map) {
-		runqueue_t *smt_rq = cpu_rq(i);
-		task_t *smt_curr = smt_rq->curr;
+		smt_curr = smt_rq->curr;
 
 		/* Kernel threads do not participate in dependent sleeping */
 		if (!p->mm || !smt_curr->mm || rt_task(p))
@@ -2860,18 +2831,18 @@ check_smt_task:
 			else
 				wakeup_busy_runqueue(smt_rq);
 		}
+
+		spin_unlock(&smt_rq->lock);
 	}
-out_unlock:
-	for_each_cpu_mask(i, sibling_map)
-		spin_unlock(&cpu_rq(i)->lock);
 	return ret;
 }
 #else
-static inline void wake_sleeping_dependent(int this_cpu, runqueue_t *this_rq)
+static inline void wake_sleeping_dependent(int this_cpu)
 {
 }
 
-static inline int dependent_sleeper(int this_cpu, runqueue_t *this_rq)
+static inline int dependent_sleeper(int this_cpu, struct runqueue *this_rq,
+	struct task_struct *p)
 {
 	return 0;
 }
@@ -2993,32 +2964,13 @@ need_resched_nonpreemptible:
 
 	cpu = smp_processor_id();
 	if (unlikely(!rq->nr_running)) {
-go_idle:
 		idle_balance(cpu, rq);
 		if (!rq->nr_running) {
 			next = rq->idle;
 			rq->expired_timestamp = 0;
-			wake_sleeping_dependent(cpu, rq);
-			/*
-			 * wake_sleeping_dependent() might have released
-			 * the runqueue, so break out if we got new
-			 * tasks meanwhile:
-			 */
-			if (!rq->nr_running)
-				goto switch_tasks;
-		}
-	} else {
-		if (dependent_sleeper(cpu, rq)) {
-			next = rq->idle;
+			wake_sleeping_dependent(cpu);
 			goto switch_tasks;
 		}
-		/*
-		 * dependent_sleeper() releases and reacquires the runqueue
-		 * lock, hence go into the idle loop if the rq went
-		 * empty meanwhile:
-		 */
-		if (unlikely(!rq->nr_running))
-			goto go_idle;
 	}
 
 	array = rq->active;
@@ -3056,6 +3008,8 @@ go_idle:
 		}
 	}
 	next->sleep_type = SLEEP_NORMAL;
+	if (dependent_sleeper(cpu, rq, next))
+		next = rq->idle;
 switch_tasks:
 	if (next == rq->idle)
 		schedstat_inc(rq, sched_goidle);
@@ -6152,7 +6106,6 @@ void __init sched_init(void)
 		rq->push_cpu = 0;
 		rq->migration_thread = NULL;
 		INIT_LIST_HEAD(&rq->migration_queue);
-		rq->cpu = i;
 #endif
 		atomic_set(&rq->nr_iowait, 0);
 
#19 lore raw
In reply to Chen, Kenneth W
Quoted 14 lines · Kenneth W

Con Kolivas wrote on Friday, June 02, 2006 3:13 AM

Quoted 11 lines · Kenneth W
Quoted 5 lines

Yeah, but that is the worst case though. Average would probably be a lot lower than worst case. Also, on smt it's not like the current logical cpu is getting blocked because of another task is running on its sibling CPU. The hardware still guarantees equal share of hardware resources for both logical CPUs.

"Equal share of hardware resources" is exactly the problem; they shouldn't have equal share since they're sharing one physical cpu's resources. It's a relative breakage of the imposed nice support and I disagree with your conclusion.

Quoted 7 lines

But you keep on missing the point that this only happens in the initial stage of tasks competing for CPU resources.

If this is broken, then current smt nice is equally broken with the same
reasoning: once the low priority task gets scheduled, there is nothing to kick it off the CPU until its entire time slice get used up. They compete equally with a high priority task running on the sibling CPU.

There has to be some way of metering it out and in the absence of cpu based hardware priority support (like ppc64 has) the only useful thing we have to work with is timeslice. Yes sometimes the high priority task is at the start and sometimes at the end of the timeslice but overall it balances the proportions out reasonably fairly.

Signature · 1 line
-ck
#20 lore raw

Con Kolivas wrote on Friday, June 02, 2006 3:15 PM

Quoted 23 lines · Kenneth W
Quoted 14 lines

Con Kolivas wrote on Friday, June 02, 2006 3:13 AM

Quoted 11 lines · Kenneth W
Quoted 5 lines

Yeah, but that is the worst case though. Average would probably be a lot lower than worst case. Also, on smt it's not like the current logical cpu is getting blocked because of another task is running on its sibling CPU. The hardware still guarantees equal share of hardware resources for both logical CPUs.

"Equal share of hardware resources" is exactly the problem; they shouldn't have equal share since they're sharing one physical cpu's resources. It's a relative breakage of the imposed nice support and I disagree with your conclusion.

Quoted 7 lines

But you keep on missing the point that this only happens in the initial stage of tasks competing for CPU resources.

If this is broken, then current smt nice is equally broken with the same
reasoning: once the low priority task gets scheduled, there is nothing to kick it off the CPU until its entire time slice get used up. They compete equally with a high priority task running on the sibling CPU.

Quoted 5 lines

There has to be some way of metering it out and in the absence of cpu based hardware priority support (like ppc64 has) the only useful thing we have to work with is timeslice. Yes sometimes the high priority task is at the start and sometimes at the end of the timeslice but overall it balances the proportions out reasonably fairly.

Good! Then why special case the initial stage? Just let task run and it will even out statistically. Everyone is happy, less code, less special case, same end result.

#21 lore raw
Quoted 32 lines · Kenneth W

Con Kolivas wrote on Friday, June 02, 2006 3:15 PM

Quoted 24 lines · Kenneth W
Quoted 14 lines

Con Kolivas wrote on Friday, June 02, 2006 3:13 AM

Quoted 11 lines · Kenneth W
Quoted 5 lines

Yeah, but that is the worst case though. Average would probably be a lot lower than worst case. Also, on smt it's not like the current logical cpu is getting blocked because of another task is running on its sibling CPU. The hardware still guarantees equal share of hardware resources for both logical CPUs.

"Equal share of hardware resources" is exactly the problem; they shouldn't have equal share since they're sharing one physical cpu's resources. It's a relative breakage of the imposed nice support and I disagree with your conclusion.

Quoted 8 lines

But you keep on missing the point that this only happens in the initial stage of tasks competing for CPU resources.

If this is broken, then current smt nice is equally broken with the same reasoning: once the low priority task gets scheduled, there is nothing to kick it off the CPU until its entire time slice get used up.
They compete equally with a high priority task running on the sibling
CPU.

Quoted 5 lines

There has to be some way of metering it out and in the absence of cpu based hardware priority support (like ppc64 has) the only useful thing we have to work with is timeslice. Yes sometimes the high priority task is at the start and sometimes at the end of the timeslice but overall it balances the proportions out reasonably fairly.

Quoted 3 lines

Good! Then why special case the initial stage? Just let task run and it will even out statistically. Everyone is happy, less code, less special case, same end result.

Hang on I think I missed something there. What did you conclude I conceded there? When I say "work with timeslice" I mean use percentage of timeslice the way smt nice currently does.

Signature · 1 line
-ck
#22 lore raw

Con Kolivas wrote on Friday, June 02, 2006 3:32 PM

Quoted 15 lines
Quoted 15 lines
Quoted 14 lines
Quoted 8 lines

But you keep on missing the point that this only happens in the initial stage of tasks competing for CPU resources.

If this is broken, then current smt nice is equally broken with the same reasoning: once the low priority task gets scheduled, there is nothing to kick it off the CPU until its entire time slice get used up.
They compete equally with a high priority task running on the sibling
CPU.

There has to be some way of metering it out and in the absence of cpu based hardware priority support (like ppc64 has) the only useful thing we have to work with is timeslice. Yes sometimes the high priority task is at the start and sometimes at the end of the timeslice but overall it balances the proportions out reasonably fairly.

Quoted 7 lines
Quoted 3 lines

Good! Then why special case the initial stage? Just let task run and it will even out statistically. Everyone is happy, less code, less special case, same end result.

Hang on I think I missed something there. What did you conclude I conceded there? When I say "work with timeslice" I mean use percentage of timeslice the way smt nice currently does.

You haven't answered my question either. What is the benefit of special casing the initial stage of cpu resource competition? Is it quantitatively measurable? If so, how much and with what workload?

Also there are oddness in the way that the sleep decision is made: 75% of resched decision is to sleep, while 25% of the time is to run, but there are fussiness in there and all depends on when the resched and time slice expires. Considering a scenario when resched occurs on jiffies%100 = 10, and low priority task time slice of 100 jiffies, the current code always decide to run the low priority task!

 if (rt_task(smt_curr)) {
    /*
     * With real time tasks we run non-rt tasks only
     * per_cpu_gain% of the time.
     */
    if ((jiffies % DEF_TIMESLICE) >
       (sd->per_cpu_gain * DEF_TIMESLICE / 100))
             ret = 1;

The whole point is: precise fairness can not be (or difficult to) control at milli-second range. It all will work out statistically in a long run. Which again brings back the question: what does the special casing in precision control will bring to the overall scheme? So far, I have not seen any quantitative measure at all that indicates it is a win.

- Ken

#23 lore raw
Quoted 3 lines · Kenneth W

You haven't answered my question either. What is the benefit of special casing the initial stage of cpu resource competition? Is it quantitatively measurable? If so, how much and with what workload?

Ah you mean what the whole point of smt nice is? Yes it's simple enough to do. Take the single hyperthreaded cpu with two cpu bound workloads. Let's say I run a cpu bound task nice 0 by itself and it completes in time X. If I boot it with hyperthread disabled and run a nice 0 and nice 19 task, the nice 0 task gets 95% of the cpu and completes in time X*0.95. If I boot with hyperthread enabled and run the nice 0 and nice 19 tasks, the nice 0 task gets 100% of one sibling and the nice 19 task 100% of the other sibling. The nice 0 task completes in X*0.6. With the smt nice code added it completed in X*0.95. The ratios here are dependent on the workload but that was the average I could determine from comparing mprime workloads at differing nice and kernel compiles. There is no explicit way on the Intel smt cpus to tell it which sibling is running lower priority tasks (sprinkling mwaits around at regular intervals is not a realistic option for example).

Signature · 1 line
-ck
#24 lore raw

Con Kolivas wrote on Friday, June 02, 2006 5:03 PM

Quoted 5 lines · Kenneth W
Quoted 3 lines

You haven't answered my question either. What is the benefit of special casing the initial stage of cpu resource competition? Is it quantitatively measurable? If so, how much and with what workload?

Quoted 13 lines

Ah you mean what the whole point of smt nice is? Yes it's simple enough to do. Take the single hyperthreaded cpu with two cpu bound workloads. Let's say I run a cpu bound task nice 0 by itself and it completes in time X. If I boot it with hyperthread disabled and run a nice 0 and nice 19 task, the nice 0 task gets 95% of the cpu and completes in time X*0.95. If I boot with hyperthread enabled and run the nice 0 and nice 19 tasks, the nice 0 task gets 100% of one sibling and the nice 19 task 100% of the other sibling. The nice 0 task completes in X*0.6. With the smt nice code added it completed in X*0.95. The ratios here are dependent on the workload but that was the average I could determine from comparing mprime workloads at differing nice and kernel compiles. There is no explicit way on the Intel smt cpus to tell it which sibling is running lower priority tasks (sprinkling mwaits around at regular intervals is not a realistic option for example).

I know what smt nice is doing, and it is fine to have. I'm simply proposing the following patch, on top of last roll up patch.

kernel/sched.c +1 -27
diff -u ./kernel/sched.c ./kernel/sched.c
@@ -2782,7 +2782,7 @@
 
 		/* Kernel threads do not participate in dependent sleeping */
 		if (!p->mm || !smt_curr->mm || rt_task(p))
-			goto check_smt_task;
+			continue;
 
 		/*
 		 * If a user task with lower static priority than the
@@ -2806,32 +2806,6 @@
 				smt_slice(smt_curr, sd) > task_timeslice(p))
 					ret = 1;
 
-check_smt_task:
-		if ((!smt_curr->mm && smt_curr != smt_rq->idle) ||
-			rt_task(smt_curr))
-				continue;
-		if (!p->mm) {
-			wakeup_busy_runqueue(smt_rq);
-			continue;
-		}
-
-		/*
-		 * Reschedule a lower priority task on the SMT sibling for
-		 * it to be put to sleep, or wake it up if it has been put to
-		 * sleep for priority reasons to see if it should run now.
-		 */
-		if (rt_task(p)) {
-			if ((jiffies % DEF_TIMESLICE) >
-				(sd->per_cpu_gain * DEF_TIMESLICE / 100))
-					resched_task(smt_curr);
-		} else {
-			if (TASK_PREEMPTS_CURR(p, smt_rq) &&
-				smt_slice(p, sd) > task_timeslice(smt_curr))
-					resched_task(smt_curr);
-			else
-				wakeup_busy_runqueue(smt_rq);
-		}
-
 		spin_unlock(&smt_rq->lock);
 	}
 	return ret;
#25 lore raw
Quoted 2 lines · Kenneth W

I know what smt nice is doing, and it is fine to have. I'm simply proposing the following patch, on top of last roll up patch.

It's still relative breakage of the semantics but I'm willing to concede that it will only help a very small proportion of the time with the largest timeslices and is in the fastpath.

Signature · 1 line
-ck