15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Copyright (c) 2010, Google Inc. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * All rights reserved. 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * modification, are permitted provided that the following conditions are 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * met: 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Redistributions of source code must retain the above copyright 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Redistributions in binary form must reproduce the above 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * in the documentation and/or other materials provided with the 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * distribution. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * * Neither the name of Google Inc. nor the names of its 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * contributors may be used to endorse or promote products derived from 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * this software without specific prior written permission. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The OS-specific header included below must provide two calls: 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// base::internal::SpinLockDelay() and base::internal::SpinLockWake(). 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See spinlock_internal.h for the spec of SpinLockWake(). 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// void SpinLockDelay(volatile Atomic32 *w, int32 value, int loop) 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SpinLockDelay() generates an apprproate spin delay on iteration "loop" of a 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// spin loop on location *w, whose previously observed value was "value". 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SpinLockDelay() may do nothing, may yield the CPU, may sleep a clock tick, 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// or may wait for a delay that can be truncated by a call to SpinlockWake(w). 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// In all cases, it must return in bounded time even if SpinlockWake() is not 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// called. 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock_internal.h" 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// forward declaration for use by spinlock_*-inl.h 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { namespace internal { static int SuggestedDelayNS(int loop); }} 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if defined(_WIN32) 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock_win32-inl.h" 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#elif defined(__linux__) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock_linux-inl.h" 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#else 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/spinlock_posix-inl.h" 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace internal { 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See spinlock_internal.h for spec. 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int32 SpinLockWait(volatile Atomic32 *w, int n, 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const SpinLockWaitTransition trans[]) { 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int32 v; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) bool done = false; 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int loop = 0; !done; loop++) { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) v = base::subtle::Acquire_Load(w); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i; 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (i = 0; i != n && v != trans[i].from; i++) { 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i == n) { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SpinLockDelay(w, v, loop); // no matching transition 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else if (trans[i].to == v || // null transition 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::subtle::Acquire_CompareAndSwap(w, v, trans[i].to) == v) { 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) done = trans[i].done; 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return v; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return a suggested delay in nanoseconds for iteration number "loop" 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int SuggestedDelayNS(int loop) { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Weak pseudo-random number generator to get some spread between threads 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // when many are spinning. 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) static base::subtle::Atomic64 rand; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) uint64 r = base::subtle::NoBarrier_Load(&rand); 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r = 0x5deece66dLL * r + 0xb; // numbers from nrand48() 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) base::subtle::NoBarrier_Store(&rand, r); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) r <<= 16; // 48-bit random number now in top 48-bits. 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (loop < 0 || loop > 32) { // limit loop to 0..32 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) loop = 32; 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // loop>>3 cannot exceed 4 because loop cannot exceed 32. 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Select top 20..24 bits of lower 48 bits, 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // giving approximately 0ms to 16ms. 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Mean is exponential in loop for first 32 iterations, then 8ms. 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // The futex path multiplies this by 16, since we expect explicit wakeups 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // almost always on that path. 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return r >> (44 - (loop >> 3)); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace internal 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace base 103