Add a few more WTF locking benchmarks
[WebKit-https.git] / Source / WTF / benchmarks / ToyLocks.h
1 /*
2  * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #ifndef ToyLocks_h
27 #define ToyLocks_h
28
29 #include <thread>
30 #include <wtf/Atomics.h>
31 #include <wtf/Lock.h>
32 #include <wtf/ParkingLot.h>
33 #include <wtf/WordLock.h>
34
35 namespace {
36
37 unsigned toyLockSpinLimit = 40;
38
39 // This is the old WTF::SpinLock class, included here so that we can still compare our new locks to a
40 // spinlock baseline.
41 class YieldSpinLock {
42 public:
43     YieldSpinLock()
44     {
45         m_lock.store(0, std::memory_order_relaxed);
46     }
47
48     void lock()
49     {
50         while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
51             std::this_thread::yield();
52     }
53
54     void unlock()
55     {
56         m_lock.store(0, std::memory_order_release);
57     }
58
59     bool isLocked() const
60     {
61         return m_lock.load(std::memory_order_acquire);
62     }
63
64 private:
65     Atomic<unsigned> m_lock;
66 };
67
68 class PauseSpinLock {
69 public:
70     PauseSpinLock()
71     {
72         m_lock.store(0, std::memory_order_relaxed);
73     }
74
75     void lock()
76     {
77         while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
78             asm volatile ("pause");
79     }
80
81     void unlock()
82     {
83         m_lock.store(0, std::memory_order_release);
84     }
85
86     bool isLocked() const
87     {
88         return m_lock.load(std::memory_order_acquire);
89     }
90
91 private:
92     Atomic<unsigned> m_lock;
93 };
94
95 template<typename StateType>
96 class BargingLock {
97 public:
98     BargingLock()
99     {
100         m_state.store(0);
101     }
102     
103     void lock()
104     {
105         if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
106             return;
107         
108         lockSlow();
109     }
110     
111     void unlock()
112     {
113         if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
114             return;
115         
116         unlockSlow();
117     }
118     
119     bool isLocked() const
120     {
121         return m_state.load(std::memory_order_acquire) & isLockedBit;
122     }
123     
124 private:
125     NEVER_INLINE void lockSlow()
126     {
127         for (unsigned i = toyLockSpinLimit; i--;) {
128             StateType currentState = m_state.load();
129             
130             if (!(currentState & isLockedBit)
131                 && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
132                 return;
133             
134             if (currentState & hasParkedBit)
135                 break;
136             
137             std::this_thread::yield();
138         }
139         
140         for (;;) {
141             StateType currentState = m_state.load();
142             
143             if (!(currentState & isLockedBit)
144                 && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
145                 return;
146             
147             m_state.compareExchangeWeak(isLockedBit, isLockedBit | hasParkedBit);
148             
149             ParkingLot::compareAndPark(&m_state, isLockedBit | hasParkedBit);
150         }
151     }
152     
153     NEVER_INLINE void unlockSlow()
154     {
155         ParkingLot::unparkOne(
156             &m_state,
157             [this] (ParkingLot::UnparkResult result) {
158                 if (result.mayHaveMoreThreads)
159                     m_state.store(hasParkedBit);
160                 else
161                     m_state.store(0);
162             });
163     }
164     
165     static const StateType isLockedBit = 1;
166     static const StateType hasParkedBit = 2;
167     
168     Atomic<StateType> m_state;
169 };
170
171 template<typename StateType>
172 class ThunderLock {
173 public:
174     ThunderLock()
175     {
176         m_state.store(Unlocked);
177     }
178     
179     void lock()
180     {
181         if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
182             return;
183         
184         lockSlow();
185     }
186     
187     void unlock()
188     {
189         if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
190             return;
191         
192         unlockSlow();
193     }
194     
195     bool isLocked() const
196     {
197         return m_state.load(std::memory_order_acquire) != Unlocked;
198     }
199     
200 private:
201     NEVER_INLINE void lockSlow()
202     {
203         for (unsigned i = toyLockSpinLimit; i--;) {
204             State currentState = m_state.load();
205             
206             if (currentState == Unlocked
207                 && m_state.compareExchangeWeak(Unlocked, Locked))
208                 return;
209             
210             if (currentState == LockedAndParked)
211                 break;
212             
213             std::this_thread::yield();
214         }
215         
216         for (;;) {
217             if (m_state.compareExchangeWeak(Unlocked, Locked))
218                 return;
219             
220             m_state.compareExchangeWeak(Locked, LockedAndParked);
221             ParkingLot::compareAndPark(&m_state, LockedAndParked);
222         }
223     }
224     
225     NEVER_INLINE void unlockSlow()
226     {
227         if (m_state.exchange(Unlocked) == LockedAndParked)
228             ParkingLot::unparkAll(&m_state);
229     }
230     
231     enum State : StateType {
232         Unlocked,
233         Locked,
234         LockedAndParked
235     };
236     
237     Atomic<State> m_state;
238 };
239
240 template<typename StateType>
241 class CascadeLock {
242 public:
243     CascadeLock()
244     {
245         m_state.store(Unlocked);
246     }
247     
248     void lock()
249     {
250         if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
251             return;
252         
253         lockSlow();
254     }
255     
256     void unlock()
257     {
258         if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
259             return;
260         
261         unlockSlow();
262     }
263     
264     bool isLocked() const
265     {
266         return m_state.load(std::memory_order_acquire) != Unlocked;
267     }
268     
269 private:
270     NEVER_INLINE void lockSlow()
271     {
272         for (unsigned i = toyLockSpinLimit; i--;) {
273             State currentState = m_state.load();
274             
275             if (currentState == Unlocked
276                 && m_state.compareExchangeWeak(Unlocked, Locked))
277                 return;
278             
279             if (currentState == LockedAndParked)
280                 break;
281             
282             std::this_thread::yield();
283         }
284         
285         State desiredState = Locked;
286         for (;;) {
287             if (m_state.compareExchangeWeak(Unlocked, desiredState))
288                 return;
289             
290             desiredState = LockedAndParked;
291             m_state.compareExchangeWeak(Locked, LockedAndParked);
292             ParkingLot::compareAndPark(&m_state, LockedAndParked);
293         }
294     }
295     
296     NEVER_INLINE void unlockSlow()
297     {
298         if (m_state.exchange(Unlocked) == LockedAndParked)
299             ParkingLot::unparkOne(&m_state);
300     }
301     
302     enum State : StateType {
303         Unlocked,
304         Locked,
305         LockedAndParked
306     };
307     
308     Atomic<State> m_state;
309 };
310
311 class HandoffLock {
312 public:
313     HandoffLock()
314     {
315         m_state.store(0);
316     }
317     
318     void lock()
319     {
320         if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
321             return;
322
323         lockSlow();
324     }
325
326     void unlock()
327     {
328         if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
329             return;
330
331         unlockSlow();
332     }
333
334     bool isLocked() const
335     {
336         return m_state.load(std::memory_order_acquire) & isLockedBit;
337     }
338     
339 private:
340     NEVER_INLINE void lockSlow()
341     {
342         for (;;) {
343             unsigned state = m_state.load();
344             
345             if (!(state & isLockedBit)) {
346                 if (m_state.compareExchangeWeak(state, state | isLockedBit))
347                     return;
348                 continue;
349             }
350             
351             if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
352                 bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit);
353                 m_state.exchangeAndAdd(-parkedCountUnit);
354                 if (result)
355                     return;
356             }
357         }
358     }
359     
360     NEVER_INLINE void unlockSlow()
361     {
362         for (;;) {
363             unsigned state = m_state.load();
364             
365             if (!(state >> parkedCountShift)) {
366                 RELEASE_ASSERT(state == isLockedBit);
367                 if (m_state.compareExchangeWeak(isLockedBit, 0))
368                     return;
369                 continue;
370             }
371             
372             if (ParkingLot::unparkOne(&m_state).didUnparkThread) {
373                 // We unparked someone. There are now running and they hold the lock.
374                 return;
375             }
376             
377             // Nobody unparked. Maybe there isn't anyone waiting. Just try again.
378         }
379     }
380     
381     static const unsigned isLockedBit = 1;
382     static const unsigned parkedCountShift = 1;
383     static const unsigned parkedCountUnit = 1 << parkedCountShift;
384     
385     Atomic<unsigned> m_state;
386 };
387
388 template<typename Benchmark>
389 void runEverything(const char* what)
390 {
391     if (!strcmp(what, "yieldspinlock") || !strcmp(what, "all"))
392         Benchmark::template run<YieldSpinLock>("YieldSpinLock");
393     if (!strcmp(what, "pausespinlock") || !strcmp(what, "all"))
394         Benchmark::template run<PauseSpinLock>("PauseSpinLock");
395     if (!strcmp(what, "wordlock") || !strcmp(what, "all"))
396         Benchmark::template run<WordLock>("WTFWordLock");
397     if (!strcmp(what, "lock") || !strcmp(what, "all"))
398         Benchmark::template run<Lock>("WTFLock");
399     if (!strcmp(what, "barginglock") || !strcmp(what, "all"))
400         Benchmark::template run<BargingLock<uint8_t>>("ByteBargingLock");
401     if (!strcmp(what, "bargingwordlock") || !strcmp(what, "all"))
402         Benchmark::template run<BargingLock<uint32_t>>("WordBargingLock");
403     if (!strcmp(what, "thunderlock") || !strcmp(what, "all"))
404         Benchmark::template run<ThunderLock<uint8_t>>("ByteThunderLock");
405     if (!strcmp(what, "thunderwordlock") || !strcmp(what, "all"))
406         Benchmark::template run<ThunderLock<uint32_t>>("WordThunderLock");
407     if (!strcmp(what, "cascadelock") || !strcmp(what, "all"))
408         Benchmark::template run<CascadeLock<uint8_t>>("ByteCascadeLock");
409     if (!strcmp(what, "cascadewordlock") || !strcmp(what, "all"))
410         Benchmark::template run<CascadeLock<uint32_t>>("WordCascadeLock");
411     if (!strcmp(what, "handofflock") || !strcmp(what, "all"))
412         Benchmark::template run<HandoffLock>("HandoffLock");
413     if (!strcmp(what, "mutex") || !strcmp(what, "all"))
414         Benchmark::template run<Mutex>("PlatformMutex");
415 }
416
417 } // anonymous namespace
418
419 #endif // ToyLocks_h
420