src/ext/timeouts/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() */