Description
Introduction
For Assignment 4, you are implementing the Very Simple File System. A file system dump utility is a
useful tool for file system developers, so in this tutorial exercise you will write one for an ext2 disk image.
You will also learn how to read the file system metadata structures in the file system image, without the
added complexity of running FUSE. You will also be able to explore the on-disk structures of a real-world
Linux file system.
You should be able to reuse some of the code you write for this exercise in your assignment, or reuse
some of your assignment code in this exercise (if you have already written it).
This tutorial exercise consists of three tasks, each of which requires you to print out some information
about the content of an ext2 file system in a disk image file.
You will need to obtain the starter files from MarkUs (click the ‘add to repository’ button after clicking the
T8 link).
Learning Outcomes
By the end of the tutorial exercise students will be able to:
use mmap to map a file into memory and use it like a data structure
recognize the global parameters to a file system
extract key parameters from a memory-mapped disk image
use xxd to locate and interpret data in a binary file
Companion videos
You should read through the tutorial handout carefully before watching the videos.
Tutorial walkthrough (https://web.microsoftstream.com/video/5f6b1a65-9951-48b8-811cf5e46d597e78)
Bitmaps (pdf) (https://q.utoronto.ca/courses/315157/files/27443807?wrap=1)
(https://q.utoronto.ca/courses/315157/files/27443807/download?download_frd=1)
Tutorial Video Slides (https://q.utoronto.ca/courses/315157/files/27443808?wrap=1)
(https://q.utoronto.ca/courses/315157/files/27443808/download?download_frd=1)
Requirements
You should not need to do a lot of extra reading to be able to carry out these exercises. The tutorial
notes and starter code should be sufficient. You may need to review bit manipulation operations in C.
You are given two files (and a Makefile) as starter code:
ext2.h
readimage.c
Note that readimage.c is not expected to compile before you write the code to complete the first task.
There are also several disk images available to you in /u/csc369h/fall/pub/tutorials/t8/diskimages on
teach.cs.toronto.edu
emptydisk.img: An empty virtual disk.
onefile.img: A single text file has been added to emptydisk.
largefile: A file larger than 13KB (13440 bytes) is in the root directory. This file requires the single
indirect block in the inode.
twolevel: 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 .
The rest of the disk images are for entertainment purposes, if you want to go beyond the requirements of
this tutorial. Your MarkUs repository also contains the expected output for the disk images that you are
expected to parse correctly, which you can use to check your work as you go.
Note that readimage uses mmap to map the disk image file into memory. The superblock is in the second
block on the disk starting at byte 1024, so we can interpret these bytes as the superblock struct.
You should also look at these bytes of one of the images, for example emptydisk.img by running xxd
emptydisk.img > emptydisk.txt and using an editor to view the contents of the file. Try the following:
Figure out where each block starts.
See what the inode bit map and block bitmaps look like.
Find other non-empty blocks to see if you can figure out what might be in them.
Task 1: Print block group descriptor fields
Add code to readimage.c to print out the following fields from the block group descriptor. When you run
./readimage emptydisk.img your output should look exactly like the following. In other words, we should
be able to use diff to compare your output to this and see that it is identical (the indentation below
uses 4 spaces). The print statements are given to you in the starter code, so this should be easy. The
Makefile also includes a tests rule (‘make tests’) that you can use to check your work.
Inodes: 32
Blocks: 128
Block group:
block bitmap: 3
inode bitmap: 4
inode table: 5
free blocks: 105
free inodes: 21
used_dirs: 2
Task 2: Print data block and inode bitmaps
The information from the previous task tells you where to find the data block bitmap and the inode
bitmap. It also tells you how many data blocks and inodes there are in the system. This is enough
information to print out the data block and inode bitmaps.
After you have completed this task, when you run ./readimage emptydisk.img you should see exactly the
following output. (Note that the block bitmap is one long line.)
Inodes: 32
Blocks: 128
Block group:
block bitmap: 3
inode bitmap: 4
inode table: 5
free blocks: 105
free inodes: 21
used_dirs: 2
Block bitmap: 11111111 11111111 11111100 00000000 00000000 00000000 00000000 00000000 00000000 00000
000 00000000 00000000 00000000 00000000 00000000 00000001
Inode bitmap: 11111111 11100000 00000000 00000000
Task 3: Print in-use inodes
The inode table is an array of inode structs. The block group descriptor tells you where the inode table is
found and how many inodes there are. Your task is to print out several values from the inodes that are
“in use”.
Note that in ext2, the inodes are indexed starting at 1, this means the inode number of the first inode
structure in the inode table is 1., e.g.:
vsfs inode table
+—+—+—+
| 0 | 1 | 2 | …
+—+—+—+
ext2 inode table
+—+—+—+
| 1 | 2 | 3 | …
+—+—+—+
The first 11 inodes are reserved. We are interested in the root inode (inode number 2, but it’s the inode
structure at index 1), but we will ignore the rest of the first 11 inodes. An inode is “in use” if its bit in the
inode bitmap has the value 1.
So, first print the root inode, and then print all inodes starting at index 11 if their bit in the inode bitmap is
1. (Hint: write a 2- or 3-line function that, given a pointer to the inode bitmap, and an inode index, returns
true if the bit at the given index is 1.)
The data you will print for each in-use inode is:
index
type: “d” for directory and “f” for file. (We aren’t considering any other types right now)
size in bytes
links count
blocks count (Note that the actual number of blocks is i_blocks/2 , because i_blocks stores the
number of 512 byte disk sectors rather than file system blocks)
the values of the pointers in the i_block array that are being used
If i_blocks is 6, only the first 3 pointers in the i_block array are valid.
To simplify your code you can assume that the largest file you need to worry about uses at most
the single indirect block, so if i_blocks is greater than 24, print the first 13 pointers.
After you have implemented this task, when you run ./readimage emptydisk.img you will get the following
output:
Inodes: 32
Blocks: 128
Block group:
block bitmap: 3
inode bitmap: 4
inode table: 5
free blocks: 105
free inodes: 21
used_dirs: 2
Block bitmap: 11111111 11111111 11111100 00000000 00000000 00000000 00000000 00000000 00000000 00000
000 00000000 00000000 00000000 00000000 00000000 00000001
Inode bitmap: 11111111 11100000 00000000 00000000
Inodes:
[2] type: d size: 1024 links: 3 blocks: 2
[2] Blocks: 9
You can see the expected output for two other disk images in your repository.
Submission
Make sure your files (at least readimage.c ) have been committed to your T8 MarkUs repo. Commit
changes locally and push readimage.c to your T8 MarkUs repo. We will use our own Makefile to test
your work.
