File Systems

01 Lab overview

This lab contributes to U10.1 through U10.7, and to course learning outcomes CLO5 and CLO8.

02 Learning objectives

03 Background

3.1 The file abstraction

A file is a named, persistent sequence of bytes. The file system provides a small set of operations on files: create, open, read, write, lseek, close, unlink, and a few others. Everything else — buffering, blocking, caching, allocation — is the file system's responsibility. The abstraction hides the physical layout of storage: the application sees a linear array of bytes, and the file system maps that array onto disk sectors, possibly scattered across the device.

3.2 Inodes

An inode (index node) is the data structure that describes a file. It contains the file's metadata — owner, permissions, size, timestamps, link count — and the pointers to the file's data blocks. It does not contain the file's name: names are stored in directories, which map names to inode numbers. On ext4, the inode contains 15 block pointers: 12 direct pointers, one single-indirect pointer, one double-indirect pointer, and one triple-indirect pointer. With 4 KB blocks, this allows files up to about 4 TB in size.

3.3 Directory organisation

A directory is itself a file whose contents map names to inode numbers. In ext4, the directory is stored as a hash tree (htree), which makes lookup O(1) rather than O(n). In older systems (and in simple file systems like FAT), the directory is a linear list of entries and lookup is O(n). The directory file has its own inode, so it has metadata and (unlike a regular file) a size that reflects the length of the name-to-inode mapping.

3.4 File allocation

• Contiguous allocation. The file's blocks are consecutive on disk. Fast sequential access; simple to implement. Suffers from external fragmentation; growing a file may require moving it.
• Linked allocation. Each block contains a pointer to the next. No external fragmentation; files grow easily. Poor random access (a lookup requires traversing the chain), and a single corrupted pointer can truncate the file.
• Indexed allocation. An index block holds the addresses of the file's data blocks. Supports efficient random access and growth, at the cost of an extra block per file and a limit on the maximum file size (unless multi-level indices are used).

3.5 Journaling

A journaling file system writes metadata (and, optionally, data) to a log before applying the changes to the file system's structures. After a crash, the file system replays the log to bring the structures to a consistent state. The alternative — an fsck pass over the entire file system — can take hours on a large volume. The journal can record metadata only (fastest, but data may be lost while metadata is consistent), metadata plus data in ordered mode (data is written before metadata; the default in ext4), or metadata plus data in journal mode (slowest, but the strongest guarantee).

3.6 Modern file systems

Ext4 is a journaling file system with extents (runs of contiguous blocks), delayed allocation, and a hash-tree directory index. XFS is a high-performance journaling file system designed for large files and parallel I/O. Btrfs and ZFS are copy-on-write file systems with snapshots, checksums, and (for ZFS) pooled storage and RAID integration. The copy-on-write design writes new data to fresh blocks and atomically updates the tree, so it never overwrites live data — a crash leaves either the old tree or the new one, never a mix.

04 Guided activities

Activity 4.1 — Inspecting file metadata

1. Create the lab directory:

   mkdir -p ~/comp3150/lab9 && cd ~/comp3150/lab9

2. Create a small file and inspect it with stat, ls -li, and file. Record the inode number, size, mode, timestamps (atime, mtime, ctime), link count, and block count.
3. Create a hard link to the file with ln and a symbolic link with ln -s. Run stat on the original, the hard link, and the symbolic link. Explain why the hard link has the same inode number and the same link count while the symbolic link has a different inode and a small file size.
4. Remove the original file with rm. Check the contents of the hard link and the symbolic link. Explain the result: the hard link still has the data because its link count is now 1; the symbolic link is now dangling because it points to a name that no longer exists.
5. Use stat --format='%i %s %h %a %n' to print the inode number, size, link count, permissions, and name for a set of files. Automate the check for a directory tree.

Activity 4.2 — Reading inodes directly

1. Create a 32 MB ext4 image:

   dd if=/dev/zero of=fs.img bs=1M count=32
   mkfs.ext4 fs.img
   mkdir mnt
   sudo mount -o loop fs.img mnt

2. Create a file inside the mounted file system and fill it with a known pattern (for example, 1 MB of zeros). Record its inode number with ls -i.
3. Unmount the image and use debugfs -R "stat <inode>" fs.img to print the inode. Identify the direct, single-indirect, double-indirect, and triple-indirect pointers, and the block numbers they reference.
4. Use dumpe2fs -h fs.img to print the file system's superblock: block size, inode size, number of inodes, number of blocks, journal size, and features. Explain what each field means.
5. Use debugfs -R "blocks <inode>" fs.img to list the data blocks of the file. Confirm that a 1 MB file with 4 KB blocks uses 256 data blocks and (for a file that fits within the 12 direct pointers) no indirect blocks.
6. Create a file larger than 12 × 4 KB = 48 KB and repeat. Identify which indirect pointer is used and how many levels of indirection are required.

Activity 4.3 — Reading a directory

1. Write readdir.c that opens a directory and lists its entries. Use the system call getdents64 directly (via syscall(SYS_getdents64, ...)) rather than readdir(3), so that you see the raw on-disk directory format.
2. For each entry, print the inode number, the record length, the file type, and the name. The structure is struct linux_dirent64:

struct linux_dirent64 {
    ino64_t        d_ino;    /* inode number */
    off64_t        d_off;    /* offset to next dirent */
    unsigned short d_reclen; /* length of this record */
    unsigned char  d_type;   /* file type */
    char           d_name[]; /* filename, null-terminated */
};

3. Run the program on the directory /etc. Verify that the first two entries are . and .. and that the last entry is empty (a zero-length record marks the end of the buffer).
4. Compare the output of your program with ls -lai /etc. Every inode number should match.
5. Modify the program to print a histogram of file types (regular, directory, symbolic link, other). Explain the distribution you observe on /etc.

Activity 4.4 — File allocation simulator

1. Write alloc.c that simulates a disk with N blocks. It supports three allocation strategies, selectable by a flag: --contig, --linked, --indexed.
2. The simulator reads a trace of operations: create <name> <size>, read <name> <offset> <len>, append <name> <size>, delete <name>. It reports the number of disk accesses for each operation and, at the end, the total number of accesses and the external fragmentation (number of free blocks that are not adjacent to any allocated block, or the largest free run).
3. Run the same trace under all three strategies. Compare:
   • Number of accesses for a sequential read of a whole file.
   • Number of accesses for a random read of a single block.
   • Number of accesses to append to the end of a file.
   • Total external fragmentation after the workload.
4. Generate a workload that favours contiguous allocation (all files created at once, no deletions) and one that favours linked or indexed allocation (interleaved creations and deletions). Report which strategy wins on each.

Activity 4.5 — Journaling and crash consistency

1. Unmount the ext4 image from Activity 4.2 and inspect its journal with dumpe2fs. Record the journal size and location.
2. Remount the image with different journaling modes using the data= mount option:

   sudo mount -o loop,data=journal fs.img mnt
   sudo mount -o loop,data=ordered fs.img mnt   # default
   sudo mount -o loop,data=writeback fs.img mnt

3. Run a workload that creates and writes many small files. After the workload, use sync to flush, then unmount and check the journal's activity with debugfs -R "logdump" fs.img | head -100. Identify the descriptor blocks and the commit blocks.
4. Simulate a crash: while a write workload is running, kill the mount with sudo umount -f mnt (or power off the VM if permitted). Remount the image with mount -o loop fs.img mnt and run e2fsck -fn fs.img to verify that the file system is consistent. Explain what the journal replay did.
5. Repeat with data=writeback and explain why the metadata is consistent but the data may be lost — the writeback mode does not order data before metadata, so after a crash the file system may have a metadata entry for a file whose data blocks were never written.

05 Exercises

06 Deliverables

Submit a single archive named lab9-<lastname>-<studentnumber>.tar.gz containing:

• readdir.c — Activity 4.3.
• alloc.c — Activity 4.4 with all three allocation strategies.
• ext2_reader.c — Exercise 1.
• The Makefile with one target per program and a clean target.
• inodes.txt — the debugfs, dumpe2fs, and stat output for Activities 4.1 and 4.2, with your annotations.
• journal.txt — the logdump excerpt and e2fsck output for Activity 4.5.
• outputs.txt — the output logs of all programs with the commands that produced them.
• report.md (or report.pdf) — the lab report described below.

Lab report

The report should be 5–7 pages (excluding code) and contain:

1. Metadata and inodes. The stat output for the original, hard link, and symbolic link, with an explanation of each field and of the difference between the two link types.
2. Inode structure. The debugfs output for one inode, with the direct and indirect pointers annotated and the corresponding data blocks identified.
3. Directory format. A description of the linux_dirent64 records for one directory, with the inode numbers verified against ls.
4. Allocation comparison. The results from Activity 4.4, presented as a table with a row per strategy and a column per operation, and a discussion of which strategy is appropriate for which workload.
5. Journaling. The journal descriptor and commit blocks, the crash-recovery demonstration, and a discussion of the three data= modes.
6. Reflection. A discussion of how copy-on-write file systems (Btrfs, ZFS) avoid the consistency problem that journaling solves, and what trade-offs they introduce.

07 Grading rubric

Late submission penalty: 10% per day, up to a maximum of three days, after which the lab is accepted only with documented extenuating circumstances.

08 Knowledge check

09 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapters 13–15.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 39–43.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 4.
• McKusick, M. K., Joy, W. N., Leffler, S. J., & Fabry, R. S. A Fast File System for UNIX. ACM Transactions on Computer Systems, 1984.
• Rosenblum, M., & Ousterhout, J. K. The Design and Implementation of a Log-Structured File System. ACM Transactions on Computer Systems, 1992.
• Mathur, A., Cao, M., Bhattacharya, S., Dilger, A., Tomas, A., & Vivier, L. The New ext4 File System. Ottawa Linux Symposium, 2007.
• Linux man-pages: man 2 stat, man 2 open, man 2 readdir, man 5 proc, man 8 debugfs, man 8 dumpe2fs.