Updated memory allocator to improve support for unaligned or partially
[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 pre_size;
70         ssize_t post_size;
71         struct memory_block *pre;
72         struct memory_block *post;
73
74         /* Round up alignment and size to multiples of MIN_MEMBLOCK_SIZE */
75         align = ( align + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
76         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
77
78         /* Search through blocks for the first one with enough space */
79         list_for_each_entry ( block, &free_blocks, list ) {
80                 pre_size = ( - virt_to_phys ( block ) ) & ( align - 1 );
81                 post_size = block->size - pre_size - size;
82                 if ( post_size >= 0 ) {
83                         /* Split block into pre-block, block, and
84                          * post-block.  After this split, the "pre"
85                          * block is the one currently linked into the
86                          * free list.
87                          */
88                         pre   = block;
89                         block = ( ( ( void * ) pre   ) + pre_size );
90                         post  = ( ( ( void * ) block ) + size     );
91                         /* If there is a "post" block, add it in to
92                          * the free list.  Leak it if it is too small
93                          * (which can happen only at the very end of
94                          * the heap).
95                          */
96                         if ( ( size_t ) post_size > MIN_MEMBLOCK_SIZE ) {
97                                 post->size = post_size;
98                                 list_add ( &post->list, &pre->list );
99                         }
100                         /* Shrink "pre" block, leaving the main block
101                          * isolated and no longer part of the free
102                          * list.
103                          */
104                         pre->size = pre_size;
105                         /* If there is no "pre" block, remove it from
106                          * the list.  Also remove it (i.e. leak it) if
107                          * it is too small, which can happen only at
108                          * the very start of the heap.
109                          */
110                         if ( pre_size < MIN_MEMBLOCK_SIZE )
111                                 list_del ( &pre->list );
112                         /* Zero allocated memory, for calloc() */
113                         memset ( block, 0, size );
114                         return block;
115                 }
116         }
117         return NULL;
118 }
119
120 /**
121  * Free a memory block
122  *
123  * @v ptr               Memory allocated by alloc_memblock(), or NULL
124  * @v size              Size of the memory
125  *
126  * If @c ptr is NULL, no action is taken.
127  */
128 void free_memblock ( void *ptr, size_t size ) {
129         struct memory_block *freeing;
130         struct memory_block *block;
131         ssize_t gap_before;
132         ssize_t gap_after;
133
134         /* Allow for ptr==NULL */
135         if ( ! ptr )
136                 return;
137
138         /* Round up size to match actual size that alloc_memblock()
139          * would have used.
140          */
141         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
142         freeing = ptr;
143         freeing->size = size;
144
145         /* Insert/merge into free list */
146         list_for_each_entry ( block, &free_blocks, list ) {
147                 /* Calculate gaps before and after the "freeing" block */
148                 gap_before = ( ( ( void * ) freeing ) - 
149                                ( ( ( void * ) block ) + block->size ) );
150                 gap_after = ( ( ( void * ) block ) - 
151                               ( ( ( void * ) freeing ) + freeing->size ) );
152                 /* Merge with immediately preceding block, if possible */
153                 if ( gap_before == 0 ) {
154                         block->size += size;
155                         list_del ( &block->list );
156                         freeing = block;
157                 }
158                 /* Insert before the immediately following block.  If
159                  * possible, merge the following block into the
160                  * "freeing" block.
161                  */
162                 if ( gap_after >= 0 ) {
163                         list_add_tail ( &freeing->list, &block->list );
164                         if ( gap_after == 0 ) {
165                                 freeing->size += block->size;
166                                 list_del ( &block->list );
167                         }
168                         break;
169                 }
170         }
171 }
172
173 /**
174  * Allocate memory
175  *
176  * @v size              Requested size
177  * @ret ptr             Memory, or NULL
178  *
179  * Allocates memory with no particular alignment requirement.  @c ptr
180  * will be aligned to at least a multiple of sizeof(void*).
181  *
182  * Note that malloc() is very inefficient for allocating blocks where
183  * the size is a power of two; if you have many of these
184  * (e.g. descriptor rings, data buffers) you should use malloc_dma()
185  * instead.
186  */
187 void * malloc ( size_t size ) {
188         size_t total_size;
189         struct autosized_block *block;
190
191         total_size = size + offsetof ( struct autosized_block, data );
192         block = alloc_memblock ( total_size, 1 );
193         if ( ! block )
194                 return NULL;
195         block->size = size;
196         return &block->data;
197 }
198
199 /**
200  * Free memory
201  *
202  * @v size              Memory allocated by malloc(), or NULL
203  *
204  * Memory allocated with malloc_dma() cannot be freed with free(); it
205  * must be freed with free_dma() instead.
206  *
207  * If @c ptr is NULL, no action is taken.
208  */
209 void free ( void *ptr ) {
210         struct autosized_block *block;
211
212         if ( ptr ) {
213                 block = container_of ( ptr, struct autosized_block, data );
214                 free_memblock ( block, block->size );
215         }
216 }
217
218 /**
219  * Add memory to allocation pool
220  *
221  * @v start             Start address
222  * @v end               End address
223  *
224  * Adds a block of memory [start,end) to the allocation pool.  This is
225  * a one-way operation; there is no way to reclaim this memory.
226  *
227  * @c start must be aligned to at least a multiple of sizeof(void*).
228  */
229 void mpopulate ( void *start, size_t len ) {
230         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
231 }
232
233 #if 1
234 #include <vsprintf.h>
235 /**
236  * Dump free block list
237  *
238  */
239 void mdumpfree ( void ) {
240         struct memory_block *block;
241
242         printf ( "Free block list:\n" );
243         list_for_each_entry ( block, &free_blocks, list ) {
244                 printf ( "[%p,%p] (size %zx)\n", block,
245                          ( ( ( void * ) block ) + block->size ), block->size );
246         }
247 }
248 #endif
249