27 Jul
2003
27 Jul
'03
4:10 p.m.
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:
[snip]
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 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