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