iPXE
memtop_umalloc.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2007 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 /**
00027  * @file
00028  *
00029  * External memory allocation
00030  *
00031  */
00032 
00033 #include <limits.h>
00034 #include <errno.h>
00035 #include <ipxe/uaccess.h>
00036 #include <ipxe/hidemem.h>
00037 #include <ipxe/io.h>
00038 #include <ipxe/memblock.h>
00039 #include <ipxe/umalloc.h>
00040 
00041 /** Maximum usable address for external allocated memory */
00042 #define EM_MAX_ADDRESS 0xffffffffUL
00043 
00044 /** Alignment of external allocated memory */
00045 #define EM_ALIGN ( 4 * 1024 )
00046 
00047 /** Equivalent of NOWHERE for user pointers */
00048 #define UNOWHERE ( ~UNULL )
00049 
00050 /** An external memory block */
00051 struct external_memory {
00052         /** Size of this memory block (excluding this header) */
00053         size_t size;
00054         /** Block is currently in use */
00055         int used;
00056 };
00057 
00058 /** Top of heap */
00059 static userptr_t top = UNULL;
00060 
00061 /** Bottom of heap (current lowest allocated block) */
00062 static userptr_t bottom = UNULL;
00063 
00064 /** Remaining space on heap */
00065 static size_t heap_size;
00066 
00067 /**
00068  * Find largest usable memory region
00069  *
00070  * @ret start           Start of region
00071  * @ret len             Length of region
00072  */
00073 size_t largest_memblock ( userptr_t *start ) {
00074         struct memory_map memmap;
00075         struct memory_region *region;
00076         physaddr_t max = EM_MAX_ADDRESS;
00077         physaddr_t region_start;
00078         physaddr_t region_end;
00079         size_t region_len;
00080         unsigned int i;
00081         size_t len = 0;
00082 
00083         /* Avoid returning uninitialised data on error */
00084         *start = UNULL;
00085 
00086         /* Scan through all memory regions */
00087         get_memmap ( &memmap );
00088         for ( i = 0 ; i < memmap.count ; i++ ) {
00089                 region = &memmap.regions[i];
00090                 DBG ( "Considering [%llx,%llx)\n", region->start, region->end );
00091 
00092                 /* Truncate block to maximum physical address */
00093                 if ( region->start > max ) {
00094                         DBG ( "...starts after maximum address %lx\n", max );
00095                         continue;
00096                 }
00097                 region_start = region->start;
00098                 if ( region->end > max ) {
00099                         DBG ( "...end truncated to maximum address %lx\n", max);
00100                         region_end = 0; /* =max, given the wraparound */
00101                 } else {
00102                         region_end = region->end;
00103                 }
00104                 region_len = ( region_end - region_start );
00105 
00106                 /* Use largest block */
00107                 if ( region_len > len ) {
00108                         DBG ( "...new best block found\n" );
00109                         *start = phys_to_user ( region_start );
00110                         len = region_len;
00111                 }
00112         }
00113 
00114         return len;
00115 }
00116 
00117 /**
00118  * Initialise external heap
00119  *
00120  */
00121 static void init_eheap ( void ) {
00122         userptr_t base;
00123 
00124         heap_size = largest_memblock ( &base );
00125         bottom = top = userptr_add ( base, heap_size );
00126         DBG ( "External heap grows downwards from %lx (size %zx)\n",
00127               user_to_phys ( top, 0 ), heap_size );
00128 }
00129 
00130 /**
00131  * Collect free blocks
00132  *
00133  */
00134 static void ecollect_free ( void ) {
00135         struct external_memory extmem;
00136         size_t len;
00137 
00138         /* Walk the free list and collect empty blocks */
00139         while ( bottom != top ) {
00140                 copy_from_user ( &extmem, bottom, -sizeof ( extmem ),
00141                                  sizeof ( extmem ) );
00142                 if ( extmem.used )
00143                         break;
00144                 DBG ( "EXTMEM freeing [%lx,%lx)\n", user_to_phys ( bottom, 0 ),
00145                       user_to_phys ( bottom, extmem.size ) );
00146                 len = ( extmem.size + sizeof ( extmem ) );
00147                 bottom = userptr_add ( bottom, len );
00148                 heap_size += len;
00149         }
00150 }
00151 
00152 /**
00153  * Reallocate external memory
00154  *
00155  * @v old_ptr           Memory previously allocated by umalloc(), or UNULL
00156  * @v new_size          Requested size
00157  * @ret new_ptr         Allocated memory, or UNULL
00158  *
00159  * Calling realloc() with a new size of zero is a valid way to free a
00160  * memory block.
00161  */
00162 static userptr_t memtop_urealloc ( userptr_t ptr, size_t new_size ) {
00163         struct external_memory extmem;
00164         userptr_t new = ptr;
00165         size_t align;
00166 
00167         /* (Re)initialise external memory allocator if necessary */
00168         if ( bottom == top )
00169                 init_eheap();
00170 
00171         /* Get block properties into extmem */
00172         if ( ptr && ( ptr != UNOWHERE ) ) {
00173                 /* Determine old size */
00174                 copy_from_user ( &extmem, ptr, -sizeof ( extmem ),
00175                                  sizeof ( extmem ) );
00176         } else {
00177                 /* Create a zero-length block */
00178                 if ( heap_size < sizeof ( extmem ) ) {
00179                         DBG ( "EXTMEM out of space\n" );
00180                         return UNULL;
00181                 }
00182                 ptr = bottom = userptr_add ( bottom, -sizeof ( extmem ) );
00183                 heap_size -= sizeof ( extmem );
00184                 DBG ( "EXTMEM allocating [%lx,%lx)\n",
00185                       user_to_phys ( ptr, 0 ), user_to_phys ( ptr, 0 ) );
00186                 extmem.size = 0;
00187         }
00188         extmem.used = ( new_size > 0 );
00189 
00190         /* Expand/shrink block if possible */
00191         if ( ptr == bottom ) {
00192                 /* Update block */
00193                 if ( new_size > ( heap_size - extmem.size ) ) {
00194                         DBG ( "EXTMEM out of space\n" );
00195                         return UNULL;
00196                 }
00197                 new = userptr_add ( ptr, - ( new_size - extmem.size ) );
00198                 align = ( user_to_phys ( new, 0 ) & ( EM_ALIGN - 1 ) );
00199                 new_size += align;
00200                 new = userptr_add ( new, -align );
00201                 DBG ( "EXTMEM expanding [%lx,%lx) to [%lx,%lx)\n",
00202                       user_to_phys ( ptr, 0 ),
00203                       user_to_phys ( ptr, extmem.size ),
00204                       user_to_phys ( new, 0 ),
00205                       user_to_phys ( new, new_size ));
00206                 memmove_user ( new, 0, ptr, 0, ( ( extmem.size < new_size ) ?
00207                                                  extmem.size : new_size ) );
00208                 bottom = new;
00209                 heap_size -= ( new_size - extmem.size );
00210                 extmem.size = new_size;
00211         } else {
00212                 /* Cannot expand; can only pretend to shrink */
00213                 if ( new_size > extmem.size ) {
00214                         /* Refuse to expand */
00215                         DBG ( "EXTMEM cannot expand [%lx,%lx)\n",
00216                               user_to_phys ( ptr, 0 ),
00217                               user_to_phys ( ptr, extmem.size ) );
00218                         return UNULL;
00219                 }
00220         }
00221 
00222         /* Write back block properties */
00223         copy_to_user ( new, -sizeof ( extmem ), &extmem,
00224                        sizeof ( extmem ) );
00225 
00226         /* Collect any free blocks and update hidden memory region */
00227         ecollect_free();
00228         hide_umalloc ( user_to_phys ( bottom, ( ( bottom == top ) ?
00229                                                 0 : -sizeof ( extmem ) ) ),
00230                        user_to_phys ( top, 0 ) );
00231 
00232         return ( new_size ? new : UNOWHERE );
00233 }
00234 
00235 PROVIDE_UMALLOC ( memtop, urealloc, memtop_urealloc );