• 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