MIPS Q&A

About MIPS32.

Page Fault

What is a page fault ?

A page fault is an exception that MMU raises when a process accesses a memory page without proper preparations.

Accessing the page requires:

  1. A mapping be added to the process’s virtual address space.
  2. The actual page contents be loaded from a back-up, e.g. a disk.

The page fault is detected by the memory management unit (MMU), and the exception is handled by the OS kernel by making the required page accessible in the physical memory or denying an illegal memory access.

Types of page faults include:

  1. Minor (or Soft): The page is loaded in memory, but not marked in MMU. This could happen if the memory is shared by different programs, and other programs have already mapped it into their own address space.
  2. Major (or Hard): The page is mapped in the virtual address space of a program, but the data has not been loaded into physical memory yet. The page fault handler in the OS needs to find a free location: either a free page in memory, or a non-free page in memory. Major faults are more expensive than minor faults and add storage access latency to the interrupted program’s execution.
  3. Invalid: If a page fault occurs for a reference to an address that is not part of the virtual address space, meaning there cannot be a page in memory corresponding to it, then it is called an invalid page fault.

Memory Management Unit (MMU)

We first discuss MMUs of different architectures. In terms of TLB, MMUs can be divided into two categories[1]:

  1. Hardware-Managed TLB (most ISAs): Hardware is (at least partially) involved in PTE lookup and TLB maintenance. A PTW FSM is maintained to handle TLB misses, eliminating the need to flush the pipeline and save context to enter the interrupt handler. Most PTWs directly use PAs rather than VAs to access the page table, avoiding the VA-to-PA translation for the page table. PTW needs to know the base address of the page table, so the ISA usually provides a control register that is configured by the OS kernel as part of the context switch, such as CR3 on x86, TTBR0 and TTBR1 on ARM.
  2. Software-Managed TLB (MIPS): PTEs are used and maintained by the OS kernel and all address translations are done through TLBs. Once a TLB miss occurs, an exception is triggered and the OS kernel looks up PTEs, then maintains the TLB. Software-managed TLBs have poor performance, and each TLB miss requires a context switch by the operating system.

硬件维护 TLB 提供了性能和便利性，如直接修改 CR3 实现不同地址空间的切换，劣势是减少了页表组织方式的灵活性。

现代体系结构多为多级页表，避免了大量索引连续地址空间造成的页表项浪费，如 Linux x86-64[2] 默认的 PDG - PUD - PMD - PTE ( 四级页表 )，ARM32[3] 默认的 PGD - PTE. 这里简化了模型，只讨论 PTE - TLB.

MIPS Page Fault

发生 page fault 时，页表的状态可能为

  1. 没有对应表项
  2. 该 VA 被使用过，但已被清除

对于硬件维护的 TLB，发生 TLB miss 时可以尝试查找 PTE，查询失败则触发缺页中断。而 MIPS 中没有明确定义该异常，其缺页处理过程由数个 TLB 异常组成。

首先，查找 TLB Entry 失败。这一步可能是由多种原因构成的，因为 MIPS 所有地址翻译都经过 TLB，而 TLB 作为 PTE 缓存，可能只是有效页表项被逐出导致的 TLB miss，由 OS kernel 查找 PTE 重新填入 TLB 即可。

如果确为缺页，根据对 TLB Invalid 异常的分析，MIPS 应该并没有在此时处理缺页。

TLB Invalid Exception

The TLB invalid exception occurs when a virtual address reference matches a TLB entry that is marked invalid (TLB valid bit cleared). This exception is not maskable.[4]

A TLB entry is typically marked invalid when one of the following is true:

  • a virtual address does not exist
  • the virtual address exists, but is not in main memory (page fault)
  • a trap is desired on any reference to the page (for example, to maintain a reference bit)

After servicing the cause of a TLB Invalid exception, the TLB entry is located with TLBP (TLB Probe), and replaced by an entry with that entry’s Valid bit set.

所有页表项只有在确定被使用时，OS kernel 才会给它分配物理页的空间。通过 TLB Invalid 异常实现该功能，首次填入 TLB 的页表项的 PFN | C | D | V 均为 0，处理异常后，Valid 被置位。

MIPS 缺页中断过程

至此，分析 MIPS 缺页中断过程。

  1. 缺页时必然触发 TLB Miss. 这一步只意味着 PTE 缓存未命中，尚不能确定是否为缺页
  2. OS kernel 执行 TLB Miss 的异常处理，因为是缺页，页表中没有有效表项，则填入一个 Valid = 0 的 TLB Entry
  3. 从异常恢复后，CPU 重新访问触发 TLB Miss 的 VA，此时触发 TLB Invalid
  4. OS kernel 执行 TLB Invalid 的异常处理，正式处理缺页

这一过程的效率是比较低下的，软件管理 TLB 的弊端。在 x86 中，缺页过程要简化不少，TLB Miss → PTE Miss 后，直接触发缺页异常。我们分析，不直接在 TLB Miss 处理缺页的原因可能是 TLB Refill (TLB Miss) 不能写太多汇编，所以放在 TLB Invalid 中处理。

实际的 MIPS 缺页中断可能还嵌套其他异常。由于页表维护在 kseg2，该地址段也经过虚实地址转换，因此可能触发 TLB Miss 嵌套。注意，第二次 TLB Miss 并不是因为缺页触发的。

TLB Modified Exception

另一个异常是 TLB Modified Exception. 这个异常和缺页没有直接关系，但 CPU 设计实战 对其的描述似乎有些问题，在此处做记录。

The TLB modified exception occurs when a store operation virtual address reference to memory matches a TLB entry that is marked valid but is not dirty and therefore is not writable. This exception is not maskable.

通过以上描述可知， TLB Modified 异常在尝试 STORE 只读地址时触发，并非某书所描述的检查脏位，优化存储管理过程。这应是由 Cache 负责的。

The End

花了两天时间分析并整理了 MIPS 缺页中断过程，仍然感觉很无力，细节之处，推测偏多，难以查找相关资料。以后若有时间，希望能对着 ISA 手册和 Linux 源码细细走一遍。

其他参考资料 [5] [6] [7]

访存指令

地址对齐

Why address alignment ?

硬件对存储单元的实现是字对齐的。如果访存不是字对齐的，则一条跨边界的访存指令可能需要两次内存访问才能完成。

这可能对应两个 Cache Line 或两个 TLB Entry 的访问，任一个访问均有可能 miss；或两个独立的总线访问事务，两者的完成顺序可能和发起顺序不一致。地址不对齐的 MMU 设计需对以上情况进行讨论，提高硬件复杂性。

[Author] 地址对齐可通过砍掉地址低位而压缩寻址编码长度，提高访存指令可扩展性。

跨边界访存

然而，字对齐并不总是被严格保证。为避免处理非对齐访存时引入复杂的硬件访存模型，MIPS32 继续发扬 RISC 思想，将一次非对齐访存分解为两次半字访存，由软件自行控制。保证每条 inst 只解码一个 μop，同时只对应一次 RAM 访问。

一般 LWL / LWR 配合使用，SWL / SWR 配合使用。注意机器字节序对数据高低位的影响。

LWL/LWR

半字 LW 引入新问题，即如何实现目的寄存器的部分更新。提出两个方案。

  1. 为 regfile 添加字节写使能
  2. 先读 $target，拼接后写回

方案 1 很好，因为即使 LWL 与 LWR 连用 ( 一般如此 )，也仅仅是 WAW，并且由于写使能有字节粒度，甚至可认为是没有相关产生的。

考虑功耗。

简单地，CPU 这样的数字逻辑电路功耗可分为静态功耗和动态功耗，时钟网络功耗和触发器动态功耗在 CPU 动态功耗中占比显著。

时钟门控允许在除法器不需要更新时关闭其时钟，对 MIPS32，寄存器堆有 32 个时钟门控。如果写使能达到字节级，则门控升至 128 个，功耗不降反增。

考虑 LWL / LWR 出现频率不高，可通过控制代码来保持门控仍为 32 个。

方案 2 会引入阻塞，这因为 LWL 需要等待访存级才能前递，如果继续流动，此时 LWR 已经位于执行级，这是不可能的，因为形成了 RAW，必须阻塞一拍。方案 2 的优势在于数据通路复用，且设计简单。

SWL/SWR

和其他 STORE 指令作相同处理即可，没有引入半字 LW 的相关。

  1. 虚拟内存的架构和操作系统支持 笔记（三）：现代虚拟内存的硬件实现 | Li Shi ↩︎

  2. notes/kernel/mm/mm_pagetable.md at master · freelancer-leon/notes ↩︎

  3. linux-4.x.y/arch/arm/mm/mmu.c/README.md at master · novelinux/linux-4.x.y ↩︎

  4. -TLB Exceptions ↩︎

  5. x86中的页表结构和页表项格式 - VinoZhu - 博客园 ↩︎

  6. 4.3 页表（Page Table） | MIT6.S081 ↩︎

  7. Mips TLB miss异常 ↩︎