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
   5  * list implementation. This is designed to be portable, so it can serve as
   6  * syscalls to malloc/free in the c std lib.
   7  *
   8  * This version of code is however the simplest and yet insecured,
   9  * it just to demonstrate how the malloc/free works behind the stage
  10  *
  11  * @version 0.2
  12  * @date 2022-03-3
  13  *
  14  * @copyright Copyright (c) Lunaixsky 2022
  15  *
  16  */
  17
  18 #include <lunaix/mm/dmm.h>
  19 #include <lunaix/mm/page.h>
  20 #include <lunaix/mm/vmm.h>
  21
  22 #include <lunaix/constants.h>
  23 #include <lunaix/spike.h>
  24
  25 #define M_ALLOCATED 0x1
  26 #define M_PREV_FREE 0x2
  27
  28 #define M_NOT_ALLOCATED 0x0
  29 #define M_PREV_ALLOCATED 0x0
  30
  31 #define CHUNK_S(header) ((header) & ~0x3)
  32 #define CHUNK_PF(header) ((header)&M_PREV_FREE)
  33 #define CHUNK_A(header) ((header)&M_ALLOCATED)
  34
  35 #define PACK(size, flags) (((size) & ~0x3) | (flags))
  36
  37 #define SW(p, w) (*((uint32_t*)(p)) = w)
  38 #define LW(p) (*((uint32_t*)(p)))
  39
  40 #define HPTR(bp) ((uint32_t*)(bp)-1)
  41 #define BPTR(bp) ((uint8_t*)(bp) + WSIZE)
  42 #define FPTR(hp, size) ((uint32_t*)(hp + size - WSIZE))
  43 #define NEXT_CHK(hp) ((uint8_t*)(hp) + CHUNK_S(LW(hp)))
  44
  45 #define BOUNDARY 4
  46 #define WSIZE 4
  47
  48 void*
  49 coalesce(uint8_t* chunk_ptr);
  50
  51 void*
  52 lx_grow_heap(heap_context_t* heap, size_t sz);
  53
  54 void
  55 place_chunk(uint8_t* ptr, size_t size);
  56
  57 int
  58 dmm_init(heap_context_t* heap)
  59 {
  60     assert((uintptr_t)heap->start % BOUNDARY == 0);
  61
  62     heap->brk = heap->start;
  63
  64     vmm_alloc_page(heap->brk, PG_PREM_RW);
  65
  66     SW(heap->start, PACK(4, M_ALLOCATED));
  67     SW(heap->start + WSIZE, PACK(0, M_ALLOCATED));
  68     heap->brk += WSIZE;
  69
  70     return lx_grow_heap(heap, HEAP_INIT_SIZE) != NULL;
  71 }
  72
  73 int
  74 lxsbrk(heap_context_t* heap, void* addr)
  75 {
  76     return lxbrk(heap, addr - heap->brk) != NULL;
  77 }
  78
  79 void*
  80 lxbrk(heap_context_t* heap, size_t size)
  81 {
  82     if (size == 0) {
  83         return heap->brk;
  84     }
  85
  86     // The upper bound of our next brk of heap given the size.
  87     // This will be used to calculate the page we need to allocate.
  88     // The "+ WSIZE" capture the overhead for epilogue marker
  89     void* next = heap->brk + ROUNDUP(size + WSIZE, WSIZE);
  90
  91     if ((uintptr_t)next >= K_STACK_START) {
  92         return NULL;
  93     }
  94
  95     uintptr_t heap_top_pg = PG_ALIGN(heap->brk);
  96     if (heap_top_pg != PG_ALIGN(next)) {
  97         // if next do require new pages to be allocated
  98         if (!vmm_alloc_pages((void*)(heap_top_pg + PG_SIZE),
  99                              ROUNDUP(size, PG_SIZE),
 100                              PG_PREM_RW)) {
 101             return NULL;
 102         }
 103     }
 104
 105     void* old = heap->brk;
 106     heap->brk += size;
 107     return old;
 108 }
 109
 110 void*
 111 lx_grow_heap(heap_context_t* heap, size_t sz)
 112 {
 113     void* start;
 114
 115     if (!(start = lxbrk(heap, sz))) {
 116         return NULL;
 117     }
 118     sz = ROUNDUP(sz, BOUNDARY);
 119
 120     uint32_t old_marker = *((uint32_t*)start);
 121     uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 122     SW(start, free_hdr);
 123     SW(FPTR(start, sz), free_hdr);
 124     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 125
 126     return coalesce(start);
 127 }
 128
 129 void*
 130 lx_malloc(heap_context_t* heap, size_t size)
 131 {
 132     // Simplest first fit approach.
 133
 134     uint8_t* ptr = heap->start;
 135     // round to largest 4B aligned value
 136     //  and space for header
 137     size = ROUNDUP(size, BOUNDARY) + WSIZE;
 138     while (ptr < (uint8_t*)heap->brk) {
 139         uint32_t header = *((uint32_t*)ptr);
 140         size_t chunk_size = CHUNK_S(header);
 141         if (chunk_size >= size && !CHUNK_A(header)) {
 142             // found!
 143             place_chunk(ptr, size);
 144             return BPTR(ptr);
 145         }
 146         ptr += chunk_size;
 147     }
 148
 149     // if heap is full (seems to be!), then allocate more space (if it's
 150     // okay...)
 151     if ((ptr = lx_grow_heap(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
 161 place_chunk(uint8_t* ptr, size_t size)
 162 {
 163     uint32_t header = *((uint32_t*)ptr);
 164     size_t chunk_size = CHUNK_S(header);
 165     *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 166     uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 167     uint32_t diff = chunk_size - size;
 168     if (!diff) {
 169         // if the current free block is fully occupied
 170         uint32_t n_hdr = LW(n_hdrptr);
 171         // notify the next block about our avaliability
 172         SW(n_hdrptr, n_hdr & ~0x2);
 173     } else {
 174         // if there is remaining free space left
 175         uint32_t remainder_hdr = 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     size_t sz = CHUNK_S(hdr);
 193     uint8_t* next_hdr = chunk_ptr + sz;
 194
 195     // make sure the ptr we are 'bout to free makes sense
 196     //   the size trick comes from:
 197     //  https://sourceware.org/git/?p=glibc.git;a=blob;f=malloc/malloc.c;h=1a1ac1d8f05b6f9bf295d7fdd0f12c2e4650a33c;hb=HEAD#l4437
 198     assert_msg(((uintptr_t)ptr < (uintptr_t)(-sz)) && !((uintptr_t)ptr & ~0x3),
 199                "free(): invalid pointer");
 200     assert_msg(sz > WSIZE && (sz & ~0x3),
 201                "free(): invalid size");
 202
 203     SW(chunk_ptr, hdr & ~M_ALLOCATED);
 204     SW(FPTR(chunk_ptr, sz), hdr & ~M_ALLOCATED);
 205     SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
 206
 207     coalesce(chunk_ptr);
 208 }
 209
 210 void*
 211 coalesce(uint8_t* chunk_ptr)
 212 {
 213     uint32_t hdr = LW(chunk_ptr);
 214     uint32_t pf = CHUNK_PF(hdr);
 215     uint32_t sz = CHUNK_S(hdr);
 216
 217     uint32_t n_hdr = LW(chunk_ptr + sz);
 218
 219     if (CHUNK_A(n_hdr) && pf) {
 220         // case 1: prev is free
 221         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 222         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 223         uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 224         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 225         SW(FPTR(chunk_ptr, sz), new_hdr);
 226         chunk_ptr -= prev_chunk_sz;
 227     } else if (!CHUNK_A(n_hdr) && !pf) {
 228         // case 2: next is free
 229         size_t next_chunk_sz = CHUNK_S(n_hdr);
 230         uint32_t new_hdr = PACK(next_chunk_sz + sz, pf);
 231         SW(chunk_ptr, new_hdr);
 232         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 233     } else if (!CHUNK_A(n_hdr) && pf) {
 234         // case 3: both free
 235         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);
 236         size_t next_chunk_sz = CHUNK_S(n_hdr);
 237         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 238         uint32_t new_hdr =
 239           PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 240         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 241         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 242         chunk_ptr -= prev_chunk_sz;
 243     }
 244
 245     // case 4: prev and next are not free
 246     return chunk_ptr;
 247 }