From: burley@churchy.gnu.ai.mit.edu (Craig Burley)
Newsgroups: comp.os.linux
Subject: Re: GCC2.1 (Wonderful !)
Date: 17 Apr 92 07:43:12 GMT
	<1992Apr15.015254.25547@ucc.su.OZ.AU>
	<1992Apr15.151509@hammer.Prime.COM>
	<1992Apr16.102220.3952@colorado.edu>
	<1992Apr16.230809.28737@ux1.cso.uiuc.edu>
Organization: Free Software Foundation 545 Tech Square Cambridge, MA 02139
In-reply-to: jplevyak@ncsa.uiuc.edu's message of 16 Apr 92 23:08:09 GMT

In article <1992Apr16.230809.28737@ux1.cso.uiuc.edu> jplevyak@ncsa.uiuc.edu (John Plevyak) writes:

   As I remember (from long ago) the Primos (the Prime operating system)
   replaced all dynamic calls with calls to illegal addresses.  

Specifically, I believe the linker did the replacing when building a program
image file (EPF or old-style) -- so the file had pointer-faulted references
to dynamic links (remove the "pointer-fault" bit in the pointer and you have
a pointer to a CHAR(*) VARYING string having the name of the routine needed.

   A table in
   the image mapped the index of the illegal address to a filename/symbol
   pair.  The filename was found or loaded and the address was patched.  This
   has the advantage that you could dynamically replace the library without
   relinking (the linker was in the OS).  This could be used on a 386 class
   machine.

Well, you have to make sacrifices to do this on a 386 that you couldn't make
on Prime 50 series machines.  Specifically, all 50 series machines had only
one general format for indirect pointers that imposed the pointer-fault, ring,
and extension bits on all such pointers.

The flat-address model for the 486 allows a task to address all 4 gigabytes
representable by a 32-bit pointer.  In this form, dynamic linking is still
possible but adds an expense to each unsnapped pointer -- unless you reduce
the accessible space to 2GB by allocating one bit as the "fault" bit (so the
unfaulted version points to a string) or some such thing, you need more
memory for each faulted pointer.

The segmented pointers of the 486 (48-bit pointers) offer slightly more
opportunity for providing Prime-style unsnapped pointers without significantly
infringing on the overall accessible space in a program, I think.  For example,
(and I'm just guessing here, after only reading the 486 arch manual once),
two segment numbers could be reserved to "unsnapped pointer to name in CS
seg space" and "unsnapped pointer to name in DS space" or some such thing.

But the lack of an explicit "fault" pointer means 486 OS architects do have
to make a tough choice when deciding on how to provide dynamic linking (the
"true" kind -- it's still quite easy to do the semi-dynamic kind that VMS
does, where all unsnapped pointers are snapped by the OS when an executable
is mapped to memory).

   The disadvantages were:

	   1) your program could suddenly fail if the new library (installed by
		   someone else) had a bug

Yes, but it taught most of us Prime OS and library engineers to get our act
together, since even our pet programs would break if we screwed up a new
library install even before we'd relinked the programs!  I.e. this might
really be an advantage overall.  It teaches people to treat library changes
and testing more like they're doing OS work than doing single-program work.

	   2) you could not page directly off the executable

Either I misunderstand you or this is wrong.  EPFs were directly paged into
memory as needed (that is, the "text" or code-space portion).  PRIMOS generally
had pointers (especially unsnapped ones) in read/write segments (pointed to
by the Link Base, LB%) along with ECBs (procedure Entry Control Blocks) and
such.  So, normally, changing these things to accommodate the latest placement
of a newly invoked EPF (program/library) didn't require changing pure code,
so that code could be paged in on demand, making startup potentially quite
fast.  Some applications required pointers and ECBs to be placed in pure code
to improve shareability, but naturally this meant things they pointed to had
to be statically placed (typically in system-wide shared and unshared segments
rather than per-user shared/unshared segments), so they don't really count
in this discussion.

Sheesh, it's been a long time since I've thought about this stuff.  If I
screw it up, Kevin Cummings will likely correct me, since he probably knows
far more about it than I do (and as I recall, knew more back when I was still
at Prime)!

	   3) your operating system was forced to intervene on  the first of
		   every dynamic call... thus slowing startup time.

Mmm, maybe, I'd say the penalty wasn't so much slower startup time, but
slower execution of newly reached paths with the payoff often being _faster_
startup time.  PRIMOS might not have to even read much of the program in
at all, just some LB%-relative stuff to adjust pointers and ECB link-segment
numbers for the user's particular segment placement.  If the program was
already shared (mapped) via either another user or a recent invocation of
the same program by the same user, that'd be very little time.  It might be
that a comparatively few link-snaps later, the user'd get a useful response
(like a prompt), faster than the old way of having to block-read a monolothic
program entirely into a static place in memory (and with more flexibility than
the latter).

Problem was, if the user issued a command, it might well involve hundreds or
thousands of new link-snaps (dynamic links not yet resolved), so _that_
command's first invocation would be slower than subsequent invocations.

The idea was that amortizing the cost of loading and linking across the
entire execution of the program would often cut down on the need to snap
many links at all, since (particularly for large monolothic apps, like SPSS)
users typically wouldn't invoke all the code in the program per invocation.
So it was actually expected to be practical for a user to frequently invoke
a large monolothic app just to do a quick command or two.  Of course, that
was based on assumptions regarding user interaction that are increasingly
coming into question today for at least some popular application domains.

Still, thinking about designing an OS for the 486 causes me to weigh a lot
of interesting questions, like: should a given task be able to stack
multiple programs in arbitrary places (segments) in its memory space as
PRIMOS permitted (with EPFs but not with old-style static images), given an
OS that permits cheap tasks?  I.e. is the cost of allowing arbitrary placement
of programs in per-task virtual memory worth the benefit, when an alternative
(cheap processes) is available?  Can it be provided in a manner that costs
non-users of the feature very little?  (My guess: no.)

Also, whether to provide access to segments in a 486 OS (instead of the
highly convenient flat-4GB-space model people expect coming from VAXland)
is a sticky question, because _lots_ of people want the flat memory model,
but the segmented model _does_ offer advantages.  Problem: on the 486, the
pointer formats are different, so what does providing _both_ models cost in
terms of the OS interface -- i.e. do you need two sets of OS calls?

   The advantages were:
	   1) no need to relink shared library programs
	   2) no need to link to libraries that this execution of the program
		   did not require... finer grain linking could be a win here.

I wonder how useful #2 has been in practice in the PRIMOS world.  PRIMOS
provided not just dynamically linked libraries, but statically linked ones
as well (and the PRIMOS entry points essentially belonged in the latter
category).  This meant that any library you expected to be occasionally
invoked for a "quickie" but that was inherently large, you could just make
static in your system, so the only cost was the link-snap cost (name-space
search, snap pointer, continue) but no library-loading cost.

   In general I don't think that you will find an obvious clean and simple winner
   in a war of dynamic linking strategies if you ask more that a few people.

That's for sure.  A lot of the answer depends on the question -- if you want
big monolithic apps that use a variety of big libraries but not necessarily
all of them each time the apps are run, the PRIMOS approach is probably quite
good.  I don't know if most UNIX apps fall into this area; either the apps
are short and sweet (tools, filters, etc) or monolithic with little use of
multiple shared libraries (EMACS comes to mind).

Note that one of the ideas of shared libraries under PRIMOS was that they would
be the primary means for providing services, such as electronic mail, remote
file transfer, queueing, etc.  Under UNIX, these services are typically
provided by separate processes, accessed through IPC via tiny libraries for
apps to just get at the IPC stuff (X follows this model, for example).
Sharing tiny libraries isn't as important as sharing the X server code, which
if you'd talked to the PRIMOS architects back when dynamic linking and
libraries were being designed, would have felt should go into shared
libraries and used shared memory and semaphores to do the display management
and IPC between server tasks.  (I have always felt the server model was better
than the shared-memory model, but couldn't convince the PRIMOS architects
otherwise back when the issue was being decided for most subsystems in
1978/1979.  Nevertheless, the resulting dynamic-linking model seems to be
well-suited for the shared-library-service model, whether or not you like
that latter model.)

Point being that for what "we" want to do in UNIX, and what I am thinking of
doing in my OS research and design, PRIMOS' dynamic linking may provide good
lessons but not necessarily a good model.  It _does_ stretch ones' thought
a bit, though.

   The simplest solution is usually the best though, and (not intending to start
   a war here) while Primos did dynamic linking which was nice, the lack of
   child processes, memory protection of 'shelled' programs, the segmented
   architecture, system calls with a mix PL1/G and FORTRAN interfaces and assorted
   other goodies made me wish for Unix with or without dynamic linking
   (perhaps it has changed, this was 1986).

I last "knew" PRIMOS at rev 19.4 in 1985, which is why I refer to it in the
past tense; I don't know how much it has changed.  I agree with the
disadvantages you cite, except that I am unwilling to categorically state
that segmented architecture is bad (yes, it's hard, but it offers wonderful
optimization opportunities at the hardware/microcode level from what I can
tell, and also offers higher bit-efficiency for instructions in memory; I
don't think these advantages translate well to RISC, however).  The lack of
memory protection between programs in the same task (stacked programs) was
sometimes a pain, but the segmented architecture _itself_ mitigated this
significantly (i.e. programs didn't tend to just run off one segment into
another, because the necessary pointer arithmetic was rarely implemented
except when an array was known to span segments, itself a rare condition,
and in any case getting _contiguous_ arrays wasn't always possible).  So
though it may have happened occasionally, I don't remember having to chase
down any inter-program-stomping bugs like we all do under Mac or DOS or
similar (PC-like) OSes; similarly, the stack being in separate segments (and
separately managed by the OS) also allowed certain bugs to be caught much
earlier than in a typical flat-model OS (though a paging OS can help provide
almost as early detection of stack overflows as did PRIMOS' segmented
model).

Sigh, I _am_ rambling -- must be late, and I must not want to get any real
work done!  :-)
--

James Craig Burley, Software Craftsperson    burley@gnu.ai.mit.edu
Member of the League for Programming Freedom (LPF)
Newsgroups: comp.os.linux