// 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 "absl/base/internal/spinlock.h"

#include <algorithm>

#include <atomic>

#include <cstdint>

#include <limits>

#include "absl/base/attributes.h"

#include "absl/base/call_once.h"

#include "absl/base/config.h"

#include "absl/base/internal/atomic_hook.h"

#include "absl/base/internal/cycleclock.h"

#include "absl/base/internal/scheduling_mode.h"

#include "absl/base/internal/spinlock_wait.h"

#include "absl/base/internal/sysinfo.h" /* For NumCPUs() */

#include "absl/base/internal/tsan_mutex_interface.h"

#include "absl/base/nullability.h"

// Description of lock-word:

//  31..00: [............................3][2][1][0]

//

//     [0]: kSpinLockHeld

//     [1]: kSpinLockCooperative

//     [2]: kSpinLockDisabledScheduling

// [31..3]: ONLY kSpinLockSleeper OR

//          Wait time in cycles >> PROFILE_TIMESTAMP_SHIFT

//

// Detailed descriptions:

//

// Bit [0]: The lock is considered held iff kSpinLockHeld is set.

//

// Bit [1]: Eligible waiters (e.g. Fibers) may co-operatively reschedule when

//          contended iff kSpinLockCooperative is set.

//

// Bit [2]: This bit is exclusive from bit [1].  It is used only by a

//          non-cooperative lock.  When set, indicates that scheduling was

//          successfully disabled when the lock was acquired.  May be unset,

//          even if non-cooperative, if a ThreadIdentity did not yet exist at

//          time of acquisition.

//

// Bit [3]: If this is the only upper bit ([31..3]) set then this lock was

//          acquired without contention, however, at least one waiter exists.

//

//          Otherwise, bits [31..3] represent the time spent by the current lock

//          holder to acquire the lock.  There may be outstanding waiter(s).

namespace absl {

ABSL_NAMESPACE_BEGIN

namespace base_internal {

ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES static AtomicHook<void (*)(

    const void* lock, int64_t wait_cycles)>

    submit_unlock_profile_data;

ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES static AtomicHook<void (*)(

    const void* lock, int64_t wait_cycles)>

    submit_lock_profile_data;

void RegisterSpinLockProfiler(void (*absl_nonnull fn)(

    const void* absl_nonnull contendedlock, int64_t wait_cycles)) {

  submit_unlock_profile_data.Store(fn);

}

void RegisterSpinLockLockProfiler(void (*absl_nonnull fn)(

    const void* absl_nonnull contendedlock, int64_t wait_cycles)) {

  submit_lock_profile_data.Store(fn);

}

// Waits shorter than one profiling timestamp unit (see

// kProfileTimestampShift below) are not reported.

static constexpr int64_t kMinProfiledWaitCycles = 1 << 7;

// Report how long an acquiring thread was blocked, measured from the point

// at which it gave up spinning for the lock.

static void ReportLockWait(SpinLock& lock, int64_t wait_start_time,

                           int64_t wait_end_time) {

  const int64_t wait_cycles = wait_end_time - wait_start_time;

  if (wait_cycles < kMinProfiledWaitCycles) {

    return;

  }

  ABSL_TSAN_MUTEX_PRE_DIVERT(&lock, 0);

  submit_lock_profile_data(&lock, wait_cycles);

  ABSL_TSAN_MUTEX_POST_DIVERT(&lock, 0);

}

// Monitor the lock to see if its value changes within some time period

// (adaptive_spin_count_ loop iterations). The last value read from the lock

// is returned from the method.

ABSL_CONST_INIT std::atomic<int> SpinLock::adaptive_spin_count_{0};

uint32_t SpinLock::SpinLoop() {

  // We are already in the slow path of SpinLock, initialize the

  // adaptive_spin_count here.

  if (adaptive_spin_count_.load(std::memory_order_relaxed) == 0) {

    int current_spin_count = 0;

    int new_spin_count = NumCPUs() > 1 ? 1000 : 1;

    // If this fails, the value will remain unchanged. We may not spin for the

    // intended duration, but that is still safe. We will try again on the next

    // call to SpinLoop.

    adaptive_spin_count_.compare_exchange_weak(

        current_spin_count, new_spin_count, std::memory_order_relaxed,

        std::memory_order_relaxed);

  }

  int c = adaptive_spin_count_.load(std::memory_order_relaxed);

  uint32_t lock_value;

  do {

    lock_value = lockword_.load(std::memory_order_relaxed);

  } while ((lock_value & kSpinLockHeld) != 0 && --c > 0);

  return lock_value;

}

void SpinLock::SlowLock() {

  uint32_t lock_value = SpinLoop();

  lock_value = TryLockInternal(lock_value, 0);

  if ((lock_value & kSpinLockHeld) == 0) {

    return;

  }

  SchedulingMode scheduling_mode;

  if ((lock_value & kSpinLockCooperative) != 0) {

    scheduling_mode = SCHEDULE_COOPERATIVE_AND_KERNEL;

  } else {

    scheduling_mode = SCHEDULE_KERNEL_ONLY;

  }

  // The lock was not obtained initially, so this thread needs to wait for

  // it.  Record the current timestamp in the local variable wait_start_time

  // so the total wait time can be reported once this thread obtains the lock,

  // and stored in the lockword for the unlock-side profiler.

  const int64_t wait_start_time = CycleClock::Now();

  int64_t now = wait_start_time;

  uint32_t wait_cycles = 0;

  int lock_wait_call_count = 0;

  while ((lock_value & kSpinLockHeld) != 0) {

    // If the lock is currently held, but not marked as having a sleeper, mark

    // it as having a sleeper.

    if ((lock_value & kWaitTimeMask) == 0) {

      // Here, just "mark" that the thread is going to sleep.  Don't store the

      // lock wait time in the lock -- the lock word stores the amount of time

      // that the current holder waited before acquiring the lock, not the wait

      // time of any thread currently waiting to acquire it.

      if (lockword_.compare_exchange_strong(

              lock_value, lock_value | kSpinLockSleeper,

              std::memory_order_relaxed, std::memory_order_relaxed)) {

        // Successfully transitioned to kSpinLockSleeper.  Pass

        // kSpinLockSleeper to the SpinLockWait routine to properly indicate

        // the last lock_value observed.

        lock_value |= kSpinLockSleeper;

      } else if ((lock_value & kSpinLockHeld) == 0) {

        // Lock is free again, so try and acquire it before sleeping.  The

        // new lock state will be the number of cycles this thread waited if

        // this thread obtains the lock.

        lock_value = TryLockInternal(lock_value, wait_cycles);

        continue;  // Skip the delay at the end of the loop.

      } else if ((lock_value & kWaitTimeMask) == 0) {

        // The lock is still held, without a waiter being marked, but something

        // else about the lock word changed, causing our CAS to fail. For

        // example, a new lock holder may have acquired the lock with

        // kSpinLockDisabledScheduling set, whereas the previous holder had not

        // set that flag. In this case, attempt again to mark ourselves as a

        // waiter.

        continue;

      }

    }

    // SpinLockDelay() calls into fiber scheduler, we need to see

    // synchronization there to avoid false positives.

    ABSL_TSAN_MUTEX_PRE_DIVERT(this, 0);

    // Wait for an OS specific delay.

    SpinLockDelay(&lockword_, lock_value, ++lock_wait_call_count,

                  scheduling_mode);

    ABSL_TSAN_MUTEX_POST_DIVERT(this, 0);

    // Spin again after returning from the wait routine to give this thread

    // some chance of obtaining the lock.

    lock_value = SpinLoop();

    now = CycleClock::Now();

    wait_cycles = EncodeWaitCycles(wait_start_time, now);

    lock_value = TryLockInternal(lock_value, wait_cycles);

  }

  ReportLockWait(*this, wait_start_time, now);

}

void SpinLock::SlowUnlock(uint32_t lock_value) {

  SpinLockWake(&lockword_,

               false);  // wake waiter if necessary

  // If our acquisition was contended, collect contentionz profile info.  We

  // reserve a unitary wait time to represent that a waiter exists without our

  // own acquisition having been contended.

  if ((lock_value & kWaitTimeMask) != kSpinLockSleeper) {

    const int64_t wait_cycles = DecodeWaitCycles(lock_value);

    ABSL_TSAN_MUTEX_PRE_DIVERT(this, 0);

    submit_unlock_profile_data(this, wait_cycles);

    ABSL_TSAN_MUTEX_POST_DIVERT(this, 0);

  }

}

// We use the upper 29 bits of the lock word to store the time spent waiting to

// acquire this lock.  This is reported by contentionz profiling.  Since the

// lower bits of the cycle counter wrap very quickly on high-frequency

// processors we divide to reduce the granularity to 2^kProfileTimestampShift

// sized units.  On a 4Ghz machine this will lose track of wait times greater

// than (2^29/4 Ghz)*128 =~ 17.2 seconds.  Such waits should be extremely rare.

static constexpr int kProfileTimestampShift = 7;

// We currently reserve the lower 3 bits.

static constexpr int kLockwordReservedShift = 3;

uint32_t SpinLock::EncodeWaitCycles(int64_t wait_start_time,

                                    int64_t wait_end_time) {

  static const int64_t kMaxWaitTime =

      std::numeric_limits<uint32_t>::max() >> kLockwordReservedShift;

  int64_t scaled_wait_time =

      (wait_end_time - wait_start_time) >> kProfileTimestampShift;

  // Return a representation of the time spent waiting that can be stored in

  // the lock word's upper bits.

  uint32_t clamped = static_cast<uint32_t>(

      std::min(scaled_wait_time, kMaxWaitTime) << kLockwordReservedShift);

  if (clamped == 0) {

    return kSpinLockSleeper;  // Just wake waiters, but don't record contention.

  }

  // Bump up value if necessary to avoid returning kSpinLockSleeper.

  const uint32_t kMinWaitTime =

      kSpinLockSleeper + (1 << kLockwordReservedShift);

  if (clamped == kSpinLockSleeper) {

    return kMinWaitTime;

  }

  return clamped;

}

int64_t SpinLock::DecodeWaitCycles(uint32_t lock_value) {

  // Cast to uint32_t first to ensure bits [63:32] are cleared.

  const int64_t scaled_wait_time =

      static_cast<uint32_t>(lock_value & kWaitTimeMask);

  return scaled_wait_time << (kProfileTimestampShift - kLockwordReservedShift);

}

}  // namespace base_internal

ABSL_NAMESPACE_END

}  // namespace absl