Assignment 3: File System Implementation

Due Date: 8:00am, Monday, June 7th, Week 14

Worth 25 marks (of the 100 available for the class mark component of the course). 13 marks for automarking, 12 marks awarded manually for correctness, performance, and clarity.

The 10% bonus for one week early is available for the basic assignment. Deadline: 8:00am, Monday, May 31st, Week 13

The extra 5% bonus for a submitted, working assignment within 48 hours of release, is also available for the basic assignment. Deadline: Midnight, Wednesday May 19th

See course intro for exact details. Note the demonstration requirement.

Up to a 20% bonus is available for the advanced part of the assignment

To attempt the advanced part, you must finish the standard assignment at least one week early, and get permission from Kevin.

Any bonus awarded for the advanced part can be used to make up for lost marks in any class mark component of the course.

Introduction

In this assignment, you will extend OS/161's native file system (SFS) to support large files and block accounting. If you attempt the advanced part of the assignment, you will add support for subdirectories, thus enabling a hierarchical naming system. If this is not enough, you can add a buffer cache to OS/161 to improve performance.

Code walk-through

Bring your answers to the code walk-through questions to your week 12 tutorial. The OS/161 sfs file system we provide is very simple. The implementation resides in the fs/sfs directory. The fs/vfs directory provides the infrastructure to support multiple file systems.

kern/include

You should examine the files fs.h, vfs.h, vnode.h, and sfs.h.

1. What is the difference between VOP_ routines and FSOP_ routines?

kern/fs/vfs

device.c

This implements raw device support.

2. What vnode operations are permitted on devices?

devnull.c

This implements the OS/161 equivalent of /dev/null, null:.

vfscwd.c

This implements current working directory support.

3. Why is VOP_INCREF called in vfs_getcurdir?

vfslist.c

This implements operations on the entire set of file systems.

4. How do items get added to the vfslist?

vfslookup.c

Name translation operations.

vfspath.c

Operations on path names; implements the vfs operations.

vnode.c

Initialization and reference count management.

kern/fs/sfs

sfs_fs.c

File system routines.

5. There is no buffer cache currently in sfs. However, the bitmaps and superblock are not written to disk on every modification. How is this possible?

6. What do the statements in Question 5 mean about the integrity of your file system after a crash?

7. Can you unmount a file system on which you have open files?

8. List 3 reasons why a mount might fail.

sfs_io.c

Block I/O routines

sfs_vnode.c

File routines

9. Why is a routine like sfs_partialio necessary? Why is this currently a performance problem? What part of this assignment will make it less of one.

10. What is the sfs_bmap routine used for?

sbin/mksfs

Implements the mksfs utility which creates an sfs file system on a device.

disk.h/disk.c

Defines what the disk looks like.

mksfs.c

11. What is the inode number of the root?

Setting Up Assignment 3

At the end of the previous assignment, you will have archived a copy of your previous solution. If you have not, please go back and do it now. These instructions assume the src directory from the previous assignment has been removed.

We also assume that the remainder of the ~/cs3231 directory is in place.

Copy the sources to this assignment into this directory. 

% cp -r ~cs3231/assigns/asst3/src ~/cs3231
You should now have a src directory to work on.

Note: We have included a simple implementation of the syscalls open(), close(), read(), write(), lseek(), sync(), fstat().

Building and Testing Your Assignment

Configure OS/161 for Assignment 3

Before proceeding further, configure your new sources. 

% cd ~/cs3231/src
% ./configure

Unlike previous the previous assignment, you will need to build and install the user-level programs that will be run by your kernel in this assignment. 

% cd ~/cs3231/src
% make
Note: "make" in this directory does both "make" and "make install".

For your kernel development, again we have provided you with a framework for you to run your solutions for ASST3.

You have to reconfigure your kernel before you can use this framework. The procedure for configuring a kernel is the same as in ASST0, ASST1, etc, except you will use the ASST3 configuration file: 

% cd ~/cs3231/src/kern/conf	
% ./config ASST3
You should now see an ASST3 directory in the compile directory.

Building for ASST3

When you built OS/161 for ASST1, you ran make from compile/ASST1 . In ASST3, you run make from (you guessed it) compile/ASST3. 
% cd ../compile/ASST3
% make depend
% make
% make install
If you are told that the compile/ASST3 directory does not exist, make sure you ran config for ASST3.

Command Line Arguments to OS/161

Your solutions to ASST3 will be tested by running OS/161 with command line arguments that correspond to the menu options in the OS/161 boot menu.

IMPORTANT: Please DO NOT change these menu option strings!

Running "asst3"

For this assignment, we have supplied a user-level OS/161 program that you can use for testing. It is called asst3, and its sources live in src/testbin/asst3.

You can test your assignment by typing p /testbin/asst3 at the OS/161 menu prompt.

Running the program produces output similar to the following prior to starting the assignment. You must configure sys161, and format and mount your disk first (see below). 

************************************************************
* Asst3 Tester
************************************************************
* Testing first file system block (pos 0)
************************************************************
opening file "lhd0:testfile"
open() got fd 3

lseeking pos 0

writing test string at pos 0
wrote 45 bytes

lseek to pos 0

reading 45 bytes into buffer
attempting read of 45 bytes
read 45 bytes
reading complete

file content okay
Unknown syscall 16
ERROR testing file: No such system call
Unknown syscall 0
asst3 produces the following output on a (maybe partially) working assignment. 
 
************************************************************
* Asst3 Tester
************************************************************
* Testing first file system block (pos 0)
************************************************************
opening file "lhd0:testfile"
open() got fd 3

lseeking pos 0

writing test string at pos 0
wrote 45 bytes

lseek to pos 0

reading 45 bytes into buffer
attempting read of 45 bytes
read 45 bytes
reading complete

file content okay
file stats: size: 45 blocks: 1
************************************************************
* Testing file system indirect block (pos 7680)
************************************************************
opening file "lhd0:testfile"
open() got fd 3

lseeking pos 7680

writing test string at pos 7680
wrote 46 bytes

lseek to pos 7680

reading 46 bytes into buffer
attempting read of 46 bytes
read 46 bytes
reading complete

file content okay
file stats: size: 7726 blocks: 3
************************************************************
* Testing file system double indirect block (pos 73216)
************************************************************
opening file "lhd0:testfile"
open() got fd 3

lseeking pos 73216

writing test string at pos 73216
wrote 45 bytes

lseek to pos 73216

reading 45 bytes into buffer
attempting read of 45 bytes
read 45 bytes
reading complete

file content okay
file stats: size: 73261 blocks: 6
************************************************************
* Testing last double indirect block (pos 8461312)
************************************************************
opening file "lhd0:testfile"
open() got fd 3

lseeking pos 8461312

writing test string at pos 8461312
wrote 46 bytes

lseek to pos 8461312

reading 46 bytes into buffer
attempting read of 46 bytes
read 46 bytes
reading complete

file content okay
file stats: size: 8461358 blocks: 8
************************************************************
* Testing file system beyond max file size (pos 1082203648)
************************************************************
opening file "lhd0:testfile"
open() got fd 3

lseeking pos 1082203648

writing test string at pos 1082203648
wrote -1 bytes
EXPECTED ERROR testing file:Invalid argument
************************************************************
Sync()'ing files and finished!!!
************************************************************
Unknown syscall 0

Configuring System/161

You may need to have configured System/161 to have at least one disk to test your file system on. The following should be sufficient in your ~/cs3231/root/sys161.conf. 
2	disk	rpm=7200	sectors=2048	file=DISK1.img
#3	disk	rpm=7200	sectors=2048	file=DISK2.img
These disk images are created if they don't exist on System/161 startup.

You can also increase the amount of RAM in System/161, if you need it. 

31	busctl	ramsize=4194304

Formatting and Using Your SFS Disks

Before using SFS, you need to format the disk on which you are going to mount the file system. This should be done on your host system. The following examples illustrate how to format lhd0 (DISK1.img).

In your cs3231/root directory:

host% hostbin/host-mksfs DISK1.img my-vol-name
The next time you run OS/161, you can mount SFS on the formatted disk device (lhd0 in this example) from the OS161 command menu: 
OS/161 kernel [? for menu]: mount sfs lhd0
vfs: Mounted my-vol-name: on lhd0
Once mounted, you can then read and write files on the file system by specifying the mounted device in the pathname of the open call. 
open("lhd0:newfile", O_RDWR | O_CREAT);

Basic Assignment

The following sections outline what you must do for the basic assignment.

Add block accounting support to SFS

The fstat system call is applied to a valid file descriptor, and the following information is returned about the file. 
struct stat {
	u_int32_t st_mode;	/* protection mode and file type */
	u_int32_t st_nlink;	/* number of hard links */
	off_t st_size;		/* file size (bytes) */
	u_int32_t st_blocks;	/* number of blocks file is using */
};
We have provided the in-kernel implementation of fstat (and sync) that works for all present (and future) vfs-based file systems.

However, SFS currently only supports st_mode and st_size. You must add support for st_blocks within SFS. st_blocks contains the number of disk blocks consumed by the file on disk. Once you extend SFS to support block accounting, fstat will return the correct value in st_blocks.

Notes:

Adding Support for Large Files

SFS only supports medium sized, potentially sparse, files using a scheme very similar to the UNIX inode scheme covered in lectures. SFS only supports direct block pointers and single indirect block pointers. Thus the largest file currently supported by SFS is (15 + 128) * 512 = 71.5 Kbytes.

You must extend SFS to support files up to 1082203648 bytes (1+ Gigabytes) by adding support for double indirect and triple indirect blocks on disk. Note that we can actually test creating files of maximum size on our small test disk by using lseek to write to specific locations within the file, thus creating a sparsely populated file.

For additional background, consult one or more of the following texts for details how similar existing operating systems structure their file system management:

Basic Assignment Submission

As with assignment 0, you again will be submitting a diff of your changes to the original tree. Once your assignment works, you now need to generate a diff of the changes you made to OS/161. Firstly, you need to clean the source tree. 
% cd ~/cs3231/src
% make clean
% cd kern/compile/ASST2
% make clean
You will be submitting a diff of your changes to the original tree. So generate a file containing this diff. 
% cd ~/cs3231
% diff -N -r -u -X src/.diffex ~cs3231/assigns/asst3/src src > ~/asst3.diff
The arguments to diff are as follows

Testing Your Submission

Look here for information on testing and resubmitting your assignment.

Submitting Your Assignment

Now submit the diff as your assignment. 
% cd ~
% give cs3231 asst3 asst3.diff
You're now done.

Even though the generated diff output should represent all the changes you have made to the supplied code, occasionally students do something "ingenious" and generate non representative diff output.

We suggest keeping a copy of the source tree as a compressed tar file until you get your results back. After getting your results back, you should be confident the diff was representative and you can safely keep the diff file as a record of your work, and consequently remove the tar file.

To create a compressed tar file and remove the sources to asst3: 

% cd ~/cs3231
% tar cvzf asst3.tar.gz src
You can confirm the tar file contains your assignment by listing its contents. 
% tar tvfz asst3.tar.gz
If all looks well, you can remove the sources if your not going to attempt the advanced assignment. 
% rm -rf src
You're now done.

Advanced Assignment

The advanced assignment is to complete the basic assignment, plus the following. Note: To get the available 20%, it is not expected that everything that follows be implemented. The 20% is available to those that implement a substantial subset of the following.

Setting Up Advanced Assignment 3

Given your doing the advanced version of the assignment, I'm assuming your competent enough to not need detailed instructions to start where you left off for the basic assignment while still preserving a copy (.tar.gz or diff file).

Adding support for hierarchical directories

As supplied, SFS has support for various aspects of directories in that it supports a single directory at the root of the mounted file system. See the function table sfs_dirops for a list of supported directory operations. You should add support for the following system calls for vfs file systems in general, and if required, add the underlying support for the operations in SFS itself. Some things you will have to consider when adding hierarchical naming to SFS. Your code should do the following: Your code must not do the following:

Add support for renaming and deleting files

Implement the rename and remove system calls, and the underlying sfs implementation.

Add a Buffer Cache

You will find that the performance of SFS is not great. In particular, there is no buffer cache. You should add a buffer cache to OS/161. You will need to decide what data structures you need to implement this and what interface routines you will use. Figure out exactly where the buffer cache will interface with the rest of the system, and how you will maintain the integrity of your file system in the face of caching. You should have a clear design of your interface and data structures, your replacement algorithms, and any extra precautions you take to ensure the integrity of the file system. Also, consider any additional support necessary to make sure that buffered data eventually gets written to disk.

Advanced Assignment Submission

Submission for the advanced assignment is similar to the basic assignment, except the advance component is given to a distinguished assignment name: asst3-adv Again, you need to clean the source tree. 
% cd ~/cs3231/src
% make clean
% cd kern/compile/ASST3
% make clean
Generate a file containing this diff. 
% cd ~/cs3231
% diff -N -r -u -X src/.diffex ~cs3231/assigns/asst3/src src > ~/asst3-adv.diff

% cd ~
% give cs3231 asst3-adv asst3-adv.diff
You're now done.