qemu/roms/ipxe/src/arch/i386/interface/pcbios/memtop_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., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  *
  19  * You can also choose to distribute this program under the terms of
  20  * the Unmodified Binary Distribution Licence (as given in the file
  21  * COPYING.UBDL), provided that you have satisfied its requirements.
  22  */
  23
  24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  25
  26 /**
  27  * @file
  28  *
  29  * External memory allocation
  30  *
  31  */
  32
  33 #include <limits.h>
  34 #include <errno.h>
  35 #include <ipxe/uaccess.h>
  36 #include <ipxe/hidemem.h>
  37 #include <ipxe/io.h>
  38 #include <ipxe/memblock.h>
  39 #include <ipxe/umalloc.h>
  40
  41 /** Alignment of external allocated memory */
  42 #define EM_ALIGN ( 4 * 1024 )
  43
  44 /** Equivalent of NOWHERE for user pointers */
  45 #define UNOWHERE ( ~UNULL )
  46
  47 /** An external memory block */
  48 struct external_memory {
  49         /** Size of this memory block (excluding this header) */
  50         size_t size;
  51         /** Block is currently in use */
  52         int used;
  53 };
  54
  55 /** Top of heap */
  56 static userptr_t top = UNULL;
  57
  58 /** Bottom of heap (current lowest allocated block) */
  59 static userptr_t bottom = UNULL;
  60
  61 /** Remaining space on heap */
  62 static size_t heap_size;
  63
  64 /**
  65  * Initialise external heap
  66  *
  67  */
  68 static void init_eheap ( void ) {
  69         userptr_t base;
  70
  71         heap_size = largest_memblock ( &base );
  72         bottom = top = userptr_add ( base, heap_size );
  73         DBG ( "External heap grows downwards from %lx (size %zx)\n",
  74               user_to_phys ( top, 0 ), heap_size );
  75 }
  76
  77 /**
  78  * Collect free blocks
  79  *
  80  */
  81 static void ecollect_free ( void ) {
  82         struct external_memory extmem;
  83         size_t len;
  84
  85         /* Walk the free list and collect empty blocks */
  86         while ( bottom != top ) {
  87                 copy_from_user ( &extmem, bottom, -sizeof ( extmem ),
  88                                  sizeof ( extmem ) );
  89                 if ( extmem.used )
  90                         break;
  91                 DBG ( "EXTMEM freeing [%lx,%lx)\n", user_to_phys ( bottom, 0 ),
  92                       user_to_phys ( bottom, extmem.size ) );
  93                 len = ( extmem.size + sizeof ( extmem ) );
  94                 bottom = userptr_add ( bottom, len );
  95                 heap_size += len;
  96         }
  97 }
  98
  99 /**
 100  * Reallocate external memory
 101  *
 102  * @v old_ptr           Memory previously allocated by umalloc(), or UNULL
 103  * @v new_size          Requested size
 104  * @ret new_ptr         Allocated memory, or UNULL
 105  *
 106  * Calling realloc() with a new size of zero is a valid way to free a
 107  * memory block.
 108  */
 109 static userptr_t memtop_urealloc ( userptr_t ptr, size_t new_size ) {
 110         struct external_memory extmem;
 111         userptr_t new = ptr;
 112         size_t align;
 113
 114         /* (Re)initialise external memory allocator if necessary */
 115         if ( bottom == top )
 116                 init_eheap();
 117
 118         /* Get block properties into extmem */
 119         if ( ptr && ( ptr != UNOWHERE ) ) {
 120                 /* Determine old size */
 121                 copy_from_user ( &extmem, ptr, -sizeof ( extmem ),
 122                                  sizeof ( extmem ) );
 123         } else {
 124                 /* Create a zero-length block */
 125                 if ( heap_size < sizeof ( extmem ) ) {
 126                         DBG ( "EXTMEM out of space\n" );
 127                         return UNULL;
 128                 }
 129                 ptr = bottom = userptr_add ( bottom, -sizeof ( extmem ) );
 130                 heap_size -= sizeof ( extmem );
 131                 DBG ( "EXTMEM allocating [%lx,%lx)\n",
 132                       user_to_phys ( ptr, 0 ), user_to_phys ( ptr, 0 ) );
 133                 extmem.size = 0;
 134         }
 135         extmem.used = ( new_size > 0 );
 136
 137         /* Expand/shrink block if possible */
 138         if ( ptr == bottom ) {
 139                 /* Update block */
 140                 if ( new_size > ( heap_size - extmem.size ) ) {
 141                         DBG ( "EXTMEM out of space\n" );
 142                         return UNULL;
 143                 }
 144                 new = userptr_add ( ptr, - ( new_size - extmem.size ) );
 145                 align = ( user_to_phys ( new, 0 ) & ( EM_ALIGN - 1 ) );
 146                 new_size += align;
 147                 new = userptr_add ( new, -align );
 148                 DBG ( "EXTMEM expanding [%lx,%lx) to [%lx,%lx)\n",
 149                       user_to_phys ( ptr, 0 ),
 150                       user_to_phys ( ptr, extmem.size ),
 151                       user_to_phys ( new, 0 ),
 152                       user_to_phys ( new, new_size ));
 153                 memmove_user ( new, 0, ptr, 0, ( ( extmem.size < new_size ) ?
 154                                                  extmem.size : new_size ) );
 155                 bottom = new;
 156                 heap_size -= ( new_size - extmem.size );
 157                 extmem.size = new_size;
 158         } else {
 159                 /* Cannot expand; can only pretend to shrink */
 160                 if ( new_size > extmem.size ) {
 161                         /* Refuse to expand */
 162                         DBG ( "EXTMEM cannot expand [%lx,%lx)\n",
 163                               user_to_phys ( ptr, 0 ),
 164                               user_to_phys ( ptr, extmem.size ) );
 165                         return UNULL;
 166                 }
 167         }
 168
 169         /* Write back block properties */
 170         copy_to_user ( new, -sizeof ( extmem ), &extmem,
 171                        sizeof ( extmem ) );
 172
 173         /* Collect any free blocks and update hidden memory region */
 174         ecollect_free();
 175         hide_umalloc ( user_to_phys ( bottom, ( ( bottom == top ) ?
 176                                                 0 : -sizeof ( extmem ) ) ),
 177                        user_to_phys ( top, 0 ) );
 178
 179         return ( new_size ? new : UNOWHERE );
 180 }
 181
 182 PROVIDE_UMALLOC ( memtop, urealloc, memtop_urealloc );