• Nick Mathewson's avatar
    Correct and simplify timeouts_readd() · d00a3762
    Nick Mathewson authored
    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.
    d00a3762
timeout.c 19.6 KB