Physical memory, sbrk and page faults

1warm-upChoose one

kalloc and kfree keep a linked list of free pages. Where are the list’s nodes stored?

kernel/kalloc.c

17struct run {
18  struct run *next;
19};
20
21struct {
22  struct spinlock lock;
23  struct run *freelist;
24} kmem;

In an array of 32,768 entries in the kernel’s .bss, one per physical page.In nodes allocated with malloc in the kernel.In the first 8 bytes of each free page itself, read as a struct run.In the kernel page table, as PTEs with V clear.

2solidType a number

In this build the kernel image ends at end = 0x80020bb0, and PHYSTOP is 0x88000000. How many pages does freerange put on the free list at boot?

kernel/kalloc.c

26void
27kinit()
28{
29  initlock(&kmem.lock, "kmem");
30  freerange(end, (void *)PHYSTOP);
31}
32
33void
34freerange(void *pa_start, void *pa_end)
35{
36  char *p;
37  p = (char *)PGROUNDUP((uint64)pa_start);
38  for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE)
39    kfree(p);
40}

decimal, 0x hex or 0b binary

3warm-upChoose one

Right after kinit, which physical page does the first kalloc return (it becomes the root of the kernel page table)?

kernel/kalloc.c

33void
34freerange(void *pa_start, void *pa_end)
35{
36  char *p;
37  p = (char *)PGROUNDUP((uint64)pa_start);
38  for (; p + PGSIZE <= (char *)pa_end; p += PGSIZE)
39    kfree(p);
40}

0x87fff000, the highest page below PHYSTOP0x80021000, the first page after the kernel0x88000000, PHYSTOP0x80020bb0, the address of end

4solidChoose one

kalloc fills each page it hands out with 0x05 bytes instead of zeros, even though many callers then zero it themselves. Why?

kernel/kalloc.c

68void *
69kalloc(void)
70{
71  struct run *r;
72
73  acquire(&kmem.lock);
74  r = kmem.freelist;
75  if (r)
76    kmem.freelist = r->next;
77  release(&kmem.lock);
78
79  if (r)
80    memset((char *)r, 5, PGSIZE); // fill with junk
81  return (void *)r;
82}

Because 5 is the fastest value to store on RISC-V.Zeros would hide bugs where a caller uses memory without initialising it, and some callers overwrite the whole page anyway.To mark the page as allocated, so kfree can detect a double free.Because zeroing must be done under kmem.lock, which would slow other harts.

5warm-upClick the line

A program calls sbrklazy(4096). Click the line in sys_sbrk that is the entire allocation work the kernel does for it.

kernel/sysproc.c

39uint64
40sys_sbrk(void)
41{
uint64 addr;
int t;
int n;
45
argint(0, &n);
argint(1, &t);
addr = myproc()->sz;
49
if (t == SBRK_EAGER || n < 0) {
  if (growproc(n) < 0) {
    return -1;
  }
} else {
  // Lazily allocate memory for this process: increase its memory
  // size but don't allocate memory. If the processes uses the
  // memory, vmfault() will allocate it.
  if (addr + n < addr)
    return -1;
  if (addr + n > TRAPFRAME)
    return -1;
  myproc()->sz += n;
}
return addr;
65}

Your pick: none yet (click a line in the code)

6solidChoose all that apply

kalloc returns pages full of 0x05 junk. Which of these functions zero the page they get from kalloc before using it?

vmfault, for a lazily allocated pageuvmcopy, for the child’s copy of a pagewalk, for a new page-table pageuvmalloc, for a new heap pageproc_mapstacks, for the kernel stacksallocproc, for the trapframe page

7solidClick the line

Click the line in vmfault that makes a user-mode store to the stack’s guard page fatal instead of quietly supplying a new page.

kernel/vm.c

458uint64
459vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
460{
uint64 mem;
462
if (va >= psz)
  return 0;
va = PGROUNDDOWN(va);
if (ismapped(pagetable, va)) {
  return 0;
}
mem = (uint64)kalloc();
if (mem == 0)
  return 0;
memset((void *)mem, 0, PGSIZE);
if (mappages(pagetable, va, PGSIZE, mem, PTE_W | PTE_U | PTE_R) != 0) {
  kfree((void *)mem);
  return 0;
}
return mem;
478}

Your pick: none yet (click a line in the code)

8solidPut in order

After sbrklazy(1 << 30), usertests stores to 0x13000, a page that is not mapped yet. Put the events in order.

usertrap sees scause 15 and calls vmfault with p->sz and stval
The store finds a level-0 PTE with V clear and raises a store page fault: scause 15, stval 0x13000
userret installs the user page table between two sfence.vma and executes sret
vmfault checks 0x13000 < sz and that the page is not mapped, then kallocs, zeroes and maps it R W U
uservec saves the user registers in the trapframe and switches satp to the kernel page table
The same store executes again, since sepc was not advanced, and succeeds

9deepFill in the machine state

A process takes a page fault on a lazily allocated heap page. usertrap calls vmfault, which calls kalloc, which has just acquired kmem.lock. What is the state of this hart?

kernel/trap.c

if (r_scause() == 8) {
  // system call
56
  if (killed(p))
    kexit(-1);
59
  // sepc points to the ecall instruction,
  // but we want to return to the next instruction.
  p->trapframe->epc += 4;
63
  // an interrupt will change sepc, scause, and sstatus,
  // so enable only now that we're done with those registers.
  intr_on();
67
  syscall();
} else if ((which_dev = devintr()) != 0) {
  // ok
} else if ((r_scause() == 15 || r_scause() == 13) &&
           vmfault(p->pagetable, p->sz, r_stval(),
                   (r_scause() == 13) ? 1 : 0) != 0) {
  // page fault on lazily-allocated page

Privilege modeActive stackPage table (satp)Interrupts (sstatus.SIE)noffintena

10deepTrue or false, and why

True or false: after sbrk(-8192) frees two pages, xv6 must flush them from the TLB, but it forgets to, so the program could still reach the freed pages through stale TLB entries.

kernel/vm.c

248uint64
249uvmdealloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz)
250{
251  if (newsz >= oldsz)
252    return oldsz;
253
254  if (PGROUNDUP(newsz) < PGROUNDUP(oldsz)) {
255    int npages = (PGROUNDUP(oldsz) - PGROUNDUP(newsz)) / PGSIZE;
256    uvmunmap(pagetable, PGROUNDUP(newsz), npages, 1);
257  }
258
259  return newsz;
260}

TrueFalse

Why?

uservec flushed the whole TLB right after installing the kernel page table, and userret flushes again around installing the user table; the process runs on only one hart at a time, so no other hart holds its translations either.uvmunmap sets the PTEs to 0, and the hardware always rereads PTEs from memory.kfree fills the pages with 0x01, so a stale access would be harmless.

11deepType a number

In our run, the usertests child running lazy_alloc had p->sz = 0x12000 when it called sbrklazy(1 << 30). It then stores to 0x13000, 0x53000, … , every 64 pages, 4096 stores in all. Besides the 4096 data pages, how many page-table pages does walk allocate during these faults?

user/usertests.c

2627void
2628lazy_alloc(char *s)
2629{
2630  char *i, *prev_end, *new_end;
2631
2632  prev_end = sbrklazy(REGION_SZ);
2633  if (prev_end == (char *)SBRK_ERROR) {
2634    printf("sbrklazy() failed\n");
2635    exit(1);
2636  }
2637  new_end = prev_end + REGION_SZ;
2638
2639  for (i = prev_end + PGSIZE; i < new_end; i += 64 * PGSIZE)
2640    *(char **)i = i;
2641
2642  for (i = prev_end + PGSIZE; i < new_end; i += 64 * PGSIZE) {
2643    if (*(char **)i != i) {
2644      printf("failed to read value from memory\n");
2645      exit(1);
2646    }
2647  }
2648
2649  exit(0);

decimal, 0x hex or 0b binary

12warm-upChoose one

A process with p->sz = 0x5000 calls sbrk(65536) and it succeeds. What does sbrk return?

kernel/sysproc.c

39uint64
40sys_sbrk(void)
41{
uint64 addr;
int t;
int n;
45
argint(0, &n);
argint(1, &t);
addr = myproc()->sz;
49
if (t == SBRK_EAGER || n < 0) {
  if (growproc(n) < 0) {
    return -1;
  }
} else {
  // Lazily allocate memory for this process: increase its memory
  // size but don't allocate memory. If the processes uses the
  // memory, vmfault() will allocate it.
  if (addr + n < addr)
    return -1;
  if (addr + n > TRAPFRAME)
    return -1;
  myproc()->sz += n;
}
return addr;
65}

0x15000, the new end of memory0, meaning success0x5000, the old end, which is the start of the new memory0x5000 + 65536, rounded up to a page

13solidChoose one

kexec maps the user stack’s guard page and then clears its PTE_U, instead of simply leaving the page unmapped. In this kernel, why does that difference matter?

kernel/exec.c

// Allocate some pages at the next page boundary.
// Make the first inaccessible as a stack guard.
// Use the rest as the user stack.
sz = PGROUNDUP(sz);
uint64 sz1;
if ((sz1 = uvmalloc(pagetable, sz, sz + (USERSTACK + 1) * PGSIZE, PTE_W)) ==
    0)
  goto bad;
sz = sz1;
uvmclear(pagetable, sz - (USERSTACK + 1) * PGSIZE);
sp = sz;
stackbase = sp - USERSTACK * PGSIZE;

The guard page is below sz, and vmfault treats an unmapped page below sz as a lazily allocated one, so an unmapped guard would quietly get a fresh page.So that the kernel can still use the guard page as extra stack during system calls.A missing PTE would cause a kernel panic instead of a user page fault.Unmapped pages cannot exist below sz in xv6.

14deepType a number

A process has p->sz = 0x5000 (page-aligned, nothing mapped above it). It calls sbrk(1) and then sbrk(1) again, both eager. How many physical pages does uvmalloc allocate in total across the two calls?

kernel/vm.c

215// Allocate PTEs and physical memory to grow a process from oldsz to
216// newsz, which need not be page aligned.  Returns new size or 0 on error.
217uint64
218uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
219{
char *mem;
uint64 a;
222
if (newsz < oldsz)
  return oldsz;
225
oldsz = PGROUNDUP(oldsz);
for (a = oldsz; a < newsz; a += PGSIZE) {
  mem = kalloc();
  if (mem == 0) {
    uvmdealloc(pagetable, a, oldsz);
    return 0;
  }
  memset(mem, 0, PGSIZE);
  if (mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R | PTE_U | xperm) !=
      0) {
    kfree(mem);
    uvmdealloc(pagetable, a, oldsz);
    return 0;
  }
}
return newsz;
242}

decimal, 0x hex or 0b binary

15deepChoose one

A process has p->sz = 0x5000 (page-aligned, nothing mapped above it). It calls sbrklazy(1), then, as its very next memory access above 0x5000, stores a byte at 0x5800. What happens?

kernel/vm.c

458uint64
459vmfault(pagetable_t pagetable, uint64 psz, uint64 va, int read)
460{
461  uint64 mem;
462
463  if (va >= psz)
464    return 0;
465  va = PGROUNDDOWN(va);
466  if (ismapped(pagetable, va)) {
467    return 0;
468  }

The store succeeds without any fault, because sbrklazy maps a page when n is small.sys_sbrk rejects sbrklazy(1) because 1 is not a multiple of the page size.The process is killed, because 0x5800 is not below the new sz (0x5001), so vmfault refuses.vmfault maps page 0x5000 and the store succeeds, as it would after sbrk(1).

16solidChoose all that apply

Which of these functions can call vmfault to allocate a lazily promised page?

17solidChoose one

A program grows its memory with sbrklazy, writes machine code into the new region (which faults the page in), and then jumps to it. What happens at the jump?

kernel/trap.c

} else if ((which_dev = devintr()) != 0) {
  // ok
} else if ((r_scause() == 15 || r_scause() == 13) &&
           vmfault(p->pagetable, p->sz, r_stval(),
                   (r_scause() == 13) ? 1 : 0) != 0) {
  // page fault on lazily-allocated page
} else {
  printk("usertrap(): unexpected scause 0x%lx pid=%d\n", r_scause(), p->pid);
  printk("            sepc=0x%lx stval=0x%lx\n", r_sepc(), r_stval());
  setkilled(p);
}

vmfault adds PTE_X to the page and the jump is retried.The code runs, because the page is mapped and readable.The fetch faults and the process is killed, because lazily allocated pages are mapped R W U without X, and usertrap doesn’t treat scause 12 as a lazy fault anyway.The kernel panics in kerneltrap.

18warm-upTrue or false, and why

True or false: kalloc returns a page filled with zeros.

kernel/kalloc.c

68void *
69kalloc(void)
70{
71  struct run *r;
72
73  acquire(&kmem.lock);
74  r = kmem.freelist;
75  if (r)
76    kmem.freelist = r->next;
77  release(&kmem.lock);
78
79  if (r)
80    memset((char *)r, 5, PGSIZE); // fill with junk
81  return (void *)r;
82}

TrueFalse

Why?

It returns the page as it was when freed, still holding the previous owner’s data.It fills the page with 0x05 bytes after popping it, so that callers who forget to initialise memory see obvious junk.It fills the page with 0x01 bytes, the same value kfree uses.

19solidMatch the pairs

Match each function with what it writes into a physical page it has just freed or obtained.

kfreekallocuvmallocvmfaultuvmcopy

20deepChoose one

Imagine kmem.lock were removed. Hart 1 in kalloc reads the head (A); then hart 2 runs a complete kfree(P); then hart 1 stores A->next (B) as the new head. What is the result?

kernel/kalloc.c

57  r = (struct run *)pa;
58
59  acquire(&kmem.lock);
60  r->next = kmem.freelist;
61  kmem.freelist = r;
62  release(&kmem.lock);
63}
64
65// Allocate one 4096-byte page of physical memory.
66// Returns a pointer that the kernel can use.
67// Returns 0 if the memory cannot be allocated.
68void *
69kalloc(void)
70{
71  struct run *r;
72
73  acquire(&kmem.lock);
74  r = kmem.freelist;
75  if (r)
76    kmem.freelist = r->next;
77  release(&kmem.lock);
78
79  if (r)
80    memset((char *)r, 5, PGSIZE); // fill with junk
81  return (void *)r;

Hart 1 gets P instead of A.P is on no list and owned by nobody: it has leaked until reboot.A is handed out twice.Nothing goes wrong, because each kfree and kalloc touches the head only once.

21solidChoose all that apply

Which of these calls make kfree panic? (In this build end = 0x80020bb0 and PHYSTOP = 0x88000000.)

kernel/kalloc.c

46void
47kfree(void *pa)
48{
49  struct run *r;
50
51  if (((uint64)pa % PGSIZE) != 0 || (char *)pa < end || (uint64)pa >= PHYSTOP)
52    panic("kfree");

kfree((void*)0x80021800)kfree((void*)0x80010000)kfree of a page that is already on the free listkfree((void*)0x87fff000) on a page from kallockfree((void*)0x88000000)

22warm-upChoose one

A program calls sbrklazy(-8192) to give back two pages. What does sys_sbrk do?

kernel/sysproc.c

39uint64
40sys_sbrk(void)
41{
uint64 addr;
int t;
int n;
45
argint(0, &n);
argint(1, &t);
addr = myproc()->sz;
49
if (t == SBRK_EAGER || n < 0) {
  if (growproc(n) < 0) {
    return -1;
  }
} else {
  // Lazily allocate memory for this process: increase its memory
  // size but don't allocate memory. If the processes uses the
  // memory, vmfault() will allocate it.
  if (addr + n < addr)
    return -1;
  if (addr + n > TRAPFRAME)
    return -1;
  myproc()->sz += n;
}
return addr;
65}

It returns -1, because lazy sbrk cannot shrink.It only subtracts 8192 from sz; the pages are freed when the process exits.It calls growproc, exactly as for an eager shrink, which unmaps the pages and frees those that exist now.It marks the pages for vmfault to free on the next page fault.

23solidType a number

The shell’s child has p->sz = 0x5000 and its whole memory is mapped through a single level-0 page-table page. malloc calls sbrk(65536) (eager). How many times is kalloc called during that system call?

kernel/vm.c

215// Allocate PTEs and physical memory to grow a process from oldsz to
216// newsz, which need not be page aligned.  Returns new size or 0 on error.
217uint64
218uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)
219{
char *mem;
uint64 a;
222
if (newsz < oldsz)
  return oldsz;
225
oldsz = PGROUNDUP(oldsz);
for (a = oldsz; a < newsz; a += PGSIZE) {
  mem = kalloc();
  if (mem == 0) {
    uvmdealloc(pagetable, a, oldsz);
    return 0;
  }
  memset(mem, 0, PGSIZE);
  if (mappages(pagetable, a, PGSIZE, (uint64)mem, PTE_R | PTE_U | xperm) !=
      0) {
    kfree(mem);
    uvmdealloc(pagetable, a, oldsz);
    return 0;
  }
}
return newsz;
242}

decimal, 0x hex or 0b binary

24warm-upChoose one

Physical memory is nearly exhausted. How does running out show up to a program that grew with eager sbrk, compared with one that used sbrklazy?

Both return -1 from the sbrk call.Eager: sbrk returns -1 at the call, and the program can handle it. Lazy: some later load or store faults, vmfault gets no page, and the process is killed.Both cause a kernel panic.Lazy: the faulting process sleeps until another process frees memory.

25warm-upDecode the bits

Right after exec, the level-0 PTE for sh’s page at 0x3000 (just below its one stack page) read 0x21fce407 in our run. Decode it.

Value: 0x21fce407

V (bit 0)R and W (bits 1-2)U (bit 4)What vmfault does on a user store fault here