MCS-378 Lab 3: File Allocation, Fall 2009

Due: December 2, 2009

Primary Assignment

In this lab, you will experimentally determine how performance-critical the Linux kernel's choice of block groups is when creating new files and directories.

You should carry out Exploration Project 8.6 from the textbook (pages 320-321), except as modified below.

The book calls for making two versions of the kernel, one of which is unmodified and one of which spreads newly created files more uniformly. Conducting the experiment would require rebooting repeatedly, switching back and forth between the two kernels. Instead, you can use the same techniques as in the previous lab to conduct your experiments under a single kernel that has selectable behavior.

You should use the same statistical techniques as in the previous lab and write a report of the same kind.

You can decide whether you want to conduct your experiments in your main file system (which is partially full and has gone through a complicated history of having files created and deleted), or in a separate file system in another partition. If you use a separate file system, you can decide whether you want to use a freshly created empty file system or use some standardized but non-freshly-created file system contents of your devising. If you are using a non-empty filesystem (such as your main one), you can use debugfs's stat command to characterize the initial distribution of inodes and blocks among the block groups. Rather than deciding between a fresh file system and a used one, you could also consider conducting a comparison of the two.

Recent versions of ialloc.c have a bug in find_group_dir that runs some chance of causing one of your experimental runs to fail with a bogus "no space left" error. This arises from the use of a per-CPU approximation to the number of free inodes. If this affects your experimentation (or you want to be sure that it won't), you can apply the following patch: ialloc.patch. (This patch is for ext3; ext2 could be patched similarly if you choose to use it.)

Assuming that the use of find_group_dir makes your experimental workload run more slowly, you might also want to give some though to how you could determine whether the extra time is being spent within find_group_dir itself (taking longer to choose a block group) or instead is being spent on disk seeks (because the chosen block groups exhibit less locality).

Another possible variant on this primary assignment would be to use a find_group_X that you have written specifically to spread out inodes, rather than find_group_dir, which just happens to do a pretty good job of spreading out the inodes.

Alternative Assignment

If you prefer, you can do this instead of the primary assignment.

Produce a patch for fs/ext3/ialloc.c which corrects all the comments concerning how a block group is found. (That would be any comments either immediately preceding or within find_group_dir, find_group_orlov, and find_group_other, as well as the comment immediately preceding ext3_new_inode.) Your patch should also remove any useless code from the find_group procedures.

Instructor: Max Hailperin