root/opal/class/opal_free_list.h

/* [<][>][^][v][top][bottom][index][help] */

INCLUDED FROM


DEFINITIONS

This source file includes following definitions.
  1. opal_free_list_get_mt
  2. opal_free_list_get_st
  3. opal_free_list_get
  4. opal_free_list_wait_mt
  5. opal_free_list_wait_st
  6. opal_free_list_wait
  7. opal_free_list_return_mt
  8. opal_free_list_return_st
  9. opal_free_list_return

   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 

/* [<][>][^][v][top][bottom][index][help] */