Module: xenomai-2.6
Branch: master
Commit: 8e1e2e37f9ee510f19417ea4ad873fdd560918fe
URL:
http://git.xenomai.org/?p=xenomai-2.6.git;a=commit;h=8e1e2e37f9ee510f19417ea4ad873fdd560918fe
Author: Gilles Chanteperdrix <gilles.chanteperd...@xenomai.org>
Date: Sun Apr 3 23:57:31 2016 +0200
nucleus/timers: fix the timers situation
Remove bheap and timerwheel timer list structures, as they had been
broken by commit b51bb27b3e73e68b9d63a00b11596229ebb31a67. Introduce
rbtree, and use it instead for large number of timers, make it the
default on x86_64 so that it gets tested.
---
include/nucleus/Makefile.am | 1 -
include/nucleus/bheap.h | 242 -------------------------------------------
include/nucleus/timer.h | 163 +++++++----------------------
ksrc/nucleus/Kconfig | 35 +------
ksrc/nucleus/timer.c | 41 ++++++--
5 files changed, 78 insertions(+), 404 deletions(-)
diff --git a/include/nucleus/Makefile.am b/include/nucleus/Makefile.am
index 7af212a..00d2654 100644
--- a/include/nucleus/Makefile.am
+++ b/include/nucleus/Makefile.am
@@ -2,7 +2,6 @@ includesubdir = $(includedir)/nucleus
includesub_HEADERS = \
assert.h \
- bheap.h \
bufd.h \
compiler.h \
heap.h \
diff --git a/include/nucleus/bheap.h b/include/nucleus/bheap.h
deleted file mode 100644
index 3b1ba78..0000000
--- a/include/nucleus/bheap.h
+++ /dev/null
@@ -1,242 +0,0 @@
-/*
- * Copyright (C) 2006 Gilles Chanteperdrix <gilles.chanteperd...@xenomai.org>
- *
- * Xenomai is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published
- * by the Free Software Foundation; either version 2 of the License,
- * or (at your option) any later version.
- *
- * Xenomai is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with Xenomai; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
- * 02111-1307, USA.
- */
-
-#ifndef _XENO_NUCLEUS_BHEAP_H
-#define _XENO_NUCLEUS_BHEAP_H
-
-#include <nucleus/compiler.h>
-
-/* debug support */
-#include <nucleus/assert.h>
-
-/* Priority queue implementation, using a binary heap. */
-
-typedef unsigned long long bheap_key_t;
-
-typedef struct bheaph {
- bheap_key_t key;
- unsigned prio;
- unsigned pos;
-} bheaph_t;
-
-#define bheaph_init(holder) do { } while (0)
-#define bheaph_key(holder) ((holder)->key)
-#define bheaph_prio(holder) ((holder)->prio)
-#define bheaph_pos(holder) ((holder)->pos)
-#define bheaph_lt(h1, h2) ((long long) ((h1)->key - (h2)->key) < 0 ||
\
- ((h1)->key == (h2)->key && \
- (h1)->prio > (h2)->prio))
-
-typedef struct bheap {
- unsigned sz;
- unsigned last;
- bheaph_t *elems[];
-} bheap_t;
-
-#define DECLARE_BHEAP_CONTAINER(name, sz) \
- struct { \
- bheap_t bheap; \
- bheaph_t *elems[sz + 1]; \
- } name
-
-/* Check the binary heap invariant. */
-static inline int bheap_ordered(bheap_t *heap)
-{
- unsigned i;
- for (i = 2; i < heap->last; i++)
- if (bheaph_lt(heap->elems[i], heap->elems[i / 2]))
- return 0;
- return 1;
-}
-
-#define BHEAP_CHECK(heap) \
- XENO_BUGON(QUEUES, ((heap)->sz == 0) || !bheap_ordered(heap))
-
-#define bheap_gethead(heap) \
- ({ \
- bheap_t *_bheap = &(heap)->bheap; \
- BHEAP_CHECK(_bheap); \
- __internal_bheap_gethead(_bheap); \
- })
-
-static inline bheaph_t *__internal_bheap_gethead(bheap_t *heap)
-{
- if (heap->last == 1)
- return NULL;
-
- return heap->elems[1];
-}
-
-#define bheap_next(heap, holder) \
- ({ \
- bheap_t *_bheap = &(heap)->bheap; \
- BHEAP_CHECK(_bheap); \
- __internal_bheap_next(_bheap, holder); \
- })
-
-static inline bheaph_t *__internal_bheap_next(bheap_t *heap, bheaph_t *holder)
-{
- unsigned pos;
-
- if (unlikely(bheaph_pos(holder) >= heap->last
- || heap->elems[bheaph_pos(holder)] != holder))
- return (bheaph_t *) ERR_PTR(-EINVAL);
-
- pos = bheaph_pos(holder) + 1;
-
- return likely(pos < heap->last) ? heap->elems[pos] : NULL;
-}
-
-static inline bheaph_t *bheaph_parent(bheap_t *heap, bheaph_t *holder)
-{
- const unsigned pos = holder->pos;
-
- return likely(pos > 1) ? heap->elems[pos / 2] : NULL;
-}
-
-static inline bheaph_t *bheaph_child(bheap_t *heap, bheaph_t *holder, int side)
-{
- const unsigned pos = 2 * holder->pos + side;
-
- return likely(pos < heap->last) ? heap->elems[pos] : NULL;
-}
-
-#define bheap_init(heap, sz) __internal_bheap_init(&(heap)->bheap, sz)
-
-static inline void __internal_bheap_init(bheap_t *heap, unsigned sz)
-{
- heap->sz = sz;
- heap->last = 1;
-}
-
-#define bheap_destroy(heap) __internal_bheap_destroy(&(heap)->bheap)
-
-static inline void __internal_bheap_destroy(bheap_t *heap)
-{
- heap->sz = 0;
- heap->last = 1;
-}
-
-static inline void bheap_swap(bheap_t *heap, bheaph_t *h1, bheaph_t *h2)
-{
- const unsigned pos2 = bheaph_pos(h2);
-
- heap->elems[bheaph_pos(h1)] = h2;
- bheaph_pos(h2) = bheaph_pos(h1);
- heap->elems[pos2] = h1;
- bheaph_pos(h1) = pos2;
-}
-
-static inline void bheap_up(bheap_t *heap, bheaph_t *holder)
-{
- bheaph_t *parent;
-
- while ((parent = bheaph_parent(heap, holder)) && bheaph_lt(holder,
parent))
- bheap_swap(heap, holder, parent);
-}
-
-static inline void bheap_down(bheap_t *heap, bheaph_t *holder)
-{
- bheaph_t *left, *right, *minchild;
-
- for (;;) {
- left = bheaph_child(heap, holder, 0);
- right = bheaph_child(heap, holder, 1);
-
- if (left && right)
- minchild = bheaph_lt(left, right) ? left : right;
- else
- minchild = left ?: right;
-
- if (!minchild || bheaph_lt(holder, minchild))
- break;
-
- bheap_swap(heap, minchild, holder);
- }
-}
-
-#define bheap_insert(heap, holder) \
- ({ \
- bheap_t *_bheap = &(heap)->bheap; \
- BHEAP_CHECK(_bheap); \
- __internal_bheap_insert(_bheap, holder); \
- })
-
-static inline int __internal_bheap_insert(bheap_t *heap, bheaph_t *holder)
-{
- if (heap->last == heap->sz + 1)
- return EBUSY;
-
- heap->elems[heap->last] = holder;
- bheaph_pos(holder) = heap->last;
- ++heap->last;
- bheap_up(heap, holder);
- return 0;
-}
-
-#define bheap_delete(heap, holder) \
- ({ \
- bheap_t *_bheap = &(heap)->bheap; \
- BHEAP_CHECK(_bheap); \
- __internal_bheap_delete(_bheap, holder); \
- })
-
-static inline int __internal_bheap_delete(bheap_t *heap, bheaph_t *holder)
-{
- bheaph_t *lasth;
-
- if (unlikely(bheaph_pos(holder) >= heap->last
- || heap->elems[bheaph_pos(holder)] != holder))
- return EINVAL;
-
- --heap->last;
- if (heap->last != bheaph_pos(holder)) {
- bheaph_t *parent;
- lasth = heap->elems[heap->last];
- heap->elems[bheaph_pos(holder)] = lasth;
- bheaph_pos(lasth) = bheaph_pos(holder);
- if ((parent = bheaph_parent(heap, lasth)) && bheaph_lt(lasth,
parent))
- bheap_up(heap, lasth);
- else
- bheap_down(heap, lasth);
- }
-
- return 0;
-}
-
-#define bheap_get(heap) \
- ({ \
- bheap_t *_bheap = &(heap)->bheap; \
- BHEAP_CHECK(_bheap); \
- __internal_bheap_get(_bheap, holder); \
- })
-
-static inline bheaph_t *__internal_bheap_get(bheap_t *heap)
-{
- bheaph_t *holder = __internal_bheap_gethead(heap);
-
- if (!holder)
- return NULL;
-
- __internal_bheap_delete(heap, holder);
-
- return holder;
-}
-
-#endif /* _XENO_NUCLEUS_BHEAP_H */
diff --git a/include/nucleus/timer.h b/include/nucleus/timer.h
index ef05822..bced14f 100644
--- a/include/nucleus/timer.h
+++ b/include/nucleus/timer.h
@@ -83,6 +83,8 @@ typedef struct {
!_h ? NULL : link2tlholder(_h); \
})
+#define xntlist_second(q, h) xntlist_next((q),(h))
+
static inline void xntlist_insert(xnqueue_t *q, xntlholder_t *holder)
{
xnholder_t *p;
@@ -103,147 +105,59 @@ static inline void xntlist_insert(xnqueue_t *q,
xntlholder_t *holder)
#define xntlist_remove(q, h) removeq((q),&(h)->link)
-#if defined(CONFIG_XENO_OPT_TIMER_HEAP)
-
-#include <nucleus/bheap.h>
-
-typedef bheaph_t xntimerh_t;
-
-#define xntimerh_date(h) bheaph_key(h)
-#define xntimerh_prio(h) bheaph_prio(h)
-#define xntimerh_init(h) bheaph_init(h)
-
-typedef DECLARE_BHEAP_CONTAINER(xntimerq_t,
CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY);
+#if defined(CONFIG_XENO_OPT_TIMER_RBTREE)
-#define xntimerq_init(q) bheap_init((q),
CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY)
-#define xntimerq_destroy(q) bheap_destroy(q)
-#define xntimerq_head(q) bheap_gethead(q)
-#define xntimerq_insert(q, h) bheap_insert((q),(h))
-#define xntimerq_remove(q, h) bheap_delete((q),(h))
+#include <linux/rbtree.h>
-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 xntlholder_t xntimerh_t;
+typedef struct {
+ unsigned long long date;
+ unsigned prio;
+ struct rb_node link;
+} xntimerh_t;
-#define xntimerh_date(h) xntlholder_date(h)
-#define xntimerh_prio(h) xntlholder_prio(h)
-#define xntimerh_init(h) xntlholder_init(h)
+#define xntimerh_date(h) ((h)->date)
+#define xntimerh_prio(h) ((h)->prio)
+#define xntimerh_init(h) do { } while (0)
-typedef struct xntimerq {
- unsigned date_shift;
- unsigned long long next_shot;
- unsigned long long shot_wrap;
- xnqueue_t bucket[XNTIMER_WHEELSIZE];
+typedef struct {
+ struct rb_root root;
+ xntimerh_t *head;
} xntimerq_t;
-typedef struct xntimerq_it {
- unsigned bucket;
-} xntimerq_it_t;
-
-static inline void xntimerq_init(xntimerq_t *q)
-{
- unsigned long long step_tsc;
- unsigned 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 < sizeof(q->bucket)/sizeof(xnqueue_t); i++)
- xntlist_init(&q->bucket[i]);
-}
-
-#define xntimerq_destroy(q) do { } while (0)
-
-static inline xntlholder_t *xntimerq_head(xntimerq_t *q)
-{
- unsigned bucket = ((unsigned) q->next_shot) & XNTIMER_WHEELMASK;
- xntlholder_t *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) {
- xntlholder_t *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;
+#define xntimerq_init(q) \
+ ({ \
+ xntimerq_t *_q = (q); \
+ _q->root = RB_ROOT; \
+ _q->head = NULL; \
+ })
- if (!result || (xnsticks_t) (xntlholder_date(candidate)
- - xntlholder_date(result)) < 0)
- result = candidate;
- }
+#define xntimerq_destroy(q) do { } while (0)
+#define xntimerq_empty(q) ((q)->head != NULL)
- 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 bucket = ((unsigned) shifted_date) & XNTIMER_WHEELMASK;
+#define xntimerq_head(q) ((q)->head)
- if ((long long) (shifted_date - q->next_shot) < 0)
- q->next_shot = shifted_date;
- xntlist_insert(&q->bucket[bucket], h);
-}
+#define xntimerq_next(q, h) \
+ ({ \
+ struct rb_node *_node = rb_next(&(h)->link); \
+ _node ? (container_of(_node, xntimerh_t, link)) : NULL; \
+ })
-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;
+#define xntimerq_second(q, h) xntimerq_next(q, h)
- xntlist_remove(&q->bucket[bucket], h);
- /* Do not attempt to update q->next_shot, xntimerq_head will recover. */
-}
+void xntimerq_insert(xntimerq_t *q, xntimerh_t *holder);
-static inline xntimerh_t *xntimerq_it_begin(xntimerq_t *q, xntimerq_it_t *it)
+static inline void xntimerq_remove(xntimerq_t *q, xntimerh_t *holder)
{
- xntimerh_t *holder = NULL;
+ if (holder == q->head)
+ q->head = xntimerq_second(q, holder);
- for (it->bucket = 0; it->bucket < XNTIMER_WHEELSIZE; it->bucket++)
- if ((holder = xntlist_head(&q->bucket[it->bucket])))
- break;
-
- return holder;
+ rb_erase(&holder->link, &q->root);
}
-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;
+typedef struct { } xntimerq_it_t;
- return next;
-}
+#define xntimerq_it_begin(q,i) ((void) (i), xntimerq_head(q))
+#define xntimerq_it_next(q,i,h) ((void) (i), xntimerq_next((q),(h)))
#else /* CONFIG_XENO_OPT_TIMER_LIST */
@@ -258,6 +172,7 @@ typedef xnqueue_t xntimerq_t;
#define xntimerq_init(q) xntlist_init(q)
#define xntimerq_destroy(q) do { } while (0)
#define xntimerq_head(q) xntlist_head(q)
+#define xntimerq_second(q,h) xntlist_second((q),(h))
#define xntimerq_insert(q,h) xntlist_insert((q),(h))
#define xntimerq_remove(q, h) xntlist_remove((q),(h))
diff --git a/ksrc/nucleus/Kconfig b/ksrc/nucleus/Kconfig
index 2f2f6f6..280f227 100644
--- a/ksrc/nucleus/Kconfig
+++ b/ksrc/nucleus/Kconfig
@@ -447,7 +447,8 @@ config XENO_OPT_SCALABLE_SCHED
choice
prompt "Timer indexing method"
- default XENO_OPT_TIMER_LIST
+ default XENO_OPT_TIMER_LIST if !X86_64
+ default XENO_OPT_TIMER_RBTREE if X86_64
help
This option allows to select the underlying data structure
@@ -464,44 +465,16 @@ config XENO_OPT_TIMER_LIST
particularly efficient when only a few timers (< 10) may be
concurrently outstanding at any point in time.
-config XENO_OPT_TIMER_HEAP
+config XENO_OPT_TIMER_RBTREE
bool "Tree"
help
- Use a binary heap. This data structure is efficient when a
+ Use a red-black tree. This data structure is efficient when a
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
- int "Binary heap capacity"
- depends on XENO_OPT_TIMER_HEAP
- default 256
- help
-
- 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.
-
endmenu
endif
diff --git a/ksrc/nucleus/timer.c b/ksrc/nucleus/timer.c
index 0365759..7dd0940 100644
--- a/ksrc/nucleus/timer.c
+++ b/ksrc/nucleus/timer.c
@@ -59,7 +59,6 @@ void xntimer_next_local_shot(xnsched_t *sched)
{
struct xntimer *timer;
xnsticks_t delay;
- xntimerq_it_t it;
xntimerh_t *h;
/*
@@ -70,7 +69,7 @@ void xntimer_next_local_shot(xnsched_t *sched)
if (testbits(sched->status, XNINTCK))
return;
- h = xntimerq_it_begin(&sched->timerqueue, &it);
+ h = xntimerq_head(&sched->timerqueue);
if (h == NULL)
return;
@@ -99,7 +98,7 @@ void xntimer_next_local_shot(xnsched_t *sched)
if (unlikely(timer == &sched->htimer)) {
if (xnsched_resched_p(sched) ||
!xnthread_test_state(sched->curr, XNROOT)) {
- h = xntimerq_it_next(&sched->timerqueue, &it, h);
+ h = xntimerq_second(&sched->timerqueue, h);
if (h) {
__setbits(sched->lflags, XNHDEFER);
timer = aplink2timer(h);
@@ -123,15 +122,14 @@ void xntimer_next_local_shot(xnsched_t *sched)
static inline int xntimer_heading_p(struct xntimer *timer)
{
struct xnsched *sched = timer->sched;
- xntimerq_it_t it;
xntimerh_t *h;
- h = xntimerq_it_begin(&sched->timerqueue, &it);
+ h = xntimerq_head(&sched->timerqueue);
if (h == &timer->aplink)
return 1;
if (testbits(sched->lflags, XNHDEFER)) {
- h = xntimerq_it_next(&sched->timerqueue, &it, h);
+ h = xntimerq_second(&sched->timerqueue, h);
if (h == &timer->aplink)
return 1;
}
@@ -1165,4 +1163,35 @@ void xntimer_cleanup_proc(void)
#endif /* CONFIG_XENO_OPT_VFILE */
+#if defined(CONFIG_XENO_OPT_TIMER_RBTREE)
+static inline bool xntimerh_is_lt(xntimerh_t *left, xntimerh_t *right)
+{
+ return left->date < right->date
+ || (left->date == right->date && left->prio > right->prio);
+}
+
+void xntimerq_insert(xntimerq_t *q, xntimerh_t *holder)
+{
+ struct rb_node **new = &q->root.rb_node, *parent = NULL;
+
+ if (!q->head)
+ q->head = holder;
+ else if (xntimerh_is_lt(holder, q->head)) {
+ parent = &q->head->link;
+ new = &parent->rb_left;
+ q->head = holder;
+ } else while (*new) {
+ xntimerh_t *i = container_of(*new, xntimerh_t, link);
+
+ parent = *new;
+ if (xntimerh_is_lt(holder, i))
+ new = &((*new)->rb_left);
+ else
+ new = &((*new)->rb_right);
+ }
+
+ rb_link_node(&holder->link, parent, new);
+ rb_insert_color(&holder->link, &q->root);
+}
+#endif
/*@}*/
_______________________________________________
Xenomai-git mailing list
Xenomai-git@xenomai.org
https://xenomai.org/mailman/listinfo/xenomai-git
