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. --- src/Makefile.am | 2 +- src/rbtree.c | 389 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 390 insertions(+), 1 deletion(-) create mode 100644 src/rbtree.c (limited to 'src') 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. --- src/timer.c | 176 ++++++++++++++++++++++++++++++++---------------------------- 1 file changed, 95 insertions(+), 81 deletions(-) (limited to 'src') 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 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(-) (limited to 'src') 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