gc-7.2/libatomic_ops/src/atomic_ops_stack.h

   1 /*
   2  * The implementation of the routines described here is covered by the GPL.
   3  * This header file is covered by the following license:
   4  */
   5
   6 /*
   7  * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
   8  *
   9  * Permission is hereby granted, free of charge, to any person obtaining a copy
  10  * of this software and associated documentation files (the "Software"), to deal
  11  * in the Software without restriction, including without limitation the rights
  12  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  13  * copies of the Software, and to permit persons to whom the Software is
  14  * furnished to do so, subject to the following conditions:
  15  *
  16  * The above copyright notice and this permission notice shall be included in
  17  * all copies or substantial portions of the Software.
  18  *
  19  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  22  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  23  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  24  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  25  * SOFTWARE.
  26  */
  27
  28 /* Almost lock-free LIFO linked lists (linked stacks).  */
  29 #ifndef AO_STACK_H
  30 #define AO_STACK_H
  31
  32 #include "atomic_ops.h"
  33
  34 #if !defined(AO_HAVE_compare_double_and_swap_double) \
  35     && !defined(AO_HAVE_compare_double_and_swap) \
  36     && defined(AO_HAVE_compare_and_swap)
  37 # define AO_USE_ALMOST_LOCK_FREE
  38 #else
  39   /* If we have no compare-and-swap operation defined, we assume        */
  40   /* that we will actually be using CAS emulation.  If we do that,      */
  41   /* it's cheaper to use the version-based implementation.              */
  42 # define AO_STACK_IS_LOCK_FREE
  43 #endif
  44
  45 /*
  46  * These are not guaranteed to be completely lock-free.
  47  * List insertion may spin under extremely unlikely conditions.
  48  * It cannot deadlock due to recursive reentry unless AO_list_remove
  49  * is called while at least AO_BL_SIZE activations of
  50  * AO_list_remove are currently active in the same thread, i.e.
  51  * we must have at least AO_BL_SIZE recursive signal handler
  52  * invocations.
  53  *
  54  * All operations take an AO_list_aux argument.  It is safe to
  55  * share a single AO_list_aux structure among all lists, but that
  56  * may increase contention.  Any given list must always be accessed
  57  * with the same AO_list_aux structure.
  58  *
  59  * We make some machine-dependent assumptions:
  60  *   - We have a compare-and-swap operation.
  61  *   - At least _AO_N_BITS low order bits in pointers are
  62  *     zero and normally unused.
  63  *   - size_t and pointers have the same size.
  64  *
  65  * We do use a fully lock-free implementation if double-width
  66  * compare-and-swap operations are available.
  67  */
  68
  69 #ifdef AO_USE_ALMOST_LOCK_FREE
  70 /* The number of low order pointer bits we can use for a small  */
  71 /* version number.                                              */
  72 # if defined(__LP64__) || defined(_LP64) || defined(_WIN64)
  73    /* WIN64 isn't really supported yet. */
  74 #  define AO_N_BITS 3
  75 # else
  76 #  define AO_N_BITS 2
  77 # endif
  78
  79 # define AO_BIT_MASK ((1 << AO_N_BITS) - 1)
  80 /*
  81  * AO_stack_aux should be treated as opaque.
  82  * It is fully defined here, so it can be allocated, and to facilitate
  83  * debugging.
  84  */
  85 #ifndef AO_BL_SIZE
  86 #  define AO_BL_SIZE 2
  87 #endif
  88
  89 #if AO_BL_SIZE > (1 << AO_N_BITS)
  90 #  error AO_BL_SIZE too big
  91 #endif
  92
  93 typedef struct AO__stack_aux {
  94   volatile AO_t AO_stack_bl[AO_BL_SIZE];
  95 } AO_stack_aux;
  96
  97 /* The stack implementation knows only about the location of    */
  98 /* link fields in nodes, and nothing about the rest of the      */
  99 /* stack elements.  Link fields hold an AO_t, which is not      */
 100 /* necessarily a real pointer.  This converts the AO_t to a     */
 101 /* real (AO_t *) which is either o, or points at the link       */
 102 /* field in the next node.                                      */
 103 #define AO_REAL_NEXT_PTR(x) (AO_t *)((x) & ~AO_BIT_MASK)
 104
 105 /* The following two routines should not normally be used directly.     */
 106 /* We make them visible here for the rare cases in which it makes sense */
 107 /* to share the an AO_stack_aux between stacks.                         */
 108 void
 109 AO_stack_push_explicit_aux_release(volatile AO_t *list, AO_t *x,
 110                                   AO_stack_aux *);
 111
 112 AO_t *
 113 AO_stack_pop_explicit_aux_acquire(volatile AO_t *list, AO_stack_aux *);
 114
 115 /* And now AO_stack_t for the real interface:                           */
 116
 117 typedef struct AO__stack {
 118   volatile AO_t AO_ptr;
 119   AO_stack_aux AO_aux;
 120 } AO_stack_t;
 121
 122 #define AO_STACK_INITIALIZER {0}
 123
 124 AO_INLINE void AO_stack_init(AO_stack_t *list)
 125 {
 126 # if AO_BL_SIZE == 2
 127     list -> AO_aux.AO_stack_bl[0] = 0;
 128     list -> AO_aux.AO_stack_bl[1] = 0;
 129 # else
 130     int i;
 131     for (i = 0; i < AO_BL_SIZE; ++i)
 132       list -> AO_aux.AO_stack_bl[i] = 0;
 133 # endif
 134   list -> AO_ptr = 0;
 135 }
 136
 137 /* Convert an AO_stack_t to a pointer to the link field in      */
 138 /* the first element.                                           */
 139 #define AO_REAL_HEAD_PTR(x) AO_REAL_NEXT_PTR((x).AO_ptr)
 140
 141 #define AO_stack_push_release(l, e) \
 142         AO_stack_push_explicit_aux_release(&((l)->AO_ptr), e, &((l)->AO_aux))
 143 #define AO_HAVE_stack_push_release
 144
 145 #define AO_stack_pop_acquire(l) \
 146         AO_stack_pop_explicit_aux_acquire(&((l)->AO_ptr), &((l)->AO_aux))
 147 #define AO_HAVE_stack_pop_acquire
 148
 149 # else /* Use fully non-blocking data structure, wide CAS       */
 150
 151 #ifndef AO_HAVE_double_t
 152   /* Can happen if we're using CAS emulation, since we don't want to    */
 153   /* force that here, in case other atomic_ops clients don't want it.   */
 154 # include "atomic_ops/sysdeps/standard_ao_double_t.h"
 155 #endif
 156
 157 typedef volatile AO_double_t AO_stack_t;
 158 /* AO_val1 is version, AO_val2 is pointer.      */
 159
 160 #define AO_STACK_INITIALIZER {0}
 161
 162 AO_INLINE void AO_stack_init(AO_stack_t *list)
 163 {
 164   list -> AO_val1 = 0;
 165   list -> AO_val2 = 0;
 166 }
 167
 168 #define AO_REAL_HEAD_PTR(x) (AO_t *)((x).AO_val2)
 169 #define AO_REAL_NEXT_PTR(x) (AO_t *)(x)
 170
 171 void AO_stack_push_release(AO_stack_t *list, AO_t *new_element);
 172 #define AO_HAVE_stack_push_release
 173 AO_t * AO_stack_pop_acquire(AO_stack_t *list);
 174 #define AO_HAVE_stack_pop_acquire
 175
 176 #endif /* Wide CAS case */
 177
 178 #if defined(AO_HAVE_stack_push_release) && !defined(AO_HAVE_stack_push)
 179 # define AO_stack_push(l, e) AO_stack_push_release(l, e)
 180 # define AO_HAVE_stack_push
 181 #endif
 182
 183 #if defined(AO_HAVE_stack_pop_acquire) && !defined(AO_HAVE_stack_pop)
 184 # define AO_stack_pop(l) AO_stack_pop_acquire(l)
 185 # define AO_HAVE_stack_pop
 186 #endif
 187
 188 #endif /* !AO_STACK_H */