Introduction
In this activity, we will ask our operating system to take on a lazy approach to
memory allocation. When a process asks for more memory, using the sbrk
system call, the operating system does not really allocate any memory for that
process. Why? Because programmers are bad, they often over-allocate memory and
end up not using. So why give them all that memory if they don’t really need it?
What we are going to do is to give a process a page of memory only when it tries to access it, and not before. How are we going to do that? We are going to make use of our good old friend, the segmentation fault.
Getting the source code
For this activity, we will need to mess around with the code for the xv6 kernel. So before you start this activity, please make sure that all of your code for your labs is pushed to your own private repo, otherwise, we might risk mixing things up and losing your progress.
Backing up your lab code
If you have made a private xv6 repo, first commit and push all of your changes to your repo. You can do so using:
$ git commit -am "saving progress"
$ git push
Getting on the right branch
First, switch to the main
branch to get everything back in order, to do so,
use (recall, if your main branch’s name is master
, use master
)
$ git checkout main
Next, fetch the changes from our end using
$ git fetch upstream
Then, make sure that the branch lazy_alloc
shows up
$ git branch -a
clab_solution
heapmm_solution
* main
remotes/origin/clab_solution
remotes/origin/heapmm_solution
remotes/origin/main
remotes/upstream/clab
remotes/upstream/heapmm
remotes/upstream/main
remotes/upstream/paging_act
remotes/upstream/lazy_alloc
Then, get the lazy_alloc
branch as follows:
$ git checkout -b lazy_alloc_sol upstream/lazy_alloc
branch 'lazy_alloc_sol' set up to track 'upstream/lazy_alloc'.
Switched to a new branch 'lazy_alloc'
Finally, push the empty stub to your own repo using:
$ git push --set-upstream origin lazy_alloc_sol
Enumerating objects: 99, done.
Counting objects: 100% (99/99), done.
Delta compression using up to 56 threads
Compressing objects: 100% (80/80), done.
Writing objects: 100% (88/88), 3.15 MiB | 11.39 MiB/s, done.
Total 88 (delta 15), reused 19 (delta 2), pack-reused 0
remote: Resolving deltas: 100% (15/15), completed with 11 local objects.
remote:
remote: Create a pull request for 'lazy_alloc_sol' on GitHub by visiting:
remote: https://github.com/user/csse332-labs-user/pull/new/lazy_alloc_sol
remote:
To github.com:user/csse332-labs-noureddi.git
* [new branch] lazy_alloc_sol -> lazy_alloc_sol
branch 'lazy_alloc_sol' set up to track 'origin/lazy_alloc_sol'.
The Activity
The idea that we’d like to implement is the following. When a process requests an increase in its allocated size, we will increase it but not really allocate the physical frames for that process. Instead, we will wait for that process to attempt to access the pages that it needs, and only then we allocate the frames for it and map them into its page table.
sbrk
The first thing to look at is the code for the sbrk
system call. Under
kernel/sysproc.c
, look at the function sys_sbrk(void)
and notice the changes
we introduced. The function should look something like:
sys_sbrk(void)
{
uint64 addr;
int n;
argint(0, &n);
addr = myproc()->sz;
// Activity: We will not actually grow the process's memory unless we really
// want to. More trickery for the OS point of view.
// if(growproc(n) < 0)
// return -1;
// Instead, we will just increase the process's size without actually growing
// it now.
myproc()->sz += n;
return addr;
}
Note that we have removed the code that actually grows the process’ address
space, growproc(n)
. Instead, we only increase the size variable for the
process, as shown in the line myproc()->sz += n;
.
Testing
Now compile and build xv6 using make qemu
, and try to run any command, for
example echo hi
, you should see something like this:
[xv6 shell] $ echo hi
usertrap(): unexpected scause 0x000000000000000f pid=3
sepc=0x00000000000012c0 stval=0x0000000000005008
❓ What does the error message indicate? What are the scause
, sepc
, and
stval
values?
Any time a process attempts to access an un-allocated page, the hardware will
generate a page fault, and trigger a trap handler in the kernel. Checkout the
code in kernel/trap.c
for more information. Specifically, look at
usertrap(void)
.
Handling Page Faults
Your task in this activity is to modify the xv6 trap handling so that when a page fault happens for a page that is not mapped, the kernel will allocate a physical frame for that page, and then map the page into the process’s page table.
Some Hints
Here are some hints to help you on your task:
-
You can read the
scause
andstval
registers using ther_scause()
andr_stval()
functions. - It would be helpful for you to better understand things to print a message
that says something like this:
printf("Segmentation fault occurred at address %p, from process %s (%d)\n", fault_addr, p->name, p->pid);
-
If you cannot allocate a page for a process, make sure to set that process as killed using
setkilled(p);
. -
Note that the faulty address might be an address within a page. How can we extract the page address from that faulty address?
-
To allocate a physical frame, you can ask the kernel to do that for you using the
kalloc()
function. Notice howkalloc
does not accept any arguments, it only allocate a single page (of size 4096 bytes). -
You will find the functions in
kernel/vm.c
very useful. Specifically,uvmalloc
might be very inspirational. - If you need permission bits, you can use
PTE_R|PTE_W|PTE_U
to mark the page as readable, writable, and user accessible.
Testing
Once you have your implementation ready, look into the user/lazy.c
program and
run it while experimenting with its values. I recommend that you first try to
run it as follows:
[xv6 shell] $ lazy 1024 10
❓ How many segmentation faults do you see? Why is there this many?
Now, try to use different arguments, something like
[xv6 shell] $ lazy 4096 10
❓ How many segmentation faults do you see? Why is there this many?
Experiment with the arguments and to make sure you understand how things operate. Ask you instructor questions as you doing so.
This page was last edited by Mohammad Noureddine on Mon Dec 18 16:21:32 2023. If you notice any typos or inaccuracies, please open a GitHub issue on this repository.