[Windows] One TimeTicks clock: efficient/reliable high-res, with low-res fallback.

base/time/time_win.cc

Index: base/time/time_win.cc
diff --git a/base/time/time_win.cc b/base/time/time_win.cc
index 9b4f17d6613c7e60b8576adc9ae3b2a6afc8c8a3..bb599bb1215b4b43dc250ccacb798383fb3e751e 100644
--- a/base/time/time_win.cc
+++ b/base/time/time_win.cc
@@ -37,6 +37,7 @@
 #include <windows.h>
 #include <mmsystem.h>
 
+#include "base/atomicops.h"
 #include "base/basictypes.h"
 #include "base/cpu.h"
 #include "base/lazy_instance.h"
@@ -307,13 +308,13 @@ DWORD timeGetTimeWrapper() {
   return timeGetTime();
 }
 
-DWORD (*tick_function)(void) = &timeGetTimeWrapper;
+DWORD (*g_tick_function)(void) = &timeGetTimeWrapper;
 
 // Accumulation of time lost due to rollover (in milliseconds).
-int64 rollover_ms = 0;
+int64 g_rollover_ms = 0;
 
 // The last timeGetTime value we saw, to detect rollover.
-DWORD last_seen_now = 0;
+DWORD g_last_seen_now = 0;
 
 // Lock protecting rollover_ms and last_seen_now.
 // Note: this is a global object, and we usually avoid these. However, the time
@@ -321,31 +322,26 @@ DWORD last_seen_now = 0;
 // easy to use a Singleton without even knowing it, and that may lead to many
 // gotchas). Its impact on startup time should be negligible due to low-level
 // nature of time code.
-base::Lock rollover_lock;
+base::Lock g_rollover_lock;
 
 // We use timeGetTime() to implement TimeTicks::Now().  This can be problematic
 // because it returns the number of milliseconds since Windows has started,
 // which will roll over the 32-bit value every ~49 days.  We try to track
 // rollover ourselves, which works if TimeTicks::Now() is called at least every
 // 49 days.
-TimeDelta RolloverProtectedNow() {
-  base::AutoLock locked(rollover_lock);
+TimeTicks RolloverProtectedNow() {
+  base::AutoLock locked(g_rollover_lock);
   // We should hold the lock while calling tick_function to make sure that
   // we keep last_seen_now stay correctly in sync.
-  DWORD now = tick_function();
-  if (now < last_seen_now)
-    rollover_ms += 0x100000000I64;  // ~49.7 days.
-  last_seen_now = now;
-  return TimeDelta::FromMilliseconds(now + rollover_ms);
+  DWORD now = g_tick_function();
+  if (now < g_last_seen_now)
+    g_rollover_ms += 0x100000000I64;  // ~49.7 days.
+  g_last_seen_now = now;
+  return TimeTicks() + TimeDelta::FromMilliseconds(now + g_rollover_ms);
 }
 
-bool IsBuggyAthlon(const base::CPU& cpu) {
-  // On Athlon X2 CPUs (e.g. model 15) QueryPerformanceCounter is
-  // unreliable.  Fallback to low-res clock.
-  return cpu.vendor_name() == "AuthenticAMD" && cpu.family() == 15;
-}
-
-// Overview of time counters:
+// Discussion of tick counter options on Windows:
+//
 // (1) CPU cycle counter. (Retrieved via RDTSC)
 // The CPU counter provides the highest resolution time stamp and is the least
 // expensive to retrieve. However, the CPU counter is unreliable and should not
@@ -373,117 +369,100 @@ bool IsBuggyAthlon(const base::CPU& cpu) {
 // (3) System time. The system time provides a low-resolution (typically 10ms
 // to 55 milliseconds) time stamp but is comparatively less expensive to

[cpu_(ooo_6.6-7.5), 2015/01/07 17:41:31]

55 ?

[miu, 2015/01/07 19:20:17]

Not sure where these numbers come from, but I'll update them.  I've been doing
enough debugging on several different machines to believe the well-known 1ms -
15.6ms is the correct range.

 // retrieve and more reliable.
-class HighResNowSingleton {
- public:
-  HighResNowSingleton()
-      : ticks_per_second_(0),
-        skew_(0) {
-
-    base::CPU cpu;
-    if (IsBuggyAthlon(cpu))
-      return;
-
-    // Synchronize the QPC clock with GetSystemTimeAsFileTime.
-    LARGE_INTEGER ticks_per_sec = {0};
-    if (!QueryPerformanceFrequency(&ticks_per_sec))
-      return; // QPC is not available.
-    ticks_per_second_ = ticks_per_sec.QuadPart;
-
-    skew_ = UnreliableNow() - ReliableNow();
-  }
-
-  bool IsUsingHighResClock() {
-    return ticks_per_second_ != 0;
-  }
-
-  TimeDelta Now() {
-    if (IsUsingHighResClock())
-      return TimeDelta::FromMicroseconds(UnreliableNow());
 
-    // Just fallback to the slower clock.
-    return RolloverProtectedNow();
-  }
+using NowFunction = TimeTicks (*)(void);
 
-  int64 GetQPCDriftMicroseconds() {
-    if (!IsUsingHighResClock())
-      return 0;
-    return abs((UnreliableNow() - ReliableNow()) - skew_);
-  }
+TimeTicks InitialNowFunction();
+TimeTicks InitialSystemTraceNowFunction();
 
-  int64 QPCValueToMicroseconds(LONGLONG qpc_value) {
-    if (!ticks_per_second_)
-      return 0;
-    // If the QPC Value is below the overflow threshold, we proceed with
-    // simple multiply and divide.
-    if (qpc_value < Time::kQPCOverflowThreshold)
-      return qpc_value * Time::kMicrosecondsPerSecond / ticks_per_second_;
-    // Otherwise, calculate microseconds in a round about manner to avoid
-    // overflow and precision issues.
-    int64 whole_seconds = qpc_value / ticks_per_second_;
-    int64 leftover_ticks = qpc_value - (whole_seconds * ticks_per_second_);
-    int64 microseconds = (whole_seconds * Time::kMicrosecondsPerSecond) +
-                         ((leftover_ticks * Time::kMicrosecondsPerSecond) /
-                          ticks_per_second_);
-    return microseconds;
-  }
+// See "threading notes" in InitializeNowFunctionPointers() for details on how
+// concurrent reads/writes to these globals has been made safe.
+NowFunction g_now_function = &InitialNowFunction;
+NowFunction g_system_trace_now_function = &InitialSystemTraceNowFunction;
+int64 g_qpc_ticks_per_second = 0;
 
- private:
-  // Get the number of microseconds since boot in an unreliable fashion.
-  int64 UnreliableNow() {
-    LARGE_INTEGER now;
-    QueryPerformanceCounter(&now);
-    return QPCValueToMicroseconds(now.QuadPart);
-  }
+TimeDelta QPCValueToTimeDelta(LONGLONG qpc_value) {

[brianderson, 2015/01/07 19:53:11]

@brucedawson makes a good point about needing to protect the reads.

If we stick with the current approach, do we also need a barrier at the start of
this function to make sure the value of g_pqc_ticks_per_second isn't fetched
before g_now_function is set? It's *extremely* unlikely since a CPU wouldn't
know to predictively branch here until after g_now_function is set, but
theoretically possible given sufficiently crazy optimizations+reordering.

Would definitely prefer a single threaded init if possible, but is there a way
to do that just from code in base without requiring all base users to call some
init function?

[miu, 2015/01/07 22:04:32]

Done.  I had considered this, but deemed it impossible because how would a
compiler/CPU know how to predictively branch w/o knowing the function pointer
value?  However, a teammate pointed out to me that the compiler could decide not
to use function pointers at all (e.g., if it noticed g_now_function could only
take 2 possible values, it might choose to replace the function pointer with a
branch instruction + inlined code at each call point instead).

So, to be absolutely explicit (and since it is cheap), I've added the second
memory barrier here.  Now the code is correct from the theoretical standpoint
too.  :)

+  DCHECK_GT(g_qpc_ticks_per_second, 0);
 
-  // Get the number of microseconds since boot in a reliable fashion.
-  int64 ReliableNow() {
-    return RolloverProtectedNow().InMicroseconds();
+  // If the QPC Value is below the overflow threshold, we proceed with
+  // simple multiply and divide.
+  if (qpc_value < Time::kQPCOverflowThreshold) {
+    return TimeDelta::FromMicroseconds(
+        qpc_value * Time::kMicrosecondsPerSecond / g_qpc_ticks_per_second);
   }
+  // Otherwise, calculate microseconds in a round about manner to avoid
+  // overflow and precision issues.
+  int64 whole_seconds = qpc_value / g_qpc_ticks_per_second;
+  int64 leftover_ticks = qpc_value - (whole_seconds * g_qpc_ticks_per_second);
+  return TimeDelta::FromMicroseconds(
+      (whole_seconds * Time::kMicrosecondsPerSecond) +
+      ((leftover_ticks * Time::kMicrosecondsPerSecond) /
+       g_qpc_ticks_per_second));
+}
 
-  int64 ticks_per_second_;  // 0 indicates QPF failed and we're broken.
-  int64 skew_;  // Skew between lo-res and hi-res clocks (for debugging).
-};
-
-static base::LazyInstance<HighResNowSingleton>::Leaky
-    leaky_high_res_now_singleton = LAZY_INSTANCE_INITIALIZER;
-
-HighResNowSingleton* GetHighResNowSingleton() {
-  return leaky_high_res_now_singleton.Pointer();
+TimeTicks QPCNow() {
+  LARGE_INTEGER now;
+  QueryPerformanceCounter(&now);
+  return TimeTicks() + QPCValueToTimeDelta(now.QuadPart);
 }
 
-TimeDelta HighResNowWrapper() {
-  return GetHighResNowSingleton()->Now();
+bool IsBuggyAthlon(const base::CPU& cpu) {
+  // On Athlon X2 CPUs (e.g. model 15) QueryPerformanceCounter is unreliable.
+  return cpu.vendor_name() == "AuthenticAMD" && cpu.family() == 15;
 }
 
-typedef TimeDelta (*NowFunction)(void);
+void InitializeNowFunctionPointers() {
+  LARGE_INTEGER ticks_per_sec = {0};
+  if (!QueryPerformanceFrequency(&ticks_per_sec))
+    ticks_per_sec.QuadPart = 0;
 
-bool CPUReliablySupportsHighResTime() {
+  // If Windows cannot provide a QPC implementation, both Now() and
+  // NowFromSystemTraceTime() must use the low-resolution clock.
+  //
+  // If the QPC implementation is expensive and/or unreliable, Now() will use
+  // the low-resolution clock, but NowFromSystemTraceTime() will use the QPC (in
+  // the hope that it is still useful for tracing purposes). A CPU lacking a
+  // non-stop time counter will cause Windows to provide an alternate QPC
+  // implementation that works, but is expensive to use. Certain Athlon CPUs are
+  // known to make the QPC implementation unreliable.
+  //
+  // Otherwise, both Now functions can use the high-resolution QPC clock. As of
+  // 4 January 2015, ~68% of users fall within this category.
+  NowFunction now_function;
+  NowFunction system_trace_now_function;
   base::CPU cpu;
-  if (!cpu.has_non_stop_time_stamp_counter() ||
-      !GetHighResNowSingleton()->IsUsingHighResClock())
-    return false;
-
-  if (IsBuggyAthlon(cpu))
-    return false;
+  if (ticks_per_sec.QuadPart <= 0) {
+    now_function = system_trace_now_function = &RolloverProtectedNow;
+  } else if (!cpu.has_non_stop_time_stamp_counter() || IsBuggyAthlon(cpu)) {
+    now_function = &RolloverProtectedNow;
+    system_trace_now_function = &QPCNow;
+  } else {
+    now_function = system_trace_now_function = &QPCNow;
+  }
 
-  return true;
+  // Threading note 1: In an unlikely race condition, it's possible for two or
+  // more threads to enter InitializeNowFunctionPointers() in parallel. This is
+  // not a problem since all threads should end up writing out the same values
+  // to the global variables.
+  //

[cpu_(ooo_6.6-7.5), 2015/01/07 17:41:31]

remind me again why we don't simply initialize this once, cleanly when we are
single threaded?

[miu, 2015/01/07 19:20:17]

We could.  I was just sticking with what we had.

Where would the "startup one-time init" call be made?  Is there a base::Init()
or something similar already being used to initialize the library?  Also, how do
we account for startup in all other non-chrome projects/libraries?

I think we're all focused on this one-time-init threading issue where, in
reality, I doubt there ever is a race.  Nevertheless, the MemoryBarrier is a
dirt-simple solution to resolve that, and I'm sure MSAN will hound me if I'm
wrong.  ;-)

+  // Threading note 2: The store to |g_qpc_ticks_per_second| must be complete
+  // and visible to other threads before the new value for |g_now_function|
+  // becomes visible to other threads. A memory barrier is used to guarantee
+  // this ordering.
+  g_qpc_ticks_per_second = ticks_per_sec.QuadPart;
+  base::subtle::MemoryBarrier();
+  g_now_function = now_function;
+  g_system_trace_now_function = system_trace_now_function;
 }
 
-TimeDelta InitialNowFunction();
-
-volatile NowFunction now_function = InitialNowFunction;
+TimeTicks InitialNowFunction() {
+  InitializeNowFunctionPointers();
+  return g_now_function();
+}
 
-TimeDelta InitialNowFunction() {
-  if (!CPUReliablySupportsHighResTime()) {
-    InterlockedExchangePointer(
-        reinterpret_cast<void* volatile*>(&now_function),
-        &RolloverProtectedNow);
-    return RolloverProtectedNow();
-  }
-  InterlockedExchangePointer(
-        reinterpret_cast<void* volatile*>(&now_function),
-        &HighResNowWrapper);
-  return HighResNowWrapper();
+TimeTicks InitialSystemTraceNowFunction() {
+  InitializeNowFunctionPointers();
+  return g_system_trace_now_function();
 }
 
 }  // namespace
@@ -491,27 +470,24 @@ TimeDelta InitialNowFunction() {
 // static
 TimeTicks::TickFunctionType TimeTicks::SetMockTickFunction(
     TickFunctionType ticker) {
-  base::AutoLock locked(rollover_lock);
-  TickFunctionType old = tick_function;
-  tick_function = ticker;
-  rollover_ms = 0;
-  last_seen_now = 0;
+  base::AutoLock locked(g_rollover_lock);
+  TickFunctionType old = g_tick_function;
+  g_tick_function = ticker;
+  g_rollover_ms = 0;
+  g_last_seen_now = 0;
   return old;
 }
 
 // static
 TimeTicks TimeTicks::Now() {
-  return TimeTicks() + now_function();
+  return g_now_function();
 }
 
 // static
-TimeTicks TimeTicks::HighResNow() {
-  return TimeTicks() + HighResNowWrapper();
-}
-
-// static
-bool TimeTicks::IsHighResNowFastAndReliable() {
-  return CPUReliablySupportsHighResTime();
+bool TimeTicks::IsHighResolution() {
+  if (g_now_function == &InitialNowFunction)
+    InitializeNowFunctionPointers();
+  return g_now_function == &QPCNow;
 }
 
 // static
@@ -522,27 +498,17 @@ TimeTicks TimeTicks::ThreadNow() {
 
 // static
 TimeTicks TimeTicks::NowFromSystemTraceTime() {
-  return HighResNow();
-}
-
-// static
-int64 TimeTicks::GetQPCDriftMicroseconds() {
-  return GetHighResNowSingleton()->GetQPCDriftMicroseconds();
+  return g_system_trace_now_function();
 }
 
 // static
 TimeTicks TimeTicks::FromQPCValue(LONGLONG qpc_value) {
-  return TimeTicks(GetHighResNowSingleton()->QPCValueToMicroseconds(qpc_value));
-}
-
-// static
-bool TimeTicks::IsHighResClockWorking() {
-  return GetHighResNowSingleton()->IsUsingHighResClock();
+  return TimeTicks() + QPCValueToTimeDelta(qpc_value);
 }
 
 // TimeDelta ------------------------------------------------------------------
 
 // static
 TimeDelta TimeDelta::FromQPCValue(LONGLONG qpc_value) {
-  return TimeDelta(GetHighResNowSingleton()->QPCValueToMicroseconds(qpc_value));
+  return QPCValueToTimeDelta(qpc_value);
 }