OpenMPI  0.1.1
opal_atomic_lifo.h
1 /*
2  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
3  * University Research and Technology
4  * Corporation. All rights reserved.
5  * Copyright (c) 2004-2007 The University of Tennessee and The University
6  * of Tennessee Research Foundation. All rights
7  * reserved.
8  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
9  * University of Stuttgart. All rights reserved.
10  * Copyright (c) 2004-2005 The Regents of the University of California.
11  * All rights reserved.
12  * Copyright (c) 2007 Voltaire All rights reserved.
13  * Copyright (c) 2010 IBM Corporation. All rights reserved.
14  * $COPYRIGHT$
15  *
16  * Additional copyrights may follow
17  *
18  * $HEADER$
19  */
20 
21 #ifndef OPAL_ATOMIC_LIFO_H_HAS_BEEN_INCLUDED
22 #define OPAL_ATOMIC_LIFO_H_HAS_BEEN_INCLUDED
23 
24 #include "opal_config.h"
25 #include "opal/class/opal_list.h"
26 
27 #if OPAL_ENABLE_MULTI_THREADS
28 #include "opal/sys/atomic.h"
29 #endif /* OPAL_ENABLE_MULTI_THREADS */
30 
31 BEGIN_C_DECLS
32 
33 /* Atomic Last In First Out lists. If we are in a multi-threaded environment then the
34  * atomicity is insured via the compare-and-swap operation, if not we simply do a read
35  * and/or a write.
36  *
37  * There is a trick. The ghost element at the end of the list. This ghost element has
38  * the next pointer pointing to itself, therefore we cannot go past the end of the list.
39  * With this approach we will never have a NULL element in the list, so we never have
40  * to test for the NULL.
41  */
43 {
44  opal_object_t super;
45  opal_list_item_t* opal_lifo_head;
46  opal_list_item_t opal_lifo_ghost;
47 };
48 
50 
52 
53 
54 /* The ghost pointer will never change. The head will change via an atomic
55  * compare-and-swap. On most architectures the reading of a pointer is an
56  * atomic operation so we don't have to protect it.
57  */
58 static inline bool opal_atomic_lifo_is_empty( opal_atomic_lifo_t* lifo )
59 {
60  return (lifo->opal_lifo_head == &(lifo->opal_lifo_ghost) ? true : false);
61 }
62 
63 
64 /* Add one element to the LIFO. We will return the last head of the list
65  * to allow the upper level to detect if this element is the first one in the
66  * list (if the list was empty before this operation).
67  */
68 static inline opal_list_item_t* opal_atomic_lifo_push( opal_atomic_lifo_t* lifo,
69  opal_list_item_t* item )
70 {
71 #if OPAL_ENABLE_MULTI_THREADS
72  do {
73  item->opal_list_next = lifo->opal_lifo_head;
75  if( opal_atomic_cmpset_ptr( &(lifo->opal_lifo_head),
76  (void*)item->opal_list_next,
77  item ) ) {
78  opal_atomic_cmpset_32((volatile int32_t*)&item->item_free, 1, 0);
79  return (opal_list_item_t*)item->opal_list_next;
80  }
81  /* DO some kind of pause to release the bus */
82  } while( 1 );
83 #else
84  item->opal_list_next = lifo->opal_lifo_head;
85  lifo->opal_lifo_head = item;
86  return (opal_list_item_t*)item->opal_list_next;
87 #endif /* OPAL_ENABLE_MULTI_THREADS */
88 }
89 
90 /* Retrieve one element from the LIFO. If we reach the ghost element then the LIFO
91  * is empty so we return NULL.
92  */
93 static inline opal_list_item_t* opal_atomic_lifo_pop( opal_atomic_lifo_t* lifo )
94 {
95  opal_list_item_t* item;
96 #if OPAL_ENABLE_MULTI_THREADS
97  while((item = lifo->opal_lifo_head) != &(lifo->opal_lifo_ghost))
98  {
100  if(!opal_atomic_cmpset_32((volatile int32_t*)&item->item_free, 0, 1))
101  continue;
102  if( opal_atomic_cmpset_ptr( &(lifo->opal_lifo_head),
103  item,
104  (void*)item->opal_list_next ) )
105  break;
106  opal_atomic_cmpset_32((volatile int32_t*)&item->item_free, 1, 0);
107  /* Do some kind of pause to release the bus */
108  }
109 #else
110  item = lifo->opal_lifo_head;
111  lifo->opal_lifo_head = (opal_list_item_t*)item->opal_list_next;
112 #endif /* OPAL_ENABLE_MULTI_THREADS */
113  if( item == &(lifo->opal_lifo_ghost) ) return NULL;
114  item->opal_list_next = NULL;
115  return item;
116 }
117 
118 END_C_DECLS
119 
120 #endif /* OPAL_ATOMIC_LIFO_H_HAS_BEEN_INCLUDED */
121 
volatile struct opal_list_item_t * opal_list_next
Pointer to next list item.
Definition: opal_list.h:102
void opal_atomic_rmb(void)
Read memory barrier.
The opal_list_t interface is used to provide a generic doubly-linked list container for Open MPI...
Definition: opal_atomic_lifo.h:42
Definition: opal_list.h:98
Base object.
Definition: opal_object.h:182
void opal_atomic_wmb(void)
Write memory barrier.
Atomic operations.
#define OBJ_CLASS_DECLARATION(NAME)
Declaration for class descriptor.
Definition: opal_object.h:236