unlink is not forever

[Dave Martindale]

In article <1220 at burl.UUCP> rcj at burl.UUCP (Curtis Jackson) writes:
>Why the kernel designers didn't put newly-freed blocks at the END of the
>freelist I'll never know.

The only "optimization" of the layout of blocks on the disk is done via
the free list.  When you build a free list (via mkfs) or rebuild it
(via icheck -s), the free list is built one cylinder after another,
with blocks within one cylinder being spaced every N sectors, subject
of course to which blocks were actually free in any given cylinder.

Then, when you allocate a large file, you get blocks in the order they
are in the free list, which is "optimum".  When you delete the file,
the are put back onto the head of the free list in reverse order, thus
doing the lest "scrambling" of the list.

This algorithm also has the property of "growing" the filesystem slowly
towards larger cylinders as the space required increases - if you have
a large filesystem that has grown from 0% full to 50% full, the latter
half of the cylinders will have never been used for files, thus
reducing seek times.  Putting newly-freed block on the END of the
freelist would guarantee that a filesystem with few files would have
them spread all over the allocated area.  Worse yet, blocks of
individual files would also be spread like this.

Of course, if you are running a system that tends to have more than one
program writing at the same time, and where filesystems are always
above 90% full, the free list is thoroughly scrambled anyway.  But for
a system that had one or a few active users, and small slow disks, it
makes a great deal of sense.

I used to have a "grabfree" program to snatch blocks from the free
list, written many years ago after someone (probably me) rm'ed an
important file.  I used it every once in a while (until 4.2BSD).

But now I'm used to working on machines that have an automatic backup
daemon that backs up changing files once every hour.  So I don't have
as much to lose.

	Dave Martindale