Tor  0.4.7.0-alpha-dev
timeout.c
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 static inline wheel_t rotl(const wheel_t v, int c) {
193  if (!(c &= (sizeof v * CHAR_BIT - 1)))
194  return v;
195 
196  return (v << c) | (v >> (sizeof v * CHAR_BIT - c));
197 } /* rotl() */
198 
199 
200 static inline wheel_t rotr(const wheel_t v, int c) {
201  if (!(c &= (sizeof v * CHAR_BIT - 1)))
202  return v;
203 
204  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 static struct timeouts *timeouts_init(struct timeouts *T, timeout_t hz) {
226  unsigned i, j;
227 
228  for (i = 0; i < countof(T->wheel); i++) {
229  for (j = 0; j < countof(T->wheel[i]); j++) {
230  TOR_TAILQ_INIT(&T->wheel[i][j]);
231  }
232  }
233 
234  TOR_TAILQ_INIT(&T->expired);
235 
236  for (i = 0; i < countof(T->pending); i++) {
237  T->pending[i] = 0;
238  }
239 
240  T->curtime = 0;
241  T->hertz = (hz)? hz : TIMEOUT_mHZ;
242 
243  return T;
244 } /* timeouts_init() */
245 
246 
247 TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t hz, int *error) {
248  struct timeouts *T;
249 
250  if ((T = malloc(sizeof *T)))
251  return timeouts_init(T, hz);
252 
253  *error = errno;
254 
255  return NULL;
256 } /* timeouts_open() */
257 
258 
259 static void timeouts_reset(struct timeouts *T) {
260  struct timeout_list reset;
261  struct timeout *to;
262  unsigned i, j;
263 
264  TOR_TAILQ_INIT(&reset);
265 
266  for (i = 0; i < countof(T->wheel); i++) {
267  for (j = 0; j < countof(T->wheel[i]); j++) {
268  TOR_TAILQ_CONCAT(&reset, &T->wheel[i][j], tqe);
269  }
270  }
271 
272  TOR_TAILQ_CONCAT(&reset, &T->expired, tqe);
273 
274  TOR_TAILQ_FOREACH(to, &reset, tqe) {
275  to->pending = NULL;
276  TO_SET_TIMEOUTS(to, NULL);
277  }
278 } /* timeouts_reset() */
279 
280 
281 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  timeouts_reset(T);
287 
288  free(T);
289 } /* timeouts_close() */
290 
291 
292 TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *T) {
293  return T->hertz;
294 } /* timeouts_hz() */
295 
296 
297 TIMEOUT_PUBLIC void timeouts_del(struct timeouts *T, struct timeout *to) {
298  if (to->pending) {
299  TOR_TAILQ_REMOVE(to->pending, to, tqe);
300 
301  if (to->pending != &T->expired && TOR_TAILQ_EMPTY(to->pending)) {
302  ptrdiff_t index_ = to->pending - &T->wheel[0][0];
303  int wheel = (int) (index_ / WHEEL_LEN);
304  int slot = index_ % WHEEL_LEN;
305 
306  T->pending[wheel] &= ~(WHEEL_C(1) << slot);
307  }
308 
309  to->pending = NULL;
310  TO_SET_TIMEOUTS(to, NULL);
311  }
312 } /* timeouts_del() */
313 
314 
315 static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to) {
316  return to->expires - T->curtime;
317 } /* timeout_rem() */
318 
319 
320 static inline int timeout_wheel(timeout_t timeout) {
321  /* must be called with timeout != 0, so fls input is nonzero */
322  return (fls(MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT;
323 } /* timeout_wheel() */
324 
325 
326 static inline int timeout_slot(int wheel, timeout_t expires) {
327  return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel);
328 } /* timeout_slot() */
329 
330 
331 static void timeouts_sched(struct timeouts *T, struct timeout *to, timeout_t expires) {
332  timeout_t rem;
333  int wheel, slot;
334 
335  timeouts_del(T, to);
336 
337  to->expires = expires;
338 
339  TO_SET_TIMEOUTS(to, T);
340 
341  if (expires > T->curtime) {
342  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  wheel = timeout_wheel(rem);
350  slot = timeout_slot(wheel, to->expires);
351 
352  to->pending = &T->wheel[wheel][slot];
353  TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
354 
355  T->pending[wheel] |= WHEEL_C(1) << slot;
356  } else {
357  to->pending = &T->expired;
358  TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
359  }
360 } /* 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 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  if (to->flags & TIMEOUT_ABS)
389  timeouts_sched(T, to, timeout);
390  else
391  timeouts_sched(T, to, T->curtime + timeout);
392 } /* timeouts_add() */
393 
394 
395 TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) {
396  timeout_t elapsed = curtime - T->curtime;
397  struct timeout_list todo;
398  int wheel;
399 
400  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  for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
407  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  if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) {
424  pending = (wheel_t)~WHEEL_C(0);
425  } else {
426  wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT));
427  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  oslot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT));
435  pending = rotl(((WHEEL_C(1) << _elapsed) - 1), oslot);
436 
437  nslot = WHEEL_MASK & (curtime >> (wheel * WHEEL_BIT));
438  pending |= rotr(rotl(((WHEEL_C(1) << _elapsed) - 1), nslot), (int)_elapsed);
439  pending |= WHEEL_C(1) << nslot;
440  }
441 
442  while (pending & T->pending[wheel]) {
443  /* ctz input cannot be zero: loop condition. */
444  int slot = ctz(pending & T->pending[wheel]);
445  TOR_TAILQ_CONCAT(&todo, &T->wheel[wheel][slot], tqe);
446  T->pending[wheel] &= ~(UINT64_C(1) << slot);
447  }
448 
449  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  elapsed = MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT)));
454  }
455 
456  T->curtime = curtime;
457 
458  while (!TOR_TAILQ_EMPTY(&todo)) {
459  struct timeout *to = TOR_TAILQ_FIRST(&todo);
460 
461  TOR_TAILQ_REMOVE(&todo, to, tqe);
462  to->pending = NULL;
463 
464  timeouts_sched(T, to, to->expires);
465  }
466 
467  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 static timeout_t timeouts_int(struct timeouts *T) {
513  timeout_t timeout = ~TIMEOUT_C(0), _timeout;
514  timeout_t relmask;
515  int wheel, slot;
516 
517  relmask = 0;
518 
519  for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
520  if (T->pending[wheel]) {
521  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  _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  _timeout -= relmask & T->curtime;
529  /* reduce by how much lower wheels have progressed */
530 
531  timeout = MIN(_timeout, timeout);
532  }
533 
534  relmask <<= WHEEL_BIT;
535  relmask |= WHEEL_MASK;
536  }
537 
538  return timeout;
539 } /* timeouts_int() */
540 
541 
542 /*
543  * Calculate the interval our caller can wait before needing to process
544  * events.
545  */
546 TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *T) {
547  if (!TOR_TAILQ_EMPTY(&T->expired))
548  return 0;
549 
550  return timeouts_int(T);
551 } /* timeouts_timeout() */
552 
553 
554 TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *T) {
555  if (!TOR_TAILQ_EMPTY(&T->expired)) {
556  struct timeout *to = TOR_TAILQ_FIRST(&T->expired);
557 
558  TOR_TAILQ_REMOVE(&T->expired, to, tqe);
559  to->pending = NULL;
560  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  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 TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *to, int flags) {
701  memset(to, 0, sizeof *to);
702 
703  to->flags = flags;
704 
705  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() */
#define MAX(a, b)
Definition: cmp.h:22
#define T(s, t, a, o)
Definition: parsecommon.h:245