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