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 <stdio.h>
  20 #include <stddef.h>
  21 #include <stdint.h>
  22 #include <string.h>
  23 #include <strings.h>
  24 #include <io.h>
  25 #include <gpxe/list.h>
  26 #include <malloc.h>
  27
  28 /** @file
  29  *
  30  * Dynamic memory allocation
  31  *
  32  */
  33
  34 /** A free block of memory */
  35 struct memory_block {
  36         /** List of free blocks */
  37         struct list_head list;
  38         /** Size of this block */
  39         size_t size;
  40 };
  41
  42 #define MIN_MEMBLOCK_SIZE \
  43         ( ( size_t ) ( 1 << ( fls ( sizeof ( struct memory_block ) - 1 ) ) ) )
  44
  45 /** A block of allocated memory complete with size information */
  46 struct autosized_block {
  47         /** Size of this block */
  48         size_t size;
  49         /** Remaining data */
  50         char data[0];
  51 };
  52
  53 /** List of free memory blocks */
  54 static LIST_HEAD ( free_blocks );
  55
  56 /**
  57  * Allocate a memory block
  58  *
  59  * @v size              Requested size
  60  * @v align             Physical alignment
  61  * @ret ptr             Memory block, or NULL
  62  *
  63  * Allocates a memory block @b physically aligned as requested.  No
  64  * guarantees are provided for the alignment of the virtual address.
  65  *
  66  * @c align must be a power of two.  @c size may not be zero.
  67  */
  68 void * alloc_memblock ( size_t size, size_t align ) {
  69         struct memory_block *block;
  70         size_t align_mask;
  71         size_t pre_size;
  72         ssize_t post_size;
  73         struct memory_block *pre;
  74         struct memory_block *post;
  75
  76         /* Round up size to multiple of MIN_MEMBLOCK_SIZE and
  77          * calculate alignment mask.
  78          */
  79         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
  80         align_mask = ( align - 1 ) | ( MIN_MEMBLOCK_SIZE - 1 );
  81
  82         DBG ( "Allocating %#zx (aligned %#zx)\n", size, align );
  83
  84         /* Search through blocks for the first one with enough space */
  85         list_for_each_entry ( block, &free_blocks, list ) {
  86                 pre_size = ( - virt_to_phys ( block ) ) & align_mask;
  87                 post_size = block->size - pre_size - size;
  88                 if ( post_size >= 0 ) {
  89                         /* Split block into pre-block, block, and
  90                          * post-block.  After this split, the "pre"
  91                          * block is the one currently linked into the
  92                          * free list.
  93                          */
  94                         pre   = block;
  95                         block = ( ( ( void * ) pre   ) + pre_size );
  96                         post  = ( ( ( void * ) block ) + size     );
  97                         DBG ( "[%p,%p) -> [%p,%p) + [%p,%p)\n", pre,
  98                               ( ( ( void * ) pre ) + pre->size ), pre, block,
  99                               post, ( ( ( void * ) pre ) + pre->size ) );
 100                         /* If there is a "post" block, add it in to
 101                          * the free list.  Leak it if it is too small
 102                          * (which can happen only at the very end of
 103                          * the heap).
 104                          */
 105                         if ( ( size_t ) post_size >= MIN_MEMBLOCK_SIZE ) {
 106                                 post->size = post_size;
 107                                 list_add ( &post->list, &pre->list );
 108                         }
 109                         /* Shrink "pre" block, leaving the main block
 110                          * isolated and no longer part of the free
 111                          * list.
 112                          */
 113                         pre->size = pre_size;
 114                         /* If there is no "pre" block, remove it from
 115                          * the list.  Also remove it (i.e. leak it) if
 116                          * it is too small, which can happen only at
 117                          * the very start of the heap.
 118                          */
 119                         if ( pre_size < MIN_MEMBLOCK_SIZE )
 120                                 list_del ( &pre->list );
 121                         /* Zero allocated memory, for calloc() */
 122                         memset ( block, 0, size );
 123                         DBG ( "Allocated [%p,%p)\n", block,
 124                               ( ( ( void * ) block ) + size ) );
 125                         return block;
 126                 }
 127         }
 128
 129         DBG ( "Failed to allocate %#zx (aligned %#zx)\n", size, align );
 130         return NULL;
 131 }
 132
 133 /**
 134  * Free a memory block
 135  *
 136  * @v ptr               Memory allocated by alloc_memblock(), or NULL
 137  * @v size              Size of the memory
 138  *
 139  * If @c ptr is NULL, no action is taken.
 140  */
 141 void free_memblock ( void *ptr, size_t size ) {
 142         struct memory_block *freeing;
 143         struct memory_block *block;
 144         ssize_t gap_before;
 145         ssize_t gap_after = -1;
 146
 147         /* Allow for ptr==NULL */
 148         if ( ! ptr )
 149                 return;
 150
 151         /* Round up size to match actual size that alloc_memblock()
 152          * would have used.
 153          */
 154         size = ( size + MIN_MEMBLOCK_SIZE - 1 ) & ~( MIN_MEMBLOCK_SIZE - 1 );
 155         freeing = ptr;
 156         freeing->size = size;
 157         DBG ( "Freeing [%p,%p)\n", freeing, ( ( ( void * ) freeing ) + size ));
 158
 159         /* Insert/merge into free list */
 160         list_for_each_entry ( block, &free_blocks, list ) {
 161                 /* Calculate gaps before and after the "freeing" block */
 162                 gap_before = ( ( ( void * ) freeing ) -
 163                                ( ( ( void * ) block ) + block->size ) );
 164                 gap_after = ( ( ( void * ) block ) -
 165                               ( ( ( void * ) freeing ) + freeing->size ) );
 166                 /* Merge with immediately preceding block, if possible */
 167                 if ( gap_before == 0 ) {
 168                         DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", block,
 169                               ( ( ( void * ) block ) + block->size ), freeing,
 170                               ( ( ( void * ) freeing ) + freeing->size ),block,
 171                               ( ( ( void * ) freeing ) + freeing->size ) );
 172                         block->size += size;
 173                         list_del ( &block->list );
 174                         freeing = block;
 175                 }
 176                 /* Stop processing as soon as we reach a following block */
 177                 if ( gap_after >= 0 )
 178                         break;
 179         }
 180
 181         /* Insert before the immediately following block.  If
 182          * possible, merge the following block into the "freeing"
 183          * block.
 184          */
 185         DBG ( "[%p,%p)\n", freeing, ( ( ( void * ) freeing ) + freeing->size));
 186         list_add_tail ( &freeing->list, &block->list );
 187         if ( gap_after == 0 ) {
 188                 DBG ( "[%p,%p) + [%p,%p) -> [%p,%p)\n", freeing,
 189                       ( ( ( void * ) freeing ) + freeing->size ), block,
 190                       ( ( ( void * ) block ) + block->size ), freeing,
 191                       ( ( ( void * ) block ) + block->size ) );
 192                 freeing->size += block->size;
 193                 list_del ( &block->list );
 194         }
 195 }
 196
 197 /**
 198  * Allocate memory
 199  *
 200  * @v size              Requested size
 201  * @ret ptr             Memory, or NULL
 202  *
 203  * Allocates memory with no particular alignment requirement.  @c ptr
 204  * will be aligned to at least a multiple of sizeof(void*).
 205  */
 206 void * malloc ( size_t size ) {
 207         size_t total_size;
 208         struct autosized_block *block;
 209
 210         total_size = size + offsetof ( struct autosized_block, data );
 211         block = alloc_memblock ( total_size, 1 );
 212         if ( ! block )
 213                 return NULL;
 214         block->size = total_size;
 215         return &block->data;
 216 }
 217
 218 /**
 219  * Free memory
 220  *
 221  * @v size              Memory allocated by malloc(), or NULL
 222  *
 223  * Memory allocated with malloc_dma() cannot be freed with free(); it
 224  * must be freed with free_dma() instead.
 225  *
 226  * If @c ptr is NULL, no action is taken.
 227  */
 228 void free ( void *ptr ) {
 229         struct autosized_block *block;
 230
 231         if ( ptr ) {
 232                 block = container_of ( ptr, struct autosized_block, data );
 233                 free_memblock ( block, block->size );
 234         }
 235 }
 236
 237 /**
 238  * Add memory to allocation pool
 239  *
 240  * @v start             Start address
 241  * @v end               End address
 242  *
 243  * Adds a block of memory [start,end) to the allocation pool.  This is
 244  * a one-way operation; there is no way to reclaim this memory.
 245  *
 246  * @c start must be aligned to at least a multiple of sizeof(void*).
 247  */
 248 void mpopulate ( void *start, size_t len ) {
 249         /* Prevent free_memblock() from rounding up len beyond the end
 250          * of what we were actually given...
 251          */
 252         free_memblock ( start, ( len & ~( MIN_MEMBLOCK_SIZE - 1 ) ) );
 253 }
 254
 255 #if 0
 256 #include <vsprintf.h>
 257 /**
 258  * Dump free block list
 259  *
 260  */
 261 void mdumpfree ( void ) {
 262         struct memory_block *block;
 263
 264         printf ( "Free block list:\n" );
 265         list_for_each_entry ( block, &free_blocks, list ) {
 266                 printf ( "[%p,%p] (size %#zx)\n", block,
 267                          ( ( ( void * ) block ) + block->size ), block->size );
 268         }
 269 }
 270 #endif