Re: [PATCH] Staircase Scheduler v6.3 for 2.6.7-rc2

[William Lee Irwin III <wli@holomorphy.com>]

On Mon, Jun 07, 2004 at 07:07:14AM -0700, William Lee Irwin III wrote:
>> cpu_to_node_mask() is dead.

On Mon, Jun 07, 2004 at 08:00:37AM -0700, William Lee Irwin III wrote:
> task->array is nothing more than a boolean flag. Shove it into
> task->thread_info->flags, saving sizeof(prio_array_t *) from sizeof(task_t).
> Compiletested only on sparc64 only.

prio_array_t is no longer a useful abstraction. Compiletested only on
sparc64 only.


Index: kolivas-2.6.7-rc2/kernel/sched.c
===================================================================
--- kolivas-2.6.7-rc2.orig/kernel/sched.c	2004-06-07 07:59:22.711997000 -0700
+++ kolivas-2.6.7-rc2/kernel/sched.c	2004-06-07 08:07:09.705003000 -0700
@@ -81,15 +81,8 @@
  * These are the runqueue data structures:
  */
 
-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
-
 typedef struct runqueue runqueue_t;
 
-typedef struct prio_array {
-	unsigned long bitmap[BITMAP_SIZE];
-	struct list_head queue[MAX_PRIO + 1];
-} prio_array_t;
-
 /*
  * This is the main, per-CPU runqueue data structure.
  *
@@ -113,7 +106,8 @@
 	unsigned long long timestamp_last_tick;
 	task_t *curr, *idle;
 	struct mm_struct *prev_mm;
-	prio_array_t array;
+	unsigned long bitmap[BITS_TO_LONGS(MAX_PRIO+1)];
+	struct list_head queue[MAX_PRIO + 1];
 	atomic_t nr_iowait;
 
 #ifdef CONFIG_SMP
@@ -207,21 +201,19 @@
 }
 
 /*
- * Adding/removing a task to/from a priority array:
+ * Adding/removing a task to/from a runqueue:
  */
 static void dequeue_task(struct task_struct *p, runqueue_t *rq)
 {
-	prio_array_t* array = &rq->array;
 	list_del(&p->run_list);
-	if (list_empty(array->queue + p->prio))
-		__clear_bit(p->prio, array->bitmap);
+	if (list_empty(rq->queue + p->prio))
+		__clear_bit(p->prio, rq->bitmap);
 }
 
 static void enqueue_task(struct task_struct *p, runqueue_t *rq)
 {
-	prio_array_t* array = &rq->array;
-	list_add_tail(&p->run_list, array->queue + p->prio);
-	__set_bit(p->prio, array->bitmap);
+	list_add_tail(&p->run_list, rq->queue + p->prio);
+	__set_bit(p->prio, rq->bitmap);
 	set_task_queued(p);
 }
 
@@ -232,9 +224,8 @@
  */
 static inline void enqueue_task_head(struct task_struct *p, runqueue_t *rq)
 {
-	prio_array_t* array = &rq->array;
-	list_add(&p->run_list, array->queue + p->prio);
-	__set_bit(p->prio, array->bitmap);
+	list_add(&p->run_list, rq->queue + p->prio);
+	__set_bit(p->prio, rq->bitmap);
 	set_task_queued(p);
 }
 
@@ -1257,27 +1248,24 @@
 		      unsigned long max_nr_move, struct sched_domain *sd,
 		      enum idle_type idle)
 {
-	prio_array_t* array, *dst_array;
 	struct list_head *head, *curr;
 	int idx, pulled = 0;
 	task_t *tmp;
 
 	if (max_nr_move <= 0 || busiest->nr_running <= 1)
 		goto out;
-	array = &busiest->array;
-	dst_array = &this_rq->array;
 
 	/* Start searching at priority 0: */
 	idx = 0;
 skip_bitmap:
 	if (!idx)
-		idx = sched_find_first_bit(array->bitmap);
+		idx = sched_find_first_bit(busiest->bitmap);
 	else
-		idx = find_next_bit(array->bitmap, MAX_PRIO, idx);
+		idx = find_next_bit(busiest->bitmap, MAX_PRIO, idx);
 	if (idx >= MAX_PRIO) 
 		goto out;
 
-	head = array->queue + idx;
+	head = busiest->queue + idx;
 	curr = head->prev;
 skip_queue:
 	tmp = list_entry(curr, task_t, run_list);
@@ -1919,7 +1907,6 @@
 	long *switch_count;
 	task_t *prev, *next;
 	runqueue_t *rq;
-	prio_array_t* array;
 	struct list_head *queue;
 	unsigned long long now;
 	int cpu, idx;
@@ -1971,9 +1958,8 @@
 		}
 	}
 
-	array = &rq->array;
-	idx = sched_find_first_bit(array->bitmap);
-	queue = array->queue + idx;
+	idx = sched_find_first_bit(rq->bitmap);
+	queue = rq->queue + idx;
 	next = list_entry(queue->next, task_t, run_list);
 
 	if (dependent_sleeper(cpu, rq, next))
@@ -3590,8 +3576,6 @@
 #endif
 
 	for (i = 0; i < NR_CPUS; i++) {
-		prio_array_t* array;
-
 		rq = cpu_rq(i);
 		spin_lock_init(&rq->lock);
 
@@ -3604,14 +3588,11 @@
 		INIT_LIST_HEAD(&rq->migration_queue);
 #endif
 		atomic_set(&rq->nr_iowait, 0);
-		array = &rq->array;
-
-		for (j = 0; j <= MAX_PRIO; j++) {
-			INIT_LIST_HEAD(array->queue + j);
-			__clear_bit(j, array->bitmap);
-		}
+		for (j = 0; j <= MAX_PRIO; j++)
+			INIT_LIST_HEAD(&rq->queue[j]);
+		memset(rq->bitmap, 0, BITS_TO_LONGS(MAX_PRIO+1)*sizeof(long));
 		// delimiter for bitsearch
-		__set_bit(MAX_PRIO, array->bitmap);
+		__set_bit(MAX_PRIO, rq->bitmap);
 	}
 	/*
 	 * We have to do a little magic to get the first