Module: xenomai-gch
Branch: timers-bench
Commit: 56b3390e7e7eb9c15ee096cdf65e594c520bcf07
URL:    
http://git.xenomai.org/?p=xenomai-gch.git;a=commit;h=56b3390e7e7eb9c15ee096cdf65e594c520bcf07

Author: Gilles Chanteperdrix <gilles.chanteperd...@xenomai.org>
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
Xenomai-git@xenomai.org
https://xenomai.org/mailman/listinfo/xenomai-git

Reply via email to