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#pragma once
27
28#include <wtf/LockAlgorithm.h>
29#include <wtf/Locker.h>
30#include <wtf/Noncopyable.h>
31
32namespace TestWebKitAPI {
33struct LockInspector;
34}
35
36namespace WTF {
37
38typedef LockAlgorithm<uint8_t, 1, 2> DefaultLockAlgorithm;
39
40// This is a fully adaptive mutex that only requires 1 byte of storage. It has fast paths that are
41// competetive to a spinlock (uncontended locking is inlined and is just a CAS, microcontention is
42// handled by spinning and yielding), and a slow path that is competetive to std::mutex (if a lock
43// cannot be acquired in a short period of time, the thread is put to sleep until the lock is
44// available again). It uses less memory than a std::mutex. This lock guarantees eventual stochastic
45// fairness, even in programs that relock the lock immediately after unlocking it. Except when there
46// are collisions between this lock and other locks in the ParkingLot, this lock will guarantee that
47// at worst one call to unlock() per millisecond will do a direct hand-off to the thread that is at
48// the head of the queue. When there are collisions, each collision increases the fair unlock delay
49// by one millisecond in the worst case.
50class Lock {
51 WTF_MAKE_NONCOPYABLE(Lock);
52 WTF_MAKE_FAST_ALLOCATED;
53public:
54 constexpr Lock() = default;
55
56 void lock()
57 {
58 if (UNLIKELY(!DefaultLockAlgorithm::lockFastAssumingZero(m_byte)))
59 lockSlow();
60 }
61
62 bool tryLock()
63 {
64 return DefaultLockAlgorithm::tryLock(m_byte);
65 }
66
67 // Need this version for std::unique_lock.
68 bool try_lock()
69 {
70 return tryLock();
71 }
72
73 // Relinquish the lock. Either one of the threads that were waiting for the lock, or some other
74 // thread that happens to be running, will be able to grab the lock. This bit of unfairness is
75 // called barging, and we allow it because it maximizes throughput. However, we bound how unfair
76 // barging can get by ensuring that every once in a while, when there is a thread waiting on the
77 // lock, we hand the lock to that thread directly. Every time unlock() finds a thread waiting,
78 // we check if the last time that we did a fair unlock was more than roughly 1ms ago; if so, we
79 // unlock fairly. Fairness matters most for long critical sections, and this virtually
80 // guarantees that long critical sections always get a fair lock.
81 void unlock()
82 {
83 if (UNLIKELY(!DefaultLockAlgorithm::unlockFastAssumingZero(m_byte)))
84 unlockSlow();
85 }
86
87 // This is like unlock() but it guarantees that we unlock the lock fairly. For short critical
88 // sections, this is much slower than unlock(). For long critical sections, unlock() will learn
89 // to be fair anyway. However, if you plan to relock the lock right after unlocking and you want
90 // to ensure that some other thread runs in the meantime, this is probably the function you
91 // want.
92 void unlockFairly()
93 {
94 if (UNLIKELY(!DefaultLockAlgorithm::unlockFastAssumingZero(m_byte)))
95 unlockFairlySlow();
96 }
97
98 void safepoint()
99 {
100 if (UNLIKELY(!DefaultLockAlgorithm::safepointFast(m_byte)))
101 safepointSlow();
102 }
103
104 bool isHeld() const
105 {
106 return DefaultLockAlgorithm::isLocked(m_byte);
107 }
108
109 bool isLocked() const
110 {
111 return isHeld();
112 }
113
114private:
115 friend struct TestWebKitAPI::LockInspector;
116
117 static const uint8_t isHeldBit = 1;
118 static const uint8_t hasParkedBit = 2;
119
120 WTF_EXPORT_PRIVATE void lockSlow();
121 WTF_EXPORT_PRIVATE void unlockSlow();
122 WTF_EXPORT_PRIVATE void unlockFairlySlow();
123 WTF_EXPORT_PRIVATE void safepointSlow();
124
125 // Method used for testing only.
126 bool isFullyReset() const
127 {
128 return !m_byte.load();
129 }
130
131 Atomic<uint8_t> m_byte { 0 };
132};
133
134using LockHolder = Locker<Lock>;
135
136} // namespace WTF
137
138using WTF::Lock;
139using WTF::LockHolder;
140