blob: e3c85b112032375baad1c7deb075f9f1c83029e2 [file] [log] [blame]
swissChilie4f01992021-02-25 15:38:12 -08001#include "alloc.h"
swissChili22399352021-02-28 10:45:04 -08002#include "io.h"
swissChilie4f01992021-02-25 15:38:12 -08003#include "kheap.h"
4#include "kint.h"
5#include "log.h"
6#include "paging.h"
swissChilie4f01992021-02-25 15:38:12 -08007
8extern uint end;
9static size_t palloc_base = (size_t)&end;
swissChilie20b79b2021-03-17 21:20:13 -070010static size_t malloc_base = (size_t)&end + 0x8000;
swissChilie4f01992021-02-25 15:38:12 -080011
12#define HEADER_SIZE sizeof(struct heap_alloc_header)
13#define FOOTER_SIZE sizeof(struct heap_alloc_footer)
14
15static struct min_heap heap = {0};
16
17void *_kmalloc(size_t size, bool align, void **phys)
18{
19 if (align && (palloc_base & 0xfff)) // if not yet aligned
20 {
21 palloc_base &= ~0xfff;
22 palloc_base += 0x1000;
23 }
24
25 if (phys)
26 {
swissChilie20b79b2021-03-17 21:20:13 -070027 *phys = (void *)VIRT_TO_PHYS((void *)palloc_base);
swissChilie4f01992021-02-25 15:38:12 -080028 }
29
30 size_t addr = palloc_base;
31 palloc_base += size;
swissChilie20b79b2021-03-17 21:20:13 -070032
33 if (palloc_base >= malloc_base)
34 {
35 kpanic("fatal error: placeholder kmalloc has overrun malloc() memory,"
36 " cannot recover.");
37 }
38
swissChilie4f01992021-02-25 15:38:12 -080039 return (void *)addr;
40}
41
42void *kmalloc(size_t size)
43{
44 return _kmalloc(size, false, NULL);
45}
46
47void *kmalloc_a(size_t size)
48{
49 return _kmalloc(size, true, NULL);
50}
51
52void *kmalloc_ap(size_t size, void **p)
53{
54 return _kmalloc(size, true, p);
55}
56
57// Proper allocators
58
59void init_allocator()
60{
swissChilie4f01992021-02-25 15:38:12 -080061 heap.size = 1;
swissChilif238c222021-02-25 15:47:50 -080062 int size = 0xC0400000 - malloc_base;
swissChilie4f01992021-02-25 15:38:12 -080063 heap.elements[0] = (struct heap_entry){
swissChilif238c222021-02-25 15:47:50 -080064 .key = size,
swissChilie4f01992021-02-25 15:38:12 -080065 .address = malloc_base,
66 };
swissChilif238c222021-02-25 15:47:50 -080067 memset((void *)malloc_base, 0, size);
68
69 struct heap_alloc_header *h = (struct heap_alloc_header *)malloc_base;
70 h->magic = HEAP_MAGIC;
71 h->size = size;
72 h->allocated = false;
swissChilie4f01992021-02-25 15:38:12 -080073}
74
75void *malloc(size_t size)
76{
77 bool ok;
78 size_t full_size = size + HEADER_SIZE + FOOTER_SIZE;
79 int i;
80
81 struct heap_entry e = heap_lookup_min(&heap, full_size, &ok, false, &i);
82
83 if (ok)
84 {
85 // Found smallest hole
86 struct heap_alloc_header *h = (struct heap_alloc_header *)e.address;
87
88 kassert(!h->allocated,
89 "Gap already allocated (this should never happen)");
90
91 size_t old_size = h->size;
92
93 if (full_size == old_size)
94 {
95 // Completely used, no need to change anything!
96 heap_delete(&heap, i);
97 }
98 else
99 {
100 // If there isn't very much space left
101 size_t new_size = old_size - full_size;
102 if (new_size <= HEADER_SIZE + FOOTER_SIZE + 8)
103 {
104 full_size = old_size;
105 heap_delete(&heap, i);
106 }
107 else
108 {
109 struct heap_alloc_footer *old_f =
110 (struct heap_alloc_footer *)(e.address + old_size -
111 FOOTER_SIZE);
112
113 // Else create a new header
114 size_t new_header_addr = e.address + full_size;
115 struct heap_alloc_header *h =
116 (struct heap_alloc_header *)new_header_addr;
117
swissChilie4f01992021-02-25 15:38:12 -0800118 h->size = new_size;
119 old_f->size = new_size;
120
121 heap_decrease(&heap, i,
122 (struct heap_entry){
123 .key = new_size,
124 .address = new_header_addr,
125 });
126 }
127
128 struct heap_alloc_footer *f =
129 (struct heap_alloc_footer *)(e.address + full_size -
130 FOOTER_SIZE);
131
swissChilif238c222021-02-25 15:47:50 -0800132 h->allocated = true;
133 h->magic = HEAP_MAGIC;
swissChilie4f01992021-02-25 15:38:12 -0800134 h->size = full_size;
135 f->size = h->size;
136 }
137
138 return (void *)(e.address + HEADER_SIZE);
139 }
140 else
141 {
142 // We need more memory :L
143 kpanic("Whoops, malloc ran out of memory");
144 }
145}
146
147void free(void *mem)
148{
swissChilie4f01992021-02-25 15:38:12 -0800149 if (!mem)
150 return; // freeing NULL ptr
151
152 struct heap_alloc_header *base =
153 (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE);
154
155 if (base->magic != HEAP_MAGIC)
156 {
157 kpanic("Freeing memory not allocated with malloc()");
158 }
159
swissChili22399352021-02-28 10:45:04 -0800160 // Check free block before this one
161
162 struct heap_alloc_footer *prev_f =
163 (struct heap_alloc_footer *)((size_t)mem - HEADER_SIZE - FOOTER_SIZE);
164
165 // Header of block before this one
166 struct heap_alloc_header *prev_h =
swissChili6575dd72021-02-28 11:31:28 -0800167 (struct heap_alloc_header *)((size_t)prev_f - prev_f->size +
168 FOOTER_SIZE);
swissChili22399352021-02-28 10:45:04 -0800169
170 // Header of block after this one
171 struct heap_alloc_header *next_h =
172 (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE + base->size);
173
174 size_t size = base->size;
175 size_t start = (size_t)base;
176
177 if (prev_h->magic == HEAP_MAGIC && !prev_h->allocated)
178 {
179 size += prev_h->size;
180 start = (size_t)prev_h;
181 }
182 if (next_h->magic == HEAP_MAGIC && !next_h->allocated)
183 {
184 size += next_h->size;
185 }
186
187 struct heap_alloc_header *h = (struct heap_alloc_header *)start;
188 h->allocated = false;
189 h->magic = HEAP_MAGIC;
190 h->size = size;
191
swissChilie4f01992021-02-25 15:38:12 -0800192 // Add entry into heap
193
swissChili22399352021-02-28 10:45:04 -0800194 struct heap_entry entry = {
195 .key = size,
196 .address = start,
swissChilie4f01992021-02-25 15:38:12 -0800197 };
swissChili22399352021-02-28 10:45:04 -0800198
swissChilie4f01992021-02-25 15:38:12 -0800199 heap_insert(&heap, entry);
200}
swissChili6575dd72021-02-28 11:31:28 -0800201
202void *realloc(void *mem, size_t size)
203{
204 if (!mem)
205 return NULL; // freeing NULL ptr
206
207 struct heap_alloc_header *base =
208 (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE);
209 struct heap_alloc_header *next =
210 (struct heap_alloc_header *)((size_t)base + base->size);
211
212 if (!next->allocated &&
213 next->size + base->size - HEADER_SIZE - FOOTER_SIZE >= size)
214 {
215 // Okay, we can just expand this block
216 // Actually, need to check if there is enough space remaining for an
217 // additional block, otherwise, just add that memory to this block (
218 // same as is done in malloc )
219
220 struct heap_alloc_footer *f;
221
222 size_t remaining =
223 base->size + next->size - size - HEADER_SIZE - FOOTER_SIZE;
224
225 struct heap_entry old_entry = {
226 .key = next->size,
227 .address = (size_t)next,
228 };
229
230 if (remaining <= HEADER_SIZE + FOOTER_SIZE + 8)
231 {
232 // Just join this into the same memory chunk
233 f = (struct heap_alloc_footer *)(next + next->size - FOOTER_SIZE);
234
235 heap_delete_entry(&heap, old_entry);
236 }
237 else
238 {
239 f = mem + size;
240 struct heap_alloc_header *new_h =
241 (struct heap_alloc_header *)(f + FOOTER_SIZE);
242
243 struct heap_alloc_footer *new_f =
244 (struct heap_alloc_footer *)(new_h + remaining - FOOTER_SIZE);
245
246 new_h->allocated = false;
247 new_h->size = new_f->size = remaining;
248 new_h->magic = HEAP_MAGIC;
249
250 struct heap_entry entry = {
251 .key = remaining,
252 .address = (size_t)new_h,
253 };
254
255 heap_decrease_entry(&heap, old_entry, entry);
256 }
257
258 size_t full_size = (size_t)f - (size_t)base + FOOTER_SIZE;
259
260 f->size = full_size;
261 base->size = full_size;
262 base->magic = HEAP_MAGIC;
263 base->allocated = true;
swissChili8efa4922021-03-02 16:34:49 -0800264
265 return mem;
swissChili6575dd72021-02-28 11:31:28 -0800266 }
267 else
268 {
269 void *new = malloc(size);
270 if (!new)
271 return new;
272
273 memcpy(new, mem, base->size - HEADER_SIZE - FOOTER_SIZE);
274 free(mem);
275
276 return new;
277 }
278}
swissChili6c0519e2021-03-07 19:40:23 -0800279
280void test_allocator()
281{
282 int *one = malloc(sizeof(int));
283 int *two = malloc(sizeof(int));
284
285 *one = 1;
286 *two = 2;
287
288 int *array = malloc(sizeof(int[12]));
289
290 for (int i = 0; i < 12; i++)
291 array[i] = i;
292
293 kprintf("Allocated one, two, array[3] = %d, %d, %d\n", *one, *two,
294 array[3]);
295 kprintf("[%x, %x, %x]\n", one, two, array);
296
297 kprintf("Freeing two\n");
298 free(two);
299 int *four = malloc(sizeof(int));
300 *four = 4;
301 kprintf("Allocated four = %d (%x)\n", *four, four);
302}