Add 'third_party/abseil_cpp/' from commit '768eb2ca2857342673fcd462792ce04b8bac3fa3' r/781

git-subtree-dir: third_party/abseil_cpp
git-subtree-mainline: ffb2ae54beb5796cd408fbe15d2d2da09ff37adf
git-subtree-split: 768eb2ca2857342673fcd462792ce04b8bac3fa3

1 files changed, 265 insertions, 0 deletions

diff --git a/third_party/abseil_cpp/absl/base/spinlock_test_common.cc b/third_party/abseil_cpp/absl/base/spinlock_test_common.cc
new file mode 100644
index 000000000000..b68c51a1dcde
--- /dev/null
+++ b/third_party/abseil_cpp/absl/base/spinlock_test_common.cc
@@ -0,0 +1,265 @@
+// 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.
+
+// A bunch of threads repeatedly hash an array of ints protected by a
+// spinlock.  If the spinlock is working properly, all elements of the
+// array should be equal at the end of the test.
+
+#include <cstdint>
+#include <limits>
+#include <random>
+#include <thread>  // NOLINT(build/c++11)
+#include <vector>
+
+#include "gtest/gtest.h"
+#include "absl/base/attributes.h"
+#include "absl/base/internal/low_level_scheduling.h"
+#include "absl/base/internal/scheduling_mode.h"
+#include "absl/base/internal/spinlock.h"
+#include "absl/base/internal/sysinfo.h"
+#include "absl/base/macros.h"
+#include "absl/synchronization/blocking_counter.h"
+#include "absl/synchronization/notification.h"
+
+constexpr int32_t kNumThreads = 10;
+constexpr int32_t kIters = 1000;
+
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace base_internal {
+
+// 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 uint64_t DecodeWaitCycles(uint32_t lock_value) {
+    return SpinLock::DecodeWaitCycles(lock_value);
+  }
+};
+
+namespace {
+
+static constexpr int kArrayLength = 10;
+static uint32_t values[kArrayLength];
+
+ABSL_CONST_INIT static SpinLock static_cooperative_spinlock(
+    absl::kConstInit, base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL);
+ABSL_CONST_INIT static SpinLock static_noncooperative_spinlock(
+    absl::kConstInit, base_internal::SCHEDULE_KERNEL_ONLY);
+
+// Simple integer hash function based on the public domain lookup2 hash.
+// http://burtleburtle.net/bob/c/lookup2.c
+static uint32_t Hash32(uint32_t a, uint32_t c) {
+  uint32_t b = 0x9e3779b9UL;  // The golden ratio; an arbitrary value.
+  a -= b; a -= c; a ^= (c >> 13);
+  b -= c; b -= a; b ^= (a << 8);
+  c -= a; c -= b; c ^= (b >> 13);
+  a -= b; a -= c; a ^= (c >> 12);
+  b -= c; b -= a; b ^= (a << 16);
+  c -= a; c -= b; c ^= (b >> 5);
+  a -= b; a -= c; a ^= (c >> 3);
+  b -= c; b -= a; b ^= (a << 10);
+  c -= a; c -= b; c ^= (b >> 15);
+  return c;
+}
+
+static void TestFunction(int thread_salt, SpinLock* spinlock) {
+  for (int i = 0; i < kIters; i++) {
+    SpinLockHolder h(spinlock);
+    for (int j = 0; j < kArrayLength; j++) {
+      const int index = (j + thread_salt) % kArrayLength;
+      values[index] = Hash32(values[index], thread_salt);
+      std::this_thread::yield();
+    }
+  }
+}
+
+static void ThreadedTest(SpinLock* spinlock) {
+  std::vector<std::thread> threads;
+  for (int i = 0; i < kNumThreads; ++i) {
+    threads.push_back(std::thread(TestFunction, i, spinlock));
+  }
+  for (auto& thread : threads) {
+    thread.join();
+  }
+
+  SpinLockHolder h(spinlock);
+  for (int i = 1; i < kArrayLength; i++) {
+    EXPECT_EQ(values[0], values[i]);
+  }
+}
+
+TEST(SpinLock, StackNonCooperativeDisablesScheduling) {
+  SpinLock spinlock(base_internal::SCHEDULE_KERNEL_ONLY);
+  spinlock.Lock();
+  EXPECT_FALSE(base_internal::SchedulingGuard::ReschedulingIsAllowed());
+  spinlock.Unlock();
+}
+
+TEST(SpinLock, StaticNonCooperativeDisablesScheduling) {
+  static_noncooperative_spinlock.Lock();
+  EXPECT_FALSE(base_internal::SchedulingGuard::ReschedulingIsAllowed());
+  static_noncooperative_spinlock.Unlock();
+}
+
+TEST(SpinLock, WaitCyclesEncoding) {
+  // 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 uint64_t kMaxCycles = (int64_t{1} << kMaxCyclesShift) - 1;
+
+  // These bits should be zero after encoding.
+  const uint32_t kLockwordReservedMask = (1 << kLockwordReservedShift) - 1;
+
+  // These bits are dropped when wait cycles are encoded.
+  const uint64_t kProfileTimestampMask = (1 << kProfileTimestampShift) - 1;
+
+  // Test a bunch of random values
+  std::default_random_engine generator;
+  // Shift to avoid overflow below.
+  std::uniform_int_distribution<uint64_t> time_distribution(
+      0, std::numeric_limits<uint64_t>::max() >> 4);
+  std::uniform_int_distribution<uint64_t> cycle_distribution(0, kMaxCycles);
+
+  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);
+    EXPECT_EQ(0, lock_value & kLockwordReservedMask);
+    uint64_t decoded = SpinLockTest::DecodeWaitCycles(lock_value);
+    EXPECT_EQ(0, decoded & kProfileTimestampMask);
+    EXPECT_EQ(cycles & ~kProfileTimestampMask, decoded);
+  }
+
+  // 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));
+
+  // 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);
+  uint64_t max_value_decoded = SpinLockTest::DecodeWaitCycles(max_value);
+  uint64_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);
+  uint64_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);
+  uint64_t before_max_value_decoded =
+    SpinLockTest::DecodeWaitCycles(before_max_value);
+  EXPECT_GT(expected_max_value_decoded, before_max_value_decoded);
+}
+
+TEST(SpinLockWithThreads, StackSpinLock) {
+  SpinLock spinlock;
+  ThreadedTest(&spinlock);
+}
+
+TEST(SpinLockWithThreads, StackCooperativeSpinLock) {
+  SpinLock spinlock(base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL);
+  ThreadedTest(&spinlock);
+}
+
+TEST(SpinLockWithThreads, StackNonCooperativeSpinLock) {
+  SpinLock spinlock(base_internal::SCHEDULE_KERNEL_ONLY);
+  ThreadedTest(&spinlock);
+}
+
+TEST(SpinLockWithThreads, StaticCooperativeSpinLock) {
+  ThreadedTest(&static_cooperative_spinlock);
+}
+
+TEST(SpinLockWithThreads, StaticNonCooperativeSpinLock) {
+  ThreadedTest(&static_noncooperative_spinlock);
+}
+
+TEST(SpinLockWithThreads, DoesNotDeadlock) {
+  struct Helper {
+    static void NotifyThenLock(Notification* locked, SpinLock* spinlock,
+                               BlockingCounter* b) {
+      locked->WaitForNotification();  // Wait for LockThenWait() to hold "s".
+      b->DecrementCount();
+      SpinLockHolder l(spinlock);
+    }
+
+    static void LockThenWait(Notification* locked, SpinLock* spinlock,
+                             BlockingCounter* b) {
+      SpinLockHolder l(spinlock);
+      locked->Notify();
+      b->Wait();
+    }
+
+    static void DeadlockTest(SpinLock* spinlock, int num_spinners) {
+      Notification locked;
+      BlockingCounter counter(num_spinners);
+      std::vector<std::thread> threads;
+
+      threads.push_back(
+          std::thread(Helper::LockThenWait, &locked, spinlock, &counter));
+      for (int i = 0; i < num_spinners; ++i) {
+        threads.push_back(
+            std::thread(Helper::NotifyThenLock, &locked, spinlock, &counter));
+      }
+
+      for (auto& thread : threads) {
+        thread.join();
+      }
+    }
+  };
+
+  SpinLock stack_cooperative_spinlock(
+      base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL);
+  SpinLock stack_noncooperative_spinlock(base_internal::SCHEDULE_KERNEL_ONLY);
+  Helper::DeadlockTest(&stack_cooperative_spinlock,
+                       base_internal::NumCPUs() * 2);
+  Helper::DeadlockTest(&stack_noncooperative_spinlock,
+                       base_internal::NumCPUs() * 2);
+  Helper::DeadlockTest(&static_cooperative_spinlock,
+                       base_internal::NumCPUs() * 2);
+  Helper::DeadlockTest(&static_noncooperative_spinlock,
+                       base_internal::NumCPUs() * 2);
+}
+
+}  // namespace
+}  // namespace base_internal
+ABSL_NAMESPACE_END
+}  // namespace absl