[PATCH] Avoid moving tasks when a schedule can be made.

[PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

I found this in the -rt kernel.  While running "hackbench 20" I hit
latencies of over 1.5 ms.  That is huge!  This latency was created by
the move_tasks function in sched.c to rebalance the queues over CPUS.  

There currently isn't any check in this function to see if it should
stop, thus a large number of tasks can drive the latency high.

With the below patch, (tested on -rt with latency tracing), the latency
caused by hackbench disappeared below my notice threshold (100 usecs).

I'm not convinced that this bail out is in the right location, but it
worked where it is.  Comments are welcome.

-- Steve

Signed-off-by: Steven Rostedt <rostedt@goodmis.org>

Index: linux-2.6.16-rc1/kernel/sched.c
===================================================================
--- linux-2.6.16-rc1.orig/kernel/sched.c	2006-01-19 15:58:52.000000000 -0500
+++ linux-2.6.16-rc1/kernel/sched.c	2006-01-31 14:27:17.000000000 -0500
@@ -1983,6 +1983,10 @@
 
 	curr = curr->prev;
 
+	/* bail if someone else woke up */
+	if (need_resched())
+		goto out;
+
 	if (!can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
 		if (curr != head)
 			goto skip_queue;

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Peter Williams]

Steven Rostedt wrote:
> I found this in the -rt kernel.  While running "hackbench 20" I hit
> latencies of over 1.5 ms.  That is huge!  This latency was created by
> the move_tasks function in sched.c to rebalance the queues over CPUS.  
> 
> There currently isn't any check in this function to see if it should
> stop, thus a large number of tasks can drive the latency high.
> 
> With the below patch, (tested on -rt with latency tracing), the latency
> caused by hackbench disappeared below my notice threshold (100 usecs).
> 
> I'm not convinced that this bail out is in the right location, but it
> worked where it is.  Comments are welcome.
> 
> -- Steve
> 
> Signed-off-by: Steven Rostedt <rostedt@goodmis.org>
> 
> Index: linux-2.6.16-rc1/kernel/sched.c
> ===================================================================
> --- linux-2.6.16-rc1.orig/kernel/sched.c	2006-01-19 15:58:52.000000000 -0500
> +++ linux-2.6.16-rc1/kernel/sched.c	2006-01-31 14:27:17.000000000 -0500
> @@ -1983,6 +1983,10 @@
>  
>  	curr = curr->prev;
>  
> +	/* bail if someone else woke up */
> +	if (need_resched())
> +		goto out;
> +
>  	if (!can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
>  		if (curr != head)
>  			goto skip_queue;
> 

I presume that the intention here is to allow a newly woken task that 
preempts the current task to stop the load balancing?

As I see it (and I may be wrong), for this to happen, the task must have 
woken before the run queue locks were taken (otherwise it wouldn't have 
got as far as activation) i.e. before move_tasks() is called and 
therefore you may as well just do this check at the start of move_tasks().

However, a newly woken task that preempts the current task isn't the 
only way that needs_resched() can become true just before load balancing 
is started.  E.g. scheduler_tick() calls set_tsk_need_resched(p) when a 
task finishes a time slice and this patch would cause rebalance_tick() 
to be aborted after a lot of work has been done in this case.

In summary, I think that the bail out is badly placed and needs some way 
of knowing if the reason need_resched() has become true is because of 
preemption of a newly woken task and not some other reason.

Peter
PS I've added Nick Piggin to the CC list as he is interested in load 
balancing issues.
-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

On Wed, 2006-02-01 at 14:36 +1100, Peter Williams wrote:
> Steven Rostedt wrote:
> > I found this in the -rt kernel.  While running "hackbench 20" I hit
> > latencies of over 1.5 ms.  That is huge!  This latency was created by
> > the move_tasks function in sched.c to rebalance the queues over CPUS.  
> > 
> > There currently isn't any check in this function to see if it should
> > stop, thus a large number of tasks can drive the latency high.
> > 
> > With the below patch, (tested on -rt with latency tracing), the latency
> > caused by hackbench disappeared below my notice threshold (100 usecs).
> > 
> > I'm not convinced that this bail out is in the right location, but it
> > worked where it is.  Comments are welcome.
> > 

> 
> I presume that the intention here is to allow a newly woken task that 
> preempts the current task to stop the load balancing?
> 
> As I see it (and I may be wrong), for this to happen, the task must have 
> woken before the run queue locks were taken (otherwise it wouldn't have 
> got as far as activation) i.e. before move_tasks() is called and 
> therefore you may as well just do this check at the start of move_tasks().

Actually, one of the tasks that was moved might need to resched right
away, since it preempts the current task that is doing the moving.

> 
> However, a newly woken task that preempts the current task isn't the 
> only way that needs_resched() can become true just before load balancing 
> is started.  E.g. scheduler_tick() calls set_tsk_need_resched(p) when a 
> task finishes a time slice and this patch would cause rebalance_tick() 
> to be aborted after a lot of work has been done in this case.

No real work is lost.  This is a loop that individually pulls tasks.  So
the bail only stops the work of looking for more tasks to pull and we
don't lose the tasks that have already been pulled.

> 
> In summary, I think that the bail out is badly placed and needs some way 
> of knowing if the reason need_resched() has become true is because of 
> preemption of a newly woken task and not some other reason.

I need that bail in the loop, so it can stop if needed. Like I said, it
can be a task that is pulled to cause the bail. Also, having the run
queue locks and interrupts off for over a msec is really a bad idea.

> 
> Peter
> PS I've added Nick Piggin to the CC list as he is interested in load 
> balancing issues.

Thanks, and thanks for the comments too.  I'm up for all suggestions and
ideas.  I just feel it is important that we don't have unbounded
latencies of spin locks and interrupts off.

-- Steve

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Steven Rostedt wrote:
> On Wed, 2006-02-01 at 14:36 +1100, Peter Williams wrote:

>>However, a newly woken task that preempts the current task isn't the 
>>only way that needs_resched() can become true just before load balancing 
>>is started.  E.g. scheduler_tick() calls set_tsk_need_resched(p) when a 
>>task finishes a time slice and this patch would cause rebalance_tick() 
>>to be aborted after a lot of work has been done in this case.
> 
> 
> No real work is lost.  This is a loop that individually pulls tasks.  So
> the bail only stops the work of looking for more tasks to pull and we
> don't lose the tasks that have already been pulled.
> 
> 

Once we've gone to the trouble of deciding which tasks to move and how
many (and the estimate should be very conservative), and locked the source
and destination runqueues, it is a very good idea to follow up with our
threat of actually moving the tasks rather than bail out early.

It is quite likely (though perhaps less so in this braindead benchmark)
that a subsequent load balance operation will need to move the remaining
tasks anyway, so decreasing the efficiency of this routine is going to cause
more damage to your RT task even if you "fix" it to not actually show up as
a single latency blip.

>>In summary, I think that the bail out is badly placed and needs some way 
>>of knowing if the reason need_resched() has become true is because of 
>>preemption of a newly woken task and not some other reason.
> 
> 
> I need that bail in the loop, so it can stop if needed. Like I said, it
> can be a task that is pulled to cause the bail. Also, having the run
> queue locks and interrupts off for over a msec is really a bad idea.
> 

I don't think we need to change it in the mainline kernel just yet. At least
not something that will bail after moving just a single task every time in
the worst case.

> 
>>Peter
>>PS I've added Nick Piggin to the CC list as he is interested in load 
>>balancing issues.
> 
> 
> Thanks, and thanks for the comments too.  I'm up for all suggestions and
> ideas.  I just feel it is important that we don't have unbounded
> latencies of spin locks and interrupts off.
> 

That's a long way off (if ever) if you want to run crazy code that simply
increases some resource loading until something breaks. Take an rwsem for
writing and then queue up thousands of readers on the lock. Release the
writer. (this will be very similar to run queue balancing, in effect).

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Steven Rostedt <rostedt@goodmis.org> wrote:

[pls. use -p when generating patches]

> @@ -1983,6 +1983,10 @@
>  
>  	curr = curr->prev;
>  
> +	/* bail if someone else woke up */
> +	if (need_resched())
> +		goto out;
> +
>  	if (!can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
>  		if (curr != head)
>  			goto skip_queue;

even putting the problems of this approach aside (is it right to abort 
the act of load-balancing - which is a periodic activity that wont be 
restarted after this - so we lose real work), i think this will not 
solve the latency. Imagine a hardirq hitting the CPU that is executing 
move_tasks() above. We might not service that hardirq for up to 1.5 
msecs ...

i think the right approach would be to split up this work into smaller 
chunks. Or rather, lets first see how this can happen: why is 
can_migrate() false for so many tasks? Are they all cpu-hot? If yes, 
shouldnt we simply skip only up to a limit of tasks in this case - it's 
not like we want to spend 1.5 msecs searching for a cache-cold task 
which might give us a 50 usecs advantage over cache-hot tasks ...

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Nick Piggin wrote:
> Steven Rostedt wrote:
> 
>>
>> No real work is lost.  This is a loop that individually pulls tasks.  So
>> the bail only stops the work of looking for more tasks to pull and we
>> don't lose the tasks that have already been pulled.
>>
>>
> 
> Once we've gone to the trouble of deciding which tasks to move and how
> many (and the estimate should be very conservative), and locked the source
> and destination runqueues, it is a very good idea to follow up with our
> threat of actually moving the tasks rather than bail out early.
> 

Oh, I forgot: Ingo once introduced some code to bail early (though for
different reasons and under different conditions), and this actually
was found to cause significant regressions in some database workloads.
So it is not a nice thing to tinker with unless there is good reason.

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Ingo Molnar <mingo@elte.hu> wrote:

> i think the right approach would be to split up this work into smaller 
> chunks. Or rather, lets first see how this can happen: why is 
> can_migrate() false for so many tasks? Are they all cpu-hot? If yes, 
> shouldnt we simply skip only up to a limit of tasks in this case - 
> it's not like we want to spend 1.5 msecs searching for a cache-cold 
> task which might give us a 50 usecs advantage over cache-hot tasks ...

the only legimate case where we have to skip alot of tasks is the case 
when there are alot of CPU-bound (->cpus_alowed) tasks in the runqueue.  
In that case the scheduler really has to skip that task. But that is not 
an issue in your workload.

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

On Wed, 2006-02-01 at 14:08 +0100, Ingo Molnar wrote:
> * Steven Rostedt <rostedt@goodmis.org> wrote:
> 
> [pls. use -p when generating patches]
> 
> > @@ -1983,6 +1983,10 @@
> >  
> >  	curr = curr->prev;
> >  
> > +	/* bail if someone else woke up */
> > +	if (need_resched())
> > +		goto out;
> > +
> >  	if (!can_migrate_task(tmp, busiest, this_cpu, sd, idle, &pinned)) {
> >  		if (curr != head)
> >  			goto skip_queue;
> 
> even putting the problems of this approach aside (is it right to abort 
> the act of load-balancing - which is a periodic activity that wont be 
> restarted after this - so we lose real work), i think this will not 
> solve the latency. Imagine a hardirq hitting the CPU that is executing 
> move_tasks() above. We might not service that hardirq for up to 1.5 
> msecs ...
> 
> i think the right approach would be to split up this work into smaller 
> chunks. Or rather, lets first see how this can happen: why is 
> can_migrate() false for so many tasks? Are they all cpu-hot? If yes, 
> shouldnt we simply skip only up to a limit of tasks in this case - it's 
> not like we want to spend 1.5 msecs searching for a cache-cold task 
> which might give us a 50 usecs advantage over cache-hot tasks ...
> 

OK, agreed.

Just to clear things up.  I looked further into what was causing this,
and the can_migrate was indeed true, and it just happened that we got a
large imbalance, and it pulled a few hundred tasks.  So, my earlier
analysis was incorrect about the can_migrate being false.

-- Steve

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> >Once we've gone to the trouble of deciding which tasks to move and how
> >many (and the estimate should be very conservative), and locked the source
> >and destination runqueues, it is a very good idea to follow up with our
> >threat of actually moving the tasks rather than bail out early.
> 
> Oh, I forgot: Ingo once introduced some code to bail early (though for 
> different reasons and under different conditions), and this actually 
> was found to cause significant regressions in some database workloads.

well, we both did changes with that effect - pretty much any change in 
this area can cause a regression on _some_ workload ;) So there wont be 
any silver bullet.

> So it is not a nice thing to tinker with unless there is good reason.

unbound latencies with hardirqs off are obviously a good reason - but i 
agree that the solution is not good enough, yet.

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

On Wed, 2006-02-01 at 14:08 +0100, Ingo Molnar wrote:
> * Steven Rostedt <rostedt@goodmis.org> wrote:
> 
> [pls. use -p when generating patches]
> 

OK, how do you make quilt do that?

Thanks,

-- Steve

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Steven Rostedt <rostedt@goodmis.org> wrote:

> On Wed, 2006-02-01 at 14:08 +0100, Ingo Molnar wrote:
> > * Steven Rostedt <rostedt@goodmis.org> wrote:
> > 
> > [pls. use -p when generating patches]
> > 
> 
> OK, how do you make quilt do that?

hm, i'm using 0.42, and this command:

  #!/bin/bash

  quilt refresh --diffstat --sort --no-timestamps -p 1 $@

does the -p thing automatically. (the -p option to quilt is for the 
patch-file-depth, not for the function-name thing.)

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:

>>Oh, I forgot: Ingo once introduced some code to bail early (though for 
>>different reasons and under different conditions), and this actually 
>>was found to cause significant regressions in some database workloads.
> 
> 
> well, we both did changes with that effect - pretty much any change in 
> this area can cause a regression on _some_ workload ;) So there wont be 
> any silver bullet.
> 

Well yes. Although specifically the bail-out-early stuff which IIRC
you did... I wasn't singling you out in particular, I've broken the
scheduler at _least_ as much as you have since starting work on it ;)

> 
>>So it is not a nice thing to tinker with unless there is good reason.
> 
> 
> unbound latencies with hardirqs off are obviously a good reason - but i 
> agree that the solution is not good enough, yet.
> 

Ah, so this is an RT tree thing where the scheduler lock turns off "hard
irqs"? As opposed to something like the rwsem lock that only turns off
your "soft irqs" (sorry, I'm not with the terminlogy)?

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Nick Piggin wrote:
> Ingo Molnar wrote:
> 
>> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> 
>>> Oh, I forgot: Ingo once introduced some code to bail early (though 
>>> for different reasons and under different conditions), and this 
>>> actually was found to cause significant regressions in some database 
>>> workloads.
>>
>>
>>
>> well, we both did changes with that effect - pretty much any change in 
>> this area can cause a regression on _some_ workload ;) So there wont 
>> be any silver bullet.
>>
> 
> Well yes. Although specifically the bail-out-early stuff which IIRC
> you did... I wasn't singling you out in particular, I've broken the
> scheduler at _least_ as much as you have since starting work on it ;)
> 

... and my point is that there is not much reason to introduce a
possible performance regression because of such a latency in an
artificial test case, especially when there are other sources of
unbound latency when dealing with large numbers of tasks (and on
uniprocessor too, eg. rwsem).

However, as an RT-tree thing obviously I have no problems with it,
but unless your interrupt thread is preemptible, then there isn't
much point because it can cause a similar latency (that your tools
won't detect) simply by running multiple times.

You really want isolcpus on SMP machines to really ensure load
balancing doesn't harm RT behaviour, yeah?

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> >>So it is not a nice thing to tinker with unless there is good reason.
> >
> >unbound latencies with hardirqs off are obviously a good reason - but i 
> >agree that the solution is not good enough, yet.
> 
> Ah, so this is an RT tree thing where the scheduler lock turns off 
> "hard irqs"? [...]

no, this is about the mainline kernel turning off hardirqs for a long 
time. (i used the hardirqs-off terminology instead of irqs-off to 
differentiate it from softirqs-off a'ka local_bh_disable(). It's a 
side-effect of working on the lock validator i guess ;).

> [...] As opposed to something like the rwsem lock that only turns off 
> your "soft irqs" (sorry, I'm not with the terminlogy)?

rwsems/rwlocks are not an issue in -rt because they have different 
semantics there - and thus readers cannot amass. I do think rwsems and 
rwlocks have pretty nasty characteristics [non-latency ones] for the 
mainline kernel's use too, but that's not being argued here ;)

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> 
>>>>So it is not a nice thing to tinker with unless there is good reason.
>>>
>>>unbound latencies with hardirqs off are obviously a good reason - but i 
>>>agree that the solution is not good enough, yet.
>>
>>Ah, so this is an RT tree thing where the scheduler lock turns off 
>>"hard irqs"? [...]
> 
> 
> no, this is about the mainline kernel turning off hardirqs for a long 
> time. (i used the hardirqs-off terminology instead of irqs-off to 
> differentiate it from softirqs-off a'ka local_bh_disable(). It's a 
> side-effect of working on the lock validator i guess ;).
> 

OK.

> 
>>[...] As opposed to something like the rwsem lock that only turns off 
>>your "soft irqs" (sorry, I'm not with the terminlogy)?
> 
> 
> rwsems/rwlocks are not an issue in -rt because they have different 
> semantics there - and thus readers cannot amass. I do think rwsems and 
> rwlocks have pretty nasty characteristics [non-latency ones] for the 
> mainline kernel's use too, but that's not being argued here ;)
> 

But all I'm saying is that while there are equivalent magnitudes of
interrupts off regions in mainline, there is little point introducing
a hack like this to "solve" one of them.

Sure, rework one of them nicely to solve the issue for that case, or
hack _all_ of them (not for mainline but for your specific RT system).
But hacking just one does not make any sense.

Just because this one path actually _triggered_ due to a silly
benchmark doesn't make it any more valid. I think it shouldn't be too
hard to cause similar or worse latencies with the mmap_sem rwsem using
the same number of threads.

If anyone is running hackbench 20 on their sound mixer, then they
deserve to have overruns.

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> ... and my point is that there is not much reason to introduce a 
> possible performance regression because of such a latency in an 
> artificial test case, especially when there are other sources of 
> unbound latency when dealing with large numbers of tasks (and on 
> uniprocessor too, eg. rwsem).
> 
> However, as an RT-tree thing obviously I have no problems with it, but 
> unless your interrupt thread is preemptible, then there isn't much 
> point because it can cause a similar latency (that your tools won't 
> detect) simply by running multiple times.

we can (and do) detect any type of latency. E.g. there's the 
CONFIG_LPPTEST feature in the -rt kernel, which allows me to inject 
50,000 hardirqs per second from another box, over a parallel port, and 
allows me to validate the worst-case IRQ response time from that 
external box. The 'external' component of LPPTEST injects the interrupt 
with interrupts disabled, and polls for the response, and does all 
measurements on that other box. I can use that in conjunction with the 
latency tracer running on the measured box, to get an easy snapshot of 
the longest hardirq latency path.

to answer your question: yes, all hardware interrupt handlers [except a 
very slim shim that blocks the irq source and wakes up the interrupt 
thread] are fully preemptible in the -rt kernel too. I.e. all the IDE 
irq handlers, all the networking handlers, all the irq codepath that 
usually runs with irqs off, runs fully preemptible in the -rt kernel.

so when we say the -rt kernel has a 20 usecs worst-case scheduling 
latency on a fast box, while running arbitrary SCHED_OTHER workloads 
(including heavy networking, heavy swapping/VM and IO work, using 
thousands of tasks) it really means we measured it using robust methods.

> You really want isolcpus on SMP machines to really ensure load 
> balancing doesn't harm RT behaviour, yeah?

not really - isolcpus is useful for certain problems, but it is not 
generic as it puts heavy constraints on usability and resource 
utilization. We have really, really good latencies on SMP too in the -rt 
kernel, with _arbitrary_ SCHED_OTHER workloads. Rwsems and rwlocks are 
not an issue, pretty much the only issue is the scheduler's 
load-balancing.

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> >rwsems/rwlocks are not an issue in -rt because they have different 
> >semantics there - and thus readers cannot amass. I do think rwsems and 
> >rwlocks have pretty nasty characteristics [non-latency ones] for the 
> >mainline kernel's use too, but that's not being argued here ;)
> 
> But all I'm saying is that while there are equivalent magnitudes of 
> interrupts off regions in mainline, there is little point introducing 
> a hack like this to "solve" one of them.

nobody is arguing to have this hack included. Hacks are to be introduced 
into the scheduler only over my cold dead body ;-) Steve only sent this 
as an RFC thing, to raise the issue.

> If anyone is running hackbench 20 on their sound mixer, then they 
> deserve to have overruns.

just to give you an idea of what we have achieved with the -rt kernel so 
far: my regular -rt stress-test setup has a "hackbench 50" in its 
"deadly mix of SCHED_OTHER workloads", in addition to 40 parallel runs 
of LTP runalltests.sh, with flood pinging and other networking and IO 
stresstests, combined with a task that allocates and dirties a 1.5GB 
buffer in an infinite loop while there's only 1GB of RAM - and still 
during many hours of running this stress-test (which produces a load 
average of 200-500) the -rt kernel runs SCHED_FIFO tasks in 20 usecs, 
worst-case.

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 

>>However, as an RT-tree thing obviously I have no problems with it, but 
>>unless your interrupt thread is preemptible, then there isn't much 
>>point because it can cause a similar latency (that your tools won't 
>>detect) simply by running multiple times.
> 
> 
> we can (and do) detect any type of latency. E.g. there's the 
> CONFIG_LPPTEST feature in the -rt kernel, which allows me to inject 
> 50,000 hardirqs per second from another box, over a parallel port, and 
> allows me to validate the worst-case IRQ response time from that 
> external box. The 'external' component of LPPTEST injects the interrupt 
> with interrupts disabled, and polls for the response, and does all 
> measurements on that other box. I can use that in conjunction with the 
> latency tracer running on the measured box, to get an easy snapshot of 
> the longest hardirq latency path.
> 

What I am talking about is when you want a task to have the highest
possible scheduling priority and you'd like to guarantee that it is
not interrupted for more than Xus, including scheduling latency.

Presumably this is your classic RT control type application.

Now in your kernel you can measure a single long interrupt time, but
if you "break" that latency by splitting it into two interrupts, the
end result will be the same if not worse due to decreased efficiency.

This is what I was talking about. But that's going off topic...

>>You really want isolcpus on SMP machines to really ensure load 
>>balancing doesn't harm RT behaviour, yeah?
> 
> 
> not really - isolcpus is useful for certain problems, but it is not 
> generic as it puts heavy constraints on usability and resource 
> utilization. We have really, really good latencies on SMP too in the -rt 
> kernel, with _arbitrary_ SCHED_OTHER workloads. Rwsems and rwlocks are 
> not an issue, pretty much the only issue is the scheduler's 
> load-balancing.
> 

Then it is a fine hack for the RT kernel (or at least an improved,
batched version of the patch). No arguments from me.

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

On Wed, 2006-02-01 at 15:22 +0100, Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> > >rwsems/rwlocks are not an issue in -rt because they have different 
> > >semantics there - and thus readers cannot amass. I do think rwsems and 
> > >rwlocks have pretty nasty characteristics [non-latency ones] for the 
> > >mainline kernel's use too, but that's not being argued here ;)
> > 
> > But all I'm saying is that while there are equivalent magnitudes of 
> > interrupts off regions in mainline, there is little point introducing 
> > a hack like this to "solve" one of them.
> 
> nobody is arguing to have this hack included. Hacks are to be introduced 
> into the scheduler only over my cold dead body ;-) Steve only sent this 
> as an RFC thing, to raise the issue.

I'll confirm this. Even in my submission, I stated that this was
probably wrong, and wanted comments (thank you btw for commenting :).  I
just wanted to show where the problem was, and that the problem went
away with the "hack".

-- Steve

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> What I am talking about is when you want a task to have the highest 
> possible scheduling priority and you'd like to guarantee that it is 
> not interrupted for more than Xus, including scheduling latency.

this is not a big issue in practice, because it's very hard to saturate 
current x86 systems running the -rt kernel with pure IRQ load. The APIC 
messages all have a natural latency, which serves as a throttler.

[ Pretty much the only way i know to lock up a box via hardirq load is
  to misprogram the local APIC timer IRQ. (but we have protection
  against that in the HRT code, and the same is not possible via
  external interrupts.) ]

in case this becomes a problem (on some other platforms) we have a 
solution for it: interrupt prioritiziation. We didnt want to complicate 
things with this in the current IRQ preemption model, but it's all 
pretty straightforward to do.

> Now in your kernel you can measure a single long interrupt time, but 
> if you "break" that latency by splitting it into two interrupts, the 
> end result will be the same if not worse due to decreased efficiency.

there really is a maximum rate of interrupts you can inject, which has 
an effect of slowing down the CPU, which has a linear effect on the 
worst-case latency - but not not some other drastic effect.

> >not really - isolcpus is useful for certain problems, but it is not 
> >generic as it puts heavy constraints on usability and resource 
> >utilization. We have really, really good latencies on SMP too in the -rt 
> >kernel, with _arbitrary_ SCHED_OTHER workloads. Rwsems and rwlocks are 
> >not an issue, pretty much the only issue is the scheduler's 
> >load-balancing.
> 
> Then it is a fine hack for the RT kernel (or at least an improved, 
> batched version of the patch). No arguments from me.

no, it is also fine for the mainline scheduler, as long as the patch is 
clean and does the obviously right thing [which the current patch doesnt 
offer]. A 1+ msec latency with irqs off is nothing to sniff at. Trying 
to argue that 'you can get the same by using rwsems so why should we 
bother' is pretty lame: rwsems are rare and arguably broken in behavior, 
and i'd not say the same about the scheduler (just yet :-).

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> 
>>What I am talking about is when you want a task to have the highest 
>>possible scheduling priority and you'd like to guarantee that it is 
>>not interrupted for more than Xus, including scheduling latency.
> 
> 
> this is not a big issue in practice, because it's very hard to saturate 
> current x86 systems running the -rt kernel with pure IRQ load. The APIC 
> messages all have a natural latency, which serves as a throttler.
> 

Either way, you don't measure it. Doesn't matter. As I said, off topic.

>>
>>Then it is a fine hack for the RT kernel (or at least an improved, 
>>batched version of the patch). No arguments from me.
> 
> 
> no, it is also fine for the mainline scheduler, as long as the patch is 
> clean and does the obviously right thing [which the current patch doesnt 
> offer]. A 1+ msec latency with irqs off is nothing to sniff at. Trying 

If it were generated by some real workload that cares, then I would care.

> to argue that 'you can get the same by using rwsems so why should we 
> bother' is pretty lame: rwsems are rare and arguably broken in behavior, 
> and i'd not say the same about the scheduler (just yet :-).
> 

I don't think it is lame at all. They're fairly important in use in mmap_sem
that I know of. And I have seen workloads where the up_write path gets really
expensive (arguably more relevant ones than hackbench).

PS. I'd like to see you argue how they're broken in behaviour, and how
you're going to replace mmap_sem -- this is not a rhetorical statement,
I'd really be interested to see ;)

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> Ingo Molnar wrote:
> >* Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> >
> >
> >>What I am talking about is when you want a task to have the highest 
> >>possible scheduling priority and you'd like to guarantee that it is 
> >>not interrupted for more than Xus, including scheduling latency.
> >
> >
> >this is not a big issue in practice, because it's very hard to saturate 
> >current x86 systems running the -rt kernel with pure IRQ load. The APIC 
> >messages all have a natural latency, which serves as a throttler.
> >
> 
> Either way, you don't measure it. Doesn't matter. As I said, off 
> topic.

(sure we are measuring such effects too - our current worst-case latency 
paths are related to two-irqs-after-each-other scenarios.)

> >>
> >>Then it is a fine hack for the RT kernel (or at least an improved, 
> >>batched version of the patch). No arguments from me.
> >
> >
> >no, it is also fine for the mainline scheduler, as long as the patch is 
> >clean and does the obviously right thing [which the current patch doesnt 
> >offer]. A 1+ msec latency with irqs off is nothing to sniff at. Trying 
> 
> If it were generated by some real workload that cares, then I would care.

well, you might not care, but i do. It's up to you what you care about, 
but right now the scheduler policy is that we do care about latencies.  
Yes, it's obviously all subject to common sense, and if something 
triggers in a rare and extreme workload then any change related to it 
has a _much_ higher barrier of acceptance than a common codepath. But
your blanket dismissal of this whole subject based on the rarity of the
workload is just plain wrong.

> >to argue that 'you can get the same by using rwsems so why should we 
> >bother' is pretty lame: rwsems are rare and arguably broken in 
> >behavior, and i'd not say the same about the scheduler (just yet :-).
> 
> I don't think it is lame at all. They're fairly important in use in 
> mmap_sem that I know of. And I have seen workloads where the up_write 
> path gets really expensive (arguably more relevant ones than 
> hackbench).

they are broken e.g. in that they are mass-waking all the readers with 
interrupts disabled. At a minimum rwsems should be declared irq-unsafe 
(like mutexes), as all the substantial uses are in process-context 
codepaths anyway. I'll revisit rwsems once the current mutex work is 
done.

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:

>>If it were generated by some real workload that cares, then I would care.
> 
> 
> well, you might not care, but i do. It's up to you what you care about, 
> but right now the scheduler policy is that we do care about latencies.  
> Yes, it's obviously all subject to common sense, and if something 
> triggers in a rare and extreme workload then any change related to it 
> has a _much_ higher barrier of acceptance than a common codepath. But
> your blanket dismissal of this whole subject based on the rarity of the
> workload is just plain wrong.
> 

No, if you read what I'd been saying, I'm not dismissing the whole
subject based on the workload. I'm saying that there is no point to
include such a "fix" based on the numbers given by this workload (if
there is a more meaningful one, then sure). Especially not while
there are sources of equivalent latency.

It is really simple: I can find a code path in the kernel, and work
out how to exploit it by increasing resource loading until it goes
bang (another example, tasklist_lock).

This is not really a justification for trying to "fix" it.

Unless somewhere there was an agreement that 1.5ms interrupt latency
was a bug, full stop.

> 
>>>to argue that 'you can get the same by using rwsems so why should we 
>>>bother' is pretty lame: rwsems are rare and arguably broken in 
>>>behavior, and i'd not say the same about the scheduler (just yet :-).
>>
>>I don't think it is lame at all. They're fairly important in use in 
>>mmap_sem that I know of. And I have seen workloads where the up_write 
>>path gets really expensive (arguably more relevant ones than 
>>hackbench).
> 
> 
> they are broken e.g. in that they are mass-waking all the readers with 
> interrupts disabled. At a minimum rwsems should be declared irq-unsafe 
> (like mutexes), as all the substantial uses are in process-context 
> codepaths anyway. I'll revisit rwsems once the current mutex work is 
> done.
> 

That would be great. Actually I have some patches that move the actual
waking of the tasks out from underneath the lock too which gave some
scalability benefits (and I'd imagine far less interrupt-off time, so
let me know when you start work on rwsems).

But there are still places where interrupts can be held off for
indefinite periods. I don't see why the scheduler lock is suddenly
important - I could have told you years ago what would happen if you
trigger the load balancer with enough tasks.

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> Ingo Molnar wrote:
> >* Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> >>If it were generated by some real workload that cares, then I would care.
> >
> >
> >well, you might not care, but i do. It's up to you what you care about, 
> >but right now the scheduler policy is that we do care about latencies.  
> >Yes, it's obviously all subject to common sense, and if something 
> >triggers in a rare and extreme workload then any change related to it 
> >has a _much_ higher barrier of acceptance than a common codepath. But
> >your blanket dismissal of this whole subject based on the rarity of the
> >workload is just plain wrong.
> >
> 
> No, if you read what I'd been saying, I'm not dismissing the whole 
> subject based on the workload. I'm saying that there is no point to 
> include such a "fix" based on the numbers given by this workload (if 
> there is a more meaningful one, then sure). Especially not while there 
> are sources of equivalent latency.

firstly, you are ignoring the fact that Steve never submitted this for 
actual inclusion. His very first email stated:

  "I'm not convinced that this bail out is in the right location, but 
   it worked where it is.  Comments are welcome."

so i'm not sure why you are still pounding upon his patch and suggesting 
that any solution to this problem is to be limited to the -rt kernel and 
suggesting that the mainline kernel should not care. Yes, the mainline 
kernel does care. We might not apply anything resulting out of this 
(because this is a tricky piece of code), but we do care very much. 
Indifference really does not help.

secondly,

> It is really simple: I can find a code path in the kernel, and work 
> out how to exploit it by increasing resource loading until it goes 
> bang (another example, tasklist_lock).

we are busy fixing tasklist_lock latencies too. The point you are still 
trying to make, that the scheduler should not be touched just because 
there are other problem areas with unbound latencies, is still plain 
illogical.

> But there are still places where interrupts can be held off for 
> indefinite periods. I don't see why the scheduler lock is suddenly 
> important [...]

the scheduler lock is obviously important because it's the most central 
lock in existence.

> [...] I could have told you years ago what would happen if you trigger 
> the load balancer with enough tasks.

i very well know what move_tasks() can do. There used to be other ways 
to provoke unbound latencies in the scheduler - e.g.  via pinned tasks, 
for which we introduced the all_pinned hack. The all_pinned hack was 
needed because the worst-case behavior was getting so bad on some larger 
boxes under larger loads that it totally DoSed the system. So it's not 
at all unprecedented for us to care about boundary behavior in the 
scheduler, nor are we as shy about aborting load-balancing decisions as 
you are suggesting, it just all depends on the circumstances and on the 
quality of the patch.

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

On Wed, 2006-02-01 at 14:26 +0100, Ingo Molnar wrote:
> * Steven Rostedt <rostedt@goodmis.org> wrote:
> 
> > On Wed, 2006-02-01 at 14:08 +0100, Ingo Molnar wrote:
> > > * Steven Rostedt <rostedt@goodmis.org> wrote:
> > > 
> > > [pls. use -p when generating patches]
> > > 
> > 
> > OK, how do you make quilt do that?
> 
> hm, i'm using 0.42, and this command:
> 
>   #!/bin/bash
> 
>   quilt refresh --diffstat --sort --no-timestamps -p 1 $@
> 
> does the -p thing automatically. (the -p option to quilt is for the 
> patch-file-depth, not for the function-name thing.)

Found it.  Do you have QUILT_DIFF_OPTS set as an environment variable?
If I do the following:

QUILT_DIFF_OPTS='-p' quilt refresh

It works.

I guess I'll add that to my .bash_profile.

Thanks,

-- Steve

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> 
>>Ingo Molnar wrote:
>>

>>No, if you read what I'd been saying, I'm not dismissing the whole 
>>subject based on the workload. I'm saying that there is no point to 
>>include such a "fix" based on the numbers given by this workload (if 
>>there is a more meaningful one, then sure). Especially not while there 
>>are sources of equivalent latency.
> 
> 
> firstly, you are ignoring the fact that Steve never submitted this for 
> actual inclusion. His very first email stated:
> 

You keep saying this. I'm talking about the general concept of
"avoid moving tasks when a schedule can be made", or some way to
reduce latencies in move_tasks. Obviously we are long past the fact
that this particular patch isn't the best implementation.

>   "I'm not convinced that this bail out is in the right location, but 
>    it worked where it is.  Comments are welcome."
> 
> so i'm not sure why you are still pounding upon his patch and suggesting 
> that any solution to this problem is to be limited to the -rt kernel and 

Err, I'm not.

>>It is really simple: I can find a code path in the kernel, and work 
>>out how to exploit it by increasing resource loading until it goes 
>>bang (another example, tasklist_lock).
> 
> 
> we are busy fixing tasklist_lock latencies too. The point you are still 
> trying to make, that the scheduler should not be touched just because 
> there are other problem areas with unbound latencies, is still plain 
> illogical.
> 

Actually my main argument is that it is not a realistic workload,
and that I'd prefer not to touch the fragile scheduler until I see
one. I think that's perfectly logical, but whatever.

> 
>>But there are still places where interrupts can be held off for 
>>indefinite periods. I don't see why the scheduler lock is suddenly 
>>important [...]
> 
> 
> the scheduler lock is obviously important because it's the most central 
> lock in existence.
> 

Now I call that argument much more illogical than any of mine. How
can such a fine grained, essentially per-cpu lock be "central", let
alone "most central"? And even if it were central, why would that
make it obviously important?

> 
>>[...] I could have told you years ago what would happen if you trigger 
>>the load balancer with enough tasks.
> 
> 
> i very well know what move_tasks() can do. There used to be other ways 
> to provoke unbound latencies in the scheduler - e.g.  via pinned tasks, 
> for which we introduced the all_pinned hack. The all_pinned hack was 
> needed because the worst-case behavior was getting so bad on some larger 
> boxes under larger loads that it totally DoSed the system. So it's not 

But luckily the scheduler is basically completely non functional in
the presence of pinned tasks anyway, so this is the only time this
special case kicks in.

But sure, it is there. I don't see how that justifies more changes
in that place for no reason. As soon as I see a good reason then I'd
be more than happy to look into it myself.

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Ingo Molnar]

* Nick Piggin <nickpiggin@yahoo.com.au> wrote:

> >>But there are still places where interrupts can be held off for 
> >>indefinite periods. I don't see why the scheduler lock is suddenly 
> >>important [...]
> >
> >
> >the scheduler lock is obviously important because it's the most central 
> >lock in existence.
> >
> 
> Now I call that argument much more illogical than any of mine. How can 
> such a fine grained, essentially per-cpu lock be "central", let alone 
> "most central"? [...]

i meant central in the sense that it's the most frequently taken lock, 
in the majority of workloads. Here's the output from the lock validator, 
sorted by number of ops per lock:

 -> (dcache_lock){--} 124233 {
 -> (&rt_hash_locks[i]){-+} 131085 {
 -> (&dentry->d_lock){--} 312431 {
 -> (cpa_lock){++} 507385 {
 -> (__pte_lockptr(new)){--} 660193 {
 -> (kernel/synchro-test.c:&mutex){--} 825023 {
 -> (&rwsem){--} 930501 {
 -> (&rq->lock){++} 2029146 {

the runqueue lock is also central in the sense that it is the most 
spread-out lock in the locking dependencies graph. Toplist of locks, by 
number of backwards dependencies:

     15     -> &cwq->lock
     15     -> nl_table_wait
     15     -> &zone->lock
     17     -> &base->t_base.lock
     32     -> modlist_lock
     38     -> &cachep->spinlock
     46     -> &parent->list_lock
     47     -> &rq->lock

(obviously, as no other lock must nest inside the runqueue lock.)

so the quality of code (including asymptotic behavior) that runs under 
the runqueue lock is of central importance. I didnt think i'd ever have 
to explain this to you, but it is my pleasure to do so ;-) Maybe you 
thought of something else under "central"?

	Ingo

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Peter Williams]

Steven Rostedt wrote:
> On Wed, 2006-02-01 at 14:36 +1100, Peter Williams wrote:
> 
>>Steven Rostedt wrote:
>>
>>>I found this in the -rt kernel.  While running "hackbench 20" I hit
>>>latencies of over 1.5 ms.  That is huge!  This latency was created by
>>>the move_tasks function in sched.c to rebalance the queues over CPUS.  
>>>
>>>There currently isn't any check in this function to see if it should
>>>stop, thus a large number of tasks can drive the latency high.
>>>
>>>With the below patch, (tested on -rt with latency tracing), the latency
>>>caused by hackbench disappeared below my notice threshold (100 usecs).
>>>
>>>I'm not convinced that this bail out is in the right location, but it
>>>worked where it is.  Comments are welcome.
>>>
> 
> 
>>I presume that the intention here is to allow a newly woken task that 
>>preempts the current task to stop the load balancing?
>>
>>As I see it (and I may be wrong), for this to happen, the task must have 
>>woken before the run queue locks were taken (otherwise it wouldn't have 
>>got as far as activation) i.e. before move_tasks() is called and 
>>therefore you may as well just do this check at the start of move_tasks().
> 
> 
> Actually, one of the tasks that was moved might need to resched right
> away, since it preempts the current task that is doing the moving.

Good point but I'd say that this was an instance when you didn't want to 
bail out of the load balance.  E.g. during idle balancing the very first 
task moved would trigger it regardless of its priority.  Also, if the 
task was of sufficiently high priority for it to warrant bailing out of 
the load balance why wasn't the current task (i.e. why didn't it preempt 
on its current CPU).

> 
> 
>>However, a newly woken task that preempts the current task isn't the 
>>only way that needs_resched() can become true just before load balancing 
>>is started.  E.g. scheduler_tick() calls set_tsk_need_resched(p) when a 
>>task finishes a time slice and this patch would cause rebalance_tick() 
>>to be aborted after a lot of work has been done in this case.
> 
> 
> No real work is lost.   This is a loop that individually pulls tasks.  So
> the bail only stops the work of looking for more tasks to pull and we
> don't lose the tasks that have already been pulled.

I disagree.  A bunch of work is done to determine which CPU to pull from 
and how many tasks to pull and then it will bail out before any of them 
are moved (and for no good reason).

> 
> 
>>In summary, I think that the bail out is badly placed and needs some way 
>>of knowing if the reason need_resched() has become true is because of 
>>preemption of a newly woken task and not some other reason.
> 
> 
> I need that bail in the loop, so it can stop if needed. Like I said, it
> can be a task that is pulled to cause the bail. Also, having the run
> queue locks and interrupts off for over a msec is really a bad idea.

Clearly, the way to handle this is to impose some limit on the number of 
tasks to be moved or split large moves into a number of smaller moves 
(releasing and reacquiring locks in between).  This could be done in the 
bits of code that set things up before move_tasks() is called.

> 
> 
>>Peter
>>PS I've added Nick Piggin to the CC list as he is interested in load 
>>balancing issues.
> 
> 
> Thanks, and thanks for the comments too.  I'm up for all suggestions and
> ideas.  I just feel it is important that we don't have unbounded
> latencies of spin locks and interrupts off.

Well, you seem to have succeeded in starting a discussion :-)

Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Peter Williams]

Ingo Molnar wrote:
> * Ingo Molnar <mingo@elte.hu> wrote:
> 
> 
>>i think the right approach would be to split up this work into smaller 
>>chunks. Or rather, lets first see how this can happen: why is 
>>can_migrate() false for so many tasks? Are they all cpu-hot? If yes, 
>>shouldnt we simply skip only up to a limit of tasks in this case - 
>>it's not like we want to spend 1.5 msecs searching for a cache-cold 
>>task which might give us a 50 usecs advantage over cache-hot tasks ...
> 
> 
> the only legimate case where we have to skip alot of tasks is the case 
> when there are alot of CPU-bound (->cpus_alowed) tasks in the runqueue.  
> In that case the scheduler really has to skip that task. But that is not 
> an issue in your workload.

The new SMP nice load balancing may cause some tasks to be skipped while 
it's looking for ones with small enough bias_prios but I doubt that this 
would cause many to be skipped on a real system.

BTW why do you assume that this problem is caused by can_migrate() 
failing and is not just simply due to large numbers of tasks needing to 
be moved (which is highly likely to be true when hackbench is running)?

If it is a "skip" problem that would make the "busting it up into 
smaller chunks" solution more complex as it would make it desirable to 
remember where you were up to between chunks.

Peter
-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

On Thu, 2006-02-02 at 12:26 +1100, Peter Williams wrote:

> > 
> > Actually, one of the tasks that was moved might need to resched right
> > away, since it preempts the current task that is doing the moving.
> 
> Good point but I'd say that this was an instance when you didn't want to 
> bail out of the load balance.  E.g. during idle balancing the very first 
> task moved would trigger it regardless of its priority.  Also, if the 
> task was of sufficiently high priority for it to warrant bailing out of 
> the load balance why wasn't the current task (i.e. why didn't it preempt 
> on its current CPU).

Because the task running on the current CPU is higher in priority.  That
doesn't mean that the next one down shouldn't get scheduled on another
CPU if it is a higher priority than the currently running one.  Of
course one needs to be careful not to cause too much cache blasting by
popping RT tasks all over CPUS.

> 
> > 
> > 
> >>However, a newly woken task that preempts the current task isn't the 
> >>only way that needs_resched() can become true just before load balancing 
> >>is started.  E.g. scheduler_tick() calls set_tsk_need_resched(p) when a 
> >>task finishes a time slice and this patch would cause rebalance_tick() 
> >>to be aborted after a lot of work has been done in this case.
> > 
> > 
> > No real work is lost.   This is a loop that individually pulls tasks.  So
> > the bail only stops the work of looking for more tasks to pull and we
> > don't lose the tasks that have already been pulled.
> 
> I disagree.  A bunch of work is done to determine which CPU to pull from 
> and how many tasks to pull and then it will bail out before any of them 
> are moved (and for no good reason).

Yeah, that was my mistake.  There is work lost. So nuke that argument of
mine :)

> 
> > 
> > 
> >>In summary, I think that the bail out is badly placed and needs some way 
> >>of knowing if the reason need_resched() has become true is because of 
> >>preemption of a newly woken task and not some other reason.
> > 
> > 
> > I need that bail in the loop, so it can stop if needed. Like I said, it
> > can be a task that is pulled to cause the bail. Also, having the run
> > queue locks and interrupts off for over a msec is really a bad idea.
> 
> Clearly, the way to handle this is to impose some limit on the number of 
> tasks to be moved or split large moves into a number of smaller moves 
> (releasing and reacquiring locks in between).  This could be done in the 
> bits of code that set things up before move_tasks() is called.

I think that's something like what Ingo wants to do.  Or something other
than my first brain dead patch.

> 
> > 
> > 
> >>Peter
> >>PS I've added Nick Piggin to the CC list as he is interested in load 
> >>balancing issues.
> > 
> > 
> > Thanks, and thanks for the comments too.  I'm up for all suggestions and
> > ideas.  I just feel it is important that we don't have unbounded
> > latencies of spin locks and interrupts off.
> 
> Well, you seem to have succeeded in starting a discussion :-)

:)

-- Steve

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Steven Rostedt]

On Thu, 2006-02-02 at 12:42 +1100, Peter Williams wrote:
> Ingo Molnar wrote:

> BTW why do you assume that this problem is caused by can_migrate() 
> failing and is not just simply due to large numbers of tasks needing to 
> be moved (which is highly likely to be true when hackbench is running)?

That's my fault.  In another thread (-rt related) I told Ingo that the
problem was with the can_migrate function call.  But later I realized
that was because I miss read some of my logging output, and discovered
that it was indeed passing the can_migrate and getting further.

-- Steve

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Peter Williams]

Steven Rostedt wrote:
> On Thu, 2006-02-02 at 12:26 +1100, Peter Williams wrote:
> 
> 
>>>Actually, one of the tasks that was moved might need to resched right
>>>away, since it preempts the current task that is doing the moving.
>>
>>Good point but I'd say that this was an instance when you didn't want to 
>>bail out of the load balance.  E.g. during idle balancing the very first 
>>task moved would trigger it regardless of its priority.  Also, if the 
>>task was of sufficiently high priority for it to warrant bailing out of 
>>the load balance why wasn't the current task (i.e. why didn't it preempt 
>>on its current CPU).
> 
> 
> Because the task running on the current CPU is higher in priority.  That
> doesn't mean that the next one down shouldn't get scheduled on another
> CPU if it is a higher priority than the currently running one.

Yes, but I don't think that it warrants interrupting the load balancing.

>  Of
> course one needs to be careful not to cause too much cache blasting by
> popping RT tasks all over CPUS.
> 
> 
>>>
>>>>However, a newly woken task that preempts the current task isn't the 
>>>>only way that needs_resched() can become true just before load balancing 
>>>>is started.  E.g. scheduler_tick() calls set_tsk_need_resched(p) when a 
>>>>task finishes a time slice and this patch would cause rebalance_tick() 
>>>>to be aborted after a lot of work has been done in this case.
>>>
>>>
>>>No real work is lost.   This is a loop that individually pulls tasks.  So
>>>the bail only stops the work of looking for more tasks to pull and we
>>>don't lose the tasks that have already been pulled.
>>
>>I disagree.  A bunch of work is done to determine which CPU to pull from 
>>and how many tasks to pull and then it will bail out before any of them 
>>are moved (and for no good reason).
> 
> 
> Yeah, that was my mistake.  There is work lost. So nuke that argument of
> mine :)
> 
> 
>>>
>>>>In summary, I think that the bail out is badly placed and needs some way 
>>>>of knowing if the reason need_resched() has become true is because of 
>>>>preemption of a newly woken task and not some other reason.
>>>
>>>
>>>I need that bail in the loop, so it can stop if needed. Like I said, it
>>>can be a task that is pulled to cause the bail. Also, having the run
>>>queue locks and interrupts off for over a msec is really a bad idea.
>>
>>Clearly, the way to handle this is to impose some limit on the number of 
>>tasks to be moved or split large moves into a number of smaller moves 
>>(releasing and reacquiring locks in between).  This could be done in the 
>>bits of code that set things up before move_tasks() is called.
> 
> 
> I think that's something like what Ingo wants to do.  Or something other
> than my first brain dead patch.
> 
> 
>>>
>>>>Peter
>>>>PS I've added Nick Piggin to the CC list as he is interested in load 
>>>>balancing issues.
>>>
>>>
>>>Thanks, and thanks for the comments too.  I'm up for all suggestions and
>>>ideas.  I just feel it is important that we don't have unbounded
>>>latencies of spin locks and interrupts off.
>>
>>Well, you seem to have succeeded in starting a discussion :-)
> 
> 
> :)
> 
> -- Steve
> 


-- 
Peter Williams                                   pwil3058@bigpond.net.au

"Learning, n. The kind of ignorance distinguishing the studious."
  -- Ambrose Bierce

Re: [PATCH] Avoid moving tasks when a schedule can be made.

[Nick Piggin]

Ingo Molnar wrote:
> * Nick Piggin <nickpiggin@yahoo.com.au> wrote:
> 
> 
>>>>But there are still places where interrupts can be held off for 
>>>>indefinite periods. I don't see why the scheduler lock is suddenly 
>>>>important [...]
>>>
>>>
>>>the scheduler lock is obviously important because it's the most central 
>>>lock in existence.
>>>
>>
>>Now I call that argument much more illogical than any of mine. How can 
>>such a fine grained, essentially per-cpu lock be "central", let alone 
>>"most central"? [...]
> 
> 
> i meant central in the sense that it's the most frequently taken lock, 
> in the majority of workloads. Here's the output from the lock validator, 
> sorted by number of ops per lock:
> 
>  -> (dcache_lock){--} 124233 {
>  -> (&rt_hash_locks[i]){-+} 131085 {
>  -> (&dentry->d_lock){--} 312431 {
>  -> (cpa_lock){++} 507385 {
>  -> (__pte_lockptr(new)){--} 660193 {
>  -> (kernel/synchro-test.c:&mutex){--} 825023 {
>  -> (&rwsem){--} 930501 {
>  -> (&rq->lock){++} 2029146 {
> 
> the runqueue lock is also central in the sense that it is the most 
> spread-out lock in the locking dependencies graph. Toplist of locks, by 
> number of backwards dependencies:
> 
>      15     -> &cwq->lock
>      15     -> nl_table_wait
>      15     -> &zone->lock
>      17     -> &base->t_base.lock
>      32     -> modlist_lock
>      38     -> &cachep->spinlock
>      46     -> &parent->list_lock
>      47     -> &rq->lock
> 
> (obviously, as no other lock must nest inside the runqueue lock.)
> 
> so the quality of code (including asymptotic behavior) that runs under 
> the runqueue lock is of central importance. I didnt think i'd ever have 
> to explain this to you, but it is my pleasure to do so ;-) Maybe you 
> thought of something else under "central"?
>

That's all very interesting, but is purely based on some statistical
analysis of some workload of your choice, and ignores other possible
measures like contention or average/max hold times.

One could concoct a workload for which some other lock is the "*most*
central", strangely enough.

Anyway I'm not trying to say that the runqueue locks are not important,
nor that large latencies should not be avoided in the mainline kernel..
But we've known about this theoretical latency for years, ditto for
rwsem latency (which can also be a central lock in some workloads). I
was simply surprised that you just now jump into action when you see
an equally theoretical workload show you what you already know.

Enough talk from me. I'm looking at a couple of ideas which might help
to improve this too.

-- 
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com