Simplest (practical) file system?

From: Patrick Rigney <patrick_at_evocative.com>
Date: Sun Jul 27 22:59:01 2003

> For a tree, the directory entry points to a block which is a list of all
> the allocation map blocks for that file. So the allocation map block list
> can point to up to 256 allocation map blocks, and each allocation map
> block can point to up to 256 blocks (2 bytes are used to store a block
> number).
>
> It's fairly sophisticated for an 8-bit operating system.

The thing I really don't like about this approach is that any file that uses
only a few allocation units still wastes an entire sector with a mostly
empty map block. If you look around on these disks, I'll bet you find a lot
of mostly-empty map blocks, which is just wasted space.

> > > Using one bit per byte (or word) you can store the status of
> up to 2048
> > > allocation units (sectors, blocks, whatever) in 256 (8-bit)
> bytes of disk
> > > space. So assuming your allocation units--let's call them
[snip]
>
> I still think it's a better and more efficient way to go, and not much
> more work to code than the simpler schemes being suggested.

I agree that it's simple, but not that it's efficient. For small micros,
finding the first "0" bit in an arbitrarily long bit string takes a few
cycles. Brute force approaches will bleed time badly as the filesystem
fills. And if you free a sparse or fragmented file in a large filesystem,
it can require resetting a lot of sparse bits in that map, which can in turn
require a lot of reads and writes to the map blocks.

If the file system is of any size (in terms of number of allocation units),
I think it's more efficient to keep the maps on some kind of linked list.
My bias would be to maintain a list very similar to the DOS FAT, with a
twist. File directory entries point to the first block a file owns, and
thereafter, the allocation list points the way to the next block, or flags
that there is no next block (end of file). This is like MS/PC-DOS. But
unlike DOS, the free blocks would be chained together in the allocation list
as well. In this way, you can quickly find a free block just by popping the
head block off the allocation list. You can also quickly delete a really
large file with a long chain of allocation units simply by setting its last
allocation block pointer to the head of the free list, then resetting the
head of the free list to the first block of the file being deleted--voila.

Patrick
Received on Sun Jul 27 2003 - 22:59:01 BST