Module: xenomai-forge
Branch: rtdm-api-waitqueues
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
