root/opal/class/opal_lifo.h

INCLUDED FROM

DEFINITIONS

1. opal_update_counted_pointer
2. opal_read_counted_pointer
3. _opal_lifo_release_cpu
4. opal_lifo_is_empty
5. opal_lifo_push_atomic
6. opal_lifo_pop_atomic
7. opal_lifo_push_atomic
8. opal_lifo_pop_atomic
9. opal_lifo_pop_atomic
10. opal_lifo_push_st
11. opal_lifo_pop_st
12. opal_lifo_push
13. opal_lifo_pop

   1 /* -*- Mode: C; c-basic-offset:4 ; indent-tabs-mode:nil -*- */
   2 /*
   3  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   4  *                         University Research and Technology
   5  *                         Corporation.  All rights reserved.
   6  * Copyright (c) 2004-2007 The University of Tennessee and The University
   7  *                         of Tennessee Research Foundation.  All rights
   8  *                         reserved.
   9  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
  10  *                         University of Stuttgart.  All rights reserved.
  11  * Copyright (c) 2004-2005 The Regents of the University of California.
  12  *                         All rights reserved.
  13  * Copyright (c) 2007      Voltaire All rights reserved.
  14  * Copyright (c) 2010      IBM Corporation.  All rights reserved.
  15  * Copyright (c) 2014-2018 Los Alamos National Security, LLC. All rights
  16  *                         reseved.
  17  * Copyright (c) 2016-2018 Research Organization for Information Science
  18  *                         and Technology (RIST).  All rights reserved.
  19  * $COPYRIGHT$
  20  *
  21  * Additional copyrights may follow
  22  *
  23  * $HEADER$
  24  */
  25 
  26 #ifndef OPAL_LIFO_H_HAS_BEEN_INCLUDED
  27 #define OPAL_LIFO_H_HAS_BEEN_INCLUDED
  28 
  29 #include "opal_config.h"
  30 #include <time.h>
  31 #include "opal/class/opal_list.h"
  32 
  33 #include "opal/sys/atomic.h"
  34 #include "opal/threads/mutex.h"
  35 
  36 BEGIN_C_DECLS
  37 
  38 /* NTH: temporarily suppress warnings about this not being defined */
  39 #if !defined(OPAL_HAVE_ATOMIC_COMPARE_EXCHANGE_128)
  40 #define OPAL_HAVE_ATOMIC_COMPARE_EXCHANGE_128 0
  41 #endif
  42 
  43 /**
  44  * Counted pointer to avoid the ABA problem.
  45  */
  46 union opal_counted_pointer_t {
  47     struct {
  48         /** update counter used when cmpset_128 is available */
  49         uint64_t counter;
  50         /** list item pointer */
  51         volatile opal_atomic_intptr_t item;
  52     } data;
  53 #if OPAL_HAVE_ATOMIC_COMPARE_EXCHANGE_128 && HAVE_OPAL_INT128_T
  54     /** used for atomics when there is a cmpset that can operate on
  55      * two 64-bit values */
  56     opal_atomic_int128_t atomic_value;
  57     opal_int128_t value;
  58 #endif
  59 };
  60 typedef union opal_counted_pointer_t opal_counted_pointer_t;
  61 
  62 
  63 #if OPAL_HAVE_ATOMIC_COMPARE_EXCHANGE_128
  64 
  65 /* Add one element to the FIFO. We will return the last head of the list
  66  * to allow the upper level to detect if this element is the first one in the
  67  * list (if the list was empty before this operation).
  68  */
  69 static inline bool opal_update_counted_pointer (volatile opal_counted_pointer_t * volatile addr, opal_counted_pointer_t *old,
  70                                                 opal_list_item_t *item)
  71 {
  72     opal_counted_pointer_t new_p;
  73     new_p.data.item = (intptr_t) item;
  74     new_p.data.counter = old->data.counter + 1;
  75     return opal_atomic_compare_exchange_strong_128 (&addr->atomic_value, &old->value, new_p.value);
  76 }
  77 
  78 __opal_attribute_always_inline__
  79 static inline void opal_read_counted_pointer (volatile opal_counted_pointer_t * volatile addr, opal_counted_pointer_t *value)
  80 {
  81     /* most platforms do not read the value atomically so make sure we read the counted pointer in a specific order */
  82     value->data.counter = addr->data.counter;
  83     opal_atomic_rmb ();
  84     value->data.item = addr->data.item;
  85 }
  86 
  87 #endif
  88 
  89 /**
  90  * @brief Helper function for lifo/fifo to sleep this thread if excessive contention is detected
  91  */
  92 static inline void _opal_lifo_release_cpu (void)
  93 {
  94     /* NTH: there are many ways to cause the current thread to be suspended. This one
  95      * should work well in most cases. Another approach would be to use poll (NULL, 0, ) but
  96      * the interval will be forced to be in ms (instead of ns or us). Note that there
  97      * is a performance improvement for the lifo test when this call is made on detection
  98      * of contention but it may not translate into actually MPI or application performance
  99      * improvements. */
 100     static struct timespec interval = { .tv_sec = 0, .tv_nsec = 100 };
 101     nanosleep (&interval, NULL);
 102 }
 103 
 104 
 105 /* Atomic Last In First Out lists. If we are in a multi-threaded environment then the
 106  * atomicity is insured via the compare-and-swap operation, if not we simply do a read
 107  * and/or a write.
 108  *
 109  * There is a trick. The ghost element at the end of the list. This ghost element has
 110  * the next pointer pointing to itself, therefore we cannot go past the end of the list.
 111  * With this approach we will never have a NULL element in the list, so we never have
 112  * to test for the NULL.
 113  */
 114 struct opal_lifo_t {
 115     opal_object_t super;
 116 
 117     /** head element of the lifo. points to opal_lifo_ghost if the lifo is empty */
 118     volatile opal_counted_pointer_t opal_lifo_head;
 119 
 120     /** list sentinel (always points to self) */
 121     opal_list_item_t opal_lifo_ghost;
 122 };
 123 
 124 typedef struct opal_lifo_t opal_lifo_t;
 125 
 126 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_lifo_t);
 127 
 128 
 129 /* The ghost pointer will never change. The head will change via an atomic
 130  * compare-and-swap. On most architectures the reading of a pointer is an
 131  * atomic operation so we don't have to protect it.
 132  */
 133 static inline bool opal_lifo_is_empty( opal_lifo_t* lifo )
 134 {
 135     return (opal_list_item_t *) lifo->opal_lifo_head.data.item == &lifo->opal_lifo_ghost;
 136 }
 137 
 138 
 139 #if OPAL_HAVE_ATOMIC_COMPARE_EXCHANGE_128
 140 
 141 /* Add one element to the LIFO. We will return the last head of the list
 142  * to allow the upper level to detect if this element is the first one in the
 143  * list (if the list was empty before this operation).
 144  */
 145 static inline opal_list_item_t *opal_lifo_push_atomic (opal_lifo_t *lifo,
 146                                                        opal_list_item_t *item)
 147 {
 148     opal_list_item_t *next = (opal_list_item_t *) lifo->opal_lifo_head.data.item;
 149 
 150     do {
 151         item->opal_list_next = next;
 152         opal_atomic_wmb ();
 153 
 154         /* to protect against ABA issues it is sufficient to only update the counter in pop */
 155         if (opal_atomic_compare_exchange_strong_ptr (&lifo->opal_lifo_head.data.item, (intptr_t *) &next, (intptr_t) item)) {
 156             return next;
 157         }
 158         /* DO some kind of pause to release the bus */
 159     } while (1);
 160 }
 161 
 162 /* Retrieve one element from the LIFO. If we reach the ghost element then the LIFO
 163  * is empty so we return NULL.
 164  */
 165 static inline opal_list_item_t *opal_lifo_pop_atomic (opal_lifo_t* lifo)
 166 {
 167     opal_counted_pointer_t old_head;
 168     opal_list_item_t *item;
 169 
 170     opal_read_counted_pointer (&lifo->opal_lifo_head, &old_head);
 171 
 172     do {
 173         item = (opal_list_item_t *) old_head.data.item;
 174         if (item == &lifo->opal_lifo_ghost) {
 175             return NULL;
 176         }
 177 
 178         if (opal_update_counted_pointer (&lifo->opal_lifo_head, &old_head,
 179                                          (opal_list_item_t *) item->opal_list_next)) {
 180             opal_atomic_wmb ();
 181             item->opal_list_next = NULL;
 182             return item;
 183         }
 184     } while (1);
 185 }
 186 
 187 #else
 188 
 189 /* Add one element to the LIFO. We will return the last head of the list
 190  * to allow the upper level to detect if this element is the first one in the
 191  * list (if the list was empty before this operation).
 192  */
 193 static inline opal_list_item_t *opal_lifo_push_atomic (opal_lifo_t *lifo,
 194                                                        opal_list_item_t *item)
 195 {
 196     opal_list_item_t *next = (opal_list_item_t *) lifo->opal_lifo_head.data.item;
 197 
 198     /* item free acts as a mini lock to avoid ABA problems */
 199     item->item_free = 1;
 200 
 201     do {
 202         item->opal_list_next = next;
 203         opal_atomic_wmb();
 204         if (opal_atomic_compare_exchange_strong_ptr (&lifo->opal_lifo_head.data.item, (intptr_t *) &next, (intptr_t) item)) {
 205             opal_atomic_wmb ();
 206             /* now safe to pop this item */
 207             item->item_free = 0;
 208             return next;
 209         }
 210         /* DO some kind of pause to release the bus */
 211     } while (1);
 212 }
 213 
 214 #if OPAL_HAVE_ATOMIC_LLSC_PTR
 215 
 216 /* Retrieve one element from the LIFO. If we reach the ghost element then the LIFO
 217  * is empty so we return NULL.
 218  */
 219 static inline opal_list_item_t *opal_lifo_pop_atomic (opal_lifo_t* lifo)
 220 {
 221     register opal_list_item_t *item, *next;
 222     int attempt = 0, ret;
 223 
 224     do {
 225         if (++attempt == 5) {
 226             /* deliberatly suspend this thread to allow other threads to run. this should
 227              * only occur during periods of contention on the lifo. */
 228             _opal_lifo_release_cpu ();
 229             attempt = 0;
 230         }
 231 
 232         opal_atomic_ll_ptr(&lifo->opal_lifo_head.data.item, item);
 233         if (&lifo->opal_lifo_ghost == item) {
 234             return NULL;
 235         }
 236 
 237         next = (opal_list_item_t *) item->opal_list_next;
 238         opal_atomic_sc_ptr(&lifo->opal_lifo_head.data.item, next, ret);
 239     } while (!ret);
 240 
 241     opal_atomic_wmb ();
 242 
 243     item->opal_list_next = NULL;
 244     return item;
 245 }
 246 
 247 #else
 248 
 249 /* Retrieve one element from the LIFO. If we reach the ghost element then the LIFO
 250  * is empty so we return NULL.
 251  */
 252 static inline opal_list_item_t *opal_lifo_pop_atomic (opal_lifo_t* lifo)
 253 {
 254     opal_list_item_t *item, *head, *ghost = &lifo->opal_lifo_ghost;
 255 
 256     while ((item=(opal_list_item_t *)lifo->opal_lifo_head.data.item) != ghost) {
 257         /* ensure it is safe to pop the head */
 258         if (opal_atomic_swap_32((opal_atomic_int32_t *) &item->item_free, 1)) {
 259             continue;
 260         }
 261 
 262         opal_atomic_wmb ();
 263 
 264         head = item;
 265         /* try to swap out the head pointer */
 266         if (opal_atomic_compare_exchange_strong_ptr (&lifo->opal_lifo_head.data.item, (intptr_t *) &head,
 267                                                      (intptr_t) item->opal_list_next)) {
 268             break;
 269         }
 270 
 271         /* NTH: don't need another atomic here */
 272         item->item_free = 0;
 273         item = head;
 274 
 275         /* Do some kind of pause to release the bus */
 276     }
 277 
 278     if (item == &lifo->opal_lifo_ghost) {
 279         return NULL;
 280     }
 281 
 282     opal_atomic_wmb ();
 283 
 284     item->opal_list_next = NULL;
 285     return item;
 286 }
 287 
 288 #endif /* OPAL_HAVE_ATOMIC_LLSC_PTR */
 289 
 290 #endif
 291 
 292 /* single-threaded versions of the lifo functions */
 293 static inline opal_list_item_t *opal_lifo_push_st (opal_lifo_t *lifo,
 294                                                    opal_list_item_t *item)
 295 {
 296     item->opal_list_next = (opal_list_item_t *) lifo->opal_lifo_head.data.item;
 297     item->item_free = 0;
 298     lifo->opal_lifo_head.data.item = (intptr_t) item;
 299     return (opal_list_item_t *) item->opal_list_next;
 300 }
 301 
 302 static inline opal_list_item_t *opal_lifo_pop_st (opal_lifo_t *lifo)
 303 {
 304     opal_list_item_t *item;
 305     item = (opal_list_item_t *) lifo->opal_lifo_head.data.item;
 306     lifo->opal_lifo_head.data.item = (intptr_t) item->opal_list_next;
 307     if (item == &lifo->opal_lifo_ghost) {
 308         return NULL;
 309     }
 310 
 311     item->opal_list_next = NULL;
 312     item->item_free = 1;
 313     return item;
 314 }
 315 
 316 /* conditional versions of lifo functions. use atomics if opal_using_threads is set */
 317 static inline opal_list_item_t *opal_lifo_push (opal_lifo_t *lifo,
 318                                                 opal_list_item_t *item)
 319 {
 320     if (opal_using_threads ()) {
 321         return opal_lifo_push_atomic (lifo, item);
 322     }
 323 
 324     return opal_lifo_push_st (lifo, item);
 325 }
 326 
 327 static inline opal_list_item_t *opal_lifo_pop (opal_lifo_t *lifo)
 328 {
 329     if (opal_using_threads ()) {
 330         return opal_lifo_pop_atomic (lifo);
 331     }
 332 
 333     return opal_lifo_pop_st (lifo);
 334 }
 335 
 336 END_C_DECLS
 337 
 338 #endif  /* OPAL_LIFO_H_HAS_BEEN_INCLUDED */