5dec3db069eca72529d93a859a61d963c5556c34
[WebKit-https.git] / Source / WTF / wtf / Atomics.h
1 /*
2  * Copyright (C) 2007-2017 Apple Inc. All rights reserved.
3  * Copyright (C) 2007 Justin Haygood (jhaygood@reaktix.com)
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
17  * DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS BE LIABLE FOR ANY
18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
20  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
21  * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
23  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #ifndef Atomics_h
27 #define Atomics_h
28
29 #include <atomic>
30 #include <wtf/StdLibExtras.h>
31
32 #if OS(WINDOWS)
33 #if !COMPILER(GCC_OR_CLANG)
34 extern "C" void _ReadWriteBarrier(void);
35 #pragma intrinsic(_ReadWriteBarrier)
36 #endif
37 #include <windows.h>
38 #include <intrin.h>
39 #endif
40
41 namespace WTF {
42
43 ALWAYS_INLINE bool hasFence(std::memory_order order)
44 {
45     return order != std::memory_order_relaxed;
46 }
47     
48 // Atomic wraps around std::atomic with the sole purpose of making the compare_exchange
49 // operations not alter the expected value. This is more in line with how we typically
50 // use CAS in our code.
51 //
52 // Atomic is a struct without explicitly defined constructors so that it can be
53 // initialized at compile time.
54
55 template<typename T>
56 struct Atomic {
57     // Don't pass a non-default value for the order parameter unless you really know
58     // what you are doing and have thought about it very hard. The cost of seq_cst
59     // is usually not high enough to justify the risk.
60
61     ALWAYS_INLINE T load(std::memory_order order = std::memory_order_seq_cst) const { return value.load(order); }
62     
63     ALWAYS_INLINE T loadRelaxed() const { return load(std::memory_order_relaxed); }
64     
65     // This is a load that simultaneously does a full fence - neither loads nor stores will move
66     // above or below it.
67     ALWAYS_INLINE T loadFullyFenced() const
68     {
69         Atomic<T>* ptr = const_cast<Atomic<T>*>(this);
70         return ptr->exchangeAdd(T());
71     }
72     
73     ALWAYS_INLINE void store(T desired, std::memory_order order = std::memory_order_seq_cst) { value.store(desired, order); }
74     
75     ALWAYS_INLINE void storeRelaxed(T desired) { store(desired, std::memory_order_relaxed); }
76
77     // This is a store that simultaneously does a full fence - neither loads nor stores will move
78     // above or below it.
79     ALWAYS_INLINE void storeFullyFenced(T desired)
80     {
81         exchange(desired);
82     }
83
84     ALWAYS_INLINE bool compareExchangeWeak(T expected, T desired, std::memory_order order = std::memory_order_seq_cst)
85     {
86         T expectedOrActual = expected;
87         return value.compare_exchange_weak(expectedOrActual, desired, order);
88     }
89
90     ALWAYS_INLINE bool compareExchangeWeakRelaxed(T expected, T desired)
91     {
92         return compareExchangeWeak(expected, desired, std::memory_order_relaxed);
93     }
94
95     ALWAYS_INLINE bool compareExchangeWeak(T expected, T desired, std::memory_order order_success, std::memory_order order_failure)
96     {
97         T expectedOrActual = expected;
98         return value.compare_exchange_weak(expectedOrActual, desired, order_success, order_failure);
99     }
100
101     // WARNING: This does not have strong fencing guarantees when it fails. For example, stores could
102     // sink below it in that case.
103     ALWAYS_INLINE T compareExchangeStrong(T expected, T desired, std::memory_order order = std::memory_order_seq_cst)
104     {
105         T expectedOrActual = expected;
106         value.compare_exchange_strong(expectedOrActual, desired, order);
107         return expectedOrActual;
108     }
109
110     ALWAYS_INLINE T compareExchangeStrong(T expected, T desired, std::memory_order order_success, std::memory_order order_failure)
111     {
112         T expectedOrActual = expected;
113         value.compare_exchange_strong(expectedOrActual, desired, order_success, order_failure);
114         return expectedOrActual;
115     }
116
117     template<typename U>
118     ALWAYS_INLINE T exchangeAdd(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_add(operand, order); }
119     
120     template<typename U>
121     ALWAYS_INLINE T exchangeAnd(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_and(operand, order); }
122     
123     template<typename U>
124     ALWAYS_INLINE T exchangeOr(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_or(operand, order); }
125     
126     template<typename U>
127     ALWAYS_INLINE T exchangeSub(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_sub(operand, order); }
128     
129     template<typename U>
130     ALWAYS_INLINE T exchangeXor(U operand, std::memory_order order = std::memory_order_seq_cst) { return value.fetch_xor(operand, order); }
131     
132     ALWAYS_INLINE T exchange(T newValue, std::memory_order order = std::memory_order_seq_cst) { return value.exchange(newValue, order); }
133
134     template<typename Func>
135     ALWAYS_INLINE bool transaction(const Func& func, std::memory_order order = std::memory_order_seq_cst)
136     {
137         for (;;) {
138             T oldValue = load(std::memory_order_relaxed);
139             T newValue = oldValue;
140             if (!func(newValue))
141                 return false;
142             if (compareExchangeWeak(oldValue, newValue, order))
143                 return true;
144         }
145     }
146
147     template<typename Func>
148     ALWAYS_INLINE bool transactionRelaxed(const Func& func)
149     {
150         return transaction(func, std::memory_order_relaxed);
151     }
152
153     Atomic() = default;
154     constexpr Atomic(T initial)
155         : value(std::forward<T>(initial))
156     {
157     }
158
159     std::atomic<T> value;
160 };
161
162 template<typename T>
163 inline T atomicLoad(T* location, std::memory_order order = std::memory_order_seq_cst)
164 {
165     return bitwise_cast<Atomic<T>*>(location)->load(order);
166 }
167
168 template<typename T>
169 inline T atomicLoadFullyFenced(T* location)
170 {
171     return bitwise_cast<Atomic<T>*>(location)->loadFullyFenced();
172 }
173
174 template<typename T>
175 inline void atomicStore(T* location, T newValue, std::memory_order order = std::memory_order_seq_cst)
176 {
177     bitwise_cast<Atomic<T>*>(location)->store(newValue, order);
178 }
179
180 template<typename T>
181 inline void atomicStoreFullyFenced(T* location, T newValue)
182 {
183     bitwise_cast<Atomic<T>*>(location)->storeFullyFenced(newValue);
184 }
185
186 template<typename T>
187 inline bool atomicCompareExchangeWeak(T* location, T expected, T newValue, std::memory_order order = std::memory_order_seq_cst)
188 {
189     return bitwise_cast<Atomic<T>*>(location)->compareExchangeWeak(expected, newValue, order);
190 }
191
192 template<typename T>
193 inline bool atomicCompareExchangeWeakRelaxed(T* location, T expected, T newValue)
194 {
195     return bitwise_cast<Atomic<T>*>(location)->compareExchangeWeakRelaxed(expected, newValue);
196 }
197
198 template<typename T>
199 inline T atomicCompareExchangeStrong(T* location, T expected, T newValue, std::memory_order order = std::memory_order_seq_cst)
200 {
201     return bitwise_cast<Atomic<T>*>(location)->compareExchangeStrong(expected, newValue, order);
202 }
203
204 template<typename T, typename U>
205 inline T atomicExchangeAdd(T* location, U operand, std::memory_order order = std::memory_order_seq_cst)
206 {
207     return bitwise_cast<Atomic<T>*>(location)->exchangeAdd(operand, order);
208 }
209
210 template<typename T, typename U>
211 inline T atomicExchangeAnd(T* location, U operand, std::memory_order order = std::memory_order_seq_cst)
212 {
213     return bitwise_cast<Atomic<T>*>(location)->exchangeAnd(operand, order);
214 }
215
216 template<typename T, typename U>
217 inline T atomicExchangeOr(T* location, U operand, std::memory_order order = std::memory_order_seq_cst)
218 {
219     return bitwise_cast<Atomic<T>*>(location)->exchangeOr(operand, order);
220 }
221
222 template<typename T, typename U>
223 inline T atomicExchangeSub(T* location, U operand, std::memory_order order = std::memory_order_seq_cst)
224 {
225     return bitwise_cast<Atomic<T>*>(location)->exchangeSub(operand, order);
226 }
227
228 template<typename T, typename U>
229 inline T atomicExchangeXor(T* location, U operand, std::memory_order order = std::memory_order_seq_cst)
230 {
231     return bitwise_cast<Atomic<T>*>(location)->exchangeXor(operand, order);
232 }
233
234 template<typename T>
235 inline T atomicExchange(T* location, T newValue, std::memory_order order = std::memory_order_seq_cst)
236 {
237     return bitwise_cast<Atomic<T>*>(location)->exchange(newValue, order);
238 }
239
240 // Just a compiler fence. Has no effect on the hardware, but tells the compiler
241 // not to move things around this call. Should not affect the compiler's ability
242 // to do things like register allocation and code motion over pure operations.
243 inline void compilerFence()
244 {
245 #if OS(WINDOWS) && !COMPILER(GCC_OR_CLANG)
246     _ReadWriteBarrier();
247 #else
248     asm volatile("" ::: "memory");
249 #endif
250 }
251
252 #if CPU(ARM_THUMB2) || CPU(ARM64)
253
254 // Full memory fence. No accesses will float above this, and no accesses will sink
255 // below it.
256 inline void arm_dmb()
257 {
258     asm volatile("dmb ish" ::: "memory");
259 }
260
261 // Like the above, but only affects stores.
262 inline void arm_dmb_st()
263 {
264     asm volatile("dmb ishst" ::: "memory");
265 }
266
267 inline void arm_isb()
268 {
269     asm volatile("isb" ::: "memory");
270 }
271
272 inline void loadLoadFence() { arm_dmb(); }
273 inline void loadStoreFence() { arm_dmb(); }
274 inline void storeLoadFence() { arm_dmb(); }
275 inline void storeStoreFence() { arm_dmb_st(); }
276 inline void memoryBarrierAfterLock() { arm_dmb(); }
277 inline void memoryBarrierBeforeUnlock() { arm_dmb(); }
278 inline void crossModifyingCodeFence() { arm_isb(); }
279
280 #elif CPU(X86) || CPU(X86_64)
281
282 inline void x86_ortop()
283 {
284 #if OS(WINDOWS)
285     MemoryBarrier();
286 #elif CPU(X86_64)
287     // This has acqrel semantics and is much cheaper than mfence. For exampe, in the JSC GC, using
288     // mfence as a store-load fence was a 9% slow-down on Octane/splay while using this was neutral.
289     asm volatile("lock; orl $0, (%%rsp)" ::: "memory");
290 #else
291     asm volatile("lock; orl $0, (%%esp)" ::: "memory");
292 #endif
293 }
294
295 inline void x86_cpuid()
296 {
297 #if OS(WINDOWS)
298     int info[4];
299     __cpuid(info, 0);
300 #elif CPU(X86)
301     // GCC 4.9 on x86 in PIC mode can't use %ebx, so we have to save and restore it manually.
302     // But since we don't care about what cpuid returns (we use it as a serializing instruction),
303     // we can simply throw away what cpuid put in %ebx.
304     intptr_t a = 0, c, d;
305     asm volatile(
306         "pushl %%ebx\n\t"
307         "cpuid\n\t"
308         "popl %%ebx\n\t"
309         : "+a"(a), "=c"(c), "=d"(d)
310         :
311         : "memory");
312 #else
313     intptr_t a = 0, b, c, d;
314     asm volatile(
315         "cpuid"
316         : "+a"(a), "=b"(b), "=c"(c), "=d"(d)
317         :
318         : "memory");
319 #endif
320 }
321
322 inline void loadLoadFence() { compilerFence(); }
323 inline void loadStoreFence() { compilerFence(); }
324 inline void storeLoadFence() { x86_ortop(); }
325 inline void storeStoreFence() { compilerFence(); }
326 inline void memoryBarrierAfterLock() { compilerFence(); }
327 inline void memoryBarrierBeforeUnlock() { compilerFence(); }
328 inline void crossModifyingCodeFence() { x86_cpuid(); }
329
330 #else
331
332 inline void loadLoadFence() { std::atomic_thread_fence(std::memory_order_seq_cst); }
333 inline void loadStoreFence() { std::atomic_thread_fence(std::memory_order_seq_cst); }
334 inline void storeLoadFence() { std::atomic_thread_fence(std::memory_order_seq_cst); }
335 inline void storeStoreFence() { std::atomic_thread_fence(std::memory_order_seq_cst); }
336 inline void memoryBarrierAfterLock() { std::atomic_thread_fence(std::memory_order_seq_cst); }
337 inline void memoryBarrierBeforeUnlock() { std::atomic_thread_fence(std::memory_order_seq_cst); }
338 inline void crossModifyingCodeFence() { std::atomic_thread_fence(std::memory_order_seq_cst); } // Probably not strong enough.
339
340 #endif
341
342 typedef unsigned Dependency;
343
344 ALWAYS_INLINE Dependency nullDependency()
345 {
346     return 0;
347 }
348
349 template <typename T, typename std::enable_if<sizeof(T) == 8>::type* = nullptr>
350 ALWAYS_INLINE Dependency dependency(T value)
351 {
352     unsigned dependency;
353     uint64_t copy = bitwise_cast<uint64_t>(value);
354 #if CPU(ARM64)
355     // Create a magical zero value through inline assembly, whose computation
356     // isn't visible to the optimizer. This zero is then usable as an offset in
357     // further address computations: adding zero does nothing, but the compiler
358     // doesn't know it. It's magical because it creates an address dependency
359     // from the load of `location` to the uses of the dependency, which triggers
360     // the ARM ISA's address dependency rule, a.k.a. the mythical C++ consume
361     // ordering. This forces weak memory order CPUs to observe `location` and
362     // dependent loads in their store order without the reader using a barrier
363     // or an acquire load.
364     asm("eor %w[dependency], %w[in], %w[in]"
365         : [dependency] "=r"(dependency)
366         : [in] "r"(copy));
367 #elif CPU(ARM)
368     asm("eor %[dependency], %[in], %[in]"
369         : [dependency] "=r"(dependency)
370         : [in] "r"(copy));
371 #else
372     // No dependency is needed for this architecture.
373     loadLoadFence();
374     dependency = 0;
375     UNUSED_PARAM(copy);
376 #endif
377     return dependency;
378 }
379
380 // FIXME: This code is almost identical to the other dependency() overload.
381 // https://bugs.webkit.org/show_bug.cgi?id=169405
382 template <typename T, typename std::enable_if<sizeof(T) == 4>::type* = nullptr>
383 ALWAYS_INLINE Dependency dependency(T value)
384 {
385     unsigned dependency;
386     uint32_t copy = bitwise_cast<uint32_t>(value);
387 #if CPU(ARM64)
388     asm("eor %w[dependency], %w[in], %w[in]"
389         : [dependency] "=r"(dependency)
390         : [in] "r"(copy));
391 #elif CPU(ARM)
392     asm("eor %[dependency], %[in], %[in]"
393         : [dependency] "=r"(dependency)
394         : [in] "r"(copy));
395 #else
396     loadLoadFence();
397     dependency = 0;
398     UNUSED_PARAM(copy);
399 #endif
400     return dependency;
401 }
402
403 template <typename T, typename std::enable_if<sizeof(T) == 2>::type* = nullptr>
404 ALWAYS_INLINE Dependency dependency(T value)
405 {
406     return dependency(static_cast<uint32_t>(value));
407 }
408
409 template <typename T, typename std::enable_if<sizeof(T) == 1>::type* = nullptr>
410 ALWAYS_INLINE Dependency dependency(T value)
411 {
412     return dependency(static_cast<uint32_t>(value));
413 }
414
415 template<typename T>
416 struct DependencyWith {
417 public:
418     DependencyWith()
419         : dependency(nullDependency())
420         , value()
421     {
422     }
423     
424     DependencyWith(Dependency dependency, const T& value)
425         : dependency(dependency)
426         , value(value)
427     {
428     }
429     
430     Dependency dependency;
431     T value;
432 };
433     
434 template<typename T>
435 inline DependencyWith<T> dependencyWith(Dependency dependency, const T& value)
436 {
437     return DependencyWith<T>(dependency, value);
438 }
439
440 template<typename T>
441 inline T* consume(T* pointer, Dependency dependency)
442 {
443 #if CPU(ARM64) || CPU(ARM)
444     return bitwise_cast<T*>(bitwise_cast<char*>(pointer) + dependency);
445 #else
446     UNUSED_PARAM(dependency);
447     return pointer;
448 #endif
449 }
450
451 template<typename T, typename Func>
452 ALWAYS_INLINE T& ensurePointer(Atomic<T*>& pointer, const Func& func)
453 {
454     for (;;) {
455         T* oldValue = pointer.load(std::memory_order_relaxed);
456         if (oldValue) {
457             // On all sensible CPUs, we get an implicit dependency-based load-load barrier when
458             // loading this.
459             return *oldValue;
460         }
461         T* newValue = func();
462         if (pointer.compareExchangeWeak(oldValue, newValue))
463             return *newValue;
464         delete newValue;
465     }
466 }
467
468 } // namespace WTF
469
470 using WTF::Atomic;
471 using WTF::Dependency;
472 using WTF::DependencyWith;
473 using WTF::consume;
474 using WTF::dependency;
475 using WTF::dependencyWith;
476 using WTF::ensurePointer;
477 using WTF::nullDependency;
478
479 #endif // Atomics_h