ECE357 PS 2 A simple hypothetical filesystem solution




5/5 - (5 votes)

Problem 1 — A simple hypothetical filesystem
In this problem, you’ll trace out the operation of a simple, hypothetical filesystem which follows the principles laid
out under “UNIX Filesystems” in the lecture notes. Specifically, we envision this filesystem as having a superblock,
inode table, free map and data block areas. To simplify this problem, we can represent the inode “table”
schematically, as in the lecture notes, as a table with rows representing inodes and columns the fields of the inode.
I.e. we won’t concern ourselves with the actual on-disk layout of the inode. We’ll also ignore the superblock and the
free map. We shall not worry about how the filesystem actually allocates blocks. Directories will be represented as a
table of name/inode# pairs. We won’t worry about how the directory is actually laid out, or how much disk space it
takes. Here are a few more assumptions:
• The first inode is #2 (as is conventional)
• When allocating an inode, the lowest numbered free inode is used
• Directories are in order of directory entry creation time (not sorted by name or inode #, etc.)
Now, let’s get started. I initialized a volume and made the first file and the first subdirectory:
mkfs /dev/sda1 #Don’t try this at home, folks!
mount /dev/sda1 /mnt1
mkdir /mnt1/alpha
echo “TEST123” >/mnt1/alpha/beta
This is what the volume looks like at this point, so you have a clear idea of the representational format:
Inode #
Type nlink (data)
NowIperform the following operations:
mkdir /mnt1/alpha/gamma
ln /mnt1/alpha/beta /mnt1/alpha/gamma/delta
ln -s /mnt1/alpha/beta /mnt1/epsilon
rm /mnt1/alpha/beta
echo “ggg” >/mnt1/alpha/zeta
ECE357:Computer Operating Systems PS 2/pg 2 ©2018 Jeff Hakner
Sketch the inode table and directories at this point (attach separate page)
Problem 2 — Exploratory Questions
Answer each of the following with a paragraph or two in your own words. After you read the lecture notes, you’ll
have enough material to answer.
a) What is the advantage of a cylinder group organization of a filesystem vs the traditional approach (e.g. page 4 of
the lecture notes)? How about when using a SSD?
b) List the reasons why a umount command would fail
c) At exactly 1PM on Sep 26, 2018 (approximately when you will have started this assignment) I create a file:
echo “HELLO” >file123
Then at 1:10PM I do
cat file123
Finally, at 1:30 PM I do:
touch -m -t 09091313.13 file123
What are the values of atime, mtime and ctime (you can represent these in human-readable form instead of UNIX
“seconds since 1970”)
Problem 3 — Recursive filesystem lister
Write a program in C which uses the directory exploration library functions such as readdir to produce a recursive
directory listing which is similar to the output of find /starting_directory -ls
The program takes one optional argument which is the starting directory. If this is omitted, it defaults to “./” which is
the current directory. Output of the program goes to stdout. Any errors should go to stderr. There is no prohibition
against using library functions, except that you must use opendir(3) and related functions to scan directories. Don’t
cheat by using something like ftw(3)
First, make some test cases by making nested directories with various files inside. See what the find command
does. This will give you a basis of comparison with your own program output. If you format your output the same
way, you can even use the diff command to compare. On the course web site, you’ll find a small sample filesystem
which can be used for testing. You should also run your own tests, e.g. on your own Linux system’s file tree.
For reference, the output of find with the -ls option is:
Inode #, disk usage of file (measured in units of 1K), inode type and mode
string, link count, uid name (or number if no number->name translation
is found), gid name (ditto), file size, mtime in human-readable format,
full path name, for symlinks only: the string ” -> ” and the contents
of the symlink
ECE357:Computer Operating Systems PS 2/pg 3 ©2018 Jeff Hakner
This output is identical to what would be produced by running ls -dils on each full path name.
Note that the order in which the directory entries are printed is not necessarily sorted. It is simply the order in which
readdir returns the entries. Along with that, the order of recursion (e.g. depth-first) is not defined. Subdirectories
are recursively descended as they are encountered (as opposed to, for example, exploring all the subdirectories first
before listing the contents of the current directory).
There are some issues which we’ll consider beyond the scope of this simple program. 1) you aren’t required to detect
loops in the filesystem tree, which after all could only happen if someone managed to create a forbidden hard link to
a directory 2) you don’t hav e to worry about running out of file descriptors for opendir because of a tree that is too
deep. Just detect the error in this case, but no need to recover from it.
Submission: the program source code, some screenshots showing the program running. If you used diff to verify
your output, show that too.
Problem 4 — Extra Credit Filesystem corruption and recover y– 1pt
Attach screenshots (or terminal session text pastes) as you perform the following system maintenance tasks. Note:
you must do these as root (uid 0) on a real UNIX system. It might not work on a VM modulo issues in passing
through USB devices. The examples below are specific to Linux. Be very careful since an error in one of these
commands could destroy data on your hard disk! There are numerous online resources to help you with this process.
1) Obtain a USB memory stick or USB external hard disk that you don’t care about.
2) Attach this device to your system. Using the dmesg command you should see some system log messages which
reveal which device node the kernel has assigned to the drive. A typical series of log messages is below:
[1309116.520803] usb 1-4: new high-speed USB device number 3 using ehci-pci
[1309116.648472] usb 1-4: New USB device found, idVendor=154b, idProduct=005b
[1309116.648475] usb 1-4: New USB device strings: Mfr=1, Product=2, SerialNumber=3
[1309116.648477] usb 1-4: Product: USB 2.0 FD
[1309116.648479] usb 1-4: Manufacturer: PNY Technologies
[1309116.648481] usb 1-4: SerialNumber: AA00000000000033
[1309116.648836] usb-storage 1-4:1.0: USB Mass Storage device detected
[1309116.648947] scsi10 : usb-storage 1-4:1.0
[1309118.001013] scsi 10:0:0:0: Direct-Access PNY USB 2.0 FD 1100 PQ: 0 ANSI: [1309118.001181] sd 10:0:0:0: Attached scsi generic sg8 type 0
[1309118.002042] sd 10:0:0:0: [sdh] 63901440 512-byte logical blocks: (32.7 GB/30.4 GiB)
[1309118.002862] sd 10:0:0:0: [sdh] Write Protect is off
[1309118.002864] sd 10:0:0:0: [sdh] Mode Sense: 43 00 00 00
[1309118.003578] sd 10:0:0:0: [sdh] No Caching mode page found
[1309118.003580] sd 10:0:0:0: [sdh] Assuming drive cache: write through
[1309118.007737] sdh: sdh1
[1309118.010834] sd 10:0:0:0: [sdh] Attached SCSI removable disk
Verify that the description of the device matches what you just inserted! Note that the kernel has assigned
/dev/sdh to the overall disk, and that there is one partition /dev/sdh1.
ECE357:Computer Operating Systems PS 2/pg 4 ©2018 Jeff Hakner
3) MakeaLinux EXT2 filesystem on the disk (OK to use either the partition or the entire disk). Make sure
journalling is NOT enabled in this case. Show the commands and responses.
4) Mount the disk. Show the output of the mount commands (without any arguments) which shows the mounted
volume (highlight the relevant line). Run a test program to generate endless disk metadata activity, e.g. repeatedly
create, rename and delete files. If this test program produces a lot of debugging output you don’t need to include that
in the screenshots.
5) Disconnect the disk while it is active. CAUTION: this may hang your system for a while, and may require a
reboot to recover.
6) Reconnect the disk. Run fsck to repair the filesystem (note, you may have to use fsck.ext2 specifically,
depending on your distribution, as it may attempt to fsck the disk as a FAT filesystem first). You should see at the
very least that the filesystem was “not cleanly unmounted.” If you’ve generated enough corruption from your
interrupted activity, you may see other errors as well. Answer “y” to allow repairs to take place. Now mount it and
see if any files have appeared in lost+found. Show all these commands and outputs. Umount the filesystem. We
are done with this first test.
7) Makeanew Linux EXT3 or EXT4 filesystem on the disk (overwriting the previous filesystem). Make sure
journalling IS enabled this time.
8) Mount the filesystem and perform your steps 4 and 5 again.
9) Reconnect the disk and attempt to mount it. Verify from the logs that the journal was recovered. Show (highlight)
the relevant lines of the dmesg logs relating to journal recovery.