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