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