Ch2__Page Table

Page Table 比較重要的意義在於讓不同process的memory adress translate(map)到physical adress，這樣可以保護不同process的記憶體。

Paging hardware

page table hardware就是藉由mapping連接下面這兩種Adress

xv6裡面的指令(kernel,User)都是用Virtual Adress
machine’s RAM, physical memory,用到的是 physical Adress

Page Table Entire

一整個pageTable包含的是2^20 PTEs(Page Table Entire)
每個PTE有20 bit PPN(Physical Page Number)和12 bit flag

整體來說

底層是Page Directory(含有1024個32 bit PTE)
Page Directory指向的又是一個Page Table(亦含有1024個32 bit PTE)

所以Page Table Hardware就是採用這樣雙重的結構maping，可以讓大部分的virtual Adress有unmapping的情況。
其上面有關Flag定義和Page Table Hardware相關的sturct都定義在 mmu.h裡面。

Process address space

雖然從entry建立pageTable可以讓kernel裡的C code可以執行，但main還是有使用kernel裡kvmalloc來建立一些更縝密的pageTable
每個process 都有自己的pageTable，切換process時也會通知pageTable Hardware切換pageTable
User可以用的virtual adress從0開始到KERNELBASE
一個kernel裡的process只能用到最多2GB
有一些使用memory map 的 I/O 存在 0xFE000000 之上，xv6採用直接mapping。
memlayout.h宣告了memory layout的常數，ex:KERNELBASE
當process需要更多的memory時:
1. 先找到free的physical merory
2. 然後加入PTE進pageTable.
3. KERN-BASE:KERNBASE+PHYSTOP map to 0:PHYSTOP.

Code: creating an address space

main call了 kvmalloc 創建並切換了pageTable(KERNALBASE上所需要的)

int 
main(void)
{
    kinit1(end, P2V(4*1024*1024)); // phys page allocator
    kvmalloc();      // kernel page table <-------------------------------------Here
    mpinit();        // detect other processors
    lapicinit();     // interrupt controller
    seginit();       // segment descriptors
    picinit();       // disable pic
    ioapicinit();    // another interrupt controller
    consoleinit();   // console hardware
    uartinit();      // serial port
    pinit();         // process table
    tvinit();        // trap vectors
    binit();         // buffer cache
    fileinit();      // file table
    ideinit();       // disk 
    startothers();   // start other processors
    kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after startothers()
    userinit();      // first user process
    mpmain();        // finish this processor's setup
}

// Allocate one page table for the machine for the kernel address
// space for scheduler processes.
void
kvmalloc(void)
{
    kpgdir = setupkvm();
    switchkvm();
}

大部分的事情發生在setupkvm

他call了mappages來 install kernel 需要的 translations 會在kmap裡被提及，但只是set-up實際上不會被建立

// Set up kernel part of a 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) { //<-Here
            freevm(pgdir);
            return 0;
        }
        return pgdir;
}

mappages裡又call了walkpgdir找到該地址的PTE，並initializes the PTE，且 Set 權限及將 PTE_P 標為 valid

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) //<----------------------Here
            return -1;
        if(*pte & PTE_P)
            panic("remap");                     // initializes the PTE
        *pte = pa | perm | PTE_P;               // Set 權限及將 PTE_P 標為 valid
        if(a == last)
            break;
        a += PGSIZE;
        pa += PGSIZE;
}
return 0;
}

如之前所說先找高位元 10 bit 的 pageDirectory，再找後 10 bit 的 pageTable

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

Flow

Physical memory allocation

kernal 在 run-time 時必須為 pageTable Process… 去 allocate 和 free physical memory
xv6 使用 kernel 裡 end 到 PHYSTOP 的 physical memory 區分配一整個 pageTable

Code: Physical memory allocator

allocator 的資料結構是 free list 位在 struct run
```
struct run {
    struct run *next;
};
```
而這個free list 由一個 spin lock 所保護，ch4 會詳細說明

從 main 開始 call 了 kinit1 和 kinit2 去初始化 allocator

int 
main(void)
{
    kinit1(end, P2V(4*1024*1024)); // phys page allocator <-------------------------------------Here
    kvmalloc();      // kernel page table 
    mpinit();        // detect other processors
    lapicinit();     // interrupt controller
    seginit();       // segment descriptors
    picinit();       // disable pic
    ioapicinit();    // another interrupt controller
    consoleinit();   // console hardware
    uartinit();      // serial port
    pinit();         // process table
    tvinit();        // trap vectors
    binit();         // buffer cache
    fileinit();      // file table
    ideinit();       // disk 
    startothers();   // start other processors
    kinit2(P2V(4*1024*1024), P2V(PHYSTOP)); // must come after <-------------------------------------Herestartothers()
    userinit();      // first user process
    mpmain();        // finish this processor's setup
}

kinit1 和 kinit2 會去call freerange 對每個 page call kfree 將 memory 加入 free list ，其中使用到常數PGROUNDUP確保釋放對齊的物理位置

// Initialization happens in two phases.
// 1. main() calls kinit1() while still using entrypgdir to place just
// the pages mapped by entrypgdir on free list.
// 2. main() calls kinit2() with the rest of the physical pages
// after installing a full page table that maps them on all cores.
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);
}

Flow

User part of an address space

上圖說明清楚，每個Adress從0開始 text -> data -> stack -> heap，call sbrk使 heap 增長，而 stack 是一個 page ，顯示exec創建的一些基本參數(如圖所示)
guard page 沒有 map ，避免 stack 超出發生問題，設在下面，若發生問題也只會找到 unmap 的 page

Code: sbrk

sbrk 是一個system call 使 heap 增長，由growproc實作

int
sys_sbrk(void)
{
    int addr;
    int n;

    if(argint(0, &n) < 0)
        return -1;
    addr = myproc()->sz;
    if(growproc(n) < 0)
        return -1;
    return addr;
}

growproc由 n 的正負決定call allocuvm or deallocuvm

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

Flow

Code: exec

exec 是一個systemcall，中間透過namei開啟檔案，Ch6 會提及

他讀取的會是ELF檔，在elf.h提及

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) {  <-----------------------------------HERE
        end_op();
        cprintf("exec: fail\n");
        return -1;
    }
    ......

// File header
struct elfhdr {
    uint magic;  // must equal ELF_MAGIC
    uchar elf[12];
    ushort type;
    ushort machine;
    uint version;
    uint entry;
    uint phoff;
    uint shoff;
    uint flags;
    ushort ehsize;
    ushort phentsize;
    ushort phnum;
    ushort shentsize;
    ushort shnum;
    ushort shstrndx;
};

// Program section header
struct proghdr {
    uint type;
    uint off;
    uint vaddr;
    uint paddr;
    uint filesz;
    uint memsz;
    uint flags;
    uint align;
};

然後確認ELF檔，執行setupkvm 建pageTable

    ......
    // Check 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;
    ......

執行allocuvm allocate再用，loaduvm load進memory

    ......
    // Load program into 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;
    ......

建立guard State，預防

......
// Allocate two pages at the next page boundary.
// Make the first inaccessible.  Use the second as the user stack.
sz = PGROUNDUP(sz);
if ((sz = allocuvm(pgdir, sz, sz + 2 * PGSIZE)) == 0)
	goto bad;
clearpteu(pgdir, (char*)(sz - 2 * PGSIZE));
sp = sz;
......

參數資料的stack

    ......
    // Push argument strings, prepare rest of stack in ustack.
    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;
    ......

如果遭遇錯誤就會跳到bad去情除然後return-1，沒事就好安裝一些image 然後return 0

    ......
    // Save program name for 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;

bad:
    if (pgdir)
        freevm(pgdir);
    if (ip) {
        iunlockput(ip);
        end_op();
    }
    return -1;
}

Flow