timers.c (8666B)
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 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 143 timer_advance_to_cur_time(const monotime_t *now) 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 155 libevent_timer_reschedule(void) 156 { 157 monotime_t now; 158 monotime_get(&now); 159 timer_advance_to_cur_time(&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 173 timers_run_pending(void) 174 { 175 monotime_t now; 176 monotime_get(&now); 177 timer_advance_to_cur_time(&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 190 libevent_timer_callback(mainloop_event_t *ev, void *arg) 191 { 192 (void)ev; 193 (void)arg; 194 195 timers_run_pending(); 196 197 libevent_timer_reschedule(); 198 } 199 200 /** 201 * Initialize the timers subsystem. Requires that libevent has already been 202 * initialized. 203 */ 204 void 205 timers_initialize(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 227 libevent_timer_reschedule(); 228 } 229 230 /** 231 * Release all storage held in the timers subsystem. Does not fire timers. 232 */ 233 void 234 timers_shutdown(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); 307 timer_advance_to_cur_time(&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 } 318 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 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 }