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.
diff --git a/include/osmocom/core/timer.h b/include/osmocom/core/timer.h
index 8f8c826..30f558b 100644
--- a/include/osmocom/core/timer.h
+++ b/include/osmocom/core/timer.h
@@ -32,6 +32,7 @@
#include <sys/time.h>
#include <osmocom/core/linuxlist.h>
+#include <osmocom/core/linuxrbtree.h>
/**
* 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 */