I've assembled some notes from old manuals and other sources
on the formats used for on-disk file systems through the
Additional notes, comments on style, and whatnot are welcome.
(It may be sensible to send anything in the last two categories
directly to me, rather than to the whole list.)
Hi all, I received an e-mail looking for the ksh-88 source code. A quick
search for it on-line doesn't reveal it. Does anybody have a copy?
I recently built a PiDP11 and have been enjoying going back in time
to 2.11BSD.. I was at UC Davis in the the early 1980's and we had
a few PDP-11/70's running 2.8/2.9 BSD. Back then we reached out to
David Korn and he sent us the source for KSH -- this would have been
in 1985ish if I remember, and we compiled it for 2.9 & 4.1BSD, Xenix,
and some other variants that used K&R C. It may have been what was
later called ksh88. I wish I still had the files from then..
I was wondering if you might know if there's an older version like this
or one that's been ported for 2.11BSD?
I've recently started to implement a set of helper functions and
procedures for parsing Unix-like command-line interfaces (i.e., POSIX +
GNU-style long options, in this case) in Ada.
While doing that, I learned that there is a better way to approach
this problem – beyond using getopt(s) (which never really made sense to
me) and having to write case statements in loops every time: Define a
grammar, let a pre-built parser do the work, and have the parser
provide the results to the program.
Now, defining such a grammar requires a thoroughly systematic approach
to the design of command-line interfaces. One problem with that is
whether that grammar should allow for sub-commands. And that leads to
the question of how task-specific tool sets should be designed. These
seem to be a relatively new phenomenon in Unix-like systems that POSIX
doesn't say anything about, as far as I can see.
So, I've prepared a bit of a write-up, pondering on the pros and cons
of two different ways of having task-specific tool sets
(non-hierarchical command sets vs. sub-commands) that is available at
I tend to think the sub-command approach is better. But I'm neither a UI
nor a Unix expert and have no formal training in computer things. So, I
thought this would be a good place to ask for comment (and get some
This is all just my pro-hobbyist attempt to make some people's lives
easier, especially mine. I mean, currently, the "Unix" command line is
quite a zoo, and not in a positive sense. Also, the number of
well-thought-out command-line interfaces doesn't seem to be a growing
one. But I guess that could be changed by providing truly easy ways to
make good interfaces.
> On 7/31/21, Michael Siegel <msi(a)malbolge.net> wrote:
> The TOPS-20 COMND JSYS implemented both of these features, and I
think that command
> completion was eventually added to the VMS command interpreter, too.
FYI, There is also a unix version of the COMND JSYS capability. It was
developed at Columbia University as part of their "mm" mail manager. It
is located in to the ccmd subdirectory in the mm.tar.gz file.
Besides C-Kermit on Unix systems, the TOPS-20 command interface is
used inside the mm mail client, which I've been using for decades on
TOPS-20, VMS, and several flavors of Unix:
mm doesn't handle attachments, or do fancy display of HTML, and thus,
cannot do anything nasty in response to incoming mail messages.
I rarely need to extract an attachment, and I then save the message in
a temporary file and run munpack on it.
Here are some small snippets of its inline help:
MM] read (messages) ? message number
or range of message numbers, n:m
or range of message numbers, n-m
or range of message numbers, n+m (m messages beginning with n)
or "." to specify the current message
or "*" to specify the last message
or message sequence, one of the following:
after all answered before
current deleted flagged from
inverse keyword last longer
new on previous-sequence recent
seen shorter since subject
text to unanswered undeleted
unflagged unkeyword unseen
or "," and another message sequence
R] read (messages) flagged since yesterday
[message(s) appear here]
MM] headers (messages) since monday longer (than) 100000
[list of long messages here]
- Nelson H. F. Beebe Tel: +1 801 581 5254 -
- University of Utah FAX: +1 801 581 4148 -
- Department of Mathematics, 110 LCB Internet e-mail: beebe(a)math.utah.edu -
- 155 S 1400 E RM 233 beebe(a)acm.org beebe(a)computer.org -
- Salt Lake City, UT 84112-0090, USA URL: http://www.math.utah.edu/~beebe/ -
> TUHS list (Rob Pike, Aug 2019)
> I think it was slightly later. I joined mid-1980 and VAXes to replace the
> 11/70 were being discussed but had not arrived. We needed to convert a lab
> into a VAX machine room and decide between BSD and Reiser, all of which
> happened in the second half of 1980.
> Reiser Unix got demand paging a little later, and it was spectacularly
> fast. I remember being gobsmacked when I saw a demo in early 1981.
> Dead ends everywhere.
I think I have figured out why 32V R3 was so fast (assuming my current understanding of how 32V R3 must have worked is correct).
Its VM subsystem tags each memory frame with its disk mirror location, be it in swap or in the file system. A page can quickly be found as they are hashed on device and block no. This is true both for pages in the working set and pages on the 2nd chance list. Effectively, most core is a disk cache.
In a unified buffer design, the buffer code would first look for an existing buffer header for the requested disk block, as in V7. If not found, it would check the page frame list for that block and if found it would connect the frame to an empty buffer header, increment its use count and move it to the working set. If not found there either, it would be loaded from disk as per usual. When a buffer is released, the frame use count would be decremented and if zero the page frame would be put back on the 2nd chance list and the buffer header would be marked empty. With this approach, up to 4MB of the disk could be cached in RAM.
Early in 1981 most binaries and files were a few dozen KB in size. All of the shell, editor, compiler tool chain, library files, intermediate files, etc. would have fitted in RAM all at once. In a developer focused demo and once memory was primed, the system would effectively run from RAM, barely hitting the disk, even with tens of concurrent logins. Also something like “ls -l /bin” would have been much faster on its second run.
It puts a comment from JFR in a clearer context:
Strict LRU on 8,192 pages, plus Copy-On-Write, made the second reference to a page "blindingly fast".
So far I read this in context of the paging algorithm, and then it is hard to understand (is LRU really that much better than NRU?). In the context of a unified buffer and disk pages, it makes a lot more sense. Even the CoW part: as the (clean) data segment of executables would still be in core, they could start without reloading from disk - CoW would create copies as needed.
The interesting question now is: if this buffer unification was so impressive, why was it abandoned in SVr2-vax? I can think of 3 reasons:
1. Maybe there was a subtle bug that was hard to diagnose. “Research" opting for the BSD memory system “as it did not want to do the maintenance” suggests that there may have been lingering issues.
1b. A variation of this: JFR mentioned that his implementation of unified buffers broke conceptual layering. USG do not strike me as purists, but maybe they thought the code was too messy to maintain.
2. Maybe there was an unintended semantic issue (e.g. you can lock a buffer, but not a mmap ‘ed page).
3. Maybe it was hard to come up with a good sync() policy, making database work risky (and system crashes more devastating to the file system).
JFR mentioned that he did the design and implementation for 32V R3 in about 3 months, with 3 more months for bug fixing and polishing. That is not a lot of time for such a big and complex kernel mod (for its time).
Currently reading through IPC in CB Unix 3.0, Vr1-vax and SVr1-pdp11.
The IPC primitives in CB Unix (maus, event and msg) are quite different from those in SVr1 (although maus survives in SVr1-pdp11).
It made me wonder: is it still known who designed the IPC primitives for SysV?
> Sat Aug 31 06:21:47 AEST 2019
> John Reiser did do his own paging system for UNIX 32/V.
> I heard about it from friends at Bell Labs ca. 1982-83,
> when I was still running systems for physicists at Caltech.
> It sounded very interesting, and I would love to have had
> my hands on it--page cache unified with buffer cache,
> copy-on-write from the start.
> It is in any case a shame that jfr's code never saw the light
> of day. I really hope someone can find it on an old tape
> somewhere and we can get it into the archive, if only because
> I'd love to look at it.
> Norman Wilson
> Toronto ON
I am getting more optimistic that much of this version of 32V can be ‘triangulated’ from the surviving sources. For convenience I call this version “32V r3” (with the first swapping version being "32V r1" and the scatter loading version being "32V r2").
I’ve been reading my way through the surviving 32/V r2, SysIII-Vax, SVr1-Vax and SVr2-Vax sources. There seems to be a lot of continuous progression in these versions. From a communication with Keith Kelleman I thought that VM in SVr2 was unrelated, but that appears to have been a misunderstanding. In short, it seems that the basic paging algorithms and data structures in SVr2 (other than the region abstraction) come from 32V r3.
The strongest clue for the source link is in the SVr2 “page.h” file. In it, the union describing a page table entry matches with JFR’s description and is otherwise (partially) unused in SVr2. There are other, similar clues in the other source trees.
To explain more clearly, have a look at this code section: https://github.com/ryanwoodsmall/oldsysv/blob/master/sysvr2-vax/src/uts/vax…
In this union, the 2nd struct “pgd” is never used, nor is the bit pg_disk in the “pgm” struct ever used. It matches with JFR’s recollection:
My internal design strategy was to use the hardware page table entry
(4 bytes per page, with "page not present" being one bit which freed
the other 31 bits for use by software) as the anchor to track everything
about a page. This resulted in a complicated union of bitfield structs,
which became a headache. When other departments took over the work,
the first thing they did was use 8 bytes per page, which meant shuffling
between the software and the hardware descriptors: its own mess.
In the pte as given, a pte can be in two states: (i) the pg_disk bit is reset in which case it is in “pgm” format - this format is recognized by the mmu hardware; (ii) the pg_disk bit is set in which case it is in “pgd” format. When a page is paged in, the disk form of the pte was I think saved in the page frame descriptor (the “pfdat" table) and the pte converted to the memory form. Upon page-out the reverse happened. In the SVr2 version of this code the “pgd” form is abandoned and replaced by the separate disk descriptors (see https://github.com/ryanwoodsmall/oldsysv/blob/master/sysvr2-vax/src/uts/vax…)
The “pgd” structure is a bit puzzling. There is a 19 bit device block number, which is less than the 24 bits allowed by the filesystem code and also less than the 20 bits that would fit in the pte. Maybe this is because the RP04/RP05 disks of the early 80’s worked with 19 bits. I am not sure what the “pg_iord” field is about. The comment “inode index” may be misleading. My hypothesis that it is a short form of the device code, for instance an index into the mount table; magic values could have been used to identify the swap device, “demand zero”, etc.
It seems probable to me that the paging algorithm in SVr2 was derived from the 32/V r3 algorithm. John's recollection:
Our machine started with 512KB of RAM, but within a few months was upgraded
to 4 MB with boards that used a new generation of RAM chips.
The hardware page size was 512 bytes, which is quite small. Strict LRU
on 8,192 pages, plus Copy-On-Write, made the second reference to a page
In a follow up mail conversation with JFR we (I?) arrived at the conclusion that literal “strict LRU” is not likely on VAX hardware, but that an algorithm that maintains a small working set combined with a large second chance list amounts to about the same. It seems to me that this description also applies to the surviving SVr2 implementation: every 4 seconds sweep through the page tables of all processes and pages that were not referenced are moved to the free/2nd chance list.
To implement this it seems likely to me that 32V r3 used a structure similar to this: https://github.com/ryanwoodsmall/oldsysv/blob/master/sysvr2-vax/src/uts/vax… Such a structure is also in line with viewing core as a cache for disk, similar to TENEX that JFR had in mind.
The big change from SysIII to SVr1 in kernel page table management is the introduction of the “sptmap” (https://chiselapp.com/user/pnr/repository/paging/file?name=os/machdep.c&ci=…). In 32V r2 and SysIII the user page tables are swapped in and out of kernel space along with the _u area. This makes it impractical to do the working set sweep every few seconds. The “sptmap” innovation effectively creates a global page table space that fits with the needs of the working set sweep. In SVr1 it seems to have no real benefit, and it seems likely to me that it came from 32V r3.
In general it seems plausible to me that SVr1 derives from 32V r3, but was regressed to SysIII code where necessary to keep the code PDP-11 compatible. Another clue for this is in the buffer code of SVr1: https://chiselapp.com/user/pnr/repository/paging/file?name=os/main.c&ci=fba…
Here, the disk buffers are allocated as virtual memory pages, not as an array. This too is otherwise unused in SVr1, but makes perfect sense in the context of 32V r3.
So, in summary, it would seem to me that the 32V r3 virtual memory system:
- used sptmap code similar to SVr1/r2 to manage page tables in the kernel
- used the pte structure from SVr2 and a pfdat table similar to SVr2 to manage mappings
- used page stealer and fault code similar to SVr2
Phrased the other way around: SVr2-vax seems to use the 32V r3 virtual memory code with the region abstraction added on top, and the unified buffer removed.
At the moment I have not found clear clues for the unified buffer algorithms or mmap implementation. Perhaps careful reading of the IPC shared memory code in SVr1 will yield some.
To be continued …