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