It should be easy to decide how WebKit yields
[WebKit-https.git] / Source / WTF / wtf / LockAlgorithm.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 WTF_LockAlgorithm_h
27 #define WTF_LockAlgorithm_h
28
29 #include <wtf/Atomics.h>
30 #include <wtf/Compiler.h>
31 #include <wtf/Threading.h>
32
33 namespace WTF {
34
35 // This is the algorithm used by WTF::Lock. You can use it to project one lock onto any atomic
36 // field. The limit of one lock is due to the use of the field's address as a key to find the lock's
37 // queue.
38
39 template<typename LockType, LockType isHeldBit, LockType hasParkedBit>
40 class LockAlgorithm {
41     static const bool verbose = false;
42     static const LockType mask = isHeldBit | hasParkedBit;
43
44 public:
45     static bool lockFastAssumingZero(Atomic<LockType>& lock)
46     {
47         return lock.compareExchangeWeak(0, isHeldBit, std::memory_order_acquire);
48     }
49     
50     static bool lockFast(Atomic<LockType>& lock)
51     {
52         return lock.transaction(
53             [&] (LockType& value) -> bool {
54                 if (value & isHeldBit)
55                     return false;
56                 value |= isHeldBit;
57                 return true;
58             },
59             std::memory_order_acquire);
60     }
61     
62     static void lock(Atomic<LockType>& lock)
63     {
64         if (UNLIKELY(!lockFast(lock)))
65             lockSlow(lock);
66     }
67     
68     static bool tryLock(Atomic<LockType>& lock)
69     {
70         for (;;) {
71             uint8_t currentByteValue = lock.load(std::memory_order_relaxed);
72             if (currentByteValue & isHeldBit)
73                 return false;
74             if (lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit, std::memory_order_acquire))
75                 return true;
76         }
77     }
78
79     static bool unlockFastAssumingZero(Atomic<LockType>& lock)
80     {
81         return lock.compareExchangeWeak(isHeldBit, 0, std::memory_order_release);
82     }
83     
84     static bool unlockFast(Atomic<LockType>& lock)
85     {
86         return lock.transaction(
87             [&] (LockType& value) -> bool {
88                 if ((value & mask) != isHeldBit)
89                     return false;
90                 value &= ~isHeldBit;
91                 return true;
92             },
93             std::memory_order_relaxed);
94     }
95     
96     static void unlock(Atomic<LockType>& lock)
97     {
98         if (UNLIKELY(!unlockFast(lock)))
99             unlockSlow(lock, Unfair);
100     }
101     
102     static void unlockFairly(Atomic<LockType>& lock)
103     {
104         if (UNLIKELY(!unlockFast(lock)))
105             unlockSlow(lock, Fair);
106     }
107     
108     static bool safepointFast(const Atomic<LockType>& lock)
109     {
110         WTF::compilerFence();
111         return !(lock.load(std::memory_order_relaxed) & hasParkedBit);
112     }
113     
114     static void safepoint(Atomic<LockType>& lock)
115     {
116         if (UNLIKELY(!safepointFast(lock)))
117             safepointSlow(lock);
118     }
119     
120     static bool isLocked(const Atomic<LockType>& lock)
121     {
122         return lock.load(std::memory_order_acquire) & isHeldBit;
123     }
124     
125     NEVER_INLINE static void lockSlow(Atomic<LockType>& lock);
126     
127     enum Fairness {
128         Unfair,
129         Fair
130     };
131     NEVER_INLINE static void unlockSlow(Atomic<LockType>& lock, Fairness fairness = Unfair);
132     
133     NEVER_INLINE static void safepointSlow(Atomic<LockType>& lockWord)
134     {
135         unlockFairly(lockWord);
136         lock(lockWord);
137     }
138     
139 private:
140     enum Token {
141         BargingOpportunity,
142         DirectHandoff
143     };
144 };
145
146 } // namespace WTF
147
148 using WTF::LockAlgorithm;
149
150 #endif // WTF_LockAlgorithm_h
151