commit dc6f5d1dc1ccc86f32b39b939a5f83c35865d666 Author: Nick Mathewson nickm@torproject.org Date: Fri Jul 8 12:53:51 2016 -0400
Basic portable monotonic timer implementation
This code uses QueryPerformanceCounter() [**] on Windows, mach_absolute_time() on OSX, clock_gettime() where available, and gettimeofday() [*] elsewhere.
Timer types are stored in an opaque OS-specific format; the only supported operation is to compute the difference between two timers.
[*] As you know, gettimeofday() isn't monotonic, so we include a simple ratchet function to ensure that it only moves forward.
[**] As you may not know, QueryPerformanceCounter() isn't actually always as monotonic as you might like it to be, so we ratchet that one too.
We also include a "coarse monotonic timer" for cases where we don't actually need high-resolution time. This is GetTickCount{,64}() on Windows, clock_gettime(CLOCK_MONOTONIC_COARSE) on Linux, and falls back to regular monotonic time elsewhere. --- src/common/compat_time.c | 381 ++++++++++++++++++++++++++++++++++++++++++++++- src/common/compat_time.h | 121 +++++++++++++++ 2 files changed, 501 insertions(+), 1 deletion(-)
diff --git a/src/common/compat_time.c b/src/common/compat_time.c index 866c288..bbbca33 100644 --- a/src/common/compat_time.c +++ b/src/common/compat_time.c @@ -9,7 +9,7 @@ * timers, etc. **/
-#define COMPAT_PRIVATE +#define COMPAT_TIME_PRIVATE #include "compat.h"
#ifdef _WIN32 @@ -30,6 +30,10 @@ #endif #endif
+#ifdef __APPLE__ +#include <mach/mach_time.h> +#endif + #include "torlog.h" #include "util.h" #include "container.h" @@ -108,3 +112,378 @@ tor_gettimeofday(struct timeval *timeval) return; }
+#define ONE_MILLION ((int64_t) (1000 * 1000)) +#define ONE_BILLION ((int64_t) (1000 * 1000 * 1000)) + +/** True iff monotime_init has been called. */ +static int monotime_initialized = 0; + +#ifdef __APPLE__ + +/** Initialized on startup: tells is how to convert from ticks to + * nanoseconds. + */ +static struct mach_timebase_info mach_time_info; + +static void +monotime_init_internal(void) +{ + tor_assert(!monotime_initialized); + int r = mach_timebase_info(&mach_time_info); + tor_assert(r == 0); + tor_assert(mach_time_info.denom != 0); +} + +/** + * Set "out" to the most recent monotonic time value + */ +void +monotime_get(monotime_t *out) +{ + out->abstime_ = mach_absolute_time(); +} + +/** + * Return the number of nanoseconds between <b>start</b> and <b>end</b>. + */ +int64_t +monotime_diff_nsec(const monotime_t *start, + const monotime_t *end) +{ + if (BUG(mach_time_info.denom == 0)) { + monotime_init(); + } + const int64_t diff_ticks = end->abstime_ - start->abstime_; + const int64_t diff_nsec = + (diff_ticks * mach_time_info.numer) / mach_time_info.denom; + return diff_nsec; +} + +/* end of "__APPLE__" */ +#elif defined(HAVE_CLOCK_GETTIME) + +static void +monotime_init_internal(void) +{ + /* no action needed. */ +} + +void +monotime_get(monotime_t *out) +{ + int r = clock_gettime(CLOCK_MONOTONIC, &out->ts_); + tor_assert(r == 0); +} + +#ifdef CLOCK_MONOTONIC_COARSE +void +monotime_coarse_get(monotime_coarse_t *out) +{ + int r = clock_gettime(CLOCK_MONOTONIC_COARSE, &out->ts_); + tor_assert(r == 0); +} +#endif + +int64_t +monotime_diff_nsec(const monotime_t *start, + const monotime_t *end) +{ + const int64_t diff_sec = end->ts_.tv_sec - start->ts_.tv_sec; + const int64_t diff_nsec = diff_sec * ONE_BILLION + + (end->ts_.tv_nsec - start->ts_.tv_nsec); + + return diff_nsec; +} + +/* end of "HAVE_CLOCK_GETTIME" */ +#elif defined (_WIN32) + +/** Result of QueryPerformanceFrequency, as an int64_t. */ +static int64_t ticks_per_second = 0; + +/** Protected by lock: last value returned by monotime_get(). */ +static int64_t last_pctr = 0; +/** Protected by lock: offset we must add to monotonic time values. */ +static int64_t pctr_offset = 0; +/** Lock to protect last_pctr and pctr_offset */ +static CRITICAL_SECTION monotime_lock; +/* If we are using GetTickCount(), how many times has it rolled over? */ +static uint32_t rollover_count = 0; +/* If we are using GetTickCount(), what's the last value it returned? */ +static int64_t last_tick_count = 0; +/** Lock to protect rollover_count and */ +static CRITICAL_SECTION monotime_coarse_lock; + +typedef ULONGLONG (WINAPI *GetTickCount64_fn_t)(void); +static GetTickCount64_fn_t GetTickCount64_fn = NULL; + +static void +monotime_init_internal(void) +{ + tor_assert(!monotime_initialized); + BOOL ok = InitializeCriticalSectionAndSpinCount(&monotime_lock, 200); + tor_assert(ok); + ok = InitializeCriticalSectionAndSpinCount(&monotime_coarse_lock, 200); + tor_assert(ok); + LARGE_INTEGER li; + ok = QueryPerformanceFrequency(&li); + tor_assert(ok); + tor_assert(li.QuadPart); + ticks_per_second = li.QuadPart; + last_pctr = 0; + pctr_offset = 0; + + HANDLE h = load_windows_system_library(TEXT("kernel32.dll")); + if (h) { + GetTickCount64_fn = (GetTickCount64_fn_t) + GetProcAddress(h, "GetTickCount64"); + } + // FreeLibrary(h) ? +} + +/** Helper for windows: Called with a sequence of times that are supposed + * to be monotonic; increments them as appropriate so that they actually + * _are_ monotonic. + * + * Caller must hold lock. */ +STATIC int64_t +ratchet_performance_counter(int64_t count_raw) +{ + /* must hold lock */ + const int64_t count_adjusted = count_raw + pctr_offset; + + if (PREDICT_UNLIKELY(count_adjusted < last_pctr)) { + /* Monotonicity failed! Pretend no time elapsed. */ + pctr_offset = last_pctr - count_raw; + return last_pctr; + } else { + last_pctr = count_adjusted; + return count_adjusted; + } +} + +STATIC int64_t +ratchet_coarse_performance_counter(const int64_t count_raw) +{ + int64_t count = count_raw + (((int64_t)rollover_count) << 32); + while (PREDICT_UNLIKELY(count < last_tick_count)) { + ++rollover_count; + count = count_raw + (((int64_t)rollover_count) << 32); + } + last_tick_count = count; + return count; +} + +void +monotime_get(monotime_t *out) +{ + if (BUG(monotime_initialized == 0)) { + monotime_init(); + } + + /* Alas, QueryPerformanceCounter is not always monotonic: see bug list at + + https://www.python.org/dev/peps/pep-0418/#windows-queryperformancecounter + */ + + EnterCriticalSection(&monotime_lock); + LARGE_INTEGER res; + BOOL ok = QueryPerformanceCounter(&res); + tor_assert(ok); + const int64_t count_raw = res.QuadPart; + out->pcount_ = ratchet_performance_counter(count_raw); + LeaveCriticalSection(&monotime_lock); +} + +void +monotime_coarse_get(monotime_coarse_t *out) +{ + if (GetTickCount64_fn) { + out->tick_count_ = (int64_t)GetTickCount64_fn(); + } else { + EnterCriticalSection(&monotime_coarse_lock); + DWORD tick = GetTickCount(); + out->tick_count_ = ratchet_coarse_performance_counter(tick); + LeaveCriticalSection(&monotime_coarse_lock); + } +} + +int64_t +monotime_diff_nsec(const monotime_t *start, + const monotime_t *end) +{ + if (BUG(monotime_initialized == 0)) { + monotime_init(); + } + const int64_t diff_ticks = end->pcount_ - start->pcount_; + return (diff_ticks * ONE_BILLION) / ticks_per_second; +} + +int64_t +monotime_coarse_diff_msec(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ + const int64_t diff_ticks = end->tick_count_ - start->tick_count_; + return diff_ticks; +} + +int64_t +monotime_coarse_diff_usec(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ + return monotime_coarse_diff_msec(start, end) * 1000; +} + +int64_t +monotime_coarse_diff_nsec(const monotime_coarse_t *start, + const monotime_coarse_t *end) +{ + return monotime_coarse_diff_msec(start, end) * ONE_MILLION; +} + +/* end of "_WIN32" */ +#elif defined(MONOTIME_USING_GETTIMEOFDAY) + +static int monotime_initialized = 0; +static struct timeval last_timeofday = { 0, 0 }; +static struct timeval timeofday_offset = { 0, 0 }; +static tor_mutex_t monotime_lock; + +/** Initialize the monotonic timer subsystem. */ +static void +monotime_init_internal(void) +{ + tor_assert(!monotime_initialized); + tor_mutex_init(&monotime_lock); +} + +/** Helper for gettimeofday(): Called with a sequence of times that are + * supposed to be monotonic; increments them as appropriate so that they + * actually _are_ monotonic. + * + * Caller must hold lock. */ +STATIC void +ratchet_timeval(const struct timeval *timeval_raw, struct timeval *out) +{ + /* must hold lock */ + timeradd(timeval_raw, &timeofday_offset, out); + if (PREDICT_UNLIKELY(timercmp(out, &last_timeofday, <))) { + /* time ran backwards. Instead, declare that no time occurred. */ + timersub(&last_timeofday, timeval_raw, &timeofday_offset); + memcpy(out, &last_timeofday, sizeof(struct timeval)); + } else { + memcpy(&last_timeofday, out, sizeof(struct timeval)); + } +} + +void +monotime_get(monotime_t *out) +{ + if (BUG(monotime_initialized == 0)) { + monotime_init(); + } + + tor_mutex_acquire(&monotime_lock); + struct timeval timeval_raw; + tor_gettimeofday(&timeval_raw); + ratchet_timeval(&timeval_raw, &out->tv_); + tor_mutex_release(&monotime_lock); +} + +int64_t +monotime_diff_nsec(const monotime_t *start, + const monotime_t *end) +{ + struct timeval diff; + timersub(&end->tv_, &start->tv_, &diff); + return (diff.tv_sec * ONE_BILLION + diff.tv_usec * 1000); +} + +/* end of "MONOTIME_USING_GETTIMEOFDAY" */ +#else +#error "No way to implement monotonic timers." +#endif + +static monotime_t initialized_at; +#ifdef MONOTIME_COARSE_FN_IS_DIFFERENT +static monotime_coarse_t initialized_at_coarse; +#endif + +/** + * Initialize the monotonic timer subsystem. Must be called before any + * monotonic timer functions. This function is idempotent. + */ +void +monotime_init(void) +{ + if (!monotime_initialized) { + monotime_init_internal(); + monotime_get(&initialized_at); +#ifdef MONOTIME_COARSE_FN_IS_DIFFERENT + monotime_coarse_get(&initialized_at_coarse); +#endif + monotime_initialized = 1; + } +} + +int64_t +monotime_diff_usec(const monotime_t *start, + const monotime_t *end) +{ + const int64_t nsec = monotime_diff_nsec(start, end); + return CEIL_DIV(nsec, 1000); +} + +int64_t +monotime_diff_msec(const monotime_t *start, + const monotime_t *end) +{ + const int64_t nsec = monotime_diff_nsec(start, end); + return CEIL_DIV(nsec, ONE_MILLION); +} + +uint64_t +monotime_absolute_nsec(void) +{ + monotime_t now; + monotime_get(&now); + return monotime_diff_nsec(&initialized_at, &now); +} + +uint64_t +monotime_absolute_usec(void) +{ + return monotime_absolute_nsec() / 1000; +} + +uint64_t +monotime_absolute_msec(void) +{ + return monotime_absolute_nsec() / ONE_MILLION; +} + +#ifdef MONOTIME_COARSE_FN_IS_DIFFERENT +uint64_t +monotime_coarse_absolute_nsec(void) +{ + monotime_coarse_t now; + monotime_coarse_get(&now); + return monotime_coarse_diff_nsec(&initialized_at_coarse, &now); +} + +uint64_t +monotime_coarse_absolute_usec(void) +{ + monotime_coarse_t now; + monotime_coarse_get(&now); + return monotime_coarse_diff_usec(&initialized_at_coarse, &now); +} + +uint64_t +monotime_coarse_absolute_msec(void) +{ + monotime_coarse_t now; + monotime_coarse_get(&now); + return monotime_coarse_diff_msec(&initialized_at_coarse, &now); +} +#endif diff --git a/src/common/compat_time.h b/src/common/compat_time.h index 56126ba..d69af8f 100644 --- a/src/common/compat_time.h +++ b/src/common/compat_time.h @@ -3,11 +3,28 @@ * Copyright (c) 2007-2016, The Tor Project, Inc. */ /* See LICENSE for licensing information */
+/** + * \file compat_time.h + * + * \brief Functions and types for monotonic times. + * + * monotime_* functions try to provide a high-resolution monotonic timer with + * something the best resolution the system provides. monotime_coarse_* + * functions run faster (if the operating system gives us a way to do that) + * but produce a less accurate timer: accuracy will probably be on the order + * of tens of milliseconds. + */ + #ifndef TOR_COMPAT_TIME_H #define TOR_COMPAT_TIME_H
#include "orconfig.h"
+#if defined(HAVE_CLOCK_GETTIME) +/* to ensure definition of CLOCK_MONOTONIC_COARSE if it's there */ +#include <time.h> +#endif + #if !defined(HAVE_GETTIMEOFDAY) && !defined(HAVE_STRUCT_TIMEVAL_TV_SEC) /** Implementation of timeval for platforms that don't have it. */ struct timeval { @@ -16,11 +33,115 @@ struct timeval { }; #endif
+/** Represents a monotonic timer in a platform-dependent way. */ +typedef struct monotime_t { +#ifdef __APPLE__ + /* On apple, there is a 64-bit counter whose precision we must look up. */ + uint64_t abstime_; +#elif defined(HAVE_CLOCK_GETTIME) + /* It sure would be nice to use clock_gettime(). Posix is a nice thing. */ + struct timespec ts_; +#elif defined (_WIN32) + /* On Windows, there is a 64-bit counter whose precision we must look up. */ + int64_t pcount_; +#else +#define MONOTIME_USING_GETTIMEOFDAY + /* Otherwise, we will be stuck using gettimeofday. */ + struct timeval tv_; +#endif +} monotime_t; + +#if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_MONOTONIC_COARSE) +#define MONOTIME_COARSE_FN_IS_DIFFERENT +#define monotime_coarse_t monotime_t +#elif defined(_WIN32) +#define MONOTIME_COARSE_FN_IS_DIFFERENT +#define MONOTIME_COARSE_TYPE_IS_DIFFERENT +/** Represents a coarse monotonic time in a platform-independent way. */ +typedef struct monotime_coarse_t { + uint64_t tick_count_; +} monotime_coarse_t; +#else +#define monotime_coarse_t monotime_t +#endif + +/** + * Initialize the timing subsystem. This function is idempotent. + */ +void monotime_init(void); +/** + * Set <b>out</b> to the current time. + */ +void monotime_get(monotime_t *out); +/** + * Return the number of nanoseconds between <b>start</b> and <b>end</b>. + */ +int64_t monotime_diff_nsec(const monotime_t *start, const monotime_t *end); +/** + * Return the number of microseconds between <b>start</b> and <b>end</b>. + */ +int64_t monotime_diff_usec(const monotime_t *start, const monotime_t *end); +/** + * Return the number of milliseconds between <b>start</b> and <b>end</b>. + */ +int64_t monotime_diff_msec(const monotime_t *start, const monotime_t *end); +/** + * Return the number of nanoseconds since the timer system was initialized. + */ +uint64_t monotime_absolute_nsec(void); +/** + * Return the number of microseconds since the timer system was initialized. + */ +uint64_t monotime_absolute_usec(void); +/** + * Return the number of milliseconds since the timer system was initialized. + */ +uint64_t monotime_absolute_msec(void); + +#if defined(MONOTIME_COARSE_FN_IS_DIFFERENT) +/** + * Set <b>out</b> to the current coarse time. + */ +void monotime_coarse_get(monotime_coarse_t *out); +uint64_t monotime_coarse_absolute_nsec(void); +uint64_t monotime_coarse_absolute_usec(void); +uint64_t monotime_coarse_absolute_msec(void); +#else +#define monotime_coarse_get monotime_get +#define monotime_coarse_absolute_nsec monotime_absolute_nsec +#define monotime_coarse_absolute_usec monotime_absolute_usec +#define monotime_coarse_absolute_msec monotime_absolute_msec +#endif + +#if defined(MONOTIME_COARSE_TYPE_IS_DIFFERENT) +int64_t monotime_coarse_diff_nsec(const monotime_coarse_t *start, + const monotime_coarse_t *end); +int64_t monotime_coarse_diff_usec(const monotime_coarse_t *start, + const monotime_coarse_t *end); +int64_t monotime_coarse_diff_msec(const monotime_coarse_t *start, + const monotime_coarse_t *end); +#else +#define monotime_coarse_diff_nsec monotime_diff_nsec +#define monotime_coarse_diff_usec monotime_diff_usec +#define monotime_coarse_diff_msec monotime_diff_msec +#endif + void tor_gettimeofday(struct timeval *timeval);
#ifdef TOR_UNIT_TESTS void tor_sleep_msec(int msec); #endif
+#ifdef COMPAT_TIME_PRIVATE +#ifdef _WIN32 +STATIC int64_t ratchet_performance_counter(int64_t count_raw); +STATIC int64_t ratchet_coarse_performance_counter(int64_t count_raw); +#endif +#ifdef MONOTIME_USING_GETTIMEOFDAY +STATIC void ratchet_timeval(const struct timeval *timeval_raw, + struct timeval *out); +#endif +#endif + #endif