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