2 pcboot - bootable PC demo/game kernel
3 Copyright (C) 2018-2019 John Tsiombikas <nuclear@member.fsf.org>
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY, without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>.
35 struct mem_desc *next;
39 static void check_cycles(struct mem_desc *mem);
40 static void print_pool(void);
43 #define MAGIC_USED 0xdeadf00d
44 #define MAGIC_FREE 0x1ee7d00d
46 #define DESC_PTR(b) ((void*)((struct mem_desc*)(b) + 1))
47 #define PTR_DESC(p) ((struct mem_desc*)(p) - 1)
50 static struct mem_desc *pool;
54 #define FIRST_POOL_POW2 5
55 /* 2**(x+5) size pools: 0->32, 1->64, 2->128 .. 15->1048576 */
56 #define POOL_SIZE(x) (1 << ((x) + FIRST_POOL_POW2))
57 #define MAX_POOL_SIZE (1 << ((NUM_POOLS - 1) + FIRST_POOL_POW2))
58 #define MAX_POOL_PAGES BYTES_TO_PAGES(MAX_POOL_SIZE)
59 static struct mem_desc *pools[NUM_POOLS];
61 static int add_to_pool(struct mem_desc *b);
63 static int pool_index(int sz)
71 return x - FIRST_POOL_POW2;
73 #endif /* !SINGLE_POOL */
77 #define MIN_BLOCK_SIZE (sizeof(struct mem_desc) * 2)
79 void *malloc(size_t sz)
82 size_t total_sz, rest_sz;
83 struct mem_desc *mem, *rest, *prev, dummy;
86 total_sz = (sz + sizeof(struct mem_desc) + 3) & 0xfffffffc;
92 /* give the whole block to the allocation if mem->size == total_sz or
93 * if it's larger, but not large enough to fit another mem_desc in there
94 * for the new block that we're going to split off + some reasonable
95 * amount of memory for the new block.
97 if(mem->size >= total_sz && mem->size < total_sz + MIN_BLOCK_SIZE) {
98 prev->next = mem->next;
102 /* if we have enough space, split the block and give the upper part
105 if(mem->size > total_sz) {
106 void *ptr = (char*)mem + mem->size - total_sz;
107 mem->size -= total_sz;
117 mem->size = total_sz;
118 mem->magic = MAGIC_USED;
120 return DESC_PTR(mem);
123 /* did not find a free block, grab a new one */
124 npages = BYTES_TO_PAGES(total_sz);
125 if((pg0 = alloc_ppages(npages, 0)) == -1) {
129 mem = PAGE_TO_PTR(pg0);
130 mem->size = total_sz;
132 mem->magic = MAGIC_USED;
134 /* add the rest of the block to pool */
135 rest_sz = npages * 4096 - total_sz;
137 rest = (struct mem_desc*)((char*)mem + total_sz);
138 rest->size = rest_sz;
140 rest->magic = MAGIC_USED;
141 free(DESC_PTR(rest));
144 return DESC_PTR(mem);
149 struct mem_desc *mem, *prev, *cur, dummy;
155 if(mem->magic != MAGIC_USED) {
156 if(mem->magic == MAGIC_FREE) {
157 panic("free(%p): double-free\n", p);
159 panic("free(%p): corrupted magic (%x)!\n", p, mem->magic);
162 mem->magic = MAGIC_FREE;
165 /* nothing in the pool, just add this one */
171 end = (char*)mem + mem->size;
179 /* block starts right at the end of mem: coalesce */
180 if((char*)cur == end) {
181 mem->size += cur->size;
182 mem->next = cur->next;
188 /* block starts *after* the end of mem: add in front */
189 if((char*)cur > end) {
198 /* our block starts at the end of the last block in the pool: coalesce */
199 if((char*)prev + prev->size == (char*)mem) {
201 prev->size += mem->size;
205 /* so our block starts after the end of the last block: append */
216 #else /* !SINGLE_POOL */
218 void *malloc(size_t sz)
221 size_t total_sz, halfsz;
222 struct mem_desc *mem, *other;
224 total_sz = sz + sizeof(struct mem_desc);
226 if(total_sz > MAX_POOL_SIZE) {
227 /*printf(" allocation too big, hitting sys_alloc directly\n");*/
228 if((pg0 = alloc_ppages(BYTES_TO_PAGES(total_sz), 0)) == -1) {
232 mem = PAGE_TO_PTR(pg0);
233 mem->magic = MAGIC_USED;
234 mem->size = total_sz;
236 return DESC_PTR(mem);
239 pidx = pool_index(total_sz);
240 while(pidx < NUM_POOLS) {
242 /* found a pool with a free block that fits */
244 pools[pidx] = mem->next;
247 /*printf(" using pool %d (size %ld)\n", pidx, (unsigned long)mem->size);*/
249 /* while the mem size is larger than twice the allocation, split it */
250 while(pidx-- > 0 && total_sz <= (halfsz = mem->size / 2)) {
251 /*printf(" splitting %ld block in half and ", (unsigned long)mem->size);*/
252 other = (struct mem_desc*)((char*)mem + halfsz);
253 mem->size = other->size = halfsz;
258 if(mem->magic != MAGIC_FREE) {
259 panic("Trying to allocate range surrounded by an aura of wrong MAGIC\n");
261 mem->magic = MAGIC_USED;
262 return DESC_PTR(mem);
268 /* did not find a free block, add a new one */
269 pidx = NUM_POOLS - 1;
270 if((pg0 = alloc_ppages(MAX_POOL_PAGES, 0)) == -1) {
274 mem = PAGE_TO_PTR(pg0);
275 mem->size = MAX_POOL_SIZE;
276 mem->next = pools[pidx];
277 mem->magic = MAGIC_FREE;
280 /* try again now that there is a free block */
288 struct mem_desc *mem;
293 if(mem->magic != MAGIC_USED) {
294 if(mem->magic == MAGIC_FREE) {
295 panic("free(%p): double-free\n", p);
297 panic("free(%p): corrupted magic (%x)!\n", p, mem->magic);
301 if(mem->size > MAX_POOL_SIZE) {
302 /*printf("foo_free(%p): %ld bytes. block too large for pools, returning to system\n",
303 (void*)p, (unsigned long)mem->size);*/
304 pg0 = ADDR_TO_PAGE(mem);
305 free_ppages(pg0, BYTES_TO_PAGES(mem->size));
309 /*printf("foo_free(%p): block of %ld bytes and ", (void*)p, (unsigned long)mem->size);*/
313 #endif /* !def SINGLE_POOL */
316 void *calloc(size_t num, size_t size)
318 void *ptr = malloc(num * size);
320 memset(ptr, 0, num * size);
325 void *realloc(void *ptr, size_t size)
327 struct mem_desc *mem;
335 if(mem->size >= size) {
336 return ptr; /* TODO: shrink */
339 if(!(newp = malloc(size))) {
342 memcpy(newp, ptr, mem->size);
348 static void check_cycles(struct mem_desc *mem)
350 static uint32_t dbg = 42;
351 uint32_t cur_dbg = dbg++;
354 if(mem->magic != MAGIC_FREE) {
355 panic("check_cycles: NON-FREE MAGIC!\n");
357 if(mem->dbg == cur_dbg) {
358 panic("CYCLE DETECTED\n");
365 static void print_pool(void)
367 struct mem_desc *mem = pool;
369 printf("DBG: malloc pool:\n");
371 printf(" %p (%ld) [%x]\n", mem, mem->size, mem->magic);
374 assert((uint32_t)mem != MAGIC_USED);
377 #endif /* MALLOC_DEBUG */
380 static int add_to_pool(struct mem_desc *mem)
383 struct mem_desc head;
384 struct mem_desc *iter, *pnode;
386 pidx = pool_index(mem->size);
388 /*printf("adding %ld block to pool %d\n", (unsigned long)mem->size, pidx);*/
391 head.next = pools[pidx];
395 if(mem->size == pnode->size) { /* only coalesce same-sized blocks */
396 size_t size = mem->size;
398 if((char*)mem == (char*)pnode - size) {
399 iter->next = pnode->next; /* unlink pnode */
400 pools[pidx] = head.next;
404 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
405 return add_to_pool(mem);
407 if((char*)mem == (char*)pnode + size) {
408 iter->next = pnode->next; /* unlink pnode */
409 pools[pidx] = head.next;
413 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
414 return add_to_pool(pnode);
420 /* otherwise just add it to the pool */
421 mem->magic = MAGIC_FREE;
422 mem->next = pools[pidx];
426 check_cycles(pools[pidx]);
430 #endif /* !def SINGLE_POOL */