シリウスの砂

Memory Management

✏️ 🔧 📄 34 min read

约定命名

  • page2pa (Page to PA)
    • 含义：把 struct Page * 转换成对应的 物理地址。
    • 逻辑：它计算该 Page 结构体在 pages 数组里的索引（Index），然后 Index * 4096。
    • 公式：PA=(pp−pages)×4096
  • pa2page (PA to Page)
    • 含义：page2pa 的反向操作。
    • 逻辑：给你一个物理地址，算出它是第几个物理页，返回对应的 struct Page *。
  • kva (Kernel Virtual Address)
    • 含义：内核虚拟地址。
    • 特点：在 MOS 中，内核地址通常在 0x80000000 以上。这部分虚拟地址与物理地址是线性偏移关系。
    • 公式：KVA=PA+0x80000000
  • KADDR (Kernel Address)
    • 含义：输入一个 PA，返回对应的 KVA。
    • 用途：当你拿到了物理地址（比如从页表项里读出来的），但你想读写这块内存时，必须用 KADDR 转成内核能碰的地址。
  • PADDR (Physical Address)
    • 含义：输入一个 KVA，返回对应的 PA。
    • 用途：当你有一个内核里的变量地址，但你想把这个地址填进页表项（PTE）时，必须用 PADDR 转成物理地址，因为页表里存的都是 PA

对照表:

缩写全称作用
ppPage Pointer管理员的手册页（struct Page *）
paPhysical Address内存条上的位置（0x0…）
vaVirtual Address分页看到的幻象
kvaKernel VA内核特权级看到的地址（0x8…）
page2paPage → PA从手册页找到对应的内存条上的地址
pa2pagePA → Page从物理地址翻回对应的手册页
KADDRPA → KVA把物理地址映射到内核视野，以便读写内容
PADDRKVA → PA把内核视野还原回物理地址，以便填入页表

4Kc 访存流程

4Kc 是在后续所有实验中所采用的 CPU

CPU 发出地址

在实际程序中, 访存与跳转等指令以及用于取指的 PC 寄存器中的访存目标地址都是虚拟地址.
我们编写的 C 程序中也经常通过对指针解引用来进行访存, 其中指针的值也会被视为虚拟地址, 经过编译后生成相应的访存指令.

虚拟地址映射

在 4Kc 上, 软件访存的虚拟地址会先被 MMU 硬件, 按照内存布局映射到物理地址, 随后使用物理地址来访问内存或其他外设.

MMU 采用硬件 TLB 来完成地址映射. TLB 需要由软件进行填写, 即操作系统内核负责维护 TLB 中的数据.
所有对低 2GB 空间(kuseg)的内存访问操作都需要经过 TLB.

CPU-TLB-Memory 关系
图中的 Cache 和外设之间虽然存在物理上的连接, 但在一般情况下, 对外设的读写往往不会经过 Cache.

内核程序启动

mips_init(u_int argc, char **argv, char **penv, u_int ram_low_size) 函数需要分别调用如下三个函数：

  • mips_detect_memory(u_int _memsize): 作用是探测硬件可用内存, 并对一些和内存管理相关的变量进行初始化.
  • mips_vm_init(): 作用是为内存管理机制作准备, 建立一些用于管理的数据结构.
  • page_init(): 作用是初始化 pages 数组中的 Page 结构体以及空闲链表.

mips_init 函数中的参数 u_int argc, char **argv, char **penv, u_int ram_low_size 是由 bootloader 传递给内核的.
在 bootloader 加载内核, 跳转到内核入口处之前, 会按照 MIPS ABI 的调用约定, 将这些参数填入 a0-a3 寄存器供内核使用.
其中传递的 ram_low_size 参数, 指定了硬件可用内存大小.

mips_detect_memory 函数

作用是探测硬件可用内存, 并对一些和内存管理相关的变量进行初始化.

要初始化的变量有:

  • memsize, 表示总物理内存对应的字节数.
  • npage, 表示总物理页数.

mips_vm_init 函数

在探测完可用内存后, 将开始建立内存管理机制.
为了建立起内存管理机制, 还需要用到 alloc 函数.

void mips_vm_init() {
 pages = (struct Page *)alloc(npage * sizeof(struct Page), PAGE_SIZE, 1);
}

Note

在没有页式内存管理机制时, 操作系统也需要建立一些数据结构来管理内存, 这就会涉及到内存空间的分配.
alloc 函数的功能就是用于分配内存空间(在建立页式内存管理机制之前使用).

/* Overview:
    Allocate `n` bytes physical memory with alignment `align`, if `clear` is set, clear the
    allocated memory.
    This allocator is used only while setting up virtual memory system.
   Post-Condition:
    If we're out of memory, should panic, else return this address of memory we have allocated.*/
void *alloc(u_int n, u_int align, int clear)
{
 extern char end[];
 u_long alloced_mem;
 
 /* Initialize `freemem` if this is the first time. The first virtual address that the
  * linker did *not* assign to any kernel code or global variables. */
 if (freemem == 0) {
  freemem = (u_long)end; // end
 }
 
 /* Step 1: Round up `freemem` up to be aligned properly */
 freemem = ROUND(freemem, align);
 
 /* Step 2: Save current value of `freemem` as allocated chunk. */
 alloced_mem = freemem;
 
 /* Step 3: Increase `freemem` to record allocation. */
 freemem = freemem + n;
 
 // Panic if we're out of memory.
 panic_on(PADDR(freemem) >= memsize);
 
 /* Step 4: Clear allocated chunk if parameter `clear` is set. */
 if (clear) {
  memset((void *)alloced_mem, 0, n);
 }
 
 /* Step 5: return allocated chunk. */
 return (void *)alloced_mem;
}

extern char end[] 在 kernel.lds 中:

. = 0x80400000;
end = . ;

也就是说该变量对应虚拟地址 0x80400000.
在建立内存管理机制时都是通过 kseg0 来访问内存. 根据映射规则, 0x80400000 对应的物理地址是 0x400000. 在物理地址 0x400000 的前面, 存放着操作系统内核的代码和定义的全局变量或数组(还额外保留了一些空间).
接下来将从物理地址 0x400000 开始分配物理内存, 用于建立管理内存的数据结构.

物理地址管理

采用链表法管理空闲物理页框.

链表宏

实现了一个双向链表的功能. 由于 C 语言没有泛型或模板, 通过宏提高泛用性.

  • LIST_HEAD(name, type): 创建一个名称为 name 链表的头部结构体, 包含一个指向 type 类型结构体的指针, 这个指针可以指向链表的首个元素.
  • LIST_ENTRY(type): 作为一个特殊的类型出现, 例如可以进行如下的定义: LIST_ENTRY(Page) a;
    它的本质是一个链表项, 包括指向下一个元素的指针 le_next, 以及指向前一个元素链表项 le_next 的指针 le_prev.
    le_prev 是一个指针的指针, 它的作用是当删除一个元素时, 更改前一个元素链表项的 le_next.
#define LIST_ENTRY(type)                                                             \
 struct {                                                                            \
  struct type *le_next;  /* next element */                                          \
  struct type **le_prev; /* address of previous next element */                      \
 }
  • LIST_EMPTY(head): 判断 head 指针指向的头部结构体对应的链表是否为空.
  • LIST_FIRST(head): 将返回 head 对应的链表的首个元素.
  • LIST_INIT(head): 将 head 对应的链表初始化.
  • LIST_NEXT(elm, field), 返回指针 elm 指向的元素在对应链表中的下一个元素的指针.
    elm 是一个指针，指向当前操作的那个结构体(比如 struct Page *)
    elm 指针指向的结构体需要包含一个名为 field 的字段, 类型是一个链表项 LIST_ENTRY(type).
  • LIST_INSERT_AFTER(listelm, elm, field): 将 elm 插到已有元素 listelm 之后.
  • LIST_INSERT_BEFORE(listelm, elm, field): 将 elm 插到已有元素 listelm 之前.
  • LIST_INSERT_HEAD(head, elm, field): 将 elm 插到 head 对应链表的头部.
  • LIST_REMOVE(elm, field): 将 elm 从对应链表中删除 由于前面”field 指针的指针 le_prev”的设计, 这里可以不必判断是否为首元素, 直接删除本元素.

这个宏链表是为了高效删除和快速头插优化的.

  • 宏来实现链表的好处:
    • C 语言中没有模板和泛型, 用宏可以作为替代, 满足不同类型的数据使用链表作为存储结构的需求.
    • 复用性极高, 因为我们的链表是一个宏, 和类型完全解耦了. 因此可以给各种类型使用, 实现一种”多态”.
    • 更进一步, 用这个宏可以将结构体嵌入一个链表, 从而可以做到让一个结构体存在于多个链表, 而不需要创建一个复杂的链表节点结构体.
  • 性能差异对比
操作单向链表 (SLIST)双向链表 (LIST)循环链表 (CIRCLEQ)
头插O(1)O(1)O(1)
尾插O(n)O(n)O(1)
指定元素后插入O(1)O(1)O(1)
指定元素前插入O(n)O(1)O(1)
任意元素删除O(n)O(1)O(1)

页控制块

MOS 中维护了 npage 个页控制块, 也就是 Page 结构体.
每一个页控制块对应一页的物理内存, MOS 用这个结构体来按页管理物理内存的分配.

对于定义

LIST_HEAD(Page_list, Page)
typedef LIST_ENTRY(Page) Page_LIST_entry_t;
 
struct Page {
    Page_LIST_entry_t pp_link; /* free list link */
    // Ref is the count of pointers (usually in page table entries)
    // to this page.  This only holds for pages allocated using
    // page_alloc.  Pages allocated at boot time using pmap.c's "alloc"
    // do not have valid reference count fields.
    u_short pp_ref;
};

展开后, 逻辑关系如下:

struct Page_list {
    struct {                   // <--- 这里的结构体就是 Page 的定义
        struct {               // <--- 这里的结构体就是 LIST_ENTRY 的定义
            struct Page *le_next;
            struct Page **le_prev;
        } pp_link;
        u_short pp_ref;
    } *lh_first;               // <--- LIST_HEAD 里的指针，指向上面定义的 Page 结构
};

真实展开代码如下:

struct Page_list {
    struct Page *lh_first;  // 指向第一个 Page 结构体
};
 
struct Page {
    // Page_LIST_entry_t (即 LIST_ENTRY) 展开的结果
    struct {
        struct Page *le_next;
        struct Page **le_prev;
    } pp_link; 
 
    // Page 自己的数据成员
    u_short pp_ref;
};

将空闲物理页对应的 Page 结构体全部插入一个链表中，该链表被称为空闲链表，即 page_free_list.
当一个进程需要分配内存时, 就需要将空闲链表头部的页控制块对应的那一页物理内存分配出去, 同时将该页控制块从空闲链表中删去.
当一页物理内存被使用完毕(准确来说，引用次数 pp_ref 为 0)时, 将其对应的页控制块重新插入到空闲链表的头部.

因此我们可以看到, Page 结构体是对物理内存进行管理的数据块, 其在 pages 数组的序号 i 对应着第 i 个物理页.
并且, 空闲的页, 其对应的结构体被 page_free_list 串联, 用于分配管理.
这种数组存实体，链表连逻辑的形式很常用, 利用数组的性质快速获取偏移, 进行映射; 利用链表的性质快速增删元素, 申请释放内存.
这样的技巧页出现在进程控制块的管理中.

graph TD
    subgraph "The Array (Static Storage)"
        P0[Page 0]
        P1[Page 1]
        P2[Page 2]
        P3[Page 3]
        PN[Page N]
    end

    subgraph "The Free List (Dynamic Logic)"
        Head((Free List Head))
        Head --> P1
        P1 -- pp_link --> P3
        P3 -- pp_link --> P0
        P0 -- pp_link --> Null[NULL]
    end

    subgraph "In Use (Mapped)"
        P2 --> VA1[Mapped to VA 0x1000]
        PN --> VA2[Mapped to VA 0x5000]
    end

    style Head fill:#f96
    style P2 fill:#dfd
    style PN fill:#dfd

等到后面详细讲解关于页面管理的函数操作时, 请记住:

  • 当你通过地址找到 pp 时, 你在用它的数组属性.
  • 当你调用 page_alloc 拿到一个页时, 你在用它的链表属性.

其他相关函数

  • page_init():
    1. 首先利用链表相关宏初始化 page_free_list.
    2. 将目前已被操作系统内核使用的空间的地址标记进行页对齐, 即将 freemem 按照 PAGE_SIZE 进行对齐. 具体地, 之前用 alloc 分配空间后, 如果 freemem 处于一个页的中间, 会将其按页对齐.
    3. 接着将已使用空间对应的所有物理页面的页控制块的引用次数全部标为 1.
    4. 最后将剩下的物理页面的引用次数全部标为 0, 并将它们对应的页控制块插入到 page_free_list.
  • page_alloc(struct Page **pp):
    它的作用是将 page_free_list 空闲链表头部页控制块对应的物理页面分配出去,
    将其从空闲链表中移除, 并清空此页中的数据, 最后将 pp 指向的空间赋值为这个页控制块的地址. 这个函数本身不负责更改 pp 的 pp_ref 字段, 由调用者按照自己的使用需求, 负责更改.
  • page_decref(struct Page *pp):
    作用是令 pp 对应页控制块的引用次数减少 1, 如果引用次数为 0 则会调用 page_free 函数将对应物理页面重新设置为空闲页面.
  • page_free(struct Page *pp):
    它的作用是将 pp 指向的页控制块重新插入到 page_free_list 中. 此外需要先确保 pp 指向的页控制块对应的物理页面引用次数为 0.

虚拟内存管理

MOS 中用 PADDR 与 KADDR 这两个宏可以对位于 kseg0 的虚拟地址和对应的物理地址进行转换.
但是, 对于位于 kuseg 的虚拟地址, MOS 中采用两级页表结构对其进行地址转换.

Warning

内核能访问是内核视角的虚拟地址, 也就是 kva, 若要通过物理地址访问页表项, 需要使用 KADDR() 转化.

两级页表结构

第一级表称为页目录(Page Directory), 第二级表称为页表(Page Table).

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

PDX(va) 可以获取虚拟地址 va 的 31-22位，PTX(va) 可以获取虚拟地址 va 的 21-12 位.

访问虚拟地址时, 先通过一级页表基地址和一级页表项的偏移量, 找到对应的一级页表项, 得到对应的二级页表的物理页号.
再根据二级页表项的偏移量找到所需的二级页表项, 进而得到该虚拟地址对应的物理页号.

Two-Level Page Table

因此从 C 语言角度来看, 一二级页表实际上都是一个数组, 每一项为 32 位(4 字节, 一个 int 大小).
因此下文 “note” 中, 写明了地址拼接和 C 语言数组访问的一致性.

相关函数

Functions

地址拼接与 C 语言数组访问转换

C 中数组访问, 实际就是 基地址 + 索引 << log(size)(由于 size == sizeof(PDE) == sizeof(PTE) == 4, 因此实际为末位补 2 个 0)
[PDBase(VA) | PDX | 00] 对应的就是 &pgdir[PDX(va)]
[PTBase(VA) | PTX | 00] 对应的就是 &pgtable_kva[PTX(va)]

  • int pgdir_walk(Pde *pgdir, u_long va, int create, Pte **ppte):
    该函数将一级页表基地址 pgdir 对应的两级页表结构中, va 虚拟地址所在的二级页表项的指针存储在 ppte 指向的空间上. 如果 create 不为 0 且对应的二级页表不存在, 则会使用 [[#其他相关函数|page_alloc]] 函数分配一页物理内存用于存放二级页表, 如果分配失败则返回错误码. 获得二级页表项指针后, 我们可以对他进行操作, 例如读取权限位; 获取物理页号, 和低位拼接获得物理地址.
    获得的物理地址可以用于填写其他页表项, 或者用 KADDR() 转化为内核视角的虚拟地址, 从而进程访存.
  • int page_insert(Pde *pgdir, u_int asid, struct Page *pp, u_long va, u_int perm):
    将一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 映射到页控制块 pp 对应的物理页面，并将页表项权限为设置为 perm.
    如果此前 va 已经有映射关系, 那么该函数也会进行旧页移除.
  • struct Page * page_lookup(Pde *pgdir, u_long va, Pte **ppte):
    作用是返回一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 映射的物理页面的页控制块,
    同时将 ppte 指向的空间设为对应的二级页表项地址.
  • void page_remove(Pde *pgdir, u_int asid, u_long va):
    作用是删除一级页表基地址 pgdir 对应的两级页表结构中虚拟地址 va 对物理地址的映射.
    如果存在这样的映射, 那么对应物理页面的引用次数会减少一次.

我们在访问页表, 修改页表的时候, 应该优先使用这些函数.

  • 取资源: 用 page_alloc, 注意通过 page_insert 或者手动, 给引用数增加.
  • 读数据: 可以用 pgdir_walk 获取 PTE 后读取.
  • 改映射: 用 page_insert.
  • 删映射: 用 page_remove.
  • 查物理页: 用 page_lookup 获取已分配的管理结构.

如果尝试自己手动获取地址, 进行简单赋值, 则很可能因为引用数或者访问到非法内存而内核崩溃.

Note

在虚拟内存的世界里，PTE 决定了你能看到什么; 而在物理内存的世界里, struct Page 决定了这块内存归谁, 还能活多久.

graph LR
    subgraph "程序员 / 用户态 (User Space)"
        VA["虚拟地址 (VA)"]
    end

    subgraph "内核管理 (Kernel / Page Management)"
        PP["管理结构 (struct Page *)"]
        REF["pp_ref (引用计数)"]
        PP --- REF
    end

    subgraph "硬件 / 内存条 (Hardware / RAM)"
        PA["物理地址 (PA)"]
    end

     操作关系
    PP -- "page_insert (建立映射)" --> VA
    VA -- "page_remove (断开映射)" --> PP

    style VA fill:#f9f,stroke:#333,stroke-width:2px
    style PP fill:#bbf,stroke:#333,stroke-width:2px
    style PA fill:#bfb,stroke:#333,stroke-width:2px

写代码遇到内存问题时, 依次问自己这三个问题:

  • VA 层面: 我现在的进程能访问这个地址吗?(页表项 PTE_V 位是否有效)
  • PA 层面: 这个虚拟地址最终对应到哪块物理内存?(是否和其他进程冲突)
  • PP 层面: 这块物理内存现在有几个人在用? (pp_ref 是否正确, 是否会还没用完就被 page_free)

TLB 重填

TLB 结构

每个 TLB 表项都有两个组成部分, 包括一组 Key 和两组 Data.

EntryHi, EntryLo0, EntryLo1 都是 CP0 中的寄存器, 他们分别对应到 TLB 的 Key 与两组 Data, 并不是 TLB 本身.
VPN 高 19 位和 ASID 作为 key, 而 VPN 最低位分别对应两个 Data(VPN 共 20 位, 最后一位分奇偶页).

TLB 相关寄存器

ASID

虚拟内存通过 ASID 辨别虚拟地址来自哪个进程. ASID 的全称是 Address Space Identifier(地址空间标识符). 简单来说, 它是给每个进程分配的一个数字编号, 用来区分不同进程的虚拟地址空间。

  • ASID 的必要性
    • 解决虚拟地址重叠, 使得不同进程的同一虚拟地址可以映射到不同的物理地址, 而不会相互冲突, 错误访问. 很好地保证了隔离性.
    • 避免 TLB 反复刷新. 如果没有 ASID, 而想要保证隔离性, 必须在切换进程的时候刷新清空 TLB, 造成大量 TLB Miss, 拖慢系统. 而 ASID 的存在避免了这一点.
      系统无须在切换进程的时候清空 TLB, 也可以直接区分不同进程的虚拟地址.
  • 4Kc 可容纳不同的地址空间的最大数量 由于 ASID 段占据了 8 位, 因此最大支持 256 个地址空间.

ASID 资源是有限的, 需要使用一定的资源管理方法来分配与回收 ASID.
MOS 实验采用了位图法管理 256 个可用的 ASID, 如果 ASID 耗尽时仍要创建进程, 内核会发生崩溃.
实际的 Linux 系统中通过 ASID 分代机制来使得同时运行的进程数不受硬件ASID 位数的限制.

相关指令

  • tlbr: 以 Index 寄存器中的值为索引, 读出 TLB 中对应的表项到 EntryHi 与 EntryLo0, EntryLo1.
  • tlbwi: 以 Index 寄存器中的值为索引, 将此时 EntryHi 与 EntryLo0, EntryLo1 的值写到索引指定的 TLB 表项中.
  • tlbwr: 将 EntryHi 与 EntryLo0, EntryLo1 的数据随机写到一个 TLB 表项中.
    (此处使用 Random 寄存器来随机指定表项, Random 寄存器本质上是一个不停运行的循环计数器)
  • tlbp: 根据 EntryHi 中的 Key(包含 VPN 与 ASID), 查找 TLB 中与之对应的表项, 并将表项的索引存入 Index 寄存器. 若未找到匹配项, 则 Index 最高位被置 1.

操作流程

  1. 填写 CP0 寄存器.
  2. 使用 TLB 相关指令.

MIPS 4Kc 的 MMU 硬件中只有 TLB. 在用户地址空间访存时, 虚拟地址到物理地址的转换均通过 TLB 进行.

访问需要经过转换的虚拟内存地址时:
首先要使用虚拟页号和当前进程的 ASID 在 TLB 中查询该地址对应的物理页号.
如果虚页号和 ASID 组成的 Key 在 TLB 中存在对应的 TLB 表项(或虚页号在 TLB 中存在对应的 TLB 表项且表项权限位中的 G 位为 1)时, 则可取得物理地址;
如果不能查询到，则产生 TLB Miss 异常, 系统跳转到异常处理程序, 在内核的两级页表结构中找到对应的物理地址, 对 TLB 进行重填.

操作系统可以修改页表中虚拟地址映射的物理页号或映射的权限位.
如果 TLB 中已暂存了页表中某一虚拟地址对应的页表项内容, 之后操作系统更新了该页表项, 但没有更新 TLB, 则访问该虚拟地址时实际可能会访问到错误的物理页面.
所以我们需要维护 TLB 的表项, 使得当TLB 能够查询到虚拟地址相应的页号时, 取得的物理页号和权限信息与实际在内核页表中对应的数据一致.

所以, 维护 TLB 的流程是:

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

维护操作

旧表项无效化

tlb_invalidate 函数实现删除特定虚拟地址在 TLB 中的旧表项.

  1. tlb_invalidate 和 tlb_out 的调用关系: tlb_invalidate 作为 C 语言接口调用汇编实现的 tlb_out.
    tlb_invalidate 将 va 的高 19 位和 ASID 正确拼接, 作为参数, 通过 $a0 传入 tlb_out
  2. 一句话概括 tlb_invalidate 的作用: 根据给定的 ASID 和 va, 在 TLB 中查找匹配的条目, 并将其 key 和 data 均彻底清空, 以确保后续对该地址的访问不会命中旧的映射.
  3. tlb_out 汇编代码逐行解释:
LEAF(tlb_out)                 # 定义叶子函数 tlb_out
.set noreorder                # 禁止汇编器自动调整指令顺序
 
    mfc0    t0, CP0_ENTRYHI   # 将 CP0 EntryHi 寄存器的值保存到 t0, 防止破坏当前进程的上下文
 
    # 准备进行 TLB 查找（Probe）
    mtc0    a0, CP0_ENTRYHI   # 将传入的参数(由 tlb_invalidate 拼接好的待无效化的 VA+ASID 作为 key)写入 EntryHi
    nop                       # 解决数据冒险
 
    /* Step 1: Use 'tlbp' to probe TLB entry */
    tlbp                      # 在 TLB 中查找是否存在与 EntryHi 匹配的项, 索引存在 CP0 INDEX 中
    nop                       # 解决数据冒险
 
    /* Step 2: Fetch the probe result from CP0.Index */
    mfc0    t1, CP0_INDEX     # 将查找结果读入 t1. 若未命中, t1 的最高位会置为 1
 
.set reorder                  # 允许汇编器自动调整指令顺序
    bltz    t1, NO_SUCH_ENTRY # 如果 t1 < 0 (最高位为 1), 说明未找到映射, 跳转到结束标签
 
.set noreorder                # 禁止汇编器自动调整指令顺序
    # 准备用于覆盖原有表项的全 0 数据
    mtc0    zero, CP0_ENTRYHI # 清零 EntryHi
    mtc0    zero, CP0_ENTRYLO0# 清零 EntryLo0
    mtc0    zero, CP0_ENTRYLO1# 清零 EntryLo1
    nop                       # 解决数据冒险
 
    /* Step 3: Use 'tlbwi' to write CP0.EntryHi/Lo into TLB at CP0.Index  */
    tlbwi                     # 根据 Index 寄存器指示的位置, 即我们要无效化的条目, 将刚才准备好的全 0 数据写入该 TLB 条目, 完成无效化.
 
.set reorder                  # 允许汇编器自动调整指令顺序
 
NO_SUCH_ENTRY:                # 如果没有匹配项, 或者已经写完 TLB, 都会来到这里
    mtc0    t0, CP0_ENTRYHI   # 恢复 EntryHi, 把最开始保存在 t0 里的旧值, 也就是当前进程的上下文写回去
 
    j       ra                # 函数返回
END(tlb_out)                  # 函数结束

TLB 重填

do_tlb_refill 函数完成此工作.

由于 4Kc 中存在的奇偶页设计, 该过程需重填触发异常的页面及其邻居页面.
将两个页面对应的页表项先写入 EntryLo 寄存器，再填入 TLB.

大致流程为:

  1. 从 BadVAddr 中取出引发 TLB 缺失的虚拟地址.
  2. 从 EntryHi 的 0 – 7 位取出当前进程的 ASID.
  3. 先在栈上为返回地址, 待填入 TLB 的页表项以及函数参数传递预留空间, 并存入返回地址. 以存储奇偶页表项的地址, 触发异常的虚拟地址和 ASID 为参数, 调用 _do_tlb_refill 函数.
    该函数是 TLB 重填过程的核心, 其功能是根据虚拟地址和 ASID 查找页表, 将对应的奇偶页表项写回其第一个参数所指定的地址.
  4. 将页表项存入 EntryLo0, EntryLo1, 并执行 tlbwr 将此时的 EntryHi 与 EntryLo0, EntryLo1 写入到 TLB 中 (在发生 TLB 缺失时, EntryHi 已经由硬件写入了虚拟页号等信息, 无需修改).

TLB Refill

再次注意:

PTE 与 TLB Data 映射关系

通过这种设计, 我们可以通过右移, 简单地把 PTE 条目放入 TLB Data.

void _do_tlb_refill(u_long *pentrylo, u_int va, u_int asid)
{
 tlb_invalidate(asid, va);
 Pte *ppte;
 /* Hints:
  *  Invoke 'page_lookup' repeatedly in a loop to find the page table entry '*ppte'
  * associated with the virtual address 'va' in the current address space 'cur_pgdir'.
  *
  *  **While** 'page_lookup' returns 'NULL', indicating that the '*ppte' could not be found,
  *  allocate a new page using 'passive_alloc' until 'page_lookup' succeeds.
  */
 while (!page_lookup(cur_pgdir, va, &ppte)) {
  passive_alloc(va, cur_pgdir, asid);
 }
  
 
 ppte = (Pte *)((u_long)ppte & ~0x7); //   去掉物理地址的低 3 位, 第 4 位为奇偶位.
 pentrylo[0] = ppte[0] >> 6;  // 右移 6 位, 直接去掉软件标志位, 把硬件标志位移动到正确位置.
 pentrylo[1] = ppte[1] >> 6;
}

总结

Kernel initialization

用 mips_detect_memory, mips_vm_init 和 page_init 检测内存资源, 建立空闲页面管理的数据结构, 并且完成初始化.
为后续的访存建立资源池.

User processes

  1. 触发硬件 TLB Miss
    CPU 访存行为: 用户进程执行指令(如 lw t0, (vaddr)), CPU 查找 TLB, 发现没有对应的 VPN+ASID 匹配项.
    对应函数: 无, 触发异常.
  2. 异常处理
    CPU 行为: 硬件自动跳转到特定的异常入口.
    对应函数: do_tlb_refill, 负责保存现场, 并从 CP0_BADVADDR 获取失败地址.
  3. 查询软件页表, 寻找映射
    OS 行为: 在内存里的多级页表中找到这个虚拟地址对应的物理地址.
    对应函数:
    • _do_tlb_refill
    • page_lookup
  4. 按需分配物理地址
    OS 行为: 如果 page_lookup 失败，说明这块内存还没分配.
    对应函数:
    • passive_alloc: 被动分配.
    • page_alloc: 从空闲链表中获取一块物理内存.
    • page_insert: 将这块物理内存挂载到页表对应的位置, 并设置权限位.
    • tlb_invalidate: 清空 TLB 中可能存在的旧表项.
  5. 重填 TLB
    OS 行为: 软件已经把正确的物理地址准备好了, 通知硬件.
    对应函数: 返回到汇编 do_tlb_refill, 将物理页号填入 EntryLo0/1, 用 tlbwr 将条目写入 TLB.

Lab2 in MOS

注意 OS 和硬件 TLB 两套管理机制的关系:

  • CPU 追求效率, 使用 TLB 作为缓存; 缓存不命中是常态.
  • OS 必须维持一套完整的页表作为真相.
  • 联系点:
    • page_insert 改变的是真相(页表).
    • tlb_out, tlb_invalidate 改变的是缓存(TLB).
    • 如果不调用 tlb_invalidate, 即使修改了页表, CPU 可能还在用 TLB 里的旧缓存, 导致错误访问.

关系图谱

反向链接