Subject: Eli Heffrons on Hampshire Street, Cambridge,MA, USA

From: "Steve Jones" <[email-masked]>
Date: Sat Jul 26 20:57:50 2003

Bob Shannon wrote:
.
>  I've owned two, and serviced a great many back in the Eli Heffron days.

Yow! I drive by the site every now and again and shed a tear for
what was once a wonderful place to lose an afternoon. Back around
'89-91 I worked at MIT and Eli's was a prime source of parts for
labs with tight hardware budgets to repair/upgrade their ailing
MicroVAX II's and such.  

I remember wandering the shelves and seeing RX0n drive cabinets,
whole pdp-11/44's, and other goodies that I didn't do anything
about. What I did do was buy an SGI Iris 3130 with monitor -- nobody
seemed to know what it was, but I got it to boot. I believe I paid
$2k for that thing with 20" color monitor, and hauled it home in a
friend's car.

Fooled around with that for a couple months but something in the
monitor went, probably a flyback. I decided by that time that I
needed a Sun for a project I wanted to do when I returned to college
(anybody remember UCB's Sprite?), so I sold the thing with a dead
monitor for the same price. Who knows, maybe I could have gotten
more, the thing was loaded with bitplane and Geometry Engine
boards. But the weird System III derivative OS really put me off at
the time.

Manys the time I've wished I could go back in time and raid those
shelves, or browse through the tables of electronics parts...

--Steve.

---

From: evan <[email-masked]>
Date: Sun Jul 27 07:48:59 2003

http://www.eli.com/index.cfm?template=history

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:01:00 2003

What is the simplest usable disk file system to implement?

More specifically, if your going to write a disk file system from 
scratch, what would be the easiest way to implement
some basic file system functionality?

How did some of the very early DOS systems allocate disk space in the 
days before FAT tables, etc?

Just how simply can this be done?

---

From: Jim Battle <[email-masked]>
Date: Sun Jul 27 19:03:25 2003

> Just how simply can this be done?

The wang 2200 that I have (pre 1975) has two modes:

1) direct access.  the program and read or write any absolutely address 
sector, which is 256 bytes.  this isn't what you asked for.

2) random access tape.  the first N sectors of the disk contain a 
catalog of files on the disk.  an entry consists of 8 bytes of filename, 
two bytes of starting sector, two bytes of final sector (or is it size?) 
and an attribute byte (program/data).  it is quite primitive.  if you 
want to create a data file, you must first reserve all the space you 
will ever need for it.  unused parts of the file still take up space. 
if the file does grow bigger than you had already preallocated, you must 
basically shuffle files around on disk to make room.  when you delete a 
file, it just makes a hole in your map.  all sectors are allocated linearly.

it is very simple, but not too convenient.

---

From: "Patrick Rigney" <[email-masked]>
Date: Sun Jul 27 19:06:35 2003

> Just how simply can this be done?

Bob, pre-CP/M, the fairly popular North Star DOS filesystem simply used a
directory (first four blocks of the filesystem) with the name, starting
sector, number of sectors, and type for each file (16 bytes per entry).
Each file was laid out contiguously on the disk, starting at the sector
indicated and continuing for the set number of sectors.  There was no file
allocation table or similar structure.  It's lightweight and simple, but it
required you to know or "guess" the length of a new file when creating it.
You could specify a starting sector when creating a file, but if you didn't,
N*DOS would traverse the active directory entries to find the
highest-numbered used sector (start+length of each active file), then create
the new file at highest+1.  And "growing" a file was a leap of faith--if
there was free space after it (and you had to know), you could delete the
file, which modified only the directory (didn't touch the data blocks), and
immediately recreate it with a new increased length using the same starting
sector.  You could, of course, shrink a file using the same process.  An
included utility would compress "holes" out of the filesystem caused by
deleted or shrinking files.  --Patrick

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:08:11 2003

This sounds just about right, vintage-wise!

Ok, so once you have a hole, do you only recover that disk space by 
SQUEEZEing the disk?

I think RT-11 works this way, at least I recall the SQUEEZE command 
making the disk free space
larger.

Is a FAT needed for this, or is there a simple way to calculate this on 
the fly?

Jim Battle wrote:

> 1) direct access.  the program and read or write any absolutely 
> address sector, which is 256 bytes.  this isn't what you asked for.
>
> catalog of files on the disk.  an entry consists of 8 bytes of 
> filename, two bytes of starting sector, two bytes of final sector (or 
> is it size?) and an attribute byte (program/data).  it is quite 
> primitive.  if you want to create a data file, you must first reserve 
> all the space you will ever need for it.  unused parts of the file 
> still take up space. if the file does grow bigger than you had already 
> preallocated, you must basically shuffle files around on disk to make 
> room.  when you delete a file, it just makes a hole in your map.  all 
> sectors are allocated linearly.
>

---

From: ben franchuk <[email-masked]>
Date: Sun Jul 27 19:09:54 2003

> Just how simply can this be done?

Use the whole disk ... block by block ...  FIG FORTH worked this way.

---

From: "Patrick Rigney" <[email-masked]>
Date: Sun Jul 27 19:11:30 2003

Bob,

In "from scratch" projects I've done, I've always just implemented the
MS/PC-DOS FAT filesystem.  It's simple, and it has the advantage of being
readable and writable from any regular desktop PC directly.  I've also done
several variants of *nix filesystems, which are only slightly more complex,
but perform much better at the expense of a bit of RAM.  Naturally, if you
stick to the standards, you'll have no trouble reading, writing (and
verifying the correctness of) these volumes from Linux or FreeBSD.  I prefer
the former for floppies and other small-size removables, that latter for
hard disks.

Patrick

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]On
> Behalf Of Bob Shannon
> Sent: Sunday, July 27, 2003 10:14 AM
> To: [email-masked]
> Subject: Simplest (practical) file system?
>
>

---

From: Vintage Computer Festival <[email-masked]>
Date: Sun Jul 27 19:14:41 2003

> Just how simply can this be done?

One such way:

Have some portion of the disk set aside for a fixed number of directory
entries (the "directory").

Each directory entry has a certain number of characters for a filename (12
is good), a file type byte, a status byte, and a pointer to the portion of
the disk where the file is stored.

The file data is then stored on consecutive sectors, with the last one or
two words (depending on word size implemented) pointing to the next sector
of the file.  Zero values means "end of file".

There also needs to be a map somewhere specifying which sectors are
free/used.

This is basically how most early microcomputer DOS works.  I take my
example from Apple DOS 3.3.

Anything simpler would involve having files take up static areas of the
disk, perhaps defined by track boundries, with a fixed number of directory
entries (as defined by the total number of file areas) and a limited file
size (as defined by the size of each file area).

-- 

Sellam Ismail                                        Vintage Computer Festival
------------------------------------------------------------------------------
International Man of Intrigue and Danger                http://www.vintage.org

 * Old computing resources for business and academia at www.VintageTech.com *

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:17:00 2003

Just how much code does this take, and where can I find source?

---

From: [email-masked] (Tony Duell)
Date: Sun Jul 27 19:21:45 2003

> I think RT-11 works this way, at least I recall the SQUEEZE command 

Yep.

> making the disk free space

The HP LIF disk format works like this too.

> Is a FAT needed for this, or is there a simple way to calculate this on 

The LIF directory just stores the starting block and length for each 
file. The directory is also stored in ascending order, so from the 
staring blocks of 2 adjacent files in the directory, and the length of 
the first one, you can work out if there's any space between them, and 
how big that space is.

When a file is deleted, its directory entry is changed to indicate that 
the file no longer exists, If a shorter file is then stored on the disk, 
then the directory entry is changed again for the new file. THis then 
leaves some unused blocks on the disk which can't be used becuase there's 
no way to create a directory entry in the right place in the directory.

-tony

---

From: Fred Cisin <[email-masked]>
Date: Sun Jul 27 19:25:01 2003

> some basic file system functionality?

What size drive?  You might want something different for an 80G drive than
for a 100K floppy

> days before FAT tables, etc?

I thought that you said that you wanted PRACTICAL

> Just how simply can this be done?

It is unusual for somebody to set out to write a file system who isn't
already familiar with what's been done before.  (some say that UCSD P
system was the last time that one was written by people who had no idea
what they were doing)

Do you WANT it to be compatible with anything else?
If NOT, then you will also have to write conversion software.  Maybe not
now, but someday.

Greatest compatibility would be to implement the MS-DOS structure.  To
make it simple, you can wait and add sub-directory support later (like MS
did with 2.00)

But if you want to roll your own from scratch, . . .
Your drive head will spend more time in the DIRectory than anywhere else.
(Yes, it could be cached in RAM, but remember the fiasco that resulted in
having to release MS-DOS 6.2x!)

Does your drive have a track 0 switch?  If so, then that's where you
oughta put the DIRectory. (CP/M (after reserved track(s)), MS-DOS, MAC
400/800K, etc.)  If not, then consider mid-disk. (TRS-DOS, Coco, MS
Stand-alone BASIC (NEC-DOS, etc.), OS/2 HPFS, etc.)
Putting the DIRectory at the beginning of the usable space simplifies a
few things.

Decide how large an allocation unit you want.  Large ones make for fewer
to keep track of, with possible performance benefits, but wast more space
if you use a lot of tiny files.  You COULD use blocks that are SMALLER
than a sector (128 bytes, ...); but you said simple.

Decide the DIR structure.
Fixed size for each FPDE (File Primary Directory Entry) avoids some
unnecessary hassles.
Filenames shorter than 8.3 are too short.
Long filenames make for a much more complex DIR structure.
(NOTE: Windoze does NOT have long filenames.  It has 8.3 filenames, PLUS a
file can also have a "nickname" that is NOT stored in that file's FPDE
(MS stores the nicknames in the space that would otherwise have held
FPDEs, but does NOT store it as an FPDE))

UCSD P system stores starting and ending block numbers, and can not have a
non-contiguous file.

CP/M stores a list of block numbers, and when that overflows the space
provided in the FPDE, an additional directory enty is needed for the file.

TRS-DOS stores a short list of starting points plus length for each
starting point.

Apple-DOS stores starting point, and then each file contains IN THE FILE'S
SPACE, pointers to the next space. Thus forming a linked list of sectors,
but giving you 254? bytes of data in each 256 byte sector.

MS Stand-Alone BASIC, MS-DOS, and MAC 400K/800K use a linked list of block
numbers stored in a separate section of the DIR.
(MAC 400k/800k uses the same structure as MS-DOS, with just enough changes
to not be interchangeable.  (serious shortage of systems programmers in
those days))

If you want full functionality, then nothing is going to be significantly
less work to implement than MS-DOS, which would give you disk
interchangeability.

---

From: Fred Cisin <[email-masked]>
Date: Sun Jul 27 19:26:40 2003

> Just how much code does this take, and where can I find source?

MS-DOS 1.0 needed 16K of RAM.

Full description, but NOT source code, is in the appendix of the MS/PC-DOS
manuals from 1.0 - 2.00.  After that, there was an appendectomy, and the
appendix (still with "appendix #" page numbers) was sold separately as the
DOS Technical Reference Manual.

Are you using an 8086 family processor?

There are a number of commercially available packages with source for an
OS, such as Caldera Open-DOS (formerly DR-DOS, formerly CCP/M, etc.)

Now, WHAT are you trying to do?

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:28:16 2003

> Use the whole disk ... block by block ...  FIG FORTH worked this way.
Very tempting, as I'm adding a file system to a threaded interpreter 
(not FORTH).

But a basic block system is just too primative.  Named files at a minimum.

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:29:51 2003

>of the file.  Zero values means "end of file".

If you have a pointer to form a linked list, why use consecutive sectors?

>There also needs to be a map somewhere specifying which sectors are

Now things are getting complicated!  This one component adds a major 
design decision I'd rather
aviod, how to allocate unused sectors (linear versus first-fit).

>size (as defined by the size of each file area).
This latter approach is more like what I'm thinking of.

Either fix the file size at creation time, or even simpler, set all 
files to some lenght, and longer files can be
implemented (later?) as a linear set of files, a file and its 
extensions.  Maybe allocate 64 kbytes to each
file 'slot'.

New files always get allocated at the end, as in the Northstar DOS 
example Patrick Rigney described.

The trick then becomes how to efficiently 'squeeze' the disk drive to 
recover space from deleted files?

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:31:27 2003

>Now, WHAT are you trying to do?
Err, well, ok.

I'm adding a file system to a custom programming language and operating 
system combination.

The CPU is an HP minicomputer, ranging from 2116's up through the 21MX 
machines.

Disk drives may range from the HP 7900A to CS/80 drives, as well as a 
custom ATA disk controller
for HP 1000's.  So disk sizes range from 5 mb per physical volume to 8 
gb (or more) for the ATA disk.

Media interchangability is not a factor.

Basically a friend of mine and I, with some additional help, have 
written a threaded interpreter for HP 1000's
that is designed to be a tool for bootstrapping and restoring any HP CPU 
from a 4K 2114 up to a E of F series
with a full megaword of memory.

We already have a sort of 'linear' file system for 7970-series mag tape, 
and are now working to add a file
system to this beast.  SIMH recently added (buggy) HP 7900 disk 
emulation, and in real-hardware land we have
working CS-80 and ATA disk subsystems with working low-level code.  So 
the trick is to write a layer between
the threaded engine and the low level disk driver code.

Having looked at several modern file systems, we can see where a lot of 
complexity comes from.  But the machines
we are writing code for predate these file systems by a decade or more. 
 So these approaches don't seem to be a
good fit at all.

Something more along the lines of the Northstar DOS system looks more 
attractive.  We are looking for a 1960's to
1970's sort of approach, only with reasonable file name sizes. 
 Subdirectories are not mandatory if we can have several
named logical units on a large physical drive (like the ATA controller).

---

From: [email-masked] (Sean 'Captain Napalm' Conner)
Date: Sun Jul 27 19:35:25 2003

It was thus said that the Great Bob Shannon once stated:
> Either fix the file size at creation time, or even simpler, set all files to
> some lenght, and longer files can be implemented (later?) as a linear set of
> files, a file and its extensions.  Maybe allocate 64 kbytes to each file
> 'slot'.

  Make the slots too big, and you limit the number of files available and
waste much of the space on the disk.  Too small, and you have overflow (file
is too big for a slot).  

  Fast, efficient (disk space usage), easy (to implement):  pick any two 8-)

  I have come up with a system that is easy to implement, is quite efficient
of disk space, but don't bother with measuring the speed because it will be
S-L-O-W ... if you want fast and efficient, then possibly a B-tree or B-*
disk format would be the way to go, but then that's not too easy to
implement.  Using a file per track is fast and easy, but doesn't use space
efficiently.

  It also depends upon the size of the disk you are going to use---up to a
few meg in size the MS-DOS FAT system (12 or 16 bit variants) will probably
be the best bet---well documented with the ability for interoperability
between most systems.

  -spc (my two bits worth ... )

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:38:20 2003

Fred Cisin wrote:

<snip>

>I thought that you said that you wanted PRACTICAL

Yes, practical, like RT-11 was (is).

Remember this is a file system for vintage hardware (well, including 
vintage hardware with a ATA disk hack).

>system was the last time that one was written by people who had no idea
Its unusual for anyone to try to write a file system without a lot of 
modern fluff added too.

>If NOT, then you will also have to write conversion software.  Maybe not
Actually, in this case, we already have ways to exchange data with 
conventional machines.  We can support
a vintage HP CPU hung off a serial port, as a parasite to a PC host 
machine, or a stand-alone system that
cold boots from its own disk drive for HP's in collections with working 
peripherals.

>Putting the DIRectory at the beginning of the usable space simplifies a
Not an option for actual HP hardware.  HP's cold-boot roms load an 
intermediate loader program from
track 0, and this intermediate loader (like MS-DOS's) then loads the O/S 
into memory.  So to be compatible
with HP's cold boot mechanisim track 0 holds the start of the intrim loader.

>than a sector (128 bytes, ...); but you said simple.
Right, because of the way HP21MX machines page VM, and all HP1000's see 
memory, we are allocating
units of 1024 16-bit words.  In fact, the ATA disk controller reads, 
writes, and addresses its 8 gb disk as an
array of 1024 16-bit words.

>Fixed size for each FPDE (File Primary Directory Entry) avoids some
Yep, probably 32K words, given the vintage of the machines and their 
maximum logical memory capacity.

>Long filenames make for a much more complex DIR structure.
Yep, we are also placing file pointers for each file in the directory 
entry, so we can 'reopen' files from their
last point of access, or 'open' them from the start.  One of the reasons 
behind this hack is that we are limited
to only 2 file buffers in memory (unless the file system becamse HP 21MX 
specific).  We plan to keep this
open to the 2116 and 2100A/S machines as well.

>UCSD P system stores starting and ending block numbers, and can not have a
This is actually a feature for HP machines.  Some disk systems MUST use 
DMA transfers, and DMA transfers
to and from the disk must be made to linear disk blocks.  Nonlinear 
files add a lot of complexity.

>provided in the FPDE, an additional directory enty is needed for the file.
So CP/M files are non-linear?  Or can be non-linear?  Then again, the 
BDOS is like 6K, right?

>less work to implement than MS-DOS, which would give you disk
Define full functionality?

RT-11 works just fine, and it does not have the level of 'fluff' found 
in many modern file systems.

---

From: "Patrick Rigney" <[email-masked]>
Date: Sun Jul 27 19:43:08 2003

Bob,

Here's a public domain implementation...
http://www.alumni.caltech.edu/~pje/rdcf2.txt

Patrick

> Sent: Sunday, July 27, 2003 12:29 PM
> Subject: Re: Simplest (practical) file system?
>
>

---

From: Fred Cisin <[email-masked]>
Date: Sun Jul 27 19:44:43 2003

> Its unusual for anyone to try to write a file system without a lot of

That was what Jobs intended for the Lisa.  backfired.

> with HP's cold boot mechanisim track 0 holds the start of the intrim loader.

Of course it is an option.  IFF you want.  "Beginning of usable space"
would mean immediately following whatever fixed location stuff there is.
MS-DOS and MAC DIR follows the boot record.
DEC Rainbow MS-DOS follows a "boot track"

> maximum logical memory capacity.

This is fixed size for the directory ENTRY, NOT file allocation.  Some
systems, mostly in order to accomodate long filenames, use a variably
sized entry in the directory.

> in many modern file systems.

Then it sounds like the decision is made!

---

From: Vintage Computer Festival <[email-masked]>
Date: Sun Jul 27 19:46:19 2003

> but giving you 254? bytes of data in each 256 byte sector.

In Apple ProDOS, the file entry in the directory points to either the
first block of the file (if the file is only one block in length) or a
block that contains a list of all the blocks the file uses.  This is still
simple but elegant.

--

---

From: Vintage Computer Festival <[email-masked]>
Date: Sun Jul 27 19:47:54 2003

> If you have a pointer to form a linked list, why use consecutive sectors?

I didn't mean that.  The sectors can be in any order on any part of the
disk.

> aviod, how to allocate unused sectors (linear versus first-fit).

That's not complicated at all.  You just named two of several choices:
linear or first-fit.  Linear is the simplest.  Just start at the beginning
of the map and find the first free sector and use it, then repeat.  When
the disk is new, there will be lots of large blocks of open space.  As the
disk gets used over time, with files enlarged, shrunk, deleted and added,
files will be all over the place.  You then write a utility to
re-organize the disk for better performance.

First-fit only adds a little bit of logic to the code to allocate space.
An easy algorithm would be to find the largest block of contiguous space
in the map to fit the file you are saving.  If none exists, use the
largest contiguous space to store the first part of the file, then repeat
until the file is saved.  This is not a lot of programming.

> This latter approach is more like what I'm thinking of.

Boring.

> recover space from deleted files?

This is your trade off.  You can spend the programming time doing a more
proper filesystem ;)

--

---

From: Bob Shannon <[email-masked]>
Date: Sun Jul 27 19:50:01 2003

<snip>

>This is your trade off.  You can spend the programming time doing a more
It all comes down to available memory.

We are talking about CPU's with a logical address space of 32K words. 
 Much of that is already used, so I need
something very small.

And how 'correct' would it be to have a modern file system running on an 
HP2116 anyway?  It may be far from
practical.

---

From: "Patrick Rigney" <[email-masked]>
Date: Sun Jul 27 19:53:12 2003

> block that contains a list of all the blocks the file uses.  This is still

Is the file size limited to the number of blocks that can be represented in
a single map block, or does it allow multiple map blocks?  If the latter,
how does it chain them?  --Patrick

---

From: "Patrick Rigney" <[email-masked]>
Date: Sun Jul 27 19:58:01 2003

> Just how much code does this take, and where can I find source?

Bob, I looked in my archives, and I've got a much older implementation of
the library referenced in my earlier posting that does not support directory
structure, just flat filesystem--saves a lot.  I'll send that under separate
cover.  --Patrick

---

From: Vintage Computer Festival <[email-masked]>
Date: Wed Jul 30 20:26:01 2003

> how does it chain them?  --Patrick

It allows multiple map blocks.  The directory entry indicates what type of
file it is.  The smallest is a seed (points to the file's single block),
then a sapling (points to the file's block allocation map), then a tree
(points to the file's block allocation map block list).  This is from
memory so the seed/sapling/tree designation may be wrong, but that's the
gist of it.  I think this scheme allows for a file of up to 32MB in size.

BTW: a block in ProDOS is 512 bytes (2 256-byte sectors).

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.

--

---

From: Vintage Computer Festival <[email-masked]>
Date: Wed Jul 30 20:43:00 2003

>  Much of that is already used, so I need

Apple ][ DOS 3.3, a simple but complete disk operating system, is
implemented inside of 10,752 bytes.

> HP2116 anyway?  It may be far from

It depends on how useful/usable you want it to be.

--

---

From: ben franchuk <[email-masked]>
Date: Wed Jul 30 20:46:00 2003

Lets not forget the old machines too often had fixed data areas on media 
used as scratch storage. A single page of memory often was the only room
a OS could use for all device handeling and bootstrapping. You often had 
to have a system that could load a paper tape image in core memory all 
ready and then work from disk or mag tape. A fixed file size is not a 
problem since only with text editing do you need a variable file size.

---

From: Jim Battle <[email-masked]>
Date: Wed Jul 30 21:19:02 2003

> Ok, so once you have a hole, do you only recover that disk space by 

yes, although the OS supplied command that does this can't do an 
in-place squeeze.  the command is MOVE, and it copies the first disk to 
the second disk while removing any SCRATCH'd files along the way.  I'm 
sure people did write their own in-place squeeze programs, but it would 
be inherently hazardous.  Because the file system doesn't have a linked 
list or indirection table of some kind, you can't incrementally move 
around pieces of the file safely.  You have to atomically move the 
entire program and update the catalog.  So the build in command, MOVE, 
required the squeeze to happen during a whole-disk copy so that the 
integrity of the source disk was never compromised.

---

From: Jdavis <[email-masked]>
Date: Wed Jul 30 21:27:07 2003

<snip>
Trying to insult as many as possible before I commit suicide.
Jim D.