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 int
  66 kalloc_init()
  67 {
  68     kheap.start = KHEAP_START;
  69     kheap.brk = NULL;
  70     kheap.max_addr =
  71       (void*)PROC_START; // 在新的布局中，堆结束的地方即为进程表开始的地方
  72
  73     for (size_t i = 0; i < KHEAP_SIZE_MB >> 2; i++) {
  74         vmm_set_mapping(PD_REFERENCED,
  75                         (uintptr_t)kheap.start + (i << 22),
  76                         0,
  77                         PG_PREM_RW,
  78                         VMAP_NOMAP);
  79     }
  80
  81     if (!dmm_init(&kheap)) {
  82         return 0;
  83     }
  84
  85     SW(kheap.start, PACK(4, M_ALLOCATED));
  86     SW(kheap.start + WSIZE, PACK(0, M_ALLOCATED));
  87     kheap.brk += WSIZE;
  88
  89     return lx_grow_heap(&kheap, HEAP_INIT_SIZE) != NULL;
  90 }
  91
  92 void*
  93 lxmalloc(size_t size)
  94 {
  95     mutex_lock(&kheap.lock);
  96     void* r = lx_malloc_internal(&kheap, size);
  97     mutex_unlock(&kheap.lock);
  98
  99     return r;
 100 }
 101
 102 void*
 103 lxcalloc(size_t n, size_t elem)
 104 {
 105     size_t pd = n * elem;
 106
 107     // overflow detection
 108     if (pd < elem || pd < n) {
 109         return NULL;
 110     }
 111
 112     void* ptr = lxmalloc(pd);
 113     if (!ptr) {
 114         return NULL;
 115     }
 116
 117     return memset(ptr, 0, pd);
 118 }
 119
 120 void
 121 lxfree(void* ptr)
 122 {
 123     if (!ptr) {
 124         return;
 125     }
 126     mutex_lock(&kheap.lock);
 127
 128     uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
 129     uint32_t hdr = LW(chunk_ptr);
 130     size_t sz = CHUNK_S(hdr);
 131     uint8_t* next_hdr = chunk_ptr + sz;
 132
 133     // make sure the ptr we are 'bout to free makes sense
 134     //   the size trick is stolen from glibc's malloc/malloc.c:4437 ;P
 135
 136     assert_msg(((uintptr_t)ptr < (uintptr_t)(-sz)) && !((uintptr_t)ptr & 0x3),
 137                "free(): invalid pointer");
 138
 139     assert_msg(sz > WSIZE, "free(): invalid size");
 140
 141     SW(chunk_ptr, hdr & ~M_ALLOCATED);
 142     SW(FPTR(chunk_ptr, sz), hdr & ~M_ALLOCATED);
 143     SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
 144
 145     coalesce(chunk_ptr);
 146
 147     mutex_unlock(&kheap.lock);
 148 }
 149
 150 void*
 151 lx_malloc_internal(heap_context_t* heap, size_t size)
 152 {
 153     // Simplest first fit approach.
 154
 155     if (!size) {
 156         return NULL;
 157     }
 158
 159     uint8_t* ptr = heap->start;
 160     // round to largest 4B aligned value
 161     //  and space for header
 162     size = ROUNDUP(size + WSIZE, BOUNDARY);
 163     while (ptr < (uint8_t*)heap->brk) {
 164         uint32_t header = *((uint32_t*)ptr);
 165         size_t chunk_size = CHUNK_S(header);
 166         if (!chunk_size && CHUNK_A(header)) {
 167             break;
 168         }
 169         if (chunk_size >= size && !CHUNK_A(header)) {
 170             // found!
 171             place_chunk(ptr, size);
 172             return BPTR(ptr);
 173         }
 174         ptr += chunk_size;
 175     }
 176
 177     // if heap is full (seems to be!), then allocate more space (if it's
 178     // okay...)
 179     if ((ptr = lx_grow_heap(heap, size))) {
 180         place_chunk(ptr, size);
 181         return BPTR(ptr);
 182     }
 183
 184     // Well, we are officially OOM!
 185     return NULL;
 186 }
 187
 188 void
 189 place_chunk(uint8_t* ptr, size_t size)
 190 {
 191     uint32_t header = *((uint32_t*)ptr);
 192     size_t chunk_size = CHUNK_S(header);
 193     *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 194     uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 195     uint32_t diff = chunk_size - size;
 196
 197     if (!diff) {
 198         // if the current free block is fully occupied
 199         uint32_t n_hdr = LW(n_hdrptr);
 200         // notify the next block about our avaliability
 201         SW(n_hdrptr, n_hdr & ~0x2);
 202     } else {
 203         // if there is remaining free space left
 204         uint32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
 205         SW(n_hdrptr, remainder_hdr);
 206         SW(FPTR(n_hdrptr, diff), remainder_hdr);
 207
 208         /*
 209             | xxxx |      |         |
 210
 211                         |
 212                         v
 213
 214             | xxxx |                |
 215         */
 216         coalesce(n_hdrptr);
 217     }
 218 }
 219
 220 void*
 221 coalesce(uint8_t* chunk_ptr)
 222 {
 223     uint32_t hdr = LW(chunk_ptr);
 224     uint32_t pf = CHUNK_PF(hdr);
 225     uint32_t sz = CHUNK_S(hdr);
 226
 227     uint32_t n_hdr = LW(chunk_ptr + sz);
 228
 229     if (CHUNK_A(n_hdr) && pf) {
 230         // case 1: prev is free
 231         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 232         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 233         uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 234         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 235         SW(FPTR(chunk_ptr, sz), new_hdr);
 236         chunk_ptr -= prev_chunk_sz;
 237     } else if (!CHUNK_A(n_hdr) && !pf) {
 238         // case 2: next is free
 239         size_t next_chunk_sz = CHUNK_S(n_hdr);
 240         uint32_t new_hdr = PACK(next_chunk_sz + sz, pf);
 241         SW(chunk_ptr, new_hdr);
 242         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 243     } else if (!CHUNK_A(n_hdr) && pf) {
 244         // case 3: both free
 245         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 246         size_t next_chunk_sz = CHUNK_S(n_hdr);
 247         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 248         uint32_t new_hdr =
 249           PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 250         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 251         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 252         chunk_ptr -= prev_chunk_sz;
 253     }
 254
 255     // (fall through) case 4: prev and next are not free
 256     return chunk_ptr;
 257 }
 258
 259 void*
 260 lx_grow_heap(heap_context_t* heap, size_t sz)
 261 {
 262     void* start;
 263
 264     // The "+ WSIZE" capture the overhead for epilogue marker
 265     if (!(start = lxsbrk(heap, sz + WSIZE, 0))) {
 266         return NULL;
 267     }
 268     sz = ROUNDUP(sz, BOUNDARY);
 269
 270     // minus the overhead for epilogue, keep the invariant.
 271     heap->brk -= WSIZE;
 272
 273     uint32_t old_marker = *((uint32_t*)start);
 274     uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 275     SW(start, free_hdr);
 276     SW(FPTR(start, sz), free_hdr);
 277     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 278
 279     return coalesce(start);
 280 }