aboutsummaryrefslogtreecommitdiffstats
path: root/contrib/restricted/abseil-cpp-tstring/y_absl/base/internal/spinlock.h
blob: b2e0ee8bbc0187add0a372b4baeef6e348e6c871 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
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.
//

//  Most users requiring mutual exclusion should use Mutex.
//  SpinLock is provided for use in two situations:
//   - for use by Abseil internal code that Mutex itself depends on
//   - for async signal safety (see below)

// SpinLock with a base_internal::SchedulingMode::SCHEDULE_KERNEL_ONLY 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 Y_ABSL_BASE_INTERNAL_SPINLOCK_H_
#define Y_ABSL_BASE_INTERNAL_SPINLOCK_H_

#include <atomic>
#include <cstdint>

#include "y_absl/base/attributes.h"
#include "y_absl/base/const_init.h"
#include "y_absl/base/dynamic_annotations.h"
#include "y_absl/base/internal/low_level_scheduling.h"
#include "y_absl/base/internal/raw_logging.h"
#include "y_absl/base/internal/scheduling_mode.h"
#include "y_absl/base/internal/tsan_mutex_interface.h"
#include "y_absl/base/thread_annotations.h"

namespace tcmalloc {
namespace tcmalloc_internal {

class AllocationGuardSpinLockHolder;

}  // namespace tcmalloc_internal
}  // namespace tcmalloc

namespace y_absl {
Y_ABSL_NAMESPACE_BEGIN
namespace base_internal {

class Y_ABSL_LOCKABLE SpinLock {
 public:
  SpinLock() : lockword_(kSpinLockCooperative) {
    Y_ABSL_TSAN_MUTEX_CREATE(this, __tsan_mutex_not_static);
  }

  // Constructors that allow non-cooperative spinlocks to be created for use
  // inside thread schedulers.  Normal clients should not use these.
  explicit SpinLock(base_internal::SchedulingMode mode);

  // Constructor for global SpinLock instances.  See y_absl/base/const_init.h.
  constexpr SpinLock(y_absl::ConstInitType, base_internal::SchedulingMode mode)
      : lockword_(IsCooperative(mode) ? kSpinLockCooperative : 0) {}

  // For global SpinLock instances prefer trivial destructor when possible.
  // Default but non-trivial destructor in some build configurations causes an
  // extra static initializer.
#ifdef Y_ABSL_INTERNAL_HAVE_TSAN_INTERFACE
  ~SpinLock() { Y_ABSL_TSAN_MUTEX_DESTROY(this, __tsan_mutex_not_static); }
#else
  ~SpinLock() = default;
#endif

  // Acquire this SpinLock.
  inline void Lock() Y_ABSL_EXCLUSIVE_LOCK_FUNCTION() {
    Y_ABSL_TSAN_MUTEX_PRE_LOCK(this, 0);
    if (!TryLockImpl()) {
      SlowLock();
    }
    Y_ABSL_TSAN_MUTEX_POST_LOCK(this, 0, 0);
  }

  // Try to acquire this SpinLock without blocking and return true if the
  // acquisition was successful.  If the lock was not acquired, false is
  // returned.  If this SpinLock is free at the time of the call, TryLock
  // will return true with high probability.
  inline bool TryLock() Y_ABSL_EXCLUSIVE_TRYLOCK_FUNCTION(true) {
    Y_ABSL_TSAN_MUTEX_PRE_LOCK(this, __tsan_mutex_try_lock);
    bool res = TryLockImpl();
    Y_ABSL_TSAN_MUTEX_POST_LOCK(
        this, __tsan_mutex_try_lock | (res ? 0 : __tsan_mutex_try_lock_failed),
        0);
    return res;
  }

  // Release this SpinLock, which must be held by the calling thread.
  inline void Unlock() Y_ABSL_UNLOCK_FUNCTION() {
    Y_ABSL_TSAN_MUTEX_PRE_UNLOCK(this, 0);
    uint32_t lock_value = lockword_.load(std::memory_order_relaxed);
    lock_value = lockword_.exchange(lock_value & kSpinLockCooperative,
                                    std::memory_order_release);

    if ((lock_value & kSpinLockDisabledScheduling) != 0) {
      base_internal::SchedulingGuard::EnableRescheduling(true);
    }
    if ((lock_value & kWaitTimeMask) != 0) {
      // Collect contentionz profile info, and speed the wakeup of any waiter.
      // The wait_cycles value indicates how long this thread spent waiting
      // for the lock.
      SlowUnlock(lock_value);
    }
    Y_ABSL_TSAN_MUTEX_POST_UNLOCK(this, 0);
  }

  // Determine if the lock is held.  When the lock is held by the invoking
  // thread, true will always be returned. Intended to be used as
  // CHECK(lock.IsHeld()).
  inline bool IsHeld() const {
    return (lockword_.load(std::memory_order_relaxed) & kSpinLockHeld) != 0;
  }

  // Return immediately if this thread holds the SpinLock exclusively.
  // Otherwise, report an error by crashing with a diagnostic.
  inline void AssertHeld() const Y_ABSL_ASSERT_EXCLUSIVE_LOCK() {
    if (!IsHeld()) {
      Y_ABSL_RAW_LOG(FATAL, "thread should hold the lock on SpinLock");
    }
  }

 protected:
  // These should not be exported except for testing.

  // Store number of cycles between wait_start_time and wait_end_time in a
  // lock value.
  static uint32_t EncodeWaitCycles(int64_t wait_start_time,
                                   int64_t wait_end_time);

  // Extract number of wait cycles in a lock value.
  static int64_t DecodeWaitCycles(uint32_t lock_value);

  // Provide access to protected method above.  Use for testing only.
  friend struct SpinLockTest;
  friend class tcmalloc::tcmalloc_internal::AllocationGuardSpinLockHolder;

 private:
  // lockword_ is used to store the following:
  //
  // bit[0] encodes whether a lock is being held.
  // bit[1] encodes whether a lock uses cooperative scheduling.
  // bit[2] encodes whether the current lock holder disabled scheduling when
  //        acquiring the lock. Only set when kSpinLockHeld is also set.
  // bit[3:31] encodes time a lock spent on waiting as a 29-bit unsigned int.
  //        This is set by the lock holder to indicate how long it waited on
  //        the lock before eventually acquiring it. The number of cycles is
  //        encoded as a 29-bit unsigned int, or in the case that the current
  //        holder did not wait but another waiter is queued, the LSB
  //        (kSpinLockSleeper) is set. The implementation does not explicitly
  //        track the number of queued waiters beyond this. It must always be
  //        assumed that waiters may exist if the current holder was required to
  //        queue.
  //
  // Invariant: if the lock is not held, the value is either 0 or
  // kSpinLockCooperative.
  static constexpr uint32_t kSpinLockHeld = 1;
  static constexpr uint32_t kSpinLockCooperative = 2;
  static constexpr uint32_t kSpinLockDisabledScheduling = 4;
  static constexpr uint32_t kSpinLockSleeper = 8;
  // Includes kSpinLockSleeper.
  static constexpr uint32_t kWaitTimeMask =
      ~(kSpinLockHeld | kSpinLockCooperative | kSpinLockDisabledScheduling);

  // Returns true if the provided scheduling mode is cooperative.
  static constexpr bool IsCooperative(
      base_internal::SchedulingMode scheduling_mode) {
    return scheduling_mode == base_internal::SCHEDULE_COOPERATIVE_AND_KERNEL;
  }

  bool IsCooperative() const {
    return lockword_.load(std::memory_order_relaxed) & kSpinLockCooperative;
  }

  uint32_t TryLockInternal(uint32_t lock_value, uint32_t wait_cycles);
  void SlowLock() Y_ABSL_ATTRIBUTE_COLD;
  void SlowUnlock(uint32_t lock_value) Y_ABSL_ATTRIBUTE_COLD;
  uint32_t SpinLoop();

  inline bool TryLockImpl() {
    uint32_t lock_value = lockword_.load(std::memory_order_relaxed);
    return (TryLockInternal(lock_value, 0) & kSpinLockHeld) == 0;
  }

  std::atomic<uint32_t> lockword_;

  SpinLock(const SpinLock&) = delete;
  SpinLock& operator=(const SpinLock&) = delete;
};

// Corresponding locker object that arranges to acquire a spinlock for
// the duration of a C++ scope.
class Y_ABSL_SCOPED_LOCKABLE SpinLockHolder {
 public:
  inline explicit SpinLockHolder(SpinLock* l) Y_ABSL_EXCLUSIVE_LOCK_FUNCTION(l)
      : lock_(l) {
    l->Lock();
  }
  inline ~SpinLockHolder() Y_ABSL_UNLOCK_FUNCTION() { lock_->Unlock(); }

  SpinLockHolder(const SpinLockHolder&) = delete;
  SpinLockHolder& operator=(const SpinLockHolder&) = delete;

 private:
  SpinLock* lock_;
};

// Register a hook for profiling support.
//
// The function pointer registered here will be called whenever a spinlock is
// contended.  The callback is given an opaque handle to the contended spinlock
// and the number of wait cycles.  This is thread-safe, but only a single
// profiler can be registered.  It is an error to call this function multiple
// times with different arguments.
void RegisterSpinLockProfiler(void (*fn)(const void* lock,
                                         int64_t wait_cycles));

//------------------------------------------------------------------------------
// Public interface ends here.
//------------------------------------------------------------------------------

// If (result & kSpinLockHeld) == 0, then *this was successfully locked.
// Otherwise, returns last observed value for lockword_.
inline uint32_t SpinLock::TryLockInternal(uint32_t lock_value,
                                          uint32_t wait_cycles) {
  if ((lock_value & kSpinLockHeld) != 0) {
    return lock_value;
  }

  uint32_t sched_disabled_bit = 0;
  if ((lock_value & kSpinLockCooperative) == 0) {
    // For non-cooperative locks we must make sure we mark ourselves as
    // non-reschedulable before we attempt to CompareAndSwap.
    if (base_internal::SchedulingGuard::DisableRescheduling()) {
      sched_disabled_bit = kSpinLockDisabledScheduling;
    }
  }

  if (!lockword_.compare_exchange_strong(
          lock_value,
          kSpinLockHeld | lock_value | wait_cycles | sched_disabled_bit,
          std::memory_order_acquire, std::memory_order_relaxed)) {
    base_internal::SchedulingGuard::EnableRescheduling(sched_disabled_bit != 0);
  }

  return lock_value;
}

}  // namespace base_internal
Y_ABSL_NAMESPACE_END
}  // namespace y_absl

#endif  // Y_ABSL_BASE_INTERNAL_SPINLOCK_H_