Module: xenomai-gch
Branch: next
Commit: 0392e782f490d3d0a5083eaa7ccb1ae5e5d0cd5f
URL:    
http://git.xenomai.org/?p=xenomai-gch.git;a=commit;h=0392e782f490d3d0a5083eaa7ccb1ae5e5d0cd5f

Author: Gilles Chanteperdrix <gilles.chanteperd...@xenomai.org>
Date:   Sun Apr  3 22:47:55 2016 +0200

cobalt/timer: replace bheap with rbtree

make rbtree the default on x86_64, so that it gets tested.

---

 include/cobalt/kernel/Makefile.am |    1 -
 include/cobalt/kernel/bheap.h     |  266 -------------------------------------
 include/cobalt/kernel/timer.h     |   80 ++++++-----
 kernel/cobalt/Kconfig             |   14 +-
 kernel/cobalt/clock.c             |    2 +-
 kernel/cobalt/timer.c             |   34 ++++-
 6 files changed, 87 insertions(+), 310 deletions(-)

diff --git a/include/cobalt/kernel/Makefile.am 
b/include/cobalt/kernel/Makefile.am
index 757675a..4d95702 100644
--- a/include/cobalt/kernel/Makefile.am
+++ b/include/cobalt/kernel/Makefile.am
@@ -4,7 +4,6 @@ noinst_HEADERS =        \
        apc.h           \
        arith.h         \
        assert.h        \
-       bheap.h         \
        bufd.h          \
        clock.h         \
        compat.h        \
diff --git a/include/cobalt/kernel/bheap.h b/include/cobalt/kernel/bheap.h
deleted file mode 100644
index 4c05bb4..0000000
--- a/include/cobalt/kernel/bheap.h
+++ /dev/null
@@ -1,266 +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 _COBALT_KERNEL_BHEAP_H
-#define _COBALT_KERNEL_BHEAP_H
-
-/* debug support */
-#include <cobalt/kernel/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[]; /* only padding, indexing starts at 1 */
-} 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_BUG_ON(COBALT, ((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_second(heap)                             \
-       ({                                              \
-               bheap_t *_bheap = &(heap)->bheap;       \
-               BHEAP_CHECK(_bheap);                    \
-               __internal_bheap_second(_bheap);        \
-       })
-
-#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;
-}
-
-static inline bheaph_t *__internal_bheap_second(bheap_t *heap)
-{
-       bheaph_t *left, *right, *first = __internal_bheap_gethead(heap);
- 
-       left = bheaph_child(heap, first, 0);
-       right = bheaph_child(heap, first, 1);
- 
-       if (!left || !right)
-               return left ?: right;
- 
-       return bheaph_lt(left, right) ? left : right;
-}
- 
-#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;
-}
-
-#define bheap_empty(heap)                              \
-       ({                                              \
-               bheap_t *_bheap = &(heap)->bheap;       \
-               BHEAP_CHECK(_bheap);                    \
-               _bheap->last == 1;                      \
-       })
-
-#endif /* _COBALT_KERNEL_BHEAP_H */
diff --git a/include/cobalt/kernel/timer.h b/include/cobalt/kernel/timer.h
index 5868fcb..9f85985 100644
--- a/include/cobalt/kernel/timer.h
+++ b/include/cobalt/kernel/timer.h
@@ -101,15 +101,9 @@ static inline struct xntlholder *xntlist_next(struct 
list_head *q,
        return list_entry(h->link.next, struct xntlholder, link);
 }
 
-static inline struct xntlholder *xntlist_second(struct list_head *q)
+static inline struct xntlholder *xntlist_second(struct list_head *q,
+       struct xntlholder *h)
 {
-       struct xntlholder *h;
-
-       if (list_empty(q))
-               return NULL;
-
-       h = list_first_entry(q, struct xntlholder, link);
-
        return xntlist_next(q, h);
 }
 
@@ -142,35 +136,59 @@ static inline void xntlist_insert(struct list_head *q, 
struct xntlholder *holder
                list_del(&(h)->link);           \
        } while (0)
 
-#if defined(CONFIG_XENO_OPT_TIMER_HEAP)
+#if defined(CONFIG_XENO_OPT_TIMER_RBTREE)
 
-#include <cobalt/kernel/bheap.h>
+#include <linux/rbtree.h>
 
-typedef bheaph_t xntimerh_t;
+typedef struct {
+       unsigned long long date;
+       unsigned prio;
+       struct rb_node link;
+} xntimerh_t;
 
-#define xntimerh_date(h)          bheaph_key(h)
-#define xntimerh_prio(h)          bheaph_prio(h)
-#define xntimerh_init(h)          bheaph_init(h)
+#define xntimerh_date(h) ((h)->date)
+#define xntimerh_prio(h) ((h)->prio)
+#define xntimerh_init(h) do { } while (0)
 
-typedef DECLARE_BHEAP_CONTAINER(xntimerq_t, 
CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY);
+typedef struct {
+       struct rb_root root;
+       xntimerh_t *head;
+} xntimerq_t;
 
-#define xntimerq_init(q)          bheap_init((q), 
CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY)
-#define xntimerq_destroy(q)       bheap_destroy(q)
-#define xntimerq_empty(q)         bheap_empty(q)
-#define xntimerq_head(q)          bheap_gethead(q)
-#define xntimerq_second(q)        bheap_second(q)
-#define xntimerq_insert(q, h)     bheap_insert((q),(h))
-#define xntimerq_remove(q, h)     bheap_delete((q),(h))
+#define xntimerq_init(q)                       \
+       ({                                      \
+               xntimerq_t *_q = (q);           \
+               _q->root = RB_ROOT;             \
+               _q->head = NULL;                \
+       })
 
-typedef struct {} xntimerq_it_t;
+#define xntimerq_destroy(q) do { } while (0)
+#define xntimerq_empty(q) ((q)->head != NULL)
 
-/*
- * BIG FAT WARNING: the iterator does NOT guarantee any particular
- * order when returning elements (typically, items may be returned in
- * random timestamp order).
- */
-#define xntimerq_it_begin(q, i)   ((void) (i), bheap_gethead(q))
-#define xntimerq_it_next(q, i, h) ((void) (i), bheap_next((q),(h)))
+#define xntimerq_head(q) ((q)->head)
+
+#define xntimerq_next(q, h)                                            \
+       ({                                                              \
+               struct rb_node *_node = rb_next(&(h)->link);            \
+               _node ? (container_of(_node, xntimerh_t, link)) : NULL; \
+       })
+
+#define xntimerq_second(q, h) xntimerq_next(q, h)
+
+void xntimerq_insert(xntimerq_t *q, xntimerh_t *holder);
+
+static inline void xntimerq_remove(xntimerq_t *q, xntimerh_t *holder)
+{
+       if (holder == q->head)
+               q->head = xntimerq_second(q, holder);
+
+       rb_erase(&holder->link, &q->root);
+}
+
+typedef struct { } xntimerq_it_t;
+
+#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 */
 
@@ -186,7 +204,7 @@ typedef struct list_head xntimerq_t;
 #define xntimerq_destroy(q)     do { } while (0)
 #define xntimerq_empty(q)       xntlist_empty(q)
 #define xntimerq_head(q)        xntlist_head(q)
-#define xntimerq_second(q)      xntlist_second(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/kernel/cobalt/Kconfig b/kernel/cobalt/Kconfig
index 24f09e8..1d7c7cc 100644
--- a/kernel/cobalt/Kconfig
+++ b/kernel/cobalt/Kconfig
@@ -177,7 +177,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
        which is going to be used for ordering the outstanding
@@ -190,22 +191,15 @@ 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.
 
 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 the binary heap can index.
-
 config XENO_OPT_HOSTRT
        depends on IPIPE_HAVE_HOSTRT
        def_bool y
diff --git a/kernel/cobalt/clock.c b/kernel/cobalt/clock.c
index a696f0e..1794f0e 100644
--- a/kernel/cobalt/clock.c
+++ b/kernel/cobalt/clock.c
@@ -167,7 +167,7 @@ void xnclock_core_local_shot(struct xnsched *sched)
        if (unlikely(timer == &sched->htimer)) {
                if (xnsched_resched_p(sched) ||
                    !xnthread_test_state(sched->curr, XNROOT)) {
-                       h = xntimerq_second(&tmd->q);
+                       h = xntimerq_second(&tmd->q, h);
                        if (h) {
                                sched->lflags |= XNHDEFER;
                                timer = container_of(h, struct xntimer, aplink);
diff --git a/kernel/cobalt/timer.c b/kernel/cobalt/timer.c
index 114c2ed..bc5893d 100644
--- a/kernel/cobalt/timer.c
+++ b/kernel/cobalt/timer.c
@@ -55,7 +55,7 @@ int xntimer_heading_p(struct xntimer *timer)
                return 1;
 
        if (sched->lflags & XNHDEFER) {
-               h = xntimerq_second(q);
+               h = xntimerq_second(q, h);
                if (h == &timer->aplink)
                        return 1;
        }
@@ -925,4 +925,36 @@ void xntimer_release_hardware(void)
 }
 EXPORT_SYMBOL_GPL(xntimer_release_hardware);
 
+#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

Reply via email to