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