[ioapi] Remove old io.h file and switch all users over to <gpxe/io.h>
[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 <gpxe/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 void * alloc_memblock ( size_t size, size_t align ) {
99         struct memory_block *block;
100         size_t align_mask;
101         size_t pre_size;
102         ssize_t post_size;
103         struct memory_block *pre;
104         struct memory_block *post;
105
106         /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
107          * calculate alignment mask.
108          */
109         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
110         align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );
111
112         DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );
113
114         /* Search through blocks for the first one with enough space */
115         list_for_each_entry ( block, &free_blocks, list ) {
116                 pre_size = ( - virt_to_phys ( block ) ) & align_mask;
117                 post_size = block->size - pre_size - size;
118                 if ( post_size >= 0 ) {
119                         /* Split block into pre-block, block, and
120                          * post-block.  After this split, the "pre"
121                          * block is the one currently linked into the
122                          * free list.
123                          */
124                         pre   = block;
125                         block = ( ( ( void * ) pre   ) + pre_size );
126                         post  = ( ( ( void * ) block ) + size     );
127                         DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
128                               ( ( ( void * ) pre ) + pre->size ), pre, block,
129                               post, ( ( ( void * ) pre ) + pre->size ) );
130                         /* If there is a "post" block, add it in to
131                          * the free list.  Leak it if it is too small
132                          * (which can happen only at the very end of
133                          * the heap).
134                          */
135                         if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
136                                 post->size = post_size;
137                                 list_add ( &post->list, &pre->list );
138                         }
139                         /* Shrink "pre" block, leaving the main block
140                          * isolated and no longer part of the free
141                          * list.
142                          */
143                         pre->size = pre_size;
144                         /* If there is no "pre" block, remove it from
145                          * the list.  Also remove it (i.e. leak it) if
146                          * it is too small, which can happen only at
147                          * the very start of the heap.
148                          */
149                         if ( pre_size < MIN_MEMBLOCK_SIZE )
150                                 list_del ( &pre->list );
151                         /* Update total free memory */
152                         freemem -= size;
153                         /* Return allocated block */
154                         DBG ( "Allocated [%p,%p)\n", block,
155                               ( ( ( void * ) block ) + size ) );
156                         return block;
157                 }
158         }
159
160         DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
161         return NULL;
162 }
163
164 /**
165  * Free a memory block
166  *
167  * @v ptr               Memory allocated by alloc_memblock(), or NULL
168  * @v size              Size of the memory
169  *
170  * If @c ptr is NULL, no action is taken.
171  */
172 void free_memblock ( void *ptr, size_t size ) {
173         struct memory_block *freeing;
174         struct memory_block *block;
175         ssize_t gap_before;
176         ssize_t gap_after = -1;
177
178         /* Allow for ptr==NULL */
179         if ( ! ptr )
180                 return;
181
182         /* Round up size to match actual size that alloc_memblock()
183          * would have used.
184          */
185         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
186         freeing = ptr;
187         freeing->size = size;
188         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
189
190         /* Insert/merge into free list */
191         list_for_each_entry ( block, &free_blocks, list ) {
192                 /* Calculate gaps before and after the "freeing" block */
193                 gap_before = ( ( ( void * ) freeing ) - 
194                                ( ( ( void * ) block ) + block->size ) );
195                 gap_after = ( ( ( void * ) block ) - 
196                               ( ( ( void * ) freeing ) + freeing->size ) );
197                 /* Merge with immediately preceding block, if possible */
198                 if ( gap_before == 0 ) {
199                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
200                               ( ( ( void * ) block ) + block->size ), freeing,
201                               ( ( ( void * ) freeing ) + freeing->size ),block,
202                               ( ( ( void * ) freeing ) + freeing->size ) );
203                         block->size += size;
204                         list_del ( &block->list );
205                         freeing = block;
206                 }
207                 /* Stop processing as soon as we reach a following block */
208                 if ( gap_after >= 0 )
209                         break;
210         }
211
212         /* Insert before the immediately following block.  If
213          * possible, merge the following block into the "freeing"
214          * block.
215          */
216         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
217         list_add_tail ( &freeing->list, &block->list );
218         if ( gap_after == 0 ) {
219                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
220                       ( ( ( void * ) freeing ) + freeing->size ), block,
221                       ( ( ( void * ) block ) + block->size ), freeing,
222                       ( ( ( void * ) block ) + block->size ) );
223                 freeing->size += block->size;
224                 list_del ( &block->list );
225         }
226
227         /* Update free memory counter */
228         freemem += size;
229 }
230
231 /**
232  * Reallocate memory
233  *
234  * @v old_ptr           Memory previously allocated by malloc(), or NULL
235  * @v new_size          Requested size
236  * @ret new_ptr         Allocated memory, or NULL
237  *
238  * Allocates memory with no particular alignment requirement.  @c
239  * new_ptr will be aligned to at least a multiple of sizeof(void*).
240  * If @c old_ptr is non-NULL, then the contents of the newly allocated
241  * memory will be the same as the contents of the previously allocated
242  * memory, up to the minimum of the old and new sizes.  The old memory
243  * will be freed.
244  *
245  * If allocation fails the previously allocated block is left
246  * untouched and NULL is returned.
247  *
248  * Calling realloc() with a new size of zero is a valid way to free a
249  * memory block.
250  */
251 void * realloc ( void *old_ptr, size_t new_size ) {
252         struct autosized_block *old_block;
253         struct autosized_block *new_block;
254         size_t old_total_size;
255         size_t new_total_size;
256         size_t old_size;
257         void *new_ptr = NOWHERE;
258
259         /* Allocate new memory if necessary.  If allocation fails,
260          * return without touching the old block.
261          */
262         if ( new_size ) {
263                 new_total_size = ( new_size +
264                                    offsetof ( struct autosized_block, data ) );
265                 new_block = alloc_memblock ( new_total_size, 1 );
266                 if ( ! new_block )
267                         return NULL;
268                 new_block->size = new_total_size;
269                 new_ptr = &new_block->data;
270         }
271         
272         /* Copy across relevant part of the old data region (if any),
273          * then free it.  Note that at this point either (a) new_ptr
274          * is valid, or (b) new_size is 0; either way, the memcpy() is
275          * valid.
276          */
277         if ( old_ptr && ( old_ptr != NOWHERE ) ) {
278                 old_block = container_of ( old_ptr, struct autosized_block,
279                                            data );
280                 old_total_size = old_block->size;
281                 old_size = ( old_total_size -
282                              offsetof ( struct autosized_block, data ) );
283                 memcpy ( new_ptr, old_ptr,
284                          ( ( old_size < new_size ) ? old_size : new_size ) );
285                 free_memblock ( old_block, old_total_size );
286         }
287
288         return new_ptr;
289 }
290
291 /**
292  * Allocate memory
293  *
294  * @v size              Requested size
295  * @ret ptr             Memory, or NULL
296  *
297  * Allocates memory with no particular alignment requirement.  @c ptr
298  * will be aligned to at least a multiple of sizeof(void*).
299  */
300 void * malloc ( size_t size ) {
301         return realloc ( NULL, size );
302 }
303
304 /**
305  * Free memory
306  *
307  * @v ptr               Memory allocated by malloc(), or NULL
308  *
309  * Memory allocated with malloc_dma() cannot be freed with free(); it
310  * must be freed with free_dma() instead.
311  *
312  * If @c ptr is NULL, no action is taken.
313  */
314 void free ( void *ptr ) {
315         realloc ( ptr, 0 );
316 }
317
318 /**
319  * Allocate cleared memory
320  *
321  * @v size              Requested size
322  * @ret ptr             Allocated memory
323  *
324  * Allocate memory as per malloc(), and zero it.
325  *
326  * This function name is non-standard, but pretty intuitive.
327  * zalloc(size) is always equivalent to calloc(1,size)
328  */
329 void * zalloc ( size_t size ) {
330         void *data;
331
332         data = malloc ( size );
333         if ( data )
334                 memset ( data, 0, size );
335         return data;
336 }
337
338 /**
339  * Add memory to allocation pool
340  *
341  * @v start             Start address
342  * @v end               End address
343  *
344  * Adds a block of memory [start,end) to the allocation pool.  This is
345  * a one-way operation; there is no way to reclaim this memory.
346  *
347  * @c start must be aligned to at least a multiple of sizeof(void*).
348  */
349 void mpopulate ( void *start, size_t len ) {
350         /* Prevent free_memblock() from rounding up len beyond the end
351          * of what we were actually given...
352          */
353         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
354 }
355
356 /**
357  * Initialise the heap
358  *
359  */
360 static void init_heap ( void ) {
361         mpopulate ( heap, sizeof ( heap ) );
362 }
363
364 /** Memory allocator initialisation function */
365 struct init_fn heap_init_fn __init_fn ( INIT_EARLY ) = {
366         .initialise = init_heap,
367 };
368
369 #if 0
370 #include <stdio.h>
371 /**
372  * Dump free block list
373  *
374  */
375 void mdumpfree ( void ) {
376         struct memory_block *block;
377
378         printf ( "Free block list:\n" );
379         list_for_each_entry ( block, &free_blocks, list ) {
380                 printf ( "[%p,%p] (size %#zx)\n", block,
381                          ( ( ( void * ) block ) + block->size ), block->size );
382         }
383 }
384 #endif