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 <stdint.h>
  20 #include <string.h>
  21 #include <io.h>
  22 #include <gpxe/list.h>
  23 #include <gpxe/malloc.h>
  24
  25 /** @file
  26  *
  27  * Memory allocation
  28  *
  29  */
  30
  31 /** A free block of memory */
  32 struct free_block {
  33         /** List of free blocks */
  34         struct list_head list;
  35         /** Size of this block */
  36         size_t size;
  37 };
  38
  39 /** List of free memory blocks */
  40 static LIST_HEAD ( free_blocks );
  41
  42 /**
  43  * Round size up to a memory allocation block size
  44  *
  45  * @v requested         Requested size
  46  * @ret obtained        Obtained size
  47  *
  48  * The requested size is rounded up to the minimum allocation block
  49  * size (the size of a struct @c free_block) and then rounded up to
  50  * the nearest power of two.
  51  */
  52 static size_t block_size ( size_t requested ) {
  53         size_t obtained = 1;
  54
  55         while ( ( obtained < sizeof ( struct free_block ) ) ||
  56                 ( obtained < requested ) ) {
  57                 obtained <<= 1;
  58         }
  59         return obtained;
  60 }
  61
  62 /**
  63  * Allocate memory
  64  *
  65  * @v size              Requested size
  66  * @ret ptr             Allocated memory
  67  *
  68  * gmalloc() will always allocate memory in power-of-two sized blocks,
  69  * aligned to the corresponding power-of-two boundary.  For example, a
  70  * request for 1500 bytes will return a 2048-byte block aligned to a
  71  * 2048-byte boundary.
  72  *
  73  * The alignment applies to the physical address, not the virtual
  74  * address.  The pointer value returned by gmalloc() therefore has no
  75  * alignment guarantees, except as provided for by the
  76  * virtual-to-physical mapping.  (In a PXE environment, this mapping
  77  * is guaranteed to be a multiple of 16 bytes.)
  78  *
  79  * Unlike traditional malloc(), the caller must remember the size of
  80  * the allocated block and pass the size to gfree().  This is done in
  81  * order to allow efficient allocation of power-of-two sized and
  82  * aligned blocks.
  83  */
  84 void * gmalloc ( size_t size ) {
  85         struct free_block *block;
  86         struct free_block *buddy;
  87
  88         /* Round up block size to power of two */
  89         size = block_size ( size );
  90
  91         /* Find the best available block */
  92         list_for_each_entry ( block, &free_blocks, list ) {
  93                 if ( block->size == size ) {
  94                         list_del ( &block->list );
  95                         memset ( block, 0, size );
  96                         return block;
  97                 }
  98                 while ( block->size > size ) {
  99                         block->size >>= 1;
 100                         buddy = ( ( ( void * ) block ) + block->size );
 101                         buddy->size = block->size;
 102                         list_add ( &buddy->list, &block->list );
 103                 }
 104         }
 105
 106         /* Nothing available */
 107         return NULL;
 108 }
 109
 110 /**
 111  * Free memory
 112  *
 113  * @v ptr               Allocated memory
 114  * @v size              Originally requested size
 115  *
 116  * Frees memory originally allocated by gmalloc().
 117  *
 118  * Calling gfree() with a NULL @c ptr is explicitly allowed, and
 119  * defined to have no effect.  Code such as
 120  *
 121  * @code
 122  *
 123  * if ( ! my_ptr )
 124  *     gfree ( my_ptr, my_size )
 125  *
 126  * @endcode
 127  *
 128  * is perfectly valid, but should be avoided as unnecessary bloat.
 129  */
 130 void gfree ( void *ptr, size_t size ) {
 131         struct free_block *freed_block = ptr;
 132         struct free_block *block;
 133
 134         /* Cope with gfree(NULL,x) */
 135         if ( ! ptr )
 136                 return;
 137
 138         /* Round up block size to power of two */
 139         size = block_size ( size );
 140         freed_block->size = size;
 141
 142         /* Merge back into free list */
 143         list_for_each_entry ( block, &free_blocks, list ) {
 144                 if ( ( ( virt_to_phys ( block ) ^
 145                          virt_to_phys ( freed_block ) ) == size ) &&
 146                      ( block->size == size ) ) {
 147                         list_del ( &block->list );
 148                         size <<= 1;
 149                         if ( block < freed_block )
 150                                 freed_block = block;
 151                         freed_block->size = size;
 152                 } else if ( block->size > size ) {
 153                         break;
 154                 }
 155         }
 156         list_add_tail ( &freed_block->list, &block->list );
 157 }
 158
 159 /**
 160  * Add memory to allocation pool
 161  *
 162  * @v start             Start address
 163  * @v len               Length
 164  *
 165  * Adds a block of memory to the allocation pool.  This is a one-way
 166  * operation; there is no way to reclaim this memory.
 167  *
 168  * There are no alignment requirements on either start or len.
 169  */
 170 void gmpopulate ( void *start, size_t len ) {
 171         size_t frag_len;
 172
 173         /* Split region into power-of-two sized and aligned blocks,
 174          * and feed them to gfree().
 175          */
 176         while ( len ) {
 177                 frag_len = 1;
 178                 /* Find maximum allowed alignment for this address */
 179                 while ( ( virt_to_phys ( start ) & frag_len ) == 0 ) {
 180                         frag_len <<= 1;
 181                 }
 182                 /* Find maximum block size that fits in remaining space */
 183                 while ( frag_len > len ) {
 184                         frag_len >>= 1;
 185                 }
 186                 /* Skip blocks that are too small */
 187                 if ( frag_len >= sizeof ( struct free_block ) )
 188                         gfree ( start, frag_len );
 189                 start += frag_len;
 190                 len -= frag_len;
 191         }
 192 }
 193
 194 #if 0
 195 #include <vsprintf.h>
 196 /**
 197  * Dump free block list
 198  *
 199  */
 200 void gdumpfree ( void ) {
 201         struct free_block *block;
 202
 203         printf ( "Free block list:\n" );
 204         list_for_each_entry ( block, &free_blocks, list ) {
 205                 printf ( "[%p,%p] (size %zx)\n", block,
 206                          ( ( ( void * ) block ) + block->size ), block->size );
 207         }
 208 }
 209 #endif