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 /**
  53  * Address for zero-length memory blocks
  54  *
  55  * @c malloc(0) or @c realloc(ptr,0) will return the special value @c
  56  * NOWHERE.  Calling @c free(NOWHERE) will have no effect.
  57  *
  58  * This is consistent with the ANSI C standards, which state that
  59  * "either NULL or a pointer suitable to be passed to free()" must be
  60  * returned in these cases.  Using a special non-NULL value means that
  61  * the caller can take a NULL return value to indicate failure,
  62  * without first having to check for a requested size of zero.
  63  *
  64  * Code outside of malloc.c do not ever need to refer to the actual
  65  * value of @c NOWHERE; this is an internal definition.
  66  */
  67 #define NOWHERE ( ( void * ) ~( ( intptr_t ) 0 ) )
  68
  69 /** List of free memory blocks */
  70 static LIST_HEAD ( free_blocks );
  71
  72 /**
  73  * Allocate a memory block
  74  *
  75  * @v size              Requested size
  76  * @v align             Physical alignment
  77  * @ret ptr             Memory block, or NULL
  78  *
  79  * Allocates a memory block @b physically aligned as requested.  No
  80  * guarantees are provided for the alignment of the virtual address.
  81  *
  82  * @c align must be a power of two.  @c size may not be zero.
  83  */
  84 void * alloc_memblock ( size_t size, size_t align ) {
  85         struct memory_block *block;
  86         size_t align_mask;
  87         size_t pre_size;
  88         ssize_t post_size;
  89         struct memory_block *pre;
  90         struct memory_block *post;
  91
  92         /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
  93          * calculate alignment mask.
  94          */
  95         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
  96         align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );
  97
  98         DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );
  99
 100         /* Search through blocks for the first one with enough space */
 101         list_for_each_entry ( block, &free_blocks, list ) {
 102                 pre_size = ( - virt_to_phys ( block ) ) & align_mask;
 103                 post_size = block->size - pre_size - size;
 104                 if ( post_size >= 0 ) {
 105                         /* Split block into pre-block, block, and
 106                          * post-block.  After this split, the "pre"
 107                          * block is the one currently linked into the
 108                          * free list.
 109                          */
 110                         pre   = block;
 111                         block = ( ( ( void * ) pre   ) + pre_size );
 112                         post  = ( ( ( void * ) block ) + size     );
 113                         DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
 114                               ( ( ( void * ) pre ) + pre->size ), pre, block,
 115                               post, ( ( ( void * ) pre ) + pre->size ) );
 116                         /* If there is a "post" block, add it in to
 117                          * the free list.  Leak it if it is too small
 118                          * (which can happen only at the very end of
 119                          * the heap).
 120                          */
 121                         if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
 122                                 post->size = post_size;
 123                                 list_add ( &post->list, &pre->list );
 124                         }
 125                         /* Shrink "pre" block, leaving the main block
 126                          * isolated and no longer part of the free
 127                          * list.
 128                          */
 129                         pre->size = pre_size;
 130                         /* If there is no "pre" block, remove it from
 131                          * the list.  Also remove it (i.e. leak it) if
 132                          * it is too small, which can happen only at
 133                          * the very start of the heap.
 134                          */
 135                         if ( pre_size < MIN_MEMBLOCK_SIZE )
 136                                 list_del ( &pre->list );
 137                         /* Zero allocated memory, for calloc() */
 138                         memset ( block, 0, size );
 139                         DBG ( "Allocated [%p,%p)\n", block,
 140                               ( ( ( void * ) block ) + size ) );
 141                         return block;
 142                 }
 143         }
 144
 145         DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
 146         return NULL;
 147 }
 148
 149 /**
 150  * Free a memory block
 151  *
 152  * @v ptr               Memory allocated by alloc_memblock(), or NULL
 153  * @v size              Size of the memory
 154  *
 155  * If @c ptr is NULL, no action is taken.
 156  */
 157 void free_memblock ( void *ptr, size_t size ) {
 158         struct memory_block *freeing;
 159         struct memory_block *block;
 160         ssize_t gap_before;
 161         ssize_t gap_after = -1;
 162
 163         /* Allow for ptr==NULL */
 164         if ( ! ptr )
 165                 return;
 166
 167         /* Round up size to match actual size that alloc_memblock()
 168          * would have used.
 169          */
 170         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
 171         freeing = ptr;
 172         freeing->size = size;
 173         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
 174
 175         /* Insert/merge into free list */
 176         list_for_each_entry ( block, &free_blocks, list ) {
 177                 /* Calculate gaps before and after the "freeing" block */
 178                 gap_before = ( ( ( void * ) freeing ) -
 179                                ( ( ( void * ) block ) + block->size ) );
 180                 gap_after = ( ( ( void * ) block ) -
 181                               ( ( ( void * ) freeing ) + freeing->size ) );
 182                 /* Merge with immediately preceding block, if possible */
 183                 if ( gap_before == 0 ) {
 184                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
 185                               ( ( ( void * ) block ) + block->size ), freeing,
 186                               ( ( ( void * ) freeing ) + freeing->size ),block,
 187                               ( ( ( void * ) freeing ) + freeing->size ) );
 188                         block->size += size;
 189                         list_del ( &block->list );
 190                         freeing = block;
 191                 }
 192                 /* Stop processing as soon as we reach a following block */
 193                 if ( gap_after >= 0 )
 194                         break;
 195         }
 196
 197         /* Insert before the immediately following block.  If
 198          * possible, merge the following block into the "freeing"
 199          * block.
 200          */
 201         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
 202         list_add_tail ( &freeing->list, &block->list );
 203         if ( gap_after == 0 ) {
 204                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
 205                       ( ( ( void * ) freeing ) + freeing->size ), block,
 206                       ( ( ( void * ) block ) + block->size ), freeing,
 207                       ( ( ( void * ) block ) + block->size ) );
 208                 freeing->size += block->size;
 209                 list_del ( &block->list );
 210         }
 211 }
 212
 213 /**
 214  * Reallocate memory
 215  *
 216  * @v old_ptr           Memory previously allocated by malloc(), or NULL
 217  * @v new_size          Requested size
 218  * @ret new_ptr         Allocated memory, or NULL
 219  *
 220  * Allocates memory with no particular alignment requirement.  @c
 221  * new_ptr will be aligned to at least a multiple of sizeof(void*).
 222  * If @c old_ptr is non-NULL, then the contents of the newly allocated
 223  * memory will be the same as the contents of the previously allocated
 224  * memory, up to the minimum of the old and new sizes.  The old memory
 225  * will be freed.
 226  *
 227  * If allocation fails the previously allocated block is left
 228  * untouched and NULL is returned.
 229  *
 230  * Calling realloc() with a new size of zero is a valid way to free a
 231  * memory block.
 232  */
 233 void * realloc ( void *old_ptr, size_t new_size ) {
 234         struct autosized_block *old_block;
 235         struct autosized_block *new_block;
 236         size_t old_total_size;
 237         size_t new_total_size;
 238         size_t old_size;
 239         void *new_ptr = NOWHERE;
 240
 241         /* Allocate new memory if necessary.  If allocation fails,
 242          * return without touching the old block.
 243          */
 244         if ( new_size ) {
 245                 new_total_size = ( new_size +
 246                                    offsetof ( struct autosized_block, data ) );
 247                 new_block = alloc_memblock ( new_total_size, 1 );
 248                 if ( ! new_block )
 249                         return NULL;
 250                 new_block->size = new_total_size;
 251                 new_ptr = &new_block->data;
 252         }
 253
 254         /* Copy across relevant part of the old data region (if any),
 255          * then free it.  Note that at this point either (a) new_ptr
 256          * is valid, or (b) new_size is 0; either way, the memcpy() is
 257          * valid.
 258          */
 259         if ( old_ptr && ( old_ptr != NOWHERE ) ) {
 260                 old_block = container_of ( old_ptr, struct autosized_block,
 261                                            data );
 262                 old_total_size = old_block->size;
 263                 old_size = ( old_total_size -
 264                              offsetof ( struct autosized_block, data ) );
 265                 memcpy ( new_ptr, old_ptr,
 266                          ( ( old_size < new_size ) ? old_size : new_size ) );
 267                 free_memblock ( old_block, old_total_size );
 268         }
 269
 270         return new_ptr;
 271 }
 272
 273 /**
 274  * Allocate memory
 275  *
 276  * @v size              Requested size
 277  * @ret ptr             Memory, or NULL
 278  *
 279  * Allocates memory with no particular alignment requirement.  @c ptr
 280  * will be aligned to at least a multiple of sizeof(void*).
 281  */
 282 void * malloc ( size_t size ) {
 283         return realloc ( NULL, size );
 284 }
 285
 286 /**
 287  * Free memory
 288  *
 289  * @v ptr               Memory allocated by malloc(), or NULL
 290  *
 291  * Memory allocated with malloc_dma() cannot be freed with free(); it
 292  * must be freed with free_dma() instead.
 293  *
 294  * If @c ptr is NULL, no action is taken.
 295  */
 296 void free ( void *ptr ) {
 297         realloc ( ptr, 0 );
 298 }
 299
 300 /**
 301  * Add memory to allocation pool
 302  *
 303  * @v start             Start address
 304  * @v end               End address
 305  *
 306  * Adds a block of memory [start,end) to the allocation pool.  This is
 307  * a one-way operation; there is no way to reclaim this memory.
 308  *
 309  * @c start must be aligned to at least a multiple of sizeof(void*).
 310  */
 311 void mpopulate ( void *start, size_t len ) {
 312         /* Prevent free_memblock() from rounding up len beyond the end
 313          * of what we were actually given...
 314          */
 315         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
 316 }
 317
 318 #if 0
 319 #include <vsprintf.h>
 320 /**
 321  * Dump free block list
 322  *
 323  */
 324 void mdumpfree ( void ) {
 325         struct memory_block *block;
 326
 327         printf ( "Free block list:\n" );
 328         list_for_each_entry ( block, &free_blocks, list ) {
 329                 printf ( "[%p,%p] (size %#zx)\n", block,
 330                          ( ( ( void * ) block ) + block->size ), block->size );
 331         }
 332 }
 333 #endif