Module: xenomai-3
Branch: wip/dovetail
Commit: 15a799e1edf1da86ad80b5d19cb6d3c704c6e614
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=15a799e1edf1da86ad80b5d19cb6d3c704c6e614
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
