1// Copyright (c) 2005, 2006, Google Inc. 2// Copyright (c) 2010, Patrick Gansterer <paroga@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@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 58static void TCMalloc_SlowLock(volatile unsigned int* lockword); 59 60// The following is a struct so that it can be initialized at compile time 61struct 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 137static 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 205static void TCMalloc_SlowLock(LPLONG lockword); 206 207// The following is a struct so that it can be initialized at compile time 208struct 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 230static 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 241struct 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. 271class 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 281typedef TCMalloc_SpinLock SpinLock; 282typedef TCMalloc_SpinLockHolder SpinLockHolder; 283 284#endif // TCMALLOC_INTERNAL_SPINLOCK_H__ 285