2.4-ac: more scheduler updates (1/3)

diff -urN linux-2.4.19-pre8-ac5/include/asm-i386/bitops.h linux/include/asm-i386/bitops.h
@@ -6,6 +6,7 @@
  */
 
 #include <linux/config.h>
+#include <linux/compiler.h>
 
 /*
  * These have to be done with inline assembly: that way the bit-setting

@@ -421,6 +422,25 @@
 
 #ifdef __KERNEL__
 
+/*
+ * Every architecture must define this function. It's the fastest
+ * way of searching a 140-bit bitmap where the first 100 bits are
+ * unlikely to be set. It's guaranteed that at least one of the 140
+ * bits is cleared.
+ */
+static inline int sched_find_first_bit(unsigned long *b)
+{
+	if (unlikely(b[0]))
+		return __ffs(b[0]);
+	if (unlikely(b[1]))
+		return __ffs(b[1]) + 32;
+	if (unlikely(b[2]))
+		return __ffs(b[2]) + 64;
+	if (b[3])
+		return __ffs(b[3]) + 96;
+	return __ffs(b[4]) + 128;
+}
+
 /**
  * ffs - find first bit set
  * @x: the word to search

diff -urN linux-2.4.19-pre8-ac5/include/asm-i386/mmu_context.h linux/include/asm-i386/mmu_context.h
@@ -7,25 +7,6 @@
 #include <asm/pgalloc.h>
 
 /*
- * Every architecture must define this function. It's the fastest
- * way of searching a 140-bit bitmap where the first 100 bits are
- * unlikely to be set. It's guaranteed that at least one of the 140
- * bits is cleared.
- */
-static inline int sched_find_first_bit(unsigned long *b)
-{
-	if (unlikely(b[0]))
-		return __ffs(b[0]);
-	if (unlikely(b[1]))
-		return __ffs(b[1]) + 32;
-	if (unlikely(b[2]))
-		return __ffs(b[2]) + 64;
-	if (b[3])
-		return __ffs(b[3]) + 96;
-	return __ffs(b[4]) + 128;
-}
-
-/*
  * possibly do the LDT unload here?
  */
 #define destroy_context(mm)		do { } while(0)

diff -urN linux-2.4.19-pre8-ac5/kernel/fork.c linux/kernel/fork.c
@@ -770,24 +770,16 @@
 
 	if (p->ptrace & PT_PTRACED)
 		send_sig(SIGSTOP, p, 1);
-
-#define RUN_CHILD_FIRST 1
-#if RUN_CHILD_FIRST
 	wake_up_forked_process(p);	/* do this last */
-#else
-	wake_up_process(p);		/* do this last */
-#endif
 	++total_forks;
 	if (clone_flags & CLONE_VFORK)
 		wait_for_completion(&vfork);
-#if RUN_CHILD_FIRST
 	else
 		/*
 		 * Let the child process run first, to avoid most of the
 		 * COW overhead when the child exec()s afterwards.
 		 */
 		current->need_resched = 1;
-#endif
 
 fork_out:
 	return retval;

diff -urN linux-2.4.19-pre8-ac5/kernel/sched.c linux/kernel/sched.c
@@ -3,13 +3,17 @@
  *
  *  Kernel scheduler and related syscalls
  *
- *  Copyright (C) 1991, 1992  Linus Torvalds
+ *  Copyright (C) 1991-2002  Linus Torvalds
  *
  *  1996-12-23  Modified by Dave Grothe to fix bugs in semaphores and
  *              make semaphores SMP safe
  *  1998-11-19	Implemented schedule_timeout() and related stuff
  *		by Andrea Arcangeli
- *  1998-12-28  Implemented better SMP scheduling by Ingo Molnar
+ *  2002-01-04	New ultra-scalable O(1) scheduler by Ingo Molnar:
+ *  		hybrid priority-list and round-robin design with
+ *  		an array-switch method of distributing timeslices
+ *  		and per-CPU runqueues.  Additional code by Davide
+ *  		Libenzi, Robert Love, and Rusty Russel.
  */
 
 #include <linux/mm.h>

@@ -1530,6 +1534,16 @@
 		task_rq_unlock(rq, &flags);
 		return;
 	}
+
+	/*
+	 * If the task is not on a runqueue, then it is safe to
+	 * simply update the task's cpu field.
+	 */
+	if (!p->array) {
+		p->cpu = __ffs(p->cpus_allowed);
+		task_rq_unlock(rq, &flags);
+		return;
+	}
 
 	init_MUTEX_LOCKED(&req.sem);
 	req.task = p;

diff -urN linux-2.4.19-pre8-ac5-rml/include/asm-i386/bitops.h linux/include/asm-i386/bitops.h
@@ -428,7 +428,7 @@
  * unlikely to be set. It's guaranteed that at least one of the 140
  * bits is cleared.
  */
-static inline int sched_find_first_bit(unsigned long *b)
+static inline int _sched_find_first_bit(unsigned long *b)
 {
 	if (unlikely(b[0]))
 		return __ffs(b[0]);

diff -urN linux-2.4.19-pre8-ac5-rml/include/linux/sched.h linux/include/linux/sched.h
@@ -162,6 +162,36 @@
 extern int current_is_keventd(void);
 
 /*
+ * Priority of a process goes from 0..MAX_PRIO-1, valid RT
+ * priority is 0..MAX_RT_PRIO-1, and SCHED_OTHER tasks are
+ * in the range MAX_RT_PRIO..MAX_PRIO-1. Priority values
+ * are inverted: lower p->prio value means higher priority.
+ *
+ * The MAX_RT_USER_PRIO value allows the actual maximum
+ * RT priority to be separate from the value exported to
+ * user-space.  This allows kernel threads to set their
+ * priority to a value higher than any user task. Note:
+ * MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO.
+ */
+
+#define MAX_USER_RT_PRIO	100
+#define MAX_RT_PRIO		MAX_USER_RT_PRIO
+
+#define MAX_PRIO		(MAX_RT_PRIO + 40)
+
+/*
+ * The maximum RT priority is configurable.  If the resulting
+ * bitmap is 160-bits , we can use a hand-coded routine which
+ * is optimal.  Otherwise, we fall back on a generic routine for
+ * finding the first set bit from an arbitrarily-sized bitmap.
+ */
+#if MAX_PRIO < 160 && MAX_PRIO > 127
+#define sched_find_first_bit(map)	_sched_find_first_bit(map)
+#else
+#define sched_find_first_bit(map)	find_first_bit(map, MAX_PRIO)
+#endif
+
+/*
  * The default fd array needs to be at least BITS_PER_LONG,
  * as this is the granularity returned by copy_fdset().
  */

@@ -478,8 +508,8 @@
     addr_limit:		KERNEL_DS,					\
     exec_domain:	&default_exec_domain,				\
     lock_depth:		-1,						\
-    prio:		120,						\
-    static_prio:	120,						\
+    prio:		MAX_PRIO-20,					\
+    static_prio:	MAX_PRIO-20,					\
     policy:		SCHED_OTHER,					\
     cpus_allowed:	-1,						\
     mm:			NULL,						\

diff -urN linux-2.4.19-pre8-ac5-rml/kernel/sched.c linux/kernel/sched.c
@@ -26,20 +26,6 @@
 #include <linux/kernel_stat.h>
 
 /*
- * Priority of a process goes from 0 to 139. The 0-99
- * priority range is allocated to RT tasks, the 100-139
- * range is for SCHED_OTHER tasks. Priority values are
- * inverted: lower p->prio value means higher priority.
- * 
- * MAX_USER_RT_PRIO allows the actual maximum RT priority
- * to be separate from the value exported to user-space.
- * NOTE: MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO.
- */
-#define MAX_RT_PRIO		100
-#define MAX_USER_RT_PRIO	100
-#define MAX_PRIO		(MAX_RT_PRIO + 40)
-
-/*
  * Convert user-nice values [ -20 ... 0 ... 19 ]
  * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
  * and back.