#ifdef HAVE_CONFIG_H
#include "orconfig.h"
#endif
#include <limits.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <string.h>
#include <errno.h>
#include "ext/tor_queue.h"
#include "ext/timeouts/timeout.h"
#ifndef TIMEOUT_DEBUG
#define TIMEOUT_DEBUG 0
#endif
#if TIMEOUT_DEBUG - 0
#include "ext/timeouts/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 "ext/timeouts/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((uint32_t)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(((WHEEL_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;
}