GC constraint solving should be parallel
[WebKit-https.git] / Source / WTF / wtf / CountingLock.h
1 /*
2  * Copyright (C) 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/DataLog.h>
29 #include <wtf/LockAlgorithm.h>
30
31 namespace WTF {
32
33 // This is mostly just a word-sized WTF::Lock. It supports basically everything that lock supports. But as
34 // a bonus, it atomically counts lock() calls and allows you to perform an optimistic read transaction by
35 // comparing the count before and after the transaction. If at the start of the transaction the lock is
36 // not held and the count remains the same throughout the transaction, then you know that nobody could
37 // have modified your data structure while you ran. You can even use this to optimistically read pointers
38 // that could become dangling under concurrent writes, if you just revalidate the count every time you're
39 // about to do something dangerous.
40 //
41 // This is largely inspired by StampedLock from Java:
42 // https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/locks/CountingLock.html
43 //
44 // This is simplified a lot compared to StampedLock. Unlike StampedLock, it uses an exclusive lock as a
45 // fallback. There is no way to acquire a CountingLock for read. The only read access is via optimistic
46 // read transactions.
47 //
48 // CountingLock provides two ways of doing optimistic reads:
49 //
50 // - The easy way, where CountingLock does all of the fencing for you. That fencing is free on x86 but
51 //   somewhat expensive on ARM.
52 // - The hard way, where you do fencing yourself using Dependency. This allows you to be fenceless on both
53 //   x86 and ARM.
54 //
55 // The latter is important for us because some GC paths are known to be sensitive to fences on ARM.
56
57 class CountingLock {
58     typedef unsigned LockType;
59     
60     static constexpr LockType isHeldBit = 1;
61     static constexpr LockType hasParkedBit = 2;
62     static constexpr LockType mask = isHeldBit | hasParkedBit;
63     static constexpr LockType shift = 2;
64     static constexpr LockType countUnit = 4;
65     
66     struct LockHooks {
67         static LockType lockHook(LockType value)
68         {
69             return value + countUnit;
70         }
71         
72         static LockType unlockHook(LockType value) { return value; }
73         static LockType parkHook(LockType value) { return value; }
74         static LockType handoffHook(LockType value) { return value; }
75     };
76     
77     typedef LockAlgorithm<LockType, isHeldBit, hasParkedBit, LockHooks> ExclusiveAlgorithm;
78     
79 public:
80     CountingLock()
81     {
82         m_word.storeRelaxed(0);
83     }
84     
85     ~CountingLock()
86     {
87     }
88     
89     bool tryLock()
90     {
91         return ExclusiveAlgorithm::tryLock(m_word);
92     }
93
94     void lock()
95     {
96         if (UNLIKELY(!ExclusiveAlgorithm::lockFast(m_word)))
97             lockSlow();
98     }
99     
100     void unlock()
101     {
102         if (UNLIKELY(!ExclusiveAlgorithm::unlockFast(m_word)))
103             unlockSlow();
104     }
105     
106     bool isHeld() const
107     {
108         return ExclusiveAlgorithm::isLocked(m_word);
109     }
110     
111     bool isLocked() const
112     {
113         return isHeld();
114     }
115     
116     // The only thing you're allowed to infer from this value is that if it's zero, then you didn't get
117     // a real count.
118     class Count {
119     public:
120         explicit operator bool() const { return !!m_value; }
121         
122         bool operator==(const Count& other) const { return m_value == other.m_value; }
123         bool operator!=(const Count& other) const { return m_value != other.m_value; }
124         
125     private:
126         friend class CountingLock;
127         
128         LockType m_value { 0 };
129     };
130     
131     // Example of how to use this:
132     //
133     //     int read()
134     //     {
135     //         if (CountingLock::Count count = m_lock.tryOptimisticRead()) {
136     //             int value = m_things;
137     //             if (m_lock.validate(count))
138     //                 return value; // success!
139     //         }
140     //         auto locker = holdLock(m_lock);
141     //         int value = m_things;
142     //         return value;
143     //     }
144     //
145     // If tryOptimisitcRead() runs when the lock is not held, this thread will run a critical section
146     // without ever writing to memory. However, on ARM, this requires fencing. We use a load-acquire for
147     // tryOptimisticRead(). We have no choice but to use the more expensive `dmb ish` in validate(). If
148     // you want to avoid that, you could try to use tryOptimisticFencelessRead().
149     Count tryOptimisticRead()
150     {
151         LockType currentValue = m_word.load();
152         // FIXME: We could eliminate this check, if we think it's OK to proceed with the optimistic read
153         // path even after knowing that it must fail. That's probably good for perf since we expect
154         // failure to be super rare. We would get rid of this check and instead of calling getCount below,
155         // we would return currentValue ^ mask. If the lock state was empty to begin with, the result
156         // would be a properly blessed count (both low bits set). If the lock state was anything else, we
157         // would get an improperly blessed count that would not possibly succeed in validate. We could
158         // actually do something like "return (currentValue | hasParkedBit) ^ isHeldBit", which would mean
159         // that we allow parked-but-not-held-locks through.
160         // https://bugs.webkit.org/show_bug.cgi?id=180394
161         if (currentValue & isHeldBit)
162             return Count();
163         return getCount(currentValue);
164     }
165     
166     bool validate(Count count)
167     {
168         WTF::loadLoadFence();
169         LockType currentValue = m_word.loadRelaxed();
170         return getCount(currentValue) == count;
171     }
172     
173     // Example of how to use this:
174     //
175     //     int read()
176     //     {
177     //         return m_lock.doOptimizedRead(
178     //             [&] () -> int {
179     //                 int value = m_things;
180     //                 return value;
181     //             });
182     //     }
183     template<typename Func>
184     auto doOptimizedRead(const Func& func)
185     {
186         Count count = tryOptimisticRead();
187         if (count) {
188             auto result = func();
189             if (validate(count))
190                 return result;
191         }
192         lock();
193         auto result = func();
194         unlock();
195         return result;
196     }
197     
198     // Example of how to use this:
199     //
200     //     int read()
201     //     {
202     //         auto result = m_lock.tryOptimisticFencelessRead();
203     //         if (CountingLock::Count count = result.value) {
204     //             Dependency fenceBefore = Dependency::fence(result.input);
205     //             auto* fencedThis = fenceBefore.consume(this);
206     //             int value = fencedThis->m_things;
207     //             if (m_lock.fencelessValidate(count, Dependency::fence(value)))
208     //                 return value; // success!
209     //         }
210     //         auto locker = holdLock(m_lock);
211     //         int value = m_things;
212     //         return value;
213     //     }
214     //
215     // Use this to create a read transaction using dependency chains only. You have to be careful to
216     // thread the dependency input (the `input` field that the returns) through a Dependency, and then
217     // thread that Dependency into every load (except for loads that are chasing pointers loaded from
218     // loads that already uses that dependency). Then, to validate the read transaction, you have to pass
219     // both the count and another Dependency that is based on whatever loads you used to produce the
220     // output.
221     //
222     // On non-ARM platforms, the Dependency objects don't do anything except for Dependency::fence, which
223     // is a load-load fence. The idiom above does the right thing on both ARM and TSO.
224     //
225     // WARNING: This can be hard to get right. Please only use this for very short critical sections that
226     // are known to be sufficiently perf-critical to justify the risk.
227     InputAndValue<LockType, Count> tryOptimisticFencelessRead()
228     {
229         LockType currentValue = m_word.loadRelaxed();
230         if (currentValue & isHeldBit)
231             return inputAndValue(currentValue, Count());
232         return inputAndValue(currentValue, getCount(currentValue));
233     }
234     
235     bool fencelessValidate(Count count, Dependency dependency)
236     {
237         LockType currentValue = dependency.consume(this)->m_word.loadRelaxed();
238         return getCount(currentValue) == count;
239     }
240     
241     template<typename OptimisticFunc, typename Func>
242     auto doOptimizedFencelessRead(const OptimisticFunc& optimisticFunc, const Func& func)
243     {
244         auto count = tryOptimisticFencelessRead();
245         if (count.value) {
246             Dependency dependency = Dependency::fence(count.input);
247             auto result = optimisticFunc(dependency, count.value);
248             if (fencelessValidate(count.value, dependency))
249                 return result;
250         }
251         lock();
252         auto result = func();
253         unlock();
254         return result;
255     }
256     
257 private:
258     WTF_EXPORT_PRIVATE void lockSlow();
259     WTF_EXPORT_PRIVATE void unlockSlow();
260     
261     Count getCount(LockType value)
262     {
263         Count result;
264         result.m_value = value | mask;
265         return result;
266     }
267     
268     Atomic<LockType> m_word;
269 };
270
271 } // namespace WTF
272
273 using WTF::CountingLock;
274