gc-7.2/libatomic_ops/src/atomic_ops_stack.c

   1 /*
   2  * Copyright (c) 2005 Hewlett-Packard Development Company, L.P.
   3  * Original Author: Hans Boehm
   4  *
   5  * This file may be redistributed and/or modified under the
   6  * terms of the GNU General Public License as published by the Free Software
   7  * Foundation; either version 2, or (at your option) any later version.
   8  *
   9  * It is distributed in the hope that it will be useful, but WITHOUT ANY
  10  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  11  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License in the
  12  * file doc/COPYING for more details.
  13  */
  14
  15 #if defined(HAVE_CONFIG_H)
  16 # include "config.h"
  17 #endif
  18
  19 #include <string.h>
  20 #include <stdlib.h>
  21 #include <assert.h>
  22 #define AO_REQUIRE_CAS
  23 #include "atomic_ops_stack.h"
  24
  25 #if defined(_MSC_VER) \
  26     || defined(_WIN32) && !defined(__CYGWIN32__) && !defined(__CYGWIN__)
  27   /* AO_pause not defined elsewhere */
  28   /* FIXME: At least AO_spin should be factored out.    */
  29 #include <windows.h>
  30
  31 AO_t dummy;
  32
  33 /* Spin for 2**n units. */
  34 static void AO_spin(int n)
  35 {
  36   int i;
  37   AO_T j = AO_load(&dummy);
  38
  39   for (i = 0; i < (2 << n); ++i)
  40     {
  41        j *= 5;
  42        j -= 4;
  43     }
  44   AO_store(&dummy, j);
  45 }
  46
  47 void AO_pause(int n)
  48 {
  49     if (n < 12)
  50       AO_spin(n);
  51     else
  52       {
  53         DWORD msecs;
  54
  55         /* Short async-signal-safe sleep. */
  56         msecs = (n > 18? 100 : (1 << (n - 12)));
  57         Sleep(msecs);
  58       }
  59 }
  60
  61 #else
  62
  63 /* AO_pause is available elsewhere */
  64
  65 extern void AO_pause(int);
  66
  67 #endif
  68
  69 #ifdef AO_USE_ALMOST_LOCK_FREE
  70
  71 /* LIFO linked lists based on compare-and-swap.  We need to avoid       */
  72 /* the case of a node deletion and reinsertion while I'm deleting       */
  73 /* it, since that may cause my CAS to succeed eventhough the next       */
  74 /* pointer is now wrong.  Our solution is not fully lock-free, but it   */
  75 /* is good enough for signal handlers, provided we have a suitably low  */
  76 /* bound on the number of recursive signal handler reentries.           */
  77 /* A list consists of a first pointer and a blacklist                   */
  78 /* of pointer values that are currently being removed.  No list element */
  79 /* on the blacklist may be inserted.  If we would otherwise do so, we   */
  80 /* are allowed to insert a variant that differs only in the least       */
  81 /* significant, ignored, bits.  If the list is full, we wait.           */
  82
  83 /* Crucial observation: A particular padded pointer x (i.e. pointer     */
  84 /* plus arbitrary low order bits) can never be newly inserted into      */
  85 /* a list while it's in the corresponding auxiliary data structure.     */
  86
  87 /* The second argument is a pointer to the link field of the element    */
  88 /* to be inserted.                                                      */
  89 /* Both list headers and link fields contain "perturbed" pointers, i.e. */
  90 /* pointers with extra bits "or"ed into the low order bits.             */
  91 void
  92 AO_stack_push_explicit_aux_release(volatile AO_t *list, AO_t *x,
  93                                    AO_stack_aux *a)
  94 {
  95   AO_t x_bits = (AO_t)x;
  96   AO_t next;
  97
  98   /* No deletions of x can start here, since x is not currently in the  */
  99   /* list.                                                              */
 100  retry:
 101 # if AO_BL_SIZE == 2
 102   {
 103     /* Start all loads as close to concurrently as possible. */
 104     AO_t entry1 = AO_load(a -> AO_stack_bl);
 105     AO_t entry2 = AO_load(a -> AO_stack_bl + 1);
 106     if (entry1 == x_bits || entry2 == x_bits)
 107       {
 108         /* Entry is currently being removed.  Change it a little.       */
 109           ++x_bits;
 110           if ((x_bits & AO_BIT_MASK) == 0)
 111             /* Version count overflowed;         */
 112             /* EXTREMELY unlikely, but possible. */
 113             x_bits = (AO_t)x;
 114         goto retry;
 115       }
 116   }
 117 # else
 118   {
 119     int i;
 120     for (i = 0; i < AO_BL_SIZE; ++i)
 121       {
 122         if (AO_load(a -> AO_stack_bl + i) == x_bits)
 123           {
 124             /* Entry is currently being removed.  Change it a little.   */
 125               ++x_bits;
 126               if ((x_bits & AO_BIT_MASK) == 0)
 127                 /* Version count overflowed;         */
 128                 /* EXTREMELY unlikely, but possible. */
 129                 x_bits = (AO_t)x;
 130             goto retry;
 131           }
 132       }
 133   }
 134 # endif
 135   /* x_bits is not currently being deleted */
 136   do
 137     {
 138       next = AO_load(list);
 139       *x = next;
 140     }
 141   while(!AO_compare_and_swap_release(list, next, x_bits));
 142 }
 143
 144 /*
 145  * I concluded experimentally that checking a value first before
 146  * performing a compare-and-swap is usually beneficial on X86, but
 147  * slows things down appreciably with contention on Itanium.
 148  * Since the Itanium behavior makes more sense to me (more cache line
 149  * movement unless we're mostly reading, but back-off should guard
 150  * against that), we take Itanium as the default.  Measurements on
 151  * other multiprocessor architectures would be useful.  (On a uniprocessor,
 152  * the initial check is almost certainly a very small loss.) - HB
 153  */
 154 #ifdef __i386__
 155 # define PRECHECK(a) (a) == 0 &&
 156 #else
 157 # define PRECHECK(a)
 158 #endif
 159
 160 AO_t *
 161 AO_stack_pop_explicit_aux_acquire(volatile AO_t *list, AO_stack_aux * a)
 162 {
 163   unsigned i;
 164   int j = 0;
 165   AO_t first;
 166   AO_t * first_ptr;
 167   AO_t next;
 168
 169  retry:
 170   first = AO_load(list);
 171   if (0 == first) return 0;
 172   /* Insert first into aux black list.                                  */
 173   /* This may spin if more than AO_BL_SIZE removals using auxiliary     */
 174   /* structure a are currently in progress.                             */
 175   for (i = 0; ; )
 176     {
 177       if (PRECHECK(a -> AO_stack_bl[i])
 178           AO_compare_and_swap_acquire(a->AO_stack_bl+i, 0, first))
 179         break;
 180       ++i;
 181       if ( i >= AO_BL_SIZE )
 182         {
 183           i = 0;
 184           AO_pause(++j);
 185         }
 186     }
 187   assert(i >= 0 && i < AO_BL_SIZE);
 188   assert(a -> AO_stack_bl[i] == first);
 189   /* First is on the auxiliary black list.  It may be removed by        */
 190   /* another thread before we get to it, but a new insertion of x       */
 191   /* cannot be started here.                                            */
 192   /* Only we can remove it from the black list.                         */
 193   /* We need to make sure that first is still the first entry on the    */
 194   /* list.  Otherwise it's possible that a reinsertion of it was        */
 195   /* already started before we added the black list entry.              */
 196   if (first != AO_load(list)) {
 197     AO_store_release(a->AO_stack_bl+i, 0);
 198     goto retry;
 199   }
 200   first_ptr = AO_REAL_NEXT_PTR(first);
 201   next = AO_load(first_ptr);
 202   if (!AO_compare_and_swap_release(list, first, next)) {
 203     AO_store_release(a->AO_stack_bl+i, 0);
 204     goto retry;
 205   }
 206   assert(*list != first);
 207   /* Since we never insert an entry on the black list, this cannot have */
 208   /* succeeded unless first remained on the list while we were running. */
 209   /* Thus its next link cannot have changed out from under us, and we   */
 210   /* removed exactly one entry and preserved the rest of the list.      */
 211   /* Note that it is quite possible that an additional entry was        */
 212   /* inserted and removed while we were running; this is OK since the   */
 213   /* part of the list following first must have remained unchanged, and */
 214   /* first must again have been at the head of the list when the        */
 215   /* compare_and_swap succeeded.                                        */
 216   AO_store_release(a->AO_stack_bl+i, 0);
 217   return first_ptr;
 218 }
 219
 220 #else /* ! USE_ALMOST_LOCK_FREE */
 221
 222 /* Better names for fields in AO_stack_t */
 223 #define ptr AO_val2
 224 #define version AO_val1
 225
 226 #if defined(AO_HAVE_compare_double_and_swap_double)
 227
 228 void AO_stack_push_release(AO_stack_t *list, AO_t *element)
 229 {
 230     AO_t next;
 231
 232     do {
 233       next = AO_load(&(list -> ptr));
 234       *element = next;
 235     } while (!AO_compare_and_swap_release
 236                     ( &(list -> ptr), next, (AO_t) element));
 237     /* This uses a narrow CAS here, an old optimization suggested       */
 238     /* by Treiber.  Pop is still safe, since we run into the ABA        */
 239     /* problem only if there were both intervening "pop"s and "push"es. */
 240     /* In that case we still see a change in the version number.        */
 241 }
 242
 243 AO_t *AO_stack_pop_acquire(AO_stack_t *list)
 244 {
 245 #   ifdef __clang__
 246       AO_t *volatile cptr;
 247                         /* Use volatile to workaround a bug in          */
 248                         /* clang-1.1/x86 causing test_stack failure.    */
 249 #   else
 250       AO_t *cptr;
 251 #   endif
 252     AO_t next;
 253     AO_t cversion;
 254
 255     do {
 256       /* Version must be loaded first.  */
 257       cversion = AO_load_acquire(&(list -> version));
 258       cptr = (AO_t *)AO_load(&(list -> ptr));
 259       if (cptr == 0) return 0;
 260       next = *cptr;
 261     } while (!AO_compare_double_and_swap_double_release
 262                     (list, cversion, (AO_t) cptr, cversion+1, (AO_t) next));
 263     return cptr;
 264 }
 265
 266
 267 #elif defined(AO_HAVE_compare_and_swap_double)
 268
 269 /* Needed for future IA64 processors.  No current clients? */
 270
 271 #error Untested!  Probably doesnt work.
 272
 273 /* We have a wide CAS, but only does an AO_t-wide comparison.   */
 274 /* We can't use the Treiber optimization, since we only check   */
 275 /* for an unchanged version number, not an unchanged pointer.   */
 276 void AO_stack_push_release(AO_stack_t *list, AO_t *element)
 277 {
 278     AO_t version;
 279     AO_t next_ptr;
 280
 281     do {
 282       /* Again version must be loaded first, for different reason.      */
 283       version = AO_load_acquire(&(list -> version));
 284       next_ptr = AO_load(&(list -> ptr));
 285       *element = next_ptr;
 286     } while (!AO_compare_and_swap_double_release(
 287                            list, version,
 288                            version+1, (AO_t) element));
 289 }
 290
 291 AO_t *AO_stack_pop_acquire(AO_stack_t *list)
 292 {
 293     AO_t *cptr;
 294     AO_t next;
 295     AO_t cversion;
 296
 297     do {
 298       cversion = AO_load_acquire(&(list -> version));
 299       cptr = (AO_t *)AO_load(&(list -> ptr));
 300       if (cptr == 0) return 0;
 301       next = *cptr;
 302     } while (!AO_compare_double_and_swap_double_release
 303                     (list, cversion, (AO_t) cptr, cversion+1, next));
 304     return cptr;
 305 }
 306
 307
 308 #endif /* AO_HAVE_compare_and_swap_double */
 309
 310 #endif /* ! USE_ALMOST_LOCK_FREE */