We don't actually have a stdio.h header file. Our printf() functions are
[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 /** List of free memory blocks */
53 static LIST_HEAD ( free_blocks );
54
55 /**
56  * Allocate a memory block
57  *
58  * @v size              Requested size
59  * @v align             Physical alignment
60  * @ret ptr             Memory block, or NULL
61  *
62  * Allocates a memory block @b physically aligned as requested.  No
63  * guarantees are provided for the alignment of the virtual address.
64  *
65  * @c align must be a power of two.  @c size may not be zero.
66  */
67 void * alloc_memblock ( size_t size, size_t align ) {
68         struct memory_block *block;
69         size_t align_mask;
70         size_t pre_size;
71         ssize_t post_size;
72         struct memory_block *pre;
73         struct memory_block *post;
74
75         /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
76          * calculate alignment mask.
77          */
78         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
79         align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );
80
81         DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );
82
83         /* Search through blocks for the first one with enough space */
84         list_for_each_entry ( block, &free_blocks, list ) {
85                 pre_size = ( - virt_to_phys ( block ) ) & align_mask;
86                 post_size = block->size - pre_size - size;
87                 if ( post_size >= 0 ) {
88                         /* Split block into pre-block, block, and
89                          * post-block.  After this split, the "pre"
90                          * block is the one currently linked into the
91                          * free list.
92                          */
93                         pre   = block;
94                         block = ( ( ( void * ) pre   ) + pre_size );
95                         post  = ( ( ( void * ) block ) + size     );
96                         DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
97                               ( ( ( void * ) pre ) + pre->size ), pre, block,
98                               post, ( ( ( void * ) pre ) + pre->size ) );
99                         /* If there is a "post" block, add it in to
100                          * the free list.  Leak it if it is too small
101                          * (which can happen only at the very end of
102                          * the heap).
103                          */
104                         if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
105                                 post->size = post_size;
106                                 list_add ( &post->list, &pre->list );
107                         }
108                         /* Shrink "pre" block, leaving the main block
109                          * isolated and no longer part of the free
110                          * list.
111                          */
112                         pre->size = pre_size;
113                         /* If there is no "pre" block, remove it from
114                          * the list.  Also remove it (i.e. leak it) if
115                          * it is too small, which can happen only at
116                          * the very start of the heap.
117                          */
118                         if ( pre_size < MIN_MEMBLOCK_SIZE )
119                                 list_del ( &pre->list );
120                         /* Zero allocated memory, for calloc() */
121                         memset ( block, 0, size );
122                         DBG ( "Allocated [%p,%p)\n", block,
123                               ( ( ( void * ) block ) + size ) );
124                         return block;
125                 }
126         }
127
128         DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
129         return NULL;
130 }
131
132 /**
133  * Free a memory block
134  *
135  * @v ptr               Memory allocated by alloc_memblock(), or NULL
136  * @v size              Size of the memory
137  *
138  * If @c ptr is NULL, no action is taken.
139  */
140 void free_memblock ( void *ptr, size_t size ) {
141         struct memory_block *freeing;
142         struct memory_block *block;
143         ssize_t gap_before;
144         ssize_t gap_after = -1;
145
146         /* Allow for ptr==NULL */
147         if ( ! ptr )
148                 return;
149
150         /* Round up size to match actual size that alloc_memblock()
151          * would have used.
152          */
153         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
154         freeing = ptr;
155         freeing->size = size;
156         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
157
158         /* Insert/merge into free list */
159         list_for_each_entry ( block, &free_blocks, list ) {
160                 /* Calculate gaps before and after the "freeing" block */
161                 gap_before = ( ( ( void * ) freeing ) - 
162                                ( ( ( void * ) block ) + block->size ) );
163                 gap_after = ( ( ( void * ) block ) - 
164                               ( ( ( void * ) freeing ) + freeing->size ) );
165                 /* Merge with immediately preceding block, if possible */
166                 if ( gap_before == 0 ) {
167                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
168                               ( ( ( void * ) block ) + block->size ), freeing,
169                               ( ( ( void * ) freeing ) + freeing->size ),block,
170                               ( ( ( void * ) freeing ) + freeing->size ) );
171                         block->size += size;
172                         list_del ( &block->list );
173                         freeing = block;
174                 }
175                 /* Stop processing as soon as we reach a following block */
176                 if ( gap_after >= 0 )
177                         break;
178         }
179
180         /* Insert before the immediately following block.  If
181          * possible, merge the following block into the "freeing"
182          * block.
183          */
184         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
185         list_add_tail ( &freeing->list, &block->list );
186         if ( gap_after == 0 ) {
187                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
188                       ( ( ( void * ) freeing ) + freeing->size ), block,
189                       ( ( ( void * ) block ) + block->size ), freeing,
190                       ( ( ( void * ) block ) + block->size ) );
191                 freeing->size += block->size;
192                 list_del ( &block->list );
193         }
194 }
195
196 /**
197  * Allocate memory
198  *
199  * @v size              Requested size
200  * @ret ptr             Memory, or NULL
201  *
202  * Allocates memory with no particular alignment requirement.  @c ptr
203  * will be aligned to at least a multiple of sizeof(void*).
204  */
205 void * malloc ( size_t size ) {
206         size_t total_size;
207         struct autosized_block *block;
208
209         total_size = size + offsetof ( struct autosized_block, data );
210         block = alloc_memblock ( total_size, 1 );
211         if ( ! block )
212                 return NULL;
213         block->size = total_size;
214         return &block->data;
215 }
216
217 /**
218  * Free memory
219  *
220  * @v size              Memory allocated by malloc(), or NULL
221  *
222  * Memory allocated with malloc_dma() cannot be freed with free(); it
223  * must be freed with free_dma() instead.
224  *
225  * If @c ptr is NULL, no action is taken.
226  */
227 void free ( void *ptr ) {
228         struct autosized_block *block;
229
230         if ( ptr ) {
231                 block = container_of ( ptr, struct autosized_block, data );
232                 free_memblock ( block, block->size );
233         }
234 }
235
236 /**
237  * Add memory to allocation pool
238  *
239  * @v start             Start address
240  * @v end               End address
241  *
242  * Adds a block of memory [start,end) to the allocation pool.  This is
243  * a one-way operation; there is no way to reclaim this memory.
244  *
245  * @c start must be aligned to at least a multiple of sizeof(void*).
246  */
247 void mpopulate ( void *start, size_t len ) {
248         /* Prevent free_memblock() from rounding up len beyond the end
249          * of what we were actually given...
250          */
251         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
252 }
253
254 #if 0
255 #include <vsprintf.h>
256 /**
257  * Dump free block list
258  *
259  */
260 void mdumpfree ( void ) {
261         struct memory_block *block;
262
263         printf ( "Free block list:\n" );
264         list_for_each_entry ( block, &free_blocks, list ) {
265                 printf ( "[%p,%p] (size %#zx)\n", block,
266                          ( ( ( void * ) block ) + block->size ), block->size );
267         }
268 }
269 #endif