From fe6bc8c530795a6c718f7e8fd1a6643d9f3024a1 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Wed, 29 Oct 2014 16:02:46 +1030 Subject: [PATCH 1/1] timer: change timers_expire() to return a single timer. The linked list method was problematic, especially if timers delete other expired timers (eg. the next one in the expired list: the timer_del will delete it from expired, but that's a bit unexpected). Signed-off-by: Rusty Russell --- ccan/timer/_info | 7 +++---- ccan/timer/benchmarks/expected-usage.c | 4 ++-- ccan/timer/test/run-expiry.c | 7 ++----- ccan/timer/test/run-ff.c | 13 +++++-------- ccan/timer/test/run.c | 9 +++------ ccan/timer/timer.c | 22 ++++++++++------------ ccan/timer/timer.h | 25 +++++++++++-------------- 7 files changed, 36 insertions(+), 51 deletions(-) diff --git a/ccan/timer/_info b/ccan/timer/_info index 4c58d9e5..420aba11 100644 --- a/ccan/timer/_info +++ b/ccan/timer/_info @@ -28,7 +28,7 @@ * { * struct timers timers; * struct list_head strings; - * struct list_head expired; + * struct timer *t; * struct timed_string *s; * * timers_init(&timers, time_now()); @@ -48,9 +48,8 @@ * struct timeabs now = time_now(); * list_for_each(&strings, s, node) * printf("%s", s->string); - * timers_expire(&timers, now, &expired); - * while ((s = list_pop(&expired, struct timed_string, - * timer.list)) != NULL) { + * while ((t = timers_expire(&timers, now)) != NULL) { + * s = container_of(t, struct timed_string, timer); * list_del_from(&strings, &s->node); * free(s); * } diff --git a/ccan/timer/benchmarks/expected-usage.c b/ccan/timer/benchmarks/expected-usage.c index a5018271..e0fed2ec 100644 --- a/ccan/timer/benchmarks/expected-usage.c +++ b/ccan/timer/benchmarks/expected-usage.c @@ -34,10 +34,10 @@ int main(int argc, char *argv[]) curr = time_add(curr, time_from_msec(1)); if (check) timers_check(&timers, NULL); - timers_expire(&timers, curr, &expired); + if (timers_expire(&timers, curr)) + abort(); if (check) timers_check(&timers, NULL); - assert(list_empty(&expired)); if (i >= PER_CONN_TIME) { timer_del(&timers, &t[i%PER_CONN_TIME]); diff --git a/ccan/timer/test/run-expiry.c b/ccan/timer/test/run-expiry.c index e53de6a9..d2969d25 100644 --- a/ccan/timer/test/run-expiry.c +++ b/ccan/timer/test/run-expiry.c @@ -7,7 +7,6 @@ int main(void) { struct timers timers; struct timer t; - struct list_head list; /* This is how many tests you plan to run */ plan_tests(7); @@ -17,12 +16,10 @@ int main(void) timer_add(&timers, &t, grains_to_time(1364984761003398ULL)); ok1(t.time == 1364984761003398ULL); ok1(timers.first == 1364984761003398ULL); - timers_expire(&timers, grains_to_time(1364984760903444ULL), &list); + ok1(!timers_expire(&timers, grains_to_time(1364984760903444ULL))); ok1(timers_check(&timers, NULL)); - ok1(list_pop(&list, struct timer, list) == NULL); - timers_expire(&timers, grains_to_time(1364984761002667ULL), &list); + ok1(!timers_expire(&timers, grains_to_time(1364984761002667ULL))); ok1(timers_check(&timers, NULL)); - ok1(list_pop(&list, struct timer, list) == NULL); timers_cleanup(&timers); diff --git a/ccan/timer/test/run-ff.c b/ccan/timer/test/run-ff.c index 0f398d55..148b7f79 100644 --- a/ccan/timer/test/run-ff.c +++ b/ccan/timer/test/run-ff.c @@ -12,20 +12,17 @@ static struct timeabs timeabs_from_usec(unsigned long long usec) int main(void) { struct timers timers; - struct timer t; - struct list_head expired; + struct timer t, *expired; /* This is how many tests you plan to run */ plan_tests(3); timers_init(&timers, timeabs_from_usec(1364726722653919ULL)); timer_add(&timers, &t, timeabs_from_usec(1364726722703919ULL)); - timers_expire(&timers, timeabs_from_usec(1364726722653920ULL), &expired); - ok1(list_empty(&expired)); - timers_expire(&timers, timeabs_from_usec(1364726725454187ULL), &expired); - ok1(!list_empty(&expired)); - ok1(list_top(&expired, struct timer, list) == &t); - + ok1(!timers_expire(&timers, timeabs_from_usec(1364726722653920ULL))); + expired = timers_expire(&timers, timeabs_from_usec(1364726725454187ULL)); + ok1(expired == &t); + ok1(!timers_expire(&timers, timeabs_from_usec(1364726725454187ULL))); timers_cleanup(&timers); /* This exits depending on whether all tests passed */ diff --git a/ccan/timer/test/run.c b/ccan/timer/test/run.c index cebc99ce..f7b711f2 100644 --- a/ccan/timer/test/run.c +++ b/ccan/timer/test/run.c @@ -13,7 +13,6 @@ int main(void) { struct timers timers; struct timer t[64]; - struct list_head expired; struct timeabs earliest; uint64_t i; struct timeabs epoch = { { 0, 0 } }; @@ -69,13 +68,11 @@ int main(void) struct timer *t1, *t2; ok1(timer_earliest(&timers, &earliest)); - timers_expire(&timers, earliest, &expired); - - t1 = list_pop(&expired, struct timer, list); + t1 = timers_expire(&timers, earliest); ok1(t1); - t2 = list_pop(&expired, struct timer, list); + t2 = timers_expire(&timers, earliest); ok1(t2); - ok1(list_empty(&expired)); + ok1(!timers_expire(&timers, earliest)); ok1(t1 == &t[i*2] || t1 == &t[i*2+1]); ok1(t2 != t1 && (t2 == &t[i*2] || t2 == &t[i*2+1])); diff --git a/ccan/timer/timer.c b/ccan/timer/timer.c index c30c6227..c1979fd3 100644 --- a/ccan/timer/timer.c +++ b/ccan/timer/timer.c @@ -259,37 +259,35 @@ static void timer_fast_forward(struct timers *timers, uint64_t time) timer_add_raw(timers, i); } -/* Fills list of expired timers. */ -void timers_expire(struct timers *timers, - struct timeabs expire, - struct list_head *list) +/* Returns an expired timer. */ +struct timer *timers_expire(struct timers *timers, struct timeabs expire) { uint64_t now = time_to_grains(expire); unsigned int off; + struct timer *t; assert(now >= timers->base); - list_head_init(list); - if (!timers->level[0]) { if (list_empty(&timers->far)) - return; + return NULL; add_level(timers, 0); } do { if (timers->first > now) { timer_fast_forward(timers, now); - break; + return NULL; } timer_fast_forward(timers, timers->first); off = timers->base % PER_LEVEL; - list_append_list(list, &timers->level[0]->list[off]); - if (timers->base == now) - break; - } while (update_first(timers)); + /* This *may* be NULL, if we deleted the first timer */ + t = list_pop(&timers->level[0]->list[off], struct timer, list); + } while (!t && update_first(timers)); + + return t; } static bool timer_list_check(const struct list_head *l, diff --git a/ccan/timer/timer.h b/ccan/timer/timer.h index 79399cc4..aeb2aebc 100644 --- a/ccan/timer/timer.h +++ b/ccan/timer/timer.h @@ -89,32 +89,29 @@ void timer_del(struct timers *timers, struct timer *timer); bool timer_earliest(struct timers *timers, struct timeabs *first); /** - * timers_expire - update timers structure and remove expired timers. + * timers_expire - update timers structure and remove one expire timer. * @timers: the struct timers * @expire: the current time - * @list: the list for expired timers. * - * @list will be initialized to the empty list, then all timers added - * with a @when arg less than or equal to @expire will be added to it in - * expiry order (within TIMER_GRANULARITY nanosecond precision). + * A timers added with a @when arg less than or equal to @expire will be + * returned (within TIMER_GRANULARITY nanosecond precision). If + * there are no timers due to expire, NULL is returned. * - * After this, @expire is considered the current time, and adding any - * timers with @when before this value will be silently changed to - * adding them with immediate expiration. + * After this returns NULL, @expire is considered the current time, + * and adding any timers with @when before this value will be silently + * changed to adding them with immediate expiration. * * You should not move @expire backwards, though it need not move * forwards. * * Example: - * struct list_head expired; + * struct timer *expired; * - * timers_expire(&timeouts, time_now(), &expired); - * if (!list_empty(&expired)) + * while ((expired = timers_expire(&timeouts, time_now())) != NULL) * printf("Timer expired!\n"); + * */ -void timers_expire(struct timers *timers, - struct timeabs expire, - struct list_head *list); +struct timer *timers_expire(struct timers *timers, struct timeabs expire); /** * timers_check - check timer structure for consistency -- 2.39.2