lunaix-os/kernel/mm/kalloc.c

   1
   2 /**** DO NOT USE ****/
   3
   4 /**
   5  * @file kalloc.c
   6  * @author Lunaixsky
   7  * @brief Implicit free list implementation of malloc family, for kernel use.
   8  *
   9  * This version of code is however the simplest and yet insecured, thread unsafe
  10  * it just to demonstrate how the malloc/free works behind the curtain
  11  * @version 0.1
  12  * @date 2022-03-05
  13  *
  14  * @copyright Copyright (c) 2022
  15  *
  16  */
  17 // #include <lunaix/mm/dmm.h>
  18 // #include <lunaix/mm/kalloc.h>
  19 // #include <lunaix/mm/vmm.h>
  20
  21 // #include <lunaix/common.h>
  22 // #include <lunaix/spike.h>
  23
  24 // #include <klibc/string.h>
  25
  26 // #include <stdint.h>
  27
  28 // extern uint8_t __kernel_heap_start;
  29
  30 // void*
  31 // lx_malloc_internal(heap_context_t* heap, size_t size);
  32
  33 // void
  34 // place_chunk(uint8_t* ptr, size_t size);
  35
  36 // void
  37 // lx_free_internal(void* ptr);
  38
  39 // void*
  40 // coalesce(uint8_t* chunk_ptr);
  41
  42 // void*
  43 // lx_grow_heap(heap_context_t* heap, size_t sz);
  44
  45 // /*
  46 //     At the beginning, we allocate an empty page and put our initial marker
  47
  48 //     | 4/1 | 0/1 |
  49 //     ^     ^ brk
  50 //     start
  51
  52 //     Then, expand the heap further, with HEAP_INIT_SIZE (evaluated to 4096,
  53 //     i.e.,
  54 //    1 pg size) This will allocate as much pages and override old epilogue
  55 //    marker with a free region hdr and put new epilogue marker. These are
  56 //    handled by lx_grow_heap which is internally used by alloc to expand the
  57 //    heap at many moment when needed.
  58
  59 //     | 4/1 | 4096/0 |   .......   | 4096/0 | 0/1 |
  60 //     ^     ^ brk_old                       ^
  61 //     start                                 brk
  62
  63 //     Note: the brk always point to the beginning of epilogue.
  64 // */
  65
  66 // static heap_context_t kheap;
  67
  68 // int
  69 // kalloc_init()
  70 // {
  71 //     kheap.start = KHEAP_START;
  72 //     kheap.brk = NULL;
  73 //     kheap.max_addr =
  74 //       (void*)PROC_START; // 在新的布局中，堆结束的地方即为进程表开始的地方
  75
  76 //     for (size_t i = 0; i < KHEAP_SIZE_MB >> 2; i++) {
  77 //         vmm_set_mapping(PD_REFERENCED,
  78 //                         (uintptr_t)kheap.start + (i << 22),
  79 //                         0,
  80 //                         PG_PREM_RW,
  81 //                         VMAP_NOMAP);
  82 //     }
  83
  84 //     if (!dmm_init(&kheap)) {
  85 //         return 0;
  86 //     }
  87
  88 //     SW(kheap.start, PACK(4, M_ALLOCATED));
  89 //     SW(kheap.start + WSIZE, PACK(0, M_ALLOCATED));
  90 //     kheap.brk += WSIZE;
  91
  92 //     return lx_grow_heap(&kheap, HEAP_INIT_SIZE) != NULL;
  93 // }
  94
  95 // void*
  96 // lxmalloc(size_t size)
  97 // {
  98 //     mutex_lock(&kheap.lock);
  99 //     void* r = lx_malloc_internal(&kheap, size);
 100 //     mutex_unlock(&kheap.lock);
 101
 102 //     return r;
 103 // }
 104
 105 // void*
 106 // lxcalloc(size_t n, size_t elem)
 107 // {
 108 //     size_t pd = n * elem;
 109
 110 //     // overflow detection
 111 //     if (pd < elem || pd < n) {
 112 //         return NULL;
 113 //     }
 114
 115 //     void* ptr = lxmalloc(pd);
 116 //     if (!ptr) {
 117 //         return NULL;
 118 //     }
 119
 120 //     return memset(ptr, 0, pd);
 121 // }
 122
 123 // void
 124 // lxfree(void* ptr)
 125 // {
 126 //     if (!ptr) {
 127 //         return;
 128 //     }
 129 //     mutex_lock(&kheap.lock);
 130
 131 //     uint8_t* chunk_ptr = (uint8_t*)ptr - WSIZE;
 132 //     u32_t hdr = LW(chunk_ptr);
 133 //     size_t sz = CHUNK_S(hdr);
 134 //     uint8_t* next_hdr = chunk_ptr + sz;
 135
 136 //     // make sure the ptr we are 'bout to free makes sense
 137 //     //   the size trick is stolen from glibc's malloc/malloc.c:4437 ;P
 138
 139 //     assert_msg(((uintptr_t)ptr < (uintptr_t)(-sz)) && !((uintptr_t)ptr &
 140 //     0x3),
 141 //                "free(): invalid pointer");
 142
 143 //     assert_msg(sz > WSIZE, "free(): invalid size");
 144
 145 //     SW(chunk_ptr, hdr & ~M_ALLOCATED);
 146 //     SW(FPTR(chunk_ptr, sz), hdr & ~M_ALLOCATED);
 147 //     SW(next_hdr, LW(next_hdr) | M_PREV_FREE);
 148
 149 //     coalesce(chunk_ptr);
 150
 151 //     mutex_unlock(&kheap.lock);
 152 // }
 153
 154 // void*
 155 // lx_malloc_internal(heap_context_t* heap, size_t size)
 156 // {
 157 //     // Simplest first fit approach.
 158
 159 //     if (!size) {
 160 //         return NULL;
 161 //     }
 162
 163 //     uint8_t* ptr = heap->start;
 164 //     // round to largest 4B aligned value
 165 //     //  and space for header
 166 //     size = ROUNDUP(size + WSIZE, BOUNDARY);
 167 //     while (ptr < (uint8_t*)heap->brk) {
 168 //         u32_t header = *((u32_t*)ptr);
 169 //         size_t chunk_size = CHUNK_S(header);
 170 //         if (!chunk_size && CHUNK_A(header)) {
 171 //             break;
 172 //         }
 173 //         if (chunk_size >= size && !CHUNK_A(header)) {
 174 //             // found!
 175 //             place_chunk(ptr, size);
 176 //             return BPTR(ptr);
 177 //         }
 178 //         ptr += chunk_size;
 179 //     }
 180
 181 //     // if heap is full (seems to be!), then allocate more space (if it's
 182 //     // okay...)
 183 //     if ((ptr = lx_grow_heap(heap, size))) {
 184 //         place_chunk(ptr, size);
 185 //         return BPTR(ptr);
 186 //     }
 187
 188 //     // Well, we are officially OOM!
 189 //     return NULL;
 190 // }
 191
 192 // void
 193 // place_chunk(uint8_t* ptr, size_t size)
 194 // {
 195 //     u32_t header = *((u32_t*)ptr);
 196 //     size_t chunk_size = CHUNK_S(header);
 197 //     *((u32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 198 //     uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 199 //     u32_t diff = chunk_size - size;
 200
 201 //     if (!diff) {
 202 //         // if the current free block is fully occupied
 203 //         u32_t n_hdr = LW(n_hdrptr);
 204 //         // notify the next block about our avaliability
 205 //         SW(n_hdrptr, n_hdr & ~0x2);
 206 //     } else {
 207 //         // if there is remaining free space left
 208 //         u32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED |
 209 //         M_PREV_ALLOCATED); SW(n_hdrptr, remainder_hdr); SW(FPTR(n_hdrptr,
 210 //         diff), remainder_hdr);
 211
 212 //         /*
 213 //             | xxxx |      |         |
 214
 215 //                         |
 216 //                         v
 217
 218 //             | xxxx |                |
 219 //         */
 220 //         coalesce(n_hdrptr);
 221 //     }
 222 // }
 223
 224 // void*
 225 // coalesce(uint8_t* chunk_ptr)
 226 // {
 227 //     u32_t hdr = LW(chunk_ptr);
 228 //     u32_t pf = CHUNK_PF(hdr);
 229 //     u32_t sz = CHUNK_S(hdr);
 230
 231 //     u32_t n_hdr = LW(chunk_ptr + sz);
 232
 233 //     if (CHUNK_A(n_hdr) && pf) {
 234 //         // case 1: prev is free
 235 //         u32_t prev_ftr = LW(chunk_ptr - WSIZE);
 236 //         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 237 //         u32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 238 //         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 239 //         SW(FPTR(chunk_ptr, sz), new_hdr);
 240 //         chunk_ptr -= prev_chunk_sz;
 241 //     } else if (!CHUNK_A(n_hdr) && !pf) {
 242 //         // case 2: next is free
 243 //         size_t next_chunk_sz = CHUNK_S(n_hdr);
 244 //         u32_t new_hdr = PACK(next_chunk_sz + sz, pf);
 245 //         SW(chunk_ptr, new_hdr);
 246 //         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 247 //     } else if (!CHUNK_A(n_hdr) && pf) {
 248 //         // case 3: both free
 249 //         u32_t prev_ftr = LW(chunk_ptr - WSIZE);
 250 //         size_t next_chunk_sz = CHUNK_S(n_hdr);
 251 //         size_t prev_chunk_sz = CHUNK_S(prev_ftr);
 252 //         u32_t new_hdr =
 253 //           PACK(next_chunk_sz + prev_chunk_sz + sz, CHUNK_PF(prev_ftr));
 254 //         SW(chunk_ptr - prev_chunk_sz, new_hdr);
 255 //         SW(FPTR(chunk_ptr, sz + next_chunk_sz), new_hdr);
 256 //         chunk_ptr -= prev_chunk_sz;
 257 //     }
 258
 259 //     // (fall through) case 4: prev and next are not free
 260 //     return chunk_ptr;
 261 // }
 262
 263 // void*
 264 // lx_grow_heap(heap_context_t* heap, size_t sz)
 265 // {
 266 //     void* start;
 267
 268 //     // The "+ WSIZE" capture the overhead for epilogue marker
 269 //     if (!(start = lxsbrk(heap, sz + WSIZE, 0))) {
 270 //         return NULL;
 271 //     }
 272 //     sz = ROUNDUP(sz, BOUNDARY);
 273
 274 //     // minus the overhead for epilogue, keep the invariant.
 275 //     heap->brk -= WSIZE;
 276
 277 //     u32_t old_marker = *((u32_t*)start);
 278 //     u32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 279 //     SW(start, free_hdr);
 280 //     SW(FPTR(start, sz), free_hdr);
 281 //     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 282
 283 //     return coalesce(start);
 284 // }