test-timeout.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
 
#include "ext/timeouts/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 = 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.
 
 */