Export of internal Abseil changes

--
17141711ee419daa597a9f31e73721f80143e55a by Gennadiy Rozental <rogeeff@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 401384949

--
ac48584a7b16e8a12e26d49deb6cddec584a20b5 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 401337785

--
8a51bb7c962845e0707240c5ba12c1b80f6fbbe9 by Derek Mauro <dmauro@google.com>:

Internal change

PiperOrigin-RevId: 401047691

--
8e18024510869247f3c04c7807c93709eca2322a by Chris Kennelly <ckennelly@google.com>:

Note that SpinLock does not guarantee priorities for wakeups.

PiperOrigin-RevId: 400999238

--
75bc09b5f95fbb74b74d14c370bfb80011e8fb7f by Derek Mauro <dmauro@google.com>:

Add visibility restrictions to some internal targets

PiperOrigin-RevId: 400718253

--
1de5061016bc42cd7be009c9725ed2343ce12e3d by Abseil Team <absl-team@google.com>:

Make it clear that operator<< can also be used in place of ToString when logging absl::Status.

PiperOrigin-RevId: 400248269

--
cda15d9dc6e5cd569de7e5e73f409b72a3caed51 by Abseil Team <absl-team@google.com>:

Minor cleanup

PiperOrigin-RevId: 400087535

--
b001375ec47da3a0434be9ca9a45c0df510e7dda by Abseil Team <absl-team@google.com>:

Move periodic_sampler from base/internal to profiling/internal

PiperOrigin-RevId: 400038533

--
e7e02e686abc3900e723080849a3607d190ef57f by Abseil Team <absl-team@google.com>:

Move exponential_biased from base/internal to profiling/internal

PiperOrigin-RevId: 400020329
GitOrigin-RevId: 17141711ee419daa597a9f31e73721f80143e55a
Change-Id: I10924df7e1cc198447813dbe97a374a5cef66b49

9 files changed, 5 insertions, 943 deletions

diff --git a/absl/base/internal/exponential_biased.cc b/absl/base/internal/exponential_biased.cc
deleted file mode 100644
index 05aeea56..00000000
--- a/absl/base/internal/exponential_biased.cc
+++ /dev/null
@@ -1,93 +0,0 @@
-// Copyright 2019 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 "absl/base/internal/exponential_biased.h"
-
-#include <stdint.h>
-
-#include <algorithm>
-#include <atomic>
-#include <cmath>
-#include <limits>
-
-#include "absl/base/attributes.h"
-#include "absl/base/optimization.h"
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace base_internal {
-
-// The algorithm generates a random number between 0 and 1 and applies the
-// inverse cumulative distribution function for an exponential. Specifically:
-// Let m be the inverse of the sample period, then the probability
-// distribution function is m*exp(-mx) so the CDF is
-// p = 1 - exp(-mx), so
-// q = 1 - p = exp(-mx)
-// log_e(q) = -mx
-// -log_e(q)/m = x
-// log_2(q) * (-log_e(2) * 1/m) = x
-// In the code, q is actually in the range 1 to 2**26, hence the -26 below
-int64_t ExponentialBiased::GetSkipCount(int64_t mean) {
-  if (ABSL_PREDICT_FALSE(!initialized_)) {
-    Initialize();
-  }
-
-  uint64_t rng = NextRandom(rng_);
-  rng_ = rng;
-
-  // Take the top 26 bits as the random number
-  // (This plus the 1<<58 sampling bound give a max possible step of
-  // 5194297183973780480 bytes.)
-  // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
-  // under piii debug for some binaries.
-  double q = static_cast<uint32_t>(rng >> (kPrngNumBits - 26)) + 1.0;
-  // Put the computed p-value through the CDF of a geometric.
-  double interval = bias_ + (std::log2(q) - 26) * (-std::log(2.0) * mean);
-  // Very large values of interval overflow int64_t. To avoid that, we will
-  // cheat and clamp any huge values to (int64_t max)/2. This is a potential
-  // source of bias, but the mean would need to be such a large value that it's
-  // not likely to come up. For example, with a mean of 1e18, the probability of
-  // hitting this condition is about 1/1000. For a mean of 1e17, standard
-  // calculators claim that this event won't happen.
-  if (interval > static_cast<double>(std::numeric_limits<int64_t>::max() / 2)) {
-    // Assume huge values are bias neutral, retain bias for next call.
-    return std::numeric_limits<int64_t>::max() / 2;
-  }
-  double value = std::rint(interval);
-  bias_ = interval - value;
-  return value;
-}
-
-int64_t ExponentialBiased::GetStride(int64_t mean) {
-  return GetSkipCount(mean - 1) + 1;
-}
-
-void ExponentialBiased::Initialize() {
-  // We don't get well distributed numbers from `this` so we call NextRandom() a
-  // bunch to mush the bits around. We use a global_rand to handle the case
-  // where the same thread (by memory address) gets created and destroyed
-  // repeatedly.
-  ABSL_CONST_INIT static std::atomic<uint32_t> global_rand(0);
-  uint64_t r = reinterpret_cast<uint64_t>(this) +
-               global_rand.fetch_add(1, std::memory_order_relaxed);
-  for (int i = 0; i < 20; ++i) {
-    r = NextRandom(r);
-  }
-  rng_ = r;
-  initialized_ = true;
-}
-
-}  // namespace base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
diff --git a/absl/base/internal/exponential_biased.h b/absl/base/internal/exponential_biased.h
deleted file mode 100644
index a81f10e2..00000000
--- a/absl/base/internal/exponential_biased.h
+++ /dev/null
@@ -1,130 +0,0 @@
-// Copyright 2019 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.
-
-#ifndef ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_
-#define ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_
-
-#include <stdint.h>
-
-#include "absl/base/config.h"
-#include "absl/base/macros.h"
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace base_internal {
-
-// ExponentialBiased provides a small and fast random number generator for a
-// rounded exponential distribution. This generator manages very little state,
-// and imposes no synchronization overhead. This makes it useful in specialized
-// scenarios requiring minimum overhead, such as stride based periodic sampling.
-//
-// ExponentialBiased provides two closely related functions, GetSkipCount() and
-// GetStride(), both returning a rounded integer defining a number of events
-// required before some event with a given mean probability occurs.
-//
-// The distribution is useful to generate a random wait time or some periodic
-// event with a given mean probability. For example, if an action is supposed to
-// happen on average once every 'N' events, then we can get a random 'stride'
-// counting down how long before the event to happen. For example, if we'd want
-// to sample one in every 1000 'Frobber' calls, our code could look like this:
-//
-//   Frobber::Frobber() {
-//     stride_ = exponential_biased_.GetStride(1000);
-//   }
-//
-//   void Frobber::Frob(int arg) {
-//     if (--stride == 0) {
-//       SampleFrob(arg);
-//       stride_ = exponential_biased_.GetStride(1000);
-//     }
-//     ...
-//   }
-//
-// The rounding of the return value creates a bias, especially for smaller means
-// where the distribution of the fraction is not evenly distributed. We correct
-// this bias by tracking the fraction we rounded up or down on each iteration,
-// effectively tracking the distance between the cumulative value, and the
-// rounded cumulative value. For example, given a mean of 2:
-//
-//   raw = 1.63076, cumulative = 1.63076, rounded = 2, bias = -0.36923
-//   raw = 0.14624, cumulative = 1.77701, rounded = 2, bias =  0.14624
-//   raw = 4.93194, cumulative = 6.70895, rounded = 7, bias = -0.06805
-//   raw = 0.24206, cumulative = 6.95101, rounded = 7, bias =  0.24206
-//   etc...
-//
-// Adjusting with rounding bias is relatively trivial:
-//
-//    double value = bias_ + exponential_distribution(mean)();
-//    double rounded_value = std::rint(value);
-//    bias_ = value - rounded_value;
-//    return rounded_value;
-//
-// This class is thread-compatible.
-class ExponentialBiased {
- public:
-  // The number of bits set by NextRandom.
-  static constexpr int kPrngNumBits = 48;
-
-  // `GetSkipCount()` returns the number of events to skip before some chosen
-  // event happens. For example, randomly tossing a coin, we will on average
-  // throw heads once before we get tails. We can simulate random coin tosses
-  // using GetSkipCount() as:
-  //
-  //   ExponentialBiased eb;
-  //   for (...) {
-  //     int number_of_heads_before_tail = eb.GetSkipCount(1);
-  //     for (int flips = 0; flips < number_of_heads_before_tail; ++flips) {
-  //       printf("head...");
-  //     }
-  //     printf("tail\n");
-  //   }
-  //
-  int64_t GetSkipCount(int64_t mean);
-
-  // GetStride() returns the number of events required for a specific event to
-  // happen. See the class comments for a usage example. `GetStride()` is
-  // equivalent to `GetSkipCount(mean - 1) + 1`. When to use `GetStride()` or
-  // `GetSkipCount()` depends mostly on what best fits the use case.
-  int64_t GetStride(int64_t mean);
-
-  // Computes a random number in the range [0, 1<<(kPrngNumBits+1) - 1]
-  //
-  // This is public to enable testing.
-  static uint64_t NextRandom(uint64_t rnd);
-
- private:
-  void Initialize();
-
-  uint64_t rng_{0};
-  double bias_{0};
-  bool initialized_{false};
-};
-
-// Returns the next prng value.
-// pRNG is: aX+b mod c with a = 0x5DEECE66D, b =  0xB, c = 1<<48
-// This is the lrand64 generator.
-inline uint64_t ExponentialBiased::NextRandom(uint64_t rnd) {
-  const uint64_t prng_mult = uint64_t{0x5DEECE66D};
-  const uint64_t prng_add = 0xB;
-  const uint64_t prng_mod_power = 48;
-  const uint64_t prng_mod_mask =
-      ~((~static_cast<uint64_t>(0)) << prng_mod_power);
-  return (prng_mult * rnd + prng_add) & prng_mod_mask;
-}
-
-}  // namespace base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
-
-#endif  // ABSL_BASE_INTERNAL_EXPONENTIAL_BIASED_H_
diff --git a/absl/base/internal/exponential_biased_test.cc b/absl/base/internal/exponential_biased_test.cc
deleted file mode 100644
index 075583ca..00000000
--- a/absl/base/internal/exponential_biased_test.cc
+++ /dev/null
@@ -1,199 +0,0 @@
-// Copyright 2019 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 "absl/base/internal/exponential_biased.h"
-
-#include <stddef.h>
-
-#include <cmath>
-#include <cstdint>
-#include <vector>
-
-#include "gmock/gmock.h"
-#include "gtest/gtest.h"
-#include "absl/strings/str_cat.h"
-
-using ::testing::Ge;
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace base_internal {
-
-MATCHER_P2(IsBetween, a, b,
-           absl::StrCat(std::string(negation ? "isn't" : "is"), " between ", a,
-                        " and ", b)) {
-  return a <= arg && arg <= b;
-}
-
-// Tests of the quality of the random numbers generated
-// This uses the Anderson Darling test for uniformity.
-// See "Evaluating the Anderson-Darling Distribution" by Marsaglia
-// for details.
-
-// Short cut version of ADinf(z), z>0 (from Marsaglia)
-// This returns the p-value for Anderson Darling statistic in
-// the limit as n-> infinity. For finite n, apply the error fix below.
-double AndersonDarlingInf(double z) {
-  if (z < 2) {
-    return exp(-1.2337141 / z) / sqrt(z) *
-           (2.00012 +
-            (0.247105 -
-             (0.0649821 - (0.0347962 - (0.011672 - 0.00168691 * z) * z) * z) *
-                 z) *
-                z);
-  }
-  return exp(
-      -exp(1.0776 -
-           (2.30695 -
-            (0.43424 - (0.082433 - (0.008056 - 0.0003146 * z) * z) * z) * z) *
-               z));
-}
-
-// Corrects the approximation error in AndersonDarlingInf for small values of n
-// Add this to AndersonDarlingInf to get a better approximation
-// (from Marsaglia)
-double AndersonDarlingErrFix(int n, double x) {
-  if (x > 0.8) {
-    return (-130.2137 +
-            (745.2337 -
-             (1705.091 - (1950.646 - (1116.360 - 255.7844 * x) * x) * x) * x) *
-                x) /
-           n;
-  }
-  double cutoff = 0.01265 + 0.1757 / n;
-  if (x < cutoff) {
-    double t = x / cutoff;
-    t = sqrt(t) * (1 - t) * (49 * t - 102);
-    return t * (0.0037 / (n * n) + 0.00078 / n + 0.00006) / n;
-  } else {
-    double t = (x - cutoff) / (0.8 - cutoff);
-    t = -0.00022633 +
-        (6.54034 - (14.6538 - (14.458 - (8.259 - 1.91864 * t) * t) * t) * t) *
-            t;
-    return t * (0.04213 + 0.01365 / n) / n;
-  }
-}
-
-// Returns the AndersonDarling p-value given n and the value of the statistic
-double AndersonDarlingPValue(int n, double z) {
-  double ad = AndersonDarlingInf(z);
-  double errfix = AndersonDarlingErrFix(n, ad);
-  return ad + errfix;
-}
-
-double AndersonDarlingStatistic(const std::vector<double>& random_sample) {
-  int n = random_sample.size();
-  double ad_sum = 0;
-  for (int i = 0; i < n; i++) {
-    ad_sum += (2 * i + 1) *
-              std::log(random_sample[i] * (1 - random_sample[n - 1 - i]));
-  }
-  double ad_statistic = -n - 1 / static_cast<double>(n) * ad_sum;
-  return ad_statistic;
-}
-
-// Tests if the array of doubles is uniformly distributed.
-// Returns the p-value of the Anderson Darling Statistic
-// for the given set of sorted random doubles
-// See "Evaluating the Anderson-Darling Distribution" by
-// Marsaglia and Marsaglia for details.
-double AndersonDarlingTest(const std::vector<double>& random_sample) {
-  double ad_statistic = AndersonDarlingStatistic(random_sample);
-  double p = AndersonDarlingPValue(random_sample.size(), ad_statistic);
-  return p;
-}
-
-TEST(ExponentialBiasedTest, CoinTossDemoWithGetSkipCount) {
-  ExponentialBiased eb;
-  for (int runs = 0; runs < 10; ++runs) {
-    for (int flips = eb.GetSkipCount(1); flips > 0; --flips) {
-      printf("head...");
-    }
-    printf("tail\n");
-  }
-  int heads = 0;
-  for (int i = 0; i < 10000000; i += 1 + eb.GetSkipCount(1)) {
-    ++heads;
-  }
-  printf("Heads = %d (%f%%)\n", heads, 100.0 * heads / 10000000);
-}
-
-TEST(ExponentialBiasedTest, SampleDemoWithStride) {
-  ExponentialBiased eb;
-  int stride = eb.GetStride(10);
-  int samples = 0;
-  for (int i = 0; i < 10000000; ++i) {
-    if (--stride == 0) {
-      ++samples;
-      stride = eb.GetStride(10);
-    }
-  }
-  printf("Samples = %d (%f%%)\n", samples, 100.0 * samples / 10000000);
-}
-
-
-// Testing that NextRandom generates uniform random numbers. Applies the
-// Anderson-Darling test for uniformity
-TEST(ExponentialBiasedTest, TestNextRandom) {
-  for (auto n : std::vector<int>({
-           10,  // Check short-range correlation
-           100, 1000,
-           10000  // Make sure there's no systemic error
-       })) {
-    uint64_t x = 1;
-    // This assumes that the prng returns 48 bit numbers
-    uint64_t max_prng_value = static_cast<uint64_t>(1) << 48;
-    // Initialize.
-    for (int i = 1; i <= 20; i++) {
-      x = ExponentialBiased::NextRandom(x);
-    }
-    std::vector<uint64_t> int_random_sample(n);
-    // Collect samples
-    for (int i = 0; i < n; i++) {
-      int_random_sample[i] = x;
-      x = ExponentialBiased::NextRandom(x);
-    }
-    // First sort them...
-    std::sort(int_random_sample.begin(), int_random_sample.end());
-    std::vector<double> random_sample(n);
-    // Convert them to uniform randoms (in the range [0,1])
-    for (int i = 0; i < n; i++) {
-      random_sample[i] =
-          static_cast<double>(int_random_sample[i]) / max_prng_value;
-    }
-    // Now compute the Anderson-Darling statistic
-    double ad_pvalue = AndersonDarlingTest(random_sample);
-    EXPECT_GT(std::min(ad_pvalue, 1 - ad_pvalue), 0.0001)
-        << "prng is not uniform: n = " << n << " p = " << ad_pvalue;
-  }
-}
-
-// The generator needs to be available as a thread_local and as a static
-// variable.
-TEST(ExponentialBiasedTest, InitializationModes) {
-  ABSL_CONST_INIT static ExponentialBiased eb_static;
-  EXPECT_THAT(eb_static.GetSkipCount(2), Ge(0));
-
-#ifdef ABSL_HAVE_THREAD_LOCAL
-  thread_local ExponentialBiased eb_thread;
-  EXPECT_THAT(eb_thread.GetSkipCount(2), Ge(0));
-#endif
-
-  ExponentialBiased eb_stack;
-  EXPECT_THAT(eb_stack.GetSkipCount(2), Ge(0));
-}
-
-}  // namespace base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
diff --git a/absl/base/internal/periodic_sampler.cc b/absl/base/internal/periodic_sampler.cc
deleted file mode 100644
index 520dabba..00000000
--- a/absl/base/internal/periodic_sampler.cc
+++ /dev/null
@@ -1,53 +0,0 @@
-// Copyright 2019 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 "absl/base/internal/periodic_sampler.h"
-
-#include <atomic>
-
-#include "absl/base/internal/exponential_biased.h"
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace base_internal {
-
-int64_t PeriodicSamplerBase::GetExponentialBiased(int period) noexcept {
-  return rng_.GetStride(period);
-}
-
-bool PeriodicSamplerBase::SubtleConfirmSample() noexcept {
-  int current_period = period();
-
-  // Deal with period case 0 (always off) and 1 (always on)
-  if (ABSL_PREDICT_FALSE(current_period < 2)) {
-    stride_ = 0;
-    return current_period == 1;
-  }
-
-  // Check if this is the first call to Sample()
-  if (ABSL_PREDICT_FALSE(stride_ == 1)) {
-    stride_ = static_cast<uint64_t>(-GetExponentialBiased(current_period));
-    if (static_cast<int64_t>(stride_) < -1) {
-      ++stride_;
-      return false;
-    }
-  }
-
-  stride_ = static_cast<uint64_t>(-GetExponentialBiased(current_period));
-  return true;
-}
-
-}  // namespace base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
diff --git a/absl/base/internal/periodic_sampler.h b/absl/base/internal/periodic_sampler.h
deleted file mode 100644
index f8a86796..00000000
--- a/absl/base/internal/periodic_sampler.h
+++ /dev/null
@@ -1,211 +0,0 @@
-// Copyright 2019 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.
-
-#ifndef ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_
-#define ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_
-
-#include <stdint.h>
-
-#include <atomic>
-
-#include "absl/base/internal/exponential_biased.h"
-#include "absl/base/optimization.h"
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace base_internal {
-
-// PeriodicSamplerBase provides the basic period sampler implementation.
-//
-// This is the base class for the templated PeriodicSampler class, which holds
-// a global std::atomic value identified by a user defined tag, such that
-// each specific PeriodSampler implementation holds its own global period.
-//
-// PeriodicSamplerBase is thread-compatible except where stated otherwise.
-class PeriodicSamplerBase {
- public:
-  // PeriodicSamplerBase is trivial / copyable / movable / destructible.
-  PeriodicSamplerBase() = default;
-  PeriodicSamplerBase(PeriodicSamplerBase&&) = default;
-  PeriodicSamplerBase(const PeriodicSamplerBase&) = default;
-
-  // Returns true roughly once every `period` calls. This is established by a
-  // randomly picked `stride` that is counted down on each call to `Sample`.
-  // This stride is picked such that the probability of `Sample()` returning
-  // true is 1 in `period`.
-  inline bool Sample() noexcept;
-
-  // The below methods are intended for optimized use cases where the
-  // size of the inlined fast path code is highly important. Applications
-  // should use the `Sample()` method unless they have proof that their
-  // specific use case requires the optimizations offered by these methods.
-  //
-  // An example of such a use case is SwissTable sampling. All sampling checks
-  // are in inlined SwissTable methods, and the number of call sites is huge.
-  // In this case, the inlined code size added to each translation unit calling
-  // SwissTable methods is non-trivial.
-  //
-  // The `SubtleMaybeSample()` function spuriously returns true even if the
-  // function should not be sampled, applications MUST match each call to
-  // 'SubtleMaybeSample()' returning true with a `SubtleConfirmSample()` call,
-  // and use the result of the latter as the sampling decision.
-  // In other words: the code should logically be equivalent to:
-  //
-  //    if (SubtleMaybeSample() && SubtleConfirmSample()) {
-  //      // Sample this call
-  //    }
-  //
-  // In the 'inline-size' optimized case, the `SubtleConfirmSample()` call can
-  // be placed out of line, for example, the typical use case looks as follows:
-  //
-  //   // --- frobber.h -----------
-  //   void FrobberSampled();
-  //
-  //   inline void FrobberImpl() {
-  //     // ...
-  //   }
-  //
-  //   inline void Frobber() {
-  //     if (ABSL_PREDICT_FALSE(sampler.SubtleMaybeSample())) {
-  //       FrobberSampled();
-  //     } else {
-  //       FrobberImpl();
-  //     }
-  //   }
-  //
-  //   // --- frobber.cc -----------
-  //   void FrobberSampled() {
-  //     if (!sampler.SubtleConfirmSample())) {
-  //       // Spurious false positive
-  //       FrobberImpl();
-  //       return;
-  //     }
-  //
-  //     // Sampled execution
-  //     // ...
-  //   }
-  inline bool SubtleMaybeSample() noexcept;
-  bool SubtleConfirmSample() noexcept;
-
- protected:
-  // We explicitly don't use a virtual destructor as this class is never
-  // virtually destroyed, and it keeps the class trivial, which avoids TLS
-  // prologue and epilogue code for our TLS instances.
-  ~PeriodicSamplerBase() = default;
-
-  // Returns the next stride for our sampler.
-  // This function is virtual for testing purposes only.
-  virtual int64_t GetExponentialBiased(int period) noexcept;
-
- private:
-  // Returns the current period of this sampler. Thread-safe.
-  virtual int period() const noexcept = 0;
-
-  // Keep and decrement stride_ as an unsigned integer, but compare the value
-  // to zero casted as a signed int. clang and msvc do not create optimum code
-  // if we use signed for the combined decrement and sign comparison.
-  //
-  // Below 3 alternative options, all compiles generate the best code
-  // using the unsigned increment <---> signed int comparison option.
-  //
-  // Option 1:
-  //   int64_t stride_;
-  //   if (ABSL_PREDICT_TRUE(++stride_ < 0)) { ... }
-  //
-  //   GCC   x64 (OK) : https://gcc.godbolt.org/z/R5MzzA
-  //   GCC   ppc (OK) : https://gcc.godbolt.org/z/z7NZAt
-  //   Clang x64 (BAD): https://gcc.godbolt.org/z/t4gPsd
-  //   ICC   x64 (OK) : https://gcc.godbolt.org/z/rE6s8W
-  //   MSVC  x64 (OK) : https://gcc.godbolt.org/z/ARMXqS
-  //
-  // Option 2:
-  //   int64_t stride_ = 0;
-  //   if (ABSL_PREDICT_TRUE(--stride_ >= 0)) { ... }
-  //
-  //   GCC   x64 (OK) : https://gcc.godbolt.org/z/jSQxYK
-  //   GCC   ppc (OK) : https://gcc.godbolt.org/z/VJdYaA
-  //   Clang x64 (BAD): https://gcc.godbolt.org/z/Xm4NjX
-  //   ICC   x64 (OK) : https://gcc.godbolt.org/z/4snaFd
-  //   MSVC  x64 (BAD): https://gcc.godbolt.org/z/BgnEKE
-  //
-  // Option 3:
-  //   uint64_t stride_;
-  //   if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) { ... }
-  //
-  //   GCC   x64 (OK) : https://gcc.godbolt.org/z/bFbfPy
-  //   GCC   ppc (OK) : https://gcc.godbolt.org/z/S9KkUE
-  //   Clang x64 (OK) : https://gcc.godbolt.org/z/UYzRb4
-  //   ICC   x64 (OK) : https://gcc.godbolt.org/z/ptTNfD
-  //   MSVC  x64 (OK) : https://gcc.godbolt.org/z/76j4-5
-  uint64_t stride_ = 0;
-  ExponentialBiased rng_;
-};
-
-inline bool PeriodicSamplerBase::SubtleMaybeSample() noexcept {
-  // See comments on `stride_` for the unsigned increment / signed compare.
-  if (ABSL_PREDICT_TRUE(static_cast<int64_t>(++stride_) < 0)) {
-    return false;
-  }
-  return true;
-}
-
-inline bool PeriodicSamplerBase::Sample() noexcept {
-  return ABSL_PREDICT_FALSE(SubtleMaybeSample()) ? SubtleConfirmSample()
-                                                 : false;
-}
-
-// PeriodicSampler is a concreted periodic sampler implementation.
-// The user provided Tag identifies the implementation, and is required to
-// isolate the global state of this instance from other instances.
-//
-// Typical use case:
-//
-//   struct HashTablezTag {};
-//   thread_local PeriodicSampler sampler;
-//
-//   void HashTableSamplingLogic(...) {
-//     if (sampler.Sample()) {
-//       HashTableSlowSamplePath(...);
-//     }
-//   }
-//
-template <typename Tag, int default_period = 0>
-class PeriodicSampler final : public PeriodicSamplerBase {
- public:
-  ~PeriodicSampler() = default;
-
-  int period() const noexcept final {
-    return period_.load(std::memory_order_relaxed);
-  }
-
-  // Sets the global period for this sampler. Thread-safe.
-  // Setting a period of 0 disables the sampler, i.e., every call to Sample()
-  // will return false. Setting a period of 1 puts the sampler in 'always on'
-  // mode, i.e., every call to Sample() returns true.
-  static void SetGlobalPeriod(int period) {
-    period_.store(period, std::memory_order_relaxed);
-  }
-
- private:
-  static std::atomic<int> period_;
-};
-
-template <typename Tag, int default_period>
-std::atomic<int> PeriodicSampler<Tag, default_period>::period_(default_period);
-
-}  // namespace base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
-
-#endif  // ABSL_BASE_INTERNAL_PERIODIC_SAMPLER_H_
diff --git a/absl/base/internal/periodic_sampler_benchmark.cc b/absl/base/internal/periodic_sampler_benchmark.cc
deleted file mode 100644
index 5ad469ce..00000000
--- a/absl/base/internal/periodic_sampler_benchmark.cc
+++ /dev/null
@@ -1,79 +0,0 @@
-// Copyright 2019 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 "benchmark/benchmark.h"
-#include "absl/base/internal/periodic_sampler.h"
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace base_internal {
-namespace {
-
-template <typename Sampler>
-void BM_Sample(Sampler* sampler, benchmark::State& state) {
-  for (auto _ : state) {
-    benchmark::DoNotOptimize(sampler);
-    benchmark::DoNotOptimize(sampler->Sample());
-  }
-}
-
-template <typename Sampler>
-void BM_SampleMinunumInlined(Sampler* sampler, benchmark::State& state) {
-  for (auto _ : state) {
-    benchmark::DoNotOptimize(sampler);
-    if (ABSL_PREDICT_FALSE(sampler->SubtleMaybeSample())) {
-      benchmark::DoNotOptimize(sampler->SubtleConfirmSample());
-    }
-  }
-}
-
-void BM_PeriodicSampler_TinySample(benchmark::State& state) {
-  struct Tag {};
-  PeriodicSampler<Tag, 10> sampler;
-  BM_Sample(&sampler, state);
-}
-BENCHMARK(BM_PeriodicSampler_TinySample);
-
-void BM_PeriodicSampler_ShortSample(benchmark::State& state) {
-  struct Tag {};
-  PeriodicSampler<Tag, 1024> sampler;
-  BM_Sample(&sampler, state);
-}
-BENCHMARK(BM_PeriodicSampler_ShortSample);
-
-void BM_PeriodicSampler_LongSample(benchmark::State& state) {
-  struct Tag {};
-  PeriodicSampler<Tag, 1024 * 1024> sampler;
-  BM_Sample(&sampler, state);
-}
-BENCHMARK(BM_PeriodicSampler_LongSample);
-
-void BM_PeriodicSampler_LongSampleMinunumInlined(benchmark::State& state) {
-  struct Tag {};
-  PeriodicSampler<Tag, 1024 * 1024> sampler;
-  BM_SampleMinunumInlined(&sampler, state);
-}
-BENCHMARK(BM_PeriodicSampler_LongSampleMinunumInlined);
-
-void BM_PeriodicSampler_Disabled(benchmark::State& state) {
-  struct Tag {};
-  PeriodicSampler<Tag, 0> sampler;
-  BM_Sample(&sampler, state);
-}
-BENCHMARK(BM_PeriodicSampler_Disabled);
-
-}  // namespace
-}  // namespace base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
diff --git a/absl/base/internal/periodic_sampler_test.cc b/absl/base/internal/periodic_sampler_test.cc
deleted file mode 100644
index 3b301e37..00000000
--- a/absl/base/internal/periodic_sampler_test.cc
+++ /dev/null
@@ -1,177 +0,0 @@
-// Copyright 2019 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 "absl/base/internal/periodic_sampler.h"
-
-#include <thread>  // NOLINT(build/c++11)
-
-#include "gmock/gmock.h"
-#include "gtest/gtest.h"
-#include "absl/base/attributes.h"
-#include "absl/base/macros.h"
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace base_internal {
-namespace {
-
-using testing::Eq;
-using testing::Return;
-using testing::StrictMock;
-
-class MockPeriodicSampler : public PeriodicSamplerBase {
- public:
-  virtual ~MockPeriodicSampler() = default;
-
-  MOCK_METHOD(int, period, (), (const, noexcept));
-  MOCK_METHOD(int64_t, GetExponentialBiased, (int), (noexcept));
-};
-
-TEST(PeriodicSamplerBaseTest, Sample) {
-  StrictMock<MockPeriodicSampler> sampler;
-
-  EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(16));
-  EXPECT_CALL(sampler, GetExponentialBiased(16))
-      .WillOnce(Return(2))
-      .WillOnce(Return(3))
-      .WillOnce(Return(4));
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_TRUE(sampler.Sample());
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_TRUE(sampler.Sample());
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-}
-
-TEST(PeriodicSamplerBaseTest, ImmediatelySample) {
-  StrictMock<MockPeriodicSampler> sampler;
-
-  EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
-  EXPECT_CALL(sampler, GetExponentialBiased(16))
-      .WillOnce(Return(1))
-      .WillOnce(Return(2))
-      .WillOnce(Return(3));
-
-  EXPECT_TRUE(sampler.Sample());
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_TRUE(sampler.Sample());
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-}
-
-TEST(PeriodicSamplerBaseTest, Disabled) {
-  StrictMock<MockPeriodicSampler> sampler;
-
-  EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(0));
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-}
-
-TEST(PeriodicSamplerBaseTest, AlwaysOn) {
-  StrictMock<MockPeriodicSampler> sampler;
-
-  EXPECT_CALL(sampler, period()).Times(3).WillRepeatedly(Return(1));
-
-  EXPECT_TRUE(sampler.Sample());
-  EXPECT_TRUE(sampler.Sample());
-  EXPECT_TRUE(sampler.Sample());
-}
-
-TEST(PeriodicSamplerBaseTest, Disable) {
-  StrictMock<MockPeriodicSampler> sampler;
-
-  EXPECT_CALL(sampler, period()).WillOnce(Return(16));
-  EXPECT_CALL(sampler, GetExponentialBiased(16)).WillOnce(Return(3));
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-
-  EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(0));
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-}
-
-TEST(PeriodicSamplerBaseTest, Enable) {
-  StrictMock<MockPeriodicSampler> sampler;
-
-  EXPECT_CALL(sampler, period()).WillOnce(Return(0));
-  EXPECT_FALSE(sampler.Sample());
-
-  EXPECT_CALL(sampler, period()).Times(2).WillRepeatedly(Return(16));
-  EXPECT_CALL(sampler, GetExponentialBiased(16))
-      .Times(2)
-      .WillRepeatedly(Return(3));
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_TRUE(sampler.Sample());
-
-  EXPECT_FALSE(sampler.Sample());
-  EXPECT_FALSE(sampler.Sample());
-}
-
-TEST(PeriodicSamplerTest, ConstructConstInit) {
-  struct Tag {};
-  ABSL_CONST_INIT static PeriodicSampler<Tag> sampler;
-  (void)sampler;
-}
-
-TEST(PeriodicSamplerTest, DefaultPeriod0) {
-  struct Tag {};
-  PeriodicSampler<Tag> sampler;
-  EXPECT_THAT(sampler.period(), Eq(0));
-}
-
-TEST(PeriodicSamplerTest, DefaultPeriod) {
-  struct Tag {};
-  PeriodicSampler<Tag, 100> sampler;
-  EXPECT_THAT(sampler.period(), Eq(100));
-}
-
-TEST(PeriodicSamplerTest, SetGlobalPeriod) {
-  struct Tag1 {};
-  struct Tag2 {};
-  PeriodicSampler<Tag1, 25> sampler1;
-  PeriodicSampler<Tag2, 50> sampler2;
-
-  EXPECT_THAT(sampler1.period(), Eq(25));
-  EXPECT_THAT(sampler2.period(), Eq(50));
-
-  std::thread thread([] {
-    PeriodicSampler<Tag1, 25> sampler1;
-    PeriodicSampler<Tag2, 50> sampler2;
-    EXPECT_THAT(sampler1.period(), Eq(25));
-    EXPECT_THAT(sampler2.period(), Eq(50));
-    sampler1.SetGlobalPeriod(10);
-    sampler2.SetGlobalPeriod(20);
-  });
-  thread.join();
-
-  EXPECT_THAT(sampler1.period(), Eq(10));
-  EXPECT_THAT(sampler2.period(), Eq(20));
-}
-
-}  // namespace
-}  // namespace base_internal
-ABSL_NAMESPACE_END
-}  // namespace absl
diff --git a/absl/base/internal/spinlock.h b/absl/base/internal/spinlock.h
index c73b5e09..ac40daff 100644
--- a/absl/base/internal/spinlock.h
+++ b/absl/base/internal/spinlock.h
@@ -16,13 +16,15 @@
 
 //  Most users requiring mutual exclusion should use Mutex.
 //  SpinLock is provided for use in two situations:
-//   - for use in code that Mutex itself depends on
+//   - for use by Abseil internal code that Mutex itself depends on
 //   - for async signal safety (see below)
 
 // SpinLock is async signal safe.  If a spinlock is used within a signal
 // handler, all code that acquires the lock must ensure that the signal cannot
 // arrive while they are holding the lock.  Typically, this is done by blocking
 // the signal.
+//
+// Threads waiting on a SpinLock may be woken in an arbitrary order.
 
 #ifndef ABSL_BASE_INTERNAL_SPINLOCK_H_
 #define ABSL_BASE_INTERNAL_SPINLOCK_H_
diff --git a/absl/base/internal/spinlock_wait.h b/absl/base/internal/spinlock_wait.h
index 579bd09f..9a1adcda 100644
--- a/absl/base/internal/spinlock_wait.h
+++ b/absl/base/internal/spinlock_wait.h
@@ -39,6 +39,8 @@ struct SpinLockWaitTransition {
 // satisfying 0<=i<n && trans[i].done, atomically make the transition,
 // then return the old value of *w.   Make any other atomic transitions
 // where !trans[i].done, but continue waiting.
+//
+// Wakeups for threads blocked on SpinLockWait do not respect priorities.
 uint32_t SpinLockWait(std::atomic<uint32_t> *w, int n,
                       const SpinLockWaitTransition trans[],
                       SchedulingMode scheduling_mode);