Fix typo
[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 <malloc.h>
26
27 /** @file
28  *
29  * Dynamic memory allocation
30  *
31  */
32
33 /** A free block of memory */
34 struct memory_block {
35         /** List of free blocks */
36         struct list_head list;
37         /** Size of this block */
38         size_t size;
39 };
40
41 #define MIN_MEMBLOCK_SIZE \
42         ( ( size_t ) ( 1 << ( fls ( sizeof ( struct memory_block ) - 1 ) ) ) )
43
44 /** A block of allocated memory complete with size information */
45 struct autosized_block {
46         /** Size of this block */
47         size_t size;
48         /** Remaining data */
49         char data[0];
50 };
51
52 /**
53  * Address for zero-length memory blocks
54  *
55  * @c malloc(0) or @c realloc(ptr,0) will return the special value @c
56  * NOWHERE.  Calling @c free(NOWHERE) will have no effect.
57  *
58  * This is consistent with the ANSI C standards, which state that
59  * "either NULL or a pointer suitable to be passed to free()" must be
60  * returned in these cases.  Using a special non-NULL value means that
61  * the caller can take a NULL return value to indicate failure,
62  * without first having to check for a requested size of zero.
63  *
64  * Code outside of malloc.c do not ever need to refer to the actual
65  * value of @c NOWHERE; this is an internal definition.
66  */
67 #define NOWHERE ( ( void * ) ~( ( intptr_t ) 0 ) )
68
69 /** List of free memory blocks */
70 static LIST_HEAD ( free_blocks );
71
72 /**
73  * Allocate a memory block
74  *
75  * @v size              Requested size
76  * @v align             Physical alignment
77  * @ret ptr             Memory block, or NULL
78  *
79  * Allocates a memory block @b physically aligned as requested.  No
80  * guarantees are provided for the alignment of the virtual address.
81  *
82  * @c align must be a power of two.  @c size may not be zero.
83  */
84 void * alloc_memblock ( size_t size, size_t align ) {
85         struct memory_block *block;
86         size_t align_mask;
87         size_t pre_size;
88         ssize_t post_size;
89         struct memory_block *pre;
90         struct memory_block *post;
91
92         /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
93          * calculate alignment mask.
94          */
95         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
96         align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );
97
98         DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );
99
100         /* Search through blocks for the first one with enough space */
101         list_for_each_entry ( block, &free_blocks, list ) {
102                 pre_size = ( - virt_to_phys ( block ) ) & align_mask;
103                 post_size = block->size - pre_size - size;
104                 if ( post_size >= 0 ) {
105                         /* Split block into pre-block, block, and
106                          * post-block.  After this split, the "pre"
107                          * block is the one currently linked into the
108                          * free list.
109                          */
110                         pre   = block;
111                         block = ( ( ( void * ) pre   ) + pre_size );
112                         post  = ( ( ( void * ) block ) + size     );
113                         DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
114                               ( ( ( void * ) pre ) + pre->size ), pre, block,
115                               post, ( ( ( void * ) pre ) + pre->size ) );
116                         /* If there is a "post" block, add it in to
117                          * the free list.  Leak it if it is too small
118                          * (which can happen only at the very end of
119                          * the heap).
120                          */
121                         if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
122                                 post->size = post_size;
123                                 list_add ( &post->list, &pre->list );
124                         }
125                         /* Shrink "pre" block, leaving the main block
126                          * isolated and no longer part of the free
127                          * list.
128                          */
129                         pre->size = pre_size;
130                         /* If there is no "pre" block, remove it from
131                          * the list.  Also remove it (i.e. leak it) if
132                          * it is too small, which can happen only at
133                          * the very start of the heap.
134                          */
135                         if ( pre_size < MIN_MEMBLOCK_SIZE )
136                                 list_del ( &pre->list );
137                         /* Zero allocated memory, for calloc() */
138                         memset ( block, 0, size );
139                         DBG ( "Allocated [%p,%p)\n", block,
140                               ( ( ( void * ) block ) + size ) );
141                         return block;
142                 }
143         }
144
145         DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
146         return NULL;
147 }
148
149 /**
150  * Free a memory block
151  *
152  * @v ptr               Memory allocated by alloc_memblock(), or NULL
153  * @v size              Size of the memory
154  *
155  * If @c ptr is NULL, no action is taken.
156  */
157 void free_memblock ( void *ptr, size_t size ) {
158         struct memory_block *freeing;
159         struct memory_block *block;
160         ssize_t gap_before;
161         ssize_t gap_after = -1;
162
163         /* Allow for ptr==NULL */
164         if ( ! ptr )
165                 return;
166
167         /* Round up size to match actual size that alloc_memblock()
168          * would have used.
169          */
170         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
171         freeing = ptr;
172         freeing->size = size;
173         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
174
175         /* Insert/merge into free list */
176         list_for_each_entry ( block, &free_blocks, list ) {
177                 /* Calculate gaps before and after the "freeing" block */
178                 gap_before = ( ( ( void * ) freeing ) - 
179                                ( ( ( void * ) block ) + block->size ) );
180                 gap_after = ( ( ( void * ) block ) - 
181                               ( ( ( void * ) freeing ) + freeing->size ) );
182                 /* Merge with immediately preceding block, if possible */
183                 if ( gap_before == 0 ) {
184                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
185                               ( ( ( void * ) block ) + block->size ), freeing,
186                               ( ( ( void * ) freeing ) + freeing->size ),block,
187                               ( ( ( void * ) freeing ) + freeing->size ) );
188                         block->size += size;
189                         list_del ( &block->list );
190                         freeing = block;
191                 }
192                 /* Stop processing as soon as we reach a following block */
193                 if ( gap_after >= 0 )
194                         break;
195         }
196
197         /* Insert before the immediately following block.  If
198          * possible, merge the following block into the "freeing"
199          * block.
200          */
201         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
202         list_add_tail ( &freeing->list, &block->list );
203         if ( gap_after == 0 ) {
204                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
205                       ( ( ( void * ) freeing ) + freeing->size ), block,
206                       ( ( ( void * ) block ) + block->size ), freeing,
207                       ( ( ( void * ) block ) + block->size ) );
208                 freeing->size += block->size;
209                 list_del ( &block->list );
210         }
211 }
212
213 /**
214  * Reallocate memory
215  *
216  * @v old_ptr           Memory previously allocated by malloc(), or NULL
217  * @v new_size          Requested size
218  * @ret new_ptr         Allocated memory, or NULL
219  *
220  * Allocates memory with no particular alignment requirement.  @c
221  * new_ptr will be aligned to at least a multiple of sizeof(void*).
222  * If @c old_ptr is non-NULL, then the contents of the newly allocated
223  * memory will be the same as the contents of the previously allocated
224  * memory, up to the minimum of the old and new sizes.  The old memory
225  * will be freed.
226  *
227  * If allocation fails the previously allocated block is left
228  * untouched and NULL is returned.
229  *
230  * Calling realloc() with a new size of zero is a valid way to free a
231  * memory block.
232  */
233 void * realloc ( void *old_ptr, size_t new_size ) {
234         struct autosized_block *old_block;
235         struct autosized_block *new_block;
236         size_t old_total_size;
237         size_t new_total_size;
238         size_t old_size;
239         void *new_ptr = NOWHERE;
240
241         /* Allocate new memory if necessary.  If allocation fails,
242          * return without touching the old block.
243          */
244         if ( new_size ) {
245                 new_total_size = ( new_size +
246                                    offsetof ( struct autosized_block, data ) );
247                 new_block = alloc_memblock ( new_total_size, 1 );
248                 if ( ! new_block )
249                         return NULL;
250                 new_block->size = new_total_size;
251                 new_ptr = &new_block->data;
252         }
253         
254         /* Copy across relevant part of the old data region (if any),
255          * then free it.  Note that at this point either (a) new_ptr
256          * is valid, or (b) new_size is 0; either way, the memcpy() is
257          * valid.
258          */
259         if ( old_ptr && ( old_ptr != NOWHERE ) ) {
260                 old_block = container_of ( old_ptr, struct autosized_block,
261                                            data );
262                 old_total_size = old_block->size;
263                 old_size = ( old_total_size -
264                              offsetof ( struct autosized_block, data ) );
265                 memcpy ( new_ptr, old_ptr,
266                          ( ( old_size < new_size ) ? old_size : new_size ) );
267                 free_memblock ( old_block, old_total_size );
268         }
269
270         return new_ptr;
271 }
272
273 /**
274  * Allocate memory
275  *
276  * @v size              Requested size
277  * @ret ptr             Memory, or NULL
278  *
279  * Allocates memory with no particular alignment requirement.  @c ptr
280  * will be aligned to at least a multiple of sizeof(void*).
281  */
282 void * malloc ( size_t size ) {
283         return realloc ( NULL, size );
284 }
285
286 /**
287  * Free memory
288  *
289  * @v ptr               Memory allocated by malloc(), or NULL
290  *
291  * Memory allocated with malloc_dma() cannot be freed with free(); it
292  * must be freed with free_dma() instead.
293  *
294  * If @c ptr is NULL, no action is taken.
295  */
296 void free ( void *ptr ) {
297         realloc ( ptr, 0 );
298 }
299
300 /**
301  * Add memory to allocation pool
302  *
303  * @v start             Start address
304  * @v end               End address
305  *
306  * Adds a block of memory [start,end) to the allocation pool.  This is
307  * a one-way operation; there is no way to reclaim this memory.
308  *
309  * @c start must be aligned to at least a multiple of sizeof(void*).
310  */
311 void mpopulate ( void *start, size_t len ) {
312         /* Prevent free_memblock() from rounding up len beyond the end
313          * of what we were actually given...
314          */
315         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
316 }
317
318 #if 0
319 #include <vsprintf.h>
320 /**
321  * Dump free block list
322  *
323  */
324 void mdumpfree ( void ) {
325         struct memory_block *block;
326
327         printf ( "Free block list:\n" );
328         list_for_each_entry ( block, &free_blocks, list ) {
329                 printf ( "[%p,%p] (size %#zx)\n", block,
330                          ( ( ( void * ) block ) + block->size ), block->size );
331         }
332 }
333 #endif