The latest sched-devel.git tree can be pulled from:
  git://git.kernel.org/pub/scm/linux/kernel/git/mingo/linux-2.6-sched-devel.git
Lots of scheduler updates in the past few days, done by many people.

Most importantly, the SMP latency problems reported and debugged by Mike

Galbraith should be fixed for good now.
I've also included the latest and greatest group-fairness scheduling

patch from Srivatsa Vaddagiri, which can now be used without containers

as well (in a simplified, each-uid-gets-its-fair-share mode). This

feature (CONFIG_FAIR_USER_SCHED) is now default-enabled.
Peter Zijlstra has been busy enhancing the math of the scheduler: we've

got the new 'vslice' forked-task code that should enable snappier shell

commands during load while still keeping kbuild workloads in check.
On my testsystems this codebase starts looking like something that could

be merged into v2.6.24, so please give it a good workout and let us know

if there's anything bad going on. (If this works out fine then i'll

propagate these changes back into the CFS backport, for wider testing.)
	Ingo
----------------------------------------->

the shortlog relative to 2.6.23-rc7:
Dmitry Adamushko (8):

      sched: clean up struct load_stat

      sched: clean up schedstat block in dequeue_entity()

      sched: sched_setscheduler() fix

      sched: add set_curr_task() calls

      sched: do not keep current in the tree and get rid of sched_entity::fair_key

      sched: optimize task_new_fair()

      sched: simplify sched_class::yield_task()

      sched: rework enqueue/dequeue_entity() to get rid of set_curr_task()
Ingo Molnar (41):

      sched: fix new-task method

      sched: resched task in task_new_fair()

      sched: small sched_debug cleanup

      sched: debug: track maximum 'slice'

      sched: uniform tunings

      sched: use constants if !CONFIG_SCHED_DEBUG

      sched: remove stat_gran

      sched: remove precise CPU load

      sched: remove precise CPU load calculations #...
[ message continues ]

This doornails the Vaio.  After grub handover the screen remains black

and the fan goes whir.
http://userweb.kernel.org/~akpm/config-sony.txt

-

This seems to be UP regression. Sorry abt that. I could recreate

the problem very easily with CONFIG_SMP turned off.
Can you check if this patch works? Works for me here.
--
Fix UP breakage.
Signed-off-by : Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
---

 kernel/sched.c |    2 +-

 1 file changed, 1 insertion(+), 1 deletion(-)
Index: current/kernel/sched.c

===================================================================

--- current.orig/kernel/sched.c

+++ current/kernel/sched.c

@@ -1029,8 +1029,8 @@ static inline void __set_task_cpu(struct

 {

 #ifdef CONFIG_SMP

 	task_thread_info(p)->cpu = cpu;

-	set_task_cfs_rq(p);

 #endif

+	set_task_cfs_rq(p);

 }
 #ifdef CONFIG_SMP
--

Regards,

vatsa

-

thanks - i've put this fix into the core group-scheduling patch.
	Ingo

-

yup, that's a fix.  It was 15 minutes too late for rc8-mm1 though :(

-

Hi;
Seems like following trivial change needed to compile without CONFIG_SCHEDSTATS
caglar@zangetsu linux-2.6 $ LC_ALL=C make

  CHK     include/linux/version.h

  CHK     include/linux/utsrelease.h

  CALL    scripts/checksyscalls.sh

  CHK     include/linux/compile.h

  CC      kernel/sched.o

In file included from kernel/sched.c:853:

kernel/sched_debug.c: In function `print_cfs_rq':

kernel/sched_debug.c:139: error: structure has no member named `bkl_cnt'

kernel/sched_debug.c:139: error: structure has no member named `bkl_cnt'

make[1]: *** [kernel/sched.o] Error 1

make: *** [kernel] Error 2
Signed-off-by: S.Çağlar Onur <caglar@pardus.org.tr>
diff --git a/kernel/sched_debug.c b/kernel/sched_debug.c

index b68e593..4659c90 100644

--- a/kernel/sched_debug.c

+++ b/kernel/sched_debug.c

@@ -136,8 +136,10 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)

 			SPLIT_NS(spread0));

 	SEQ_printf(m, "  .%-30s: %ld\n", "nr_running", cfs_rq->nr_running);

 	SEQ_printf(m, "  .%-30s: %ld\n", "load", cfs_rq->load.weight);

+#ifdef CONFIG_SCHEDSTATS

 	SEQ_printf(m, "  .%-30s: %ld\n", "bkl_cnt",

 			rq->bkl_cnt);

+#endif

 	SEQ_printf(m, "  .%-30s: %ld\n", "nr_spread_over",

 			cfs_rq->nr_spread_over);

 }
Cheers

--

S.Çağlar Onur <caglar@pardus.org.tr>

http://cekirdek.pardus.org.tr/~caglar/
Linux is like living in a teepee. No Windows, no Gates and an Apache in house!

-

thanks, applied!
	Ingo

-

Off-by-one bug in attribution, rocks and sticks (down boy!) don't

count ;-)  I just built, and will spend the morning beating on it... no

news is good news.
	-Mike
-

Darn, have news: latency thing isn't dead.  Two busy loops, one at nice

0 pinned to CPU0, and one at nice 19 pinned to CPU1 produced the

latencies below for nice -5 Xorg.  Didn't kill the box though.
se.wait_max              :            10.068169

se.wait_max              :             7.465334

se.wait_max              :           135.501816

se.wait_max              :             0.884483

se.wait_max              :           144.218955

se.wait_max              :           128.578376

se.wait_max              :            93.975768

se.wait_max              :             4.965965

se.wait_max              :           113.655533

se.wait_max              :             4.301075
sched_debug (attached) is.. strange.
	-Mike

Disabling CONFIG_FAIR_GROUP_SCHED fixed both.  Latencies of up to 336ms

hit me during the recompile (make -j3), with nothing else running.

Since reboot, latencies are, so far, very very nice.  I'm leaving it

disabled for now.
	-Mike 
-

heh. Evil plan to enable the group scheduler by default worked out as

planned! ;-) [guess how many container users would do ... interactivity 
ok, i'm too seeing some sort of latency weirdness with

CONFIG_FAIR_GROUP_SCHED enabled, _if_ there's Xorg involved which runs

under root uid on my box - and hence gets 50% of all CPU time.
Srivatsa, any ideas? It could either be an accounting buglet (less

likely, seems like the group scheduling bits stick to the 50% splitup

nicely), or a preemption buglet. One potential preemption buglet would

be for the group scheduler to not properly preempt a running task when a

task from another uid is woken?
	Ingo

-

Yep, I noticed that too.
check_preempt_wakeup()

{

	...
	if (is_same_group(curr, p)) {

	    ^^^^^^^^^^^^^
		resched_task();

	}
}
Will try a fix to check for preemption at higher levels ..
--

Regards,

vatsa

-

i bet fixing this will increase precision of group scheduling as well.

Those long latencies can be thought of as noise as well, and the

fair-scheduling "engine" might not be capable to offset all sources of

noise. So generally, while we allow a certain amount of lag in

preemption decisions (wakeup-granularity, etc.), with which the fairness

engine will cope just fine, we do not want to allow unlimited lag.
	Ingo

-

hm, i tried the naive patch. In theory the vruntime of all scheduling

entities should be 'compatible' and comparable (that's the point behind

using vruntime - the fairness engine drives each vruntime forward and

tries to balance them).
So the patch below just removes the is_same_group() condition. But i can

still see bad (and obvious) latencies with Mike's 2-hogs test:
 taskset 01 perl -e 'while (1) {}' &

 nice -19 taskset 02 perl -e 'while (1) {}' &
So something's amiss.
	Ingo
------------------->

Subject: sched: group scheduler wakeup latency fix

From: Ingo Molnar <mingo@elte.hu>
group scheduler wakeup latency fix.
Signed-off-by: Ingo Molnar <mingo@elte.hu>

---

 kernel/sched_fair.c |    9 ++++-----

 1 file changed, 4 insertions(+), 5 deletions(-)
Index: linux/kernel/sched_fair.c

===================================================================

--- linux.orig/kernel/sched_fair.c

+++ linux/kernel/sched_fair.c

@@ -785,6 +785,7 @@ static void check_preempt_wakeup(struct

 {

 	struct task_struct *curr = rq->curr;

 	struct cfs_rq *cfs_rq = task_cfs_rq(curr);

+	s64 delta;
 	if (unlikely(rt_prio(p->prio))) {

 		update_rq_clock(rq);

@@ -792,12 +793,10 @@ static void check_preempt_wakeup(struct

 		resched_task(curr);

 		return;

 	}

-	if (is_same_group(curr, p)) {

-		s64 delta = curr->se.vruntime - p->se.vruntime;

+	delta = curr->se.vruntime - p->se.vruntime;
-		if (delta > (s64)sysctl_sched_wakeup_granularity)

-			resched_task(curr);

-	}

+	if (delta > (s64)sysctl_sched_wakeup_granularity)

+		resched_task(curr);

 }
 static struct task_struct *pick_next_task_fair(struct rq *rq)

-

While I try recreating this myself, I wonder if this patch helps?
---

 kernel/sched_fair.c |   19 ++++++++++++++-----

 1 file changed, 14 insertions(+), 5 deletions(-)
Index: current/kernel/sched_fair.c

===================================================================

--- current.orig/kernel/sched_fair.c

+++ current/kernel/sched_fair.c

@@ -794,7 +794,8 @@ static void yield_task_fair(struct rq *r

 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)

 {

 	struct task_struct *curr = rq->curr;

-	struct cfs_rq *cfs_rq = task_cfs_rq(curr);

+	struct cfs_rq *cfs_rq = task_cfs_rq(curr), *pcfs_rq;

+	struct sched_entity *se = &curr->se, *pse = &p->se;
 	if (unlikely(rt_prio(p->prio))) {

 		update_rq_clock(rq);

@@ -802,11 +803,19 @@ static void check_preempt_wakeup(struct

 		resched_task(curr);

 		return;

 	}

-	if (is_same_group(curr, p)) {

-		s64 delta = curr->se.vruntime - p->se.vruntime;
-		if (delta > (s64)sysctl_sched_wakeup_granularity)

-			resched_task(curr);

+	for_each_sched_entity(se) {

+		cfs_rq = cfs_rq_of(se);

+		pcfs_rq = cfs_rq_of(pse);

+

+		if (cfs_rq == pcfs_rq) {

+			s64 delta = se->vruntime - pse->vruntime;

+

+			if (delta > (s64)sysctl_sched_wakeup_granularity)

+				resched_task(curr);

+			break;

+		}

+		pse = pse->parent;

 	}

 }
--

Regards,

vatsa

-

It didn't here, nor did tweaking root's share.  Booting with maxcpus=1,

I was unable to produce large latencies, but didn't try very many

things.
	-Mike
-

Easy way to make it pretty bad: pin a nice 0 loop to CPU0, pin a nice 19

loop to CPU1, then start an unpinned make.. more Xorg bouncing back and

forth I suppose.
se.wait_max              :            14.105683

se.wait_max              :           316.943787

se.wait_max              :           692.884324

se.wait_max              :            38.165534

se.wait_max              :           732.883492

se.wait_max              :           127.059784

se.wait_max              :            63.403549

se.wait_max              :           372.933284
	-Mike
-

you should be able to recreate this easily by booting with maxcpus=1 and

the commands above - then run a few instances of chew-max (without them

being bound to any particular CPUs) and the latencies should show up.
i have tried your patch and it does not solve the problem - i think

there's a more fundamental bug lurking, besides the wakeup latency

problem.
Find below a /proc/sched_debug output of a really large latency. The

latency is caused by the _huge_ (~450 seconds!) vruntime offset that

'loop_silent' and 'sshd' has:
            task   PID         tree-key  switches  prio     exec-runtime

     -------------------------------------------------------------------

     loop_silent  2391     55344.211189       203   120     55344.211189

            sshd  2440    513334.978030         4   120    513334.978030

R            cat  2496    513672.558835         4   120    513672.558835
hm. perhaps this fixup in kernel/sched.c:set_task_cpu():
        p->se.vruntime -= old_rq->cfs.min_vruntime - new_rq->cfs.min_vruntime;
needs to become properly group-hierarchy aware?
	Ingo
------------------>

Sched Debug Version: v0.05-v20, 2.6.23-rc7 #89

now at 95878.065440 msecs

  .sysctl_sched_latency                    : 20.000000

  .sysctl_sched_min_granularity            : 2.000000

  .sysctl_sched_wakeup_granularity         : 2.000000

  .sysctl_sched_batch_wakeup_granularity   : 25.000000

  .sysctl_sched_child_runs_first           : 0.000001

  .sysctl_sched_features                   : 3
cpu#0, 1828.868 MHz

  .nr_running                    : 3

  .load                          : 3072

  .nr_switches                   : 32032

  .nr_load_updates               : 95906

  .nr_uninterruptible            : 4294967238

  .jiffies                       : 4294763202

  .next_balance                  : 4294.763420

  .curr->pid                     : 2496

  .clock                         : 95893.484495

  .idle_clock                    : 55385.089335

  .prev_clock_raw  ...
[ message continues ]

This definitely does need some fixup, even though I am not sure yet if

it will solve completely the latency issue.
I tried the following patch. I *think* I see some improvement, wrt

latency seen when I type on the shell. Before this patch, I noticed

oddities like "kill -9 chew-max-pid" wont kill chew-max (it is queued in

runqueue waiting for a looong time to run before it can acknowledge

signal and exit). With this patch, I don't see such oddities ..So I am hoping

it fixes the latency problem you are seeing as well.
Index: current/kernel/sched.c

===================================================================

--- current.orig/kernel/sched.c

+++ current/kernel/sched.c

@@ -1039,6 +1039,8 @@ void set_task_cpu(struct task_struct *p,

 {

 	int old_cpu = task_cpu(p);

 	struct rq *old_rq = cpu_rq(old_cpu), *new_rq = cpu_rq(new_cpu);

+	struct cfs_rq *old_cfsrq = task_cfs_rq(p),

+		      *new_cfsrq = cpu_cfs_rq(old_cfsrq, new_cpu);

 	u64 clock_offset;
 	clock_offset = old_rq->clock - new_rq->clock;

@@ -1051,7 +1053,8 @@ void set_task_cpu(struct task_struct *p,

 	if (p->se.block_start)

 		p->se.block_start -= clock_offset;

 #endif

-	p->se.vruntime -= old_rq->cfs.min_vruntime - new_rq->cfs.min_vruntime;

+	p->se.vruntime -= old_cfsrq->min_vruntime -

+					 new_cfsrq->min_vruntime;
 	__set_task_cpu(p, new_cpu);

 }
--

Regards,

vatsa

-

http://lkml.org/lkml/2007/9/25/117 plus the below seems to be the SIlver
-

Cool ..Thanks for the quick feedback.
Ingo, do the two patches fix the latency problems you were seeing as

well?
--

Regards,

vatsa

-

a quick first stab like the one below does not appear to solve the

problem.
	Ingo
------------------->

Subject: sched: group scheduler SMP migration fix

From: Ingo Molnar <mingo@elte.hu>
group scheduler SMP migration fix.
Signed-off-by: Ingo Molnar <mingo@elte.hu>

---

 kernel/sched.c |    9 +++++++--

 1 file changed, 7 insertions(+), 2 deletions(-)
Index: linux/kernel/sched.c

===================================================================

--- linux.orig/kernel/sched.c

+++ linux/kernel/sched.c

@@ -1039,7 +1039,8 @@ void set_task_cpu(struct task_struct *p,

 {

 	int old_cpu = task_cpu(p);

 	struct rq *old_rq = cpu_rq(old_cpu), *new_rq = cpu_rq(new_cpu);

-	u64 clock_offset;

+	struct sched_entity *se;

+	u64 clock_offset, voffset;
 	clock_offset = old_rq->clock - new_rq->clock;
@@ -1051,7 +1052,11 @@ void set_task_cpu(struct task_struct *p,

 	if (p->se.block_start)

 		p->se.block_start -= clock_offset;

 #endif

-	p->se.vruntime -= old_rq->cfs.min_vruntime - new_rq->cfs.min_vruntime;

+

+	se = &p->se;

+	voffset = old_rq->cfs.min_vruntime - new_rq->cfs.min_vruntime;

+	for_each_sched_entity(se)

+		se->vruntime -= voffset;
 	__set_task_cpu(p, new_cpu);

 }

-

You seem to have hit the nerve for this problem. The two patches I sent:
	http://lkml.org/lkml/2007/9/25/117

	http://lkml.org/lkml/2007/9/25/168
Note that parent entities for a task is per-cpu. So if a task A

belonging to userid guest hops from CPU0 to CPU1, then it gets a new parent

entity as well, which is different from its parent entity on CPU0.
Before:

	taskA->se.parent = guest's tg->se[0]
After:

	taskA->se.parent = guest's tg->se[1]
So walking up the entity hierarchy and fixing up (parent)se->vruntime will do

little good after the task has moved to a new cpu.
IMO, we need to be doing this :
	- For dequeue of higher level sched entities, simulate as if

	  they are going to "sleep"

	- For enqueue of higher level entities, simulate as if they are

	  "waking up". This will cause enqueue_entity() to reset their

	  vruntime (to existing value for cfs_rq->min_vruntime) when they

	  "wakeup".
If we don't do this, then lets say a group had only one task (A) and it

moves from CPU0 to CPU1. Then on CPU1, when group level entity for task

A is enqueued, it will have a very low vruntime (since it was never

running) and this will give task A unlimited cpu time, until its group

entity catches up with all the "sleep" time.
Let me try a fix for this next ..
--

Regards,

vatsa

-

Yes.  Very VERY nice feel.
	-Mike
-

cool :-)
Maybe there's more to come: if we can get CONFIG_FAIR_USER_SCHED to work

properly then your Xorg will have a load-independent 50% of CPU time all

to itself. (Group scheduling is quite impressive already: i can log in

as root without feeling _any_ effect from a perpetual 'hackbench 100'

running as uid mingo. Fork bombs no more.) Will the Amarok gforce plugin

like that CPU time splitup? (or is most of the gforce overhead under

your user uid?)
it could also work out negatively, _sometimes_ X does not like being too

high prio. (weird as that might be.) So we'll see.
	Ingo

-

It seems that perhaps that 50% makes more sense on a single/dual CPU

system than on a more robust one, such as a four way dual core Xeon with

HT or some such. With hotplug CPUs, and setups on various machines,

perhaps some resource limit independent of the available resource would

be useful.
Just throwing out the idea, in case it lands on fertile ground.
--

Bill Davidsen <davidsen@tmr.com>

   "We have more to fear from the bungling of the incompetent than from

the machinations of the wicked."  - from Slashdot

-

I piddled around with fair users this morning, and it worked well.  With

Xorg and Gforce as one user (X and Gforce are synchronous ATM), and a

make -j30 as another, I could barely tell the make was running.

Watching a dvd, I couldn't tell. Latencies were pretty darn good

throughout three hours of testing this and that.
	-Mike
-

I run everything as root (naughty me), so I'd have to change my evil

ways to reap the benefits.  (I'll do that to test, but it's unlikely to

ever become a permanent habit here)  Amarok/Gforce will definitely like

the user split as long as latency is low.  Visualizations are not only

bandwidth hungry, they're extremely latency sensitive.
	-Mike
-

Mike,

	Do you have FAIR_USER_SCHED turned on as well? Can you send me

your .config pls?
--

Regards,

vatsa

-

I did have.  gzipped config attached.. this is current though, after

disabling groups.  I'm still beating on the basic changes (boy does it

ever feel nice [awaits other shoe]).
	-Mike

These busy loops - are they spawned by the same user? Is it the root

user? Also is this seen in UP mode also?
Can you also pls check if tuning root user's cpu share helps? Basically,
	# echo 4096 > /proc/root_user_share
Ok ..I see that it is in /proc/sched_debug.
--

Regards,

vatsa

-

I'll try these after I beat on the box some more.
	-Mike
-

Does this have anything to do with idle balancing ? I noticed some

fairly large latencies in that code in 2.6.23-rc's ..
Daniel
-

any measurements?
	Ingo

-

Yes, I made this a while ago,
ftp://source.mvista.com/pub/dwalker/misc/long-cfs-load-balance-trace.txt
This was with PREEMPT_RT on btw, so it's not the most recent kernel. I

was able to reproduce it in all the -rc's I tried.
Daniel
-

On Mon, 24 Sep 2007 23:45:37 +0200
I'm pulling linux-2.6-sched.git, and it's oopsing all over the place on

ia64, and Lee's observations about set_leftmost()'s weirdness are

pertinent.
Should I instead be pulling linux-2.6-sched-devel.git?
-

yeah, please pull that one.
linux-2.6-sched.git by mistake contained an older sched-devel tree for

about a day (where your scripts picked it up). I've restored that one to

-rc7 meanwhile. It's only supposed to contain strict fixes for upstream.

(none at the moment)
	Ingo

-