Horbynz hub

⌈xv6-fall2021⌋ lab 3：Page tables

xv6
Word count: 3.4kReading time: 15 min
2022/03/25

LAB

传送门：Lab: page tables


Speed up system calls (EASY)

要求

When each process is created, map one read-only page at USYSCALL (a VA defined in memlayout.h). At the start of this page, store a struct usyscall (also defined in memlayout.h), and initialize it to store the PID of the current process. For this lab, ugetpid() has been provided on the userspace side and will automatically use the USYSCALL mapping. You will receive full credit for this part of the lab if the ugetpid test case passes when running pgtbltest.

“每当有进程创建后，就在 USYSCALL 处映射一个只读页（USYSCALL 是 memlayout.h 定义的一个宏）。该只读页的开始处，存储一个 usyscall 的结构体（同样也是定义在 memlayout.h），还需要存储当前进程的 PID 以完成初始化。对于这个 lab，用户态下提供的 ugetpid() 会自动使用 USYSCALL 映射。如果你在运行 pgtbltest 脚本时， ugetpid() 通过则你会得到全部分数”

整理一下要求，其实就是在用户进程空间中新增一项（本文暂且称为缓存项，因为看题意加速就是通过缓存实现的） USYSCALL，该缓存项映射到某个只读页，而在只读页上记录 usyscall 结构体。下面给出新增缓存项前后的用户空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 原用户空间     -> 新增缓存项后的用户空间
/*
 * ┌──────────┐     ┌──────────┐
 * │trampoline│     │trampoline│
 * ├──────────┤     ├──────────┤
 * │trapframe │     │trapframe │
 * ├──────────┤     ├──────────┤
 * │          │     │USYSCALL  │
 * │heap      │     ├──────────┤
 * │          │     │heap      │
 * ├──────────┤     ├──────────┤
 * │stack     │     │stack     │
 * ├──────────┤     ├──────────┤
 * │data & bss│     │data & bss│
 * ├──────────┤     ├──────────┤
 * │text      │     │text      │
 * └──────────┘     └──────────┘
 */

提示

You can perform the mapping in proc_pagetable() in kernel/proc.c.

“在 kernel/proc.c 的 proc_pagetable() 里执行映射”

这里 “执行映射” 其实就是安装映射的意思，就是创建一个从 USYSCALL 到实际缓存项只读页的映射，这里其实参考 kernel/proc.c/proc_pagetable() 里面其他映射的安装就知道怎么做了

Choose permission bits that allow userspace to only read the page.

“选择允许用户程序访问只读页的权限位”

这里是 PTE_U 和 PTE_R，用户空间可访问以及只读

Don’t forget to allocate and initialize the page in allocproc().

“在 allocproc() 分配一页并且初始化”

Make sure to free the page in freeproc().

“确保在 freeproc() 释放该页”


Summary

整个 assignment 看起来要求不高，唯一困难的是可能你需要认真阅读 proc_pagetable()，allocproc() 和 freeproc() 这三个函数：

  • proc_pagetable()：这个函数就是创建一个页表，页表只初始化 trampoline 和 trapframe 两个 PTE
  • allocproc()：这个函数就是从进程数组里找到空闲的进程，然后对该进程初始化（其实就是填充 proc 结构体）
  • freeproc()：这个函数作用是释放给定进程

现在，只需要在这三个函数内完成 “提示” 所要求的内容即可，不过有几个细节的地方要注意：

  • 像 USYSCALL 和 struct usyscall 这些内容官方都是用条件编译（#ifdef LAB_PGTBL）括起来的，所以谨慎起见，这个 assignment 里添加的内容也这么括起来比较好（或者把官方的条件编译删掉，这样以后切换去其他 branch 应该也不会报错）
  • allocproc() 按提示是 “分配并初始化 USYSCALL 页”，然后 proc_pagetable() 按提示是 “安装映射”。但是这里有两个棘手的问题，第一个是新创建的页面需要在两个函数内传递，这需要考虑引入一个全局变量之类的东西保存；第二个是在只读页开头处需要保存 struct usyscall 结构体，但问题是这个只读页我们只能得到物理地址（uint64 * 类型），如何将一个其他类型的变量保存于某个指针处，我现在所能想到的只有 memmove() 之类的内存函数，可能处理起来比较繁琐。所以这里我参考其他大神的思路决定作出些简化，那就是，直接在 struct proc 结构体新增一个成员变量保存 struct usyscall 结构体而不保存只读页物理地址了，这样读写 struct usyscall 结构体变量会变成非常方便

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// path: kernel/proc.h
struct proc {
    ...
#ifdef LAB_PGTBL
    // 新增一个成员变量保存 struct usyscall 结构体
    struct usyscall *share;
#endif
    ...
};

// path: kernel/proc.c
// 要修改的第一个函数
static struct proc*
allocproc(void) {
    ...
#ifdef LAB_PGTBL
    // 创建一个 "只读页"，事实上没有创建页，这里只是简化的实现
    if((p->share = (struct usyscall *)kalloc()) == 0){
        freeproc(p);
        release(&p->lock);
        return 0;
    }
    p->share->pid = p->pid;
#endif
    ...
}
// 要修改的第二个函数
static void
freeproc(struct proc *p) {
    ...
#ifdef LAB_PGTBL
    if (p->share)
        kfree((void *)p->share);
    p->share = 0;
#endif
    ...
}
// 要修改的第三个函数
void
proc_freepagetable(pagetable_t pagetable, uint64 sz) {
    ...
#ifdef LAB_PGTBL
    uvmunmap(pagetable, USYSCALL, 1, 0);
#endif
    ...
}
// 要修改的第四个函数
pagetable_t
proc_pagetable(struct proc *p) {
    ...
#ifdef LAB_PGTBL
    // 添加从 USYSCALL 到 struct proc 的成员变量 share 的映射
    if(mappages(pagetable, USYSCALL, PGSIZE,
                (uint64)(p->share), PTE_R | PTE_U) < 0){
        uvmunmap(pagetable, USYSCALL, 1, 0);
        uvmunmap(pagetable, TRAMPOLINE, 1, 0);
        uvmfree(pagetable, 0);
        return 0;
    }
#endif
    ...
}

Print a page table (EASY)

要求

Define a function called vmprint(). It should take a pagetable_t argument, and print that pagetable in the format described below. Insert if(p->pid==1) vmprint(p->pagetable) in exec.c just before the return argc, to print the first process’s page table. You receive full credit for this part of the lab if you pass the pte printout test of make grade.

“定义一个叫做 vmprint() 的函数。它带一个 pagetable_t 类型的参数，并且用下面给出的格式打印这个页表参数。在 kernel/exec.c 的 return argc; 前面插入 if(p->pid == 1) vmprint(p->pagetable) 以打印第一个进程的页表。如果你在 make grade 的 ‘pte printout’ 测试中通过，你会得到这一节的满分”

以下是页表的打印格式，同时也是你刚启动 xv6 后 shell 上面要输出的内容（物理地址可以不同，但 PTE 索引和虚拟地址需要保持一致才算对）：

1
2
3
4
5
6
7
8
9
10
11
page table 0x0000000087f6e000
 ..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
 .. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
 .. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
 .. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
 .. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
 ..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
 .. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
 .. .. ..509: pte 0x0000000021fdd813 pa 0x0000000087f76000
 .. .. ..510: pte 0x0000000021fddc07 pa 0x0000000087f77000
 .. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000

第一行是形参

随后每一行对应一个 PTE，每个 PTE 由三部分组成：

  • 第一部分是诸如 “… …511:” 之类的缩进格式，这是三层页表的层次树，“511” 表示当前 PTE 是它所在页表的下标 511 号条目
  • 第二部分是 “pte …”，这是对应 PTE 条目里面的内容
  • 第三部分是 “pa …”，这是 PTE 对应的物理地址

这个例子说明了最高级页表只有下标 0 和 255 两项 PTE 存在（即 PTE_V 置位），下标 0 PTE 的下级页表只有 PTE 为下标 0 的一项，再下级页表只有 0、1、2 三项 PTE 存在；对于最高级页表 255 号索引也是同理


提示

The function freewalk may be inspirational.

“函数 freewalk() 是非常有用的”

这里不是说打印页表需要调用 freewalk() 进行释放，而是这个函数递归遍历每一层页表这个思想非常有参考意义

此处给出页表机制原理（注意页表地址和虚拟地址不同，页表地址是下图红框处，虚拟地址是下图蓝框处）：

再结合代码来理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void
freewalk(pagetable_t pagetable)
{
    for(int i = 0; i < 512; i++){
        pte_t pte = pagetable[i];
        if((pte & PTE_V) && (pte & (PTE_R|PTE_W|PTE_X)) == 0){
            // 若当前 PTE 标志位全零，那就是一级或二级页表的页表项

            uint64 child = PTE2PA(pte);// 提取 PTE 里面的物理地址
            freewalk((pagetable_t)child);
            pagetable[i] = 0;
        } else if(pte & PTE_V) {
            // 反之若当前 PTE 标志位但凡有一个是非零，那就说明到达第三级页表了
            panic("freewalk: leaf");
        }
    }
    kfree((void*)pagetable);
}

这里我加了注释，可能你会疑惑，为什么通过标志位是否全零可以判断到达了最后一级页表呢？这和 walk() PA2PTE()、PTE2PA() 这些宏函数有关。由于这些宏函数实际上是通过左移右移使一个 64 位的数据迎合 sv39 的页表机制，而这个移位是补零的（因为这是一个 uint64）———— 最终会使标志位变成全零

但这里只要知道这种思想就行了，实际上我没有这样实现，我用了更简单的计数器的方法来实现当前是第几层

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// path: kernel/exec.c
#ifdef LAB_PGTBL
    if (p->pid == 1)
        vmprint(p->pagetable);
#endif

// kernel/defs.h
// vm.c 注释处
#ifdef LAB_PGTBL
void vmprint(pagetable_t);
#endif

// kernel/vm.c
void 
subvmprint(pagetable_t pagetable, int dot) {
    if (dot > 3)    return;

    for(int i = 0; i < 512; i++) {
        pte_t pte = pagetable[i];
        if(pte & PTE_V) {
            // 打点
            for (int j = 0; j < dot; ++j) {
                if (j != 0)    printf(" ");
                printf("..");
            }

            // 打印索引
            printf("%d: ", i);

            // 打印 pte
            printf("pte %p ", pte);

            // 打印 pa
            uint64 child = PTE2PA(pte);// 提取 PTE 里面的物理地址
            printf("pa %p\n", child);
            subvmprint((pagetable_t)child, dot + 1);
        }
    }
}

void 
vmprint(pagetable_t pagetable) {
    printf("page table %p\n", pagetable);

    subvmprint(pagetable, 1);
}

Detecting which pages have been accessed (HARD)

要求

Your job is to implement pgaccess(), a system call that reports which pages have been accessed. The system call takes three arguments. First, it takes the starting virtual address of the first user page to check. Second, it takes the number of pages to check. Finally, it takes a user address to a buffer to store the results into a bitmask (a datastructure that uses one bit per page and where the first page corresponds to the least significant bit). You will receive full credit for this part of the lab if the pgaccess test case passes when running pgtbltest.

“你的任务是实现 pgaccess()，一个能报告访问过哪一页的系统调用。这个系统调用接受三个参数：第一个是要检查的用户页的第一页；第二个是要检查的页数量；第三个是存放结果的地址，这个地址其实是一个位掩码的数据结构，每个待检查页对应一位，第一页对应于最低有效位。当你运行 pgtbltest 脚本时，如果你能通过 pgaccess 测试，你就会得到这个 assignment 的满分”

这里困难是读懂存放位掩码的这个数据结构的设置要求，我们可以观察 user/pgtbltest.c/pgaccess_test() 的调用代码 ———— pgaccess(buf, 32, &abits) 第三个参数就是位掩码，通过定义 unsigned int abits 可以发现其实是个无符号整型，这让我想起了第二个 lab syscalls：System call tracing 的掩码，其实就是同样的思想，在此不再赘述


提示

walk() in kernel/vm.c is very useful for finding the right PTEs.

“在 kernel/vm.c 里的 walk() 对于寻找 PTE 将是非常有参考价值”

我直接把 walk() 代码拷过来了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
    if(va >= MAXVA)
        panic("walk");

    for(int level = 2; level > 0; level--) {
        pte_t *pte = &pagetable[PX(level, va)];
        if(*pte & PTE_V) {
            // 将当前 PTE 转换的物理地址，用作下一级页表的虚拟地址，重复流程
            pagetable = (pagetable_t)PTE2PA(*pte);
        } else {
            if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
                return 0;
            memset(pagetable, 0, PGSIZE);
            *pte = PA2PTE(pagetable) | PTE_V;
        }
    }
    return &pagetable[PX(0, va)];
}

这里我们直接忽略 else() 分支，因为这是 walk() 的其他方面要求。而 Hardware minics 的逻辑直接看 if() 就够了

在 xv6-handout-riscv-fall 2021, p36, section 3.3, paragraph 5 有这样的一句话：

For example, as walk descends levels of the page table, it pulls the (physical) address of the next-level-down page table from a PTE (kernel/vm.c:89), and then uses that address as a virtual address to fetch the PTE at the next level down (kernel/vm.c:87).

“当 walk() 递减页表的层数时，它从 PTE 中取出下一级页表的（物理）地址，然后使用这个地址作为获取下一层 PTE 的虚拟地址”

所以 walk() 的 if() 分支是将物理地址赋值为页表地址，这个页表地址继续迭代寻址下一层

下一个提示，

You’ll need to define PTE_A, the access bit, in kernel/riscv.h. Consult the RISC-V manual to determine its value.

“你需要在 kernel/riscv.h 定义访问位 PTE_A，这里的设置需要参考 riscv 手册”

可以参考 上面页表机制那张图，得到 PTE_A 是 bit-6 这个位，因此可以这么设置：

1
#define PTE_A (1L << 6)

这里顺便一提，标志位实际的设置是硬件负责的，比如我们编程时往某个页面写入数据或读取之类的，硬件会帮我们置位访问位

前面 “要求” 处有句话是这么说的：

The RISC-V hardware page walker marks these bits in the PTE whenever it resolves a TLB miss.

“riscv 页表机制的硬件每当解决一个 TLB 丢失后，就会在 PTE 标识这些位（访问位）”

再下一个提示，

Be sure to clear PTE_A after checking if it is set. Otherwise, it won’t be possible to determine if the page was accessed since the last time pgaccess() was called (i.e., the bit will be set forever).

“如果 PTE 是置位的，那你需要在检查完 PTE 访问位之后进行清位。否则，当最后一次调用 pgaccess() 后这个页仍会是 ‘已访问’ 状态（也即是这个标志位会永远置位）”

这告诉我们清位操作是我们负责的


Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#ifdef LAB_PGTBL
int
sys_pgaccess(void)
{
    uint64 va;
    int n;
    uint64 result;
    unsigned int bitmask = 0;

    // 获取三个参数
    if (argaddr(0, &va) < 0)    return -1;
    if (argint(1, &n) < 0)    return -1;
    if (argaddr(2, &result) < 0)    return -1;

    // 检查参数有没有超过范围
    if (va >= MAXVA)    return -1;
    if (va + PGSIZE * n >= MAXVA)    return -1;

    for (int i = 0; i < n; ++i, va += PGSIZE) {
        // 获取 va 对应的 pte
        pagetable_t pagetable = myproc()->pagetable;
        for (int level = 2; level > 0; level--) {
            pte_t *pte = &pagetable[PX(level, va)];
            if (*pte & PTE_V) {
                pagetable = (pagetable_t)PTE2PA(*pte);
            } else    return -1;
        }
        pte_t *pte = &pagetable[PX(0, va)];

        // 检查 pte 上的 flag
        unsigned int mask = 0;
        if (*pte & PTE_A) {
            // bitmask 置位
            mask = 1L << i;
            // pte 上的 PTE_A 清位（异或可以实现取反）
            *pte ^= PTE_A;
        }
        bitmask |= mask;
    }

    // 将 bitmask 送回用户空间
    if (copyout(myproc()->pagetable, result, (char *)&bitmask, sizeof(unsigned int)) < 0)
        return -1;

    return 0;
}
#endif

写在最后

耗时 15h6m

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. LAB
  2. 2. Speed up system calls (EASY)
    1. 2.1. 要求
    2. 2.2. 提示
    3. 2.3. Summary
    4. 2.4. Solution
  3. 3. Print a page table (EASY)
    1. 3.1. 要求
    2. 3.2. 提示
    3. 3.3. Solution
  4. 4. Detecting which pages have been accessed (HARD)
    1. 4.1. 要求
    2. 4.2. 提示
    3. 4.3. Solution
  5. 5. 写在最后
Total : 18
2022
cpp translation winsock xv6
LIVEHOOD