Module: xenomai-gch Branch: timers-bench Commit: 56b3390e7e7eb9c15ee096cdf65e594c520bcf07 URL: http://git.xenomai.org/?p=xenomai-gch.git;a=commit;h=56b3390e7e7eb9c15ee096cdf65e594c520bcf07
Author: Gilles Chanteperdrix <[email protected]> Date: Mon Jan 11 08:22:34 2016 +0100 Add timers benchmarks --- include/cobalt/kernel/avl.h | 317 +++++++++++++++++++++ include/cobalt/kernel/stat_accumulator.h | 45 +++ include/cobalt/kernel/timer.h | 225 +++++++++++++-- kernel/cobalt/Kconfig | 12 + kernel/cobalt/Makefile | 2 + kernel/cobalt/avl.c | 443 ++++++++++++++++++++++++++++++ kernel/cobalt/clock.c | 2 +- kernel/cobalt/posix/process.c | 3 + kernel/cobalt/posix/timer.c | 1 + kernel/cobalt/stat_accumulator.c | 197 +++++++++++++ kernel/cobalt/timer.c | 87 +++++- testsuite/xeno-test/dohell | 2 +- testsuite/xeno-test/xeno-test.in | 16 +- 13 files changed, 1324 insertions(+), 28 deletions(-) diff --git a/include/cobalt/kernel/avl.h b/include/cobalt/kernel/avl.h new file mode 100644 index 0000000..8d22329 --- /dev/null +++ b/include/cobalt/kernel/avl.h @@ -0,0 +1,317 @@ +/* + * Copyright (c) 2015 Gilles Chanteperdrix + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. + * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY + * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef CH_AVL_H +#define CH_AVL_H + +#define AVL_DUMP 0 + +typedef struct avlh { + unsigned thr: 3; + int type: 2; + int balance :2; + unsigned flags :25; /* Application-specific */ + struct avlh *link[3]; +} avlh_t; + +/* Using -1 and 1 for left and right is slightly faster than 0 and 1, using 0 + for "up" is just here for orthogonality... and avoid wasting 4 bytes or + having to use a union in avlh_t. */ +#define AVL_LEFT -1 +#define AVL_UP 0 +#define AVL_RIGHT 1 +/* maps AVL_LEFT to AVL_RIGHT and reciprocally. */ +#define avl_opposite(type) (-(type)) +/* maps AVL_LEFT to -1 and AVL_RIGHT to 1. */ +#define avl_type2sign(type) (type) +/* maps AVL_LEFT and AVL_RIGHT to arrays index (or bit positions). */ +#define avl_type2index(type) ((type)+1) +/* maps <0 to AVL_LEFT and >0 to AVL_RIGHT. */ +#define avl_sign2type(sign) (sign) + +#define AVL_THR_LEFT (1<<avl_type2index(AVL_LEFT)) +#define AVL_THR_RIGHT (1<<avl_type2index(AVL_RIGHT)) + +#define avlh_thr_set(holder, side) ((holder)->thr |= 1<<avl_type2index(side)) +#define avlh_thr_clr(holder, side) ((holder)->thr &= ~(1<<avl_type2index(side))) +#define avlh_thr_tst(holder, side) ((holder)->thr & (1<<avl_type2index(side))) +#define avlh_link(holder, dir) ((holder)->link[avl_type2index(dir)]) +#define avlh_up(holder) avlh_link((holder), AVL_UP) +#define avlh_left(holder) avlh_link((holder), AVL_LEFT) +#define avlh_right(holder) avlh_link((holder), AVL_RIGHT) +#define avlh_parent_link(holder) (avlh_link(avlh_up(holder), (holder)->type)) + +struct avl; +typedef struct avl avl_t; + +typedef avlh_t *avl_search_t(const avl_t *, const avlh_t *, int *); + +typedef int avlh_cmp_t(const avlh_t *const, const avlh_t *const); + +struct avl { + avlh_t anchor; + avl_search_t *search; + avlh_cmp_t *cmp; + avlh_t *end[3]; + unsigned count; + unsigned height; +}; + +#define avl_searchfn(avl) ((avl)->search) +#define avl_cmp(avl) ((avl)->cmp) +#define avl_count(avl) ((avl)->count) +#define avl_height(avl) ((avl)->height) +#define avl_anchor(avl) (&(avl)->anchor) +#define avl_end(avl, dir) ((avl)->end[avl_type2index(dir)]) +#define avl_top(avl) (avlh_right(avl_anchor(avl))) +#define avl_head(avl) (avl_end((avl), AVL_LEFT)) +#define avl_tail(avl) (avl_end((avl), AVL_RIGHT)) + +#ifdef __cplusplus +extern "C" { +#endif /* __cplusplus */ + +void avl_init(avl_t *avl, avl_search_t *search, avlh_cmp_t *cmp); + +void avl_destroy(avl_t *avl); + +void avl_clear(avl_t *avl, void (*destruct)(avlh_t *)); + +int avl_insert(avl_t *avl, avlh_t *holder); + +int avl_prepend(avl_t *avl, avlh_t *holder); + +int avl_append(avl_t *avl, avlh_t *holder); + +avlh_t *avl_update(avl_t *avl, avlh_t *holder); + +avlh_t *avl_set(avl_t *avl, avlh_t *holder); + +int avl_delete(avl_t *avl, avlh_t *node); + +#if AVL_DUMP +#include <stdio.h> + +typedef int avlh_prn_t(char *, size_t, const avlh_t *const); + +void avl_dump(FILE *file, + avl_t *avl, + avlh_prn_t *prn, + unsigned indent, + unsigned len); + +#else /* !AVL_DUMP */ + +#define avl_dump(f,t,p,i,l) do {} while (0) + +#endif /* AVL_DUMP */ + +static inline avlh_t *avl_gettop(avl_t *const avl) +{ + avlh_t *const holder = avl_top(avl); + + if (holder != avl_anchor(avl)) + return holder; + + return NULL; +} + +static inline avlh_t *avl_gethead(avl_t *const avl) +{ + avlh_t *const holder = avl_head(avl); + + if (holder != avl_anchor(avl)) + return holder; + + return NULL; +} + +static inline avlh_t *avl_gettail(avl_t *const avl) +{ + avlh_t *const holder = avl_tail(avl); + + if (holder != avl_anchor(avl)) + return holder; + + return NULL; +} + +static inline unsigned avl_getcount(avl_t *const avl) +{ + return avl_count(avl); +} + +static inline avlh_t *avl_inorder(avl_t *const avl, + avlh_t *const holder, + const int dir) +{ + /* Assume dir == AVL_RIGHT in comments. */ + avlh_t *child = avlh_link(holder, dir); + + /* If the current node is not right threaded, then go down left, starting + from its right child. */ + if (!avlh_thr_tst(holder, dir)) { + const int opp_dir = avl_opposite(dir); + while (!avlh_thr_tst(child, opp_dir)) + child = avlh_link(child, opp_dir); + } else + /* Else follow its right thread. */ + if (child != avl_anchor(avl)) + return child; + else + return NULL; + + return child; +} + +static inline avlh_t *avl_postorder(avl_t *const avl, + avlh_t *const holder, const int dir) +{ + /* Assume dir == AVL_RIGHT in comments. */ + avlh_t *next = avlh_up(holder); + + if (holder->type != dir) + /* If the current node is not a right node, follow the nodes in inorder + until we find a right threaded node. */ + while (!avlh_thr_tst(next, dir)) + next = avl_inorder(avl, next, dir); + else + /* else the current node is a right node, its parent is the next in + postorder. */ + if (next != avl_anchor(avl)) + return next; + else + return NULL; + + return next; +} + +static inline avlh_t *avl_preorder(avl_t *const avl, + avlh_t *holder, const int dir) +{ + avlh_t *next; + /* Assume dir == AVL_RIGHT in comments. */ + /* If the current node has a left child (hence is not left threaded), then + return it. */ + if (!avlh_thr_tst(holder, avl_opposite(dir))) + return avlh_link(holder, avl_opposite(dir)); + + /* Else follow the right threads until we find a node which is not right + threaded (hence has a right child) and return its right child. */ + next = holder; + + while (avlh_thr_tst(next, dir)) { + next = avlh_link(next, dir); + if (next == avl_anchor(avl)) + goto ret_null; + } + + return avlh_link(next, dir); + ret_null: + return NULL; +} + +/** + * Get next node in symmetrical a.k.a inorder ordering. + */ +static inline avlh_t *avl_next(avl_t *const avl, avlh_t *const holder) +{ + return avl_inorder(avl, holder, AVL_RIGHT); +} + +/** + * Get previous node in symmetrical a.k.a inorder ordering. + */ +static inline avlh_t *avl_prev(avl_t *const avl, avlh_t *const holder) +{ + return avl_inorder(avl, holder, AVL_LEFT); +} + +static inline avlh_t *avl_postorder_next(avl_t *const avl, avlh_t *const holder) +{ + return avl_postorder(avl, holder, AVL_RIGHT); +} + +static inline avlh_t *avl_postorder_prev(avl_t *const avl, avlh_t *const holder) +{ + return avl_postorder(avl, holder, AVL_LEFT); +} + +static inline avlh_t *avl_preorder_next(avl_t *const avl, avlh_t *const holder) +{ + return avl_preorder(avl, holder, AVL_RIGHT); +} + +static inline avlh_t *avl_preorder_prev(avl_t *const avl, avlh_t *const holder) +{ + return avl_preorder(avl, holder, AVL_LEFT); +} + +static inline void avlh_init(avlh_t *const holder) +{ + *(unsigned long *)holder = 0UL; /* Please valgrind */ + holder->thr = AVL_THR_LEFT | AVL_THR_RIGHT; + holder->balance = 0; + holder->type = 0; +} + +static inline avlh_t *avl_search(avl_t *const avl, const avlh_t *node) +{ + avlh_t *holder; + int delta; + + holder = avl_searchfn(avl)(avl, node, &delta); + if (!delta) + return holder; + + return NULL; +} + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +/** + * Search a node, return its parent if it could not be found. + */ +#define DECLARE_AVL_SEARCH(avl_search_inner, cmp) \ + static avlh_t *avl_search_inner(const avl_t *const avl, \ + const avlh_t *const node, \ + int *const pdelta) \ + { \ + int delta = avl_type2sign(AVL_RIGHT); \ + avlh_t *holder = avl_top(avl); \ + \ + if (holder != avl_anchor(avl)) { \ + while ((delta = cmp(holder, node))) { \ + delta = delta < 0 ? -1 : 1; \ + if (avlh_thr_tst(holder,avl_sign2type(delta))) \ + break; \ + holder = avlh_link(holder, avl_sign2type(delta)); \ + } \ + } \ + *pdelta = delta; \ + return holder; \ + } \ + +#endif /* CH_AVL_H */ diff --git a/include/cobalt/kernel/stat_accumulator.h b/include/cobalt/kernel/stat_accumulator.h new file mode 100644 index 0000000..2a591db --- /dev/null +++ b/include/cobalt/kernel/stat_accumulator.h @@ -0,0 +1,45 @@ +#ifndef STAT_ACCUMULATOR_H +#define STAT_ACCUMULATOR_H + +struct stat_accumulator { + unsigned long long min, max, sum, var_s, var_m, count; +}; + +struct stat_results { + unsigned long long avg, std_dev; +}; + +struct chrono { + unsigned long long start; + struct stat_accumulator a; + const char *name; + struct list_head holder; +}; + +extern struct chrono chrono_empty, chrono_head, chrono_second, chrono_insert, chrono_remove; + +void stat_accumulator_init(struct stat_accumulator *a); + +void stat_accumulate(struct stat_accumulator *a, unsigned long long val); + +void stat_results_get(struct stat_results *r, struct stat_accumulator *a); + +void chrono_init(struct chrono *c, const char *name); + +static inline void chrono_start(struct chrono *c) +{ + c->start = xnclock_core_read_raw(); +} + +void chrono_stop(struct chrono *c); + +#ifdef CONFIG_XENO_CHRONO_TIMERLIST +void chronos_init(void); + +void chronos_dump(void); +#else +#define chronos_init() +#define chronos_dump() +#endif + +#endif /* STAT_ACCUMULATOR_H */ diff --git a/include/cobalt/kernel/timer.h b/include/cobalt/kernel/timer.h index 5868fcb..f502060 100644 --- a/include/cobalt/kernel/timer.h +++ b/include/cobalt/kernel/timer.h @@ -25,6 +25,7 @@ #include <cobalt/kernel/list.h> #include <cobalt/kernel/assert.h> #include <cobalt/kernel/ancillaries.h> +#include <cobalt/kernel/stat_accumulator.h> #include <asm/xenomai/wrappers.h> /** @@ -101,15 +102,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); } @@ -156,11 +151,11 @@ typedef DECLARE_BHEAP_CONTAINER(xntimerq_t, CONFIG_XENO_OPT_TIMER_HEAP_CAPACITY) #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_empty(q) bheap_empty(q) +#define _xntimerq_head(q) bheap_gethead(q) +#define _xntimerq_second(q, h) ((void)(h), bheap_second(q)) +#define _xntimerq_insert(q, h) bheap_insert((q),(h)) +#define _xntimerq_remove(q, h) bheap_delete((q),(h)) typedef struct {} xntimerq_it_t; @@ -172,7 +167,7 @@ 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))) -#else /* CONFIG_XENO_OPT_TIMER_LIST */ +#elif defined(CONFIG_XENO_OPT_TIMER_LIST) typedef struct xntlholder xntimerh_t; @@ -184,18 +179,208 @@ typedef struct list_head xntimerq_t; #define xntimerq_init(q) xntlist_init(q) #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_insert(q, h) xntlist_insert((q),(h)) -#define xntimerq_remove(q, h) xntlist_remove((q),(h)) +#define _xntimerq_empty(q) xntlist_empty(q) +#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)) typedef struct { } xntimerq_it_t; #define xntimerq_it_begin(q,i) ((void) (i), xntlist_head(q)) #define xntimerq_it_next(q,i,h) ((void) (i), xntlist_next((q),(h))) -#endif /* CONFIG_XENO_OPT_TIMER_LIST */ +#elif defined(CONFIG_XENO_OPT_TIMER_RBTREE) + +#include <linux/rbtree.h> + +typedef struct { + unsigned long long date; + unsigned prio; + struct rb_node link; +} xntimerh_t; + +#define xntimerh_date(h) ((h)->date) +#define xntimerh_prio(h) ((h)->prio) +#define xntimerh_init(h) do { } while (0) + +typedef struct rb_root xntimerq_t; + +#define xntimerq_init(q) (*(q) = RB_ROOT) +#define xntimerq_destroy(q) do { } while (0) +#define _xntimerq_empty(q) ((q)->rb_node != NULL) +#define _xntimerq_head(q) \ + ({ \ + struct rb_root *_root = (q); \ + struct rb_node *_node = rb_first(_root); \ + _node ? (container_of(_node, xntimerh_t, link)) : NULL; \ + }) + +#define _xntimerq_second(q, h) \ + ({ \ + struct rb_node *_node = rb_next(&(h)->link); \ + _node ? (container_of(_node, xntimerh_t, link)) : NULL; \ + }) + +void _xntimerq_insert(struct rb_root *root, xntimerh_t *holder); + +#define _xntimerq_remove(q, h) rb_erase(&(h)->link, (q)) + +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_second((q),(h))) + +#elif defined(CONFIG_XENO_OPT_TIMER_RBTREE_HT) + +#include <linux/rbtree.h> + +typedef struct { + unsigned long long date; + unsigned prio; + struct rb_node link; +} xntimerh_t; + +#define xntimerh_date(h) ((h)->date) +#define xntimerh_prio(h) ((h)->prio) +#define xntimerh_init(h) do { } while (0) + +typedef struct { + struct rb_root root; + xntimerh_t *head; +} xntimerq_t; + +#define xntimerq_init(q) \ + ({ \ + xntimerq_t *_q = (q); \ + _q->root = RB_ROOT; \ + _q->head = NULL; \ + }) + +#define xntimerq_destroy(q) do { } while (0) +#define _xntimerq_empty(q) ((q)->head != NULL) + +#define _xntimerq_head(q) ((q)->head) + +#define _xntimerq_second(q, h) \ + ({ \ + struct rb_node *_node = rb_next(&(h)->link); \ + _node ? (container_of(_node, xntimerh_t, link)) : NULL; \ + }) + +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_second((q),(h))) + +#elif defined(CONFIG_XENO_OPT_TIMER_AVL) + +#include <cobalt/kernel/avl.h> + +typedef struct { + unsigned long long date; + unsigned prio; + struct avlh link; +} xntimerh_t; + +#define xntimerh_date(h) ((h)->date) +#define xntimerh_prio(h) ((h)->prio) +#define xntimerh_init(h) do { } while (0) + +typedef struct avl xntimerq_t; + +void xntimerq_init(struct avl *root); + +#define xntimerq_destroy(q) avl_destroy(q) +#define _xntimerq_empty(q) (avl_gethead(q) != NULL) + +#define _xntimerq_head(q) \ + ({ \ + struct avlh *_node = avl_gethead((q)); \ + _node ? (container_of(_node, xntimerh_t, link)) : NULL; \ + }) + +#define _xntimerq_second(q, h) \ + ({ \ + struct avlh *_node = avl_next((q), &(h)->link); \ + _node ? (container_of(_node, xntimerh_t, link)) : NULL; \ + }) + +void _xntimerq_insert(xntimerq_t *q, xntimerh_t *holder); + +#define _xntimerq_remove(q, h) (avl_delete((q), &(h)->link)) + +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_second((q),(h))) + +#endif /* CONFIG_XENO_OPT_TIMER_AVL */ + +#ifndef CONFIG_XENO_CHRONO_TIMERLIST +#define xntimerq_empty _xntimerq_empty +#define xntimerq_head _xntimerq_head +#define xntimerq_second _xntimerq_second +#define xntimerq_insert _xntimerq_insert +#define xntimerq_remove _xntimerq_remove +#else +static inline int xntimerq_empty(xntimerq_t *q) +{ + int ret; + + chrono_start(&chrono_empty); + ret = _xntimerq_empty(q); + chrono_stop(&chrono_empty); + + return ret; +} + +static inline xntimerh_t *xntimerq_head(xntimerq_t *q) +{ + xntimerh_t *ret; + + chrono_start(&chrono_head); + ret = _xntimerq_head(q); + chrono_stop(&chrono_head); + + return ret; +} + +static inline xntimerh_t *xntimerq_second(xntimerq_t *q, xntimerh_t *h) +{ + xntimerh_t *ret; + + chrono_start(&chrono_second); + ret = _xntimerq_second(q, h); + chrono_stop(&chrono_second); + + return ret; +} + +static inline void xntimerq_insert(xntimerq_t *q, xntimerh_t *h) +{ + chrono_start(&chrono_insert); + _xntimerq_insert(q, h); + chrono_stop(&chrono_insert); +} + +static inline void xntimerq_remove(xntimerq_t *q, xntimerh_t *h) +{ + chrono_start(&chrono_remove); + _xntimerq_remove(q, h); + chrono_stop(&chrono_remove); +} +#endif struct xnsched; diff --git a/kernel/cobalt/Kconfig b/kernel/cobalt/Kconfig index 24f09e8..8851aae 100644 --- a/kernel/cobalt/Kconfig +++ b/kernel/cobalt/Kconfig @@ -135,6 +135,9 @@ config XENO_OPT_STATS per-thread runtime statistics, which are accessible through the /proc/xenomai/sched/stat interface. +config XENO_CHRONO_TIMERLIST + bool "Arm timerlist statistics" + config XENO_OPT_SHIRQ bool "Shared interrupts" help @@ -197,6 +200,15 @@ config XENO_OPT_TIMER_HEAP high number of software timers may be concurrently outstanding at any point in time. +config XENO_OPT_TIMER_RBTREE + bool "RB tree" + +config XENO_OPT_TIMER_RBTREE_HT + bool "RB tree with head tracking" + +config XENO_OPT_TIMER_AVL + bool "AVL with head tracking and threading" + endchoice config XENO_OPT_TIMER_HEAP_CAPACITY diff --git a/kernel/cobalt/Makefile b/kernel/cobalt/Makefile index 6e1cebe..e24dd89 100644 --- a/kernel/cobalt/Makefile +++ b/kernel/cobalt/Makefile @@ -21,8 +21,10 @@ xenomai-y := apc.o \ xenomai-$(CONFIG_XENO_OPT_SCHED_QUOTA) += sched-quota.o xenomai-$(CONFIG_XENO_OPT_SCHED_WEAK) += sched-weak.o xenomai-$(CONFIG_XENO_OPT_SCHED_SPORADIC) += sched-sporadic.o +xenomai-$(CONFIG_XENO_CHRONO_TIMERLIST) += stat_accumulator.o xenomai-$(CONFIG_XENO_OPT_SCHED_TP) += sched-tp.o xenomai-$(CONFIG_XENO_OPT_DEBUG) += debug.o xenomai-$(CONFIG_XENO_OPT_PIPE) += pipe.o xenomai-$(CONFIG_XENO_OPT_MAP) += map.o xenomai-$(CONFIG_PROC_FS) += vfile.o procfs.o +xenomai-$(CONFIG_XENO_OPT_TIMER_AVL) += avl.o diff --git a/kernel/cobalt/avl.c b/kernel/cobalt/avl.c new file mode 100644 index 0000000..22faa01 --- /dev/null +++ b/kernel/cobalt/avl.c @@ -0,0 +1,443 @@ +/* + * Copyright (c) 2015 Gilles Chanteperdrix + * + * Permission is hereby granted, free of charge, to any person obtaining + * a copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to + * permit persons to whom the Software is furnished to do so, subject to + * the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. + * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY + * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, + * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE + * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#include <linux/kernel.h> +#include <linux/string.h> +#include <cobalt/kernel/avl.h> + +/* Internal functions used for rebalancing (for insertion and deletion). */ +static inline avlh_t *avlh_rotate(avlh_t *const holder, const int dir) +{ + const int opp_dir = avl_opposite(dir); + avlh_t *const nexttop = avlh_link(holder, opp_dir); + + if (!avlh_thr_tst(nexttop, dir)) { + avlh_t *const subtree = avlh_link(nexttop, dir); + + avlh_link(holder, opp_dir) = subtree; + avlh_thr_clr(holder, opp_dir); + avlh_up(subtree) = holder; + subtree->type = opp_dir; + } else + avlh_thr_set(holder, opp_dir); + + avlh_link(nexttop, dir) = holder; + avlh_thr_clr(nexttop, dir); + + avlh_up(nexttop) = avlh_up(holder); + nexttop->type = holder->type; + avlh_up(holder) = nexttop; + holder->type = dir; + + avlh_parent_link(nexttop) = nexttop; + + return nexttop; +} + +static inline avlh_t *avlh_dbl_rotate(avlh_t *const holder, const int dir) +{ + const int opp = avl_opposite(dir); + + avlh_rotate(avlh_link(holder, opp), opp); + return avlh_rotate(holder, dir); +} + +static avlh_t *avlh_rebalance(avlh_t *holder, const int delta) +{ + + int dir = avl_sign2type(delta); + avlh_t *const heavy_side = avlh_link(holder, dir); + + if (heavy_side->balance == -delta) { + /* heavy_side->balance == -delta, double rotation needed. */ + holder = avlh_dbl_rotate(holder, avl_opposite(dir)); + + /* recompute balances, there are three nodes involved, two of which + balances become null.*/ + dir = holder->balance ? avl_sign2type(holder->balance) : AVL_RIGHT; + avlh_link(holder, dir)->balance = 0; + avlh_link(holder, avl_opposite(dir))->balance = -holder->balance; + holder->balance = 0; + } else { + /* heavy_side->balance == delta or 0, simple rotation needed. + the case 0 occurs only when deleting, never when inserting. */ + /* heavy_side becomes the new root. */ + avlh_rotate(holder, avl_opposite(dir)); + + /* recompute balances. */ + holder->balance -= heavy_side->balance; + heavy_side->balance -= delta; + + holder = heavy_side; + } + return holder; +} + +/* The avlh_rebalance functions was split in two parts to allow inlining in + the simplest case. */ +static inline avlh_t *avlh_balance_add(avlh_t *const holder, const int delta) +{ + if (holder->balance == delta) + /* we need to rebalance the current subtree. */ + return avlh_rebalance(holder, delta); + + /* the current subtree does not need rebalancing */ + holder->balance += delta; + return holder; +} + +static inline void avlh_link_child(avlh_t *const oldh, + avlh_t *const newh, const int side) +{ + avlh_t *const child = avlh_link(oldh, side); + + avlh_link(newh, side) = child; + if (!avlh_thr_tst(oldh, side)) { + /* avl_inorder won't use its tree parameter, hence NULL is Ok. */ + avlh_t *const inorder_adj = avl_inorder(NULL, oldh, side); + const int opp_side = avl_opposite(side); + avlh_link(inorder_adj, opp_side) = newh; + /* Do not change child before using avl_prev... */ + avlh_up(child) = newh; + } +} + +static inline void avlh_replace(avlh_t *const oldh, avlh_t *const newh) +{ + newh->thr = oldh->thr; + newh->type = oldh->type; + /* Do not update the balance, this has to be done by the caller. */ + + avlh_up(newh) = avlh_up(oldh); + avlh_parent_link(oldh) = newh; + + avlh_link_child(oldh, newh, AVL_LEFT); + avlh_link_child(oldh, newh, AVL_RIGHT); +} + +/* Deletion helpers. */ +static void avl_delete_leaf(avl_t *const avl, avlh_t *const node) +{ + /* Node has no child at all. It disappears and its father becomes + threaded on the side id was. */ + + avlh_t *const new_node = avlh_up(node); + const int dir = node->type; + + /* Suppress node. */ + avlh_link(new_node, dir) = avlh_link(node, dir); + avlh_thr_set(new_node, dir); + + if (node == avl_end(avl, dir)) + avl_end(avl, dir) = new_node; +} + +static avlh_t *avl_delete_1child(avl_t *const avl, + avlh_t *const node, const int dir) +{ + /* Node is threaded on one side and has a child on the other + side. In this case, node is replaced by its child. */ + + avlh_t *const new_node = avlh_link(node, dir); + + /* Change links as if new_node was suppressed before calling + avlh_replace. */ + avlh_link(node, dir) = avlh_link(new_node, dir); + if (avlh_thr_tst(new_node, dir)) + avlh_thr_set(node, dir); + avlh_replace(node, new_node); + + if (node == avl_end(avl, avl_opposite(dir))) + avl_end(avl, avl_opposite(dir)) = new_node; + /* new_node->balance 0, which is correct. */ + return new_node; +} + +static int avl_delete_2children(avl_t *const avl, avlh_t *const node); + +/* Insertion helpers. */ +static inline void avlh_attach(avlh_t *const parent, + avlh_t *const child, const int side) +{ + avlh_link(child, side) = avlh_link(parent, side); + avlh_link(child, avl_opposite(side)) = parent; + avlh_up(child) = parent; + avlh_link(parent, side) = child; + child->type = side; +} + +/** + * Insert a node, given its parent and the side where it should be inserted. + * Helper for all insertion functions. + */ +static inline void avl_insert_inner(avl_t *const avl, avlh_t *parent, + avlh_t *const node, const int side) +{ + avlh_attach(parent, node, side); + ++avl_count(avl); + + if (parent == avl_anchor(avl)) { + goto insert_first_and_ret; /* Get away from fast path */ + } else if (parent == avl_end(avl, side)) + avl_end(avl, side) = node; + + /* Do not touch these for first insertion. */ + avlh_thr_clr(parent, side); + parent->balance += avl_type2sign(side); + + while (parent->balance) { + const int delta = avl_type2sign(parent->type); + parent = avlh_up(parent); + if (parent == avl_anchor(avl)) + goto inc_height_and_ret; /* Get away from fast path */ + parent = avlh_balance_add(parent, delta); + } + + return; + + insert_first_and_ret: + avl_head(avl) = avl_tail(avl) = node; + inc_height_and_ret: + ++avl_height(avl); + return; +} + +/* External functions. */ + +int avl_delete(avl_t *const avl, avlh_t *node) +{ + if (!--avl_count(avl)) { + goto delete_last_and_ret; + } + + switch(node->thr) { + case (AVL_THR_LEFT|AVL_THR_RIGHT): /* thr is 5 */ + avl_delete_leaf(avl, node); + break; + + case AVL_THR_LEFT: /* only AVL_LEFT bit is on, thr is 1. */ + node = avl_delete_1child(avl, node, AVL_RIGHT); + break; + + case AVL_THR_RIGHT: /* only AVL_RIGHT bit is on, thr is 4. */ + node = avl_delete_1child(avl, node, AVL_LEFT); + break; + + case 0: + return avl_delete_2children(avl, node); + } + + /* node is the first node which needs to be rebalanced. + The tree is rebalanced, and contrarily to what happened for insertion, + the rebalancing stops when a node which is NOT balanced is met. */ + while (!node->balance) { + const int delta = -avl_type2sign(node->type); + node = avlh_up(node); + if (node == avl_anchor(avl)) + goto dec_height_and_ret; + node = avlh_balance_add(node, delta); + } + + return 0; + + delete_last_and_ret: + avl_top(avl) = avl_head(avl) = avl_tail(avl) = avl_anchor(avl); + dec_height_and_ret: + --avl_height(avl); + return 0; +} + +static int avl_delete_2children(avl_t *const avl, avlh_t *const node) +{ + const int dir = avl_sign2type(node->balance ? node->balance : 1); + avlh_t *const new_node = avl_inorder(avl, node, dir); + avl_delete(avl, new_node); + ++avl_count(avl); + avlh_replace(node, new_node); + new_node->balance = node->balance; + if (avl_end(avl, dir) == node) + avl_end(avl, dir) = new_node; + return 0; +} + +int avl_prepend(avl_t *const avl, avlh_t *const holder) +{ + avlh_t *const parent = avl_head(avl); + int type = parent == avl_anchor(avl) ? AVL_RIGHT : AVL_LEFT; + + if (parent == avl_anchor(avl) || avl_cmp(avl)(parent, holder) < 0) { + avl_insert_inner(avl, parent, holder, avl_type2sign(type)); + return 0; + } + + return -EINVAL; +} + +int avl_insert(avl_t *const avl, avlh_t *const holder) +{ + int delta; + avlh_t *parent; + + parent = avl_searchfn(avl)(avl, holder, &delta); + if (delta == 0) + delta = -1; + + avl_insert_inner(avl, parent, holder, avl_sign2type(delta)); + return 0; +} + +int avl_append(avl_t *const avl, avlh_t *const holder) +{ + avlh_t *const parent = avl_tail(avl); + + if (parent == avl_anchor(avl) || avl_cmp(avl)(parent, holder) > 0) { + avl_insert_inner(avl, parent, holder, avl_type2sign(AVL_RIGHT)); + return 0; + } + + return -EINVAL; +} + +avlh_t *avl_update(avl_t *const avl, avlh_t *const holder) +{ + int delta; + avlh_t *const oldh = avl_searchfn(avl)(avl, holder, &delta); + + if (!delta) { + avlh_replace(oldh, holder); + holder->balance = oldh->balance; + return oldh; + } + + return NULL; +} + +avlh_t *avl_set(avl_t *const avl, avlh_t *const holder) +{ + int delta; + avlh_t *const oldh = avl_searchfn(avl)(avl, holder, &delta); + + if (delta) { + avl_insert_inner(avl, oldh, holder, avl_sign2type(delta)); + return NULL; + } + + avlh_replace(oldh, holder); + holder->balance = oldh->balance; + return oldh; +} + +void avl_init(avl_t *avl, avl_search_t *search, avlh_cmp_t *cmp) +{ + avlh_init(avl_anchor(avl)); /* Beware of the union; this must be first. */ + avl_cmp(avl) = cmp; + avl_height(avl) = 0; + avl_count(avl) = 0; + avl_searchfn(avl) = search; + avlh_right(avl_anchor(avl)) = avl_anchor(avl); + + avl_head(avl) = avl_tail(avl) = avl_anchor(avl); +} + +void avl_destroy(avl_t *avl) +{ + avl_init(avl, NULL, NULL); +} + +void avl_clear(avl_t *const avl, void (*destruct)(avlh_t *)) +{ + if (destruct) { + avlh_t *next, *holder = avl_gethead(avl); + + while (holder) { + next = avl_postorder_next(avl, holder); + destruct(holder); + holder = next; + } + } + + avl_init(avl, avl_searchfn(avl), avl_cmp(avl)); +} + +#if AVL_DUMP +static inline void avl_dumper_visit(avlh_t *node, + avlh_prn_t *prn, const char *blank, + unsigned blank_sz, char *buf, + unsigned indent, unsigned len) +{ + char bal; + + if (!avlh_thr_tst(node, AVL_RIGHT)) { + if (blank_sz >= (unsigned) (buf-blank)) { + snprintf(buf, len+3, "%*s\n", (int) len+1, "bug!"); + printk(buf-blank_sz); + } else + avl_dumper_visit(avlh_link(node, AVL_RIGHT), prn, blank, + blank_sz+indent, buf, indent, len); + } + + switch(node->balance) { + case 0: bal = '.'; break; + case -1: bal = '-'; break; + case 1: bal = '+'; break; + default: bal = '?'; /* Bug. */ + } + + (*prn)(buf, len+1, node); + buf[len] = bal; + buf[len+1] = '\n'; + buf[len+2] = '\0'; + + printk(buf-blank_sz); + + if (!avlh_thr_tst(node, AVL_LEFT)) { + if (blank_sz >= (unsigned) (buf-blank)) { + snprintf(buf, len+3, "%*s\n", (int) len+1, "bug!"); + printk(buf-blank_sz); + } else + avl_dumper_visit(avlh_link(node, AVL_LEFT), prn, blank, + blank_sz+indent, buf, indent, len); + } +} + +void avl_dump(avl_t *avl, + avlh_prn_t *prn, unsigned indent, unsigned len) +{ + + avlh_t *holder = avl_gettop(avl); + + printk("\n"); + if (!holder) + fputs("Empty.\n", file); + else { + size_t blank_sz = (avl_height(avl)-1)*indent; + char buffer[blank_sz+len+3]; /* 3 == balance char + sizeof("\n\0") */ + memset(buffer, ' ', blank_sz); + + avl_dumper_visit(holder, prn, buffer, 0, + buffer+blank_sz, indent, len); + } + fflush(file); +} + +#endif 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/posix/process.c b/kernel/cobalt/posix/process.c index 5c152e8..fcae8a7 100644 --- a/kernel/cobalt/posix/process.c +++ b/kernel/cobalt/posix/process.c @@ -48,6 +48,7 @@ #include <cobalt/kernel/ppd.h> #include <cobalt/kernel/vdso.h> #include <cobalt/kernel/thread.h> +#include <cobalt/kernel/stat_accumulator.h> #include <cobalt/uapi/signal.h> #include <cobalt/uapi/syscall.h> #include <trace/events/cobalt-core.h> @@ -1369,6 +1370,8 @@ static void *cobalt_process_attach(void) return ERR_PTR(ret); } + chronos_init(); + INIT_LIST_HEAD(&process->resources.condq); INIT_LIST_HEAD(&process->resources.mutexq); INIT_LIST_HEAD(&process->resources.semq); diff --git a/kernel/cobalt/posix/timer.c b/kernel/cobalt/posix/timer.c index cf1c919..eba43e0 100644 --- a/kernel/cobalt/posix/timer.c +++ b/kernel/cobalt/posix/timer.c @@ -591,5 +591,6 @@ void cobalt_timer_reclaim(struct cobalt_process *p) xnlock_get_irqsave(&nklock, s); } out: + chronos_dump(); xnlock_put_irqrestore(&nklock, s); } diff --git a/kernel/cobalt/stat_accumulator.c b/kernel/cobalt/stat_accumulator.c new file mode 100644 index 0000000..27dc5c1 --- /dev/null +++ b/kernel/cobalt/stat_accumulator.c @@ -0,0 +1,197 @@ +#include <linux/kernel.h> +#include <linux/list.h> +#include <linux/math64.h> +#include <linux/bitops.h> + +#include <cobalt/kernel/sched.h> +#include <cobalt/kernel/stat_accumulator.h> + +static inline unsigned __attribute__((const)) ulsqrt(unsigned long x) +{ + register unsigned order, approx; + + order = fls(x) - 1; + /* Big enough to be sure that the series is going down and allows us an + easy stopping criterion. */ + approx = (order % 2 == 0 + ? x >> order / 2 + : (1UL << (order / 2 + 1)) - 1); + + while (likely((unsigned long)approx * approx > x)) + approx = (approx + x / approx) >> 1; + + return approx; +} + +#if BITS_PER_LONG == 32 +static inline unsigned __attribute__((const)) ullsqrt(unsigned long long x) +{ + register unsigned order, approx; + + order = fls64(x) - 1; + /* Big enough to be sure that the series is going down and allows us an + easy stopping criterion. */ + approx = (order % 2 == 0 + ? x >> order / 2 + : (1ULL << (order / 2 + 1)) - 1); + + while (likely((unsigned long long)approx * approx > x)) { + unsigned long long tmp = x; + do_div(tmp, approx); + approx = ((unsigned long long)approx + tmp) >> 1; + } + + return approx; +} +#else +#define ullsqrt ulsqrt +#endif + +void stat_accumulator_init(struct stat_accumulator *a) +{ + a->min = ~0ULL; + a->max = a->sum = a->count = a->var_s = a->var_m = 0; +} + +void stat_accumulate(struct stat_accumulator *a, unsigned long long val) +{ + unsigned long long new_m; + + if (val < a->min) + a->min = val; + if (val > a->max) + a->max = val; + a->sum += val; + + ++a->count; + new_m = a->sum + (a->count >> 1); + do_div(new_m, a->count); + + a->var_s += (long long)(val - a->var_m) * (long long)(val - new_m); + a->var_m = new_m; +} + +void stat_results_get(struct stat_results *r, struct stat_accumulator *a) +{ + unsigned long long avg, variance; + + if (a->count == 0) { + r->avg = 0; + r->std_dev = 0; + return; + } + + + avg = a->sum + (a->count >> 1); + do_div(avg, a->count); + r->avg = avg; + + if (a->count == 1) { + r->std_dev = 0; + return; + } + + variance = a->var_s + ((a->count - 1) >> 1); + do_div(variance, a->count - 1); + + r->std_dev = ullsqrt(variance); +} + +static LIST_HEAD(all_chronos); +struct chrono chrono_empty, chrono_head, chrono_second, chrono_insert, chrono_remove; +static struct chrono runtime; +static struct stat_accumulator overall; + +void chrono_init(struct chrono *c, const char *name) +{ + stat_accumulator_init(&c->a); + c->name = name; + list_add_tail(&c->holder, &all_chronos); +} + +void chrono_stop(struct chrono *c) +{ + unsigned long long duration; + + duration = xnclock_core_read_raw() - c->start; + + stat_accumulate(&c->a, duration); + stat_accumulate(&overall, duration); +} + +void chronos_init(void) +{ + spl_t s; + + xnlock_get_irqsave(&nklock, s); + INIT_LIST_HEAD(&all_chronos); + chrono_init(&chrono_empty, "empty"); + chrono_init(&chrono_head, "head"); + chrono_init(&chrono_second, "second"); + chrono_init(&chrono_insert, "insert"); + chrono_init(&chrono_remove, "remove"); + chrono_init(&runtime, "test runtime"); + stat_accumulator_init(&overall); + chrono_start(&runtime); + xnlock_put_irqrestore(&nklock, s); +} + +void chronos_dump(void) +{ + unsigned long long percent, tmp; + unsigned long percent_remainder; + struct stat_accumulator saved_overall; + struct stat_results r; + struct chrono *c; + spl_t s; + + xnlock_get_irqsave(&nklock, s); + saved_overall = overall; + chrono_stop(&runtime); + + list_for_each_entry(c, &all_chronos, holder) { + if (c == &runtime) + continue; + + stat_results_get(&r, &c->a); + + if (c->a.count) + printk("%s: %Lu samples, %Luns < %Luns < %Luns, stddev %Luns\n", + c->name, c->a.count, + xnclock_core_ticks_to_ns_rounded(c->a.min), + xnclock_core_ticks_to_ns_rounded(r.avg), + xnclock_core_ticks_to_ns_rounded(c->a.max), + xnclock_core_ticks_to_ns_rounded(r.std_dev)); + else + printk("%s: 0 samples\n", c->name); + } + + stat_results_get(&r, &saved_overall); + + if (overall.count) + printk("overall: %Lu samples, %Lu ns < %Luns < %Luns, stddev %Luns\n", + saved_overall.count, + xnclock_core_ticks_to_ns_rounded(saved_overall.min), + xnclock_core_ticks_to_ns_rounded(r.avg), + xnclock_core_ticks_to_ns_rounded(saved_overall.max), + xnclock_core_ticks_to_ns_rounded(r.std_dev)); + else + printk("overall: 0 samples\n"); + + percent = 100 * saved_overall.sum; + tmp = runtime.a.sum + 500000; + do_div(tmp, 1000000); + if (tmp == 0) { + percent = 0; + percent_remainder = 0; + } else { + do_div(percent, tmp); + percent_remainder = do_div(percent, 1000000); + } + + printk("overall run-time: %Lu/%Luns, i.e: %Lu.%06lu%%\n", + xnclock_core_ticks_to_ns_rounded(saved_overall.sum), + xnclock_core_ticks_to_ns_rounded(runtime.a.sum), + percent, percent_remainder); + xnlock_put_irqrestore(&nklock, s); +} diff --git a/kernel/cobalt/timer.c b/kernel/cobalt/timer.c index 114c2ed..e1fba45 100644 --- a/kernel/cobalt/timer.c +++ b/kernel/cobalt/timer.c @@ -55,7 +55,8 @@ int xntimer_heading_p(struct xntimer *timer) return 1; if (sched->lflags & XNHDEFER) { - h = xntimerq_second(q); + /* First timer is necessarily the host timer, hence not null */ + h = xntimerq_second(q, h); if (h == &timer->aplink) return 1; } @@ -926,3 +927,87 @@ void xntimer_release_hardware(void) EXPORT_SYMBOL_GPL(xntimer_release_hardware); /** @} */ +#if defined(CONFIG_XENO_OPT_TIMER_RBTREE) +void _xntimerq_insert(struct rb_root *root, xntimerh_t *holder) +{ + struct rb_node **new = &root->rb_node, *parent = NULL; + + while (*new) { + xntimerh_t *i = container_of(*new, xntimerh_t, link); + + parent = *new; + if (holder->date < i->date + || (holder->date == i->date && holder->prio > i->prio)) + new = &((*new)->rb_left); + else + new = &((*new)->rb_right); + } + + rb_link_node(&holder->link, parent, new); + rb_insert_color(&holder->link, root); +} + +#elif defined(CONFIG_XENO_OPT_TIMER_RBTREE_HT) +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); +} + +#elif defined(CONFIG_XENO_OPT_TIMER_AVL) + +static inline int +xntimerh_cmp(const struct avlh *lefth, const struct avlh *righth) +{ + const xntimerh_t *left, *right; + long long ret; + + left = container_of(lefth, xntimerh_t, link); + right = container_of(righth, xntimerh_t, link); + + ret = (long long)(right->date - left->date); + if (ret == 0) + ret = (int)(left->prio - right->prio); + + return ret <= 0 ? -1 : 1; +} + +DECLARE_AVL_SEARCH(xntimerq_search_inner, xntimerh_cmp); + +void xntimerq_init(struct avl *root) +{ + avl_init(root, xntimerq_search_inner, xntimerh_cmp); +} + +void _xntimerq_insert(struct avl *root, xntimerh_t *holder) +{ + avlh_init(&holder->link); + if (avl_prepend(root, &holder->link) < 0) + BUG_ON(avl_insert(root, &holder->link) < 0); +} + +#endif diff --git a/testsuite/xeno-test/dohell b/testsuite/xeno-test/dohell index 68c5a5f..3b23ba5 100644 --- a/testsuite/xeno-test/dohell +++ b/testsuite/xeno-test/dohell @@ -64,7 +64,7 @@ if [ -n "$mntpoint" ]; then fi if [ -n "$hackbench" ]; then - while :; do $hackbench 1; done & + while :; do $hackbench 10 process 2000; done & pids="$pids $!" fi diff --git a/testsuite/xeno-test/xeno-test.in b/testsuite/xeno-test/xeno-test.in index b4bb403..bfeaf5e 100644 --- a/testsuite/xeno-test/xeno-test.in +++ b/testsuite/xeno-test/xeno-test.in @@ -38,6 +38,7 @@ EOF keep_going= rt_load=false +timerlist_bench=false while :; do case "$1" in @@ -56,6 +57,11 @@ while :; do shift ;; + -b) + timerlist_bench=true + shift + ;; + --) shift break @@ -73,10 +79,6 @@ echo 0 > /proc/xenomai/latency || : testdir=@testdir@ -$testdir/smokey --run $keep_going -$testdir/clocktest -D -T 30 -C CLOCK_HOST_REALTIME || $testdir/clocktest -T 30 -$testdir/switchtest -T 30 - start_load if $rt_load; then @@ -84,6 +86,10 @@ if $rt_load; then check_alive $testdir/switchtest -s 1000 fi -check_alive $testdir/latency ${1+"$@"} +if $timerlist_bench; then + check_alive timerlist_bench +else + check_alive $testdir/latency ${1+"$@"} +fi wait_load _______________________________________________ Xenomai-git mailing list [email protected] https://xenomai.org/mailman/listinfo/xenomai-git
