123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754 |
- #ifdef HAVE_CONFIG_H
- #include "orconfig.h"
- #endif
- #include <limits.h> /* CHAR_BIT */
- #include <stddef.h> /* NULL */
- #include <stdlib.h> /* malloc(3) free(3) */
- #include <stdio.h> /* FILE fprintf(3) */
- #include <inttypes.h> /* UINT64_C uint64_t */
- #include <string.h> /* memset(3) */
- #include <errno.h> /* errno */
- #include "tor_queue.h"
- #include "timeout.h"
- #ifndef TIMEOUT_DEBUG
- #define TIMEOUT_DEBUG 0
- #endif
- #if TIMEOUT_DEBUG - 0
- #include "timeout-debug.h"
- #endif
- #ifdef TIMEOUT_DISABLE_RELATIVE_ACCESS
- #define TO_SET_TIMEOUTS(to, T) ((void)0)
- #else
- #define TO_SET_TIMEOUTS(to, T) ((to)->timeouts = (T))
- #endif
- #define abstime_t timeout_t
- #define reltime_t timeout_t
- #if !defined countof
- #define countof(a) (sizeof (a) / sizeof *(a))
- #endif
- #if !defined endof
- #define endof(a) (&(a)[countof(a)])
- #endif
- #if !defined MIN
- #define MIN(a, b) (((a) < (b))? (a) : (b))
- #endif
- #if !defined MAX
- #define MAX(a, b) (((a) > (b))? (a) : (b))
- #endif
- #if !defined TOR_TAILQ_CONCAT
- #define TOR_TAILQ_CONCAT(head1, head2, field) do { \
- if (!TOR_TAILQ_EMPTY(head2)) { \
- *(head1)->tqh_last = (head2)->tqh_first; \
- (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
- (head1)->tqh_last = (head2)->tqh_last; \
- TOR_TAILQ_INIT((head2)); \
- } \
- } while (0)
- #endif
- #if !defined TOR_TAILQ_FOREACH_SAFE
- #define TOR_TAILQ_FOREACH_SAFE(var, head, field, tvar) \
- for ((var) = TOR_TAILQ_FIRST(head); \
- (var) && ((tvar) = TOR_TAILQ_NEXT(var, field), 1); \
- (var) = (tvar))
- #endif
- #if !defined WHEEL_BIT
- #define WHEEL_BIT 6
- #endif
- #if !defined WHEEL_NUM
- #define WHEEL_NUM 4
- #endif
- #define WHEEL_LEN (1U << WHEEL_BIT)
- #define WHEEL_MAX (WHEEL_LEN - 1)
- #define WHEEL_MASK (WHEEL_LEN - 1)
- #define TIMEOUT_MAX ((TIMEOUT_C(1) << (WHEEL_BIT * WHEEL_NUM)) - 1)
- #include "timeout-bitops.c"
- #if WHEEL_BIT == 6
- #define ctz(n) ctz64(n)
- #define clz(n) clz64(n)
- #define fls(n) ((int)(64 - clz64(n)))
- #else
- #define ctz(n) ctz32(n)
- #define clz(n) clz32(n)
- #define fls(n) ((int)(32 - clz32(n)))
- #endif
- #if WHEEL_BIT == 6
- #define WHEEL_C(n) UINT64_C(n)
- #define WHEEL_PRIu PRIu64
- #define WHEEL_PRIx PRIx64
- typedef uint64_t wheel_t;
- #elif WHEEL_BIT == 5
- #define WHEEL_C(n) UINT32_C(n)
- #define WHEEL_PRIu PRIu32
- #define WHEEL_PRIx PRIx32
- typedef uint32_t wheel_t;
- #elif WHEEL_BIT == 4
- #define WHEEL_C(n) UINT16_C(n)
- #define WHEEL_PRIu PRIu16
- #define WHEEL_PRIx PRIx16
- typedef uint16_t wheel_t;
- #elif WHEEL_BIT == 3
- #define WHEEL_C(n) UINT8_C(n)
- #define WHEEL_PRIu PRIu8
- #define WHEEL_PRIx PRIx8
- typedef uint8_t wheel_t;
- #else
- #error invalid WHEEL_BIT value
- #endif
- static inline wheel_t rotl(const wheel_t v, int c) {
- if (!(c &= (sizeof v * CHAR_BIT - 1)))
- return v;
- return (v << c) | (v >> (sizeof v * CHAR_BIT - c));
- }
- static inline wheel_t rotr(const wheel_t v, int c) {
- if (!(c &= (sizeof v * CHAR_BIT - 1)))
- return v;
- return (v >> c) | (v << (sizeof v * CHAR_BIT - c));
- }
- TOR_TAILQ_HEAD(timeout_list, timeout);
- struct timeouts {
- struct timeout_list wheel[WHEEL_NUM][WHEEL_LEN], expired;
- wheel_t pending[WHEEL_NUM];
- timeout_t curtime;
- timeout_t hertz;
- };
- static struct timeouts *timeouts_init(struct timeouts *T, timeout_t hz) {
- unsigned i, j;
- for (i = 0; i < countof(T->wheel); i++) {
- for (j = 0; j < countof(T->wheel[i]); j++) {
- TOR_TAILQ_INIT(&T->wheel[i][j]);
- }
- }
- TOR_TAILQ_INIT(&T->expired);
- for (i = 0; i < countof(T->pending); i++) {
- T->pending[i] = 0;
- }
- T->curtime = 0;
- T->hertz = (hz)? hz : TIMEOUT_mHZ;
- return T;
- }
- TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t hz, int *error) {
- struct timeouts *T;
- if ((T = malloc(sizeof *T)))
- return timeouts_init(T, hz);
- *error = errno;
- return NULL;
- }
- static void timeouts_reset(struct timeouts *T) {
- struct timeout_list reset;
- struct timeout *to;
- unsigned i, j;
- TOR_TAILQ_INIT(&reset);
- for (i = 0; i < countof(T->wheel); i++) {
- for (j = 0; j < countof(T->wheel[i]); j++) {
- TOR_TAILQ_CONCAT(&reset, &T->wheel[i][j], tqe);
- }
- }
- TOR_TAILQ_CONCAT(&reset, &T->expired, tqe);
- TOR_TAILQ_FOREACH(to, &reset, tqe) {
- to->pending = NULL;
- TO_SET_TIMEOUTS(to, NULL);
- }
- }
- TIMEOUT_PUBLIC void timeouts_close(struct timeouts *T) {
-
- timeouts_reset(T);
- free(T);
- }
- TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *T) {
- return T->hertz;
- }
- TIMEOUT_PUBLIC void timeouts_del(struct timeouts *T, struct timeout *to) {
- if (to->pending) {
- TOR_TAILQ_REMOVE(to->pending, to, tqe);
- if (to->pending != &T->expired && TOR_TAILQ_EMPTY(to->pending)) {
- ptrdiff_t index_ = to->pending - &T->wheel[0][0];
- int wheel = (int) (index_ / WHEEL_LEN);
- int slot = index_ % WHEEL_LEN;
- T->pending[wheel] &= ~(WHEEL_C(1) << slot);
- }
- to->pending = NULL;
- TO_SET_TIMEOUTS(to, NULL);
- }
- }
- static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to) {
- return to->expires - T->curtime;
- }
- static inline int timeout_wheel(timeout_t timeout) {
-
- return (fls(MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT;
- }
- static inline int timeout_slot(int wheel, timeout_t expires) {
- return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel);
- }
- static void timeouts_sched(struct timeouts *T, struct timeout *to, timeout_t expires) {
- timeout_t rem;
- int wheel, slot;
- timeouts_del(T, to);
- to->expires = expires;
- TO_SET_TIMEOUTS(to, T);
- if (expires > T->curtime) {
- rem = timeout_rem(T, to);
-
- wheel = timeout_wheel(rem);
- slot = timeout_slot(wheel, to->expires);
- to->pending = &T->wheel[wheel][slot];
- TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
- T->pending[wheel] |= WHEEL_C(1) << slot;
- } else {
- to->pending = &T->expired;
- TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
- }
- }
- #ifndef TIMEOUT_DISABLE_INTERVALS
- static void timeouts_readd(struct timeouts *T, struct timeout *to) {
- to->expires += to->interval;
- if (to->expires <= T->curtime) {
-
- timeout_t n = T->curtime - to->expires;
- timeout_t r = n % to->interval;
- to->expires = T->curtime + (to->interval - r);
- }
- timeouts_sched(T, to, to->expires);
- }
- #endif
- TIMEOUT_PUBLIC void timeouts_add(struct timeouts *T, struct timeout *to, timeout_t timeout) {
- #ifndef TIMEOUT_DISABLE_INTERVALS
- if (to->flags & TIMEOUT_INT)
- to->interval = MAX(1, timeout);
- #endif
- if (to->flags & TIMEOUT_ABS)
- timeouts_sched(T, to, timeout);
- else
- timeouts_sched(T, to, T->curtime + timeout);
- }
- TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) {
- timeout_t elapsed = curtime - T->curtime;
- struct timeout_list todo;
- int wheel;
- TOR_TAILQ_INIT(&todo);
-
- for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
- wheel_t pending;
-
- if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) {
- pending = (wheel_t)~WHEEL_C(0);
- } else {
- wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT));
- int oslot, nslot;
-
- oslot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT));
- pending = rotl(((UINT64_C(1) << _elapsed) - 1), oslot);
- nslot = WHEEL_MASK & (curtime >> (wheel * WHEEL_BIT));
- pending |= rotr(rotl(((WHEEL_C(1) << _elapsed) - 1), nslot), (int)_elapsed);
- pending |= WHEEL_C(1) << nslot;
- }
- while (pending & T->pending[wheel]) {
-
- int slot = ctz(pending & T->pending[wheel]);
- TOR_TAILQ_CONCAT(&todo, &T->wheel[wheel][slot], tqe);
- T->pending[wheel] &= ~(UINT64_C(1) << slot);
- }
- if (!(0x1 & pending))
- break;
-
- elapsed = MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT)));
- }
- T->curtime = curtime;
- while (!TOR_TAILQ_EMPTY(&todo)) {
- struct timeout *to = TOR_TAILQ_FIRST(&todo);
- TOR_TAILQ_REMOVE(&todo, to, tqe);
- to->pending = NULL;
- timeouts_sched(T, to, to->expires);
- }
- return;
- }
- TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(struct timeouts *T) {
- return T->curtime;
- }
- TIMEOUT_PUBLIC void timeouts_step(struct timeouts *T, reltime_t elapsed) {
- timeouts_update(T, T->curtime + elapsed);
- }
- TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *T) {
- wheel_t pending = 0;
- int wheel;
- for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
- pending |= T->pending[wheel];
- }
- return !!pending;
- }
- TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *T) {
- return !TOR_TAILQ_EMPTY(&T->expired);
- }
- static timeout_t timeouts_int(struct timeouts *T) {
- timeout_t timeout = ~TIMEOUT_C(0), _timeout;
- timeout_t relmask;
- int wheel, slot;
- relmask = 0;
- for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
- if (T->pending[wheel]) {
- slot = WHEEL_MASK & (T->curtime >> (wheel * WHEEL_BIT));
-
- _timeout = (ctz(rotr(T->pending[wheel], slot)) + !!wheel) << (wheel * WHEEL_BIT);
-
- _timeout -= relmask & T->curtime;
-
- timeout = MIN(_timeout, timeout);
- }
- relmask <<= WHEEL_BIT;
- relmask |= WHEEL_MASK;
- }
- return timeout;
- }
- TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *T) {
- if (!TOR_TAILQ_EMPTY(&T->expired))
- return 0;
- return timeouts_int(T);
- }
- TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *T) {
- if (!TOR_TAILQ_EMPTY(&T->expired)) {
- struct timeout *to = TOR_TAILQ_FIRST(&T->expired);
- TOR_TAILQ_REMOVE(&T->expired, to, tqe);
- to->pending = NULL;
- TO_SET_TIMEOUTS(to, NULL);
- #ifndef TIMEOUT_DISABLE_INTERVALS
- if ((to->flags & TIMEOUT_INT) && to->interval > 0)
- timeouts_readd(T, to);
- #endif
- return to;
- } else {
- return 0;
- }
- }
- static struct timeout *timeouts_min(struct timeouts *T) {
- struct timeout *to, *min = NULL;
- unsigned i, j;
- for (i = 0; i < countof(T->wheel); i++) {
- for (j = 0; j < countof(T->wheel[i]); j++) {
- TOR_TAILQ_FOREACH(to, &T->wheel[i][j], tqe) {
- if (!min || to->expires < min->expires)
- min = to;
- }
- }
- }
- return min;
- }
- #define report(...) do { \
- if ((fp)) \
- fprintf(fp, __VA_ARGS__); \
- } while (0)
- #define check(expr, ...) do { \
- if (!(expr)) { \
- report(__VA_ARGS__); \
- return 0; \
- } \
- } while (0)
- TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *T, FILE *fp) {
- timeout_t timeout;
- struct timeout *to;
- if ((to = timeouts_min(T))) {
- check(to->expires > T->curtime, "missed timeout (expires:%" TIMEOUT_PRIu " <= curtime:%" TIMEOUT_PRIu ")\n", to->expires, T->curtime);
- timeout = timeouts_int(T);
- 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);
- timeout = timeouts_timeout(T);
- 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);
- } else {
- timeout = timeouts_timeout(T);
- if (!TOR_TAILQ_EMPTY(&T->expired))
- check(timeout == 0, "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, TIMEOUT_C(0));
- else
- check(timeout == ~TIMEOUT_C(0), "wrong soft timeout (soft:%" TIMEOUT_PRIu " != hard:%" TIMEOUT_PRIu ")\n", timeout, ~TIMEOUT_C(0));
- }
- return 1;
- }
- #define ENTER \
- do { \
- static const int pc0 = __LINE__; \
- switch (pc0 + it->pc) { \
- case __LINE__: (void)0
- #define SAVE_AND_DO(do_statement) \
- do { \
- it->pc = __LINE__ - pc0; \
- do_statement; \
- case __LINE__: (void)0; \
- } while (0)
- #define YIELD(rv) \
- SAVE_AND_DO(return (rv))
- #define LEAVE \
- SAVE_AND_DO(break); \
- } \
- } while (0)
- TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *T, struct timeouts_it *it) {
- struct timeout *to;
- ENTER;
- if (it->flags & TIMEOUTS_EXPIRED) {
- if (it->flags & TIMEOUTS_CLEAR) {
- while ((to = timeouts_get(T))) {
- YIELD(to);
- }
- } else {
- TOR_TAILQ_FOREACH_SAFE(to, &T->expired, tqe, it->to) {
- YIELD(to);
- }
- }
- }
- if (it->flags & TIMEOUTS_PENDING) {
- for (it->i = 0; it->i < countof(T->wheel); it->i++) {
- for (it->j = 0; it->j < countof(T->wheel[it->i]); it->j++) {
- TOR_TAILQ_FOREACH_SAFE(to, &T->wheel[it->i][it->j], tqe, it->to) {
- YIELD(to);
- }
- }
- }
- }
- LEAVE;
- return NULL;
- }
- #undef LEAVE
- #undef YIELD
- #undef SAVE_AND_DO
- #undef ENTER
- TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *to, int flags) {
- memset(to, 0, sizeof *to);
- to->flags = flags;
- return to;
- }
- #ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
- TIMEOUT_PUBLIC bool timeout_pending(struct timeout *to) {
- return to->pending && to->pending != &to->timeouts->expired;
- }
- TIMEOUT_PUBLIC bool timeout_expired(struct timeout *to) {
- return to->pending && to->pending == &to->timeouts->expired;
- }
- TIMEOUT_PUBLIC void timeout_del(struct timeout *to) {
- timeouts_del(to->timeouts, to);
- }
- #endif
- TIMEOUT_PUBLIC int timeout_version(void) {
- return TIMEOUT_VERSION;
- }
- TIMEOUT_PUBLIC const char *timeout_vendor(void) {
- return TIMEOUT_VENDOR;
- }
- TIMEOUT_PUBLIC int timeout_v_rel(void) {
- return TIMEOUT_V_REL;
- }
- TIMEOUT_PUBLIC int timeout_v_abi(void) {
- return TIMEOUT_V_ABI;
- }
- TIMEOUT_PUBLIC int timeout_v_api(void) {
- return TIMEOUT_V_API;
- }
|