OS Lab 2 内存管理

区域	地址范围	大小	访问权限	是否经 TLB	是否缓存
kuseg	`0x00000000` - `0x7FFFFFFF`	2GB	用户态 / 内核态都可用	是	取决于页属性，通常可缓存
kseg0	`0x80000000` - `0x9FFFFFFF`	512MB	仅内核态	否，直接映射	是
kseg1	`0xA0000000` - `0xBFFFFFFF`	512MB	仅内核态	否，直接映射	否

只有kuseg需要虚拟-物理地址转换，所以只有它才需要页表/TLB，其他的两个可以直接地址转换（已经封装好宏，在mmu.h）。

并且MIPS 通常是：先查 TLB。如果 TLB miss，触发异常，由内核软件去查页表，然后把结果写回 TLB，故操作系统内核负责维护TLB中的数据。在这个Lab里面流程是这样的：

用户态地址（kuseg）运行时先走 TLB
页表是内核维护的“后备映射信息”
TLB miss 之后，由 tlb_asm.S / tlbex.c 去查页表并回填 TLB

所以内核中，需要先初始化页表、负责页表管理函数，并负责TLB miss的处理。

在 lab 里，实际 RAM [0, memsize) 被划分成 npage 个物理页；pages 是一个长度为 npage 的物理页管理数组，pages[i] 对应第 i 个物理页。pages 数组本身也存放在普通物理内存中，只是它记录的是所有物理页的元数据。

真实物理内存 [0, memsize)
-----------------------------------------
| page0 | page1 | page2 | page3 | ...  |
-----------------------------------------

管理数组 pages[]
-----------------------------------------
| pages[0] | pages[1] | pages[2] | ... |
-----------------------------------------

对应关系：
pages[0] -> page0
pages[1] -> page1
pages[2] -> page2
...

所以总的流程是：

初始化pages（包括计算页数量、分配pages这个数组的内存），负责管理所有物理页，同时将空闲页加入链表。
然后写一些物理内存、虚拟内存管理的函数
页表与TLB逻辑连接

一、基础数据结构

在进行内存操作之前，先定义了一些基础的数据结构。最主要的数据结构是struct Page以及作为空闲页链表头的struct Page_list。

要理解这两个数据结构，需要先了解代码中宏定义的“双向链表”结构。这个结构与平常存前后指针的双向链表不同，它存的是下一个元素的指针next、和前一个元素的 next 指针地址（指针的指针）。

（1）双向链表宏

位置include/queue.h，实现双向链表功能，定义了很多宏定义。指导书的一些对这里面宏定义的解释说明（基本上都是要传指针进去的）：

作用	宏名
定义链表头结构体	`LIST_HEAD(name, type)`
定义链表节点中的链接字段	`LIST_ENTRY(type)`
判断链表是否为空	`LIST_EMPTY(head)`
获取链表第一个元素（重要）	`LIST_FIRST(head)`
初始化链表	`LIST_INIT(head)`
获取当前元素的下一个元素（重要）	`LIST_NEXT(elm, field)`
在某元素后插入新元素	`LIST_INSERT_AFTER(listelm, elm, field)`
在某元素前插入新元素	`LIST_INSERT_BEFORE(listelm, elm, field)`
在链表头部插入元素	`LIST_INSERT_HEAD(head, elm, field)`
删除某个元素	`LIST_REMOVE(elm, field)`

基本上，head表示头结构体的指针，elm（饿了么）代表当前要操作的指针，field代表挂载结构体中LIST_ENTRY()变量的变量名，listelm代表另一个要操作的元素。定义宏里面的name是链表头结构体的名字，type是链表结构体的名字。

这里面前两个是两个结构体定义，接着的四个是一些基本功能、辅助函数，最后四个是一些链表操作函数。

结构体定义

定义里面最重要的是LIST_ENTRY这个结构体定义，它负责链表的连接工作。

#define LIST_ENTRY(type)                                                                           \
    struct {                                                                                   \
        struct type *le_next;  /* 下一个元素 */                                           \
        struct type **le_prev; /* 前一个位置中的 next 指针地址 */                       \
    }

上面的链表只有前后节点，但是链表不能没有值，所以LIST_ENTRY并不是完整的链表元素结构体，他是链表元素的一部分（嵌套进去的，结构体中结构体），只负责链接工作，比如真正的链表元素结构体类似于下面这种：

struct Page {
    int id; // 这里ai只是为了演示，瞎写的
    LIST_ENTRY(Page) page_link; // 上面的宏定义
};

上面例子里面的page_link即是后面很多宏定义所需的field字段，比如通过Page->page_link，我们可以拿到LIST_ENTRY这个结构体，故我们可以用Page->page_link.le_next获取当前元素的下一个元素指针。

宏定义特性

总结了一下这里面宏定义的一些特殊写法：

宏定义是把对应的定义在代码中直接替换成后面所有的内容。
每行写完之后加上\，代表这个宏定义还没有结束。
使用while{ } do(0)结构，防止宏定义解析到单行的if或者while之后被拆开，同时do(0)后面最好不加分号，真正代码里再加。
部分字段为了防止解析错误，最好加上括号，比如(elm)，防止解析的时候被拆开，优先解析。有的部分不能加括号。

如何修改链表元素

链表里面每一个元素保存了下一个元素的指针next，同时还保存了上一个元素的next指针的指针prev（类型是指针的指针，指向的是前一个元素的next指针，而非元素）。

所以不管是修改/插入/删除元素，都只需要考虑修改四件事（删除的时候不用管与当前元素相关的两项，删了就好）。可以分为两类：

首先是当前和上一项的next，即当前元素对应的下一个元素指针le_next (LIST_NEXT(elm, field))、上一个元素对应的下一个元素指针le_next(LIST_NEXT(pre, field) (知道上一个元素的话) 或者 *elm->field.le_prev)

然后是当前和下一项的prev，以及当前元素下保存上一个元素next指针的指针(elm->field.le_prev )、下一个元素保存的上一个元素next指针的指针（nxt->field.le_prev (知道下一个元素的话) 或者 LIST_NEXT((elm), field)->field.le_prev）。

（2）Page结构体定义

typedef LIST_ENTRY(Page) Page_LIST_entry_t;

struct Page {
    Page_LIST_entry_t pp_link; /* free list link ，上面定义的那个东西 */
    u_short pp_ref; // 用来记录page被用了几回，次数为0就可以放空余链表里面
};

这是物理页的“管理”结构体，记录了page被用了几回，也可以被当做链表元素插入删除。

在接下来的内存管理里面，定义了一个Page“管理”数组pages，并把其下标和真实内存地址相对应（后面部分）：

struct Page *pages;

（3）空闲页链表

LIST_HEAD(Page_list, Page);

struct Page_list page_free_list;

属于是结构体套结构体套结构体了，很晕，展开之后应该是这样的：

page_free_list的作用是链表头，通过LIST_FIRST(page_free_list)可以获得链表里第一个空闲页，注意要先判断是否为空。

到这里，我们定义了物理页对应的管理结构体，以及空闲页的管理数据结构（链表）。下面我们要进行的是把物理页初始化，并与结构体相对应~

二、内存初始化流程

上一节内核启动之后，跳转到了init.c里面的mips_init函数。

void mips_init(u_int argc, char **argv, char **penv, u_int ram_low_size) {
    printk("init.c:\tmips_init() is called\n");

    // lab2:
    mips_detect_memory(ram_low_size);
    mips_vm_init();
    page_init();
    ...
}

这几个函数都在pmap.c中，所以先来看一下pmap.c的结构以及一些全局变量：

static u_long memsize：物理内存总大小，单位是字节。
u_long npage：总页数，memsize / PAGE_SIZE。
Pde *cur_pgdir：当前页目录指针。
struct Page *pages：页管理数组（宏定义那里的），每个物理页对应一个 struct Page，用于记录这个页是否被占用、引用计数多少等。
static u_long freemem：当前内存分配到哪里了的位置，靠它线性分配内存。只在启动阶段有用。
struct Page_list page_free_list：空闲物理页链表（宏定义那里的）。

下面按照三个函数看一下：

（1）mips_detect_memory

init里面第一步访问的是pmap.c里面的mips_detect_memory(ram_low_size)，负责探测内存大小、物理页数，传入的是“系统可用物理内存大小”。设置了以下两个全局变量：

memsize：物理内存大小，也是最大物理地址
npage：物理页数量，即物理内存大小除以每一页的大小（右移PGSHIFT）

计算一下就好了~

（2）mips_vm_init

第二步，是调用mips_vm_init()函数，负责初始化虚拟内存管理，主要执行了这一个函数，辅助分配内存空间：

pages = (struct Page *)alloc(npage * sizeof(struct Page), PAGE_SIZE, 1);

这个函数指导书的描述如下：分配n字节的空间并返回初始的虚拟地址，同时将地址按align字节对齐（保证align可以整除初始虚拟地址），若clear为真，则将对应内存空间的值清零，否则不清零。

三个参数分别是分配内存大小、分配空间的地址对齐要求、是否清空，并返回分配到内存的首地址。代码如下：

/* 概述：
    以对齐方式 `align` 分配 `n` 字节的物理内存；如果 `clear` 被设置，则将所分配
    的内存清零。
    这个分配器只在建立虚拟内存系统时使用。
   后置条件：
    如果内存耗尽，应当 panic；否则返回分配到的这段内存地址。*/
void *alloc(u_int n, u_int align, int clear) {
    extern char end[];
    u_long alloced_mem;

    /* 如果这是第一次调用，则初始化 `freemem`。
     * 它表示链接器没有分配给任何内核代码或全局变量的第一个虚拟地址。 */
    if (freemem == 0) {
        freemem = (u_long)end; // end
    }

    /* 步骤 1：将 `freemem` 向上取整到满足对齐要求。 */
    freemem = ROUND(freemem, align);

    /* 步骤 2：保存当前 `freemem` 的值作为本次分配到的内存块起始地址。 */
    alloced_mem = freemem;

    /* 步骤 3：增加 `freemem`，记录这次分配。 */
    freemem = freemem + n;

    // 如果内存耗尽则触发 panic。
    panic_on(PADDR(freemem) >= memsize);

    /* 步骤 4：如果参数 `clear` 被设置，则将分配到的内存块清零。 */
    if (clear) {
        memset((void *)alloced_mem, 0, n);
    }

    /* 步骤 5：返回分配到的内存块。 */
    return (void *)alloced_mem;
}

干的事情就是：freemem控制当前内存分配到哪里，首先先放到上次内存分配的结尾end，再得先满足地址对其要求，然后分配n大小的内存，并进行clear清零，并返回分配到的内存块首地址。

注意，这里分配的不是物理页内存，而是为 Page 结构体数组 pages按页分配物理内存。

（3）page_init

刚才只是分配了物理页管理数组，这时候要把空闲的page放到page_free_list里面。

这一步首先初始化链表头，然后通过freemem找到已经使用过的pages，把从0到used_pages之间所有页都标上pp_ref=0，然后把剩下没用的放到page_free_list里面。

void page_init(void) {
    /* Step 1: Initialize page_free_list. */
    /* Hint: Use macro `LIST_INIT` defined in include/queue.h. */
    /* Exercise 2.3: Your code here. (1/4) */
    LIST_INIT(&page_free_list);

    /* Step 2: Align `freemem` up to multiple of PAGE_SIZE. */
    /* Exercise 2.3: Your code here. (2/4) */
    freemem = ROUND(freemem, PAGE_SIZE);

    /* Step 3: Mark all memory below `freemem` as used (set `pp_ref` to 1) */
    /* Exercise 2.3: Your code here. (3/4) */
    int used_pages = PADDR(freemem) / PAGE_SIZE;
    int i;
    for(i = 0; i < used_pages; i++){
        pages[i].pp_ref = 1;
    }

    /* Step 4: Mark the other memory as free. */
    /* Exercise 2.3: Your code here. (4/4) */
    for(i = used_pages; i < npage; i++){
        pages[i].pp_ref = 0;
        LIST_INSERT_HEAD(&page_free_list, &pages[i], pp_link);
    }
}

三、物理内存管理

主要还是在pmap.c这个文件，首先先看一下这个文件的结构吧，里面包含了太多函数。

/* ==================== 初始化相关 ==================== */

void mips_detect_memory(u_int _memsize); 
// 根据 bootloader 提供的内存大小初始化 memsize 和 npage

void *alloc(u_int n, u_int align, int clear); 
// 启动阶段按对齐要求线性分配一段内存，并可选择清零

void mips_vm_init(void); 
// 初始化内存管理基础结构，并为 pages 数组分配空间

void page_init(void); 
// 初始化所有物理页状态，并建立空闲物理页链表


/* ==================== 物理内存 / 物理页分配相关 ==================== */

int page_alloc(struct Page **new); 
// 从空闲页链表中分配一个物理页并清零页内容

void page_free(struct Page *pp); 
// 释放一个引用计数为 0 的物理页并放回空闲链表

void page_decref(struct Page *pp); 
// 将物理页引用计数减一，若减到 0 则自动释放


/* ==================== 虚拟内存 / 页表映射相关 ==================== */

static int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte); 
// 查找虚拟地址对应的页表项，必要时创建新的页表页

int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm); 
// 将物理页映射到指定虚拟地址并设置权限

struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte); 
// 查询某个虚拟地址当前映射到的物理页

void page_remove(Pde *pgdir, u_int asid, u_long va); 
// 删除指定虚拟地址的映射并维护引用计数与 TLB


/* ==================== 测试检查相关 ==================== */

void physical_memory_manage_check(void); 
// 检查物理页分配、释放和空闲链表管理是否正确

void page_check(void); 
// 检查页表创建、页映射插入删除和引用计数维护是否正确

前四个函数是初始化相关的流程，涉及物理内存管理的有以下几个，包括分配物理页、把某一物理页引用次数减1（一个程序使用完毕）、free掉一个物理页。剩下的函数与虚拟内存管理有关。

（1）page_alloc

从空闲页链表中分配一个物理页并将其内容清零。

int page_alloc(struct Page **new) {
    /* Step 1: Get a page from free memory. If fails, return the error code.*/
    struct Page *pp;
    /* Exercise 2.4: Your code here. (1/2) */
    if(LIST_EMPTY(&page_free_list)){
        return -E_NO_MEM;
    }
    pp = LIST_FIRST(&page_free_list);
    LIST_REMOVE(pp, pp_link);

    /* Step 2: Initialize this page with zero.
     * Hint: use `memset`. */
    /* Exercise 2.4: Your code here. (2/2) */
    memset(page2kva(pp), 0, PAGE_SIZE);
    *new = pp;
    return 0;
}

它的作用是将 page_free_list 空闲链表头部页控制块对应的物理页面分配出去，将其从空闲链表中移除，并清空此页中的数据，最后将pp 指向的空间赋值为这个页控制块的地址。

（2） page_decref

void page_decref(struct Page *pp) {
    assert(pp->pp_ref > 0);

    /* If 'pp_ref' reaches to 0, free this page. */
    if (--pp->pp_ref == 0) {
        page_free(pp);
    }
}

主要用到page_free函数。

（3）page_free

它的作用是将pp指向的页控制块重新插入到page_free_list 中。此外需要先确保pp指向的页控制块对应的物理页面引用次数为0。

void page_free(struct Page *pp) {
    assert(pp->pp_ref == 0);
    /* Just insert it into 'page_free_list'. */
    /* Exercise 2.5: Your code here. */
    LIST_INSERT_HEAD(&page_free_list, pp, pp_link);
}

直接插入链表即可。

四、虚拟内存管理

（0）内存映射规则

MIPS中包含两级页表结构，对于kuseg段的虚拟地址使用两级页表转化。第一级表称为页目录(PageDirectory)，第二级表称为页表(Page Table)。

对于一个32位的虚存地址，从低到高从0开始编号，其31-22位表示的是一级页表项的偏移量，21-12 位表示的是二级页表项的偏移量，11-0位表示的是页内偏移量。

访问流程如下：

一二级页表的结构一样，每个页表均由1024个页表项组成，每个页表项由32位组成，包括20位物理页号以及12位标志位。其中，12位标志位包含高6位硬件标志位与低6位软件标志位，高6位硬件标志位用于存入EntryLo寄存器中（主要是一些有效位，用宏封装了）。

代码中，由于一个页表项可以恰好由一个32位整型来表示，因此可以使用Pde来表示一级页表项类型，用Pte来表示二级页表项类型，这两者的本质都是u_long类型。

因为每个页表大小是1024 * 4字节 = 4KB，每个页表大小正好就是一页，需要单独占一个物理页。

页表修改时，需要调用 tlb_invalidate 函数，可以实现删除特定虚拟地址的映射，每当页表被修改，就需要调用该函数以保证下次访问相应虚拟地址时一定触发TLB重填，进而保证访存的正确性。

再看一下这部分相关的那几个函数：

static int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte); 
// 查找虚拟地址对应的页表项，必要时创建新的页表页

int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm); 
// 将物理页映射到指定虚拟地址并设置权限

struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte); 
// 查询某个虚拟地址当前映射到的物理页

void page_remove(Pde *pgdir, u_int asid, u_long va); 
// 删除指定虚拟地址的映射并维护引用计数与 TLB

（1）pgdir_walk

static int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte) {
    Pde *pgdir_entryp; // va对应的一级页表项
    struct Page *pp;

    /* Step 1: Get the corresponding page directory entry. */
    /* Exercise 2.6: Your code here. (1/3) */
    pgdir_entryp = pgdir + PDX(va);

    /* Step 2: If the corresponding page table is not existent (valid) then:
     *   * If parameter `create` is set, create one. Set the permission bits 'PTE_C_CACHEABLE |
     *     PTE_V' for this new page in the page directory. If failed to allocate a new page (out
     *     of memory), return the error.
     *   * Otherwise, assign NULL to '*ppte' and return 0.
     */
    /* Exercise 2.6: Your code here. (2/3) */
    if(!( *pgdir_entryp & PTE_V )){
        if( create ){
            if( page_alloc(&pp) < 0 ) return -E_NO_MEM; // 分配新页
            pp->pp_ref++;
            *pgdir_entryp = page2pa(pp) | PTE_C_CACHEABLE | PTE_V;
        }else{
            *ppte = NULL;
            return 0;
        }
    }

    /* Step 3: Assign the kernel virtual address of the page table entry to '*ppte'. */
    /* Exercise 2.6: Your code here. (3/3) */
    Pte *pt = (Pte *)KADDR(PTE_ADDR(*pgdir_entryp));
    *ppte = pt + PTX(va);
    return 0;
}

该函数将一级页表基地址pgdir 对应的两级页表结构中 va 虚拟地址所在的二级页表项的指针存储在 ppte 指向的空间上（超级长难句）。如果create不为0且对应的二级页表不存在，则会使用page_alloc函数分配一页物理内存。

就是查找虚拟地址对应的页表项，必要时创建新的页表页（分配一个新的物理页存这个页表页），最后ppte指针存的是对应的二级页表项位置。

（2）page_insert

int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm) {
    Pte *pte;

    /* Step 1: Get corresponding page table entry. */
    pgdir_walk(pgdir, va, 0, &pte);

    if (pte && (*pte & PTE_V)) {
        if (pa2page(*pte) != pp) {
            page_remove(pgdir, asid, va);
        } else {
            tlb_invalidate(asid, va);
            *pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V;
            return 0;
        }
    }

    /* Step 2: Flush TLB with 'tlb_invalidate'. */
    /* Exercise 2.7: Your code here. (1/3) */
    tlb_invalidate(asid, va);

    /* Step 3: Re-get or create the page table entry. */
    /* If failed to create, return the error. */
    /* Exercise 2.7: Your code here. (2/3) */
    if (pgdir_walk(pgdir, va, 1, &pte) < 0) {
        return -E_NO_MEM;
    }

    /* Step 4: Insert the page to the page table entry with 'perm | PTE_C_CACHEABLE | PTE_V'
     * and increase its 'pp_ref'. */
    /* Exercise 2.7: Your code here. (3/3) */
    *pte = page2pa(pp) | perm | PTE_C_CACHEABLE | PTE_V;
    pp->pp_ref++;
    return 0;
}

指导书又是长难句，不贴了。

主要干的事是把虚拟地址va通过页表，映射到物理页pp对应的物理地址，并设置权限。

这个函数首先获得了二级页表项的位置，并且通过看二级页表项有没有、是否有效，如果有效的话，判断与当前要插入的一不一样，不一样则先移除，一样的话设置完权限就return。

然后在TLB中把这个页表项设置为失效。

接着再次使用walk，防止二级页表项不存在，所以先创建一个。然后把pp对应的地址、权限位组装完放到pte，并设置pp_ref++。

（3）page_lookup

查询某个虚拟地址当前映射到的物理页。主要是通过walk查询到二级页表项之后，获得对应页控制块指针。

（4）page_remove

删除指定虚拟地址的映射并维护引用计数与 TLB。

先通过上一个查找，如果查找成功则减小一次物理页控制块的ref次数，并清空页表项，清TLB缓存。

五、访问内存与TLB重填

看指导书吧

维护TLB的流程如下：

更新页表中虚拟地址对应的页表项的同时，将TLB中对应的旧表项无效化
在下一次访问该虚拟地址时，硬件会触发TLB重填异常，此时操作系统对TLB进行重填

所以主要维护了这两个步骤函数。

（1）旧表项无效化

这个感觉说的很清楚了。主要也不用自己写什么东西。

（2）TLB重填

CPU 访问某个虚拟地址时，TLB 里没找到对应映射，于是陷入内核；内核去页表里查这个虚拟地址应该映射到哪个物理页，再把这个结果写回 TLB，最后 CPU 重新执行刚才那次访存。

TLB 的重填过程由 kern/tlb_asm.S 中的 do_tlb_refill 函数完成。

主要是通过储存页表项的地址、触发异常虚拟地址、ASID，访问c语言函数：

void _do_tlb_refill(u_long *pentrylo, u_int va, u_int asid) {
    tlb_invalidate(asid, va);
    Pte *ppte;

    /* Exercise 2.9: Your code here. */
    while (page_lookup(cur_pgdir, va, &ppte) == NULL) {
        passive_alloc(va, cur_pgdir, asid);
    }

    ppte = (Pte *)((u_long)ppte & ~0x7);
    pentrylo[0] = ppte[0] >> 6;
    pentrylo[1] = ppte[1] >> 6;
}

先查找va对应的物理页，然后如果查不到表项，对应的调用passive_alloc申请物理页并进行映射。

附录

（一）各种头文件/宏定义

mmu.h

/* ===== 页大小与地址分解 ===== */
#define NASID 256                                        // ASID 最大数量
#define PAGE_SIZE 4096                                   // 页面大小 4KB
#define PTMAP PAGE_SIZE                                  // 一个页表项映射 4KB
#define PDMAP (4 * 1024 * 1024)                          // 一个页目录项映射 4MB
#define PGSHIFT 12                                       // 页内偏移位数
#define PDSHIFT 22                                       // 页目录索引起始位
#define PDX(va) ((((u_long)(va)) >> PDSHIFT) & 0x03FF)  // 取虚拟地址的一级页表索引
#define PTX(va) ((((u_long)(va)) >> PGSHIFT) & 0x03FF)  // 取虚拟地址的二级页表索引
#define PPN(pa) (((u_long)(pa)) >> PGSHIFT)              // 物理地址转物理页号
#define VPN(va) (((u_long)(va)) >> PGSHIFT)              // 虚拟地址转虚拟页号

/* ===== 页表项处理 ===== */
#define PTE_ADDR(pte) (((u_long)(pte)) & ~0xFFF)         // 取页表项中的物理页基地址
#define PTE_FLAGS(pte) (((u_long)(pte)) & 0xFFF)         // 取页表项中的低 12 位标志位
#define PTE_HARDFLAG_SHIFT 6                             // 硬件标志位从 bit6 开始

/* ===== 页表 / TLB 权限位 ===== */
#define PTE_G (0x0001 << PTE_HARDFLAG_SHIFT)             // 全局位，匹配时可忽略 ASID
#define PTE_V (0x0002 << PTE_HARDFLAG_SHIFT)             // 有效位，表示映射存在
#define PTE_D (0x0004 << PTE_HARDFLAG_SHIFT)             // 可写位，允许写入
#define PTE_C_CACHEABLE (0x0018 << PTE_HARDFLAG_SHIFT)   // 可缓存
#define PTE_C_UNCACHEABLE (0x0010 << PTE_HARDFLAG_SHIFT) // 不可缓存

/* ===== MIPS 地址空间分段 ===== */
#define KUSEG 0x00000000U                                // 用户空间，走 TLB/页表
#define KSEG0 0x80000000U                                // 内核直映射、可缓存
#define KSEG1 0xA0000000U                                // 内核直映射、不可缓存
#define KSEG2 0xC0000000U                                // 内核高地址映射区，走 TLB/页表

/* ===== 本实验常用地址布局 ===== */
#define KERNBASE 0x80020000                              // 内核镜像起始地址
#define ULIM 0x80000000                                  // 用户空间上界
#define UVPT (ULIM - PDMAP)                              // 用户只读页表映射区
#define UPAGES (UVPT - PDMAP)                            // 用户只读 pages 数组映射区
#define UENVS (UPAGES - PDMAP)                           // 用户只读 envs 数组映射区
#define UTOP UENVS                                       // 用户空间顶部
#define UXSTACKTOP UTOP                                  // 用户异常栈顶
#define USTACKTOP (UTOP - 2 * PTMAP)                     // 普通用户栈顶
#define UTEXT PDMAP                                      // 用户程序起始地址
#define UCOW (UTEXT - PTMAP)                             // COW 预留页
#define UTEMP (UCOW - PTMAP)                             // 临时映射页
#define KSTACKTOP (ULIM + PDMAP)                         // 内核栈顶

/* ===== 地址转换辅助 ===== */
#define PADDR(kva) ((u_long)(kva) - ULIM)                // kseg0 内核虚拟地址转物理地址（原宏还会检查合法性）
#define KADDR(pa) ((u_long)(pa) + ULIM)                  // 物理地址转 kseg0 内核虚拟地址（原宏还会检查越界）

queue.h

位置include/queue.h，实现双向链表功能，定义了很多宏定义。

作用	宏名
定义链表头结构体	`LIST_HEAD(name, type)`
定义链表节点中的链接字段	`LIST_ENTRY(type)`
判断链表是否为空	`LIST_EMPTY(head)`
获取链表第一个元素（重要）	`LIST_FIRST(head)`
初始化链表	`LIST_INIT(head)`
获取当前元素的下一个元素（重要）	`LIST_NEXT(elm, field)`
在某元素后插入新元素	`LIST_INSERT_AFTER(listelm, elm, field)`
在某元素前插入新元素	`LIST_INSERT_BEFORE(listelm, elm, field)`
在链表头部插入元素	`LIST_INSERT_HEAD(head, elm, field)`
删除某个元素	`LIST_REMOVE(elm, field)`

pmap.h

/* ===== 链表类型与页结构定义 ===== */

LIST_HEAD(Page_list, Page);                     // 定义空闲页链表头类型 Page_list

typedef LIST_ENTRY(Page) Page_LIST_entry_t;    // 定义 struct Page 的链表结点类型

struct Page {
    Page_LIST_entry_t pp_link;                  // 空闲页链表中的链接字段
    u_short pp_ref;                            // 该物理页的引用计数
};


/* ===== 页与地址转换辅助函数 ===== */

static inline u_long page2ppn(struct Page *pp); 
// Page 结构指针 -> 物理页号（pages 数组下标）

static inline u_long page2pa(struct Page *pp);  
// Page 结构指针 -> 物理地址

static inline struct Page *pa2page(u_long pa);  
// 物理地址 -> 对应的 Page 结构指针

static inline u_long page2kva(struct Page *pp); 
// Page 结构指针 -> 该物理页在内核中的 kseg0 虚拟地址

static inline u_long va2pa(Pde *pgdir, u_long va); 
// 根据页目录把虚拟地址翻译成物理地址，若无映射返回 ~0


/* ===== 初始化相关函数 ===== */

void mips_detect_memory(u_int _memsize);       
// 根据 bootloader 提供的物理内存大小初始化 memsize / npage

void mips_vm_init(void);                       
// 初始化虚拟内存管理基础结构，主要分配 pages 数组空间

void mips_init(u_int argc, char **argv, char **penv, u_int ram_low_size); 
// MIPS 内存管理总初始化入口

void page_init(void);                          
// 初始化所有物理页状态并建立空闲页链表

void *alloc(u_int n, u_int align, int clear);  
// 启动阶段使用的线性内存分配器


/* ===== 物理页分配与回收 ===== */

int page_alloc(struct Page **pp);              
// 从空闲链表分配一个物理页

void page_free(struct Page *pp);               
// 释放一个引用计数为 0 的物理页

void page_decref(struct Page *pp);             
// 将物理页引用计数减一，减到 0 时自动释放


/* ===== 虚拟内存页表映射管理 ===== */

int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm); 
// 将物理页映射到指定虚拟地址

struct Page *page_lookup(Pde *pgdir, u_long va, Pte **ppte); 
// 查询虚拟地址当前映射到哪个物理页

void page_remove(Pde *pgdir, u_int asid, u_long va); 
// 删除指定虚拟地址的页映射


/* ===== 测试函数 ===== */

void physical_memory_manage_check(void);       
// 检查物理页分配、释放和空闲链表逻辑

void page_check(void);                         
// 检查页表建立、插入、删除和引用计数逻辑

其他地方的宏

ROUND

（二）其他东西

Page_list结构体

EntryLO寄存器

PTE_V 有效位，若某页表项的有效位为1，则该页表项有效，其中高20位就是对应的物理页号。
PTE_D 可写位，若某页表项的可写位为1，则允许经由该页表项对物理页进行写操作。
PTE_G 全局位，若某页表项的全局位为1，则TLB仅通过虚页号匹配表项，而不匹配 ASID，将在 Lab3 中用于映射 pages 和 envs 到用户空间。本 Lab 中可以忽略。
PTE_C_CACHEABLE 可缓存位，配置对应页面的访问属性为可缓存。通常对于所有物理页面，都将其配置为可缓存，以允许CPU使用cache加速对这些页面的访存请求。
PTE_COW 写时复制位，将在 Lab4 中用到，用于实现 fork 的写时复制机制。本 Lab 中可以忽略。
PTE_LIBRARY 共享页面位，将在 Lab6 中用到，用于实现管道机制。本Lab中可以忽略

地址转换机制

其他函数

memset(void *s, int c, size_t n) ，按字节填内容。

s：要操作的内存起始地址
c：要填充的值
n：要填充的字节数

加载中...

整体框架与流程