MCS-378 Lab 3: Filesystem Locality, Fall 1999

Due: November 17, 1999

In general, it will improve performance if inodes that are commonly accessed in close succession are located near one another on disk. Because it is common to access multiple files in the same directory one after another, and in close proximity to accessing the directory itself, the ext2 filesystem normally tries to place inodes nearby to the parent directory's inode. In particular, it tries to place the new inode in the same block group as the parent directory's inode.

However, of this policy were always followed, even for (sub)directory inodes, it would try to bunch all the inodes in the whole filesystem in a single block group, which clearly isn't possible if the whole disk (consisting of multiple block groups) is going to be used. Some countervailing policy is clearly needed to spread the filesystem across the disk.

Therefore, the ext2 filesystem uses a different policy for placing a new inode if the new inode is for a (sub)directory. This alternative policy puts considerably greater emphasis on even spreading across the disk than on locality.

These policies are implemented in the ext2_new_inode procedure in the file /usr/src/linux/fs/ext2/ialloc.c. In particular, there is a conditional statement near the top of the procedure controlled by

if (S_ISDIR(mode)) {

There is almost zero programming to do in this lab and the basic experimental procedure is relatively simple and is spelled out for you (though you are invited to expand on it), so the key is going to be for your group to write a good lab report that reports what you observed and provides some interpretation of those observations.

1. The comment at the top of the procedure is apparently out of date, and doesn't correctly document the actual policies. Rewrite it to be correct.

2. Make a variant kernel (as in the prior lab) in which the policy normally used only for allocating directory inodes is instead always used. You should also make a normal, unmodified, kernel onto a boot floppy, so that you can do experimental comparisons between the two and be sure there are no other differences. (The boot floppy I gave you should have no other differences, but it is best to be sure.)

3. Now your goal is to compare the two kernels, both for performance (speed) and also to see directly that the inode placement is in fact different. The basic experimental procedure is as follows:
   1. Boot one of your kernels and log in, doing nothing extraneous.
   2. Time the benchmark by doing the command

      time sh -c 'tar Ccf /usr - lib | tar Cxf /tmp -'
      

      This copies the directory tree /usr/lib to /tmp/lib, by using the tar program twice: once to pack up all the files in the original directory, and then again to unpack them into the new directory. You should look for the elapsed time reported by the time command.
   3. Now measure the inode placement locality of the normal files and directories in the /tmp/lib directory tree. A separate web page explains how to do this.
   4. Record all your experimental findings somewhere other than on the experimental computer's hard disk, remove all temporary data files created in the course of the previous step (measuring placement locality), and then remove the /tmp/lib directory tree itself. That way the filesystem should be back the way it started.
   5. Now you can reboot again, using the same kernel or a different one, and start the procedure over from the top. You should do multiple trials with each of the kernels, ideally in a randomized order.

4. At this point, you have experimented with the impact on one simple benchmark of one simple change in filesystem policy. To more fully characterize how inode allocation affects performance, it would be desirable to try other benchmarks and/or other policy changes. Feel free to do any extensions of this kind, as time permits.

Instructor: Max Hailperin