Module: xenomai-forge
Branch: next
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

Reply via email to