OpenMPI  0.1.1
ompi_free_list.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-2006 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) 2010 IBM Corporation. All rights reserved.
13  * Copyright (c) 2010 Cisco Systems, Inc. All rights reserved.
14  * $COPYRIGHT$
15  *
16  * Additional copyrights may follow
17  *
18  * $HEADER$
19  */
20 
21 #ifndef OMPI_FREE_LIST_H
22 #define OMPI_FREE_LIST_H
23 
24 #include "ompi_config.h"
25 #include "opal/class/opal_atomic_lifo.h"
26 #include "opal/prefetch.h"
27 #include "opal/threads/condition.h"
28 #include "ompi/constants.h"
29 #include "opal/runtime/opal.h"
30 
31 BEGIN_C_DECLS
32 
33 struct mca_mem_pool_t;
35 
36 typedef void (*ompi_free_list_item_init_fn_t) (
37  struct ompi_free_list_item_t*, void* ctx);
38 
40 {
41  opal_atomic_lifo_t super;
42  size_t fl_max_to_alloc;
43  size_t fl_num_allocated;
44  size_t fl_num_per_alloc;
45  size_t fl_num_waiting;
46  size_t fl_frag_size; /* size of the fragment descriptor */
47  size_t fl_frag_alignment; /* fragment descriptor alignment */
48  size_t fl_payload_buffer_size; /* size of payload buffer */
49  size_t fl_payload_buffer_alignment; /* payload buffer alignment */
50  opal_class_t* fl_frag_class;
51  struct mca_mpool_base_module_t* fl_mpool;
52  opal_mutex_t fl_lock;
53  opal_condition_t fl_condition;
54  opal_list_t fl_allocations;
55  ompi_free_list_item_init_fn_t item_init;
56  void* ctx;
57 };
58 typedef struct ompi_free_list_t ompi_free_list_t;
60 
63 {
64  opal_list_item_t super;
65  struct mca_mpool_base_registration_t *registration;
66  void *ptr;
67 };
70 
71 /**
72  * Initialize a free list.
73  *
74  * @param free_list (IN) Free list.
75  * @param element_size (IN) Size of each element.
76  * @param element_class (IN) opal_class_t of element - used to initialize allocated elements.
77  * @param num_elements_to_alloc Initial number of elements to allocate.
78  * @param max_elements_to_alloc Maximum number of elements to allocate.
79  * @param num_elements_per_alloc Number of elements to grow by per allocation.
80  * @param mpool Optional memory pool for allocation.s
81  */
82 
83 OMPI_DECLSPEC int ompi_free_list_init_ex(
84  ompi_free_list_t *free_list,
85  size_t element_size,
86  size_t alignment,
87  opal_class_t* element_class,
88  int num_elements_to_alloc,
89  int max_elements_to_alloc,
90  int num_elements_per_alloc,
92  ompi_free_list_item_init_fn_t item_init,
93  void *ctx
94  );
95 
96 static inline int ompi_free_list_init(
97  ompi_free_list_t *free_list,
98  size_t element_size,
99  opal_class_t* element_class,
100  int num_elements_to_alloc,
101  int max_elements_to_alloc,
102  int num_elements_per_alloc,
103  struct mca_mpool_base_module_t* mpool)
104 {
105  return ompi_free_list_init_ex(free_list, element_size, opal_cache_line_size,
106  element_class, num_elements_to_alloc, max_elements_to_alloc,
107  num_elements_per_alloc, mpool, NULL, NULL);
108 }
109 
110 /**
111  * Initialize a free list. - this will replace ompi_free_list_init_ex
112  *
113  * @param free_list (IN) Free list.
114  * @param frag_size (IN) Size of each element - allocated by malloc.
115  * @param frag_alignment (IN) Fragment alignment.
116  * @param frag_class (IN) opal_class_t of element - used to initialize allocated elements.
117  * @param payload_buffer_size (IN) Size of payload buffer - allocated from mpool.
118  * @param payload_buffer_alignment (IN) Payload buffer alignment.
119  * @param num_elements_to_alloc (IN) Initial number of elements to allocate.
120  * @param max_elements_to_alloc (IN) Maximum number of elements to allocate.
121  * @param num_elements_per_alloc (IN) Number of elements to grow by per allocation.
122  * @param mpool (IN) Optional memory pool for allocation.s
123  * @param item_init (IN)
124  * @param ctx (IN)
125  */
126 
127 OMPI_DECLSPEC int ompi_free_list_init_ex_new(
128  ompi_free_list_t *free_list,
129  size_t frag_size,
130  size_t frag_alignment,
131  opal_class_t* frag_class,
132  size_t payload_buffer_size,
133  size_t payload_buffer_alignment,
134  int num_elements_to_alloc,
135  int max_elements_to_alloc,
136  int num_elements_per_alloc,
137  struct mca_mpool_base_module_t*,
138  ompi_free_list_item_init_fn_t item_init,
139  void *ctx
140  );
141 
142 /**
143  * Initialize a free list. - this will replace ompi_free_list_init
144  *
145  * @param free_list (IN) Free list.
146  * @param frag_size (IN) Size of each element - allocated by malloc.
147  * @param frag_alignment (IN) Fragment alignment.
148  * @param frag_class (IN) opal_class_t of element - used to initialize allocated elements.
149  * @param payload_buffer_size (IN) Size of payload buffer - allocated from mpool.
150  * @param payload_buffer_alignment (IN) Payload buffer alignment.
151  * @param num_elements_to_alloc (IN) Initial number of elements to allocate.
152  * @param max_elements_to_alloc (IN) Maximum number of elements to allocate.
153  * @param num_elements_per_alloc (IN) Number of elements to grow by per allocation.
154  * @param mpool (IN) Optional memory pool for allocation.s
155  */
156 static inline int ompi_free_list_init_new(
157  ompi_free_list_t *free_list,
158  size_t frag_size,
159  size_t frag_alignment,
160  opal_class_t* frag_class,
161  size_t payload_buffer_size,
162  size_t payload_buffer_alignment,
163  int num_elements_to_alloc,
164  int max_elements_to_alloc,
165  int num_elements_per_alloc,
166  struct mca_mpool_base_module_t* mpool)
167 {
168  return ompi_free_list_init_ex_new(free_list,
169  frag_size, frag_alignment, frag_class,
170  payload_buffer_size, payload_buffer_alignment,
171  num_elements_to_alloc, max_elements_to_alloc,
172  num_elements_per_alloc, mpool, NULL, NULL);
173 }
174 
175 OMPI_DECLSPEC int ompi_free_list_grow(ompi_free_list_t* flist, size_t num_elements);
176 
177 /* Grow the free list to be *at least* size elements. This function
178  will not shrink the list if it is already larger than size and may
179  grow it past size if necessary (it will grow in
180  num_elements_per_alloc chunks) */
181 OMPI_DECLSPEC int ompi_free_list_resize(ompi_free_list_t *flist, size_t size);
182 
183 /**
184  * Attemp to obtain an item from a free list.
185  *
186  * @param fl (IN) Free list.
187  * @param item (OUT) Allocated item.
188  * @param rc (OUT) OMPI_SUCCESS or error status on failure.
189  *
190  * If the requested item is not available the free list is grown to
191  * accomodate the request - unless the max number of allocations has
192  * been reached. If this is the case - an out of resource error is
193  * returned to the caller.
194  */
195 
196 #define OMPI_FREE_LIST_GET(fl, item, rc) \
197 { \
198  rc = OMPI_SUCCESS; \
199  item = (ompi_free_list_item_t*) opal_atomic_lifo_pop(&((fl)->super)); \
200  if( OPAL_UNLIKELY(NULL == item) ) { \
201  if(opal_using_threads()) { \
202  opal_mutex_lock(&((fl)->fl_lock)); \
203  ompi_free_list_grow((fl), (fl)->fl_num_per_alloc); \
204  opal_mutex_unlock(&((fl)->fl_lock)); \
205  } else { \
206  ompi_free_list_grow((fl), (fl)->fl_num_per_alloc); \
207  } \
208  item = (ompi_free_list_item_t*) opal_atomic_lifo_pop(&((fl)->super)); \
209  if( OPAL_UNLIKELY(NULL == item) ) rc = OMPI_ERR_TEMP_OUT_OF_RESOURCE; \
210  } \
211 }
212 
213 /**
214  * Blocking call to obtain an item from a free list.
215  *
216  * @param fl (IN) Free list.
217  * @param item (OUT) Allocated item.
218  * @param rc (OUT) OMPI_SUCCESS or error status on failure.
219  *
220  * If the requested item is not available the free list is grown to
221  * accomodate the request - unless the max number of allocations has
222  * been reached. In this case the caller is blocked until an item
223  * is returned to the list.
224  */
225 
226 #define OMPI_FREE_LIST_WAIT(fl, item, rc) \
227  rc = __ompi_free_list_wait( (fl), &(item) )
228 
229 static inline int __ompi_free_list_wait( ompi_free_list_t* fl,
230  ompi_free_list_item_t** item )
231 {
232  *item = (ompi_free_list_item_t*)opal_atomic_lifo_pop(&((fl)->super));
233  while( NULL == *item ) {
234  if( !OPAL_THREAD_TRYLOCK(&((fl)->fl_lock)) ) {
235  if((fl)->fl_max_to_alloc <= (fl)->fl_num_allocated) {
236  (fl)->fl_num_waiting++;
237  opal_condition_wait(&((fl)->fl_condition), &((fl)->fl_lock));
238  (fl)->fl_num_waiting--;
239  } else {
240  if(ompi_free_list_grow((fl), (fl)->fl_num_per_alloc)
241  == OMPI_SUCCESS) {
242  if( 0 < (fl)->fl_num_waiting ) {
243  if( 1 == (fl)->fl_num_waiting ) {
244  opal_condition_signal(&((fl)->fl_condition));
245  } else {
246  opal_condition_broadcast(&((fl)->fl_condition));
247  }
248  }
249  } else {
250  (fl)->fl_num_waiting++;
251  opal_condition_wait(&((fl)->fl_condition), &((fl)->fl_lock));
252  (fl)->fl_num_waiting--;
253  }
254  }
255  } else {
256  /* If I wasn't able to get the lock in the begining when I finaly grab it
257  * the one holding the lock in the begining already grow the list. I will
258  * release the lock and try to get a new element until I succeed.
259  */
260  OPAL_THREAD_LOCK(&((fl)->fl_lock));
261  }
262  OPAL_THREAD_UNLOCK(&((fl)->fl_lock));
263  *item = (ompi_free_list_item_t*)opal_atomic_lifo_pop(&((fl)->super));
264  }
265  return OMPI_SUCCESS;
266 }
267 
268 /**
269  * Return an item to a free list.
270  *
271  * @param fl (IN) Free list.
272  * @param item (OUT) Allocated item.
273  *
274  */
275 
276 #define OMPI_FREE_LIST_RETURN(fl, item) \
277  do { \
278  opal_list_item_t* original; \
279  \
280  original = opal_atomic_lifo_push( &(fl)->super, \
281  &(item)->super); \
282  if( &(fl)->super.opal_lifo_ghost == original ) { \
283  OPAL_THREAD_LOCK(&(fl)->fl_lock); \
284  if((fl)->fl_num_waiting > 0) { \
285  if( 1 == (fl)->fl_num_waiting ) { \
286  opal_condition_signal(&((fl)->fl_condition)); \
287  } else { \
288  opal_condition_broadcast(&((fl)->fl_condition)); \
289  } \
290  } \
291  OPAL_THREAD_UNLOCK(&(fl)->fl_lock); \
292  } \
293  } while(0)
294 
295 END_C_DECLS
296 #endif
297 
#define OPAL_THREAD_TRYLOCK(mutex)
Try to lock a mutex if opal_using_threads() says that multiple threads may be active in the process...
Definition: mutex.h:269
Definition: condition.h:49
Definition: mutex_unix.h:53
Definition: mpool.h:44
Definition: opal_atomic_lifo.h:42
Definition: opal_list.h:98
#define OPAL_THREAD_LOCK(mutex)
Lock a mutex if opal_using_threads() says that multiple threads may be active in the process...
Definition: mutex.h:223
Class descriptor.
Definition: opal_object.h:152
#define OPAL_THREAD_UNLOCK(mutex)
Unlock a mutex if opal_using_threads() says that multiple threads may be active in the process...
Definition: mutex.h:309
Definition: ompi_free_list.h:39
Definition: ompi_free_list.h:62
Definition: opal_list.h:147
Compiler-specific prefetch functions.
#define OBJ_CLASS_DECLARATION(NAME)
Declaration for class descriptor.
Definition: opal_object.h:236
mpool module descriptor.
Definition: mpool.h:174