src/third_party/tcmalloc/vendor/src/base/spinlock_internal.cc

   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
  46 namespace 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
  56 namespace base {
  57 namespace internal {
  58
  59 // See spinlock_internal.h for spec.
  60 int32 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"
  80 static 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