Memory Management Walk Through

Page Tables

Page tables determine what memory address mean, what part of physical memory can be accessed.

A page table gives the operating system control over virtual to-physical address translations at the granularity of aligned chunks of 4096 (2^12) bytes.

Page Table

Creating kernel address space

See process allocation section.

Allocate a kernel stack for each process

procinit (kernel/proc.c:24), which is called from main, allocates a kernel stack for each process. It maps each stack at the virtual address generated by KSTACK, which leaves room for the invalid stack-guard pages. kvmmap adds the mapping PTEs to the kernel page table, and the call to kvminithartreloads the kernel page table into satp so that the hardware knows about the new PTEs.

void
procinit(void)
{
  struct proc *p;

  initlock(&pid_lock, “nextpid”);
  for(p = proc; p < &proc[NPROC]; p++) {
      initlock(&p->lock, “proc”);

      // Allocate a page for the process’s kernel stack.
      // Map it high in memory, followed by an invalid
      // guard page.
      char *pa = kalloc();
      if(pa == 0)
        panic(“kalloc”);
      uint64 va = KSTACK((int) (p - proc));
      kvmmap(va, (uint64)pa, PGSIZE, PTE_R | PTE_W);
      p->kstack = va;
  }
  kvminithart();
}

// map kernel stacks beneath the trampoline,
// each surrounded by invalid guard pages.
#define KSTACK(p) (TRAMPOLINE - ((p)+1)* 2*PGSIZE)

Diagram of kernel stack address space

Stack grows downwards.

TLB cache

Each RISC-V core caches page table entries in a Translation Look-aside Buffer (TLB), and when xv6 changes a page table, it must tell the CPU to invalidate corresponding cached TLB entries.

The RISC-V has an instruction sfence.vma that flushes the current core’s TLB. xv6 executes sfence.vma in kvminithart after reloading the satp register, and in the trampoline code that switches to a user page table before returning to user space (kernel/trampoline.S:79).

Physical Memory Allocation

The allocator sometimes treats addresses as integers in order to perform arithmetic on them (e.g., traversing all pages in freerange), and sometimes uses addresses as pointers to read and write memory (e.g., manipulating the run structure stored in each page).

xv6 buddy allocator

Process Address Space

TODO

How exec works

How exec() works

1. Find inode by path

2. Check ELF header

3. Load program by memory. uvmalloc to allocate new size.

4. loadseg load file to memory address at ph.vaddr. Note: Exec loads bytes from the ELF file into memory at addresses specified by the ELF file.

5. Allocate 2 pages. 2nd one is user stack.

6. Push args to stack. Prepare ustack to save each argument with its address.

7. Push the array of argv[] pointers (ustack) to stack.

8. Set sp to a1.

9. Commit to user image. Free old process’ page table.

10. Set epc, sp, sz.

11. return argc which set argc in reg a0. Now we have main(args, args) from entry, a0, a1.

How stack look after pushing args?

Find PA from VA

  uint64 off = va % PGSIZE;
  pte_t *pte;
  uint64 pa;

  pte = walk(kernel_pagetable, va, 0);
  pa = PTE2PA(*pte);
  return pa+off;

This code is to find a physical address from virtual address. The PA from *pte is at start of page. We also need to add offset to it when return.

Exercises

Explain how the following functions work:

int     mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm);
uint64  walkaddr(pagetable_t pagetable, uint64 va);

static pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)

int     copyout(pagetable_t pagetable, uint64 dstva, char *src, uint64 len);
int     copyin(pagetable_t pagetable, char *dst, uint64 srcva, uint64 len);

void    uvmunmap(pagetable_t pagetable, uint64 va, uint64 size, int do_free);
void    freewalk(pagetable_t pagetable)