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