libcilkrts/runtime/frame_malloc.h

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