> The demand paging code for SysVR2 was written by Keith A. Kelleman and Steven J. Buroff, and in contemporary conference talks they were saying that they wanted to combine the best parts of demand-paged 32V and BSD. They may have some additional memories that could help with getting a better understanding of the final version of 32V.
>
> Does anybody have contact details for these two gentlemen?
I’ve managed to contact Keith Kelleman and he had some interesting remarks. The paging code in SVR2 was all new code, with a focus the 3B dual processor. It does not derive at the code level from 32V and in fact he does not recall working with the 32V paging code. This kills the hope that the SVR2 code had clues about the 32V code. Keith did suggest that I tried to contact Tom Raleigh, who might have worked with the later 32V code base. Anybody with suggestions for locating him?
===
Besides functionality, the people that remember paged 32V all recall it being very fast. I wonder what made it fast.
First to consider is “faster than what?”. Maybe Rob P. has a specific memory, but I would assume faster than 4BSD: if the comparison was with the "scatter loading, partial swapping” version of 32V people would have expected the better performance and not remember it as impressive 40 years later. Possibly the comparison is with 8th Edition which would have used the 4BSD paging code by then.
If the comparison is with 4BSD, then the CoW feature in paging 32V would have been mostly matched by the vfork mechanism in 4BSD: it covers 80% of the use and it leaves the code paths simpler. If the comparison is with 8th edition, this may be the difference that people remember.
The next possibility is that paging 32V had a better page-out algorithm. Joy/Babaoglu mention that the cost of the clock process is noticable. Maybe paged 32V used a VMS-like FIFO/second chance algorithm that did not need a separate kernel process/thread. Arguably this is not enough for a convincing speed difference.
It is also possible that JFR found a more clever way to do LRU approximation. He remembers that his code used ‘strict LRU’, but not the algorithm. On Tenex - his conceptual reference - that was natural to do, because the MMU hardware maintains a table with 4 words of 36 bits for each frame with statistical data. With the VAX hardware it is a challenge. Considering his mathematical prowess it is maybe plausible that JFR found an efficient way. A slightly better page hit rate gives a significant speed improvement.
All speculation of course: only finding the source will truly tell.
> So there you have it. Just a line of B code that wasn't updated to C.
>
> Cheers,
> aap
I love posts like this, thank you! “Sherlock Holmes and the mysterious case of the excessive parameter list"
Greetings,
It has always bugged me that the bsd-family-tree file got 2.8BSD slightly
wrong.
It has the relationship V6 -> 1BSD -> 2BSD -> 2.79BSD -> 2.8BSD
with V7 -> 32V -> 3BSD ... -> 4.1BSD -> 2.8BSD
Now, as far as it goes, that's not terrible. But it's missing something.
First, there was no V6 code in 1BSD or 2BSD through 2.79BSD. It was for V6
at first then for both V6 and V7, but w/o V7 code. There weren't even
patches for V6 or new drivers on the early 1BSD and 2BSDs. However,
starting with 2.8BSD, there's a V7 kernel. Or should I say a heavily
patched V7 kernel with a ton of #ifdefs for all the fixes and enhancements
collected by Berkeley and a few minor build system tweaks.
Also, the code from 4.1BSD that's in 2.8 is rather minimal from what I can
tell with my analysis so far, except indirectly in some of the patches to
the V7 kernel appear to also be in 4.1BSD. The biggest thing that's in
2.8BSD from 4.1BSD is the job control (confined to its own directory with
big warnings that basically say you'll need to update the code and even
then the system is unstable). 2.9BSD has much better 4.xBSD integration,
but 2.8 was quite early days for rejoining the two lines. 4.1BSD didn't
have many berkeley rewrites of userland code, and the 2.8 tape has only a
few of them (eg ls). So although it's not as complete as one would hope,
there was a decent amount of code from 4.1BSD flowing into 2.8BSD.
Now, my request. I've created a code review for FreeBSD to fix this.
https://reviews.freebsd.org/D30883 is the review. We use phabricator in the
FreeBSD project. Anybody can view this, but if you don't want to create an
account, please send me email with a comment about the change and/or the
commit message. It just adds an arc from V7 to 2.8BSD.
Thanks for any time and/or insight you might have here. I'm judging the
above entirely on the archived code rather than any historical knowledge...
Warner
On 23/06/21, silas poulson wrote:
> I’m aware line 2238’s famous “You are not expected to understand
> this.” Comment is due to odd PDP-11/45 behaviour.
Actually there are two different takes on what it is exactly that you're
not expected to understand. The "obvious" one in Lions' book, (i.e. saved
stack being overwritten when swapping so you have to restore from the
special swap-saved stack), but dmr had a different take on it, that it
had to do with functions really not being happy if you switch the stack
underneath them. You can find dummy variables in the interdata port that
make sure the stack frames of some functions (newproc and swtch?) match.
So not really a hardware thing but a consequence of the compiler.
> Do you know if other sections of the C show remnants of B or the PDP?
> Or is it just those spots?
For the kernel I'm just aware of this one. printf was copied over a
number of times (the c compiler also includes a version) but the kernel
was never written in B, so i wouldn't expect any B-ness in there
otherwise.
aap
... when he declared all the parameters for this procedure"
I'm sure some of you remember this quote expressing John Lions'
puzzlement over the declaration of printf in the UNIX kernel:
printf(fmt,x1,x2,x3,x4,x5,x6,x7,x8,x9,xa,xb,xc)
Note that parameters x2 and following are never referenced by name
in the function body, only by pointer arithmetic from &x1.
The historical reason for this long list of parameters is probably
not well known, so I want to explain it and hope that you will find
it as enjoyable as I did when I came across it some time ago while
studying leftover files of B.
To call a function in B, there's a little dance you have to do:
first push the function address onto the stack, remember the stack
pointer, push all the arguments, then restore the stack pointer and
do the actual call.
In diagrams, this is what happens to the B stack:
push func addr:
+------------+
| | <- sp
+------------+
| func addr |
+------------+
mark (n2):
+------------+
| | <- sp
+------------+
| | <- old sp (saved on native stack)
+------------+
| func addr |
+------------+
push arguments:
+------------+
| | <- sp
+------------+
| arg n |
+------------+
| ... |
+------------+
| arg 0 |
+------------+
| | <- old sp (saved on native stack)
+------------+
| func addr |
+------------+
call (n3):
pop old sp from stack
jump to func addr on stack
set ret addr and old fp
+------------+
| arg n |
+------------+
| ... |
+------------+
| arg 0 |
+------------+
| ret addr |
+------------+
| old fp | <- sp, fp
+------------+
The callee then sets sp, so has to know how many args and automatics!
+------------+
| | <- sp
+------------+
| auto n |
+------------+
| ... |
+------------+
| auto 0 |
+------------+
| arg n |
+------------+
| ... |
+------------+
| arg 0 |
+------------+
| ret addr |
+------------+
| old fp | <- fp
+------------+
So because the arguments to a functions were grouped together with
the automatics and not below the ret addr and saved fp, there has
to be space on the stack lest they clash. This of course means that
this printf in B would probably break if called with more arguments
than it expects.
So there you have it. Just a line of B code that wasn't updated to C.
Cheers,
aap
Hello,
I'm currently trying out the rc shell (using Byron Rakitzis'
implementation for Unix). Compared to Bash, which I normally use, this
shell has a rather small feature set (which isn't to say that that's
necessarily a bad thing).
Now, one of the features that Bash has and rc doesn't have is the
ability to perform arithmetic expansion. That's not really a problem
because you can just use `expr` instead. I wonder, though, when
arithmetic expansion as a shell built-in became a thing, especially in
POSIX sh.
POSIX has included that feature since at least 2001, and probably quite
some years earlier, given that Bash already had it in 1995 (going by
the manual page of version 1.14.7, the oldest I could find).
So, maybe someone here can help me find out when this was actually
standardized.
Thanks.
--
Michael
even tho it was there, in-shell integer arithmetic had a few
issues before ksh86.
pre-ksh86 these had problems --
A. decimal point in a number
$ integer I
$ I=2.2
would error on the assignment, but with ksh86 $I is truncated to 2
(yes "integer" is an builtin alias to typeset -i and ksh courses at the time
instructed to use that over typset)
B. negative numbers
$ integer I
$ I=-2
here pre-86 $I would be assigned a large value like 2147483646
also ksh was not stardard until SVR4 (very late 80s) so it was found
in paths like /usr/add-on/bin/ksh or /usr/exptools/bin/ksh, or not even
there at all, you could not reliably #! ksh scripts
also with ksh86 the double paren ((...)) notation was exactly the same as
"let ..." and were completely optional if the variable was predefined as
an integer, so
$ I=0
$ ((I=I+1))
and
$ integer I
$ I=0
$ I=I+1
are the same.
All internal integers in ksh were C longs (at least 32-bits)
where Bourne shell all vars are strings so you would need to do this --
$ I=`expr $I + 1`
But also at that time expr(1) could NOT deal with negative numbers on input,
they became strings. So
$ expr -9 + 1
is an error with "non-numeric argument", and
$ expr -11 '<' -1
returns 0, a false statement, which are hidden bugs with variables.
expr(1) was also 32-bits, as was test (i.e [ ) which could deal with
negative numbers just fine.
for arbitrarily large numbers you needed use dc(1) or bc(1). but dc(1)
also has a issue with inputing negative numbers as it uses an _ not
a - to denote a negatve number on input, but does use the - on output.
$ I=`echo _9 1 - p | dc`
is how you would do ((I=-9 - 1)) in bourne with dc
which is cumbersome if you have a variable with a neagtive number in it,
and required a "tr - _" first.
however
$ I=`echo -9 - 1 | bc`
worked just fine in bourne.
-Brian
Chet Ramey wrote:
> On 6/21/21 5:57 AM, arnold at skeeve.com wrote:
> > Arithmetic expansion dates back at least as far as ksh88.
>
> ksh had the `let' builtin from at least 1983. The ((...)) compound command
> was there by ksh-86.
>
> > Bash likely picked it up from there.
>
> Sort of, see below.
>
> > The original was only integer math and Bash remains that way (IIRC,
> > Chet can correct me if I'm wrong). ksh93 added floating point math.
>
> Yes, bash only has integer arithmetic, since it's all POSIX requires.
>
> > POSIX would have picked it up from ksh88.
>
> The $((...)) form of arithmetic expansion is something POSIX picked up
> from ksh-88, eventually. The early drafts of the standard (through 1003.2
> d9, at least), used $[...], but they eventually adopted $((...)) because
> ksh-88 had already implemented it, though it's not documented in Bolsky
> and Korn.
>
> I put $[...] into bash first (it's still there, though deprecated), then
> `let', then $((...)) after POSIX added it, and finally `((' for
> compatibility.
>
> Chet
I’m still researching John Reiser’s 32V with demand paging, copy-on-write and mmap.
Unfortunately, JFR does not have the bits or a listing for this version of 32V.
I’ve read the MSc theses of Leffler and Shannon with interest (https://www.tuhs.org/Archive/Documentation/Theses/) The thesis of Shannon has an interesting discussion of a demand paged version of his Harris/6 Unix (Chapter 5). It is based on the Tenex ideas, just as JFR mentioned for his version. The thesis of Leffler contains a gant chart that shows that the demand paged version was written in the first months of 1980 -- concurrently with or slightly after the 32V version.
I’ve also (superficially) read the papers on Tenex memory management. The design is closely tied to PDP-10 MMU that BBN designed for Tenex. Some of its data structuring is recognisable in Shannon’s version. One defining aspect is that the design for both is for a virtual address space that is smaller than the physical address space; on a 1980 VAX it was the reverse.
If 32V followed the same design ideas (a big if), it most likely limited processes to a capped address space (e.g. 2MB). It might also have contained an in-core flag/data vector with as many entries as there are pages frames in swap space. If true, these downsides may have been why it did not go on to become the root for SysVR1 or R2 paging.
The demand paging code for SysVR2 was written by Keith A. Kelleman and Steven J. Buroff, and in contemporary conference talks they were saying that they wanted to combine the best parts of demand-paged 32V and BSD. They may have some additional memories that could help with getting a better understanding of the final version of 32V.
Does anybody have contact details for these two gentlemen?
Not Unix in particular.
At least in Germany it is already the 16th, and my BSD calendar
notifies that "first programming error is encountered at the
U. S. Census Bureau".
As not being hard-to-the-core i may have missed it, but also in
1951, in March, the wonderful Grace Hopper "conceives the first
compiler, called A-O and later released as Math-Matic. Hopper is
also credited with coining the term 'bug' following an incident
involving a moth and a Mark II.
All (hm!) according to COMPUTERWORLD January 18th, 1999 (i was
young!), with assistance of the Computer Museum of Boston.
Like McCartney said in the legendary 1999 concert at the Cavern
club, the first after his wonderful wife Linda died, "See, with
this band, if we don't get it right ... we start again!".
Thank you.
--steffen
|
|Der Kragenbaer, The moon bear,
|der holt sich munter he cheerfully and one by one
|einen nach dem anderen runter wa.ks himself off
|(By Robert Gernhardt)
Rob Pike:
Although upon reflection, I think what I did was fix 'adb' and call it
'db'. Haven't had my coffee yet this morning.
====
I don't think so. I did quite a lot of work on adb during my
time at the Labs. I remember clearly that it still used all
the Bournegol macros when I started; I doubt Rob would have
left that there. (It was Rob who translated the shell
back to C, I believe.)
I got into adb because it still used ptrace and everyone else
seemed scared to touch the code to convert it to use /proc.
So I fixed that, and fixed sdb too, and finally removed
the ptrace call from the kernel. I remember celebrating
by expunging ptrace from the UNIX Room copy of the V8
manual. ptrace happened to occupt two facing pages, which
I glued together.
I did a lot more hacking on adb after that, ranging from
little stuff like making # a synonym for 0x in input
(so that adb's output could be picked up from the screen
and re-used as input, a principle established firmly and
correctly by Rob!) to a major restructuring to isolate
machine-dependent pieces like instruction decoding and
word formats, so that it was simpler not only to make
adb work on a new processor architecture but even to make
a sort of cross-adb that could, say, correctly interpret
a PDP-11 core image on a VAX. (This actually mattered;
by the time I arrived Research had no PDP-11s running
general-purpose UNIX, but did have LSI-11s acting as
Datakit controllers and a standalone power-backed-up
LSI-11 that decoded the time signal from WWVB.)
I was never really happy about the restructuring; it did
more or less what I wanted but it wasn't really graceful.
And cross-adb needed a distinct binary for each target.
I had thoughts of trying to make a meta-language to
describe the target's data formats (simple except for
floating point) and how to print its instructions
(messier, but I remember being inspired by the clever
table-driven code in an disassembler Ken wrote for,
I think it was, the NS32000), so that one could load
a table from a file at startup; never had the time or
the courage to carry through on it.
Norman Wilson
Toronto ON
