Re: Windows 95 (VFAT) file systems?

Paul H. Hargrove (hargrove@sccm.Stanford.EDU)
Wed, 18 Oct 1995 18:39:45 -0700 (PDT)

As the author of the Mac (HFS) filesystem mcoding Linux, which is
still read-only, I thought I'd put in my $0.02.
In my case school has taken away the time I once had to work on HFS,
so the rate of development slowed significantly after the read-only
portion was done. However, in general the read-only FS is much easier
to implement than the writable version. This is especially true when
you are faced with incomplete documentation, such as the case with
HPFS (from IBM) and HFS (from Apple). If you don't know, for
instance, the legal range of some parameter you can write code that
deals with all values when reading, but what about writing? Do you
write a possibly illegal value and hope it works? It's sort of like
working on any mechanical device (such as a car) without a manual.
You may be able to take it apart (read) it with out a great deal of
understanding of how it was put together, but reassembling it (writing)
is much more difficult.
HFS (and also, I am told HPFS) is based on B-tree structures which
are great for efficient location of keys (= filenames or disk block
numbers) in a large database (=filesystem). The problems with
writablity come from concurrency. In the conventional "Unixy"
filesystems (xia, minix, ext, ext2) an update to a directory is
accomplished by obtaining exclusive access to the directory's inode
for the short period needed to update the directory, so any process
that runs while you wait on disk I/O or memory traffic to/from user
space is prevented from reading a partially completed update.
With B-trees all the "directory entries" are in one huge tree, which
is not organized according to the directory hierarchy. Thus a change
such as deleting or adding a file can necessitate changes at all
levels of the B-tree. As one moves up and down the tree structure
disk I/O is needed, which allows other processes to be scheduled. The
result is that I am trying (in a now greatly reduced amount of
available time) to produce a workable system of locks to allow
concurrent access (rather than using the "one giant mutex" approach)
that is deadlock-proof as well as "safe" and "live". The theory on
how this can/should be done is well established but oding it within
the structure of a Linux filesystem driver and Linux's semaphore ops
is not an entirely trivial task.
While this is just my example, I am sure that other read-only fs
authors have similar hurdles to surpass. As was said before,
certainly none of the read-only fs authors are trying to annoy anyone.
Paul H. Hargrove All material not otherwise attributed is the opinion of the author or a typo.