MCS-378 Lab 3: Filesystem Locality, Fall 2000

Due: November 22, 2000

In this lab, your team will experimentally explore the performance implications of the ext2 filesystem's policy for choosing the location on disk of newly allocated inodes (files). The ext2 filesystem is linux's normal filesystem.

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)) {
The two branches of this conditional statement provide the two policies. You should read this part of the procedure to understand the two policies. (The rest of the procedure concerns other mechanical details that aren't relevant to this lab.) Note that a large chunk of the first branch of this conditional statement is commented out. Also, there are lots of grungy details that I don't want to stand between you and understanding the overall policies; be sure to ask me for help. In particular, the procedures le16_to_cpu and le32_to_cpu just return unchanged the number they are given; you can pretend they aren't even there. (They exist for the sake of running Linux on other processor architectures; the goal is to always store the bytes on disk in the same order, even though processors differ on the order they use internally.)

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. (Booting off the hard disk should have no other differences, but it is best to be sure.) I'm giving each group three floppies, all MS-DOS formatted. You can use two for the kernels and leave one MS-DOS formatted for transferring files. Note that you must make both kernel floppies before you do any performance measurement; you can't measure the unmodified kernel's performance first, before making the modified kernel. This is because we use the kernel source tree as a sample directory tree to copy in the performance measurement, so modifying the kernel source modifies the "benchmark" you are using for measurement.

  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 - src | tar Cxf /tmp -'
      This copies the directory tree /usr/src to /tmp/src, 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/src 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/src 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