I did not have a lot of time to work on documenting the evolution of paging / virtual memory code in 32V, Sys III and early SysV in the past months, but I did get some more background information that seems worth sharing.
My understanding of the virtual memory story at USG is now as follows:
Somewhere in 1981/82 a project plan for Unix 5 / System V was made and evolving John Reiser’s virtual memory code for 32V-r3 was part of that plan. “Evolving” in this context meant making it more maintainable and more hardware independent. John’s code assumed a memory page, a disk block and a file block all to be the same size, and it needed to be more general. It was also designed around the VAX MMU and this too needed to be generalised. The person assigned to that job was Bob (Robert) Baron, reporting to Tom Raleigh. The project involved quite a bit of re-architecting and progress was slowish. On top of that Bob left for CMU to work on Mach. Tom Raleigh tried to pick up where Bob had left off, but progress remained slowish.
In parallel, Keith Kelleman and Steve Burroff were working on Unix for the 3B20 Unix. They did paging code from scratch around the 3B20 MMU (which used a more or less ‘modern’ page table design) and developed their idea for the “regions” abstraction to support large, non-contiguous address spaces. It seems that they built on the main working set ideas/concepts in the Reiser/Baron/Raleigh code base, combined these with their “regions” idea, made it multi-processor capable and made it all work on the 3B20. Around that time Tom Raleigh seems to have transferred to Bellcore, and the VAX code base got orphaned.
Two young engineers appear to have picked up the work on the VAX code base: Dean Jagels and Jim McCormick. My understanding is that they essentially back ported the 3B20 work to the VAX, falling back on the Reiser/Baron/Raleigh work where necessary. They got it working, and as far as I can tell, this is what got released in 1984 as part of SysV R2.4 for the VAX (the oldest surviving source code for this that I could find).
This somewhat tortuous birth may in part explain why Research chose to use the 4BSD virtual memory code for 8th edition.
> From: Bakul Shah
> My impression is that there is much less traffic on pretty much all the
> mailing lists I am on and I am wondering why.
Ukraine? That's certainly been absorbing a lot of my attention (but it
seems like it's going to go on for quite a while now).
Noel
> From: Warren Toomey
> Just checking that the TUHS list hasn't gone belly up, as it's been
> pretty quiet for a week :-)
Thank goodness!
That's one way to improve the S/N ratio.
Noel
> From: Clem Cole
> I'm thrilled to see the 11 kept alive.
Ditto. The most elegant archtecture ever, IMO.
> I was under the impression ??Ken?? had created them for B
> independently (which, of course, was first on the PDP-7).
"The Development of the C Language", by Dennis M. Ritchie:
https://www.bell-labs.com/usr/dmr/www/chist.html
says:
The PDP-7, however, did have a few `auto-increment' memory cells, with the
property that an indirect memory reference through them incremented the cell.
This feature probably suggested such operators to Thompson; the
generalization to make them both prefix and postfix was his own. Indeed,
the auto-increment cells were not used directly in implementation of the
operators, and a stronger motivation for the innovation was probably his
observation that the translation of ++x was smaller than that of x=x+1.
Note the "probably"; unless Ken remembers, and says something, that's
probably the best we are going to get.
> I did not think the PDP-7 ISA includes addressing modes in the same
> manner as the 11. .. I thought PDP-7 is a very simple instruction (and
> small) with an AC, Link/Indirection and a PC - it reminded me of the
> PDP-8 more than anything else
The PDP-4, -7 and -9 are all the same architecture (very similar to the
PDP-1, but simplified a bit), differing only in implementation. (Most PDP-7
code will run on a -9, un-modified.) Basic instructions look like:
Instructions had a 4-bit opcode ('000'-'054'), 1 bit of indirect, and 13
bits of address. It was a load-store architecture, with a single accumulator.
So, yes, similar to an -8. There are other opcodes for non-memory operations
('074' opcode), and I/O ('070'), using bits in the 'address' field. ('060'
opcodes were for the optional EAE.) All of the -4/-7/-9 had the
'auto-increment on locations 010-017' when indirecting through them' feature.
Bitsavers has fairly complete docs on them all:
http://www.bitsavers.org/pdf/dec/pdp4/http://www.bitsavers.org/pdf/dec/pdp7/http://www.bitsavers.org/pdf/dec/pdp9/
Noel
> From: "Nelson H. F. Beebe"
> there is a nice compact history of the PDP-11 and early Unix at this
> new article:
Not a bad artcle, but it had a number of minor errors, which I found irritating.
They should have gotten an expert to proof it.
Here are some:
registers could access any other register - as well as memory or direct
data - using one of the six different addressing modes
I think 'instruction' may have been meant for the first "register"; as
written it makes on sense. (Unlike the PDP-10, in the PDP-11, a register
can't address another register.) Oh, and there are eight addressing modes.
use of labels instead of hard-coded addresses makes it easier to
program and makes the code relocatable in memory
I'm not sure whether the writer knows the difference between 'PC-relative
addressing' (a PDP-11 feature; code that will run at any address, without
_any_ changes to the binary) and 'relocatable binary (which uses labels, as he
describes). - but is not PDP-11 specific.
The program counter can be accessed like any of the other registers ... The
program counter is intended to support jump, branching, and other control
flow instructions.
Uh, no. It's not clear _exactly_ what was meant here, but... having the PC as
a general register is for PC-relative addressing of operands, immediate data,
and absolute addressing of operands. Jumps, branches, etc don't use the fact
that the PC is a general register.
These are the key advantages of assembly programming over high-level
languages - assembler code always runs faster and uses less memory.
Not really, with modern compilers.
The number above represents -2.
A commenter caught this one.
Just use a $ to represent a decimal number
In UNIX assembler, "$" means 'immediate data'; a trailing
"." means decimal.
And a tip of the hatly hat for getting this:
Although the ++ and - operators in C are equivalents of DEC and INC
instructions, they were inspired by an addressing mode in the PDP-7.
right.
Noel
Although the story is well known to members of this list, there is a nice
compact history of the PDP-11 and early Unix at this new article:
A brief tour of the PDP-11, the most influential minicomputer of all time
https://arstechnica.com/gadgets/2022/03/a-brief-tour-of-the-pdp-11-the-most…
It describes PDP-11 assembly language, and shows the booting of a Unix
system on a simh instance. It also includes the famous picture of
Dennis and Ken at a PDP-11 console, and concludes with a link to an
online text of a book about PDP-11 assembly language programming.
-------------------------------------------------------------------------------
- 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/ -
-------------------------------------------------------------------------------
I am reading some UNIX text processing books and am interested in the
lineage of Documenter's Workbench.
I see documentation of 1.0 (i.e
https://archive.org/details/sysv-dwb/page/n5/mode/2up)
I see a copy of 2.0 for 3B2 (i.e.
https://archives.loomcom.com/3b2/software/Documenters_Workbench/)
>From there things get a little less clear, it seems like we jump to
3.2 with SysVR3.2?
Then there is a 3.3 version https://github.com/n-t-roff/DWB3.3
One of my books from the late 80s references 3.4 available as a source
code purchase independent of UNIX.
Then it appears SGI might have had a 4.x strain? (i.e.
https://archive.org/details/sgi_Documenters_Workbench_4.1.3)
Heirloom is derived from OpenSolaris which is derived from?
Can anyone firm this lineage up a bit; and is 4.x an SGI thing or what
(I extracted the image, the relnotes inside might as well not exist).
Regards,
Kevin
> On Mar 12, 2022, at 2:02 PM, Rob Pike <r(a)golang.org> wrote:
>
> Indeed. Be careful about the code Numerical Recipes if you are doing
> important numerical work.
> For simple stuff it's fine, of course, but floating point is a
> minefield that requires expert navigation.
>
> -rob
That's the seductive trap of floating-point numbers, isn't it? They invite us to think about them as if they were the real numbers, but they are very, very much *not* the real numbers. And yet, most of the time, for most applications, if you treat them as if they were, you get plausible results.
Adam
Hello,
I'm trying to understand a quirk in 32-bit x86 code generation conventions:
on Linux, when returning a structure from a function by value:
struct S {
int i, j;
};
struct S f(int x)
{
return (struct S){x, sizeof(void*)};
}
the caller reserves space for the returned structure and passes a pointer
to that space as an 'invisible' extra argument, which is prepended to
the argument list; the callee returns this pointer (although the caller
knows it anyway); it's as if the function is transformed to
struct S *f(struct S *ret, int x)
{
ret->i = x;
ret->j = sizeof(void*);
return ret;
}
with one essential difference: the function 'f' itself is responsible for
popping the extra argument off the stack (the 'x' argument is popped by
its caller).
This necessitates using the return-with-immediate ('ret 4') instruction
instead of the normal 'ret'; this is the only instance where this variant of
the 'ret' instruction is used in code generation for C programs on Linux
normally.
I wonder how this exception came to be.
Early versions of GCC (e.g. gcc-1.27) did not implement this convention, i.e.
the caller was responsible for popping the invisible pointer similar to the
normal arguments. The "callee-pops" variant was implemented later for
"compatibility with other compilers", and the option that controls this is
called -fpcc-struct-return, which also disables returning small structures in
registers (in the example above GCC would return the value in EDX:EAX register
pair).
Operating systems differ on following this convention. For example, FreeBSD
and OpenBSD do not, and neither does Windows.
Looking at 386BSD tree in unix-history-repo, I see that it used GCC, not PCC.
Where can I look at the history of x86 code generation development in PCC?
Do I understand correctly that i386 code generation in PCC evolved in parallel
with GCC, and at some point GCC was convinced to adopt the (less efficient)
PCC calling convention by default?
Did PCC prefer to do this stack adjustment for the invisible pointer on the
callee side for some other platform, and the behavior was merely carried over
to the i386 port?
Thank you.
Alexander
