HW7: Pantry
HW7a: 200 points total, group project
HW7b: 150 points total, group project
Submission notes
HW7 will be submitted in a single gzipped tarball named group_xx_hw7.tgz
where xx is your two digit group number (with leading zeros, if
applicable).
The top level directory in the tarball must be hw7. You must track at
least the following files in the repo:
format_disk_as_pantryfs.c
Makefile
mypantry.c
README.txt
Create a new repository for this assignment outside of the kernel source
tree.
Just like you did in HW4, please list git commit IDs for each part.
Please use an LTS kernel version between 4.4.43 and 4.4.51. We recommend
using a clean build of the kernel, instead of the development kernel from
the previous homework, to test the pantry module.
A loop device is a pseudo-device that makes a file accessible as a block device.
Files of this kind are often used for CD ISO images. Mounting a file containing
a file system via such a loop mount makes the files within that file system
accessible.
Tasks: ext2
Create a loop device, build & mount an ext2 filesystem, and try creating
directories and files. Below is a sample session you can follow. It
goes without saying that you need to understand what’s going on at each
step. Look at the man pages. Google stuff. You may need to boot into
the LTS kernel for this to work.
jae@vm04 ~/tmp $ sudo su
vm04 /home/jae/tmp # dd if=/dev/zero of=./ext2.img bs=1024 count=100
100+0 records in
100+0 records out
102400 bytes (102 kB) copied, 0.000626388 s, 163 MB/s
vm04 /home/jae/tmp # losetup --find --show ext2.img
/dev/loop0
vm04 /home/jae/tmp # mkfs -t ext2 /dev/loop0
mke2fs 1.42.9 (28-Dec-2013)
Filesystem label=
OS type: Linux
Block size=1024 (log=0)
Fragment size=1024 (log=0)
Stride=0 blocks, Stripe width=0 blocks
16 inodes, 100 blocks
5 blocks (5.00%) reserved for the super user
First data block=1
1 block group
8192 blocks per group, 8192 fragments per group
16 inodes per group
Allocating group tables: done
Writing inode tables: done
Writing superblocks and filesystem accounting information: done
vm04 /home/jae/tmp # mkdir mnt
vm04 /home/jae/tmp # mount /dev/loop0 ./mnt
vm04 /home/jae/tmp # cd mnt
vm04 /home/jae/tmp/mnt # ll
total 17
drwxr-xr-x 3 root root 1024 Apr 20 11:19 ./
drwxr-xr-x 5 jae users 4096 Apr 20 11:20 ../
drwx------ 2 root root 12288 Apr 20 11:19 lost+found/
vm04 /home/jae/tmp/mnt # mkdir sub2
vm04 /home/jae/tmp/mnt # ll
total 18
drwxr-xr-x 4 root root 1024 Apr 20 11:26 ./
drwxr-xr-x 5 jae users 4096 Apr 20 11:20 ../
drwx------ 2 root root 12288 Apr 20 11:19 lost+found/
drwxr-xr-x 2 root root 1024 Apr 20 11:26 sub2/
vm04 /home/jae/tmp/mnt # cd sub2
vm04 /home/jae/tmp/mnt/sub2 # ll
total 2
drwxr-xr-x 2 root root 1024 Apr 20 11:26 ./
drwxr-xr-x 4 root root 1024 Apr 20 11:26 ../
vm04 /home/jae/tmp/mnt/sub2 # mkdir sub2.1
vm04 /home/jae/tmp/mnt/sub2 # ll
total 3
drwxr-xr-x 3 root root 1024 Apr 20 11:27 ./
drwxr-xr-x 4 root root 1024 Apr 20 11:26 ../
drwxr-xr-x 2 root root 1024 Apr 20 11:27 sub2.1/
vm04 /home/jae/tmp/mnt/sub2 # touch file2.1
vm04 /home/jae/tmp/mnt/sub2 # ll
total 3
drwxr-xr-x 3 root root 1024 Apr 20 11:28 ./
drwxr-xr-x 4 root root 1024 Apr 20 11:26 ../
-rw-r--r-- 1 root root 0 Apr 20 11:28 file2.1
drwxr-xr-x 2 root root 1024 Apr 20 11:27 sub2.1/
vm04 /home/jae/tmp/mnt/sub2 # cd ../../
vm04 /home/jae/tmp # umount mnt
vm04 /home/jae/tmp # losetup --find
/dev/loop1
vm04 /home/jae/tmp # losetup --detach /dev/loop0
vm04 /home/jae/tmp # losetup --find
/dev/loop0
vm04 /home/jae/tmp # ll mnt/
total 8
drwxr-xr-x 2 root root 4096 Apr 20 11:20 ./
drwxr-xr-x 5 jae users 4096 Apr 20 11:20 ../
vm04 /home/jae/tmp # exit
exit
jae@vm04 ~/tmp $
In the sample session shown above, files and directories are created.
Make sure you see the number of links each file or directory has, and
make sure you understand why.
Also try creating some hard links and symlinks. Make sure you
understand how they affect the link counts.
Assuming you built your 4.4.50-UNI kernel with a reduced .config
using make localmodconfig, you won’t be able to create and mount a
loop device. Identify the kernel config option(s) required for creating
and mounting loop devices. Rebuild your 4.4.50-UNI kernel and try
running through the session again.
Tasks: PantryFS
In this part, we will mount a loop device and format it as PantryFS. Then, we’ll
use the compiled solution code (pantry.ko) to read our newly formatted disk.
Create a disk image and assign it to a loop device:
dd bs=4096 count=200 if=/dev/zero of=~/pantry_disk.img
losetup --find --show ~/pantry_disk.img
- This will create the file
pantry_disk.img and bind it to an available
loop device, probably /dev/loop0. Now, /dev/loop0 can be used as if it
were a physical disk, and the data backing it will be stored in
pantry_disk.img.
Format the disk as PantryFS.
- The skeleton code contains a formatting program called
format_disk_as_pantryfs.c.
Mount the disk at /mnt/pantry using the reference implementation:
mkdir /mnt/pantry
insmod pantry.ko
mount -t pantryfs /dev/loopN /mnt/pantry
- If you are unable to insert
pantry.ko, you should boot into the LTS
kernel, or recompile your kernel with a full .config and without running
make localmodconfig.
Explore the newly created filesystem. Edit hello.txt and create some new
files.
- You may encounter a warning while using vim. This is the expected
behavior, since vim creates swapfiles that exceed the size limit of our
filesystem.
Deliverables
The formatting utility creates the new filesystem’s root directory and places
hello.txt in that directory. In this part, we will create another directory
and file.
PantryFS Specification
View slides
Tasks
Read the provided formatting utility, format_disk_as_pantryfs.c. Make sure
you understand the on-disk format and what each line contributes toward
creating the filesystem. Test your understanding by thinking about the
following questions:
The program writes two inodes for the root directory and hello.txt, but
does not zero out the rest of the inode block. Can you convince yourself
that this is OK?
However, for filling out the root directory block, the program ensures
that the unused portion of the block is zeroed out. Can you see why this
is necessary?
Extend the program to create a subdirectory called members. The directory
should contain a single file, names.txt, that lists the names of your team
members.
To make things easier, consider starting with an empty members
directory. Once you have that working, create names.txt.
Be sure to set the directories’ link counts correctly.
Create and format a new disk using your modified program. Use the reference
implementation, pantry.ko, to verify that the new file and directory were
created correctly. You can use the stat command to see the size, inode
number, and other properties.
Deliverables
Part 2: The filesystem awakens (50 points)
The rest of this assignment is structured to guide you while implementing your
filesystem driver. Each part represents a milestone toward a working driver,
forcing you to develop incrementally. It also allows the graders to award
partial credit if you don’t get the whole thing working in the end.
In this part, we will begin by writing the code that mounts disks. Later, we’ll
add the ability to read files, modify existing files, create new files, and
delete them. There is an optional part that adds support for creating and
removing directories.
Don’t worry about concurrency in your filesystem driver. That is, you may assume
that each PantryFS disk will only have one thread of one program performing
operations at any given time.
You are welcome to search the web for info. The linux-4.4.50/Documentation
directory contains a wealth of information as well. Here are some resources that
might be useful:
LKD chapter 13
LKD chapter 14: pages 289 - 294
Page cache overview slides
Linux Kernel Internals chapter 3 (Virtual Filesystem)
Documentation/filesystems/vfs.txt
Linux VFS tutorial at lwn.net
- Note that the tutorial was written for an older version of the Linux
kernel, so its code doesn’t build on our version. Nevertheless, the
article provides a good high-level overview of how to interact with VFS.
Tasks
Read the skeleton code starting from its entry point, pantryfs_init().
This module is written so that it can be loaded simultaneously with the
reference implementation. How is this accomplished?
Unmount your PantryFS drive and try to mount it with the skeleton code
instead. The following error message indicates that you are no longer
mounting with the reference implementation:
mount: mount /dev/loop0 on /mnt/pantry failed: Function not implemented
This error is returned from pantryfs_fill_super() via pantryfs_mount().
Implement pantryfs_fill_super() so that you can mount disks. Note that
we’re only interested in making the mount and umount commands work
cleanly in this part. We won’t be reading any files or directories at this
time.
Use sb_set_blocksize() to ensure that the block layer reads blocks of
the correct size.
Read the PantryFS superblock and inodes. Assign them to an instance of
struct pantryfs_sb_buffer_heads. Store this struct in the s_fs_info
member of the VFS superblock. This way, we can always find the PantryFS
superblock and inodes by following the trail of pointers from the VFS
superblock.
The following diagram shows the relationship between these structs after
this step.
You will have to fill out some additional members of the VFS superblock
structure, such as the magic number and pointer to the ops struct.
Use iget_locked() to create a new VFS inode for the root directory.
Read the kernel source to learn what this function does for you and get
some hints on how you’re supposed to use it. The only metadata you need
to set is the mode. Make the root directory drwxrwxrwx for now.
After creating an inode for the root directory, you need to create a
dentry associated with it. Make the VFS superblock point to the dentry.
Make sure to handle errors by returning an appropriate error code. For
example, what if someone asks you to mount a filesystem that isn’t
PantryFS?
Deliverables
Part 3: Listing the contents of the root directory (50 points)
Tasks
In the previous part, we created a VFS inode without associating it with the
corresponding PantryFS inode from disk. Update your code to associate the
root VFS inode with the root PantryFS inode.
Use the i_private member of the VFS inode to store a pointer to the
PantryFS inode. All of the PantryFS inodes live in the inode store that we
read from disk in the previous section.
Note that you must set the i_sb and i_op members so that VFS can
identify which filesystem the inode belongs to.
Consult the diagram in the PantryFS Specification section.
Add support for listing the root directory.
You should be able to run ls and ls -a. Here’s sample session:
[archie@vm17 hw7]$ sudo ls /mnt/pantry
hello.txt members
[archie@vm17 hw7]$ sudo ls -a /mnt/pantry
. .. hello.txt members
[archie@vm17 hw7]$ sudo ls /mnt/pantry/members
ls: cannot access '/mnt/pantry/members': No such file or directory
Note that we do not support listing the contents of a subdirectory yet.
The VFS framework will call the iterate member of the
struct file_operations. Inside your iterate implementation, use
dir_emit() to provide VFS with the contents of the requested
directory. VFS will continue to call iterate until your implementation
returns without calling dir_emit().
You can use the ctx->pos variable as a cursor to the directory entry
that you are about to emit. (Note that the dir_emit_dots() function
modifies ctx->pos.)
The following is an excerpt from the output of
strace ls /usr/bin > /dev/null:
[...]
open("/usr/bin", O_RDONLY|O_NONBLOCK|O_LARGEFILE|O_DIRECTORY|O_CLOEXEC) = 3
[...]
getdents64(3, /* 1007 entries */, 32768) = 32768
[...]
getdents64(3, /* 731 entries */, 32768) = 23960
[...]
getdents64(3, /* 0 entries */, 32768) = 0
close(3) = 0
The ls program first opens the /usr/bin directory file. Then, it
calls getdents64() three times to retrieve the list of 1,738 files in
/usr/bin. Finally, ls closes the directory file.
Each call to getdents64() will result in one call to iterate_dir(),
which in turn will call your iterate implementation. Consequently,
your iterate implementation should call dir_emit() until the given
buffer is full.
Running ls -l might print error messages because the ls program is
unable to stat the files. This is the expected behavior for this part.
Deliverables
- An updated version of
mypantry.c.
Part 4: Accessing subdirectories (30 points)
In this part, we’ll implement the lookup function of inode_operations. The
kernel calls this function repeatedly as it walks through a filepath such as
/a/b/c/d/e/f.txt. For example, once it knows the inode of c, it will ask you
for the inode associated with the name d in the directory c. Your job is to
retrieve the inode for d from the filesystem.
To avoid repeated work when looking up similar paths, the kernel maintains a
cache called the dentry cache. Learn how the dentry cache works by reading the
materials given earlier.
Tasks
Add support for looking up filepaths.
You should be able to cd into directories and ls the contents of
directories that aren’t the root.
As a side effect, the -l flag and stat command should work on both
files and directories now.
Here’s a sample session:
[archie@vm17 hw7]$ sudo su - root
[root@vm17 ~]# ls /mnt/pantry/members
names.txt
[root@vm17 ~]# cd /mnt/pantry/members
[root@vm17 members]# stat names.txt
File: names.txt
Size: 0 Blocks: 0 IO Block: 4096 regular empty file
Device: 700h/1792d Inode: 4 Links: 1
Access: (0000/----------) Uid: ( 0/ root) Gid: ( 0/ root)
Access: 2017-03-30 02:42:27.629345430 -0400
Modify: 2017-03-30 02:42:27.629345430 -0400
Change: 2017-03-30 02:42:27.629345430 -0400
Birth: -
[root@vm17 members]# stat does_not_exist.txt
stat: cannot stat 'does_not_exist.txt': No such file or directory
[root@vm17 members]# ls -l ..
total 0
---------- 1 root root 0 Apr 3 23:31 hello.txt
d--------- 1 root root 0 Dec 31 1969 members
VFS does most of the heavy lifting when looking up a filepath. It splits
up the given path and looks up each part in the dentry cache. If a part
isn’t in the dentry cache, it asks you to add it. Before you add things to
the dentry cache, you’re responsible for determining whether the given
parent directory contains an entry with the given name.
Don’t worry about returning metadata correctly at this time. That is, it’s
fine to show incorrect permission bits, create/modify/access times, owner,
group, etc.
Deliverables
- An updated version of
mypantry.c.
Part 5: Reading the contents of regular files (20 points)
In this part, we are going to implement reading the contents of files. Our implementation is made very simple by the fact that each file occupies exactly one block.
Tasks
Add support for reading the contents of files.
[archie@vm17 hw7]$ sudo cat /mnt/pantry/hello.txt
Hello world!
[archie@vm17 hw7]$ sudo cat /mnt/pantry/members/names.txt
Kevin Chen
Mitchell Gouzenko
John Hui
[archie@vm17 hw7]$ sudo dd if=/mnt/pantry/hello.txt
Hello world!
0+1 records in
0+1 records out
13 bytes copied, 4.5167e-05 s, 266 kB/s
[archie@vm17 hw7]$ sudo dd if=/mnt/pantry/hello.txt bs=1 skip=6
world!
7+0 records in
7+0 records out
7 bytes copied, 5.1431e-05 s, 117 kB/s
- Which parameters are controlled by the user program? Make sure to check
whether they’re reasonable.
Deliverables
- An updated version of
mypantry.c.
Part 6: A full-featured, read-only PantryFS implementation (20 points)
Tasks
Fix all of the corners we cut in the previous section by making sure your
code returns correct metadata for all files and directories. These include
size, link count, timestamps, permissions, owner, and group.
At this point, you should stress test your PantryFS implementation. The rest
of this assignment will be easier if you can depend on the reading
functionality to report things correctly.
Here are some ideas:
Try copying all the files in your pantry with cp or rsync:
cp --archive /mnt/pantry/ ~/stuff-in-pantry/
Extend the formatting program again to create additional files and a more
complex directory structure. Be sure to include different file types. For
example, add a small team photo to the members directory.
Overwrite the disk with random garbage from /dev/urandom (instead of
/dev/zero). Format it. After formatting, the random data should not
affect the normal operation of the filesystem.
Write a program that requests invalid offsets when reading files or
iterating through directories.
Deliverables
HW7b: Writable Pantry
Below is HW7b (i.e., parts 7–10 of HW7). Before you start, please complete the
following.
Please download the updated skeleton code. We fixed some bugs in pantry.ko,
and made the following bugfix to the bitvector macros in pantryfs_sb.h. If you
modified that header file, simply make the change yourself:
-#define SETBIT(A,k) ( A[(k/32)] |= (1 << (k%32)) )
-#define CLEARBIT(A,k) ( A[(k/32)] &= ~(1 << (k%32)) )
-#define IS_SET(A,k) ( A[(k/32)] & (1 << (k%32)) )
+#define SETBIT(A,k) ( A[((k) / 32)] |= (1 << ((k) % 32)) )
+#define CLEARBIT(A,k) ( A[((k) / 32)] &= ~(1 << ((k) % 32)) )
+#define IS_SET(A,k) ( A[((k) / 32)] & (1 << ((k) % 32)) )
Review the ops structs in the header files ending with *_ops.h. Ensure that
you have commented out all unimplemented function pointers.
By the way, you may set the setattr function pointer to NULL or remove it
entirely. This causes VFS to run simple_setattr() instead, which is fine for
our purposes.
Part 7: Overwriting existing files (40 points)
So far, we’ve only been reading what’s already on the filesystem. In this part,
we’ll begin implementing functions for modifying the filesystem contents.
Tasks
Add support for overwriting the contents of existing files.
If the existing file is smaller than the user buffer to be written, you
don’t have to worry about changing the length of the file. Just write
into the buffer head representing the data block until you reach the end
of the user buffer or exceed the file’s size.
Here’s a sample session. The notrunc option is needed to prevent dd
from passing the O_TRUNC flag to open(), which sets the length of
the file to zero.
[archie@vm17 hw7]$ cd /mnt/pantry
[archie@vm17 pantry]$ echo -ne "4118" | dd of=hello.txt bs=1 seek=7 conv=notrunc
[...]
[archie@vm17 pantry]$ cat hello.txt
Hello w4118!
[archie@vm17 pantry]$ echo "Greetings and salutations, w4118!" | dd of=hello.txt conv=notrunc
[...]
[archie@vm17 pantry]$ cat hello.txt
Greetings and[archie@vm17 pantry]$
Writing to the buffer head only changes the contents in memory. It does
not cause those changes to be written back to disk. Be sure to take the
appropriate measures so that your modifications are written to disk.
Properly update the VFS inode’s size if the length of the write exceeds the
file’s length.
Here’s a sample session:
[archie@vm17 pantry]$ ls -l hello.txt
-rw-rw-rw- 1 archie users 13 Apr 16 17:15 hello.txt
[archie@vm17 pantry]$ echo "Greetings and salutations, w4118!" > hello.txt
[archie@vm17 pantry]$ cat hello.txt
Greetings and salutations, w4118!
[archie@vm17 pantry]$ ls -l hello.txt
-rw-rw-rw- 1 archie users 34 Apr 16 17:32 hello.txt
[archie@vm17 pantry]$ echo "Hi w4118!" > hello.txt
[archie@vm17 pantry]$ cat hello.txt
Hi w4118!
[archie@vm17 pantry]$ ls -l hello.txt
-rw-rw-rw- 1 archie users 10 Apr 16 17:38 hello.txt
You should also be able to edit files with the nano editor.
Ensure that changes to the VFS inode are written back to disk. You
should do this by implementing pantryfs_write_inode(). Of course, VFS
needs to be informed that the VFS inode is out of sync with the PantryFS
inode.
Test this by unmounting and remounting.
You may have noticed that although the nano editor works, vim complains
about fsync() failing and refuses to save the file. Fix it.
- You can use the Linux page cache function
sync_dirty_buffer() to have
a dirty buffer written to disk immediately.
Deliverables
- An updated version of
mypantry.c.
Part 8: Creating new files (50 points)
Tasks
Implement creating new files. That is, user programs should be able to call
open() with a mode that includes O_CREAT.
What you need to do in this part is a combination of what you did in
Part 1 (“Creating additional files upon formatting”) and Task 3 of
Part 2 (“The filesystem awakens”).
Here’s a sample session:
[archie@vm17 hw7]$ cd /mnt/pantry/
[archie@vm17 pantry]$ ls
hello.txt members
[archie@vm17 pantry]$ touch world.txt
[archie@vm17 pantry]$ ls
hello.txt members world.txt
[archie@vm17 pantry]$ stat world.txt
File: world.txt
Size: 0 Blocks: 0 IO Block: 4096 regular empty file
Device: 700h/1792d Inode: 5 Links: 1
Access: (0644/-rw-r--r--) Uid: ( 1000/ archie) Gid: ( 100/ users)
Access: 2017-04-16 19:21:03.000000000 -0400
Modify: 2017-04-16 19:21:03.000000000 -0400
Change: 2017-04-16 19:21:03.000000000 -0400
Birth: -
[archie@vm17 pantry]$ cat > members/favorite_foods.txt
tacos
pad thai
kale
[archie@vm17 pantry]$ cat members/favorite_foods.txt
tacos
pad thai
kale
Deliverables
- An updated version of
mypantry.c.
Part 9: Deleting files (60 points)
While testing the previous part, you probably created lots of files that are now
cluttering your disk. Let’s implement a way to delete those files.
Tasks
Review how the VFS dentry and inode caches interact with each other using
the resources given earlier in this assignment.
Implement the unlink and evict_inode ops so that you can delete files.
You are not required to implement directory removal functionality.
Ensure that you are reclaiming data blocks and PantryFS inodes when
appropriate. To test this, see if you can repeatedly create and remove
files.
for i in {1..10}; do touch {1..14}; rm {1..14}; done
In a Unix-like operating system, what is the correct behavior if one
process unlinks a file while another process has the same file open?
Here’s an experiment you can run on ext4 or the PantryFS reference
implementation to find out:
Create a file named foo.
In terminal window A, run tail -f foo. This command will open foo,
print out all the contents, and wait for more lines to be written.
In terminal B, run cat > foo. This reads from stdin and outputs
the result to foo.
In terminal C, delete foo.
Back in terminal B, type some text and press return.
The text should appear in terminal A.
You can also use this C program, which tests the same functionality
without you having to open three terminal windows.
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int wait_for_user()
{
printf("Press any key to continue...");
return getchar();
}
int main(int argc, char **argv)
{
int fd;
int ret;
char buf[4096];
ssize_t len;
if (argc != 2) {
printf("usage: %s /path/to/file\n", argv[0]);
return 1;
}
fd = open(argv[1], 0);
printf("=> Opened as fd %d\n", fd);
wait_for_user();
ret = unlink(argv[1]);
printf("=> Called unlink(%s) = %d\n", argv[1], ret);
printf("=> Running ls to show that hello.txt is unlinked:\n");
system("ls /mnt/pantry");
wait_for_user();
len = read(fd, buf, sizeof(buf));
if (len > 0) {
printf("=> Read %d bytes:\n", len);
fwrite(buf, 1, len, stdout);
}
wait_for_user();
ret = close(fd);
printf("=> close(fd) = %d\n", ret);
return 0;
}
Deliverables
- An updated version of
mypantry.c.
Part 10: Implementing odds and ends (0 points)
This part is optional. However, if you successfully complete one or more
tasks in this part, Jae will take it into consideration for boosting borderline
grades at the end of the semester.
Tasks
Implement creating new directories. mkdir should work.
- Be sure to update the appropriate link counts.
Implement removing directories. rmdir should work on empty directories.
- Be sure to update the appropriate link counts.
Implement hard and soft links. ln should work on regular files, and
ln -s should work on both regular files and directories.
- Make sure that unlink works correctly on inodes with multiple hard links.
Acknowledgment
The PantryFS assignment and reference implementation are designed and
implemented by the following TAs of COMS W4118 Operating Systems I, Spring 2017,
Columbia University:
- Mitchell Gouzenko
- Kevin Chen
Last updated: 2017–04–17