10

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?

  • 2
    If you can find a copy, chapter 2 of the UCSD Technical Reference IV has some code showing the packed records for files and directories. 77 is an interesting enough number that I bet it has to do with that number or size of such structures in another packed structure. – user12 Feb 15 at 14:49
  • 2
    This was a common problem. My first computer (Altos 586 running MP/M-86) had a 1024 file limit for a 20 Meg. hard drive. Way too restricting. So I poked around and figured out how to patch MP/M-86 for 2048 files - not an official patch but changing some of the assembly language drivers (all, fortunately, included in those days), which let me effectively use the entire hard drive. A bit risky of course - I could have ended up with any number of crazy problems if I got it wrong, but it worked. – manassehkatz Feb 15 at 15:49
15

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.

9

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.

  • And why exactly "default size was to be 4 blocks of 512 bytes", if the file system was developed for a floppy with block size 128 or 256? – Leo B. Feb 15 at 19:45
  • @LeoB. The file system was designed to be hardware agnostic - that's the whole point of the p-system, creating an environment that can be implemented on any machine available to the university and provide a cnsistent unified interface. This starts with organizing all block media in units of 512 bytes. – Raffzahn Feb 18 at 14:22
  • My question focused not on "of 512 bytes" but rather "4 blocks". What good does that hardware agnosticism do if it doesn't allow a variable number of files depending on media capacity? – Leo B. Feb 18 at 18:40
  • @LeoB. Erm, you are somehow mixing up blocks and sectors. The p-system works on blocks (of 512) bytes. The file system was not made to work on 128 or 256 byte sectors. It was made to work on 512 byte blocks. That's the abstraction layer used to work on any kind of disk, no matter if 128 or 2048 byte sectors are used, the file system doesn't care about them It only works with blocks. The whole idea was to make a system that can be implemented on all systems available at the university, not just PDP-11 and RX01. – Raffzahn Feb 18 at 19:14
  • @LeoB. In addition, there was a pointer (to the first usable data block after what was reserved for the directory. Meant to reserve space for directories of arbitrary length. So while complaining that none (of the common implementation) is legal, it doesn't make much sense. If at all, the file system was developed toward subdirectories. – Raffzahn Feb 18 at 19:19
2

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.

  • That's guessing, right?. For one, it was 78 entries, but more important, it justt adds up the way the directory entries are layed out. Keep in mind, they are made the Pascal way, so not really caring about the underlaying structure. – Raffzahn Feb 15 at 19:34
  • @Raffzahn The directory structure doesn't fill the whole first track, so the remaining 77 entries for files allow each of the files to start on a separate track. Other explanations lack the rationale for limiting the directory size at 2 kb. – Leo B. Feb 15 at 19:40
  • 1
    I don't se no rational in using the track number here in any way (BTW it's 78 entries). An RX01 track had 26 128 byte sectors. So that's not 2 KiB either. The p-System manages disks as logic blocks of 512 byte - a RX01 track would be 6 1/2 blocks. Using that as an assignment value makes again no sense. Even worse, only every 8th track is aligned to a 2 KiB boundry. Also, there is no other 2 Kib structure used. Last but maybe most important, the p-system was meant to be device agnostic. So why on earth would they then deeply encode a specific drive here? Bottom line: Pure conincidence. – Raffzahn Feb 15 at 20:08
  • Now, when looking at the track size 3,25 KiB or 6 1/2 filesystem blocks and the way the filesystem is organized, 4 blocks is exactly the number of continuous blocks left on track 0. The filesytem reserves (and ignores) the first two blocks (1 KiB) for any kind of bootloader. The Directory starts right thereafter - and there are exactly 4 blocks left before the system would need to switch sides or tracks. Considering this, the RX01 might in fact have lead to this 4 block default size used as a good start value, and never really changed. So your idea was maybe right, but the reasoning way off. – Raffzahn Feb 15 at 20:08
  • 1
    Yes, it could - like the BESM-6 could have had the structure of a 6502, and we all still being subjects to the Roman empire :)) Except, they didn't so it is two blocks that get ignored at the begin of each volume. And while a larger reservation after the boot blocks would have been possible (The volume header includes a field of the first usable data block after the directory), it never has - at least to my knowledge - been used to extend it in length. Instead it has been used to reserve space for a directory duplicate on some systems, as well as to 'hide' some data. – Raffzahn Feb 15 at 21:15
2

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.