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