Re: [patch] O(1) scheduler, -D1, 2.5.2-pre9, 2.4.17

[Anton Blanchard <anton@samba.org>]

Hi Ingo,

I tested 2.5.2-pre10 today. There is some bitop abuse that needs fixing
for big endian machines to work :)

At the moment we have:

	#define BITMAP_SIZE ((MAX_PRIO+7)/8)
	char bitmap[BITMAP_SIZE];

Which is initialised using:

	memset(array->bitmap, 0xff, BITMAP_SIZE);
	clear_bit(MAX_PRIO, array->bitmap);

This results in the following in memory (in ascending memory order):

ffffffffffffffff ffffffffffffffff fffffeffff000000

The problem here is that when we search the high word, we do so from
the right, therefore we get 128 all the time :)

The following patch fixes this. We need to define the bitmap to be in
terms of unsigned long, in this case its only lucky we have the correct
alignment. We also replace the memset of the bitmap with set_bit.

With the patch things look much better (and the kernel boots on my
ppc64 machine :)

ffffffffffffffff ffffffffffffffff 000000ffffffffff 

Anton

diff -urN linuxppc_2_5/include/asm-i386/mmu_context.h linuxppc_2_5_work/include/asm-i386/mmu_context.h
--- linuxppc_2_5/include/asm-i386/mmu_context.h	Tue Jan  8 17:09:47 2002
+++ linuxppc_2_5_work/include/asm-i386/mmu_context.h	Tue Jan  8 22:06:35 2002
@@ -16,7 +16,7 @@
 # error update this function.
 #endif
 
-static inline int sched_find_first_zero_bit(char *bitmap)
+static inline int sched_find_first_zero_bit(unsigned long *bitmap)
 {
 	unsigned int *b = (unsigned int *)bitmap;
 	unsigned int rt;
diff -urN linuxppc_2_5/kernel/sched.c linuxppc_2_5_work/kernel/sched.c
--- linuxppc_2_5/kernel/sched.c	Tue Jan  8 17:09:47 2002
+++ linuxppc_2_5_work/kernel/sched.c	Tue Jan  8 22:13:45 2002
@@ -20,15 +20,13 @@
 #include <linux/interrupt.h>
 #include <asm/mmu_context.h>
 
-#define BITMAP_SIZE ((MAX_PRIO+7)/8)
-
 typedef struct runqueue runqueue_t;
 
 struct prio_array {
 	int nr_active;
 	spinlock_t *lock;
 	runqueue_t *rq;
-	char bitmap[BITMAP_SIZE];
+	unsigned long bitmap[3];
 	list_t queue[MAX_PRIO];
 };
 
@@ -1306,11 +1304,12 @@
 			array = rq->arrays + j;
 			array->rq = rq;
 			array->lock = &rq->lock;
-			for (k = 0; k < MAX_PRIO; k++)
+			for (k = 0; k < MAX_PRIO; k++) {
 				INIT_LIST_HEAD(array->queue + k);
-			memset(array->bitmap, 0xff, BITMAP_SIZE);
+				__set_bit(k, array->bitmap);
+			}
 			// zero delimiter for bitsearch
-			clear_bit(MAX_PRIO, array->bitmap);
+			__clear_bit(MAX_PRIO, array->bitmap);
 		}
 	}
 	/*