41 #include "ext/tor_queue.h"
43 #include "ext/timeouts/timeout.h"
46 #define TIMEOUT_DEBUG 0
50 #include "ext/timeouts/timeout-debug.h"
53 #ifdef TIMEOUT_DISABLE_RELATIVE_ACCESS
54 #define TO_SET_TIMEOUTS(to, T) ((void)0)
56 #define TO_SET_TIMEOUTS(to, T) ((to)->timeouts = (T))
64 #define abstime_t timeout_t
65 #define reltime_t timeout_t
68 #define countof(a) (sizeof (a) / sizeof *(a))
72 #define endof(a) (&(a)[countof(a)])
76 #define MIN(a, b) (((a) < (b))? (a) : (b))
80 #define MAX(a, b) (((a) > (b))? (a) : (b))
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)); \
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); \
131 #if !defined WHEEL_BIT
135 #if !defined WHEEL_NUM
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)
144 #include "ext/timeouts/timeout-bitops.c"
147 #define ctz(n) ctz64(n)
148 #define clz(n) clz64(n)
149 #define fls(n) ((int)(64 - clz64(n)))
151 #define ctz(n) ctz32(n)
152 #define clz(n) clz32(n)
153 #define fls(n) ((int)(32 - clz32((uint32_t)n)))
157 #define WHEEL_C(n) UINT64_C(n)
158 #define WHEEL_PRIu PRIu64
159 #define WHEEL_PRIx PRIx64
161 typedef uint64_t wheel_t;
165 #define WHEEL_C(n) UINT32_C(n)
166 #define WHEEL_PRIu PRIu32
167 #define WHEEL_PRIx PRIx32
169 typedef uint32_t wheel_t;
173 #define WHEEL_C(n) UINT16_C(n)
174 #define WHEEL_PRIu PRIu16
175 #define WHEEL_PRIx PRIx16
177 typedef uint16_t wheel_t;
181 #define WHEEL_C(n) UINT8_C(n)
182 #define WHEEL_PRIu PRIu8
183 #define WHEEL_PRIx PRIx8
185 typedef uint8_t wheel_t;
188 #error invalid WHEEL_BIT value
192 static inline wheel_t rotl(
const wheel_t v,
int c) {
193 if (!(c &= (
sizeof v * CHAR_BIT - 1)))
196 return (v << c) | (v >> (
sizeof v * CHAR_BIT - c));
200 static inline wheel_t rotr(
const wheel_t v,
int c) {
201 if (!(c &= (
sizeof v * CHAR_BIT - 1)))
204 return (v >> c) | (v << (
sizeof v * CHAR_BIT - c));
213 TOR_TAILQ_HEAD(timeout_list,
timeout);
216 struct timeout_list wheel[WHEEL_NUM][WHEEL_LEN], expired;
218 wheel_t pending[WHEEL_NUM];
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]);
234 TOR_TAILQ_INIT(&
T->expired);
236 for (i = 0; i < countof(
T->pending); i++) {
241 T->hertz = (hz)? hz : TIMEOUT_mHZ;
247 TIMEOUT_PUBLIC
struct timeouts *timeouts_open(timeout_t hz,
int *error) {
250 if ((
T = malloc(
sizeof *
T)))
251 return timeouts_init(
T, hz);
259 static void timeouts_reset(
struct timeouts *
T) {
260 struct timeout_list reset;
264 TOR_TAILQ_INIT(&reset);
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);
272 TOR_TAILQ_CONCAT(&reset, &
T->expired, tqe);
274 TOR_TAILQ_FOREACH(to, &reset, tqe) {
276 TO_SET_TIMEOUTS(to, NULL);
281 TIMEOUT_PUBLIC
void timeouts_close(
struct timeouts *
T) {
292 TIMEOUT_PUBLIC timeout_t timeouts_hz(
struct timeouts *
T) {
299 TOR_TAILQ_REMOVE(to->pending, to, tqe);
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;
306 T->pending[wheel] &= ~(WHEEL_C(1) << slot);
310 TO_SET_TIMEOUTS(to, NULL);
315 static inline reltime_t timeout_rem(
struct timeouts *
T,
struct timeout *to) {
316 return to->expires -
T->curtime;
320 static inline int timeout_wheel(timeout_t
timeout) {
322 return (fls(MIN(
timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT;
326 static inline int timeout_slot(
int wheel, timeout_t expires) {
327 return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel);
331 static void timeouts_sched(
struct timeouts *
T,
struct timeout *to, timeout_t expires) {
337 to->expires = expires;
339 TO_SET_TIMEOUTS(to,
T);
341 if (expires >
T->curtime) {
342 rem = timeout_rem(
T, to);
349 wheel = timeout_wheel(rem);
350 slot = timeout_slot(wheel, to->expires);
352 to->pending = &
T->wheel[wheel][slot];
353 TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
355 T->pending[wheel] |= WHEEL_C(1) << slot;
357 to->pending = &
T->expired;
358 TOR_TAILQ_INSERT_TAIL(to->pending, to, tqe);
363 #ifndef TIMEOUT_DISABLE_INTERVALS
365 to->expires += to->interval;
367 if (to->expires <=
T->curtime) {
372 timeout_t n =
T->curtime - to->expires;
373 timeout_t r = n % to->interval;
374 to->expires =
T->curtime + (to->interval - r);
377 timeouts_sched(
T, to, to->expires);
383 #ifndef TIMEOUT_DISABLE_INTERVALS
384 if (to->flags & TIMEOUT_INT)
388 if (to->flags & TIMEOUT_ABS)
391 timeouts_sched(
T, to,
T->curtime +
timeout);
395 TIMEOUT_PUBLIC
void timeouts_update(
struct timeouts *
T, abstime_t curtime) {
396 timeout_t elapsed = curtime -
T->curtime;
397 struct timeout_list todo;
400 TOR_TAILQ_INIT(&todo);
406 for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
423 if ((elapsed >> (wheel * WHEEL_BIT)) > WHEEL_MAX) {
424 pending = (wheel_t)~WHEEL_C(0);
426 wheel_t _elapsed = WHEEL_MASK & (elapsed >> (wheel * WHEEL_BIT));
434 oslot = WHEEL_MASK & (
T->curtime >> (wheel * WHEEL_BIT));
435 pending = rotl(((WHEEL_C(1) << _elapsed) - 1), oslot);
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;
442 while (pending &
T->pending[wheel]) {
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);
449 if (!(0x1 & pending))
453 elapsed =
MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT)));
456 T->curtime = curtime;
458 while (!TOR_TAILQ_EMPTY(&todo)) {
459 struct timeout *to = TOR_TAILQ_FIRST(&todo);
461 TOR_TAILQ_REMOVE(&todo, to, tqe);
464 timeouts_sched(
T, to, to->expires);
470 TIMEOUT_PUBLIC timeout_t timeouts_get_curtime(
struct timeouts *
T) {
474 TIMEOUT_PUBLIC
void timeouts_step(
struct timeouts *
T, reltime_t elapsed) {
475 timeouts_update(
T,
T->curtime + elapsed);
479 TIMEOUT_PUBLIC
bool timeouts_pending(
struct timeouts *
T) {
483 for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
484 pending |=
T->pending[wheel];
491 TIMEOUT_PUBLIC
bool timeouts_expired(
struct timeouts *
T) {
492 return !TOR_TAILQ_EMPTY(&
T->expired);
512 static timeout_t timeouts_int(
struct timeouts *
T) {
513 timeout_t
timeout = ~TIMEOUT_C(0), _timeout;
519 for (wheel = 0; wheel < WHEEL_NUM; wheel++) {
520 if (
T->pending[wheel]) {
521 slot = WHEEL_MASK & (
T->curtime >> (wheel * WHEEL_BIT));
525 _timeout = (ctz(rotr(
T->pending[wheel], slot)) + !!wheel) << (wheel * WHEEL_BIT);
528 _timeout -= relmask &
T->curtime;
534 relmask <<= WHEEL_BIT;
535 relmask |= WHEEL_MASK;
546 TIMEOUT_PUBLIC timeout_t timeouts_timeout(
struct timeouts *
T) {
547 if (!TOR_TAILQ_EMPTY(&
T->expired))
550 return timeouts_int(
T);
555 if (!TOR_TAILQ_EMPTY(&
T->expired)) {
556 struct timeout *to = TOR_TAILQ_FIRST(&
T->expired);
558 TOR_TAILQ_REMOVE(&
T->expired, to, tqe);
560 TO_SET_TIMEOUTS(to, NULL);
562 #ifndef TIMEOUT_DISABLE_INTERVALS
563 if ((to->flags & TIMEOUT_INT) && to->interval > 0)
564 timeouts_readd(
T, to);
579 struct timeout *to, *min = NULL;
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)
599 #define report(...) do { \
601 fprintf(fp, __VA_ARGS__); \
604 #define check(expr, ...) do { \
606 report(__VA_ARGS__); \
611 TIMEOUT_PUBLIC
bool timeouts_check(
struct timeouts *
T, FILE *fp) {
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);
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);
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);
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));
629 check(
timeout == ~TIMEOUT_C(0),
"wrong soft timeout (soft:%" TIMEOUT_PRIu
" != hard:%" TIMEOUT_PRIu
")\n",
timeout, ~TIMEOUT_C(0));
638 static const int pc0 = __LINE__; \
639 switch (pc0 + it->pc) { \
640 case __LINE__: (void)0
642 #define SAVE_AND_DO(do_statement) \
644 it->pc = __LINE__ - pc0; \
646 case __LINE__: (void)0; \
650 SAVE_AND_DO(return (rv))
653 SAVE_AND_DO(break); \
662 if (it->flags & TIMEOUTS_EXPIRED) {
663 if (it->flags & TIMEOUTS_CLEAR) {
664 while ((to = timeouts_get(
T))) {
668 TOR_TAILQ_FOREACH_SAFE(to, &
T->expired, tqe, it->to) {
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) {
700 TIMEOUT_PUBLIC
struct timeout *timeout_init(
struct timeout *to,
int flags) {
701 memset(to, 0,
sizeof *to);
709 #ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS
710 TIMEOUT_PUBLIC
bool timeout_pending(
struct timeout *to) {
711 return to->pending && to->pending != &to->timeouts->expired;
715 TIMEOUT_PUBLIC
bool timeout_expired(
struct timeout *to) {
716 return to->pending && to->pending == &to->timeouts->expired;
720 TIMEOUT_PUBLIC
void timeout_del(
struct timeout *to) {
721 timeouts_del(to->timeouts, to);
731 TIMEOUT_PUBLIC
int timeout_version(
void) {
732 return TIMEOUT_VERSION;
736 TIMEOUT_PUBLIC
const char *timeout_vendor(
void) {
737 return TIMEOUT_VENDOR;
741 TIMEOUT_PUBLIC
int timeout_v_rel(
void) {
742 return TIMEOUT_V_REL;
746 TIMEOUT_PUBLIC
int timeout_v_abi(
void) {
747 return TIMEOUT_V_ABI;
751 TIMEOUT_PUBLIC
int timeout_v_api(
void) {
752 return TIMEOUT_V_API;