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