Home | History | Annotate | Download | only in base 
      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
    103