]>
git.proxmox.com Git - ovs.git/blob - lib/ovs-atomic.h
2 * Copyright (c) 2013, 2014, 2017 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 (*)
72 * uint64_t atomic_uint64_t (*)
73 * int64_t atomic_int64_t (*)
75 * (*) Not specified by C11.
77 * Atomic types may also be obtained via ATOMIC(TYPE), e.g. ATOMIC(void *).
78 * Only basic integer types and pointer types can be made atomic this way,
79 * e.g. atomic structs are not supported.
81 * The atomic version of a type doesn't necessarily have the same size or
82 * representation as the ordinary version; for example, atomic_int might be a
83 * typedef for a struct. The range of an atomic type does match the range of
84 * the corresponding ordinary type.
86 * C11 says that one may use the _Atomic keyword in place of the typedef name,
87 * e.g. "_Atomic int" instead of "atomic_int". This library doesn't support
94 * To initialize an atomic variable at its point of definition, use
97 * static atomic_int ai = ATOMIC_VAR_INIT(123);
99 * To initialize an atomic variable in code, use atomic_init():
101 * static atomic_int ai;
103 * atomic_init(&ai, 123);
109 * enum memory_order specifies the strictness of a memory barrier. It has the
112 * memory_order_relaxed:
114 * Only atomicity is provided, does not imply any memory ordering with
115 * respect to any other variable (atomic or not). Relaxed accesses to
116 * the same atomic variable will be performed in the program order.
117 * The compiler and CPU are free to move memory accesses to other
118 * variables past the atomic operation.
120 * memory_order_consume:
122 * Memory accesses with data dependency on the result of the consume
123 * operation (atomic_read_explicit, or a load operation preceding a
124 * atomic_thread_fence) will not be moved prior to the consume
125 * barrier. Non-data-dependent loads and stores can be reordered to
126 * happen before the consume barrier.
128 * RCU is the prime example of the use of the consume barrier: The
129 * consume barrier guarantees that reads from a RCU protected object
130 * are performed after the RCU protected pointer is read. A
131 * corresponding release barrier is used to store the modified RCU
132 * protected pointer after the RCU protected object has been fully
133 * constructed. The synchronization between these barriers prevents
134 * the RCU "consumer" from seeing uninitialized data.
136 * May not be used with atomic_store_explicit(), as consume semantics
137 * applies only to atomic loads.
139 * memory_order_acquire:
141 * Memory accesses after an acquire barrier cannot be moved before the
142 * barrier. Memory accesses before an acquire barrier *can* be moved
145 * An atomic_thread_fence with memory_order_acquire does not have a
146 * load operation by itself; it prevents all following memory accesses
147 * from moving prior to preceding loads.
149 * May not be used with atomic_store_explicit(), as acquire semantics
150 * applies only to atomic loads.
152 * memory_order_release:
154 * Memory accesses before a release barrier cannot be moved after the
155 * barrier. Memory accesses after a release barrier *can* be moved
158 * An atomic_thread_fence with memory_order_release does not have a
159 * store operation by itself; it prevents all preceding memory accesses
160 * from moving past subsequent stores.
162 * May not be used with atomic_read_explicit(), as release semantics
163 * applies only to atomic stores.
165 * memory_order_acq_rel:
167 * Memory accesses cannot be moved across an acquire-release barrier in
170 * May only be used with atomic read-modify-write operations, as both
171 * load and store operation is required for acquire-release semantics.
173 * An atomic_thread_fence with memory_order_acq_rel does not have
174 * either load or store operation by itself; it prevents all following
175 * memory accesses from moving prior to preceding loads and all
176 * preceding memory accesses from moving past subsequent stores.
178 * memory_order_seq_cst:
180 * Prevents movement of memory accesses like an acquire-release barrier,
181 * but whereas acquire-release synchronizes cooperating threads (using
182 * the same atomic variable), sequential-consistency synchronizes the
183 * whole system, providing a total order for stores on all atomic
186 * OVS atomics require the memory_order to be passed as a compile-time constant
187 * value, as some compiler implementations may perform poorly if the memory
188 * order parameter is passed in as a run-time value.
190 * The following functions insert explicit barriers. Most of the other atomic
191 * functions also include barriers.
193 * void atomic_thread_fence(memory_order order);
195 * Inserts a barrier of the specified type.
197 * For memory_order_relaxed, this is a no-op.
199 * void atomic_signal_fence(memory_order order);
201 * Inserts a barrier of the specified type, but only with respect to
202 * signal handlers in the same thread as the barrier. This is
203 * basically a compiler optimization barrier, except for
204 * memory_order_relaxed, which is a no-op.
210 * In this section, A is an atomic type and C is the corresponding non-atomic
213 * The "store" and "compare_exchange" primitives match C11:
215 * void atomic_store(A *object, C value);
216 * void atomic_store_explicit(A *object, C value, memory_order);
218 * Atomically stores 'value' into '*object', respecting the given
219 * memory order (or memory_order_seq_cst for atomic_store()).
221 * bool atomic_compare_exchange_strong(A *object, C *expected, C desired);
222 * bool atomic_compare_exchange_weak(A *object, C *expected, C desired);
223 * bool atomic_compare_exchange_strong_explicit(A *object, C *expected,
225 * memory_order success,
226 * memory_order failure);
227 * bool atomic_compare_exchange_weak_explicit(A *object, C *expected,
229 * memory_order success,
230 * memory_order failure);
232 * Atomically loads '*object' and compares it with '*expected' and if
233 * equal, stores 'desired' into '*object' (an atomic read-modify-write
234 * operation) and returns true, and if non-equal, stores the actual
235 * value of '*object' into '*expected' (an atomic load operation) and
236 * returns false. The memory order for the successful case (atomic
237 * read-modify-write operation) is 'success', and for the unsuccessful
238 * case (atomic load operation) 'failure'. 'failure' may not be
239 * stronger than 'success'.
241 * The weak forms may fail (returning false) also when '*object' equals
242 * '*expected'. The strong form can be implemented by the weak form in
243 * a loop. Some platforms can implement the weak form more
244 * efficiently, so it should be used if the application will need to
247 * The following primitives differ from the C11 ones (and have different names)
248 * because there does not appear to be a way to implement the standard
249 * primitives in standard C:
251 * void atomic_read(A *src, C *dst);
252 * void atomic_read_explicit(A *src, C *dst, memory_order);
254 * Atomically loads a value from 'src', writing the value read into
255 * '*dst', respecting the given memory order (or memory_order_seq_cst
256 * for atomic_read()).
258 * void atomic_add(A *rmw, C arg, C *orig);
259 * void atomic_sub(A *rmw, C arg, C *orig);
260 * void atomic_or(A *rmw, C arg, C *orig);
261 * void atomic_xor(A *rmw, C arg, C *orig);
262 * void atomic_and(A *rmw, C arg, C *orig);
263 * void atomic_add_explicit(A *rmw, C arg, C *orig, memory_order);
264 * void atomic_sub_explicit(A *rmw, C arg, C *orig, memory_order);
265 * void atomic_or_explicit(A *rmw, C arg, C *orig, memory_order);
266 * void atomic_xor_explicit(A *rmw, C arg, C *orig, memory_order);
267 * void atomic_and_explicit(A *rmw, C arg, C *orig, memory_order);
269 * Atomically applies the given operation, with 'arg' as the second
270 * operand, to '*rmw', and stores the original value of '*rmw' into
271 * '*orig', respecting the given memory order (or memory_order_seq_cst
272 * if none is specified).
274 * The results are similar to those that would be obtained with +=, -=,
275 * |=, ^=, or |= on non-atomic types.
281 * atomic_flag is a typedef for a type with two states, set and clear, that
282 * provides atomic test-and-set functionality.
288 * ATOMIC_FLAG_INIT is an initializer for atomic_flag. The initial state is
291 * An atomic_flag may also be initialized at runtime with atomic_flag_clear().
297 * The following functions are available.
299 * bool atomic_flag_test_and_set(atomic_flag *object)
300 * bool atomic_flag_test_and_set_explicit(atomic_flag *object,
303 * Atomically sets '*object', respecting the given memory order (or
304 * memory_order_seq_cst for atomic_flag_test_and_set()). Returns the
305 * previous value of the flag (false for clear, true for set).
307 * void atomic_flag_clear(atomic_flag *object);
308 * void atomic_flag_clear_explicit(atomic_flag *object, memory_order);
310 * Atomically clears '*object', respecting the given memory order (or
311 * memory_order_seq_cst for atomic_flag_clear()).
319 #include "compiler.h"
322 #define IN_OVS_ATOMIC_H
324 /* sparse doesn't understand some GCC extensions we use. */
325 #include "ovs-atomic-pthreads.h"
326 #elif __has_extension(c_atomic)
327 #include "ovs-atomic-clang.h"
328 #elif HAVE_ATOMIC && __cplusplus >= 201103L
329 #include "ovs-atomic-c++.h"
330 #elif HAVE_STDATOMIC_H && !defined(__cplusplus)
331 #include "ovs-atomic-c11.h"
332 #elif __GNUC__ >= 5 && !defined(__cplusplus)
333 #error "GCC 5+ should have <stdatomic.h>"
334 #elif __GNUC__ >= 5 || (__GNUC__ >= 4 && __GNUC_MINOR__ >= 7)
335 #include "ovs-atomic-gcc4.7+.h"
336 #elif __GNUC__ && defined(__x86_64__)
337 #include "ovs-atomic-x86_64.h"
338 #elif __GNUC__ && defined(__i386__)
339 #include "ovs-atomic-i586.h"
340 #elif HAVE_GCC4_ATOMICS
341 #include "ovs-atomic-gcc4+.h"
343 #include "ovs-atomic-msvc.h"
345 /* ovs-atomic-pthreads implementation is provided for portability.
346 * It might be too slow for real use because Open vSwitch is
347 * optimized for platforms where real atomic ops are available. */
348 #include "ovs-atomic-pthreads.h"
350 #undef IN_OVS_ATOMIC_H
352 #ifndef OMIT_STANDARD_ATOMIC_TYPES
353 typedef ATOMIC(bool) atomic_bool
;
355 typedef ATOMIC(char) atomic_char
;
356 typedef ATOMIC(signed char) atomic_schar
;
357 typedef ATOMIC(unsigned char) atomic_uchar
;
359 typedef ATOMIC(short) atomic_short
;
360 typedef ATOMIC(unsigned short) atomic_ushort
;
362 typedef ATOMIC(int) atomic_int
;
363 typedef ATOMIC(unsigned int) atomic_uint
;
365 typedef ATOMIC(long) atomic_long
;
366 typedef ATOMIC(unsigned long) atomic_ulong
;
368 typedef ATOMIC(long long) atomic_llong
;
369 typedef ATOMIC(unsigned long long) atomic_ullong
;
371 typedef ATOMIC(size_t) atomic_size_t
;
372 typedef ATOMIC(ptrdiff_t) atomic_ptrdiff_t
;
374 typedef ATOMIC(intmax_t) atomic_intmax_t
;
375 typedef ATOMIC(uintmax_t) atomic_uintmax_t
;
377 typedef ATOMIC(intptr_t) atomic_intptr_t
;
378 typedef ATOMIC(uintptr_t) atomic_uintptr_t
;
379 #endif /* !OMIT_STANDARD_ATOMIC_TYPES */
381 /* Nonstandard atomic types. */
382 typedef ATOMIC(uint8_t) atomic_uint8_t
;
383 typedef ATOMIC(uint16_t) atomic_uint16_t
;
384 typedef ATOMIC(uint32_t) atomic_uint32_t
;
385 typedef ATOMIC(uint64_t) atomic_uint64_t
;
387 typedef ATOMIC(int8_t) atomic_int8_t
;
388 typedef ATOMIC(int16_t) atomic_int16_t
;
389 typedef ATOMIC(int32_t) atomic_int32_t
;
390 typedef ATOMIC(int64_t) atomic_int64_t
;
392 /* Relaxed atomic operations.
394 * When an operation on an atomic variable is not expected to synchronize
395 * with operations on other (atomic or non-atomic) variables, no memory
396 * barriers are needed and the relaxed memory ordering can be used. These
397 * macros make such uses less daunting, but not invisible. */
398 #define atomic_store_relaxed(VAR, VALUE) \
399 atomic_store_explicit(VAR, VALUE, memory_order_relaxed)
400 #define atomic_read_relaxed(VAR, DST) \
401 atomic_read_explicit(VAR, DST, memory_order_relaxed)
402 #define atomic_compare_exchange_strong_relaxed(DST, EXP, SRC) \
403 atomic_compare_exchange_strong_explicit(DST, EXP, SRC, \
404 memory_order_relaxed, \
405 memory_order_relaxed)
406 #define atomic_compare_exchange_weak_relaxed(DST, EXP, SRC) \
407 atomic_compare_exchange_weak_explicit(DST, EXP, SRC, \
408 memory_order_relaxed, \
409 memory_order_relaxed)
410 #define atomic_add_relaxed(RMW, ARG, ORIG) \
411 atomic_add_explicit(RMW, ARG, ORIG, memory_order_relaxed)
412 #define atomic_sub_relaxed(RMW, ARG, ORIG) \
413 atomic_sub_explicit(RMW, ARG, ORIG, memory_order_relaxed)
414 #define atomic_or_relaxed(RMW, ARG, ORIG) \
415 atomic_or_explicit(RMW, ARG, ORIG, memory_order_relaxed)
416 #define atomic_xor_relaxed(RMW, ARG, ORIG) \
417 atomic_xor_explicit(RMW, ARG, ORIG, memory_order_relaxed)
418 #define atomic_and_relaxed(RMW, ARG, ORIG) \
419 atomic_and_explicit(RMW, ARG, ORIG, memory_order_relaxed)
420 #define atomic_flag_test_and_set_relaxed(FLAG) \
421 atomic_flag_test_and_set_explicit(FLAG, memory_order_relaxed)
422 #define atomic_flag_clear_relaxed(FLAG) \
423 atomic_flag_clear_explicit(FLAG, memory_order_relaxed)
425 /* A simplified atomic count. Does not provide any synchronization with any
428 * Typically a counter is not used to synchronize the state of any other
429 * variables (with the notable exception of reference count, below).
430 * This abstraction releaves the user from the memory order considerations,
431 * and may make the code easier to read.
433 * We only support the unsigned int counters, as those are the most common. */
434 typedef struct atomic_count
{
438 #define ATOMIC_COUNT_INIT(VALUE) { VALUE }
441 atomic_count_init(atomic_count
*count
, unsigned int value
)
443 atomic_init(&count
->count
, value
);
446 static inline unsigned int
447 atomic_count_inc(atomic_count
*count
)
451 atomic_add_relaxed(&count
->count
, 1u, &old
);
456 static inline unsigned int
457 atomic_count_dec(atomic_count
*count
)
461 atomic_sub_relaxed(&count
->count
, 1u, &old
);
466 static inline unsigned int
467 atomic_count_get(atomic_count
*count
)
471 atomic_read_relaxed(&count
->count
, &value
);
477 atomic_count_set(atomic_count
*count
, unsigned int value
)
479 atomic_store_relaxed(&count
->count
, value
);
482 /* Reference count. */
483 struct ovs_refcount
{
487 /* Initializes 'refcount'. The reference count is initially 1. */
489 ovs_refcount_init(struct ovs_refcount
*refcount
)
491 atomic_init(&refcount
->count
, 1u);
494 /* Increments 'refcount'.
496 * Does not provide a memory barrier, as the calling thread must have
497 * protected access to the object already. */
499 ovs_refcount_ref(struct ovs_refcount
*refcount
)
501 unsigned int old_refcount
;
503 atomic_add_explicit(&refcount
->count
, 1u, &old_refcount
,
504 memory_order_relaxed
);
505 ovs_assert(old_refcount
> 0);
508 /* Decrements 'refcount' and returns the previous reference count. Often used
511 * if (ovs_refcount_unref(&object->ref_cnt) == 1) {
512 * // ...uninitialize object...
516 * Provides a release barrier making the preceding loads and stores to not be
517 * reordered after the unref, and in case of the last reference provides also
518 * an acquire barrier to keep all the following uninitialization from being
519 * reordered before the atomic decrement operation. Together these synchronize
520 * any concurrent unref operations between each other. */
521 static inline unsigned int
522 ovs_refcount_unref(struct ovs_refcount
*refcount
)
524 unsigned int old_refcount
;
526 atomic_sub_explicit(&refcount
->count
, 1u, &old_refcount
,
527 memory_order_release
);
528 ovs_assert(old_refcount
> 0);
529 if (old_refcount
== 1) {
530 /* 'memory_order_release' above means that there are no (reordered)
531 * accesses to the protected object from any thread at this point.
532 * An acquire barrier is needed to keep all subsequent access to the
533 * object's memory from being reordered before the atomic operation
535 atomic_thread_fence(memory_order_acquire
);
540 /* Reads and returns 'refcount_''s current reference count.
542 * Does not provide a memory barrier.
545 static inline unsigned int
546 ovs_refcount_read(const struct ovs_refcount
*refcount_
)
548 struct ovs_refcount
*refcount
549 = CONST_CAST(struct ovs_refcount
*, refcount_
);
552 atomic_read_explicit(&refcount
->count
, &count
, memory_order_relaxed
);
556 /* Increments 'refcount', but only if it is non-zero.
558 * This may only be called for an object which is RCU protected during
559 * this call. This implies that its possible destruction is postponed
560 * until all current RCU threads quiesce.
562 * Returns false if the refcount was zero. In this case the object may
563 * be safely accessed until the current thread quiesces, but no additional
564 * references to the object may be taken.
566 * Does not provide a memory barrier, as the calling thread must have
567 * RCU protected access to the object already.
569 * It is critical that we never increment a zero refcount to a
570 * non-zero value, as whenever a refcount reaches the zero value, the
571 * protected object may be irrevocably scheduled for deletion. */
573 ovs_refcount_try_ref_rcu(struct ovs_refcount
*refcount
)
577 atomic_read_explicit(&refcount
->count
, &count
, memory_order_relaxed
);
582 } while (!atomic_compare_exchange_weak_explicit(&refcount
->count
, &count
,
584 memory_order_relaxed
,
585 memory_order_relaxed
));
589 /* Decrements 'refcount' and returns the previous reference count. To
590 * be used only when a memory barrier is already provided for the
591 * protected object independently.
595 * if (ovs_refcount_unref_relaxed(&object->ref_cnt) == 1) {
596 * // Schedule uninitialization and freeing of the object:
597 * ovsrcu_postpone(destructor_function, object);
600 * Here RCU quiescing already provides a full memory barrier. No additional
601 * barriers are needed here.
605 * if (stp && ovs_refcount_unref_relaxed(&stp->ref_cnt) == 1) {
606 * ovs_mutex_lock(&mutex);
607 * ovs_list_remove(&stp->node);
608 * ovs_mutex_unlock(&mutex);
613 * Here a mutex is used to guard access to all of 'stp' apart from
614 * 'ref_cnt'. Hence all changes to 'stp' by other threads must be
615 * visible when we get the mutex, and no access after the unlock can
616 * be reordered to happen prior the lock operation. No additional
617 * barriers are needed here.
619 static inline unsigned int
620 ovs_refcount_unref_relaxed(struct ovs_refcount
*refcount
)
622 unsigned int old_refcount
;
624 atomic_sub_explicit(&refcount
->count
, 1u, &old_refcount
,
625 memory_order_relaxed
);
626 ovs_assert(old_refcount
> 0);
630 #endif /* ovs-atomic.h */