Add HLE locks and synchronic TTAS locks to the ToyLocks benchmark suite
[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             std::this_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             std::this_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             std::this_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) {
239                 if (result.mayHaveMoreThreads)
240                     m_state.store(hasParkedBit);
241                 else
242                     m_state.store(0);
243             });
244     }
245     
246     static const StateType isLockedBit = 1;
247     static const StateType hasParkedBit = 2;
248     
249     Atomic<StateType> m_state;
250 };
251
252 template<typename StateType>
253 class ThunderLock {
254 public:
255     ThunderLock()
256     {
257         m_state.store(Unlocked);
258     }
259     
260     void lock()
261     {
262         if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
263             return;
264         
265         lockSlow();
266     }
267     
268     void unlock()
269     {
270         if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
271             return;
272         
273         unlockSlow();
274     }
275     
276     bool isLocked() const
277     {
278         return m_state.load(std::memory_order_acquire) != Unlocked;
279     }
280     
281 private:
282     NEVER_INLINE void lockSlow()
283     {
284         for (unsigned i = toyLockSpinLimit; i--;) {
285             State currentState = m_state.load();
286             
287             if (currentState == Unlocked
288                 && m_state.compareExchangeWeak(Unlocked, Locked))
289                 return;
290             
291             if (currentState == LockedAndParked)
292                 break;
293             
294             std::this_thread::yield();
295         }
296         
297         for (;;) {
298             if (m_state.compareExchangeWeak(Unlocked, Locked))
299                 return;
300             
301             m_state.compareExchangeWeak(Locked, LockedAndParked);
302             ParkingLot::compareAndPark(&m_state, LockedAndParked);
303         }
304     }
305     
306     NEVER_INLINE void unlockSlow()
307     {
308         if (m_state.exchange(Unlocked) == LockedAndParked)
309             ParkingLot::unparkAll(&m_state);
310     }
311     
312     enum State : StateType {
313         Unlocked,
314         Locked,
315         LockedAndParked
316     };
317     
318     Atomic<State> m_state;
319 };
320
321 template<typename StateType>
322 class CascadeLock {
323 public:
324     CascadeLock()
325     {
326         m_state.store(Unlocked);
327     }
328     
329     void lock()
330     {
331         if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
332             return;
333         
334         lockSlow();
335     }
336     
337     void unlock()
338     {
339         if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
340             return;
341         
342         unlockSlow();
343     }
344     
345     bool isLocked() const
346     {
347         return m_state.load(std::memory_order_acquire) != Unlocked;
348     }
349     
350 private:
351     NEVER_INLINE void lockSlow()
352     {
353         for (unsigned i = toyLockSpinLimit; i--;) {
354             State currentState = m_state.load();
355             
356             if (currentState == Unlocked
357                 && m_state.compareExchangeWeak(Unlocked, Locked))
358                 return;
359             
360             if (currentState == LockedAndParked)
361                 break;
362             
363             std::this_thread::yield();
364         }
365         
366         State desiredState = Locked;
367         for (;;) {
368             if (m_state.compareExchangeWeak(Unlocked, desiredState))
369                 return;
370             
371             desiredState = LockedAndParked;
372             m_state.compareExchangeWeak(Locked, LockedAndParked);
373             ParkingLot::compareAndPark(&m_state, LockedAndParked);
374         }
375     }
376     
377     NEVER_INLINE void unlockSlow()
378     {
379         if (m_state.exchange(Unlocked) == LockedAndParked)
380             ParkingLot::unparkOne(&m_state);
381     }
382     
383     enum State : StateType {
384         Unlocked,
385         Locked,
386         LockedAndParked
387     };
388     
389     Atomic<State> m_state;
390 };
391
392 class HandoffLock {
393 public:
394     HandoffLock()
395     {
396         m_state.store(0);
397     }
398     
399     void lock()
400     {
401         if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
402             return;
403
404         lockSlow();
405     }
406
407     void unlock()
408     {
409         if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
410             return;
411
412         unlockSlow();
413     }
414
415     bool isLocked() const
416     {
417         return m_state.load(std::memory_order_acquire) & isLockedBit;
418     }
419     
420 private:
421     NEVER_INLINE void lockSlow()
422     {
423         for (;;) {
424             unsigned state = m_state.load();
425             
426             if (!(state & isLockedBit)) {
427                 if (m_state.compareExchangeWeak(state, state | isLockedBit))
428                     return;
429                 continue;
430             }
431             
432             if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
433                 bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit);
434                 m_state.exchangeAndAdd(-parkedCountUnit);
435                 if (result)
436                     return;
437             }
438         }
439     }
440     
441     NEVER_INLINE void unlockSlow()
442     {
443         for (;;) {
444             unsigned state = m_state.load();
445             
446             if (!(state >> parkedCountShift)) {
447                 RELEASE_ASSERT(state == isLockedBit);
448                 if (m_state.compareExchangeWeak(isLockedBit, 0))
449                     return;
450                 continue;
451             }
452             
453             if (ParkingLot::unparkOne(&m_state).didUnparkThread) {
454                 // We unparked someone. There are now running and they hold the lock.
455                 return;
456             }
457             
458             // Nobody unparked. Maybe there isn't anyone waiting. Just try again.
459         }
460     }
461     
462     static const unsigned isLockedBit = 1;
463     static const unsigned parkedCountShift = 1;
464     static const unsigned parkedCountUnit = 1 << parkedCountShift;
465     
466     Atomic<unsigned> m_state;
467 };
468
469 template<typename Benchmark>
470 void runEverything(const char* what)
471 {
472     if (!strcmp(what, "yieldspinlock") || !strcmp(what, "all"))
473         Benchmark::template run<YieldSpinLock>("YieldSpinLock");
474     if (!strcmp(what, "pausespinlock") || !strcmp(what, "all"))
475         Benchmark::template run<PauseSpinLock>("PauseSpinLock");
476 #if defined(EXTRA_LOCKS) && EXTRA_LOCKS
477     if (!strcmp(what, "transactionalspinlock") || !strcmp(what, "all"))
478         Benchmark::template run<TransactionalSpinLock>("TransactionalSpinLock");
479     if (!strcmp(what, "synchroniclock") || !strcmp(what, "all"))
480         Benchmark::template run<SynchronicLock>("SynchronicLock");
481 #endif
482     if (!strcmp(what, "wordlock") || !strcmp(what, "all"))
483         Benchmark::template run<WordLock>("WTFWordLock");
484     if (!strcmp(what, "lock") || !strcmp(what, "all"))
485         Benchmark::template run<Lock>("WTFLock");
486     if (!strcmp(what, "barginglock") || !strcmp(what, "all"))
487         Benchmark::template run<BargingLock<uint8_t>>("ByteBargingLock");
488     if (!strcmp(what, "bargingwordlock") || !strcmp(what, "all"))
489         Benchmark::template run<BargingLock<uint32_t>>("WordBargingLock");
490     if (!strcmp(what, "thunderlock") || !strcmp(what, "all"))
491         Benchmark::template run<ThunderLock<uint8_t>>("ByteThunderLock");
492     if (!strcmp(what, "thunderwordlock") || !strcmp(what, "all"))
493         Benchmark::template run<ThunderLock<uint32_t>>("WordThunderLock");
494     if (!strcmp(what, "cascadelock") || !strcmp(what, "all"))
495         Benchmark::template run<CascadeLock<uint8_t>>("ByteCascadeLock");
496     if (!strcmp(what, "cascadewordlock") || !strcmp(what, "all"))
497         Benchmark::template run<CascadeLock<uint32_t>>("WordCascadeLock");
498     if (!strcmp(what, "handofflock") || !strcmp(what, "all"))
499         Benchmark::template run<HandoffLock>("HandoffLock");
500     if (!strcmp(what, "mutex") || !strcmp(what, "all"))
501         Benchmark::template run<Mutex>("PlatformMutex");
502 }
503
504 } // anonymous namespace
505
506 #endif // ToyLocks_h
507