New timer scheduler that can sleep for long times
authorHenning Rogge <henning.rogge@fkie.fraunhofer.de>
Wed, 29 Feb 2012 15:06:26 +0000 (16:06 +0100)
committerHenning Rogge <henning.rogge@fkie.fraunhofer.de>
Wed, 29 Feb 2012 15:06:26 +0000 (16:06 +0100)
13 files changed:
CMake.config
src/common/common_types.h
src/core/CMakeLists.txt
src/core/olsr_clock.c
src/core/olsr_socket.c
src/core/olsr_socket.h
src/core/olsr_timer.c
src/core/olsr_timer.h
src/core/os_clock.h [new file with mode: 0644]
src/core/os_linux/os_clock_linux.c [new file with mode: 0644]
src/core/os_linux/os_clock_linux.h [new file with mode: 0644]
src/core/os_linux/os_system_linux.c
src/olsr_main.c

index 406d218..6e4bc13 100644 (file)
@@ -22,16 +22,16 @@ set (OONF_VERSION_TRAILER "Visit http://www.olsr.org\\\\n")
 set (OONF_VERSION 0.7.0)
 
 # set static plugins (space separated list of plugin names)
-set (OONF_STATIC_PLUGINS cfgparser_compact cfgio_file remotecontrol httptelnet)
+set (OONF_STATIC_PLUGINS cfgparser_compact cfgio_file) # remotecontrol httptelnet)
 
 # choose if framework should be linked static or dynamic
 set (OONF_FRAMEWORD_DYNAMIC false)
 
 # set to true to stop application running without root privileges (true/false)
-set (OONF_NEED_ROOT true)
+set (OONF_NEED_ROOT false)
 
 # set to true if the application needs to set ip routes for traffic forwarding
-set (OONF_NEED_ROUTING true)
+set (OONF_NEED_ROUTING false)
 
 # allow removal of Logging levels from code
 set (OONF_REMOVE_DEBUG_LOGGING false)
index 48f9461..2c1cba3 100644 (file)
@@ -102,19 +102,45 @@ typedef signed int int32_t;
 typedef signed long long int64_t;
 
 /* Minimum of signed integral types.  */
+#ifndef INT8_MIN
 # define INT8_MIN   (-128)
+#endif
+#ifndef INT16_MIN
 # define INT16_MIN    (-32767-1)
+#endif
+#ifndef INT32_MIN
 # define INT32_MIN    (-2147483647-1)
+#endif
 
 /* Maximum of signed integral types.  */
+#ifndef INT8_MAX
 # define INT8_MAX   (127)
+#endif
+#ifndef INT16_MAX
 # define INT16_MAX    (32767)
+#endif
+#ifndef INT32_MAX
 # define INT32_MAX    (2147483647)
+#endif
 
 /* Maximum of unsigned integral types.  */
+#ifndef UINT8_MAX
 # define UINT8_MAX    (255)
+#endif
+#ifndef UINT16_MAX
 # define UINT16_MAX   (65535)
+#endif
+#ifndef UINT32_MAX
 # define UINT32_MAX   (4294967295U)
+#endif
+
+/* printf modifier for int64_t and uint64_t */
+#ifndef PRId64
+#define PRId64        "lld"
+#endif
+#ifndef PRIu64
+#define PRIu64        "llu"
+#endif
 
 #ifdef __GNUC__
 /* we simulate a C99 environment */
index a79ca90..a92fb1b 100644 (file)
@@ -26,7 +26,8 @@ IF(LINUX)
     SET(OONF_CORE_SRCS ${OONF_CORE_SRCS}
                        os_linux/os_net_linux.c
                        os_linux/os_system_linux.c
-                       os_linux/os_routing_linux.c)
+                       os_linux/os_routing_linux.c
+                       os_linux/os_clock_linux.c)
 ENDIF(LINUX)
 
 IF(BSD)
index 4843e44..5e1ade0 100644 (file)
@@ -45,7 +45,7 @@
 #include <stdio.h>
 #include <time.h>
 
-#include "os_system.h"
+#include "os_clock.h"
 #include "olsr_logging.h"
 #include "olsr_clock.h"
 #include "olsr.h"
@@ -68,11 +68,13 @@ olsr_clock_init(void) {
   if (olsr_subsystem_is_initialized(&_clock_state))
     return 0;
 
-  if (os_system_gettime64(&start_time)) {
+  if (os_clock_gettime64(&start_time)) {
     OLSR_WARN(LOG_TIMER, "OS clock is not working: %s (%d)\n", strerror(errno), errno);
     return -1;
   }
 
+  now_times = 0;
+
   olsr_subsystem_init(&_clock_state);
   return 0;
 }
@@ -92,8 +94,9 @@ olsr_clock_cleanup(void) {
 int
 olsr_clock_update(void)
 {
+
   uint64_t now;
-  if (os_system_gettime64(&now)) {
+  if (os_clock_gettime64(&now)) {
     OLSR_WARN(LOG_TIMER, "OS clock is not working: %s (%d)\n", strerror(errno), errno);
     return -1;
   }
index e27b73a..4d476e5 100644 (file)
@@ -51,6 +51,7 @@
 #include "olsr_logging.h"
 #include "os_net.h"
 #include "olsr_socket.h"
+#include "olsr_timer.h"
 #include "olsr.h"
 
 /* List of all active sockets in scheduler */
@@ -119,41 +120,25 @@ olsr_socket_remove(struct olsr_socket_entry *entry)
 
 /**
  * Handle all incoming socket events until a certain time
- * @param until_time timestamp when the function should return
+ * @param stop_time timestamp when the handler should stop,
+ *   0 if it should keep running
  * @return -1 if an error happened, 0 otherwise
  */
 int
-olsr_socket_handle(uint32_t until_time)
+olsr_socket_handle(uint64_t stop_time)
 {
   struct olsr_socket_entry *entry, *iterator;
-  struct timeval tvp;
-  int32_t remaining;
+  uint64_t next_event;
+  struct timeval tv, *tv_ptr;
   int n = 0;
   bool fd_read;
   bool fd_write;
 
-  /* Update time since this is much used by the parsing functions */
-  if (olsr_clock_update()) {
-    return -1;
+  if (stop_time == 0) {
+    stop_time = ~0ull;
   }
 
-  remaining = olsr_clock_getRelative(until_time);
-  if (remaining <= 0) {
-    /* we are already over the interval */
-    if (list_is_empty(&socket_head)) {
-      /* If there are no registered sockets we do not call select(2) */
-      return 0;
-    }
-    tvp.tv_sec = 0;
-    tvp.tv_usec = 0;
-  } else {
-    /* we need an absolute time - milliseconds */
-    tvp.tv_sec = remaining / MSEC_PER_SEC;
-    tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
-  }
-
-  /* do at least one select */
-  for (;;) {
+  while (olsr_is_running()) {
     fd_set ibits, obits;
     int hfd = 0;
 
@@ -182,19 +167,46 @@ olsr_socket_handle(uint32_t until_time)
       }
     }
 
-    if (hfd == 0 && (long)remaining <= 0) {
-      /* we are over the interval and we have no fd's. Skip the select() etc. */
-      return 0;
-    }
-
     do {
-      n = os_select(hfd,
-          fd_read ? &ibits : NULL,
-          fd_write ? &obits : NULL,
-          NULL, &tvp);
+      /* Update time since this is much used by the parsing functions */
+      if (olsr_clock_update()) {
+        return -1;
+      }
+
+      if (olsr_clock_getNow() >= stop_time) {
+        return 0;
+      }
+
+      if (olsr_timer_getNextEvent() <= olsr_clock_getNow()) {
+        olsr_timer_walk();
+      }
+
+      next_event = olsr_timer_getNextEvent();
+      if (next_event > stop_time) {
+        next_event = stop_time;
+      }
+
+      if (next_event == ~0ull) {
+        /* no events waiting */
+        tv_ptr = NULL;
+      }
+      else {
+        /* convert time interval until event triggers */
+        next_event = olsr_clock_getRelative(next_event);
+
+        tv_ptr = &tv;
+        tv.tv_sec = (time_t)(next_event / 1000ull);
+        tv.tv_usec = (int)(next_event % 1000) * 1000;
+        fprintf(stderr, "Sleep time %ld.%03ld seconds (%"PRIu64", %"PRIu64")\n",
+            tv.tv_sec, tv.tv_usec/1000, olsr_clock_getNow(), olsr_timer_getNextEvent());
+      }
       if (!olsr_is_running()) {
         return 0;
       }
+      n = os_select(hfd,
+          fd_read ? &ibits : NULL,
+          fd_write ? &obits : NULL,
+          NULL, tv_ptr);
     } while (n == -1 && errno == EINTR);
 
     if (n == 0) {               /* timeout! */
@@ -202,13 +214,12 @@ olsr_socket_handle(uint32_t until_time)
     }
     if (n < 0) {              /* Did something go wrong? */
       OLSR_WARN(LOG_SOCKET, "select error: %s (%d)", strerror(errno), errno);
-      break;
+      return -1;
     }
 
     /* Update time since this is much used by the parsing functions */
     if (olsr_clock_update()) {
-      n = -1;
-      break;
+      return -1;
     }
     OLSR_FOR_ALL_SOCKETS(entry, iterator) {
       if (entry->process == NULL) {
@@ -221,19 +232,6 @@ olsr_socket_handle(uint32_t until_time)
         entry->process(entry->fd, entry->data, fd_read, fd_write);
       }
     }
-
-    /* calculate the next timeout */
-    remaining = olsr_clock_getRelative(until_time);
-    if (remaining <= 0) {
-      /* we are already over the interval */
-      break;
-    }
-    /* we need an absolute time - milliseconds */
-    tvp.tv_sec = remaining / MSEC_PER_SEC;
-    tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
   }
-
-  if (n<0)
-    return -1;
   return 0;
 }
index 546d3cb..b453554 100644 (file)
@@ -74,7 +74,7 @@ EXPORT extern struct list_entity socket_head;
 
 EXPORT void olsr_socket_init(void);
 EXPORT void olsr_socket_cleanup(void);
-EXPORT int olsr_socket_handle(uint32_t until_time) __attribute__((warn_unused_result));
+EXPORT int olsr_socket_handle(uint64_t) __attribute__((warn_unused_result));
 
 EXPORT void olsr_socket_add(struct olsr_socket_entry *);
 EXPORT void olsr_socket_remove(struct olsr_socket_entry *);
index 663eba8..4498f75 100644 (file)
 #include <unistd.h>
 
 #include "common/avl.h"
-#include "common/avl_comp.h"
+#include "common/common_types.h"
 #include "olsr_clock.h"
 #include "olsr_logging.h"
 #include "olsr_memcookie.h"
 #include "olsr_timer.h"
 #include "olsr.h"
 
-/* Hashed root of all timers */
-static struct list_entity _timer_wheel[TIMER_WHEEL_SLOTS];
-static uint64_t _timer_last_run;        /* remember the last timeslot walk */
+/* BUCKET_COUNT and BUCKET_TIMESLICE must be powers of 2 */
+#define BUCKET_DEPTH 3
+#define BUCKET_COUNT 512ull
+#define BUCKET_TIMESLICE 128ull /* ms */
+
+/* root of all timers */
+static struct list_entity _buckets[BUCKET_COUNT][BUCKET_DEPTH];
+static int _bucket_ptr[BUCKET_DEPTH];
+
+/* time when the next timer will fire */
+static uint64_t _next_fire_event;
+
+/* number of timer events still in queue */
+static uint32_t _total_timer_events;
 
 /* Memory cookie for the timer manager */
 struct list_entity timerinfo_list;
@@ -67,7 +78,9 @@ static struct olsr_memcookie_info _timer_mem_cookie = {
 OLSR_SUBSYSTEM_STATE(_timer_state);
 
 /* Prototypes */
-static uint64_t calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int random_val);
+static uint64_t _calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int random_val);
+static void _insert_into_bucket(struct olsr_timer_entry *);
+static void _calculate_next_event(void);
 
 /**
  * Initialize timer scheduler subsystem
@@ -76,22 +89,33 @@ static uint64_t calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int
 void
 olsr_timer_init(void)
 {
-  int idx;
+  uint64_t now, offset;
+  unsigned i,j;
 
   if (olsr_subsystem_init(&_timer_state))
     return;
 
-  OLSR_INFO(LOG_SOCKET, "Initializing scheduler.\n");
+  OLSR_INFO(LOG_TIMER, "Initializing timer scheduler.\n");
+  /* mask "last run" to slot size */
+  now = olsr_clock_getNow();
+
+  offset = BUCKET_TIMESLICE * BUCKET_COUNT;
+  now /= BUCKET_TIMESLICE;
 
-  /* init lists */
-  for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
-    list_init_head(&_timer_wheel[idx]);
+  for (i = 0; i < BUCKET_DEPTH; i++) {
+    _bucket_ptr[i] = now & (BUCKET_COUNT - 1ull);
+
+    now /= BUCKET_COUNT;
+    offset *= BUCKET_COUNT;
+
+    for (j = 0; j < BUCKET_COUNT; j++) {
+      list_init_head(&_buckets[j][i]);
+    }
   }
 
-  /*
-   * Reset the last timer run.
-   */
-  _timer_last_run = olsr_clock_getNow();
+  /* at the moment we have no timer */
+  _next_fire_event = ~0ull;
+  _total_timer_events = 0;
 
   /* initialize a cookie for the block based memory manager. */
   olsr_memcookie_add(&_timer_mem_cookie);
@@ -107,20 +131,22 @@ olsr_timer_cleanup(void)
 {
   struct olsr_timer_info *ti, *iterator;
   struct list_entity *timer_head_node;
-  unsigned int wheel_slot = 0;
+  unsigned i,j;
 
   if (olsr_subsystem_cleanup(&_timer_state))
     return;
 
-  for (wheel_slot = 0; wheel_slot < TIMER_WHEEL_SLOTS; wheel_slot++) {
-    timer_head_node = &_timer_wheel[wheel_slot & TIMER_WHEEL_MASK];
+  for (i = 0; i < BUCKET_DEPTH; i++) {
+    for (j = 0; j < BUCKET_COUNT; j++) {
+      timer_head_node = &_buckets[j][i];
 
-    /* Kill all entries hanging off this hash bucket. */
-    while (!list_is_empty(timer_head_node)) {
-      struct olsr_timer_entry *timer;
+      /* Kill all entries hanging off this hash bucket. */
+      while (!list_is_empty(timer_head_node)) {
+        struct olsr_timer_entry *timer;
 
-      timer = list_first_element(timer_head_node, timer, timer_list);
-      olsr_timer_stop(timer);
+        timer = list_first_element(timer_head_node, timer, _node);
+        olsr_timer_stop(timer);
+      }
     }
   }
 
@@ -150,13 +176,15 @@ olsr_timer_add(struct olsr_timer_info *ti) {
 void
 olsr_timer_remove(struct olsr_timer_info *info) {
   struct olsr_timer_entry *timer, *iterator;
-  int slot;
-
-  for (slot=0; slot < TIMER_WHEEL_SLOTS; slot++) {
-    list_for_each_element_safe(&_timer_wheel[slot], timer, timer_list, iterator) {
-      /* remove all timers of this timer_info */
-      if (timer->timer_info == info) {
-        olsr_timer_stop(timer);
+  unsigned i,j;
+
+  for (i = 0; i < BUCKET_DEPTH; i++) {
+    for (j = 0; j < BUCKET_COUNT; j++) {
+      list_for_each_element_safe(&_buckets[j][i], timer, _node, iterator) {
+        /* remove all timers of this timer_info */
+        if (timer->timer_info == info) {
+          olsr_timer_stop(timer);
+        }
       }
     }
   }
@@ -177,13 +205,14 @@ olsr_timer_start(uint64_t rel_time,
     uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
 {
   struct olsr_timer_entry *timer;
+
 #if !defined(REMOVE_LOG_DEBUG)
   struct timeval_buf timebuf;
 #endif
 
-  assert(ti != 0);          /* we want timer cookies everywhere */
-  assert(rel_time);
+  assert(ti != 0);
   assert(jitter_pct <= 100);
+  assert (rel_time > 0 && rel_time < 1000ull * INT32_MAX);
 
   timer = olsr_memcookie_malloc(&_timer_mem_cookie);
 
@@ -195,7 +224,7 @@ olsr_timer_start(uint64_t rel_time,
   }
 
   /* Fill entry */
-  timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
+  timer->timer_clock = _calc_jitter(rel_time, jitter_pct, timer->timer_random);
   timer->timer_cb_context = context;
   timer->timer_jitter_pct = jitter_pct;
   timer->timer_running = true;
@@ -211,7 +240,13 @@ olsr_timer_start(uint64_t rel_time,
   /*
    * Now insert in the respective _timer_wheel slot.
    */
-  list_add_before(&_timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
+  _insert_into_bucket(timer);
+
+  /* and update internal time data */
+  _total_timer_events++;
+  if (timer->timer_clock < _next_fire_event) {
+    _next_fire_event = timer->timer_clock;
+  }
 
   OLSR_DEBUG(LOG_TIMER, "TIMER: start %s timer %p firing in %s, ctx %p\n",
              ti->name, timer, olsr_clock_toClockString(&timebuf, timer->timer_clock), context);
@@ -231,9 +266,6 @@ olsr_timer_stop(struct olsr_timer_entry *timer)
     return;
   }
 
-  assert(timer->timer_info);     /* we want timer cookies everywhere */
-  assert(timer->timer_list.next != NULL && timer->timer_list.prev != NULL);
-
   OLSR_DEBUG(LOG_TIMER, "TIMER: stop %s timer %p, ctx %p\n",
              timer->timer_info->name, timer, timer->timer_cb_context);
 
@@ -241,11 +273,17 @@ olsr_timer_stop(struct olsr_timer_entry *timer)
   /*
    * Carve out of the existing wheel_slot and free.
    */
-  list_remove(&timer->timer_list);
+  list_remove(&timer->_node);
   timer->timer_running = false;
   timer->timer_info->usage--;
   timer->timer_info->changes++;
 
+  /* and update internal time data */
+  _total_timer_events--;
+  if (_next_fire_event == timer->timer_clock) {
+    _calculate_next_event();
+  }
+
   if (!timer->timer_in_callback) {
     olsr_memcookie_free(&_timer_mem_cookie, timer);
   }
@@ -263,29 +301,41 @@ olsr_timer_change(struct olsr_timer_entry *timer, uint64_t rel_time, uint8_t jit
 #if !defined(REMOVE_LOG_DEBUG)
   struct timeval_buf timebuf;
 #endif
+  bool recalculate;
 
   /* Sanity check. */
   if (!timer) {
     return;
   }
 
-  assert(timer->timer_info);     /* we want timer cookies everywhere */
+  assert (rel_time < 1000ull * INT32_MAX);
+
+  /* remember if we have to recalculate the _next_fire_event variable */
+  recalculate = _next_fire_event == timer->timer_clock;
 
   /* Singleshot or periodical timer ? */
   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
 
-  timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
+  timer->timer_clock = _calc_jitter(rel_time, jitter_pct, timer->timer_random);
   timer->timer_jitter_pct = jitter_pct;
 
   /*
-   * Changes are easy: Remove timer from the exisiting _timer_wheel slot
+   * Changes are easy: Remove timer from the existing _timer_wheel slot
    * and reinsert into the new slot.
    */
-  list_remove(&timer->timer_list);
-  list_add_before(&_timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
 
-  OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
-             timer->timer_info->name, timer,
+  list_remove(&timer->_node);
+  _insert_into_bucket(timer);
+
+  if (timer->timer_clock < _next_fire_event) {
+    _next_fire_event = timer->timer_clock;
+  }
+  else if (recalculate) {
+    _calculate_next_event();
+  }
+
+  OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer, firing to %s, ctx %p\n",
+             timer->timer_info->name,
              olsr_clock_toClockString(&timebuf, timer->timer_clock), timer->timer_cb_context);
 }
 
@@ -327,100 +377,87 @@ olsr_timer_set(struct olsr_timer_entry **timer_ptr,
 void
 olsr_timer_walk(void)
 {
-  int timers_walked = 0, timers_fired = 0;
-  int wheel_slot_walks = 0;
-
-  /*
-   * Check the required wheel slots since the last time a timer walk was invoked,
-   * or check *all* the wheel slots, whatever is less work.
-   * The latter is meant as a safety belt if the scheduler falls behind.
-   */
-  while ((_timer_last_run <= olsr_clock_getNow()) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
-    struct list_entity tmp_head_node;
-
-    /* Get the hash slot for this clocktick */
-    struct list_entity *timer_head_node;
-
-    timer_head_node = &_timer_wheel[_timer_last_run & TIMER_WHEEL_MASK];
-
-    /* Walk all entries hanging off this hash bucket. We treat this basically as a stack
-     * so that we always know if and where the next element is.
-     */
-    list_init_head(&tmp_head_node);
-    while (!list_is_empty(timer_head_node)) {
-      /* the top element */
-      struct olsr_timer_entry *timer;
-
-      timer = list_first_element(timer_head_node, timer, timer_list);
-
-      /*
-       * Dequeue and insert to a temporary list.
-       * We do this to avoid loosing our walking context when
-       * multiple timers fire.
-       */
-      list_remove(&timer->timer_list);
-      list_add_after(&tmp_head_node, &timer->timer_list);
-      timers_walked++;
-
-      /* Ready to fire ? */
-      if (olsr_clock_isPast(timer->timer_clock)) {
-        OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
-                   "at clocktick %" PRIu64 "\n",
-                   timer->timer_info->name,
-                   timer, timer->timer_cb_context, _timer_last_run);
-
-        /* This timer is expired, call into the provided callback function */
-        timer->timer_in_callback = true;
-        timer->timer_info->callback(timer->timer_cb_context);
-        timer->timer_in_callback = false;
-        timer->timer_info->changes++;
-
-        /* Only act on actually running timers */
-        if (timer->timer_running) {
-          /*
-           * Don't restart the periodic timer if the callback function has
-           * stopped the timer.
-           */
-          if (timer->timer_period) {
-            /* For periodical timers, rehash the random number and restart */
-            timer->timer_random = random();
-            olsr_timer_change(timer, timer->timer_period, timer->timer_jitter_pct);
-          } else {
-            /* Singleshot timers are stopped */
-            olsr_timer_stop(timer);
-          }
-        }
-        else {
-          /* free memory */
-          olsr_memcookie_free(&_timer_mem_cookie, timer);
-        }
-
-        timers_fired++;
-      }
+  struct olsr_timer_entry *timer, *t_it;
+  int i;
+
+  while (_next_fire_event <= olsr_clock_getNow()) {
+    i = _bucket_ptr[0];
+    list_for_each_element_safe(&_buckets[i][0], timer, _node, t_it) {
+      OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
+                  "at clocktick %" PRIu64 "\n",
+                  timer->timer_info->name,
+                  timer, timer->timer_cb_context, _next_fire_event);
+
+       /* This timer is expired, call into the provided callback function */
+       timer->timer_in_callback = true;
+       timer->timer_info->callback(timer->timer_cb_context);
+       timer->timer_in_callback = false;
+       timer->timer_info->changes++;
+
+       /* Only act on actually running timers */
+       if (timer->timer_running) {
+         /*
+          * Don't restart the periodic timer if the callback function has
+          * stopped the timer.
+          */
+         if (timer->timer_period) {
+           /* For periodical timers, rehash the random number and restart */
+           timer->timer_random = random();
+           olsr_timer_change(timer, timer->timer_period, timer->timer_jitter_pct);
+         } else {
+           /* Singleshot timers are stopped */
+           olsr_timer_stop(timer);
+         }
+       }
+       else {
+         /* free memory */
+         olsr_memcookie_free(&_timer_mem_cookie, timer);
+       }
     }
 
-    /*
-     * Now merge the temporary list back to the old bucket.
-     */
-    list_merge(timer_head_node, &tmp_head_node);
-
-    /* Increment the time slot and wheel slot walk iteration */
-    _timer_last_run++;
-    wheel_slot_walks++;
+    /* advance our 'next event' marker */
+    _calculate_next_event();
   }
+}
 
-  OLSR_DEBUG(LOG_TIMER, "TIMER: processed %4u/%d clockwheel slots, "
-             "timers walked %u, timers fired %u\n",
-             wheel_slot_walks, TIMER_WHEEL_SLOTS,
-             timers_walked, timers_fired);
+/**
+ * @return timestamp when next timer will fire
+ */
+uint64_t
+olsr_timer_getNextEvent(void) {
+  return _next_fire_event;
+}
 
-  /*
-   * If the scheduler has slipped and we have walked all wheel slots,
-   * reset the last timer run.
-   */
-  _timer_last_run = olsr_clock_getNow();
+/**
+ *
+ * @param timestamp
+ * @param depth
+ * @return true if the
+ */
+static void
+_insert_into_bucket(struct olsr_timer_entry *timer) {
+  uint64_t slot;
+  int64_t relative;
+  int group;
+
+  slot = timer->timer_clock / BUCKET_TIMESLICE;
+  relative = olsr_clock_getRelative(timer->timer_clock) / BUCKET_TIMESLICE;
+  OLSR_DEBUG(LOG_TIMER, "Insert new timer: %" PRIu64, relative);
+
+  for (group = 0; group < BUCKET_DEPTH; group++, slot /= BUCKET_COUNT, relative /= BUCKET_COUNT) {
+    if (relative < (int64_t)BUCKET_COUNT) {
+      slot %= BUCKET_COUNT;
+      OLSR_DEBUG_NH(LOG_TIMER, "    Insert into bucket: %" PRId64"/%d", slot, group);
+      list_add_tail(&_buckets[slot][group], &timer->_node);
+      return;
+    }
+  }
+
+  OLSR_WARN(LOG_TIMER, "Error, timer event too far in the future: %" PRIu64,
+      olsr_clock_getRelative(timer->timer_clock));
 }
 
+
 /**
  * Decrement a relative timer by a random number range.
  * @param the relative timer expressed in units of milliseconds.
@@ -429,7 +466,7 @@ olsr_timer_walk(void)
  * @return the absolute time when timer will fire
  */
 static uint64_t
-calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int random_val)
+_calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int random_val)
 {
   uint64_t jitter_time;
 
@@ -444,11 +481,80 @@ calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int random_val)
   /*
    * Play some tricks to avoid overflows with integer arithmetic.
    */
-  jitter_time = (jitter_pct * rel_time) / 100;
-  jitter_time = random_val / (1 + RAND_MAX / (jitter_time + 1));
+  jitter_time = ((uint64_t)jitter_pct * rel_time) / 100;
+  jitter_time = (uint64_t)random_val / (1ull + (uint64_t)RAND_MAX / (jitter_time + 1ull));
 
   OLSR_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %" PRIu64 "ms to %" PRIu64 "ms\n",
       jitter_pct, rel_time, rel_time - jitter_time);
 
   return olsr_clock_get_absolute(rel_time - jitter_time);
 }
+
+static void
+_copy_bucket(unsigned depth, unsigned idx) {
+  struct olsr_timer_entry *timer, *timer_it;
+  uint64_t divide;
+  unsigned i;
+
+  assert (depth > 0 && depth < BUCKET_DEPTH && idx < BUCKET_COUNT);
+
+  divide = BUCKET_TIMESLICE;
+  for (i = 0; i < depth-1; i++) {
+    divide *= BUCKET_COUNT;
+  }
+
+  _bucket_ptr[depth] = idx+1;
+
+  list_for_each_element_safe(&_buckets[idx][depth], timer, _node, timer_it) {
+    list_remove(&timer->_node);
+
+    i = (timer->timer_clock / divide) & (BUCKET_COUNT - 1ull);
+    list_add_tail(&_buckets[i][depth-1], &timer->_node);
+  }
+}
+
+static int
+_look_for_event(unsigned depth) {
+  unsigned i,j;
+  int idx;
+
+  /* first look in existing data */
+  for (i=_bucket_ptr[depth], j=0; j < BUCKET_COUNT; i=(i+1)&255, j++) {
+    if (!list_is_empty(&_buckets[i][depth])) {
+      return i;
+    }
+  }
+
+  /* copy bucket from level higher if possible */
+  if (depth < BUCKET_DEPTH - 1) {
+    idx = _look_for_event(depth+1);
+    if (idx != -1) {
+      _copy_bucket(depth+1, idx);
+    }
+  }
+
+  for (i=0; i < BUCKET_COUNT; i++) {
+    if (!list_is_empty(&_buckets[i][depth])) {
+      return i;
+    }
+  }
+
+  return -1;
+}
+
+static void
+_calculate_next_event(void) {
+  struct olsr_timer_entry *timer;
+
+  /* no timer event in queue ? */
+  if (_total_timer_events == 0) {
+    _next_fire_event = ~0ull;
+    return;
+  }
+
+  _bucket_ptr[0] = _look_for_event(0);
+  assert (_bucket_ptr[0] != -1);
+
+  timer = list_first_element(&_buckets[_bucket_ptr[0]][0], timer, _node);
+  _next_fire_event = timer->timer_clock & (~((uint64_t)BUCKET_TIMESLICE - 1));
+}
index ab51c50..036ae0d 100644 (file)
@@ -46,9 +46,6 @@
 #include "common/list.h"
 #include "common/avl.h"
 
-#define TIMER_WHEEL_SLOTS 1024
-#define TIMER_WHEEL_MASK (TIMER_WHEEL_SLOTS - 1)
-
 /* prototype for timer callback */
 typedef void (*timer_cb_func) (void *);
 
@@ -86,7 +83,7 @@ struct olsr_timer_info {
  */
 struct olsr_timer_entry {
   /* Wheel membership */
-  struct list_entity timer_list;
+  struct list_entity _node;
 
   /* backpointer to timer info */
   struct olsr_timer_info *timer_info;
@@ -131,4 +128,6 @@ EXPORT struct olsr_timer_entry *olsr_timer_start(uint64_t, uint8_t,
 EXPORT void olsr_timer_change(struct olsr_timer_entry *, uint64_t, uint8_t);
 EXPORT void olsr_timer_stop(struct olsr_timer_entry *);
 
+EXPORT uint64_t olsr_timer_getNextEvent(void);
+
 #endif /* OLSR_TIMER_H_ */
diff --git a/src/core/os_clock.h b/src/core/os_clock.h
new file mode 100644 (file)
index 0000000..6e4d899
--- /dev/null
@@ -0,0 +1,130 @@
+
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004-2011, the olsr.org team - see HISTORY file
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ *
+ */
+
+#ifndef OS_CLOCK_H_
+#define OS_CLOCK_H_
+
+#include <stdio.h>
+#include <sys/time.h>
+
+#include "common/common_types.h"
+#include "olsr_logging.h"
+#include "olsr_interface.h"
+
+#define MSEC_PER_SEC 1000
+#define USEC_PER_MSEC 1000
+
+/*
+ * Set one of the following defines in the os specific os_net includes
+ * to OS_SPECIFIC to define that the os code is implementing the function
+ * itself and does not use the generic function
+ * Set it to OS_GENERIC to define that the code use the default implementation.
+ *
+ * Example from os_system_linux.h:
+ *
+ * #define OS_SYSTEM_INIT         OS_SPECIFIC
+ * #define OS_SYSTEM_INIT_IF      OS_SPECIFIC
+ * #define OS_SYSTEM_SET_IFSTATE  OS_SPECIFIC
+ * #define OS_SYSTEM_GETTIMEOFDAY OS_GENERIC
+ * #define OS_SYSTEM_LOG          OS_GENERIC
+ */
+
+/* set the guard macro so we can include the os specific settings */
+#define OS_NET_SPECIFIC_INCLUDE
+#include "os_helper.h"
+
+#ifdef OS_LINUX
+#include "os_linux/os_clock_linux.h"
+#endif
+
+#ifdef OS_BSD
+#include "os_bsd/os_clock_bsd.h"
+#endif
+
+#ifdef OS_WIN32
+#include "os_win32/os_clock_win32.h"
+#endif
+
+#undef OS_NET_SPECIFIC_INCLUDE
+
+/* prototypes for all os_system functions */
+EXPORT int os_clock_init(void);
+EXPORT void os_clock_cleanup(void);
+
+EXPORT int os_clock_gettime64(uint64_t *t64);
+
+/*
+ * INLINE implementations for generic os_net functions
+ */
+
+#if OS_CLOCK_INIT == OS_GENERIC
+/**
+ * Dummy init function
+ * @return always returns 0
+ */
+static INLINE int
+os_clock_init(void) {
+  return 0;
+}
+
+/**
+ * Dummy cleanup function
+ */
+static INLINE void
+os_clock_init(void) {
+}
+
+#endif
+
+#if OS_CLOCK_GETTIMEOFDAY == OS_GENERIC
+/**
+ * Inline wrapper around gettimeofday
+ * @param tv pointer to target timeval object
+ * @return -1 if an error happened, 0 otherwise
+ */
+static INLINE int
+os_clock_gettimeofday(struct timeval *tv) {
+  return gettimeofday(tv, NULL);
+}
+#endif
+
+
+#endif /* OS_CLOCK_H_ */
diff --git a/src/core/os_linux/os_clock_linux.c b/src/core/os_linux/os_clock_linux.c
new file mode 100644 (file)
index 0000000..14af31e
--- /dev/null
@@ -0,0 +1,127 @@
+
+/*
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * Copyright (c) 2004-2011, the olsr.org team - see HISTORY file
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Visit http://www.olsr.org for more information.
+ *
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
+ *
+ */
+
+#include <time.h>
+
+#include "common/common_types.h"
+#include "olsr.h"
+#include "os_clock.h"
+
+/* type of clock source to be used */
+#if defined(CLOCK_MONOTONIC_RAW) || defined (CLOCK_MONOTONIC)
+static int _clock_source = 0;
+#endif
+
+OLSR_SUBSYSTEM_STATE(_os_clock_state);
+
+/**
+ * Initialize os-specific subsystem
+ */
+int
+os_clock_init(void) {
+  struct timespec ts;
+
+  if (olsr_subsystem_init(&_os_clock_state)) {
+    return 0;
+  }
+
+#ifdef CLOCK_MONOTONIC_RAW
+  if (clock_gettime(CLOCK_MONOTONIC_RAW, &ts) == 0) {
+    _clock_source = CLOCK_MONOTONIC_RAW;
+  }
+#endif
+#ifdef CLOCK_MONOTONIC
+  if (clock_gettime(CLOCK_MONOTONIC, &ts) == 0) {
+    _clock_source = CLOCK_MONOTONIC;
+  }
+#endif
+  return 0;
+}
+
+/**
+ * Cleanup os-specific subsystem
+ */
+void
+os_clock_cleanup(void) {
+  if (olsr_subsystem_cleanup(&_os_clock_state))
+    return;
+}
+
+/**
+ * Reads the current time as a monotonic timestamp
+ * @param pointer to timestamp
+ * @return 0 if valid timestamp was read, negative otherwise
+ */
+int
+os_clock_gettime64(uint64_t *t64) {
+  static time_t offset = 0, last_sec = 0;
+  struct timeval tv;
+  int error;
+
+#if defined(CLOCK_MONOTONIC_RAW) || defined (CLOCK_MONOTONIC)
+  if (_clock_source) {
+    struct timespec ts;
+
+    if ((error = clock_gettime(_clock_source, &ts)) != 0) {
+      return error;
+    }
+
+    *t64 = 1000ull * ts.tv_sec + ts.tv_nsec / 1000000;
+    return 0;
+  }
+#endif
+  if ((error = gettimeofday(&tv, NULL)) != 0) {
+    return error;
+  }
+
+  tv.tv_sec += offset;
+  if (last_sec == 0) {
+    last_sec = tv.tv_sec;
+  }
+  if (tv.tv_sec < last_sec || tv.tv_sec > last_sec + 60) {
+    offset += last_sec - tv.tv_sec;
+    tv.tv_sec = last_sec;
+  }
+  last_sec = tv.tv_sec;
+
+  *t64 = 1000ull * tv.tv_sec + tv.tv_usec/ 1000;
+  return 0;
+}
diff --git a/src/core/os_linux/os_clock_linux.h b/src/core/os_linux/os_clock_linux.h
new file mode 100644 (file)
index 0000000..2cc966e
--- /dev/null
@@ -0,0 +1,21 @@
+/*
+ * os_system_linux.h
+ *
+ *  Created on: Oct 15, 2011
+ *      Author: henning
+ */
+
+#ifndef OS_CLOCK_LINUX_H_
+#define OS_CLOCK_LINUX_H_
+
+#ifndef OS_NET_SPECIFIC_INCLUDE
+#error "DO not include this file directly, always use 'os_system.h'"
+#endif
+
+#include "os_helper.h"
+
+/* Linux os_system runs on "all default" except for init/cleanup */
+#define OS_CLOCK_GETTIMEOFDAY  OS_GENERIC
+#define OS_CLOCK_INIT          OS_SPECIFIC
+
+#endif /* OS_CLOCK_LINUX_H_ */
index 9bc07ad..f95d422 100644 (file)
@@ -117,11 +117,6 @@ static struct olsr_timer_info _netlink_timer= {
 /* built in rtnetlink multicast receiver */
 static struct os_system_netlink _rtnetlink_receiver;
 
-/* type of clock source to be used */
-#if defined(CLOCK_MONOTONIC_RAW) || defined (CLOCK_MONOTONIC)
-static int _clock_source = 0;
-#endif
-
 OLSR_SUBSYSTEM_STATE(_os_system_state);
 
 /**
@@ -130,8 +125,6 @@ OLSR_SUBSYSTEM_STATE(_os_system_state);
  */
 int
 os_system_init(void) {
-  struct timespec ts;
-
   if (olsr_subsystem_is_initialized(&_os_system_state)) {
     return 0;
   }
@@ -152,17 +145,6 @@ os_system_init(void) {
 
   olsr_timer_add(&_netlink_timer);
 
-#ifdef CLOCK_MONOTONIC_RAW
-  if (clock_gettime(CLOCK_MONOTONIC_RAW, &ts) == 0) {
-    _clock_source = CLOCK_MONOTONIC_RAW;
-  }
-#endif
-#ifdef CLOCK_MONOTONIC
-  if (clock_gettime(CLOCK_MONOTONIC, &ts) == 0) {
-    _clock_source = CLOCK_MONOTONIC;
-  }
-#endif
-
   olsr_subsystem_init(&_os_system_state);
   return 0;
 }
@@ -180,44 +162,6 @@ os_system_cleanup(void) {
   close(_ioctl_fd);
 }
 
-/**
- * Reads the current time as a monotonic timestamp
- * @param pointer to timestamp
- * @return 0 if valid timestamp was read, negative otherwise
- */
-int
-os_system_gettime64(uint64_t *t64) {
-  static time_t offset = 0, last_sec = 0;
-  struct timeval tv;
-  int error;
-
-#if defined(CLOCK_MONOTONIC_RAW) || defined (CLOCK_MONOTONIC)
-  if (_clock_source) {
-    struct timespec ts;
-
-    if ((error = clock_gettime(_clock_source, &ts)) != 0) {
-      return error;
-    }
-
-    *t64 = 1000ull * ts.tv_sec + ts.tv_nsec / 1000000ull;
-    return 0;
-  }
-#endif
-  if ((error = gettimeofday(&tv, NULL)) != 0) {
-    return error;
-  }
-
-  tv.tv_sec += offset;
-  if (tv.tv_sec < last_sec || tv.tv_sec > last_sec + 60) {
-    offset += last_sec - tv.tv_sec;
-    tv.tv_sec = last_sec;
-  }
-  last_sec = tv.tv_sec;
-
-  *t64 = 1000ull * tv.tv_sec + tv.tv_usec/ 1000ull;
-  return 0;
-}
-
 /**
  * Set interface up or down
  * @param dev pointer to name of interface
index ffcccb8..ea88069 100644 (file)
@@ -56,6 +56,7 @@
 #include "config/cfg_schema.h"
 #include "builddata/plugin_static.h"
 #include "builddata/data.h"
+#include "os_clock.h"
 #include "os_net.h"
 #include "os_system.h"
 #include "os_routing.h"
@@ -228,6 +229,9 @@ main(int argc, char **argv) {
   /* initialize basic framework */
   os_system_openlog();
   olsr_memcookie_init();
+  if (os_clock_init()) {
+    goto olsrd_cleanup;
+  }
   if (olsr_clock_init()) {
     goto olsrd_cleanup;
   }
@@ -314,6 +318,8 @@ olsrd_cleanup:
   olsr_packet_cleanup();
   olsr_socket_cleanup();
   olsr_timer_cleanup();
+  olsr_clock_cleanup();
+  os_clock_cleanup();
   olsr_memcookie_cleanup();
   os_system_closelog();
   olsr_logcfg_cleanup();
@@ -350,14 +356,59 @@ hup_signal_handler(int signo __attribute__ ((unused))) {
   olsr_cfg_trigger_reload();
 }
 
+static struct olsr_timer_info _test_timer_info;
+
+static void _cb_test(void *t __attribute__((unused))) {
+  fprintf(stderr, "Fire %" PRIu64 "\n", olsr_clock_getNow());
+
+//  olsr_timer_start((random() % 20000) + 1000, 0, NULL, &_test_timer_info);
+}
+static struct olsr_timer_info _test_timer_info = {
+    .name = "test",
+    .callback = _cb_test,
+    .periodic = false,
+};
+
+static int cmp(const void *a, const void *b) {
+  const uint64_t *a64 = a;
+  const uint64_t *b64 = b;
+
+  if (*a64 < *b64)
+    return -1;
+  if (*a64 > *b64)
+    return 1;
+  return 0;
+}
 /**
  * Mainloop of olsrd
  * @return exit code for olsrd
  */
 static int
 mainloop(int argc, char **argv) {
-  uint32_t next_interval;
+  static uint64_t starts[3];
+  uint64_t next_interval;
   int exit_code = 0;
+  size_t i;
+
+  olsr_timer_add(&_test_timer_info);
+
+  for (i=0; i< ARRAYSIZE(starts); i++) {
+    starts[i] = (uint64_t)(random() % 600000) + 1000ull;
+  }
+
+  starts[0] = 4526;
+  starts[1] = 11012;
+  starts[2] = 39335;
+
+  qsort(starts, ARRAYSIZE(starts), sizeof(uint64_t), cmp);
+
+  for (i=0; i<ARRAYSIZE(starts); i++) {
+    fprintf(stderr, "Random start: %" PRIu64" / %" PRIu64 "\n", starts[i], i==0 ? 0 : starts[i]-starts[i-1]);
+  }
+
+  for (i=0; i< ARRAYSIZE(starts); i++) {
+    olsr_timer_start(starts[i], 0, NULL, &_test_timer_info);
+  }
 
   OLSR_INFO(LOG_MAIN, "Starting %s.", olsr_log_get_builddata()->app_name);
 
@@ -372,13 +423,8 @@ mainloop(int argc, char **argv) {
       break;
     }
 
-    next_interval = olsr_clock_get_absolute(1000);
-
-    /* Process timers */
-    olsr_timer_walk();
-
     /* Read incoming data and handle it immediately */
-    if (olsr_socket_handle(next_interval)) {
+    if (olsr_socket_handle(0)) {
       exit_code = 1;
       break;
     }
@@ -407,7 +453,6 @@ mainloop(int argc, char **argv) {
 
   /* wait for 500 milliseconds and process socket events */
   next_interval = olsr_clock_get_absolute(500);
-  olsr_timer_walk();
   if (olsr_socket_handle(next_interval)) {
     exit_code = 1;
   }