Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : /*
8 : * Implements (almost always) lock-free atomic operations. The operations here
9 : * are a subset of that which can be found in C++11's <atomic> header, with a
10 : * different API to enforce consistent memory ordering constraints.
11 : *
12 : * Anyone caught using |volatile| for inter-thread memory safety needs to be
13 : * sent a copy of this header and the C++11 standard.
14 : */
15 :
16 : #ifndef mozilla_Atomics_h
17 : #define mozilla_Atomics_h
18 :
19 : #include "mozilla/Assertions.h"
20 : #include "mozilla/Attributes.h"
21 : #include "mozilla/Compiler.h"
22 : #include "mozilla/TypeTraits.h"
23 :
24 : #include <atomic>
25 :
26 : #include <stdint.h>
27 :
28 : namespace mozilla {
29 :
30 : /**
31 : * An enum of memory ordering possibilities for atomics.
32 : *
33 : * Memory ordering is the observable state of distinct values in memory.
34 : * (It's a separate concept from atomicity, which concerns whether an
35 : * operation can ever be observed in an intermediate state. Don't
36 : * conflate the two!) Given a sequence of operations in source code on
37 : * memory, it is *not* always the case that, at all times and on all
38 : * cores, those operations will appear to have occurred in that exact
39 : * sequence. First, the compiler might reorder that sequence, if it
40 : * thinks another ordering will be more efficient. Second, the CPU may
41 : * not expose so consistent a view of memory. CPUs will often perform
42 : * their own instruction reordering, above and beyond that performed by
43 : * the compiler. And each core has its own memory caches, and accesses
44 : * (reads and writes both) to "memory" may only resolve to out-of-date
45 : * cache entries -- not to the "most recently" performed operation in
46 : * some global sense. Any access to a value that may be used by
47 : * multiple threads, potentially across multiple cores, must therefore
48 : * have a memory ordering imposed on it, for all code on all
49 : * threads/cores to have a sufficiently coherent worldview.
50 : *
51 : * http://gcc.gnu.org/wiki/Atomic/GCCMM/AtomicSync and
52 : * http://en.cppreference.com/w/cpp/atomic/memory_order go into more
53 : * detail on all this, including examples of how each mode works.
54 : *
55 : * Note that for simplicity and practicality, not all of the modes in
56 : * C++11 are supported. The missing C++11 modes are either subsumed by
57 : * the modes we provide below, or not relevant for the CPUs we support
58 : * in Gecko. These three modes are confusing enough as it is!
59 : */
60 : enum MemoryOrdering {
61 : /*
62 : * Relaxed ordering is the simplest memory ordering: none at all.
63 : * When the result of a write is observed, nothing may be inferred
64 : * about other memory. Writes ostensibly performed "before" on the
65 : * writing thread may not yet be visible. Writes performed "after" on
66 : * the writing thread may already be visible, if the compiler or CPU
67 : * reordered them. (The latter can happen if reads and/or writes get
68 : * held up in per-processor caches.) Relaxed ordering means
69 : * operations can always use cached values (as long as the actual
70 : * updates to atomic values actually occur, correctly, eventually), so
71 : * it's usually the fastest sort of atomic access. For this reason,
72 : * *it's also the most dangerous kind of access*.
73 : *
74 : * Relaxed ordering is good for things like process-wide statistics
75 : * counters that don't need to be consistent with anything else, so
76 : * long as updates themselves are atomic. (And so long as any
77 : * observations of that value can tolerate being out-of-date -- if you
78 : * need some sort of up-to-date value, you need some sort of other
79 : * synchronizing operation.) It's *not* good for locks, mutexes,
80 : * reference counts, etc. that mediate access to other memory, or must
81 : * be observably consistent with other memory.
82 : *
83 : * x86 architectures don't take advantage of the optimization
84 : * opportunities that relaxed ordering permits. Thus it's possible
85 : * that using relaxed ordering will "work" on x86 but fail elsewhere
86 : * (ARM, say, which *does* implement non-sequentially-consistent
87 : * relaxed ordering semantics). Be extra-careful using relaxed
88 : * ordering if you can't easily test non-x86 architectures!
89 : */
90 : Relaxed,
91 :
92 : /*
93 : * When an atomic value is updated with ReleaseAcquire ordering, and
94 : * that new value is observed with ReleaseAcquire ordering, prior
95 : * writes (atomic or not) are also observable. What ReleaseAcquire
96 : * *doesn't* give you is any observable ordering guarantees for
97 : * ReleaseAcquire-ordered operations on different objects. For
98 : * example, if there are two cores that each perform ReleaseAcquire
99 : * operations on separate objects, each core may or may not observe
100 : * the operations made by the other core. The only way the cores can
101 : * be synchronized with ReleaseAcquire is if they both
102 : * ReleaseAcquire-access the same object. This implies that you can't
103 : * necessarily describe some global total ordering of ReleaseAcquire
104 : * operations.
105 : *
106 : * ReleaseAcquire ordering is good for (as the name implies) atomic
107 : * operations on values controlling ownership of things: reference
108 : * counts, mutexes, and the like. However, if you are thinking about
109 : * using these to implement your own locks or mutexes, you should take
110 : * a good, hard look at actual lock or mutex primitives first.
111 : */
112 : ReleaseAcquire,
113 :
114 : /*
115 : * When an atomic value is updated with SequentiallyConsistent
116 : * ordering, all writes observable when the update is observed, just
117 : * as with ReleaseAcquire ordering. But, furthermore, a global total
118 : * ordering of SequentiallyConsistent operations *can* be described.
119 : * For example, if two cores perform SequentiallyConsistent operations
120 : * on separate objects, one core will observably perform its update
121 : * (and all previous operations will have completed), then the other
122 : * core will observably perform its update (and all previous
123 : * operations will have completed). (Although those previous
124 : * operations aren't themselves ordered -- they could be intermixed,
125 : * or ordered if they occur on atomic values with ordering
126 : * requirements.) SequentiallyConsistent is the *simplest and safest*
127 : * ordering of atomic operations -- it's always as if one operation
128 : * happens, then another, then another, in some order -- and every
129 : * core observes updates to happen in that single order. Because it
130 : * has the most synchronization requirements, operations ordered this
131 : * way also tend to be slowest.
132 : *
133 : * SequentiallyConsistent ordering can be desirable when multiple
134 : * threads observe objects, and they all have to agree on the
135 : * observable order of changes to them. People expect
136 : * SequentiallyConsistent ordering, even if they shouldn't, when
137 : * writing code, atomic or otherwise. SequentiallyConsistent is also
138 : * the ordering of choice when designing lockless data structures. If
139 : * you don't know what order to use, use this one.
140 : */
141 : SequentiallyConsistent,
142 : };
143 :
144 : namespace detail {
145 :
146 : /*
147 : * We provide CompareExchangeFailureOrder to work around a bug in some
148 : * versions of GCC's <atomic> header. See bug 898491.
149 : */
150 : template<MemoryOrdering Order> struct AtomicOrderConstraints;
151 :
152 : template<>
153 : struct AtomicOrderConstraints<Relaxed>
154 : {
155 : static const std::memory_order AtomicRMWOrder = std::memory_order_relaxed;
156 : static const std::memory_order LoadOrder = std::memory_order_relaxed;
157 : static const std::memory_order StoreOrder = std::memory_order_relaxed;
158 : static const std::memory_order CompareExchangeFailureOrder =
159 : std::memory_order_relaxed;
160 : };
161 :
162 : template<>
163 : struct AtomicOrderConstraints<ReleaseAcquire>
164 : {
165 : static const std::memory_order AtomicRMWOrder = std::memory_order_acq_rel;
166 : static const std::memory_order LoadOrder = std::memory_order_acquire;
167 : static const std::memory_order StoreOrder = std::memory_order_release;
168 : static const std::memory_order CompareExchangeFailureOrder =
169 : std::memory_order_acquire;
170 : };
171 :
172 : template<>
173 : struct AtomicOrderConstraints<SequentiallyConsistent>
174 : {
175 : static const std::memory_order AtomicRMWOrder = std::memory_order_seq_cst;
176 : static const std::memory_order LoadOrder = std::memory_order_seq_cst;
177 : static const std::memory_order StoreOrder = std::memory_order_seq_cst;
178 : static const std::memory_order CompareExchangeFailureOrder =
179 : std::memory_order_seq_cst;
180 : };
181 :
182 : template<typename T, MemoryOrdering Order>
183 : struct IntrinsicBase
184 : {
185 : typedef std::atomic<T> ValueType;
186 : typedef AtomicOrderConstraints<Order> OrderedOp;
187 : };
188 :
189 : template<typename T, MemoryOrdering Order>
190 : struct IntrinsicMemoryOps : public IntrinsicBase<T, Order>
191 : {
192 : typedef IntrinsicBase<T, Order> Base;
193 :
194 166737112 : static T load(const typename Base::ValueType& aPtr)
195 : {
196 284177328 : return aPtr.load(Base::OrderedOp::LoadOrder);
197 : }
198 :
199 97119 : static void store(typename Base::ValueType& aPtr, T aVal)
200 : {
201 97119 : aPtr.store(aVal, Base::OrderedOp::StoreOrder);
202 97118 : }
203 :
204 436304 : static T exchange(typename Base::ValueType& aPtr, T aVal)
205 : {
206 872607 : return aPtr.exchange(aVal, Base::OrderedOp::AtomicRMWOrder);
207 : }
208 :
209 144 : static bool compareExchange(typename Base::ValueType& aPtr,
210 : T aOldVal, T aNewVal)
211 : {
212 : return aPtr.compare_exchange_strong(aOldVal, aNewVal,
213 : Base::OrderedOp::AtomicRMWOrder,
214 247 : Base::OrderedOp::CompareExchangeFailureOrder);
215 : }
216 : };
217 :
218 : template<typename T, MemoryOrdering Order>
219 : struct IntrinsicAddSub : public IntrinsicBase<T, Order>
220 : {
221 : typedef IntrinsicBase<T, Order> Base;
222 :
223 645083 : static T add(typename Base::ValueType& aPtr, T aVal)
224 : {
225 1290166 : return aPtr.fetch_add(aVal, Base::OrderedOp::AtomicRMWOrder);
226 : }
227 :
228 531640 : static T sub(typename Base::ValueType& aPtr, T aVal)
229 : {
230 1063280 : return aPtr.fetch_sub(aVal, Base::OrderedOp::AtomicRMWOrder);
231 : }
232 : };
233 :
234 : template<typename T, MemoryOrdering Order>
235 : struct IntrinsicAddSub<T*, Order> : public IntrinsicBase<T*, Order>
236 : {
237 : typedef IntrinsicBase<T*, Order> Base;
238 :
239 : static T* add(typename Base::ValueType& aPtr, ptrdiff_t aVal)
240 : {
241 : return aPtr.fetch_add(aVal, Base::OrderedOp::AtomicRMWOrder);
242 : }
243 :
244 : static T* sub(typename Base::ValueType& aPtr, ptrdiff_t aVal)
245 : {
246 : return aPtr.fetch_sub(aVal, Base::OrderedOp::AtomicRMWOrder);
247 : }
248 : };
249 :
250 : template<typename T, MemoryOrdering Order>
251 : struct IntrinsicIncDec : public IntrinsicAddSub<T, Order>
252 : {
253 : typedef IntrinsicBase<T, Order> Base;
254 :
255 615983 : static T inc(typename Base::ValueType& aPtr)
256 : {
257 615983 : return IntrinsicAddSub<T, Order>::add(aPtr, 1);
258 : }
259 :
260 318542 : static T dec(typename Base::ValueType& aPtr)
261 : {
262 318542 : return IntrinsicAddSub<T, Order>::sub(aPtr, 1);
263 : }
264 : };
265 :
266 : template<typename T, MemoryOrdering Order>
267 : struct AtomicIntrinsics : public IntrinsicMemoryOps<T, Order>,
268 : public IntrinsicIncDec<T, Order>
269 : {
270 : typedef IntrinsicBase<T, Order> Base;
271 :
272 0 : static T or_(typename Base::ValueType& aPtr, T aVal)
273 : {
274 0 : return aPtr.fetch_or(aVal, Base::OrderedOp::AtomicRMWOrder);
275 : }
276 :
277 : static T xor_(typename Base::ValueType& aPtr, T aVal)
278 : {
279 : return aPtr.fetch_xor(aVal, Base::OrderedOp::AtomicRMWOrder);
280 : }
281 :
282 : static T and_(typename Base::ValueType& aPtr, T aVal)
283 : {
284 : return aPtr.fetch_and(aVal, Base::OrderedOp::AtomicRMWOrder);
285 : }
286 : };
287 :
288 : template<typename T, MemoryOrdering Order>
289 : struct AtomicIntrinsics<T*, Order>
290 : : public IntrinsicMemoryOps<T*, Order>, public IntrinsicIncDec<T*, Order>
291 : {
292 : };
293 :
294 : template<typename T>
295 : struct ToStorageTypeArgument
296 : {
297 49687 : static constexpr T convert (T aT) { return aT; }
298 : };
299 :
300 : template<typename T, MemoryOrdering Order>
301 : class AtomicBase
302 : {
303 : static_assert(sizeof(T) == 4 || sizeof(T) == 8,
304 : "mozilla/Atomics.h only supports 32-bit and 64-bit types");
305 :
306 : protected:
307 : typedef typename detail::AtomicIntrinsics<T, Order> Intrinsics;
308 : typedef typename Intrinsics::ValueType ValueType;
309 : ValueType mValue;
310 :
311 : public:
312 183 : constexpr AtomicBase() : mValue() {}
313 49687 : explicit constexpr AtomicBase(T aInit)
314 49687 : : mValue(ToStorageTypeArgument<T>::convert(aInit))
315 49687 : {}
316 :
317 : // Note: we can't provide operator T() here because Atomic<bool> inherits
318 : // from AtomcBase with T=uint32_t and not T=bool. If we implemented
319 : // operator T() here, it would cause errors when comparing Atomic<bool> with
320 : // a regular bool.
321 :
322 97120 : T operator=(T aVal)
323 : {
324 97120 : Intrinsics::store(mValue, aVal);
325 97121 : return aVal;
326 : }
327 :
328 : /**
329 : * Performs an atomic swap operation. aVal is stored and the previous
330 : * value of this variable is returned.
331 : */
332 436296 : T exchange(T aVal)
333 : {
334 436296 : return Intrinsics::exchange(mValue, aVal);
335 : }
336 :
337 : /**
338 : * Performs an atomic compare-and-swap operation and returns true if it
339 : * succeeded. This is equivalent to atomically doing
340 : *
341 : * if (mValue == aOldValue) {
342 : * mValue = aNewValue;
343 : * return true;
344 : * } else {
345 : * return false;
346 : * }
347 : */
348 144 : bool compareExchange(T aOldValue, T aNewValue)
349 : {
350 144 : return Intrinsics::compareExchange(mValue, aOldValue, aNewValue);
351 : }
352 :
353 : private:
354 : template<MemoryOrdering AnyOrder>
355 : AtomicBase(const AtomicBase<T, AnyOrder>& aCopy) = delete;
356 : };
357 :
358 : template<typename T, MemoryOrdering Order>
359 : class AtomicBaseIncDec : public AtomicBase<T, Order>
360 : {
361 : typedef typename detail::AtomicBase<T, Order> Base;
362 :
363 : public:
364 131 : constexpr AtomicBaseIncDec() : Base() {}
365 43848 : explicit constexpr AtomicBaseIncDec(T aInit) : Base(aInit) {}
366 :
367 : using Base::operator=;
368 :
369 160084244 : operator T() const { return Base::Intrinsics::load(Base::mValue); }
370 585240 : T operator++(int) { return Base::Intrinsics::inc(Base::mValue); }
371 299274 : T operator--(int) { return Base::Intrinsics::dec(Base::mValue); }
372 30740 : T operator++() { return Base::Intrinsics::inc(Base::mValue) + 1; }
373 19268 : T operator--() { return Base::Intrinsics::dec(Base::mValue) - 1; }
374 :
375 : private:
376 : template<MemoryOrdering AnyOrder>
377 : AtomicBaseIncDec(const AtomicBaseIncDec<T, AnyOrder>& aCopy) = delete;
378 : };
379 :
380 : } // namespace detail
381 :
382 : /**
383 : * A wrapper for a type that enforces that all memory accesses are atomic.
384 : *
385 : * In general, where a variable |T foo| exists, |Atomic<T> foo| can be used in
386 : * its place. Implementations for integral and pointer types are provided
387 : * below.
388 : *
389 : * Atomic accesses are sequentially consistent by default. You should
390 : * use the default unless you are tall enough to ride the
391 : * memory-ordering roller coaster (if you're not sure, you aren't) and
392 : * you have a compelling reason to do otherwise.
393 : *
394 : * There is one exception to the case of atomic memory accesses: providing an
395 : * initial value of the atomic value is not guaranteed to be atomic. This is a
396 : * deliberate design choice that enables static atomic variables to be declared
397 : * without introducing extra static constructors.
398 : */
399 : template<typename T,
400 : MemoryOrdering Order = SequentiallyConsistent,
401 : typename Enable = void>
402 : class Atomic;
403 :
404 : /**
405 : * Atomic<T> implementation for integral types.
406 : *
407 : * In addition to atomic store and load operations, compound assignment and
408 : * increment/decrement operators are implemented which perform the
409 : * corresponding read-modify-write operation atomically. Finally, an atomic
410 : * swap method is provided.
411 : */
412 : template<typename T, MemoryOrdering Order>
413 : class Atomic<T, Order, typename EnableIf<IsIntegral<T>::value &&
414 : !IsSame<T, bool>::value>::Type>
415 : : public detail::AtomicBaseIncDec<T, Order>
416 : {
417 : typedef typename detail::AtomicBaseIncDec<T, Order> Base;
418 :
419 : public:
420 11 : constexpr Atomic() : Base() {}
421 28485 : explicit constexpr Atomic(T aInit) : Base(aInit) {}
422 :
423 : using Base::operator=;
424 :
425 29063 : T operator+=(T aDelta)
426 : {
427 29063 : return Base::Intrinsics::add(Base::mValue, aDelta) + aDelta;
428 : }
429 :
430 213064 : T operator-=(T aDelta)
431 : {
432 213064 : return Base::Intrinsics::sub(Base::mValue, aDelta) - aDelta;
433 : }
434 :
435 0 : T operator|=(T aVal)
436 : {
437 0 : return Base::Intrinsics::or_(Base::mValue, aVal) | aVal;
438 : }
439 :
440 : T operator^=(T aVal)
441 : {
442 : return Base::Intrinsics::xor_(Base::mValue, aVal) ^ aVal;
443 : }
444 :
445 : T operator&=(T aVal)
446 : {
447 : return Base::Intrinsics::and_(Base::mValue, aVal) & aVal;
448 : }
449 :
450 : private:
451 : Atomic(Atomic<T, Order>& aOther) = delete;
452 : };
453 :
454 : /**
455 : * Atomic<T> implementation for pointer types.
456 : *
457 : * An atomic compare-and-swap primitive for pointer variables is provided, as
458 : * are atomic increment and decement operators. Also provided are the compound
459 : * assignment operators for addition and subtraction. Atomic swap (via
460 : * exchange()) is included as well.
461 : */
462 : template<typename T, MemoryOrdering Order>
463 : class Atomic<T*, Order> : public detail::AtomicBaseIncDec<T*, Order>
464 : {
465 : typedef typename detail::AtomicBaseIncDec<T*, Order> Base;
466 :
467 : public:
468 120 : constexpr Atomic() : Base() {}
469 15363 : explicit constexpr Atomic(T* aInit) : Base(aInit) {}
470 :
471 : using Base::operator=;
472 :
473 : T* operator+=(ptrdiff_t aDelta)
474 : {
475 : return Base::Intrinsics::add(Base::mValue, aDelta) + aDelta;
476 : }
477 :
478 : T* operator-=(ptrdiff_t aDelta)
479 : {
480 : return Base::Intrinsics::sub(Base::mValue, aDelta) - aDelta;
481 : }
482 :
483 : private:
484 : Atomic(Atomic<T*, Order>& aOther) = delete;
485 : };
486 :
487 : /**
488 : * Atomic<T> implementation for enum types.
489 : *
490 : * The atomic store and load operations and the atomic swap method is provided.
491 : */
492 : template<typename T, MemoryOrdering Order>
493 : class Atomic<T, Order, typename EnableIf<IsEnum<T>::value>::Type>
494 : : public detail::AtomicBase<T, Order>
495 : {
496 : typedef typename detail::AtomicBase<T, Order> Base;
497 :
498 : public:
499 : constexpr Atomic() : Base() {}
500 205 : explicit constexpr Atomic(T aInit) : Base(aInit) {}
501 :
502 149907 : operator T() const { return T(Base::Intrinsics::load(Base::mValue)); }
503 :
504 : using Base::operator=;
505 :
506 : private:
507 : Atomic(Atomic<T, Order>& aOther) = delete;
508 : };
509 :
510 : /**
511 : * Atomic<T> implementation for boolean types.
512 : *
513 : * The atomic store and load operations and the atomic swap method is provided.
514 : *
515 : * Note:
516 : *
517 : * - sizeof(Atomic<bool>) != sizeof(bool) for some implementations of
518 : * bool and/or some implementations of std::atomic. This is allowed in
519 : * [atomic.types.generic]p9.
520 : *
521 : * - It's not obvious whether the 8-bit atomic functions on Windows are always
522 : * inlined or not. If they are not inlined, the corresponding functions in the
523 : * runtime library are not available on Windows XP. This is why we implement
524 : * Atomic<bool> with an underlying type of uint32_t.
525 : */
526 : template<MemoryOrdering Order>
527 : class Atomic<bool, Order>
528 : : protected detail::AtomicBase<uint32_t, Order>
529 : {
530 : typedef typename detail::AtomicBase<uint32_t, Order> Base;
531 :
532 : public:
533 52 : constexpr Atomic() : Base() {}
534 5634 : explicit constexpr Atomic(bool aInit) : Base(aInit) {}
535 :
536 : // We provide boolean wrappers for the underlying AtomicBase methods.
537 6517304 : MOZ_IMPLICIT operator bool() const
538 : {
539 6517304 : return Base::Intrinsics::load(Base::mValue);
540 : }
541 :
542 25041 : bool operator=(bool aVal)
543 : {
544 25041 : return Base::operator=(aVal);
545 : }
546 :
547 1389 : bool exchange(bool aVal)
548 : {
549 1389 : return Base::exchange(aVal);
550 : }
551 :
552 103 : bool compareExchange(bool aOldValue, bool aNewValue)
553 : {
554 103 : return Base::compareExchange(aOldValue, aNewValue);
555 : }
556 :
557 : private:
558 : Atomic(Atomic<bool, Order>& aOther) = delete;
559 : };
560 :
561 : } // namespace mozilla
562 :
563 : #endif /* mozilla_Atomics_h */
|
