blob: e090f9b29fd77c28def87e19e9ccc822c299895c [file] [log] [blame]
Austin Schuh745610d2015-09-06 18:19:50 -07001// -*- 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
47namespace 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
57namespace base {
58namespace internal {
59
60// See spinlock_internal.h for spec.
61int32 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"
81static 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