作業系統 作業一

章節ch2 Page Table

隨班附讀 Ｍ121355 廖哲賢

章節閱讀概要

在作業系統中執行的程式（Process）及資料都會存在memory中,各有各自的地址,而由作業系統中的page table 通過page hardware 連接對應物理地址及虛擬地址。
本章節介紹的概念有

1. Page Hardware 說明
2. Process address space 程序的地址空間
3. creating an address space 創造一個地址空間（程式示範）
4. Physical memory allocation 物理記憶體的分派
5. Physical memory allocator 物理記憶體的分派（程式示範）

1.Page Hardware

以x86為例 ,不管是user還是kernel指令都是虛擬地址。電腦的RAM，或者物理記憶體，則是用物理地址來作標記的。x86 的Page hardware通過對應機制將虛擬地址和物理地址關聯起來。
閱讀文件後理解的架構及運作方式如下說明
page table entries （PTEs） ,包含了20-bit的物理頁碼physical page number (PPN)和12-bit 的flag(對應的虛擬地址的使用權限),paging hardware 使用前20-bit來找到該虛擬地址在頁表中的索引，然後把前20-bit替換為對應PTE的PPN。
對應地址分成兩步驟

1. 先從Virtual address前面10-bit找到對應process的Page Table。
2. 緊接著的10-bit找對應的PPN。

2.Process address space

每個Process的user memory 從virtual address的0開始倒定義的KERNBASE,最高允許的記憶體到2GB,在xv6的memlayout.h程式宣告了memory layout的相關參數。程式碼如下

// Memory layout

#define EXTMEM  0x100000            // Start of extended memory
#define PHYSTOP 0xE000000           // Top physical memory
#define DEVSPACE 0xFE000000         // Other devices are at high addresses

// Key addresses for address space layout (see kmap in vm.c for layout)
#define KERNBASE 0x80000000         // First kernel virtual address
#define KERNLINK (KERNBASE+EXTMEM)  // Address where kernel is linked

#define V2P(a) (((uint) (a)) - KERNBASE)
#define P2V(a) (((void *) (a)) + KERNBASE)

#define V2P_WO(x) ((x) - KERNBASE)    // same as V2P, but without casts
#define P2V_WO(x) ((x) + KERNBASE)    // same as P2V, but without casts

當Process向xv6要求更多的Memory時，xv6首先要找到空的物理頁，然後把這些頁對應的PTE加入該進程的頁表中，並讓PTE指向對應的物理頁。XV6設定了PTE中的PTE_U，PTE_W，PTE_P(定義為flag)。大多數process不會用完整個memory; XV6會把沒有被使用的PTE的PTE_P標誌位設為0。不同process的頁表將其user memory對應到不同的物理內存中，因此每個process就擁有了私有的用戶內存。

3.creating an address space 創造一個地址空間（程式示範）

程式檔案：vm.c

程式流程

資料結構

static struct kmap {
  void *virt;       //virtual address 開始位置
  uint phys_start;  //physical address 開始位置
  uint phys_end;    //physical address 結束位置
  int perm;         //存放page table的flag
} 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
};

function名稱：kvmalloc
代碼解釋：
呼叫setupkvm()初始化Page table,大多數的作業都在這個function發生。
switchkvm()來代換page table。

kvmalloc(void)
{
  kpgdir = setupkvm();
  switchkvm();
}

function名稱：setupkvm()

代碼解釋：
建造kernel所需要的page table。一開始呼叫kalloc()來存放Page Directory（變數pgdir），接下呼叫 mappages() 設定各層kmap值，若 mappages() return -1 就不再配置page table。

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

  if((pgdir = (pde_t*)kalloc()) == 0)
    return 0;
  memset(pgdir, 0, PGSIZE);
  if (P2V(PHYSTOP) > (void*)DEVSPACE)
    panic("PHYSTOP too high");
  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) {
      freevm(pgdir);
      return 0;
    }
  return pgdir;
}

function名稱：mappages(pde_t pgdir, void va, uint size, uint pa, int perm)

代碼解釋：
function作用是在page table建立一段virtual addresses到一段 physical addresses的對應,這一段的range是使用變數a及變數last來設定開始即結束區間,使用for迴圈呼叫walkpgdir跑一次迴圈a就加上PGSIZE,當a==last時跳出迴圈，用此來找到該地址對應的PTE地址。然後初始化該PTE以保存對應PPN

static int
mappages(pde_t *pgdir, void *va, uint size, uint pa, int perm)
{
  char *a, *last;
  pte_t *pte;

  a = (char*)PGROUNDDOWN((uint)va);
  last = (char*)PGROUNDDOWN(((uint)va) + size - 1);
  for(;;){
    if((pte = walkpgdir(pgdir, a, 1)) == 0)
      return -1;
    if(*pte & PTE_P) 
      panic("remap");
    *pte = pa | perm | PTE_P;
    if(a == last)
      break;
    a += PGSIZE;
    pa += PGSIZE;
  }
  return 0;
}

function名稱：walkpgdir(pde_t pgdir, const void va, int alloc)

代碼解釋：
function是實作virtual addresses尋找PTE，如此章節所講述，使用virtual addresses前10-bit來尋找page directory entry，如果存在，在使用後10-bit來找尋PTE，反之，若不存在及alloc參數未被設置，說明要找的page table尚未分配

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

  pde = &pgdir[PDX(va)];
  if(*pde & PTE_P){
    pgtab = (pte_t*)P2V(PTE_ADDR(*pde));
  } else {
    if(!alloc || (pgtab = (pte_t*)kalloc()) == 0)
      return 0;
    // Make sure all those PTE_P bits are zero.
    memset(pgtab, 0, PGSIZE);
    // The permissions here are overly generous, but they can
    // be further restricted by the permissions in the page table
    // entries, if necessary.
    *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;
  }
  return &pgtab[PTX(va)];
}

4.Physical memory allocation 物理記憶體的分派

在process運行時，kernel需要為page table、process’s user memory、kernel stacks, a pipe buffers分配空閒的Physical memory。

xv6使用從內核結尾到PHYSTOP之間的Physical memory為運行時分配提供memory資源。每次分配，它會將整塊4096-byte的page配出去。

5.Physical memory allocator （程式示範）

程式檔案：kalloc.c

流程圖

資料結構

struct run {
  struct run *next;
};

//kmem是用來存放free list的，並且加入lock來管理
struct {
  struct spinlock lock; //放入lock 的struct
  int use_lock;         //選擇是否要用lock，要的話填1
  struct run *freelist; //放入free list
} kmem;

function名稱：kinit1, kinit2
代碼解釋：
定義兩個方法是因為kinit1在前4MB不能使用lock 及 memory。而kinit2允許使用lock，並使得更多的內存可用於分配。可以從程式碼看到kmem.use_lock設0，kinit2使用Lock，因此kmem.use_lock改設為1，兩個代碼都有呼叫function freerange。

void
kinit1(void *vstart, void *vend)
{
  initlock(&kmem.lock, "kmem");
  kmem.use_lock = 0;
  freerange(vstart, vend);
}

void
kinit2(void *vstart, void *vend)
{
  freerange(vstart, vend);
  kmem.use_lock = 1;
}

function名稱：freerange

代碼解釋：
function 宣告 p 變數利用PGROUNDUP函式來確保分配器只會釋放對齊的Physical Adress，使用for迴圈來將一個個page 當做參數傳入kfree，由kfree分配器來管理。

void
freerange(void *vstart, void *vend)
{
  char *p;
  p = (char*)PGROUNDUP((uint)vstart);
  for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
    kfree(p);
}

function名稱：kfree

代碼解釋：
function kinit會使用P2V(PHYSTOP)來將PHYSTOP（一個物理地址）轉成為虛擬地址。首先將memory的每個byte設為1。讓已被釋放memory讀到的不是原數據，接下來kfree把v轉換為一個指向struct run的指針，在r->next中保存原有 free list ，然後將其設置為r。kalloc移除並返回 free list的第一個元素 。

void
kfree(char *v)
{
  struct run *r;

  if((uint)v % PGSIZE || v < end || V2P(v) >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(v, 1, PGSIZE);

  if(kmem.use_lock)
    acquire(&kmem.lock);
  r = (struct run*)v;
  r->next = kmem.freelist;
  kmem.freelist = r;
  if(kmem.use_lock)
    release(&kmem.lock);
}