diff options
Diffstat (limited to 'deps/timeout')
| -rw-r--r-- | deps/timeout/Makefile | 68 | ||||
| -rw-r--r-- | deps/timeout/test-timeout.c | 530 | ||||
| -rw-r--r-- | deps/timeout/timeout-bitops.c | 249 | ||||
| -rw-r--r-- | deps/timeout/timeout-debug.h | 77 | ||||
| -rw-r--r-- | deps/timeout/timeout.c | 749 | ||||
| -rw-r--r-- | deps/timeout/timeout.h | 256 |
6 files changed, 1929 insertions, 0 deletions
diff --git a/deps/timeout/Makefile b/deps/timeout/Makefile new file mode 100644 index 0000000..554ebb9 --- /dev/null +++ b/deps/timeout/Makefile @@ -0,0 +1,68 @@ +# NOTE: GNU Make 3.81 won't export MAKEFLAGS if .POSIX is specified, but +# Solaris make won't export MAKEFLAGS unless .POSIX is specified. +$(firstword ignore).POSIX: + +.DEFAULT_GOAL = all + +.SUFFIXES: + +all: + +# +# USER-MODIFIABLE MACROS +# +top_srcdir = . +top_builddir = . + +CFLAGS = -O2 -march=native -g -Wall -Wextra -Wno-unused-parameter -Wno-unused-function +SOFLAGS = $$(auto_soflags) +LIBS = $$(auto_libs) + +ALL_CPPFLAGS = -I$(top_srcdir) -DWHEEL_BIT=$(WHEEL_BIT) -DWHEEL_NUM=$(WHEEL_NUM) $(CPPFLAGS) +ALL_CFLAGS = $(CFLAGS) +ALL_SOFLAGS = $(SOFLAGS) +ALL_LDFLAGS = $(LDFLAGS) +ALL_LIBS = $(LIBS) + +LUA_API = 5.3 +LUA = lua +LUA51_CPPFLAGS = $(LUA_CPPFLAGS) +LUA52_CPPFLAGS = $(LUA_CPPFLAGS) +LUA53_CPPFLAGS = $(LUA_CPPFLAGS) + +WHEEL_BIT = 6 +WHEEL_NUM = 4 + +RM = rm -f + +# END MACROS + +SHRC = \ + top_srcdir="$(top_srcdir)"; \ + top_builddir="$(top_builddir)"; \ + . "$${top_srcdir}/Rules.shrc" + +LUA_APIS = 5.1 5.2 5.3 + +include $(top_srcdir)/lua/Rules.mk +include $(top_srcdir)/bench/Rules.mk + +all: test-timeout + +timeout.o: $(top_srcdir)/timeout.c +test-timeout.o: $(top_srcdir)/test-timeout.c + +timeout.o test-timeout.o: + @$(SHRC); echo_cmd $(CC) $(ALL_CFLAGS) -c -o $@ $${top_srcdir}/$(@F:%.o=%.c) $(ALL_CPPFLAGS) + +test-timeout: timeout.o test-timeout.o + @$(SHRC); echo_cmd $(CC) $(ALL_CPPFLAGS) $(ALL_CFLAGS) -o $@ timeout.o test-timeout.o + +.PHONY: clean clean~ + +clean: + $(RM) $(top_builddir)/test-timeout $(top_builddir)/*.o + $(RM) -r $(top_builddir)/*.dSYM + +clean~: + find $(top_builddir) $(top_srcdir) -name "*~" -exec $(RM) -- {} "+" diff --git a/deps/timeout/test-timeout.c b/deps/timeout/test-timeout.c new file mode 100644 index 0000000..ab9f72d --- /dev/null +++ b/deps/timeout/test-timeout.c @@ -0,0 +1,530 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> +#include <limits.h> + +#include "timeout.h" + +#define THE_END_OF_TIME ((timeout_t)-1) + +static int check_misc(void) { + if (TIMEOUT_VERSION != timeout_version()) + return 1; + if (TIMEOUT_V_REL != timeout_v_rel()) + return 1; + if (TIMEOUT_V_API != timeout_v_api()) + return 1; + if (TIMEOUT_V_ABI != timeout_v_abi()) + return 1; + if (strcmp(timeout_vendor(), TIMEOUT_VENDOR)) + return 1; + return 0; +} + +static int check_open_close(timeout_t hz_set, timeout_t hz_expect) { + int err=0; + struct timeouts *tos = timeouts_open(hz_set, &err); + if (!tos) + return 1; + if (err) + return 1; + if (hz_expect != timeouts_hz(tos)) + return 1; + timeouts_close(tos); + return 0; +} + +/* Not very random */ +static timeout_t random_to(timeout_t min, timeout_t max) +{ + if (max <= min) + return min; + /* Not actually all that random, but should exercise the code. */ + timeout_t rand64 = random() * (timeout_t)INT_MAX + random(); + return min + (rand64 % (max-min)); +} + +/* configuration for check_randomized */ +struct rand_cfg { + /* When creating timeouts, smallest possible delay */ + timeout_t min_timeout; + /* When creating timeouts, largest possible delay */ + timeout_t max_timeout; + /* First time to start the clock at. */ + timeout_t start_at; + /* Do not advance the clock past this time. */ + timeout_t end_at; + /* Number of timeouts to create and monitor. */ + int n_timeouts; + /* Advance the clock by no more than this each step. */ + timeout_t max_step; + /* Use relative timers and stepping */ + int relative; + /* Every time the clock ticks, try removing this many timeouts at + * random. */ + int try_removing; + /* When we're done, advance the clock to the end of time. */ + int finalize; +}; + +static int check_randomized(const struct rand_cfg *cfg) +{ +#define FAIL() do { \ + printf("Failure on line %d\n", __LINE__); \ + goto done; \ + } while (0) + + int i, err; + int rv = 1; + struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout)); + timeout_t *timeouts = calloc(cfg->n_timeouts, sizeof(timeout_t)); + uint8_t *fired = calloc(cfg->n_timeouts, sizeof(uint8_t)); + uint8_t *found = calloc(cfg->n_timeouts, sizeof(uint8_t)); + uint8_t *deleted = calloc(cfg->n_timeouts, sizeof(uint8_t)); + struct timeouts *tos = timeouts_open(0, &err); + timeout_t now = cfg->start_at; + int n_added_pending = 0, cnt_added_pending = 0; + int n_added_expired = 0, cnt_added_expired = 0; + struct timeouts_it it_p, it_e, it_all; + int p_done = 0, e_done = 0, all_done = 0; + struct timeout *to = NULL; + const int rel = cfg->relative; + + if (!t || !timeouts || !tos || !fired || !found || !deleted) + FAIL(); + timeouts_update(tos, cfg->start_at); + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (&t[i] != timeout_init(&t[i], rel ? 0 : TIMEOUT_ABS)) + FAIL(); + if (timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + + timeouts[i] = random_to(cfg->min_timeout, cfg->max_timeout); + + timeouts_add(tos, &t[i], timeouts[i] - (rel ? now : 0)); + if (timeouts[i] <= cfg->start_at) { + if (timeout_pending(&t[i])) + FAIL(); + if (! timeout_expired(&t[i])) + FAIL(); + ++n_added_expired; + } else { + if (! timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + ++n_added_pending; + } + } + + if (!!n_added_pending != timeouts_pending(tos)) + FAIL(); + if (!!n_added_expired != timeouts_expired(tos)) + FAIL(); + + /* Test foreach, interleaving a few iterators. */ + TIMEOUTS_IT_INIT(&it_p, TIMEOUTS_PENDING); + TIMEOUTS_IT_INIT(&it_e, TIMEOUTS_EXPIRED); + TIMEOUTS_IT_INIT(&it_all, TIMEOUTS_ALL); + while (! (p_done && e_done && all_done)) { + if (!p_done) { + to = timeouts_next(tos, &it_p); + if (to) { + i = to - &t[0]; + ++found[i]; + ++cnt_added_pending; + } else { + p_done = 1; + } + } + if (!e_done) { + to = timeouts_next(tos, &it_e); + if (to) { + i = to - &t[0]; + ++found[i]; + ++cnt_added_expired; + } else { + e_done = 1; + } + } + if (!all_done) { + to = timeouts_next(tos, &it_all); + if (to) { + i = to - &t[0]; + ++found[i]; + } else { + all_done = 1; + } + } + } + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (found[i] != 2) + FAIL(); + } + if (cnt_added_expired != n_added_expired) + FAIL(); + if (cnt_added_pending != n_added_pending) + FAIL(); + + while (NULL != (to = timeouts_get(tos))) { + i = to - &t[0]; + assert(&t[i] == to); + if (timeouts[i] > cfg->start_at) + FAIL(); /* shouldn't have happened yet */ + + --n_added_expired; /* drop expired timeouts. */ + ++fired[i]; + } + + if (n_added_expired != 0) + FAIL(); + + while (now < cfg->end_at) { + int n_fired_this_time = 0; + timeout_t first_at = timeouts_timeout(tos) + now; + + timeout_t oldtime = now; + timeout_t step = random_to(1, cfg->max_step); + int another; + now += step; + if (rel) + timeouts_step(tos, step); + else + timeouts_update(tos, now); + + for (i = 0; i < cfg->try_removing; ++i) { + int idx = random() % cfg->n_timeouts; + if (! fired[idx]) { + timeout_del(&t[idx]); + ++deleted[idx]; + } + } + + another = (timeouts_timeout(tos) == 0); + + while (NULL != (to = timeouts_get(tos))) { + if (! another) + FAIL(); /* Thought we saw the last one! */ + i = to - &t[0]; + assert(&t[i] == to); + if (timeouts[i] > now) + FAIL(); /* shouldn't have happened yet */ + if (timeouts[i] <= oldtime) + FAIL(); /* should have happened already */ + if (timeouts[i] < first_at) + FAIL(); /* first_at should've been earlier */ + fired[i]++; + n_fired_this_time++; + another = (timeouts_timeout(tos) == 0); + } + if (n_fired_this_time && first_at > now) + FAIL(); /* first_at should've been earlier */ + if (another) + FAIL(); /* Huh? We think there are more? */ + if (!timeouts_check(tos, stderr)) + FAIL(); + } + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (fired[i] > 1) + FAIL(); /* Nothing fired twice. */ + if (timeouts[i] <= now) { + if (!(fired[i] || deleted[i])) + FAIL(); + } else { + if (fired[i]) + FAIL(); + } + if (fired[i] && deleted[i]) + FAIL(); + if (cfg->finalize > 1) { + if (!fired[i]) + timeout_del(&t[i]); + } + } + + /* Now nothing more should fire between now and the end of time. */ + if (cfg->finalize) { + timeouts_update(tos, THE_END_OF_TIME); + if (cfg->finalize > 1) { + if (timeouts_get(tos)) + FAIL(); + TIMEOUTS_FOREACH(to, tos, TIMEOUTS_ALL) + FAIL(); + } + } + rv = 0; + + done: + if (tos) timeouts_close(tos); + if (t) free(t); + if (timeouts) free(timeouts); + if (fired) free(fired); + if (found) free(found); + if (deleted) free(deleted); + return rv; +} + +struct intervals_cfg { + const timeout_t *timeouts; + int n_timeouts; + timeout_t start_at; + timeout_t end_at; + timeout_t skip; +}; + +int +check_intervals(struct intervals_cfg *cfg) +{ + int i, err; + int rv = 1; + struct timeout *to; + struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout)); + unsigned *fired = calloc(cfg->n_timeouts, sizeof(unsigned)); + struct timeouts *tos = timeouts_open(0, &err); + + timeout_t now = cfg->start_at; + if (!t || !tos || !fired) + FAIL(); + + timeouts_update(tos, now); + + for (i = 0; i < cfg->n_timeouts; ++i) { + if (&t[i] != timeout_init(&t[i], TIMEOUT_INT)) + FAIL(); + if (timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + + timeouts_add(tos, &t[i], cfg->timeouts[i]); + if (! timeout_pending(&t[i])) + FAIL(); + if (timeout_expired(&t[i])) + FAIL(); + } + + while (now < cfg->end_at) { + timeout_t delay = timeouts_timeout(tos); + if (cfg->skip && delay < cfg->skip) + delay = cfg->skip; + timeouts_step(tos, delay); + now += delay; + + while (NULL != (to = timeouts_get(tos))) { + i = to - &t[0]; + assert(&t[i] == to); + fired[i]++; + if (0 != (to->expires - cfg->start_at) % cfg->timeouts[i]) + FAIL(); + if (to->expires <= now) + FAIL(); + if (to->expires > now + cfg->timeouts[i]) + FAIL(); + } + if (!timeouts_check(tos, stderr)) + FAIL(); + } + + timeout_t duration = now - cfg->start_at; + for (i = 0; i < cfg->n_timeouts; ++i) { + if (cfg->skip) { + if (fired[i] > duration / cfg->timeouts[i]) + FAIL(); + } else { + if (fired[i] != duration / cfg->timeouts[i]) + FAIL(); + } + if (!timeout_pending(&t[i])) + FAIL(); + } + + rv = 0; + done: + if (t) free(t); + if (fired) free(fired); + if (tos) free(tos); + return rv; +} + +int +main(int argc, char **argv) +{ + int j; + int n_failed = 0; +#define DO(fn) do { \ + printf("."); fflush(stdout); \ + if (fn) { \ + ++n_failed; \ + printf("%s failed\n", #fn); \ + } \ + } while (0) + +#define DO_N(n, fn) do { \ + for (j = 0; j < (n); ++j) { \ + DO(fn); \ + } \ + } while (0) + + DO(check_misc()); + DO(check_open_close(1000, 1000)); + DO(check_open_close(0, TIMEOUT_mHZ)); + + struct rand_cfg cfg1 = { + .min_timeout = 1, + .max_timeout = 100, + .start_at = 5, + .end_at = 1000, + .n_timeouts = 1000, + .max_step = 10, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(300,check_randomized(&cfg1)); + + struct rand_cfg cfg2 = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 2, + }; + DO_N(300,check_randomized(&cfg2)); + + struct rand_cfg cfg2b = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 1, + }; + DO_N(300,check_randomized(&cfg2b)); + + struct rand_cfg cfg2c = { + .min_timeout = 20, + .max_timeout = 1000, + .start_at = 10, + .end_at = 100, + .n_timeouts = 1000, + .max_step = 5, + .relative = 1, + .try_removing = 0, + .finalize = 0, + }; + DO_N(300,check_randomized(&cfg2c)); + + struct rand_cfg cfg3 = { + .min_timeout = 2000, + .max_timeout = ((uint64_t)1) << 50, + .start_at = 100, + .end_at = ((uint64_t)1) << 49, + .n_timeouts = 1000, + .max_step = ((uint64_t)1) << 31, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg3)); + + struct rand_cfg cfg3b = { + .min_timeout = ((uint64_t)1) << 50, + .max_timeout = ((uint64_t)1) << 52, + .start_at = 100, + .end_at = ((uint64_t)1) << 53, + .n_timeouts = 1000, + .max_step = ((uint64_t)1)<<48, + .relative = 0, + .try_removing = 0, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg3b)); + + struct rand_cfg cfg4 = { + .min_timeout = 2000, + .max_timeout = ((uint64_t)1) << 30, + .start_at = 100, + .end_at = ((uint64_t)1) << 26, + .n_timeouts = 10000, + .max_step = 1<<16, + .relative = 0, + .try_removing = 3, + .finalize = 2, + }; + DO_N(10,check_randomized(&cfg4)); + + const timeout_t primes[] = { + 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53, + 59,61,67,71,73,79,83,89,97 + }; + const timeout_t factors_of_1337[] = { + 1, 7, 191, 1337 + }; + const timeout_t multiples_of_five[] = { + 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 + }; + + struct intervals_cfg icfg1 = { + .timeouts = primes, + .n_timeouts = sizeof(primes)/sizeof(timeout_t), + .start_at = 50, + .end_at = 5322, + .skip = 0, + }; + DO(check_intervals(&icfg1)); + + struct intervals_cfg icfg2 = { + .timeouts = factors_of_1337, + .n_timeouts = sizeof(factors_of_1337)/sizeof(timeout_t), + .start_at = 50, + .end_at = 50000, + .skip = 0, + }; + DO(check_intervals(&icfg2)); + + struct intervals_cfg icfg3 = { + .timeouts = multiples_of_five, + .n_timeouts = sizeof(multiples_of_five)/sizeof(timeout_t), + .start_at = 49, + .end_at = 5333, + .skip = 0, + }; + DO(check_intervals(&icfg3)); + + struct intervals_cfg icfg4 = { + .timeouts = primes, + .n_timeouts = sizeof(primes)/sizeof(timeout_t), + .start_at = 50, + .end_at = 5322, + .skip = 16, + }; + DO(check_intervals(&icfg4)); + + if (n_failed) { + puts("\nFAIL"); + } else { + puts("\nOK"); + } + return !!n_failed; +} + +/* TODO: + + * Solve PR#3. + + * Investigate whether any untaken branches are possible. + + */ diff --git a/deps/timeout/timeout-bitops.c b/deps/timeout/timeout-bitops.c new file mode 100644 index 0000000..d8325db --- /dev/null +++ b/deps/timeout/timeout-bitops.c @@ -0,0 +1,249 @@ +#include <stdint.h> +#ifdef _MSC_VER +#include <intrin.h> /* _BitScanForward, _BitScanReverse */ +#endif + +/* First define ctz and clz functions; these are compiler-dependent if + * you want them to be fast. */ +#if defined(__GNUC__) && !defined(TIMEOUT_DISABLE_GNUC_BITOPS) + +/* On GCC and clang and some others, we can use __builtin functions. They + * are not defined for n==0, but timeout.s never calls them with n==0. */ + +#define ctz64(n) __builtin_ctzll(n) +#define clz64(n) __builtin_clzll(n) +#if LONG_BITS == 32 +#define ctz32(n) __builtin_ctzl(n) +#define clz32(n) __builtin_clzl(n) +#else +#define ctz32(n) __builtin_ctz(n) +#define clz32(n) __builtin_clz(n) +#endif + +#elif defined(_MSC_VER) && !defined(TIMEOUT_DISABLE_MSVC_BITOPS) + +/* On MSVC, we have these handy functions. We can ignore their return + * values, since we will never supply val == 0. */ + +static __inline int ctz32(unsigned long val) +{ + DWORD zeros = 0; + _BitScanForward(&zeros, val); + return zeros; +} +static __inline int clz32(unsigned long val) +{ + DWORD zeros = 0; + _BitScanReverse(&zeros, val); + return zeros; +} +#ifdef _WIN64 +/* According to the documentation, these only exist on Win64. */ +static __inline int ctz64(uint64_t val) +{ + DWORD zeros = 0; + _BitScanForward64(&zeros, val); + return zeros; +} +static __inline int clz64(uint64_t val) +{ + DWORD zeros = 0; + _BitScanReverse64(&zeros, val); + return zeros; +} +#else +static __inline int ctz64(uint64_t val) +{ + uint32_t lo = (uint32_t) val; + uint32_t hi = (uint32_t) (val >> 32); + return lo ? ctz32(lo) : 32 + ctz32(hi); +} +static __inline int clz64(uint64_t val) +{ + uint32_t lo = (uint32_t) val; + uint32_t hi = (uint32_t) (val >> 32); + return hi ? clz32(hi) : 32 + clz32(lo); +} +#endif + +/* End of MSVC case. */ + +#else + +/* TODO: There are more clever ways to do this in the generic case. */ + + +#define process_(one, cz_bits, bits) \ + if (x < ( one << (cz_bits - bits))) { rv += bits; x <<= bits; } + +#define process64(bits) process_((UINT64_C(1)), 64, (bits)) +static inline int clz64(uint64_t x) +{ + int rv = 0; + + process64(32); + process64(16); + process64(8); + process64(4); + process64(2); + process64(1); + return rv; +} +#define process32(bits) process_((UINT32_C(1)), 32, (bits)) +static inline int clz32(uint32_t x) +{ + int rv = 0; + + process32(16); + process32(8); + process32(4); + process32(2); + process32(1); + return rv; +} + +#undef process_ +#undef process32 +#undef process64 +#define process_(one, bits) \ + if ((x & ((one << (bits))-1)) == 0) { rv += bits; x >>= bits; } + +#define process64(bits) process_((UINT64_C(1)), bits) +static inline int ctz64(uint64_t x) +{ + int rv = 0; + + process64(32); + process64(16); + process64(8); + process64(4); + process64(2); + process64(1); + return rv; +} + +#define process32(bits) process_((UINT32_C(1)), bits) +static inline int ctz32(uint32_t x) +{ + int rv = 0; + + process32(16); + process32(8); + process32(4); + process32(2); + process32(1); + return rv; +} + +#undef process32 +#undef process64 +#undef process_ + +/* End of generic case */ + +#endif /* End of defining ctz */ + +#ifdef TEST_BITOPS +#include <stdio.h> +#include <stdlib.h> + +static uint64_t testcases[] = { + 13371337 * 10, + 100, + 385789752, + 82574, + (((uint64_t)1)<<63) + (((uint64_t)1)<<31) + 10101 +}; + +static int +naive_clz(int bits, uint64_t v) +{ + int r = 0; + uint64_t bit = ((uint64_t)1) << (bits-1); + while (bit && 0 == (v & bit)) { + r++; + bit >>= 1; + } + /* printf("clz(%d,%lx) -> %d\n", bits, v, r); */ + return r; +} + +static int +naive_ctz(int bits, uint64_t v) +{ + int r = 0; + uint64_t bit = 1; + while (bit && 0 == (v & bit)) { + r++; + bit <<= 1; + if (r == bits) + break; + } + /* printf("ctz(%d,%lx) -> %d\n", bits, v, r); */ + return r; +} + +static int +check(uint64_t vv) +{ + uint32_t v32 = (uint32_t) vv; + + if (vv == 0) + return 1; /* c[tl]z64(0) is undefined. */ + + if (ctz64(vv) != naive_ctz(64, vv)) { + printf("mismatch with ctz64: %d\n", ctz64(vv)); + exit(1); + return 0; + } + if (clz64(vv) != naive_clz(64, vv)) { + printf("mismatch with clz64: %d\n", clz64(vv)); + exit(1); + return 0; + } + + if (v32 == 0) + return 1; /* c[lt]z(0) is undefined. */ + + if (ctz32(v32) != naive_ctz(32, v32)) { + printf("mismatch with ctz32: %d\n", ctz32(v32)); + exit(1); + return 0; + } + if (clz32(v32) != naive_clz(32, v32)) { + printf("mismatch with clz32: %d\n", clz32(v32)); + exit(1); + return 0; + } + return 1; +} + +int +main(int c, char **v) +{ + unsigned int i; + const unsigned int n = sizeof(testcases)/sizeof(testcases[0]); + int result = 0; + + for (i = 0; i <= 63; ++i) { + uint64_t x = 1 << i; + if (!check(x)) + result = 1; + --x; + if (!check(x)) + result = 1; + } + + for (i = 0; i < n; ++i) { + if (! check(testcases[i])) + result = 1; + } + if (result) { + puts("FAIL"); + } else { + puts("OK"); + } + return result; +} +#endif + diff --git a/deps/timeout/timeout-debug.h b/deps/timeout/timeout-debug.h new file mode 100644 index 0000000..fc727a6 --- /dev/null +++ b/deps/timeout/timeout-debug.h @@ -0,0 +1,77 @@ +/* + * D E B U G R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if TIMEOUT_DEBUG - 0 +#include <stdlib.h> +#include <stdio.h> + +#undef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 1 +#define DEBUG_LEVEL timeout_debug + +static int timeout_debug; + +#define SAYit_(lvl, fmt, ...) do { \ + if (DEBUG_LEVEL >= (lvl)) \ + fprintf(stderr, fmt "%s", __FILE__, __LINE__, __func__, __VA_ARGS__); \ +} while (0) + +#define SAYit(lvl, ...) SAYit_((lvl), "%s:%d:%s: " __VA_ARGS__, "\n") + +#define PANIC(...) do { \ + SAYit(0, __VA_ARGS__); \ + _Exit(EXIT_FAILURE); \ +} while (0) +#else +#undef TIMEOUT_DEBUG +#define TIMEOUT_DEBUG 0 +#define DEBUG_LEVEL 0 + +#define SAYit(...) (void)0 +#endif + +#define SAY(...) SAYit(1, __VA_ARGS__) +#define HAI SAY("HAI") + + +static inline char *fmt_(char *buf, uint64_t ts, int wheel_bit, int wheel_num) { + char *p = buf; + int wheel, n, i; + + for (wheel = wheel_num - 2; wheel >= 0; wheel--) { + n = ((1 << wheel_bit) - 1) & (ts >> (wheel * WHEEL_BIT)); + + for (i = wheel_bit - 1; i >= 0; i--) { + *p++ = '0' + !!(n & (1 << i)); + } + + if (wheel != 0) + *p++ = ':'; + } + + *p = 0; + + return buf; +} /* fmt_() */ + +#define fmt(ts) fmt_(((char[((1 << WHEEL_BIT) * WHEEL_NUM) + WHEEL_NUM + 1]){ 0 }), (ts), WHEEL_BIT, WHEEL_NUM) + + +static inline char *bin64_(char *buf, uint64_t n, int wheel_bit) { + char *p = buf; + int i; + + for (i = 0; i < (1 << wheel_bit); i++) { + *p++ = "01"[0x1 & (n >> (((1 << wheel_bit) - 1) - i))]; + } + + *p = 0; + + return buf; +} /* bin64_() */ + +#define bin64(ts) bin64_(((char[((1 << WHEEL_BIT) * WHEEL_NUM) + 1]){ 0 }), (ts), WHEEL_BIT) + + diff --git a/deps/timeout/timeout.c b/deps/timeout/timeout.c new file mode 100644 index 0000000..aac21a0 --- /dev/null +++ b/deps/timeout/timeout.c @@ -0,0 +1,749 @@ +/* ========================================================================== + * timeout.c - Tickless hierarchical timing wheel. + * -------------------------------------------------------------------------- + * Copyright (c) 2013, 2014 William Ahern + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * ========================================================================== + */ +#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 <sys/queue.h> /* TAILQ(3) */ + +#include "timeout.h" + +#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 + +/* + * A N C I L L A R Y R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#define abstime_t timeout_t /* for documentation purposes */ +#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 TAILQ_CONCAT +#define TAILQ_CONCAT(head1, head2, field) do { \ + if (!TAILQ_EMPTY(head2)) { \ + *(head1)->tqh_last = (head2)->tqh_first; \ + (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ + (head1)->tqh_last = (head2)->tqh_last; \ + TAILQ_INIT((head2)); \ + } \ +} while (0) +#endif + +#if !defined TAILQ_FOREACH_SAFE +#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \ + for ((var) = TAILQ_FIRST(head); \ + (var) && ((tvar) = TAILQ_NEXT(var, field), 1); \ + (var) = (tvar)) +#endif + + +/* + * B I T M A N I P U L A T I O N R O U T I N E S + * + * The macros and routines below implement wheel parameterization. The + * inputs are: + * + * WHEEL_BIT - The number of value bits mapped in each wheel. The + * lowest-order WHEEL_BIT bits index the lowest-order (highest + * resolution) wheel, the next group of WHEEL_BIT bits the + * higher wheel, etc. + * + * WHEEL_NUM - The number of wheels. WHEEL_BIT * WHEEL_NUM = the number of + * value bits used by all the wheels. For the default of 6 and + * 4, only the low 24 bits are processed. Any timeout value + * larger than this will cycle through again. + * + * The implementation uses bit fields to remember which slot in each wheel + * is populated, and to generate masks of expiring slots according to the + * current update interval (i.e. the "tickless" aspect). The slots to + * process in a wheel are (populated-set & interval-mask). + * + * WHEEL_BIT cannot be larger than 6 bits because 2^6 -> 64 is the largest + * number of slots which can be tracked in a uint64_t integer bit field. + * WHEEL_BIT cannot be smaller than 3 bits because of our rotr and rotl + * routines, which only operate on all the value bits in an integer, and + * there's no integer smaller than uint8_t. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#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)); +} /* rotl() */ + + +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)); +} /* rotr() */ + + +/* + * T I M E R R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +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; + long long count; +}; /* struct timeouts */ + + +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++) { + TAILQ_INIT(&T->wheel[i][j]); + } + } + + 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; + T->count =0; + return T; +} /* timeouts_init() */ +long long timeouts_count(struct timeouts *T) +{ + return T->count; +} +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; +} /* timeouts_open() */ + + +static void timeouts_reset(struct timeouts *T) { + struct timeout_list reset; + struct timeout *to; + unsigned i, j; + + TAILQ_INIT(&reset); + + for (i = 0; i < countof(T->wheel); i++) { + for (j = 0; j < countof(T->wheel[i]); j++) { + TAILQ_CONCAT(&reset, &T->wheel[i][j], tqe); + } + } + + TAILQ_CONCAT(&reset, &T->expired, tqe); + + TAILQ_FOREACH(to, &reset, tqe) { + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + } + T->count=0; +} /* timeouts_reset() */ + + +TIMEOUT_PUBLIC void timeouts_close(struct timeouts *T) { + /* + * NOTE: Delete installed timeouts so timeout_pending() and + * timeout_expired() worked as expected. + */ + timeouts_reset(T); + + free(T); +} /* timeouts_close() */ + + +TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *T) { + return T->hertz; +} /* timeouts_hz() */ + + +TIMEOUT_PUBLIC void timeouts_del(struct timeouts *T, struct timeout *to) { + if (to->pending) { + TAILQ_REMOVE(to->pending, to, tqe); + + if (to->pending != &T->expired && TAILQ_EMPTY(to->pending)) { + ptrdiff_t index = to->pending - &T->wheel[0][0]; + int wheel = index / WHEEL_LEN; + int slot = index % WHEEL_LEN; + + T->pending[wheel] &= ~(WHEEL_C(1) << slot); + } + + to->pending = NULL; + TO_SET_TIMEOUTS(to, NULL); + T->count--; + } +} /* timeouts_del() */ + + +static inline reltime_t timeout_rem(struct timeouts *T, struct timeout *to) { + return to->expires - T->curtime; +} /* timeout_rem() */ + + +static inline int timeout_wheel(timeout_t timeout) { + /* must be called with timeout != 0, so fls input is nonzero */ + return (fls(MIN(timeout, TIMEOUT_MAX)) - 1) / WHEEL_BIT; +} /* timeout_wheel() */ + + +static inline int timeout_slot(int wheel, timeout_t expires) { + return WHEEL_MASK & ((expires >> (wheel * WHEEL_BIT)) - !!wheel); +} /* timeout_slot() */ + + +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); + + /* rem is nonzero since: + * rem == timeout_rem(T,to), + * == to->expires - T->curtime + * and above we have expires > T->curtime. + */ + wheel = timeout_wheel(rem); + slot = timeout_slot(wheel, to->expires); + + to->pending = &T->wheel[wheel][slot]; + TAILQ_INSERT_TAIL(to->pending, to, tqe); + + T->pending[wheel] |= WHEEL_C(1) << slot; + } else { + to->pending = &T->expired; + TAILQ_INSERT_TAIL(to->pending, to, tqe); + } +} /* timeouts_sched() */ + + +#ifndef TIMEOUT_DISABLE_INTERVALS +static void timeouts_readd(struct timeouts *T, struct timeout *to) { + to->expires += to->interval; + + if (to->expires <= T->curtime) { + /* If we've missed the next firing of this timeout, reschedule + * it to occur at the next multiple of its interval after + * the last time that it fired. + */ + 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); +} /* timeouts_readd() */ +#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 + T->count++; + if (to->flags & TIMEOUT_ABS) + timeouts_sched(T, to, timeout); + else + timeouts_sched(T, to, T->curtime + timeout); +} /* timeouts_add() */ + + +TIMEOUT_PUBLIC void timeouts_update(struct timeouts *T, abstime_t curtime) { + timeout_t elapsed = curtime - T->curtime; + struct timeout_list todo; + int wheel; + + TAILQ_INIT(&todo); + + /* + * There's no avoiding looping over every wheel. It's best to keep + * WHEEL_NUM smallish. + */ + for (wheel = 0; wheel < WHEEL_NUM; wheel++) { + wheel_t pending; + + /* + * Calculate the slots expiring in this wheel + * + * If the elapsed time is greater than the maximum period of + * the wheel, mark every position as expiring. + * + * Otherwise, to determine the expired slots fill in all the + * bits between the last slot processed and the current + * slot, inclusive of the last slot. We'll bitwise-AND this + * with our pending set below. + * + * If a wheel rolls over, force a tick of the next higher + * wheel. + */ + 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; + + /* + * TODO: It's likely that at least one of the + * following three bit fill operations is redundant + * or can be replaced with a simpler operation. + */ + 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), _elapsed); + pending |= WHEEL_C(1) << nslot; + } + + while (pending & T->pending[wheel]) { + /* ctz input cannot be zero: loop condition. */ + int slot = ctz(pending & T->pending[wheel]); + TAILQ_CONCAT(&todo, &T->wheel[wheel][slot], tqe); + T->pending[wheel] &= ~(UINT64_C(1) << slot); + } + + if (!(0x1 & pending)) + break; /* break if we didn't wrap around end of wheel */ + + /* if we're continuing, the next wheel must tick at least once */ + elapsed = MAX(elapsed, (WHEEL_LEN << (wheel * WHEEL_BIT))); + } + + T->curtime = curtime; + + while (!TAILQ_EMPTY(&todo)) { + struct timeout *to = TAILQ_FIRST(&todo); + + TAILQ_REMOVE(&todo, to, tqe); + to->pending = NULL; + + timeouts_sched(T, to, to->expires); + } + + return; +} /* timeouts_update() */ + + +TIMEOUT_PUBLIC void timeouts_step(struct timeouts *T, reltime_t elapsed) { + timeouts_update(T, T->curtime + elapsed); +} /* timeouts_step() */ + + +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; +} /* timeouts_pending() */ + + +TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *T) { + return !TAILQ_EMPTY(&T->expired); +} /* timeouts_expired() */ + + +/* + * Calculate the interval before needing to process any timeouts pending on + * any wheel. + * + * (This is separated from the public API routine so we can evaluate our + * wheel invariant assertions irrespective of the expired queue.) + * + * This might return a timeout value sooner than any installed timeout if + * only higher-order wheels have timeouts pending. We can only know when to + * process a wheel, not precisely when a timeout is scheduled. Our timeout + * accuracy could be off by 2^(N*M)-1 units where N is the wheel number and + * M is WHEEL_BIT. Only timeouts which have fallen through to wheel 0 can be + * known exactly. + * + * We should never return a timeout larger than the lowest actual timeout. + */ +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)); + + /* ctz input cannot be zero: T->pending[wheel] is + * nonzero, so rotr() is nonzero. */ + _timeout = (ctz(rotr(T->pending[wheel], slot)) + !!wheel) << (wheel * WHEEL_BIT); + /* +1 to higher order wheels as those timeouts are one rotation in the future (otherwise they'd be on a lower wheel or expired) */ + + _timeout -= relmask & T->curtime; + /* reduce by how much lower wheels have progressed */ + + timeout = MIN(_timeout, timeout); + } + + relmask <<= WHEEL_BIT; + relmask |= WHEEL_MASK; + } + + return timeout; +} /* timeouts_int() */ + + +/* + * Calculate the interval our caller can wait before needing to process + * events. + */ +TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *T) { + if (!TAILQ_EMPTY(&T->expired)) + return 0; + + return timeouts_int(T); +} /* timeouts_timeout() */ + + +TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *T) { + if (!TAILQ_EMPTY(&T->expired)) { + struct timeout *to = TAILQ_FIRST(&T->expired); + + 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 + T->count--; + return to; + } else { + return 0; + } +} /* timeouts_get() */ + + +/* + * Use dumb looping to locate the earliest timeout pending on the wheel so + * our invariant assertions can check the result of our optimized code. + */ +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++) { + TAILQ_FOREACH(to, &T->wheel[i][j], tqe) { + if (!min || to->expires < min->expires) + min = to; + } + } + } + + return min; +} /* timeouts_min() */ + + +/* + * Check some basic algorithm invariants. If these invariants fail then + * something is definitely broken. + */ +#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 (!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; +} /* timeouts_check() */ + + +#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 { + 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++) { + TAILQ_FOREACH_SAFE(to, &T->wheel[it->i][it->j], tqe, it->to) { + YIELD(to); + } + } + } + } + + LEAVE; + + return NULL; +} /* timeouts_next */ + +#undef LEAVE +#undef YIELD +#undef SAVE_AND_DO +#undef ENTER + + +/* + * T I M E O U T R O U T I N E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *to, int flags) { + memset(to, 0, sizeof *to); + + to->flags = flags; + + return to; +} /* timeout_init() */ + + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS +TIMEOUT_PUBLIC bool timeout_pending(struct timeout *to) { + return to->pending && to->pending != &to->timeouts->expired; +} /* timeout_pending() */ + + +TIMEOUT_PUBLIC bool timeout_expired(struct timeout *to) { + return to->pending && to->pending == &to->timeouts->expired; +} /* timeout_expired() */ + + +TIMEOUT_PUBLIC void timeout_del(struct timeout *to) { + timeouts_del(to->timeouts, to); +} /* timeout_del() */ +#endif + + +/* + * V E R S I O N I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +TIMEOUT_PUBLIC int timeout_version(void) { + return TIMEOUT_VERSION; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC const char *timeout_vendor(void) { + return TIMEOUT_VENDOR; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_rel(void) { + return TIMEOUT_V_REL; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_abi(void) { + return TIMEOUT_V_ABI; +} /* timeout_version() */ + + +TIMEOUT_PUBLIC int timeout_v_api(void) { + return TIMEOUT_V_API; +} /* timeout_version() */ + diff --git a/deps/timeout/timeout.h b/deps/timeout/timeout.h new file mode 100644 index 0000000..b597ab5 --- /dev/null +++ b/deps/timeout/timeout.h @@ -0,0 +1,256 @@ +/* ========================================================================== + * timeout.h - Tickless hierarchical timing wheel. + * -------------------------------------------------------------------------- + * Copyright (c) 2013, 2014 William Ahern + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the + * "Software"), to deal in the Software without restriction, including + * without limitation the rights to use, copy, modify, merge, publish, + * distribute, sublicense, and/or sell copies of the Software, and to permit + * persons to whom the Software is furnished to do so, subject to the + * following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS + * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN + * NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, + * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR + * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE + * USE OR OTHER DEALINGS IN THE SOFTWARE. + * ========================================================================== + */ +#ifndef TIMEOUT_H +#define TIMEOUT_H + +#include <stdbool.h> /* bool */ +#include <stdio.h> /* FILE */ + +#include <inttypes.h> /* PRIu64 PRIx64 PRIX64 uint64_t */ + +#include <sys/queue.h> /* TAILQ(3) */ + + +/* + * V E R S I O N I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#if !defined TIMEOUT_PUBLIC +#define TIMEOUT_PUBLIC +#endif + +#define TIMEOUT_VERSION TIMEOUT_V_REL +#define TIMEOUT_VENDOR "[email protected]" + +#define TIMEOUT_V_REL 0x20160226 +#define TIMEOUT_V_ABI 0x20160224 +#define TIMEOUT_V_API 0x20160226 + +TIMEOUT_PUBLIC int timeout_version(void); + +TIMEOUT_PUBLIC const char *timeout_vendor(void); + +TIMEOUT_PUBLIC int timeout_v_rel(void); + +TIMEOUT_PUBLIC int timeout_v_abi(void); + +TIMEOUT_PUBLIC int timeout_v_api(void); + + +/* + * I N T E G E R T Y P E I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#define TIMEOUT_C(n) UINT64_C(n) +#define TIMEOUT_PRIu PRIu64 +#define TIMEOUT_PRIx PRIx64 +#define TIMEOUT_PRIX PRIX64 + +#define TIMEOUT_mHZ TIMEOUT_C(1000) +#define TIMEOUT_uHZ TIMEOUT_C(1000000) +#define TIMEOUT_nHZ TIMEOUT_C(1000000000) + +typedef uint64_t timeout_t; + +#define timeout_error_t int /* for documentation purposes */ + + +/* + * C A L L B A C K I N T E R F A C E + * + * Callback function parameters unspecified to make embedding into existing + * applications easier. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#ifndef TIMEOUT_CB_OVERRIDE +struct timeout_cb { + void (*fn)(); + void *arg; +}; /* struct timeout_cb */ +#endif + +/* + * T I M E O U T I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#ifndef TIMEOUT_DISABLE_INTERVALS +#define TIMEOUT_INT 0x01 /* interval (repeating) timeout */ +#endif +#define TIMEOUT_ABS 0x02 /* treat timeout values as absolute */ + +#define TIMEOUT_INITIALIZER(flags) { (flags) } + +#define timeout_setcb(to, fn, arg) do { \ + (to)->callback.fn = (fn); \ + (to)->callback.arg = (arg); \ +} while (0) + +struct timeout { + int flags; + + timeout_t expires; + /* absolute expiration time */ + + struct timeout_list *pending; + /* timeout list if pending on wheel or expiry queue */ + + TAILQ_ENTRY(timeout) tqe; + /* entry member for struct timeout_list lists */ + +#ifndef TIMEOUT_DISABLE_CALLBACKS + struct timeout_cb callback; + /* optional callback information */ +#endif + +#ifndef TIMEOUT_DISABLE_INTERVALS + timeout_t interval; + /* timeout interval if periodic */ +#endif + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS + struct timeouts *timeouts; + /* timeouts collection if member of */ +#endif +}; /* struct timeout */ + + +TIMEOUT_PUBLIC struct timeout *timeout_init(struct timeout *, int); +/* initialize timeout structure (same as TIMEOUT_INITIALIZER) */ + +#ifndef TIMEOUT_DISABLE_RELATIVE_ACCESS +TIMEOUT_PUBLIC bool timeout_pending(struct timeout *); +/* true if on timing wheel, false otherwise */ + +TIMEOUT_PUBLIC bool timeout_expired(struct timeout *); +/* true if on expired queue, false otherwise */ + +TIMEOUT_PUBLIC void timeout_del(struct timeout *); +/* remove timeout from any timing wheel (okay if not member of any) */ +#endif + +/* + * T I M I N G W H E E L I N T E R F A C E S + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +struct timeouts; + +TIMEOUT_PUBLIC struct timeouts *timeouts_open(timeout_t, timeout_error_t *); +/* open a new timing wheel, setting optional HZ (for float conversions) */ + +TIMEOUT_PUBLIC void timeouts_close(struct timeouts *); +/* destroy timing wheel */ + +TIMEOUT_PUBLIC long long timeouts_count(struct timeouts *); +/* count timeout of timeouts*/ + +TIMEOUT_PUBLIC timeout_t timeouts_hz(struct timeouts *); +/* return HZ setting (for float conversions) */ + +TIMEOUT_PUBLIC void timeouts_update(struct timeouts *, timeout_t); +/* update timing wheel with current absolute time */ + +TIMEOUT_PUBLIC void timeouts_step(struct timeouts *, timeout_t); +/* step timing wheel by relative time */ + +TIMEOUT_PUBLIC timeout_t timeouts_timeout(struct timeouts *); +/* return interval to next required update */ + +TIMEOUT_PUBLIC void timeouts_add(struct timeouts *, struct timeout *, timeout_t); +/* add timeout to timing wheel */ + +TIMEOUT_PUBLIC void timeouts_del(struct timeouts *, struct timeout *); +/* remove timeout from any timing wheel or expired queue (okay if on neither) */ + +TIMEOUT_PUBLIC struct timeout *timeouts_get(struct timeouts *); +/* return any expired timeout (caller should loop until NULL-return) */ + +TIMEOUT_PUBLIC bool timeouts_pending(struct timeouts *); +/* return true if any timeouts pending on timing wheel */ + +TIMEOUT_PUBLIC bool timeouts_expired(struct timeouts *); +/* return true if any timeouts on expired queue */ + +TIMEOUT_PUBLIC bool timeouts_check(struct timeouts *, FILE *); +/* return true if invariants hold. describes failures to optional file handle. */ + +#define TIMEOUTS_PENDING 0x10 +#define TIMEOUTS_EXPIRED 0x20 +#define TIMEOUTS_ALL (TIMEOUTS_PENDING|TIMEOUTS_EXPIRED) +#define TIMEOUTS_CLEAR 0x40 + +#define TIMEOUTS_IT_INITIALIZER(flags) { (flags), 0, 0, 0, 0 } + +#define TIMEOUTS_IT_INIT(cur, _flags) do { \ + (cur)->flags = (_flags); \ + (cur)->pc = 0; \ +} while (0) + +struct timeouts_it { + int flags; + unsigned pc, i, j; + struct timeout *to; +}; /* struct timeouts_it */ + +TIMEOUT_PUBLIC struct timeout *timeouts_next(struct timeouts *, struct timeouts_it *); +/* return next timeout in pending wheel or expired queue. caller can delete + * the returned timeout, but should not otherwise manipulate the timing + * wheel. in particular, caller SHOULD NOT delete any other timeout as that + * could invalidate cursor state and trigger a use-after-free. + */ + +#define TIMEOUTS_FOREACH(var, T, flags) \ + struct timeouts_it _it = TIMEOUTS_IT_INITIALIZER((flags)); \ + while (((var) = timeouts_next((T), &_it))) + + +/* + * B O N U S W H E E L I N T E R F A C E S + * + * I usually use floating point timeouts in all my code, but it's cleaner to + * separate it to keep the core algorithmic code simple. + * + * Using macros instead of static inline routines where <math.h> routines + * might be used to keep -lm linking optional. + * + * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ + +#include <math.h> /* ceil(3) */ + +#define timeouts_f2i(T, f) \ + ((timeout_t)ceil((f) * timeouts_hz((T)))) /* prefer late expiration over early */ + +#define timeouts_i2f(T, i) \ + ((double)(i) / timeouts_hz((T))) + +#define timeouts_addf(T, to, timeout) \ + timeouts_add((T), (to), timeouts_f2i((T), (timeout))) + +#endif /* TIMEOUT_H */ |