Line data Source code
1 : /* ==========================================================================
2 : * timeout.c - Tickless hierarchical timing wheel.
3 : * --------------------------------------------------------------------------
4 : * Copyright (c) 2013, 2014 William Ahern
5 : *
6 : * Permission is hereby granted, free of charge, to any person obtaining a
7 : * copy of this software and associated documentation files (the
8 : * "Software"), to deal in the Software without restriction, including
9 : * without limitation the rights to use, copy, modify, merge, publish,
10 : * distribute, sublicense, and/or sell copies of the Software, and to permit
11 : * persons to whom the Software is furnished to do so, subject to the
12 : * following conditions:
13 : *
14 : * The above copyright notice and this permission notice shall be included
15 : * in all copies or substantial portions of the Software.
16 : *
17 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
18 : * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
19 : * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
20 : * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
21 : * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
22 : * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
23 : * USE OR OTHER DEALINGS IN THE SOFTWARE.
24 : * ==========================================================================
25 : */
26 : #ifdef HAVE_CONFIG_H
27 : #include "orconfig.h"
28 : #endif
29 : #include <limits.h> /* CHAR_BIT */
30 :
31 : #include <stddef.h> /* NULL */
32 : #include <stdlib.h> /* malloc(3) free(3) */
33 : #include <stdio.h> /* FILE fprintf(3) */
34 :
35 : #include <inttypes.h> /* UINT64_C uint64_t */
36 :
37 : #include <string.h> /* memset(3) */
38 :
39 : #include <errno.h> /* errno */
40 :
41 : #include "ext/tor_queue.h" /* TAILQ(3) */
42 :
43 : #include "ext/timeouts/timeout.h"
44 :
45 : #ifndef TIMEOUT_DEBUG
46 : #define TIMEOUT_DEBUG 0
47 : #endif
48 :
49 : #if TIMEOUT_DEBUG - 0
50 : #include "ext/timeouts/timeout-debug.h"
51 : #endif
52 :
53 : #ifdef TIMEOUT_DISABLE_RELATIVE_ACCESS
54 : #define TO_SET_TIMEOUTS(to, T) ((void)0)
55 : #else
56 : #define TO_SET_TIMEOUTS(to, T) ((to)->timeouts = (T))
57 : #endif
58 :
59 : /*
60 : * A N C I L L A R Y R O U T I N E S
61 : *
62 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
63 :
64 : #define abstime_t timeout_t /* for documentation purposes */
65 : #define reltime_t timeout_t /* "" */
66 :
67 : #if !defined countof
68 : #define countof(a) (sizeof (a) / sizeof *(a))
69 : #endif
70 :
71 : #if !defined endof
72 : #define endof(a) (&(a)[countof(a)])
73 : #endif
74 :
75 : #if !defined MIN
76 : #define MIN(a, b) (((a) < (b))? (a) : (b))
77 : #endif
78 :
79 : #if !defined MAX
80 : #define MAX(a, b) (((a) > (b))? (a) : (b))
81 : #endif
82 :
83 : #if !defined TOR_TAILQ_CONCAT
84 : #define TOR_TAILQ_CONCAT(head1, head2, field) do { \
85 : if (!TOR_TAILQ_EMPTY(head2)) { \
86 : *(head1)->tqh_last = (head2)->tqh_first; \
87 : (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
88 : (head1)->tqh_last = (head2)->tqh_last; \
89 : TOR_TAILQ_INIT((head2)); \
90 : } \
91 : } while (0)
92 : #endif
93 :
94 : #if !defined TOR_TAILQ_FOREACH_SAFE
95 : #define TOR_TAILQ_FOREACH_SAFE(var, head, field, tvar) \
96 : for ((var) = TOR_TAILQ_FIRST(head); \
97 : (var) && ((tvar) = TOR_TAILQ_NEXT(var, field), 1); \
98 : (var) = (tvar))
99 : #endif
100 :
101 :
102 : /*
103 : * B I T M A N I P U L A T I O N R O U T I N E S
104 : *
105 : * The macros and routines below implement wheel parameterization. The
106 : * inputs are:
107 : *
108 : * WHEEL_BIT - The number of value bits mapped in each wheel. The
109 : * lowest-order WHEEL_BIT bits index the lowest-order (highest
110 : * resolution) wheel, the next group of WHEEL_BIT bits the
111 : * higher wheel, etc.
112 : *
113 : * WHEEL_NUM - The number of wheels. WHEEL_BIT * WHEEL_NUM = the number of
114 : * value bits used by all the wheels. For the default of 6 and
115 : * 4, only the low 24 bits are processed. Any timeout value
116 : * larger than this will cycle through again.
117 : *
118 : * The implementation uses bit fields to remember which slot in each wheel
119 : * is populated, and to generate masks of expiring slots according to the
120 : * current update interval (i.e. the "tickless" aspect). The slots to
121 : * process in a wheel are (populated-set & interval-mask).
122 : *
123 : * WHEEL_BIT cannot be larger than 6 bits because 2^6 -> 64 is the largest
124 : * number of slots which can be tracked in a uint64_t integer bit field.
125 : * WHEEL_BIT cannot be smaller than 3 bits because of our rotr and rotl
126 : * routines, which only operate on all the value bits in an integer, and
127 : * there's no integer smaller than uint8_t.
128 : *
129 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
130 :
131 : #if !defined WHEEL_BIT
132 : #define WHEEL_BIT 6
133 : #endif
134 :
135 : #if !defined WHEEL_NUM
136 : #define WHEEL_NUM 4
137 : #endif
138 :
139 : #define WHEEL_LEN (1U << WHEEL_BIT)
140 : #define WHEEL_MAX (WHEEL_LEN - 1)
141 : #define WHEEL_MASK (WHEEL_LEN - 1)
142 : #define TIMEOUT_MAX ((TIMEOUT_C(1) << (WHEEL_BIT * WHEEL_NUM)) - 1)
143 :
144 : #include "ext/timeouts/timeout-bitops.c"
145 :
146 : #if WHEEL_BIT == 6
147 : #define ctz(n) ctz64(n)
148 : #define clz(n) clz64(n)
149 : #define fls(n) ((int)(64 - clz64(n)))
150 : #else
151 : #define ctz(n) ctz32(n)
152 : #define clz(n) clz32(n)
153 : #define fls(n) ((int)(32 - clz32((uint32_t)n)))
154 : #endif
155 :
156 : #if WHEEL_BIT == 6
157 : #define WHEEL_C(n) UINT64_C(n)
158 : #define WHEEL_PRIu PRIu64
159 : #define WHEEL_PRIx PRIx64
160 :
161 : typedef uint64_t wheel_t;
162 :
163 : #elif WHEEL_BIT == 5
164 :
165 : #define WHEEL_C(n) UINT32_C(n)
166 : #define WHEEL_PRIu PRIu32
167 : #define WHEEL_PRIx PRIx32
168 :
169 : typedef uint32_t wheel_t;
170 :
171 : #elif WHEEL_BIT == 4
172 :
173 : #define WHEEL_C(n) UINT16_C(n)
174 : #define WHEEL_PRIu PRIu16
175 : #define WHEEL_PRIx PRIx16
176 :
177 : typedef uint16_t wheel_t;
178 :
179 : #elif WHEEL_BIT == 3
180 :
181 : #define WHEEL_C(n) UINT8_C(n)
182 : #define WHEEL_PRIu PRIu8
183 : #define WHEEL_PRIx PRIx8
184 :
185 : typedef uint8_t wheel_t;
186 :
187 : #else
188 : #error invalid WHEEL_BIT value
189 : #endif
190 :
191 :
192 12306 : static inline wheel_t rotl(const wheel_t v, int c) {
193 12306 : if (!(c &= (sizeof v * CHAR_BIT - 1)))
194 : return v;
195 :
196 10423 : return (v << c) | (v >> (sizeof v * CHAR_BIT - c));
197 : } /* rotl() */
198 :
199 :
200 15375 : static inline wheel_t rotr(const wheel_t v, int c) {
201 15375 : if (!(c &= (sizeof v * CHAR_BIT - 1)))
202 : return v;
203 :
204 7568 : return (v >> c) | (v << (sizeof v * CHAR_BIT - c));
205 : } /* rotr() */
206 :
207 :
208 : /*
209 : * T I M E R R O U T I N E S
210 : *
211 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
212 :
213 : TOR_TAILQ_HEAD(timeout_list, timeout);
214 :
215 : struct timeouts {
216 : struct timeout_list wheel[WHEEL_NUM][WHEEL_LEN], expired;
217 :
218 : wheel_t pending[WHEEL_NUM];
219 :
220 : timeout_t curtime;
221 : timeout_t hertz;
222 : }; /* struct timeouts */
223 :
224 :
225 15 : static struct timeouts *timeouts_init(struct timeouts *T, timeout_t hz) {
226 15 : unsigned i, j;
227 :
228 90 : for (i = 0; i < countof(T->wheel); i++) {
229 4875 : for (j = 0; j < countof(T->wheel[i]); j++) {
230 4800 : TOR_TAILQ_INIT(&T->wheel[i][j]);
231 : }
232 : }
233 :
234 15 : TOR_TAILQ_INIT(&T->expired);
235 :
236 90 : for (i = 0; i < countof(T->pending); i++) {
237 75 : T->pending[i] = 0;
238 : }
239 :
240 15 : T->curtime = 0;
241 15 : T->hertz = (hz)? hz : TIMEOUT_mHZ;
242 :
243 15 : return T;
244 : } /* timeouts_init() */
245 :
246 :
247 15 : TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t hz, int *error) {
248 15 : struct timeouts *T;
249 :
250 15 : if ((T = malloc(sizeof *T)))
251 15 : return timeouts_init(T, hz);
252 :
253 0 : *error = errno;
254 :
255 0 : return NULL;
256 : } /* timeouts_open() */
257 :
258 :
259 9 : static void timeouts_reset(struct timeouts *T) {
260 9 : struct timeout_list reset;
261 9 : struct timeout *to;
262 9 : unsigned i, j;
263 :
264 9 : TOR_TAILQ_INIT(&reset);
265 :
266 54 : for (i = 0; i < countof(T->wheel); i++) {
267 2925 : for (j = 0; j < countof(T->wheel[i]); j++) {
268 2880 : TOR_TAILQ_CONCAT(&reset, &T->wheel[i][j], tqe);
269 : }
270 : }
271 :
272 9 : TOR_TAILQ_CONCAT(&reset, &T->expired, tqe);
273 :
274 9 : TOR_TAILQ_FOREACH(to, &reset, tqe) {
275 0 : to->pending = NULL;
276 0 : TO_SET_TIMEOUTS(to, NULL);
277 : }
278 9 : } /* timeouts_reset() */
279 :
280 :
281 9 : TIMEOUT_PUBLIC void timeouts_close(struct timeouts *T) {
282 : /*
283 : * NOTE: Delete installed timeouts so timeout_pending() and
284 : * timeout_expired() worked as expected.
285 : */
286 9 : timeouts_reset(T);
287 :
288 9 : free(T);
289 9 : } /* timeouts_close() */
290 :
291 :
292 : TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *T) {
293 : return T->hertz;
294 : } /* timeouts_hz() */
295 :
296 :
297 9324 : TIMEOUT_PUBLIC void timeouts_del(struct timeouts *T, struct timeout *to) {
298 9324 : if (to->pending) {
299 29 : TOR_TAILQ_REMOVE(to->pending, to, tqe);
300 :
301 29 : if (to->pending != &T->expired && TOR_TAILQ_EMPTY(to->pending)) {
302 24 : ptrdiff_t index_ = to->pending - &T->wheel[0][0];
303 24 : int wheel = (int) (index_ / WHEEL_LEN);
304 24 : int slot = index_ % WHEEL_LEN;
305 :
306 24 : T->pending[wheel] &= ~(WHEEL_C(1) << slot);
307 : }
308 :
309 29 : to->pending = NULL;
310 9324 : TO_SET_TIMEOUTS(to, NULL);
311 : }
312 9324 : } /* timeouts_del() */
313 :
314 :
315 7003 : static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to) {
316 7003 : return to->expires - T->curtime;
317 : } /* timeout_rem() */
318 :
319 :
320 7003 : static inline int timeout_wheel(timeout_t timeout) {
321 : /* must be called with timeout != 0, so fls input is nonzero */
322 7003 : return (fls(MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT;
323 : } /* timeout_wheel() */
324 :
325 :
326 7003 : static inline int timeout_slot(int wheel, timeout_t expires) {
327 7003 : return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel);
328 : } /* timeout_slot() */
329 :
330 :
331 8208 : static void timeouts_sched(struct timeouts *T, struct timeout *to, timeout_t expires) {
332 8208 : timeout_t rem;
333 8208 : int wheel, slot;
334 :
335 8208 : timeouts_del(T, to);
336 :
337 8208 : to->expires = expires;
338 :
339 8208 : TO_SET_TIMEOUTS(to, T);
340 :
341 8208 : if (expires > T->curtime) {
342 7003 : rem = timeout_rem(T, to);
343 :
344 : /* rem is nonzero since:
345 : * rem == timeout_rem(T,to),
346 : * == to->expires - T->curtime
347 : * and above we have expires > T->curtime.
348 : */
349 7003 : wheel = timeout_wheel(rem);
350 7003 : slot = timeout_slot(wheel, to->expires);
351 :
352 7003 : to->pending = &T->wheel[wheel][slot];
353 7003 : TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
354 :
355 7003 : T->pending[wheel] |= WHEEL_C(1) << slot;
356 : } else {
357 1205 : to->pending = &T->expired;
358 1205 : TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
359 : }
360 8208 : } /* timeouts_sched() */
361 :
362 :
363 : #ifndef TIMEOUT_DISABLE_INTERVALS
364 : static void timeouts_readd(struct timeouts *T, struct timeout *to) {
365 : to->expires += to->interval;
366 :
367 : if (to->expires <= T->curtime) {
368 : /* If we've missed the next firing of this timeout, reschedule
369 : * it to occur at the next multiple of its interval after
370 : * the last time that it fired.
371 : */
372 : timeout_t n = T->curtime - to->expires;
373 : timeout_t r = n % to->interval;
374 : to->expires = T->curtime + (to->interval - r);
375 : }
376 :
377 : timeouts_sched(T, to, to->expires);
378 : } /* timeouts_readd() */
379 : #endif
380 :
381 :
382 1234 : TIMEOUT_PUBLIC void timeouts_add(struct timeouts *T, struct timeout *to, timeout_t timeout) {
383 : #ifndef TIMEOUT_DISABLE_INTERVALS
384 : if (to->flags & TIMEOUT_INT)
385 : to->interval = MAX(1, timeout);
386 : #endif
387 :
388 1234 : if (to->flags & TIMEOUT_ABS)
389 0 : timeouts_sched(T, to, timeout);
390 : else
391 1234 : timeouts_sched(T, to, T->curtime + timeout);
392 1234 : } /* timeouts_add() */
393 :
394 :
395 4997 : TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) {
396 4997 : timeout_t elapsed = curtime - T->curtime;
397 4997 : struct timeout_list todo;
398 4997 : int wheel;
399 :
400 4997 : TOR_TAILQ_INIT(&todo);
401 :
402 : /*
403 : * There's no avoiding looping over every wheel. It's best to keep
404 : * WHEEL_NUM smallish.
405 : */
406 7137 : for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
407 6962 : wheel_t pending;
408 :
409 : /*
410 : * Calculate the slots expiring in this wheel
411 : *
412 : * If the elapsed time is greater than the maximum period of
413 : * the wheel, mark every position as expiring.
414 : *
415 : * Otherwise, to determine the expired slots fill in all the
416 : * bits between the last slot processed and the current
417 : * slot, inclusive of the last slot. We'll bitwise-AND this
418 : * with our pending set below.
419 : *
420 : * If a wheel rolls over, force a tick of the next higher
421 : * wheel.
422 : */
423 6962 : if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) {
424 6962 : pending = (wheel_t)~WHEEL_C(0);
425 : } else {
426 6153 : wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT));
427 6153 : int oslot, nslot;
428 :
429 : /*
430 : * TODO: It's likely that at least one of the
431 : * following three bit fill operations is redundant
432 : * or can be replaced with a simpler operation.
433 : */
434 6153 : oslot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT));
435 6153 : pending = rotl(((WHEEL_C(1) << _elapsed) - 1), oslot);
436 :
437 6153 : nslot = WHEEL_MASK & (curtime >> (wheel * WHEEL_BIT));
438 6153 : pending |= rotr(rotl(((WHEEL_C(1) << _elapsed) - 1), nslot), (int)_elapsed);
439 6153 : pending |= WHEEL_C(1) << nslot;
440 : }
441 :
442 9338 : while (pending & T->pending[wheel]) {
443 : /* ctz input cannot be zero: loop condition. */
444 2376 : int slot = ctz(pending & T->pending[wheel]);
445 2376 : TOR_TAILQ_CONCAT(&todo, &T->wheel[wheel][slot], tqe);
446 2376 : T->pending[wheel] &= ~(UINT64_C(1) << slot);
447 : }
448 :
449 6962 : if (!(0x1 & pending))
450 : break; /* break if we didn't wrap around end of wheel */
451 :
452 : /* if we're continuing, the next wheel must tick at least once */
453 2140 : elapsed = MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT)));
454 : }
455 :
456 4997 : T->curtime = curtime;
457 :
458 11971 : while (!TOR_TAILQ_EMPTY(&todo)) {
459 6974 : struct timeout *to = TOR_TAILQ_FIRST(&todo);
460 :
461 6974 : TOR_TAILQ_REMOVE(&todo, to, tqe);
462 6974 : to->pending = NULL;
463 :
464 6974 : timeouts_sched(T, to, to->expires);
465 : }
466 :
467 4997 : return;
468 : } /* timeouts_update() */
469 :
470 : TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *T) {
471 : return T->curtime;
472 : } /* timeouts_get_curtime() */
473 :
474 : TIMEOUT_PUBLIC void timeouts_step(struct timeouts *T, reltime_t elapsed) {
475 : timeouts_update(T, T->curtime + elapsed);
476 : } /* timeouts_step() */
477 :
478 :
479 : TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *T) {
480 : wheel_t pending = 0;
481 : int wheel;
482 :
483 : for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
484 : pending |= T->pending[wheel];
485 : }
486 :
487 : return !!pending;
488 : } /* timeouts_pending() */
489 :
490 :
491 : TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *T) {
492 : return !TOR_TAILQ_EMPTY(&T->expired);
493 : } /* timeouts_expired() */
494 :
495 :
496 : /*
497 : * Calculate the interval before needing to process any timeouts pending on
498 : * any wheel.
499 : *
500 : * (This is separated from the public API routine so we can evaluate our
501 : * wheel invariant assertions irrespective of the expired queue.)
502 : *
503 : * This might return a timeout value sooner than any installed timeout if
504 : * only higher-order wheels have timeouts pending. We can only know when to
505 : * process a wheel, not precisely when a timeout is scheduled. Our timeout
506 : * accuracy could be off by 2^(N*M)-1 units where N is the wheel number and
507 : * M is WHEEL_BIT. Only timeouts which have fallen through to wheel 0 can be
508 : * known exactly.
509 : *
510 : * We should never return a timeout larger than the lowest actual timeout.
511 : */
512 3053 : static timeout_t timeouts_int(struct timeouts *T) {
513 3053 : timeout_t timeout = ~TIMEOUT_C(0), _timeout;
514 3053 : timeout_t relmask;
515 3053 : int wheel, slot;
516 :
517 3053 : relmask = 0;
518 :
519 18318 : for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
520 15265 : if (T->pending[wheel]) {
521 9222 : slot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT));
522 :
523 : /* ctz input cannot be zero: T->pending[wheel] is
524 : * nonzero, so rotr() is nonzero. */
525 9222 : _timeout = (ctz(rotr(T->pending[wheel], slot)) + !!wheel) << (wheel * WHEEL_BIT);
526 : /* +1 to higher order wheels as those timeouts are one rotation in the future (otherwise they'd be on a lower wheel or expired) */
527 :
528 9222 : _timeout -= relmask & T->curtime;
529 : /* reduce by how much lower wheels have progressed */
530 :
531 9222 : timeout = MIN(_timeout, timeout);
532 : }
533 :
534 15265 : relmask <<= WHEEL_BIT;
535 15265 : relmask |= WHEEL_MASK;
536 : }
537 :
538 3053 : return timeout;
539 : } /* timeouts_int() */
540 :
541 :
542 : /*
543 : * Calculate the interval our caller can wait before needing to process
544 : * events.
545 : */
546 3053 : TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *T) {
547 3053 : if (!TOR_TAILQ_EMPTY(&T->expired))
548 : return 0;
549 :
550 3053 : return timeouts_int(T);
551 : } /* timeouts_timeout() */
552 :
553 :
554 3149 : TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *T) {
555 3149 : if (!TOR_TAILQ_EMPTY(&T->expired)) {
556 1205 : struct timeout *to = TOR_TAILQ_FIRST(&T->expired);
557 :
558 1205 : TOR_TAILQ_REMOVE(&T->expired, to, tqe);
559 1205 : to->pending = NULL;
560 1205 : TO_SET_TIMEOUTS(to, NULL);
561 :
562 : #ifndef TIMEOUT_DISABLE_INTERVALS
563 : if ((to->flags & TIMEOUT_INT) && to->interval > 0)
564 : timeouts_readd(T, to);
565 : #endif
566 :
567 1205 : return to;
568 : } else {
569 : return 0;
570 : }
571 : } /* timeouts_get() */
572 :
573 :
574 : /*
575 : * Use dumb looping to locate the earliest timeout pending on the wheel so
576 : * our invariant assertions can check the result of our optimized code.
577 : */
578 : static struct timeout *timeouts_min(struct timeouts *T) {
579 : struct timeout *to, *min = NULL;
580 : unsigned i, j;
581 :
582 : for (i = 0; i < countof(T->wheel); i++) {
583 : for (j = 0; j < countof(T->wheel[i]); j++) {
584 : TOR_TAILQ_FOREACH(to, &T->wheel[i][j], tqe) {
585 : if (!min || to->expires < min->expires)
586 : min = to;
587 : }
588 : }
589 : }
590 :
591 : return min;
592 : } /* timeouts_min() */
593 :
594 :
595 : /*
596 : * Check some basic algorithm invariants. If these invariants fail then
597 : * something is definitely broken.
598 : */
599 : #define report(...) do { \
600 : if ((fp)) \
601 : fprintf(fp, __VA_ARGS__); \
602 : } while (0)
603 :
604 : #define check(expr, ...) do { \
605 : if (!(expr)) { \
606 : report(__VA_ARGS__); \
607 : return 0; \
608 : } \
609 : } while (0)
610 :
611 : TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *T, FILE *fp) {
612 : timeout_t timeout;
613 : struct timeout *to;
614 :
615 : if ((to = timeouts_min(T))) {
616 : check(to->expires > T->curtime, "missed timeout (expires:%" TIMEOUT_PRIu " <= curtime:%" TIMEOUT_PRIu ")\n", to->expires, T->curtime);
617 :
618 : timeout = timeouts_int(T);
619 : check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime);
620 :
621 : timeout = timeouts_timeout(T);
622 : check(timeout <= to->expires - T->curtime, "wrong soft timeout (soft:%" TIMEOUT_PRIu " > hard:%" TIMEOUT_PRIu ") (expires:%" TIMEOUT_PRIu "; curtime:%" TIMEOUT_PRIu ")\n", timeout, (to->expires - T->curtime), to->expires, T->curtime);
623 : } else {
624 : timeout = timeouts_timeout(T);
625 :
626 : if (!TOR_TAILQ_EMPTY(&T->expired))
627 : check(timeout == 0, "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, TIMEOUT_C(0));
628 : else
629 : check(timeout == ~TIMEOUT_C(0), "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, ~TIMEOUT_C(0));
630 : }
631 :
632 : return 1;
633 : } /* timeouts_check() */
634 :
635 :
636 : #define ENTER \
637 : do { \
638 : static const int pc0 = __LINE__; \
639 : switch (pc0 + it->pc) { \
640 : case __LINE__: (void)0
641 :
642 : #define SAVE_AND_DO(do_statement) \
643 : do { \
644 : it->pc = __LINE__ - pc0; \
645 : do_statement; \
646 : case __LINE__: (void)0; \
647 : } while (0)
648 :
649 : #define YIELD(rv) \
650 : SAVE_AND_DO(return (rv))
651 :
652 : #define LEAVE \
653 : SAVE_AND_DO(break); \
654 : } \
655 : } while (0)
656 :
657 : TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *T, struct timeouts_it *it) {
658 : struct timeout *to;
659 :
660 : ENTER;
661 :
662 : if (it->flags & TIMEOUTS_EXPIRED) {
663 : if (it->flags & TIMEOUTS_CLEAR) {
664 : while ((to = timeouts_get(T))) {
665 : YIELD(to);
666 : }
667 : } else {
668 : TOR_TAILQ_FOREACH_SAFE(to, &T->expired, tqe, it->to) {
669 : YIELD(to);
670 : }
671 : }
672 : }
673 :
674 : if (it->flags & TIMEOUTS_PENDING) {
675 : for (it->i = 0; it->i < countof(T->wheel); it->i++) {
676 : for (it->j = 0; it->j < countof(T->wheel[it->i]); it->j++) {
677 : TOR_TAILQ_FOREACH_SAFE(to, &T->wheel[it->i][it->j], tqe, it->to) {
678 : YIELD(to);
679 : }
680 : }
681 : }
682 : }
683 :
684 : LEAVE;
685 :
686 : return NULL;
687 : } /* timeouts_next */
688 :
689 : #undef LEAVE
690 : #undef YIELD
691 : #undef SAVE_AND_DO
692 : #undef ENTER
693 :
694 :
695 : /*
696 : * T I M E O U T R O U T I N E S
697 : *
698 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
699 :
700 1107 : TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *to, int flags) {
701 1107 : memset(to, 0, sizeof *to);
702 :
703 1107 : to->flags = flags;
704 :
705 1107 : return to;
706 : } /* timeout_init() */
707 :
708 :
709 : #ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
710 : TIMEOUT_PUBLIC bool timeout_pending(struct timeout *to) {
711 : return to->pending && to->pending != &to->timeouts->expired;
712 : } /* timeout_pending() */
713 :
714 :
715 : TIMEOUT_PUBLIC bool timeout_expired(struct timeout *to) {
716 : return to->pending && to->pending == &to->timeouts->expired;
717 : } /* timeout_expired() */
718 :
719 :
720 : TIMEOUT_PUBLIC void timeout_del(struct timeout *to) {
721 : timeouts_del(to->timeouts, to);
722 : } /* timeout_del() */
723 : #endif
724 :
725 :
726 : /*
727 : * V E R S I O N I N T E R F A C E S
728 : *
729 : * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
730 :
731 : TIMEOUT_PUBLIC int timeout_version(void) {
732 : return TIMEOUT_VERSION;
733 : } /* timeout_version() */
734 :
735 :
736 : TIMEOUT_PUBLIC const char *timeout_vendor(void) {
737 : return TIMEOUT_VENDOR;
738 : } /* timeout_version() */
739 :
740 :
741 : TIMEOUT_PUBLIC int timeout_v_rel(void) {
742 : return TIMEOUT_V_REL;
743 : } /* timeout_version() */
744 :
745 :
746 : TIMEOUT_PUBLIC int timeout_v_abi(void) {
747 : return TIMEOUT_V_ABI;
748 : } /* timeout_version() */
749 :
750 :
751 : TIMEOUT_PUBLIC int timeout_v_api(void) {
752 : return TIMEOUT_V_API;
753 : } /* timeout_version() */
|
