作業系統 HW1

Ch.2 Page tables

四資工三 B10415037 陳品劭

Page tables在作業系統中，擔任了memory之間溝通的腳色，其儲存了虛擬位址到實體位址間的對映。一隻程式可能會使用一塊大的連續的memory，但實際上他們會分散在實體memory的各處。透過Page tables，使系統在執行程式時，可以更容易對memory進行操作。

虛擬記憶體與實體記憶體的轉換:硬體部分要用前20位元的PPN找到page table中對應PPN的page table entries(PTE)，將PPN置換，而後12位元原樣複製。
一個 Page table由 2^20 個PTE的陣列組成，每個PTE由一個20 bit 的PPN與一些Flag(12 bits)組成，共32 bits。
在memory address的轉換上，需經過兩步驟。page table以一個two-level的樹狀結構儲存在實體memory上。樹的root是一個4096 Byte的 page directory，存放1024筆類似PTE的資料指向(reference to) page table pages。
每個 page table page 儲存1024組各32 bits的PTE，virtual address 的前10 bits決定page directory entry。若此page directory entry被使用，會用接下來的10 bits 會用於page table entry，若都沒有被使用，則會報錯。

PTE 的 Flag

P:是否陳列在 page table中。
W:是否能對此page執行write。
U:User 能否使用此page。

Process address space

每個process都有自己的page table，系統會在process切換時，同時切換page table。
user可用的memory，從0到KERNBASE，一個process最多能用2GB的memory。沒有用到的PTE，flag_P會被設為0。
每個process的page table都保留一段空間給kernel，讓kernel可以存放自己的指令及data。KERNBASE:KERNBASE+PHYSTOP 對應到 0:PHYSTOP。

Code: creating an address space

main呼叫 kvmalloc，create一個page table。kvmalloc呼叫setupkvm執行大部分的工作，先Allocate一塊記憶體給Page directory，然後呼叫mappages建立虛擬memory和實體memory的mapping。
mappages 呼叫 walkpgdir 找到對應的PTE，並初始化。walkpgdir透過address的前10bit找到page directory entry，若該page directory entry不存在，表示該page table page尚未被allocate。若存在，則會用接下來的10bits找到page table page的PTE。

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

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

    if((pgdir = (pde_t*)kalloc()) == 0) //allocate
        return 0;
    memset(pgdir, 0, PGSIZE); // 初始化 page directory
    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) 
        //建立kernel需要的mapping
     {
         freevm(pgdir);
         return 0;
     }
     return pgdir;
 }
 
 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;
 }
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;

         memset(pgtab, 0, PGSIZE);
         *pde = V2P(pgtab) | PTE_P | PTE_W | PTE_U;
     }
     return &pgtab[PTX(va)];
 }

Physical memory allocation

OS要控管資源，閒置的記憶體需要被OS收回，xv6用了一個Physical memory allocator來完成這件事。

Code: Physical memory allocator

main 呼叫kinit1、kinit2 初始化 allocator。kinit1 allocate 一塊
沒有被lock的4MB memory，kinit2 將lock 啟用，讓其他memory 可以被allocate。

kinit1 和 kinit2呼叫 freerange 將memory 加到free list，freerange 透過呼叫kfree 實現此功能。

p2v(PHYSTOP)將一個實體的address轉為一個虛擬的address。

kfree先將每個被release的Byte設為1，這樣能讓錯誤的程式在讀取已被釋放的memory時，盡快報錯。然後將v assign 給 r，r−>next = kmem.freelist，歸還memory。

 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;
 }
 void freerange(void *vstart, void *vend)
 {
     char *p;
     p = (char*)PGROUNDUP((uint)vstart);
     for(; p + PGSIZE <= (char*)vend; p += PGSIZE)
         kfree(p);
 }
 
 void kfree(char *v)
 {
 struct run *r;

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


 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);
 }

User part of an address space

xv6 中，一個process的user可用的memory。stack佔一個page，存放參數。當stack的access超出範圍時，guard page作為保護機制。heap可以用sbrk()進行增長。

Code: sbrk

system呼叫 growproc，若n>0，則allocate一或多塊memory並mapping到 process top 的空間。若n<0，則不會allocate，並釋放對應的page。

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

     sz = curproc−>sz;
     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;
     }
         curproc−>sz = sz;
         switchuvm(curproc);
     return 0;
 }
 
 int
 deallocuvm(pde_t *pgdir, uint oldsz, uint newsz)
 {
     pte_t *pte;
     uint a, pa;

     if(newsz >= oldsz)
         return oldsz;

     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;
 }
 
 int allocuvm(pde_t *pgdir, uint oldsz, uint newsz)
 {
     char *mem;
     uint a;

     if(newsz >= KERNBASE)
         return 0;
     if(newsz < oldsz)
         return oldsz;

     a = PGROUNDUP(oldsz);
     for(; a < newsz; a += PGSIZE){
         mem = kalloc();
     if(mem == 0){
         cprintf("allocuvm out of memory\n");
         deallocuvm(pgdir, newsz, oldsz);
         return 0;
     }
     memset(mem, 0, PGSIZE);
     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;
 }