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 */ 70struct free_list { 71 /** Pointer to next free frame */ 72 struct free_list *cdr; 73}; 74 75/** per-worker memory cache */ 76struct __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 */ 125COMMON_PORTABLE 126void *__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 */ 138COMMON_PORTABLE 139void __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 */ 150COMMON_PORTABLE 151void __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 */ 158COMMON_PORTABLE 159void __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 */ 169COMMON_PORTABLE 170void __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 */ 181COMMON_PORTABLE 182size_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 */ 192COMMON_PORTABLE 193size_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 */ 200COMMON_PORTABLE 201void __cilkrts_frame_malloc_global_init(global_state_t *g); 202 203__CILKRTS_END_EXTERN_C 204 205#endif // ! defined(INCLUDED_FRAME_MALLOC_DOT_H) 206