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
34 namespace absl {
35 ABSL_NAMESPACE_BEGIN
36 namespace base_internal {
37
38 // See spinlock_wait.h for spec.
SpinLockWait(std::atomic<uint32_t> * w,int n,const SpinLockWaitTransition trans[],base_internal::SchedulingMode scheduling_mode)39 uint32_t SpinLockWait(std::atomic<uint32_t> *w, int n,
40 const SpinLockWaitTransition trans[],
41 base_internal::SchedulingMode scheduling_mode) {
42 int loop = 0;
43 for (;;) {
44 uint32_t v = w->load(std::memory_order_acquire);
45 int i;
46 for (i = 0; i != n && v != trans[i].from; i++) {
47 }
48 if (i == n) {
49 SpinLockDelay(w, v, ++loop, scheduling_mode); // no matching transition
50 } else if (trans[i].to == v || // null transition
51 w->compare_exchange_strong(v, trans[i].to,
52 std::memory_order_acquire,
53 std::memory_order_relaxed)) {
54 if (trans[i].done) return v;
55 }
56 }
57 }
58
59 static std::atomic<uint64_t> delay_rand;
60
61 // Return a suggested delay in nanoseconds for iteration number "loop"
SpinLockSuggestedDelayNS(int loop)62 int SpinLockSuggestedDelayNS(int loop) {
63 // Weak pseudo-random number generator to get some spread between threads
64 // when many are spinning.
65 uint64_t r = delay_rand.load(std::memory_order_relaxed);
66 r = 0x5deece66dLL * r + 0xb; // numbers from nrand48()
67 delay_rand.store(r, std::memory_order_relaxed);
68
69 if (loop < 0 || loop > 32) { // limit loop to 0..32
70 loop = 32;
71 }
72 const int kMinDelay = 128 << 10; // 128us
73 // Double delay every 8 iterations, up to 16x (2ms).
74 int delay = kMinDelay << (loop / 8);
75 // Randomize in delay..2*delay range, for resulting 128us..4ms range.
76 return delay | ((delay - 1) & static_cast<int>(r));
77 }
78
79 } // namespace base_internal
80 ABSL_NAMESPACE_END
81 } // namespace absl
82