Skip to content

File System Interpretation (exp1)

In this exp, we will inspect filesystem images. We will reason about how filedata and metadata are stored and maintained.

Objectives

  • (primary) Reinforcing understanding of ext2
  • (secondary) Working with binary data structures

Roadmap

  • Understand the on-disk data format of the EXT2 file system. We will mount a provided image file on your own Linux system and explore it with familiar file navigation commands and debugfs(8).
  • Write a program to analyze the file system in that image file and output a summary to standard out (describing the super block, groups, free-lists, inodes, indirect blocks, and directories).

Prerequisites

git clone https://github.com/fxlin/p4-fs

Required environment

Fiddling with a whole filesystem (and disk images) requires the root privilege. So do this exp either on your Linux box, or Windows WSL2, for which you have root. WARNING: WSL1 is known to have issue with mount.

(Adventurous) You MAY try it inside a QEMU emulator on the server (e.g. granger1). The problem with QEMU: you will need a system image with all the utilities, e.g. dumpe2fs, etc. Can be built with buildroot which requires some exploration. So consider this as an unbeaten path. I'll be happy to learn if you pull it off.

Choice of programming languages

You can use any programming language (C/C++, Python, Java...).

C/C++ code can directly use the C header we provide to manipulate ext2 data structures; other programming languages will have to manipulate those bits per the C header.

DELIVERABLES:

A single tarball (.tar.gz) containing:

  • Your code, can be in any programming language (C/C++, Python, Java...).
  • If your code requires compilation, include a Makefile to build and run the deliverable program. The higher level targets should be:
  • default ... compile your program (with the -Wall and -Wextra options) to produce an executable
  • clean ... delete all programs and output generated by the Makefile.
  • If your code requires no compilation (e.g. written in Python), no Makefile is needed.
  • The name of executable must be fsdump, regardless of your language choice. Btw, a Python script can be made as a standalone executable (Google it).
  • A short README text file (NOT PDF) containing descriptions of each of the included files and any other information about your submission that you would like to bring to our attention (e.g., research, limitations, features, testing methodology).
  • You do NOT need to submit any CSV file

PROJECT DESCRIPTION:

Historically, file systems were almost always been implemented as part of the operating system, running in kernel mode. Kernel code is expensive to develop, difficult to test, and prone to catastrophic failures. Within the past 15 years or so, new developments have made it possible to implement file systems in user mode, improving maintainability, and in some cases delivering even better performance than could be achieved with kernel code. All of this project will be done as user-mode software.

To ensure data privacy and integrity, file system disks are generally protected from access by ordinary applications. Linux supports the creation, mounting, checking, and debugging of file systems stored in ordinary files. In this project, we will provide EXT2 file system images in ordinary files. Because they are in ordinary files (rather than protected disks) you can access/operate on those file system images with ordinary user mode code.

PART 1: Exploring an EXT2 Image

Follow the steps in here.

PART 2: Summarizing an EXT2 Image

In this step, you will write a program called fsdump that:

  • Reads a file system image, whose name is specified as a command line argument. For example, we may run your program with the above file system image using the a command like:

./fsdump EXT2_test.img

  • Analyzes the provided file system image and produces (to standard out) CSV summaries of what it finds. The contents of these CSV lines described below. Your program must output these files with exactly the same formats as shown below. We will use sort(1) and diff(1) to compare your csv output with ours, so the order of output lines does not matter, but a different format (even extra white space) will make your program fail the test.

  • You need to parse filesystem data structures using your own code. You CANNOT rely on existing ext2 libraries or tools (such as debugfs) and parse their output.

Even if you cannot mount the provided image file and run debugfs on departmental servers, your program should be able to run on departmental servers, because it does not require mount.

There are six types of output lines that your program should produce, each summarizing a different part of the file system. Remember, you can always check your program's output against debugfs's output. All the information required for the summary can be manually found and checked by using debugfs. This is described here.

We have also provided to you (for testing purposes) a much smaller image (trivial.img) as well as a correct output summary (trivial.csv).

superblock summary

A single new-line terminated line, comprised of eight comma-separated fields (with no white-space), summarizing the key file system parameters:

  1. SUPERBLOCK
  2. total number of blocks (decimal)
  3. total number of i-nodes (decimal)
  4. block size (in bytes, decimal)
  5. i-node size (in bytes, decimal)
  6. blocks per group (decimal)
  7. i-nodes per group (decimal)
  8. first non-reserved i-node (decimal)

group summary

Scan each of the groups in the file system. For each group, produce a new-line terminated line for each group, each comprised of nine comma-separated fields (with no white space), summarizing its contents.

  1. GROUP
  2. group number (decimal, starting from zero)
  3. total number of blocks in this group (decimal)
  4. total number of i-nodes in this group (decimal)
  5. number of free blocks (decimal)
  6. number of free i-nodes (decimal)
  7. block number of free block bitmap for this group (decimal)
  8. block number of free i-node bitmap for this group (decimal)
  9. block number of first block of i-nodes in this group (decimal)

NOTE: of a disk, block 0 is the boot block. Therefore, group 0 has 1 fewer block than any other groups. Example: group size is 64; group 0 spans block 1--63. You can verify this by dumpe2fs. Despite this, in your output for group 0, still output the actual group size, e.g. 64 in the above example.

free block entries

Scan the free block bitmap for each group. For each free block, produce a new-line terminated line, with two comma-separated fields (with no white space).

  1. BFREE
  2. number of the free block (decimal)

Take care to verify that you:

  1. understand whether 1 means "allocated" or "free".
  2. have correctly understood the block number to which the first bit corresponds.
  3. know how many blocks are in each group, and do not interpret more bits than there are blocks in the group.

free I-node entries

Scan the free I-node bitmap for each group. For each free I-node, produce a new-line terminated line, with two comma-separated fields (with no white space).

  1. IFREE
  2. number of the free I-node (decimal)

Take care to verify that you:

  1. understand whether 1 means "allocated" or "free".
  2. have correctly understood the I-node number to which the first bit corresponds.
  3. know how many I-nodes are in each group, and do not interpret more bits than there are I-nodes in the group.

I-node summary

Scan the I-nodes for each group. For each allocated (non-zero mode and non-zero link count) I-node, produce a new-line terminated line, with up to 27 comma-separated fields (with no white space). The first twelve fields are i-node attributes:

  1. INODE
  2. inode number (decimal)
  3. file type ('f' for file, 'd' for directory, 's' for symbolic link, '?" for anything else)
  4. mode (low order 12-bits, octal ... suggested format "%o")
  5. owner (decimal)
  6. group (decimal)
  7. link count (decimal)
  8. time of last I-node change (mm/dd/yy hh:mm:ss, GMT)
  9. modification time (mm/dd/yy hh:mm:ss, GMT)
  10. time of last access (mm/dd/yy hh:mm:ss, GMT)
  11. file size (decimal)
  12. number of (512 byte) blocks of disk space (decimal) taken up by this file

The number of blocks (field 12) should contain the same value as the i_blocks field of the I-node. There are a few interesting and non-obvious things about this number:

  1. This number is in units of 512 byte blocks, even if the file system block size is something else (e.g. 1024 or 4096 byte blocks).
  2. This number (times 512) may be smaller than the file size, as it includes only blocks that have actually been allocated to the file. A very large file might be sparse, in that some parts of the file may not have actually been written, and take up no disk space, but will read back as zeroes.
  3. This number (times 512) may be larger than the file size because it includes not only data blocks, but (single, double, and triple) indirect blocks that point to data blocks.

For ordinary files (type 'f') and directories (type 'd') the next fifteen fields are block addresses (decimal, 12 direct, one indirect, one double indirect, one triple indirect).

Timestamp format. Related functions: gmtime() and strftime(), both in <time.h>. If you notice there's an offset between yours and the sample dump: make sure you print time in GMT instead of local time such as GST.

Symbolic links. If the file length is less than the size of the block pointers (60 bytes) the file will contain zero data blocks, and the name (a text string) is stored in the space normally occupied by the block pointers (i.e. inline).

For an inline symbolic link:

  • field 13: print the first four bytes of the name as unsigned int (decimal).

  • no field 14 and beyond

  • Example line from trivial.csv: INODE,15,s,777,1028 ... 08/07/17 17:58:47,26,0,1886221359

  • If you run into some bug, make sure you get the byte order right (big endian vs. little endian)

Otherwise, a symbolic link actually occupies data block(s):

  • field 13 and beyond: only print the non-zero block addresses (unlike a normal file when you would print all 0s)
  • Aside: for some reason, the num of blocks (field 12) can be == the actual number of blocks + 1 (e.g. there's one non-zero block, and field 12 == 2). This is also the behavior of trivial.csv and debugfs. Just follow it.

While these rules may appear confusing, you will find examples in trivial.csv. Just make your output consistent with it!

directory entries

For each directory I-node, scan every data block. For each valid (non-zero I-node number) directory entry, produce a new-line terminated line, with seven comma-separated fields (no white space).

  1. DIRENT
  2. parent inode number (decimal) ... the I-node number of the directory that contains this entry
  3. logical byte offset (decimal) of this entry within the directory
  4. inode number of the referenced file (decimal)
  5. entry length (decimal)
  6. name length (decimal)
  7. name (string, surrounded by single-quotes). Don't worry about escaping, we promise there will be no single-quotes or commas in any of the file names.

indirect block references

The I-node summary contains a list of all 12 blocks, and the primary single, double, and triple indirect blocks. We also need to know about the blocks that are pointed to by those indirect blocks. For each I-node (file or directory), scan the single indirect blocks and (recursively) the double and triple indirect blocks. For each non-zero block pointer you find, produce a new-line terminated line with six comma-separated fields (no white space).

  1. INDIRECT
  2. I-node number of the owning file (decimal)
  3. (decimal) level of indirection for the block being scanned ... 1 for single indirect, 2 for double indirect, 3 for triple
  4. logical block offset (decimal) represented by the referenced block. If the referenced block is a data block, this is the logical block offset of that block within the file. If the referenced block is a single- or double-indirect block, this is the same as the logical offset of the first data block to which it refers.
  5. block number of the (1, 2, 3) indirect block being scanned (decimal) . . . not the highest level block (in the recursive scan), but the lower level block that contains the block reference reported by this entry.
  6. block number of the referenced block (decimal)

What is a logical block? Given a file, let us ignore the file's physical structure (where data is actually stored, indirect blocks, sparseness, etc) and view the data in the file as a (logical) stream of bytes. If the block size is 1K (1024 bytes):

  • bytes 0-1023 would be in logical block 0 of the file
  • bytes 1024-2047 would be in logical block 1 of the file
  • bytes 2048-3071 would be in logical block 2 of the file
  • ...

You can confirm your understanding of logical block numbers by looking at the INDIRECT entries in the sample output.

If an I-node contains a triple indirect block:

  • the triple indirect block number would be included in the INODE summary.
  • INDIRECT entries (with level 3) would be produced for each double indirect block pointed to by that triple indirect block.
  • INDIRECT entries (with level 2) would be produced for each indirect block pointed to by one of those double indirect blocks.
  • INDIRECT entries (with level 1) would be produced for each data block pointed to by one of those indirect blocks.

Sample Output

We have provided a very simple test file system image (trivial.img) as well as a correct output summary (trivial.csv) that you can download and test with. Your program should be able to generate (modulo line ordering) the same output.

Implementation strategy

Read through the entire document; do simple feature first; test often; backup code regularly. Have fun!