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 /** Maximum usable address for external allocated memory */
42 #define EM_MAX_ADDRESS 0xffffffffUL
43
44 /** Alignment of external allocated memory */
45 #define EM_ALIGN ( 4 * 1024 )
46
47 /** Equivalent of NOWHERE for user pointers */
48 #define UNOWHERE ( ~UNULL )
49
50 /** An external memory block */
51 struct external_memory {
52 /** Size of this memory block (excluding this header) */
53 size_t size;
54 /** Block is currently in use */
55 int used;
56 };
57
58 /** Top of heap */
59 static userptr_t top = UNULL;
60
61 /** Bottom of heap (current lowest allocated block) */
62 static userptr_t bottom = UNULL;
63
64 /** Remaining space on heap */
65 static size_t heap_size;
66
67 /**
68 * Find largest usable memory region
69 *
70 * @ret start Start of region
71 * @ret len Length of region
72 */
largest_memblock(userptr_t * start)73 size_t largest_memblock ( userptr_t *start ) {
74 struct memory_map memmap;
75 struct memory_region *region;
76 physaddr_t max = EM_MAX_ADDRESS;
77 physaddr_t region_start;
78 physaddr_t region_end;
79 size_t region_len;
80 unsigned int i;
81 size_t len = 0;
82
83 /* Avoid returning uninitialised data on error */
84 *start = UNULL;
85
86 /* Scan through all memory regions */
87 get_memmap ( &memmap );
88 for ( i = 0 ; i < memmap.count ; i++ ) {
89 region = &memmap.regions[i];
90 DBG ( "Considering [%llx,%llx)\n", region->start, region->end );
91
92 /* Truncate block to maximum physical address */
93 if ( region->start > max ) {
94 DBG ( "...starts after maximum address %lx\n", max );
95 continue;
96 }
97 region_start = region->start;
98 if ( region->end > max ) {
99 DBG ( "...end truncated to maximum address %lx\n", max);
100 region_end = 0; /* =max, given the wraparound */
101 } else {
102 region_end = region->end;
103 }
104 region_len = ( region_end - region_start );
105
106 /* Use largest block */
107 if ( region_len > len ) {
108 DBG ( "...new best block found\n" );
109 *start = phys_to_user ( region_start );
110 len = region_len;
111 }
112 }
113
114 return len;
115 }
116
117 /**
118 * Initialise external heap
119 *
120 */
init_eheap(void)121 static void init_eheap ( void ) {
122 userptr_t base;
123
124 heap_size = largest_memblock ( &base );
125 bottom = top = userptr_add ( base, heap_size );
126 DBG ( "External heap grows downwards from %lx (size %zx)\n",
127 user_to_phys ( top, 0 ), heap_size );
128 }
129
130 /**
131 * Collect free blocks
132 *
133 */
ecollect_free(void)134 static void ecollect_free ( void ) {
135 struct external_memory extmem;
136 size_t len;
137
138 /* Walk the free list and collect empty blocks */
139 while ( bottom != top ) {
140 copy_from_user ( &extmem, bottom, -sizeof ( extmem ),
141 sizeof ( extmem ) );
142 if ( extmem.used )
143 break;
144 DBG ( "EXTMEM freeing [%lx,%lx)\n", user_to_phys ( bottom, 0 ),
145 user_to_phys ( bottom, extmem.size ) );
146 len = ( extmem.size + sizeof ( extmem ) );
147 bottom = userptr_add ( bottom, len );
148 heap_size += len;
149 }
150 }
151
152 /**
153 * Reallocate external memory
154 *
155 * @v old_ptr Memory previously allocated by umalloc(), or UNULL
156 * @v new_size Requested size
157 * @ret new_ptr Allocated memory, or UNULL
158 *
159 * Calling realloc() with a new size of zero is a valid way to free a
160 * memory block.
161 */
memtop_urealloc(userptr_t ptr,size_t new_size)162 static userptr_t memtop_urealloc ( userptr_t ptr, size_t new_size ) {
163 struct external_memory extmem;
164 userptr_t new = ptr;
165 size_t align;
166
167 /* (Re)initialise external memory allocator if necessary */
168 if ( bottom == top )
169 init_eheap();
170
171 /* Get block properties into extmem */
172 if ( ptr && ( ptr != UNOWHERE ) ) {
173 /* Determine old size */
174 copy_from_user ( &extmem, ptr, -sizeof ( extmem ),
175 sizeof ( extmem ) );
176 } else {
177 /* Create a zero-length block */
178 if ( heap_size < sizeof ( extmem ) ) {
179 DBG ( "EXTMEM out of space\n" );
180 return UNULL;
181 }
182 ptr = bottom = userptr_add ( bottom, -sizeof ( extmem ) );
183 heap_size -= sizeof ( extmem );
184 DBG ( "EXTMEM allocating [%lx,%lx)\n",
185 user_to_phys ( ptr, 0 ), user_to_phys ( ptr, 0 ) );
186 extmem.size = 0;
187 }
188 extmem.used = ( new_size > 0 );
189
190 /* Expand/shrink block if possible */
191 if ( ptr == bottom ) {
192 /* Update block */
193 if ( new_size > ( heap_size - extmem.size ) ) {
194 DBG ( "EXTMEM out of space\n" );
195 return UNULL;
196 }
197 new = userptr_add ( ptr, - ( new_size - extmem.size ) );
198 align = ( user_to_phys ( new, 0 ) & ( EM_ALIGN - 1 ) );
199 new_size += align;
200 new = userptr_add ( new, -align );
201 DBG ( "EXTMEM expanding [%lx,%lx) to [%lx,%lx)\n",
202 user_to_phys ( ptr, 0 ),
203 user_to_phys ( ptr, extmem.size ),
204 user_to_phys ( new, 0 ),
205 user_to_phys ( new, new_size ));
206 memmove_user ( new, 0, ptr, 0, ( ( extmem.size < new_size ) ?
207 extmem.size : new_size ) );
208 bottom = new;
209 heap_size -= ( new_size - extmem.size );
210 extmem.size = new_size;
211 } else {
212 /* Cannot expand; can only pretend to shrink */
213 if ( new_size > extmem.size ) {
214 /* Refuse to expand */
215 DBG ( "EXTMEM cannot expand [%lx,%lx)\n",
216 user_to_phys ( ptr, 0 ),
217 user_to_phys ( ptr, extmem.size ) );
218 return UNULL;
219 }
220 }
221
222 /* Write back block properties */
223 copy_to_user ( new, -sizeof ( extmem ), &extmem,
224 sizeof ( extmem ) );
225
226 /* Collect any free blocks and update hidden memory region */
227 ecollect_free();
228 hide_umalloc ( user_to_phys ( bottom, ( ( bottom == top ) ?
229 0 : -sizeof ( extmem ) ) ),
230 user_to_phys ( top, 0 ) );
231
232 return ( new_size ? new : UNOWHERE );
233 }
234
235 PROVIDE_UMALLOC ( memtop, urealloc, memtop_urealloc );
236