1// Copyright 2017 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15// The OS-specific header included below must provide two calls:
16// AbslInternalSpinLockDelay() and AbslInternalSpinLockWake().
17// See spinlock_wait.h for the specs.
18
19#include <atomic>
20#include <cstdint>
21
22#include "absl/base/internal/spinlock_wait.h"
23
24#if defined(_WIN32)
25#include "absl/base/internal/spinlock_win32.inc"
26#elif defined(__linux__)
27#include "absl/base/internal/spinlock_linux.inc"
28#elif defined(__akaros__)
29#include "absl/base/internal/spinlock_akaros.inc"
30#else
31#include "absl/base/internal/spinlock_posix.inc"
32#endif
33
34namespace absl {
35namespace base_internal {
36
37// See spinlock_wait.h for spec.
38uint32_t SpinLockWait(std::atomic<uint32_t> *w, int n,
39 const SpinLockWaitTransition trans[],
40 base_internal::SchedulingMode scheduling_mode) {
41 int loop = 0;
42 for (;;) {
43 uint32_t v = w->load(std::memory_order_acquire);
44 int i;
45 for (i = 0; i != n && v != trans[i].from; i++) {
46 }
47 if (i == n) {
48 SpinLockDelay(w, v, ++loop, scheduling_mode); // no matching transition
49 } else if (trans[i].to == v || // null transition
50 w->compare_exchange_strong(v, trans[i].to,
51 std::memory_order_acquire,
52 std::memory_order_relaxed)) {
53 if (trans[i].done) return v;
54 }
55 }
56}
57
58static std::atomic<uint64_t> delay_rand;
59
60// Return a suggested delay in nanoseconds for iteration number "loop"
61int SpinLockSuggestedDelayNS(int loop) {
62 // Weak pseudo-random number generator to get some spread between threads
63 // when many are spinning.
64 uint64_t r = delay_rand.load(std::memory_order_relaxed);
65 r = 0x5deece66dLL * r + 0xb; // numbers from nrand48()
66 delay_rand.store(r, std::memory_order_relaxed);
67
68 if (loop < 0 || loop > 32) { // limit loop to 0..32
69 loop = 32;
70 }
71 const int kMinDelay = 128 << 10; // 128us
72 // Double delay every 8 iterations, up to 16x (2ms).
73 int delay = kMinDelay << (loop / 8);
74 // Randomize in delay..2*delay range, for resulting 128us..4ms range.
75 return delay | ((delay - 1) & static_cast<int>(r));
76}
77
78} // namespace base_internal
79} // namespace absl
80