In CP/M, how did a program know when to load a particular overlay?

Question

Here is what I understand so far:

A program that was too large to put into main memory was broken into several overlay regions. Once you needed data from outside of the currently loaded region, something happened to swap out the overlays. But what is that something?

If I understand how virtual memory works nowadays, whenever you try to access data outside of the currently page you initiate a page fault, and an ISR handles it. This makes sense to me - a hardware interrupt triggers a function call, and then memory gets modified. But it doesn't seem like that's what happened in CP/M, is it?

Answer 1

In CP/M, there is no support for overlays at the operating system level. There isn't even a system call to load an overlay (comparable to INT 21h/AX=4B03h under MS-DOS). If a program uses overlays, they are implemented entirely within that program.

One CP/M program that uses overlays is ZEM (Z80 Emulator and Monitor) by P.G.Kenny. This program is written in C, which makes it a bit easier to see how the system is implemented. The various functions are grouped into four .OVL files, each assembled to load at 0x3F80. The load_ovl() function loads an overlay, and the ovl_num variable records which overlay is currently loaded.

At startup, ZEMINIT.OVL is loaded:

    run_ovl = OVL_ADDR;             /* overlay call address */

    load_ovl(INIT_OVL);             /* load and run */
    (*run_ovl)(argc, argv);         /* initialization overlay */

    version = VERSION;              /* version number */
    date = DATE;                    /* last revision date */

    command = 0;                    /* load and run FEX overlay */
    load_ovl(FEX_OVL);              /* for extra initialization */
    (*run_ovl)();
    ovl_num = N_FEX;                /* current active overlay */

Depending on which command is entered, the appropriate overlay is loaded (if it isn't already present) and then control is passed to it.

        switch (command) {          /* single letter commands */

        case 'S' :                  /* execution class commands */
        case 'T' :
        case 'U' :
        case 'G' :

            if (ovl_num != N_FEX) { /* load execution overlay */
                load_ovl(FEX_OVL);  /* if not already in memory */
                ovl_num = N_FEX;
                disk_io = TRUE;     /* flag disk i/o */
            }
            (*run_ovl)();           /* call overlay */
            break;

You mention virtual memory in your question. This doesn't apply under CP/M-80, for various reasons. The usual scenario for virtual memory is that the computer's address space is larger than physical RAM. Programs then may be bigger than physical RAM, but still fit in the computer's address space. For example, a 128k program might be loaded in a system with 64k RAM; if control passed to code at address 96k, the operating system would use mechanisms such as page faults to ensure that there was memory at 96k containing the correct section of program.

In CP/M, the scenario is slightly different: an oversize program isn't just bigger than RAM, it's also bigger than the available address space. In our example 128k program, there is no way to express "jump to code at address 96k" in the processor's instruction set. The program therefore has to be divided into separate modules each of which will fit in the available address space, and how this is done is entirely in the hands of the program itself.

(The 8080 and Z80 also lack the memory management hardware that would be necessary to implement virtual memory, and it would not be straightforward to add even using external hardware).

Answer 2

The most popular language for CP/M that supported overlays was probably Turbo Pascal. Turbo Pascal's runtime libraries did all the overlay handling for you, you simply declared a function or procedure as 'overlay', which instructed the compiler to put the function into an '.OVL' file instead of the main .COM file. When such a function or procedure is called, Turbo's runtime library checks to see if the respective overlay is already loaded, if not, it locates the proper .OVL file and pulls in the code into memory space reserved during the compile process, then calls the routine. You can have multiple subroutines per overlay and multiple .OVL files per .COM file, overlays may even pull in further overlays - Turbo keeps track of what is where.

Thus, overlay handling completely relied on the compiler and its runtime libraries. One of the reasons that programs that used overlays were relatively common was (besides the limited TPA that was provided by CP/M) Turbo Pascal's extremely comfortable way of handling overlays.

So, for Turbo Pascal, the answer to this question is particularly simple: A program knows when to load an overlay because a subroutine is called that you have declared to be an OVERLAY subroutine. Everything else is handled by the runtime library.

Answer 3

In CP/M, how did a program know when to load a particular overlay?

Because it was part of the calling code/execution sequence?

A program that was too large to put into main memory was broken into several overlay regions. Once you needed data from outside of the currently loaded region, something happened to swap out the overlays. But what is that something?

Er ... a call to a routine?

I guess the main issue with understanding basic overlay usage is to expect some mysterious system component handling overlay management, except there is none.

Everything about overlays is done on application level (new speak userland) by each application on it's own. This is not only true for CP/M but as well for later DOS (*1) and several other basic systems.

Basic support, if at all (*2), was on assembler/compiler level to allow multiple subroutines to be compiled to run at the same address. Everything else was program specific. There was no standard, only language specific solutions - if at all.

---

At that point the question essentially leaves the RC.SE domain and becomes basic CS. But for the sake of it ... also, I already wrote the following part before realizing that I'm repeating generic CS knowledge.

---

Before continuing, it may help to remember what program structure is required to use overlay linking (*3):

A program having a main routine(s) and two or more subroutines (groups) which are mutually independent.

With this setup the main program can be linked to one address range, while all subroutines are linked to another address range, the overlay area, each group to the same address range. When some routine in the main program now wants to call a subroutine in an overlay it will not call it directly but by detour thru the overlay management.

To look into let's look at a simple program using a C-ish like syntax - note, this example does NOT assume that there is any language support - having one will of course take away much of those details - but we want to see all the dirty secrets :))

int Var1;

main()
{
    Var1 = 1;
    SomeSub();
    OVL_MGR(Ovl1,FuncA, ... ); - Calls Function A in Overlay 1
    OVL_MGR(Ovl2,FuncD, ... ); - Calls Function D in Overlay 2
}

SomeSub()
{
   Var1++;
}

Ovl1:FuncA(...)
{
    SomeSub();                 - Calls direct a function in the root segment
    FuncB( ... );              - Calls direct Function B in the same overlay
    OVL_MGR(Ovl1,FuncB, ... ); - Calls B thru the manager
}

Ovl1:FuncB(...)
{
    OVL_MGR(Ovl2,FuncC, ... );
}

Ovl2:FuncC(...)
{
    ...
}

Ovl2:FuncD(...)
{
    SomeSub();
    if(Var1<5)
    {
      OVL_MGR(Ovl1,FuncB, ... );
    };
}

Our overlay capable compiler/linker will now create 3 code segments:

• Root segment, containing functions
  • main,
  • SomeSub and
  • OVL_MGR
• First overlay segment (Ovl1), containing functions
  • FuncA and
  • FuncB
• First overlay segment (Ovl2), containing functions
  • FuncC and
  • FuncD

Address wise the root segment is compiled to Address 0100h, while all overlays are compiled to an address after the root segment. At link time the linker will calculate this from the size of the root segment. After that it will reserve space for Variables, Stack and so on.

So for simplicity lets assume our memory layout like this:

0100h..1FFFh - Code in root segment
2000h..3FFFh - Overlay region
4000h..6CFFh - (Static) Variables
6D00h..7FFFh - Stack

No lets see how running above program may look like:

1. When loading only the root segment is loaded into memory - at 0100h as custom for CP/M.
2. Startup code will setup Stack and Variables and so on
3. Main starts execution
4. Var1 at 4000h gets set to 1
5. SomeSub within the root segment is called using a regular call
6. The overlay manager is called with Ovl1 and FunctA as parameter
   • actual overlay number is saved on stack (NULL as none is loaded)
   • Check if Ovl1 is loaded
   • Not loaded right now ->
     • Ovl1 gets loaded from disk to 2000h
     • Ovl1's number gets set in a global variable
   • FuncA (at address 2000h) gets called
7. FuncA calls SomeSub within root using a standard subroutine call
8. Same is done with FuncB, as its a regular call within the same segment
9. FuncB now calls FuncC in overlay 2 using the overlay manager
   • actual overlay number is saved on stack (Ovl1)
   • Check if Ovl2 is loaded
   • Not loaded right now ->
     • Ovl2 gets loaded from disk to 2000h, replacing Ovl1
     • Ovl2's number gets set in a global variable
   • FuncC (also at address 2000h) gets called
10. FuncC does it's job and returns to the overlay manager

• Saved overlay number is pulled from Stack (Ovl1)
• Not the same as the actual one (Ovl2) ->
  • Ovl1 gets loaded from disk to 2000h, replacing Ovl2
  • Ovl1's number gets set in a global variable
• execution returns to the caller (FuncB)

11. FuncB returns the standard way to FuncA
12. FuncB is called again but using the overlay manager (maybe it was copied from some other place and not adapted *5)

• actual overlay number is saved on stack (Ovl1)
• New (Ovl1) is the same as the old (Ovl1), so no loading needed
• FuncB (maybe at address 2200h) gets called

13. FuncB does it's job (see 9..10) and returns afterwards to the overlay manager

• Saved overlay number is pulled from Stack (Ovl1)
• Actual (Ovl1) is the same as the old (Ovl1), so no (re) loading needed
• execution returns to the caller (FuncA)

14. FuncA now calls FuncD in overlay 2

• actual overlay number is saved on stack (Ovl1) *6
• Check if Ovl2 is loaded
• Not loaded right now ->
  • Ovl2 gets loaded from disk to 2000h, replacing Ovl1
  • Ovl2's number gets set in a global variable
• FuncD (also at address 2000h) gets called

15. ... and so on ...

Well, here it gets funny, take your time and see how nice they trash each other. Perfect example how overlays should not be organized :))

---

*1 - Although DOS did offer a overlay loading function (Int 21h Function 4Bh Subfunction 3h), it did not offer any support past loading a single module. In fact, the overlay manager included in Microsoft languages did not use it at all (*4).

*2 - If not, one had to 'simply' write different programs and do all linking manually.

*3 - Well, there is also the method of simply exchanging programs at whole, like a text editor followed by a mail merger followed by a print formater - sometimes with a rather small root program managing the sequence. This is also sometimes called overlay, but 'chaining' might be a better description.

*4 - Link's overlay manager installs itself by default at INT 3Fh at program start and uninstalls at exit. All Overlay calls are thus coded as INT 3Fh instructions followed by a 16 bit overlay number and a 16 bit function entry address instead of the far call within a regular linked program. By using that Int as custom call instruction this will work with any calling scheme, no matter what language. But that's a different story.

*5 - When overlay support is provided by a language this usually never happens - but this is to show even such case.

*6 - Note, this is no longer NULL, as Ovl1 is still loaded. Saves possible trashing when functions in the same overlay are called further down.

Answer 4

I used to have disassembled dBASE II files that pretty much showed it was written in 8080 assembly language.

Its overlay structure was pretty simple. All of the overlay files were loaded starting at the same address, and at the beginning of each overlay was a jump vector (just like the CP/M BIOS). The number of jumps in the vectors varied.

No swapping. No linker. No overlay management. Just load and go.