从零写 OS 内核-第十四篇：内存管理 —— 从页表到 malloc

“内存是操作系统的血液，管理它，就是管理生命本身。
今天，我们构建完整的内存管理体系：进程页表、物理页分配、用户态 malloc！”

在前面的篇章中，我们实现了分页、多进程、文件系统，但内存管理仍很原始：
- 物理页分配靠简单链表
- 用户程序无法动态申请内存（没有 malloc）
- 进程页表无法动态扩展

真正的操作系统，必须能高效管理物理内存，并为用户程序提供虚拟内存服务。

今天，我们就来实现：
✅ 每个进程独立的页表管理
✅ Buddy 系统分配物理页
✅ 用户态内存分配器（malloc/free），底层通过 mmap 系统调用

让你的用户程序能像在 Linux 中一样自由使用 malloc！

---

1 🧱 一、内存管理全景图

现代操作系统内存管理分为三层：

层级	职责	本篇实现
物理层	管理物理内存页（4KB）	✅ Buddy 分配器
虚拟层	管理进程虚拟地址空间	✅ 页表动态映射
用户层	提供 malloc/free	✅ 用户态分配器 + mmap

💡 核心思想：物理内存 → 虚拟地址 → 用户指针

---

2 📦 二、Buddy 分配器：高效管理物理页

Buddy 系统将内存划分为 2^n 页大小的块，支持快速分配/合并，减少碎片。

2.1 设计：

• 位图（Bitmap）：跟踪每个块是否空闲
• 空闲链表数组：free_list[0..10]，free_list[i] 存放 2^i 页大小的块

2.2 关键操作：

1. 初始化

#define MAX_ORDER 10  // 最大 2^10 = 1024 页 = 4MB
struct list_head free_list[MAX_ORDER];
uint8_t *buddy_bitmap;

void buddy_init(uint32_t start_addr, uint32_t end_addr) {
    uint32_t total_pages = (end_addr - start_addr) / PAGE_SIZE;
    buddy_bitmap = (uint8_t*)kmalloc(BITS_TO_BYTES(total_pages));
    // 将整个内存区域加入 free_list[MAX_ORDER]
    buddy_add_to_free_list(start_addr, MAX_ORDER);
}

2. 分配（buddy_alloc）

void *buddy_alloc(int order) {
    // 1. 从 free_list[order] 取块
    if (!list_empty(&free_list[order])) {
        return remove_from_list(&free_list[order]);
    }
    // 2. 向上找更大块
    for (int i = order + 1; i <= MAX_ORDER; i++) {
        if (!list_empty(&free_list[i])) {
            void *block = remove_from_list(&free_list[i]);
            // 3. 分割：将大块拆成两个 buddy
            buddy_split(block, i, order);
            return block;
        }
    }
    return NULL; // 内存不足
}

3. 释放（buddy_free）

void buddy_free(void *addr, int order) {
    // 1. 标记为 free
    mark_free(addr, order);
    // 2. 尝试合并 buddy
    void *buddy = get_buddy(addr, order);
    if (is_free(buddy, order)) {
        buddy_free(merge(addr, buddy), order + 1);
    } else {
        add_to_free_list(addr, order);
    }
}

✅ Buddy 系统保证：分配 N 页，最多浪费 N 页（内部碎片）

---

3 🗺️ 三、进程页表管理：动态映射虚拟地址

每个进程需要独立的页目录（Page Directory），并支持按需映射。

1. 页表操作 API

// 映射虚拟地址到物理页
int map_page(uint32_t *pgdir, uint32_t vaddr, uint32_t paddr, uint32_t flags);

// 分配新页表（如果需要）
uint32_t *get_page_table(uint32_t *pgdir, uint32_t vaddr, bool create);

// 取消映射
void unmap_page(uint32_t *pgdir, uint32_t vaddr);

2. 按需分配（Demand Paging）

当用户访问未映射的虚拟地址： - 触发 Page Fault（#PF） - 内核分配物理页，映射到该地址 - 恢复执行

void page_fault_handler(registers_t *regs) {
    uint32_t fault_addr;
    asm("mov %%cr2, %0" : "=r"(fault_addr));

    if (is_user_address(fault_addr)) {
        // 分配物理页
        void *page = buddy_alloc(0);
        if (page) {
            // 映射到当前进程页目录
            map_page(current_task->cr3, fault_addr & ~0xFFF, 
                     (uint32_t)page, PAGE_PRESENT | PAGE_RW | PAGE_USER);
            return;
        }
    }
    // 否则：段错误（SIGSEGV）
    kill_process(current_task, SIGSEGV);
}

🔑 Page Fault 是虚拟内存的基石！

---

4 📞 四、系统调用：mmap 与 brk

用户程序通过系统调用申请内存：

1. brk 系统调用（传统）

• 调整 堆顶指针（program break）
• 用于 malloc 小内存

// sys_brk: 设置新的堆顶
void *sys_brk(void *new_brk) {
    if (!new_brk) return current_task->heap_start;

    uint32_t old_heap = current_task->heap_top;
    uint32_t new_heap = (uint32_t)new_brk;

    if (new_heap > old_heap) {
        // 映射新页面（按需）
        uint32_t vaddr = old_heap & ~0xFFF;
        while (vaddr < new_heap) {
            map_page(current_task->cr3, vaddr, 0, 
                     PAGE_PRESENT | PAGE_RW | PAGE_USER);
            vaddr += PAGE_SIZE;
        }
    }
    current_task->heap_top = new_heap;
    return (void*)new_heap;
}

2. mmap 系统调用（现代）

• 映射任意虚拟地址范围
• 可映射文件、设备、匿名内存

void *sys_mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset) {
    // 1. 找到未使用的虚拟地址范围
    uint32_t vaddr = find_free_vma(length);

    // 2. 分配物理页（匿名映射）
    if (flags & MAP_ANONYMOUS) {
        for (size_t i = 0; i < length; i += PAGE_SIZE) {
            void *page = buddy_alloc(0);
            map_page(current_task->cr3, vaddr + i, (uint32_t)page, 
                     PAGE_PRESENT | PAGE_RW | PAGE_USER);
        }
    }
    // 3. （文件映射暂不实现）
    return (void*)vaddr;
}

💡 malloc 底层：小内存用 brk，大内存用 mmap

---

5 🧵 五、用户态内存分配器（malloc/free）

现在，我们可以在用户空间实现 malloc！

1. 用户态 libc 封装

// user_malloc.c
extern void *brk(void *addr);
extern void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);

void *malloc(size_t size) {
    if (size == 0) return NULL;

    if (size < 128 * 1024) {
        // 小内存：用 brk 扩展堆
        static char *heap_start = NULL;
        static char *heap_end = NULL;

        if (!heap_start) {
            heap_start = brk(NULL);
            heap_end = heap_start;
        }

        char *new_end = heap_end + size;
        brk(new_end);
        heap_end = new_end;
        return new_end - size;
    } else {
        // 大内存：用 mmap
        return mmap(NULL, size, PROT_READ | PROT_WRITE, 
                    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    }
}

void free(void *ptr) {
    // 简化版：不回收小内存（实际需空闲链表）
    // 大内存：munmap
    // ... 
}

2. 链接用户程序

# 用户程序编译
user_program: user_main.c user_malloc.c
    i686-elf-gcc -ffreestanding -nostdlib -o $@ $^ -T user.ld

---

6 🧪 六、测试：用户程序中的 malloc

user_main.c：

int main() {
    // 小内存
    int *arr = (int*)malloc(1024 * sizeof(int));
    for (int i = 0; i < 1024; i++) {
        arr[i] = i;
    }
    printf("Small alloc: arr[100] = %d\n", arr[100]);

    // 大内存
    char *big = (char*)malloc(1024 * 1024); // 1MB
    big[0] = 'A';
    big[1024*1024-1] = 'Z';
    printf("Big alloc: %c ... %c\n", big[0], big[1024*1024-1]);

    free(arr);
    free(big);
    return 0;
}

运行效果：

Small alloc: arr[100] = 100
Big alloc: A ... Z

✅ 用户程序成功使用 malloc/free！

---

7 ⚠️ 七、优化方向

1. 用户态 malloc 优化：
2. 空闲链表（free list）回收小内存

3. 多级分配器（如 dlmalloc）

4. 写时复制（CoW）：

5. fork 时不复制物理页，只设为只读

6. 写时触发 Page Fault，才复制

7. 内存映射文件：

8. mmap 支持映射 ext2 文件内容

9. 实现 demand paging from disk

10. 交换（Swapping）：

11. 将不活跃页换出到磁盘

---

8 💬 写在最后

从 Buddy 分配器到 malloc，
你构建的不仅是内存管理代码，
更是现代操作系统的核心支柱。

今天你实现的 mmap，
正是 Linux 中 glibc malloc 的底层依赖。

🌟 内存管理的终极目标：让每个进程都拥有“无限”且安全的地址空间。

---

📬 动手挑战：
修改用户态 malloc，支持 free 小内存块并重复使用。
欢迎在评论区分享你的分配器设计！

👇 下一篇你想看：写时复制（CoW）实现，还是 内存映射文件（mmap file）？

---

#操作系统 #内核开发 #内存管理 #Buddy分配器 #malloc #mmap #页表 #从零开始

---

📢 彩蛋：关注后回复关键词 “memory”，获取： - 完整 Buddy 分配器代码 - 页表操作与 Page Fault 处理 - 用户态 malloc/free 实现模板