Module: xenomai-forge
Branch: next
Commit: c0fec740d9221b920df0ae2eaede0d99b8756e5c
URL:    
http://git.xenomai.org/?p=xenomai-forge.git;a=commit;h=c0fec740d9221b920df0ae2eaede0d99b8756e5c

Author: Philippe Gerum <r...@xenomai.org>
Date:   Mon Apr 14 18:04:12 2014 +0200

cobalt/sched: rebase multi-level queues over regular kernel bitmaps

---

 include/cobalt/kernel/schedqueue.h |   21 +++++++------------
 kernel/cobalt/sched.c              |   39 ++++++++++++------------------------
 2 files changed, 20 insertions(+), 40 deletions(-)

diff --git a/include/cobalt/kernel/schedqueue.h 
b/include/cobalt/kernel/schedqueue.h
index 15817b2..09077e4 100644
--- a/include/cobalt/kernel/schedqueue.h
+++ b/include/cobalt/kernel/schedqueue.h
@@ -25,28 +25,23 @@
 #define XNSCHED_CLASS_WEIGHT_FACTOR    1024
 
 #ifdef CONFIG_XENO_OPT_SCALABLE_SCHED
+
+#include <linux/bitmap.h>
+
 /*
  * Multi-level priority queue, suitable for handling the runnable
  * thread queue of a scheduling class with O(1) property. We only
  * manage a descending queuing order, i.e. highest numbered priorities
  * come first.
  */
-#define XNSCHED_MLQ_LEVELS  264
-
-#if BITS_PER_LONG * BITS_PER_LONG < XNSCHED_MLQ_LEVELS
-#error "internal bitmap cannot hold so many priority levels"
-#endif
-
-#define __MLQ_LONGS ((XNSCHED_MLQ_LEVELS+BITS_PER_LONG-1)/BITS_PER_LONG)
+#define XNSCHED_MLQ_LEVELS  258        /* i.e. XNSCHED_RT_NR_PRIO */
 
 struct xnsched_mlq {
        int elems;
-       unsigned long himap, lomap[__MLQ_LONGS];
+       DECLARE_BITMAP(prio_map, XNSCHED_MLQ_LEVELS);
        struct list_head heads[XNSCHED_MLQ_LEVELS];
 };
 
-#undef __MLQ_LONGS
-
 struct xnthread;
 
 void xnsched_initq(struct xnsched_mlq *q);
@@ -64,14 +59,12 @@ struct xnthread *xnsched_getq(struct xnsched_mlq *q);
 
 static inline int xnsched_emptyq_p(struct xnsched_mlq *q)
 {
-       return q->himap == 0;
+       return q->elems == 0;
 }
 
 static inline int xnsched_weightq(struct xnsched_mlq *q)
 {
-       int hi = ffnz(q->himap);
-       int lo = ffnz(q->lomap[hi]);
-       return hi * BITS_PER_LONG + lo; /* Result is undefined if none set. */
+       return find_first_bit(q->prio_map, XNSCHED_MLQ_LEVELS);
 }
 
 typedef struct xnsched_mlq xnsched_queue_t;
diff --git a/kernel/cobalt/sched.c b/kernel/cobalt/sched.c
index d89889e..47d2f13 100644
--- a/kernel/cobalt/sched.c
+++ b/kernel/cobalt/sched.c
@@ -497,8 +497,7 @@ void xnsched_initq(struct xnsched_mlq *q)
        int prio;
 
        q->elems = 0;
-       q->himap = 0;
-       memset(&q->lomap, 0, sizeof(q->lomap));
+       bitmap_zero(q->prio_map, XNSCHED_MLQ_LEVELS);
 
        for (prio = 0; prio < XNSCHED_MLQ_LEVELS; prio++)
                INIT_LIST_HEAD(q->heads + prio);
@@ -506,35 +505,30 @@ void xnsched_initq(struct xnsched_mlq *q)
 
 static inline int get_qindex(struct xnsched_mlq *q, int prio)
 {
-       XENO_BUGON(NUCLEUS, prio < XNSCHED_RT_MIN_PRIO ||
-                  prio > XNSCHED_RT_MAX_PRIO);
+       XENO_BUGON(NUCLEUS, prio < 0 || prio >= XNSCHED_MLQ_LEVELS);
        /*
         * BIG FAT WARNING: We need to rescale the priority level to a
-        * 0-based range. We use ffnz() to scan the bitmap which MUST
-        * be based on a bit scan forward op. Therefore, the lower the
-        * index value, the higher the priority (since least
+        * 0-based range. We use find_first_bit() to scan the bitmap
+        * which is a bit scan forward operation. Therefore, the lower
+        * the index value, the higher the priority (since least
         * significant bits will be found first when scanning the
-        * bitmaps).
+        * bitmap).
         */
-       return XNSCHED_RT_MAX_PRIO - prio;
+       return XNSCHED_MLQ_LEVELS - prio - 1;
 }
 
 static struct list_head *add_q(struct xnsched_mlq *q, int prio)
 {
        struct list_head *head;
-       int hi, lo, idx;
+       int idx;
 
        idx = get_qindex(q, prio);
        head = q->heads + idx;
        q->elems++;
 
        /* New item is not linked yet. */
-       if (list_empty(head)) {
-               hi = idx / BITS_PER_LONG;
-               lo = idx % BITS_PER_LONG;
-               q->himap |= (1UL << hi);
-               q->lomap[hi] |= (1UL << lo);
-       }
+       if (list_empty(head))
+               __set_bit(idx, q->prio_map);
 
        return head;
 }
@@ -554,20 +548,13 @@ void xnsched_addq_tail(struct xnsched_mlq *q, struct 
xnthread *thread)
 static void del_q(struct xnsched_mlq *q,
                  struct list_head *entry, int idx)
 {
-       struct list_head *head;
-       int hi, lo;
+       struct list_head *head = q->heads + idx;
 
-       head = q->heads + idx;
        list_del(entry);
        q->elems--;
 
-       if (list_empty(head)) {
-               hi = idx / BITS_PER_LONG;
-               lo = idx % BITS_PER_LONG;
-               q->lomap[hi] &= ~(1UL << lo);
-               if (q->lomap[hi] == 0)
-                       q->himap &= ~(1UL << hi);
-       }
+       if (list_empty(head))
+               __clear_bit(idx, q->prio_map);
 }
 
 void xnsched_delq(struct xnsched_mlq *q, struct xnthread *thread)


_______________________________________________
Xenomai-git mailing list
Xenomai-git@xenomai.org
http://www.xenomai.org/mailman/listinfo/xenomai-git

Reply via email to