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