Introduction: Page Tables(Chapter 2)

一、運作原理

1. 前言

在現代的電腦系統中，程式與其資料都必須存放在記憶體中，才能直接被CPU所使用，而在多工處理系統中，由於記憶體內會同時存放著多份程式與資料，因此作業系統不僅要負責追蹤並記錄每個程式存放在記憶體內的哪個位址，還要把程式裡面參考到的位址轉換成記憶體的位址。

2. 背景知識

一般在做Memory Allocation時分為兩種方法：

a. Contiguous Memory Allocation

直接為根據process所需記憶體大小，為其劃分可用的連續記憶體空間使用。
如下圖：
缺點為會因為外部碎裂(External Fragmentation)造成記憶體空間浪費。

b. Non-Contiguous Memory Allocation

允許process載入不連續的記憶體空間，只要可用空間的總大小足以容納該process即可。

原理是將記憶體劃分成相同大小的區塊，稱為頁框(frame)，然後將程式也劃分成相同大小的區塊，稱為分頁(page)。

當程式準備執行時，它的分頁會被載入記憶體的頁框，每個分頁對應一個頁框，但頁框不需要是連續的，分散或順序顛倒也無妨。

為了記錄程式的每個分頁是載入到記憶體的哪些頁框，因此我們需要一個分頁表(page table)。

3. 實際運作過程

a. 位址轉換

利用page table將virtual address轉為physical address時可分為兩個步驟：

1. paging hardware會根據virtual address的前10 bits找到page directory中相應的page directory entry(PDE)，若其存在則進入下個步驟。
2. paging hardware會從前一步驟找到之PDE中，根據virtual address的11~20 bits從page table定位出相應的page table page，並以此得到正確的Physical Address。

在過程中無論是PDE不存在或找不到page table page，都會導致系統錯誤。

此外，PDE其他bits(0~12)中，還會包含一些資訊，指示paging hardware這段virtual address的狀態、權限等等，如下圖所示。

b. 記憶體初始布局

xv6系統初始化後physical address的布局情況如下圖所示：

memory的0~1MB存的是BIOS，1~4MB存的是xv6的code和data segment，4~224MB可供os自由分配(因為xv6預設memory大小為224MB)，224MB以上是其他devices的空間，不屬於main memory。

實際virtual address對phsical address的mapping則如下圖所示：

具體程式碼定義可參考這裡。

二、程式流程圖

1. kvmalloc()

2. kinit()

3. growproc()

4. exec()

三、程式碼

0. Preprocessor Definitions

memlayout.h

#define EXTMEM  0x100000            // extended memory的起始位址
#define PHYSTOP 0xE000000           // physical memory的Top位址 
#define DEVSPACE 0xFE000000         // Other devices are at high addresses

#define KERNBASE 0x80000000         // 第一個kernel virtual 位址
#define KERNLINK (KERNBASE+EXTMEM)  // kernel連接的位址


#define V2P(a) (((uint) (a)) - KERNBASE)    // 將Virtual address轉換為Physical address
#define P2V(a) (((void *) (a)) + KERNBASE)  // 將Physical address轉換為Virtual address

#define V2P_WO(x) ((x) - KERNBASE)    // 與V2P相同，但沒有型別轉換
#define P2V_WO(x) ((x) + KERNBASE)    // 與V2P相同，但沒有型別轉換

mmu.h

#define NPDENTRIES      1024    // # 每個page directory中的directory entries數量
#define NPTENTRIES      1024    // # 每個page table的PTEs數量
#define PGSIZE          4096    // 一個page的大小(bytes)

#define PGSHIFT         12      // log2(PGSIZE)
#define PTXSHIFT        12      // offset of PTX in a linear address
#define PDXSHIFT        22      // offset of PDX in a linear address

#define PGROUNDUP(sz)  (((sz)+PGSIZE-1) & ~(PGSIZE-1))
#define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))

PGROUNDUP(sz)值為address所屬page的上界
PGROUNDDOWN(a)值為address所屬page的下界

ex：
若一系統PGSIZE為1KB，address為620及2400，則

PGROUNDUP(620) ==> ((620 + (1024 -1)) & ~(1023)) ==> 1024
因此address 620當頁page的上界為1024

PGROUNDDOWN(2400) ==>(2400 & ~(1023))==> 2048
因此address 2400當頁page的下界為1024

1. kvmalloc()

在剛開始運行xv6時，main會透過呼叫kvmalloc來創建並切換至kernal專屬的page table中。

void
kvmalloc(void)
{
  //創建kernal page table，並將kpgdir設為其page directory
  kpgdir = setupkvm();
  //切換至kernal page table
  switchkvm();
}

以下分為setupkvm()及switchkvm()兩部分做說明。

1. setupkvm()

為kernal分配一個page用來存放page directory，並通mappages()創建page table。

pde_t*
setupkvm(void)
{
  pde_t *pgdir;
  struct kmap *k;

  // alloc一段位址，若失敗則retun 0
  if((pgdir = (pde_t*)kalloc()) == 0)
    return 0;
  //將alloc的位址初始化為0
  memset(pgdir, 0, PGSIZE);
  
  //檢查PHYSTOP是否超過DEVSPACE，若是則提示錯誤訊息
  if (P2V(PHYSTOP) > (void*)DEVSPACE)
    panic("PHYSTOP too high");
 
  //遍歷整個kmap，並用mappages()為每個page建立PDE：
  for(k = kmap; k < &kmap[NELEM(kmap)]; k++)
    if(mappages(pgdir, k->virt, k->phys_end - k->phys_start,
               (uint)k->phys_start, k->perm) < 0) {
      //刪除pgdir
      freevm(pgdir);
      return 0;
    }
  return pgdir;
}

kmap

定義kernal的mapping

// This table defines the kernel's mappings, which are present in
// every process's page table.
static struct kmap {
  void *virt;         //virtual address  
  uint phys_start;    //physical address的起始位址
  uint phys_end;      //physical address的結束位址
  int perm;           //權限管理
} kmap[] = {
 { (void*)KERNBASE, 0,             EXTMEM,    PTE_W}, // I/O space
 { (void*)KERNLINK, V2P(KERNLINK), V2P(data), 0},     // kern text+rodata
 { (void*)data,     V2P(data),     PHYSTOP,   PTE_W}, // kern data+memory
 { (void*)DEVSPACE, DEVSPACE,      0,         PTE_W}, // more devices
};

P2V()

詳見 0. Preprocessor Definitions

panic()

print字串。

void
panic(char *s)
{
  printf(2, "%s\n", s);
  exit();
}

NELEM()

回傳陣列中的元素個數。
#define NELEM(x) (sizeof(x)/sizeof((x)[0]))

mappages()

建立page directory中的所有entry。

static int
mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
  char *a, *last;
  pte_t *pte;
  
  //利用PGROUNDOWN對齊
  a = (char*)PGROUNDDOWN((uint)va);
  last = (char*)PGROUNDDOWN(((uint)va) + size - 1);
  for(;;){
    //利用walkpgdir找到PTE，如果回傳值為0則傳回-1
    if((pte = walkpgdir(pgdir, a, 1)) == 0)
      return -1;
    //若pte已存在則提示"remap"
    if(*pte & PTE_P)
      panic("remap");
          
    //設定權限
    *pte = pa | perm | PTE_P;
    //查找到最後一項時跳出迴圈
    if(a == last)
      break;
    //跳向下一個page
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

walkpgdir()

回傳PTE的address給pgdir。

static pte_t *
walkpgdir(pde_t *pgdir, const void *va, int alloc)
{
  pde_t *pde;
  pte_t *pgtab;

  pde = &pgdir[PDX(va)];
  //如果PDE已存在，表示page table已存在，回傳轉為virtual address的PTE_ADDR
  //若不存在，則新建一個page table
  if(*pde & PTE_P){
    pgtab = (pte_t*)P2V(PTE_ADDR(*pde));
  } else {
    if(!alloc || (pgtab = (pte_t*)kalloc()) == 0)
      return 0;
    // 確保所有PTE_P都為0
    memset(pgtab, 0, PGSIZE);
    // 將轉為physical address的pgtab，加上PTE_P、PTE_W、PTE_U後指派給pde
    *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;
  }
  return &pgtab[PTX(va)];
}

freevm()

用deallocuvm()將0到KERNBASE的virtual address空間回收，然后free掉page dirctory。

void
freevm(pde_t *pgdir)
{
  uint i;

  if(pgdir == 0)
    panic("freevm: no pgdir");
  //將 0 到 KERNBASE 的virtual address回收
  deallocuvm(pgdir, KERNBASE, 0);
  //銷毀整個page directory
  for(i = 0; i < NPDENTRIES; i++){
    if(pgdir[i] & PTE_P){
      char * v = P2V(PTE_ADDR(pgdir[i]));
      kfree(v);
    }
  }
  kfree((char*)pgdir);
}

2. switchkvm()

將hardware page table register轉至kernal page table。

void
switchkvm(void)
{
  //轉移至kernal page table
  lcr3(V2P(kpgdir));
}

2. kinit()

Physical Address初始化

kernal code存在physical address的0x100000，kernal page table則是entrypgdir。
virtual address->physical address 轉換為 [KERNBASE, KERNBASE+4MB)->[0, 4MB)。

因此，4MB及以上的physical adddress需要透過main()呼叫kinit1()和kinit2()初始化。

int
main(void)
{
//初始化4MB空間
kinit1(end, P2V(4*1024*1024)); 
//初始化4MB以上空間
kinit2(P2V(4*1024*1024), P2V(PHYSTOP));
}

1. kinit1()

xv6系统啟動後被main()呼叫。
分為kinit1()和kinit2()是因為剛啟動時pdt中只存在4MB memory可以使用，需要使用kinit1()初始化。

void
kinit1(void *vstart, void *vend)
{
  initlock(&kmem.lock, "kmem");
  //此時不需要用鎖(且鎖在4MB位址外，無法用)
  kmem.use_lock = 0;
  //將vstart~vend這段memory分割為frames
  freerange(vstart, vend);
}

kmem

struct {
  //spinlock
  struct spinlock lock;
  //是否使用lock
  int use_lock;
  //儲存空閒的frame list
  struct run *freelist;
} kmem;

run

每個run都是一個list中的element，連接list中下一個element。

struct run {
  struct run *next;
};

freerange()

將vstart~vend這段memory分割為frames。

void
freerange(void *vstart, void *vend)
{
  char *p;
  //找到vstart位址所屬frame的上界
  p = (char*)PGROUNDUP((uint)vstart);
  //只要上界不超過vend，就持續將memory空間切割為frames
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
    kfree(p);
}

kfree()

將frames加入free frame list中。

void
kfree(char *v)
{
  struct run *r;
  //檢查是否超過限制範圍
  if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
    panic("kfree");

  // 將整段memory值設為1，這樣在發生dangling reference會報錯
  memset(v, 1, PGSIZE);

  if(kmem.use_lock)
    acquire(&kmem.lock);
 
  //將v轉為run型別後指派給r
  r = (struct run*)v;
  //將r接上freelist上
  r->next = kmem.freelist;
  kmem.freelist = r;
 
  if(kmem.use_lock)
    release(&kmem.lock);
}

dangling reference: 記憶體已經釋放掉還繼續使用

2. kinit2()

在建立完整的page table後，main()來初始化剩下的physical pages。
此時鎖已經可用了。

void
kinit2(void *vstart, void *vend)
{
  //將vstart~vend這段memory分割為frames
  freerange(vstart, vend);
  //設置用鎖
  kmem.use_lock = 1;
}

3. growproc()

allocate一些physical pages，然後將其map到process的address space上。
成功傳回0，失敗傳回-1。

int
growproc(int n)
{
  uint sz;
  struct proc *curproc = myproc();

  //sz儲存process memory的大小
  sz = curproc->sz;
 
  //如果n>0，則allocate新的memory
  //如果n<0，則deallocate現有的memory
  //過程中若失敗即回傳-1
  if(n > 0){
    if((sz = allocuvm(curproc->pgdir, sz, sz + n)) == 0)
      return -1;
  } else if(n < 0){
    if((sz = deallocuvm(curproc->pgdir, sz, sz + n)) == 0)
      return -1;
  }
  //更新process的memory size
  curproc->sz = sz;
  //將TSS和hardware page table轉至curproc
  switchuvm(curproc);
 
  return 0;
}

proc

struct proc {
uint sz;                     // process memory的大小 (bytes)
pde_t* pgdir;                // Page table
char *kstack;                // 此process的kernel stack底部的指針
enum procstate state;        // Process狀態
int pid;                     // Process ID
struct proc *parent;         // 母process的指針
struct trapframe *tf;        // 現在syscall的Trap frame
struct context *context;     // swtch() here to run process
void *chan;                  // 若為非0值, sleeping on chan
int killed;                  // If non-zero, have been killed
struct file *ofile[NOFILE];  // Open files
struct inode *cwd;           // Current directory
char name[16];               // Process名稱
};

process state可表示六種狀態：
enum procstate { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE };

allocuvm()

allocate新的page tables和physical memory，將process memory size從oldsz提升到newsz。
成功回傳新的memory size，失敗回傳0。

int
allocuvm(pde_t *pgdir, uint oldsz, uint newsz)
{
  char *mem;
  uint a;

  //檢查newsz是否大於KERNBASE，若是回傳0
  if(newsz >= KERNBASE)
    return 0;
  //檢查newsz是否小於oldsz，若是回傳oldsz
  if(newsz < oldsz)
    return oldsz;

  //將a設為oldsz所屬page上限
  //以a為起始點，allocate新的memory直到滿足newsz
  a = PGROUNDUP(oldsz);
  for(; a < newsz; a += PGSIZE){
    
    //allocate一段memory         
    mem = kalloc();
    
    //若kalloc()失敗，則deallocate剛剛嘗試allocate的區段
    //並cprintf報錯橫，傳回0
    if(mem == 0){
      cprintf("allocuvm out of memory\n");
      deallocuvm(pgdir, newsz, oldsz);
      return 0;
    }
    
    //將新allocate的memory初始為0
    memset(mem, 0, PGSIZE);
    
    //建立page directory中的所有entry
    //最後回傳新的memory size；
    //如果發生out of memory則釋放掉前面allocate的memory
    //回傳0
    if(mappages(pgdir, (char*)a, PGSIZE, V2P(mem), PTE_W|PTE_U) < 0){
      cprintf("allocuvm out of memory (2)\n");
      deallocuvm(pgdir, newsz, oldsz);
      kfree(mem);
      return 0;
    }
  }
  return newsz;
}

deallocuvm()

deallocate現有的user pages，把process的memory size由oldsz降為newsz。
成功回傳新的memory size。

deallocuvm(pde_t *pgdir, uint oldsz, uint newsz)
{
  pte_t *pte;
  uint a, pa;
 
  //檢查newsz是否大於oldsz，若是回傳oldsz
  if(newsz >= oldsz)
    return oldsz;
 
  // 將a設為newsz所屬page上限
  // 以a為起始點，deallocate現有memory直到滿足newsz
  a = PGROUNDUP(newsz);
  for(; a  < oldsz; a += PGSIZE){
    pte = walkpgdir(pgdir, (char*)a, 0);
    if(!pte)
      a = PGADDR(PDX(a) + 1, 0, 0) - PGSIZE;
    else if((*pte & PTE_P) != 0){
      pa = PTE_ADDR(*pte);
      if(pa == 0)
        panic("kfree");
      char *v = P2V(pa);
      kfree(v);
      *pte = 0;
    }
  }
  return newsz;
}

4. exec()

exec透過setupkvm\(\)分配了一個空閒的page table，然後透過 allocuvm\(\)為每個ELF分配memory，最後透過loaduvm\(\)把program segment載入memory中。

int
exec(char *path, char **argv)
{
  char *s, *last;
  int i, off;
  uint argc, sz, sp, ustack[3+MAXARG+1];
  struct elfhdr elf;
  struct inode *ip;
  struct proghdr ph;
  pde_t *pgdir, *oldpgdir;
  struct proc *curproc = myproc();

  begin_op();

  if((ip = namei(path)) == 0){
    end_op();
    cprintf("exec: fail\n");
    return -1;
  }
  ilock(ip);
  pgdir = 0;

  // 檢查ELF header
  if(readi(ip, (char*)&elf, 0, sizeof(elf)) != sizeof(elf))
    goto bad;
  if(elf.magic != ELF_MAGIC)
    goto bad;

  if((pgdir = setupkvm()) == 0)
    goto bad;

  // 將program載入memory.
  sz = 0;
  for(i=0, off=elf.phoff; i<elf.phnum; i++, off+=sizeof(ph)){
    if(readi(ip, (char*)&ph, off, sizeof(ph)) != sizeof(ph))
      goto bad;
    if(ph.type != ELF_PROG_LOAD)
      continue;
    if(ph.memsz < ph.filesz)
      goto bad;
    if(ph.vaddr + ph.memsz < ph.vaddr)
      goto bad;
    // 透過allocuvm為user process分配memory和建立page table
    // 如果失敗則報錯
    if((sz = allocuvm(pgdir, sz, ph.vaddr + ph.memsz)) == 0)
      goto bad;
    if(ph.vaddr % PGSIZE != 0)
      goto bad;
    //透過loaduvm將program segment載入到memory
    //如果失敗則報錯
    if(loaduvm(pgdir, (char*)ph.vaddr, ip, ph.off, ph.filesz) < 0)
      goto bad;
  }
  iunlockput(ip);
  end_op();
  ip = 0;

  // 在此page上限後再allocate 2 pages
  // 將第一個設為無法訪問，這樣當程式試圖使用超過一個page時的stack時就會報錯
  // 最後將第二個做為user stack
  sz = PGROUNDUP(sz);
  if((sz = allocuvm(pgdir, sz, sz + 2*PGSIZE)) == 0)
    goto bad;
  clearpteu(pgdir, (char*)(sz - 2*PGSIZE));
  sp = sz;

  // 輸入argument strings
  // 並設置好ustack剩下的stack空間
  for(argc = 0; argv[argc]; argc++) {
    if(argc >= MAXARG)
      goto bad;
    sp = (sp - (strlen(argv[argc]) + 1)) & ~3;
    if(copyout(pgdir, sp, argv[argc], strlen(argv[argc]) + 1) < 0)
      goto bad;
    ustack[3+argc] = sp;
  }
  ustack[3+argc] = 0;

  //將ustack[0]設為fake return PC
  //將ustack[1]設為argument counter
  //將ustack[2]設為argument strings指針
  ustack[0] = 0xffffffff;
  ustack[1] = argc;
  ustack[2] = sp - (argc+1)*4;

  sp -= (3+argc+1) * 4;
 
  //將ustack複製進pgdir中
  if(copyout(pgdir, sp, ustack, (3+argc+1)*4) < 0)
    goto bad;

  // 儲存程式名稱(debugging時可用)
  for(last=s=path; *s; s++)
    if(*s == '/')
      last = s+1;
  safestrcpy(curproc->name, last, sizeof(curproc->name));

  // Commit to the user image.
  oldpgdir = curproc->pgdir;
  curproc->pgdir = pgdir;
  curproc->sz = sz;
  curproc->tf->eip = elf.entry;  // main
  curproc->tf->esp = sp;
  switchuvm(curproc);
  freevm(oldpgdir);
  return 0;

 //只要前面有任何錯誤都會跳到這
 //釋放memory
 //最後回傳-1
 bad:
  if(pgdir)
    freevm(pgdir);
  if(ip){
    iunlockput(ip);
    end_op();
  }
  return -1;
}

setupkvm

可參考第一段。

allocuvm

可參考第三段。

loaduvm

將program segment載入pgdir中。
成功回傳0，失敗回傳-1。

int
loaduvm(pde_t *pgdir, char *addr, struct inode *ip, uint offset, uint sz)
{
  uint i, pa, n;
  pte_t *pte;
  
  //檢查addr是否有做page aligned
  //若沒有則報錯
  if((uint) addr % PGSIZE != 0)
    panic("loaduvm: addr must be page aligned");
 
  //遍歷整個page中的pte
  //透過walkpgdir來找到寫入ELF段的physical address
  //然後透過readi来將program segment從文件中讀出。
  for(i = 0; i < sz; i += PGSIZE){
    if((pte = walkpgdir(pgdir, addr+i, 0)) == 0)
      panic("loaduvm: address should exist");
    pa = PTE_ADDR(*pte);
    if(sz - i < PGSIZE)
      n = sz - i;
    else
      n = PGSIZE;
    if(readi(ip, P2V(pa), offset+i, n) != n)
      return -1;
  }
  return 0;
}

copyout

將長度lenbytes的data從p複製到page table pgdi中的user address
成功回傳0，失敗回傳-1

int
copyout(pde_t *pgdir, uint va, void *p, uint len)
{
  char *buf, *pa0;
  uint n, va0;

  buf = (char*)p;
 
  //複製長度len的資料
  while(len > 0){
    //va0為va所屬page的下限
    va0 = (uint)PGROUNDDOWN(va);
    
    //確保pgdir為PTE_U pages
    pa0 = uva2ka(pgdir, (char*)va0);
    if(pa0 == 0)
      return -1;
    n = PGSIZE - (va - va0);
    if(n > len)
      n = len;
    
    //移動data
    memmove(pa0 + (va - va0), buf, n);
                 
    //更新變數
    len -= n;
    buf += n;
    va = va0 + PGSIZE;
  }
  return 0;
}