1 // Copyright (c) 2005, 2006, Google Inc. 2 // Copyright (c) 2010, Patrick Gansterer <paroga (at) paroga.com> 3 // All rights reserved. 4 // 5 // Redistribution and use in source and binary forms, with or without 6 // modification, are permitted provided that the following conditions are 7 // met: 8 // 9 // * Redistributions of source code must retain the above copyright 10 // notice, this list of conditions and the following disclaimer. 11 // * Redistributions in binary form must reproduce the above 12 // copyright notice, this list of conditions and the following disclaimer 13 // in the documentation and/or other materials provided with the 14 // distribution. 15 // * Neither the name of Google Inc. nor the names of its 16 // contributors may be used to endorse or promote products derived from 17 // this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 20 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 21 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 22 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 23 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 24 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 25 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 26 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 27 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 28 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 29 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 30 31 // --- 32 // Author: Sanjay Ghemawat <opensource (at) google.com> 33 34 #ifndef TCMALLOC_INTERNAL_SPINLOCK_H__ 35 #define TCMALLOC_INTERNAL_SPINLOCK_H__ 36 37 #if (CPU(X86) || CPU(X86_64) || CPU(PPC)) && (COMPILER(GCC) || COMPILER(MSVC)) 38 39 #include <time.h> /* For nanosleep() */ 40 41 #if HAVE(STDINT_H) 42 #include <stdint.h> 43 #elif HAVE(INTTYPES_H) 44 #include <inttypes.h> 45 #else 46 #include <sys/types.h> 47 #endif 48 49 #if OS(WINDOWS) 50 #ifndef WIN32_LEAN_AND_MEAN 51 #define WIN32_LEAN_AND_MEAN 52 #endif 53 #include <windows.h> 54 #else 55 #include <sched.h> /* For sched_yield() */ 56 #endif 57 58 static void TCMalloc_SlowLock(volatile unsigned int* lockword); 59 60 // The following is a struct so that it can be initialized at compile time 61 struct TCMalloc_SpinLock { 62 63 inline void Lock() { 64 int r; 65 #if COMPILER(GCC) 66 #if CPU(X86) || CPU(X86_64) 67 __asm__ __volatile__ 68 ("xchgl %0, %1" 69 : "=r"(r), "=m"(lockword_) 70 : "0"(1), "m"(lockword_) 71 : "memory"); 72 #else 73 volatile unsigned int *lockword_ptr = &lockword_; 74 __asm__ __volatile__ 75 ("1: lwarx %0, 0, %1\n\t" 76 "stwcx. %2, 0, %1\n\t" 77 "bne- 1b\n\t" 78 "isync" 79 : "=&r" (r), "=r" (lockword_ptr) 80 : "r" (1), "1" (lockword_ptr) 81 : "memory"); 82 #endif 83 #elif COMPILER(MSVC) 84 __asm { 85 mov eax, this ; store &lockword_ (which is this+0) in eax 86 mov ebx, 1 ; store 1 in ebx 87 xchg [eax], ebx ; exchange lockword_ and 1 88 mov r, ebx ; store old value of lockword_ in r 89 } 90 #endif 91 if (r) TCMalloc_SlowLock(&lockword_); 92 } 93 94 inline void Unlock() { 95 #if COMPILER(GCC) 96 #if CPU(X86) || CPU(X86_64) 97 __asm__ __volatile__ 98 ("movl $0, %0" 99 : "=m"(lockword_) 100 : "m" (lockword_) 101 : "memory"); 102 #else 103 __asm__ __volatile__ 104 ("isync\n\t" 105 "eieio\n\t" 106 "stw %1, %0" 107 #if OS(DARWIN) || CPU(PPC) 108 : "=o" (lockword_) 109 #else 110 : "=m" (lockword_) 111 #endif 112 : "r" (0) 113 : "memory"); 114 #endif 115 #elif COMPILER(MSVC) 116 __asm { 117 mov eax, this ; store &lockword_ (which is this+0) in eax 118 mov [eax], 0 ; set lockword_ to 0 119 } 120 #endif 121 } 122 // Report if we think the lock can be held by this thread. 123 // When the lock is truly held by the invoking thread 124 // we will always return true. 125 // Indended to be used as CHECK(lock.IsHeld()); 126 inline bool IsHeld() const { 127 return lockword_ != 0; 128 } 129 130 inline void Init() { lockword_ = 0; } 131 132 volatile unsigned int lockword_; 133 }; 134 135 #define SPINLOCK_INITIALIZER { 0 } 136 137 static void TCMalloc_SlowLock(volatile unsigned int* lockword) { 138 // Yield immediately since fast path failed 139 #if OS(WINDOWS) 140 Sleep(0); 141 #else 142 sched_yield(); 143 #endif 144 while (true) { 145 int r; 146 #if COMPILER(GCC) 147 #if CPU(X86) || CPU(X86_64) 148 __asm__ __volatile__ 149 ("xchgl %0, %1" 150 : "=r"(r), "=m"(*lockword) 151 : "0"(1), "m"(*lockword) 152 : "memory"); 153 154 #else 155 int tmp = 1; 156 __asm__ __volatile__ 157 ("1: lwarx %0, 0, %1\n\t" 158 "stwcx. %2, 0, %1\n\t" 159 "bne- 1b\n\t" 160 "isync" 161 : "=&r" (r), "=r" (lockword) 162 : "r" (tmp), "1" (lockword) 163 : "memory"); 164 #endif 165 #elif COMPILER(MSVC) 166 __asm { 167 mov eax, lockword ; assign lockword into eax 168 mov ebx, 1 ; assign 1 into ebx 169 xchg [eax], ebx ; exchange *lockword and 1 170 mov r, ebx ; store old value of *lockword in r 171 } 172 #endif 173 if (!r) { 174 return; 175 } 176 177 // This code was adapted from the ptmalloc2 implementation of 178 // spinlocks which would sched_yield() upto 50 times before 179 // sleeping once for a few milliseconds. Mike Burrows suggested 180 // just doing one sched_yield() outside the loop and always 181 // sleeping after that. This change helped a great deal on the 182 // performance of spinlocks under high contention. A test program 183 // with 10 threads on a dual Xeon (four virtual processors) went 184 // from taking 30 seconds to 16 seconds. 185 186 // Sleep for a few milliseconds 187 #if OS(WINDOWS) 188 Sleep(2); 189 #else 190 struct timespec tm; 191 tm.tv_sec = 0; 192 tm.tv_nsec = 2000001; 193 nanosleep(&tm, NULL); 194 #endif 195 } 196 } 197 198 #elif OS(WINDOWS) 199 200 #ifndef WIN32_LEAN_AND_MEAN 201 #define WIN32_LEAN_AND_MEAN 202 #endif 203 #include <windows.h> 204 205 static void TCMalloc_SlowLock(LPLONG lockword); 206 207 // The following is a struct so that it can be initialized at compile time 208 struct TCMalloc_SpinLock { 209 210 inline void Lock() { 211 if (InterlockedExchange(&m_lockword, 1)) 212 TCMalloc_SlowLock(&m_lockword); 213 } 214 215 inline void Unlock() { 216 InterlockedExchange(&m_lockword, 0); 217 } 218 219 inline bool IsHeld() const { 220 return m_lockword != 0; 221 } 222 223 inline void Init() { m_lockword = 0; } 224 225 LONG m_lockword; 226 }; 227 228 #define SPINLOCK_INITIALIZER { 0 } 229 230 static void TCMalloc_SlowLock(LPLONG lockword) { 231 Sleep(0); // Yield immediately since fast path failed 232 while (InterlockedExchange(lockword, 1)) 233 Sleep(2); 234 } 235 236 #else 237 238 #include <pthread.h> 239 240 // Portable version 241 struct TCMalloc_SpinLock { 242 pthread_mutex_t private_lock_; 243 244 inline void Init() { 245 if (pthread_mutex_init(&private_lock_, NULL) != 0) CRASH(); 246 } 247 inline void Finalize() { 248 if (pthread_mutex_destroy(&private_lock_) != 0) CRASH(); 249 } 250 inline void Lock() { 251 if (pthread_mutex_lock(&private_lock_) != 0) CRASH(); 252 } 253 inline void Unlock() { 254 if (pthread_mutex_unlock(&private_lock_) != 0) CRASH(); 255 } 256 bool IsHeld() { 257 if (pthread_mutex_trylock(&private_lock_)) 258 return true; 259 260 Unlock(); 261 return false; 262 } 263 }; 264 265 #define SPINLOCK_INITIALIZER { PTHREAD_MUTEX_INITIALIZER } 266 267 #endif 268 269 // Corresponding locker object that arranges to acquire a spinlock for 270 // the duration of a C++ scope. 271 class TCMalloc_SpinLockHolder { 272 private: 273 TCMalloc_SpinLock* lock_; 274 public: 275 inline explicit TCMalloc_SpinLockHolder(TCMalloc_SpinLock* l) 276 : lock_(l) { l->Lock(); } 277 inline ~TCMalloc_SpinLockHolder() { lock_->Unlock(); } 278 }; 279 280 // Short-hands for convenient use by tcmalloc.cc 281 typedef TCMalloc_SpinLock SpinLock; 282 typedef TCMalloc_SpinLockHolder SpinLockHolder; 283 284 #endif // TCMALLOC_INTERNAL_SPINLOCK_H__ 285
