Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watmath!clyde!rutgers!labrea!aurora!ames!lll-tis!lll-lcc!well!ewhac
From: ewhac@well.UUCP
Newsgroups: comp.sys.amiga
Subject: Some Filesystem Stuff I Cooked Up...
Message-ID: <4013@well.UUCP>
Date: Tue, 22-Sep-87 19:41:47 EDT
Article-I.D.: well.4013
Posted: Tue Sep 22 19:41:47 1987
Date-Received: Fri, 25-Sep-87 06:34:51 EDT
Reply-To: ewhac@well.UUCP (Leo 'Bols Ewhac' Schwab)
Distribution: world
Organization: Absolutely none.  I'm not kidding, either.
Lines: 138

[ Forget the lawyers and guns; just send the money. ]

	Some time back, I had delusions of writing a new dos.library.  To
that end, I cooked up the beginnings of a filesystem specification.  I've
since woken up from that dream, but I still have this slightly interesting
beginning for a filesystem base.

	Having nothing better to do (actually, I have to start on the Killer
Demo entry), I thought I'd throw it you people and see what you thought of
it so far.  There isn't much....

	Incidentally, I was going to call this fictitious DOS "LEOS" (Leo's
Excuse for an Operating System).

--------
/*  Block 0 of *ALL* mounted block devices.  */

struct DevRootBlock {
	ULONG	ID = 'LEOS';		/*  Not to be confused with 'DOS\0' */
	UWORD	NVolumes;		/*  # of volumes on this device */
	ULONG	VolumeKeys[NVolumes];	/*  Block #'s where each volume root
					    block (start of volume) is
					    located.  */
};

/*  Root block for each volume  */
struct VolRootBlock {
	ULONG	FADB;			/*  First Available Data Block
					    (absolute block number)  */
	ULONG	VolSize;		/*  In blocks  */
	ULONG	RootDir;		/*  Block # of root dir file  */
	ULONG	BitMapSize;		/*  # of blocks in volume's block
					    availability map.  Bit 31 ==
					    bitmap vaild flag  */
	char	VolName[64];		/*  Null terminated  */
	UWORD	HashTabSize;		/*  # of ULONGS in a directory's
					    hash table.  If NULL, directories
					    are searched linearly.  */
	UWORD	HashCodeSize;		/*  # of bytes in hash code routine */
	UBYTE	HashCode[HashCodeSize];	/*  Executable image of hashing
					    computation routine.  Must fit in
					    what's left of block size; must
					    be position-independent.  Passed
					    A0 pointing at null-terminated
					    string.  Returns index into hash
					    table (0 ... HashTabSize-1) in
					    D0.w.  Coded as subroutine.  */
};

/*
 * The above is the first "official" block in a given volume.  The next
 * BitMapSize blocks after that are (drum roll please) the bitmap blocks.
 * FADB points to (ideally) the block just after all the bitmap blocks.
 *
 * The block availability bitmap is formatted as follows:
 *
 * Bitmap is stored as an array of bytes.  Each bytes holds the status of
 * four blocks, represented by two bits.  The possible combinations are:
 *	00:	Free
 *	01:	Allocated
 *	10:	Bad block (format failed or something; avoid)
 *	11:	Invalid condition (used as consistency check)
 */

--------

	I never got around to formally laying down a directory
specification, but basically it was going to be a magic header, followed by
HashTabSize ULONGS of hash table, followed by individual directory entries
(filename, file size, protection bits, etc.).

	The way the directories would work is as follows:  LEOS would pass a
filename to the hashing routine.  It would return an index into the
directory's hash table.  LEOS would go and fetch the value in the table at
that index.  The value retrieved would be an absolute offset into the
directory file, which LEOS would then lseek() to get the file info.
Collisions would be handled much as they are now, except they'd be lseek()
pointers instead of block pointers.

Implications of the above
-------------------------

	Floppies would be able to have multiple volumes per disk, which may
or may not appeal to people (sounds kinda neat to me, though I'd never use
it myself).

	Directory listings would be perfectly quick, since directories are
now defined as files rather than gooey mish-mash.  'DIR'-type programs would
simply lseek() past the header and hash table, and start picking off
filenames.

	We would still retain the advantages (if any) of hashing filenames
when opening files.

	Hashing routines can be altered by the user or (more typically) by
the vendor on a per-volume basis.  Thus, if some vendor has a strange
application that would benefit from a hashing algorithm different from the
default, they could install that on their distribution disk, and it would be
totally invisible to the user.  The hashing function can be eliminated
altogether as well, saving space in the directory files.

	Currently, there is no way for the AmigaDOS to robustly handle bad
blocks.  This is especially bad with hard disks where the media can't be
swapped easily.  The new block bitmap specification would help to alleviate
this problem.  If LEOS detected a hard error, it could throw up a requestor
asking if the user wanted to mark the block as bad.  LEOS could then try to
recover as much of the data as possible, then mark the bad block in the
bitmap, and the user would never be bothered by it again.

Problems I Thought Of
---------------------

	Suppose we have a floppy that has multiple volumes on it.  What,
then, does DF0: refer to?  The raw block device?  The first volume on the
media?  This problem extends to hard drives as well (what does DH0: refer
to?)

	One possible solution is not to have any hardwired device
references.  This would quickly lead to people scratching their heads every
time they inserted a new disk ("What was this called again?").  Or they'd
name them all the same thing, which gets real interesting when they insert
two disks of the same name.

	So there should be some form of hardwired device reference.  But I
can't figure out a way to reconcile the multiple-volumes-per-device/what-
does-this-device-name-refer-to conflict off the top of my head.  Anyone got
a neat solution for this?

------------
	Oh well, there's my idea.  Do with it what you will.  Comments on it
are most welcome and encouraged.  How many wheels did I re-invent?  Will
this work nicely?  Or should I stick to display hacks?

_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
Leo L. Schwab -- The Guy in The Cape	ihnp4!ptsfa -\
 \_ -_	 Bike shrunk by popular demand,	      dual ---> !{well,unicom}!ewhac
O----^o	 But it's still the only way to fly.  hplabs / (pronounced "AE-wack")
"Work FOR?  I don't work FOR anybody!  I'm just having fun."  -- The Doctor