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

base/time/time_win.cc

 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 
 // Windows Timer Primer
 //
 // A good article:  http://www.ddj.com/windows/184416651
 // A good mozilla bug:  http://bugzilla.mozilla.org/show_bug.cgi?id=363258
 //
@@ skipping 19 matching lines @@
 // To work around all this, we're going to generally use timeGetTime().  We
 // will only increase the system-wide timer if we're not running on battery
 // power.
 
 #include "base/time/time.h"
 
 #pragma comment(lib, "winmm.lib")
 #include <windows.h>
 #include <mmsystem.h>
 
+#include <atomic>
+
 #include "base/basictypes.h"
 #include "base/cpu.h"
 #include "base/lazy_instance.h"
 #include "base/logging.h"
 #include "base/synchronization/lock.h"
 
 using base::Time;
 using base::TimeDelta;
 using base::TimeTicks;
 
@@ skipping 126 matching lines @@
   if (g_high_res_timer_enabled == enable)
     return;
   g_high_res_timer_enabled = enable;
   if (!g_high_res_timer_count)
     return;
   // Since g_high_res_timer_count != 0, an ActivateHighResolutionTimer(true)
   // was called which called timeBeginPeriod with g_high_res_timer_enabled
   // with a value which is the opposite of |enable|. With that information we
   // call timeEndPeriod with the same value used in timeBeginPeriod and
   // therefore undo the period effect.
+
   if (enable) {
     timeEndPeriod(kMinTimerIntervalLowResMs);
     timeBeginPeriod(kMinTimerIntervalHighResMs);
   } else {
     timeEndPeriod(kMinTimerIntervalHighResMs);
     timeBeginPeriod(kMinTimerIntervalLowResMs);
   }
 }
 
 // static
@@ skipping 104 matching lines @@
 // TimeTicks ------------------------------------------------------------------
 namespace {
 
 // We define a wrapper to adapt between the __stdcall and __cdecl call of the
 // mock function, and to avoid a static constructor.  Assigning an import to a
 // function pointer directly would require setup code to fetch from the IAT.
 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
 // code is low-level, and we don't want to use Singletons here (it would be too
 // 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
-// be used in production. Its biggest issue is that it is per processor and it
-// is not synchronized between processors. Also, on some computers, the counters
-// will change frequency due to thermal and power changes, and stop in some
-// states.
+// expensive to retrieve. However, on older CPUs, two issues can affect its
+// reliability: First it is maintained per processor and not synchronized
+// between processors. Also, the counters will change frequency due to thermal
+// and power changes, and stop in some states.
 //
 // (2) QueryPerformanceCounter (QPC). The QPC counter provides a high-
-// resolution (100 nanoseconds) time stamp but is comparatively more expensive
-// to retrieve. What QueryPerformanceCounter actually does is up to the HAL.
-// (with some help from ACPI).
-// According to http://blogs.msdn.com/oldnewthing/archive/2005/09/02/459952.aspx
-// in the worst case, it gets the counter from the rollover interrupt on the
+// resolution (<1 microsecond) time stamp. On most hardware running today, it
+// auto-detects and uses the constant-rate RDTSC counter to provide extremely
+// efficient and reliable time stamps.
+//
+// On older CPUs where RDTSC is unreliable, it falls back to using more
+// expensive (20X to 40X more costly) alternate clocks, such as HPET or the ACPI
+// PM timer, and can involve system calls; and all this is up to the HAL (with
+// some help from ACPI). According to
+// http://blogs.msdn.com/oldnewthing/archive/2005/09/02/459952.aspx, in the
+// worst case, it gets the counter from the rollover interrupt on the
 // programmable interrupt timer. In best cases, the HAL may conclude that the
 // RDTSC counter runs at a constant frequency, then it uses that instead. On
 // multiprocessor machines, it will try to verify the values returned from
 // RDTSC on each processor are consistent with each other, and apply a handful
 // of workarounds for known buggy hardware. In other words, QPC is supposed to
-// give consistent result on a multiprocessor computer, but it is unreliable in
-// reality due to bugs in BIOS or HAL on some, especially old computers.
-// With recent updates on HAL and newer BIOS, QPC is getting more reliable but
-// it should be used with caution.
+// give consistent results on a multiprocessor computer, but for older CPUs it
+// can be unreliable due bugs in BIOS or HAL.
 //
-// (3) System time. The system time provides a low-resolution (typically 10ms
-// to 55 milliseconds) time stamp but is comparatively less expensive to
-// retrieve and more reliable.
-class HighResNowSingleton {
- public:
-  HighResNowSingleton()
-      : ticks_per_second_(0),
-        skew_(0) {
+// (3) System time. The system time provides a low-resolution (from ~1 to ~15.6
+// milliseconds) time stamp but is comparatively less expensive to retrieve and
+// more reliable. Time::EnableHighResolutionTimer() and
+// Time::ActivateHighResolutionTimer() can be called to alter the resolution of
+// this timer; and also other Windows applications can alter it, affecting this
+// one.
 
-    base::CPU cpu;
-    if (IsBuggyAthlon(cpu))
-      return;
+using NowFunction = TimeTicks (*)(void);
 
-    // 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;
+TimeTicks InitialNowFunction();
+TimeTicks InitialSystemTraceNowFunction();
 
-    skew_ = UnreliableNow() - ReliableNow();
+// 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;
+std::atomic<int64> g_qpc_ticks_per_second;
+
+TimeDelta QPCValueToTimeDelta(LONGLONG qpc_value) {
+  const int64 qpc_ticks_per_second =
+      g_qpc_ticks_per_second.load(std::memory_order_acquire);
+  DCHECK_GT(qpc_ticks_per_second, 0);
+
+  // 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 / qpc_ticks_per_second);
+  }
+  // Otherwise, calculate microseconds in a round about manner to avoid
+  // overflow and precision issues.
+  int64 whole_seconds = qpc_value / qpc_ticks_per_second;
+  int64 leftover_ticks = qpc_value - (whole_seconds * qpc_ticks_per_second);
+  return TimeDelta::FromMicroseconds(
+      (whole_seconds * Time::kMicrosecondsPerSecond) +
+      ((leftover_ticks * Time::kMicrosecondsPerSecond) /
+       qpc_ticks_per_second));
+}
+
+TimeTicks QPCNow() {
+  LARGE_INTEGER now;
+  QueryPerformanceCounter(&now);
+  return TimeTicks() + QPCValueToTimeDelta(now.QuadPart);
+}
+
+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;
+}
+
+void InitializeNowFunctionPointers() {
+  LARGE_INTEGER ticks_per_sec = {0};
+  if (!QueryPerformanceFrequency(&ticks_per_sec))
+    ticks_per_sec.QuadPart = 0;
+
+  // 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 (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;
   }
 
-  bool IsUsingHighResClock() {
-    return ticks_per_second_ != 0;
-  }
-
-  TimeDelta Now() {
-    if (IsUsingHighResClock())
-      return TimeDelta::FromMicroseconds(UnreliableNow());
-
-    // Just fallback to the slower clock.
-    return RolloverProtectedNow();
-  }
-
-  int64 GetQPCDriftMicroseconds() {
-    if (!IsUsingHighResClock())
-      return 0;
-    return abs((UnreliableNow() - ReliableNow()) - skew_);
-  }
-
-  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;
-  }
-
- private:
-  // Get the number of microseconds since boot in an unreliable fashion.
-  int64 UnreliableNow() {
-    LARGE_INTEGER now;
-    QueryPerformanceCounter(&now);
-    return QPCValueToMicroseconds(now.QuadPart);
-  }
-
-  // Get the number of microseconds since boot in a reliable fashion.
-  int64 ReliableNow() {
-    return RolloverProtectedNow().InMicroseconds();
-  }
-
-  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();
+  // 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.
+  //
+  // Threading note 2: The memory store to |g_qpc_ticks_per_second| must be
+  // atomic and visible to other threads before the new value for
+  // |g_now_function| becomes visible to other threads. Memory ordering
+  // constraints are used here and where |g_qpc_ticks_per_second| is read in
+  // QPCValueToTimeDelta() to guarantee this.
+  g_qpc_ticks_per_second.store(ticks_per_sec.QuadPart,
+                               std::memory_order_release);

[brucedawson, 2015/01/08 01:36:57]

I *think* this is wrong. I believe that it is the write to g_now_function that
needs std::memory_order_release. g_qpc_ticks_per_second is the payload, and
g_now_function is the flag that makes it available, so g_now_function is what is
releasing access to g_qpc_ticks_per_second.

See the example from the top of one of my favorite lockless resources:

http://preshing.com/20131125/acquire-and-release-fences-dont-work-the-way-you...

This would mean that reads from g_now_function would need the
std::memory_order_acquire.

See also:
http://preshing.com/20130823/the-synchronizes-with-relation/

Note that the alternative is to use
std::atomic_thread_fence(std::memory_order_acquire); and
std::atomic_thread_fence(std::memory_order_release);, placing these between the
reads and between the writes. The acquire fence could either go right before the
read of g_qpc_ticks_per_second or right after the read of g_now_function --
whichever is most convenient.

All this debate over a race that in practice might never happen. Such fun.

[miu, 2015/01/08 03:15:45]

Ah, yes.  I understand now.  I fixed this by using the
std::atomic_thread_fence() approach, as it turned out to be much simpler.

+  g_now_function = now_function;
+  g_system_trace_now_function = system_trace_now_function;
 }
 
-TimeDelta HighResNowWrapper() {
-  return GetHighResNowSingleton()->Now();
+TimeTicks InitialNowFunction() {
+  InitializeNowFunctionPointers();
+  return g_now_function();
 }
 
-typedef TimeDelta (*NowFunction)(void);
-
-bool CPUReliablySupportsHighResTime() {
-  base::CPU cpu;
-  if (!cpu.has_non_stop_time_stamp_counter() ||
-      !GetHighResNowSingleton()->IsUsingHighResClock())
-    return false;
-
-  if (IsBuggyAthlon(cpu))
-    return false;
-
-  return true;
-}
-
-TimeDelta InitialNowFunction();
-
-volatile NowFunction now_function = InitialNowFunction;
-
-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
 
 // 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();
+bool TimeTicks::IsHighResolution() {
+  if (g_now_function == &InitialNowFunction)
+    InitializeNowFunctionPointers();
+  return g_now_function == &QPCNow;
 }
 
 // static
-bool TimeTicks::IsHighResNowFastAndReliable() {
-  return CPUReliablySupportsHighResTime();
-}
-
-// static
 TimeTicks TimeTicks::ThreadNow() {
   NOTREACHED();
   return TimeTicks();
 }
 
 // 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);
 }