From f74db0b33d491a3189df7f909d382f93f9152c30 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Mon, 26 Sep 2011 11:44:57 +0200 Subject: add rb-tree implementation to libosmocore This patch adds red black trees implementation to libosmocore. This data structure is very useful to search for elements in ordered sets in O(log n) instead of O(n) that lists provide. The first client of this code will be one follow up patch that implements rbtree-based timer scheduler. --- include/osmocom/core/Makefile.am | 2 +- include/osmocom/core/linuxrbtree.h | 160 +++++++++++++++ src/Makefile.am | 2 +- src/rbtree.c | 389 +++++++++++++++++++++++++++++++++++++ 4 files changed, 551 insertions(+), 2 deletions(-) create mode 100644 include/osmocom/core/linuxrbtree.h create mode 100644 src/rbtree.c diff --git a/include/osmocom/core/Makefile.am b/include/osmocom/core/Makefile.am index aabb775f..5465d5f1 100644 --- a/include/osmocom/core/Makefile.am +++ b/include/osmocom/core/Makefile.am @@ -2,7 +2,7 @@ osmocore_HEADERS = signal.h linuxlist.h timer.h select.h msgb.h bits.h \ bitvec.h statistics.h utils.h socket.h \ gsmtap.h write_queue.h prim.h \ logging.h rate_ctr.h gsmtap_util.h \ - crc16.h panic.h process.h \ + crc16.h panic.h process.h linuxrbtree.h \ backtrace.h conv.h application.h \ crcgen.h crc8gen.h crc16gen.h crc32gen.h crc64gen.h diff --git a/include/osmocom/core/linuxrbtree.h b/include/osmocom/core/linuxrbtree.h new file mode 100644 index 00000000..ee988918 --- /dev/null +++ b/include/osmocom/core/linuxrbtree.h @@ -0,0 +1,160 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli + + This program 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. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/include/linux/rbtree.h + + To use rbtrees you'll have to implement your own insert and search cores. + This will avoid us to use callbacks and to drop drammatically performances. + I know it's not the cleaner way, but in C (not in C++) to get + performances and genericity... + + Some example of insert and search follows here. The search is a plain + normal search over an ordered tree. The insert instead must be implemented + int two steps: as first thing the code must insert the element in + order as a red leaf in the tree, then the support library function + rb_insert_color() must be called. Such function will do the + not trivial work to rebalance the rbtree if necessary. + +----------------------------------------------------------------------- +static inline struct page * rb_search_page_cache(struct inode * inode, + unsigned long offset) +{ + struct rb_node * n = inode->i_rb_page_cache.rb_node; + struct page * page; + + while (n) + { + page = rb_entry(n, struct page, rb_page_cache); + + if (offset < page->offset) + n = n->rb_left; + else if (offset > page->offset) + n = n->rb_right; + else + return page; + } + return NULL; +} + +static inline struct page * __rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct rb_node ** p = &inode->i_rb_page_cache.rb_node; + struct rb_node * parent = NULL; + struct page * page; + + while (*p) + { + parent = *p; + page = rb_entry(parent, struct page, rb_page_cache); + + if (offset < page->offset) + p = &(*p)->rb_left; + else if (offset > page->offset) + p = &(*p)->rb_right; + else + return page; + } + + rb_link_node(node, parent, p); + + return NULL; +} + +static inline struct page * rb_insert_page_cache(struct inode * inode, + unsigned long offset, + struct rb_node * node) +{ + struct page * ret; + if ((ret = __rb_insert_page_cache(inode, offset, node))) + goto out; + rb_insert_color(node, &inode->i_rb_page_cache); + out: + return ret; +} +----------------------------------------------------------------------- +*/ + +#ifndef _LINUX_RBTREE_H +#define _LINUX_RBTREE_H + +#include + +struct rb_node +{ + unsigned long rb_parent_color; +#define RB_RED 0 +#define RB_BLACK 1 + struct rb_node *rb_right; + struct rb_node *rb_left; +} __attribute__((aligned(sizeof(long)))); + /* The alignment might seem pointless, but allegedly CRIS needs it */ + +struct rb_root +{ + struct rb_node *rb_node; +}; + + +#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3)) +#define rb_color(r) ((r)->rb_parent_color & 1) +#define rb_is_red(r) (!rb_color(r)) +#define rb_is_black(r) rb_color(r) +#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0) +#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0) + +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) +{ + rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p; +} +static inline void rb_set_color(struct rb_node *rb, int color) +{ + rb->rb_parent_color = (rb->rb_parent_color & ~1) | color; +} + +#define RB_ROOT { NULL, } +#define rb_entry(ptr, type, member) container_of(ptr, type, member) + +#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) +#define RB_EMPTY_NODE(node) (rb_parent(node) == node) +#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) + +extern void rb_insert_color(struct rb_node *, struct rb_root *); +extern void rb_erase(struct rb_node *, struct rb_root *); + +/* Find logical next and previous nodes in a tree */ +extern struct rb_node *rb_next(struct rb_node *); +extern struct rb_node *rb_prev(struct rb_node *); +extern struct rb_node *rb_first(struct rb_root *); +extern struct rb_node *rb_last(struct rb_root *); + +/* Fast replacement of a single node without remove/rebalance/add/rebalance */ +extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root); + +static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, + struct rb_node ** rb_link) +{ + node->rb_parent_color = (unsigned long )parent; + node->rb_left = node->rb_right = NULL; + + *rb_link = node; +} + +#endif /* _LINUX_RBTREE_H */ diff --git a/src/Makefile.am b/src/Makefile.am index df104ac3..dfc2d493 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -14,7 +14,7 @@ libosmocore_la_SOURCES = timer.c select.c signal.c msgb.c bits.c \ write_queue.c utils.c socket.c \ logging.c logging_syslog.c rate_ctr.c \ gsmtap_util.c crc16.c panic.c backtrace.c \ - conv.c application.c \ + conv.c application.c rbtree.c \ crc8gen.c crc16gen.c crc32gen.c crc64gen.c if ENABLE_PLUGIN diff --git a/src/rbtree.c b/src/rbtree.c new file mode 100644 index 00000000..07e1041a --- /dev/null +++ b/src/rbtree.c @@ -0,0 +1,389 @@ +/* + Red Black Trees + (C) 1999 Andrea Arcangeli + (C) 2002 David Woodhouse + + This program 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. + + This program 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 this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + + linux/lib/rbtree.c +*/ + +#include + +static void __rb_rotate_left(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *right = node->rb_right; + struct rb_node *parent = rb_parent(node); + + if ((node->rb_right = right->rb_left)) + rb_set_parent(right->rb_left, node); + right->rb_left = node; + + rb_set_parent(right, parent); + + if (parent) + { + if (node == parent->rb_left) + parent->rb_left = right; + else + parent->rb_right = right; + } + else + root->rb_node = right; + rb_set_parent(node, right); +} + +static void __rb_rotate_right(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *left = node->rb_left; + struct rb_node *parent = rb_parent(node); + + if ((node->rb_left = left->rb_right)) + rb_set_parent(left->rb_right, node); + left->rb_right = node; + + rb_set_parent(left, parent); + + if (parent) + { + if (node == parent->rb_right) + parent->rb_right = left; + else + parent->rb_left = left; + } + else + root->rb_node = left; + rb_set_parent(node, left); +} + +void rb_insert_color(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *parent, *gparent; + + while ((parent = rb_parent(node)) && rb_is_red(parent)) + { + gparent = rb_parent(parent); + + if (parent == gparent->rb_left) + { + { + register struct rb_node *uncle = gparent->rb_right; + if (uncle && rb_is_red(uncle)) + { + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->rb_right == node) + { + register struct rb_node *tmp; + __rb_rotate_left(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + rb_set_black(parent); + rb_set_red(gparent); + __rb_rotate_right(gparent, root); + } else { + { + register struct rb_node *uncle = gparent->rb_left; + if (uncle && rb_is_red(uncle)) + { + rb_set_black(uncle); + rb_set_black(parent); + rb_set_red(gparent); + node = gparent; + continue; + } + } + + if (parent->rb_left == node) + { + register struct rb_node *tmp; + __rb_rotate_right(parent, root); + tmp = parent; + parent = node; + node = tmp; + } + + rb_set_black(parent); + rb_set_red(gparent); + __rb_rotate_left(gparent, root); + } + } + + rb_set_black(root->rb_node); +} + +static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, + struct rb_root *root) +{ + struct rb_node *other; + + while ((!node || rb_is_black(node)) && node != root->rb_node) + { + if (parent->rb_left == node) + { + other = parent->rb_right; + if (rb_is_red(other)) + { + rb_set_black(other); + rb_set_red(parent); + __rb_rotate_left(parent, root); + other = parent->rb_right; + } + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) + { + rb_set_red(other); + node = parent; + parent = rb_parent(node); + } + else + { + if (!other->rb_right || rb_is_black(other->rb_right)) + { + struct rb_node *o_left; + if ((o_left = other->rb_left)) + rb_set_black(o_left); + rb_set_red(other); + __rb_rotate_right(other, root); + other = parent->rb_right; + } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + if (other->rb_right) + rb_set_black(other->rb_right); + __rb_rotate_left(parent, root); + node = root->rb_node; + break; + } + } + else + { + other = parent->rb_left; + if (rb_is_red(other)) + { + rb_set_black(other); + rb_set_red(parent); + __rb_rotate_right(parent, root); + other = parent->rb_left; + } + if ((!other->rb_left || rb_is_black(other->rb_left)) && + (!other->rb_right || rb_is_black(other->rb_right))) + { + rb_set_red(other); + node = parent; + parent = rb_parent(node); + } + else + { + if (!other->rb_left || rb_is_black(other->rb_left)) + { + register struct rb_node *o_right; + if ((o_right = other->rb_right)) + rb_set_black(o_right); + rb_set_red(other); + __rb_rotate_left(other, root); + other = parent->rb_left; + } + rb_set_color(other, rb_color(parent)); + rb_set_black(parent); + if (other->rb_left) + rb_set_black(other->rb_left); + __rb_rotate_right(parent, root); + node = root->rb_node; + break; + } + } + } + if (node) + rb_set_black(node); +} + +void rb_erase(struct rb_node *node, struct rb_root *root) +{ + struct rb_node *child, *parent; + int color; + + if (!node->rb_left) + child = node->rb_right; + else if (!node->rb_right) + child = node->rb_left; + else + { + struct rb_node *old = node, *left; + + node = node->rb_right; + while ((left = node->rb_left) != NULL) + node = left; + child = node->rb_right; + parent = rb_parent(node); + color = rb_color(node); + + if (child) + rb_set_parent(child, parent); + if (parent == old) { + parent->rb_right = child; + parent = node; + } else + parent->rb_left = child; + + node->rb_parent_color = old->rb_parent_color; + node->rb_right = old->rb_right; + node->rb_left = old->rb_left; + + if (rb_parent(old)) + { + if (rb_parent(old)->rb_left == old) + rb_parent(old)->rb_left = node; + else + rb_parent(old)->rb_right = node; + } else + root->rb_node = node; + + rb_set_parent(old->rb_left, node); + if (old->rb_right) + rb_set_parent(old->rb_right, node); + goto color; + } + + parent = rb_parent(node); + color = rb_color(node); + + if (child) + rb_set_parent(child, parent); + if (parent) + { + if (parent->rb_left == node) + parent->rb_left = child; + else + parent->rb_right = child; + } + else + root->rb_node = child; + + color: + if (color == RB_BLACK) + __rb_erase_color(child, parent, root); +} + +/* + * This function returns the first node (in sort order) of the tree. + */ +struct rb_node *rb_first(struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_left) + n = n->rb_left; + return n; +} + +struct rb_node *rb_last(struct rb_root *root) +{ + struct rb_node *n; + + n = root->rb_node; + if (!n) + return NULL; + while (n->rb_right) + n = n->rb_right; + return n; +} + +struct rb_node *rb_next(struct rb_node *node) +{ + struct rb_node *parent; + + if (rb_parent(node) == node) + return NULL; + + /* If we have a right-hand child, go down and then left as far + as we can. */ + if (node->rb_right) { + node = node->rb_right; + while (node->rb_left) + node=node->rb_left; + return node; + } + + /* No right-hand children. Everything down and left is + smaller than us, so any 'next' node must be in the general + direction of our parent. Go up the tree; any time the + ancestor is a right-hand child of its parent, keep going + up. First time it's a left-hand child of its parent, said + parent is our 'next' node. */ + while ((parent = rb_parent(node)) && node == parent->rb_right) + node = parent; + + return parent; +} + +struct rb_node *rb_prev(struct rb_node *node) +{ + struct rb_node *parent; + + if (rb_parent(node) == node) + return NULL; + + /* If we have a left-hand child, go down and then right as far + as we can. */ + if (node->rb_left) { + node = node->rb_left; + while (node->rb_right) + node=node->rb_right; + return node; + } + + /* No left-hand children. Go up till we find an ancestor which + is a right-hand child of its parent */ + while ((parent = rb_parent(node)) && node == parent->rb_left) + node = parent; + + return parent; +} + +void rb_replace_node(struct rb_node *victim, struct rb_node *new, + struct rb_root *root) +{ + struct rb_node *parent = rb_parent(victim); + + /* Set the surrounding nodes to point to the replacement */ + if (parent) { + if (victim == parent->rb_left) + parent->rb_left = new; + else + parent->rb_right = new; + } else { + root->rb_node = new; + } + if (victim->rb_left) + rb_set_parent(victim->rb_left, new); + if (victim->rb_right) + rb_set_parent(victim->rb_right, new); + + /* Copy the pointers/colour from the victim to the replacement */ + *new = *victim; +} -- cgit v1.2.3 From 066c912fd3b4554d4475ae0837c1d62ef6c872d1 Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Mon, 26 Sep 2011 11:45:03 +0200 Subject: timer: add scalable RB-tree based timer infrastructure This patch adds RB-tree based timers which scales better than the previous list-based implementation. It does not require any API changes. It breaks ABI because the osmo_timer_list structure has changed though (to avoid this in the future, we can put internal data in some private structure). The following table summarizes the worst-case computational complexity of this new implementation versus the previous one: rb-tree list-based ------- ---------- calculate next timer to expire O(1) O(n) insertion of new timer O(log n) O(n) deletion of timer O(log n) O(1) timer-fired scheduler O(log n) O(3n) The most repeated cases are: * the calculation of the next timer to expire, that happens in every loop of our select function. * the timer-fired scheduler execution. This new implementation only loses in the deletion of timer scenario, this happens because we may need to rebalance the tree after the removal. So I think there is some real gain if we have some situation in which we have to handle lots of timers. --- include/osmocom/core/timer.h | 6 +- src/timer.c | 176 +++++++++++++++++++++++-------------------- 2 files changed, 98 insertions(+), 84 deletions(-) diff --git a/include/osmocom/core/timer.h b/include/osmocom/core/timer.h index 8f8c826d..30f558b4 100644 --- a/include/osmocom/core/timer.h +++ b/include/osmocom/core/timer.h @@ -32,6 +32,7 @@ #include #include +#include /** * Timer management: @@ -51,11 +52,10 @@ */ /*! \brief A structure representing a single instance of a timer */ struct osmo_timer_list { - struct llist_head entry; /*!< \brief linked list header */ + struct rb_node node; /*!< \brief rb-tree node header */ + struct llist_head list; /*!< \brief internal list header */ struct timeval timeout; /*!< \brief expiration time */ unsigned int active : 1; /*!< \brief is it active? */ - unsigned int handled : 1; /*!< \brief did we already handle it */ - unsigned int in_list : 1; /*!< \brief is it in the global list? */ void (*cb)(void*); /*!< \brief call-back called at timeout */ void *data; /*!< \brief user data for callback */ diff --git a/src/timer.c b/src/timer.c index ed2b2963..68529833 100644 --- a/src/timer.c +++ b/src/timer.c @@ -1,7 +1,12 @@ /* * (C) 2008,2009 by Holger Hans Peter Freyther + * (C) 2011 by Harald Welte * All Rights Reserved * + * Authors: Holger Hans Peter Freyther + * Harald Welte + * Pablo Neira Ayuso + * * This program 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 @@ -18,6 +23,10 @@ * */ +/* These store the amount of time that we wait until next timer expires. */ +static struct timeval nearest; +static struct timeval *nearest_p; + /*! \addtogroup timer * @{ */ @@ -27,35 +36,41 @@ #include #include +#include #include +#include + +static struct rb_root timer_root = RB_ROOT; + +static void __add_timer(struct osmo_timer_list *timer) +{ + struct rb_node **new = &(timer_root.rb_node); + struct rb_node *parent = NULL; -static LLIST_HEAD(timer_list); -static struct timeval s_nearest_time; -static struct timeval s_select_time; + while (*new) { + struct osmo_timer_list *this; -#define MICRO_SECONDS 1000000LL + this = container_of(*new, struct osmo_timer_list, node); -#define TIME_SMALLER(left, right) \ - (left.tv_sec*MICRO_SECONDS+left.tv_usec) <= (right.tv_sec*MICRO_SECONDS+right.tv_usec) + parent = *new; + if (timercmp(&timer->timeout, &this->timeout, <)) + new = &((*new)->rb_left); + else + new = &((*new)->rb_right); + } + rb_link_node(&timer->node, parent, new); + rb_insert_color(&timer->node, &timer_root); +} /*! \brief add a new timer to the timer management * \param[in] timer the timer that should be added */ void osmo_timer_add(struct osmo_timer_list *timer) { - struct osmo_timer_list *list_timer; - - /* TODO: Optimize and remember the closest item... */ timer->active = 1; - - /* this might be called from within update_timers */ - llist_for_each_entry(list_timer, &timer_list, entry) - if (timer == list_timer) - return; - - timer->in_list = 1; - llist_add(&timer->entry, &timer_list); + INIT_LLIST_HEAD(&timer->list); + __add_timer(timer); } /*! \brief schedule a timer at a given future relative time @@ -74,10 +89,9 @@ osmo_timer_schedule(struct osmo_timer_list *timer, int seconds, int microseconds struct timeval current_time; gettimeofday(¤t_time, NULL); - unsigned long long currentTime = current_time.tv_sec * MICRO_SECONDS + current_time.tv_usec; - currentTime += seconds * MICRO_SECONDS + microseconds; - timer->timeout.tv_sec = currentTime / MICRO_SECONDS; - timer->timeout.tv_usec = currentTime % MICRO_SECONDS; + timer->timeout.tv_sec = seconds; + timer->timeout.tv_usec = microseconds; + timeradd(&timer->timeout, ¤t_time, &timer->timeout); osmo_timer_add(timer); } @@ -89,10 +103,12 @@ osmo_timer_schedule(struct osmo_timer_list *timer, int seconds, int microseconds */ void osmo_timer_del(struct osmo_timer_list *timer) { - if (timer->in_list) { + if (timer->active) { timer->active = 0; - timer->in_list = 0; - llist_del(&timer->entry); + rb_erase(&timer->node, &timer_root); + /* make sure this is not already scheduled for removal. */ + if (!llist_empty(&timer->list)) + llist_del_init(&timer->list); } } @@ -116,26 +132,28 @@ int osmo_timer_pending(struct osmo_timer_list *timer) */ struct timeval *osmo_timers_nearest(void) { - struct timeval current_time; - - if (s_nearest_time.tv_sec == 0 && s_nearest_time.tv_usec == 0) - return NULL; - - if (gettimeofday(¤t_time, NULL) == -1) - return NULL; + static struct timeval no_timers = { 0, 0 }; - unsigned long long nearestTime = s_nearest_time.tv_sec * MICRO_SECONDS + s_nearest_time.tv_usec; - unsigned long long currentTime = current_time.tv_sec * MICRO_SECONDS + current_time.tv_usec; + if (nearest_p != NULL && !timerisset(nearest_p)) + return nearest_p; + else + return &no_timers; +} - if (nearestTime < currentTime) { - s_select_time.tv_sec = 0; - s_select_time.tv_usec = 0; +static void update_nearest(struct timeval *cand, struct timeval *current) +{ + if (cand->tv_sec != LONG_MAX) { + if (timercmp(cand, current, >)) + timersub(cand, current, &nearest); + else { + /* loop again inmediately */ + nearest.tv_sec = 0; + nearest.tv_usec = 0; + } + nearest_p = &nearest; } else { - s_select_time.tv_sec = (nearestTime - currentTime) / MICRO_SECONDS; - s_select_time.tv_usec = (nearestTime - currentTime) % MICRO_SECONDS; + nearest_p = NULL; } - - return &s_select_time; } /* @@ -143,17 +161,18 @@ struct timeval *osmo_timers_nearest(void) */ void osmo_timers_prepare(void) { - struct osmo_timer_list *timer, *nearest_timer = NULL; - llist_for_each_entry(timer, &timer_list, entry) { - if (!nearest_timer || TIME_SMALLER(timer->timeout, nearest_timer->timeout)) { - nearest_timer = timer; - } - } + struct rb_node *node; + struct timeval current; + + gettimeofday(¤t, NULL); - if (nearest_timer) { - s_nearest_time = nearest_timer->timeout; + node = rb_first(&timer_root); + if (node) { + struct osmo_timer_list *this; + this = container_of(node, struct osmo_timer_list, node); + update_nearest(&this->timeout, ¤t); } else { - memset(&s_nearest_time, 0, sizeof(struct timeval)); + nearest_p = NULL; } } @@ -163,46 +182,41 @@ void osmo_timers_prepare(void) int osmo_timers_update(void) { struct timeval current_time; - struct osmo_timer_list *timer, *tmp; + struct rb_node *node; + struct llist_head timer_eviction_list; + struct osmo_timer_list *this; int work = 0; gettimeofday(¤t_time, NULL); + INIT_LLIST_HEAD(&timer_eviction_list); + for (node = rb_first(&timer_root); node; node = rb_next(node)) { + this = container_of(node, struct osmo_timer_list, node); + + if (timercmp(&this->timeout, ¤t_time, >)) + break; + + llist_add(&this->list, &timer_eviction_list); + } + /* * The callbacks might mess with our list and in this case * even llist_for_each_entry_safe is not safe to use. To allow - * del_timer, add_timer, schedule_timer to be called from within - * the callback we jump through some loops. + * osmo_timer_del to be called from within the callback we need + * to restart the iteration for each element scheduled for removal. * - * First we set the handled flag of each active timer to zero, - * then we iterate over the list and execute the callbacks. As the - * list might have been changed (specially the next) from within - * the callback we have to start over again. Once every callback - * is dispatched we will remove the non-active from the list. - * - * TODO: If this is a performance issue we can poison a global - * variable in add_timer and del_timer and only then restart. + * The problematic scenario is the following: Given two timers A + * and B that have expired at the same time. Thus, they are both + * in the eviction list in this order: A, then B. If we remove + * timer B from the A's callback, we continue with B in the next + * iteration step, leading to an access-after-release. */ - llist_for_each_entry(timer, &timer_list, entry) { - timer->handled = 0; - } - restart: - llist_for_each_entry(timer, &timer_list, entry) { - if (!timer->handled && TIME_SMALLER(timer->timeout, current_time)) { - timer->handled = 1; - timer->active = 0; - (*timer->cb)(timer->data); - work = 1; - goto restart; - } - } - - llist_for_each_entry_safe(timer, tmp, &timer_list, entry) { - timer->handled = 0; - if (!timer->active) { - osmo_timer_del(timer); - } + llist_for_each_entry(this, &timer_eviction_list, list) { + osmo_timer_del(this); + this->cb(this->data); + work = 1; + goto restart; } return work; @@ -210,10 +224,10 @@ restart: int osmo_timers_check(void) { - struct osmo_timer_list *timer; + struct rb_node *node; int i = 0; - llist_for_each_entry(timer, &timer_list, entry) { + for (node = rb_first(&timer_root); node; node = rb_next(node)) { i++; } return i; -- cgit v1.2.3 From 9ebc5056b464ffd8384cdd8302361d997cafcfbc Mon Sep 17 00:00:00 2001 From: Pablo Neira Ayuso Date: Mon, 26 Sep 2011 11:46:32 +0200 Subject: tests: add new torture test for timer infrastructure This is a new test for the timer infrastructure. It basically consists of adding 2^N timers per step (where N is the number of step) that expire in (random() % 10) + 1 seconds. Moreover, we randomly delete timers that fulfill (random() % 100) < 10 everytime one timer expires. The default number of steps is 16, the test also allows to check for timer imprecisions (currently, defaulting to 10ms as aceptable). The list-based implementation crashes or it seems loop forever with this test (I guess due to some memory corruption). BTW, this patch contains one cosmetic clean up since we go back to 8-chars per indentations, which seems to be the policy in osmocom. --- tests/timer/timer_test.c | 141 ++++++++++++++++++++++++++++++++++++----------- 1 file changed, 108 insertions(+), 33 deletions(-) diff --git a/tests/timer/timer_test.c b/tests/timer/timer_test.c index 240bc480..bcaafdb2 100644 --- a/tests/timer/timer_test.c +++ b/tests/timer/timer_test.c @@ -1,7 +1,11 @@ /* * (C) 2008 by Holger Hans Peter Freyther + * (C) 2011 by Harald Welte * All Rights Reserved * + * Authors: Holger Hans Peter Freyther + * Pablo Neira Ayuso + * * This program 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 @@ -19,59 +23,130 @@ */ #include +#include +#include #include #include +#include #include "../../config.h" -static void timer_fired(void *data); +static void main_timer_fired(void *data); +static void secondary_timer_fired(void *data); -static struct osmo_timer_list timer_one = { - .cb = timer_fired, - .data = (void*)1, +static unsigned int main_timer_step = 0; +static struct osmo_timer_list main_timer = { + .cb = main_timer_fired, + .data = &main_timer_step, }; -static struct osmo_timer_list timer_two = { - .cb = timer_fired, - .data = (void*)2, -}; +static LLIST_HEAD(timer_test_list); -static struct osmo_timer_list timer_three = { - .cb = timer_fired, - .data = (void*)3, +struct test_timer { + struct llist_head head; + struct osmo_timer_list timer; + struct timeval start; + struct timeval stop; }; -static void timer_fired(void *_data) +/* number of test steps. We add fact(steps) timers in the whole test. */ +#define MAIN_TIMER_NSTEPS 16 + +/* time between two steps, in secs. */ +#define TIME_BETWEEN_STEPS 1 + +/* timer imprecision that we accept for this test: 10 milliseconds. */ +#define TIMER_PRES_SECS 0 +#define TIMER_PRES_USECS 10000 + +static unsigned int expired_timers = 0; +static unsigned int total_timers = 0; +static unsigned int too_late = 0; + +static void main_timer_fired(void *data) +{ + unsigned int *step = data; + unsigned int add_in_this_step; + int i; + + if (*step == MAIN_TIMER_NSTEPS) { + printf("Main timer has finished, please, wait a bit for the " + "final report.\n"); + return; + } + /* add 2^step pair of timers per step. */ + add_in_this_step = (1 << *step); + + for (i=0; istart, NULL); + v->timer.cb = secondary_timer_fired; + v->timer.data = v; + unsigned int seconds = (random() % 10) + 1; + v->stop.tv_sec = v->start.tv_sec + seconds; + osmo_timer_schedule(&v->timer, seconds, 0); + llist_add(&v->head, &timer_test_list); + } + printf("added %d timers in step %u (expired=%u)\n", + add_in_this_step, *step, expired_timers); + total_timers += add_in_this_step; + osmo_timer_schedule(&main_timer, TIME_BETWEEN_STEPS, 0); + (*step)++; +} + +static void secondary_timer_fired(void *data) { - unsigned long data = (unsigned long) _data; - printf("Fired timer: %lu\n", data); - - if (data == 1) { - osmo_timer_schedule(&timer_one, 3, 0); - osmo_timer_del(&timer_two); - } else if (data == 2) { - printf("Should not be fired... bug in del_timer\n"); - } else if (data == 3) { - printf("Timer fired not registering again\n"); - } else { - printf("wtf... wrong data\n"); - } + struct test_timer *v = data, *this, *tmp; + struct timeval current, res, precision = { 1, 0 }; + + gettimeofday(¤t, NULL); + + timersub(¤t, &v->stop, &res); + if (timercmp(&res, &precision, >)) { + printf("ERROR: timer %p has expired too late!\n", v->timer); + too_late++; + } + + llist_del(&v->head); + talloc_free(data); + expired_timers++; + if (expired_timers == total_timers) { + printf("test over: added=%u expired=%u too_late=%u \n", + total_timers, expired_timers, too_late); + exit(EXIT_SUCCESS); + } + + /* randomly (10%) deletion of timers. */ + llist_for_each_entry_safe(this, tmp, &timer_test_list, head) { + if ((random() % 100) < 10) { + osmo_timer_del(&this->timer); + llist_del(&this->head); + talloc_free(this); + expired_timers++; + } + } } int main(int argc, char** argv) { - printf("Starting... timer\n"); + printf("Running timer test for %u steps, accepting imprecision " + "of %u.%.6u seconds\n", + MAIN_TIMER_NSTEPS, TIMER_PRES_SECS, TIMER_PRES_USECS); - osmo_timer_schedule(&timer_one, 3, 0); - osmo_timer_schedule(&timer_two, 5, 0); - osmo_timer_schedule(&timer_three, 4, 0); + osmo_timer_schedule(&main_timer, 1, 0); #ifdef HAVE_SYS_SELECT_H - while (1) { - osmo_select_main(0); - } + while (1) { + osmo_select_main(0); + } #else - printf("Select not supported on this platform!\n"); + printf("Select not supported on this platform!\n"); #endif } -- cgit v1.2.3 From 4a0a163d817a08662adef7a286cb01cbdef47b05 Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Mon, 17 Oct 2011 13:26:52 +0200 Subject: bump major library version / breaking the ABI with the rb_tree timers --- src/Makefile.am | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/Makefile.am b/src/Makefile.am index dfc2d493..89b8138f 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -2,7 +2,7 @@ SUBDIRS=. vty codec gsm # This is _NOT_ the library release version, it's an API version. # Please read Chapter 6 "Library interface versions" of the libtool documentation before making any modification -LIBVERSION=2:1:0 +LIBVERSION=3:0:0 INCLUDES = $(all_includes) -I$(top_srcdir)/include AM_CFLAGS = -fPIC -Wall -- cgit v1.2.3