Don't always zero memory in malloc(). This saves around 2us on a
[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                         DBG ( "Allocated [%p,%p)\n", block,
138                               ( ( ( void * ) block ) + size ) );
139                         return block;
140                 }
141         }
142
143         DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
144         return NULL;
145 }
146
147 /**
148  * Free a memory block
149  *
150  * @v ptr               Memory allocated by alloc_memblock(), or NULL
151  * @v size              Size of the memory
152  *
153  * If @c ptr is NULL, no action is taken.
154  */
155 void free_memblock ( void *ptr, size_t size ) {
156         struct memory_block *freeing;
157         struct memory_block *block;
158         ssize_t gap_before;
159         ssize_t gap_after = -1;
160
161         /* Allow for ptr==NULL */
162         if ( ! ptr )
163                 return;
164
165         /* Round up size to match actual size that alloc_memblock()
166          * would have used.
167          */
168         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
169         freeing = ptr;
170         freeing->size = size;
171         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
172
173         /* Insert/merge into free list */
174         list_for_each_entry ( block, &free_blocks, list ) {
175                 /* Calculate gaps before and after the "freeing" block */
176                 gap_before = ( ( ( void * ) freeing ) - 
177                                ( ( ( void * ) block ) + block->size ) );
178                 gap_after = ( ( ( void * ) block ) - 
179                               ( ( ( void * ) freeing ) + freeing->size ) );
180                 /* Merge with immediately preceding block, if possible */
181                 if ( gap_before == 0 ) {
182                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
183                               ( ( ( void * ) block ) + block->size ), freeing,
184                               ( ( ( void * ) freeing ) + freeing->size ),block,
185                               ( ( ( void * ) freeing ) + freeing->size ) );
186                         block->size += size;
187                         list_del ( &block->list );
188                         freeing = block;
189                 }
190                 /* Stop processing as soon as we reach a following block */
191                 if ( gap_after >= 0 )
192                         break;
193         }
194
195         /* Insert before the immediately following block.  If
196          * possible, merge the following block into the "freeing"
197          * block.
198          */
199         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
200         list_add_tail ( &freeing->list, &block->list );
201         if ( gap_after == 0 ) {
202                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
203                       ( ( ( void * ) freeing ) + freeing->size ), block,
204                       ( ( ( void * ) block ) + block->size ), freeing,
205                       ( ( ( void * ) block ) + block->size ) );
206                 freeing->size += block->size;
207                 list_del ( &block->list );
208         }
209 }
210
211 /**
212  * Reallocate memory
213  *
214  * @v old_ptr           Memory previously allocated by malloc(), or NULL
215  * @v new_size          Requested size
216  * @ret new_ptr         Allocated memory, or NULL
217  *
218  * Allocates memory with no particular alignment requirement.  @c
219  * new_ptr will be aligned to at least a multiple of sizeof(void*).
220  * If @c old_ptr is non-NULL, then the contents of the newly allocated
221  * memory will be the same as the contents of the previously allocated
222  * memory, up to the minimum of the old and new sizes.  The old memory
223  * will be freed.
224  *
225  * If allocation fails the previously allocated block is left
226  * untouched and NULL is returned.
227  *
228  * Calling realloc() with a new size of zero is a valid way to free a
229  * memory block.
230  */
231 void * realloc ( void *old_ptr, size_t new_size ) {
232         struct autosized_block *old_block;
233         struct autosized_block *new_block;
234         size_t old_total_size;
235         size_t new_total_size;
236         size_t old_size;
237         void *new_ptr = NOWHERE;
238
239         /* Allocate new memory if necessary.  If allocation fails,
240          * return without touching the old block.
241          */
242         if ( new_size ) {
243                 new_total_size = ( new_size +
244                                    offsetof ( struct autosized_block, data ) );
245                 new_block = alloc_memblock ( new_total_size, 1 );
246                 if ( ! new_block )
247                         return NULL;
248                 new_block->size = new_total_size;
249                 new_ptr = &new_block->data;
250         }
251         
252         /* Copy across relevant part of the old data region (if any),
253          * then free it.  Note that at this point either (a) new_ptr
254          * is valid, or (b) new_size is 0; either way, the memcpy() is
255          * valid.
256          */
257         if ( old_ptr && ( old_ptr != NOWHERE ) ) {
258                 old_block = container_of ( old_ptr, struct autosized_block,
259                                            data );
260                 old_total_size = old_block->size;
261                 old_size = ( old_total_size -
262                              offsetof ( struct autosized_block, data ) );
263                 memcpy ( new_ptr, old_ptr,
264                          ( ( old_size < new_size ) ? old_size : new_size ) );
265                 free_memblock ( old_block, old_total_size );
266         }
267
268         return new_ptr;
269 }
270
271 /**
272  * Allocate memory
273  *
274  * @v size              Requested size
275  * @ret ptr             Memory, or NULL
276  *
277  * Allocates memory with no particular alignment requirement.  @c ptr
278  * will be aligned to at least a multiple of sizeof(void*).
279  */
280 void * malloc ( size_t size ) {
281         return realloc ( NULL, size );
282 }
283
284 /**
285  * Free memory
286  *
287  * @v ptr               Memory allocated by malloc(), or NULL
288  *
289  * Memory allocated with malloc_dma() cannot be freed with free(); it
290  * must be freed with free_dma() instead.
291  *
292  * If @c ptr is NULL, no action is taken.
293  */
294 void free ( void *ptr ) {
295         realloc ( ptr, 0 );
296 }
297
298 /**
299  * Allocate cleared memory
300  *
301  * @v size              Requested size
302  * @ret ptr             Allocated memory
303  *
304  * Allocate memory as per malloc(), and zero it.
305  */
306 void * _calloc ( size_t size ) {
307         void *data;
308
309         data = malloc ( size );
310         if ( data )
311                 memset ( data, 0, size );
312         return data;
313 }
314
315 /**
316  * Add memory to allocation pool
317  *
318  * @v start             Start address
319  * @v end               End address
320  *
321  * Adds a block of memory [start,end) to the allocation pool.  This is
322  * a one-way operation; there is no way to reclaim this memory.
323  *
324  * @c start must be aligned to at least a multiple of sizeof(void*).
325  */
326 void mpopulate ( void *start, size_t len ) {
327         /* Prevent free_memblock() from rounding up len beyond the end
328          * of what we were actually given...
329          */
330         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
331 }
332
333 #if 0
334 #include <vsprintf.h>
335 /**
336  * Dump free block list
337  *
338  */
339 void mdumpfree ( void ) {
340         struct memory_block *block;
341
342         printf ( "Free block list:\n" );
343         list_for_each_entry ( block, &free_blocks, list ) {
344                 printf ( "[%p,%p] (size %#zx)\n", block,
345                          ( ( ( void * ) block ) + block->size ), block->size );
346         }
347 }
348 #endif