Module: xenomai-forge
Branch: master
Commit: b8eed0ef7d578c9dc5932b9c448dde62bf7bb7e5
URL:
http://git.xenomai.org/?p=xenomai-forge.git;a=commit;h=b8eed0ef7d578c9dc5932b9c448dde62bf7bb7e5
Author: Philippe Gerum <r...@xenomai.org>
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++)
- if ((next = xntlist_head(&q->bucket[it->bucket])))
- break;
-
- return next;
-}
-
#else /* CONFIG_XENO_OPT_TIMER_LIST */
typedef struct xntlholder xntimerh_t;
diff --git a/kernel/cobalt/Kconfig b/kernel/cobalt/Kconfig
index 8b45d8c..af7511e 100644
--- a/kernel/cobalt/Kconfig
+++ b/kernel/cobalt/Kconfig
@@ -188,17 +188,6 @@ config XENO_OPT_TIMER_HEAP
high number of software timers may be concurrently
outstanding at any point in time.
-config XENO_OPT_TIMER_WHEEL
- bool "Hash"
- help
-
- Use a hash table. Timers operations using this data structure
- should have an O(1) complexity if the timers follow two
- conditions:
- - timers expiration dates do not collide too much;
- - there is at least one periodic timer using a period near
- the wheel step (around 100000 ns by default).
-
endchoice
config XENO_OPT_TIMER_HEAP_CAPACITY
@@ -209,15 +198,6 @@ config XENO_OPT_TIMER_HEAP_CAPACITY
Set the maximum number of timers in the nucleus timers list.
-config XENO_OPT_TIMER_WHEEL_STEP
- int "Timer wheel step"
- depends on XENO_OPT_TIMER_WHEEL
- default 100000
- help
-
- Set the duration in ns of a timer wheel step. At each step,
- the timer wheel use the next hash bucket.
-
config XENO_OPT_HOSTRT
depends on IPIPE_HAVE_HOSTRT
def_bool y
_______________________________________________
Xenomai-git mailing list
Xenomai-git@xenomai.org
http://www.xenomai.org/mailman/listinfo/xenomai-git
