Subject: RE: Simplest (practical) file system?

From: "Dwight K. Elvey" <[email-masked]>
Date: Wed Jul 30 22:23:28 2003

>From: Joe <[email-masked]>
>
>At 11:18 AM 7/28/03 -0700, Patrick wrote:
>>> > 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. 
>
>
>   I wonder if it really would sap a lot of time. Modern IDE drives have
>large cache buffers so I would think that system could very likely read the
>data from the buffer. I'm thinking that as slow as these old systems are
>and as fast as the modern drives are that it would be better to use a
>simple and fast algorithim even if it means more drive accesses.
>
>   Joe
>

As I recall, Bob is looking to put this onto some old HP hardware.
Dwight

---

From: Bob Shannon <[email-masked]>
Date: Wed Jul 30 22:39:59 2003

Dwight K. Elvey wrote:

<snip>

>As I recall, Bob is looking to put this onto some old HP hardware.

Yes, I'm using old HP hardware, ranging from a 4 microsecond per 
instruction HP 2116 with 16K words
of core up to a sub-microsecond HP 2113 with half a megaword of 
high-perf RAM.  

For disks, I beleive its possible to support anything from a 2.5 meg 
7900 cartridge, up to a 300 meg CS/80
disk, or even my 8 gig ATA disk controller using an identical set of 
disk data structures.

In fact, very large physical devices would consist of an array of 
smaller identical subsystems, so larger devices
would appear to have subdirectories.

Its true that as the drive gets larger and larger, this approach will 
become more and more inefficient.  But its also
true that this becomes less and less important at a faster rate than the 
inefficiencies grow.  Add to this the fact that
a squeeze utility can reduce the performance inefficiencies to nearly 
zero as-needed.

So in strict terms of number of machine code instructions needed versus 
functionality provided, simple does seem to
imply a flat, linear, probably FAT-less file system.  From what I've 
read, this is not unlike a BFS partition, only I'm
thinking of something like an array of BFS's for large disks, and a 
single 'logical volume' for smaller ones, so all the
disk allocation parameters are constant.