Relocating application architecture and compiler support - Page 4

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Re: Relocating application architecture and compiler support

Quoted text here. Click to load it
   ....

followed by an explanation about relocation techniques
for the /360.

Corby wrote a paper
  Corbató, F. J., System requirements for multiple-access, time-shared computers,
  MAC-TR-3, May 1964.

  "It is now clear that it is possible to create a general-purpose time-shared
  multiple access system on most contemporary computers.
  However, it is equally clear that none of the existent
  computers are well designed for multiple access systems...."

essentially explaining why the /360 architecture wouldn't do for
what was becoming the Multics project.  There's a downloadable
version referenced  in the Multicians' bibliography at
  http://www.multicians.org/biblio.html (the paper is image format).

The do-it-yourself relocation scheme caused lots of pain for
more vanilla users too: ultimately the addresses were physically
absolute and the OS doesn't know where the addresses are.
So if the operator wanted to swap something out, it was necessary
to bring it back to the same place.

Base-and-bounds relocation (added as a hack by Boeing, as
Wheeler reported) and of course the 360/67 and later DAT fixed
this.

    Dennis





Re: Relocating application architecture and compiler support
Quoted text here. Click to load it


Yup.  IBM published a most interesting set of articles on the S/360 in
the IBM Systems Journal in 1964.  An article by Gene Amdahl on
"Processing unit design considerations" says on p 147-148 that
relocation hardware was expensive, so they designed the 360's
instruction set with small address displacements in the instructions
to force all addressing to be relative to base registers so you can
relocate programs by changing the base registers.

http://www.research.ibm.com/journal/sj/032/amdahl.pdf

By the following year they'd figured out that didn't work.  In an
article "On dynamic relocation" W. C. McGee, which references
Corbató's report, he covers the various ways to make programs
relocatable and concludes that you need hardware like that in
the just-announced 360/67.

http://www.research.ibm.com/journal/sj/043/ibmsjIVRIIIC.pdf


Re: Relocating application architecture and compiler support
Quoted text here. Click to load it

In the 1974..78 period I developed my own p-code system.  It was
designed to run on at least the 8080, and was largely patterned
after the HP3000 architecture.  Code was loaded in segments, and
those segments were never altered.  Data was stack (and stack
marker) relative.  Unfortunately data could not be moved, due to
the lack of hardware, which was a limitation _on the 8080_.

Code segments limited branching to functions, and the code for
branches, conditional or otherwise, was always self-relative.
Function call was done via a table appended to the segment, and
addressed by table index.  The table entries could be negative,
when they specified a self-relative point within the segment, or
positive, when they contained two fields in 0..127 (leaving a spare
bit).  These described segment number, and an index within that
segments transfer table, and provided for inter-segment calls.
This meant the stack marker on a call had to hold segment and
segment displacement values.

The result was that a segment could be freely moved during any
inter-segment call, and that no more than the single destination
segment needed to be in memory at any one time.  A single system
table indexed by segment number sufficed to keep track of
everything.  A table required 8 bytes per segment for this, and was
fixed in memory.

The system could execute an upper limit of approximately 3 Mbytes
of code using the swapping algorithms (which were independent of
the organization).  For comparison the complete ISO compliant
Pascal compiler occupied about 40 Kbytes.  The same compiler,
compiled to machine code for either the HP3000 or 8086 (MsDos),
occupied about 150 Kbytes, which indicates the compactness of the
actual pcode.

I intended the system to be directly portable to many
architectures.  When the 8088 effectively took over the PC world
circa 1982 I started to port it, but never finished.  The reason
was that there was no need for it in my particular small niche,
which was providing embedded machinery for medical testing, and
revolved around 8080 based hardware I had designed and built.  It
all worked so well that I had no excuse for rebuilding it.  It had
the unfortunate limitation to 64k of data space, barring which it
would be viable today.

--
"If you want to post a followup via groups.google.com, don't use
 the broken "Reply" link at the bottom of the article.  Click on
We've slightly trimmed the long signature. Click to see the full one.
Re: Relocating application architecture and compiler support
(snip)

Quoted text here. Click to load it

One of the reasons for base registers is to keep code size down.
In the days of 24 bit address space on 32K byte machines, it
is not necessary to use 24 instruction bits for each address.

Base plus 12 bit displacement uses 16 instruction bits, and
allows for a variety of different addressing modes using one
addressing model.

1) Absolute addressing within the first 4K.

2) With one base register, addressing within a 4K CSECT
    often including data and code.

3) Indirect addressing by loading an address into a register
    and using that in the instruction.

4) Indexed using the index field of RX instructions, or
    computing the address using other instructions.

To do relocation using base registers would require that the OS
know which registers contained addresses.  There is no hardware
support for that.

-- glen


Re: Relocating application architecture and compiler support
Quoted text here. Click to load it

however, there was one hardware mechanism of getting a value
of the current instruction into a register for addressability
... w/o there having been loaded from some sort of address
constant ... standard convention of
                  
                BALR  R12,0
                USING *,R12

assembler convention and could also be used by compilers.  Normally,
branch-and-link was used for calls to subroutines with the supplied to
branch address ... and at the same time saving the address of where
the call came from. The above sequence was special case of
branch-and-link, where it didn't actually take any branch but did
establish the current address in a register (w/o requiring any address
constant).

a fairly typical os/360 calling convention is something like:

                L     R15,=A(subroutine)
                BALR  R14,R15

or

                L     R15,=V(subroutine)
                BALR  R14,R15

where =A(subroutine) and =V(subroutine) become address constants that
are internal to the program. In standard os/360, address constants are
embedded inside the program and administrative detail is added at the
end of the program which the program loader uses to swizzle all
address constants to their absolute value when the program is loaded.

While the standard hardware didn't provide relocation of base
registers .... it did provide the BALR convention of establishing an
address on the fly w/o requiring (fixed) address constant and it
didn't preclude software conventions that avoided the use of fixed
address constants embedded in the executable image of the code.

TSS/360 created a different type of convention where on entry to a
program, certain registers had preloaded values ... one of the
registers contains a pointer to block of storage outside the
executable code image ... where various things like address constants
were located. The other convention was something like this

                L    R15,=V(subroutine-executablebase)
                AR   R15,R12
                BALR R14,R15

Where R12 contains "executablebase" for situation invoving
displacements larger than 12bits. In os/360 terms, the value
=A(subroutine-executablebase) is an absolute address constant (not a
relocatible address constant requiring swizzle at program load)
.... amd would be the same/constant value, regardless of the address
that the program image was loaded. I used the above convention a lot
in the early 70s for relocable shared segments.

One argument for =V(subroutine) address constant was that there was
effectively "early binding" of the address (performed at program load
time) ... and saved a register (assigning extra register for the
convention) as well as saving an instruction in each calling sequence.

Now there were 360 machines that did have some additional relocation
provided (not the virtual memory kind found in 360/67). System
engineer on boeing account adapted a version of cp/67 (normally using
paged virtual memory) to run on 360/50(?). My understanding is the
360/50 had something that I think was referred to as a DIL instruction
(not part of standard 360 instruction operation) that was used in
conjunction with some emulation packages (7090?) that allowed
specification of base&bound .... basically a base value that the
hardware added to all address calculations and then checked against
the a bound value. This allowed simple contiguous address relocation
(and required swapping of whole address space ... rather than the more
granular paging available on 360/67.

This would be more akin to the current mainframe implementation of
hardware supported virtual machines called LPARS (logical partitions)
where physical memory can be partitioned into logical contiguous
areas. No swapping or paging is supported by the hardware microcode
for LPARs ... just the (relative) static partitioning of available
physical memory. LPARS started out sort of being a significant subset
of the mainframe virtual machine operating system support dropped
into the hardware of the mainframe.

mainframe logical partition getting eal5 certification:
http://www-1.ibm.com/servers/eserver/zseries/security/eal5_ac.html

LPAR support even has extended to non-mainframes:
http://www-1.ibm.com/servers/eserver/iseries/lpar /
http://www-1.ibm.com/servers/eserver/pseries/lpar /
http://www-1.ibm.com/servers/eserver/pseries/lpar/faq_2.html


lots of past posts mentioning LPARs:
http://www.garlic.com/~lynn/98.html#45 Why can't more CPUs virtualize themselves?
http://www.garlic.com/~lynn/98.html#57 Reliability and SMPs
http://www.garlic.com/~lynn/99.html#191 Merced Processor Support at it again
http://www.garlic.com/~lynn/2000b.html#50 VM (not VMS or Virtual Machine, the
IBM sort)
http://www.garlic.com/~lynn/2000b.html#51 VM (not VMS or Virtual Machine, the
IBM sort)
http://www.garlic.com/~lynn/2000b.html#52 VM (not VMS or Virtual Machine, the
IBM sort)
http://www.garlic.com/~lynn/2000b.html#61 VM (not VMS or Virtual Machine, the
IBM sort)
http://www.garlic.com/~lynn/2000b.html#62 VM (not VMS or Virtual Machine, the
IBM sort)
http://www.garlic.com/~lynn/2000c.html#8 IBM Linux
http://www.garlic.com/~lynn/2000c.html#50 Does the word "mainframe" still have a
meaning?
http://www.garlic.com/~lynn/2000c.html#68 Does the word "mainframe" still have a
meaning?
http://www.garlic.com/~lynn/2000c.html#76 Is a VAX a mainframe?
http://www.garlic.com/~lynn/2000f.html#78 TSS ancient history, was X86 ultimate
CISC? designs)
http://www.garlic.com/~lynn/2000g.html#3 virtualizable 360, was TSS ancient
history
http://www.garlic.com/~lynn/2000.html#8 Computer of the century
http://www.garlic.com/~lynn/2000.html#63 Mainframe operating systems
http://www.garlic.com/~lynn/2000.html#86 Ux's good points.
http://www.garlic.com/~lynn/2001b.html#72 Z/90, S/390, 370/ESA (slightly off
topic)
http://www.garlic.com/~lynn/2001d.html#67 Pentium 4 Prefetch engine?
http://www.garlic.com/~lynn/2001e.html#5 SIMTICS
http://www.garlic.com/~lynn/2001e.html#61 Estimate JCL overhead
http://www.garlic.com/~lynn/2001f.html#17 Accounting systems ... still in use?
(Do we still share?)
http://www.garlic.com/~lynn/2001f.html#23 MERT Operating System & Microkernels
http://www.garlic.com/~lynn/2001h.html#2 Alpha:  an invitation to communicate
http://www.garlic.com/~lynn/2001h.html#33 D
http://www.garlic.com/~lynn/2001.html#34 Competitors to SABRE?
http://www.garlic.com/~lynn/2001l.html#24 mainframe question
http://www.garlic.com/~lynn/2001m.html#38 CMS under MVS
http://www.garlic.com/~lynn/2001n.html#26 Open Architectures ?
http://www.garlic.com/~lynn/2001n.html#31 Hercules etc. IBM not just missing a
great opportunity...
http://www.garlic.com/~lynn/2001n.html#32 Hercules etc. IBM not just missing a
great opportunity...
http://www.garlic.com/~lynn/2002b.html#44 PDP-10 Archive migration plan
http://www.garlic.com/~lynn/2002c.html#53 VAX, M68K complex instructions (was
Re: Did Intel Bite Off More Than   It Can Chew?)
http://www.garlic.com/~lynn/2002d.html#31 2 questions: diag 68 and calling
convention
http://www.garlic.com/~lynn/2002e.html#25 Crazy idea: has it been done?
http://www.garlic.com/~lynn/2002e.html#75 Computers in Science Fiction
http://www.garlic.com/~lynn/2002f.html#6 Blade architectures
http://www.garlic.com/~lynn/2002f.html#57 IBM competes with Sun w/new Chips
http://www.garlic.com/~lynn/2002n.html#6 Tweaking old computers?
http://www.garlic.com/~lynn/2002n.html#27 why does wait state exist?
http://www.garlic.com/~lynn/2002n.html#28 why does wait state exist?
http://www.garlic.com/~lynn/2002o.html#0 Home mainframes
http://www.garlic.com/~lynn/2002o.html#15 Home mainframes
http://www.garlic.com/~lynn/2002o.html#16 Home mainframes
http://www.garlic.com/~lynn/2002o.html#18 Everything you wanted to know about
z900 from IBM
http://www.garlic.com/~lynn/2002p.html#4 Running z/VM 4.3 in LPAR & guest v-r or
v=f
http://www.garlic.com/~lynn/2002p.html#40 Linux paging
http://www.garlic.com/~lynn/2002p.html#44 Linux paging
http://www.garlic.com/~lynn/2002p.html#54 Newbie: Two quesions about mainframes
http://www.garlic.com/~lynn/2002p.html#55 Running z/VM 4.3 in LPAR & guest v-r
or v=f
http://www.garlic.com/~lynn/2002q.html#26 LISTSERV Discussion List For USS
Questions?
http://www.garlic.com/~lynn/2003c.html#41 How much overhead is "running another
MVS LPAR" ?
http://www.garlic.com/~lynn/2003f.html#56 ECPS:VM DISPx instructions
http://www.garlic.com/~lynn/2003.html#9 Mainframe System
Programmer/Administrator market demand?
http://www.garlic.com/~lynn/2003.html#14 vax6k.openecs.org rebirth
http://www.garlic.com/~lynn/2003.html#15 vax6k.openecs.org rebirth
http://www.garlic.com/~lynn/2003.html#56 Wild hardware idea
http://www.garlic.com/~lynn/2003k.html#9 What is timesharing, anyway?
http://www.garlic.com/~lynn/2003l.html#12 Why are there few viruses for
UNIX/Linux systems?
http://www.garlic.com/~lynn/2003l.html#41 Secure OS Thoughts
http://www.garlic.com/~lynn/2003m.html#32 SR 15,15 was: IEFBR14 Problems
http://www.garlic.com/~lynn/2003m.html#37 S/360 undocumented instructions?
http://www.garlic.com/~lynn/2003n.html#13 CPUs with microcode  ?
http://www.garlic.com/~lynn/2003n.html#29 Architect Mainframe system -
books/guidenance
http://www.garlic.com/~lynn/2003o.html#52 Virtual Machine Concept
http://www.garlic.com/~lynn/2004b.html#58 Oldest running code
http://www.garlic.com/~lynn/2004c.html#4 OS Partitioning and security
http://www.garlic.com/~lynn/2004c.html#5 PSW Sampling
http://www.garlic.com/~lynn/2004d.html#6 Memory Affinity
http://www.garlic.com/~lynn/2004e.html#26 The attack of the killer mainframes
http://www.garlic.com/~lynn/2004e.html#28 The attack of the killer mainframes
http://www.garlic.com/~lynn/2004f.html#47 Infiniband - practicalities for small
clusters
http://www.garlic.com/~lynn/2004g.html#15 Infiniband - practicalities for small
clusters
http://www.garlic.com/~lynn/2004k.html#37 Wars against bad things
http://www.garlic.com/~lynn/2004k.html#43 Vintage computers are better than
modern crap !
http://www.garlic.com/~lynn/2004m.html#41 EAL5
http://www.garlic.com/~lynn/2004n.html#10 RISCs too close to hardware?
http://www.garlic.com/~lynn/2004o.html#13 Integer types for 128-bit addressing
http://www.garlic.com/~lynn/2004o.html#32 What system Release do you use...
OS390? z/os? I'm a Vendor S
http://www.garlic.com/~lynn/2004q.html#18 PR/SM Dynamic Time Slice calculation
http://www.garlic.com/~lynn/2004q.html#72 IUCV in VM/CMS


--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn /

Re: Relocating application architecture and compiler support

Quoted text here. Click to load it



But once you do that it can't be relocated without knowing which
registers contain addresses.


(snip)

Quoted text here. Click to load it



This reminds me of the way Macintosh OS used to work.  (Does it
still do that?)   Fortunately I never wrote any low level Mac
code, but you had to be careful when things could be relocated,
and not store addresses across system calls that could move
things around.

In the code above, you can't move things around between the AR
and the BALR.  The original mac didn't do preemptive
multitasking, so the user program always knew when things could
move and when they couldn't.

On the other hand, for a system like 680x0 with separate address
and data registers, maybe it isn't so hard.

-- glen


Re: Relocating application architecture and compiler support
Quoted text here. Click to load it

the displatcher, scheduler, page replacement, etc for cp/67 ... a lot
of it as undergraduate ... which was shipped in the standard product.
a lot of this was dropped in the morphing of cp/67 into vm/370 ... but
I got to put it (and a lot of other stuff) back in when i did
the resource manager for vm/370
http://www.garlic.com/~lynn/subtopic.html#fairshare
http://www.garlic.com/~lynn/subtopic.html#wsclock

because cp/67 (and vm/370) had virtual memory support ... each user
had their own virtual address space ... where pages could be brought
in and out of real storage at arbitrary real addresses.

the problem i had in the early 70s with location independent code ...
was that i wanted to be able to page-map applications to files on
disks ... and that multiple different virtual address spaces could
share the same exact (r/o) page-mapped information.

the problem with the standard os/360 model was that when executable
files out on disk were mapped into memory (virtual or real), the
program loader had to run thru arbritrary locations in the executable
image ... swizzling arbritrary address constants into different values
(randomly spread thruout the executable image).

as a result, it wasn't just a simple matter of page mapping an
executable image file (out on disk) into a virtual address space
... there was still all this address constant swizzling that had to be
done before the program could actually start execution. Furthermore,
the default was to touch every possible page that potentially
contained an address constant (that concievably might be used
... whether it actually was used or not) and do the appropriate
swizzling operation. And even further complicating the process was
that the swizzling operation went on within the specific virtual
address space that had just mapped the executable image.

So the swizzling operation that would go on in each virtual address
space ... pre-touched and changed an arbritrary number of virtual
pages (whether the actually application execution would touch those
specific pages or not) ... as well as making the pages chnaged
... defeating the ability to have the program image mapped into r/o
shared segments that were possibly common across a large number of
different address spaces. The issue that i was trying to address
wasn't what might be in the registers of each individual process
context in each virtual address space .... it was trying to make the
physical executable storage image of the application r/o shared
concurrently across a large number of different address spaces.  Any
modification required on the contents of that executable image,
defeated the ability to have it r/o shared concurrently across a large
number of different address spaces (as well as possibly prefetching
and changing pages that might never actually be used).

So that was the first problem.

A subset of the relocating shared segment implemention (that I had
done in the early 70s) was picked up by the product group and released
under the feature name as DCSS (DisContiguous Shared Segments). I had
done a page mapped file system along with the extended shared segment
support ... so that it was relatively straight-forward to page map
objects in the file system into virtual address spaces. The page
mapped file system wasn't part of the subset of stuff that was picked
up for DCSS. random posts on the page mapped file system work
http://www.garlic.com/~lynn/subtopic.html#mmap

They addressed the address constant swizzling problem by defining
globally unique system addresses for every application that would
reside in predefined virtual memory segments; loading the application
at that predefined virtual memory location and saving the virtual
address space image to a reserved portion of the system-wide paging
system (in part because they had failed to pick up the page mapped
filesystem enhancements).

So DCSS had a new kind of system command that would map a portion
of a virtual address space to a presaved application image (and
specify things like shared segments, etc).

So there were several limitations ... one it required system wide
coordination of the presaved applications as well as system privileges
to setup stuff (i.e. individual department couldn't enable their own
private applications).

A large installation would have more applications defined in this
infrastructure than could fit in a single 16mbyte virtual address
space ... and as a result, there had to be careful management of
applications that were assigned conflicting predefined, preswizzled
virtual addresses. While no single user was likely to try an map all
possible applications into a single address space at the same moment
... it was possible that a single user might need to map an arbritrary
combination of applications (in total less than 16mbytes), some of
which may have conflicting, pre-assigned and swizzled virtual address
images. As systems got bigger with wider variety of users and
applications, the problem of pre-swizzled virtual application images
with conflicting virtual address locations increased.

So the next solution was to have multiple pre-swizzled application
images defined at multiple different virtual address location. Users
would decide on the combination of page image applications and
libraries that needed to have concurrently loaded ... and try and find
some possible combination of the multiple different images of each
application that could comfortably co-exist in the same address space.

The original implementation that i had done from the ealy 70s ...  had
allowed page mapping arbitrary files as virtual address apace images
at arbitrary virtual address locations .... w/o needing to swizzle
address constants embedded in those page mapped images ...
in part because I had both done a lot of work on allowing address
location independent executable images
http://www.garlic.com/~lynn/subtopic.html#adcon
as well as page mapped filesystem enhancements
http://www.garlic.com/~lynn/subtopic.html#mmap

and furthermore that an executable image could occupy a read-only shared
segment ... were the same exact same pages were mapped concurrently
into multiple different virtual address spaces ... at possibly
different virtual addressses.

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn /

Re: Relocating application architecture and compiler support

so tss/360 had page mapped filesystem as standard and an objective
that a portion of virtual address space could be mapped to the
executable image out in the filesystem ... and that the mapping
process didn't have to track thru arbritrary virtual pages of that
executable image ... swizzling address constant. The system could do
the mapping and start program execution (almost) immedately ...
possibly w/o having to prefetch any of the executable image.

furthermore, if other address spaces were already sharing that
executable image on a r/o basis ... the mapping process would just
setup the segments so the different address spaces utilized the same
virtual pages.

so tss/360 had system wide convention ... assembler, applications,
compilers, etc ... that positioned any address constants that needed
swizzling separately from the executable image. This separate table of
address constants needing swizzling would be prefetched (as part of
mapping the executable file to the virtual address space) and the
necessary swizzle of address constants could be done in a private area
for each specific virtual address space. There then were system wide
conventions on how executable code accessed the table of (swizzled)
address constants .... the executable code image could be exactly the
same for all virtual address spaces ...  and in fact, the same exact
executable image could be the same exact virtual pages (using shared
segments) .... but the swizzled address constants would be located in
an (tss/360 system-wide convention) area separate from the executable
program image.

--
Anne & Lynn Wheeler | http://www.garlic.com/~lynn /

Site Timeline