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