Simplest (practical) file system?

From: J.C. Wren <jcwren_at_jcwren.com>
Date: Sun Jul 27 23:10:01 2003

        There was always the OS-9 approach (IIRC), that used the last two bytes of
each sector to link to the next sector. Worked well enough, although not
dealing with even powers of two can be a pain.

        --John

On Sunday 27 July 2003 23:55 pm, Patrick Rigney wrote:
> > 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 - 23:10:01 BST