2 pcboot - bootable PC demo/game kernel
3 Copyright (C) 2018 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/>.
28 struct mem_desc *next;
31 #define MAGIC 0xdeadf00d
33 #define DESC_PTR(b) ((void*)((struct mem_desc*)(b) + 1))
34 #define PTR_DESC(p) ((struct mem_desc*)(p) - 1)
37 #define FIRST_POOL_POW2 5
38 /* 2**(x+5) size pools: 0->32, 1->64, 2->128 .. 15->1048576 */
39 #define POOL_SIZE(x) (1 << ((x) + FIRST_POOL_POW2))
40 #define MAX_POOL_SIZE (1 << ((NUM_POOLS - 1) + FIRST_POOL_POW2))
41 #define MAX_POOL_PAGES BYTES_TO_PAGES(MAX_POOL_SIZE)
42 static struct mem_desc *pools[NUM_POOLS];
44 static int add_to_pool(struct mem_desc *b);
46 static int pool_index(int sz)
54 return x - FIRST_POOL_POW2;
57 void *malloc(size_t sz)
60 size_t total_sz, halfsz;
61 struct mem_desc *mem, *other;
63 total_sz = sz + sizeof(struct mem_desc);
65 if(total_sz > MAX_POOL_SIZE) {
66 /*printf(" allocation too big, hitting sys_alloc directly\n");*/
67 if((pg0 = alloc_ppages(BYTES_TO_PAGES(total_sz))) == -1) {
71 mem = PAGE_TO_PTR(pg0);
78 pidx = pool_index(total_sz);
79 while(pidx < NUM_POOLS) {
81 /* found a pool with a free block that fits */
83 pools[pidx] = mem->next;
86 /*printf(" using pool %d (size %ld)\n", pidx, (unsigned long)mem->size);*/
88 /* while the mem size is larger than twice the allocation, split it */
89 while(pidx-- > 0 && total_sz <= (halfsz = mem->size / 2)) {
90 /*printf(" splitting %ld block in half and ", (unsigned long)mem->size);*/
91 other = (struct mem_desc*)((char*)mem + halfsz);
92 mem->size = other->size = halfsz;
104 /* did not find a free block, add a new one */
105 pidx = NUM_POOLS - 1;
106 if((pg0 = alloc_ppages(MAX_POOL_PAGES)) == -1) {
110 mem = PAGE_TO_PTR(pg0);
111 mem->size = MAX_POOL_SIZE;
112 mem->next = pools[pidx];
116 /* try again now that there is a free block */
124 struct mem_desc *mem = PTR_DESC(p);
126 if(mem->magic != MAGIC) {
127 panic("free: corrupted magic!\n");
130 if(mem->size > MAX_POOL_SIZE) {
131 /*printf("foo_free(%p): %ld bytes. block too large for pools, returning to system\n",
132 (void*)p, (unsigned long)mem->size);*/
133 pg0 = ADDR_TO_PAGE(mem);
134 free_ppages(pg0, BYTES_TO_PAGES(mem->size));
138 /*printf("foo_free(%p): block of %ld bytes and ", (void*)p, (unsigned long)mem->size);*/
143 void *calloc(size_t num, size_t size)
145 void *ptr = malloc(num * size);
147 memset(ptr, 0, num * size);
152 void *realloc(void *ptr, size_t size)
154 struct mem_desc *mem;
162 if(mem->size >= size) {
163 return ptr; /* TODO: shrink */
166 if(!(newp = malloc(size))) {
174 static int add_to_pool(struct mem_desc *mem)
177 struct mem_desc head;
178 struct mem_desc *iter, *pnode;
180 pidx = pool_index(mem->size);
182 /*printf("adding %ld block to pool %d\n", (unsigned long)mem->size, pidx);*/
185 head.next = pools[pidx];
189 if(mem->size == pnode->size) { /* only coalesce same-sized blocks */
190 if((char*)mem == (char*)pnode - pnode->size) {
191 iter->next = pnode->next; /* unlink pnode */
192 pools[pidx] = head.next;
194 mem->size += pnode->size;
196 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
197 return add_to_pool(mem);
199 if((char*)mem == (char*)pnode + pnode->size) {
200 iter->next = pnode->next; /* unlink pnode */
201 pools[pidx] = head.next;
203 pnode->size += mem->size;
205 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
206 return add_to_pool(pnode);
212 /* otherwise just add it to the pool */
213 mem->next = pools[pidx];