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 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 128kB.
  82  */
  83 #define HEAP_SIZE ( 128 * 1024 )
  84
  85 /** The heap itself */
  86 static char heap[HEAP_SIZE] __attribute__ (( aligned ( __alignof__(void *) )));
  87
  88 /**
  89  * Discard some cached data
  90  *
  91  * @ret discarded       Number of cached items discarded
  92  */
  93 static unsigned int discard_cache ( void ) {
  94         struct cache_discarder *discarder;
  95         unsigned int discarded = 0;
  96
  97         for_each_table_entry ( discarder, CACHE_DISCARDERS ) {
  98                 discarded += discarder->discard();
  99         }
 100         return discarded;
 101 }
 102
 103 /**
 104  * Allocate a memory block
 105  *
 106  * @v size              Requested size
 107  * @v align             Physical alignment
 108  * @ret ptr             Memory block, or NULL
 109  *
 110  * Allocates a memory block @b physically aligned as requested.  No
 111  * guarantees are provided for the alignment of the virtual address.
 112  *
 113  * @c align must be a power of two.  @c size may not be zero.
 114  */
 115 void * alloc_memblock ( size_t size, size_t align ) {
 116         struct memory_block *block;
 117         size_t align_mask;
 118         size_t pre_size;
 119         ssize_t post_size;
 120         struct memory_block *pre;
 121         struct memory_block *post;
 122
 123         /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
 124          * calculate alignment mask.
 125          */
 126         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
 127         align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );
 128
 129         DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );
 130         while ( 1 ) {
 131                 /* Search through blocks for the first one with enough space */
 132                 list_for_each_entry ( block, &free_blocks, list ) {
 133                         pre_size = ( - virt_to_phys ( block ) ) & align_mask;
 134                         post_size = block->size - pre_size - size;
 135                         if ( post_size >= 0 ) {
 136                                 /* Split block into pre-block, block, and
 137                                  * post-block.  After this split, the "pre"
 138                                  * block is the one currently linked into the
 139                                  * free list.
 140                                  */
 141                                 pre   = block;
 142                                 block = ( ( ( void * ) pre   ) + pre_size );
 143                                 post  = ( ( ( void * ) block ) + size     );
 144                                 DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
 145                                       ( ( ( void * ) pre ) + pre->size ),
 146                                       pre, block, post,
 147                                       ( ( ( void * ) pre ) + pre->size ) );
 148                                 /* If there is a "post" block, add it in to
 149                                  * the free list.  Leak it if it is too small
 150                                  * (which can happen only at the very end of
 151                                  * the heap).
 152                                  */
 153                                 if ( (size_t) post_size >= MIN_MEMBLOCK_SIZE ) {
 154                                         post->size = post_size;
 155                                         list_add ( &post->list, &pre->list );
 156                                 }
 157                                 /* Shrink "pre" block, leaving the main block
 158                                  * isolated and no longer part of the free
 159                                  * list.
 160                                  */
 161                                 pre->size = pre_size;
 162                                 /* If there is no "pre" block, remove it from
 163                                  * the list.  Also remove it (i.e. leak it) if
 164                                  * it is too small, which can happen only at
 165                                  * the very start of the heap.
 166                                  */
 167                                 if ( pre_size < MIN_MEMBLOCK_SIZE )
 168                                         list_del ( &pre->list );
 169                                 /* Update total free memory */
 170                                 freemem -= size;
 171                                 /* Return allocated block */
 172                                 DBG ( "Allocated [%p,%p)\n", block,
 173                                       ( ( ( void * ) block ) + size ) );
 174                                 return block;
 175                         }
 176                 }
 177
 178                 /* Try discarding some cached data to free up memory */
 179                 if ( ! discard_cache() ) {
 180                         /* Nothing available to discard */
 181                         DBG ( "Failed to allocate %#zx (aligned %#zx)\n",
 182                               size, align );
 183                         return NULL;
 184                 }
 185         }
 186 }
 187
 188 /**
 189  * Free a memory block
 190  *
 191  * @v ptr               Memory allocated by alloc_memblock(), or NULL
 192  * @v size              Size of the memory
 193  *
 194  * If @c ptr is NULL, no action is taken.
 195  */
 196 void free_memblock ( void *ptr, size_t size ) {
 197         struct memory_block *freeing;
 198         struct memory_block *block;
 199         ssize_t gap_before;
 200         ssize_t gap_after = -1;
 201
 202         /* Allow for ptr==NULL */
 203         if ( ! ptr )
 204                 return;
 205
 206         /* Round up size to match actual size that alloc_memblock()
 207          * would have used.
 208          */
 209         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
 210         freeing = ptr;
 211         freeing->size = size;
 212         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
 213
 214         /* Insert/merge into free list */
 215         list_for_each_entry ( block, &free_blocks, list ) {
 216                 /* Calculate gaps before and after the "freeing" block */
 217                 gap_before = ( ( ( void * ) freeing ) -
 218                                ( ( ( void * ) block ) + block->size ) );
 219                 gap_after = ( ( ( void * ) block ) -
 220                               ( ( ( void * ) freeing ) + freeing->size ) );
 221                 /* Merge with immediately preceding block, if possible */
 222                 if ( gap_before == 0 ) {
 223                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
 224                               ( ( ( void * ) block ) + block->size ), freeing,
 225                               ( ( ( void * ) freeing ) + freeing->size ),block,
 226                               ( ( ( void * ) freeing ) + freeing->size ) );
 227                         block->size += size;
 228                         list_del ( &block->list );
 229                         freeing = block;
 230                 }
 231                 /* Stop processing as soon as we reach a following block */
 232                 if ( gap_after >= 0 )
 233                         break;
 234         }
 235
 236         /* Insert before the immediately following block.  If
 237          * possible, merge the following block into the "freeing"
 238          * block.
 239          */
 240         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
 241         list_add_tail ( &freeing->list, &block->list );
 242         if ( gap_after == 0 ) {
 243                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
 244                       ( ( ( void * ) freeing ) + freeing->size ), block,
 245                       ( ( ( void * ) block ) + block->size ), freeing,
 246                       ( ( ( void * ) block ) + block->size ) );
 247                 freeing->size += block->size;
 248                 list_del ( &block->list );
 249         }
 250
 251         /* Update free memory counter */
 252         freemem += size;
 253 }
 254
 255 /**
 256  * Reallocate memory
 257  *
 258  * @v old_ptr           Memory previously allocated by malloc(), or NULL
 259  * @v new_size          Requested size
 260  * @ret new_ptr         Allocated memory, or NULL
 261  *
 262  * Allocates memory with no particular alignment requirement.  @c
 263  * new_ptr will be aligned to at least a multiple of sizeof(void*).
 264  * If @c old_ptr is non-NULL, then the contents of the newly allocated
 265  * memory will be the same as the contents of the previously allocated
 266  * memory, up to the minimum of the old and new sizes.  The old memory
 267  * will be freed.
 268  *
 269  * If allocation fails the previously allocated block is left
 270  * untouched and NULL is returned.
 271  *
 272  * Calling realloc() with a new size of zero is a valid way to free a
 273  * memory block.
 274  */
 275 void * realloc ( void *old_ptr, size_t new_size ) {
 276         struct autosized_block *old_block;
 277         struct autosized_block *new_block;
 278         size_t old_total_size;
 279         size_t new_total_size;
 280         size_t old_size;
 281         void *new_ptr = NOWHERE;
 282
 283         /* Allocate new memory if necessary.  If allocation fails,
 284          * return without touching the old block.
 285          */
 286         if ( new_size ) {
 287                 new_total_size = ( new_size +
 288                                    offsetof ( struct autosized_block, data ) );
 289                 new_block = alloc_memblock ( new_total_size, 1 );
 290                 if ( ! new_block )
 291                         return NULL;
 292                 new_block->size = new_total_size;
 293                 new_ptr = &new_block->data;
 294         }
 295
 296         /* Copy across relevant part of the old data region (if any),
 297          * then free it.  Note that at this point either (a) new_ptr
 298          * is valid, or (b) new_size is 0; either way, the memcpy() is
 299          * valid.
 300          */
 301         if ( old_ptr && ( old_ptr != NOWHERE ) ) {
 302                 old_block = container_of ( old_ptr, struct autosized_block,
 303                                            data );
 304                 old_total_size = old_block->size;
 305                 old_size = ( old_total_size -
 306                              offsetof ( struct autosized_block, data ) );
 307                 memcpy ( new_ptr, old_ptr,
 308                          ( ( old_size < new_size ) ? old_size : new_size ) );
 309                 free_memblock ( old_block, old_total_size );
 310         }
 311
 312         return new_ptr;
 313 }
 314
 315 /**
 316  * Allocate memory
 317  *
 318  * @v size              Requested size
 319  * @ret ptr             Memory, or NULL
 320  *
 321  * Allocates memory with no particular alignment requirement.  @c ptr
 322  * will be aligned to at least a multiple of sizeof(void*).
 323  */
 324 void * malloc ( size_t size ) {
 325         return realloc ( NULL, size );
 326 }
 327
 328 /**
 329  * Free memory
 330  *
 331  * @v ptr               Memory allocated by malloc(), or NULL
 332  *
 333  * Memory allocated with malloc_dma() cannot be freed with free(); it
 334  * must be freed with free_dma() instead.
 335  *
 336  * If @c ptr is NULL, no action is taken.
 337  */
 338 void free ( void *ptr ) {
 339         realloc ( ptr, 0 );
 340 }
 341
 342 /**
 343  * Allocate cleared memory
 344  *
 345  * @v size              Requested size
 346  * @ret ptr             Allocated memory
 347  *
 348  * Allocate memory as per malloc(), and zero it.
 349  *
 350  * This function name is non-standard, but pretty intuitive.
 351  * zalloc(size) is always equivalent to calloc(1,size)
 352  */
 353 void * zalloc ( size_t size ) {
 354         void *data;
 355
 356         data = malloc ( size );
 357         if ( data )
 358                 memset ( data, 0, size );
 359         return data;
 360 }
 361
 362 /**
 363  * Add memory to allocation pool
 364  *
 365  * @v start             Start address
 366  * @v end               End address
 367  *
 368  * Adds a block of memory [start,end) to the allocation pool.  This is
 369  * a one-way operation; there is no way to reclaim this memory.
 370  *
 371  * @c start must be aligned to at least a multiple of sizeof(void*).
 372  */
 373 void mpopulate ( void *start, size_t len ) {
 374         /* Prevent free_memblock() from rounding up len beyond the end
 375          * of what we were actually given...
 376          */
 377         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
 378 }
 379
 380 /**
 381  * Initialise the heap
 382  *
 383  */
 384 static void init_heap ( void ) {
 385         mpopulate ( heap, sizeof ( heap ) );
 386 }
 387
 388 /** Memory allocator initialisation function */
 389 struct init_fn heap_init_fn __init_fn ( INIT_EARLY ) = {
 390         .initialise = init_heap,
 391 };
 392
 393 #if 0
 394 #include <stdio.h>
 395 /**
 396  * Dump free block list
 397  *
 398  */
 399 void mdumpfree ( void ) {
 400         struct memory_block *block;
 401
 402         printf ( "Free block list:\n" );
 403         list_for_each_entry ( block, &free_blocks, list ) {
 404                 printf ( "[%p,%p] (size %#zx)\n", block,
 405                          ( ( ( void * ) block ) + block->size ), block->size );
 406         }
 407 }
 408 #endif