blob: 026892862e4410bf563c7277f735836ac0c3879e [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;
10static size_t malloc_base = (size_t)&end + 0x2000;
11
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 {
27 *phys = (void *)palloc_base;
28 }
29
30 size_t addr = palloc_base;
31 palloc_base += size;
32 return (void *)addr;
33}
34
35void *kmalloc(size_t size)
36{
37 return _kmalloc(size, false, NULL);
38}
39
40void *kmalloc_a(size_t size)
41{
42 return _kmalloc(size, true, NULL);
43}
44
45void *kmalloc_ap(size_t size, void **p)
46{
47 return _kmalloc(size, true, p);
48}
49
50// Proper allocators
51
52void init_allocator()
53{
swissChilie4f01992021-02-25 15:38:12 -080054 heap.size = 1;
swissChilif238c222021-02-25 15:47:50 -080055 int size = 0xC0400000 - malloc_base;
swissChilie4f01992021-02-25 15:38:12 -080056 heap.elements[0] = (struct heap_entry){
swissChilif238c222021-02-25 15:47:50 -080057 .key = size,
swissChilie4f01992021-02-25 15:38:12 -080058 .address = malloc_base,
59 };
swissChilif238c222021-02-25 15:47:50 -080060 memset((void *)malloc_base, 0, size);
61
62 struct heap_alloc_header *h = (struct heap_alloc_header *)malloc_base;
63 h->magic = HEAP_MAGIC;
64 h->size = size;
65 h->allocated = false;
swissChilie4f01992021-02-25 15:38:12 -080066}
67
68void *malloc(size_t size)
69{
70 bool ok;
71 size_t full_size = size + HEADER_SIZE + FOOTER_SIZE;
72 int i;
73
74 struct heap_entry e = heap_lookup_min(&heap, full_size, &ok, false, &i);
75
76 if (ok)
77 {
78 // Found smallest hole
79 struct heap_alloc_header *h = (struct heap_alloc_header *)e.address;
80
81 kassert(!h->allocated,
82 "Gap already allocated (this should never happen)");
83
84 size_t old_size = h->size;
85
86 if (full_size == old_size)
87 {
88 // Completely used, no need to change anything!
89 heap_delete(&heap, i);
90 }
91 else
92 {
93 // If there isn't very much space left
94 size_t new_size = old_size - full_size;
95 if (new_size <= HEADER_SIZE + FOOTER_SIZE + 8)
96 {
97 full_size = old_size;
98 heap_delete(&heap, i);
99 }
100 else
101 {
102 struct heap_alloc_footer *old_f =
103 (struct heap_alloc_footer *)(e.address + old_size -
104 FOOTER_SIZE);
105
106 // Else create a new header
107 size_t new_header_addr = e.address + full_size;
108 struct heap_alloc_header *h =
109 (struct heap_alloc_header *)new_header_addr;
110
swissChilie4f01992021-02-25 15:38:12 -0800111 h->size = new_size;
112 old_f->size = new_size;
113
114 heap_decrease(&heap, i,
115 (struct heap_entry){
116 .key = new_size,
117 .address = new_header_addr,
118 });
119 }
120
121 struct heap_alloc_footer *f =
122 (struct heap_alloc_footer *)(e.address + full_size -
123 FOOTER_SIZE);
124
swissChilif238c222021-02-25 15:47:50 -0800125 h->allocated = true;
126 h->magic = HEAP_MAGIC;
swissChilie4f01992021-02-25 15:38:12 -0800127 h->size = full_size;
128 f->size = h->size;
129 }
130
131 return (void *)(e.address + HEADER_SIZE);
132 }
133 else
134 {
135 // We need more memory :L
136 kpanic("Whoops, malloc ran out of memory");
137 }
138}
139
140void free(void *mem)
141{
swissChilie4f01992021-02-25 15:38:12 -0800142 if (!mem)
143 return; // freeing NULL ptr
144
145 struct heap_alloc_header *base =
146 (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE);
147
148 if (base->magic != HEAP_MAGIC)
149 {
150 kpanic("Freeing memory not allocated with malloc()");
151 }
152
swissChili22399352021-02-28 10:45:04 -0800153 // Check free block before this one
154
155 struct heap_alloc_footer *prev_f =
156 (struct heap_alloc_footer *)((size_t)mem - HEADER_SIZE - FOOTER_SIZE);
157
158 // Header of block before this one
159 struct heap_alloc_header *prev_h =
swissChili6575dd72021-02-28 11:31:28 -0800160 (struct heap_alloc_header *)((size_t)prev_f - prev_f->size +
161 FOOTER_SIZE);
swissChili22399352021-02-28 10:45:04 -0800162
163 // Header of block after this one
164 struct heap_alloc_header *next_h =
165 (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE + base->size);
166
167 size_t size = base->size;
168 size_t start = (size_t)base;
169
170 if (prev_h->magic == HEAP_MAGIC && !prev_h->allocated)
171 {
172 size += prev_h->size;
173 start = (size_t)prev_h;
174 }
175 if (next_h->magic == HEAP_MAGIC && !next_h->allocated)
176 {
177 size += next_h->size;
178 }
179
180 struct heap_alloc_header *h = (struct heap_alloc_header *)start;
181 h->allocated = false;
182 h->magic = HEAP_MAGIC;
183 h->size = size;
184
swissChilie4f01992021-02-25 15:38:12 -0800185 // Add entry into heap
186
swissChili22399352021-02-28 10:45:04 -0800187 struct heap_entry entry = {
188 .key = size,
189 .address = start,
swissChilie4f01992021-02-25 15:38:12 -0800190 };
swissChili22399352021-02-28 10:45:04 -0800191
swissChilie4f01992021-02-25 15:38:12 -0800192 heap_insert(&heap, entry);
193}
swissChili6575dd72021-02-28 11:31:28 -0800194
195void *realloc(void *mem, size_t size)
196{
197 if (!mem)
198 return NULL; // freeing NULL ptr
199
200 struct heap_alloc_header *base =
201 (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE);
202 struct heap_alloc_header *next =
203 (struct heap_alloc_header *)((size_t)base + base->size);
204
205 if (!next->allocated &&
206 next->size + base->size - HEADER_SIZE - FOOTER_SIZE >= size)
207 {
208 // Okay, we can just expand this block
209 // Actually, need to check if there is enough space remaining for an
210 // additional block, otherwise, just add that memory to this block (
211 // same as is done in malloc )
212
213 struct heap_alloc_footer *f;
214
215 size_t remaining =
216 base->size + next->size - size - HEADER_SIZE - FOOTER_SIZE;
217
218 struct heap_entry old_entry = {
219 .key = next->size,
220 .address = (size_t)next,
221 };
222
223 if (remaining <= HEADER_SIZE + FOOTER_SIZE + 8)
224 {
225 // Just join this into the same memory chunk
226 f = (struct heap_alloc_footer *)(next + next->size - FOOTER_SIZE);
227
228 heap_delete_entry(&heap, old_entry);
229 }
230 else
231 {
232 f = mem + size;
233 struct heap_alloc_header *new_h =
234 (struct heap_alloc_header *)(f + FOOTER_SIZE);
235
236 struct heap_alloc_footer *new_f =
237 (struct heap_alloc_footer *)(new_h + remaining - FOOTER_SIZE);
238
239 new_h->allocated = false;
240 new_h->size = new_f->size = remaining;
241 new_h->magic = HEAP_MAGIC;
242
243 struct heap_entry entry = {
244 .key = remaining,
245 .address = (size_t)new_h,
246 };
247
248 heap_decrease_entry(&heap, old_entry, entry);
249 }
250
251 size_t full_size = (size_t)f - (size_t)base + FOOTER_SIZE;
252
253 f->size = full_size;
254 base->size = full_size;
255 base->magic = HEAP_MAGIC;
256 base->allocated = true;
swissChili8efa4922021-03-02 16:34:49 -0800257
258 return mem;
swissChili6575dd72021-02-28 11:31:28 -0800259 }
260 else
261 {
262 void *new = malloc(size);
263 if (!new)
264 return new;
265
266 memcpy(new, mem, base->size - HEADER_SIZE - FOOTER_SIZE);
267 free(mem);
268
269 return new;
270 }
271}
swissChili6c0519e2021-03-07 19:40:23 -0800272
273void test_allocator()
274{
275 int *one = malloc(sizeof(int));
276 int *two = malloc(sizeof(int));
277
278 *one = 1;
279 *two = 2;
280
281 int *array = malloc(sizeof(int[12]));
282
283 for (int i = 0; i < 12; i++)
284 array[i] = i;
285
286 kprintf("Allocated one, two, array[3] = %d, %d, %d\n", *one, *two,
287 array[3]);
288 kprintf("[%x, %x, %x]\n", one, two, array);
289
290 kprintf("Freeing two\n");
291 free(two);
292 int *four = malloc(sizeof(int));
293 *four = 4;
294 kprintf("Allocated four = %d (%x)\n", *four, four);
295}