[Xenomai-git] Philippe Gerum : kernel/cobalt/timer: drop support for hash-based indexing
Module: xenomai-forge Branch: master Commit: b8eed0ef7d578c9dc5932b9c448dde62bf7bb7e5 URL: http://git.xenomai.org/?p=xenomai-forge.git;a=commit;h=b8eed0ef7d578c9dc5932b9c448dde62bf7bb7e5 Author: Philippe Gerum Date: Wed Jun 19 23:04:09 2013 +0200 kernel/cobalt/timer: drop support for hash-based indexing We don't need two highly scalable indexing methods for timers, this is uselessly confusing to users and brings no obvious upside. Let's keep the method based on a binary heap, and drop the timer wheel (aka hash-based indexing) which has stricter constraints for delivering best performances. --- include/cobalt/kernel/timer.h | 120 - kernel/cobalt/Kconfig | 20 --- 2 files changed, 0 insertions(+), 140 deletions(-) diff --git a/include/cobalt/kernel/timer.h b/include/cobalt/kernel/timer.h index 310630a..945d96f 100644 --- a/include/cobalt/kernel/timer.h +++ b/include/cobalt/kernel/timer.h @@ -136,126 +136,6 @@ typedef struct {} xntimerq_it_t; #define xntimerq_it_begin(q, i) ((void) (i), bheap_gethead(q)) #define xntimerq_it_next(q, i, h) ((void) (i), bheap_next((q),(h))) -#elif defined(CONFIG_XENO_OPT_TIMER_WHEEL) - -typedef struct xntlholder xntimerh_t; - -#define xntimerh_date(h) xntlholder_date(h) -#define xntimerh_prio(h) xntlholder_prio(h) -#define xntimerh_init(h) do { } while (0) - -typedef struct xntimerq { - unsigned int date_shift; - unsigned long long next_shot; - unsigned long long shot_wrap; - struct list_head bucket[XNTIMER_WHEELSIZE]; -} xntimerq_t; - -typedef struct xntimerq_it { - unsigned int bucket; -} xntimerq_it_t; - -static inline void xntimerq_init(xntimerq_t *q) -{ - unsigned long long step_tsc; - unsigned int i; - - step_tsc = xnarch_ns_to_tsc(CONFIG_XENO_OPT_TIMER_WHEEL_STEP); - /* q->date_shift = fls(step_tsc); */ - for (q->date_shift = 0; (1 << q->date_shift) < step_tsc; q->date_shift++) - ; - q->next_shot = q->shot_wrap = ((~0ULL) >> q->date_shift) + 1; - for (i = 0; i < ARRAY_SIZE(q->bucket); i++) - xntlist_init(&q->bucket[i]); -} - -#define xntimerq_destroy(q)do { } while (0) - -static inline struct xntlholder *xntimerq_head(xntimerq_t *q) -{ - unsigned bucket = ((unsigned) q->next_shot) & XNTIMER_WHEELMASK; - struct xntlholder *result; - unsigned i; - - if (q->next_shot == q->shot_wrap) - return NULL; - - result = xntlist_head(&q->bucket[bucket]); - - if (result && (xntlholder_date(result) >> q->date_shift) == q->next_shot) - return result; - - /* We could not find the next timer in the first bucket, iterate over - the other buckets. */ - for (i = (bucket + 1) & XNTIMER_WHEELMASK ; -i != bucket; i = (i + 1) & XNTIMER_WHEELMASK) { - struct xntlholder *candidate = xntlist_head(&q->bucket[i]); - - if(++q->next_shot == q->shot_wrap) - q->next_shot = 0; - - if (!candidate) - continue; - - if ((xntlholder_date(candidate) >> q->date_shift) == q->next_shot) - return candidate; - - if (!result || (xnsticks_t) (xntlholder_date(candidate) -- xntlholder_date(result)) < 0) - result = candidate; - } - - if (result) - q->next_shot = (xntlholder_date(result) >> q->date_shift); - else - q->next_shot = q->shot_wrap; - return result; -} - -static inline void xntimerq_insert(xntimerq_t *q, xntimerh_t *h) -{ - unsigned long long shifted_date = xntlholder_date(h) >> q->date_shift; - unsigned int bucket = ((unsigned int)shifted_date) & XNTIMER_WHEELMASK; - - if ((long long) (shifted_date - q->next_shot) < 0) - q->next_shot = shifted_date; - - xntlist_insert(&q->bucket[bucket], h); -} - -static inline void xntimerq_remove(xntimerq_t *q, xntimerh_t *h) -{ - unsigned long long shifted_date = xntlholder_date(h) >> q->date_shift; - unsigned bucket = ((unsigned) shifted_date) & XNTIMER_WHEELMASK; - - xntlist_remove(&q->bucket[bucket], h); - /* Do not attempt to update q->next_shot, xntimerq_head will recover. */ -} - -static inline xntimerh_t *xntimerq_it_begin(xntimerq_t *q, xntimerq_it_t *it) -{ - xntimerh_t *holder = NULL; - - for (it->bucket = 0; it->bucket < XNTIMER_WHEELSIZE; it->bucket++) - if ((holder = xntlist_head(&q->bucket[it->bucket]))) - break; - - return holder; -} - -static inline xntimerh_t * -xntimerq_it_next(xntimerq_t *q, xntimerq_it_t *it, xntimerh_t *holder) -{ - xntimerh_t *next = xntlist_next(&q->bucket[it->bucket], holder); - - if (!next) - for(it->bucket++; it->bucket < XNTIMER_WHEELSIZE; it->bucket+
[Xenomai-git] Philippe Gerum : kernel/cobalt/timer: drop support for hash-based indexing
Module: xenomai-forge Branch: next Commit: b8eed0ef7d578c9dc5932b9c448dde62bf7bb7e5 URL: http://git.xenomai.org/?p=xenomai-forge.git;a=commit;h=b8eed0ef7d578c9dc5932b9c448dde62bf7bb7e5 Author: Philippe Gerum Date: Wed Jun 19 23:04:09 2013 +0200 kernel/cobalt/timer: drop support for hash-based indexing We don't need two highly scalable indexing methods for timers, this is uselessly confusing to users and brings no obvious upside. Let's keep the method based on a binary heap, and drop the timer wheel (aka hash-based indexing) which has stricter constraints for delivering best performances. --- include/cobalt/kernel/timer.h | 120 - kernel/cobalt/Kconfig | 20 --- 2 files changed, 0 insertions(+), 140 deletions(-) diff --git a/include/cobalt/kernel/timer.h b/include/cobalt/kernel/timer.h index 310630a..945d96f 100644 --- a/include/cobalt/kernel/timer.h +++ b/include/cobalt/kernel/timer.h @@ -136,126 +136,6 @@ typedef struct {} xntimerq_it_t; #define xntimerq_it_begin(q, i) ((void) (i), bheap_gethead(q)) #define xntimerq_it_next(q, i, h) ((void) (i), bheap_next((q),(h))) -#elif defined(CONFIG_XENO_OPT_TIMER_WHEEL) - -typedef struct xntlholder xntimerh_t; - -#define xntimerh_date(h) xntlholder_date(h) -#define xntimerh_prio(h) xntlholder_prio(h) -#define xntimerh_init(h) do { } while (0) - -typedef struct xntimerq { - unsigned int date_shift; - unsigned long long next_shot; - unsigned long long shot_wrap; - struct list_head bucket[XNTIMER_WHEELSIZE]; -} xntimerq_t; - -typedef struct xntimerq_it { - unsigned int bucket; -} xntimerq_it_t; - -static inline void xntimerq_init(xntimerq_t *q) -{ - unsigned long long step_tsc; - unsigned int i; - - step_tsc = xnarch_ns_to_tsc(CONFIG_XENO_OPT_TIMER_WHEEL_STEP); - /* q->date_shift = fls(step_tsc); */ - for (q->date_shift = 0; (1 << q->date_shift) < step_tsc; q->date_shift++) - ; - q->next_shot = q->shot_wrap = ((~0ULL) >> q->date_shift) + 1; - for (i = 0; i < ARRAY_SIZE(q->bucket); i++) - xntlist_init(&q->bucket[i]); -} - -#define xntimerq_destroy(q)do { } while (0) - -static inline struct xntlholder *xntimerq_head(xntimerq_t *q) -{ - unsigned bucket = ((unsigned) q->next_shot) & XNTIMER_WHEELMASK; - struct xntlholder *result; - unsigned i; - - if (q->next_shot == q->shot_wrap) - return NULL; - - result = xntlist_head(&q->bucket[bucket]); - - if (result && (xntlholder_date(result) >> q->date_shift) == q->next_shot) - return result; - - /* We could not find the next timer in the first bucket, iterate over - the other buckets. */ - for (i = (bucket + 1) & XNTIMER_WHEELMASK ; -i != bucket; i = (i + 1) & XNTIMER_WHEELMASK) { - struct xntlholder *candidate = xntlist_head(&q->bucket[i]); - - if(++q->next_shot == q->shot_wrap) - q->next_shot = 0; - - if (!candidate) - continue; - - if ((xntlholder_date(candidate) >> q->date_shift) == q->next_shot) - return candidate; - - if (!result || (xnsticks_t) (xntlholder_date(candidate) -- xntlholder_date(result)) < 0) - result = candidate; - } - - if (result) - q->next_shot = (xntlholder_date(result) >> q->date_shift); - else - q->next_shot = q->shot_wrap; - return result; -} - -static inline void xntimerq_insert(xntimerq_t *q, xntimerh_t *h) -{ - unsigned long long shifted_date = xntlholder_date(h) >> q->date_shift; - unsigned int bucket = ((unsigned int)shifted_date) & XNTIMER_WHEELMASK; - - if ((long long) (shifted_date - q->next_shot) < 0) - q->next_shot = shifted_date; - - xntlist_insert(&q->bucket[bucket], h); -} - -static inline void xntimerq_remove(xntimerq_t *q, xntimerh_t *h) -{ - unsigned long long shifted_date = xntlholder_date(h) >> q->date_shift; - unsigned bucket = ((unsigned) shifted_date) & XNTIMER_WHEELMASK; - - xntlist_remove(&q->bucket[bucket], h); - /* Do not attempt to update q->next_shot, xntimerq_head will recover. */ -} - -static inline xntimerh_t *xntimerq_it_begin(xntimerq_t *q, xntimerq_it_t *it) -{ - xntimerh_t *holder = NULL; - - for (it->bucket = 0; it->bucket < XNTIMER_WHEELSIZE; it->bucket++) - if ((holder = xntlist_head(&q->bucket[it->bucket]))) - break; - - return holder; -} - -static inline xntimerh_t * -xntimerq_it_next(xntimerq_t *q, xntimerq_it_t *it, xntimerh_t *holder) -{ - xntimerh_t *next = xntlist_next(&q->bucket[it->bucket], holder); - - if (!next) - for(it->bucket++; it->bucket < XNTIMER_WHEELSIZE; it->bucket++)