1 /* Copyright (c) 2016-2021, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
6 * \brief Wrapper around William Ahern's fast hierarchical timer wheel
7 * implementation, to tie it in with a libevent backend.
9 * Only use these functions from the main thread.
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
16 * Periodic timers are available in the backend, but I've turned them off.
17 * We can turn them back on if needed.
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.
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.
32 #define TOR_TIMERS_PRIVATE
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"
42 #ifdef HAVE_SYS_TIME_H
47 // For struct timeval.
57 * These definitions are for timeouts.c and timeouts.h.
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
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 */
80 #if SIZEOF_VOID_P == 4
81 /* On 32-bit platforms, we want to override wheel_bit, so that timeout.c will
86 #include "ext/timeouts/timeout.c"
88 static struct timeouts
*global_timeouts
= NULL
;
89 static struct mainloop_event_t
*global_timer_event
= NULL
;
91 static monotime_t start_of_time
;
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.
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.
101 #define USEC_PER_TICK 100
103 /** One million microseconds in a second */
104 #define USEC_PER_SEC 1000000
106 /** Check at least once every N seconds. */
107 #define MIN_CHECK_SECONDS 3600
109 /** Check at least once every N ticks. */
110 #define MIN_CHECK_TICKS \
111 (((timeout_t)MIN_CHECK_SECONDS) * (1000000 / USEC_PER_TICK))
114 * Convert the timeval in <b>tv</b> to a timeout_t, and return it.
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.
120 tv_to_timeout(const struct timeval
*tv
)
122 uint64_t usec
= tv
->tv_usec
;
123 usec
+= ((uint64_t)USEC_PER_SEC
) * tv
->tv_sec
;
124 return usec
/ USEC_PER_TICK
;
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.
132 timeout_to_tv(timeout_t t
, struct timeval
*tv_out
)
135 tv_out
->tv_usec
= (int)(t
% USEC_PER_SEC
);
136 tv_out
->tv_sec
= (time_t)(t
/ USEC_PER_SEC
);
140 * Update the timer <b>tv</b> to the current time in <b>tv</b>.
143 timer_advance_to_cur_time(const monotime_t
*now
)
145 timeout_t cur_tick
= CEIL_DIV(monotime_diff_usec(&start_of_time
, now
),
147 timeouts_update(global_timeouts
, cur_tick
);
151 * Adjust the time at which the libevent timer should fire based on
152 * the next-expiring time in <b>global_timeouts</b>
155 libevent_timer_reschedule(void)
159 timer_advance_to_cur_time(&now
);
161 timeout_t delay
= timeouts_timeout(global_timeouts
);
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
);
170 /** Run the callback of every timer that has expired, based on the current
171 * output of monotime_get(). */
173 timers_run_pending(void)
177 timer_advance_to_cur_time(&now
);
180 while ((t
= timeouts_get(global_timeouts
))) {
181 t
->callback
.cb(t
, t
->callback
.arg
, &now
);
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.
190 libevent_timer_callback(mainloop_event_t
*ev
, void *arg
)
195 timers_run_pending();
197 libevent_timer_reschedule();
201 * Initialize the timers subsystem. Requires that libevent has already been
205 timers_initialize(void)
207 if (BUG(global_timeouts
))
208 return; // LCOV_EXCL_LINE
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
));
220 monotime_get(&start_of_time
);
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
;
227 libevent_timer_reschedule();
231 * Release all storage held in the timers subsystem. Does not fire timers.
234 timers_shutdown(void)
236 if (global_timer_event
) {
237 mainloop_event_free(global_timer_event
);
238 global_timer_event
= NULL
;
240 if (global_timeouts
) {
241 timeouts_close(global_timeouts
);
242 global_timeouts
= NULL
;
247 * Allocate and return a new timer, with given callback and argument.
250 timer_new(timer_cb_fn_t cb
, void *arg
)
252 tor_timer_t
*t
= tor_malloc(sizeof(tor_timer_t
));
254 timer_set_cb(t
, cb
, arg
);
259 * Release all storage held by <b>t</b>, and unschedule it if was already
263 timer_free_(tor_timer_t
*t
)
268 timeouts_del(global_timeouts
, t
);
273 * Change the callback and argument associated with a timer <b>t</b>.
276 timer_set_cb(tor_timer_t
*t
, timer_cb_fn_t cb
, void *arg
)
279 t
->callback
.arg
= arg
;
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.
287 timer_get_cb(const tor_timer_t
*t
,
288 timer_cb_fn_t
*cb_out
, void **arg_out
)
291 *cb_out
= t
->callback
.cb
;
293 *arg_out
= t
->callback
.arg
;
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().
301 timer_schedule(tor_timer_t
*t
, const struct timeval
*tv
)
303 const timeout_t delay
= tv_to_timeout(tv
);
307 timer_advance_to_cur_time(&now
);
309 /* Take the old timeout value. */
310 timeout_t to
= timeouts_timeout(global_timeouts
);
312 timeouts_add(global_timeouts
, t
, delay
);
314 /* Should we update the libevent timer? */
316 return; /* we're already going to fire before this timer would trigger. */
318 libevent_timer_reschedule();
322 * Cancel the timer <b>t</b> if it is currently scheduled. (It's okay to call
323 * this on an unscheduled timer.
326 timer_disable(tor_timer_t
*t
)
328 timeouts_del(global_timeouts
, t
);
329 /* We don't reschedule the libevent timer here, since it's okay if it fires