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