os_lab2:物理内存管理

课程主页：https://www.xuetangx.com/course/THU08091000267/5883104?channel=i.area.learn_title
实验指导书：https://objectkuan.gitbooks.io/ucore-docs/content/
github：https://github.com/chyyuu/ucore_os_lab (master 分支)

前置知识

分段机制、分页机制、物理内存管理机制、伙伴系统、slub 分配算法。

改动点

相比于 lab1 源代码，lab2 主要做了如下改动：

bootasm.S 增加内存探测功能

借助于 BIOS 提供的 int 0x15 中断功能，探测当前机器的内存布局，并将其结果放置于 0x8000 处。

该结果以 地址范围描述符 结构体形式进行存放：
1
2
3
4
5
6
7
8
struct e820map {
int nr_map;
struct {
long long addr; // 基址
long long size; // 大小
long type; // 类型
} map[E820MAX];
}
kernel.ld 重新设置入口点和加载位置

在 lab1 中，ucore 入口点直接为 init.c；而在 lab2 中，ucore 入口点为 entry.S，随后跳转至 init.c，原因在于：需要在 entry.S 中完成开启分页机制、加载基本页表等工作。

值得注意的是：虽然 kernel.ld 中加载位置为 0xC0100000 ，但是 bootmian.c 却将其实际加载至 0x100000，从而形成一种不对等映射。
增加 entry.S 文件
修改 pmm_init() 函数

该函数为实现物理内存管理的关键函数，所有练习均基于此进行展开，其中主要完成如下工作：初始化物理内存管理器 pmm_manager、内核空间虚拟地址与物理地址的映射、有关页目录表和页表的各种操作。

练习一

此练习用于了解 default_pmm.c 代码所做的工作 (默认的物理内存管理：基于 First-Fit 的连续物理内存分配算法)。

对于物理内存管理而言，主要涉及两大数据结构：

// 该结构用于管理空闲物理内存。
typedef struct {
    list_entry_t free_list;         // 双向链表头部节点，该链表存放所有空闲内存块。
    unsigned int nr_free;           // 该链表所含的空闲页总数(内存块可能包含多个空闲页)。
} free_area_t;

// 该结构用于描述某页信息。
struct Page {
    int ref;                        // 指代当前页被映射至多少个虚拟页。
    uint32_t flags;                 // 指代当前页的状态信息。PG_reserved 表示当前页是否为保留页，PG_property 指代当前页是否空闲，仅内存块的第一个页设置此字段，内存块的其余页均设置为 0。
    unsigned int property;          // 指代空闲内存块所包含的空闲页个数，仅空闲内存块的第一个空闲页设置此字段，其余空闲页均设置为 0。
    list_entry_t page_link;         // 双向链表节点。
};

熟悉此两大数据结构各字段含义和 First-Fit 思想，很容易理解 default_pmm.c 所做的工作，在此不再赘述。

值得一说的是：ucore 如何初始化 free_area_t？

初始化工作具体分为两部分：

init_pmm_manager()

初始化物理内存管理器为 default_pmm_manager，并调用该管理器的 init() 以初始化 free_list 和 nr_free 。

page_init()

基于内存探测结果，将空闲物理块放置于 free_list 中，以供管理器进行管理。

鉴于此函数比较重要，在此简单列举其实现源代码 (已忽略部分无关代码)：

static void page_init(void) {
    // 之前放置内存探测结构的位置便是 0x8000 + KERNBASE，如今获取它。
    struct e820map *memmap = (struct e820map *)(0x8000 + KERNBASE);
    // maxpa 用于存放最大可用物理内存地址(注：ucore 设置可用物理空间最大为 KMEMSIZE，因此 maxpa 不可能超过此值，下面代码有设置)。
    uint64_t maxpa = 0;

    int i;
    for (i = 0; i < memmap->nr_map; i ++) {
        uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size;
        // 如果内存块类型为 E820_ARM 表明，其可供 OS 使用。
        if (memmap->map[i].type == E820_ARM) {
            if (maxpa < end && begin < KMEMSIZE) {
                maxpa = end;
            }
        }
    }
    if (maxpa > KMEMSIZE) {
        maxpa = KMEMSIZE;
    }

    // kernel.ld 中 .bss 数据段的结尾，基本也属于 OS 代码部分的结尾。
    extern char end[];

    // 计算所含页数，设置页描述数组 pages 的起始位置。
    npage = maxpa / PGSIZE;
    pages = (struct Page *)ROUNDUP((void *)end, PGSIZE);

    // 将 0~maxpa 部分的物理页，设为保留页。
    for (i = 0; i < npage; i ++) {
        SetPageReserved(pages + i);
    }

    // 页描述数组的结尾位置。
    uintptr_t freemem = PADDR((uintptr_t)pages + sizeof(struct Page) * npage);

    // 将 page table 结尾 ~ maxpa 空间放置于空闲链表内(目前仅涉及内核空间，后续 ucore 实验可能涉及用户空间)。
    for (i = 0; i < memmap->nr_map; i ++) {
        uint64_t begin = memmap->map[i].addr, end = begin + memmap->map[i].size;
        if (memmap->map[i].type == E820_ARM) {
            if (begin < freemem) {
                begin = freemem;
            }
            if (end > KMEMSIZE) {
                end = KMEMSIZE;
            }
            if (begin < end) {
                begin = ROUNDUP(begin, PGSIZE);
                end = ROUNDDOWN(end, PGSIZE);
                if (begin < end) {
                    init_memmap(pa2page(begin), (end - begin) / PGSIZE);
                }
            }
        }
    }

    /*
    * QEMU 的物理内存探测结果布局：
    * e820map:
    * memory: 0009fc00, [00000000, 0009fbff], type = 1.
    * memory: 00000400, [0009fc00, 0009ffff], type = 2.
    * memory: 00010000, [000f0000, 000fffff], type = 2.
    * memory: 07ee0000, [00100000, 07fdffff], type = 1.
    * memory: 00020000, [07fe0000, 07ffffff], type = 2.
    * memory: 00040000, [fffc0000, ffffffff], type = 2.
    * 
    * 注：type 取值为 1，表示 OS 可用空间；type 取值为其他值，则 OS 不可用，仅供某些设备可用(具体不谈，知道即可)。
    * 按照上述代码以及探测结果可知，最大可用空间为 [0~07fdffff]，近似等于 [0~128M]。
    * 
    * entry.S 中，设置基本页表 KERNBASE + (0 ~ 4M) ~ (0 ~ 4M) 的映射关系。
    * 根据最开始的汇编代码可知：0~1M 已经供给 BIOS 和 BootLoader 使用，OS 使用的是 1~4M 空间。
    * 这里就存在一个问题，重新设置页表前，OS 真的不会超过 4M 吗，即所需页面不会超过 3 * 1024 / 4 = 768？
    * 简单分析一下：
    *     运行代码查看 end 取值，可以发现其值为 0xc011bf28，刨去 BIOS 和 BootLoader 所占空间，可知：OS 代码、数据部分所占 27 个页面。
    *     page table 所需页面计算：128M的可用空间 => 分成128 * 1024 / 4 (32768) 页面 => 由于每个页面大致容纳 4K/20=200 个 page 信息，因此总共需要约 32768/200（163） 个页面。
    *     总共 27+163=190 个页面，由此可知，OS 是不会超过 4M 的。
    */
}

如何修改kern/mm/default_pmm.c中的default_init，default_init_memmap，default_alloc_pages， default_free_pages等相关函数可查看lab_answer/lab2_result中的代码和注释，这里就不再赘述。

练习二

该练习用于了解页目录表、页表的使用，以及虚拟地址的转换流程。

对于 ucore 而言，如此划分 32 位的线性地址 (其中宏 PDX/PTX/PGOFF/PPN 分别用于获取线性地址的相应部分)：

// +--------10------+-------10-------+---------12----------+
// | Page Directory |   Page Table   | Offset within Page  |
// |      Index     |     Index      |                     |
// +----------------+----------------+---------------------+
//  \--- PDX(la) --/ \--- PTX(la) --/ \---- PGOFF(la) ----/
//  \----------- PPN(la) -----------/

对于页目录表或者页表而言，其均 4KB 对齐，且表项均为 int 整数 (因为 4KB 对齐，那么页表或页的物理地址的低 12 位一定为 0，那么表项可使用这低 12 位存放权限信息，例如，当前页表或页可读、可写、是否存在)。

注：页目录项（Pag Directory Entry）和页表项（Page Table Entry）中每一个组成部分的含义可参考该资料。

get_pte() 函数的具体实现，详见源代码：

pte_t * get_pte(pde_t *pgdir, uintptr_t la, bool create) {
    // 基于宏 PDX 及页目录表基址 pgdir，获取线性地址 la 所对应的页目录表条目。
    pde_t *pdep = pgdir + PDX(la);
    
    // 判断当前条目是否存在对应页表。
    if ( !(*pdep & PTE_P))
    {
        // 尝试分配一个物理页，以此作为页表。
        struct Page* page = alloc_page();

        // 分配失败或者无需新建，则直接返回。
        if (!create || page == NULL)
        {
            return NULL;
        }
        
        // 需要使用此页表，设置引用数。基于 page2pa 获取该页对应的物理地址(页描述数组起始地址与 page 地址的差，表明其间存在多少个页描述结构，一个页描述结构对应 4KB 空间，那么很容易计算当前页所对应的物理地址)。
        set_page_ref(page, 1);
        uintptr_t pa = page2pa(page);

        // 清空该页信息(pa 为物理地址，需要将其转换为虚拟地址，因为分段机制采用的是扁平模式，因此虚拟地址等价于线性地址。对于目前的内核而言，线性地址与物理地址间相差 0xC000000，因此很容易实现地址转换)。
        memset(KADDR(pa), 0, PGSIZE);

        // 建立页表与页目录间的对应关系，并设置相应权限。
        *pdep = pa | PTE_P | PTE_W | PTE_U ;   
    }
    
    // 返回 la 对应的具体页表条目(因为页目录条目对应的是物理地址，同样需要将其转换为虚拟地址)。
    return (pte_t *)(KADDR(PDE_ADDR(*pdep))) + PTX(la);         
}

注意：函数参数、指针操作，所涉及的地址均为虚拟地址，而非实际物理地址。

练习三

该练习用于了解页目录表、页表的使用，以及虚拟地址的转换流程。

page_remove_pte() 函数的具体实现，详见源代码：

page_remove_pte(pde_t *pgdir, uintptr_t la, pte_t *ptep) {
	// 判断当前页目录条目是否存在相应的页表，如果不存在则无需移除。
    if (*ptep & PTE_P) {
        // 获取相应页表对应的页描述结构
        struct Page *page = pte2page(*ptep);
        // 解除映射关系，自然需要引用数减一，如果引用数归零，则释放此页面。
        if (page_ref_dec(page) == 0) {
            free_page(page);
        }
        // 重置页目录条目，并清除 tlb 中有关此线性地址 la 的无效信息。
        *ptep = 0;
        tlb_invalidate(pgdir, la);
    }
}

地址映射的若干阶段

段页式管理总体框架图：

在 lab2 中，最为复杂的，莫过于与分段机制和分页机制相关的若干地址映射阶段，在此简要介绍其实现过程。

第一阶段

bootasm.S 中开启分段机制，其所涉段表定义如下：

gdt:
    SEG_NULLASM                                     # null seg
    SEG_ASM(STA_X|STA_R, 0x0, 0xffffffff)           # code seg for bootloader and kernel
    SEG_ASM(STA_W, 0x0, 0xffffffff)                 # data seg for bootloader and kernel

地址映射关系为：虚拟地址 == 线性地址 == 物理地址。

第二阶段

bootmain.c 中加载 OS，由于编译的加载位置与实际的加载位置并不相同，因此存在一个隐性的地址映射关系 (实际并不存在)：虚拟地址 - 0xC0000000== 线性地址 == 物理地址。

第三阶段

entry.S 中开启分页机制，其所涉页表如下：

.globl __boot_pgdir
    # 映射虚拟地址 0 ~ 4M 至物理地址 0 ~ 4M(临时条目，跳转至 kern_init 前即会删除)。
    .long REALLOC(__boot_pt1) + (PTE_P | PTE_U | PTE_W)
    # 空白填充虚拟地址 4M ~ 0xC0000000 之间的页目录表项
    .space (KERNBASE >> PGSHIFT >> 10 << 2) - (. - __boot_pgdir) 
    # 映射虚拟地址 0xC0000000 + (0 ~ 4M) 至物理地址 0 ~ 4M。
    .long REALLOC(__boot_pt1) + (PTE_P | PTE_U | PTE_W)
    .space PGSIZE - (. - __boot_pgdir)

地址映射关系为：虚拟地址 == 线性地址 == 物理地址 + 0xC0000000 (仅限 0 ~ 4M)。

涉及到的汇编命令可参考http://flint.cs.yale.edu/cs421/papers/x86-asm/asm.html和http://flint.cs.yale.edu/cs421/papers/x86-asm/asm.html

第四阶段

pmm_init() -> boot_map_segment() 中重新设置页目录表和页表，从而得到如下地址映射关系：虚拟地址== 线性地址 == 物理地址 + 0xC0000000 (0~0x38000000，目前 ucore 所能访问的全部地址空间)。

linux 内核内存管理 slub算法

核管理页面使用了2个算法：伙伴算法和slub算法，伙伴算法以页为单位管理内存，但在大多数情况下，程序需要的并不是一整页，而是几个、几十个字节的小内存。于是需要另外一套系统来完成对小内存的管理，这就是slub系统。slub系统运行在伙伴系统之上，为内核提供小内存管理的功能。

详细内容可查看这篇博文。

前置知识

改动点

练习一

练习二

练习三

地址映射的若干阶段

linux 内核 内存管理 slub算法

linux 内核内存管理 slub算法