2 * Copyright (c) 2013, 2014 Nicira, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at:
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
18 #define OVS_ATOMIC_H 1
22 * This library implements atomic operations with an API based on the one
23 * defined in C11. It includes multiple implementations for compilers and
24 * libraries with varying degrees of built-in support for C11, including a
25 * fallback implementation for systems that have pthreads but no other support
28 * This comment describes the common features of all the implementations.
34 * The following atomic types are supported as typedefs for atomic versions of
35 * the listed ordinary types:
37 * ordinary type atomic version
38 * ------------------- ----------------------
42 * signed char atomic_schar
43 * unsigned char atomic_uchar
46 * unsigned short atomic_ushort
49 * unsigned int atomic_uint
52 * unsigned long atomic_ulong
54 * long long atomic_llong
55 * unsigned long long atomic_ullong
57 * size_t atomic_size_t
58 * ptrdiff_t atomic_ptrdiff_t
60 * intmax_t atomic_intmax_t
61 * uintmax_t atomic_uintmax_t
63 * intptr_t atomic_intptr_t
64 * uintptr_t atomic_uintptr_t
66 * uint8_t atomic_uint8_t (*)
67 * uint16_t atomic_uint16_t (*)
68 * uint32_t atomic_uint32_t (*)
69 * int8_t atomic_int8_t (*)
70 * int16_t atomic_int16_t (*)
71 * int32_t atomic_int32_t (*)
73 * (*) Not specified by C11.
75 * Atomic types may also be obtained via ATOMIC(TYPE), e.g. ATOMIC(void *).
76 * Only basic integer types and pointer types can be made atomic this way,
77 * e.g. atomic structs are not supported.
79 * The atomic version of a type doesn't necessarily have the same size or
80 * representation as the ordinary version; for example, atomic_int might be a
81 * typedef for a struct. The range of an atomic type does match the range of
82 * the corresponding ordinary type.
84 * C11 says that one may use the _Atomic keyword in place of the typedef name,
85 * e.g. "_Atomic int" instead of "atomic_int". This library doesn't support
92 * To initialize an atomic variable at its point of definition, use
95 * static atomic_int ai = ATOMIC_VAR_INIT(123);
97 * To initialize an atomic variable in code, use atomic_init():
99 * static atomic_int ai;
101 * atomic_init(&ai, 123);
107 * enum memory_order specifies the strictness of a memory barrier. It has the
110 * memory_order_relaxed:
112 * Compiler barrier only. Does not imply any CPU memory ordering.
114 * memory_order_acquire:
116 * Memory accesses after an acquire barrier cannot be moved before the
117 * barrier. Memory accesses before an acquire barrier *can* be moved
120 * memory_order_release:
122 * Memory accesses before a release barrier cannot be moved after the
123 * barrier. Memory accesses after a release barrier *can* be moved
126 * memory_order_acq_rel:
128 * Memory accesses cannot be moved across an acquire-release barrier in
131 * memory_order_seq_cst:
133 * Prevents movement of memory accesses like an acquire-release barrier,
134 * but whereas acquire-release synchronizes cooperating threads,
135 * sequential-consistency synchronizes the whole system.
137 * memory_order_consume:
139 * A slight relaxation of memory_order_acquire.
141 * The following functions insert explicit barriers. Most of the other atomic
142 * functions also include barriers.
144 * void atomic_thread_fence(memory_order order);
146 * Inserts a barrier of the specified type.
148 * For memory_order_relaxed, this is a no-op.
150 * void atomic_signal_fence(memory_order order);
152 * Inserts a barrier of the specified type, but only with respect to
153 * signal handlers in the same thread as the barrier. This is
154 * basically a compiler optimization barrier, except for
155 * memory_order_relaxed, which is a no-op.
161 * In this section, A is an atomic type and C is the corresponding non-atomic
164 * The "store" and "compare_exchange" primitives match C11:
166 * void atomic_store(A *object, C value);
167 * void atomic_store_explicit(A *object, C value, memory_order);
169 * Atomically stores 'value' into '*object', respecting the given
170 * memory order (or memory_order_seq_cst for atomic_store()).
172 * bool atomic_compare_exchange_strong(A *object, C *expected, C desired);
173 * bool atomic_compare_exchange_weak(A *object, C *expected, C desired);
174 * bool atomic_compare_exchange_strong_explicit(A *object, C *expected,
176 * memory_order success,
177 * memory_order failure);
178 * bool atomic_compare_exchange_weak_explicit(A *object, C *expected,
180 * memory_order success,
181 * memory_order failure);
183 * Atomically loads '*object' and compares it with '*expected' and if
184 * equal, stores 'desired' into '*object' (an atomic read-modify-write
185 * operation) and returns true, and if non-equal, stores the actual
186 * value of '*object' into '*expected' (an atomic load operation) and
187 * returns false. The memory order for the successful case (atomic
188 * read-modify-write operation) is 'success', and for the unsuccessful
189 * case (atomic load operation) 'failure'. 'failure' may not be
190 * stronger than 'success'.
192 * The weak forms may fail (returning false) also when '*object' equals
193 * '*expected'. The strong form can be implemented by the weak form in
194 * a loop. Some platforms can implement the weak form more
195 * efficiently, so it should be used if the application will need to
198 * The following primitives differ from the C11 ones (and have different names)
199 * because there does not appear to be a way to implement the standard
200 * primitives in standard C:
202 * void atomic_read(A *src, C *dst);
203 * void atomic_read_explicit(A *src, C *dst, memory_order);
205 * Atomically loads a value from 'src', writing the value read into
206 * '*dst', respecting the given memory order (or memory_order_seq_cst
207 * for atomic_read()).
209 * void atomic_add(A *rmw, C arg, C *orig);
210 * void atomic_sub(A *rmw, C arg, C *orig);
211 * void atomic_or(A *rmw, C arg, C *orig);
212 * void atomic_xor(A *rmw, C arg, C *orig);
213 * void atomic_and(A *rmw, C arg, C *orig);
214 * void atomic_add_explicit(A *rmw, C arg, C *orig, memory_order);
215 * void atomic_sub_explicit(A *rmw, C arg, C *orig, memory_order);
216 * void atomic_or_explicit(A *rmw, C arg, C *orig, memory_order);
217 * void atomic_xor_explicit(A *rmw, C arg, C *orig, memory_order);
218 * void atomic_and_explicit(A *rmw, C arg, C *orig, memory_order);
220 * Atomically applies the given operation, with 'arg' as the second
221 * operand, to '*rmw', and stores the original value of '*rmw' into
222 * '*orig', respecting the given memory order (or memory_order_seq_cst
223 * if none is specified).
225 * The results are similar to those that would be obtained with +=, -=,
226 * |=, ^=, or |= on non-atomic types.
232 * atomic_flag is a typedef for a type with two states, set and clear, that
233 * provides atomic test-and-set functionality.
239 * ATOMIC_FLAG_INIT is an initializer for atomic_flag. The initial state is
242 * An atomic_flag may also be initialized at runtime with atomic_flag_clear().
248 * The following functions are available.
250 * bool atomic_flag_test_and_set(atomic_flag *object)
251 * bool atomic_flag_test_and_set_explicit(atomic_flag *object,
254 * Atomically sets '*object', respsecting the given memory order (or
255 * memory_order_seq_cst for atomic_flag_test_and_set()). Returns the
256 * previous value of the flag (false for clear, true for set).
258 * void atomic_flag_clear(atomic_flag *object);
259 * void atomic_flag_clear_explicit(atomic_flag *object, memory_order);
261 * Atomically clears '*object', respecting the given memory order (or
262 * memory_order_seq_cst for atomic_flag_clear()).
270 #include "compiler.h"
273 #define IN_OVS_ATOMIC_H
275 /* sparse doesn't understand some GCC extensions we use. */
276 #include "ovs-atomic-pthreads.h"
277 #elif HAVE_STDATOMIC_H
278 #include "ovs-atomic-c11.h"
279 #elif __has_extension(c_atomic)
280 #include "ovs-atomic-clang.h"
281 #elif __GNUC__ >= 4 && __GNUC_MINOR__ >= 7
282 #include "ovs-atomic-gcc4.7+.h"
283 #elif HAVE_GCC4_ATOMICS
284 #include "ovs-atomic-gcc4+.h"
286 /* ovs-atomic-pthreads implementation is provided for portability.
287 * It might be too slow for real use because Open vSwitch is
288 * optimized for platforms where real atomic ops are available. */
289 #include "ovs-atomic-pthreads.h"
291 #undef IN_OVS_ATOMIC_H
293 #ifndef OMIT_STANDARD_ATOMIC_TYPES
294 typedef ATOMIC(bool) atomic_bool;
296 typedef ATOMIC(char) atomic_char;
297 typedef ATOMIC(signed char) atomic_schar;
298 typedef ATOMIC(unsigned char) atomic_uchar;
300 typedef ATOMIC(short) atomic_short;
301 typedef ATOMIC(unsigned short) atomic_ushort;
303 typedef ATOMIC(int) atomic_int;
304 typedef ATOMIC(unsigned int) atomic_uint;
306 typedef ATOMIC(long) atomic_long;
307 typedef ATOMIC(unsigned long) atomic_ulong;
309 typedef ATOMIC(long long) atomic_llong;
310 typedef ATOMIC(unsigned long long) atomic_ullong;
312 typedef ATOMIC(size_t) atomic_size_t;
313 typedef ATOMIC(ptrdiff_t) atomic_ptrdiff_t;
315 typedef ATOMIC(intmax_t) atomic_intmax_t;
316 typedef ATOMIC(uintmax_t) atomic_uintmax_t;
318 typedef ATOMIC(intptr_t) atomic_intptr_t;
319 typedef ATOMIC(uintptr_t) atomic_uintptr_t;
320 #endif /* !OMIT_STANDARD_ATOMIC_TYPES */
322 /* Nonstandard atomic types. */
323 typedef ATOMIC(uint8_t) atomic_uint8_t;
324 typedef ATOMIC(uint16_t) atomic_uint16_t;
325 typedef ATOMIC(uint32_t) atomic_uint32_t;
327 typedef ATOMIC(int8_t) atomic_int8_t;
328 typedef ATOMIC(int16_t) atomic_int16_t;
329 typedef ATOMIC(int32_t) atomic_int32_t;
331 /* Reference count. */
332 struct ovs_refcount {
336 /* Initializes 'refcount'. The reference count is initially 1. */
338 ovs_refcount_init(struct ovs_refcount *refcount)
340 atomic_init(&refcount->count, 1);
343 /* Increments 'refcount'.
345 * Does not provide a memory barrier, as the calling thread must have
346 * protected access to the object already. */
348 ovs_refcount_ref(struct ovs_refcount *refcount)
350 unsigned int old_refcount;
352 atomic_add_explicit(&refcount->count, 1, &old_refcount,
353 memory_order_relaxed);
354 ovs_assert(old_refcount > 0);
357 /* Decrements 'refcount' and returns the previous reference count. Often used
360 * if (ovs_refcount_unref(&object->ref_cnt) == 1) {
361 * // ...uninitialize object...
365 * Provides a release barrier making the preceding loads and stores to not be
366 * reordered after the unref. */
367 static inline unsigned int
368 ovs_refcount_unref(struct ovs_refcount *refcount)
370 unsigned int old_refcount;
372 atomic_sub_explicit(&refcount->count, 1, &old_refcount,
373 memory_order_release);
374 ovs_assert(old_refcount > 0);
375 if (old_refcount == 1) {
376 /* 'memory_order_release' above means that there are no (reordered)
377 * accesses to the protected object from any other thread at this
379 * An acquire barrier is needed to keep all subsequent access to the
380 * object's memory from being reordered before the atomic operation
382 atomic_thread_fence(memory_order_acquire);
387 /* Reads and returns 'refcount_''s current reference count.
389 * Does not provide a memory barrier.
392 static inline unsigned int
393 ovs_refcount_read(const struct ovs_refcount *refcount_)
395 struct ovs_refcount *refcount
396 = CONST_CAST(struct ovs_refcount *, refcount_);
399 atomic_read_explicit(&refcount->count, &count, memory_order_relaxed);
403 /* Increments 'refcount', but only if it is non-zero.
405 * This may only be called for an object which is RCU protected during
406 * this call. This implies that its possible destruction is postponed
407 * until all current RCU threads quiesce.
409 * Returns false if the refcount was zero. In this case the object may
410 * be safely accessed until the current thread quiesces, but no additional
411 * references to the object may be taken.
413 * Does not provide a memory barrier, as the calling thread must have
414 * RCU protected access to the object already.
416 * It is critical that we never increment a zero refcount to a
417 * non-zero value, as whenever a refcount reaches the zero value, the
418 * protected object may be irrevocably scheduled for deletion. */
420 ovs_refcount_try_ref_rcu(struct ovs_refcount *refcount)
424 atomic_read_explicit(&refcount->count, &count, memory_order_relaxed);
429 } while (!atomic_compare_exchange_weak_explicit(&refcount->count, &count,
431 memory_order_relaxed,
432 memory_order_relaxed));
436 /* Decrements 'refcount' and returns the previous reference count. To
437 * be used only when a memory barrier is already provided for the
438 * protected object independently.
442 * if (ovs_refcount_unref_relaxed(&object->ref_cnt) == 1) {
443 * // Schedule uninitialization and freeing of the object:
444 * ovsrcu_postpone(destructor_function, object);
447 * Here RCU quiescing already provides a full memory barrier. No additional
448 * barriers are needed here.
452 * if (stp && ovs_refcount_unref_relaxed(&stp->ref_cnt) == 1) {
453 * ovs_mutex_lock(&mutex);
454 * list_remove(&stp->node);
455 * ovs_mutex_unlock(&mutex);
460 * Here a mutex is used to guard access to all of 'stp' apart from
461 * 'ref_cnt'. Hence all changes to 'stp' by other threads must be
462 * visible when we get the mutex, and no access after the unlock can
463 * be reordered to happen prior the lock operation. No additional
464 * barriers are needed here.
466 static inline unsigned int
467 ovs_refcount_unref_relaxed(struct ovs_refcount *refcount)
469 unsigned int old_refcount;
471 atomic_sub_explicit(&refcount->count, 1, &old_refcount,
472 memory_order_relaxed);
473 ovs_assert(old_refcount > 0);
477 #endif /* ovs-atomic.h */