UCSD P-System: Why only 77 files per volume?

Question

What was the reason that the UCSD P-system filesystem was designed in such a way that it was limited to 77 files per volume?

Answer 1

There is some information on the internals under ucsdpsys_fs in http://ucsd-psystem-fs.sourceforge.net/ucsd-psystem-fs-1.22.pdf. Note, the default volume size was 140kb, i.e. one Apple floppy disk (see ucsdpsys_mkfs in the same PDF) which puts the "77 files and no subdirectories" limits into context.

Directory Format

Each directory entry is 26 bytes long. Thus, 78 directory entries fit into 2kB (4 blocks). The remaining bytes are zero padded. The first directory entry describes the directory itself, the remaining 77 entries are used for regular files.

ucsdpsys_text (in the same PDF) implies that the minimum size of a non-zero-length "text file" was 2kb, and hence 77 files would fill the default size file system.

Answer 2

What was the reason that the UCSD P-system filesystem was designed in such a way[...]

Quick Answer: Simplicity

Like with many early systems, it was all about making access easy by assuming certain structure.

---

The numbers are a result of the assumed default size entry size.

There's only one directory, no subdirectories and default size was to be 4 blocks of 512 bytes in length (2048 total). One entry has 26 bytes. Thus 78 entries are possible. The first describes the volume/directory itself, leaving 77 for other files.

The filesystem itself could have worked with longer directories (and subdirectories as well, there is an according type) but AFAIK it was never used on an Apple at least.

Now while the whole idea of the p-system was to provide a hardware-agnostic view of a virtual machine - not just the CPU, but disks (*1) and terminal I/O as well - selecting the default size of the directory might have been in fact hardware related. Leo B.'s Answer did remind me of the PDP-11 as eventually the first targets for the p-system, and the RX01 floppy system as disk.

The RX01 was single-sided with 26 sectors of 128 bytes each per track (and 77 tracks). With the 512 byte per block (*2) abstraction, always four 128 byte blocks (*3) must be blocked, resulting in six and a half blocks per track (*4). With the first two blocks fix reserved for any machine specific purpose/OS loader (*5), the directory starts with the third block. This only leaves 3 more full blocks that could be read without moving the head - something quite slow, thus less than desirable on directory operations.

So, while not strictly hardware related, deciding on 4 blocks for the directory was a sensible decision considering the RX01. As so often, a solution gets stuck with such shortcuts for quite a long time.

---

*1 - To facilitate this, the only high level requirement for disk storage was a block size of 512 bytes and the ability for consistent enumeration from high level, while any kind of physical placement and blocking/deblocking was done in hardware related drivers.

*2 - While block and sector are often used interchangeably, Pascal did use it on purpose to distinguish between physical sectors, which may or may not have 512 bytes, and its logical blocks which always had 512 bytes.

*3 - Unlike many users assumed, the Apple II p-system didn't use a its own disk format. Only the file system was different. It also offered the ability to create disks which are at the same time DOS and Pascal media - and eventually DOS,PASCAL, ProDOS and CP/M on a single flip disk. But that's a different story.

*4 - Yes, as result, not only block number to track/sector conversion was a bit weird, but also every 7th block was a slow read due to an intermediate track change.

*5 - This is done by convention. The first two blocks are (for most parts) ignored by the p-system. The only fixed structure is the first 26 bytes of the third block with the file system label - and the directory entries following.

In fact, since the volume begin is arbitrarily calculated by the hardware driver, it's more of a convenience function, as the hardware driver could add an arbitrary offset before the file system's first block. Heck, there was even a field within the volume header to support this.

Answer 3

There are a few basic ways a floppy-drive OS can handle directories:

1. Reserve a fixed amount of space in both RAM and on disk to hold them. This will make finding files fast, but will require that one reserve RAM to hold all the directory entries one may ever need.

2. Reserve a fixed amount of space on disk to hold them, but load them into RAM on demand. This will make things slower and more complicated, but one may be more willing to go an extra 2K or so of disk space than an extra 2K of RAM.

3. Allow directories to be arbitrarily placed on the disk. This will add even more complexity and make things even slower, but it will allow for directories of arbitrary size.

4. Require that directory blocks be stored sequentially at a fixed location, but allow the number of such blocks to vary as needed. This could work, but on a system where files must be stored sequentially, it would either be necessary to allocate directory slots from the opposite "end" of the disk from the files, require that user guess how many directory entries will be needed before placing the first file, or perhaps have every other physical track numbered 9-26, while the others are numbered from 8 down to 1 and 35 to 27 (so that directories allocated from tracks 35 downward would be located near files that are allocated from track 1 upward). Actually, I like that latter idea, but don't think anyone's ever done such a thing.

Limiting the number of directory entries makes things simpler and faster, provided there's no need to exceed the expected limits.

Answer 4

The UCSD P-system was originally developed on PDP-11, where the format of DEC RX 8-inch floppy drives had 77 cylinders (tracks) and 26 sectors per track. There are multiple ways to partition 2 Kb into directory entries, but the fact that the chosen number 77 for the directory entries matches the number of cylinders, indicates a probable attempt to simplify making most files cylinder-aligned for faster access.