src/common/timers.c

   1 /* Copyright (c) 2016, The Tor Project, Inc. */
   2 /* See LICENSE for licensing information */
   3
   4 /**
   5  * \file timers.c
   6  * \brief Wrapper around William Ahern's fast hierarchical timer wheel
   7  *   implementation, to tie it in with a libevent backend.
   8  *
   9  * Only use these functions from the main thread.
  10  *
  11  * The main advantage of tor_timer_t over using libevent's timers is that
  12  * they're way more efficient if we need to have thousands or millions of
  13  * them.  For more information, see
  14  *   http://www.25thandclement.com/~william/projects/timeout.c.html
  15  *
  16  * Periodic timers are available in the backend, but I've turned them off.
  17  * We can turn them back on if needed.
  18  */
  19
  20 /* Notes:
  21  *
  22  * The use of tor_gettimeofday_cached_monotonic() is kind of ugly.  It would
  23  * be neat to fix it.
  24  *
  25  * Having a way to free all timers on shutdown would free people from the
  26  * need to track them.  Not sure if that's clever though.
  27  *
  28  * In an ideal world, Libevent would just switch to use this backend, and we
  29  * could throw this file away.  But even if Libevent does switch, we'll be
  30  * stuck with legacy libevents for some time.
  31  */
  32
  33 #include "orconfig.h"
  34
  35 #include "compat.h"
  36 #include "compat_libevent.h"
  37 #include "timers.h"
  38 #include "torlog.h"
  39 #include "util.h"
  40
  41 #ifdef HAVE_EVENT2_EVENT_H
  42 #include <event2/event.h>
  43 #else
  44 #include <event.h>
  45 #endif
  46
  47 struct timeout_cb {
  48   timer_cb_fn_t cb;
  49   void *arg;
  50 };
  51
  52 /*
  53  * These definitions are for timeouts.c  and timeouts.h.
  54  */
  55 #ifdef __GNUC__
  56 /* We're not exposing any of the functions outside this file. */
  57 #define TIMEOUT_PUBLIC __attribute__((__unused__)) static
  58 #else
  59 /* We're not exposing any of the functions outside this file. */
  60 #define TIMEOUT_PUBLIC static
  61 #endif
  62 /* We're not using periodic events. */
  63 #define TIMEOUT_DISABLE_INTERVALS
  64 /* We always know the global_timeouts object, so we don't need each timeout
  65  * to keep a pointer to it. */
  66 #define TIMEOUT_DISABLE_RELATIVE_ACCESS
  67 /* We're providing our own struct timeout_cb. */
  68 #define TIMEOUT_CB_OVERRIDE
  69 /* We're going to support timers that are pretty far out in advance. Making
  70  * this big can be inefficient, but having a significant number of timers
  71  * above TIMEOUT_MAX can also be super-inefficent. Choosing 5 here sets
  72  * timeout_max to 2^30 ticks, or 29 hours with our value for USEC_PER_TICK */
  73 #define WHEEL_NUM 5
  74 #include "src/ext/timeouts/timeout.c"
  75
  76 static struct timeouts *global_timeouts = NULL;
  77 static struct event *global_timer_event = NULL;
  78
  79 /** We need to choose this value carefully.  Because we're using timer wheels,
  80  * it actually costs us to have extra resolution we don't use.  So for now,
  81  * I'm going to define our resolution as .1 msec, and hope that's good enough.
  82  *
  83  * Note that two of the most popular libevent backends (epoll without timerfd,
  84  * and windows select), simply can't support sub-millisecond resolution,
  85  * do this is optimistic for a lot of users.
  86  */
  87 #define USEC_PER_TICK 100
  88
  89 /** One million microseconds in a second */
  90 #define USEC_PER_SEC 1000000
  91
  92 /** Check at least once every N seconds. */
  93 #define MIN_CHECK_SECONDS 3600
  94
  95 /** Check at least once every N ticks. */
  96 #define MIN_CHECK_TICKS \
  97   (((timeout_t)MIN_CHECK_SECONDS) * (1000000 / USEC_PER_TICK))
  98
  99 /**
 100  * Convert the timeval in <b>tv</b> to a timeout_t, and return it.
 101  *
 102  * The output resolution is set by USEC_PER_TICK, and the time corresponding
 103  * to 0 is the same as the time corresponding to 0 from
 104  * tor_gettimeofday_cached_monotonic().
 105  */
 106 static timeout_t
 107 tv_to_timeout(const struct timeval *tv)
 108 {
 109   uint64_t usec = tv->tv_usec;
 110   usec += ((uint64_t)USEC_PER_SEC) * tv->tv_sec;
 111   return usec / USEC_PER_TICK;
 112 }
 113
 114 /**
 115  * Convert the timeout in <b>t</b> to a timeval in <b>tv_out</b>
 116  */
 117 static void
 118 timeout_to_tv(timeout_t t, struct timeval *tv_out)
 119 {
 120   t *= USEC_PER_TICK;
 121   tv_out->tv_usec = (int)(t % USEC_PER_SEC);
 122   tv_out->tv_sec = (time_t)(t / USEC_PER_SEC);
 123 }
 124
 125 /**
 126  * Update the timer <b>tv</b> to the current time in <b>tv</b>.
 127  */
 128 static void
 129 timer_advance_to_cur_time(const struct timeval *tv)
 130 {
 131   timeout_t cur_tick = tv_to_timeout(tv);
 132   if (BUG(cur_tick < timeouts_get_curtime(global_timeouts))) {
 133     cur_tick = timeouts_get_curtime(global_timeouts); // LCOV_EXCL_LINE
 134   }
 135   timeouts_update(global_timeouts, cur_tick);
 136 }
 137
 138 /**
 139  * Adjust the time at which the libevent timer should fire based on
 140  * the next-expiring time in <b>global_timeouts</b>
 141  */
 142 static void
 143 libevent_timer_reschedule(void)
 144 {
 145   struct timeval now;
 146   tor_gettimeofday_cached_monotonic(&now);
 147   timer_advance_to_cur_time(&now);
 148
 149   timeout_t delay = timeouts_timeout(global_timeouts);
 150   struct timeval d;
 151   if (delay > MIN_CHECK_TICKS)
 152     delay = MIN_CHECK_TICKS;
 153   timeout_to_tv(delay, &d);
 154   event_add(global_timer_event, &d);
 155 }
 156
 157 /**
 158  * Invoked when the libevent timer has expired: see which tor_timer_t events
 159  * have fired, activate their callbacks, and reschedule the libevent timer.
 160  */
 161 static void
 162 libevent_timer_callback(evutil_socket_t fd, short what, void *arg)
 163 {
 164   (void)fd;
 165   (void)what;
 166   (void)arg;
 167
 168   struct timeval now;
 169   tor_gettimeofday_cache_clear();
 170   tor_gettimeofday_cached_monotonic(&now);
 171   timer_advance_to_cur_time(&now);
 172
 173   tor_timer_t *t;
 174   while ((t = timeouts_get(global_timeouts))) {
 175     t->callback.cb(t, t->callback.arg, &now);
 176   }
 177
 178   tor_gettimeofday_cache_clear();
 179   libevent_timer_reschedule();
 180 }
 181
 182 /**
 183  * Initialize the timers subsystem.  Requires that libevent has already been
 184  * initialized.
 185  */
 186 void
 187 timers_initialize(void)
 188 {
 189   if (BUG(global_timeouts))
 190     return; // LCOV_EXCL_LINE
 191
 192   timeout_error_t err;
 193   global_timeouts = timeouts_open(0, &err);
 194   if (!global_timeouts) {
 195     // LCOV_EXCL_START -- this can only fail on malloc failure.
 196     log_err(LD_BUG, "Unable to open timer backend: %s", strerror(err));
 197     tor_assert(0);
 198     // LCOV_EXCL_STOP
 199   }
 200
 201   struct event *timer_event;
 202   timer_event = tor_event_new(tor_libevent_get_base(),
 203                               -1, 0, libevent_timer_callback, NULL);
 204   tor_assert(timer_event);
 205   global_timer_event = timer_event;
 206
 207   libevent_timer_reschedule();
 208 }
 209
 210 /**
 211  * Release all storage held in the timers subsystem.  Does not fire timers.
 212  */
 213 void
 214 timers_shutdown(void)
 215 {
 216   if (global_timer_event) {
 217     tor_event_free(global_timer_event);
 218     global_timer_event = NULL;
 219   }
 220   if (global_timeouts) {
 221     timeouts_close(global_timeouts);
 222     global_timeouts = NULL;
 223   }
 224 }
 225
 226 /**
 227  * Allocate and return a new timer, with given callback and argument.
 228  */
 229 tor_timer_t *
 230 timer_new(timer_cb_fn_t cb, void *arg)
 231 {
 232   tor_timer_t *t = tor_malloc(sizeof(tor_timer_t));
 233   timeout_init(t, 0);
 234   timer_set_cb(t, cb, arg);
 235   return t;
 236 }
 237
 238 /**
 239  * Release all storage held by <b>t</b>, and unschedule it if was already
 240  * scheduled.
 241  */
 242 void
 243 timer_free(tor_timer_t *t)
 244 {
 245   if (! t)
 246     return;
 247
 248   timeouts_del(global_timeouts, t);
 249   tor_free(t);
 250 }
 251
 252 /**
 253  * Change the callback and argument associated with a timer <b>t</b>.
 254  */
 255 void
 256 timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg)
 257 {
 258   t->callback.cb = cb;
 259   t->callback.arg = arg;
 260 }
 261
 262 /**
 263  * Schedule the timer t to fire at the current time plus a delay of <b>tv</b>.
 264  * All times are relative to tor_gettimeofday_cached_monotonic.
 265  */
 266 void
 267 timer_schedule(tor_timer_t *t, const struct timeval *tv)
 268 {
 269   const timeout_t when = tv_to_timeout(tv);
 270   struct timeval now;
 271   tor_gettimeofday_cached_monotonic(&now);
 272   timer_advance_to_cur_time(&now);
 273
 274   /* Take the old timeout value. */
 275   timeout_t to = timeouts_timeout(global_timeouts);
 276
 277   timeouts_add(global_timeouts, t, when);
 278
 279   /* Should we update the libevent timer? */
 280   if (to <= when) {
 281     return; /* we're already going to fire before this timer would trigger. */
 282   }
 283   libevent_timer_reschedule();
 284 }
 285
 286 /**
 287  * Cancel the timer <b>t</b> if it is currently scheduled.  (It's okay to call
 288  * this on an unscheduled timer.
 289  */
 290 void
 291 timer_disable(tor_timer_t *t)
 292 {
 293   timeouts_del(global_timeouts, t);
 294   /* We don't reschedule the libevent timer here, since it's okay if it fires
 295    * early. */
 296 }
 297