[patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Ingo Molnar]

this is the next release of the O(1) scheduler:

	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.5.2-A1.patch
	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.4.17-A1.patch

this release includes fixes and small improvements. (The 2.5.2-A1 patch is
against the 2.5.2-pre7 kernel.) I cannot reproduce any more failures with
this patch, but i couldnt test the vfat lockup problem. The X lockup
problem never occured on any of my boxes, but it might be fixed by one of
the changes included in this patch nevertheless.

Changes:

 - idle process notification fixes. This fixes the idle=poll breakage
   reported by Anton Blanchard.

 - fix a bug in setscheduler() which crashed if a non-SCHED_OTHER task did
   a setscheduler() call. This fixes the crash reported by Randy Hron. The
   Linux Test Project's syscall tests do not cause a crash anymore.

 - do some more unlikely()/likely() tagging of branches along the hotpath,
   suggested by Jeff Garzik.

 - fix the compile failures in md.c and loop.c and other files, reported
   by many people.

 - fix the too-big-by-one error in the bitmat sizing define, noticed by
   Anton Blanchard.

 - fix a bug in rt_lock() + setscheduler() that had a potential for a
   spinlock lockup.

 - introduce the idle_tick() function, so that idle CPUs can do
   load-balancing as well.

 - do LINUX_VERSION_CODE checking in jffs2 (Jeff Garzik)

 - optimize the big-kernel-lock releasing/acquiring code some more. From
   now on it's absolutely illegal to schedule() from cli()-ed code. (not
   that it was legal.) This moves a few instructions off the scheduler
   hotpath.

 - move the ->need_resched setting into idle_init().

 - do not clear RT tasks in reparent_to_init(). There's nothing bad with
   running RT tasks in the background.

 - RT task's priority order was inverted, it should be 0-99, not 99-0.

 - make load-balancing a bit less eager when there are lots of processes
   running: it needs a ~10% imbalance in runqueue lengths to trigger a
   rebalance.

 - (there is a small hack in serial.c in the 2.5.2-pre7 patch, to make it
   compile.)

Comments, bug reports, suggestions are welcome,

	Ingo

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Andrey Nekrasov]

Hello Ingo Molnar,


2.4.17 + A1 patch:

...
gcc -D__KERNEL__ -I/usr/src/linux-2.4.17-A1/include -Wall -Wstrict-prototypes
-Wno-trigraphs -O2 -fomit-frame-pointer -fno-strict-aliasing -fno-common -pipe
-mpreferred-stack-boundary=2 -march=i686    -c -o syncookies.o syncookies.c
gcc -D__KERNEL__ -I/usr/src/linux-2.4.17-A1/include -Wall -Wstrict-prototypes
-Wno-trigraphs -O2 -fomit-frame-pointer -fno-strict-aliasing -fno-common -pipe
-mpreferred-stack-boundary=2 -march=i686    -c -o ipconfig.o ipconfig.c
ipconfig.c: In function `ip_auto_config':
ipconfig.c:1148: `UNNAMED_MAJOR' undeclared (first use in this function)
ipconfig.c:1148: (Each undeclared identifier is reported only once
ipconfig.c:1148: for each function it appears in.)
make[3]: *** [ipconfig.o] Error 1
make[3]: Leaving directory `/usr/src/linux-2.4.17-A1/net/ipv4'
make[2]: *** [first_rule] Error 2
make[2]: Leaving directory `/usr/src/linux-2.4.17-A1/net/ipv4'
make[1]: *** [_subdir_ipv4] Error 2
make[1]: Leaving directory `/usr/src/linux-2.4.17-A1/net'
make: *** [_dir_net] Error 2
suse:/usr/src/linux #


ps. vanilla kernel compile ok.


Once you wrote about "[patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.":
 
> this is the next release of the O(1) scheduler:
> 
> 	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.5.2-A1.patch
> 	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.4.17-A1.patch
> 
> this release includes fixes and small improvements. (The 2.5.2-A1 patch is
> against the 2.5.2-pre7 kernel.) I cannot reproduce any more failures with
> this patch, but i couldnt test the vfat lockup problem. The X lockup
> problem never occured on any of my boxes, but it might be fixed by one of
> the changes included in this patch nevertheless.
> 
> Changes:
> 
>  - idle process notification fixes. This fixes the idle=poll breakage
>    reported by Anton Blanchard.
> 
>  - fix a bug in setscheduler() which crashed if a non-SCHED_OTHER task did
>    a setscheduler() call. This fixes the crash reported by Randy Hron. The
>    Linux Test Project's syscall tests do not cause a crash anymore.
> 
>  - do some more unlikely()/likely() tagging of branches along the hotpath,
>    suggested by Jeff Garzik.
> 
>  - fix the compile failures in md.c and loop.c and other files, reported
>    by many people.
> 
>  - fix the too-big-by-one error in the bitmat sizing define, noticed by
>    Anton Blanchard.
> 
>  - fix a bug in rt_lock() + setscheduler() that had a potential for a
>    spinlock lockup.
> 
>  - introduce the idle_tick() function, so that idle CPUs can do
>    load-balancing as well.
> 
>  - do LINUX_VERSION_CODE checking in jffs2 (Jeff Garzik)
> 
>  - optimize the big-kernel-lock releasing/acquiring code some more. From
>    now on it's absolutely illegal to schedule() from cli()-ed code. (not
>    that it was legal.) This moves a few instructions off the scheduler
>    hotpath.
> 
>  - move the ->need_resched setting into idle_init().
> 
>  - do not clear RT tasks in reparent_to_init(). There's nothing bad with
>    running RT tasks in the background.
> 
>  - RT task's priority order was inverted, it should be 0-99, not 99-0.
> 
>  - make load-balancing a bit less eager when there are lots of processes
>    running: it needs a ~10% imbalance in runqueue lengths to trigger a
>    rebalance.
> 
>  - (there is a small hack in serial.c in the 2.5.2-pre7 patch, to make it
>    compile.)
> 
> Comments, bug reports, suggestions are welcome,
> 
> 	Ingo
> 
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

-- 
bye.
Andrey Nekrasov, SpyLOG.

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Ingo Molnar]

On Fri, 4 Jan 2002, Andrey Nekrasov wrote:

> ipconfig.c: In function `ip_auto_config':
> ipconfig.c:1148: `UNNAMED_MAJOR' undeclared (first use in this function)
> ipconfig.c:1148: (Each undeclared identifier is reported only once
> ipconfig.c:1148: for each function it appears in.)

> ps. vanilla kernel compile ok.

hm, the patch does not change ipconfig.c.

	Ingo

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Adrian Bunk]

On Fri, 4 Jan 2002, Ingo Molnar wrote:

> On Fri, 4 Jan 2002, Andrey Nekrasov wrote:
>
> > ipconfig.c: In function `ip_auto_config':
> > ipconfig.c:1148: `UNNAMED_MAJOR' undeclared (first use in this function)
> > ipconfig.c:1148: (Each undeclared identifier is reported only once
> > ipconfig.c:1148: for each function it appears in.)
>
> > ps. vanilla kernel compile ok.
>
> hm, the patch does not change ipconfig.c.

It seems the following part of your patch broke it (net/ipv4/ipconfig.c
includes include/linux/sched.h; linux/tty.h includes linux/major.h that
defines UNNAMED_MAJOR):

--- linux/include/linux/sched.h.orig    Thu Jan  3 18:49:58 2002
+++ linux/include/linux/sched.h Fri Jan  4 15:27:20 2002
@@ -21,7 +21,6 @@
 #include <asm/mmu.h>

 #include <linux/smp.h>
-#include <linux/tty.h>
 #include <linux/sem.h>
 #include <linux/signal.h>
 #include <linux/securebits.h>



The right solution is perhaps for ipconfig.c to include major.h directly?

--- net/ipv4/ipconfig.c.old	Fri Jan  4 21:14:50 2002
+++ net/ipv4/ipconfig.c	Fri Jan  4 21:15:39 2002
@@ -32,6 +32,7 @@
 #include <linux/types.h>
 #include <linux/string.h>
 #include <linux/kernel.h>
+#include <linux/major.h>
 #include <linux/sched.h>
 #include <linux/random.h>
 #include <linux/init.h>


> 	Ingo

cu
Adrian

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Ingo Molnar]

On Fri, 4 Jan 2002, Adrian Bunk wrote:

> It seems the following part of your patch broke it (net/ipv4/ipconfig.c
> includes include/linux/sched.h; linux/tty.h includes linux/major.h that
> defines UNNAMED_MAJOR):
>
> --- linux/include/linux/sched.h.orig    Thu Jan  3 18:49:58 2002
> +++ linux/include/linux/sched.h Fri Jan  4 15:27:20 2002
> @@ -21,7 +21,6 @@
>  #include <asm/mmu.h>
>
>  #include <linux/smp.h>
> -#include <linux/tty.h>
>  #include <linux/sem.h>
>  #include <linux/signal.h>
>  #include <linux/securebits.h>

thanks for the detective work - i've reverted this part of the 2.4.17
patch and have uploaded the -A2 patch.

	Ingo

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Heinz Diehl]

On Fri Jan 04 2002, Ingo Molnar wrote:

> thanks for the detective work - i've reverted this part of the 2.4.17
> patch and have uploaded the -A2 patch.

The -A2 patch applies well to 2.4.17, however compilation fails:

[....]
gcc -D__KERNEL__ -I/usr/src/linux/include -Wall -Wstrict-prototypes
-Wno-trigraphs -O2 -fomit-frame-pointer -fno-strict-aliasing -fno-common
-pipe -mpreferred-stack-boundary=2 -march=k6    -DEXPORT_SYMTAB -c filemap.c
In file included from filemap.c:26:
/usr/src/linux/include/linux/compiler.h:13: warning: likely' redefined
/usr/src/linux/include/linux/sched.h:445: warning: this is the location of
the previous definition
/usr/src/linux/include/linux/compiler.h:14: warning: unlikely' redefined
/usr/src/linux/include/linux/sched.h:444: warning: this is the location of
the previous definition
filemap.c: In function page_cache_read':
filemap.c:696: SCHED_YIELD' undeclared (first use in this function)
filemap.c:696: (Each undeclared identifier is reported only once
filemap.c:696: for each function it appears in.)
make[2]: *** [filemap.o] Error 1
make[2]: Leaving directory /usr/src/linux/mm'
make[1]: *** [first_rule] Error 2
make[1]: Leaving directory /usr/src/linux/mm'
make: *** [_dir_mm] Error 2
elfie:/usr/src/linux #

-- 
# Heinz Diehl, 68259 Mannheim, Germany

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Evgeniy Polyakov]

On Fri, 4 Jan 2002 18:05:23 +0100 (CET)
Ingo Molnar <mingo@elte.hu> wrote:

> 
> this is the next release of the O(1) scheduler:
> 
> 	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.5.2-A1.patch
> 	http://redhat.com/~mingo/O(1)-scheduler/sched-O1-2.4.17-A1.patch
> 
> this release includes fixes and small improvements. (The 2.5.2-A1 patch
is
> against the 2.5.2-pre7 kernel.) I cannot reproduce any more failures
with
> this patch, but i couldnt test the vfat lockup problem. The X lockup
> problem never occured on any of my boxes, but it might be fixed by one
of
> the changes included in this patch nevertheless.

Nop. System hangs after couple of minutes in X mode... :(
vfat is compiled into the 2.4.17 vanilla-kernel.
Non smp i386 but with smp kernel.
Any other info?

> 
> 	Ingo

---
WBR. //s0mbre

Re: [announce] [patch] ultra-scalable O(1) SMP and UP scheduler

[Ingo Molnar]

On Fri, 4 Jan 2002, Dieter [iso-8859-15] Nützel wrote:

> What next? Maybe a combination of O(1) and preempt?

yes, fast preemption of kernel-mode tasks and the scheduler code are
almost orthogonal. So i agree that to get the best interactive performance
we need both.

	Ingo

ps. i'm working on fixing the crashes you saw.

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Dieter Nützel]

[-- Attachment #1: Type: text/plain, Size: 1115 bytes --]

On Friday, 4. January 2002 12:42, Ingo Molnar wrote:
> On Fri, 4 Jan 2002, Dieter [iso-8859-15] Nützel wrote:
> > What next? Maybe a combination of O(1) and preempt?
>
> yes, fast preemption of kernel-mode tasks and the scheduler code are
> almost orthogonal. So i agree that to get the best interactive performance
> we need both.

[....]
gcc -D__KERNEL__ -I/usr/src/linux/include -Wall -Wstrict-prototypes
-Wno-trigraphs -O2 -fomit-frame-pointer -fno-strict-aliasing -fno-common
-pipe -mpreferred-stack-boundary=2 -march=k6    -DEXPORT_SYMTAB -c filemap.c
In file included from filemap.c:26:
/usr/src/linux/include/linux/compiler.h:13: warning: likely' redefined
/usr/src/linux/include/linux/sched.h:445: warning: this is the location of
the previous definition
/usr/src/linux/include/linux/compiler.h:14: warning: unlikely' redefined
/usr/src/linux/include/linux/sched.h:444: warning: this is the location of
the previous definition

But _NO_ fails.

-A2 crash immediatly during first boot.
Second run some crashes and stuck in boot up.

I'll try a clean 2.4.17 + A2 (plus needed ReiserFS stuff), now.

-Dieter


[-- Attachment #2: messages-short.bz2 --]
[-- Type: application/x-bzip2, Size: 3548 bytes --]

[-- Attachment #3: messages-short-ksymoops.bz2 --]
[-- Type: application/x-bzip2, Size: 14889 bytes --]

[-- Attachment #4: boot.omsg.bz2 --]
[-- Type: application/x-bzip2, Size: 2955 bytes --]

Re: [patch] O(1) scheduler, 2.4.17-A1, 2.5.2-pre7-A1.

[Adrian Bunk]

On Fri, 4 Jan 2002, Dieter Nützel wrote:

> gcc -D__KERNEL__ -I/usr/src/linux/include -Wall -Wstrict-prototypes
> -Wno-trigraphs -O2 -fomit-frame-pointer -fno-strict-aliasing -fno-common
> -pipe -mpreferred-stack-boundary=2 -march=k6    -DEXPORT_SYMTAB -c filemap.c
> In file included from filemap.c:26:
> /usr/src/linux/include/linux/compiler.h:13: warning: likely' redefined
> /usr/src/linux/include/linux/sched.h:445: warning: this is the location of
> the previous definition
> /usr/src/linux/include/linux/compiler.h:14: warning: unlikely' redefined
> /usr/src/linux/include/linux/sched.h:444: warning: this is the location of
> the previous definition
>...

This warning is harmless but I'm wondering why sched.h adds a second
definition of likely/unlikely instead of using the one in compiler.h?

I'd suggest the following patch against 2.4.17-A2:

--- include/linux/sched.h.old	Sat Jan  5 18:03:41 2002
+++ include/linux/sched.h	Sat Jan  5 18:10:16 2002
@@ -7,6 +7,7 @@

 #include <linux/config.h>
 #include <linux/binfmts.h>
+#include <linux/compiler.h>
 #include <linux/threads.h>
 #include <linux/kernel.h>
 #include <linux/types.h>
@@ -441,8 +442,6 @@
  */
 #define _STK_LIM	(8*1024*1024)

-#define unlikely(x) x
-#define likely(x) x
 /*
  * The lower the priority of a process, the more likely it is
  * to run. Priority of a process goes from 0 to 63.

> -Dieter

cu
Adrian