Line data Source code
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 1234 : tv_to_timeout(const struct timeval *tv)
121 : {
122 1234 : uint64_t usec = tv->tv_usec;
123 1234 : usec += ((uint64_t)USEC_PER_SEC) * tv->tv_sec;
124 1234 : 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 1819 : timeout_to_tv(timeout_t t, struct timeval *tv_out)
133 : {
134 1819 : t *= USEC_PER_TICK;
135 1819 : tv_out->tv_usec = (int)(t % USEC_PER_SEC);
136 1819 : tv_out->tv_sec = (time_t)(t / USEC_PER_SEC);
137 1819 : }
138 :
139 : /**
140 : * Update the timer <b>tv</b> to the current time in <b>tv</b>.
141 : */
142 : static void
143 4997 : timer_advance_to_cur_time(const monotime_t *now)
144 : {
145 4997 : timeout_t cur_tick = CEIL_DIV(monotime_diff_usec(&start_of_time, now),
146 : USEC_PER_TICK);
147 4997 : timeouts_update(global_timeouts, cur_tick);
148 4997 : }
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 1819 : libevent_timer_reschedule(void)
156 : {
157 1819 : monotime_t now;
158 1819 : monotime_get(&now);
159 1819 : timer_advance_to_cur_time(&now);
160 :
161 1819 : timeout_t delay = timeouts_timeout(global_timeouts);
162 :
163 1819 : struct timeval d;
164 1819 : if (delay > MIN_CHECK_TICKS)
165 : delay = MIN_CHECK_TICKS;
166 1819 : timeout_to_tv(delay, &d);
167 1819 : mainloop_event_schedule(global_timer_event, &d);
168 1819 : }
169 :
170 : /** Run the callback of every timer that has expired, based on the current
171 : * output of monotime_get(). */
172 : STATIC void
173 1944 : timers_run_pending(void)
174 : {
175 1944 : monotime_t now;
176 1944 : monotime_get(&now);
177 1944 : timer_advance_to_cur_time(&now);
178 :
179 1944 : tor_timer_t *t;
180 3149 : while ((t = timeouts_get(global_timeouts))) {
181 1205 : t->callback.cb(t, t->callback.arg, &now);
182 : }
183 1944 : }
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 1764 : libevent_timer_callback(mainloop_event_t *ev, void *arg)
191 : {
192 1764 : (void)ev;
193 1764 : (void)arg;
194 :
195 1764 : timers_run_pending();
196 :
197 1764 : libevent_timer_reschedule();
198 1764 : }
199 :
200 : /**
201 : * Initialize the timers subsystem. Requires that libevent has already been
202 : * initialized.
203 : */
204 : void
205 15 : timers_initialize(void)
206 : {
207 15 : if (BUG(global_timeouts))
208 : return; // LCOV_EXCL_LINE
209 :
210 15 : timeout_error_t err = 0;
211 15 : global_timeouts = timeouts_open(0, &err);
212 15 : 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 15 : monotime_init();
220 15 : monotime_get(&start_of_time);
221 :
222 15 : mainloop_event_t *timer_event;
223 15 : timer_event = mainloop_event_new(libevent_timer_callback, NULL);
224 15 : tor_assert(timer_event);
225 15 : global_timer_event = timer_event;
226 :
227 15 : libevent_timer_reschedule();
228 : }
229 :
230 : /**
231 : * Release all storage held in the timers subsystem. Does not fire timers.
232 : */
233 : void
234 203 : timers_shutdown(void)
235 : {
236 203 : if (global_timer_event) {
237 9 : mainloop_event_free(global_timer_event);
238 9 : global_timer_event = NULL;
239 : }
240 203 : if (global_timeouts) {
241 9 : timeouts_close(global_timeouts);
242 9 : global_timeouts = NULL;
243 : }
244 203 : }
245 :
246 : /**
247 : * Allocate and return a new timer, with given callback and argument.
248 : */
249 : tor_timer_t *
250 1107 : timer_new(timer_cb_fn_t cb, void *arg)
251 : {
252 1107 : tor_timer_t *t = tor_malloc(sizeof(tor_timer_t));
253 1107 : timeout_init(t, 0);
254 1107 : timer_set_cb(t, cb, arg);
255 1107 : 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 1171 : timer_free_(tor_timer_t *t)
264 : {
265 1171 : if (! t)
266 : return;
267 :
268 1107 : timeouts_del(global_timeouts, t);
269 1107 : tor_free(t);
270 : }
271 :
272 : /**
273 : * Change the callback and argument associated with a timer <b>t</b>.
274 : */
275 : void
276 1234 : timer_set_cb(tor_timer_t *t, timer_cb_fn_t cb, void *arg)
277 : {
278 1234 : t->callback.cb = cb;
279 1234 : t->callback.arg = arg;
280 1234 : }
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 0 : timer_get_cb(const tor_timer_t *t,
288 : timer_cb_fn_t *cb_out, void **arg_out)
289 : {
290 0 : if (cb_out)
291 0 : *cb_out = t->callback.cb;
292 0 : if (arg_out)
293 0 : *arg_out = t->callback.arg;
294 0 : }
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 1234 : timer_schedule(tor_timer_t *t, const struct timeval *tv)
302 : {
303 1234 : const timeout_t delay = tv_to_timeout(tv);
304 :
305 1234 : monotime_t now;
306 1234 : monotime_get(&now);
307 1234 : timer_advance_to_cur_time(&now);
308 :
309 : /* Take the old timeout value. */
310 1234 : timeout_t to = timeouts_timeout(global_timeouts);
311 :
312 1234 : timeouts_add(global_timeouts, t, delay);
313 :
314 : /* Should we update the libevent timer? */
315 1234 : if (to <= delay) {
316 1194 : return; /* we're already going to fire before this timer would trigger. */
317 : }
318 40 : 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 9 : timer_disable(tor_timer_t *t)
327 : {
328 9 : timeouts_del(global_timeouts, t);
329 : /* We don't reschedule the libevent timer here, since it's okay if it fires
330 : * early. */
331 9 : }
|
