From d00a3762cd9813446a97ae8a5b3a621d20cd608d Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Fri, 26 Feb 2016 07:06:05 +0100 Subject: Correct and simplify timeouts_readd() William Ahern tells me that the intent here is that timeout_readd() should always reschedule the timeout at the first time in the future that is an even multiple of to->interval, as if we had called: do { to->expires += to->interval; } while (to->expires <= T->curtime); But of course, that's not efficient. The implementation strategy used in this patch simplifies the calculation down to a single % operation, plus a few additions and subtractions. To verify the correctness of the formula used here, note first that 0 <= r < to->interval, and so 0 < to->interval - r <= to->interval. Since expires' = curtime + (interval - r), curtime < expires' <= curtime + interval, and so the new expiration time is no more than one interval after curtime. Note second that since r = (curtime - expires) % interval, expires' = curtime + (interval - r), we have (expires' - expires) % interval = (curtime + (interval - r) - expires) % interval = (curtime - r - expires) % interval = (curtime - (curtime-expires) % interval - expires) % interval = (curtime - curtime + expires - expires) % interval = 0. And so the new expiration time is an even multiple of interval from the original expiration time. Since we have both properties we wanted, this formula should be right. --- timeout.c | 19 +++++++------------ 1 file changed, 7 insertions(+), 12 deletions(-) diff --git a/timeout.c b/timeout.c index ad2373d..1d55020 100644 --- a/timeout.c +++ b/timeout.c @@ -358,18 +358,13 @@ static void timeouts_readd(struct timeouts *T, struct timeout *to) { to->expires += to->interval; if (to->expires <= T->curtime) { - if (to->expires < T->curtime) { - timeout_t n = T->curtime - to->expires; - timeout_t q = n / to->interval; - timeout_t r = n % to->interval; - - if (r) - to->expires += (to->interval * q) + (to->interval - r); - else - to->expires += (to->interval * q); - } else { - to->expires += to->interval; - } + /* 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); -- cgit v1.2.3