Speed up system calls (easy)
目标是在用户空间和内核间共享一块只读的区域，这样内核执行SYSCALL的时候就不需要来回跑。当每个进程被创立的时候，都会在USYSCALL区域映射一块只读的分页，这里面存了一个结构体usyscall用来存储当前进程的pid。
提示让我们先看kernel/proc里的proc_pagetable()函数,那么先去看看。
proc_pagetable()
// Create a user page table for a given process,
// with no user memory, but with trampoline pages.
pagetable_t
proc_pagetable(struct proc *p)
{
pagetable_t pagetable;
// An empty page table.
pagetable = uvmcreate();
if(pagetable == 0)
return 0;
// map the trampoline code (for system call return)
// at the highest user virtual address.
// only the supervisor uses it, on the way
// to/from user space, so not PTE_U.
if(mappages(pagetable, TRAMPOLINE, PGSIZE,
(uint64)trampoline, PTE_R | PTE_X) < 0){
uvmfree(pagetable, 0);
return 0;
}
// map the trapframe just below TRAMPOLINE, for trampoline.S.
if(mappages(pagetable, TRAPFRAME, PGSIZE,
(uint64)(p->trapframe), PTE_R | PTE_W) < 0){
uvmunmap(pagetable, TRAMPOLINE, 1, 0);
uvmfree(pagetable, 0);
return 0;
}
if(mappages(pagetable, USYSCALL, PGSIZE, (uint64)(p->usyscall), PTE_R | PTE_U) < 0){
// 映射完成后，我们访问 USYSCALL 开始的页，就会访问到 p->usyscall
uvmunmap(pagetable, TRAMPOLINE, 1, 0);
uvmunmap(pagetable, TRAPFRAME, 1, 0);
uvmfree(pagetable, 0);
return 0;
}
return pagetable;
}
根据注释可以获得信息，这个函数为给定进程创建了一个用户页表，但是并不初始化其用户内存，只是存放一点trampoline，trapframe之类的信息。我们的任务就是让其再存放一个usyscall的结构体，并且往里面塞入pid，这些都是内核和用户共享的空间。
其实不用管，照抄给的代码就行了，但还是解释一下，这里的uvmunmap() 函数的作用是取消之前成功映射的页面，在出现错误时进行回滚。具体来说，它用于解除映射并清理资源，防止资源泄漏，确保系统内存和页表的管理正确。
提示还让看allocproc()这个函数，我们也来看看
allocproc()
// Look in the process table for an UNUSED proc.
// If found, initialize state required to run in the kernel,
// and return with p->lock held.
// If there are no free procs, or a memory allocation fails, return 0.
static struct proc*
allocproc(void)
{
struct proc *p;
for(p = proc; p < &proc[NPROC]; p++) {
acquire(&p->lock);
if(p->state == UNUSED) {
goto found;
} else {
release(&p->lock);
}
}
return 0;
found:
p->pid = allocpid();
p->state = USED;
// Allocate a trapframe page.
if((p->trapframe = (struct trapframe *)kalloc()) == 0){
freeproc(p);
release(&p->lock);
return 0;
}
// 分配 usyscall
if((p->usyscall = (struct usyscall *)kalloc()) == 0) {
freeproc(p);
release(&p->lock);
return 0;
}
p->usyscall->pid = p->pid;
// 创建完了顺便把 pid 直接放进去
// An empty user page table.
// 给进程分配一个页表
p->pagetable = proc_pagetable(p);
if(p->pagetable == 0){
freeproc(p);
release(&p->lock);
return 0;
}
// Set up new context to start executing at forkret,
// which returns to user space.
memset(&p->context, 0, sizeof(p->context));
p->context.ra = (uint64)forkret;
p->context.sp = p->kstack + PGSIZE;
return p;
}
观察可知，这个函数是用来创建一个新的进程的，它负责找到一个未使用的进程表项，将其状态设置为 USED，并为新进程分配内存、页表等必要资源。照猫画虎，直接就能分配usyscall页，并且往里面塞点东西。
所以这时候分配的新进程还是在使用虚拟地址？
是的，这个时候新分配的进程仍然使用虚拟地址。我们可以从以下几点看到这一点：
-
页表的分配：在 allocproc() 函数中，为新进程分配了一个新的用户页表，具体通过 proc_pagetable(p) 函数来完成。这个页表管理该进程的虚拟地址空间。当进程在用户态运行时，它会使用这个页表来映射虚拟地址到物理地址。即使在内核中，虚拟地址也是通过内核的页表映射到物理地址的。
-
内核栈的使用：在 allocproc() 中初始化了进程的内核栈（p->kstack），栈指针（sp）被设置为内核栈的虚拟地址 p->kstack + PGSIZE，而不是物理地址。这也是使用虚拟地址的一个例子。
-
trapframe 和 usyscall：这些结构也通过 kalloc() 分配，并且返回的是虚拟地址。这些虚拟地址是在内核空间中，由内核管理的内存区域的一部分。
什么时候一个进程才会被分配进物理内存，哪里看到相关部分的代码?
-
页表分配时：当进程的页表建立时，虚拟地址空间中的某些页面会被映射到物理内存。这时，内核会为进程分配实际的物理页。
-
懒分配（Lazy Allocation）：有些情况下，系统不会立即为进程分配物理内存，而是等到进程访问某个虚拟地址时再分配对应的物理页。这时，发生页面错误（page fault），操作系统会通过处理页面错误的方式分配物理内存。
1. 页表分配时的物理内存分配
在 allocproc() 函数中，我们可以看到通过 proc_pagetable(p) 为进程创建一个页表。这并不会立即为用户空间的虚拟地址分配物理内存，但是进程的某些关键数据结构（如内核栈和 trapframe）确实已经分配了物理内存。
2. 懒分配（Lazy Allocation）和页面错误
在 xv6 中，物理内存的懒分配通常发生在访问一个未分配的页面时，通过页面错误机制进行处理。关键的代码可以在 trap.c 中找到，尤其是处理 page fault 的部分。
通常流程是：
-
进程访问一个尚未映射的虚拟地址时，硬件会触发一个页面错误（trap）。
-
操作系统通过 trap() 函数捕捉到这个错误，并在 trap.c 中进行处理。
-
如果需要为该页分配物理内存，操作系统会在此时调用类似于 uvmalloc() 或 kalloc() 的函数来分配实际的物理页，并更新页表。
-
kalloc()：用于分配内核中的物理页。
-
uvmalloc()：用于给用户虚拟地址分配物理页，并且会更新进程的页表来完成虚拟地址到物理地址的映射。
3. 物理内存分配的函数
在 xv6 中，物理内存的分配通过 kalloc() 函数完成，这个函数在 kalloc.c 中实现。它管理物理内存的分配，通常以页为单位分配。
做到这里的时候，我有一个疑问，分配物理地址之前，程序到底在哪，我无法理解程序现在虚拟地址上然后再被转移到物理内存这个概念。我们写的内核不就是程序吗，难道运行内核的时候内核本身不在物理内存里面？
答案是在磁盘里，但是我目前还无法理解。
Print a page table (easy)
这个很简单，只需要在kernel/vm.c里面新加一个vmprint()函数就好了，可以用dfs搜索，我用的是三层循环。
void vmprint(pagetable_t pagetable)
{
printf("page table %p\n", pagetable);
for (int i = 0; i < 512; i++)
{
pte_t pte0 = pagetable[i];
if (pte0 & PTE_V)
{
// this PTE points to a lower-level page table.
uint64 child = PTE2PA(pte0);
printf("..%d: pte %p pa %p\n", i, pte0, child);
pagetable_t pagetable1 = (pagetable_t)child;
//二级页表的循环部分
for (int j = 0; j < 512; j++)
{
pte_t pte1 = pagetable1[j];
if (pte1 & PTE_V)
{
uint64 child1 = PTE2PA(pte1);
printf(".. ..%d: pte %p pa %p\n", j, pte1, child1);
pagetable_t pagetable2 = (pagetable_t)child1;
// 三级页表循环部分
for (int z = 0; z < 512; z++)
{
pte_t pte2 = pagetable2[z];
// 检查三级页表的有效性
if (pte2 & PTE_V)
{
uint64 child2 = PTE2PA(pte2);
printf(".. .. ..%d: pte %p pa %p\n", z, pte2, child2);
}
}
}
}
}
}
}
Detecting which pages have been accessed (hard)
应该就是记录哪些页被访问过
我们要实现在kernel/sysproc.c里面的sys_pgaccess()函数，这个函数接受三个参数，第一个参数是第一个需要check的用户页的虚拟地址，第二个参数是需要检查的页的数量，第三个参数是一个用户空间中的缓冲区地址，用于存储检查结果的位掩码。每一页对应掩码中的一位，最小的页对应最低有效位（least significant bit）。
注意，在将访问信息更新到bitmask以后，要将PTE_A的参数重制，不然每次访问都会是最近访问过。
一开始我无法理解这里第三个参数到底要我干嘛。后来才发现，定义了一个int类型的bitmask，每一位就对应了一个页的access参数，比如0...001，就代表我们访问的第一个页面的acceess为1，也就是最近访问过的，0...010，就代表第二个页面最近访问过。
int
sys_pgaccess(void)
{
// lab pgtbl: your code here.
uint64 va;
int npages;
uint64 uaddr;
//arg err
if ((argaddr(0, &va) < 0) | (argint(1, &npages) < 0) | (argaddr(2, &uaddr))) {
return -1;
}
// get thte bitmask
uint64 bitmask = 0;
for (int i = 0; i < npages; i++) {
pte_t *pte = walk(myproc()->pagetable, va + i * PGSIZE, 0);
if (pte && (*pte & PTE_V) && (*pte & PTE_A)) {
bitmask |= (1 << i); // 设置位掩码中的对应位
*pte ^= PTE_A;
}
}
if (copyout(myproc()->pagetable, uaddr, (char*)&bitmask, sizeof(bitmask)) < 0)
return -1;
return 0; // 成功
}
