# Lab3 pgtbl: 記錄
[lab pgtbl](https://pdos.csail.mit.edu/6.S081/2022/labs/pgtbl.html)
## 大綱
1. xv6 的 virtual memory
1.1 terms about virtual memory
1.2 virtual memory in xv6
1.3 xv6 中 關於 virtual memory 的程式碼
2. lab
2.1 Speed up system calls
2.2 Print a page table
2.3 Detect which pages have been accessed
## 1. xv6 的 virtual memory
### 使用 virtual memory 的動機
* 每個 process 在概念上都有**自己的**抽象的記憶體空間
### 1.1
* virtual mem, physical memory 以及 page table 之間的關係
* 每一個 process 都有自己的 Virtual memory address space
* virtual address 經由 page table 可以找到 physicall address
* 每個 process 都需要一個 page table
* 當下正在使用的 page table 的 address 會儲存在 register `stap` 中
* `stap` 儲存的是 physical address
* offset: 一個 page 的大小是 2^12
* 一個 page table 中有很多 page table entry(pte)
### 1.2 RISC-V 裡面的 virtual memory
* 可以節省空間，如果沒有用到，就可以先不用分配空間
* 每個 page table entry(pte) 都有一些 flag:
* V - 這個 pte 是不是有沒有在使用
* W - 可讀
* X - 可執行
* U - User 可不可以使用
* A - 有沒有被訪問，為了 cache 而存在的
* D - 為了 cache 而存在的 (xv6 不考慮 cache 的問題)
* 什麼是 page table?
* virtul memory address 經由 page table 可以找到 physical memory address
* 所以說 `pagetable_t` 只需要紀錄這個 table 的 **physical** address 就可以了
* `pagetable_t` 紀錄的位置開始，總共有 2 ^ 9 = 512 個 pte
* 每個 pte 需要紀錄的東西:
* 總共有 64 bits
* 44 bits - Physical Page Number
* 2 bits - Reserved for supervisor software
* 1 bits - V
* 1 bits - W
* 1 bits - X
* 1 bits - U
* 1 bits - A
* 1 bits - D
* 為什麼 Physical page Number(PPN) 會是 44 bits?
* 因為 physical address 是 56 bits =
* 44 bits physical page number +
* 12 bits offset
* size of physical memory = 2 ^ 56
* 一個 pte 包含 address 的資訊
* 44 bits PPN
* 沒有 offset 因為 offset 已經存在於原本的 virtual memory 當中了
* 一個 page table 總共有多少個 pte?
* 總共有 512(2 ^ 9) 個 pte
* 因為每個 level 都個拿了 9 bits 來當 page table 的 index
### xv6 中 關於 virtual memory 的程式碼
這裡以 bottom up 的方式說明 xv6 如何實作 virtual memory
#### 先看幾個重要的檔案:
* `kernel/memlayout.h`: 定義了 layout
* `kernel/vm.c` 大多數處理 virtual memory 的程式碼都在這裡
* `kernel/kalloc.c`: 負責 allocate 以及 free 掉 physical memory
#### 資料結構 `pte_t` 與 `pagetable_t`
```clike=
// kernel/riscv.h
typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs
```
`pagetable_t` 與 `pte_t` 是 xv6 中用來處理 virtual memory 最重要的兩個資料結構，`pagetable_t` 用來紀錄一個 pagetable 的 **physical** memory; `pte_t` 如先前提到的圖，要紀錄 44 bits 的 physical page number 以及數個 flags
#### 用來基本操作的 macro: `PX()`, `PTE2PA()`, `PA2PTE()`
在 xv6 的 virtual memory 中，有 3 個重要的詞需要弄清楚，分別為:
* virtual memory address
* physical memory address
* pagetable
* physical page number (PPN)
##### `PX()` 解析
在 xv6 中，一個 virtual memory address 中有 3 個 9 bits 的 pagetable index，`PX()` 的功用就是把一個 virtual memory address 中的其中一個 level 的 9 physical page number (PPN) 取出來
```C
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)
```
根據 level 把 virtual memory address 中的其中 9 bits PPN 移動到 64-bits 的最右邊
目前我們有了 `PX()`，可以從 va 中找到其中一個 PPN，如果現在有一個 pagetable，搭配上剛剛找到的 PPN，我們便可以找到對應的 PTE，舉例來說像是 `walk() at kernel/vm.c` 的其中一行：
```clike=
// kernel/vm.c
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) {
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)];
}
```
就是一個使用到 `PX()` 的例子:
1. 利用 va, level 丟入 `PX()` 找到 PPN: `PX(level, va)`
2. 再利用這個 PPN(`PX(level, va)`) 從 pagetable 中拿到 page table entry (PPN)
* `&pagetable[PX(level, va)]`
##### `PTE2PA()` 解析
剛剛我們已經利用了 `PX()` 讓 va 透過 pagetable 找到對應的 pte，拿到 pte 後，我們要有能力把這個 pte 轉換成 physical memory address (PA) 這才是我們最終的目的對吧: va 透過 pagetable 找到 pa
這正是 `PTE2PA()` 所要處理的事情
```C
#define PTE2PA(pte) (((pte) >> 10) << 12)
```
把 pte 當中的 physical page number 擷取出來
##### `PA2PTE()` 解析
```C
// shift a physical address to the right place for a PTE.
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
```
* 把一個 physical memory 的 offset 去掉，並且做成一個 pte (shift left 10)
* 請注意這個做好的 pte 的 flag 的地方全部都是 0，需要自己把 flag 設定上
##### `PGROUNDUP()` 解析
##### `PGROUNDDOWN()` 解析
現在我們有了 `PX()`, `PTE2PA()`, `PA2PTE()`，這幾個針對 virtual memory address, page table entry(pte) 以及 physical memory 的 macro,
#### `kernel/vm.c: walk()` 解析
在大多數情況下，va 透過 pagetable 得到 pa 的動作，像是：
```C
a = 10;
```
這種動作是由硬體完成的，risc-v 的 register `satp` 會紀錄當下 pagetable 的 **physicall** address
一旦有了 `satp` 所紀錄的這個 pagetable 的 physicall address，
硬體就有辦法把程式中的 va 藉由 pagetable(從 `satp` 得知) 轉換成 pa
可是在 kernel 中的**某些地方**(`todo`: 實際上在哪邊？)
會需要在程式中就直接拿到最後一個 level (level 0) 的 PTE (有點類似用軟體做出硬體的行為)
試想我們有一個 va 以及 pagetable，想要拿到最後一個 level 的 PTE，可以用 `walk()` 來達成:
```C
// Return the address of the PTE in page table pagetable
// that corresponds to virtual address va. If alloc!=0,
// create any required page-table pages.
// 根據 virtual address va 以及 pate table patetable
// 回傳 PTE 的 address (physical memory)
// The risc-v Sv39 scheme has three levels of page-table
// pages. A page-table page contains 512 64-bit PTEs.
// A 64-bit virtual address is split into five fields:
// 39..63 -- must be zero.
// 30..38 -- 9 bits of level-2 index.
// 21..29 -- 9 bits of level-1 index.
// 12..20 -- 9 bits of level-0 index.
// 0..11 -- 12 bits of byte offset within the page.
pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc) // pagetable 紀錄的是 pa
{
if(va >= MAXVA)
panic("walk");
// level 只會是 2, 1, 因為 level == 1 時
// 就會拿到指向 level 0 的 pagetable 的 pte
for(int level = 2; level > 0; level--) {
pte_t *pte = &pagetable[PX(level, va)]; // get pte by virtual address and level (in physical address)
if(*pte & PTE_V) {
pagetable = (pagetable_t)PTE2PA(*pte); // pagetable 是指向下一層的 pagetable
} else { // 如果這個 PTE 還沒有被 allocate，並且 alloc != 0 (alloc == true 的意思)
// 則 allocate 這個 PTE
if(!alloc || (pagetable = (pde_t*)kalloc()) == 0) // 使用 kalloc() 告訴 xv6: 我要一塊 page 來存放一個 pagetable
return 0; // (pte_t *) 是想表達 pagetable 是 pte_t 的 array 的意思
memset(pagetable, 0, PGSIZE); // 清空 pagetable (注意這時候，memset 吃的是 pa, 可是 user mode 時，function 吃的是 va)
// level == 2 時，pte 指向一個 level 1 的 page table
*pte = PA2PTE(pagetable) | PTE_V;
}
}
// 到了這裡 pagetable 已經是一個 level 0 的 page table
// 有了這個 page table 以及 va 中 level 0 的 9 bits 的 physical page number (PPN)
// 就可以拿到最終我們要的 PTE
return &pagetable[PX(0, va)];
}
```
* `walk()` 是用來根據 pagetable 以及 virtual memory address 來取得這個 vma 的 pte
* `pagetable_t` 紀錄的是 physical memory
* `walk()` 回傳 `pte_t *` 也就是 figure 3.2 所描述的那樣
* 54..63 -- 10 bits Reserved
* 10..53 -- 44 bits Physical Page Number
* 0..9 -- 10 bits Flags
* 有了 PTE 之後可以幹嘛?
* 有了 PTE 之後，就可以再利用 va 的 12 bits offset 來得到 pa
* 請注意，在大多數真正的 access pagetable 的情況下**並不會**使用 `walk()`，而是用硬體的方式處理
#### `mappages()` 解析
現在我們有了一些 macro 可以處理 va, pa, page table, pte 的轉換
`mappages()` 使用了情況為:
我們希望在 page table pagetale 中記下一筆資訊:
virtual address va 透過 pagetable 會對應到 physical address pa
並且這個對應是以一個 page (4096 bit) 做為一個單位去做 map 的
```C
// kernel/riscv.h
typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs
// kernel/vm.c
int
mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)
{
uint64 a, last;
pte_t *pte;
if(size == 0)
panic("mappages: size");
// map 必須要以一個 page 為單位, 所以需要 round up 以及 round down
a = PGROUNDDOWN(va);
last = PGROUNDDOWN(va + size - 1);
for(;;){
// 拿到 virtual address a 的 pte (walk() 會幫我們 allocate, 它使用 kalloc())
if((pte = walk(pagetable, a, 1)) == 0) // walk 失敗時 return 0
return -1;
if(*pte & PTE_V)
panic("mappages: remap");
// 在這裡，我們拿到了 pagetable, level 0, 對應到 va a 的 pte
// 現在它還沒被賦予值，現在我們要告訴這個 PTE，你要指到 pa 去!
*pte = PA2PTE(pa) | perm | PTE_V; // pte 對應到了 pa
if(a == last)
break;
a += PGSIZE;
pa += PGSIZE;
}
return 0;
}
```
`mappages()` 是用來把一個 pa 塞進一個 pagetable 裡，並且我們可以指定它的 va 以及 flag
#### `proc_pagetable()` 解析
`proc_pagetable()` 用來初始化一個新的 process
```clike=
// Create a user page table for a given process, with no user memory,
// but with trampoline and trapframe pages.
// 把一個 process 的 pagetable 做出來，
// 但這時候只有 trampoline 跟 trapframe 有被紀錄在 page table 中
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 page just below the trampoline page, 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;
}
return pagetable;
}
```
* `proc_pagetable()` 所做的事情也就是 allocate `struct proc *p` 的 pagetable
* 會需要先了解的 function 有
* `mappages()`
* `uvmcreate()`
* `uvmunmap()`
* `uvmfree()`
#### `uvmcreate()` 解析
```C
// create an empty user page table.
// returns 0 if out of memory.
pagetable_t
uvmcreate()
{
pagetable_t pagetable;
pagetable = (pagetable_t) kalloc();
if(pagetable == 0)
return 0;
memset(pagetable, 0, PGSIZE);
return pagetable;
}
```
* `uvmcreate()` 利用 `kalloc()` 做出一個全新的 pagetable
* 請注意，pagetable 所紀錄的是 physical memory
#### `uvmunmap()` 解析
```C
// Remove npages of mappings starting from va. va must be
// page-aligned. The mappings must exist.
// Optionally free the physical memory.
void
uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)
{
uint64 a;
pte_t *pte;
if((va % PGSIZE) != 0)
panic("uvmunmap: not aligned");
for(a = va; a < va + npages*PGSIZE; a += PGSIZE){
if((pte = walk(pagetable, a, 0)) == 0) // 如果這個要被 unmap 的 page (virtual address) 根本不存在
panic("uvmunmap: walk");
if((*pte & PTE_V) == 0) 它應該要是 valid
panic("uvmunmap: not mapped");
if(PTE_FLAGS(*pte) == PTE_V)
panic("uvmunmap: not a leaf");
if(do_free){
uint64 pa = PTE2PA(*pte);
kfree((void*)pa);
}
*pte = 0;
}
}
```
* `uvmunmap()`
* `va` 必須為 `PGSIZE` 的倍數
* unmap 跟 free 是兩回事
* free: 把這個 physical address 加回 `kmem.freelist` 中
* 也就是要用 `kfree((void *) pa)`
* unmap: 僅限於對於這個 pagetable 而言，把這個 virtual memory address 移除
* 所謂的移除，也就是把最後一層的 page table entry 給清為 0 `*pte = 0`
#### `uvmfree()` 解析
```C
// Free user memory pages,
// then free page-table pages.
void
uvmfree(pagetable_t pagetable, uint64 sz)
{
if(sz > 0)
uvmunmap(pagetable, 0, PGROUNDUP(sz)/PGSIZE, 1);
freewalk(pagetable);
}
```
#### `kalloc()` 解析
```C
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
struct run *r;
acquire(&kmem.lock);
r = kmem.freelist;
if(r)
kmem.freelist = r->next;
release(&kmem.lock);
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
```
* 在 xv6 中，所有可以用的 page 會被紀錄在 `kmem.freelist` 當中
```C
struct run {
struct run *next;
};
struct {
struct spinlock lock;
struct run *freelist;
} kmem;
```
* `kalloc()` 回傳一個 4096-byte 的 page
* 這是一個 pointer 指向 physical memory
* kmem 的初始化過程很值得追蹤
#### `uvmcopy()` 解析
* `uvmcopy()` 是用來把一個 parent 的 page table 複製給 child，
* 包含了 page table 以及 physical memory 的內容
* 失敗時回傳 -1，並且把先前 allocate 的 page 都給 free 掉
```C
// 把 old 的內容複製給 new
// sz 為 page 的數量，每個 page 的大小為 4096 byte
int
uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)
{
pte_t *pte;
uint64 pa, i;
uint flags;
char *mem;
for(i = 0; i < sz; i += PGSIZE){
if((pte = walk(old, i, 0)) == 0) // 拿到一個 parent 的 pte
panic("uvmcopy: pte should exist");
if((*pte & PTE_V) == 0)
panic("uvmcopy: page not present");
pa = PTE2PA(*pte); // 用 parent 的 pte 拿到 physical address
flags = PTE_FLAGS(*pte); // 拿到 parent 的 pte 的 flags
if((mem = kalloc()) == 0) // mem 是 child 的 physical memory (其中一個 page)
goto err;
memmove(mem, (char*)pa, PGSIZE); // parent 的內容搬到 child 的 memory 中 (都用 pa)
// 現在有了 mem (一個 page 的 pa)
// 接下來要把這個 page map 到 child 的 pagetable (new) 中
if(mappages(new, i, PGSIZE, (uint64)mem, flags) != 0){
kfree(mem);
goto err;
}
}
return 0;
err:
uvmunmap(new, 0, i / PGSIZE, 1);
return -1;
}
```
#### `memmove()` 解析
`memmove()` 把 n bytes 的內容從 `src` 搬到 `dst`
* 是 pa or va ?????
```C
void*
memmove(void *dst, const void *src, uint n)
{
const char *s;
char *d;
if(n == 0)
return dst;
s = src;
d = dst;
if(s < d && s + n > d){
s += n;
d += n;
while(n-- > 0)
*--d = *--s;
} else
// 這個 loop 也寫的太騷了
while(n-- > 0)
*d++ = *s++;
return dst;
}
```
#### `malloc()` 解析
`malloc()` 用來 allocate `nbytes` 個 bytes 的記憶體空間
```Clike=
void*
malloc(uint nbytes)
{
Header *p, *prevp;
uint nunits;
nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
if((prevp = freep) == 0){
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
if(p->s.size >= nunits){
if(p->s.size == nunits)
prevp->s.ptr = p->s.ptr;
else {
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void*)(p + 1);
}
if(p == freep)
if((p = morecore(nunits)) == 0)
return 0;
}
}
```
#### `copyout()` 解析
```Clike=
// Copy from kernel to user.
// Copy len bytes from src to virtual address dstva in a given page table.
// Return 0 on success, -1 on error.
int
copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len)
{
uint64 n, va0, pa0;
while(len > 0){
va0 = PGROUNDDOWN(dstva);
pa0 = walkaddr(pagetable, va0);
if(pa0 == 0)
return -1;
n = PGSIZE - (dstva - va0);
if(n > len)
n = len;
memmove((void *)(pa0 + (dstva - va0)), src, n);
len -= n;
src += n;
dstva = va0 + PGSIZE;
}
return 0;
}
```
* `src` 是 pa or va ???
## 2. lab
這個 lab 的測試程式寫在 `user/pgtbltest.c`
## 2.1 Speed up system calls
### 目標：寫出 `ugetpid()` (優化版本的 `getpid()`)
* `getpid()`:
* 會需要使用到 `SYS_getpid` 這個 system call
* 但是使用 system call 本身是耗費時間的
* `ugetpid()`
* 這個 function 直接不需要經由 system call 就可以達到相同的效果
### 作法
當一個 proccess 開始執行時，在 virtual memory address `USYSCALL`(定義在 `kernel/memlayout.h`) 中存放 `struct usyscall` 並且把 PID 存放於這個 struct 中。`ugetpid()` 是一個 user space 就可以執行的 function，所以可以跳過原本的 system call 的過程，以達到加速的效果。
### Some hints
* 可以把這個 mapping 實作在 `proc_pagetable()` 這個 function 中
### 疑問
### 測試 (`user/pgtbltest.c: ugetpid_test()`)：
```clike=
void
ugetpid_test()
{
int i;
printf("ugetpid_test starting\n");
testname = "ugetpid_test";
for (i = 0; i < 64; i++) {
int ret = fork();
if (ret != 0) {
wait(&ret);
if (ret != 0)
exit(1);
continue;
}
if (getpid() != ugetpid())
err("missmatched PID");
exit(0);
}
printf("ugetpid_test: OK\n");
}
```
### 原本的 `getpid()` 的流程為何
* `user/pgtbltest.c: ugetpid_test()`
* `getpid()`
* `usys.S`
```
.global getpid
getpid:
li a7, SYS_getpid
ecall
ret
```
* `kernel/trampoline.S: uservec`
* `kernel/trap.c: usertrap()`
* `syscall.c: syscall()`
* `sysproc.c: sys_getpid()`
* `myproc()`
* `kernel/trampoline.S: uservec`
```clike=
uint64
sys_getpid(void)
{
return myproc()->pid;
}
```
### 優化版的 `getpid()` 的流程為何
* `user/pgtbltest.c: ugetpid_test()`
* `ugetpid()`
* `user/ulib.c: ugetpid()`
```C
// ulib.c
int
ugetpid(void)
{
struct usyscall *u = (struct usyscall *)USYSCALL;
return u->pid;
}
```
### 程式實作
#### `usyscall` 題目幫我們定義好了
```Clike=
// kernel/memlayout.h
struct usyscall {
int pid; // Process ID
};
```
之後每一個 process 都會存放一份 `usyscall`
#### `kernel/proc.h` 中
先在 `proc_pagetable()` 中加入
```C
// Per-process state
struct proc {
struct spinlock lock;
// p->lock must be held when using these:
enum procstate state; // Process state
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
int xstate; // Exit status to be returned to parent's wait
int pid; // Process ID
// wait_lock must be held when using this:
struct proc *parent; // Parent process
// these are private to the process, so p->lock need not be held.
uint64 kstack; // Virtual address of kernel stack
uint64 sz; // Size of process memory (bytes)
pagetable_t pagetable; // User page table
struct trapframe *trapframe; // data page for trampoline.S
struct context context; // swtch() here to run process
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
char name[16]; // Process name (debugging)
struct usyscall *usyscall; // add this !!!!!!!!!!!!!!!
};
```
準備好 data 之後，指後要在 allocate 時以及 free 時做一些處理
#### allocate 時:
* `kernel/proc.c: allocproc()`
* `kernel/proc.c: proc_pagetable()`
#### free 時:
* `kernel/proc.c: freeproc()`
* `kernel/proc.c: proc_freepagetable()`
#### `kernel/proc.c: allocproc()`
```Clike=
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;
}
// Allocate and initialize a usyscall page !!!!!!!!!!!
if((p->usyscall = (struct usyscall *)kalloc()) == 0){ // here!
freeproc(p);
release(&p->lock);
return 0;
}
p->usyscall->pid = p->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;
}
```
#### `kernel/proc.c: proc_pagetable()` 中
```Clike=
// Create a user page table for a given process, with no user memory,
// but with trampoline and trapframe 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 page just below the trampoline page, for
// trampoline.S.
if(mappages(pagetable, TRAPFRAME, PGSIZE,
(uint64)(p->trapframe), PTE_R | PTE_W) < 0){
uvmunmap(pagetable, TRAMPOLINE, 1, 0);
uvmfree(pagetable, 1);
return 0;
}
// map one read-only page at USYSCALL !!!!!!!!!!!!!!!!!!!!!!!
if(mappages(pagetable, USYSCALL, PGSIZE,
(uint64)(p->usyscall), PTE_R | PTE_U) < 0){
uvmunmap(pagetable, TRAMPOLINE, 1, 0); // 注意是 unmap 己經被 map 好的 TRAMPOLINE, TRAPFRAME
uvmunmap(pagetable, TRAPFRAME, 1, 0);
uvmfree(pagetable, 0);
return 0;
}
return pagetable;
}
```
#### `kernel/proc.c: freeproc()`
怎麼知道這裡要處理？
```C
// free a proc structure and the data hanging from it,
// including user pages.
// p->lock must be held.
static void
freeproc(struct proc *p)
{
if(p->trapframe)
kfree((void*)p->trapframe);
p->trapframe = 0;
// free usyscall !!!!!!!!
if (proc->usyscall)
kfree((void *) p->usyscall);
p->usyscall = 0;
if(p->pagetable)
proc_freepagetable(p->pagetable, p->sz);
p->pagetable = 0;
p->sz = 0;
p->pid = 0;
p->parent = 0;
p->name[0] = 0;
p->chan = 0;
p->killed = 0;
p->xstate = 0;
p->state = UNUSED;
}
```
#### `kernel/proc.c: proc_freepagetable()`
```C
// Free a process's page table, and free the
// physical memory it refers to.
void
proc_freepagetable(pagetable_t pagetable, uint64 sz)
{
uvmunmap(pagetable, TRAMPOLINE, 1, 0);
uvmunmap(pagetable, TRAPFRAME, 1, 0);
uvmunmap(pagetable, USYSCALL, 1, 0); // unmap USYSCALL !!!!!!!
uvmfree(pagetable, sz);
}
```
## 2.2 Print a page table
prints the contents of a page table
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.
* You can put `vmprint()` in `kernel/vm.c`.
* Use the macros at the end of the file `kernel/riscv.h`.
* The function freewalk may be inspirational.
* Define the prototype for `vmprint` in `kernel/defs.h` so that you can call it from `exec.c`.
* Use `%p` in your `printf` calls to print out full 64-bit hex PTEs and addresses as shown in the example.
```
page table 0x0000000087f6b000
..0: pte 0x0000000021fd9c01 pa 0x0000000087f67000
.. ..0: pte 0x0000000021fd9801 pa 0x0000000087f66000
.. .. ..0: pte 0x0000000021fda01b pa 0x0000000087f68000
.. .. ..1: pte 0x0000000021fd9417 pa 0x0000000087f65000
.. .. ..2: pte 0x0000000021fd9007 pa 0x0000000087f64000
.. .. ..3: pte 0x0000000021fd8c17 pa 0x0000000087f63000
..255: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..511: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..509: pte 0x0000000021fdcc13 pa 0x0000000087f73000
.. .. ..510: pte 0x0000000021fdd007 pa 0x0000000087f74000
.. .. ..511: pte 0x0000000020001c0b pa 0x0000000080007000
init: starting sh
```
1. Insert `if(p->pid==1) vmprint(p->pagetable)` in `exec.c` just before the return argc, to print the first process's page table
#### `vm.c`
```C
void
vmprint(pagetable_t pagetable, int level)
{
if (level == 2)
printf("page table %p\n", pagetable);
// there are 2^9 = 512 PTEs in a page table.
for(int i = 0; i < 512; i++){
pte_t pte = pagetable[i];
if(pte & PTE_V){
// this PTE points to a lower-level page table.
// print a PTE in this level
for (int j = 2; j >= level; j--)
printf(" ..");
printf("%d: pte %p pa %p\n", i, pte, PTE2PA(pte));
if (level > 0) {
uint64 child = PTE2PA(pte);
vmprint((pagetable_t)child, level - 1);
}
} else if(pte & PTE_V){
panic("freewalk: leaf");
}
}
}
```
#### `kernel/defs.h`
```C
void vmprint(pagetable_t pagetable, int);
```
#### `kernel/exec.c`
```C
int
exec(char *path, char **argv)
{
// ... //
if(p->pid==1)
vmprint(p->pagetable, 2);
return argc; // this ends up in a0, the first argument to main(argc, argv)
// ... //
}
```
## 2.3 Detect which pages have been accessed
Some garbage collectors (a form of automatic memory management) can benefit from information about which pages have been accessed (read or write).
In this part of the lab, you will add a new feature to xv6 that detects and reports this information to userspace by inspecting the access bits in the RISC-V page table.
The RISC-V hardware page walker marks these bits in the PTE whenever it resolves a TLB miss.
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.
* Read `pgaccess_test()` in `user/pgtlbtest.c` to see how pgaccess is used.
* Start by implementing `sys_pgaccess()` in `kernel/sysproc.c`.
* You'll need to parse arguments using argaddr() and argint().
* For the output bitmask, it's easier to store a temporary buffer in the kernel and copy it to the user (via copyout()) after filling it with the right bits.
* It's okay to set an upper limit on the number of pages that can be scanned.
* walk() in kernel/vm.c is very useful for finding the right PTEs.
* You'll need to define `PTE_A`, the access bit, in kernel/riscv.h. Consult the RISC-V privileged architecture manual to determine its value.
* 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).
* `vmprint()` may come in handy to debug page tables.
先觀察 `pgaccess_test()` 是如何使用 `pgaccess()` 的
```C
void
pgaccess_test()
{
char *buf;
unsigned int abits;
printf("pgaccess_test starting\n");
testname = "pgaccess_test";
buf = malloc(32 * PGSIZE);
if (pgaccess(buf, 32, &abits) < 0)
err("pgaccess failed");
buf[PGSIZE * 1] += 1;
buf[PGSIZE * 2] += 1;
buf[PGSIZE * 30] += 1;
if (pgaccess(buf, 32, &abits) < 0)
err("pgaccess failed");
if (abits != ((1 << 1) | (1 << 2) | (1 << 30)))
err("incorrect access bits set");
free(buf);
printf("pgaccess_test: OK\n");
}
```
這就是一個 `pgaccess` 的使用例子
```C
pgaccess(buf, 32, &abits)
```
以這個例子來說，我們要檢查 buf 開始的 32 個 page 的 access bit 是否有設為 1
* `malloc()` 幫我們做出的 32 個 page 是個什麼樣子的存在？
* 首先請先認知到一個 process 只有一個 page table
* 第 2 點，請再認知到，`malloc()` 給我們的是連續的 virtual memory
* 但問題是我們現在要用的是以一個 page 為單位
* 所以這裡所說的 page 會是 level 0 的 page
* 因為現在再說的 page 會是 一個 PAGESIZE 的大小
* 在 kernel 中 (`sys_pgaccess()`) 要如何使用 walk()
* 因為我現在並不知道 page table 的 physical address
* 要使用 `copyout()`
* `kernel/sysproc.c: sys_pgaccess()`
```Clike=
int
sys_pgaccess(void) {
uint64 start;
int npages;
uint64 abitsaddr;
uint64 va;
uint64 mask;
uint64 abits;
struct proc *p = myproc();
argaddr(0, &start);
argint(1, &npages);
argaddr(2, &abitsaddr);
if (npages > 64)
return -1;
mask = 1;
abits = 0;
for(va = start; va < start + PGSIZE * npages; va += PGSIZE){
pte_t *pte = walk(p->pagetable, va, 0);
if(*pte & PTE_A) {
abits |= mask;
*pte = *pte & (~PTE_A);
}
mask <<= 1;
}
if (copyout(p->pagetable, abitsaddr, (char *)&abits, 4) < 0)
return -1;
return 0;
}
```
## 參考資料
* https://pdos.csail.mit.edu/6.S081/2022/labs/pgtbl.html
* chapter 3 of [xv6 book](https://pdos.csail.mit.edu/6.S081/2022/xv6/book-riscv-rev3.pdf)
Sign in with Wallet
Connect another wallet