PMM 负责整页分配，每次给你 4KB。但内核里经常需要分配几十、几百字节的小块——存一个结构体、一条字符串。每次都要一整页，太浪费。

这一章实现 kmalloc / kfree：按需分配任意大小的内存块，用完归还，可以复用。

设计：空闲链表

最经典的堆实现：空闲链表（Free List）。

在堆空间里，每块内存前面加一个块头（header）记录元数据，所有块串成双向链表：

typedef struct block {
    uint64_t      size;     // 这块数据区的大小（不含 header 本身）
    uint8_t       is_free;  // 1=空闲，0=已分配
    struct block *next;     // 链表后继
    struct block *prev;     // 链表前驱
} block_t;

内存布局长这样：

[block_t header | ← size → 数据区 ][block_t header | ← size → 数据区 ] ...
 ↑                                   ↑
 kmalloc 返回这个指针之前的地址        下一块 header

kmalloc 返回的指针指向数据区起始，而不是 header。kfree 时把指针往前偏移 sizeof(block_t)，找回 header，再改 is_free = 1。

堆在哪里

堆从虚拟地址 0x30000 开始，链表头指针存在 0x29000（一个固定位置，方便任何地方都能找到它）：

#define HEAP_START      0x30000ULL
#define HEAP_HEAD_ADDR  0x29000ULL
#define heap_head  (*(block_t **)HEAP_HEAD_ADDR)

初始化时预先映射 4 页（16KB）作为起始堆空间，不够了再动态扩展。

heap_extend：扩展堆

当现有空间不够分配时，向 PMM 申请新的物理页，通过 VMM 映射到堆的末尾：

static block_t *heap_extend(uint64_t n_pages) {
    // 找到当前堆的末尾虚拟地址
    uint64_t vaddr = HEAP_START;
    if (heap_head) {
        block_t *cur = heap_head;
        while (cur->next) cur = cur->next;
        vaddr = (uint64_t)cur + BLOCK_HDR_SIZE + cur->size;
    }

    // 映射新页（0x200000 以下 bootloader 已经映射好了，跳过）
    for (uint64_t i = 0; i < n_pages; i++) {
        uint64_t page_vaddr = vaddr + i * 0x1000;
        if (page_vaddr >= 0x200000ULL) {
            void *phys = pmm_alloc();
            map_page(page_vaddr, (uint64_t)phys, PAGE_KERNEL);
        }
    }

    // 在这段新空间的开头放一个大的空闲块
    block_t *blk = (block_t *)vaddr;
    blk->size    = n_pages * 0x1000 - BLOCK_HDR_SIZE;
    blk->is_free = 1;
    blk->next    = 0;
    blk->prev    = 0;

    // 接到链表末尾
    if (!heap_head) {
        heap_head = blk;
    } else {
        block_t *cur = heap_head;
        while (cur->next) cur = cur->next;
        cur->next = blk;
        blk->prev = cur;
    }
    return blk;
}

kmalloc：分配

First Fit（首次适应）：从链表头开始扫，找到第一个够大的空闲块就用。

void *kmalloc(uint64_t size) {
    if (size == 0) return 0;
    size = (size + 7) & ~7ULL;   // 8 字节对齐

    block_t *cur = heap_head;
    while (cur) {
        if (cur->is_free && cur->size >= size)
            return alloc_from(cur, size);
        cur = cur->next;
    }

    // 没有合适的块，扩展堆
    block_t *newblk = heap_extend(HEAP_INIT_PAGES);
    if (newblk && newblk->size >= size)
        return alloc_from(newblk, size);
    return 0;  // OOM
}

找到块之后，alloc_from 做切割：如果剩余空间足够再放一个 header + 至少 8 字节数据，就把块一分为二，后半截留作新的空闲块，避免浪费：

static void *alloc_from(block_t *blk, uint64_t size) {
    // 剩余空间够切出新块才分裂
    if (blk->size >= size + BLOCK_HDR_SIZE + 8) {
        block_t *newblk = (block_t *)((uint64_t)blk + BLOCK_HDR_SIZE + size);
        newblk->size    = blk->size - size - BLOCK_HDR_SIZE;
        newblk->is_free = 1;
        newblk->next    = blk->next;
        newblk->prev    = blk;
        if (blk->next) blk->next->prev = newblk;
        blk->next = newblk;
        blk->size = size;
    }
    blk->is_free = 0;
    return (void *)((uint64_t)blk + BLOCK_HDR_SIZE);
}

kfree：释放 + 合并

释放很简单，把 is_free 置 1 就行——但还有一个关键步骤：合并相邻空闲块。

如果不合并，反复 malloc/free 之后，堆里会全是零碎的小块，即使总空闲量很大，也分配不出一块大的——这叫外部碎片（External Fragmentation）。

void kfree(void *ptr) {
    if (!ptr) return;
    block_t *blk = (block_t *)((uint64_t)ptr - BLOCK_HDR_SIZE);
    blk->is_free = 1;

    // 向后合并：如果下一块也是空闲的，吸收它
    if (blk->next && blk->next->is_free) {
        blk->size += BLOCK_HDR_SIZE + blk->next->size;
        blk->next  = blk->next->next;
        if (blk->next) blk->next->prev = blk;
    }

    // 向前合并：如果上一块也是空闲的，被它吸收
    if (blk->prev && blk->prev->is_free) {
        blk->prev->size += BLOCK_HDR_SIZE + blk->size;
        blk->prev->next  = blk->next;
        if (blk->next) blk->next->prev = blk->prev;
    }
}

合并之后，两块（或三块）空闲内存变成一块大的，下次分配大块时就能用上。

验证

void *a = kmalloc(64);    // 分配 64 字节
void *b = kmalloc(128);   // 分配 128 字节
kfree(a);                  // 释放 a
void *c = kmalloc(32);    // 再分配 32 字节

输出：

kmalloc(64)=0x0000000000030020
kmalloc(128)=0x0000000000030078
after kfree(a), kmalloc(32)=0x0000000000030020
  • a 在 0x30020（0x30000 + 32字节 header）
  • b 在 0x30078（0x30020 + 64字节数据 + 32字节 header = 0x30078，8字节对齐后）
  • 释放 a 后，c 拿到了 0x30020——原来 a 的位置，说明空闲块被复用了

用 heap_dump() 看此刻链表状态：

Heap dump:
  [0] addr=0x0000000000030000 size=0x0000000000000020 USED  ← c 占着（32字节）
  [1] addr=0x0000000000030040 size=0x0000000000000018 FREE  ← a 剩下的碎片
  [2] addr=0x0000000000030070 size=0x0000000000000080 USED  ← b
  [3] addr=0x0000000000030108 size=0x0000000000003EE8 FREE  ← 剩余大块

踩过的一个坑

第一版 kfree 写完发现一个 bug：向后合并时，忘了更新 blk->next->prev。合并完后，后续块的 prev 还指着已经消失的那个 header，下次再 free 它、触发向前合并，prev->size 就乱掉了，堆损坏。

双向链表操作，指针一旦漏改就是定时炸弹——heap_dump() 在这里救了命，直接把链表打出来逐行对，很快就找到了。

这一章之后

现在内核有了完整的内存基础设施：PMM 管物理页，VMM 做地址映射，堆分配器处理小块动态内存。

下一章上进程：每个进程有自己的页表、自己的栈，CPU 在它们之间来回切换——多任务操作系统最核心的部分。

源码在这里：github.com/tongpengfei/learn-with-ai