The linked image cannot be displayed. The file may have been moved, renamed, or deleted. Verify that the link points to the correct file and location.
TOTAL MARKS: 100 Introduction
For this assignment, you are going to use xv6 for lazy allocation and and implement features of file systems not currently present in the xv6 filesystem.
These are taken from MIT’s selection of xv6 labs.
Note that there are several git repositories with attempted solutions for these problems on the Internet. We have found them, though not all of them. The solutions are going to be quite similar, so please do not copy or use any of them, as you will be cheating yourself out of a learning experience. Also, some of these are for a previous version of xv6, so they may not work right anyway, and you will create more problems than you think you will be solving.
As always, indicate your changes with /* CMPT 332 group XX change */. Updating xv6
First make sure that your repo has the xv6-origin remote by running git remote -v. The output should look like this:
$ git remote -v
origin git@git.cs.usask.ca:dwm138/groupXX.git (fetch)
origin git@git.cs.usask.ca:dwm138/groupXX.git (push)
xv6-origin git@git.cs.usask.ca:cmpt332/xv6-riscv.git (fetch) xv6-origin git@git.cs.usask.ca:cmpt332/xv6-riscv.git (push)
If xv6-origin is missing you can add it by running the following:
$ git remote add -f xv6-origin <xv6-repo-link>
<xv6-repo-link> is either
https://git.cs.usask.ca/cmpt332/xv6-riscv.git or git@git.cs.usask.ca:cmpt332/xv6-riscv.git
Now you are ready to update xv6. Run the following to update your copy of xv6.
$ git checkout master
$ git pull
$ git fetch xv6-origin
$ git pull -s subtree -Xsubtree=xv6/ xv6-origin riscv –allow-unrelated- histories
Part A: Implement lazy page allocation with xv6 (40 marks)
The goal of this component of the assignment is to understand memory management in operating systems a little better. We will achieve this goal by implementing a lazy page allocation feature in xv6. This implementation will require you to thoroughly understand how memory management and paging work in xv6.
One of the many neat tricks an O/S can play with page table hardware is lazy allocation of user- space 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. It can take a long time for a kernel to allocate and map memory for a large request. Consider, for example, that a gigabyte consists of 262,144 4096-byte pages; that’s a huge number of allocations even if each is individually cheap. In addition, some programs allocate more memory than they actually use (e.g., to implement sparse arrays), or allocate memory well in advance of use. To allow sbrk() to complete more quickly in these cases, sophisticated kernels allocate user memory lazily. That is, sbrk() doesn’t allocate physical memory, but just remembers which user addresses are allocated and marks those addresses as invalid in the user page table. When the process first tries to use any given page of lazily- allocated memory, the CPU generates a page fault, which the kernel handles by allocating physical memory, zeroing it, and mapping it. You’ll add this lazy allocation feature to xv6 in this asignment.
Before you start coding, read Chapter 4 (in particular 4.6) of the xv6 book, and related files you are likely to modify:
• kernel/trap.c
• kernel/vm.c
• kernel/sysproc.c
Eliminate allocation from sbrk()
This will be part of Lab 6.
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 (or shrinks) 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=0x0000000000001258 stval=0x0000000000004008 va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: 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.
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. Modify whatever other xv6 kernel code you need to in order to get echo hi to work.
Here are some hints:
• • • •
• • • •
If all least
You can check whether a fault is a page fault by seeing if r_scause() is 13 or 15 in usertrap().
r_stval() returns the RISC-V stval register, which contains the virtual address that caused the page fault.
Steal code from uvmalloc() in vm.c, which is what sbrk() calls (via growproc()). You’ll need to call kalloc() and mappages().
Use PGROUNDDOWN(va) to round the faulting virtual address down to a page boundary.
uvmunmap() will panic; modify it to not panic if some pages aren’t mapped.
If the kernel crashes, look up sepc in kernel/kernel.asm
Use your vmprint function from Lab 6 to print the contents of a page table.
If you see the error “incomplete type proc”, include “spinlock.h” then “proc.h”.
goes well, your lazy allocation code should result in echo hi working. You should get at one page fault (and thus lazy allocation), and perhaps two.
Lazytests and Usertests
We’ve supplied you with lazytests, an xv6 user program that tests some specific situations that may stress your lazy memory allocator. Enable lazytests by adding $U/_lazytyests\ to UPROGS in the Makefile. Modify your kernel code so that all of both lazytests and usertests pass.
• Handle negative sbrk() arguments.
• Kill a process if it page-faults on a virtual memory address higher than any allocated with
sbrk().
• Handle the parent-to-child memory copy in fork() correctly.
• Handle the case in which a process passes a valid address from sbrk() to a system call
such as read or write, but the memory for that address has not yet been allocated.
• Handle out-of-memory correctly: if kalloc() fails in the page fault handler, kill the current process.
• Handle faults on the invalid page below the user stack.
Your solution is acceptable if your kernel passes lazytests and usertests:
$ lazytests
lazytests starting running test lazy alloc test lazy alloc: OK running test lazy unmap… usertrap(): …
test lazy unmap: OK running test out of memory usertrap(): …
test out of memory: OK ALL TESTS PASSED
$ usertests
…
ALL TESTS PASSED
$
PART B: Big Files in xv6 (40 marks)
Before writing code, you should read “Chapter 8: File system” from the xv6 book and study the corresponding code.
In this assignment you’ll increase the maximum size of an xv6 file. Currently xv6 files are limited to 268 blocks, or 268*BSIZE bytes (BSIZE is 1024 in xv6). This limit comes from the fact that an xv6 inode contains 12 “direct” block numbers and one “singly-indirect” block number, which refers to a block that holds up to 256 more block numbers, for a total of 12+256=268 blocks.
Enable bigfile by adding $U/_bigfile\ to UPROGS in the Makefile
The bigfile command creates the longest file it can, and reports that size:
$ bigfile
..
wrote 268 blocks
bigfile: file is too small $
The test fails because the longest file is only 268 blocks.
You’ll change the xv6 file system code to support a “doubly-indirect” block in each inode, containing 256 addresses of singly-indirect blocks, each of which can contain up to 256 addresses of data blocks. The result will be that a file will be able to consist of up to
256*256+256+11 blocks (11 instead of 12, because we will sacrifice one of the direct block numbers for the double-indirect block).
Preliminaries
mkfs initializes the file system to have fewer than 2000 free data blocks, too few to show off the changes you’ll make. Modify kernel/param.h to change FSSIZE from 2000 to 200,000:
#define FSSIZE 200000 // size of file system in blocks
Rebuild mkfs so that is produces a bigger disk: $ rm mkfs/mkfs fs.img; make mkfs/mkfs What to Look At
The format of an on-disk inode is defined by struct dinode in fs.h. You’re particularly interested in NDIRECT, NINDIRECT, MAXFILE, and the addrs[] element of struct dinode. Look at Figure 8.3 in the xv6 text for a diagram of the standard xv6 inode.
The code that finds a file’s data on disk is in bmap() in fs.c. Have a look at it and make sure you understand what it’s doing. bmap() is called both when reading and writing a file. When writing, bmap() allocates new blocks as needed to hold file content, as well as allocating an indirect block if needed to hold block addresses.
bmap() deals with two kinds of block numbers. The bn argument is a “logical block number” — a block number within the file, relative to the start of the file. The block numbers in ip->addrs[], and the argument to bread(), are disk block numbers. You can view bmap() as mapping a file’s logical block numbers into disk block numbers.
Your Job
Modify bmap() so that it implements a doubly-indirect block, in addition to direct blocks and a singly-indirect block. You’ll have to have only 11 direct blocks, rather than 12, to make room for your new doubly-indirect block; you’re not allowed to change the size of an on-disk inode. The first 11 elements of ip->addrs[] should be direct blocks; the 12th should be a singly-indirect block (just like the current one); the 13th should be your new doubly-indirect block. You are done with this exercise when bigfile writes 65803 blocks and usertests runs successfully:
$ bigfile ………………………………………………………….. wrote 65803 blocks
done; ok
$ usertests
…
ALL TESTS PASSED
$
bigfile will take a few minutes to run. You can speed things up by modifying parameters as follows: NCPU=1 and NPROC=10 in kernel/param.h. Make sure to also change the CPUS variable in the Makefile.
Hints:
• Make sure you understand bmap(). Write out a diagram of the relationships between ip->addrs[], the indirect block, the doubly-indirect block and the singly-indirect blocks it points to, and data blocks. Make sure you understand why adding a doubly-indirect block increases the maximum file size by 256*256 blocks (really -1, since you have to decrease the number of direct blocks by one).
• Think about how you’ll index the doubly-indirect block, and the indirect blocks it points to, with the logical block number.
• If you change the definition of NDIRECT, you’ll probably have to change the declaration of addrs[] in struct inode in file.h. Make sure that struct inode and struct dinode have the same number of elements in their addrs[] arrays.
• If you change the definition of NDIRECT, make sure to create a new fs.img, since mkfs uses NDIRECT to build the file system.
• If your file system gets into a bad state, perhaps by crashing, delete fs.img (do this from Unix, not xv6). make will build a new clean file system image for you.
• Don’t forget to brelse() each block that you bread().
• You should allocate indirect blocks and doubly-indirect blocks only as needed, like the
original bmap().
• Make sure itrunc frees all blocks of a file, including double-indirect blocks.
BONUS: support triple-indirect blocks.
PART C: Symbolic links in xv6 (20 marks)
In this exercise you will add symbolic links to xv6. Symbolic links (or soft links) refer to a linked file by pathname; when a symbolic link is opened, the kernel follows the link to the referred file. Symbolic links resembles hard links, but hard links are restricted to pointing to file on the same disk, while symbolic links can cross disk devices. Although xv6 doesn’t support multiple devices, implementing this system call is a good exercise to understand how pathname lookup works.
The first part of this task is to be done as Lab 7.
Your job
You will implement the symlink(char *target, char *path) system call, which creates a new symbolic link at linkpath that refers to file named by target. For further information, see the man page symlink. To test, add symlinktest $U/_symlinktest\ to UPROGS in the Makefile and run it. Your solution is complete when the tests produce the following output (including usertests succeeding).
$ symlinktest
START: test symlinks
test symlinks: ok
Start: test concurrent symlinks test concurrent symlinks: ok
$ usertests
…
ALL TESTS PASSED
$
Hints:
• First, create a new system call number for symlink, add an entry to user/usys.pl, user/user.h, and implement an empty sys_symlink.
• Add a new file type (T_SYMLINK) to kernel/stat.h to represent a symbolic link.
• Add a new flag to kernel/fcntl.h, (O_NOFOLLOW), that can be used with the open system call. Note that flags passed to open are combined using a bitwise OR operator, so your
new flag should not overlap with any existing flags. This will let you compile
user/symlinktest.c once you add it to the Makefile.
• Implement the symlink(target, path) system call to create a new symbolic link at
path that refers to target. Note that target does not need to exist for the system call to succeed. You will need to choose somewhere to store the target path of a symbolic link, for example, in the inode’s data blocks.
• Modify the open system call to handle the case where the path refers to a symbolic link. If the file does not exist, open must fail. When a process specifies O_NOFOLLOW in the flags to open, open should open the symlink (and not follow the symbolic link).
• If the linked file is also a symbolic link, you must recursively follow it until a non-link file is reached. If the links form a cycle, you must return an error code. You may approximate this by returning an error code if the depth of links reaches some threshold (e.g., 10).
• Other system calls (e.g., link and unlink) must not follow symbolic links; these system calls operate on the symbolic link itself.
• You do not have to handle symbolic links to directories for this assignment. ———————————————————————–
Deliverables – What to hand in:
• Clean tarball (run make clean) of your xv6 source, named xv6-A3.tar, without the git details and without any binaries or object files, and most definitely without an fs.img file. Only source code. The doc directory is OK, but not really needed either. ONE tar file. This is best done by copying all of xv6 to another directory and removing the things you don’t want, like .git.
• xv6-A3.diff: a diff file listing all the changes to the kernel you made for this assignment.
Part A: Lazy page allocation in xv6
• Design document in PartA.design.txt. Description of the implementation of the allocator and where you had to make changes to the kernel.
• Test execution of your modified kernel and place the output in xv6-lazy-output.txt. This will include runs of your test programs.
Part B: Big files in xv6
• Design document in PartB.design.txt. Description of the implementation of bigfile and where you had to make changes to the kernel
• Test execution of your modified kernel and place the output in xv6-bigfile- output.txt.
Part C: Symbolic links in xv6
• Design document in PartC.design.txt. Description of the implementation of symlink and where you had to make changes to the kernel
• Test execution of your modified kernel and place the output in xv6-symlink- output.txt. This is where the results of the usertests program will be submitted.
Finally, proper git logs are required as always.
All of this should be bundled in a .tar file and submitted via Canvas with no subdirectories. The tar file of the main source tree for xv6 source code, is again to be the xv6/ directory. So, yes, that’s a .tar file that contains a .tar file.
Notes and Warnings:
Documentation: All documentation files are to be in UNIX text file format with lines shorter than 80 characters. Nothing else is acceptable; nothing else is necessary. There will not be diagrams, etc. in your work. This allows the marker to look at both your code and your documentation in the same tool: vi or emacs. It speeds the marking and a happy marker is a generous marker.