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