Why we need delayed allocation!

As those of you who have been following the BK repository of e2fsprogs
(or use Debian unstable, where I have been inflicting the Debian
unstable users with prerelease snapshots --- I should probably look into
doing the same with Fedora) might have noticed, I recently have included
into the distribution a program which uses the FIBMAP ioctl to analyze
files to determine how fragmented they are, as a tool to see how well
(or poorly) the file fragmentation avoidance algorithms in ext2 have
been working out.

When I ran the program on itself, I have surprised to find that it was
much more badly fragmented than I had expected:

# ./filefrag -v filefrag
Checking filefrag
Filesystem type is: ef53
Filesystem cylinder groups is approximately 15080
Blocksize of file filefrag is 4096
File size of filefrag is 34365 (9 blocks)
Discontinuity: Block 1 is at 1217290 (was 1217288)
Discontinuity: Block 2 is at 1217293 (was 1217290)
Discontinuity: Block 4 is at 1217291 (was 1217294)
Discontinuity: Block 6 is at 1217295 (was 1217292)
Discontinuity: Block 7 is at 1217289 (was 1217295)
Discontinuity: Block 8 is at 1217296 (was 1217289)
filefrag: 7 extents found, perfection would be 1 extent

This was true even when the block group in question had plenty of
contiguous free space.  A look at the inode via debugfs makes it very
clear what is going on:

Inode: 607065   Type: regular    Mode:  0755   Flags: 0x0   Generation: 
3543024981
User: 15806   Group: 15806   Size: 34365
File ACL: 0    Directory ACL: 0
Links: 1   Blockcount: 72
Fragment:  Address: 0    Number: 0    Size: 0
ctime: 0x3feaf8a0 -- Thu Dec 25 09:48:00 2003
atime: 0x3feaf8a8 -- Thu Dec 25 09:48:08 2003
mtime: 0x3feaf8a0 -- Thu Dec 25 09:48:00 2003
BLOCKS:
(0):1217288, (1):1217290, (2-3):1217293-1217294, (4-5):1217291-1217292, 
(6):1217295, (7):1217289, (8):1217296
TOTAL: 9

The problem is that when the linker is writing out the ELF executable,
it is doing so via apparently random seeks, probably because it is
writing out the various ELF sections in some order which is most
convenient for itself.  In particular, it appears than it wrote out the
9 4k blocks that comprise the filefrag executable in the following order:

        Blocks 0, 7, 1, 4, 5, 2, 3, 6, 8

So the filefrag executable is using 9 contiguous blocks starting at
1217288, but the order of those 9 blocks reflects the above write order.

Preallocation would have solved this problem somewhat, but it isn't a
perfect solution given much larger executables (such as Mozilla or
Evolution).  Something that would work much better would be to use
delayed allocation, where we don't actually try to determine the
placement of the blocks of a file until we are asked to write the page
from the page cache.  XFS in Irix does this, and it would probably
worthwhile for us to see if we can do something similar.

Comments?

                                                - Ted


-------------------------------------------------------
This SF.net email is sponsored by: IBM Linux Tutorials.
Become an expert in LINUX or just sharpen your skills.  Sign up for IBM's
Free Linux Tutorials.  Learn everything from the bash shell to sys admin.
Click now! http://ads.osdn.com/?ad_id=1278&alloc_id=3371&op=click