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.
You would just look for the first byte that is not a 255.
That's absolutely true, you can do that, and from there it's fairly
straightforward. But here's what I'm thinking. Let's say you have just a
1.44MB floppy, with a 512 byte sector size. A convenient allocation size
might be one sector, because you can easily fit the total number of
allocation units (2880) into a 16-bit unsigned integer (that which is used
in the file link blocks). That takes about 360 bytes to store on disk,
which fits nicely into a single sector as well. So far, so good.
But now let's say you go to an 80MB partition with 512 byte sectors. You
then have approximately 163,840 allocation units (not discounting any space
used for boot and other common structures). That's too many for a 16-bit
word, so you decide to make your allocation units four sectors. That means
you have 40,960 allocation units, each of which is 2K in size. Your
free-space bitmap, then, would be 5,120 bytes, which takes 10 sectors or 3
allocation units to store depending on your implementation choices, but
let's just go with the smaller 10-sector size.
I'm thinking about two things: first, trying to keep the entire volume
bitmap in memory chews up almost 5K of RAM, and that's probably not good for
an 8-bit machine, at least, it's not sufficiently memory-efficient, IMO.
Second, if you decide then that you'll only deal with one sector of it at a
time to save RAM, you may have to read-then-write juggle those ten sectors a
lot. If you do a linear search for a free block, it may be that you can rip
through the 255-valued bytes quickly, but they have to be in RAM, so you may
have to do several reads to find what you want, which saps time. You can,
of course, keep a pointer to where the last non-255 byte was in the map, so
your searches don't have to be linear from the beginning. But there's still
the issue of deleting a very sparse file, or allocating when the free space
is badly fragmented, so the zero-bits are spread out widely.
While the implementation of a linked list for the 80MB example would require
a 81,920 byte list (160 sectors), that map implements both the free list and
the allocated file chains, so the total space used by both structures may be
less than that consumed by the sum of leaf/sapling/tree indirect map blocks
alone once the disk starts to fill up (say, you had more than 160 or more
files on disk, each large enough--bigger than just one sector?--that it
requires at least one map block in addition to its data blocks). And access
to a free block is direct in the linked list--no search. The upper boundary
of size of any one file is the size of the disk itself, which is nice, and
if you made the simple design choices that an allocation unit can be 255
sectors maximum, and number of allocation units must be 65,520 or less
(reserving a couple of values for flags in the map like bad block), the
maximum partition size would be nearly 8GB on 512 byte sectors, which I
think is acceptable for implementation on a vintage system.
What doesn't work so well in this implementation is a lot of jumping around
inside a file, which may require many repeated trips down the file's
allocation chain, in which case that tree is a much better structure.
That tree structure, incidently, is also very close to the original *nix
filesystem.
That's what I was considering, and certainly, as someone else said in this
thread, performance is one of the tradeoffs that can be made to implement
that "simplest" requirement of the Bob's. I just love thinking about this
stuff, though. :-) Thanks for the lively discussion, and for the education
on ProDOS. Do you have a good pointer to more details on line? I just
picked up a IIe... :-)
Patrick
