Rev 4642 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 4642 | Rev 4643 | ||
---|---|---|---|
1 | /* |
1 | /* |
2 | * Copyright (c) 2009 Martin Decky |
2 | * Copyright (c) 2009 Martin Decky |
3 | * Copyright (c) 2009 Petr Tuma |
3 | * Copyright (c) 2009 Petr Tuma |
4 | * All rights reserved. |
4 | * All rights reserved. |
5 | * |
5 | * |
6 | * Redistribution and use in source and binary forms, with or without |
6 | * Redistribution and use in source and binary forms, with or without |
7 | * modification, are permitted provided that the following conditions |
7 | * modification, are permitted provided that the following conditions |
8 | * are met: |
8 | * are met: |
9 | * |
9 | * |
10 | * - Redistributions of source code must retain the above copyright |
10 | * - Redistributions of source code must retain the above copyright |
11 | * notice, this list of conditions and the following disclaimer. |
11 | * notice, this list of conditions and the following disclaimer. |
12 | * - Redistributions in binary form must reproduce the above copyright |
12 | * - Redistributions in binary form must reproduce the above copyright |
13 | * notice, this list of conditions and the following disclaimer in the |
13 | * notice, this list of conditions and the following disclaimer in the |
14 | * documentation and/or other materials provided with the distribution. |
14 | * documentation and/or other materials provided with the distribution. |
15 | * - The name of the author may not be used to endorse or promote products |
15 | * - The name of the author may not be used to endorse or promote products |
16 | * derived from this software without specific prior written permission. |
16 | * derived from this software without specific prior written permission. |
17 | * |
17 | * |
18 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
18 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
19 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
19 | * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
20 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
20 | * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
21 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
21 | * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
22 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
22 | * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
23 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
24 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 | * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
25 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 | * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
27 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
28 | */ |
28 | */ |
29 | 29 | ||
30 | /** @addtogroup libc |
30 | /** @addtogroup libc |
31 | * @{ |
31 | * @{ |
32 | */ |
32 | */ |
33 | /** @file |
33 | /** @file |
34 | */ |
34 | */ |
35 | 35 | ||
36 | #include <malloc.h> |
36 | #include <malloc.h> |
37 | #include <bool.h> |
37 | #include <bool.h> |
38 | #include <as.h> |
38 | #include <as.h> |
39 | #include <align.h> |
39 | #include <align.h> |
40 | #include <macros.h> |
40 | #include <macros.h> |
41 | #include <assert.h> |
41 | #include <assert.h> |
42 | #include <errno.h> |
42 | #include <errno.h> |
43 | #include <bitops.h> |
43 | #include <bitops.h> |
44 | #include <mem.h> |
44 | #include <mem.h> |
45 | #include <adt/gcdlcm.h> |
45 | #include <adt/gcdlcm.h> |
46 | 46 | ||
47 | /* Magic used in heap headers. */ |
47 | /* Magic used in heap headers. */ |
48 | #define HEAP_BLOCK_HEAD_MAGIC 0xBEEF0101 |
48 | #define HEAP_BLOCK_HEAD_MAGIC 0xBEEF0101 |
49 | 49 | ||
50 | /* Magic used in heap footers. */ |
50 | /* Magic used in heap footers. */ |
51 | #define HEAP_BLOCK_FOOT_MAGIC 0xBEEF0202 |
51 | #define HEAP_BLOCK_FOOT_MAGIC 0xBEEF0202 |
52 | 52 | ||
53 | /** Allocation alignment (this also covers the alignment of fields |
53 | /** Allocation alignment (this also covers the alignment of fields |
54 | in the heap header and footer) */ |
54 | in the heap header and footer) */ |
55 | #define BASE_ALIGN 16 |
55 | #define BASE_ALIGN 16 |
56 | 56 | ||
57 | /** |
57 | /** |
58 | * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures |
58 | * Either 4 * 256M on 32-bit architecures or 16 * 256M on 64-bit architectures |
59 | */ |
59 | */ |
60 | #define MAX_HEAP_SIZE (sizeof(uintptr_t) << 28) |
60 | #define MAX_HEAP_SIZE (sizeof(uintptr_t) << 28) |
61 | 61 | ||
62 | /** |
62 | /** |
63 | * |
63 | * |
64 | */ |
64 | */ |
65 | #define STRUCT_OVERHEAD (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) |
65 | #define STRUCT_OVERHEAD (sizeof(heap_block_head_t) + sizeof(heap_block_foot_t)) |
66 | 66 | ||
67 | /** |
67 | /** |
68 | * Calculate real size of a heap block (with header and footer) |
68 | * Calculate real size of a heap block (with header and footer) |
69 | */ |
69 | */ |
70 | #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) |
70 | #define GROSS_SIZE(size) ((size) + STRUCT_OVERHEAD) |
71 | 71 | ||
72 | /** |
72 | /** |
73 | * Calculate net size of a heap block (without header and footer) |
73 | * Calculate net size of a heap block (without header and footer) |
74 | */ |
74 | */ |
75 | #define NET_SIZE(size) ((size) - STRUCT_OVERHEAD) |
75 | #define NET_SIZE(size) ((size) - STRUCT_OVERHEAD) |
76 | 76 | ||
77 | 77 | ||
78 | /** Header of a heap block |
78 | /** Header of a heap block |
79 | * |
79 | * |
80 | */ |
80 | */ |
81 | typedef struct { |
81 | typedef struct { |
82 | /* Size of the block (including header and footer) */ |
82 | /* Size of the block (including header and footer) */ |
83 | size_t size; |
83 | size_t size; |
84 | 84 | ||
85 | /* Indication of a free block */ |
85 | /* Indication of a free block */ |
86 | bool free; |
86 | bool free; |
87 | 87 | ||
88 | /* A magic value to detect overwrite of heap header */ |
88 | /* A magic value to detect overwrite of heap header */ |
89 | uint32_t magic; |
89 | uint32_t magic; |
90 | } heap_block_head_t; |
90 | } heap_block_head_t; |
91 | 91 | ||
92 | /** Footer of a heap block |
92 | /** Footer of a heap block |
93 | * |
93 | * |
94 | */ |
94 | */ |
95 | typedef struct { |
95 | typedef struct { |
96 | /* Size of the block (including header and footer) */ |
96 | /* Size of the block (including header and footer) */ |
97 | size_t size; |
97 | size_t size; |
98 | 98 | ||
99 | /* A magic value to detect overwrite of heap footer */ |
99 | /* A magic value to detect overwrite of heap footer */ |
100 | uint32_t magic; |
100 | uint32_t magic; |
101 | } heap_block_foot_t; |
101 | } heap_block_foot_t; |
102 | 102 | ||
103 | /** Linker heap symbol */ |
103 | /** Linker heap symbol */ |
104 | extern char _heap; |
104 | extern char _heap; |
105 | 105 | ||
106 | /** Address of heap start */ |
106 | /** Address of heap start */ |
107 | static void *heap_start = 0; |
107 | static void *heap_start = 0; |
108 | 108 | ||
109 | /** Address of heap end */ |
109 | /** Address of heap end */ |
110 | static void *heap_end = 0; |
110 | static void *heap_end = 0; |
111 | 111 | ||
112 | /** Maximum heap size */ |
112 | /** Maximum heap size */ |
113 | static size_t max_heap_size = (size_t) -1; |
113 | static size_t max_heap_size = (size_t) -1; |
114 | 114 | ||
115 | /** Current number of pages of heap area */ |
115 | /** Current number of pages of heap area */ |
116 | static size_t heap_pages = 0; |
116 | static size_t heap_pages = 0; |
117 | 117 | ||
118 | /** Initialize a heap block |
118 | /** Initialize a heap block |
119 | * |
119 | * |
120 | * Fills in the structures related to a heap block. |
120 | * Fills in the structures related to a heap block. |
121 | * |
121 | * |
122 | * @param addr Address of the block. |
122 | * @param addr Address of the block. |
123 | * @param size Size of the block including the header and the footer. |
123 | * @param size Size of the block including the header and the footer. |
124 | * @param free Indication of a free block. |
124 | * @param free Indication of a free block. |
125 | * |
125 | * |
126 | */ |
126 | */ |
127 | static void block_init(void *addr, size_t size, bool free) |
127 | static void block_init(void *addr, size_t size, bool free) |
128 | { |
128 | { |
129 | /* Calculate the position of the header and the footer */ |
129 | /* Calculate the position of the header and the footer */ |
130 | heap_block_head_t *head = (heap_block_head_t *) addr; |
130 | heap_block_head_t *head = (heap_block_head_t *) addr; |
131 | heap_block_foot_t *foot = |
131 | heap_block_foot_t *foot = |
132 | (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t)); |
132 | (heap_block_foot_t *) (addr + size - sizeof(heap_block_foot_t)); |
133 | 133 | ||
134 | head->size = size; |
134 | head->size = size; |
135 | head->free = free; |
135 | head->free = free; |
136 | head->magic = HEAP_BLOCK_HEAD_MAGIC; |
136 | head->magic = HEAP_BLOCK_HEAD_MAGIC; |
137 | 137 | ||
138 | foot->size = size; |
138 | foot->size = size; |
139 | foot->magic = HEAP_BLOCK_FOOT_MAGIC; |
139 | foot->magic = HEAP_BLOCK_FOOT_MAGIC; |
140 | } |
140 | } |
141 | 141 | ||
142 | /** Check a heap block |
142 | /** Check a heap block |
143 | * |
143 | * |
144 | * Verifies that the structures related to a heap block still contain |
144 | * Verifies that the structures related to a heap block still contain |
145 | * the magic constants. This helps detect heap corruption early on. |
145 | * the magic constants. This helps detect heap corruption early on. |
146 | * |
146 | * |
147 | * @param addr Address of the block. |
147 | * @param addr Address of the block. |
148 | * |
148 | * |
149 | */ |
149 | */ |
150 | static void block_check(void *addr) |
150 | static void block_check(void *addr) |
151 | { |
151 | { |
152 | heap_block_head_t *head = (heap_block_head_t *) addr; |
152 | heap_block_head_t *head = (heap_block_head_t *) addr; |
153 | 153 | ||
154 | assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); |
154 | assert(head->magic == HEAP_BLOCK_HEAD_MAGIC); |
155 | 155 | ||
156 | heap_block_foot_t *foot = |
156 | heap_block_foot_t *foot = |
157 | (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); |
157 | (heap_block_foot_t *) (addr + head->size - sizeof(heap_block_foot_t)); |
158 | 158 | ||
159 | assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); |
159 | assert(foot->magic == HEAP_BLOCK_FOOT_MAGIC); |
160 | assert(head->size == foot->size); |
160 | assert(head->size == foot->size); |
161 | } |
161 | } |
162 | 162 | ||
163 | static bool grow_heap(size_t size) |
163 | static bool grow_heap(size_t size) |
164 | { |
164 | { |
165 | if (size == 0) |
165 | if (size == 0) |
166 | return false; |
166 | return false; |
167 | 167 | ||
168 | size_t heap_size = (size_t) (heap_end - heap_start); |
168 | size_t heap_size = (size_t) (heap_end - heap_start); |
169 | 169 | ||
170 | if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size)) |
170 | if ((max_heap_size != (size_t) -1) && (heap_size + size > max_heap_size)) |
171 | return false; |
171 | return false; |
172 | 172 | ||
173 | size_t pages = (size - 1) / PAGE_SIZE + 1; |
173 | size_t pages = (size - 1) / PAGE_SIZE + 1; |
174 | 174 | ||
175 | if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0) |
175 | if (as_area_resize((void *) &_heap, (heap_pages + pages) * PAGE_SIZE, 0) |
176 | == EOK) { |
176 | == EOK) { |
177 | void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) + |
177 | void *end = (void *) ALIGN_DOWN(((uintptr_t) &_heap) + |
178 | (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN); |
178 | (heap_pages + pages) * PAGE_SIZE, BASE_ALIGN); |
179 | block_init(heap_end, end - heap_end, true); |
179 | block_init(heap_end, end - heap_end, true); |
180 | heap_pages += pages; |
180 | heap_pages += pages; |
181 | heap_end = end; |
181 | heap_end = end; |
182 | return true; |
182 | return true; |
183 | } |
183 | } |
184 | 184 | ||
185 | return false; |
185 | return false; |
186 | } |
186 | } |
187 | 187 | ||
188 | static void shrink_heap(void) |
188 | static void shrink_heap(void) |
189 | { |
189 | { |
190 | // TODO |
190 | // TODO |
191 | } |
191 | } |
192 | 192 | ||
193 | /** Initialize the heap allocator |
193 | /** Initialize the heap allocator |
194 | * |
194 | * |
195 | * Finds how much physical memory we have and creates |
195 | * Finds how much physical memory we have and creates |
196 | * the heap management structures that mark the whole |
196 | * the heap management structures that mark the whole |
197 | * physical memory as a single free block. |
197 | * physical memory as a single free block. |
198 | * |
198 | * |
199 | */ |
199 | */ |
200 | void __heap_init(void) |
200 | void __heap_init(void) |
201 | { |
201 | { |
202 | if (as_area_create((void *) &_heap, PAGE_SIZE, |
202 | if (as_area_create((void *) &_heap, PAGE_SIZE, |
203 | AS_AREA_WRITE | AS_AREA_READ)) { |
203 | AS_AREA_WRITE | AS_AREA_READ)) { |
204 | heap_pages = 1; |
204 | heap_pages = 1; |
205 | heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN); |
205 | heap_start = (void *) ALIGN_UP((uintptr_t) &_heap, BASE_ALIGN); |
206 | heap_end = |
206 | heap_end = |
207 | (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN); |
207 | (void *) ALIGN_DOWN(((uintptr_t) &_heap) + PAGE_SIZE, BASE_ALIGN); |
208 | 208 | ||
209 | /* Make the entire area one large block. */ |
209 | /* Make the entire area one large block. */ |
210 | block_init(heap_start, heap_end - heap_start, true); |
210 | block_init(heap_start, heap_end - heap_start, true); |
211 | } |
211 | } |
212 | } |
212 | } |
213 | 213 | ||
214 | uintptr_t get_max_heap_addr(void) |
214 | uintptr_t get_max_heap_addr(void) |
215 | { |
215 | { |
216 | if (max_heap_size == (size_t) -1) |
216 | if (max_heap_size == (size_t) -1) |
217 | max_heap_size = |
217 | max_heap_size = |
218 | max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE); |
218 | max((size_t) (heap_end - heap_start), MAX_HEAP_SIZE); |
219 | 219 | ||
220 | return ((uintptr_t) heap_start + max_heap_size); |
220 | return ((uintptr_t) heap_start + max_heap_size); |
221 | } |
221 | } |
222 | 222 | ||
223 | static void split_mark(heap_block_head_t *cur, const size_t size) |
223 | static void split_mark(heap_block_head_t *cur, const size_t size) |
224 | { |
224 | { |
225 | assert(cur->size >= size); |
225 | assert(cur->size >= size); |
226 | 226 | ||
227 | /* See if we should split the block. */ |
227 | /* See if we should split the block. */ |
228 | size_t split_limit = GROSS_SIZE(size); |
228 | size_t split_limit = GROSS_SIZE(size); |
229 | 229 | ||
230 | if (cur->size > split_limit) { |
230 | if (cur->size > split_limit) { |
231 | /* Block big enough -> split. */ |
231 | /* Block big enough -> split. */ |
232 | void *next = ((void *) cur) + size; |
232 | void *next = ((void *) cur) + size; |
233 | block_init(next, cur->size - size, true); |
233 | block_init(next, cur->size - size, true); |
234 | block_init(cur, size, false); |
234 | block_init(cur, size, false); |
235 | } else { |
235 | } else { |
236 | /* Block too small -> use as is. */ |
236 | /* Block too small -> use as is. */ |
237 | cur->free = false; |
237 | cur->free = false; |
238 | } |
238 | } |
239 | } |
239 | } |
240 | 240 | ||
241 | /** Allocate a memory block |
241 | /** Allocate a memory block |
242 | * |
242 | * |
243 | * @param size The size of the block to allocate. |
243 | * @param size The size of the block to allocate. |
244 | * @param align Memory address alignment. |
244 | * @param align Memory address alignment. |
245 | * |
245 | * |
246 | * @return the address of the block or NULL when not enough memory. |
246 | * @return the address of the block or NULL when not enough memory. |
247 | * |
247 | * |
248 | */ |
248 | */ |
249 | static void *malloc_internal(const size_t size, const size_t align) |
249 | static void *malloc_internal(const size_t size, const size_t align) |
250 | { |
250 | { |
251 | if (align == 0) |
251 | if (align == 0) |
252 | return NULL; |
252 | return NULL; |
253 | 253 | ||
254 | size_t falign = lcm(align, BASE_ALIGN); |
254 | size_t falign = lcm(align, BASE_ALIGN); |
255 | size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); |
255 | size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign)); |
256 | 256 | ||
257 | bool grown = false; |
257 | bool grown = false; |
258 | void *result; |
258 | void *result; |
259 | 259 | ||
260 | loop: |
260 | loop: |
261 | result = NULL; |
261 | result = NULL; |
262 | heap_block_head_t *cur = (heap_block_head_t *) heap_start; |
262 | heap_block_head_t *cur = (heap_block_head_t *) heap_start; |
263 | 263 | ||
264 | while ((result == NULL) && ((void *) cur < heap_end)) { |
264 | while ((result == NULL) && ((void *) cur < heap_end)) { |
265 | block_check(cur); |
265 | block_check(cur); |
266 | 266 | ||
267 | /* Try to find a block that is free and large enough. */ |
267 | /* Try to find a block that is free and large enough. */ |
268 | if ((cur->free) && (cur->size >= real_size)) { |
268 | if ((cur->free) && (cur->size >= real_size)) { |
269 | /* We have found a suitable block. |
269 | /* We have found a suitable block. |
270 | Check for alignment properties. */ |
270 | Check for alignment properties. */ |
271 | void *addr = ((void *) cur) + sizeof(heap_block_head_t); |
271 | void *addr = ((void *) cur) + sizeof(heap_block_head_t); |
272 | void *aligned = (void *) ALIGN_UP(addr, falign); |
272 | void *aligned = (void *) ALIGN_UP(addr, falign); |
273 | 273 | ||
274 | if (addr == aligned) { |
274 | if (addr == aligned) { |
275 | /* Exact block start including alignment. */ |
275 | /* Exact block start including alignment. */ |
276 | split_mark(cur, real_size); |
276 | split_mark(cur, real_size); |
277 | result = addr; |
277 | result = addr; |
278 | } else { |
278 | } else { |
279 | /* Block start has to be aligned */ |
279 | /* Block start has to be aligned */ |
280 | size_t excess = (size_t) (aligned - addr); |
280 | size_t excess = (size_t) (aligned - addr); |
281 | 281 | ||
282 | if (cur->size >= real_size + excess) { |
282 | if (cur->size >= real_size + excess) { |
283 | /* The current block is large enough to fit |
283 | /* The current block is large enough to fit |
284 | data in including alignment */ |
284 | data in including alignment */ |
285 | if ((void *) cur > heap_start) { |
285 | if ((void *) cur > heap_start) { |
286 | /* There is a block before the current block. |
286 | /* There is a block before the current block. |
287 | This previous block can be enlarged to compensate |
287 | This previous block can be enlarged to compensate |
288 | for the alignment excess */ |
288 | for the alignment excess */ |
289 | heap_block_foot_t *prev_foot = |
289 | heap_block_foot_t *prev_foot = |
290 | ((void *) cur) - sizeof(heap_block_foot_t); |
290 | ((void *) cur) - sizeof(heap_block_foot_t); |
291 | 291 | ||
292 | heap_block_head_t *prev_head = |
292 | heap_block_head_t *prev_head = |
293 | (heap_block_head_t *) (((void *) cur) - prev_foot->size); |
293 | (heap_block_head_t *) (((void *) cur) - prev_foot->size); |
294 | 294 | ||
295 | block_check(prev_head); |
295 | block_check(prev_head); |
296 | 296 | ||
297 | size_t reduced_size = cur->size - excess; |
297 | size_t reduced_size = cur->size - excess; |
298 | heap_block_head_t *next_head = ((void *) cur) + excess; |
298 | heap_block_head_t *next_head = ((void *) cur) + excess; |
299 | 299 | ||
300 | if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) { |
300 | if ((!prev_head->free) && (excess >= STRUCT_OVERHEAD)) { |
301 | /* The previous block is not free and there is enough |
301 | /* The previous block is not free and there is enough |
302 | space to fill in a new free block between the previous |
302 | space to fill in a new free block between the previous |
303 | and current block */ |
303 | and current block */ |
304 | block_init(cur, excess, true); |
304 | block_init(cur, excess, true); |
305 | } else { |
305 | } else { |
306 | /* The previous block is free (thus there is no need to |
306 | /* The previous block is free (thus there is no need to |
307 | induce additional fragmentation to the heap) or the |
307 | induce additional fragmentation to the heap) or the |
308 | excess is small, thus just enlarge the previous block */ |
308 | excess is small, thus just enlarge the previous block */ |
309 | block_init(prev_head, prev_head->size + excess, prev_head->free); |
309 | block_init(prev_head, prev_head->size + excess, prev_head->free); |
310 | } |
310 | } |
311 | 311 | ||
312 | block_init(next_head, reduced_size, true); |
312 | block_init(next_head, reduced_size, true); |
313 | split_mark(next_head, real_size); |
313 | split_mark(next_head, real_size); |
314 | result = aligned; |
314 | result = aligned; |
315 | cur = next_head; |
315 | cur = next_head; |
316 | } else { |
316 | } else { |
317 | /* The current block is the first block on the heap. |
317 | /* The current block is the first block on the heap. |
318 | We have to make sure that the alignment excess |
318 | We have to make sure that the alignment excess |
319 | is large enough to fit a new free block just |
319 | is large enough to fit a new free block just |
320 | before the current block */ |
320 | before the current block */ |
321 | while (excess < STRUCT_OVERHEAD) { |
321 | while (excess < STRUCT_OVERHEAD) { |
322 | aligned += falign; |
322 | aligned += falign; |
323 | excess += falign; |
323 | excess += falign; |
324 | } |
324 | } |
325 | 325 | ||
326 | /* Check for current block size again */ |
326 | /* Check for current block size again */ |
327 | if (cur->size >= real_size + excess) { |
327 | if (cur->size >= real_size + excess) { |
328 | size_t reduced_size = cur->size - excess; |
328 | size_t reduced_size = cur->size - excess; |
329 | cur = (heap_block_head_t *) (heap_start + excess); |
329 | cur = (heap_block_head_t *) (heap_start + excess); |
330 | 330 | ||
331 | block_init(heap_start, excess, true); |
331 | block_init(heap_start, excess, true); |
332 | block_init(cur, reduced_size, true); |
332 | block_init(cur, reduced_size, true); |
333 | split_mark(cur, real_size); |
333 | split_mark(cur, real_size); |
334 | result = aligned; |
334 | result = aligned; |
335 | } |
335 | } |
336 | } |
336 | } |
337 | } |
337 | } |
338 | } |
338 | } |
339 | } |
339 | } |
340 | 340 | ||
341 | /* Advance to the next block. */ |
341 | /* Advance to the next block. */ |
342 | cur = (heap_block_head_t *) (((void *) cur) + cur->size); |
342 | cur = (heap_block_head_t *) (((void *) cur) + cur->size); |
343 | } |
343 | } |
344 | 344 | ||
345 | if ((result == NULL) && (!grown)) { |
345 | if ((result == NULL) && (!grown)) { |
346 | if (grow_heap(real_size)) { |
346 | if (grow_heap(real_size)) { |
347 | grown = true; |
347 | grown = true; |
348 | goto loop; |
348 | goto loop; |
349 | } |
349 | } |
350 | } |
350 | } |
351 | 351 | ||
352 | return result; |
352 | return result; |
353 | } |
353 | } |
354 | 354 | ||
355 | void *malloc(const size_t size) |
355 | void *malloc(const size_t size) |
356 | { |
356 | { |
357 | return malloc_internal(size, BASE_ALIGN); |
357 | return malloc_internal(size, BASE_ALIGN); |
358 | } |
358 | } |
359 | 359 | ||
360 | void *memalign(const size_t align, const size_t size) |
360 | void *memalign(const size_t align, const size_t size) |
361 | { |
361 | { |
362 | if (align == 0) |
362 | if (align == 0) |
363 | return NULL; |
363 | return NULL; |
364 | 364 | ||
365 | size_t palign = |
365 | size_t palign = |
366 | 1 << (fnzb(max(sizeof(void *), align) - 1) + 1); |
366 | 1 << (fnzb(max(sizeof(void *), align) - 1) + 1); |
367 | 367 | ||
368 | return malloc_internal(size, palign); |
368 | return malloc_internal(size, palign); |
369 | } |
369 | } |
370 | 370 | ||
371 | void *realloc(const void *addr, const size_t size) |
371 | void *realloc(const void *addr, const size_t size) |
372 | { |
372 | { |
373 | if (addr == NULL) |
373 | if (addr == NULL) |
374 | return malloc(size); |
374 | return malloc(size); |
375 | 375 | ||
376 | /* Calculate the position of the header. */ |
376 | /* Calculate the position of the header. */ |
377 | heap_block_head_t *head = |
377 | heap_block_head_t *head = |
378 | (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); |
378 | (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); |
379 | 379 | ||
380 | assert((void *) head >= heap_start); |
380 | assert((void *) head >= heap_start); |
381 | assert((void *) head < heap_end); |
381 | assert((void *) head < heap_end); |
382 | 382 | ||
383 | block_check(head); |
383 | block_check(head); |
384 | assert(!head->free); |
384 | assert(!head->free); |
385 | 385 | ||
386 | void *ptr = NULL; |
386 | void *ptr = NULL; |
387 | size_t real_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN)); |
387 | size_t real_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN)); |
388 | size_t orig_size = head->size; |
388 | size_t orig_size = head->size; |
389 | 389 | ||
390 | if (orig_size > real_size) { |
390 | if (orig_size > real_size) { |
391 | /* Shrink */ |
391 | /* Shrink */ |
392 | if (orig_size - real_size >= STRUCT_OVERHEAD) { |
392 | if (orig_size - real_size >= STRUCT_OVERHEAD) { |
393 | /* Split the original block to a full block |
393 | /* Split the original block to a full block |
394 | and a tailing free block */ |
394 | and a tailing free block */ |
395 | block_init((void *) head, real_size, false); |
395 | block_init((void *) head, real_size, false); |
396 | block_init((void *) head + real_size, |
396 | block_init((void *) head + real_size, |
397 | orig_size - real_size, true); |
397 | orig_size - real_size, true); |
398 | shrink_heap(); |
398 | shrink_heap(); |
399 | } |
399 | } |
400 | 400 | ||
401 | ptr = ((void *) head) + sizeof(heap_block_head_t); |
401 | ptr = ((void *) head) + sizeof(heap_block_head_t); |
402 | } else { |
402 | } else { |
403 | /* Look at the next block. If it is free and the size is |
403 | /* Look at the next block. If it is free and the size is |
404 | sufficient then merge the two. */ |
404 | sufficient then merge the two. */ |
405 | heap_block_head_t *next_head = |
405 | heap_block_head_t *next_head = |
406 | (heap_block_head_t *) (((void *) head) + head->size); |
406 | (heap_block_head_t *) (((void *) head) + head->size); |
407 | 407 | ||
408 | if (((void *) next_head < heap_end) |
408 | if (((void *) next_head < heap_end) && |
409 | && (head->size + next_head->size >= real_size)) { |
409 | (head->size + next_head->size >= real_size) && |
- | 410 | (next_head->free)) { |
|
410 | block_check(next_head); |
411 | block_check(next_head); |
411 | block_init(head, head->size + next_head->size, false); |
412 | block_init(head, head->size + next_head->size, false); |
412 | split_mark(head, ALIGN_UP(size, BASE_ALIGN)); |
413 | split_mark(head, ALIGN_UP(size, BASE_ALIGN)); |
413 | 414 | ||
414 | ptr = ((void *) head) + sizeof(heap_block_head_t); |
415 | ptr = ((void *) head) + sizeof(heap_block_head_t); |
415 | } else { |
416 | } else { |
416 | ptr = malloc(size); |
417 | ptr = malloc(size); |
417 | if (ptr != NULL) { |
418 | if (ptr != NULL) { |
418 | memcpy(ptr, addr, NET_SIZE(orig_size)); |
419 | memcpy(ptr, addr, NET_SIZE(orig_size)); |
419 | free(addr); |
420 | free(addr); |
420 | } |
421 | } |
421 | } |
422 | } |
422 | } |
423 | } |
423 | 424 | ||
424 | return ptr; |
425 | return ptr; |
425 | } |
426 | } |
426 | 427 | ||
427 | /** Free a memory block |
428 | /** Free a memory block |
428 | * |
429 | * |
429 | * @param addr The address of the block. |
430 | * @param addr The address of the block. |
430 | */ |
431 | */ |
431 | void free(const void *addr) |
432 | void free(const void *addr) |
432 | { |
433 | { |
433 | /* Calculate the position of the header. */ |
434 | /* Calculate the position of the header. */ |
434 | heap_block_head_t *head |
435 | heap_block_head_t *head |
435 | = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); |
436 | = (heap_block_head_t *) (addr - sizeof(heap_block_head_t)); |
436 | 437 | ||
437 | assert((void *) head >= heap_start); |
438 | assert((void *) head >= heap_start); |
438 | assert((void *) head < heap_end); |
439 | assert((void *) head < heap_end); |
439 | 440 | ||
440 | block_check(head); |
441 | block_check(head); |
441 | assert(!head->free); |
442 | assert(!head->free); |
442 | 443 | ||
443 | /* Mark the block itself as free. */ |
444 | /* Mark the block itself as free. */ |
444 | head->free = true; |
445 | head->free = true; |
445 | 446 | ||
446 | /* Look at the next block. If it is free, merge the two. */ |
447 | /* Look at the next block. If it is free, merge the two. */ |
447 | heap_block_head_t *next_head |
448 | heap_block_head_t *next_head |
448 | = (heap_block_head_t *) (((void *) head) + head->size); |
449 | = (heap_block_head_t *) (((void *) head) + head->size); |
449 | 450 | ||
450 | if ((void *) next_head < heap_end) { |
451 | if ((void *) next_head < heap_end) { |
451 | block_check(next_head); |
452 | block_check(next_head); |
452 | if (next_head->free) |
453 | if (next_head->free) |
453 | block_init(head, head->size + next_head->size, true); |
454 | block_init(head, head->size + next_head->size, true); |
454 | } |
455 | } |
455 | 456 | ||
456 | /* Look at the previous block. If it is free, merge the two. */ |
457 | /* Look at the previous block. If it is free, merge the two. */ |
457 | if ((void *) head > heap_start) { |
458 | if ((void *) head > heap_start) { |
458 | heap_block_foot_t *prev_foot = |
459 | heap_block_foot_t *prev_foot = |
459 | (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); |
460 | (heap_block_foot_t *) (((void *) head) - sizeof(heap_block_foot_t)); |
460 | 461 | ||
461 | heap_block_head_t *prev_head = |
462 | heap_block_head_t *prev_head = |
462 | (heap_block_head_t *) (((void *) head) - prev_foot->size); |
463 | (heap_block_head_t *) (((void *) head) - prev_foot->size); |
463 | 464 | ||
464 | block_check(prev_head); |
465 | block_check(prev_head); |
465 | 466 | ||
466 | if (prev_head->free) |
467 | if (prev_head->free) |
467 | block_init(prev_head, prev_head->size + head->size, true); |
468 | block_init(prev_head, prev_head->size + head->size, true); |
468 | } |
469 | } |
469 | 470 | ||
470 | shrink_heap(); |
471 | shrink_heap(); |
471 | } |
472 | } |
472 | 473 | ||
473 | /** @} |
474 | /** @} |
474 | */ |
475 | */ |
475 | 476 |