1 /* 2 * Copyright (C) 2006 Michael Brown <mbrown (at) 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 FILE_LICENCE ( GPL2_OR_LATER ); 20 21 #include <stddef.h> 22 #include <stdint.h> 23 #include <string.h> 24 #include <strings.h> 25 #include <gpxe/io.h> 26 #include <gpxe/list.h> 27 #include <gpxe/init.h> 28 #include <gpxe/malloc.h> 29 30 /** @file 31 * 32 * Dynamic memory allocation 33 * 34 */ 35 36 /** A free block of memory */ 37 struct memory_block { 38 /** List of free blocks */ 39 struct list_head list; 40 /** Size of this block */ 41 size_t size; 42 }; 43 44 #define MIN_MEMBLOCK_SIZE \ 45 ( ( size_t ) ( 1 << ( fls ( sizeof ( struct memory_block ) - 1 ) ) ) ) 46 47 /** A block of allocated memory complete with size information */ 48 struct autosized_block { 49 /** Size of this block */ 50 size_t size; 51 /** Remaining data */ 52 char data[0]; 53 }; 54 55 /** 56 * Address for zero-length memory blocks 57 * 58 * @c malloc(0) or @c realloc(ptr,0) will return the special value @c 59 * NOWHERE. Calling @c free(NOWHERE) will have no effect. 60 * 61 * This is consistent with the ANSI C standards, which state that 62 * "either NULL or a pointer suitable to be passed to free()" must be 63 * returned in these cases. Using a special non-NULL value means that 64 * the caller can take a NULL return value to indicate failure, 65 * without first having to check for a requested size of zero. 66 * 67 * Code outside of malloc.c do not ever need to refer to the actual 68 * value of @c NOWHERE; this is an internal definition. 69 */ 70 #define NOWHERE ( ( void * ) ~( ( intptr_t ) 0 ) ) 71 72 /** List of free memory blocks */ 73 static LIST_HEAD ( free_blocks ); 74 75 /** Total amount of free memory */ 76 size_t freemem; 77 78 /** 79 * Heap size 80 * 81 * Currently fixed at 512kB. 82 */ 83 #define HEAP_SIZE ( 512 * 1024 ) 84 85 /** The heap itself */ 86 static char heap[HEAP_SIZE] __attribute__ (( aligned ( __alignof__(void *) ))); 87 88 /** 89 * Allocate a memory block 90 * 91 * @v size Requested size 92 * @v align Physical alignment 93 * @ret ptr Memory block, or NULL 94 * 95 * Allocates a memory block @b physically aligned as requested. No 96 * guarantees are provided for the alignment of the virtual address. 97 * 98 * @c align must be a power of two. @c size may not be zero. 99 */ 100 void * alloc_memblock ( size_t size, size_t align ) { 101 struct memory_block *block; 102 size_t align_mask; 103 size_t pre_size; 104 ssize_t post_size; 105 struct memory_block *pre; 106 struct memory_block *post; 107 108 /* Round up size to multiple of MIN_MEMBLOCK_SIZE and 109 * calculate alignment mask. 110 */ 111 size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 ); 112 align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 ); 113 114 DBG ( "Allocating %#zx (aligned %#zx)\n", size, align ); 115 116 /* Search through blocks for the first one with enough space */ 117 list_for_each_entry ( block, &free_blocks, list ) { 118 pre_size = ( - virt_to_phys ( block ) ) & align_mask; 119 post_size = block->size - pre_size - size; 120 if ( post_size >= 0 ) { 121 /* Split block into pre-block, block, and 122 * post-block. After this split, the "pre" 123 * block is the one currently linked into the 124 * free list. 125 */ 126 pre = block; 127 block = ( ( ( void * ) pre ) + pre_size ); 128 post = ( ( ( void * ) block ) + size ); 129 DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre, 130 ( ( ( void * ) pre ) + pre->size ), pre, block, 131 post, ( ( ( void * ) pre ) + pre->size ) ); 132 /* If there is a "post" block, add it in to 133 * the free list. Leak it if it is too small 134 * (which can happen only at the very end of 135 * the heap). 136 */ 137 if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) { 138 post->size = post_size; 139 list_add ( &post->list, &pre->list ); 140 } 141 /* Shrink "pre" block, leaving the main block 142 * isolated and no longer part of the free 143 * list. 144 */ 145 pre->size = pre_size; 146 /* If there is no "pre" block, remove it from 147 * the list. Also remove it (i.e. leak it) if 148 * it is too small, which can happen only at 149 * the very start of the heap. 150 */ 151 if ( pre_size < MIN_MEMBLOCK_SIZE ) 152 list_del ( &pre->list ); 153 /* Update total free memory */ 154 freemem -= size; 155 /* Return allocated block */ 156 DBG ( "Allocated [%p,%p)\n", block, 157 ( ( ( void * ) block ) + size ) ); 158 return block; 159 } 160 } 161 162 DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align ); 163 return NULL; 164 } 165 166 /** 167 * Free a memory block 168 * 169 * @v ptr Memory allocated by alloc_memblock(), or NULL 170 * @v size Size of the memory 171 * 172 * If @c ptr is NULL, no action is taken. 173 */ 174 void free_memblock ( void *ptr, size_t size ) { 175 struct memory_block *freeing; 176 struct memory_block *block; 177 ssize_t gap_before; 178 ssize_t gap_after = -1; 179 180 /* Allow for ptr==NULL */ 181 if ( ! ptr ) 182 return; 183 184 /* Round up size to match actual size that alloc_memblock() 185 * would have used. 186 */ 187 size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 ); 188 freeing = ptr; 189 freeing->size = size; 190 DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size )); 191 192 /* Insert/merge into free list */ 193 list_for_each_entry ( block, &free_blocks, list ) { 194 /* Calculate gaps before and after the "freeing" block */ 195 gap_before = ( ( ( void * ) freeing ) - 196 ( ( ( void * ) block ) + block->size ) ); 197 gap_after = ( ( ( void * ) block ) - 198 ( ( ( void * ) freeing ) + freeing->size ) ); 199 /* Merge with immediately preceding block, if possible */ 200 if ( gap_before == 0 ) { 201 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block, 202 ( ( ( void * ) block ) + block->size ), freeing, 203 ( ( ( void * ) freeing ) + freeing->size ),block, 204 ( ( ( void * ) freeing ) + freeing->size ) ); 205 block->size += size; 206 list_del ( &block->list ); 207 freeing = block; 208 } 209 /* Stop processing as soon as we reach a following block */ 210 if ( gap_after >= 0 ) 211 break; 212 } 213 214 /* Insert before the immediately following block. If 215 * possible, merge the following block into the "freeing" 216 * block. 217 */ 218 DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size)); 219 list_add_tail ( &freeing->list, &block->list ); 220 if ( gap_after == 0 ) { 221 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing, 222 ( ( ( void * ) freeing ) + freeing->size ), block, 223 ( ( ( void * ) block ) + block->size ), freeing, 224 ( ( ( void * ) block ) + block->size ) ); 225 freeing->size += block->size; 226 list_del ( &block->list ); 227 } 228 229 /* Update free memory counter */ 230 freemem += size; 231 } 232 233 /** 234 * Reallocate memory 235 * 236 * @v old_ptr Memory previously allocated by malloc(), or NULL 237 * @v new_size Requested size 238 * @ret new_ptr Allocated memory, or NULL 239 * 240 * Allocates memory with no particular alignment requirement. @c 241 * new_ptr will be aligned to at least a multiple of sizeof(void*). 242 * If @c old_ptr is non-NULL, then the contents of the newly allocated 243 * memory will be the same as the contents of the previously allocated 244 * memory, up to the minimum of the old and new sizes. The old memory 245 * will be freed. 246 * 247 * If allocation fails the previously allocated block is left 248 * untouched and NULL is returned. 249 * 250 * Calling realloc() with a new size of zero is a valid way to free a 251 * memory block. 252 */ 253 void * realloc ( void *old_ptr, size_t new_size ) { 254 struct autosized_block *old_block; 255 struct autosized_block *new_block; 256 size_t old_total_size; 257 size_t new_total_size; 258 size_t old_size; 259 void *new_ptr = NOWHERE; 260 261 /* Allocate new memory if necessary. If allocation fails, 262 * return without touching the old block. 263 */ 264 if ( new_size ) { 265 new_total_size = ( new_size + 266 offsetof ( struct autosized_block, data ) ); 267 new_block = alloc_memblock ( new_total_size, 1 ); 268 if ( ! new_block ) 269 return NULL; 270 new_block->size = new_total_size; 271 new_ptr = &new_block->data; 272 } 273 274 /* Copy across relevant part of the old data region (if any), 275 * then free it. Note that at this point either (a) new_ptr 276 * is valid, or (b) new_size is 0; either way, the memcpy() is 277 * valid. 278 */ 279 if ( old_ptr && ( old_ptr != NOWHERE ) ) { 280 old_block = container_of ( old_ptr, struct autosized_block, 281 data ); 282 old_total_size = old_block->size; 283 old_size = ( old_total_size - 284 offsetof ( struct autosized_block, data ) ); 285 memcpy ( new_ptr, old_ptr, 286 ( ( old_size < new_size ) ? old_size : new_size ) ); 287 free_memblock ( old_block, old_total_size ); 288 } 289 290 return new_ptr; 291 } 292 293 /** 294 * Allocate memory 295 * 296 * @v size Requested size 297 * @ret ptr Memory, or NULL 298 * 299 * Allocates memory with no particular alignment requirement. @c ptr 300 * will be aligned to at least a multiple of sizeof(void*). 301 */ 302 void * malloc ( size_t size ) { 303 return realloc ( NULL, size ); 304 } 305 306 /** 307 * Free memory 308 * 309 * @v ptr Memory allocated by malloc(), or NULL 310 * 311 * Memory allocated with malloc_dma() cannot be freed with free(); it 312 * must be freed with free_dma() instead. 313 * 314 * If @c ptr is NULL, no action is taken. 315 */ 316 void free ( void *ptr ) { 317 realloc ( ptr, 0 ); 318 } 319 320 /** 321 * Allocate cleared memory 322 * 323 * @v size Requested size 324 * @ret ptr Allocated memory 325 * 326 * Allocate memory as per malloc(), and zero it. 327 * 328 * This function name is non-standard, but pretty intuitive. 329 * zalloc(size) is always equivalent to calloc(1,size) 330 */ 331 void * zalloc ( size_t size ) { 332 void *data; 333 334 data = malloc ( size ); 335 if ( data ) 336 memset ( data, 0, size ); 337 return data; 338 } 339 340 /** 341 * Add memory to allocation pool 342 * 343 * @v start Start address 344 * @v end End address 345 * 346 * Adds a block of memory [start,end) to the allocation pool. This is 347 * a one-way operation; there is no way to reclaim this memory. 348 * 349 * @c start must be aligned to at least a multiple of sizeof(void*). 350 */ 351 void mpopulate ( void *start, size_t len ) { 352 /* Prevent free_memblock() from rounding up len beyond the end 353 * of what we were actually given... 354 */ 355 free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) ); 356 } 357 358 /** 359 * Initialise the heap 360 * 361 */ 362 static void init_heap ( void ) { 363 mpopulate ( heap, sizeof ( heap ) ); 364 } 365 366 /** Memory allocator initialisation function */ 367 struct init_fn heap_init_fn __init_fn ( INIT_EARLY ) = { 368 .initialise = init_heap, 369 }; 370 371 #if 0 372 #include <stdio.h> 373 /** 374 * Dump free block list 375 * 376 */ 377 void mdumpfree ( void ) { 378 struct memory_block *block; 379 380 printf ( "Free block list:\n" ); 381 list_for_each_entry ( block, &free_blocks, list ) { 382 printf ( "[%p,%p] (size %#zx)\n", block, 383 ( ( ( void * ) block ) + block->size ), block->size ); 384 } 385 } 386 #endif 387
