src/arch/i386/core/umalloc.c

   1 /*
   2  * Copyright (C) 2007 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 /**
  20  * @file
  21  *
  22  * External memory allocation
  23  *
  24  */
  25
  26 #include <limits.h>
  27 #include <errno.h>
  28 #include <gpxe/uaccess.h>
  29 #include <gpxe/hidemem.h>
  30 #include <gpxe/memmap.h>
  31 #include <gpxe/umalloc.h>
  32
  33 /** Alignment of external allocated memory */
  34 #define EM_ALIGN ( 4 * 1024 )
  35
  36 /** Equivalent of NOWHERE for user pointers */
  37 #define UNOWHERE ( ~UNULL )
  38
  39 /** Start of Etherboot text, as defined by the linker */
  40 extern char _text[];
  41
  42 /** An external memory block */
  43 struct external_memory {
  44         /** Size of this memory block (excluding this header) */
  45         size_t size;
  46         /** Block is currently in use */
  47         int used;
  48 };
  49
  50 /** Top of heap */
  51 static userptr_t top = UNULL;
  52
  53 /** Bottom of heap (current lowest allocated block) */
  54 static userptr_t bottom = UNULL;
  55
  56 /**
  57  * Initialise external heap
  58  *
  59  * @ret rc              Return status code
  60  */
  61 static int init_eheap ( void ) {
  62         struct memory_map memmap;
  63         unsigned long heap_size = 0;
  64         unsigned int i;
  65
  66         DBG ( "Allocating external heap\n" );
  67
  68         get_memmap ( &memmap );
  69         for ( i = 0 ; i < memmap.count ; i++ ) {
  70                 struct memory_region *region = &memmap.regions[i];
  71                 unsigned long r_start, r_end;
  72                 unsigned long r_size;
  73
  74                 DBG ( "Considering [%llx,%llx)\n", region->start, region->end);
  75
  76                 /* Truncate block to 4GB */
  77                 if ( region->start > UINT_MAX ) {
  78                         DBG ( "...starts after 4GB\n" );
  79                         continue;
  80                 }
  81                 r_start = region->start;
  82                 if ( region->end > UINT_MAX ) {
  83                         DBG ( "...end truncated to 4GB\n" );
  84                         r_end = 0; /* =4GB, given the wraparound */
  85                 } else {
  86                         r_end = region->end;
  87                 }
  88
  89                 /* Use largest block */
  90                 r_size = ( r_end - r_start );
  91                 if ( r_size > heap_size ) {
  92                         DBG ( "...new best block found\n" );
  93                         top = bottom = phys_to_user ( r_end );
  94                         heap_size = r_size;
  95                 }
  96         }
  97
  98         if ( ! top ) {
  99                 DBG ( "No external heap available\n" );
 100                 return -ENOMEM;
 101         }
 102
 103         DBG ( "External heap grows downwards from %lx\n",
 104               user_to_phys ( top, 0 ) );
 105         return 0;
 106 }
 107
 108 /**
 109  * Collect free blocks
 110  *
 111  */
 112 static void ecollect_free ( void ) {
 113         struct external_memory extmem;
 114
 115         /* Walk the free list and collect empty blocks */
 116         while ( bottom != top ) {
 117                 copy_from_user ( &extmem, bottom, -sizeof ( extmem ),
 118                                  sizeof ( extmem ) );
 119                 if ( extmem.used )
 120                         break;
 121                 DBG ( "EXTMEM freeing [%lx,%lx)\n", user_to_phys ( bottom, 0 ),
 122                       user_to_phys ( bottom, extmem.size ) );
 123                 bottom = userptr_add ( bottom,
 124                                        ( extmem.size + sizeof ( extmem ) ) );
 125         }
 126 }
 127
 128 /**
 129  * Reallocate external memory
 130  *
 131  * @v old_ptr           Memory previously allocated by umalloc(), or UNULL
 132  * @v new_size          Requested size
 133  * @ret new_ptr         Allocated memory, or UNULL
 134  *
 135  * Calling realloc() with a new size of zero is a valid way to free a
 136  * memory block.
 137  */
 138 userptr_t urealloc ( userptr_t ptr, size_t new_size ) {
 139         struct external_memory extmem;
 140         userptr_t new = ptr;
 141         size_t align;
 142         int rc;
 143
 144         /* Initialise external memory allocator if necessary */
 145         if ( ! top  ) {
 146                 if ( ( rc = init_eheap() ) != 0 )
 147                         return rc;
 148         }
 149
 150         /* Get block properties into extmem */
 151         if ( ptr && ( ptr != UNOWHERE ) ) {
 152                 /* Determine old size */
 153                 copy_from_user ( &extmem, ptr, -sizeof ( extmem ),
 154                                  sizeof ( extmem ) );
 155         } else {
 156                 /* Create a zero-length block */
 157                 ptr = bottom = userptr_add ( bottom, -sizeof ( extmem ) );
 158                 DBG ( "EXTMEM allocating [%lx,%lx)\n",
 159                       user_to_phys ( ptr, 0 ), user_to_phys ( ptr, 0 ) );
 160                 extmem.size = 0;
 161         }
 162         extmem.used = ( new_size > 0 );
 163
 164         /* Expand/shrink block if possible */
 165         if ( ptr == bottom ) {
 166                 /* Update block */
 167                 new = userptr_add ( ptr, - ( new_size - extmem.size ) );
 168                 align = ( user_to_phys ( new, 0 ) & ( EM_ALIGN - 1 ) );
 169                 new_size += align;
 170                 new = userptr_add ( new, -align );
 171                 DBG ( "EXTMEM expanding [%lx,%lx) to [%lx,%lx)\n",
 172                       user_to_phys ( ptr, 0 ),
 173                       user_to_phys ( ptr, extmem.size ),
 174                       user_to_phys ( new, 0 ),
 175                       user_to_phys ( new, new_size ));
 176                 memmove_user ( new, 0, ptr, 0, ( ( extmem.size < new_size ) ?
 177                                                  extmem.size : new_size ) );
 178                 extmem.size = new_size;
 179                 bottom = new;
 180         } else {
 181                 /* Cannot expand; can only pretend to shrink */
 182                 if ( new_size > extmem.size ) {
 183                         /* Refuse to expand */
 184                         DBG ( "EXTMEM cannot expand [%lx,%lx)\n",
 185                               user_to_phys ( ptr, 0 ),
 186                               user_to_phys ( ptr, extmem.size ) );
 187                         return UNULL;
 188                 }
 189         }
 190
 191         /* Write back block properties */
 192         copy_to_user ( new, -sizeof ( extmem ), &extmem,
 193                        sizeof ( extmem ) );
 194
 195         /* Collect any free blocks and update hidden memory region */
 196         ecollect_free();
 197         hide_umalloc ( user_to_phys ( bottom, -sizeof ( extmem ) ),
 198                        user_to_phys ( top, 0 ) );
 199
 200         return ( new_size ? new : UNOWHERE );
 201 }
 202
 203 /**
 204  * Allocate external memory
 205  *
 206  * @v size              Requested size
 207  * @ret ptr             Memory, or UNULL
 208  *
 209  * Memory is guaranteed to be aligned to a page boundary.
 210  */
 211 userptr_t umalloc ( size_t size ) {
 212         return urealloc ( UNULL, size );
 213 }
 214
 215 /**
 216  * Free external memory
 217  *
 218  * @v ptr               Memory allocated by umalloc(), or UNULL
 219  *
 220  * If @c ptr is UNULL, no action is taken.
 221  */
 222 void ufree ( userptr_t ptr ) {
 223         urealloc ( ptr, 0 );
 224 }