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