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