spinlock_wait.cc (2826B)
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. 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" 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