1/* Copyright (c) 2010, Google Inc. 2 * All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions are 6 * met: 7 * 8 * * Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * * Redistributions in binary form must reproduce the above 11 * copyright notice, this list of conditions and the following disclaimer 12 * in the documentation and/or other materials provided with the 13 * distribution. 14 * * Neither the name of Google Inc. nor the names of its 15 * contributors may be used to endorse or promote products derived from 16 * this software without specific prior written permission. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 */ 30 31// The OS-specific header included below must provide two calls: 32// base::internal::SpinLockDelay() and base::internal::SpinLockWake(). 33// See spinlock_internal.h for the spec of SpinLockWake(). 34 35// void SpinLockDelay(volatile Atomic32 *w, int32 value, int loop) 36// SpinLockDelay() generates an apprproate spin delay on iteration "loop" of a 37// spin loop on location *w, whose previously observed value was "value". 38// SpinLockDelay() may do nothing, may yield the CPU, may sleep a clock tick, 39// or may wait for a delay that can be truncated by a call to SpinlockWake(w). 40// In all cases, it must return in bounded time even if SpinlockWake() is not 41// called. 42 43#include "base/spinlock_internal.h" 44 45// forward declaration for use by spinlock_*-inl.h 46namespace base { namespace internal { static int SuggestedDelayNS(int loop); }} 47 48#if defined(_WIN32) 49#include "base/spinlock_win32-inl.h" 50#elif defined(__linux__) 51#include "base/spinlock_linux-inl.h" 52#else 53#include "base/spinlock_posix-inl.h" 54#endif 55 56namespace base { 57namespace internal { 58 59// See spinlock_internal.h for spec. 60int32 SpinLockWait(volatile Atomic32 *w, int n, 61 const SpinLockWaitTransition trans[]) { 62 int32 v; 63 bool done = false; 64 for (int loop = 0; !done; loop++) { 65 v = base::subtle::Acquire_Load(w); 66 int i; 67 for (i = 0; i != n && v != trans[i].from; i++) { 68 } 69 if (i == n) { 70 SpinLockDelay(w, v, loop); // no matching transition 71 } else if (trans[i].to == v || // null transition 72 base::subtle::Acquire_CompareAndSwap(w, v, trans[i].to) == v) { 73 done = trans[i].done; 74 } 75 } 76 return v; 77} 78 79// Return a suggested delay in nanoseconds for iteration number "loop" 80static int SuggestedDelayNS(int loop) { 81 // Weak pseudo-random number generator to get some spread between threads 82 // when many are spinning. 83 static base::subtle::Atomic64 rand; 84 uint64 r = base::subtle::NoBarrier_Load(&rand); 85 r = 0x5deece66dLL * r + 0xb; // numbers from nrand48() 86 base::subtle::NoBarrier_Store(&rand, r); 87 88 r <<= 16; // 48-bit random number now in top 48-bits. 89 if (loop < 0 || loop > 32) { // limit loop to 0..32 90 loop = 32; 91 } 92 // loop>>3 cannot exceed 4 because loop cannot exceed 32. 93 // Select top 20..24 bits of lower 48 bits, 94 // giving approximately 0ms to 16ms. 95 // Mean is exponential in loop for first 32 iterations, then 8ms. 96 // The futex path multiplies this by 16, since we expect explicit wakeups 97 // almost always on that path. 98 return r >> (44 - (loop >> 3)); 99} 100 101} // namespace internal 102} // namespace base 103