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 #include <lunaix/mm/dmm.h>
  14 #include <lunaix/mm/page.h>
  15 #include <lunaix/mm/vmm.h>
  16
  17 #include <lunaix/assert.h>
  18 #include <lunaix/constants.h>
  19 #include <lunaix/spike.h>
  20
  21 #define M_ALLOCATED 0x1
  22 #define M_PREV_FREE 0x2
  23
  24 #define M_NOT_ALLOCATED 0x0
  25 #define M_PREV_ALLOCATED 0x0
  26
  27 #define CHUNK_S(header) ((header) & ~0x3)
  28 #define CHUNK_PF(header) ((header)&M_PREV_FREE)
  29 #define CHUNK_A(header) ((header)&M_ALLOCATED)
  30
  31 #define PACK(size, flags) (((size) & ~0x3) | (flags))
  32
  33 #define SW(p, w) (*((uint32_t*)(p)) = w)
  34 #define LW(p) (*((uint32_t*)(p)))
  35
  36 #define HPTR(bp) ((uint32_t*)(bp)-1)
  37 #define BPTR(bp) ((uint8_t*)(bp) + WSIZE)
  38 #define FPTR(hp, size) ((uint32_t*)(hp + size - WSIZE))
  39 #define NEXT_CHK(hp) ((uint8_t*)(hp) + CHUNK_S(LW(hp)))
  40
  41 #define BOUNDARY 4
  42 #define WSIZE 4
  43
  44 extern uint8_t __kernel_heap_start;
  45
  46 void* current_heap_top = NULL;
  47
  48 void*
  49 coalesce(uint8_t* chunk_ptr);
  50
  51 void*
  52 lx_grow_heap(size_t sz);
  53
  54 void place_chunk(uint8_t* ptr, size_t size);
  55
  56 int
  57 dmm_init()
  58 {
  59     assert((uintptr_t)&__kernel_heap_start % BOUNDARY == 0);
  60
  61     current_heap_top = &__kernel_heap_start;
  62     uint8_t* heap_start = &__kernel_heap_start;
  63
  64     vmm_alloc_page(current_heap_top, PG_PREM_RW);
  65
  66     SW(heap_start,     PACK(4, M_ALLOCATED));
  67     SW(heap_start + WSIZE, PACK(0, M_ALLOCATED));
  68     current_heap_top += WSIZE;
  69
  70     return lx_grow_heap(HEAP_INIT_SIZE);
  71 }
  72
  73 int
  74 lxsbrk(void* addr)
  75 {
  76     return lxbrk(addr - current_heap_top) != NULL;
  77 }
  78
  79 void*
  80 lxbrk(size_t size)
  81 {
  82     if (size == 0) {
  83         return NULL;
  84     }
  85
  86     // plus WSIZE is the overhead for epilogue marker
  87     size += WSIZE;
  88     void* next = current_heap_top + ROUNDUP((uintptr_t)size, WSIZE);
  89
  90     if (next >= K_STACK_START) {
  91         return NULL;
  92     }
  93
  94     // Check the invariant
  95     assert(size % BOUNDARY == 0)
  96
  97     uintptr_t heap_top_pg = PG_ALIGN(current_heap_top);
  98       if (heap_top_pg != PG_ALIGN(next))
  99     {
 100         // if next do require new pages to be allocated
 101         if (!vmm_alloc_pages(heap_top_pg + PG_SIZE, ROUNDUP(size, PG_SIZE), PG_PRESENT | PG_WRITE)) {
 102             return NULL;
 103         }
 104
 105     }
 106
 107     uintptr_t old = current_heap_top;
 108     current_heap_top = next - WSIZE;
 109     return old;
 110 }
 111
 112 void*
 113 lx_grow_heap(size_t sz) {
 114     uintptr_t start;
 115
 116     sz = ROUNDUP(sz, BOUNDARY);
 117     if (!(start = lxbrk(sz))) {
 118         return NULL;
 119     }
 120
 121     uint32_t old_marker = *((uint32_t*)start);
 122     uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 123     SW(start, free_hdr);
 124     SW(FPTR(start, sz), free_hdr);
 125     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 126
 127     return coalesce(start);
 128 }
 129
 130 void*
 131 lx_malloc(size_t size)
 132 {
 133     // Simplest first fit approach.
 134
 135     uint8_t* ptr = &__kernel_heap_start;
 136     // round to largest 4B aligned value
 137     //  and space for header
 138     size = ROUNDUP(size, BOUNDARY) + WSIZE;
 139     while (ptr < current_heap_top) {
 140         uint32_t header = *((uint32_t*)ptr);
 141         size_t chunk_size = CHUNK_S(header);
 142         if (chunk_size >= size && !CHUNK_A(header)) {
 143             // found!
 144             place_chunk(ptr, size);
 145             return BPTR(ptr);
 146         }
 147         ptr += chunk_size;
 148     }
 149
 150     // if heap is full (seems to be!), then allocate more space (if it's okay...)
 151     if ((ptr = lx_grow_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 place_chunk(uint8_t* ptr, size_t size) {
 161     uint32_t header = *((uint32_t*)ptr);
 162     size_t chunk_size = CHUNK_S(header);
 163     *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 164     uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 165     uint32_t diff = chunk_size - size;
 166     if (!diff) {
 167         // if the current free block is fully occupied
 168         uint32_t n_hdr = LW(n_hdrptr);
 169         // notify the next block about our avaliability
 170         SW(n_hdrptr, n_hdr & ~0x2);
 171     } else {
 172         // if there is remaining free space left
 173         uint32_t remainder_hdr =
 174             PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
 175         SW(n_hdrptr, remainder_hdr);
 176         SW(FPTR(n_hdrptr, diff), remainder_hdr);
 177
 178         coalesce(n_hdrptr);
 179     }
 180 }
 181
 182 void
 183 lx_free(void* ptr)
 184 {
 185     if (!ptr) {
 186         return;
 187     }
 188
 189     uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
 190     uint32_t hdr = LW(chunk_ptr);
 191     uint8_t* next_hdr = chunk_ptr + CHUNK_S(hdr);
 192
 193     SW(chunk_ptr, hdr & ~M_ALLOCATED);
 194     SW(FPTR(chunk_ptr, CHUNK_S(hdr)), hdr & ~M_ALLOCATED);
 195     SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
 196
 197     coalesce(chunk_ptr);
 198 }
 199
 200 void*
 201 coalesce(uint8_t* chunk_ptr)
 202 {
 203     uint32_t hdr = LW(chunk_ptr);
 204     uint32_t pf = CHUNK_PF(hdr);
 205     uint32_t sz = CHUNK_S(hdr);
 206     uint32_t ftr = LW(chunk_ptr + sz - WSIZE);
 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 }