Description
Introduction
In this assignment, you will explore the implementation of a particular file system, ext2, and will write tools
to modify ext2-format virtual disks. To do this work, you will need to be comfortable working with binary
data and will need to learn about the ext2 filesystem.
You can work in pairs for this assignment. MarkUs will only create the appropriate A4 directory in your
repository when you log into MarkUs and either invite a partner, or declare that you will work alone. As
usual, please log into MarkUs well before the deadline to make sure you can access your repository. (Do
not create an A4 the directory in svn, otherwise MarkUs won’t know about it and we won’t be able to see
your work.)
This assignment contains some bonus features. Implementing a bonus will compensate for any possible
marks lost in another section of the assignment, but can also give you more than 100% if implemented
correctly. For implementing any additional functionality which is not specified in the handout, or if you are
unsure whether to handle some inode parameters in specific cases (after having read the documentation!),
please ask on the discussion board.
Requirements
Your task is to write a set of programs (in C) that operate on an ext2 formatted virtual disk. The
executables must be named exactly as listed below, and must take the specified arguments.
ext2_cp: This program takes three command line arguments. The first is the name of an ext2
formatted virtual disk. The second is the path to a file on your native operating system, and the third
is an absolute path on your ext2 formatted disk. The program should work like cp, copying the file
on your native file system onto the specified location on the disk. If the specified file or target
location does not exist, then your program should return the appropriate error (ENOENT). Please
read the specifications of ext2 carefully, some things you will not need to worry about (like
permissions, gid, uid, etc.), while setting other information in the inodes may be important (e.g.,
i_dtime).
ext2_mkdir: This program takes two command line arguments. The first is the name of an ext2
formatted virtual disk. The second is an absolute path on your ext2 formatted disk. The program
should work like mkdir, creating the final directory on the specified path on the disk. If any
component on the path to the location where the final directory is to be created does not exist or if
the specified directory already exists, then your program should return the appropriate error
(ENOENT or EEXIST). Again, please read the specifications to make sure you’re implementing
everything correctly (e.g., directory entries should be aligned to 4B, entry names are not nullterminated, etc.).
ext2_ln: This program takes three command line arguments. The first is the name of an ext2
formatted virtual disk. The other two are absolute paths on your ext2 formatted disk. The program
should work like ln, creating a link from the first specified file to the second specified path. This
program should handle any exceptional circumstances, for example: if the source file does not exist
(ENOENT), if the link name already exists (EEXIST), if a hardlink refers to a directory (EISDIR), etc.
then your program should return the appropriate error code. Additionally, this command may take a
“-s” flag, after the disk image argument. When this flag is used, your program must create a symlink
instead (other arguments remain the same). If in doubt about correct operation of links, use the ext2
specs and ask on the discussion board.
ext2_rm: This program takes two command line arguments. The first is the name of an ext2
formatted virtual disk, and the second is an absolute path to a file or link (not a directory) on that
disk. The program should work like rm, removing the specified file from the disk. If the file does not
exist or if it is a directory, then your program should return the appropriate error. Once again, please
read the specifications of ext2 carefully, to figure out what needs to actually happen when a file or
link is removed (e.g., no need to zero out data blocks, must set i_dtime in the inode, removing a
directory entry need not shift the directory entries after the one being deleted, etc.).
BONUS: Implement an additional “-r” flag (after the disk image argument), which allows removing
directories as well. In this case, you will have to recursively remove all the contents of the directory
specified in the last argument. If “-r” is used with a regular file or link, then it should be ignored (the
ext2_rm operation should be carried out as if the flag had not been entered). If you decide to do the
bonus, make sure first that your ext2_rm works, then create a new copy of it and rename it to
ext2_rm_bonus.c, and implement the additional functionality in this separate source file.
ext2_restore: This program takes two command line arguments. The first is the name of an ext2
formatted virtual disk, and the second is an absolute path to a file or link (not a directory!) on that
disk. The program should be the exact opposite of rm, restoring the specified file that has been
previous removed. If the file does not exist (it may have been overwritten), or if it is a directory, then
your program should return the appropriate error.
Hint: The file to be restored will not appear in the directory entries of the parent directory, unless you
search the “gaps” left when files get removed. The directory entry structure is the key to finding out
these gaps and searching for the removed file.
Note: If the directory entry for the file has not been overwritten, you will still need to make sure that
the inode has not been reused, and that none of its data blocks have been reallocated. You may
assume that the bitmaps are reliable indicators of such fact. If the file cannot be fully restored, your
program should terminate with ENOENT, indicating that the operation was unsuccessful.
Note(2): For testing, you should focus primarily on restoring files that you’ve removed using your
ext2_rm implementation, since ext2_restore should undo the exact changes made by ext2_rm.
While there are some removed entries already present in some of the image files provided, the
respective files have been removed on a non-ext2 file system, which is not doing the removal the
same way that ext2 would. In ext2, when you do “rm”, the inode’s i_blocks do not get zeroed, and
you can do full recovery, as stated in the assignment (which deals solely with ext2 images, hence
why you only have to worry about this type of (simpler) recovery). In other FSs things work
differently. In ext3, when you rm a file, the data block indexes from its inode do get zeroed, so
recovery is not as trivial. For example, there are some removed files in deletedfile.img, which
have their blocks zero-ed out (due to how these images were created). In such cases, your code
should still work, but simply recover a file as an empty file (with no data blocks). However, for the
most part, try to recover files that you’ve ext2_rm-ed yourself, to make sure that you can restore
data blocks as well.
Note(3): We will not try to recover files that had hardlinks at the time of removal. This is because
when trying to restore a file, if its inode is already in use, there are two options: the file we’re trying
to restore previously had other hardlinks (and hence its inode never really got invalidated), _or_ its
inode has been re-allocated to a completely new file. Since there is no way to tell between these 2
possibilities, recovery in this case should not be attempted.
BONUS: Implement an additional “-r” flag (after the disk image argument), which allows restoring
directories as well. In this case, you will have to recursively restore all the contents of the directory
specified in the last argument. If “-r” is used with a regular file or link, then it should be ignored (the
restore operation should be carried out as if the flag had not been entered). If you decide to do the
bonus, make sure first that your ext2_restore works, then create a new copy of it and rename it to
ext2_restore_bonus.c, and implement the additional functionality in this separate source file.
ext2_checker: This program takes only one command line argument: the name of an ext2
formatted virtual disk. The program should implement a lightweight file system checker, which
detects a small subset of possible file system inconsistencies and takes appropriate actions to fix
them (as well as counts the number of fixes), as follows:
a. the superblock and block group counters for free blocks and free inodes must match the
number of free inodes and data blocks as indicated in the respective bitmaps. If an
inconsistency is detected, the checker will trust the bitmaps and update the counters. Once
such an inconsistency is fixed, your program should output the following message: “Fixed:
X’s Y counter was off by Z compared to the bitmap”, where X stands for either “superblock”
or “block group”, Y is either “free blocks” or “free inodes”, and Z is the difference (in absolute
value). The Z values should be added to the total number of fixes.
b. for each file, directory, or symlink, you must check if its inode’s i_mode matches the directory
entry file_type. If it does not, then you shall trust the inode’s i_mode and fix the file_type to
match. Once such an inconsistency is repaired, your program should output the following
message: “Fixed: Entry type vs inode mismatch: inode [I]”, where I is the inode number for the
respective file system object. Each inconsistency counts towards to total number of fixes.
c. for each file, directory or symlink, you must check that its inode is marked as allocated in the
inode bitmap. If it isn’t, then the inode bitmap must be updated to indicate that the inode is in
use. You should also update the corresponding counters in the block group and superblock
(they should be consistent with the bitmap at this point). Once such an inconsistency is
repaired, your program should output the following message: “Fixed: inode [I] not marked as
in-use”, where I is the inode number. Each inconsistency counts towards to total number of
fixes.
d. for each file, directory, or symlink, you must check that its inode’s i_dtime is set to 0. If it isn’t,
you must reset (to 0), to indicate that the file should not be marked for removal. Once such an
inconsistency is repaired, your program should output the following message: “Fixed: valid
inode marked for deletion: [I]”, where I is the inode number. Each inconsistency counts
towards to total number of fixes.
e. for each file, directory, or symlink, you must check that all its data blocks are allocated in the
data bitmap. If any of its blocks is not allocated, you must fix this by updating the data
bitmap. You should also update the corresponding counters in the block group and
superblock, (they should be consistent with the bitmap at this point). Once such an
inconsistency is fixed, your program should output the following message: “Fixed: D in-use
data blocks not marked in data bitmap for inode: [I]”, where D is the number of data blocks
fixed, and I is the inode number. Each inconsistency counts towards to total number of fixes.
Your program must count all the fixed inconsistencies, and produce one last message: either “N file
system inconsistencies repaired!”, where N is the number of fixes made, or “No file system
inconsistencies detected!”.
You may limit your consistency checks to only regular files, directories and symlinks.
Hint: You might want to fix the counters based on the bitmaps, as a one-time step before attempting
to fix any other type of inconsistency. Even if initially trusting the bitmaps may not be the way to go
(since they could be corrupted), the counters should get readjusted in the later steps anyway,
whenever the bitmaps get updated. The Z values from point a) should be added to the tally of fixes,
but do not include any further superblock or block group counter adjustments from points c) and e)
(since technically these may be just correcting the adjustments made in point a)).
All of these programs should be minimalist. Don’t implement what isn’t specified: only provide the required
functionality and specified errors. (For example, don’t implement wildcards. Also, can’t delete directories?
Too bad! Unless you want the bonus! 🙂
You will find it very useful for these programs to share code. You will want a function that performs a path
walk, for example. You will also want a function that opens a specific directory entry and writes to it.
To help you visualize your file system, we are giving you an already built tool, called ext2_ls
(ext2_ls). This program takes two command line arguments.
– The first is the name of an ext2 formatted virtual disk.
– The second is an absolute path on the ext2 formatted disk.
The program works like ls -1a (that’s number one “1”, not lowercase letter “L”): it prints one line for
every directory entry (including “.” and “..”) from the directory specified by the absolute path. If the path
does not exist, it prints “No such file or directory”. If the path is a file or link, the tool simply prints the full
path on a single line.
We are also giving you a tool called ext2_dump (ext2_dump), which dumps all the raw information
about the image contents. This is very similar to the readimage program that you have to implement for the
tutorial exercises that give you practice with ext2 images. Once again, we encourage you to work on the
tutorial exercises first, to gain experience with extracting various bits of information from an ext2 image.
We are also giving you a tool called ext2_corruptor (ext2_corruptor), which corrupts file system
images, introducing various inconsistencies like the ones that you have to fix. This tool has limited
capabilities, and is solely to help you with basic testing. You are welcome to develop your own corruptor
tool as well.
Finally, to help you in determine some basic correctness, we are giving you some sample test cases:
running a set of commands and their expected outputs (image dumps). These self-tester test cases are
found on the teaching labs under: /u/csc369h/winter/pub/public/A4-self-test
Learning about the Filesystem
Here are several sample virtual disk images:
emptydisk (./images/emptydisk.img): An empty virtual disk.
onefile (./images/onefile.img): A single text file has been added to emptydisk.
deletedfile (./images/deletedfile.img): The file from onefile has been removed.
onedirectory (./images/onedirectory.img): A single directory containing a text file has been added to
emptydisk.
hardlink (./images/hardlink.img): A hard link to the textfile in onedirectory was added.
deleteddirectory (./images/deleteddirectory.img): A recursive remove was used to remove the
directory and file from onedirectory.
twolevel (./images/twolevel.img): The root directory contains a directory called level1 and a file
called afile. level1 contains a directory called level2, and level2 contains a file called
bfile.
twolevel-corrupt (./images/twolevel-corrupt.img): Same as twolevel, except that the image
contains file system inconsistencies that you will have to repair with the checker.
twolevel-norestore-afile (./images/twolevel-norestore-afile.img): Same as twolevel, except that
/afile has been removed, and its inode number has been reused. This image can be used for testing
the case when a file cannot be restored.
largefile (./images/largefile.img): A file larger than 13KB (13440 bytes) is in the root directory. This file
requires the single indirect block in the inode.
These disks were each created and formatted in the same way (on an ubuntu virtual machine):
% dd if=/dev/zero of=~/DISKNAME.img bs=1024 count=128
% mke2fs -N 32 DISKNAME.img
% sudo mount -o loop ~/DISKNAME.img /home/bogdan/mntpoint
% cd /home/bogdan/mntpoint
% …… normal linux commands to add/remove files/directories/links …..
% cd ~
% umount /home/bogdan/mntpoint
Since we are creating images with mke2fs, the disks are formatted with the ext2 file system
(http://en.wikipedia.org/wiki/Ext2). You may wish to read about this system before doing some exploration.
The wikipedia page for ext2 (http://en.wikipedia.org/wiki/Ext2) provides a good overview, but the Ext2 wiki
(http://wiki.osdev.org/Ext2) and Dave Poirer’s Second Extended File System (http://www.nongnu.org/ext2-
doc/index.html) article provide more detail on how the system places data onto a disk. It’s a good
reference to keep on hand as you explore.
We are restricting ourselves to some simple parameters, so you can make the following assumptions when
you write your code:
A disk is 128 blocks where the block size is 1024 bytes.
There is only one block group.
There are 32 inodes.
You do not have to worry about permissions or modified time fields in the inodes. You should set the
type (in i_mode), i_size, i_links_count, i_blocks(disk sectors), and the i_block array.
We will not test your code on anything other than disk images that follow this specification, or on
corrupted disk images.
Other tips:
Inode and disk block numbering starts at 1 instead of 0.
The root inode is inode number 2 (at index 1)
The first 11 inodes are reserved.
There is always a lost+found directory in the root directory.
Disk sectors are 512 bytes. (This is relevant for the i_blocks field of the inode.)
You should be able to handle directories that require more than one block.
You should be able to handle a file that needs a single indirection
Although you can construct your own structs from the information in the documentation above, you
are welcome to use the ext2.h (./ext2.h) file that I used for the test code. I took out a bunch of
components that we aren’t using, but there are still quite a few fields that are irrelevant for our
purposes.
However, you will probably also want to explore the disk images to get an intuitive sense of how they are
structured. (The next three exercises will also help you explore the disk images and get started on the
assignment.)
There are two good ways to interface with these images. The first way is to interact with it like a user by
mounting the file system so that you can use standard commands (mkdir, cp, rm, ln) to interact with it.
Details of how to do this are below. The second way is to interact with the disk as if it is a flat binary file.
Use xxd to create hex dumps, diff to look for differences between the dumps, and your favorite text
editor to view the diffs. For example (YMMV):
% diff <(xxd emptydisk.img) <(xxd onefile.img) > empty-onefile.diff
% vimdiff empty-onefile.diff
You should be able to use a combination of these techniques to understand how files are placed on disk
and how they are removed. For example, you can create a new disk image, use mount to place files of
various sizes on it, unmount it, and then use xxd and diff to see how the image differs from the other
images you have.
Mounting a file system
If you have root access on a Linux machine (or Linux virtual machine), you can use mount to mount the
disk into your file system and to peruse its contents. (Note: this requires sudo, so you will need to do this
on a machine (or virtual machine) that you administer.
On the teaching labs, you can use a tool called FUSE that allows you to mount a file system at user-level
(from your regular account). It may not work on an NFS mounted file system, so this will only work on the
teaching labs workstations (it will not work via ssh-ing remotely).
Note: should be replaced with your own UtorID below.
# create a directory in /tmp and go there
mkdir -m 700 /tmp/-csc369h
cd /tmp/-csc369h
# to create your own disk image
dd if=/dev/zero of=DISKNAME.img bs=1024 count=128
/sbin/mke2fs -N 32 -F DISKNAME.img
# create a mount point and mount the image
# CWD is /tmp/-csc369h
mkdir mnt
fuseext2 -o rw+ DISKNAME.img mnt
# check to see if it is mounted
df -hl
# now you can use the mounted file system, for example
mkdir mnt/test
# unmount the image
fusermount -u mnt
You can use the same strategy to mount one of the images provided above.
Marking scheme
ext2_cp: 12%
ext2_mkdir: 12%
ext2_ln: 12%
ext2_rm: 14% (+5% bonus)
ext2_restore: 20% (+5% bonus)
ext2_checker: 20%
Coding Style: 10%
Submission
The assignment should be submitted to an A4 directory in your svn repository. Don’t forget to add and
commit all of the code for the required programs. Please also provide a Makefile that will create your
programs. Your Makefile should use -Wall, and produce no warnings. Please make sure that your Makefile
includes the following separate targets:
ext2_cp: compiles and produces the ext2_cp executable
ext2_mkdir: compiles and produces the ext2_mkdir executable
ext2_ln: compiles and produces the ext2_ln executable
ext2_rm: compiles and produces the ext2_rm executable
ext2_rm_bonus (optional) compiles and produces the ext2_rm_bonus executable (optional,
for bonus)
ext2_restore: compiles and produces the ext2_restore executable
ext2_restore_bonus (optional): compiles and produces the ext2_restore_bonus
executable (optional, for bonus)
ext2_checker: compiles and produces the ext2_checker executable
Additionally, invoking make without arguments must compile all the targets.
Please consider separating the bonus parts as indicated above, in order to make it easier for us to
determine if you did the bonus or not. The bonus source files and their counterparts may include large
portions of the same code. This will make it easier for you as well, to make sure that at the very least the
baseline implementation works, even if the bonus part may have problems or crash your baseline (nonbonus) implementation.
Additionally, you must submit an INFO.txt file, which contains as the first 3 lines the following:
your name(s)
your UtorID(s)
the svn revision number for your last submission. As a general rule, we will always take the last
revision before the deadline (or after, if you decide to use grace tokens), so this is simply a sanity
check for us that we did not miss a revision when we retrieve your code via MarkUs.
Aside from this, please feel free to describe problems you’ve encountered, what isn’t fully implemented (or
doesn’t work fully), any special design decisions you’ve taken, etc. Feel free to explain what is not
powered by Jekyll-Bootstrap-3 (http://jekyll-bootstrap-3.github.io/preview/#/theme/Bootstrap) and Twitter
Bootstrap 3.0.3 (http://getbootstrap.com)
© 2017 Bogdan Simion
implemented and describe what features you have completed. You may receive partial credit for
functionality that is implemented but that does not complete one of the five required programs
successfully.
Final (and Very Important) notes:
– Assignments missing a Makefile will receive a 0, as if the code did not compile!
– You must make sure that your Makefile compiles all of your files, including possible helper files,
depending on your design, and that you have included all the necessary targets specified above.
– You must make sure that the source files that are mandatory are named exactly as indicated in the
handout, and that the Makefile produces executables with the same name excluding the .c extension
(for example: compiling ext2_cp.c should generate an executable named ext2_cp – do not submit the
executables though).
– Missing files due to submission mistakes (forgot to add files, forgot to commit last version, etc.), will
not be considered!
– It is your responsibility to ensure that your code works exactly as you expect it to, on the teaching
labs!
