lunaix-os/kernel/mm/dmm.c

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