git.mutantstargoat.com Git - bootcensus/blob - src/libc/malloc.c

   1 /*
   2 pcboot - bootable PC demo/game kernel
   3 Copyright (C) 2018  John Tsiombikas <nuclear@member.fsf.org>
   4
   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.
   9
  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.
  14
  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/>.
  17 */
  18 #include <stdio.h>
  19 #include <stdlib.h>
  20 #include <string.h>
  21 #include <errno.h>
  22 #include "mem.h"
  23 #include "panic.h"
  24
  25 struct mem_desc {
  26         size_t size;
  27         uint32_t magic;
  28         struct mem_desc *next;
  29 };
  30
  31 #define MAGIC   0xdeadf00d
  32
  33 #define DESC_PTR(b)     ((void*)((struct mem_desc*)(b) + 1))
  34 #define PTR_DESC(p)     ((struct mem_desc*)(p) - 1)
  35
  36 #define NUM_POOLS       16
  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];
  43
  44 static int add_to_pool(struct mem_desc *b);
  45
  46 static int pool_index(int sz)
  47 {
  48         int x = 0;
  49         --sz;
  50         while(sz) {
  51                 sz >>= 1;
  52                 ++x;
  53         }
  54         return x - FIRST_POOL_POW2;
  55 }
  56
  57 void *malloc(size_t sz)
  58 {
  59         int pidx, pg0;
  60         size_t total_sz, halfsz;
  61         struct mem_desc *mem, *other;
  62
  63         total_sz = sz + sizeof(struct mem_desc);
  64
  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) {
  68                         errno = ENOMEM;
  69                         return 0;
  70                 }
  71                 mem = PAGE_TO_PTR(pg0);
  72                 mem->magic = MAGIC;
  73                 mem->size = total_sz;
  74                 mem->next = 0;
  75                 return DESC_PTR(mem);
  76         }
  77
  78         pidx = pool_index(total_sz);
  79         while(pidx < NUM_POOLS) {
  80                 if(pools[pidx]) {
  81                         /* found a pool with a free block that fits */
  82                         mem = pools[pidx];
  83                         pools[pidx] = mem->next;
  84                         mem->next = 0;
  85
  86                         /*printf("  using pool %d (size %ld)\n", pidx, (unsigned long)mem->size);*/
  87
  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;
  93
  94                                 add_to_pool(other);
  95                         }
  96
  97                         mem->magic = MAGIC;
  98                         return DESC_PTR(mem);
  99                 }
 100
 101                 ++pidx;
 102         }
 103
 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) {
 107                 errno = ENOMEM;
 108                 return 0;
 109         }
 110         mem = PAGE_TO_PTR(pg0);
 111         mem->size = MAX_POOL_SIZE;
 112         mem->next = pools[pidx];
 113         mem->magic = MAGIC;
 114         pools[pidx] = mem;
 115
 116         /* try again now that there is a free block */
 117         return malloc(sz);
 118 }
 119
 120
 121 void free(void *p)
 122 {
 123         int pg0;
 124         struct mem_desc *mem = PTR_DESC(p);
 125
 126         if(mem->magic != MAGIC) {
 127                 panic("free: corrupted magic!\n");
 128         }
 129
 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));
 135                 return;
 136         }
 137
 138         /*printf("foo_free(%p): block of %ld bytes and ", (void*)p, (unsigned long)mem->size);*/
 139         add_to_pool(mem);
 140 }
 141
 142
 143 void *calloc(size_t num, size_t size)
 144 {
 145         void *ptr = malloc(num * size);
 146         if(ptr) {
 147                 memset(ptr, 0, num * size);
 148         }
 149         return ptr;
 150 }
 151
 152 void *realloc(void *ptr, size_t size)
 153 {
 154         struct mem_desc *mem;
 155         void *newp;
 156
 157         if(!ptr) {
 158                 return malloc(size);
 159         }
 160
 161         mem = PTR_DESC(ptr);
 162         if(mem->size >= size) {
 163                 return ptr;     /* TODO: shrink */
 164         }
 165
 166         if(!(newp = malloc(size))) {
 167                 return 0;
 168         }
 169         free(ptr);
 170         return newp;
 171 }
 172
 173
 174 static int add_to_pool(struct mem_desc *mem)
 175 {
 176         int pidx;
 177         struct mem_desc head;
 178         struct mem_desc *iter, *pnode;
 179
 180         pidx = pool_index(mem->size);
 181
 182         /*printf("adding %ld block to pool %d\n", (unsigned long)mem->size, pidx);*/
 183
 184         iter = &head;
 185         head.next = pools[pidx];
 186
 187         while(iter->next) {
 188                 pnode = iter->next;
 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;
 193                                 mem->next = 0;
 194                                 mem->size += pnode->size;
 195
 196                                 /*printf("  coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
 197                                 return add_to_pool(mem);
 198                         }
 199                         if((char*)mem == (char*)pnode + pnode->size) {
 200                                 iter->next = pnode->next;       /* unlink pnode */
 201                                 pools[pidx] = head.next;
 202                                 pnode->next = 0;
 203                                 pnode->size += mem->size;
 204
 205                                 /*printf("  coalescing %p with %p and ", (void*)mem, (void*)pnode);*/
 206                                 return add_to_pool(pnode);
 207                         }
 208                 }
 209                 iter = iter->next;
 210         }
 211
 212         /* otherwise just add it to the pool */
 213         mem->next = pools[pidx];
 214         pools[pidx] = mem;
 215         return 0;
 216 }
 217