libcilkrts/runtime/frame_malloc.h

   1 /* frame_malloc.h                  -*-C++-*-
   2  *
   3  *************************************************************************
   4  *
   5  *  @copyright
   6  *  Copyright (C) 2009-2013, Intel Corporation
   7  *  All rights reserved.
   8  *
   9  *  @copyright
  10  *  Redistribution and use in source and binary forms, with or without
  11  *  modification, are permitted provided that the following conditions
  12  *  are met:
  13  *
  14  *    * Redistributions of source code must retain the above copyright
  15  *      notice, this list of conditions and the following disclaimer.
  16  *    * Redistributions in binary form must reproduce the above copyright
  17  *      notice, this list of conditions and the following disclaimer in
  18  *      the documentation and/or other materials provided with the
  19  *      distribution.
  20  *    * Neither the name of Intel Corporation nor the names of its
  21  *      contributors may be used to endorse or promote products derived
  22  *      from this software without specific prior written permission.
  23  *
  24  *  @copyright
  25  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  *  "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  *  LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  28  *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  29  *  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  30  *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  31  *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
  32  *  OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  33  *  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  *  LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
  35  *  WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  36  *  POSSIBILITY OF SUCH DAMAGE.
  37  **************************************************************************/
  38
  39 /**
  40  * @file frame_malloc.h
  41  *
  42  * @brief The frame allocation routines manage memory in a per-worker pool.
  43  *
  44  * The name "frame malloc" refers to an earlier implementation of Cilk which
  45  * allocated frames from the heap using this allocator.
  46  */
  47
  48 #ifndef INCLUDED_FRAME_MALLOC_DOT_H
  49 #define INCLUDED_FRAME_MALLOC_DOT_H
  50
  51 #include "worker_mutex.h"
  52 #include "rts-common.h"
  53 #include <internal/abi.h>  // __cilkrts_worker
  54
  55 #ifdef __cplusplus
  56 #   include <cstddef>
  57 #else
  58 #   include <stddef.h>
  59 #endif
  60
  61 __CILKRTS_BEGIN_EXTERN_C
  62
  63 /**
  64  * Number of buckets.  Gives us buckets to hold  64, 128, 256, 512, 1024
  65  * and 2048 bytes
  66  */
  67 #define FRAME_MALLOC_NBUCKETS 6
  68
  69 /** Layout of frames when unallocated */
  70 struct free_list {
  71      /** Pointer to next free frame */
  72      struct free_list *cdr;
  73 };
  74
  75 /** per-worker memory cache */
  76 struct __cilkrts_frame_cache
  77 {
  78     /** Mutex to serialize access */
  79     struct mutex lock;
  80
  81     /** Linked list of frames */
  82     struct pool_cons *pool_list;
  83
  84     /** Low bound of memory in pool */
  85     char *pool_begin;
  86
  87     /** High bound of memory in pool */
  88     char *pool_end;
  89
  90     /** Global free-list buckets */
  91     struct free_list *global_free_list[FRAME_MALLOC_NBUCKETS];
  92
  93     /**
  94      * How many bytes to obtain at once from the global pool
  95      * (approximately)
  96      */
  97     size_t batch_size;
  98
  99     /** Garbage-collect a bucket when its potential exceeds the limit */
 100     size_t potential_limit;
 101
 102     /** If TRUE, check for memory leaks at the end of execution */
 103     int check_for_leaks;
 104
 105     /** Bytes of memory allocated from the OS by the global cache */
 106     size_t allocated_from_os;
 107
 108     /** Tracks memory allocated by a chunk that isn't a full bucket size */
 109     size_t wasted;
 110
 111     /** Bytes of memory allocated from the global cache */
 112     size_t allocated_from_global_pool;
 113 };
 114
 115 /**
 116  * Allocate memory from the per-worker pool. If the size is too large, or
 117  * if we're given a NULL worker, the memory is allocated using
 118  * __cilkrts_malloc().
 119  *
 120  * @param w The worker to allocate the memory from.
 121  * @param size The number of bytes to allocate.
 122  *
 123  * @return pointer to allocated memory block.
 124  */
 125 COMMON_PORTABLE
 126 void *__cilkrts_frame_malloc(__cilkrts_worker *w,
 127                              size_t size) cilk_nothrow;
 128
 129 /**
 130  * Return memory to the per-worker pool. If the size is too large, or
 131  * if we're given a NULL worker, the memory is freed using
 132  * __cilkrts_free().
 133  *
 134  * @param w The worker to allocate the memory from.
 135  * @param p The memory block to be released.
 136  * @param size The size of the block, in bytes.
 137  */
 138 COMMON_PORTABLE
 139 void __cilkrts_frame_free(__cilkrts_worker *w,
 140                           void*  p,
 141                           size_t size) cilk_nothrow;
 142
 143 /**
 144  * Destroy the global cache stored in the global state, freeing all memory
 145  * to the global heap.  Checks whether any memory has been allocated but
 146  * not freed.
 147  *
 148  * @param g The global state.
 149  */
 150 COMMON_PORTABLE
 151 void __cilkrts_frame_malloc_global_cleanup(global_state_t *g);
 152
 153 /**
 154  * Initialize a worker's memory cache.  Initially it is empty.
 155  *
 156  * @param w The worker who's memory cache is to be initialized.
 157  */
 158 COMMON_PORTABLE
 159 void __cilkrts_frame_malloc_per_worker_init(__cilkrts_worker *w);
 160
 161 /**
 162  * If check_for_leaks is set in the global state's memory cache, free any
 163  * memory in the worker's memory cache.
 164  *
 165  * If check_for_leask is not set, nothing happens.
 166  *
 167  * @param w The worker who's memory cache is to be cleaned up.
 168  */
 169 COMMON_PORTABLE
 170 void __cilkrts_frame_malloc_per_worker_cleanup(__cilkrts_worker *w);
 171
 172 /**
 173  * Round a number of bytes to the size of the smallest bucket that will
 174  * hold it.  If the size is bigger than the largest bucket, the value is
 175  * unchanged.
 176  *
 177  * @param size Number of bytes to be rounded up to the nearest bucket size.
 178  *
 179  * @return The size of the smallest bucket that will hold the specified bytes.
 180  */
 181 COMMON_PORTABLE
 182 size_t __cilkrts_frame_malloc_roundup(size_t size) cilk_nothrow;
 183
 184 /**
 185  * Return the number of bytes that can fit into a bucket.
 186  *
 187  * Preconditions:
 188  *  - The index must be in the range 0 - FRAME_MALLOC_NBUCKETS
 189  *
 190  * @param bucket Index of the bucket to be sized.
 191  */
 192 COMMON_PORTABLE
 193 size_t __cilkrts_size_of_bucket(int bucket) cilk_nothrow;
 194
 195 /**
 196  * Initialize the global memory cache.
 197  *
 198  * @param g The global state.
 199  */
 200 COMMON_PORTABLE
 201 void __cilkrts_frame_malloc_global_init(global_state_t *g);
 202
 203 __CILKRTS_END_EXTERN_C
 204
 205 #endif // ! defined(INCLUDED_FRAME_MALLOC_DOT_H)