timers.c 8.4 KB

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