malloc attribute changes
[gpxe.git] / src / core / malloc.c
1 /*
2  * Copyright (C) 2006 Michael Brown <mbrown@fensystems.co.uk>.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License as
6  * published by the Free Software Foundation; either version 2 of the
7  * License, or any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but
10  * WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  * General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17  */
18
19 #include <stddef.h>
20 #include <stdint.h>
21 #include <string.h>
22 #include <strings.h>
23 #include <io.h>
24 #include <gpxe/list.h>
25 #include <gpxe/init.h>
26 #include <gpxe/malloc.h>
27
28 /** @file
29  *
30  * Dynamic memory allocation
31  *
32  */
33
34 /** A free block of memory */
35 struct memory_block {
36         /** List of free blocks */
37         struct list_head list;
38         /** Size of this block */
39         size_t size;
40 };
41
42 #define MIN_MEMBLOCK_SIZE \
43         ( ( size_t ) ( 1 << ( fls ( sizeof ( struct memory_block ) - 1 ) ) ) )
44
45 /** A block of allocated memory complete with size information */
46 struct autosized_block {
47         /** Size of this block */
48         size_t size;
49         /** Remaining data */
50         char data[0];
51 };
52
53 /**
54  * Address for zero-length memory blocks
55  *
56  * @c malloc(0) or @c realloc(ptr,0) will return the special value @c
57  * NOWHERE.  Calling @c free(NOWHERE) will have no effect.
58  *
59  * This is consistent with the ANSI C standards, which state that
60  * "either NULL or a pointer suitable to be passed to free()" must be
61  * returned in these cases.  Using a special non-NULL value means that
62  * the caller can take a NULL return value to indicate failure,
63  * without first having to check for a requested size of zero.
64  *
65  * Code outside of malloc.c do not ever need to refer to the actual
66  * value of @c NOWHERE; this is an internal definition.
67  */
68 #define NOWHERE ( ( void * ) ~( ( intptr_t ) 0 ) )
69
70 /** List of free memory blocks */
71 static LIST_HEAD ( free_blocks );
72
73 /** Total amount of free memory */
74 size_t freemem;
75
76 /**
77  * Heap size
78  *
79  * Currently fixed at 128kB.
80  */
81 #define HEAP_SIZE ( 128 * 1024 )
82
83 /** The heap itself */
84 static char heap[HEAP_SIZE] __attribute__ (( aligned ( __alignof__(void *) )));
85
86 /**
87  * Allocate a memory block
88  *
89  * @v size              Requested size
90  * @v align             Physical alignment
91  * @ret ptr             Memory block, or NULL
92  *
93  * Allocates a memory block @b physically aligned as requested.  No
94  * guarantees are provided for the alignment of the virtual address.
95  *
96  * @c align must be a power of two.  @c size may not be zero.
97  */
98 __attribute__ ((malloc))
99 void * alloc_memblock ( size_t size, size_t align ) {
100         struct memory_block *block;
101         size_t align_mask;
102         size_t pre_size;
103         ssize_t post_size;
104         struct memory_block *pre;
105         struct memory_block *post;
106
107         /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
108          * calculate alignment mask.
109          */
110         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
111         align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );
112
113         DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );
114
115         /* Search through blocks for the first one with enough space */
116         list_for_each_entry ( block, &free_blocks, list ) {
117                 pre_size = ( - virt_to_phys ( block ) ) & align_mask;
118                 post_size = block->size - pre_size - size;
119                 if ( post_size >= 0 ) {
120                         /* Split block into pre-block, block, and
121                          * post-block.  After this split, the "pre"
122                          * block is the one currently linked into the
123                          * free list.
124                          */
125                         pre   = block;
126                         block = ( ( ( void * ) pre   ) + pre_size );
127                         post  = ( ( ( void * ) block ) + size     );
128                         DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
129                               ( ( ( void * ) pre ) + pre->size ), pre, block,
130                               post, ( ( ( void * ) pre ) + pre->size ) );
131                         /* If there is a "post" block, add it in to
132                          * the free list.  Leak it if it is too small
133                          * (which can happen only at the very end of
134                          * the heap).
135                          */
136                         if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
137                                 post->size = post_size;
138                                 list_add ( &post->list, &pre->list );
139                         }
140                         /* Shrink "pre" block, leaving the main block
141                          * isolated and no longer part of the free
142                          * list.
143                          */
144                         pre->size = pre_size;
145                         /* If there is no "pre" block, remove it from
146                          * the list.  Also remove it (i.e. leak it) if
147                          * it is too small, which can happen only at
148                          * the very start of the heap.
149                          */
150                         if ( pre_size < MIN_MEMBLOCK_SIZE )
151                                 list_del ( &pre->list );
152                         /* Update total free memory */
153                         freemem -= size;
154                         /* Return allocated block */
155                         DBG ( "Allocated [%p,%p)\n", block,
156                               ( ( ( void * ) block ) + size ) );
157                         return block;
158                 }
159         }
160
161         DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
162         return NULL;
163 }
164
165 /**
166  * Free a memory block
167  *
168  * @v ptr               Memory allocated by alloc_memblock(), or NULL
169  * @v size              Size of the memory
170  *
171  * If @c ptr is NULL, no action is taken.
172  */
173 void free_memblock ( void *ptr, size_t size ) {
174         struct memory_block *freeing;
175         struct memory_block *block;
176         ssize_t gap_before;
177         ssize_t gap_after = -1;
178
179         /* Allow for ptr==NULL */
180         if ( ! ptr )
181                 return;
182
183         /* Round up size to match actual size that alloc_memblock()
184          * would have used.
185          */
186         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
187         freeing = ptr;
188         freeing->size = size;
189         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
190
191         /* Insert/merge into free list */
192         list_for_each_entry ( block, &free_blocks, list ) {
193                 /* Calculate gaps before and after the "freeing" block */
194                 gap_before = ( ( ( void * ) freeing ) - 
195                                ( ( ( void * ) block ) + block->size ) );
196                 gap_after = ( ( ( void * ) block ) - 
197                               ( ( ( void * ) freeing ) + freeing->size ) );
198                 /* Merge with immediately preceding block, if possible */
199                 if ( gap_before == 0 ) {
200                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
201                               ( ( ( void * ) block ) + block->size ), freeing,
202                               ( ( ( void * ) freeing ) + freeing->size ),block,
203                               ( ( ( void * ) freeing ) + freeing->size ) );
204                         block->size += size;
205                         list_del ( &block->list );
206                         freeing = block;
207                 }
208                 /* Stop processing as soon as we reach a following block */
209                 if ( gap_after >= 0 )
210                         break;
211         }
212
213         /* Insert before the immediately following block.  If
214          * possible, merge the following block into the "freeing"
215          * block.
216          */
217         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
218         list_add_tail ( &freeing->list, &block->list );
219         if ( gap_after == 0 ) {
220                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
221                       ( ( ( void * ) freeing ) + freeing->size ), block,
222                       ( ( ( void * ) block ) + block->size ), freeing,
223                       ( ( ( void * ) block ) + block->size ) );
224                 freeing->size += block->size;
225                 list_del ( &block->list );
226         }
227
228         /* Update free memory counter */
229         freemem += size;
230 }
231
232 /**
233  * Reallocate memory
234  *
235  * @v old_ptr           Memory previously allocated by malloc(), or NULL
236  * @v new_size          Requested size
237  * @ret new_ptr         Allocated memory, or NULL
238  *
239  * Allocates memory with no particular alignment requirement.  @c
240  * new_ptr will be aligned to at least a multiple of sizeof(void*).
241  * If @c old_ptr is non-NULL, then the contents of the newly allocated
242  * memory will be the same as the contents of the previously allocated
243  * memory, up to the minimum of the old and new sizes.  The old memory
244  * will be freed.
245  *
246  * If allocation fails the previously allocated block is left
247  * untouched and NULL is returned.
248  *
249  * Calling realloc() with a new size of zero is a valid way to free a
250  * memory block.
251  */
252 __attribute__ ((malloc))
253 void * realloc ( void *old_ptr, size_t new_size ) {
254         struct autosized_block *old_block;
255         struct autosized_block *new_block;
256         size_t old_total_size;
257         size_t new_total_size;
258         size_t old_size;
259         void *new_ptr = NOWHERE;
260
261         /* Allocate new memory if necessary.  If allocation fails,
262          * return without touching the old block.
263          */
264         if ( new_size ) {
265                 new_total_size = ( new_size +
266                                    offsetof ( struct autosized_block, data ) );
267                 new_block = alloc_memblock ( new_total_size, 1 );
268                 if ( ! new_block )
269                         return NULL;
270                 new_block->size = new_total_size;
271                 new_ptr = &new_block->data;
272         }
273         
274         /* Copy across relevant part of the old data region (if any),
275          * then free it.  Note that at this point either (a) new_ptr
276          * is valid, or (b) new_size is 0; either way, the memcpy() is
277          * valid.
278          */
279         if ( old_ptr && ( old_ptr != NOWHERE ) ) {
280                 old_block = container_of ( old_ptr, struct autosized_block,
281                                            data );
282                 old_total_size = old_block->size;
283                 old_size = ( old_total_size -
284                              offsetof ( struct autosized_block, data ) );
285                 memcpy ( new_ptr, old_ptr,
286                          ( ( old_size < new_size ) ? old_size : new_size ) );
287                 free_memblock ( old_block, old_total_size );
288         }
289
290         return new_ptr;
291 }
292
293 /**
294  * Allocate memory
295  *
296  * @v size              Requested size
297  * @ret ptr             Memory, or NULL
298  *
299  * Allocates memory with no particular alignment requirement.  @c ptr
300  * will be aligned to at least a multiple of sizeof(void*).
301  */
302 __attribute__ ((malloc))
303 void * malloc ( size_t size ) {
304         return realloc ( NULL, size );
305 }
306
307 /**
308  * Free memory
309  *
310  * @v ptr               Memory allocated by malloc(), or NULL
311  *
312  * Memory allocated with malloc_dma() cannot be freed with free(); it
313  * must be freed with free_dma() instead.
314  *
315  * If @c ptr is NULL, no action is taken.
316  */
317 void free ( void *ptr ) {
318         realloc ( ptr, 0 );
319 }
320
321 /**
322  * Allocate cleared memory
323  *
324  * @v size              Requested size
325  * @ret ptr             Allocated memory
326  *
327  * Allocate memory as per malloc(), and zero it.
328  *
329  * This function name is non-standard, but pretty intuitive.
330  * zalloc(size) is always equivalent to calloc(1,size)
331  */
332 __attribute__ ((malloc))
333 void * zalloc ( size_t size ) {
334         void *data;
335
336         data = malloc ( size );
337         if ( data )
338                 memset ( data, 0, size );
339         return data;
340 }
341
342 /**
343  * Add memory to allocation pool
344  *
345  * @v start             Start address
346  * @v end               End address
347  *
348  * Adds a block of memory [start,end) to the allocation pool.  This is
349  * a one-way operation; there is no way to reclaim this memory.
350  *
351  * @c start must be aligned to at least a multiple of sizeof(void*).
352  */
353 void mpopulate ( void *start, size_t len ) {
354         /* Prevent free_memblock() from rounding up len beyond the end
355          * of what we were actually given...
356          */
357         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
358 }
359
360 /**
361  * Initialise the heap
362  *
363  */
364 static void init_heap ( void ) {
365         mpopulate ( heap, sizeof ( heap ) );
366 }
367
368 /** Memory allocator initialisation function */
369 struct init_fn heap_init_fn __init_fn ( INIT_EARLY ) = {
370         .initialise = init_heap,
371 };
372
373 #if 0
374 #include <stdio.h>
375 /**
376  * Dump free block list
377  *
378  */
379 void mdumpfree ( void ) {
380         struct memory_block *block;
381
382         printf ( "Free block list:\n" );
383         list_for_each_entry ( block, &free_blocks, list ) {
384                 printf ( "[%p,%p] (size %#zx)\n", block,
385                          ( ( ( void * ) block ) + block->size ), block->size );
386         }
387 }
388 #endif