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