blob: 4edc7914162b1b73e4794156215b1aa3791ae8da [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 =
160 (struct heap_alloc_header *)((size_t)prev_f - prev_f->size + FOOTER_SIZE);
161
162 // Header of block after this one
163 struct heap_alloc_header *next_h =
164 (struct heap_alloc_header *)((size_t)mem - HEADER_SIZE + base->size);
165
166 size_t size = base->size;
167 size_t start = (size_t)base;
168
169 if (prev_h->magic == HEAP_MAGIC && !prev_h->allocated)
170 {
171 size += prev_h->size;
172 start = (size_t)prev_h;
173 }
174 if (next_h->magic == HEAP_MAGIC && !next_h->allocated)
175 {
176 size += next_h->size;
177 }
178
179 struct heap_alloc_header *h = (struct heap_alloc_header *)start;
180 h->allocated = false;
181 h->magic = HEAP_MAGIC;
182 h->size = size;
183
swissChilie4f01992021-02-25 15:38:12 -0800184 // Add entry into heap
185
swissChili22399352021-02-28 10:45:04 -0800186 struct heap_entry entry = {
187 .key = size,
188 .address = start,
swissChilie4f01992021-02-25 15:38:12 -0800189 };
swissChili22399352021-02-28 10:45:04 -0800190
swissChilie4f01992021-02-25 15:38:12 -0800191 heap_insert(&heap, entry);
192}