9

The OS/360 link editor was, according to Brooks (OS/360 project manager): "one of the finest overlay facilities ever built." "It allows overlay structuring to be done externally, at linkage time, without being designed into the source code" (my emphasis) (in his The Mythical Man Month - a true classic work on software engineering).

How exactly was this magic done?

(And he also said, BTW: "Yet it is also the last and finest of the dinosaurs, for it belongs to a system in which multiprogramming is the normal mode and dynamic core allocation the basic assumption.")

1 Answer 1

11

How did the OS/360 link editor achieve overlay structuring at linkage time without annotations in the source code?

By getting them as well external in form of control statements?

Mainframe programs usually don't get (all) their steering from command line parameters but read one or more control statements (CS) telling them what to do. Usually this comes from the command input, but can be redirected from some file as well.

In case of the linker those CS tell what to link and how.

And I would assume this is what your question is about. While a source contains external references, it does not contain how those references are to be satisfied and in which order - this is done by the CS for the linker, thus external to the source.

The OS/360 link editor was, according to Brooks "one of the finest overlay facilities ever built."

A wise man. It is a very simple and straight forward program with a surprising simple structure, but incredible mighty.

"Yet it is also the last and finest of the dinosaurs, for it belongs to a system in which multiprogramming is the normal mode and dynamic core allocation the basic assumption."

Again, he knows what he talks about - Since my real programming career started in a /360 environment, I never learned otherwise and still today have a hard time to understand how programmers can believe a machine is theirs and only their program and only the actual function is active at a given time.


[Not sure if I understand that right - being maybe a bit too much of an /360 man and the issue too basic to see it - what above describes is what commonly named linking. Nothing more, nothing less. So please excuse if this goes astray]


So, how does it work?

A straight forward process:

  • A source gets translated (compiled) yielding an object module
  • An object Module contains an
    • ESD (External Symbol Directory) with all external references as well as all entry names and a
    • RLD (Relocation Directory) holding all relocation information
    • (And of course, all code/data).
  • The linker gets one or more object modules handed via control statements (command to the linker)
  • Optional (well, practically always) one or more module libraries (*1)
  • He starts resolving all references in all given modules against each other in sequence given and against the libraries.
  • The result of that process is a load module
  • A load module is technically the same as an object module so it may still have unresolved references.
  • The loader will either resolve those or abort if not able to do so.

For such a linking the 'script' controlling the linker may look like this (*2):

//LKED    EXEC  PGM=IEWL
//MODLIB  DD    DSNAME=OBJLIB,DISP=(OLD,KEEP),
//SYSLIN  DD    *
ENTRY BEGIN
INCLUDE MODLIB(MODA,MODB)
INCLUDE MODLIB(MODC,MODD,MODE)
/*

All modules to be linked (MODA..MODE) are named in control statements to the linker including the symbolic name (MODLIB) for the library where they are stored. So far all gets linked into one load module. Now if this is supposed to structured in overlays (*3) OVERLAY cards (*4) are added

//LKED    EXEC  PGM=IEWL,PARM='OVLY'
//MODLIB  DD    DSNAME=OBJLIB,DISP=(OLD,KEEP),
//SYSLIN  DD    *
ENTRY BEGIN
INCLUDE MODLIB(MODA,MODB)
OVERLAY ONE
INCLUDE MODLIB(MODC)
OVERLAY ONE
INCLUDE MODLIB(MODD,MODE)
/*

Now it creates three load modules:

  • one containing MODA+MODB,
  • one containing MODC and
  • one containing MODD+MODE

All the "magic" happened in an instant. Except, there was none. All the work how to decide which module has to go into which overlay was still up to the programmer. I remember the (Assembler?) manual having a lengthy chapter how one may draw a path diagram (which module calls which other module) and then encircle potential groups of modules to define overlays. Essentially one would work down- and up-path to find potential issues and so on.

The linker helped in so far as it provided detailed listings about unresolved references as well as combined sizes, so one could easy see not only how large the overlay area had to be but as well where there was room left for balancing.

In real world applications this was usually not that hard of a task, as most were transaction orientated. so there was one overlay area for the actual transaction and maybe optional multiple others for library functions needed. So linkage was rather straight forward.


*1 - Libraries are like an archive of object modules (*5), so instead of having many sub directories to store each package to be linked with, one packs them a library and Link (and the library manager) cares about organisation. Beside being less confusing, it works great on file systems that do not support directories at all - yes, such exists(*6).

Depending on storage structure module libraries could speed up linking a lot by creating a common directory of all symbols(*7). Doing so the linker did not have to scan every module for a possible match but get it across all content in a single access - it wouldn't be wrong to think of them as code databases that can be queried for functions and entry points.

*2 - From memory, may miss lots of necessary details.

*3 - Remember, the Mainframe we have may feature a whopping 64 KiB RAM total, so overlays are quite useful when we pass the Hello-World level.

*4 - Yes, lines in a script, or records in a file are still today called cards.

*5 - In the mainframe world libraries are not only for object modules but made to hold next to any (standard) file type.

*6 - Libraries were the go-to solution before sub directories became a thing. An application with all it's files could be nicely packed into a library, distributed and used without polluting the file system - in some way we have closed the circles by various OS inventing their ways of distribution as a single package (Win, Android, etc.)

*7 - Interestingly MS did follow that scheme with their programming toolchain. The .LIB format consists of a book keeping header, a sequence of object modules and an attached symbol directory holding all declared entry points of all modules within. That way LINK had only to read that directory to find functions it was looking for.

That was at least during DOS time with LINK being able to link against library files and LIB being included as library manager. Not sure how much is still supported - or replaced by some bloaty reinvention.

14
  • 2
    Including example control statements is very helpful, thanks! Will read in detail in a bit ...
    – davidbak
    Jun 27, 2023 at 19:49
  • 4
    A similar scheme was used on the PDP-11; see Chapter 5 in the Task Builder manual. A description of the overlay structure, using the Overlay Description Language, is part of the input to the Task Builder ('linker' in other terminology).
    – dave
    Jun 27, 2023 at 21:35
  • 1
    @another-dave Of course. Any system past the very basics supports such - well at least the ones build at a time when their creators still cared about making a capable system instead of just bringing up a Linux - or Linux clone.
    – Raffzahn
    Jun 27, 2023 at 21:51
  • @another-dave and the PDP-11 one has tree-structured overlays; nice.
    – dirkt
    Jun 29, 2023 at 10:43
  • 1
    There were also linkers that were pretty good at creating overlays (under programmer guidance) for MS-DOS. Microsoft still supports archive libraries in the traditional style, although nowadays LIB.EXE is a front-end for LINK.EXE. They decided to make sure all the programs that manipulate .OBJ files were compatible by the brute-force method of them being the same program. Oct 27, 2023 at 18:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .