Fixed a very unlikely race condition in WTF::WordLock
[WebKit-https.git] / Source / WTF / benchmarks / ToyLocks.h
1 /*
2  * Copyright (C) 2015-2017 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 <mutex>
30 #include <thread>
31 #include <wtf/Atomics.h>
32 #include <wtf/Lock.h>
33 #include <wtf/ParkingLot.h>
34 #include <wtf/Threading.h>
35 #include <wtf/WordLock.h>
36
37 #if __has_include(<os/lock.h>)
38 #include <os/lock.h>
39 #define HAS_UNFAIR_LOCK
40 #endif
41
42 #if defined(EXTRA_LOCKS) && EXTRA_LOCKS
43 #include <synchronic>
44 #endif
45
46 namespace {
47
48 unsigned toyLockSpinLimit = 40;
49
50 // This is the old WTF::SpinLock class, included here so that we can still compare our new locks to a
51 // spinlock baseline.
52 class YieldSpinLock {
53 public:
54     YieldSpinLock()
55     {
56         m_lock.store(0, std::memory_order_relaxed);
57     }
58
59     void lock()
60     {
61         while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
62             Thread::yield();
63     }
64
65     void unlock()
66     {
67         m_lock.store(0, std::memory_order_release);
68     }
69
70     bool isLocked() const
71     {
72         return m_lock.load(std::memory_order_acquire);
73     }
74
75 private:
76     Atomic<unsigned> m_lock;
77 };
78
79 class PauseSpinLock {
80 public:
81     PauseSpinLock()
82     {
83         m_lock.store(0, std::memory_order_relaxed);
84     }
85
86     void lock()
87     {
88         while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
89             asm volatile ("pause");
90     }
91
92     void unlock()
93     {
94         m_lock.store(0, std::memory_order_release);
95     }
96
97     bool isLocked() const
98     {
99         return m_lock.load(std::memory_order_acquire);
100     }
101
102 private:
103     Atomic<unsigned> m_lock;
104 };
105
106 #if defined(EXTRA_LOCKS) && EXTRA_LOCKS
107 class TransactionalSpinLock {
108 public:
109     TransactionalSpinLock()
110     {
111         m_lock = 0;
112     }
113
114     void lock()
115     {
116         for (;;) {
117             unsigned char result;
118             unsigned expected = 0;
119             unsigned desired = 1;
120             asm volatile (
121                 "xacquire; lock; cmpxchgl %3, %2\n\t"
122                 "sete %1"
123                 : "+a"(expected), "=q"(result), "+m"(m_lock)
124                 : "r"(desired)
125                 : "memory");
126             if (result)
127                 return;
128             Thread::yield();
129         }
130     }
131
132     void unlock()
133     {
134         asm volatile (
135             "xrelease; movl $0, %0"
136             :
137             : "m"(m_lock)
138             : "memory");
139     }
140
141     bool isLocked() const
142     {
143         return m_lock;
144     }
145
146 private:
147     unsigned m_lock;
148 };
149
150 class SynchronicLock {
151 public:
152     SynchronicLock()
153         : m_locked(0)
154     {
155     }
156     
157     void lock()
158     {
159         for (;;) {
160             int state = 0;
161             if (m_locked.compare_exchange_weak(state, 1, std::memory_order_acquire))
162                 return;
163             m_sync.wait_for_change(m_locked, state, std::memory_order_relaxed);
164         }
165     }
166     
167     void unlock()
168     {
169         m_sync.notify_one(m_locked, 0, std::memory_order_release);
170     }
171     
172     bool isLocked()
173     {
174         return m_locked.load();
175     }
176
177 private:
178     std::atomic<int> m_locked;
179     std::experimental::synchronic<int> m_sync;
180 };
181 #endif
182
183 template<typename StateType>
184 class BargingLock {
185 public:
186     BargingLock()
187     {
188         m_state.store(0);
189     }
190     
191     void lock()
192     {
193         if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
194             return;
195         
196         lockSlow();
197     }
198     
199     void unlock()
200     {
201         if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
202             return;
203         
204         unlockSlow();
205     }
206     
207     bool isLocked() const
208     {
209         return m_state.load(std::memory_order_acquire) & isLockedBit;
210     }
211     
212 private:
213     NEVER_INLINE void lockSlow()
214     {
215         for (unsigned i = toyLockSpinLimit; i--;) {
216             StateType currentState = m_state.load();
217             
218             if (!(currentState & isLockedBit)
219                 && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
220                 return;
221             
222             if (currentState & hasParkedBit)
223                 break;
224             
225             Thread::yield();
226         }
227         
228         for (;;) {
229             StateType currentState = m_state.load();
230             
231             if (!(currentState & isLockedBit)
232                 && m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
233                 return;
234             
235             m_state.compareExchangeWeak(isLockedBit, isLockedBit | hasParkedBit);
236             
237             ParkingLot::compareAndPark(&m_state, isLockedBit | hasParkedBit);
238         }
239     }
240     
241     NEVER_INLINE void unlockSlow()
242     {
243         ParkingLot::unparkOne(
244             &m_state,
245             [this] (ParkingLot::UnparkResult result) -> intptr_t {
246                 if (result.mayHaveMoreThreads)
247                     m_state.store(hasParkedBit);
248                 else
249                     m_state.store(0);
250                 return 0;
251             });
252     }
253     
254     static const StateType isLockedBit = 1;
255     static const StateType hasParkedBit = 2;
256     
257     Atomic<StateType> m_state;
258 };
259
260 template<typename StateType>
261 class ThunderLock {
262 public:
263     ThunderLock()
264     {
265         m_state.store(Unlocked);
266     }
267     
268     void lock()
269     {
270         if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
271             return;
272         
273         lockSlow();
274     }
275     
276     void unlock()
277     {
278         if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
279             return;
280         
281         unlockSlow();
282     }
283     
284     bool isLocked() const
285     {
286         return m_state.load(std::memory_order_acquire) != Unlocked;
287     }
288     
289 private:
290     NEVER_INLINE void lockSlow()
291     {
292         for (unsigned i = toyLockSpinLimit; i--;) {
293             State currentState = m_state.load();
294             
295             if (currentState == Unlocked
296                 && m_state.compareExchangeWeak(Unlocked, Locked))
297                 return;
298             
299             if (currentState == LockedAndParked)
300                 break;
301             
302             Thread::yield();
303         }
304         
305         for (;;) {
306             if (m_state.compareExchangeWeak(Unlocked, Locked))
307                 return;
308             
309             m_state.compareExchangeWeak(Locked, LockedAndParked);
310             ParkingLot::compareAndPark(&m_state, LockedAndParked);
311         }
312     }
313     
314     NEVER_INLINE void unlockSlow()
315     {
316         if (m_state.exchange(Unlocked) == LockedAndParked)
317             ParkingLot::unparkAll(&m_state);
318     }
319     
320     enum State : StateType {
321         Unlocked,
322         Locked,
323         LockedAndParked
324     };
325     
326     Atomic<State> m_state;
327 };
328
329 template<typename StateType>
330 class CascadeLock {
331 public:
332     CascadeLock()
333     {
334         m_state.store(Unlocked);
335     }
336     
337     void lock()
338     {
339         if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
340             return;
341         
342         lockSlow();
343     }
344     
345     void unlock()
346     {
347         if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
348             return;
349         
350         unlockSlow();
351     }
352     
353     bool isLocked() const
354     {
355         return m_state.load(std::memory_order_acquire) != Unlocked;
356     }
357     
358 private:
359     NEVER_INLINE void lockSlow()
360     {
361         for (unsigned i = toyLockSpinLimit; i--;) {
362             State currentState = m_state.load();
363             
364             if (currentState == Unlocked
365                 && m_state.compareExchangeWeak(Unlocked, Locked))
366                 return;
367             
368             if (currentState == LockedAndParked)
369                 break;
370             
371             Thread::yield();
372         }
373         
374         State desiredState = Locked;
375         for (;;) {
376             if (m_state.compareExchangeWeak(Unlocked, desiredState))
377                 return;
378             
379             desiredState = LockedAndParked;
380             m_state.compareExchangeWeak(Locked, LockedAndParked);
381             ParkingLot::compareAndPark(&m_state, LockedAndParked);
382         }
383     }
384     
385     NEVER_INLINE void unlockSlow()
386     {
387         if (m_state.exchange(Unlocked) == LockedAndParked)
388             ParkingLot::unparkOne(&m_state);
389     }
390     
391     enum State : StateType {
392         Unlocked,
393         Locked,
394         LockedAndParked
395     };
396     
397     Atomic<State> m_state;
398 };
399
400 class HandoffLock {
401 public:
402     HandoffLock()
403     {
404         m_state.store(0);
405     }
406     
407     void lock()
408     {
409         if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
410             return;
411
412         lockSlow();
413     }
414
415     void unlock()
416     {
417         if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
418             return;
419
420         unlockSlow();
421     }
422
423     bool isLocked() const
424     {
425         return m_state.load(std::memory_order_acquire) & isLockedBit;
426     }
427     
428 private:
429     NEVER_INLINE void lockSlow()
430     {
431         for (;;) {
432             unsigned state = m_state.load();
433             
434             if (!(state & isLockedBit)) {
435                 if (m_state.compareExchangeWeak(state, state | isLockedBit))
436                     return;
437                 continue;
438             }
439             
440             if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
441                 bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit).wasUnparked;
442                 m_state.exchangeAdd(-parkedCountUnit);
443                 if (result)
444                     return;
445             }
446         }
447     }
448     
449     NEVER_INLINE void unlockSlow()
450     {
451         for (;;) {
452             unsigned state = m_state.load();
453             
454             if (!(state >> parkedCountShift)) {
455                 RELEASE_ASSERT(state == isLockedBit);
456                 if (m_state.compareExchangeWeak(isLockedBit, 0))
457                     return;
458                 continue;
459             }
460             
461             if (ParkingLot::unparkOne(&m_state).didUnparkThread) {
462                 // We unparked someone. There are now running and they hold the lock.
463                 return;
464             }
465             
466             // Nobody unparked. Maybe there isn't anyone waiting. Just try again.
467         }
468     }
469     
470     static const unsigned isLockedBit = 1;
471     static const unsigned parkedCountShift = 1;
472     static const unsigned parkedCountUnit = 1 << parkedCountShift;
473     
474     Atomic<unsigned> m_state;
475 };
476
477 #ifdef HAS_UNFAIR_LOCK
478 class UnfairLock {
479     os_unfair_lock l = OS_UNFAIR_LOCK_INIT;
480 public:
481     void lock()
482     {
483         os_unfair_lock_lock(&l);
484     }
485     void unlock()
486     {
487         os_unfair_lock_unlock(&l);
488     }
489 };
490 #endif
491
492 template<typename Benchmark>
493 void runEverything(const char* what)
494 {
495     if (!strcmp(what, "yieldspinlock") || !strcmp(what, "all"))
496         Benchmark::template run<YieldSpinLock>("YieldSpinLock");
497     if (!strcmp(what, "pausespinlock") || !strcmp(what, "all"))
498         Benchmark::template run<PauseSpinLock>("PauseSpinLock");
499 #if defined(EXTRA_LOCKS) && EXTRA_LOCKS
500     if (!strcmp(what, "transactionalspinlock") || !strcmp(what, "all"))
501         Benchmark::template run<TransactionalSpinLock>("TransactionalSpinLock");
502     if (!strcmp(what, "synchroniclock") || !strcmp(what, "all"))
503         Benchmark::template run<SynchronicLock>("SynchronicLock");
504 #endif
505     if (!strcmp(what, "wordlock") || !strcmp(what, "all"))
506         Benchmark::template run<WordLock>("WTFWordLock");
507     if (!strcmp(what, "lock") || !strcmp(what, "all"))
508         Benchmark::template run<Lock>("WTFLock");
509     if (!strcmp(what, "barginglock") || !strcmp(what, "all"))
510         Benchmark::template run<BargingLock<uint8_t>>("ByteBargingLock");
511     if (!strcmp(what, "bargingwordlock") || !strcmp(what, "all"))
512         Benchmark::template run<BargingLock<uint32_t>>("WordBargingLock");
513     if (!strcmp(what, "thunderlock") || !strcmp(what, "all"))
514         Benchmark::template run<ThunderLock<uint8_t>>("ByteThunderLock");
515     if (!strcmp(what, "thunderwordlock") || !strcmp(what, "all"))
516         Benchmark::template run<ThunderLock<uint32_t>>("WordThunderLock");
517     if (!strcmp(what, "cascadelock") || !strcmp(what, "all"))
518         Benchmark::template run<CascadeLock<uint8_t>>("ByteCascadeLock");
519     if (!strcmp(what, "cascadewordlock") || !strcmp(what, "all"))
520         Benchmark::template run<CascadeLock<uint32_t>>("WordCascadeLock");
521     if (!strcmp(what, "handofflock") || !strcmp(what, "all"))
522         Benchmark::template run<HandoffLock>("HandoffLock");
523 #ifdef HAS_UNFAIR_LOCK
524     if (!strcmp(what, "unfairlock") || !strcmp(what, "all"))
525         Benchmark::template run<UnfairLock>("UnfairLock");
526 #endif
527     if (!strcmp(what, "mutex") || !strcmp(what, "all"))
528         Benchmark::template run<std::mutex>("std::mutex");
529 }
530
531 } // anonymous namespace
532
533 #endif // ToyLocks_h
534