docs/tutorial/5-malloc.md

   1 ## 准备工作
   2
   3 ```sh
   4 git checkout 4c6d990440cdba6c7dd294adb7e435770ffcbcc4
   5 ```
   6
   7 观看对应视频
   8
   9 这次内容比较少。
  10
  11 ## 代码分析
  12
  13 ### kernel/mm/dmm.c 一些宏
  14
  15 堆的单位元素可以称为chunk。一个chunk包含头部空间和实际存储数据的空间。先看看下面几个宏定义。0b1表示当前chunk已分配，0b10表示前一个chunk未被分配。
  16
  17 ```c
  18 #define M_ALLOCATED 0x1
  19 #define M_PREV_FREE 0x2
  20
  21 #define M_NOT_ALLOCATED 0x0
  22 #define M_PREV_ALLOCATED 0x0
  23 ```
  24
  25 chunk的头大小为4字节，如果把低三bit清零，那么它的值就表示chunk的大小。`CHUNK_S`就是这样。
  26
  27 ```c
  28 #define CHUNK_S(header) ((header) & ~0x3)
  29 ```
  30
  31 LW表示load one word（SW表示save one word）。NEXT_CHK可以获得一个指向下一个chunk头部的指针。
  32
  33 ```c
  34 #define LW(p) (*((uint32_t*)(p)))
  35 #define NEXT_CHK(hp) ((uint8_t*)(hp) + CHUNK_S(LW(hp)))
  36 ```
  37
  38 PACK方便我们构造一个chunk头。
  39
  40 ```c
  41 #define PACK(size,flags) (((size) & ~0x3) | (flags))
  42 ```
  43
  44 ### 堆初始化
  45
  46 堆的初始化函数`kalloc_init`被`_kernel_post_init`函数调用。
  47
  48 ```c
  49 void
  50 _kernel_post_init() {
  51     printf("[KERNEL] === Post Initialization === \n");
  52     size_t hhk_init_pg_count = ((uintptr_t)(&__init_hhk_end)) >> PG_SIZE_BITS;
  53     printf("[MM] Releaseing %d pages from 0x0.\n", hhk_init_pg_count);
  54
  55     // 清除 hhk_init 与前1MiB的映射
  56     for (size_t i = 0; i < hhk_init_pg_count; i++) {
  57         vmm_unmap_page((void*)(i << PG_SIZE_BITS));
  58     }
  59
  60     assert_msg(kalloc_init(), "Fail to initialize heap");
  61 }
  62 ```
  63
  64 下面结构体用于表示以分配的堆空间的范围。start表示起始地址，brk表示结束地址。
  65
  66 ```c
  67 typedef struct
  68 {
  69     void* start;
  70     void* brk;
  71 } heap_context_t;
  72 ```
  73
  74 初始化操作会设置start和brk，最后执行`dmm_init`。符号`__kernel_heap_start`由linker.ld提供。
  75
  76 ```c
  77 extern uint8_t __kernel_heap_start;
  78 heap_context_t __kalloc_kheap;
  79 int
  80 kalloc_init() {
  81     __kalloc_kheap.start = &__kernel_heap_start;
  82     __kalloc_kheap.brk = 0;
  83
  84     return dmm_init(&__kalloc_kheap);
  85 }
  86 ```
  87
  88 ### kernel/mm/dmm.c 一些函数
  89
  90 lxbrk用于增加堆大小。这里可以忽略分配大小、对齐等细节。重点在于它使用了`vmm_alloc_pages`分配新页给新增加的空间，并且更新了brk。
  91
  92 ```c
  93 void*
  94 lxbrk(heap_context_t* heap, size_t size)
  95 {
  96     if (size == 0) {
  97         return heap->brk;
  98     }
  99
 100     // The upper bound of our next brk of heap given the size.
 101     // This will be used to calculate the page we need to allocate.
 102     // The "+ WSIZE" capture the overhead for epilogue marker
 103     void* next = heap->brk + ROUNDUP(size + WSIZE, WSIZE);
 104
 105     if ((uintptr_t)next >= K_STACK_START) {
 106         return NULL;
 107     }
 108
 109     uintptr_t heap_top_pg = PG_ALIGN(heap->brk);
 110     if (heap_top_pg != PG_ALIGN(next)) {
 111         // if next do require new pages to be allocated
 112         if (!vmm_alloc_pages((void*)(heap_top_pg + PG_SIZE),
 113                              ROUNDUP(size, PG_SIZE),
 114                              PG_PREM_RW)) {
 115             return NULL;
 116         }
 117     }
 118
 119     void* old = heap->brk;
 120     heap->brk += size;
 121     return old;
 122 }
 123 ```
 124
 125 接下来看看**Dynamic memory manager**相关代码。
 126
 127 ```c
 128 int
 129 dmm_init(heap_context_t* heap)
 130 {
 131     assert((uintptr_t)heap->start % BOUNDARY == 0);
 132     heap->brk = heap->start;
 133 ```
 134
 135 给skb（start）分配一个可读可写的页
 136
 137 ```c
 138     vmm_alloc_page(heap->brk, PG_PREM_RW);
 139 ```
 140
 141 按照视频所说的放两个chunk头部，理由见视频。读者也可以有不同设计。
 142
 143 ```c
 144     SW(heap->start, PACK(4, M_ALLOCATED));
 145     SW(heap->start + WSIZE, PACK(0, M_ALLOCATED));
 146     heap->brk += WSIZE;
 147
 148     return lx_grow_heap(heap, HEAP_INIT_SIZE) != NULL;
 149 }
 150 ```
 151
 152 接着调用`lx_grow_heap`，sz大小是HEAP_INIT_SIZE。调用lxbrk来分配新页。
 153
 154 ```c
 155 void*
 156 lx_grow_heap(heap_context_t* heap, size_t sz)
 157 {
 158     void* start;
 159
 160     if (!(start = lxbrk(heap, sz))) {
 161         return NULL;
 162     }
 163     sz = ROUNDUP(sz, BOUNDARY);
 164 ```
 165
 166 构造chunk的头部和尾部，下一个chunk的头部。调用`coalesce`。
 167
 168 ```c
 169     uint32_t old_marker = *((uint32_t*)start);
 170     uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
 171     SW(start, free_hdr);
 172     SW(FPTR(start, sz), free_hdr);
 173     SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
 174
 175     return coalesce(start);
 176 }
 177 ```
 178
 179 获得头部信息（hdr）、是否前一个chunk可使用（pf）、当前chunk大小（sz）、n_hdr（下一个头部信息）
 180
 181 ```c
 182 void*
 183 coalesce(uint8_t* chunk_ptr)
 184 {
 185     uint32_t hdr = LW(chunk_ptr);
 186     uint32_t pf = CHUNK_PF(hdr);
 187     uint32_t sz = CHUNK_S(hdr);
 188
 189     uint32_t n_hdr = LW(chunk_ptr + sz);
 190 ```
 191
 192 如果前一个chunk可用，而且下一个chunk不可用（已被分配）那么合并前一个chunk。下面只分析一种情况，其他情况类似。
 193
 194 ```c
 195         if (CHUNK_A(n_hdr) && pf) {
 196         // case 1: prev is free
 197         uint32_t prev_ftr = LW(chunk_ptr - WSIZE);//获得前一个chunk的尾部
 198         size_t prev_chunk_sz = CHUNK_S(prev_ftr);//获得前一个chunk的大小
 199         uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));//构造新头部
 200         SW(chunk_ptr - prev_chunk_sz, new_hdr);//修改前一个chunk头部
 201         SW(FPTR(chunk_ptr, sz), new_hdr);//修改当前chunk的尾部
 202         chunk_ptr -= prev_chunk_sz;//修改合并后chunk指针
 203     //...
 204     // case 4: prev and next are not free
 205     return chunk_ptr;
 206 }
 207 ```
 208
 209 place_chunk用于从一个chunk中分配出一个小chunk。如果diff等于0，就表示刚好满足大小，设置下一个chunk头即可。另外一种情况就是，小chunk比原来chunk小，此时要分割原来的chunk，最后调用coalesce合并chunk。
 210
 211 ```c
 212 void
 213 place_chunk(uint8_t* ptr, size_t size)
 214 {
 215     uint32_t header = *((uint32_t*)ptr);
 216     size_t chunk_size = CHUNK_S(header);
 217     *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
 218     uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
 219     uint32_t diff = chunk_size - size;
 220     if (!diff) {
 221         // if the current free block is fully occupied
 222         uint32_t n_hdr = LW(n_hdrptr);
 223         // notify the next block about our avaliability
 224         SW(n_hdrptr, n_hdr & ~0x2);
 225     } else {
 226         // if there is remaining free space left
 227         uint32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
 228         SW(n_hdrptr, remainder_hdr);
 229         SW(FPTR(n_hdrptr, diff), remainder_hdr);
 230
 231         coalesce(n_hdrptr);
 232     }
 233 }
 234 ```
 235
 236 最后看看`lx_malloc`函数，先是使用一个循环来遍历堆，查看是否有可用的chunk。如果存在，则调用`place_chunk`，最后返回`BPTR(ptr)`指向chunk头部后面真正的数据储存地址。
 237
 238 ```c
 239 void*
 240 lx_malloc(heap_context_t* heap, size_t size)
 241 {
 242     // Simplest first fit approach.
 243
 244     uint8_t* ptr = heap->start;
 245     // round to largest 4B aligned value
 246     //  and space for header
 247     size = ROUNDUP(size, BOUNDARY) + WSIZE;
 248     while (ptr < (uint8_t*)heap->brk) {
 249         uint32_t header = *((uint32_t*)ptr);
 250         size_t chunk_size = CHUNK_S(header);
 251         if (chunk_size >= size && !CHUNK_A(header)) {
 252             // found!
 253             place_chunk(ptr, size);
 254             return BPTR(ptr);
 255         }
 256         ptr += chunk_size;
 257     }
 258 ```
 259
 260 如果没有找到就扩大堆空间。
 261
 262 ```c
 263     // if heap is full (seems to be!), then allocate more space (if it's
 264     // okay...)
 265     if ((ptr = lx_grow_heap(heap, size))) {
 266         place_chunk(ptr, size);
 267         return BPTR(ptr);
 268     }
 269
 270     // Well, we are officially OOM!
 271     return NULL;
 272 }
 273 ```
 274
 275 其他函数略