+## 准备工作
+
+```sh
+git checkout 4c6d990440cdba6c7dd294adb7e435770ffcbcc4
+```
+
+观看对应视频
+
+这次内容比较少。
+
+## 代码分析
+
+### kernel/mm/dmm.c 一些宏
+
+堆的单位元素可以称为chunk。一个chunk包含头部空间和实际存储数据的空间。先看看下面几个宏定义。0b1表示当前chunk已分配，0b10表示前一个chunk未被分配。
+
+```c
+#define M_ALLOCATED 0x1
+#define M_PREV_FREE 0x2
+
+#define M_NOT_ALLOCATED 0x0
+#define M_PREV_ALLOCATED 0x0
+```
+
+chunk的头大小为4字节，如果把低三bit清零，那么它的值就表示chunk的大小。`CHUNK_S`就是这样。
+
+```c
+#define CHUNK_S(header) ((header) & ~0x3)
+```
+
+LW表示load one word（SW表示save one word）。NEXT_CHK可以获得一个指向下一个chunk头部的指针。
+
+```c
+#define LW(p) (*((uint32_t*)(p)))
+#define NEXT_CHK(hp) ((uint8_t*)(hp) + CHUNK_S(LW(hp)))
+```
+
+PACK方便我们构造一个chunk头。
+
+```c
+#define PACK(size,flags) (((size) & ~0x3) | (flags))
+```
+
+### 堆初始化
+
+堆的初始化函数`kalloc_init`被`_kernel_post_init`函数调用。
+
+```c
+void
+_kernel_post_init() {
+ printf("[KERNEL] === Post Initialization === \n");
+ size_t hhk_init_pg_count = ((uintptr_t)(&__init_hhk_end)) >> PG_SIZE_BITS;
+ printf("[MM] Releaseing %d pages from 0x0.\n", hhk_init_pg_count);
+
+ // 清除 hhk_init 与前1MiB的映射
+ for (size_t i = 0; i < hhk_init_pg_count; i++) {
+ vmm_unmap_page((void*)(i << PG_SIZE_BITS));
+ }
+
+ assert_msg(kalloc_init(), "Fail to initialize heap");
+}
+```
+
+下面结构体用于表示以分配的堆空间的范围。start表示起始地址，brk表示结束地址。
+
+```c
+typedef struct
+{
+ void* start;
+ void* brk;
+} heap_context_t;
+```
+
+初始化操作会设置start和brk，最后执行`dmm_init`。符号`__kernel_heap_start`由linker.ld提供。
+
+```c
+extern uint8_t __kernel_heap_start;
+heap_context_t __kalloc_kheap;
+int
+kalloc_init() {
+ __kalloc_kheap.start = &__kernel_heap_start;
+ __kalloc_kheap.brk = 0;
+
+ return dmm_init(&__kalloc_kheap);
+}
+```
+
+### kernel/mm/dmm.c 一些函数
+
+lxbrk用于增加堆大小。这里可以忽略分配大小、对齐等细节。重点在于它使用了`vmm_alloc_pages`分配新页给新增加的空间，并且更新了brk。
+
+```c
+void*
+lxbrk(heap_context_t* heap, size_t size)
+{
+ if (size == 0) {
+ return heap->brk;
+ }
+
+ // The upper bound of our next brk of heap given the size.
+ // This will be used to calculate the page we need to allocate.
+ // The "+ WSIZE" capture the overhead for epilogue marker
+ void* next = heap->brk + ROUNDUP(size + WSIZE, WSIZE);
+
+ if ((uintptr_t)next >= K_STACK_START) {
+ return NULL;
+ }
+
+ uintptr_t heap_top_pg = PG_ALIGN(heap->brk);
+ if (heap_top_pg != PG_ALIGN(next)) {
+ // if next do require new pages to be allocated
+ if (!vmm_alloc_pages((void*)(heap_top_pg + PG_SIZE),
+ ROUNDUP(size, PG_SIZE),
+ PG_PREM_RW)) {
+ return NULL;
+ }
+ }
+
+ void* old = heap->brk;
+ heap->brk += size;
+ return old;
+}
+```
+
+接下来看看**Dynamic memory manager**相关代码。
+
+```c
+int
+dmm_init(heap_context_t* heap)
+{
+ assert((uintptr_t)heap->start % BOUNDARY == 0);
+ heap->brk = heap->start;
+```
+
+给skb（start）分配一个可读可写的页
+
+```c
+ vmm_alloc_page(heap->brk, PG_PREM_RW);
+```
+
+按照视频所说的放两个chunk头部，理由见视频。读者也可以有不同设计。
+
+```c
+ SW(heap->start, PACK(4, M_ALLOCATED));
+ SW(heap->start + WSIZE, PACK(0, M_ALLOCATED));
+ heap->brk += WSIZE;
+
+ return lx_grow_heap(heap, HEAP_INIT_SIZE) != NULL;
+}
+```
+
+接着调用`lx_grow_heap`，sz大小是HEAP_INIT_SIZE。调用lxbrk来分配新页。
+
+```c
+void*
+lx_grow_heap(heap_context_t* heap, size_t sz)
+{
+ void* start;
+
+ if (!(start = lxbrk(heap, sz))) {
+ return NULL;
+ }
+ sz = ROUNDUP(sz, BOUNDARY);
+```
+
+构造chunk的头部和尾部，下一个chunk的头部。调用`coalesce`。
+
+```c
+ uint32_t old_marker = *((uint32_t*)start);
+ uint32_t free_hdr = PACK(sz, CHUNK_PF(old_marker));
+ SW(start, free_hdr);
+ SW(FPTR(start, sz), free_hdr);
+ SW(NEXT_CHK(start), PACK(0, M_ALLOCATED | M_PREV_FREE));
+
+ return coalesce(start);
+}
+```
+
+获得头部信息（hdr）、是否前一个chunk可使用（pf）、当前chunk大小（sz）、n_hdr（下一个头部信息）
+
+```c
+void*
+coalesce(uint8_t* chunk_ptr)
+{
+ uint32_t hdr = LW(chunk_ptr);
+ uint32_t pf = CHUNK_PF(hdr);
+ uint32_t sz = CHUNK_S(hdr);
+
+ uint32_t n_hdr = LW(chunk_ptr + sz);
+```
+
+如果前一个chunk可用，而且下一个chunk不可用（已被分配）那么合并前一个chunk。下面只分析一种情况，其他情况类似。
+
+```c
+ if (CHUNK_A(n_hdr) && pf) {
+ // case 1: prev is free
+ uint32_t prev_ftr = LW(chunk_ptr - WSIZE);//获得前一个chunk的尾部
+ size_t prev_chunk_sz = CHUNK_S(prev_ftr);//获得前一个chunk的大小
+ uint32_t new_hdr = PACK(prev_chunk_sz + sz, CHUNK_PF(prev_ftr));//构造新头部
+ SW(chunk_ptr - prev_chunk_sz, new_hdr);//修改前一个chunk头部
+ SW(FPTR(chunk_ptr, sz), new_hdr);//修改当前chunk的尾部
+ chunk_ptr -= prev_chunk_sz;//修改合并后chunk指针
+ //...
+ // case 4: prev and next are not free
+ return chunk_ptr;
+}
+```
+
+place_chunk用于从一个chunk中分配出一个小chunk。如果diff等于0，就表示刚好满足大小，设置下一个chunk头即可。另外一种情况就是，小chunk比原来chunk小，此时要分割原来的chunk，最后调用coalesce合并chunk。
+
+```c
+void
+place_chunk(uint8_t* ptr, size_t size)
+{
+ uint32_t header = *((uint32_t*)ptr);
+ size_t chunk_size = CHUNK_S(header);
+ *((uint32_t*)ptr) = PACK(size, CHUNK_PF(header) | M_ALLOCATED);
+ uint8_t* n_hdrptr = (uint8_t*)(ptr + size);
+ uint32_t diff = chunk_size - size;
+ if (!diff) {
+ // if the current free block is fully occupied
+ uint32_t n_hdr = LW(n_hdrptr);
+ // notify the next block about our avaliability
+ SW(n_hdrptr, n_hdr & ~0x2);
+ } else {
+ // if there is remaining free space left
+ uint32_t remainder_hdr = PACK(diff, M_NOT_ALLOCATED | M_PREV_ALLOCATED);
+ SW(n_hdrptr, remainder_hdr);
+ SW(FPTR(n_hdrptr, diff), remainder_hdr);
+
+ coalesce(n_hdrptr);
+ }
+}
+```
+
+最后看看`lx_malloc`函数，先是使用一个循环来遍历堆，查看是否有可用的chunk。如果存在，则调用`place_chunk`，最后返回`BPTR(ptr)`指向chunk头部后面真正的数据储存地址。
+
+```c
+void*
+lx_malloc(heap_context_t* heap, size_t size)
+{
+ // Simplest first fit approach.
+
+ uint8_t* ptr = heap->start;
+ // round to largest 4B aligned value
+ // and space for header
+ size = ROUNDUP(size, BOUNDARY) + WSIZE;
+ while (ptr < (uint8_t*)heap->brk) {
+ uint32_t header = *((uint32_t*)ptr);
+ size_t chunk_size = CHUNK_S(header);
+ if (chunk_size >= size && !CHUNK_A(header)) {
+ // found!
+ place_chunk(ptr, size);
+ return BPTR(ptr);
+ }
+ ptr += chunk_size;
+ }
+```
+
+如果没有找到就扩大堆空间。
+
+```c
+ // if heap is full (seems to be!), then allocate more space (if it's
+ // okay...)
+ if ((ptr = lx_grow_heap(heap, size))) {
+ place_chunk(ptr, size);
+ return BPTR(ptr);
+ }
+
+ // Well, we are officially OOM!
+ return NULL;
+}
+```
+
+其他函数略
git://scm.lunaixsky.com / lunaix-os.git / commitdiff