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
opal_fifo_head(opal_fifo_t * fifo)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
opal_fifo_tail(opal_fifo_t * fifo)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 */
opal_fifo_is_empty(opal_fifo_t * fifo)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 */
opal_fifo_push_atomic(opal_fifo_t * fifo,opal_list_item_t * item)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 (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 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 */
opal_fifo_pop_atomic(opal_fifo_t * fifo)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 (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 != item && 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 while (ghost == item->opal_list_next) {
159 opal_atomic_rmb ();
160 }
161
162 opal_atomic_rmb ();
163
164 /* update the head with the real next value. note that no other thread
165 * will be attempting to update the head until after it has been updated
166 * with the next pointer. push will not see an empty list and other pop
167 * operations will loop until the head is consistent. */
168 fifo->opal_fifo_head.data.item = (opal_list_item_t *) item->opal_list_next;
169 opal_atomic_wmb ();
170 }
171 }
172
173 item->opal_list_next = NULL;
174
175 return item;
176 }
177
178 #else
179
180 /* When compare-and-set 128 is not available we avoid the ABA problem by
181 * using a spin-lock on the head (using the head counter). Otherwise
182 * the algorithm is identical to the compare-and-set 128 version. */
opal_fifo_push_atomic(opal_fifo_t * fifo,opal_list_item_t * item)183 static inline opal_list_item_t *opal_fifo_push_atomic (opal_fifo_t *fifo,
184 opal_list_item_t *item)
185 {
186 const opal_list_item_t * const ghost = &fifo->opal_fifo_ghost;
187 opal_list_item_t *tail_item;
188
189 item->opal_list_next = (opal_list_item_t *) ghost;
190
191 opal_atomic_wmb ();
192
193 /* try to get the tail */
194 tail_item = opal_atomic_swap_ptr (&fifo->opal_fifo_tail.data.item, item);
195
196 opal_atomic_wmb ();
197
198 if (ghost == tail_item) {
199 /* update the head */
200 fifo->opal_fifo_head.data.item = item;
201 } else {
202 /* update previous item */
203 tail_item->opal_list_next = item;
204 }
205
206 opal_atomic_wmb ();
207
208 return (opal_list_item_t *) tail_item;
209 }
210
211 /* Retrieve one element from the FIFO. If we reach the ghost element then the FIFO
212 * is empty so we return NULL.
213 */
opal_fifo_pop_atomic(opal_fifo_t * fifo)214 static inline opal_list_item_t *opal_fifo_pop_atomic (opal_fifo_t *fifo)
215 {
216 const opal_list_item_t * const ghost = &fifo->opal_fifo_ghost;
217
218 #if OPAL_HAVE_ATOMIC_LLSC_PTR
219 register opal_list_item_t *item, *next;
220 int attempt = 0, ret = 0;
221
222 /* use load-linked store-conditional to avoid ABA issues */
223 do {
224 if (++attempt == 5) {
225 /* deliberatly suspend this thread to allow other threads to run. this should
226 * only occur during periods of contention on the lifo. */
227 _opal_lifo_release_cpu ();
228 attempt = 0;
229 }
230
231 opal_atomic_ll_ptr(&fifo->opal_fifo_head.data.item, item);
232 if (ghost == item) {
233 if (ghost == fifo->opal_fifo_tail.data.item) {
234 return NULL;
235 }
236
237 /* fifo does not appear empty. wait for the fifo to be made
238 * consistent by conflicting thread. */
239 continue;
240 }
241
242 next = (opal_list_item_t *) item->opal_list_next;
243 opal_atomic_sc_ptr(&fifo->opal_fifo_head.data.item, next, ret);
244 } while (!ret);
245
246 #else
247 opal_list_item_t *item, *next;
248
249 /* protect against ABA issues by "locking" the head */
250 do {
251 if (!opal_atomic_swap_32 ((volatile int32_t *) &fifo->opal_fifo_head.data.counter, 1)) {
252 break;
253 }
254
255 opal_atomic_wmb ();
256 } while (1);
257
258 opal_atomic_wmb();
259
260 item = opal_fifo_head (fifo);
261 if (ghost == item) {
262 fifo->opal_fifo_head.data.counter = 0;
263 return NULL;
264 }
265
266 next = (opal_list_item_t *) item->opal_list_next;
267 fifo->opal_fifo_head.data.item = next;
268 #endif
269
270 if (ghost == next) {
271 void *tmp = item;
272
273 if (!opal_atomic_compare_exchange_strong_ptr (&fifo->opal_fifo_tail.data.item, &tmp, (void *) ghost)) {
274 do {
275 opal_atomic_rmb ();
276 } while (ghost == item->opal_list_next);
277
278 fifo->opal_fifo_head.data.item = (opal_list_item_t *) item->opal_list_next;
279 }
280 }
281
282 opal_atomic_wmb ();
283
284 /* unlock the head */
285 fifo->opal_fifo_head.data.counter = 0;
286
287 item->opal_list_next = NULL;
288
289 return item;
290 }
291
292 #endif
293
294 /* single threaded versions of push/pop */
opal_fifo_push_st(opal_fifo_t * fifo,opal_list_item_t * item)295 static inline opal_list_item_t *opal_fifo_push_st (opal_fifo_t *fifo,
296 opal_list_item_t *item)
297 {
298 opal_list_item_t *prev = opal_fifo_tail (fifo);
299
300 item->opal_list_next = &fifo->opal_fifo_ghost;
301
302 fifo->opal_fifo_tail.data.item = item;
303 if (&fifo->opal_fifo_ghost == opal_fifo_head (fifo)) {
304 fifo->opal_fifo_head.data.item = item;
305 } else {
306 prev->opal_list_next = item;
307 }
308
309 return (opal_list_item_t *) item->opal_list_next;
310 }
311
opal_fifo_pop_st(opal_fifo_t * fifo)312 static inline opal_list_item_t *opal_fifo_pop_st (opal_fifo_t *fifo)
313 {
314 opal_list_item_t *item = opal_fifo_head (fifo);
315
316 if (item == &fifo->opal_fifo_ghost) {
317 return NULL;
318 }
319
320 fifo->opal_fifo_head.data.item = (opal_list_item_t *) item->opal_list_next;
321 if (&fifo->opal_fifo_ghost == opal_fifo_head (fifo)) {
322 fifo->opal_fifo_tail.data.item = &fifo->opal_fifo_ghost;
323 }
324
325 item->opal_list_next = NULL;
326 return item;
327 }
328
329 /* push/pop versions conditioned off opal_using_threads() */
opal_fifo_push(opal_fifo_t * fifo,opal_list_item_t * item)330 static inline opal_list_item_t *opal_fifo_push (opal_fifo_t *fifo,
331 opal_list_item_t *item)
332 {
333 if (opal_using_threads ()) {
334 return opal_fifo_push_atomic (fifo, item);
335 }
336
337 return opal_fifo_push_st (fifo, item);
338 }
339
opal_fifo_pop(opal_fifo_t * fifo)340 static inline opal_list_item_t *opal_fifo_pop (opal_fifo_t *fifo)
341 {
342 if (opal_using_threads ()) {
343 return opal_fifo_pop_atomic (fifo);
344 }
345
346 return opal_fifo_pop_st (fifo);
347 }
348
349 END_C_DECLS
350
351 #endif /* OPAL_FIFO_H_HAS_BEEN_INCLUDED */
352