Synchronization: Change KernelTimeout to always store absolute

timeouts, but when a relative timeout is provided, the timeout is an
absolute timeout against a steady clock (when possible). This allows
methods that return relative timeouts to automatically recompute the
remaining duration, for instance, on suprious wakeups.

PiperOrigin-RevId: 516304139
Change-Id: I7d739cb50dd749eba5dba7ac6c34d18dc53703ed

3 files changed, 72 insertions, 73 deletions

diff --git a/absl/synchronization/internal/kernel_timeout.cc b/absl/synchronization/internal/kernel_timeout.cc
index 548a8fc6..2e485097 100644
--- a/absl/synchronization/internal/kernel_timeout.cc
+++ b/absl/synchronization/internal/kernel_timeout.cc
@@ -32,6 +32,18 @@ constexpr uint64_t KernelTimeout::kNoTimeout;
 constexpr int64_t KernelTimeout::kMaxNanos;
 #endif
 
+int64_t KernelTimeout::SteadyClockNow() {
+#ifdef __GOOGLE_GRTE_VERSION__
+  // go/btm requires synchronized clocks, so we have to use the system
+  // clock.
+  return absl::GetCurrentTimeNanos();
+#else
+  return std::chrono::duration_cast<std::chrono::nanoseconds>(
+             std::chrono::steady_clock::now().time_since_epoch())
+      .count();
+#endif
+}
+
 KernelTimeout::KernelTimeout(absl::Time t) {
   // `absl::InfiniteFuture()` is a common "no timeout" value and cheaper to
   // compare than convert.
@@ -73,12 +85,14 @@ KernelTimeout::KernelTimeout(absl::Duration d) {
     nanos = 0;
   }
 
-  // Values greater than or equal to kMaxNanos are converted to infinite.
-  if (nanos >= kMaxNanos) {
+  int64_t now = SteadyClockNow();
+  if (nanos > kMaxNanos - now) {
+    // Durations that would be greater than kMaxNanos are converted to infinite.
     rep_ = kNoTimeout;
     return;
   }
 
+  nanos += now;
   rep_ = (static_cast<uint64_t>(nanos) << 1) | uint64_t{1};
 }
 
@@ -90,6 +104,9 @@ int64_t KernelTimeout::MakeAbsNanos() const {
   int64_t nanos = RawNanos();
 
   if (is_relative_timeout()) {
+    // We need to change epochs, because the relative timeout might be
+    // represented by an absolute timestamp from another clock.
+    nanos = std::max<int64_t>(nanos - SteadyClockNow(), 0);
     int64_t now = absl::GetCurrentTimeNanos();
     if (nanos > kMaxNanos - now) {
       // Overflow.
@@ -106,27 +123,24 @@ int64_t KernelTimeout::MakeAbsNanos() const {
   return nanos;
 }
 
-struct timespec KernelTimeout::MakeAbsTimespec() const {
-  return absl::ToTimespec(absl::Nanoseconds(MakeAbsNanos()));
-}
-
-struct timespec KernelTimeout::MakeRelativeTimespec() const {
+int64_t KernelTimeout::InNanosecondsFromNow() const {
   if (!has_timeout()) {
-    return absl::ToTimespec(absl::Nanoseconds(kMaxNanos));
-  }
-  if (is_relative_timeout()) {
-    return absl::ToTimespec(absl::Nanoseconds(RawNanos()));
+    return kMaxNanos;
   }
 
   int64_t nanos = RawNanos();
-  int64_t now = absl::GetCurrentTimeNanos();
-  if (now > nanos) {
-    // Convert past values to 0 to be safe.
-    nanos = 0;
-  } else {
-    nanos -= now;
+  if (is_absolute_timeout()) {
+    return std::max<int64_t>(nanos - absl::GetCurrentTimeNanos(), 0);
   }
-  return absl::ToTimespec(absl::Nanoseconds(nanos));
+  return std::max<int64_t>(nanos - SteadyClockNow(), 0);
+}
+
+struct timespec KernelTimeout::MakeAbsTimespec() const {
+  return absl::ToTimespec(absl::Nanoseconds(MakeAbsNanos()));
+}
+
+struct timespec KernelTimeout::MakeRelativeTimespec() const {
+  return absl::ToTimespec(absl::Nanoseconds(InNanosecondsFromNow()));
 }
 
 KernelTimeout::DWord KernelTimeout::InMillisecondsFromNow() const {
@@ -136,32 +150,21 @@ KernelTimeout::DWord KernelTimeout::InMillisecondsFromNow() const {
     return kInfinite;
   }
 
-  const int64_t nanos = RawNanos();
-  constexpr uint64_t kNanosInMillis = uint64_t{1000000};
+  constexpr uint64_t kNanosInMillis = uint64_t{1'000'000};
+  constexpr uint64_t kMaxValueNanos =
+      std::numeric_limits<int64_t>::max() - kNanosInMillis + 1;
 
-  if (is_relative_timeout()) {
-    uint64_t ms = static_cast<uint64_t>(nanos) / kNanosInMillis;
-    if (ms > static_cast<uint64_t>(kInfinite)) {
-      ms = static_cast<uint64_t>(kInfinite);
-    }
-    return static_cast<DWord>(ms);
+  uint64_t ns_from_now = static_cast<uint64_t>(InNanosecondsFromNow());
+  if (ns_from_now >= kMaxValueNanos) {
+    // Rounding up would overflow.
+    return kInfinite;
   }
-
-  int64_t now = absl::GetCurrentTimeNanos();
-  if (nanos >= now) {
-    // Round up so that now + ms_from_now >= nanos.
-    constexpr uint64_t kMaxValueNanos =
-        std::numeric_limits<int64_t>::max() - kNanosInMillis + 1;
-    uint64_t ms_from_now =
-        (std::min(kMaxValueNanos, static_cast<uint64_t>(nanos - now)) +
-         kNanosInMillis - 1) /
-        kNanosInMillis;
-    if (ms_from_now > kInfinite) {
-      return kInfinite;
-    }
-    return static_cast<DWord>(ms_from_now);
+  // Convert to milliseconds, always rounding up.
+  uint64_t ms_from_now = (ns_from_now + kNanosInMillis - 1) / kNanosInMillis;
+  if (ms_from_now > kInfinite) {
+    return kInfinite;
   }
-  return DWord{0};
+  return static_cast<DWord>(ms_from_now);
 }
 
 std::chrono::time_point<std::chrono::system_clock>
@@ -174,16 +177,7 @@ KernelTimeout::ToChronoTimePoint() const {
   // std::ratio used by std::chrono::steady_clock doesn't convert to
   // std::nanoseconds, so it doesn't compile.
   auto micros = std::chrono::duration_cast<std::chrono::microseconds>(
-      std::chrono::nanoseconds(RawNanos()));
-  if (is_relative_timeout()) {
-    auto now = std::chrono::system_clock::now();
-    if (micros >
-        std::chrono::time_point<std::chrono::system_clock>::max() - now) {
-      // Overflow.
-      return std::chrono::time_point<std::chrono::system_clock>::max();
-    }
-    return now + micros;
-  }
+      std::chrono::nanoseconds(MakeAbsNanos()));
   return std::chrono::system_clock::from_time_t(0) + micros;
 }
 
@@ -191,17 +185,7 @@ std::chrono::nanoseconds KernelTimeout::ToChronoDuration() const {
   if (!has_timeout()) {
     return std::chrono::nanoseconds::max();
   }
-  if (is_absolute_timeout()) {
-    auto d = std::chrono::duration_cast<std::chrono::nanoseconds>(
-        std::chrono::nanoseconds(RawNanos()) -
-        (std::chrono::system_clock::now() -
-         std::chrono::system_clock::from_time_t(0)));
-    if (d < std::chrono::nanoseconds(0)) {
-      d = std::chrono::nanoseconds(0);
-    }
-    return d;
-  }
-  return std::chrono::nanoseconds(RawNanos());
+  return std::chrono::nanoseconds(InNanosecondsFromNow());
 }
 
 }  // namespace synchronization_internal
diff --git a/absl/synchronization/internal/kernel_timeout.h b/absl/synchronization/internal/kernel_timeout.h
index f7c40337..e2cf3c2a 100644
--- a/absl/synchronization/internal/kernel_timeout.h
+++ b/absl/synchronization/internal/kernel_timeout.h
@@ -75,7 +75,9 @@ class KernelTimeout {
   // Convert to `struct timespec` for interfaces that expect a relative
   // timeout. If !has_timeout() or is_absolute_timeout(), attempts to convert to
   // a reasonable relative timeout, but callers should to test has_timeout() and
-  // is_absolute_timeout() and prefer to use a more appropriate interface.
+  // is_absolute_timeout() and prefer to use a more appropriate interface. Since
+  // the return value is a relative duration, it should be recomputed by calling
+  // this method in the case of a spurious wakeup.
   struct timespec MakeRelativeTimespec() const;
 
   // Convert to unix epoch nanos for interfaces that expect an absolute timeout
@@ -107,17 +109,24 @@ class KernelTimeout {
   // timeout, like std::condition_variable::wait_for(). If !has_timeout() or
   // is_absolute_timeout(), attempts to convert to a reasonable relative
   // timeout, but callers should test has_timeout() and is_absolute_timeout()
-  // and prefer to use a more appropriate interface.
+  // and prefer to use a more appropriate interface. Since the return value is a
+  // relative duration, it should be recomputed by calling this method in the
+  // case of a spurious wakeup.
   std::chrono::nanoseconds ToChronoDuration() const;
 
  private:
+  // Returns the current time, expressed as a count of nanoseconds since the
+  // epoch used by an arbitrary clock. The implementation tries to use a steady
+  // (monotonic) clock if one is available.
+  static int64_t SteadyClockNow();
+
   // Internal representation.
   //   - If the value is kNoTimeout, then the timeout is infinite, and
   //     has_timeout() will return true.
-  //   - If the low bit is 0, then the high 63 bits is number of nanoseconds
+  //   - If the low bit is 0, then the high 63 bits is the number of nanoseconds
   //     after the unix epoch.
-  //   - If the low bit is 1, then the high 63 bits is a relative duration in
-  //     nanoseconds.
+  //   - If the low bit is 1, then the high 63 bits is the number of nanoseconds
+  //     after the epoch used by SteadyClockNow().
   uint64_t rep_;
 
   // Returns the number of nanoseconds stored in the internal representation.
@@ -125,6 +134,11 @@ class KernelTimeout {
   // value is used to compute when the timeout should occur.
   int64_t RawNanos() const { return static_cast<int64_t>(rep_ >> 1); }
 
+  // Converts to nanoseconds from now. Since the return value is a relative
+  // duration, it should be recomputed by calling this method in the case of a
+  // spurious wakeup.
+  int64_t InNanosecondsFromNow() const;
+
   // A value that represents no timeout (or an infinite timeout).
   static constexpr uint64_t kNoTimeout = (std::numeric_limits<uint64_t>::max)();
 
diff --git a/absl/synchronization/internal/kernel_timeout_test.cc b/absl/synchronization/internal/kernel_timeout_test.cc
index 431ffcf4..a96f806f 100644
--- a/absl/synchronization/internal/kernel_timeout_test.cc
+++ b/absl/synchronization/internal/kernel_timeout_test.cc
@@ -62,9 +62,6 @@ TEST(KernelTimeout, FiniteTimes) {
     EXPECT_TRUE(t.is_absolute_timeout());
     EXPECT_FALSE(t.is_relative_timeout());
     EXPECT_EQ(absl::TimeFromTimespec(t.MakeAbsTimespec()), when);
-    // MakeRelativeTimespec() doesn't quite round trip when using an absolute
-    // time, but it should get pretty close. Past times are converted to zero
-    // durations.
     EXPECT_LE(
         absl::AbsDuration(absl::DurationFromTimespec(t.MakeRelativeTimespec()) -
                           std::max(duration, absl::ZeroDuration())),
@@ -201,7 +198,10 @@ TEST(KernelTimeout, FiniteDurations) {
     EXPECT_LE(absl::AbsDuration(absl::Now() + duration -
                                 absl::TimeFromTimespec(t.MakeAbsTimespec())),
               absl::Milliseconds(5));
-    EXPECT_EQ(absl::DurationFromTimespec(t.MakeRelativeTimespec()), duration);
+    EXPECT_LE(
+        absl::AbsDuration(absl::DurationFromTimespec(t.MakeRelativeTimespec()) -
+                          duration),
+        kTimingBound);
     EXPECT_LE(absl::AbsDuration(absl::Now() + duration -
                                 absl::FromUnixNanos(t.MakeAbsNanos())),
               absl::Milliseconds(5));
@@ -210,7 +210,9 @@ TEST(KernelTimeout, FiniteDurations) {
     EXPECT_LE(absl::AbsDuration(absl::Now() + duration -
                                 absl::FromChrono(t.ToChronoTimePoint())),
               kTimingBound);
-    EXPECT_EQ(absl::FromChrono(t.ToChronoDuration()), duration);
+    EXPECT_LE(
+        absl::AbsDuration(absl::FromChrono(t.ToChronoDuration()) - duration),
+        kTimingBound);
   }
 }
 
@@ -298,7 +300,6 @@ TEST(KernelTimeout, OverflowNanos) {
   int64_t limit = std::numeric_limits<int64_t>::max() - now_nanos;
   absl::Duration duration = absl::Nanoseconds(limit) + absl::Seconds(1);
   KernelTimeout t(duration);
-  EXPECT_TRUE(t.has_timeout());
   // Timeouts should still be far in the future.
   EXPECT_GT(absl::TimeFromTimespec(t.MakeAbsTimespec()),
             absl::Now() + absl::Hours(100000));