lunaix-os/kernel/mm/kalloc.c

   1 /**
   2  * @file kalloc.c
   3  * @author Lunaixsky
   4  * @brief Implicit free list implementation of malloc family, for kernel use.
   5  *
   6  * This version of code is however the simplest and yet insecured, thread unsafe
   7  * it just to demonstrate how the malloc/free works behind the curtain
   8  * @version 0.1
   9  * @date 2022-03-05
  10  *
  11  * @copyright Copyright (c) 2022
  12  *
  13  */
  14 #include <lunaix/mm/kalloc.h>
  15 #include <lunaix/mm/dmm.h>
  16
  17 #include <lunaix/common.h>
  18 #include <lunaix/spike.h>
  19
  20 #include <klibc/string.h>
  21
  22 #include <stdint.h>
  23
  24 extern uint8_t __kernel_heap_start;
  25
  26 void*
  27 lx_malloc_internal(heap_context_t* heap, size_t size);
  28
  29 void
  30 place_chunk(uint8_t* ptr, size_t size);
  31
  32 void
  33 lx_free_internal(void* ptr);
  34
  35 void*
  36 coalesce(uint8_t* chunk_ptr);
  37
  38 void*
  39 lx_grow_heap(heap_context_t* heap, size_t sz);
  40
  41 /*
  42     At the beginning, we allocate an empty page and put our initial marker
  43
  44     | 4/1 | 0/1 |
  45     ^     ^ brk
  46     start
  47
  48     Then, expand the heap further, with HEAP_INIT_SIZE (evaluated to 4096, i.e., 1 pg size)
  49     This will allocate as much pages and override old epilogue marker with a free region hdr
  50         and put new epilogue marker. These are handled by lx_grow_heap which is internally used
  51         by alloc to expand the heap at many moment when needed.
  52
  53     | 4/1 | 4096/0 |   .......   | 4096/0 | 0/1 |
  54     ^     ^ brk_old                       ^
  55     start                                 brk
  56
  57     Note: the brk always point to the beginning of epilogue.
  58 */
  59
  60 int
  61 kalloc_init() {
  62     heap_context_t* kheap = &__current->mm.k_heap;
  63     kheap->start = &__kernel_heap_start;
  64     kheap->brk = NULL;
  65     kheap->max_addr = (void*)KSTACK_START;
  66
  67     if (!dmm_init(kheap)) {
  68         return 0;
  69     }
  70
  71     SW(kheap->start, PACK(4, M_ALLOCATED));
  72     SW(kheap->start + WSIZE, PACK(0, M_ALLOCATED));
  73     kheap->brk += WSIZE;
  74
  75     return lx_grow_heap(kheap, HEAP_INIT_SIZE) != NULL;
  76 }
  77
  78 void*
  79 lxmalloc(size_t size) {
  80     return lx_malloc_internal(&__current->mm.k_heap, size);
  81 }
  82
  83 void*
  84 lxcalloc(size_t n, size_t elem) {
  85     size_t pd = n * elem;
  86
  87     // overflow detection
  88     if (pd < elem || pd < n) {
  89         return NULL;
  90     }
  91
  92     void* ptr = lxmalloc(pd);
  93     if (!ptr) {
  94         return NULL;
  95     }
  96
  97     return memset(ptr, 0, pd);
  98 }
  99
 100 void
 101 lxfree(void* ptr) {
 102     if (!ptr) {
 103         return;
 104     }
 105
 106     uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
 107     uint32_t hdr = LW(chunk_ptr);
 108     size_t sz = CHUNK_S(hdr);
 109     uint8_t* next_hdr = chunk_ptr + sz;
 110
 111     // make sure the ptr we are 'bout to free makes sense
 112     //   the size trick is stolen from glibc's malloc/malloc.c:4437 ;P
 113
 114     assert_msg(((uintptr_t)ptr < (uintptr_t)(-sz)) && !((uintptr_t)ptr & 0x3),
 115                "free(): invalid pointer");
 116
 117     assert_msg(sz > WSIZE,
 118                "free(): invalid size");
 119
 120     SW(chunk_ptr, hdr & ~M_ALLOCATED);
 121     SW(FPTR(chunk_ptr, sz), hdr & ~M_ALLOCATED);
 122     SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
 123
 124     coalesce(chunk_ptr);
 125 }
 126
 127
 128 void*
 129 lx_malloc_internal(heap_context_t* heap, size_t size)
 130 {
 131     // Simplest first fit approach.
 132
 133     if (!size) {
 134         return NULL;
 135     }
 136
 137     uint8_t* ptr = heap->start;
 138     // round to largest 4B aligned value
 139     //  and space for header
 140     size = ROUNDUP(size + WSIZE, BOUNDARY);
 141     while (ptr < (uint8_t*)heap->brk) {
 142         uint32_t header = *((uint32_t*)ptr);
 143         size_t chunk_size = CHUNK_S(header);
 144         if (!chunk_size && CHUNK_A(header)) {
 145             break;
 146         }
 147         if (chunk_size >= size && !CHUNK_A(header)) {
 148             // found!
 149             place_chunk(ptr, size);
 150             return BPTR(ptr);
 151         }
 152         ptr += chunk_size;
 153     }
 154
 155     // if heap is full (seems to be!), then allocate more space (if it's
 156     // okay...)
 157     if ((ptr = lx_grow_heap(heap, size))) {
 158         place_chunk(ptr, size);
 159         return BPTR(ptr);
 160     }
 161
 162     // Well, we are officially OOM!
 163     return NULL;
 164 }
 165
 166 void
 167 place_chunk(uint8_t* ptr, size_t size)
 168 {
 169     uint32_t header = *((uint32_t*)ptr);
 170     size_t chunk_size = CHUNK_S(header);
 171     *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 172     uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 173     uint32_t diff = chunk_size - size;
 174
 175     if (!diff) {
 176         // if the current free block is fully occupied
 177         uint32_t n_hdr = LW(n_hdrptr);
 178         // notify the next block about our avaliability
 179         SW(n_hdrptr, n_hdr & ~0x2);
 180     } else {
 181         // if there is remaining free space left
 182         uint32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
 183         SW(n_hdrptr, remainder_hdr);
 184         SW(FPTR(n_hdrptr, diff), remainder_hdr);
 185
 186         /*
 187             | xxxx |      |         |
 188
 189                         |
 190                         v
 191
 192             | xxxx |                |
 193         */
 194         coalesce(n_hdrptr);
 195     }
 196 }
 197
 198 void*
 199 coalesce(uint8_t* chunk_ptr)
 200 {
 201     uint32_t hdr = LW(chunk_ptr);
 202     uint32_t pf = CHUNK_PF(hdr);
 203     uint32_t sz = CHUNK_S(hdr);
 204
 205     uint32_t n_hdr = LW(chunk_ptr + sz);
 206
 207     if (CHUNK_A(n_hdr) && pf) {
 208         // case 1: prev is free
 209         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 210         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 211         uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 212         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 213         SW(FPTR(chunk_ptr, sz), new_hdr);
 214         chunk_ptr -= prev_chunk_sz;
 215     } else if (!CHUNK_A(n_hdr) && !pf) {
 216         // case 2: next is free
 217         size_t next_chunk_sz = CHUNK_S(n_hdr);
 218         uint32_t new_hdr = PACK(next_chunk_sz + sz, pf);
 219         SW(chunk_ptr, new_hdr);
 220         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 221     } else if (!CHUNK_A(n_hdr) && pf) {
 222         // case 3: both free
 223         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 224         size_t next_chunk_sz = CHUNK_S(n_hdr);
 225         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 226         uint32_t new_hdr =
 227           PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 228         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 229         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 230         chunk_ptr -= prev_chunk_sz;
 231     }
 232
 233     // (fall through) case 4: prev and next are not free
 234     return chunk_ptr;
 235 }
 236
 237
 238 void*
 239 lx_grow_heap(heap_context_t* heap, size_t sz)
 240 {
 241     void* start;
 242
 243     // The "+ WSIZE" capture the overhead for epilogue marker
 244     if (!(start = lxbrk(heap, sz + WSIZE))) {
 245         return NULL;
 246     }
 247     sz = ROUNDUP(sz, BOUNDARY);
 248
 249     // minus the overhead for epilogue, keep the invariant.
 250     heap->brk -= WSIZE;
 251
 252     uint32_t old_marker = *((uint32_t*)start);
 253     uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 254     SW(start, free_hdr);
 255     SW(FPTR(start, sz), free_hdr);
 256     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 257
 258     return coalesce(start);
 259 }