lib/ovs-atomic.h

   1 /*
   2  * Copyright (c) 2013 Nicira, Inc.
   3  *
   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:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 #ifndef OVS_ATOMIC_H
  18 #define OVS_ATOMIC_H 1
  19
  20 /* Atomic operations.
  21  *
  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
  26  * for atomics.
  27  *
  28  * This comment describes the common features of all the implementations.
  29  *
  30  *
  31  * Types
  32  * =====
  33  *
  34  * The following atomic types are supported as typedefs for atomic versions of
  35  * the listed ordinary types:
  36  *
  37  *     ordinary type            atomic version
  38  *     -------------------      ----------------------
  39  *     bool                     atomic_bool
  40  *
  41  *     char                     atomic_char
  42  *     signed char              atomic_schar
  43  *     unsigned char            atomic_uchar
  44  *
  45  *     short                    atomic_short
  46  *     unsigned short           atomic_ushort
  47  *
  48  *     int                      atomic_int
  49  *     unsigned int             atomic_uint
  50  *
  51  *     long                     atomic_long
  52  *     unsigned long            atomic_ulong
  53  *
  54  *     long long                atomic_llong
  55  *     unsigned long long       atomic_ullong
  56  *
  57  *     size_t                   atomic_size_t
  58  *     ptrdiff_t                atomic_ptrdiff_t
  59  *
  60  *     intmax_t                 atomic_intmax_t
  61  *     uintmax_t                atomic_uintmax_t
  62  *
  63  *     intptr_t                 atomic_intptr_t
  64  *     uintptr_t                atomic_uintptr_t
  65  *
  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     (*)
  74  *
  75  *     (*) Not specified by C11.
  76  *
  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.
  80  *
  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.
  85  *
  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
  88  * that.
  89  *
  90  *
  91  * Life Cycle
  92  * ==========
  93  *
  94  * To initialize an atomic variable at its point of definition, use
  95  * ATOMIC_VAR_INIT:
  96  *
  97  *     static atomic_int ai = ATOMIC_VAR_INIT(123);
  98  *
  99  * To initialize an atomic variable in code, use atomic_init():
 100  *
 101  *     static atomic_int ai;
 102  * ...
 103  *     atomic_init(&ai, 123);
 104  *
 105  * C11 does not hav an destruction function for atomic types, but some
 106  * implementations of the OVS atomics do need them.  Thus, the following
 107  * function is provided for destroying non-static atomic objects (A is any
 108  * atomic type):
 109  *
 110  *     void atomic_destroy(A *object);
 111  *
 112  *         Destroys 'object'.
 113  *
 114  *
 115  * Barriers
 116  * ========
 117  *
 118  * enum memory_order specifies the strictness of a memory barrier.  It has the
 119  * following values:
 120  *
 121  *    memory_order_relaxed:
 122  *
 123  *        Compiler barrier only.  Does not imply any CPU memory ordering.
 124  *
 125  *    memory_order_acquire:
 126  *
 127  *        Memory accesses after an acquire barrier cannot be moved before the
 128  *        barrier.  Memory accesses before an acquire barrier *can* be moved
 129  *        after it.
 130  *
 131  *    memory_order_release:
 132  *
 133  *        Memory accesses before a release barrier cannot be moved after the
 134  *        barrier.  Memory accesses after a release barrier *can* be moved
 135  *        before it.
 136  *
 137  *    memory_order_acq_rel:
 138  *
 139  *        Memory accesses cannot be moved across an acquire-release barrier in
 140  *        either direction.
 141  *
 142  *    memory_order_seq_cst:
 143  *
 144  *        Prevents movement of memory accesses like an acquire-release barrier,
 145  *        but whereas acquire-release synchronizes cooperating threads,
 146  *        sequential-consistency synchronizes the whole system.
 147  *
 148  *    memory_order_consume:
 149  *
 150  *        A slight relaxation of memory_order_acquire.
 151  *
 152  * The following functions insert explicit barriers.  Most of the other atomic
 153  * functions also include barriers.
 154  *
 155  *     void atomic_thread_fence(memory_order order);
 156  *
 157  *         Inserts a barrier of the specified type.
 158  *
 159  *         For memory_order_relaxed, this is a no-op.
 160  *
 161  *     void atomic_signal_fence(memory_order order);
 162  *
 163  *         Inserts a barrier of the specified type, but only with respect to
 164  *         signal handlers in the same thread as the barrier.  This is
 165  *         basically a compiler optimization barrier, except for
 166  *         memory_order_relaxed, which is a no-op.
 167  *
 168  *
 169  * Atomic Operations
 170  * =================
 171  *
 172  * In this section, A is an atomic type and C is the corresponding non-atomic
 173  * type.
 174  *
 175  * The "store" primitives match C11:
 176  *
 177  *     void atomic_store(A *object, C value);
 178  *     void atomic_store_explicit(A *object, C value, memory_order);
 179  *
 180  *         Atomically stores 'value' into '*object', respecting the given
 181  *         memory order (or memory_order_seq_cst for atomic_store()).
 182  *
 183  * The following primitives differ from the C11 ones (and have different names)
 184  * because there does not appear to be a way to implement the standard
 185  * primitives in standard C:
 186  *
 187  *     void atomic_read(A *src, C *dst);
 188  *     void atomic_read_explicit(A *src, C *dst, memory_order);
 189  *
 190  *         Atomically loads a value from 'src', writing the value read into
 191  *         '*dst', respecting the given memory order (or memory_order_seq_cst
 192  *         for atomic_read()).
 193  *
 194  *     void atomic_add(A *rmw, C arg, C *orig);
 195  *     void atomic_sub(A *rmw, C arg, C *orig);
 196  *     void atomic_or(A *rmw, C arg, C *orig);
 197  *     void atomic_xor(A *rmw, C arg, C *orig);
 198  *     void atomic_and(A *rmw, C arg, C *orig);
 199  *     void atomic_add_explicit(A *rmw, C arg, C *orig, memory_order);
 200  *     void atomic_sub_explicit(A *rmw, C arg, C *orig, memory_order);
 201  *     void atomic_or_explicit(A *rmw, C arg, C *orig, memory_order);
 202  *     void atomic_xor_explicit(A *rmw, C arg, C *orig, memory_order);
 203  *     void atomic_and_explicit(A *rmw, C arg, C *orig, memory_order);
 204  *
 205  *         Atomically applies the given operation, with 'arg' as the second
 206  *         operand, to '*rmw', and stores the original value of '*rmw' into
 207  *         '*orig', respecting the given memory order (or memory_order_seq_cst
 208  *         if none is specified).
 209  *
 210  *         The results are similar to those that would be obtained with +=, -=,
 211  *         |=, ^=, or |= on non-atomic types.
 212  *
 213  *
 214  * atomic_flag
 215  * ===========
 216  *
 217  * atomic_flag is a typedef for a type with two states, set and clear, that
 218  * provides atomic test-and-set functionality.
 219  *
 220  *
 221  * Life Cycle
 222  * ----------
 223  *
 224  * ATOMIC_FLAG_INIT is an initializer for atomic_flag.  The initial state is
 225  * "clear".
 226  *
 227  * C11 does not have an initialization or destruction function for atomic_flag,
 228  * because implementations should not need one (one may simply
 229  * atomic_flag_clear() an uninitialized atomic_flag), but some implementations
 230  * of the OVS atomics do need them.  Thus, the following two functions are
 231  * provided for initializing and destroying non-static atomic_flags:
 232  *
 233  *     void atomic_flag_init(volatile atomic_flag *object);
 234  *
 235  *         Initializes 'object'.  The initial state is "clear".
 236  *
 237  *     void atomic_flag_destroy(volatile atomic_flag *object);
 238  *
 239  *         Destroys 'object'.
 240  *
 241  *
 242  * Operations
 243  * ----------
 244  *
 245  * The following functions are available.
 246  *
 247  *     bool atomic_flag_test_and_set(atomic_flag *object)
 248  *     bool atomic_flag_test_and_set_explicit(atomic_flag *object,
 249  *                                            memory_order);
 250  *
 251  *         Atomically sets '*object', respsecting the given memory order (or
 252  *         memory_order_seq_cst for atomic_flag_test_and_set()).  Returns the
 253  *         previous value of the flag (false for clear, true for set).
 254  *
 255  *     void atomic_flag_clear(atomic_flag *object);
 256  *     void atomic_flag_clear_explicit(atomic_flag *object, memory_order);
 257  *
 258  *         Atomically clears '*object', respecting the given memory order (or
 259  *         memory_order_seq_cst for atomic_flag_clear()).
 260  */
 261
 262 #include <limits.h>
 263 #include <pthread.h>
 264 #include <stdbool.h>
 265 #include <stddef.h>
 266 #include <stdint.h>
 267 #include "compiler.h"
 268 #include "util.h"
 269
 270 #define IN_OVS_ATOMIC_H
 271     #if __CHECKER__
 272         /* sparse doesn't understand some GCC extensions we use. */
 273         #include "ovs-atomic-pthreads.h"
 274     #elif HAVE_STDATOMIC_H
 275         #include "ovs-atomic-c11.h"
 276     #elif __has_extension(c_atomic)
 277         #include "ovs-atomic-clang.h"
 278     #elif __GNUC__ >= 4 && __GNUC_MINOR__ >= 7
 279         #include "ovs-atomic-gcc4.7+.h"
 280     #elif HAVE_GCC4_ATOMICS
 281         #include "ovs-atomic-gcc4+.h"
 282     #else
 283         #include "ovs-atomic-pthreads.h"
 284     #endif
 285 #undef IN_OVS_ATOMIC_H
 286
 287 /* Reference count. */
 288 struct ovs_refcount {
 289     atomic_uint count;
 290 };
 291
 292 /* Initializes 'refcount'.  The reference count is initially 1. */
 293 static inline void
 294 ovs_refcount_init(struct ovs_refcount *refcount)
 295 {
 296     atomic_init(&refcount->count, 1);
 297 }
 298
 299 /* Destroys 'refcount'. */
 300 static inline void
 301 ovs_refcount_destroy(struct ovs_refcount *refcount)
 302 {
 303     atomic_destroy(&refcount->count);
 304 }
 305
 306 /* Increments 'refcount'. */
 307 static inline void
 308 ovs_refcount_ref(struct ovs_refcount *refcount)
 309 {
 310     unsigned int old_refcount;
 311
 312     atomic_add(&refcount->count, 1, &old_refcount);
 313     ovs_assert(old_refcount > 0);
 314 }
 315
 316 /* Decrements 'refcount' and returns the previous reference count.  Often used
 317  * in this form:
 318  *
 319  * if (ovs_refcount_unref(&object->ref_cnt) == 1) {
 320  *     // ...uninitialize object...
 321  *     free(object);
 322  * }
 323  */
 324 static inline unsigned int
 325 ovs_refcount_unref(struct ovs_refcount *refcount)
 326 {
 327     unsigned int old_refcount;
 328
 329     atomic_sub(&refcount->count, 1, &old_refcount);
 330     ovs_assert(old_refcount > 0);
 331     return old_refcount;
 332 }
 333
 334 /* Reads and returns 'ref_count_''s current reference count.
 335  *
 336  * Rarely useful. */
 337 static inline unsigned int
 338 ovs_refcount_read(const struct ovs_refcount *refcount_)
 339 {
 340     struct ovs_refcount *refcount
 341         = CONST_CAST(struct ovs_refcount *, refcount_);
 342     unsigned int count;
 343
 344     atomic_read(&refcount->count, &count);
 345     return count;
 346 }
 347
 348 #endif /* ovs-atomic.h */