Tor  0.4.7.0-alpha-dev
timers.c
Go to the documentation of this file.
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 
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
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
156 {
157  monotime_t now;
158  monotime_get(&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
174 {
175  monotime_t now;
176  monotime_get(&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
191 {
192  (void)ev;
193  (void)arg;
194 
196 
198 }
199 
200 /**
201  * Initialize the timers subsystem. Requires that libevent has already been
202  * initialized.
203  */
204 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 
228 }
229 
230 /**
231  * Release all storage held in the timers subsystem. Does not fire timers.
232  */
233 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);
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  }
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 }
mainloop_event_t * mainloop_event_new(void(*cb)(mainloop_event_t *, void *), void *userdata)
int mainloop_event_schedule(mainloop_event_t *event, const struct timeval *tv)
Header for compat_libevent.c.
void monotime_init(void)
Definition: compat_time.c:747
int64_t monotime_diff_usec(const monotime_t *start, const monotime_t *end)
Definition: compat_time.c:773
Functions and types for monotonic times.
void monotime_get(monotime_t *out)
Headers for log.c.
#define LD_BUG
Definition: log.h:86
Headers for util_malloc.c.
#define tor_free(p)
Definition: malloc.h:52
Header for muldiv.c.
#define STATIC
Definition: testsupport.h:32
static void libevent_timer_callback(mainloop_event_t *ev, void *arg)
Definition: timers.c:190
static void libevent_timer_reschedule(void)
Definition: timers.c:155
static void timer_advance_to_cur_time(const monotime_t *now)
Definition: timers.c:143
void timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg)
Definition: timers.c:276
void timer_schedule(tor_timer_t *t, const struct timeval *tv)
Definition: timers.c:301
void timer_get_cb(const tor_timer_t *t, timer_cb_fn_t *cb_out, void **arg_out)
Definition: timers.c:287
#define USEC_PER_TICK
Definition: timers.c:101
static timeout_t tv_to_timeout(const struct timeval *tv)
Definition: timers.c:120
void timers_shutdown(void)
Definition: timers.c:234
#define USEC_PER_SEC
Definition: timers.c:104
void timers_initialize(void)
Definition: timers.c:205
#define MIN_CHECK_TICKS
Definition: timers.c:110
tor_timer_t * timer_new(timer_cb_fn_t cb, void *arg)
Definition: timers.c:250
void timer_disable(tor_timer_t *t)
Definition: timers.c:326
static void timeout_to_tv(timeout_t t, struct timeval *tv_out)
Definition: timers.c:132
STATIC void timers_run_pending(void)
Definition: timers.c:173
void timer_free_(tor_timer_t *t)
Definition: timers.c:263
Header for timers.c.
Macros to manage assertions, fatal and non-fatal.
#define tor_assert(expr)
Definition: util_bug.h:102