Add realloc, since the load buffer code requires it.
[people/xl0/gpxe.git] / src / core / heap.c
1 #include "etherboot.h"
2 #include "init.h"
3 #include "memsizes.h"
4 #include "heap.h"
5
6 struct heap_block {
7         size_t size;
8         unsigned int align;
9         char data[0];
10 };
11
12 /* Linker symbols */
13 extern char _text[];
14 extern char _end[];
15
16 static physaddr_t heap_start, heap_end, heap_ptr;
17
18 /*
19  * Find the largest contiguous area of memory that I can use for the
20  * heap.
21  *
22  */
23 static void init_heap ( void ) {
24         unsigned int i;
25         physaddr_t eb_start, eb_end;
26         physaddr_t size;
27
28         size = 0;
29         
30         /* Region occupied by Etherboot */
31         eb_start = virt_to_phys ( _text );
32         eb_end = virt_to_phys ( _end );
33
34         for ( i = 0 ; i < meminfo.map_count ; i++ ) {
35                 physaddr_t r_start, r_end, r_size;
36                 physaddr_t pre_eb, post_eb;
37
38                 /* Get start and end addresses of the region */
39                 if ( meminfo.map[i].type != E820_RAM )
40                         continue;
41                 if ( meminfo.map[i].addr > ULONG_MAX )
42                         continue;
43                 r_start = meminfo.map[i].addr;
44                 if ( r_start + meminfo.map[i].size > ULONG_MAX ) {
45                         r_end = ULONG_MAX;
46                 } else {
47                         r_end = r_start + meminfo.map[i].size;
48                 }
49                 
50                 /* Avoid overlap with Etherboot.  When Etherboot is
51                  * completely contained within the region, choose the
52                  * larger of the two remaining portions.
53                  */
54                 if ( ( eb_start < r_end ) && ( eb_end > r_start ) ) {
55                         pre_eb = ( eb_start > r_start ) ?
56                                 ( eb_start - r_start ) : 0;
57                         post_eb = ( r_end > eb_end ) ?
58                                 ( r_end - eb_end ) : 0;
59                         if ( pre_eb > post_eb ) {
60                                 r_end = eb_start;
61                         } else {
62                                 r_start = eb_end;
63                         }
64                 }
65
66                 /* Use the biggest region.  Where two regions are the
67                  * same size, use the later region.  (Provided that
68                  * the memory map is laid out in a sensible order,
69                  * this should give us the higher region.)
70                  */
71                 r_size = r_end - r_start;
72                 if ( r_size >= size ) {
73                         heap_start = r_start;
74                         heap_end = r_end;
75                         size = r_size;
76                 }
77         }
78
79         ASSERT ( size != 0 );
80         DBG ( "HEAP using region [%x,%x)\n", heap_start, heap_end );
81         heap_ptr = heap_end;
82 }
83
84 /*
85  * Allocate a block from the heap.
86  *
87  */
88 static inline physaddr_t block_alloc_addr ( physaddr_t heap_ptr,
89                                             size_t size, unsigned int align ) {
90         return ( ( ( heap_ptr - size ) & ~( align - 1 ) )
91                  - sizeof ( struct heap_block ) );
92 }
93
94 void * emalloc ( size_t size, unsigned int align ) {
95         struct heap_block *block;
96         physaddr_t addr;
97         
98         ASSERT ( ( align & ( align - 1 ) ) == 0 );
99
100         addr = block_alloc_addr ( heap_ptr, size, align );
101         if ( addr < heap_start ) {
102                 DBG ( "HEAP no space for %x bytes (alignment %d) in [%x,%x)\n",
103                       size, align, heap_start, heap_ptr );
104                 return NULL;
105         }
106
107         block = phys_to_virt ( addr );
108         block->size = ( heap_ptr - addr );
109         block->align = align;
110         DBG ( "HEAP allocated %x bytes (alignment %d) at %x [%x,%x)\n",
111               size, align, virt_to_phys ( block->data ), addr, heap_ptr );
112         heap_ptr = addr;
113         return block->data;
114 }
115
116 /*
117  * Allocate all remaining space on the heap
118  *
119  */
120 void * emalloc_all ( size_t *size ) {
121         *size = heap_ptr - heap_start - sizeof ( struct heap_block );
122         return emalloc ( *size, sizeof ( void * ) );
123 }
124
125 /*
126  * Free a heap block
127  *
128  */
129 static inline physaddr_t block_free_addr ( size_t size ) {
130         return heap_ptr + size;
131 }
132
133 void efree ( void *ptr ) {
134         struct heap_block *block;
135
136         ASSERT ( ptr == phys_to_virt ( heap_ptr + sizeof ( size_t ) ) );
137         
138         block = ( struct heap_block * )
139                 ( ptr - offsetof ( struct heap_block, data ) );
140         heap_ptr = block_free_addr ( block->size );
141
142         DBG ( "HEAP freed %x [%x,%x)\n", virt_to_phys ( ptr ),
143               virt_to_phys ( block ), heap_ptr );
144
145         ASSERT ( heap_ptr <= heap_end );
146 }
147
148 /*
149  * Free all allocated heap blocks
150  *
151  */
152 void efree_all ( void ) {
153         DBG ( "HEAP discarding allocated blocks in [%x,%x)\n",
154               heap_ptr, heap_end );
155
156         heap_ptr = heap_end;
157 }
158
159 /*
160  * Resize a heap block
161  *
162  */
163 void * erealloc ( void *ptr, size_t size ) {
164         struct heap_block *old_block;
165         size_t old_size;
166         unsigned int old_align;
167         physaddr_t new_addr;
168         size_t move_size;
169         
170         /* Get descriptor of the old block */
171         old_block = ( struct heap_block * )
172                 ( ptr - offsetof ( struct heap_block, data ) );
173         old_size = old_block->size;
174         old_align = old_block->align;
175
176         /* Check that allocation is going to succeed */
177         new_addr = block_alloc_addr ( block_free_addr ( old_size ),
178                                       size, old_align );
179         if ( new_addr < heap_start ) {
180                 DBG ( "HEAP no space for %x bytes (alignment %d) in [%x,%x)\n",
181                       size, align, heap_start, block_free_addr ( old_size ) );
182                 return NULL;
183         }
184
185         /* Free the old block */
186         efree ( ptr );
187
188         /* Move the data.  Do this *before* allocating the new block,
189          * because the new block's descriptor may overwrite the old
190          * block's data, if the new block is smaller than the old
191          * block.
192          */
193         move_size = size + sizeof ( struct heap_block );
194         if ( old_size < move_size )
195                 move_size = old_size;
196         memmove ( phys_to_virt ( new_addr ), old_block, move_size );
197
198         /* Allocate the new block.  This must succeed, because we
199          * already checked that there was sufficient space.
200          */
201         ptr = emalloc ( size, old_align );
202         ASSERT ( ptr != NULL );
203
204         return ptr;
205 }
206
207 INIT_FN ( INIT_HEAP, init_heap, efree_all, NULL );