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 *
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 *
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.