summaryrefslogtreecommitdiff
path: root/absl/base/internal/spinlock.cc
diff options
context:
space:
mode:
authorGravatar misterg <misterg@google.com>2017-09-19 16:54:40 -0400
committerGravatar misterg <misterg@google.com>2017-09-19 16:54:40 -0400
commitc2e754829628d1e9b7a16b3389cfdace76950fdf (patch)
tree5a7f056f44e27c30e10025113b644f0b3b5801fc /absl/base/internal/spinlock.cc
Initial Commit
Diffstat (limited to 'absl/base/internal/spinlock.cc')
-rw-r--r--absl/base/internal/spinlock.cc243
1 files changed, 243 insertions, 0 deletions
diff --git a/absl/base/internal/spinlock.cc b/absl/base/internal/spinlock.cc
new file mode 100644
index 00000000..6257bfce
--- /dev/null
+++ b/absl/base/internal/spinlock.cc
@@ -0,0 +1,243 @@
+// 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
+//
+// http://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 "absl/base/casts.h"
+#include "absl/base/internal/atomic_hook.h"
+#include "absl/base/internal/cycleclock.h"
+#include "absl/base/internal/spinlock_wait.h"
+#include "absl/base/internal/sysinfo.h" /* For NumCPUs() */
+
+// 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 {
+namespace base_internal {
+
+static int adaptive_spin_count = 0;
+
+namespace {
+struct SpinLock_InitHelper {
+ SpinLock_InitHelper() {
+ // On multi-cpu machines, spin for longer before yielding
+ // the processor or sleeping. Reduces idle time significantly.
+ if (base_internal::NumCPUs() > 1) {
+ adaptive_spin_count = 1000;
+ }
+ }
+};
+
+// Hook into global constructor execution:
+// We do not do adaptive spinning before that,
+// but nothing lock-intensive should be going on at that time.
+static SpinLock_InitHelper init_helper;
+
+ABSL_CONST_INIT static base_internal::AtomicHook<void (*)(const void *lock,
+ int64_t wait_cycles)>
+ submit_profile_data;
+
+} // namespace
+
+void RegisterSpinLockProfiler(void (*fn)(const void *contendedlock,
+ int64_t wait_cycles)) {
+ submit_profile_data.Store(fn);
+}
+
+static inline bool IsCooperative(
+ base_internal::SchedulingMode scheduling_mode) {
+ return scheduling_mode == base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL;
+}
+
+// Uncommon constructors.
+SpinLock::SpinLock(base_internal::SchedulingMode mode)
+ : lockword_(IsCooperative(mode) ? kSpinLockCooperative : 0) {
+ ABSL_TSAN_MUTEX_CREATE(this, 0);
+}
+
+SpinLock::SpinLock(base_internal::LinkerInitialized,
+ base_internal::SchedulingMode mode) {
+ ABSL_TSAN_MUTEX_CREATE(this, __tsan_mutex_linker_init);
+ if (IsCooperative(mode)) {
+ InitLinkerInitializedAndCooperative();
+ }
+ // Otherwise, lockword_ is already initialized.
+}
+
+// Static (linker initialized) spinlocks always start life as functional
+// non-cooperative locks. When their static constructor does run, it will call
+// this initializer to augment the lockword with the cooperative bit. By
+// actually taking the lock when we do this we avoid the need for an atomic
+// operation in the regular unlock path.
+//
+// SlowLock() must be careful to re-test for this bit so that any outstanding
+// waiters may be upgraded to cooperative status.
+void SpinLock::InitLinkerInitializedAndCooperative() {
+ Lock();
+ lockword_.fetch_or(kSpinLockCooperative, std::memory_order_relaxed);
+ Unlock();
+}
+
+// Monitor the lock to see if its value changes within some time period
+// (adaptive_spin_count loop iterations). A timestamp indicating
+// when the thread initially started waiting for the lock is passed in via
+// the initial_wait_timestamp value. The total wait time in cycles for the
+// lock is returned in the wait_cycles parameter. The last value read
+// from the lock is returned from the method.
+uint32_t SpinLock::SpinLoop(int64_t initial_wait_timestamp,
+ uint32_t *wait_cycles) {
+ int c = adaptive_spin_count;
+ uint32_t lock_value;
+ do {
+ lock_value = lockword_.load(std::memory_order_relaxed);
+ } while ((lock_value & kSpinLockHeld) != 0 && --c > 0);
+ uint32_t spin_loop_wait_cycles =
+ EncodeWaitCycles(initial_wait_timestamp, CycleClock::Now());
+ *wait_cycles = spin_loop_wait_cycles;
+
+ return TryLockInternal(lock_value, spin_loop_wait_cycles);
+}
+
+void SpinLock::SlowLock() {
+ // 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 stored in the lockword once this thread
+ // obtains the lock.
+ int64_t wait_start_time = CycleClock::Now();
+ uint32_t wait_cycles;
+ uint32_t lock_value = SpinLoop(wait_start_time, &wait_cycles);
+
+ 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 as that will cause the current lock
+ // owner to think it experienced contention.
+ if (lockword_.compare_exchange_strong(
+ lock_value, lock_value | kSpinLockSleeper,
+ std::memory_order_acquire, 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.
+ }
+ }
+
+ base_internal::SchedulingMode scheduling_mode;
+ if ((lock_value & kSpinLockCooperative) != 0) {
+ scheduling_mode = base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL;
+ } else {
+ scheduling_mode = base_internal::SCHEDULE_KERNEL_ONLY;
+ }
+ // 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.
+ base_internal::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(wait_start_time, &wait_cycles);
+ }
+}
+
+void SpinLock::SlowUnlock(uint32_t lock_value) {
+ base_internal::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 uint64_t wait_cycles = DecodeWaitCycles(lock_value);
+ ABSL_TSAN_MUTEX_PRE_DIVERT(this, 0);
+ submit_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^PROFILE_TIMESTAMP_SHIFT
+// 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.
+enum { PROFILE_TIMESTAMP_SHIFT = 7 };
+enum { LOCKWORD_RESERVED_SHIFT = 3 }; // We currently reserve the lower 3 bits.
+
+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() >> LOCKWORD_RESERVED_SHIFT;
+ int64_t scaled_wait_time =
+ (wait_end_time - wait_start_time) >> PROFILE_TIMESTAMP_SHIFT;
+
+ // Return a representation of the time spent waiting that can be stored in
+ // the lock word's upper bits. bit_cast is required as Atomic32 is signed.
+ const uint32_t clamped = static_cast<uint32_t>(
+ std::min(scaled_wait_time, kMaxWaitTime) << LOCKWORD_RESERVED_SHIFT);
+
+ // bump up value if necessary to avoid returning kSpinLockSleeper.
+ const uint32_t after_spinlock_sleeper =
+ kSpinLockSleeper + (1 << LOCKWORD_RESERVED_SHIFT);
+ return clamped == kSpinLockSleeper ? after_spinlock_sleeper : clamped;
+}
+
+uint64_t SpinLock::DecodeWaitCycles(uint32_t lock_value) {
+ // Cast to uint32_t first to ensure bits [63:32] are cleared.
+ const uint64_t scaled_wait_time =
+ static_cast<uint32_t>(lock_value & kWaitTimeMask);
+ return scaled_wait_time
+ << (PROFILE_TIMESTAMP_SHIFT - LOCKWORD_RESERVED_SHIFT);
+}
+
+} // namespace base_internal
+} // namespace absl