commit 9abf541f7f70068b6f7567481739ca6374f1fd57 Author: Nick Mathewson nickm@torproject.org Date: Thu Apr 26 11:17:48 2018 -0400
Add a function to compute millisecond time difference quickly.
Our main function, though accurate on all platforms, can be very slow on 32-bit hosts. This one is faster on all 32-bit hosts, and accurate everywhere except apple, where it will typically be off by 1%. But since 32-bit apple is a relic anyway, I think we should be fine. --- src/common/compat_time.c | 50 ++++++++++++++++++++++++++++++++++++++++++++++++ src/common/compat_time.h | 27 ++++++++++++++++++++++++++ src/or/circuitmux_ewma.c | 7 ++----- src/test/test_util.c | 5 +++++ 4 files changed, 84 insertions(+), 5 deletions(-)
diff --git a/src/common/compat_time.c b/src/common/compat_time.c index 966216768..b3723f533 100644 --- a/src/common/compat_time.c +++ b/src/common/compat_time.c @@ -279,6 +279,7 @@ monotime_reset_ratchets_for_testing(void) * nanoseconds. */ static struct mach_timebase_info mach_time_info; +static struct mach_timebase_info mach_time_info_msec_cvt; static int monotime_shift = 0;
static void @@ -296,6 +297,14 @@ monotime_init_internal(void) // requires that tor_log2(0) == 0. monotime_shift = tor_log2(ms_per_tick); } + { + // For converting ticks to milliseconds in a 32-bit-friendly way, we + // will first right-shift by 20, and then multiply by 20/19, since + // (1<<20) * 19/20 is about 1e6. We precompute a new numerate and + // denominator here to avoid multiple multiplies. + mach_time_info_msec_cvt.numer = mach_time_info.numer * 20; + mach_time_info_msec_cvt.denom = mach_time_info.denom * 19; + } }
/** @@ -345,6 +354,22 @@ monotime_diff_nsec(const monotime_t *start, return diff_nsec; }
+int32_t +monotime_coarse_diff_msec32_(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ + if (BUG(mach_time_info.denom == 0)) { + monotime_init(); + } + const int64_t diff_ticks = end->abstime_ - start->abstime_; + + /* We already require in di_ops.c that right-shift performs a sign-extend. */ + const int32_t diff_microticks = (int32_t)(diff_ticks >> 20); + + return (diff_microticks * mach_time_info_msec_cvt.numer) / + mach_time_info_msec_cvt.denom; +} + uint32_t monotime_coarse_to_stamp(const monotime_coarse_t *t) { @@ -443,6 +468,15 @@ monotime_diff_nsec(const monotime_t *start, return diff_nsec; }
+int32_t +monotime_coarse_diff_msec32_(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ + const int32_t diff_sec = (int32_t)(end->ts_.tv_sec - start->ts_.tv_sec); + const int32_t diff_nsec = (int32_t)(end->ts_.tv_nsec - start->ts_.tv_nsec); + return diff_sec * 1000 + diff_nsec / ONE_MILLION; +} + /* This value is ONE_BILLION >> 20. */ static const uint32_t STAMP_TICKS_PER_SECOND = 953;
@@ -592,6 +626,13 @@ monotime_coarse_diff_msec(const monotime_coarse_t *start, return diff_ticks; }
+int32_t +monotime_coarse_diff_msec32_(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ + return (int32_t)monotime_coarse_diff_msec(start, end) +} + int64_t monotime_coarse_diff_usec(const monotime_coarse_t *start, const monotime_coarse_t *end) @@ -677,6 +718,15 @@ monotime_diff_nsec(const monotime_t *start, return (diff.tv_sec * ONE_BILLION + diff.tv_usec * 1000); }
+int32_t +monotime_coarse_diff_msec32_(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ + struct timeval diff; + timersub(&end->tv_, &start->tv_, &diff); + return diff.tv_sec * 1000 + diff.tv_usec / 1000; +} + /* This value is ONE_MILLION >> 10. */ static const uint32_t STAMP_TICKS_PER_SECOND = 976;
diff --git a/src/common/compat_time.h b/src/common/compat_time.h index 09dd6add3..57ab20ab1 100644 --- a/src/common/compat_time.h +++ b/src/common/compat_time.h @@ -173,6 +173,33 @@ void monotime_coarse_add_msec(monotime_coarse_t *out, #define monotime_coarse_add_msec monotime_add_msec #endif /* defined(MONOTIME_COARSE_TYPE_IS_DIFFERENT) */
+/** + * As monotime_coarse_diff_msec, but avoid 64-bit division. + * + * Requires that the difference fit into an int32_t; not for use with + * large time differences. + */ +int32_t monotime_coarse_diff_msec32_(const monotime_coarse_t *start, + const monotime_coarse_t *end); + +/** + * As monotime_coarse_diff_msec, but avoid 64-bit division if it is expensive. + * + * Requires that the difference fit into an int32_t; not for use with + * large time differences. + */ +static inline int32_t +monotime_coarse_diff_msec32(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ +#if SIZEOF_VOID_P == 8 + // on a 64-bit platform, let's assume 64/64 division is cheap. + return (int32_t) monotime_coarse_diff_msec(start, end); +#else + return monotime_coarse_diff_msec32_(start, end); +#endif +} + MOCK_DECL(void, tor_gettimeofday, (struct timeval *timeval));
#ifdef TOR_UNIT_TESTS diff --git a/src/or/circuitmux_ewma.c b/src/or/circuitmux_ewma.c index a8a645ca5..a360327f8 100644 --- a/src/or/circuitmux_ewma.c +++ b/src/or/circuitmux_ewma.c @@ -626,11 +626,8 @@ cell_ewma_get_current_tick_and_fraction(double *remainder_out) } monotime_coarse_t now; monotime_coarse_get(&now); - // XXXX this does a division operation that can be slow on 32-bit - // XXXX systems. - int32_t msec_diff = - (int32_t)monotime_coarse_diff_msec(&start_of_current_tick, - &now); + int32_t msec_diff = monotime_coarse_diff_msec32(&start_of_current_tick, + &now); if (msec_diff > (1000*EWMA_TICK_LEN)) { unsigned ticks_difference = msec_diff / (1000*EWMA_TICK_LEN); monotime_coarse_add_msec(&start_of_current_tick, diff --git a/src/test/test_util.c b/src/test/test_util.c index 350273bf4..9c028fd47 100644 --- a/src/test/test_util.c +++ b/src/test/test_util.c @@ -6035,6 +6035,9 @@ test_util_monotonic_time_add_msec(void *arg) monotime_coarse_add_msec(&ct2, &ct1, 1337); tt_i64_op(monotime_diff_msec(&t1, &t2), OP_EQ, 1337); tt_i64_op(monotime_coarse_diff_msec(&ct1, &ct2), OP_EQ, 1337); + // The 32-bit variant must be within 1% of the regular one. + tt_int_op(monotime_coarse_diff_msec32_(&ct1, &ct2), OP_GT, 1323); + tt_int_op(monotime_coarse_diff_msec32_(&ct1, &ct2), OP_LT, 1350);
/* Add 1337 msec twice more; make sure that any second rollover issues * worked. */ @@ -6044,6 +6047,8 @@ test_util_monotonic_time_add_msec(void *arg) monotime_coarse_add_msec(&ct2, &ct2, 1337); tt_i64_op(monotime_diff_msec(&t1, &t2), OP_EQ, 1337*3); tt_i64_op(monotime_coarse_diff_msec(&ct1, &ct2), OP_EQ, 1337*3); + tt_int_op(monotime_coarse_diff_msec32_(&ct1, &ct2), OP_GT, 3970); + tt_int_op(monotime_coarse_diff_msec32_(&ct1, &ct2), OP_LT, 4051);
done: ;