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 | |
48 #if defined(_WIN32) | 45 #if defined(_WIN32) |
49 #include "base/spinlock_win32-inl.h" | 46 #include "base/spinlock_win32-inl.h" |
50 #elif defined(__linux__) | 47 #elif defined(__linux__) |
51 #include "base/spinlock_linux-inl.h" | 48 #include "base/spinlock_linux-inl.h" |
52 #else | 49 #else |
53 #include "base/spinlock_posix-inl.h" | 50 #include "base/spinlock_posix-inl.h" |
54 #endif | 51 #endif |
55 | 52 |
56 namespace base { | 53 namespace base { |
57 namespace internal { | 54 namespace internal { |
(...skipping 11 matching lines...) Expand all Loading... |
69 if (i == n) { | 66 if (i == n) { |
70 SpinLockDelay(w, v, loop); // no matching transition | 67 SpinLockDelay(w, v, loop); // no matching transition |
71 } else if (trans[i].to == v || // null transition | 68 } else if (trans[i].to == v || // null transition |
72 base::subtle::Acquire_CompareAndSwap(w, v, trans[i].to) == v) { | 69 base::subtle::Acquire_CompareAndSwap(w, v, trans[i].to) == v) { |
73 done = trans[i].done; | 70 done = trans[i].done; |
74 } | 71 } |
75 } | 72 } |
76 return v; | 73 return v; |
77 } | 74 } |
78 | 75 |
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 | 76 } // namespace internal |
102 } // namespace base | 77 } // namespace base |
OLD | NEW |