src/lib/evloop/timers.c

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