src/common/timers.c

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