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