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