Very Computer

This patch extracts some of the stuff that Ingo uses for the O(1)
scheduler and makes it avalable in linux/prioarray.h, so that it
can be used by other parts of the kernel.

It's main use right now is by the pfutex patch, that implements
priority based futexes.

Caveats:

 - Ugly kludge in sched.h to include prioarray.h ...

Enjoy

This patch requires linux-2.5.52

diff -u /dev/null include/linux/prioarray.h:1.1.2.1
--- /dev/null   Mon Dec 16 19:01:38 2002

+/*
+ * O(1) priority arrays
+ *


+ * that other parts of the kernel can use the same constructs.
+ */
+
+#ifndef _LINUX_PRIOARRAY_
+#define _LINUX_PRIOARRAY_
+
+        /* This inclusion is kind of recursive ... hmmm */
+
+#include <linux/sched.h>
+
+struct prio_array {
+       int nr_active;
+       unsigned long bitmap[BITMAP_SIZE];
+       struct list_head queue[MAX_PRIO];
+};
+
+typedef struct prio_array prio_array_t;
+
+static inline
+void pa_init (prio_array_t *array)
+{
+        unsigned cnt;
+       array->nr_active = 0;
+        memset (array->bitmap, 0, sizeof (array->bitmap));
+        for (cnt = 0; cnt < MAX_PRIO; cnt++)
+                INIT_LIST_HEAD (&array->queue[cnt]);
+}
+
+/*
+ * Adding/removing a node to/from a priority array:
+ */
+
+static inline
+void pa_dequeue (struct list_head *p, unsigned prio, prio_array_t *array)
+{
+       array->nr_active--;
+       list_del(p);
+       if (list_empty(array->queue + prio))
+               __clear_bit(prio, array->bitmap);
+}
+
+static inline
+void pa_enqueue (struct list_head *p, unsigned prio, prio_array_t *array)
+{
+       list_add_tail(p, array->queue + prio);
+       __set_bit(prio, array->bitmap);
+       array->nr_active++;
+}
+
+
+
+#endif /* #ifndef _LINUX_PRIOARRAY_ */
diff -u include/linux/sched.h:1.1.1.8 include/linux/sched.h:1.1.1.1.2.3
--- include/linux/sched.h:1.1.1.8       Mon Dec 16 18:44:32 2002

 #define MAX_RT_PRIO            MAX_USER_RT_PRIO

 #define MAX_PRIO               (MAX_RT_PRIO + 40)
+#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
+
+#include <linux/prioarray.h> /* Okay, this is ugly, but needs MAX_PRIO */

 /*

 extern struct user_struct root_user;
 #define INIT_USER (&root_user)

-typedef struct prio_array prio_array_t;
 struct backing_dev_info;

 struct task_struct {
diff -u kernel/sched.c:1.1.1.6 kernel/sched.c:1.1.1.1.2.2
--- kernel/sched.c:1.1.1.6      Wed Dec 11 11:13:36 2002

  * These are the runqueue data structures:
  */

-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
-
 typedef struct runqueue runqueue_t;

-struct prio_array {
-       int nr_active;
-       unsigned long bitmap[BITMAP_SIZE];
-       struct list_head queue[MAX_PRIO];
-};

 /*

  */
 static inline void dequeue_task(struct task_struct *p, prio_array_t *array)
 {
-       array->nr_active--;
-       list_del(&p->run_list);
-       if (list_empty(array->queue + p->prio))
-               __clear_bit(p->prio, array->bitmap);
+        pa_dequeue (&p->run_list, p->prio, array);
 }

 static inline void enqueue_task(struct task_struct *p, prio_array_t *array)
 {
-       list_add_tail(&p->run_list, array->queue + p->prio);
-       __set_bit(p->prio, array->bitmap);
-       array->nr_active++;
+        pa_enqueue (&p->run_list, p->prio, array);
        p->array = array;
 }

--

Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my fault]
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in

More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/