OLD | NEW |
1 /* Copyright (c) 2010, Google Inc. | 1 /* Copyright (c) 2010, Google Inc. |
2 * All rights reserved. | 2 * All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions are | 5 * modification, are permitted provided that the following conditions are |
6 * met: | 6 * met: |
7 * | 7 * |
8 * * Redistributions of source code must retain the above copyright | 8 * * Redistributions of source code must retain the above copyright |
9 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
10 * * Redistributions in binary form must reproduce the above | 10 * * Redistributions in binary form must reproduce the above |
(...skipping 24 matching lines...) Expand all Loading... |
35 // void SpinLockDelay(volatile Atomic32 *w, int32 value, int loop) | 35 // void SpinLockDelay(volatile Atomic32 *w, int32 value, int loop) |
36 // SpinLockDelay() generates an apprproate spin delay on iteration "loop" of a | 36 // SpinLockDelay() generates an apprproate spin delay on iteration "loop" of a |
37 // spin loop on location *w, whose previously observed value was "value". | 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, | 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). | 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 | 40 // In all cases, it must return in bounded time even if SpinlockWake() is not |
41 // called. | 41 // called. |
42 | 42 |
43 #include "base/spinlock_internal.h" | 43 #include "base/spinlock_internal.h" |
44 | 44 |
| 45 // forward declaration for use by spinlock_*-inl.h |
| 46 namespace base { namespace internal { static int SuggestedDelayNS(int loop); }} |
| 47 |
45 #if defined(_WIN32) | 48 #if defined(_WIN32) |
46 #include "base/spinlock_win32-inl.h" | 49 #include "base/spinlock_win32-inl.h" |
47 #elif defined(__linux__) | 50 #elif defined(__linux__) |
48 #include "base/spinlock_linux-inl.h" | 51 #include "base/spinlock_linux-inl.h" |
49 #else | 52 #else |
50 #include "base/spinlock_posix-inl.h" | 53 #include "base/spinlock_posix-inl.h" |
51 #endif | 54 #endif |
52 | 55 |
53 namespace base { | 56 namespace base { |
54 namespace internal { | 57 namespace internal { |
(...skipping 11 matching lines...) Expand all Loading... |
66 if (i == n) { | 69 if (i == n) { |
67 SpinLockDelay(w, v, loop); // no matching transition | 70 SpinLockDelay(w, v, loop); // no matching transition |
68 } else if (trans[i].to == v || // null transition | 71 } else if (trans[i].to == v || // null transition |
69 base::subtle::Acquire_CompareAndSwap(w, v, trans[i].to) == v) { | 72 base::subtle::Acquire_CompareAndSwap(w, v, trans[i].to) == v) { |
70 done = trans[i].done; | 73 done = trans[i].done; |
71 } | 74 } |
72 } | 75 } |
73 return v; | 76 return v; |
74 } | 77 } |
75 | 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 |
76 } // namespace internal | 101 } // namespace internal |
77 } // namespace base | 102 } // namespace base |
OLD | NEW |