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-2013 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) 2010 IBM Corporation. All rights reserved.
14 * Copyright (c) 2010-2015 Cisco Systems, Inc. All rights reserved.
15 * Copyright (c) 2014-2018 Los Alamos National Security, LLC. All rights
16 * reserved.
17 * $COPYRIGHT$
18 *
19 * Additional copyrights may follow
20 *
21 * $HEADER$
22 */
23
24 #ifndef OPAL_FREE_LIST_H
25 #define OPAL_FREE_LIST_H
26
27 #include "opal_config.h"
28 #include "opal/class/opal_lifo.h"
29 #include "opal/prefetch.h"
30 #include "opal/threads/condition.h"
31 #include "opal/constants.h"
32 #include "opal/runtime/opal.h"
33
34 BEGIN_C_DECLS
35
36 struct mca_mem_pool_t;
37 struct opal_free_list_item_t;
38
39 /**
40 * Free list item initializtion function.
41 *
42 * @param item (IN) Free list item to initialize
43 * @param ctx (IN) Free list initialization context
44 *
45 * @returns OPAL_SUCCESS on success
46 * @returns opal error code on failure
47 *
48 * This function attempts to initialize the free list item
49 * specified in item. If the item can be initialized the
50 * function should return OPAL_SUCCESS. On any error
51 * opal_free_list_grow will stop initializing new items.
52 */
53 typedef int (*opal_free_list_item_init_fn_t) (
54 struct opal_free_list_item_t *item, void *ctx);
55
56 struct opal_free_list_t {
57 /** Items in a free list are stored last-in first-out */
58 opal_lifo_t super;
59 /** Maximum number of items to allocate in the free list */
60 size_t fl_max_to_alloc;
61 /** Current number of items allocated */
62 size_t fl_num_allocated;
63 /** Number of items to allocate when growing the free list */
64 size_t fl_num_per_alloc;
65 /** Number of threads waiting on free list item availability */
66 size_t fl_num_waiting;
67 /** Size of each free list item */
68 size_t fl_frag_size;
69 /** Free list item alignment */
70 size_t fl_frag_alignment;
71 /** Free list item buffer size */
72 size_t fl_payload_buffer_size;
73 /** Free list item buffer alignment */
74 size_t fl_payload_buffer_alignment;
75 /** Class of free list items */
76 opal_class_t *fl_frag_class;
77 /** mpool to use for free list buffer allocation (posix_memalign/malloc
78 * are used if this is NULL) */
79 struct mca_mpool_base_module_t *fl_mpool;
80 /** registration cache */
81 struct mca_rcache_base_module_t *fl_rcache;
82 /** Multi-threaded lock. Used when the free list is empty. */
83 opal_mutex_t fl_lock;
84 /** Multi-threaded condition. Used when threads are waiting on free
85 * list item availability. */
86 opal_condition_t fl_condition;
87 /** List of free list allocation */
88 opal_list_t fl_allocations;
89 /** Flags to pass to the rcache register function */
90 int fl_rcache_reg_flags;
91 /** Free list item initialization function */
92 opal_free_list_item_init_fn_t item_init;
93 /** Initialization function context */
94 void *ctx;
95 };
96 typedef struct opal_free_list_t opal_free_list_t;
97 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_free_list_t);
98
99 struct mca_mpool_base_registration_t;
100 struct opal_free_list_item_t
101 {
102 opal_list_item_t super;
103 struct mca_rcache_base_registration_t *registration;
104 void *ptr;
105 };
106 typedef struct opal_free_list_item_t opal_free_list_item_t;
107 OPAL_DECLSPEC OBJ_CLASS_DECLARATION(opal_free_list_item_t);
108
109
110 /**
111 * Initialize a free list.
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 allocations.
123 * @param rcache_reg_flags (IN) Flags to pass to rcache registration function.
124 * @param rcache (IN) Optional registration cache.
125 * @param item_init (IN) Optional item initialization function
126 * @param ctx (IN) Initialization function context.
127 */
128
129 OPAL_DECLSPEC int opal_free_list_init (opal_free_list_t *free_list,
130 size_t frag_size,
131 size_t frag_alignment,
132 opal_class_t* frag_class,
133 size_t payload_buffer_size,
134 size_t payload_buffer_alignment,
135 int num_elements_to_alloc,
136 int max_elements_to_alloc,
137 int num_elements_per_alloc,
138 struct mca_mpool_base_module_t *mpool,
139 int rcache_reg_flags,
140 struct mca_rcache_base_module_t *rcache,
141 opal_free_list_item_init_fn_t item_init,
142 void *ctx);
143
144 /**
145 * Grow the free list by at most num_elements elements.
146 *
147 * @param flist (IN) Free list to grow
148 * @param num_elements (IN) Number of elements to add
149 * @param item_out (OUT) Location to store new free list item (can be NULL)
150 *
151 * @returns OPAL_SUCCESS if any elements were added
152 * @returns OPAL_ERR_OUT_OF_RESOURCE if no elements could be added
153 *
154 * This function will attempt to grow the free list by num_elements items. The
155 * caller must hold the free list lock if calling this function on a free list
156 * that may be accessed by multiple threads simultaneously. Note: this is an
157 * internal function that will be used when needed by opal_free_list_get* and
158 * opal_free_list_wait*.
159 *
160 * The item_out parameter can be used to ensure that the thread calling this
161 * function always gets a free list item if the list is successfully grown.
162 * This eliminates a race condition with code that simply calls free_list_get
163 * and assumes NULL is an out of memory condition (which it wasn't necessarily
164 * before this parameter was added).
165 */
166 OPAL_DECLSPEC int opal_free_list_grow_st (opal_free_list_t *flist, size_t num_elements, opal_free_list_item_t **item_out);
167
168 /**
169 * Grow the free list to be at least size elements.
170 *
171 * @param flist (IN) Free list to resize.
172 * @param size (IN) New size
173 *
174 * @returns OPAL_SUCCESS if the free list was resized
175 * @returns OPAL_ERR_OUT_OF_RESOURCE if resources could not be allocated
176 *
177 * This function will not shrink the list if it is already larger than size
178 * and may grow it past size if necessary (it will grow in num_elements_per_alloc
179 * chunks). This function is thread-safe and will obtain the free list lock before
180 * growing the free list.
181 */
182 OPAL_DECLSPEC int opal_free_list_resize_mt (opal_free_list_t *flist, size_t size);
183
184
185 /**
186 * Attemp to obtain an item from a free list.
187 *
188 * @param fl (IN) Free list.
189 * @param item (OUT) Allocated item.
190 *
191 * If the requested item is not available the free list is grown to
192 * accomodate the request - unless the max number of allocations has
193 * been reached. If this is the case - a NULL pointer is returned
194 * to the caller. This function comes in three flavor: thread safe
195 * (opal_free_list_get_mt), single threaded (opal_free_list_get_st),
196 * and opal_using_threads conditioned (opal_free_list_get).
197 */
198 static inline opal_free_list_item_t *opal_free_list_get_mt (opal_free_list_t *flist)
199 {
200 opal_free_list_item_t *item =
201 (opal_free_list_item_t*) opal_lifo_pop_atomic (&flist->super);
202
203 if (OPAL_UNLIKELY(NULL == item)) {
204 opal_mutex_lock (&flist->fl_lock);
205 opal_free_list_grow_st (flist, flist->fl_num_per_alloc, &item);
206 opal_mutex_unlock (&flist->fl_lock);
207 }
208
209 return item;
210 }
211
212 static inline opal_free_list_item_t *opal_free_list_get_st (opal_free_list_t *flist)
213 {
214 opal_free_list_item_t *item =
215 (opal_free_list_item_t*) opal_lifo_pop_st (&flist->super);
216
217 if (OPAL_UNLIKELY(NULL == item)) {
218 opal_free_list_grow_st (flist, flist->fl_num_per_alloc, &item);
219 }
220
221 return item;
222 }
223
224 static inline opal_free_list_item_t *opal_free_list_get (opal_free_list_t *flist)
225 {
226 if (opal_using_threads ()) {
227 return opal_free_list_get_mt (flist);
228 }
229
230 return opal_free_list_get_st (flist);
231 }
232
233 /** compatibility macro */
234 #define OPAL_FREE_LIST_GET(fl, item) \
235 (item) = opal_free_list_get (fl)
236
237 /**
238 * Blocking call to obtain an item from a free list.
239 *
240 * @param fl (IN) Free list.
241 * @param item (OUT) Allocated item.
242 *
243 * If the requested item is not available the free list is grown to
244 * accomodate the request - unless the max number of allocations has
245 * been reached. In this case the caller is blocked until an item
246 * is returned to the list.
247 */
248
249 /** compatibility macro */
250 #define OPAL_FREE_LIST_WAIT(fl, item) \
251 (item) = opal_free_list_wait (fl)
252
253 static inline opal_free_list_item_t *opal_free_list_wait_mt (opal_free_list_t *fl)
254 {
255 opal_free_list_item_t *item =
256 (opal_free_list_item_t *) opal_lifo_pop_atomic (&fl->super);
257
258 while (NULL == item) {
259 if (!opal_mutex_trylock (&fl->fl_lock)) {
260 if (fl->fl_max_to_alloc <= fl->fl_num_allocated ||
261 OPAL_SUCCESS != opal_free_list_grow_st (fl, fl->fl_num_per_alloc, &item)) {
262 fl->fl_num_waiting++;
263 opal_condition_wait (&fl->fl_condition, &fl->fl_lock);
264 fl->fl_num_waiting--;
265 } else {
266 if (0 < fl->fl_num_waiting) {
267 if (1 == fl->fl_num_waiting) {
268 opal_condition_signal (&fl->fl_condition);
269 } else {
270 opal_condition_broadcast (&fl->fl_condition);
271 }
272 }
273 }
274 } else {
275 /* If I wasn't able to get the lock in the begining when I finaly grab it
276 * the one holding the lock in the begining already grow the list. I will
277 * release the lock and try to get a new element until I succeed.
278 */
279 opal_mutex_lock (&fl->fl_lock);
280 }
281 opal_mutex_unlock (&fl->fl_lock);
282 if (NULL == item) {
283 item = (opal_free_list_item_t *) opal_lifo_pop_atomic (&fl->super);
284 }
285 }
286
287 return item;
288 }
289
290 static inline opal_free_list_item_t *opal_free_list_wait_st (opal_free_list_t *fl)
291 {
292 opal_free_list_item_t *item =
293 (opal_free_list_item_t *) opal_lifo_pop (&fl->super);
294
295 while (NULL == item) {
296 if (fl->fl_max_to_alloc <= fl->fl_num_allocated ||
297 OPAL_SUCCESS != opal_free_list_grow_st (fl, fl->fl_num_per_alloc, &item)) {
298 /* try to make progress */
299 opal_progress ();
300 }
301 if (NULL == item) {
302 item = (opal_free_list_item_t *) opal_lifo_pop (&fl->super);
303 }
304 }
305
306 return item;
307 }
308
309 static inline opal_free_list_item_t *opal_free_list_wait (opal_free_list_t *fl)
310 {
311 if (opal_using_threads ()) {
312 return opal_free_list_wait_mt (fl);
313 } else {
314 return opal_free_list_wait_st (fl);
315 }
316 }
317
318 /**
319 * Return an item to a free list.
320 *
321 * @param fl (IN) Free list.
322 * @param item (OUT) Allocated item.
323 *
324 */
325 static inline void opal_free_list_return_mt (opal_free_list_t *flist,
326 opal_free_list_item_t *item)
327 {
328 opal_list_item_t* original;
329
330 original = opal_lifo_push_atomic (&flist->super, &item->super);
331 if (&flist->super.opal_lifo_ghost == original) {
332 if (flist->fl_num_waiting > 0) {
333 /* one one item is being returned so it doesn't make sense to wake
334 * more than a single waiting thread. additionally, posix thread
335 * semantics do not require that the lock be held to signal the
336 * condition variable. */
337 opal_condition_signal (&flist->fl_condition);
338 }
339 }
340 }
341
342 static inline void opal_free_list_return_st (opal_free_list_t *flist,
343 opal_free_list_item_t *item)
344 {
345 opal_list_item_t* original;
346
347 original = opal_lifo_push_st (&flist->super, &item->super);
348 if (&flist->super.opal_lifo_ghost == original) {
349 if (flist->fl_num_waiting > 0) {
350 /* one one item is being returned so it doesn't make sense to wake
351 * more than a single waiting thread. additionally, posix thread
352 * semantics do not require that the lock be held to signal the
353 * condition variable. */
354 opal_condition_signal (&flist->fl_condition);
355 }
356 }
357 }
358
359 static inline void opal_free_list_return (opal_free_list_t *flist,
360 opal_free_list_item_t *item)
361 {
362 if (opal_using_threads ()) {
363 opal_free_list_return_mt (flist, item);
364 } else {
365 opal_free_list_return_st (flist, item);
366 }
367 }
368
369 /** compatibility macro */
370 #define OPAL_FREE_LIST_RETURN(fl, item) \
371 opal_free_list_return (fl, item)
372
373 END_C_DECLS
374 #endif
375