root/opal/class/opal_fifo.h

INCLUDED FROM

DEFINITIONS

1. opal_fifo_head
2. opal_fifo_tail
3. opal_fifo_is_empty
4. opal_fifo_push_atomic
5. opal_fifo_pop_atomic
6. opal_fifo_push_atomic
7. opal_fifo_pop_atomic
8. opal_fifo_push_st
9. opal_fifo_pop_st
10. opal_fifo_push
11. opal_fifo_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$
  18  *
  19  * Additional copyrights may follow
  20  *
  21  * $HEADER$
  22  */
  23 
  24 #ifndef OPAL_FIFO_H_HAS_BEEN_INCLUDED
  25 #define OPAL_FIFO_H_HAS_BEEN_INCLUDED
  26 
  27 #include "opal_config.h"
  28 #include "opal/class/opal_lifo.h"
  29 
  30 #include "opal/sys/atomic.h"
  31 #include "opal/threads/mutex.h"
  32 
  33 BEGIN_C_DECLS
  34 
  35 /* Atomic First In First Out lists. If we are in a multi-threaded environment then the
  36  * atomicity is insured via the compare-and-swap operation, if not we simply do a read
  37  * and/or a write.
  38  *
  39  * There is a trick. The ghost element at the end of the list. This ghost element has
  40  * the next pointer pointing to itself, therefore we cannot go past the end of the list.
  41  * With this approach we will never have a NULL element in the list, so we never have
  42  * to test for the NULL.
  43  */
  44 struct opal_fifo_t {
  45     opal_object_t super;
  46 
  47     /** first element on the fifo */
  48     volatile opal_counted_pointer_t opal_fifo_head;
  49     /** last element on the fifo */
  50     volatile opal_counted_pointer_t opal_fifo_tail;
  51 
  52     /** list sentinel (always points to self) */
  53     opal_list_item_t opal_fifo_ghost;
  54 };
  55 
  56 typedef struct opal_fifo_t opal_fifo_t;
  57 
  58 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_fifo_t);
  59 
  60 static inline opal_list_item_t *opal_fifo_head (opal_fifo_t* fifo)
  61 {
  62     return (opal_list_item_t *) fifo->opal_fifo_head.data.item;
  63 }
  64 
  65 static inline opal_list_item_t *opal_fifo_tail (opal_fifo_t* fifo)
  66 {
  67     return (opal_list_item_t *) fifo->opal_fifo_tail.data.item;
  68 }
  69 
  70 /* The ghost pointer will never change. The head will change via an atomic
  71  * compare-and-swap. On most architectures the reading of a pointer is an
  72  * atomic operation so we don't have to protect it.
  73  */
  74 static inline bool opal_fifo_is_empty( opal_fifo_t* fifo )
  75 {
  76     return opal_fifo_head (fifo) == &fifo->opal_fifo_ghost;
  77 }
  78 
  79 #if OPAL_HAVE_ATOMIC_COMPARE_EXCHANGE_128
  80 
  81 /* Add one element to the FIFO. We will return the last head of the list
  82  * to allow the upper level to detect if this element is the first one in the
  83  * list (if the list was empty before this operation).
  84  */
  85 static inline opal_list_item_t *opal_fifo_push_atomic (opal_fifo_t *fifo,
  86                                                        opal_list_item_t *item)
  87 {
  88     opal_counted_pointer_t tail = {.value = fifo->opal_fifo_tail.value};
  89     const opal_list_item_t * const ghost = &fifo->opal_fifo_ghost;
  90 
  91     item->opal_list_next = (opal_list_item_t *) ghost;
  92 
  93     opal_atomic_wmb ();
  94 
  95     do {
  96         if (opal_update_counted_pointer (&fifo->opal_fifo_tail, &tail, item)) {
  97             break;
  98         }
  99     } while (1);
 100 
 101     opal_atomic_wmb ();
 102 
 103   if ((intptr_t) ghost == tail.data.item) {
 104         /* update the head */
 105         opal_counted_pointer_t head = {.value = fifo->opal_fifo_head.value};
 106         opal_update_counted_pointer (&fifo->opal_fifo_head, &head, item);
 107     } else {
 108         /* update previous item */
 109         ((opal_list_item_t *) tail.data.item)->opal_list_next = item;
 110     }
 111 
 112     return (opal_list_item_t *) tail.data.item;
 113 }
 114 
 115 /* Retrieve one element from the FIFO. If we reach the ghost element then the FIFO
 116  * is empty so we return NULL.
 117  */
 118 static inline opal_list_item_t *opal_fifo_pop_atomic (opal_fifo_t *fifo)
 119 {
 120     opal_list_item_t *item, *next, *ghost = &fifo->opal_fifo_ghost;
 121     opal_counted_pointer_t head, tail;
 122 
 123     opal_read_counted_pointer (&fifo->opal_fifo_head, &head);
 124 
 125     do {
 126         tail.value = fifo->opal_fifo_tail.value;
 127         opal_atomic_rmb ();
 128 
 129         item = (opal_list_item_t *) head.data.item;
 130         next = (opal_list_item_t *) item->opal_list_next;
 131 
 132         if ((intptr_t) ghost == tail.data.item && ghost == item) {
 133             return NULL;
 134         }
 135 
 136         /* the head or next pointer are in an inconsistent state. keep looping. */
 137         if (tail.data.item != (intptr_t) item && (intptr_t) ghost != tail.data.item && ghost == next) {
 138             opal_read_counted_pointer (&fifo->opal_fifo_head, &head);
 139             continue;
 140         }
 141 
 142         /* try popping the head */
 143         if (opal_update_counted_pointer (&fifo->opal_fifo_head, &head, next)) {
 144             break;
 145         }
 146     } while (1);
 147 
 148     opal_atomic_wmb ();
 149 
 150     /* check for tail and head consistency */
 151     if (ghost == next) {
 152         /* the head was just set to &fifo->opal_fifo_ghost. try to update the tail as well */
 153         if (!opal_update_counted_pointer (&fifo->opal_fifo_tail, &tail, ghost)) {
 154             /* tail was changed by a push operation. wait for the item's next pointer to be se then
 155              * update the head */
 156 
 157             /* wait for next pointer to be updated by push */
 158             do {
 159                 opal_atomic_rmb ();
 160             } while (ghost == item->opal_list_next);
 161 
 162             /* update the head with the real next value. note that no other thread
 163              * will be attempting to update the head until after it has been updated
 164              * with the next pointer. push will not see an empty list and other pop
 165              * operations will loop until the head is consistent. */
 166             fifo->opal_fifo_head.data.item = (intptr_t) item->opal_list_next;
 167             opal_atomic_wmb ();
 168         }
 169     }
 170 
 171     item->opal_list_next = NULL;
 172 
 173     return item;
 174 }
 175 
 176 #else
 177 
 178 /* When compare-and-set 128 is not available we avoid the ABA problem by
 179  * using a spin-lock on the head (using the head counter). Otherwise
 180  * the algorithm is identical to the compare-and-set 128 version. */
 181 static inline opal_list_item_t *opal_fifo_push_atomic (opal_fifo_t *fifo,
 182                                                        opal_list_item_t *item)
 183 {
 184     const opal_list_item_t * const ghost = &fifo->opal_fifo_ghost;
 185     opal_list_item_t *tail_item;
 186 
 187     item->opal_list_next = (opal_list_item_t *) ghost;
 188 
 189     opal_atomic_wmb ();
 190 
 191     /* try to get the tail */
 192     tail_item = (opal_list_item_t *) opal_atomic_swap_ptr (&fifo->opal_fifo_tail.data.item, (intptr_t) item);
 193 
 194     opal_atomic_wmb ();
 195 
 196     if (ghost == tail_item) {
 197         /* update the head */
 198         fifo->opal_fifo_head.data.item = (intptr_t) item;
 199     } else {
 200         /* update previous item */
 201         tail_item->opal_list_next = item;
 202     }
 203 
 204     opal_atomic_wmb ();
 205 
 206     return (opal_list_item_t *) tail_item;
 207 }
 208 
 209 /* Retrieve one element from the FIFO. If we reach the ghost element then the FIFO
 210  * is empty so we return NULL.
 211  */
 212 static inline opal_list_item_t *opal_fifo_pop_atomic (opal_fifo_t *fifo)
 213 {
 214     const opal_list_item_t * const ghost = &fifo->opal_fifo_ghost;
 215 
 216 #if OPAL_HAVE_ATOMIC_LLSC_PTR
 217     register opal_list_item_t *item, *next;
 218     int attempt = 0, ret = 0;
 219 
 220     /* use load-linked store-conditional to avoid ABA issues */
 221     do {
 222         if (++attempt == 5) {
 223             /* deliberatly suspend this thread to allow other threads to run. this should
 224              * only occur during periods of contention on the lifo. */
 225             _opal_lifo_release_cpu ();
 226             attempt = 0;
 227         }
 228 
 229         opal_atomic_ll_ptr(&fifo->opal_fifo_head.data.item, item);
 230         if (ghost == item) {
 231             if ((intptr_t) ghost == fifo->opal_fifo_tail.data.item) {
 232                 return NULL;
 233             }
 234 
 235             /* fifo does not appear empty. wait for the fifo to be made
 236              * consistent by conflicting thread. */
 237             continue;
 238         }
 239 
 240         next = (opal_list_item_t *) item->opal_list_next;
 241         opal_atomic_sc_ptr(&fifo->opal_fifo_head.data.item, next, ret);
 242     } while (!ret);
 243 
 244 #else
 245     opal_list_item_t *item, *next;
 246 
 247     /* protect against ABA issues by "locking" the head */
 248     do {
 249         if (!opal_atomic_swap_32 ((opal_atomic_int32_t *) &fifo->opal_fifo_head.data.counter, 1)) {
 250             break;
 251         }
 252 
 253         opal_atomic_wmb ();
 254     } while (1);
 255 
 256     opal_atomic_wmb();
 257 
 258     item = opal_fifo_head (fifo);
 259     if (ghost == item) {
 260         fifo->opal_fifo_head.data.counter = 0;
 261         return NULL;
 262     }
 263 
 264     next = (opal_list_item_t *) item->opal_list_next;
 265     fifo->opal_fifo_head.data.item = (uintptr_t) next;
 266 #endif
 267 
 268     if (ghost == next) {
 269         void *tmp = item;
 270 
 271         if (!opal_atomic_compare_exchange_strong_ptr (&fifo->opal_fifo_tail.data.item, (intptr_t *) &tmp, (intptr_t) ghost)) {
 272             do {
 273                 opal_atomic_rmb ();
 274             } while (ghost == item->opal_list_next);
 275 
 276             fifo->opal_fifo_head.data.item = (intptr_t) item->opal_list_next;
 277         }
 278     }
 279 
 280     opal_atomic_wmb ();
 281 
 282     /* unlock the head */
 283     fifo->opal_fifo_head.data.counter = 0;
 284 
 285     item->opal_list_next = NULL;
 286 
 287     return item;
 288 }
 289 
 290 #endif
 291 
 292 /* single threaded versions of push/pop */
 293 static inline opal_list_item_t *opal_fifo_push_st (opal_fifo_t *fifo,
 294                                                    opal_list_item_t *item)
 295 {
 296     opal_list_item_t *prev = opal_fifo_tail (fifo);
 297 
 298     item->opal_list_next = &fifo->opal_fifo_ghost;
 299 
 300     fifo->opal_fifo_tail.data.item = (intptr_t) item;
 301     if (&fifo->opal_fifo_ghost == opal_fifo_head (fifo)) {
 302         fifo->opal_fifo_head.data.item = (intptr_t) item;
 303     } else {
 304         prev->opal_list_next = item;
 305     }
 306 
 307     return (opal_list_item_t *) item->opal_list_next;
 308 }
 309 
 310 static inline opal_list_item_t *opal_fifo_pop_st (opal_fifo_t *fifo)
 311 {
 312     opal_list_item_t *item = opal_fifo_head (fifo);
 313 
 314     if (item == &fifo->opal_fifo_ghost) {
 315         return NULL;
 316     }
 317 
 318     fifo->opal_fifo_head.data.item = (intptr_t) item->opal_list_next;
 319     if (&fifo->opal_fifo_ghost == opal_fifo_head (fifo)) {
 320         fifo->opal_fifo_tail.data.item = (intptr_t) &fifo->opal_fifo_ghost;
 321     }
 322 
 323     item->opal_list_next = NULL;
 324     return item;
 325 }
 326 
 327 /* push/pop versions conditioned off opal_using_threads() */
 328 static inline opal_list_item_t *opal_fifo_push (opal_fifo_t *fifo,
 329                                                 opal_list_item_t *item)
 330 {
 331     if (opal_using_threads ()) {
 332         return opal_fifo_push_atomic (fifo, item);
 333     }
 334 
 335     return opal_fifo_push_st (fifo, item);
 336 }
 337 
 338 static inline opal_list_item_t *opal_fifo_pop (opal_fifo_t *fifo)
 339 {
 340     if (opal_using_threads ()) {
 341         return opal_fifo_pop_atomic (fifo);
 342     }
 343 
 344     return opal_fifo_pop_st (fifo);
 345 }
 346 
 347 END_C_DECLS
 348 
 349 #endif  /* OPAL_FIFO_H_HAS_BEEN_INCLUDED */