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