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/>.
34 struct mem_desc *next;
38 static void check_cycles(struct mem_desc *mem);
39 static void print_pool(void);
42 #define MAGIC_USED 0xdeadf00d
43 #define MAGIC_FREE 0x1ee7d00d
45 #define DESC_PTR(b) ((void*)((struct mem_desc*)(b) + 1))
46 #define PTR_DESC(p) ((struct mem_desc*)(p) - 1)
49 static struct mem_desc *pool;
53 #define FIRST_POOL_POW2 5
54 /* 2**(x+5) size pools: 0->32, 1->64, 2->128 .. 15->1048576 */
55 #define POOL_SIZE(x) (1 << ((x) + FIRST_POOL_POW2))
56 #define MAX_POOL_SIZE (1 << ((NUM_POOLS - 1) + FIRST_POOL_POW2))
57 #define MAX_POOL_PAGES BYTES_TO_PAGES(MAX_POOL_SIZE)
58 static struct mem_desc *pools[NUM_POOLS];
60 static int add_to_pool(struct mem_desc *b);
62 static int pool_index(int sz)
70 return x - FIRST_POOL_POW2;
72 #endif /* !SINGLE_POOL */
76 #define MIN_BLOCK_SIZE (sizeof(struct mem_desc) * 2)
78 void *malloc(size_t sz)
81 size_t total_sz, rest_sz;
82 struct mem_desc *mem, *rest, *prev, dummy;
85 total_sz = (sz + sizeof(struct mem_desc) + 3) & 0xfffffffc;
91 /* give the whole block to the allocation if mem->size == total_sz or
92 * if it's larger, but not large enough to fit another mem_desc in there
93 * for the new block that we're going to split off + some reasonable
94 * amount of memory for the new block.
96 if(mem->size >= total_sz && mem->size < total_sz + MIN_BLOCK_SIZE) {
97 prev->next = mem->next;
101 /* if we have enough space, split the block and give the upper part
104 if(mem->size > total_sz) {
105 void *ptr = (char*)mem + mem->size - total_sz;
106 mem->size -= total_sz;
116 mem->size = total_sz;
117 mem->magic = MAGIC_USED;
119 return DESC_PTR(mem);
122 /* did not find a free block, grab a new one */
123 npages = BYTES_TO_PAGES(total_sz);
124 if((pg0 = alloc_ppages(npages, 0)) == -1) {
128 mem = PAGE_TO_PTR(pg0);
129 mem->size = total_sz;
131 mem->magic = MAGIC_USED;
133 /* add the rest of the block to pool */
134 rest_sz = npages * 4096 - total_sz;
136 rest = (struct mem_desc*)((char*)mem + total_sz);
137 rest->size = rest_sz;
139 rest->magic = MAGIC_USED;
140 free(DESC_PTR(rest));
143 return DESC_PTR(mem);
148 struct mem_desc *mem, *prev, *cur, dummy;
154 if(mem->magic != MAGIC_USED) {
155 if(mem->magic == MAGIC_FREE) {
156 panic("free(%p): double-free\n", p);
158 panic("free(%p): corrupted magic (%x)!\n", p, mem->magic);
161 mem->magic = MAGIC_FREE;
164 /* nothing in the pool, just add this one */
170 end = (char*)mem + mem->size;
178 /* block starts right at the end of mem: coalesce */
179 if((char*)cur == end) {
180 mem->size += cur->size;
181 mem->next = cur->next;
187 /* block starts *after* the end of mem: add in front */
188 if((char*)cur > end) {
197 /* our block starts at the end of the last block in the pool: coalesce */
198 if((char*)prev + prev->size == (char*)mem) {
200 prev->size += mem->size;
204 /* so our block starts after the end of the last block: append */
215 #else /* !SINGLE_POOL */
217 void *malloc(size_t sz)
220 size_t total_sz, halfsz;
221 struct mem_desc *mem, *other;
223 total_sz = sz + sizeof(struct mem_desc);
225 if(total_sz > MAX_POOL_SIZE) {
226 /*printf(" allocation too big, hitting sys_alloc directly\n");*/
227 if((pg0 = alloc_ppages(BYTES_TO_PAGES(total_sz), 0)) == -1) {
231 mem = PAGE_TO_PTR(pg0);
232 mem->magic = MAGIC_USED;
233 mem->size = total_sz;
235 return DESC_PTR(mem);
238 pidx = pool_index(total_sz);
239 while(pidx < NUM_POOLS) {
241 /* found a pool with a free block that fits */
243 pools[pidx] = mem->next;
246 /*printf(" using pool %d (size %ld)\n", pidx, (unsigned long)mem->size);*/
248 /* while the mem size is larger than twice the allocation, split it */
249 while(pidx-- > 0 && total_sz <= (halfsz = mem->size / 2)) {
250 /*printf(" splitting %ld block in half and ", (unsigned long)mem->size);*/
251 other = (struct mem_desc*)((char*)mem + halfsz);
252 mem->size = other->size = halfsz;
257 if(mem->magic != MAGIC_FREE) {
258 panic("Trying to allocate range surrounded by an aura of wrong MAGIC\n");
260 mem->magic = MAGIC_USED;
261 return DESC_PTR(mem);
267 /* did not find a free block, add a new one */
268 pidx = NUM_POOLS - 1;
269 if((pg0 = alloc_ppages(MAX_POOL_PAGES, 0)) == -1) {
273 mem = PAGE_TO_PTR(pg0);
274 mem->size = MAX_POOL_SIZE;
275 mem->next = pools[pidx];
276 mem->magic = MAGIC_FREE;
279 /* try again now that there is a free block */
287 struct mem_desc *mem;
292 if(mem->magic != MAGIC_USED) {
293 if(mem->magic == MAGIC_FREE) {
294 panic("free(%p): double-free\n", p);
296 panic("free(%p): corrupted magic (%x)!\n", p, mem->magic);
300 if(mem->size > MAX_POOL_SIZE) {
301 /*printf("foo_free(%p): %ld bytes. block too large for pools, returning to system\n",
302 (void*)p, (unsigned long)mem->size);*/
303 pg0 = ADDR_TO_PAGE(mem);
304 free_ppages(pg0, BYTES_TO_PAGES(mem->size));
308 /*printf("foo_free(%p): block of %ld bytes and ", (void*)p, (unsigned long)mem->size);*/
312 #endif /* !def SINGLE_POOL */
315 void *calloc(size_t num, size_t size)
317 void *ptr = malloc(num * size);
319 memset(ptr, 0, num * size);
324 void *realloc(void *ptr, size_t size)
326 struct mem_desc *mem;
334 if(mem->size >= size) {
335 return ptr; /* TODO: shrink */
338 if(!(newp = malloc(size))) {
341 memcpy(newp, ptr, mem->size);
347 static void check_cycles(struct mem_desc *mem)
349 static uint32_t dbg = 42;
350 uint32_t cur_dbg = dbg++;
353 if(mem->magic != MAGIC_FREE) {
354 panic("check_cycles: NON-FREE MAGIC!\n");
356 if(mem->dbg == cur_dbg) {
357 panic("CYCLE DETECTED\n");
364 static void print_pool(void)
366 struct mem_desc *mem = pool;
368 printf("DBG: malloc pool:\n");
370 printf(" %p (%ld) [%x]\n", mem, mem->size, mem->magic);
373 assert((uint32_t)mem != MAGIC_USED);
376 #endif /* MALLOC_DEBUG */
379 static int add_to_pool(struct mem_desc *mem)
382 struct mem_desc head;
383 struct mem_desc *iter, *pnode;
385 pidx = pool_index(mem->size);
387 /*printf("adding %ld block to pool %d\n", (unsigned long)mem->size, pidx);*/
390 head.next = pools[pidx];
394 if(mem->size == pnode->size) { /* only coalesce same-sized blocks */
395 size_t size = mem->size;
397 if((char*)mem == (char*)pnode - size) {
398 iter->next = pnode->next; /* unlink pnode */
399 pools[pidx] = head.next;
403 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
404 return add_to_pool(mem);
406 if((char*)mem == (char*)pnode + size) {
407 iter->next = pnode->next; /* unlink pnode */
408 pools[pidx] = head.next;
412 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
413 return add_to_pool(pnode);
419 /* otherwise just add it to the pool */
420 mem->magic = MAGIC_FREE;
421 mem->next = pools[pidx];
425 check_cycles(pools[pidx]);
429 #endif /* !def SINGLE_POOL */