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.
   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 #include <stdbool.h>
  22
  23 #define M_ALLOCATED 0x1
  24 #define M_PREV_FREE 0x2
  25
  26 #define M_NOT_ALLOCATED 0x0
  27 #define M_PREV_ALLOCATED 0x0
  28
  29 #define CHUNK_S(header) ((header) & ~0x3)
  30 #define CHUNK_PF(header) ((header)&M_PREV_FREE)
  31 #define CHUNK_A(header) ((header)&M_ALLOCATED)
  32
  33 #define PACK(size, flags) (((size) & ~0x3) | (flags))
  34
  35 #define SW(p, w) (*((uint32_t*)(p)) = w)
  36 #define LW(p) (*((uint32_t*)(p)))
  37
  38 #define HPTR(bp) ((uint32_t*)(bp)-1)
  39 #define BPTR(bp) ((uint8_t*)(bp) + WSIZE)
  40 #define FPTR(hp, size) ((uint32_t*)(hp + size - WSIZE))
  41 #define NEXT_CHK(hp) ((uint8_t*)(hp) + CHUNK_S(LW(hp)))
  42
  43 #define BOUNDARY 4
  44 #define WSIZE 4
  45
  46 extern uint8_t __kernel_heap_start;
  47
  48 void* current_heap_top = NULL;
  49
  50 void*
  51 coalesce(uint8_t* chunk_ptr);
  52
  53 void*
  54 lx_grow_heap(size_t sz);
  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             // TODO: OOM, panic here! Rather than spinning.
 103             spin();
 104             // return NULL
 105         }
 106
 107     }
 108
 109     uintptr_t old = current_heap_top;
 110     current_heap_top = next - WSIZE;
 111     return old;
 112 }
 113
 114 void*
 115 lx_grow_heap(size_t sz) {
 116     uintptr_t start;
 117
 118     sz = ROUNDUP(sz, BOUNDARY);
 119     if (!(start = lxbrk(sz))) {
 120         return NULL;
 121     }
 122
 123     uint32_t old_marker = *((uint32_t*)start);
 124     uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 125     SW(start, free_hdr);
 126     SW(FPTR(start, sz), free_hdr);
 127     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 128
 129     return coalesce(start);
 130 }
 131
 132 void*
 133 lx_malloc(size_t size)
 134 {
 135     // Simplest first fit approach.
 136
 137     uint8_t* ptr = &__kernel_heap_start;
 138     // round to largest 4B aligned value
 139     //  and space for header
 140     size = ROUNDUP(size, BOUNDARY) + WSIZE;
 141     while (ptr < current_heap_top) {
 142         uint32_t header = *((uint32_t*)ptr);
 143         size_t chunk_size = CHUNK_S(header);
 144         if (chunk_size >= size && !CHUNK_A(header)) {
 145             // found!
 146             *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 147             uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 148             uint32_t diff = chunk_size - size;
 149             if (!diff) {
 150                 // if the current free block is fully occupied
 151                 uint32_t n_hdr = LW(n_hdrptr);
 152                 // notify the next block about our avaliability
 153                 SW(n_hdrptr, n_hdr & ~0x2);
 154             } else {
 155                 // if there is remaining free space left
 156                 uint32_t remainder_hdr =
 157                   PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
 158                 SW(n_hdrptr, remainder_hdr);
 159                 SW(FPTR(n_hdrptr, diff), remainder_hdr);
 160
 161                 coalesce(n_hdrptr);
 162             }
 163             return BPTR(ptr);
 164         }
 165         ptr += chunk_size;
 166     }
 167
 168     return NULL;
 169 }
 170
 171 void
 172 lx_free(void* ptr)
 173 {
 174     uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
 175     uint32_t hdr = LW(chunk_ptr);
 176     uint8_t* next_hdr = chunk_ptr + CHUNK_S(hdr);
 177
 178     SW(chunk_ptr, hdr & ~M_ALLOCATED);
 179     SW(FPTR(chunk_ptr, CHUNK_S(hdr)), hdr & ~M_ALLOCATED);
 180     SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
 181
 182     coalesce(chunk_ptr);
 183 }
 184
 185 void*
 186 coalesce(uint8_t* chunk_ptr)
 187 {
 188     uint32_t hdr = LW(chunk_ptr);
 189     uint32_t pf = CHUNK_PF(hdr);
 190     uint32_t sz = CHUNK_S(hdr);
 191     uint32_t ftr = LW(chunk_ptr + sz - WSIZE);
 192
 193     uint32_t n_hdr = LW(chunk_ptr + sz);
 194
 195     if (CHUNK_A(n_hdr) && pf) {
 196         // case 1: prev is free
 197         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 198         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 199         uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 200         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 201         SW(FPTR(chunk_ptr, sz), new_hdr);
 202         chunk_ptr -= prev_chunk_sz;
 203     } else if (!CHUNK_A(n_hdr) && !pf) {
 204         // case 2: next is free
 205         size_t next_chunk_sz = CHUNK_S(n_hdr);
 206         uint32_t new_hdr = PACK(next_chunk_sz + sz, pf);
 207         SW(chunk_ptr, new_hdr);
 208         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 209     } else if (!CHUNK_A(n_hdr) && pf) {
 210         // case 3: both free
 211         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 212         size_t next_chunk_sz = CHUNK_S(n_hdr);
 213         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 214         uint32_t new_hdr =
 215           PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 216         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 217         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 218         chunk_ptr -= prev_chunk_sz;
 219     }
 220
 221     // case 4: prev and next are not free
 222     return chunk_ptr;
 223 }