From 0387e2156f10130148a44d9389393ec537e3b134 Mon Sep 17 00:00:00 2001 From: Frans Kaashoek Date: Wed, 24 Jul 2019 08:37:26 -0400 Subject: Add a few sbrktest for lazy allocatioin lab --- labs/lazy.html | 132 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 132 insertions(+) create mode 100644 labs/lazy.html (limited to 'labs') diff --git a/labs/lazy.html b/labs/lazy.html new file mode 100644 index 0000000..baf5f3b --- /dev/null +++ b/labs/lazy.html @@ -0,0 +1,132 @@ + + +Lab: xv6 lazy page allocation + + + + +

Lab: xv6 lazy page allocation

+ +

+One of the many neat tricks an O/S can play with page table hardware +is lazy allocation of heap memory. Xv6 applications ask the kernel for +heap memory using the sbrk() system call. In the kernel we've given +you, sbrk() allocates physical memory and maps it into the process's +virtual address space. There are programs that allocate memory but +never use it, for example to implement large sparse arrays. +Sophisticated kernels delay allocation of each page of memory until +the application tries to use that page -- as signaled by a page fault. +You'll add this lazy allocation feature to xv6 in this lab. + +

Part One: Eliminate allocation from sbrk()

+ +Your first task is to delete page allocation from the sbrk(n) system +call implementation, which is the function sys_sbrk() in sysproc.c. The +sbrk(n) system call grows the process's memory size by n bytes, and +then returns the start of the newly allocated region (i.e., the old +size). Your new sbrk(n) should just increment the process's size +(myproc()->sz) by n and return the old size. It should not allocate memory +-- so you should delete the call to growproc() (but you still need to +increase the process's size!). + +

+Try to guess what the result of this modification will be: what will +break? + +

+Make this modification, boot xv6, and type echo hi to the shell. +You should see something like this: + +

+init: starting sh
+$ echo hi
+usertrap(): unexpected scause 0x000000000000000f pid=3
+            sepc=0x00000000000011dc stval=0x0000000000004008
+va=0x0000000000004000 pte=0x0000000000000000
+panic: unmappages: not mapped
+
+ +The "usertrap(): ..." message is from the user trap handler in trap.c; +it has caught an exception that it does not know how to handle. Make +sure you understand why this page fault occurs. The "stval=0x0..04008" +indicates that the virtual address that caused the page fault is +0x4008. + +

Part Two: Lazy allocation

+ +Modify the code in trap.c to respond to a page fault from user space +by mapping a newly-allocated page of physical memory at the faulting +address, and then returning back to user space to let the process +continue executing. You should add your code just before +the printf call that produced the "usertrap(): ..." +message. + +

+Hint: look at the printf arguments to see how to find the virtual +address that caused the page fault. + +

+Hint: steal code from allocuvm() in vm.c, which is what sbrk() +calls (via growproc()). + +

+Hint: use PGROUNDDOWN(va) to round the faulting virtual address +down to a page boundary. + +

+Hint: usertrapret() in order to avoid +the printf and the myproc()->killed = 1. + +

+Hint: you'll need to call mappages(). + +

Hint: you can check whether a fault is a page fault by r_scause() + is 13 or 15 in trap(). + +

Hint: modify unmappages() to not free pages that aren't mapped. + +

Hint: if the kernel crashes, look up sepc in kernel/kernel.asm + +

Hint: if you see the error "imcomplete type proc", include "proc.h" + (and "spinlock.h"). + +

Hint: the first test in sbrk() allocates something large, this + should succeed now. + +

+If all goes well, your lazy allocation code should result in echo +hi working. You should get at least one page fault (and thus lazy +allocation) in the shell, and perhaps two. + +

If you have the basics working, now turn your implementation into + one that handles the corner cases too. + +

+ +

Run all tests in usertests() to make sure your solution doesn't +break other tests. + +

+

+

Submit: The code that you added to trap.c in a file named hwN.c where N is the homework number as listed on the schedule. +

+ + + + -- cgit v1.2.3