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/>.
25 struct mem_desc *next;
28 #define MAGIC 0xdeadf00d
30 #define DESC_PTR(b) ((void*)((struct mem_desc*)(b) + 1))
31 #define PTR_DESC(p) ((struct mem_desc*)(p) - 1)
34 #define FIRST_POOL_POW2 5
35 /* 2**(x+5) size pools: 0->32, 1->64, 2->128 .. 15->1048576 */
36 #define POOL_SIZE(x) (1 << ((x) + FIRST_POOL_POW2))
37 #define MAX_POOL_SIZE (1 << ((NUM_POOLS - 1) + FIRST_POOL_POW2))
38 #define MAX_POOL_PAGES BYTES_TO_PAGES(MAX_POOL_SIZE)
39 static struct mem_desc *pools[NUM_POOLS];
41 static int add_to_pool(struct mem_desc *b);
43 static int pool_index(int sz)
51 return x - FIRST_POOL_POW2;
54 void *malloc(size_t sz)
57 size_t total_sz, halfsz;
58 struct mem_desc *mem, *other;
60 total_sz = sz + sizeof(struct mem_desc);
62 if(total_sz > MAX_POOL_SIZE) {
63 /*printf(" allocation too big, hitting sys_alloc directly\n");*/
64 if((pg0 = alloc_ppages(BYTES_TO_PAGES(total_sz))) == -1) {
68 mem = PAGE_TO_PTR(pg0);
75 pidx = pool_index(total_sz);
76 while(pidx < NUM_POOLS) {
78 /* found a pool with a free block that fits */
80 pools[pidx] = mem->next;
83 /*printf(" using pool %d (size %ld)\n", pidx, (unsigned long)mem->size);*/
85 /* while the mem size is larger than twice the allocation, split it */
86 while(pidx-- > 0 && total_sz <= (halfsz = mem->size / 2)) {
87 /*printf(" splitting %ld block in half and ", (unsigned long)mem->size);*/
88 other = (struct mem_desc*)((char*)mem + halfsz);
89 mem->size = other->size = halfsz;
100 /* did not find a free block, add a new one */
101 pidx = NUM_POOLS - 1;
102 if((pg0 = alloc_ppages(MAX_POOL_PAGES)) == -1) {
106 mem = PAGE_TO_PTR(pg0);
107 mem->size = MAX_POOL_SIZE;
108 mem->next = pools[pidx];
112 /* try again now that there is a free block */
120 struct mem_desc *mem = PTR_DESC(p);
122 if(mem->size > MAX_POOL_SIZE) {
123 /*printf("foo_free(%p): %ld bytes. block too large for pools, returning to system\n",
124 (void*)p, (unsigned long)mem->size);*/
125 pg0 = ADDR_TO_PAGE(mem);
126 free_ppages(pg0, BYTES_TO_PAGES(mem->size));
130 /*printf("foo_free(%p): block of %ld bytes and ", (void*)p, (unsigned long)mem->size);*/
134 static int add_to_pool(struct mem_desc *mem)
137 struct mem_desc head;
138 struct mem_desc *iter, *pnode;
140 pidx = pool_index(mem->size);
142 /*printf("adding %ld block to pool %d\n", (unsigned long)mem->size, pidx);*/
145 head.next = pools[pidx];
149 if(mem->size == pnode->size) { /* only coalesce same-sized blocks */
150 if((char*)mem == (char*)pnode - pnode->size) {
151 iter = pnode->next; /* unlink pnode */
152 pools[pidx] = head.next;
154 mem->size += pnode->size;
156 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
157 return add_to_pool(mem);
159 if((char*)mem == (char*)pnode + pnode->size) {
160 iter = pnode->next; /* unlink pnode */
161 pools[pidx] = head.next;
163 pnode->size += mem->size;
165 /*printf(" coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
166 return add_to_pool(pnode);
172 /* otherwise just add it to the pool */
173 mem->next = pools[pidx];