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