timers.c 7.5 KB

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