Report the contended hold duration from SpinLock::SlowUnlock. SlowUnlock reported the releasing thread's own acquisition wait, which the lock-side hook already reports. Instead, store in lock word bits [31:3] when the current hold first had a sleeping waiter, and report the elapsed time at unlock against the holder's stack, like Mutex's unlocking_delay. The lock word protocol is unchanged: bits [31:3] are written at the same points and are non-zero under the same conditions. Holds resolved while waiters spin are not reported. Timestamps are CycleClock >> 7 and wrap every 2^36 cycles. PiperOrigin-RevId: 991641114
diff --git a/absl/base/internal/spinlock.cc b/absl/base/internal/spinlock.cc index d9c9687..57966d2 100644 --- a/absl/base/internal/spinlock.cc +++ b/absl/base/internal/spinlock.cc
@@ -14,10 +14,8 @@ #include "absl/base/internal/spinlock.h" -#include <algorithm> #include <atomic> #include <cstdint> -#include <limits> #include "absl/base/attributes.h" #include "absl/base/call_once.h" @@ -36,8 +34,8 @@ // [0]: kSpinLockHeld // [1]: kSpinLockCooperative // [2]: kSpinLockDisabledScheduling -// [31..3]: ONLY kSpinLockSleeper OR -// Wait time in cycles >> PROFILE_TIMESTAMP_SHIFT +// [31..3]: 0 OR +// CycleClock timestamp >> PROFILE_TIMESTAMP_SHIFT // // Detailed descriptions: // @@ -52,11 +50,13 @@ // even if non-cooperative, if a ThreadIdentity did not yet exist at // time of acquisition. // -// Bit [3]: If this is the only upper bit ([31..3]) set then this lock was -// acquired without contention, however, at least one waiter exists. -// -// Otherwise, bits [31..3] represent the time spent by the current lock -// holder to acquire the lock. There may be outstanding waiter(s). +// Bits [31..3]: If non-zero, at least one waiter may be sleeping in the kernel +// and the holder must wake a waiter when it releases the lock. The +// value is the time at which the current hold first had a sleeping +// waiter: set by the first waiter to go to sleep during the hold, or +// at acquisition by a holder that itself slept, since other sleepers +// may remain. At unlock, the holder reports the time elapsed since +// then as the contended portion of its critical section. namespace absl { ABSL_NAMESPACE_BEGIN @@ -80,9 +80,22 @@ submit_lock_profile_data.Store(fn); } -// Waits shorter than one profiling timestamp unit (see -// kProfileTimestampShift below) are not reported. -static constexpr int64_t kMinProfiledWaitCycles = 1 << 7; +// We use the upper 29 bits of the lock word to store the time at which the +// current hold first had a sleeping waiter. Since the lower bits of the cycle +// counter wrap very quickly on high-frequency processors we divide to reduce +// the granularity to 2^kProfileTimestampShift sized units. Because only 29 +// bits are stored in the 32-bit lock word (and uncontended lock() does not read +// CycleClock), SlowUnlock only knows the start time modulo 2^36 CycleClock +// ticks (=~ 34 seconds at a 2 GHz CycleClock) and cannot distinguish a wrapped +// hold to saturate. +static constexpr int kProfileTimestampShift = 7; + +// We currently reserve the lower 3 bits. +static constexpr int kLockwordReservedShift = 3; + +// Waits shorter than one timestamp unit are not reported. +static constexpr int64_t kMinProfiledWaitCycles = int64_t{1} + << kProfileTimestampShift; // Report how long an acquiring thread was blocked, measured from the point // at which it gave up spinning for the lock. @@ -138,32 +151,34 @@ // The lock was not obtained initially, so this thread needs to wait for // it. Record the current timestamp in the local variable wait_start_time - // so the total wait time can be reported once this thread obtains the lock, - // and stored in the lockword for the unlock-side profiler. + // so the total wait time can be reported once this thread obtains the lock. + // + // Once this thread has slept, it must also store a wait start time in the + // lock word when it eventually acquires the lock, since other sleepers may + // remain that only the next unlock can wake. Those sleepers cannot observe + // the new hold, so the acquiring thread records its own acquisition as the + // start of contention on behalf of them. const int64_t wait_start_time = CycleClock::Now(); int64_t now = wait_start_time; - uint32_t wait_cycles = 0; + uint32_t sleeper_bits = 0; int lock_wait_call_count = 0; while ((lock_value & kSpinLockHeld) != 0) { // If the lock is currently held, but not marked as having a sleeper, mark // it as having a sleeper. if ((lock_value & kWaitTimeMask) == 0) { - // Here, just "mark" that the thread is going to sleep. Don't store the - // lock wait time in the lock -- the lock word stores the amount of time - // that the current holder waited before acquiring the lock, not the wait - // time of any thread currently waiting to acquire it. - if (lockword_.compare_exchange_strong( - lock_value, lock_value | kSpinLockSleeper, - std::memory_order_relaxed, std::memory_order_relaxed)) { - // Successfully transitioned to kSpinLockSleeper. Pass - // kSpinLockSleeper to the SpinLockWait routine to properly indicate - // the last lock_value observed. - lock_value |= kSpinLockSleeper; + // Here, "mark" that the thread is going to sleep by recording when the + // current hold first had a sleeping waiter. + const uint32_t new_value = lock_value | EncodeWaitStart(now); + if (lockword_.compare_exchange_strong(lock_value, new_value, + std::memory_order_relaxed, + std::memory_order_relaxed)) { + // Successfully marked as having a sleeper. Pass the new value to the + // SpinLockWait routine to properly indicate the last lock_value + // observed. + lock_value = new_value; } else if ((lock_value & kSpinLockHeld) == 0) { - // Lock is free again, so try and acquire it before sleeping. The - // new lock state will be the number of cycles this thread waited if - // this thread obtains the lock. - lock_value = TryLockInternal(lock_value, wait_cycles); + // Lock is free again, so try and acquire it before sleeping. + lock_value = TryLockInternal(lock_value, sleeper_bits); continue; // Skip the delay at the end of the loop. } else if ((lock_value & kWaitTimeMask) == 0) { // The lock is still held, without a waiter being marked, but something @@ -187,68 +202,50 @@ // some chance of obtaining the lock. lock_value = SpinLoop(); now = CycleClock::Now(); - wait_cycles = EncodeWaitCycles(wait_start_time, now); - lock_value = TryLockInternal(lock_value, wait_cycles); + sleeper_bits = EncodeWaitStart(now); + lock_value = TryLockInternal(lock_value, sleeper_bits); } ReportLockWait(*this, wait_start_time, now); } void SpinLock::SlowUnlock(uint32_t lock_value) { + // Read the clock before waking a waiter, which may preempt this thread. + const int64_t now = CycleClock::Now(); SpinLockWake(&lockword_, false); // wake waiter if necessary - // If our acquisition was contended, collect contentionz profile info. We - // reserve a unitary wait time to represent that a waiter exists without our - // own acquisition having been contended. - if ((lock_value & kWaitTimeMask) != kSpinLockSleeper) { - const int64_t wait_cycles = DecodeWaitCycles(lock_value); - ABSL_TSAN_MUTEX_PRE_DIVERT(this, 0); - submit_unlock_profile_data(this, wait_cycles); - ABSL_TSAN_MUTEX_POST_DIVERT(this, 0); + // Collect contentionz profile info: for how long our critical section had a + // sleeping waiter, attributed to our stack. + const int64_t wait_cycles = DecodeWaitCycles(lock_value, now); + if (wait_cycles < kMinProfiledWaitCycles) { + return; } + ABSL_TSAN_MUTEX_PRE_DIVERT(this, 0); + submit_unlock_profile_data(this, wait_cycles); + ABSL_TSAN_MUTEX_POST_DIVERT(this, 0); } -// We use the upper 29 bits of the lock word to store the time spent waiting to -// acquire this lock. This is reported by contentionz profiling. Since the -// lower bits of the cycle counter wrap very quickly on high-frequency -// processors we divide to reduce the granularity to 2^kProfileTimestampShift -// sized units. On a 4Ghz machine this will lose track of wait times greater -// than (2^29/4 Ghz)*128 =~ 17.2 seconds. Such waits should be extremely rare. -static constexpr int kProfileTimestampShift = 7; - -// We currently reserve the lower 3 bits. -static constexpr int kLockwordReservedShift = 3; - -uint32_t SpinLock::EncodeWaitCycles(int64_t wait_start_time, - int64_t wait_end_time) { - static const int64_t kMaxWaitTime = - std::numeric_limits<uint32_t>::max() >> kLockwordReservedShift; - int64_t scaled_wait_time = - (wait_end_time - wait_start_time) >> kProfileTimestampShift; - - // Return a representation of the time spent waiting that can be stored in - // the lock word's upper bits. - uint32_t clamped = static_cast<uint32_t>( - std::min(scaled_wait_time, kMaxWaitTime) << kLockwordReservedShift); - - if (clamped == 0) { - return kSpinLockSleeper; // Just wake waiters, but don't record contention. +uint32_t SpinLock::EncodeWaitStart(int64_t now) { + uint32_t scaled_now = static_cast<uint32_t>(now >> kProfileTimestampShift) & + (kWaitTimeMask >> kLockwordReservedShift); + // Zero in kWaitTimeMask means the current hold has no sleeping waiter. If + // `now` was truncated to zero, we round to the nearest positive value to + // ensure that any sleeping waiters will be woken when the lock is released. + if (scaled_now == 0) { + scaled_now = 1; } - // Bump up value if necessary to avoid returning kSpinLockSleeper. - const uint32_t kMinWaitTime = - kSpinLockSleeper + (1 << kLockwordReservedShift); - if (clamped == kSpinLockSleeper) { - return kMinWaitTime; - } - return clamped; + return scaled_now << kLockwordReservedShift; } -int64_t SpinLock::DecodeWaitCycles(uint32_t lock_value) { - // Cast to uint32_t first to ensure bits [63:32] are cleared. - const int64_t scaled_wait_time = - static_cast<uint32_t>(lock_value & kWaitTimeMask); - return scaled_wait_time << (kProfileTimestampShift - kLockwordReservedShift); +int64_t SpinLock::DecodeWaitCycles(uint32_t lock_value, int64_t now) { + // Modular subtraction in the width of the stored timestamp. Encode `now` + // the same way as `lock_value` so a timestamp truncated to zero does not + // underflow against EncodeWaitStart's rounding to one. + const uint32_t scaled_wait_time = + (EncodeWaitStart(now) - (lock_value & kWaitTimeMask)) >> + kLockwordReservedShift; + return static_cast<int64_t>(scaled_wait_time) << kProfileTimestampShift; } } // namespace base_internal
diff --git a/absl/base/internal/spinlock.h b/absl/base/internal/spinlock.h index 82a91ad..aff0c9f 100644 --- a/absl/base/internal/spinlock.h +++ b/absl/base/internal/spinlock.h
@@ -137,8 +137,8 @@ } if ((lock_value & kWaitTimeMask) != 0) { // Collect contentionz profile info, and speed the wakeup of any waiter. - // The wait_cycles value indicates how long this thread spent waiting - // for the lock. + // The upper bits record when this thread's hold first had a sleeping + // waiter. SlowUnlock(lock_value); } ABSL_TSAN_MUTEX_POST_UNLOCK(this, 0); @@ -165,13 +165,14 @@ protected: // These should not be exported except for testing. - // Store number of cycles between wait_start_time and wait_end_time in a - // lock value. - static uint32_t EncodeWaitCycles(int64_t wait_start_time, - int64_t wait_end_time); + // Encode the CycleClock timestamp `now` into the upper bits of a lock value. + // The result is never zero. + static uint32_t EncodeWaitStart(int64_t now); - // Extract number of wait cycles in a lock value. - static int64_t DecodeWaitCycles(uint32_t lock_value); + // Return the number of cycles between the timestamp encoded in a lock value + // and `now`. Must only be called when the lock value has an encoded wait + // start. + static int64_t DecodeWaitCycles(uint32_t lock_value, int64_t now); // Provide access to protected method above. Use for testing only. friend struct SpinLockTest; @@ -195,23 +196,25 @@ // bit[1] encodes whether a lock uses cooperative scheduling. // bit[2] encodes whether the current lock holder disabled scheduling when // acquiring the lock. Only set when kSpinLockHeld is also set. - // bit[3:31] encodes time a lock spent on waiting as a 29-bit unsigned int. - // This is set by the lock holder to indicate how long it waited on - // the lock before eventually acquiring it. The number of cycles is - // encoded as a 29-bit unsigned int, or in the case that the current - // holder did not wait but another waiter is queued, the LSB - // (kSpinLockSleeper) is set. The implementation does not explicitly - // track the number of queued waiters beyond this. It must always be - // assumed that waiters may exist if the current holder was required to - // queue. + // bit[3:31] is non-zero iff a waiter may be sleeping in the kernel, in which + // case the holder must wake a waiter when it releases the lock. The + // value is a 29-bit truncated CycleClock timestamp of when the + // current hold first had a sleeping waiter: set by the first waiter + // to go to sleep during the hold, or at acquisition if the holder + // itself slept while acquiring the lock. Because unlock() clears + // these bits and wakes only one waiter without a sleeper count, a + // woken sleeper must conservatively keep them non-zero on acquisition + // in case other sleepers remain (which cannot observe the new hold). + // The holder uses this at unlock to report for how long its critical + // section blocked other threads; if the woken thread was the last + // sleeper, it reports its own hold once before its unlock() clears the + // bits. // // Invariant: if the lock is not held, the value is either 0 or // kSpinLockCooperative. static constexpr uint32_t kSpinLockHeld = 1; static constexpr uint32_t kSpinLockCooperative = 2; static constexpr uint32_t kSpinLockDisabledScheduling = 4; - static constexpr uint32_t kSpinLockSleeper = 8; - // Includes kSpinLockSleeper. static constexpr uint32_t kWaitTimeMask = ~(kSpinLockHeld | kSpinLockCooperative | kSpinLockDisabledScheduling); @@ -232,7 +235,9 @@ return lockword_.load(std::memory_order_relaxed) & kSpinLockCooperative; } - uint32_t TryLockInternal(uint32_t lock_value, uint32_t wait_cycles); + // `sleeper_bits` is 0 or the result of EncodeWaitStart() and is set in the + // lock word on a successful acquisition. + uint32_t TryLockInternal(uint32_t lock_value, uint32_t sleeper_bits); ABSL_ATTRIBUTE_COLD void SlowLock(); ABSL_ATTRIBUTE_COLD void SlowUnlock(uint32_t lock_value); uint32_t SpinLoop(); @@ -267,17 +272,20 @@ // Register hooks for profiling support. // -// The callbacks are given an opaque handle to the contended spinlock and a -// number of wait cycles as measured by -// //absl/base/internal/cycleclock.h, which may not be real "cycle" -// counts. Registration is thread-safe, but only a single profiler can be -// registered for each hook. It is an error to call these functions multiple -// times with different arguments. +// The callbacks are given an opaque handle to the spinlock and a number of +// cycles as measured by //absl/base/internal/cycleclock.h, which +// may not be real "cycle" counts. Registration is thread-safe, but only a +// single profiler can be registered for each hook. It is an error to call +// these functions multiple times with different arguments. // // The function registered with RegisterSpinLockProfiler() is called when a -// thread releases a spinlock whose acquisition was contended. `wait_cycles` is -// the time the releasing thread spent waiting to acquire the lock, as stored -// in the lock word by its acquisition. +// spinlock is released after a contended hold, i.e. when at least one other +// thread went to sleep waiting for the releasing thread to release the lock. +// `wait_cycles` is the time elapsed since the first such thread went to sleep: +// approximately the duration for which the releasing thread's critical section +// blocked other threads. Unlike Mutex, the number of blocked threads is not +// known, so this is not the sum of their waits; that sum is reported by the +// lock profiler below. void RegisterSpinLockProfiler(void (*absl_nonnull fn)( const void* absl_nonnull lock, int64_t wait_cycles)); @@ -297,7 +305,7 @@ // If (result & kSpinLockHeld) == 0, then *this was successfully locked. // Otherwise, returns last observed value for lockword_. inline uint32_t SpinLock::TryLockInternal(uint32_t lock_value, - uint32_t wait_cycles) { + uint32_t sleeper_bits) { if ((lock_value & kSpinLockHeld) != 0) { return lock_value; } @@ -313,7 +321,7 @@ if (!lockword_.compare_exchange_strong( lock_value, - kSpinLockHeld | lock_value | wait_cycles | sched_disabled_bit, + kSpinLockHeld | lock_value | sleeper_bits | sched_disabled_bit, std::memory_order_acquire, std::memory_order_relaxed)) { SchedulingGuard::EnableRescheduling(sched_disabled_bit != 0); }
diff --git a/absl/base/spinlock_profiling_test.cc b/absl/base/spinlock_profiling_test.cc index 16c1e2a..8ffc604 100644 --- a/absl/base/spinlock_profiling_test.cc +++ b/absl/base/spinlock_profiling_test.cc
@@ -35,7 +35,7 @@ // True once a waiter has marked itself as about to sleep in the lock word. static bool HasSleeper(const SpinLock& l) { return (l.lockword_.load(std::memory_order_relaxed) & - SpinLock::kSpinLockSleeper) != 0; + SpinLock::kWaitTimeMask) != 0; } }; @@ -46,9 +46,6 @@ std::atomic<int64_t> lock_profiler_cycles{0}; std::atomic<int64_t> unlock_profiler_calls{0}; std::atomic<int64_t> unlock_profiler_cycles{0}; -// Number of times the unlock profiler ran for an acquisition whose lock -// profiler had not yet run. -std::atomic<int64_t> unlock_before_lock_calls{0}; void LockProfiler(const void* lock, int64_t wait_cycles) { if (lock != profiled_lock) return; @@ -58,9 +55,6 @@ void UnlockProfiler(const void* lock, int64_t wait_cycles) { if (lock != profiled_lock) return; - if (lock_profiler_calls.load(std::memory_order_relaxed) == 0) { - unlock_before_lock_calls.fetch_add(1, std::memory_order_relaxed); - } unlock_profiler_calls.fetch_add(1, std::memory_order_relaxed); unlock_profiler_cycles.fetch_add(wait_cycles, std::memory_order_relaxed); } @@ -74,7 +68,6 @@ lock_profiler_cycles.store(0, std::memory_order_relaxed); unlock_profiler_calls.store(0, std::memory_order_relaxed); unlock_profiler_cycles.store(0, std::memory_order_relaxed); - unlock_before_lock_calls.store(0, std::memory_order_relaxed); } void TearDown() override { profiled_lock = nullptr; } @@ -85,9 +78,10 @@ profiled_lock = &spinlock; // Hold the lock until a waiter is about to sleep on it, then keep holding - // it for kContendedHoldCycles so that the waiter's wait is comfortably above - // the reporting threshold. + // it for kContendedHoldCycles so that both the waiter's wait and the + // holder's contended hold are comfortably above the reporting threshold. constexpr int64_t kContendedHoldCycles = int64_t{1} << 20; + constexpr int64_t kWaiterHoldCycles = int64_t{1} << 12; Notification held; std::thread holder([&] { spinlock.lock(); @@ -97,12 +91,17 @@ } const int64_t end = CycleClock::Now() + kContendedHoldCycles; while (CycleClock::Now() < end) { + // Keep holding the lock while the waiter sleeps on it. } spinlock.unlock(); }); held.WaitForNotification(); // Causes contention, since `holder` already holds the lock. spinlock.lock(); + const int64_t end = CycleClock::Now() + kWaiterHoldCycles; + while (CycleClock::Now() < end) { + // Hold the lock long enough for this hold to be reported as well. + } spinlock.unlock(); holder.join(); profiled_lock = nullptr; @@ -111,14 +110,12 @@ EXPECT_EQ(1, lock_profiler_calls.load(std::memory_order_relaxed)); EXPECT_GE(lock_profiler_cycles.load(std::memory_order_relaxed), kContendedHoldCycles); - // The waiter's release reported the wait stored in the lock word by its - // acquisition. The holder's acquisition was uncontended. - EXPECT_EQ(1, unlock_profiler_calls.load(std::memory_order_relaxed)); + // The holder's release reported the contended portion of its hold. The + // waiter slept, so it cannot know whether other sleepers remain and its own + // hold is also reported as contended. + EXPECT_EQ(2, unlock_profiler_calls.load(std::memory_order_relaxed)); EXPECT_GE(unlock_profiler_cycles.load(std::memory_order_relaxed), kContendedHoldCycles); - // An acquisition is reported by the lock profiler before its release is - // reported by the unlock profiler. - EXPECT_EQ(0, unlock_before_lock_calls.load(std::memory_order_relaxed)); } TEST_F(SpinLockProfiling, UncontendedAcquisitionsAreNotReported) {
diff --git a/absl/base/spinlock_test_common.cc b/absl/base/spinlock_test_common.cc index e198faf..a29a7f5 100644 --- a/absl/base/spinlock_test_common.cc +++ b/absl/base/spinlock_test_common.cc
@@ -46,12 +46,11 @@ // This is defined outside of anonymous namespace so that it can be // a friend of SpinLock to access protected methods for testing. struct SpinLockTest { - static uint32_t EncodeWaitCycles(int64_t wait_start_time, - int64_t wait_end_time) { - return SpinLock::EncodeWaitCycles(wait_start_time, wait_end_time); + static uint32_t EncodeWaitStart(int64_t now) { + return SpinLock::EncodeWaitStart(now); } - static int64_t DecodeWaitCycles(uint32_t lock_value) { - return SpinLock::DecodeWaitCycles(lock_value); + static int64_t DecodeWaitCycles(uint32_t lock_value, int64_t now) { + return SpinLock::DecodeWaitCycles(lock_value, now); } static bool IsCooperative(const SpinLock& l) { return l.IsCooperative(); } @@ -142,22 +141,21 @@ EXPECT_FALSE(base_internal::SchedulingGuard::ReschedulingIsAllowed()); } -TEST(SpinLock, WaitCyclesEncoding) { +TEST(SpinLock, WaitStartEncoding) { // These are implementation details not exported by SpinLock. const int kProfileTimestampShift = 7; const int kLockwordReservedShift = 3; - const uint32_t kSpinLockSleeper = 8; - // We should be able to encode up to (1^kMaxCycleBits - 1) without clamping - // but the lower kProfileTimestampShift will be dropped. - const int kMaxCyclesShift = - 32 - kLockwordReservedShift + kProfileTimestampShift; - const int64_t kMaxCycles = (int64_t{1} << kMaxCyclesShift) - 1; + // The encoded timestamp wraps around at 2^kWrapShift cycles, and the lower + // kProfileTimestampShift bits are dropped. + const int kWrapShift = 32 - kLockwordReservedShift + kProfileTimestampShift; + const int64_t step = (1 << kProfileTimestampShift); + const int64_t kMaxCycles = (int64_t{1} << kWrapShift) - step; // These bits should be zero after encoding. const uint32_t kLockwordReservedMask = (1 << kLockwordReservedShift) - 1; - // These bits are dropped when wait cycles are encoded. + // These bits are dropped when timestamps are encoded. const int64_t kProfileTimestampMask = (1 << kProfileTimestampShift) - 1; // Test a bunch of random values @@ -165,54 +163,55 @@ // Shift to avoid overflow below. std::uniform_int_distribution<int64_t> time_distribution( 0, std::numeric_limits<int64_t>::max() >> 3); - std::uniform_int_distribution<int64_t> cycle_distribution(0, kMaxCycles); + // Leave room for the rounding of start_time and end_time to differ. + std::uniform_int_distribution<int64_t> cycle_distribution(0, + kMaxCycles - step); for (int i = 0; i < 100; i++) { int64_t start_time = time_distribution(generator); int64_t cycles = cycle_distribution(generator); int64_t end_time = start_time + cycles; - uint32_t lock_value = SpinLockTest::EncodeWaitCycles(start_time, end_time); + uint32_t lock_value = SpinLockTest::EncodeWaitStart(start_time); EXPECT_EQ(0u, lock_value & kLockwordReservedMask); - int64_t decoded = SpinLockTest::DecodeWaitCycles(lock_value); + EXPECT_NE(0u, lock_value); + if (lock_value == (1u << kLockwordReservedShift)) { + // A timestamp whose truncation is zero encodes as one, costing one unit + // of precision; skip the exact comparison below. + continue; + } + int64_t decoded = SpinLockTest::DecodeWaitCycles(lock_value, end_time); EXPECT_EQ(0, decoded & kProfileTimestampMask); - EXPECT_EQ(cycles & ~kProfileTimestampMask, decoded); + EXPECT_EQ((end_time >> kProfileTimestampShift) - + (start_time >> kProfileTimestampShift), + decoded >> kProfileTimestampShift); + EXPECT_LT(decoded, cycles + step); + EXPECT_GT(decoded, cycles - step); } // Test corner cases int64_t start_time = time_distribution(generator); - EXPECT_EQ(kSpinLockSleeper, - SpinLockTest::EncodeWaitCycles(start_time, start_time)); - EXPECT_EQ(0, SpinLockTest::DecodeWaitCycles(0)); - EXPECT_EQ(0, SpinLockTest::DecodeWaitCycles(kLockwordReservedMask)); - EXPECT_EQ(kMaxCycles & ~kProfileTimestampMask, - SpinLockTest::DecodeWaitCycles(~kLockwordReservedMask)); + start_time &= ~kProfileTimestampMask; + uint32_t lock_value = SpinLockTest::EncodeWaitStart(start_time); + EXPECT_EQ(0, SpinLockTest::DecodeWaitCycles(lock_value, start_time)); + EXPECT_EQ(step, + SpinLockTest::DecodeWaitCycles(lock_value, start_time + step)); + EXPECT_EQ(kMaxCycles, SpinLockTest::DecodeWaitCycles( + lock_value, start_time + kMaxCycles)); + // Once the clock wraps all the way around, the elapsed time wraps to zero. + EXPECT_EQ(0, SpinLockTest::DecodeWaitCycles(lock_value, + start_time + kMaxCycles + step)); + EXPECT_EQ(step, SpinLockTest::DecodeWaitCycles( + lock_value, start_time + kMaxCycles + 2 * step)); - // Check that we cannot produce kSpinLockSleeper during encoding. - int64_t sleeper_cycles = kSpinLockSleeper - << (kProfileTimestampShift - kLockwordReservedShift); - uint32_t sleeper_value = - SpinLockTest::EncodeWaitCycles(start_time, start_time + sleeper_cycles); - EXPECT_NE(sleeper_value, kSpinLockSleeper); - - // Test clamping - uint32_t max_value = - SpinLockTest::EncodeWaitCycles(start_time, start_time + kMaxCycles); - int64_t max_value_decoded = SpinLockTest::DecodeWaitCycles(max_value); - int64_t expected_max_value_decoded = kMaxCycles & ~kProfileTimestampMask; - EXPECT_EQ(expected_max_value_decoded, max_value_decoded); - - const int64_t step = (1 << kProfileTimestampShift); - uint32_t after_max_value = SpinLockTest::EncodeWaitCycles( - start_time, start_time + kMaxCycles + step); - int64_t after_max_value_decoded = - SpinLockTest::DecodeWaitCycles(after_max_value); - EXPECT_EQ(expected_max_value_decoded, after_max_value_decoded); - - uint32_t before_max_value = SpinLockTest::EncodeWaitCycles( - start_time, start_time + kMaxCycles - step); - int64_t before_max_value_decoded = - SpinLockTest::DecodeWaitCycles(before_max_value); - EXPECT_GT(expected_max_value_decoded, before_max_value_decoded); + // A timestamp whose truncation is zero must not encode as "no waiter", and + // decoding in the same tick must return zero rather than underflowing. + EXPECT_NE(0u, SpinLockTest::EncodeWaitStart(0)); + EXPECT_EQ(0, SpinLockTest::DecodeWaitCycles(SpinLockTest::EncodeWaitStart(0), + 0)); + EXPECT_NE(0u, SpinLockTest::EncodeWaitStart(int64_t{1} << kWrapShift)); + EXPECT_EQ(0, SpinLockTest::DecodeWaitCycles( + SpinLockTest::EncodeWaitStart(int64_t{1} << kWrapShift), + int64_t{1} << kWrapShift)); } TEST(SpinLockWithThreads, StackSpinLock) {