[TUHS] Unix & Memory Management Units (MMU)

[TUHS] Unix & Memory Management Units (MMU)

[Johnny Billquist]

On 2016-12-08 18:18, Paul Ruizendaal <pnr at planet.nl> wrote:
>
>>> DEC's Custom Special Systems (CSS) group .. build a simple base/limi
>>> register device, soon after the 11/20 was released.> ... So an early
>>> version of after the original 11/20 port from the PDP-7 had this
>>> however.....
>> Oh, right, I'd forgotten about that: the KS-11 - I've previously enquired to
>> see if anyone had _any_ documentation for this, but so far, nada.
> I was looking for that a few years back. Dennis Ritchie's home pages have
> some info on this (https://www.bell-labs.com/usr/dmr/www/odd.html).
> At the bottom of that page he writes:
>
> ""Back around 1970-71, Unix on the PDP-11/20 ran on hardware that not only did not support virtual memory, but didn't support any kind of hardware memory mapping or protection, for example against writing over the kernel. This was a pain, because we were using the machine for multiple users. When anyone was working on a program, it was considered a courtesy to yell "A.OUT?" before trying it, to warn others to save whatever they were editing.
> [..snip..]
> We knew the PDP-11/45, which did support memory mapping and protection for the kernel and other processes, was coming, but not instantly; in anticipation, we arranged with Digital Special Systems to buy a PDP-11/20 with KS-11 add-on. This was an extra system unit bolted to the processor that made it distinguish kernel from user mode, and provided a classical PDP-10 style "hi-seg" "low-seg" memory mapping unit. I seem to recall that maybe 6 of these had been made when we ordered it.""
>
> My hypothesis is that the very first versions of Unix were using a memory scheme similar to that used in the later LSX and MX derivatives: the kernel resides in lower memory and the user program in upper memory; each process switch implied a swap. Disclaimer: I have not studied the V0 source to verify this hypothesis.
>
> When this topic had my interest I looked for (but did not find) information on what ""the classical PDP-10 style "hi-seg" "low-seg" memory mapping unit"" was. Here my hypothesis would be that in kernel mode mapping was off, and that in user mode there were two segments, each with a base and limit into physical memory -- and that this setup has an echo in how the later KL-11 MMU was used.
>
> Does anyone have an idea what PDP-10 MMU Dennis may have been referring to?

If you read the Wikipedia page about the PDP-10, you'd find the answer.

Basically, kernel mode uses physical memory. User mode have a low 
segment and a high segment. This is decided by the high bit of the address.
For each segment, there is a base register and a length register.
Commonly, the low segment stored read/write data, while the high segment 
could be shared between processes, and have readonly data/code.

But you could play in other ways with it, if you wanted to.

Essex MUD, as far as I remember, had the game data in a shared hiseg, 
which could be written by the program.

So your guessing is pretty good. Not sure I'd say this is similar to how 
the later PDP-11 MMU works, though. But I can see someone making the 
comparison, since the PDP-11 pages can vary in size, within limits.

	Johnny

-- 
Johnny Billquist                  || "I'm on a bus
                                   ||  on a psychedelic trip
email: bqt at softjar.se             ||  Reading murder books
pdp is alive!                     ||  tryin' to stay hip" - B. Idol

[TUHS] Unix & Memory Management Units (MMU)

[Paul Ruizendaal]

On 8 Dec 2016, at 19:11 , Johnny Billquist wrote:

> So your guessing is pretty good. Not sure I'd say this is similar to how the later PDP-11 MMU works, though. But I can see someone making the comparison, since the PDP-11 pages can vary in size, within limits.

Thanks for that info on the PDP-10 MMU!

What I meant to say was that the high-low scheme has an echo in how the KL-11 was *used* (not how it *worked*). A standard binary (0407 magic) effectively has two segments in PDP11 Unix: a contiguous low segment (for text, data and bss) and a contiguous high segment (for the stack).

Paul

[TUHS] Unix & Memory Management Units (MMU)

[Lars Brinkhoff]

Paul Ruizendaal wrote:
> Thanks for that info on the PDP-10 MMU!

You're one off.  Maybe you're preoccupied with the upcoming DEC-10
holiday?

[TUHS] Unix & Memory Management Units (MMU)

[Paul Ruizendaal]

>> this setup has an echo in how the later KL-11 MMU was used.
> 
> Sorry, what's a KL-11? The only 'KL11' I know of is the serial line board
> (M780) which was the predecessor to the DL11.

Sorry, my bad -- meant KT11.

[TUHS] Unix & Memory Management Units (MMU)

[Noel Chiappa]

    > Dennis Ritchie's home pages have some info on this

Yeah, I'd read that - I was hoping for some actual technical info on the KS11,
though.

(I'm assuming he has given the name there correctly, or if his memory has
dropped a bit - a thing which human memories do! :-) - since I've never been
able to find a single mention of it, including in the Spare Module Handbook,
which covers other Special Systems products).


    > I looked for (but did not find) information on what ""the classical
    > PDP-10 style "hi-seg" "low-seg" memory mapping unit"" was.

The best description is in the DECSystem-10 Hardware Reference Manual (mine is
EK-10/20-HR-001, but alas that version appears not to be online - I'll scan my
copy and put it online when I get a chance.) This version:

  http://pdp10.nocrew.org/docs/ad-h391a-t1.pdf

does appear to cover it: pp. 5-38 through 5-40 (pp. 352-354 of the PDF) for
the KA10, and pp. 5-15 to 5-30 (pp. 329-344) for the KI10.

The KA10 provided one (optionally) two base/bounds register pairs, where the
base register contains the location in real memory. With two pairs (the
second one applied to high user address space), the high part could be
write-protected, for sharing pure code.

The KI10 provided something similar to this, but more complicated; it included
paging, but also something called User 'Concealed', which allowed proprietary
subroutine packages to be used, while hidden from the rest of the user's code.

    > Does anyone have an idea what PDP-10 MMU Dennis may have been referring
    > to?

Almost certainly the KA10.

    > Here my hypothesis would be that in kernel mode mapping was off, and
    > that in user mode there were two segments, each with a base and limit
    > into physical memory

Hard to say. Kernel mode might or might not have mapping, and User mode might
have provided one, or two, segments; the KA10 did have an option for
single-segment.


    > this setup has an echo in how the later KL-11 MMU was used.

Sorry, what's a KL-11? The only 'KL11' I know of is the serial line board
(M780) which was the predecessor to the DL11.

       Noel

[TUHS] Unix & Memory Management Units (MMU)

[Paul Ruizendaal]

Finally took a look at the V1 source.

Referring to http://minnie.tuhs.org/cgi-bin/utree.pl?file=V1/u2.s
Toward the end of the sysexec function there is:

	cmp	core,$405 / br .+14 is first instruction if file is
			  / standard a.out format
	bne	1f / branch, if not standard format
	mov	core+2,r5 / put 2nd word of users program in r5; number of
			  / bytes in program text
	sub	$14,r5 / subtract 12
	cmp	r5,u.count /
	bgt	1f / branch if r5 greater than u.count
	mov	r5,u.count
	jsr	r0,readi / read in rest of user's program text
	add	core+10,u.nread / add size of user data area to u.nread
	br	2f
1:
	jsr	r0,readi / read in rest of file
2:
	mov	u.nread,u.break / set users program break to end of 
				/ user code
	add	$core+14,u.break / plus data area
	jsr	r0,iclose / does nothing
	br	sysret3 / return to core image at $core

$core is equated to 040000 in another file (u0.s). In V1 apparently the a.out header was 6 words (http://minnie.tuhs.org/cgi-bin/utree.pl?file=V1/man/man5/a.out.5), not 8, and hence the magic for a standard executable was 0405. It was already used as magic to distinguish a.out format files from other executables. It also shows that indeed 'exec' jumped to the first word of the header (at location $core).

[TUHS] Unix & Memory Management Units (MMU)

[Joerg Schilling]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3869 bytes --]

Earl Baugh <earl.baugh at gmail.com> wrote:

> I can at least shed some light on at least when the Sun boxes supported it
> (which may or may not help narrow down the date)
> The initial Sun 1/100 multibus machines did not support virtual memory.   I
> have one of the last (if not the last) original multibus boards
> from Sun with the original PROMs...  and it was supported up to Sun OS 0.7.
>    This OS was based off UniSoft UNIX v7.     The 0.7 version was released
> in 1982.
> In order to support virtual memory systems, there was a board upgrade
> required.   Anyone who wanted to go to SunOS 1.0 had to get this board
> upgrade (which from what I know, was a board swap... not sure if money
> traded hands as well... and is one core reason the original boards are
> rare).   The release of Sun OS 1.0 was in November 1983.

The oldest Sun I had was a multibus machine with a mc68010.....This was in 
January 1985. These machines still had a keyboard that was connected to the 
frame buffer to play with the row/col readout lines. See:

/usr/include/sys/kbd.h:#define     KB_KLUNK        0x00            /* Micro Switch 103SD32-2 */

which is still in the recent sources ;-)

The problem you describe is not related to virtual memory, but to demanded page 
loading as an enhancement to the old swapping method. This demanded page 
loading did not work at all with the 68000 and even the Bourne Shell triggered 
a bug from this deficit - see below.

BTW: The name of the OS was not SunOS these days. AFAIR, the first time it was 
called "SunOS" was christmas 1985 (the 0-series of first boards with mc68020 
have been built December 24 1985) and the OS was called SunOS-3.0. I never 
understood how Sun managed to get these boards delivered through the customs 
to Berlin in December 27 or 30. At that time, I was working for the first 
large Sun customer H.Berthold AG and we received these boards.

Before SunOS-3.0, it was called similar to "BSD-4.2 UNIX Sun version foo".

I am not sure what you mean with this NULL ptr dereferences. AFAIR, on SunOS I 
never could dereference a NULL pointer but in SVr3 nearly all commands used an 
option parser that caused a NULL pointer dereference. On SunOS they dumped 
core if you tried to compile and run then.

The printf() on SunOS however printed "(null)" for printf("%s", NULL);

SVr4 used a SunOS kernel and thus did not allow to dereference NULL pointers.
The user space commands have been from SVr3 and _most_ of them had been fixed 
to avoid NULL pointer dereferences.

Today, Solaris comes with a libragy 0 at 0 that maps a page of nulls to address 0.
Call "LD_PRELOAD=0@= command" in case you have one of these nasty programs 
developed on Linux that use to dump core on Solaris ;-)

Back to the Bourne Shell:

The original Bourne Shell did not use malloc, but rather had a SIGSEGV handler 
that used to extend the "string stack" called "stak" via sbrk() whenever the 
code tried to access data beyond the end ot the heap.

This method was great, but did not work with the mc68000, as the 68000 had a 
conceptional bug in the micro code. It could not restart code like:

	*to++ = *from++;

correctly after the return from an exception handler trap.

What Sun did at that time was to add tests to the code to avoid that SIGSEGV 
hits. This code is still in recent Bourne Shell versions.

I did however discover a missed place in the code last year while running a 
fuzzer on the code. Note that the "stak" module has been replaced 2012 with 
code based on a rewrite from Geoff Collyer. See:

	http://schilytools.sourceforge.net/bosh.html

Jörg

-- 
 EMail:joerg at schily.net                  (home) Jörg Schilling D-13353 Berlin
       joerg.schilling at fokus.fraunhofer.de (work) Blog: http://schily.blogspot.com/
 URL:  http://cdrecord.org/private/ http://sourceforge.net/projects/schilytools/files/

[TUHS] Unix & Memory Management Units (MMU)

[Paul Ruizendaal]

>> DEC's Custom Special Systems (CSS) group .. build a simple base/limi
>> register device, soon after the 11/20 was released.> ... So an early
>> version of after the original 11/20 port from the PDP-7 had this
>> however.....
> 
> Oh, right, I'd forgotten about that: the KS-11 - I've previously enquired to
> see if anyone had _any_ documentation for this, but so far, nada.

I was looking for that a few years back. Dennis Ritchie's home pages have
some info on this (https://www.bell-labs.com/usr/dmr/www/odd.html).
At the bottom of that page he writes:

""Back around 1970-71, Unix on the PDP-11/20 ran on hardware that not only did not support virtual memory, but didn't support any kind of hardware memory mapping or protection, for example against writing over the kernel. This was a pain, because we were using the machine for multiple users. When anyone was working on a program, it was considered a courtesy to yell "A.OUT?" before trying it, to warn others to save whatever they were editing.
[..snip..]
We knew the PDP-11/45, which did support memory mapping and protection for the kernel and other processes, was coming, but not instantly; in anticipation, we arranged with Digital Special Systems to buy a PDP-11/20 with KS-11 add-on. This was an extra system unit bolted to the processor that made it distinguish kernel from user mode, and provided a classical PDP-10 style "hi-seg" "low-seg" memory mapping unit. I seem to recall that maybe 6 of these had been made when we ordered it.""

My hypothesis is that the very first versions of Unix were using a memory scheme similar to that used in the later LSX and MX derivatives: the kernel resides in lower memory and the user program in upper memory; each process switch implied a swap. Disclaimer: I have not studied the V0 source to verify this hypothesis.

When this topic had my interest I looked for (but did not find) information on what ""the classical PDP-10 style "hi-seg" "low-seg" memory mapping unit"" was. Here my hypothesis would be that in kernel mode mapping was off, and that in user mode there were two segments, each with a base and limit into physical memory -- and that this setup has an echo in how the later KL-11 MMU was used.

Does anyone have an idea what PDP-10 MMU Dennis may have been referring to?

> (the early 'versions' weren't very formal, there was a continuous process of
> change/improvement going on, apparently).
Can't find the reference now, but it is my understanding that this remained the case throughout. The outside world had editions, but inside Bell Labs it was a continuous process. 

>> I believe that this is when "magic
>> numbers" were really introduced so that could be supported.
My understanding is that the first magic number (0407) was present in the earliest PDP11 versions. Apparently, executables were loaded into memory including the header, and control jumped to the first word loaded. This first word then contained a "jmp $+8" to jump over the header. It stayed as a relic until reused to distinguish between regular and pure text binaries. Here, too, I must admit that I have not scrutinized the V0 source to find support for this understanding.

Paul

[TUHS] Unix & Memory Management Units (MMU)

[Earl Baugh]

I can at least shed some light on at least when the Sun boxes supported it
(which may or may not help narrow down the date)
The initial Sun 1/100 multibus machines did not support virtual memory.   I
have one of the last (if not the last) original multibus boards
from Sun with the original PROMs...  and it was supported up to Sun OS 0.7.
   This OS was based off UniSoft UNIX v7.     The 0.7 version was released
in 1982.
In order to support virtual memory systems, there was a board upgrade
required.   Anyone who wanted to go to SunOS 1.0 had to get this board
upgrade (which from what I know, was a board swap... not sure if money
traded hands as well... and is one core reason the original boards are
rare).   The release of Sun OS 1.0 was in November 1983.

So, Sun OS didn't see this until late '83.

Earl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20161207/9d61a124/attachment-0001.html>

[TUHS] Unix & Memory Management Units (MMU)

[Noel Chiappa]

    > From: Clem Cole

    > DEC's Custom Special Systems (CSS) group .. build a simple base/limi
    > register device, soon after the 11/20 was released.> ... So an early
    > version of after the original 11/20 port from the PDP-7 had this
    > however.....

Oh, right, I'd forgotten about that: the KS-11 - I've previously enquired to
see if anyone had _any_ documentation for this, but so far, nada.

    > I would look at Warren's First Edition work to see if there were dregs
    > of this in that code base

Alas, I'd already had that idea (to try and at least re-create a programming
spec, at least, for the KS11). There do not seem to be any traces there,
perhaps because that code came from a document entitled "Preliminary Release
of Unix Implementation", which argues that it's a very early 'version' of V0
(the early 'versions' weren't very formal, there was a continuous process of
change/improvement going on, apparently).


    > It is also noted that the 45 class system (45/55/70/44) had "17th"
    > address bit - i.e.  split I/D space.  I believe that this is when "magic
    > numbers" were really introduced so that could be supported.

No, they came in first for 'pure text' (0410):

  http://minnie.tuhs.org/cgi-bin/utree.pl?file=V4/nsys/ken/sys1.c

which I would expect arrived to minimize swapping on machines with small
amounts of real memmory.

Support for user split-I/D (411) didn't arrive until Version 6:

  http://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/sys/ken/sys1.c

although IIRC split I/D in the kernel was supported supported slightly
before it was in user - although V5 didn't:

  http://minnie.tuhs.org/cgi-bin/utree.pl?file=V5/usr/sys/conf/mch.s

so it couldn't have been much earlier than V6.

	 Noel

[TUHS] Unix & Memory Management Units (MMU)

[Clem Cole]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3269 bytes --]

​below....​

On Wed, Dec 7, 2016 at 11:46 AM, Erik E. Fair <fair-tuhs at netbsd.org> wrote:

> Which is to say, when did Unix run on (and properly use) computers with
> memory management units (MMU)?
>
​Two answers ....   the 11/20 did not have an MMU officially.  ​

​DEC's Custom Special Systems (CSS) group (the same group that spliced an
11/15 disk on to the PDP-7 for Bell Labs) build a simple base/limi register
device, soon after the 11/20 was released.   Ken and Dennis had one of
theses.  So an early version of after the original 11/20 port from the
PDP-7 had this however.....

I would look at Warren's First Edition work to see if there were dregs of
this in that code base to start to try to date it.

As Noel points out the first "official" PDP-11​with an MMU as standard with
it, was indeed the 11/45 (the 11/40 class which included the 35, 60, 34
etc.. came later).  Ken & Dennis got one of the first 11/45s.   It is also
noted that the 45 class system (45/55/70/44) had "17th" address bit - i.e.
split I/D space.  I believe that this is when  "magic numbers" were really
introduced so that could be supported.    I think this is around 3th or 4th
edition.

>
> One imagines that many pointer mistakes (bugs) in assembly or C were
> discovered and squashed in that version, modulo the historical unhappiness
> resulting from address zero containing a zero if dereferenced ("NULL
> pointers") in process address space.
>
> What year did that come about?
>
​Diomidis is incorrect that SunOS was the first Unix to set page 0 to zero.
  This was actually forced by a number of the Unix ports much, much
earlier.   The "NUXI" problem and the Page 0 were two of the issues that
guys that did the port to the IBM Series/1.  I want to say that was 1979 or
maybe 1980 timeframe.   IIRC: that was the Winter Usenix in Boulder CO
("The Black Hole" - conference) when I first remember it being described.

It was a well known issue when many of the 7th edition ports began.   The
problem was the some UNIX application bet in it,   The biggest sinner that
relied on that behavior for the Bourne Shell and how it did memory
management.   Almost every port that could not name page 0 writable and
with a 0 in location, had difficulties with their Unix port, although most
created some strategy to find and fix the issues.

By the time of SunOS, a number of firms were making it page zero and opton,
including BSD itself. By the early 1980s, while I can not claim I invented
it, as I had seen other folks do/talk about it previously at USENIX
conferences, but thought it was a good idea.   So, I had hacked up the CAD
system at UCB's because our team wanted it for debugging some of the codes
we were getting from an unnamed computer company who's OS worked different.
  It was an optional link and not for production, I thought of it as a
debug tool.  I know I gave the hack to Sam at one point, but I do not
remember it making it into the mainline.

But by the mid 1980s, a number of firms made it either standard or an
option like SunOS - because it was a useful debugging tool.

Clem
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20161207/4a8eed75/attachment.html>

[TUHS] Unix & Memory Management Units (MMU)

[Noel Chiappa]

    > From: "Erik E. Fair" <f

    > One imagines that many pointer mistakes (bugs) in assembly or C were
    > discovered and squashed in that version, modulo the historical
    > unhappiness resulting from address zero containing a zero if
    > dereferenced ("NULL pointers") in process address space.

PS: PDP-11 Unix didn't, I think, do much (anything?) to solve the null pointer
problem. (This is for early C versions; I don't know about the later BSD
ones.)

Location 0 was a usable address for both read and write for everything except
'pure-text' (0410 magic word) processes; in those it was only legal for
read. Address 0 mostly did not contain a 0, either; for C programs using the
stock run-time, it contained a 'setd' instruction, except in split I+D
processes, in which case data space location 0 probably (I'm too busy to spin
up my V6 emulator to check) contained some of the program's initialized data
(unless special arrangements had been made).

	Noel

[TUHS] Unix & Memory Management Units (MMU)

[Diomidis Spinellis]

On 07/12/2016 18:46, Erik E. Fair wrote:
> One imagines that many pointer mistakes (bugs) in assembly or C were
> discovered and squashed in that version, modulo the historical
> unhappiness resulting from address zero containing a zero if
> dereferenced ("NULL pointers") in process address space.

I remember Jan-Simon Pendry telling me in the 1980s, that the NULL 
dereference check was first introduced in SunOS with much pain due to 
the resulting crashes. In BSD Unix, which preceded it, the VAX MMU was 
setup with a page in virtual address 0 that would contain the value 0 at 
that address.  (BSD Unix offered memory protection. I assume it had this 
setup for backward compatibility.)

[TUHS] Unix & Memory Management Units (MMU)

[Noel Chiappa]

    > From: "Erik E. Fair"

    > Which version of Unix first ran on a computer with virtual addressing

That would be the first version to run on the PDP-11/45; I'm not sure which one
that was, there's not enough left of Version 2 or Version 3 to see; Version 4
definitely ran on the 11/45:

  http://minnie.tuhs.org/cgi-bin/utree.pl?file=V4/nsys/ken/45.s

    > My guess from a quick look at the history of the DEC PDP-11 is that the
    > target computer was likely a PDP-11/35 or PDP-11/40 with a KT11-D
    > "memory management" module.

No, they came after the -11/45 (with the KT11-C MMU).

    > What year did that come about?

They got one of the first -11/45's, per a Unix history document I'm too busy
to dig up, so 1972.

   Noel

[TUHS] Unix & Memory Management Units (MMU)

[Erik E. Fair]

Which version of Unix first ran on a computer with virtual addressing (address translation) so that a process with non-position independent code (PIC) can be loaded anywhere in RAM that the kernel decided to put it, and memory protection such that no process could accidentally or deliberately access RAM not allocated to it by the kernel (or a SIGSEGV would be delivered to it)?

Put another way, when did Unix processes stop playing Core War with each other? (OK, so long as no more than one is resident at a time, they can't play Core War with each other, but there still needs to be a mechanism to protect the kernel from inadvertent (or advertent) pointer use).

Which is to say, when did Unix run on (and properly use) computers with memory management units (MMU)?

My guess from a quick look at the history of the DEC PDP-11 is that the target computer was likely a PDP-11/35 or PDP-11/40 with a KT11-D "memory management" module.

One imagines that many pointer mistakes (bugs) in assembly or C were discovered and squashed in that version, modulo the historical unhappiness resulting from address zero containing a zero if dereferenced ("NULL pointers") in process address space.

What year did that come about?

By the time I got to Unix (2.8BSD on the Cory Hall DEC PDP-11/70), those features (virtual addresses, memory protection from the kernel) had apparently been part of Unix for a long time - certainly earlier than Version 6.

This is distinct from demand-paged virtual memory which so far as I know was developed on the DEC VAX-11.

	curious,

	Erik <fair at netbsd.org>