// 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 {
inline namespace lts_2019_08_08 {
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];

static SpinLock static_spinlock(base_internal::kLinkerInitialized);
static SpinLock static_cooperative_spinlock(
    base_internal::kLinkerInitialized,
    base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL);
static SpinLock static_noncooperative_spinlock(
    base_internal::kLinkerInitialized, 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, StaticSpinLock) {
  ThreadedTest(&static_spinlock);
}

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
}  // inline namespace lts_2019_08_08
}  // namespace absl