缺页管理
前置知识：arm的异常机制
arm 把异常分成几种 SYNC，IRQ，FIQ，ERROR
这几个名字都很抽象，先讲SYNC同步异常
什么是同步异常？arm的手册给出的定义是：确定性的(每次执行到那个指令就会产生)，由执行或尝试执行指令引发的，按照预期产生的; 而异步异常则是非确定性，非指令性的，预期之外的
例如电源被踹了一脚断电了，或者时钟定时触发中断，这是异步异常
而访问了不该访问的指令，没有权限或者EL不对，（捕获浮点错误时的）除0，这些是可以溯源到某条指令上的，是同步异常
EL1t和EL1h分别用于实际内核和虚拟机hypervisor模式
对于异步异常，又可以分成中断和错误，最终的概述如下
- sync: 同步异常，如系统调用或页面错误。
- irq: 硬件中断请求（IRQ），由外部设备生成的中断。
- fiq: 快速中断请求（FIQ），用于更高优先级的中断处理。
- error: 处理其他类型的错误，如未定义指令或故障。
下面这个文件实际上也是参考了linux的原始代码
linux ref: https://www.cnblogs.com/charliechen114514-blogs/p/18455517
//chcore中的对应部分 kernel/arch/aarch64/irq/irq_entry.h
#define SYNC_EL1t 0
#define IRQ_EL1t 1
#define FIQ_EL1t 2
#define ERROR_EL1t 3
#define SYNC_EL1h 4
#define IRQ_EL1h 5
#define FIQ_EL1h 6
#define ERROR_EL1h 7
#define SYNC_EL0_64 8
#define IRQ_EL0_64 9
#define FIQ_EL0_64 10
#define ERROR_EL0_64 11
#define SYNC_EL0_32 12
#define IRQ_EL0_32 13
#define FIQ_EL0_32 14
#define ERROR_EL0_32 15
思路设计：如何实现异常管理？
要读懂缺页管理的源代码，不妨先来捋一捋缺页管理的思路
缺页管理实质上是异常管理的一个子集，那异常管理的框架应该怎么设计呢?
首先，要区分异常的类型，正如前面所说的arm的四种异常
- 如果是同步异常，需要回调其对应的处理逻辑（例如demand paging或者COW产生的页异常）
- 如果是用户态触发的异常，不能直接让内核down掉，必须妥善处理
- 如果是内核触发的异常，尝试fix一些提前设计的机制和可以处理的操作，其他的应该down掉
- 如果是中断，需要调用其中断处理逻辑
- 如果是Error，应该down掉
实现机制上，区分内核和用户态看当前是EL0/EL1，同步异常时能得到当前产生异常的指令地址（从对应的寄存器之中读取，arm是FAR_ELx）异常触发的回调应该通过查异常表解决
源码解读
有了这样的机制，接下来就能看懂do_page_fault的代码了，具体细节参见注释
void do_page_fault(u64 esr, u64 fault_ins_addr, int type, u64 *fix_addr)
{
vaddr_t fault_addr;
int fsc; // fault status code
int wnr;
int ret;
// 一个从far_el1寄存器读的汇编的简单包装
fault_addr = get_fault_addr();
// #define GET_ESR_EL1_FSC(esr_el1) (((esr_el1) >> ESR_EL1_FSC_SHIFT) & FSC_MASK)
fsc = GET_ESR_EL1_FSC(esr);
switch (fsc) {
case DFSC_TRANS_FAULT_L0:
case DFSC_TRANS_FAULT_L1:
case DFSC_TRANS_FAULT_L2:
case DFSC_TRANS_FAULT_L3: {
// 地址转换错误，熟悉linux vma设计的同学应该知道，需要根据vma进行进一步处理
ret = handle_trans_fault(current_thread->vmspace, fault_addr);
if (ret != 0) {
// 没有正确处理
/* The trap happens in the kernel */
if (type < SYNC_EL0_64) {
// EL1 的 type, 内核态的异常
goto no_context;
}
// 用户态的异常处理失败简单打印后退出
kinfo("do_page_fault: faulting ip is 0x%lx (real IP),"
"faulting address is 0x%lx,"
"fsc is trans_fault (0b%b),"
"type is %d\n",
fault_ins_addr,
fault_addr,
fsc,
type);
kprint_vmr(current_thread->vmspace);
kinfo("current_cap_group is %s\n",
current_cap_group->cap_group_name);
sys_exit_group(-1);
}
break;
}
case DFSC_PERM_FAULT_L1:
case DFSC_PERM_FAULT_L2:
case DFSC_PERM_FAULT_L3:
// 权限错误
wnr = GET_ESR_EL1_WnR(esr);
// WnR, ESR bit[6]. Write not Read. The cause of data abort.
if (wnr) {
ret = handle_perm_fault(
current_thread->vmspace, fault_addr, VMR_WRITE);
} else {
ret = handle_perm_fault(
current_thread->vmspace, fault_addr, VMR_READ);
}
if (ret != 0) {
/* The trap happens in the kernel */
if (type < SYNC_EL0_64) {
goto no_context;
}
sys_exit_group(-1);
}
break;
case DFSC_ACCESS_FAULT_L1:
case DFSC_ACCESS_FAULT_L2:
case DFSC_ACCESS_FAULT_L3:
// Access faults：没有access bit的pte
kinfo("do_page_fault: fsc is access_fault (0b%b)\n", fsc);
BUG_ON(1);
break;
default:
kinfo("do_page_fault: faulting ip is 0x%lx (real IP),"
"faulting address is 0x%lx,"
"fsc is unsupported now (0b%b)\n",
fault_ins_addr,
fault_addr,
fsc);
kprint_vmr(current_thread->vmspace);
kinfo("current_cap_group is %s\n",
current_cap_group->cap_group_name);
BUG_ON(1);
break;
}
return;
// no_context 这一名称来源于内核的异常处理流程。
// 当内核检测到异常发生在内核态时，它发现没有“用户态上下文”
//（即不是用户程序引发的异常），因此称之为 no_context。
// 这只是一个逻辑分支，用于区分内核态异常的处理流程。
no_context:
kinfo("kernel_fault: faulting ip is 0x%lx (real IP),"
"faulting address is 0x%lx,"
"fsc is 0b%b\n",
fault_ins_addr,
fault_addr,
fsc);
__do_kernel_fault(esr, fault_ins_addr, fix_addr);
}
static void __do_kernel_fault(u64 esr, u64 fault_ins_addr, u64 *fix_addr)
{
kdebug("kernel_fault triggered\n");
// 内核态page fault的时候，查表尝试修复，修复不了就down
if (fixup_exception(fault_ins_addr, fix_addr)) {
return;
}
BUG_ON(1);
sys_exit_group(-1);
}
修复机制通常用于以下场景：
- 内核对用户空间的内存访问：内核可能尝试访问用户空间的内存地址，如果这些地址无效，内核会捕获异常并尝试修复。
- 设备驱动程序：在某些硬件操作中，可能会发生特定的异常（例如设备未准备好）。通过异常修复机制，可以跳过这些异常并执行备用代码。
- 优化代码路径：某些代码路径可能会引发异常，但开发者知道如何正确恢复执行
例如：用户程序有一个空指针，然后以它为参数发起了syscall, 内核在此处触发了page fault错误，最后给出的fix_addr可能就是一段打印Segmentation Fault的代码
练习题9 就是rb_search + rb_entry
至于vmspace, 其数据结构如下
对应源码
/* This struct represents one virtual memory region inside on address space */
struct vmregion {
struct list_head list_node; /* As one node of the vmr_list */
struct rb_node tree_node; /* As one node of the vmr_tree */
/* As one node of the pmo's mapping_list */
struct list_head mapping_list_node;
struct vmspace *vmspace;
vaddr_t start;
size_t size;
/* Offset of underlying pmo */
size_t offset;
vmr_prop_t perm;
struct pmobject *pmo;
struct list_head cow_private_pages;
};
/* This struct represents one virtual address space */
struct vmspace {
/* List head of vmregion (vmr_list) */
struct list_head vmr_list;
/* rbtree root node of vmregion (vmr_tree) */
struct rb_root vmr_tree;
/* Root page table */
void *pgtbl;
/* Address space ID for avoiding TLB conflicts */
unsigned long pcid;
/* The lock for manipulating vmregions */
struct lock vmspace_lock;
/* The lock for manipulating the page table */
struct lock pgtbl_lock;
/*
* For TLB flushing:
* Record the all the CPU that a vmspace ran on.
*/
unsigned char history_cpus[PLAT_CPU_NUM];
struct vmregion *heap_boundary_vmr;
/* Records size of memory mapped. Protected by pgtbl_lock. */
long rss;
};
注意这里的list和rbtree的node都是vmregion的包装，vmspace里面实际上有两组相同的数据list和rbtree
同时维护list和tree也是一个空间换时间的做法，从算法复杂度上看，这样似乎没有什么明显的提升，但如果从缓存的视角上看，在扫描时，list能保证新插入的项被优先遍历，有更强的TLB亲和性
在linux6.1之后，这个rbtree被换成了maple tree(多叉树的变种)
文档中说的
在 ChCore 中，一个进程的虚拟地址空间由多段“虚拟地址区域”（VMR，又称 VMA）组成，一段 VMR 记录了这段虚拟地址对应的“物理内存对象”（PMO），而 PMO 中则记录了物理地址相关信息。因此，想要处理缺页异常，首先需要找到当前进程发生页错误的虚拟地址所处的 VMR，进而才能得知其对应的物理地址，从而在页表中完成映射。
在地址空间vma之中，我们可以保持虚拟地址和物理地址的映射，通过记录下一系列的页面对应的物理地址，从而避免查进程自身空间的页表，不需要保持内核页表和每个进程页表的项的对应。这样的“一系列页面的物理地址”的保存结构就是下面的pmo, 采用的是start+size的方式省空间
/* This struct represents some physical memory resource */
struct pmobject {
paddr_t start;
size_t size;
pmo_type_t type;
/* record physical pages for on-demand-paging pmo */
struct radix *radix;
/*
* The field of 'private' depends on 'type'.
* PMO_FILE: it points to fmap_fault_pool
* others: NULL
*/
void *private;
struct list_head mapping_list;
};
我们继续发现，start+size的结构天生支持COW和on demand paging！具体而言，声明时，只需要记录pmo 的start+size，在pmo之中维护访问过的/没访问的物理地址集合，在出现pagefault的时候分配，并更新这个集合就行
我们需要一个数据结构，他能在一个连续的地址范围之中，标记哪些物理地址是被访问过的（以及拓展地标记更多meta data），chcore采用的是类似linux的radix tree优化，即pmoobject之中的radix
在 Linux 内核中，radix tree（或其改进版本 xarray）被用于管理 page cache 和内存对象（如 PMO，Physical Memory Object）时的地址到页面映射。这种选择的背后是对性能、功能和扩展性的权衡。
思考：从空间开销的角度来说，为什么不用bitmap?
答：核心在于radix tree管理的pmo的地址空间通常是很大一段稀疏的（都启用on demand paging了），这对bitmap非常不友好，而radix tree对稀疏和懒分配有很好的支持。此外，bitmap只能标记存在与否，而radix tree可以存指针达到更灵活的元数据管理
#define RADIX_LEVELS (DIV_ROUND_UP(RADIX_MAX_BITS, RADIX_NODE_BITS))
// 64位地址，4位level的radix tree
struct radix_node {
union {
struct radix_node *children[RADIX_NODE_SIZE]; // 空间复用，位操作做查询等
void *values[RADIX_NODE_SIZE];
};
};
struct radix {
struct radix_node *root;
struct lock radix_lock;
void (*value_deleter)(void *);
};
是否忘了整个流程是干什么的？接下来重新走一次处理缺页异常的流程
- 触发缺页异常
- 异常被归类为SYNC_EL0/SYNC_EL1 + TRANS异常，分别对应用户态和内核态，区别只是在最坏情况有无尝试修复
- 异常处理函数从far_el1寄存器获取出错指令(此处应该是访存)的虚拟地址fault_addr，从当前的线程cur_thread获取工作的vmspace(vma)
- 异常处理函数调用handle_trans_fault继续处理
- 有了vmspace和vaddr, 可以找到对应的vmregion和pmo, 也就找到了对应的物理地址空间对象
- 接下来根据pmo的类型进行进一步判断，注意可能出现并发pagefault, 这里的语义处理根据不同type还会发生变化：例如如果是同个进程的多个线程，且类型为PMO_ANONYM(匿名内存，cow语义)，那只需要第一个线程更新radix就够了; 如果是跨进程的线程，根据cow语义，需要各自更新各自的
- 查询radix tree内是否已经存在记录，如果存在（在PHO_SHM共享内存的时候，多个进程的物理页面是相同的， 即各自的vma引用同一个pmo，所以并发场景 下后来的线程会出现pa已经在radix之中存在的情况），就只需要在自己的页表中设置页表映射（这是并发安全的，“设置”可重入）; 否则为这个on demand paging的页面分配空间， 更新radix tree和pagetable
- 处理完毕，重新尝试翻译这个地址，此时因为已经更新pagetable, 应该能成功翻译
step67的对应源码如下
int handle_trans_fault(struct vmspace *vmspace, vaddr_t fault_addr)
{
struct vmregion *vmr;
struct pmobject *pmo;
paddr_t pa;
unsigned long offset;
unsigned long index;
int ret = 0;
/*
* Grab lock here.
* Because two threads (in same process) on different cores
* may fault on the same page, so we need to prevent them
* from adding the same mapping twice.
*/
lock(&vmspace->vmspace_lock);
vmr = find_vmr_for_va(vmspace, fault_addr);
if (vmr == NULL) {
kinfo("handle_trans_fault: no vmr found for va 0x%lx!\n",
fault_addr);
dump_pgfault_error();
unlock(&vmspace->vmspace_lock);
#if defined(CHCORE_ARCH_AARCH64) || defined(CHCORE_ARCH_SPARC)
/* kernel fault fixup is only supported on AArch64 and Sparc */
return -EFAULT;
#endif
sys_exit_group(-1);
}
pmo = vmr->pmo;
/* Get the offset in the pmo for faulting addr */
offset = ROUND_DOWN(fault_addr, PAGE_SIZE) - vmr->start + vmr->offset;
vmr_prop_t perm = vmr->perm;
switch (pmo->type) {
case PMO_ANONYM:
case PMO_SHM: {
/* Boundary check */
BUG_ON(offset >= pmo->size);
/* Get the index in the pmo radix for faulting addr */
index = offset / PAGE_SIZE;
fault_addr = ROUND_DOWN(fault_addr, PAGE_SIZE);
pa = get_page_from_pmo(pmo, index);
if (pa == 0) {
/*
* Not committed before. Then, allocate the physical
* page.
*/
void *new_va = get_pages(0);
long rss = 0;
if (new_va == NULL) {
unlock(&vmspace->vmspace_lock);
return -ENOMEM;
}
pa = virt_to_phys(new_va);
BUG_ON(pa == 0);
/* Clear to 0 for the newly allocated page */
memset((void *)phys_to_virt(pa), 0, PAGE_SIZE);
/*
* Record the physical page in the radix tree:
* the offset is used as index in the radix tree
*/
kdebug("commit: index: %ld, 0x%lx\n", index, pa);
commit_page_to_pmo(pmo, index, pa);
/* Add mapping in the page table */
lock(&vmspace->pgtbl_lock);
map_range_in_pgtbl(vmspace->pgtbl,
fault_addr,
pa,
PAGE_SIZE,
perm,
&rss);
vmspace->rss += rss;
unlock(&vmspace->pgtbl_lock);
} else {
/*
* pa != 0: the faulting address has be committed a
* physical page.
*
* For concurrent page faults:
*
* When type is PMO_ANONYM, the later faulting threads
* of the process do not need to modify the page
* table because a previous faulting thread will do
* that. (This is always true for the same process)
* However, if one process map an anonymous pmo for
* another process (e.g., main stack pmo), the faulting
* thread (e.g, in the new process) needs to update its
* page table.
* So, for simplicity, we just update the page table.
* Note that adding the same mapping is harmless.
*
* When type is PMO_SHM, the later faulting threads
* needs to add the mapping in the page table.
* Repeated mapping operations are harmless.
*/
if (pmo->type == PMO_SHM || pmo->type == PMO_ANONYM) {
/* Add mapping in the page table */
long rss = 0;
lock(&vmspace->pgtbl_lock);
map_range_in_pgtbl(vmspace->pgtbl,
fault_addr,
pa,
PAGE_SIZE,
perm,
&rss);
vmspace->rss += rss;
unlock(&vmspace->pgtbl_lock);
}
}
if (perm & VMR_EXEC) {
arch_flush_cache(fault_addr, PAGE_SIZE, SYNC_IDCACHE);
}
break;
}
case PMO_FILE: {
unlock(&vmspace->vmspace_lock);
fault_addr = ROUND_DOWN(fault_addr, PAGE_SIZE);
handle_user_fault(pmo, ROUND_DOWN(fault_addr, PAGE_SIZE));
BUG("Should never be here!\n");
break;
}
case PMO_FORBID: {
kinfo("Forbidden memory access (pmo->type is PMO_FORBID).\n");
dump_pgfault_error();
unlock(&vmspace->vmspace_lock);
sys_exit_group(-1);
break;
}
default: {
kinfo("handle_trans_fault: faulting vmr->pmo->type"
"(pmo type %d at 0x%lx)\n",
vmr->pmo->type,
fault_addr);
dump_pgfault_error();
unlock(&vmspace->vmspace_lock);
sys_exit_group(-1);
break;
}
}
unlock(&vmspace->vmspace_lock);
return ret;
}