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