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 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 */
init_eheap(void)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 */
ecollect_free(void)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 */
memtop_urealloc(userptr_t ptr,size_t new_size)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