lunaix-os/kernel/mm/dmm.c

   1 /**
   2  * @file dmm.c
   3  * @author Lunaixsky
   4  * @brief Dynamic memory manager dedicated to kernel heap. It is not portable at
   5  * this moment. Implicit free list implementation.
   6  * @version 0.1
   7  * @date 2022-02-28
   8  *
   9  * @copyright Copyright (c) Lunaixsky 2022
  10  *
  11  */
  12
  13 // TODO: Make the dmm portable
  14
  15 #include <lunaix/mm/dmm.h>
  16 #include <lunaix/mm/page.h>
  17 #include <lunaix/mm/vmm.h>
  18
  19 #include <lunaix/constants.h>
  20 #include <lunaix/spike.h>
  21
  22 #define M_ALLOCATED 0x1
  23 #define M_PREV_FREE 0x2
  24
  25 #define M_NOT_ALLOCATED 0x0
  26 #define M_PREV_ALLOCATED 0x0
  27
  28 #define CHUNK_S(header) ((header) & ~0x3)
  29 #define CHUNK_PF(header) ((header)&M_PREV_FREE)
  30 #define CHUNK_A(header) ((header)&M_ALLOCATED)
  31
  32 #define PACK(size, flags) (((size) & ~0x3) | (flags))
  33
  34 #define SW(p, w) (*((uint32_t*)(p)) = w)
  35 #define LW(p) (*((uint32_t*)(p)))
  36
  37 #define HPTR(bp) ((uint32_t*)(bp)-1)
  38 #define BPTR(bp) ((uint8_t*)(bp) + WSIZE)
  39 #define FPTR(hp, size) ((uint32_t*)(hp + size - WSIZE))
  40 #define NEXT_CHK(hp) ((uint8_t*)(hp) + CHUNK_S(LW(hp)))
  41
  42 #define BOUNDARY 4
  43 #define WSIZE 4
  44
  45 extern uint8_t __kernel_heap_start;
  46
  47 void* current_heap_top = NULL;
  48
  49 void*
  50 coalesce(uint8_t* chunk_ptr);
  51
  52 void*
  53 lx_grow_heap(size_t sz);
  54
  55 void place_chunk(uint8_t* ptr, size_t size);
  56
  57 int
  58 dmm_init()
  59 {
  60     assert((uintptr_t)&__kernel_heap_start % BOUNDARY == 0);
  61
  62     current_heap_top = &__kernel_heap_start;
  63     uint8_t* heap_start = &__kernel_heap_start;
  64
  65     vmm_alloc_page(current_heap_top, PG_PREM_RW);
  66
  67     SW(heap_start,     PACK(4, M_ALLOCATED));
  68     SW(heap_start + WSIZE, PACK(0, M_ALLOCATED));
  69     current_heap_top += WSIZE;
  70
  71     return lx_grow_heap(HEAP_INIT_SIZE) != NULL;
  72 }
  73
  74 int
  75 lxsbrk(void* addr)
  76 {
  77     return lxbrk(addr - current_heap_top) != NULL;
  78 }
  79
  80 void*
  81 lxbrk(size_t size)
  82 {
  83     if (size == 0) {
  84         return current_heap_top;
  85     }
  86
  87     // plus WSIZE is the overhead for epilogue marker
  88     size += WSIZE;
  89     void* next = current_heap_top + ROUNDUP((uintptr_t)size, WSIZE);
  90
  91     if ((uintptr_t)next >= K_STACK_START) {
  92         return NULL;
  93     }
  94
  95     // Check the invariant
  96     assert(size % BOUNDARY == 0)
  97
  98     uintptr_t heap_top_pg = PG_ALIGN(current_heap_top);
  99       if (heap_top_pg != PG_ALIGN(next))
 100     {
 101         // if next do require new pages to be allocated
 102         if (!vmm_alloc_pages((void*)(heap_top_pg + PG_SIZE), ROUNDUP(size, PG_SIZE), PG_PREM_RW)) {
 103             return NULL;
 104         }
 105
 106     }
 107
 108     void* old = current_heap_top;
 109     current_heap_top = next - WSIZE;
 110     return old;
 111 }
 112
 113 void*
 114 lx_grow_heap(size_t sz) {
 115     void* start;
 116
 117     sz = ROUNDUP(sz, BOUNDARY);
 118     if (!(start = lxbrk(sz))) {
 119         return NULL;
 120     }
 121
 122     uint32_t old_marker = *((uint32_t*)start);
 123     uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 124     SW(start, free_hdr);
 125     SW(FPTR(start, sz), free_hdr);
 126     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 127
 128     return coalesce(start);
 129 }
 130
 131 void*
 132 lx_malloc(size_t size)
 133 {
 134     // Simplest first fit approach.
 135
 136     uint8_t* ptr = &__kernel_heap_start;
 137     // round to largest 4B aligned value
 138     //  and space for header
 139     size = ROUNDUP(size, BOUNDARY) + WSIZE;
 140     while (ptr < (uint8_t*)current_heap_top) {
 141         uint32_t header = *((uint32_t*)ptr);
 142         size_t chunk_size = CHUNK_S(header);
 143         if (chunk_size >= size && !CHUNK_A(header)) {
 144             // found!
 145             place_chunk(ptr, size);
 146             return BPTR(ptr);
 147         }
 148         ptr += chunk_size;
 149     }
 150
 151     // if heap is full (seems to be!), then allocate more space (if it's okay...)
 152     if ((ptr = lx_grow_heap(size))) {
 153         place_chunk(ptr, size);
 154         return BPTR(ptr);
 155     }
 156
 157     // Well, we are officially OOM!
 158     return NULL;
 159 }
 160
 161 void place_chunk(uint8_t* ptr, size_t size) {
 162     uint32_t header = *((uint32_t*)ptr);
 163     size_t chunk_size = CHUNK_S(header);
 164     *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 165     uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 166     uint32_t diff = chunk_size - size;
 167     if (!diff) {
 168         // if the current free block is fully occupied
 169         uint32_t n_hdr = LW(n_hdrptr);
 170         // notify the next block about our avaliability
 171         SW(n_hdrptr, n_hdr & ~0x2);
 172     } else {
 173         // if there is remaining free space left
 174         uint32_t remainder_hdr =
 175             PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
 176         SW(n_hdrptr, remainder_hdr);
 177         SW(FPTR(n_hdrptr, diff), remainder_hdr);
 178
 179         coalesce(n_hdrptr);
 180     }
 181 }
 182
 183 void
 184 lx_free(void* ptr)
 185 {
 186     if (!ptr) {
 187         return;
 188     }
 189
 190     uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
 191     uint32_t hdr = LW(chunk_ptr);
 192     uint8_t* next_hdr = chunk_ptr + CHUNK_S(hdr);
 193
 194     SW(chunk_ptr, hdr & ~M_ALLOCATED);
 195     SW(FPTR(chunk_ptr, CHUNK_S(hdr)), hdr & ~M_ALLOCATED);
 196     SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
 197
 198     coalesce(chunk_ptr);
 199 }
 200
 201 void*
 202 coalesce(uint8_t* chunk_ptr)
 203 {
 204     uint32_t hdr = LW(chunk_ptr);
 205     uint32_t pf = CHUNK_PF(hdr);
 206     uint32_t sz = CHUNK_S(hdr);
 207
 208     uint32_t n_hdr = LW(chunk_ptr + sz);
 209
 210     if (CHUNK_A(n_hdr) && pf) {
 211         // case 1: prev is free
 212         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 213         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 214         uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 215         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 216         SW(FPTR(chunk_ptr, sz), new_hdr);
 217         chunk_ptr -= prev_chunk_sz;
 218     } else if (!CHUNK_A(n_hdr) && !pf) {
 219         // case 2: next is free
 220         size_t next_chunk_sz = CHUNK_S(n_hdr);
 221         uint32_t new_hdr = PACK(next_chunk_sz + sz, pf);
 222         SW(chunk_ptr, new_hdr);
 223         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 224     } else if (!CHUNK_A(n_hdr) && pf) {
 225         // case 3: both free
 226         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 227         size_t next_chunk_sz = CHUNK_S(n_hdr);
 228         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 229         uint32_t new_hdr =
 230           PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 231         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 232         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 233         chunk_ptr -= prev_chunk_sz;
 234     }
 235
 236     // case 4: prev and next are not free
 237     return chunk_ptr;
 238 }