X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Ftimer%2Ftimer.c;h=48bded19656456a500703d77d509ba750053bbda;hb=c910bdce167ff42aa6d9e4f1b8f905a76f0b9e75;hp=2c58a4e5238df00b7bd88abc8cee76feb284eab2;hpb=63f770591286a5a61ef2857377eeab5e0e75d115;p=ccan diff --git a/ccan/timer/timer.c b/ccan/timer/timer.c index 2c58a4e5..48bded19 100644 --- a/ccan/timer/timer.c +++ b/ccan/timer/timer.c @@ -2,7 +2,6 @@ #include #include #include -#include #include #include @@ -12,15 +11,39 @@ struct timer_level { struct list_head list[PER_LEVEL]; }; -static uint64_t time_to_grains(struct timeabs t) +static void *timer_default_alloc(struct timers *timers, size_t len) +{ + return malloc(len); +} + +static void timer_default_free(struct timers *timers, void *p) +{ + free(p); +} + +static void *(*timer_alloc)(struct timers *, size_t) = timer_default_alloc; +static void (*timer_free)(struct timers *, void *) = timer_default_free; + +void timers_set_allocator(void *(*alloc)(struct timers *, size_t len), + void (*free)(struct timers *, void *p)) +{ + if (!alloc) + alloc = timer_default_alloc; + if (!free) + free = timer_default_free; + timer_alloc = alloc; + timer_free = free; +} + +static uint64_t time_to_grains(struct timemono t) { return t.ts.tv_sec * ((uint64_t)1000000000 / TIMER_GRANULARITY) + (t.ts.tv_nsec / TIMER_GRANULARITY); } -static struct timeabs grains_to_time(uint64_t grains) +static struct timemono grains_to_time(uint64_t grains) { - struct timeabs t; + struct timemono t; t.ts.tv_sec = grains / (1000000000 / TIMER_GRANULARITY); t.ts.tv_nsec = (grains % (1000000000 / TIMER_GRANULARITY)) @@ -28,13 +51,14 @@ static struct timeabs grains_to_time(uint64_t grains) return t; } -void timers_init(struct timers *timers, struct timeabs start) +void timers_init(struct timers *timers, struct timemono start) { unsigned int i; list_head_init(&timers->far); timers->base = time_to_grains(start); timers->first = -1ULL; + memset(timers->firsts, 0xFF, sizeof(timers->firsts)); for (i = 0; i < ARRAY_SIZE(timers->level); i++) timers->level[i] = NULL; } @@ -52,15 +76,20 @@ static void timer_add_raw(struct timers *timers, struct timer *t) { struct list_head *l; unsigned int level = level_of(timers, t->time); + uint64_t *first; - if (!timers->level[level]) + if (!timers->level[level]) { l = &timers->far; - else { + first = &timers->firsts[ARRAY_SIZE(timers->level)]; + } else { int off = (t->time >> (level*TIMER_LEVEL_BITS)) & (PER_LEVEL-1); l = &timers->level[level]->list[off]; + first = &timers->firsts[level]; } list_add_tail(l, &t->list); + if (t->time < *first) + *first = t->time; } void timer_init(struct timer *t) @@ -68,12 +97,31 @@ void timer_init(struct timer *t) list_node_init(&t->list); } -static bool list_node_initted(const struct list_node *n) +static inline bool list_node_initted(const struct list_node *n) { return n->prev == n; } -void timer_add(struct timers *timers, struct timer *t, struct timeabs when) +void timer_addrel(struct timers *timers, struct timer *t, struct timerel rel) +{ + assert(list_node_initted(&t->list)); + + t->time = time_to_grains(timemono_add(time_mono(), rel)); + +#if TIME_HAVE_MONOTONIC + assert(t->time >= timers->base); +#else + /* Added in the past? Treat it as imminent. */ + if (t->time < timers->base) + t->time = timers->base; +#endif + if (t->time < timers->first) + timers->first = t->time; + + timer_add_raw(timers, t); +} + +void timer_addmono(struct timers *timers, struct timer *t, struct timemono when) { assert(list_node_initted(&t->list)); @@ -89,7 +137,7 @@ void timer_add(struct timers *timers, struct timer *t, struct timeabs when) } /* FIXME: inline */ -void timer_del(struct timers *timers, struct timer *t) +void timer_del(struct timers *timers UNNEEDED, struct timer *t) { list_del_init(&t->list); } @@ -115,7 +163,7 @@ static void add_level(struct timers *timers, unsigned int level) unsigned int i; struct list_head from_far; - l = malloc(sizeof(*l)); + l = timer_alloc(timers, sizeof(*l)); if (!l) return; @@ -148,37 +196,65 @@ static const struct timer *find_first(const struct list_head *list, return prev; } +/* Update level's first watermark, and return overall first. */ +static const struct timer *first_for_level(struct timers *timers, + size_t level, + const struct timer *level_first, + const struct timer *first) +{ + if (level_first) { + timers->firsts[level] = level_first->time; + if (!first || level_first->time < first->time) + first = level_first; + } else { + timers->firsts[level] = -1ULL; + } + return first; +} + +static bool level_may_beat(const struct timers *timers, size_t level, + const struct timer *first) +{ + return !first || timers->firsts[level] < first->time; +} + /* FIXME: Suboptimal */ -static const struct timer *brute_force_first(const struct timers *timers) +static const struct timer *brute_force_first(struct timers *timers) { unsigned int l, i; const struct timer *found = NULL; for (l = 0; l < ARRAY_SIZE(timers->level) && timers->level[l]; l++) { + const struct timer *t = NULL; + + /* Do we know they don't have a better one? */ + if (!level_may_beat(timers, l, found)) + continue; + + /* Find first timer on this level. */ for (i = 0; i < PER_LEVEL; i++) - found = find_first(&timers->level[l]->list[i], l, - found); + t = find_first(&timers->level[l]->list[i], l, t); + + found = first_for_level(timers, l, t, found); + } + + /* Check (and update) far list if there's a chance. */ + l = ARRAY_SIZE(timers->level); + if (level_may_beat(timers, l, found)) { + const struct timer *t = find_first(&timers->far, l, NULL); + found = first_for_level(timers, l, t, found); } - found = find_first(&timers->far, -1U, found); return found; } - -static const struct timer *get_first(const struct timers *timers) -{ - uint64_t time; - - /* Where can we start from? */ - if (timers->first < timers->base) - time = timers->base; - else - time = timers->first; +static const struct timer *get_first(struct timers *timers) +{ /* We can have just far timers, for example. */ if (timers->level[0]) { /* First search rest of lower buckets; we've already spilled * so if we find one there we don't need to search further. */ - unsigned int i, off = time % PER_LEVEL; + unsigned int i, off = timers->base % PER_LEVEL; for (i = off; i < PER_LEVEL; i++) { struct list_head *h = &timers->level[0]->list[i]; @@ -201,13 +277,13 @@ static bool update_first(struct timers *timers) if (!found) { timers->first = -1ULL; return false; - } + } timers->first = found->time; return true; } -bool timer_earliest(struct timers *timers, struct timeabs *first) +bool timer_earliest(struct timers *timers, struct timemono *first) { if (!update_first(timers)) return false; @@ -264,7 +340,7 @@ static void timer_fast_forward(struct timers *timers, uint64_t time) } /* Returns an expired timer. */ -struct timer *timers_expire(struct timers *timers, struct timeabs expire) +struct timer *timers_expire(struct timers *timers, struct timemono expire) { uint64_t now = time_to_grains(expire); unsigned int off; @@ -346,7 +422,7 @@ struct timers *timers_check(const struct timers *timers, const char *abortstr) h = &timers->level[l]->list[(i+off) % PER_LEVEL]; if (!timer_list_check(h, timers->base + i, timers->base + i, - timers->first, abortstr)) + timers->firsts[l], abortstr)) return NULL; } @@ -364,7 +440,7 @@ struct timers *timers_check(const struct timers *timers, const char *abortstr) h = &timers->level[l]->list[(i+off) % PER_LEVEL]; if (!timer_list_check(h, base, base + per_bucket - 1, - timers->first, abortstr)) + timers->firsts[l], abortstr)) return NULL; base += per_bucket; } @@ -373,7 +449,8 @@ struct timers *timers_check(const struct timers *timers, const char *abortstr) past_levels: base = (timers->base & ~((1ULL << (TIMER_LEVEL_BITS * l)) - 1)) + (1ULL << (TIMER_LEVEL_BITS * l)) - 1; - if (!timer_list_check(&timers->far, base, -1ULL, timers->first, + if (!timer_list_check(&timers->far, base, -1ULL, + timers->firsts[ARRAY_SIZE(timers->level)], abortstr)) return NULL; @@ -467,5 +544,5 @@ void timers_cleanup(struct timers *timers) unsigned int l; for (l = 0; l < ARRAY_SIZE(timers->level); l++) - free(timers->level[l]); + timer_free(timers, timers->level[l]); }