Chapter2 Page Table

OS透過Page Tables的機制來控制memory，而xv6主要就是利用page tables來區分address space以及保護memory，同時亦使用一些page table的簡單技巧:

  1. 同一段address mapping到多個不同的address space。
  2. 同一段address多次mapping到一個address space。
  3. 透過一個unmapped page保護使用者的stack。

Paging Tble

x86 page table的組成:

  1. 一個2^20 page table entries(PTEs)的array。
  2. 每個PTE包含20-bit的physical page number(PPE)以及一些flags。

Page table被儲存在physical memory內，有著類似two-level tree的結構:

address translation包含兩個步驟:

  1. paging hardware 使用virtual address的前10 bits來選擇page directory entry。
  2. 如果 page directory entry是存在那麼就繼續執行；page hardware 使用virtual address的下10 bits，從page table page中選出對應的PTE。

如果page directory entry或者PTE是不存在的，就會造成page hardware錯誤。每一個PTE包含一些flag bits用來說明virtual addess的使用權限，flag bits包含:

  1. PTE_P: 是否PTE存在。
  2. PTE_W: instructions能否被允取寫入page，不允許則只能進行讀取與取指令。
  3. PTE_U: 用戶端是否被允許使用page，不允許則只有kernel被允許使用page。

Process aaddress space

Entry所建立的page tale是足夠來讓kernel的C運行的，然而main仍然會呼叫kvmalloc來轉換到新的page table，因為kernel更精巧的描述process address space。






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

一個process的user memory從virtual address的0開始，最多能增長到KERNBASE，這讓process最多只能使用2GB的memory。當一個process向xv6要求更多的mamory的時候:

  1. xv6首先會到physical pages找尋儲存空間。
  2. 將PTEs放入process’s page table。
  3. PTEs指向新的physical page。

Code: creating an address space

main會呼叫kvmalloc來建立以及轉換到一個能夠mapping到KERNBASE之上的page table來供kernel運行，而這裡多數的工作都是由setupkvm所完成的。

















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->phy_s_start(uint)k->phy_s_start,k->perm)<0){
    freevm(pgdir);
    return 0;
    }
}























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;//紀錄PTE是否為有效
        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)];//找尋page directory entry
    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)];//找到page table pgae內的PTE
}

Code: Physical memory allocator

Allocator的資料結構是一個physical memory pages的free list













struct run 
{
    struct run *next;
};//free page's list的element

//用來保護free list的spin lock
struct 
{
    struct spinlock lock;
    int use_lock;
    struct run *freelist;
} kmem;













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 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

每一個user process從adderss 0開始，最底層包含了user program、data以及stack；而heap在stack之上如此一來當process呼叫sbrk才能擴大。

Code: sbrk

Sbrk是一個system call來讓process增減其memory，這個system call是由growproc這個function來執行。





















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

Code: exec

Exec是system call，建立使用者部分的address space，並且使用文件系統的文件來初始化部分只用者的address space。









































































































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;


    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;
        if((sz = allocuvm(pgdir, sz, ph.vaddr + ph.memsz)) == 0)
            goto bad;
        if(ph.vaddr % PGSIZE != 0)
            goto bad;
        if(loaduvm(pgdir, (char*)ph.vaddr, ip, ph.off, ph.filesz) < 0)
            goto bad;
    }
    iunlockput(ip);
    end_op();
    ip = 0;

//在下一個page boundary allocate兩個pages
    sz = PGROUNDUP(sz);
    if((sz = allocuvm(pgdir, sz, sz + 2*PGSIZE)) == 0)
        goto bad;
    clearpteu(pgdir, (char*)(sz − 2*PGSIZE));
    sp = sz;

    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] = 0xffffffff; // fake return PC
    ustack[1] = argc;
    ustack[2] = sp − (argc+1)*4; // argv pointer
    
    sp −= (3+argc+1) * 4;
    if(copyout(pgdir, sp, ustack, (3+argc+1)*4) < 0)
        goto bad;

    for(last=s=path; *s; s++)
        if(*s == ’/’)
            last = s+1;
    safestrcpy(curproc−>name, last, sizeof(curproc−>name));

    oldpgdir = curproc−>pgdir;
    curproc−>pgdir = pgdir;
    curproc−>sz = sz;
    curproc−>tf−>eip = elf.entry; // main
    6700 curproc−>tf−>esp = sp;
    switchuvm(curproc);//建置新的image
    freevm(oldpgdir);//釋放舊的image
    return 0;

    bad:
        if(pgdir)
            freevm(pgdir);//釋放新的image
        if(ip)
        {
            iunlockput(ip);
            end_op();
        }
    return −1;
}