diff options
author | anastasy888 <anastasy888@yandex-team.ru> | 2022-02-10 16:45:54 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:54 +0300 |
commit | 49f765d71da452ea93138a25559dfa68dd76c7f3 (patch) | |
tree | 1016041feb637349e401dcc0fa85217dd2c2c639 /contrib/restricted/abseil-cpp-tstring/y_absl/time/clock.cc | |
parent | 7353a3fdea9c67c256980c00a2b3b67f09b23a27 (diff) | |
download | ydb-49f765d71da452ea93138a25559dfa68dd76c7f3.tar.gz |
Restoring authorship annotation for <anastasy888@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'contrib/restricted/abseil-cpp-tstring/y_absl/time/clock.cc')
-rw-r--r-- | contrib/restricted/abseil-cpp-tstring/y_absl/time/clock.cc | 800 |
1 files changed, 400 insertions, 400 deletions
diff --git a/contrib/restricted/abseil-cpp-tstring/y_absl/time/clock.cc b/contrib/restricted/abseil-cpp-tstring/y_absl/time/clock.cc index dcc12b5633..d29b8e89d0 100644 --- a/contrib/restricted/abseil-cpp-tstring/y_absl/time/clock.cc +++ b/contrib/restricted/abseil-cpp-tstring/y_absl/time/clock.cc @@ -1,178 +1,178 @@ -// Copyright 2017 The Abseil Authors. -// -// Licensed under the Apache License, Version 2.0 (the "License"); -// you may not use this file except in compliance with the License. -// You may obtain a copy of the License at -// -// https://www.apache.org/licenses/LICENSE-2.0 -// -// Unless required by applicable law or agreed to in writing, software -// distributed under the License is distributed on an "AS IS" BASIS, -// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. -// See the License for the specific language governing permissions and -// limitations under the License. - +// Copyright 2017 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + #include "y_absl/time/clock.h" - + #include "y_absl/base/attributes.h" #include "y_absl/base/optimization.h" - -#ifdef _WIN32 -#include <windows.h> -#endif - -#include <algorithm> -#include <atomic> -#include <cerrno> -#include <cstdint> -#include <ctime> -#include <limits> - + +#ifdef _WIN32 +#include <windows.h> +#endif + +#include <algorithm> +#include <atomic> +#include <cerrno> +#include <cstdint> +#include <ctime> +#include <limits> + #include "y_absl/base/internal/spinlock.h" #include "y_absl/base/internal/unscaledcycleclock.h" #include "y_absl/base/macros.h" #include "y_absl/base/port.h" #include "y_absl/base/thread_annotations.h" - + namespace y_absl { ABSL_NAMESPACE_BEGIN -Time Now() { - // TODO(bww): Get a timespec instead so we don't have to divide. +Time Now() { + // TODO(bww): Get a timespec instead so we don't have to divide. int64_t n = y_absl::GetCurrentTimeNanos(); - if (n >= 0) { - return time_internal::FromUnixDuration( - time_internal::MakeDuration(n / 1000000000, n % 1000000000 * 4)); - } + if (n >= 0) { + return time_internal::FromUnixDuration( + time_internal::MakeDuration(n / 1000000000, n % 1000000000 * 4)); + } return time_internal::FromUnixDuration(y_absl::Nanoseconds(n)); -} +} ABSL_NAMESPACE_END } // namespace y_absl - -// Decide if we should use the fast GetCurrentTimeNanos() algorithm -// based on the cyclecounter, otherwise just get the time directly -// from the OS on every call. This can be chosen at compile-time via -// -DABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS=[0|1] -#ifndef ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS -#if ABSL_USE_UNSCALED_CYCLECLOCK -#define ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS 1 -#else -#define ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS 0 -#endif -#endif - -#if defined(__APPLE__) || defined(_WIN32) + +// Decide if we should use the fast GetCurrentTimeNanos() algorithm +// based on the cyclecounter, otherwise just get the time directly +// from the OS on every call. This can be chosen at compile-time via +// -DABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS=[0|1] +#ifndef ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS +#if ABSL_USE_UNSCALED_CYCLECLOCK +#define ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS 1 +#else +#define ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS 0 +#endif +#endif + +#if defined(__APPLE__) || defined(_WIN32) #include "y_absl/time/internal/get_current_time_chrono.inc" -#else +#else #include "y_absl/time/internal/get_current_time_posix.inc" -#endif - -// Allows override by test. -#ifndef GET_CURRENT_TIME_NANOS_FROM_SYSTEM -#define GET_CURRENT_TIME_NANOS_FROM_SYSTEM() \ +#endif + +// Allows override by test. +#ifndef GET_CURRENT_TIME_NANOS_FROM_SYSTEM +#define GET_CURRENT_TIME_NANOS_FROM_SYSTEM() \ ::y_absl::time_internal::GetCurrentTimeNanosFromSystem() -#endif - -#if !ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS +#endif + +#if !ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS namespace y_absl { ABSL_NAMESPACE_BEGIN int64_t GetCurrentTimeNanos() { return GET_CURRENT_TIME_NANOS_FROM_SYSTEM(); } ABSL_NAMESPACE_END } // namespace y_absl -#else // Use the cyclecounter-based implementation below. - -// Allows override by test. -#ifndef GET_CURRENT_TIME_NANOS_CYCLECLOCK_NOW -#define GET_CURRENT_TIME_NANOS_CYCLECLOCK_NOW() \ +#else // Use the cyclecounter-based implementation below. + +// Allows override by test. +#ifndef GET_CURRENT_TIME_NANOS_CYCLECLOCK_NOW +#define GET_CURRENT_TIME_NANOS_CYCLECLOCK_NOW() \ ::y_absl::time_internal::UnscaledCycleClockWrapperForGetCurrentTime::Now() -#endif - +#endif + namespace y_absl { ABSL_NAMESPACE_BEGIN -namespace time_internal { -// This is a friend wrapper around UnscaledCycleClock::Now() -// (needed to access UnscaledCycleClock). -class UnscaledCycleClockWrapperForGetCurrentTime { - public: - static int64_t Now() { return base_internal::UnscaledCycleClock::Now(); } -}; -} // namespace time_internal - -// uint64_t is used in this module to provide an extra bit in multiplications - -// --------------------------------------------------------------------- -// An implementation of reader-write locks that use no atomic ops in the read -// case. This is a generalization of Lamport's method for reading a multiword -// clock. Increment a word on each write acquisition, using the low-order bit -// as a spinlock; the word is the high word of the "clock". Readers read the -// high word, then all other data, then the high word again, and repeat the -// read if the reads of the high words yields different answers, or an odd -// value (either case suggests possible interference from a writer). -// Here we use a spinlock to ensure only one writer at a time, rather than -// spinning on the bottom bit of the word to benefit from SpinLock -// spin-delay tuning. - -// Acquire seqlock (*seq) and return the value to be written to unlock. -static inline uint64_t SeqAcquire(std::atomic<uint64_t> *seq) { - uint64_t x = seq->fetch_add(1, std::memory_order_relaxed); - - // We put a release fence between update to *seq and writes to shared data. - // Thus all stores to shared data are effectively release operations and - // update to *seq above cannot be re-ordered past any of them. Note that - // this barrier is not for the fetch_add above. A release barrier for the - // fetch_add would be before it, not after. - std::atomic_thread_fence(std::memory_order_release); - - return x + 2; // original word plus 2 -} - -// Release seqlock (*seq) by writing x to it---a value previously returned by -// SeqAcquire. -static inline void SeqRelease(std::atomic<uint64_t> *seq, uint64_t x) { - // The unlock store to *seq must have release ordering so that all - // updates to shared data must finish before this store. - seq->store(x, std::memory_order_release); // release lock for readers -} - -// --------------------------------------------------------------------- - -// "nsscaled" is unit of time equal to a (2**kScale)th of a nanosecond. -enum { kScale = 30 }; - -// The minimum interval between samples of the time base. -// We pick enough time to amortize the cost of the sample, -// to get a reasonably accurate cycle counter rate reading, -// and not so much that calculations will overflow 64-bits. -static const uint64_t kMinNSBetweenSamples = 2000 << 20; - -// We require that kMinNSBetweenSamples shifted by kScale -// have at least a bit left over for 64-bit calculations. -static_assert(((kMinNSBetweenSamples << (kScale + 1)) >> (kScale + 1)) == - kMinNSBetweenSamples, - "cannot represent kMaxBetweenSamplesNSScaled"); - -// data from a sample of the kernel's time value -struct TimeSampleAtomic { +namespace time_internal { +// This is a friend wrapper around UnscaledCycleClock::Now() +// (needed to access UnscaledCycleClock). +class UnscaledCycleClockWrapperForGetCurrentTime { + public: + static int64_t Now() { return base_internal::UnscaledCycleClock::Now(); } +}; +} // namespace time_internal + +// uint64_t is used in this module to provide an extra bit in multiplications + +// --------------------------------------------------------------------- +// An implementation of reader-write locks that use no atomic ops in the read +// case. This is a generalization of Lamport's method for reading a multiword +// clock. Increment a word on each write acquisition, using the low-order bit +// as a spinlock; the word is the high word of the "clock". Readers read the +// high word, then all other data, then the high word again, and repeat the +// read if the reads of the high words yields different answers, or an odd +// value (either case suggests possible interference from a writer). +// Here we use a spinlock to ensure only one writer at a time, rather than +// spinning on the bottom bit of the word to benefit from SpinLock +// spin-delay tuning. + +// Acquire seqlock (*seq) and return the value to be written to unlock. +static inline uint64_t SeqAcquire(std::atomic<uint64_t> *seq) { + uint64_t x = seq->fetch_add(1, std::memory_order_relaxed); + + // We put a release fence between update to *seq and writes to shared data. + // Thus all stores to shared data are effectively release operations and + // update to *seq above cannot be re-ordered past any of them. Note that + // this barrier is not for the fetch_add above. A release barrier for the + // fetch_add would be before it, not after. + std::atomic_thread_fence(std::memory_order_release); + + return x + 2; // original word plus 2 +} + +// Release seqlock (*seq) by writing x to it---a value previously returned by +// SeqAcquire. +static inline void SeqRelease(std::atomic<uint64_t> *seq, uint64_t x) { + // The unlock store to *seq must have release ordering so that all + // updates to shared data must finish before this store. + seq->store(x, std::memory_order_release); // release lock for readers +} + +// --------------------------------------------------------------------- + +// "nsscaled" is unit of time equal to a (2**kScale)th of a nanosecond. +enum { kScale = 30 }; + +// The minimum interval between samples of the time base. +// We pick enough time to amortize the cost of the sample, +// to get a reasonably accurate cycle counter rate reading, +// and not so much that calculations will overflow 64-bits. +static const uint64_t kMinNSBetweenSamples = 2000 << 20; + +// We require that kMinNSBetweenSamples shifted by kScale +// have at least a bit left over for 64-bit calculations. +static_assert(((kMinNSBetweenSamples << (kScale + 1)) >> (kScale + 1)) == + kMinNSBetweenSamples, + "cannot represent kMaxBetweenSamplesNSScaled"); + +// data from a sample of the kernel's time value +struct TimeSampleAtomic { std::atomic<uint64_t> raw_ns{0}; // raw kernel time std::atomic<uint64_t> base_ns{0}; // our estimate of time std::atomic<uint64_t> base_cycles{0}; // cycle counter reading std::atomic<uint64_t> nsscaled_per_cycle{0}; // cycle period - // cycles before we'll sample again (a scaled reciprocal of the period, - // to avoid a division on the fast path). + // cycles before we'll sample again (a scaled reciprocal of the period, + // to avoid a division on the fast path). std::atomic<uint64_t> min_cycles_per_sample{0}; -}; -// Same again, but with non-atomic types -struct TimeSample { +}; +// Same again, but with non-atomic types +struct TimeSample { uint64_t raw_ns = 0; // raw kernel time uint64_t base_ns = 0; // our estimate of time uint64_t base_cycles = 0; // cycle counter reading uint64_t nsscaled_per_cycle = 0; // cycle period uint64_t min_cycles_per_sample = 0; // approx cycles before next sample -}; - +}; + struct ABSL_CACHELINE_ALIGNED TimeState { std::atomic<uint64_t> seq{0}; TimeSampleAtomic last_sample; // the last sample; under seq - + // The following counters are used only by the test code. int64_t stats_initializations{0}; int64_t stats_reinitializations{0}; @@ -255,205 +255,205 @@ static int64_t GetCurrentTimeNanosFromKernel(uint64_t last_cycleclock, return current_time_nanos_from_system; } -static int64_t GetCurrentTimeNanosSlowPath() ABSL_ATTRIBUTE_COLD; - -// Read the contents of *atomic into *sample. -// Each field is read atomically, but to maintain atomicity between fields, -// the access must be done under a lock. -static void ReadTimeSampleAtomic(const struct TimeSampleAtomic *atomic, - struct TimeSample *sample) { - sample->base_ns = atomic->base_ns.load(std::memory_order_relaxed); - sample->base_cycles = atomic->base_cycles.load(std::memory_order_relaxed); - sample->nsscaled_per_cycle = - atomic->nsscaled_per_cycle.load(std::memory_order_relaxed); - sample->min_cycles_per_sample = - atomic->min_cycles_per_sample.load(std::memory_order_relaxed); - sample->raw_ns = atomic->raw_ns.load(std::memory_order_relaxed); -} - -// Public routine. -// Algorithm: We wish to compute real time from a cycle counter. In normal -// operation, we construct a piecewise linear approximation to the kernel time -// source, using the cycle counter value. The start of each line segment is at -// the same point as the end of the last, but may have a different slope (that -// is, a different idea of the cycle counter frequency). Every couple of -// seconds, the kernel time source is sampled and compared with the current -// approximation. A new slope is chosen that, if followed for another couple -// of seconds, will correct the error at the current position. The information -// for a sample is in the "last_sample" struct. The linear approximation is -// estimated_time = last_sample.base_ns + -// last_sample.ns_per_cycle * (counter_reading - last_sample.base_cycles) -// (ns_per_cycle is actually stored in different units and scaled, to avoid -// overflow). The base_ns of the next linear approximation is the -// estimated_time using the last approximation; the base_cycles is the cycle -// counter value at that time; the ns_per_cycle is the number of ns per cycle -// measured since the last sample, but adjusted so that most of the difference -// between the estimated_time and the kernel time will be corrected by the -// estimated time to the next sample. In normal operation, this algorithm -// relies on: -// - the cycle counter and kernel time rates not changing a lot in a few -// seconds. -// - the client calling into the code often compared to a couple of seconds, so -// the time to the next correction can be estimated. -// Any time ns_per_cycle is not known, a major error is detected, or the -// assumption about frequent calls is violated, the implementation returns the -// kernel time. It records sufficient data that a linear approximation can -// resume a little later. - -int64_t GetCurrentTimeNanos() { - // read the data from the "last_sample" struct (but don't need raw_ns yet) - // The reads of "seq" and test of the values emulate a reader lock. - uint64_t base_ns; - uint64_t base_cycles; - uint64_t nsscaled_per_cycle; - uint64_t min_cycles_per_sample; - uint64_t seq_read0; - uint64_t seq_read1; - - // If we have enough information to interpolate, the value returned will be - // derived from this cycleclock-derived time estimate. On some platforms - // (POWER) the function to retrieve this value has enough complexity to - // contribute to register pressure - reading it early before initializing - // the other pieces of the calculation minimizes spill/restore instructions, - // minimizing icache cost. - uint64_t now_cycles = GET_CURRENT_TIME_NANOS_CYCLECLOCK_NOW(); - - // Acquire pairs with the barrier in SeqRelease - if this load sees that - // store, the shared-data reads necessarily see that SeqRelease's updates - // to the same shared data. +static int64_t GetCurrentTimeNanosSlowPath() ABSL_ATTRIBUTE_COLD; + +// Read the contents of *atomic into *sample. +// Each field is read atomically, but to maintain atomicity between fields, +// the access must be done under a lock. +static void ReadTimeSampleAtomic(const struct TimeSampleAtomic *atomic, + struct TimeSample *sample) { + sample->base_ns = atomic->base_ns.load(std::memory_order_relaxed); + sample->base_cycles = atomic->base_cycles.load(std::memory_order_relaxed); + sample->nsscaled_per_cycle = + atomic->nsscaled_per_cycle.load(std::memory_order_relaxed); + sample->min_cycles_per_sample = + atomic->min_cycles_per_sample.load(std::memory_order_relaxed); + sample->raw_ns = atomic->raw_ns.load(std::memory_order_relaxed); +} + +// Public routine. +// Algorithm: We wish to compute real time from a cycle counter. In normal +// operation, we construct a piecewise linear approximation to the kernel time +// source, using the cycle counter value. The start of each line segment is at +// the same point as the end of the last, but may have a different slope (that +// is, a different idea of the cycle counter frequency). Every couple of +// seconds, the kernel time source is sampled and compared with the current +// approximation. A new slope is chosen that, if followed for another couple +// of seconds, will correct the error at the current position. The information +// for a sample is in the "last_sample" struct. The linear approximation is +// estimated_time = last_sample.base_ns + +// last_sample.ns_per_cycle * (counter_reading - last_sample.base_cycles) +// (ns_per_cycle is actually stored in different units and scaled, to avoid +// overflow). The base_ns of the next linear approximation is the +// estimated_time using the last approximation; the base_cycles is the cycle +// counter value at that time; the ns_per_cycle is the number of ns per cycle +// measured since the last sample, but adjusted so that most of the difference +// between the estimated_time and the kernel time will be corrected by the +// estimated time to the next sample. In normal operation, this algorithm +// relies on: +// - the cycle counter and kernel time rates not changing a lot in a few +// seconds. +// - the client calling into the code often compared to a couple of seconds, so +// the time to the next correction can be estimated. +// Any time ns_per_cycle is not known, a major error is detected, or the +// assumption about frequent calls is violated, the implementation returns the +// kernel time. It records sufficient data that a linear approximation can +// resume a little later. + +int64_t GetCurrentTimeNanos() { + // read the data from the "last_sample" struct (but don't need raw_ns yet) + // The reads of "seq" and test of the values emulate a reader lock. + uint64_t base_ns; + uint64_t base_cycles; + uint64_t nsscaled_per_cycle; + uint64_t min_cycles_per_sample; + uint64_t seq_read0; + uint64_t seq_read1; + + // If we have enough information to interpolate, the value returned will be + // derived from this cycleclock-derived time estimate. On some platforms + // (POWER) the function to retrieve this value has enough complexity to + // contribute to register pressure - reading it early before initializing + // the other pieces of the calculation minimizes spill/restore instructions, + // minimizing icache cost. + uint64_t now_cycles = GET_CURRENT_TIME_NANOS_CYCLECLOCK_NOW(); + + // Acquire pairs with the barrier in SeqRelease - if this load sees that + // store, the shared-data reads necessarily see that SeqRelease's updates + // to the same shared data. seq_read0 = time_state.seq.load(std::memory_order_acquire); - + base_ns = time_state.last_sample.base_ns.load(std::memory_order_relaxed); base_cycles = time_state.last_sample.base_cycles.load(std::memory_order_relaxed); - nsscaled_per_cycle = + nsscaled_per_cycle = time_state.last_sample.nsscaled_per_cycle.load(std::memory_order_relaxed); min_cycles_per_sample = time_state.last_sample.min_cycles_per_sample.load( std::memory_order_relaxed); - - // This acquire fence pairs with the release fence in SeqAcquire. Since it - // is sequenced between reads of shared data and seq_read1, the reads of - // shared data are effectively acquiring. - std::atomic_thread_fence(std::memory_order_acquire); - - // The shared-data reads are effectively acquire ordered, and the - // shared-data writes are effectively release ordered. Therefore if our - // shared-data reads see any of a particular update's shared-data writes, - // seq_read1 is guaranteed to see that update's SeqAcquire. + + // This acquire fence pairs with the release fence in SeqAcquire. Since it + // is sequenced between reads of shared data and seq_read1, the reads of + // shared data are effectively acquiring. + std::atomic_thread_fence(std::memory_order_acquire); + + // The shared-data reads are effectively acquire ordered, and the + // shared-data writes are effectively release ordered. Therefore if our + // shared-data reads see any of a particular update's shared-data writes, + // seq_read1 is guaranteed to see that update's SeqAcquire. seq_read1 = time_state.seq.load(std::memory_order_relaxed); - - // Fast path. Return if min_cycles_per_sample has not yet elapsed since the - // last sample, and we read a consistent sample. The fast path activates - // only when min_cycles_per_sample is non-zero, which happens when we get an - // estimate for the cycle time. The predicate will fail if now_cycles < - // base_cycles, or if some other thread is in the slow path. - // - // Since we now read now_cycles before base_ns, it is possible for now_cycles - // to be less than base_cycles (if we were interrupted between those loads and - // last_sample was updated). This is harmless, because delta_cycles will wrap - // and report a time much much bigger than min_cycles_per_sample. In that case - // we will take the slow path. + + // Fast path. Return if min_cycles_per_sample has not yet elapsed since the + // last sample, and we read a consistent sample. The fast path activates + // only when min_cycles_per_sample is non-zero, which happens when we get an + // estimate for the cycle time. The predicate will fail if now_cycles < + // base_cycles, or if some other thread is in the slow path. + // + // Since we now read now_cycles before base_ns, it is possible for now_cycles + // to be less than base_cycles (if we were interrupted between those loads and + // last_sample was updated). This is harmless, because delta_cycles will wrap + // and report a time much much bigger than min_cycles_per_sample. In that case + // we will take the slow path. uint64_t delta_cycles; - if (seq_read0 == seq_read1 && (seq_read0 & 1) == 0 && + if (seq_read0 == seq_read1 && (seq_read0 & 1) == 0 && (delta_cycles = now_cycles - base_cycles) < min_cycles_per_sample) { - return base_ns + ((delta_cycles * nsscaled_per_cycle) >> kScale); - } - return GetCurrentTimeNanosSlowPath(); -} - -// Return (a << kScale)/b. -// Zero is returned if b==0. Scaling is performed internally to -// preserve precision without overflow. -static uint64_t SafeDivideAndScale(uint64_t a, uint64_t b) { - // Find maximum safe_shift so that - // 0 <= safe_shift <= kScale and (a << safe_shift) does not overflow. - int safe_shift = kScale; - while (((a << safe_shift) >> safe_shift) != a) { - safe_shift--; - } - uint64_t scaled_b = b >> (kScale - safe_shift); - uint64_t quotient = 0; - if (scaled_b != 0) { - quotient = (a << safe_shift) / scaled_b; - } - return quotient; -} - -static uint64_t UpdateLastSample( - uint64_t now_cycles, uint64_t now_ns, uint64_t delta_cycles, - const struct TimeSample *sample) ABSL_ATTRIBUTE_COLD; - -// The slow path of GetCurrentTimeNanos(). This is taken while gathering -// initial samples, when enough time has elapsed since the last sample, and if -// any other thread is writing to last_sample. -// -// Manually mark this 'noinline' to minimize stack frame size of the fast -// path. Without this, sometimes a compiler may inline this big block of code -// into the fast path. That causes lots of register spills and reloads that -// are unnecessary unless the slow path is taken. -// + return base_ns + ((delta_cycles * nsscaled_per_cycle) >> kScale); + } + return GetCurrentTimeNanosSlowPath(); +} + +// Return (a << kScale)/b. +// Zero is returned if b==0. Scaling is performed internally to +// preserve precision without overflow. +static uint64_t SafeDivideAndScale(uint64_t a, uint64_t b) { + // Find maximum safe_shift so that + // 0 <= safe_shift <= kScale and (a << safe_shift) does not overflow. + int safe_shift = kScale; + while (((a << safe_shift) >> safe_shift) != a) { + safe_shift--; + } + uint64_t scaled_b = b >> (kScale - safe_shift); + uint64_t quotient = 0; + if (scaled_b != 0) { + quotient = (a << safe_shift) / scaled_b; + } + return quotient; +} + +static uint64_t UpdateLastSample( + uint64_t now_cycles, uint64_t now_ns, uint64_t delta_cycles, + const struct TimeSample *sample) ABSL_ATTRIBUTE_COLD; + +// The slow path of GetCurrentTimeNanos(). This is taken while gathering +// initial samples, when enough time has elapsed since the last sample, and if +// any other thread is writing to last_sample. +// +// Manually mark this 'noinline' to minimize stack frame size of the fast +// path. Without this, sometimes a compiler may inline this big block of code +// into the fast path. That causes lots of register spills and reloads that +// are unnecessary unless the slow path is taken. +// // TODO(y_absl-team): Remove this attribute when our compiler is smart enough -// to do the right thing. -ABSL_ATTRIBUTE_NOINLINE +// to do the right thing. +ABSL_ATTRIBUTE_NOINLINE static int64_t GetCurrentTimeNanosSlowPath() ABSL_LOCKS_EXCLUDED(time_state.lock) { - // Serialize access to slow-path. Fast-path readers are not blocked yet, and - // code below must not modify last_sample until the seqlock is acquired. + // Serialize access to slow-path. Fast-path readers are not blocked yet, and + // code below must not modify last_sample until the seqlock is acquired. time_state.lock.Lock(); - - // Sample the kernel time base. This is the definition of - // "now" if we take the slow path. - uint64_t now_cycles; + + // Sample the kernel time base. This is the definition of + // "now" if we take the slow path. + uint64_t now_cycles; uint64_t now_ns = GetCurrentTimeNanosFromKernel(time_state.last_now_cycles, &now_cycles); time_state.last_now_cycles = now_cycles; - - uint64_t estimated_base_ns; - - // ---------- - // Read the "last_sample" values again; this time holding the write lock. - struct TimeSample sample; + + uint64_t estimated_base_ns; + + // ---------- + // Read the "last_sample" values again; this time holding the write lock. + struct TimeSample sample; ReadTimeSampleAtomic(&time_state.last_sample, &sample); - - // ---------- - // Try running the fast path again; another thread may have updated the - // sample between our run of the fast path and the sample we just read. - uint64_t delta_cycles = now_cycles - sample.base_cycles; - if (delta_cycles < sample.min_cycles_per_sample) { - // Another thread updated the sample. This path does not take the seqlock - // so that blocked readers can make progress without blocking new readers. - estimated_base_ns = sample.base_ns + - ((delta_cycles * sample.nsscaled_per_cycle) >> kScale); + + // ---------- + // Try running the fast path again; another thread may have updated the + // sample between our run of the fast path and the sample we just read. + uint64_t delta_cycles = now_cycles - sample.base_cycles; + if (delta_cycles < sample.min_cycles_per_sample) { + // Another thread updated the sample. This path does not take the seqlock + // so that blocked readers can make progress without blocking new readers. + estimated_base_ns = sample.base_ns + + ((delta_cycles * sample.nsscaled_per_cycle) >> kScale); time_state.stats_fast_slow_paths++; - } else { - estimated_base_ns = - UpdateLastSample(now_cycles, now_ns, delta_cycles, &sample); - } - + } else { + estimated_base_ns = + UpdateLastSample(now_cycles, now_ns, delta_cycles, &sample); + } + time_state.lock.Unlock(); - - return estimated_base_ns; -} - -// Main part of the algorithm. Locks out readers, updates the approximation -// using the new sample from the kernel, and stores the result in last_sample -// for readers. Returns the new estimated time. -static uint64_t UpdateLastSample(uint64_t now_cycles, uint64_t now_ns, - uint64_t delta_cycles, - const struct TimeSample *sample) + + return estimated_base_ns; +} + +// Main part of the algorithm. Locks out readers, updates the approximation +// using the new sample from the kernel, and stores the result in last_sample +// for readers. Returns the new estimated time. +static uint64_t UpdateLastSample(uint64_t now_cycles, uint64_t now_ns, + uint64_t delta_cycles, + const struct TimeSample *sample) ABSL_EXCLUSIVE_LOCKS_REQUIRED(time_state.lock) { - uint64_t estimated_base_ns = now_ns; + uint64_t estimated_base_ns = now_ns; uint64_t lock_value = SeqAcquire(&time_state.seq); // acquire seqlock to block readers - - // The 5s in the next if-statement limits the time for which we will trust - // the cycle counter and our last sample to give a reasonable result. - // Errors in the rate of the source clock can be multiplied by the ratio - // between this limit and kMinNSBetweenSamples. - if (sample->raw_ns == 0 || // no recent sample, or clock went backwards - sample->raw_ns + static_cast<uint64_t>(5) * 1000 * 1000 * 1000 < now_ns || - now_ns < sample->raw_ns || now_cycles < sample->base_cycles) { - // record this sample, and forget any previously known slope. + + // The 5s in the next if-statement limits the time for which we will trust + // the cycle counter and our last sample to give a reasonable result. + // Errors in the rate of the source clock can be multiplied by the ratio + // between this limit and kMinNSBetweenSamples. + if (sample->raw_ns == 0 || // no recent sample, or clock went backwards + sample->raw_ns + static_cast<uint64_t>(5) * 1000 * 1000 * 1000 < now_ns || + now_ns < sample->raw_ns || now_cycles < sample->base_cycles) { + // record this sample, and forget any previously known slope. time_state.last_sample.raw_ns.store(now_ns, std::memory_order_relaxed); time_state.last_sample.base_ns.store(estimated_base_ns, std::memory_order_relaxed); @@ -464,122 +464,122 @@ static uint64_t UpdateLastSample(uint64_t now_cycles, uint64_t now_ns, time_state.last_sample.min_cycles_per_sample.store( 0, std::memory_order_relaxed); time_state.stats_initializations++; - } else if (sample->raw_ns + 500 * 1000 * 1000 < now_ns && - sample->base_cycles + 50 < now_cycles) { - // Enough time has passed to compute the cycle time. - if (sample->nsscaled_per_cycle != 0) { // Have a cycle time estimate. - // Compute time from counter reading, but avoiding overflow - // delta_cycles may be larger than on the fast path. - uint64_t estimated_scaled_ns; - int s = -1; - do { - s++; - estimated_scaled_ns = (delta_cycles >> s) * sample->nsscaled_per_cycle; - } while (estimated_scaled_ns / sample->nsscaled_per_cycle != - (delta_cycles >> s)); - estimated_base_ns = sample->base_ns + - (estimated_scaled_ns >> (kScale - s)); - } - - // Compute the assumed cycle time kMinNSBetweenSamples ns into the future - // assuming the cycle counter rate stays the same as the last interval. - uint64_t ns = now_ns - sample->raw_ns; - uint64_t measured_nsscaled_per_cycle = SafeDivideAndScale(ns, delta_cycles); - - uint64_t assumed_next_sample_delta_cycles = - SafeDivideAndScale(kMinNSBetweenSamples, measured_nsscaled_per_cycle); - - int64_t diff_ns = now_ns - estimated_base_ns; // estimate low by this much - - // We want to set nsscaled_per_cycle so that our estimate of the ns time - // at the assumed cycle time is the assumed ns time. - // That is, we want to set nsscaled_per_cycle so: - // kMinNSBetweenSamples + diff_ns == - // (assumed_next_sample_delta_cycles * nsscaled_per_cycle) >> kScale - // But we wish to damp oscillations, so instead correct only most - // of our current error, by solving: - // kMinNSBetweenSamples + diff_ns - (diff_ns / 16) == - // (assumed_next_sample_delta_cycles * nsscaled_per_cycle) >> kScale - ns = kMinNSBetweenSamples + diff_ns - (diff_ns / 16); - uint64_t new_nsscaled_per_cycle = - SafeDivideAndScale(ns, assumed_next_sample_delta_cycles); - if (new_nsscaled_per_cycle != 0 && - diff_ns < 100 * 1000 * 1000 && -diff_ns < 100 * 1000 * 1000) { - // record the cycle time measurement + } else if (sample->raw_ns + 500 * 1000 * 1000 < now_ns && + sample->base_cycles + 50 < now_cycles) { + // Enough time has passed to compute the cycle time. + if (sample->nsscaled_per_cycle != 0) { // Have a cycle time estimate. + // Compute time from counter reading, but avoiding overflow + // delta_cycles may be larger than on the fast path. + uint64_t estimated_scaled_ns; + int s = -1; + do { + s++; + estimated_scaled_ns = (delta_cycles >> s) * sample->nsscaled_per_cycle; + } while (estimated_scaled_ns / sample->nsscaled_per_cycle != + (delta_cycles >> s)); + estimated_base_ns = sample->base_ns + + (estimated_scaled_ns >> (kScale - s)); + } + + // Compute the assumed cycle time kMinNSBetweenSamples ns into the future + // assuming the cycle counter rate stays the same as the last interval. + uint64_t ns = now_ns - sample->raw_ns; + uint64_t measured_nsscaled_per_cycle = SafeDivideAndScale(ns, delta_cycles); + + uint64_t assumed_next_sample_delta_cycles = + SafeDivideAndScale(kMinNSBetweenSamples, measured_nsscaled_per_cycle); + + int64_t diff_ns = now_ns - estimated_base_ns; // estimate low by this much + + // We want to set nsscaled_per_cycle so that our estimate of the ns time + // at the assumed cycle time is the assumed ns time. + // That is, we want to set nsscaled_per_cycle so: + // kMinNSBetweenSamples + diff_ns == + // (assumed_next_sample_delta_cycles * nsscaled_per_cycle) >> kScale + // But we wish to damp oscillations, so instead correct only most + // of our current error, by solving: + // kMinNSBetweenSamples + diff_ns - (diff_ns / 16) == + // (assumed_next_sample_delta_cycles * nsscaled_per_cycle) >> kScale + ns = kMinNSBetweenSamples + diff_ns - (diff_ns / 16); + uint64_t new_nsscaled_per_cycle = + SafeDivideAndScale(ns, assumed_next_sample_delta_cycles); + if (new_nsscaled_per_cycle != 0 && + diff_ns < 100 * 1000 * 1000 && -diff_ns < 100 * 1000 * 1000) { + // record the cycle time measurement time_state.last_sample.nsscaled_per_cycle.store( - new_nsscaled_per_cycle, std::memory_order_relaxed); - uint64_t new_min_cycles_per_sample = - SafeDivideAndScale(kMinNSBetweenSamples, new_nsscaled_per_cycle); + new_nsscaled_per_cycle, std::memory_order_relaxed); + uint64_t new_min_cycles_per_sample = + SafeDivideAndScale(kMinNSBetweenSamples, new_nsscaled_per_cycle); time_state.last_sample.min_cycles_per_sample.store( - new_min_cycles_per_sample, std::memory_order_relaxed); + new_min_cycles_per_sample, std::memory_order_relaxed); time_state.stats_calibrations++; - } else { // something went wrong; forget the slope + } else { // something went wrong; forget the slope time_state.last_sample.nsscaled_per_cycle.store( 0, std::memory_order_relaxed); time_state.last_sample.min_cycles_per_sample.store( 0, std::memory_order_relaxed); - estimated_base_ns = now_ns; + estimated_base_ns = now_ns; time_state.stats_reinitializations++; - } + } time_state.last_sample.raw_ns.store(now_ns, std::memory_order_relaxed); time_state.last_sample.base_ns.store(estimated_base_ns, std::memory_order_relaxed); time_state.last_sample.base_cycles.store(now_cycles, std::memory_order_relaxed); - } else { - // have a sample, but no slope; waiting for enough time for a calibration + } else { + // have a sample, but no slope; waiting for enough time for a calibration time_state.stats_slow_paths++; - } - + } + SeqRelease(&time_state.seq, lock_value); // release the readers - - return estimated_base_ns; -} + + return estimated_base_ns; +} ABSL_NAMESPACE_END } // namespace y_absl -#endif // ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS - +#endif // ABSL_USE_CYCLECLOCK_FOR_GET_CURRENT_TIME_NANOS + namespace y_absl { ABSL_NAMESPACE_BEGIN -namespace { - -// Returns the maximum duration that SleepOnce() can sleep for. +namespace { + +// Returns the maximum duration that SleepOnce() can sleep for. constexpr y_absl::Duration MaxSleep() { -#ifdef _WIN32 - // Windows Sleep() takes unsigned long argument in milliseconds. +#ifdef _WIN32 + // Windows Sleep() takes unsigned long argument in milliseconds. return y_absl::Milliseconds( - std::numeric_limits<unsigned long>::max()); // NOLINT(runtime/int) -#else + std::numeric_limits<unsigned long>::max()); // NOLINT(runtime/int) +#else return y_absl::Seconds(std::numeric_limits<time_t>::max()); -#endif -} - -// Sleeps for the given duration. -// REQUIRES: to_sleep <= MaxSleep(). +#endif +} + +// Sleeps for the given duration. +// REQUIRES: to_sleep <= MaxSleep(). void SleepOnce(y_absl::Duration to_sleep) { -#ifdef _WIN32 +#ifdef _WIN32 Sleep(to_sleep / y_absl::Milliseconds(1)); -#else +#else struct timespec sleep_time = y_absl::ToTimespec(to_sleep); - while (nanosleep(&sleep_time, &sleep_time) != 0 && errno == EINTR) { - // Ignore signals and wait for the full interval to elapse. - } -#endif -} - -} // namespace + while (nanosleep(&sleep_time, &sleep_time) != 0 && errno == EINTR) { + // Ignore signals and wait for the full interval to elapse. + } +#endif +} + +} // namespace ABSL_NAMESPACE_END } // namespace y_absl - -extern "C" { - + +extern "C" { + ABSL_ATTRIBUTE_WEAK void ABSL_INTERNAL_C_SYMBOL(AbslInternalSleepFor)( y_absl::Duration duration) { while (duration > y_absl::ZeroDuration()) { y_absl::Duration to_sleep = std::min(duration, y_absl::MaxSleep()); y_absl::SleepOnce(to_sleep); - duration -= to_sleep; - } -} - -} // extern "C" + duration -= to_sleep; + } +} + +} // extern "C" |