timers.c 8.1 KB

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