The Microsoft(R) Overlay Virtual Environment (MOVE)

Created: March 20, 1992

ABSTRACT

This article explains how the MicrosoftÒ overlay virtual environment (MOVE) helps overcome memory limitations for programs that run in the MS-DOSÒ operating system. The article compares MOVE technology to conventional overlays and to paged virtual memory systems, and explains the basics of the technology.

INTRODUCTION

Along with death and taxes, all programmers eventually share another misery: insufficient memory. Since the beginning of their profession, programmers have needed to cram too-big programs into too-little random-access memory (RAM). MS-DOSÒ programmers are further restricted by the infamous 640K limit; a program running on a 4 MB computer, for example, can directly execute only in the first 640K of RAM. Many techniques have been employed to overcome this limitation: optimizing compilers, interpreters, MS-DOS extenders, and so on. The most commonly used technique, overlays, is also one of the most cumbersome to use. The new MicrosoftÒ overlay virtual environment (MOVE) is a significant advance over previous overlay methods. MOVE is both easier to use and more effective than conventional overlay systems.

In many ways, the MOVE technology combines the benefits of overlays and virtual memory. Some of the advantages of MOVE over conventional overlays are:

The MOVE system keeps multiple overlays in memory at the same time. This makes devising efficient overlay structures much easier.

Discarded overlays can be cached in extended memory (XMS) or expanded memory (EMS).

MOVE supports pointers to functions. You do not need to modify your source code.

The memory allocated for overlays can be set at program startup. Your program can adapt to different memory situations.

The MOVE technology can be used only in MS-DOS operating system programs. Programs in the Microsoft WindowsÔ graphical environment automatically take advantage of a similar mechanism built into Windows.

The next three sections cover the basics of conventional overlays and virtual memory. If you’re already familiar with these concepts, you can skip ahead to “MOVE Basics.”

OVERLAY BASICS

If you’re not using overlays or other techniques, your program size cannot exceed available memory. When loading your program, MS-DOS copies the program’s code and data segments into memory, starting at the first available memory location and continuing to the end of the program (see Figure 1).

Figure 1. Memory Map for a Nonoverlaid Application

With overlays, however, the entire program need not fit into memory at one time. A portion of the program, called the root, occupies the lower portion of available memory and works just like a nonoverlaid program. The other portions of the program, called overlays, have overlapping memory addresses. This trick is accomplished by keeping only one or a subset of these overlays in memory at one time.

When you use overlays, the linker automatically includes a routine called the overlay manager in your program’s EXE file. When the program calls a function located in another overlay, the overlay manager loads the necessary overlay into memory, overwriting the previous overlay (Figure 2).

Figure 2. Memory Map for an Overlaid Application

This way, a program can be many times larger than available memory; it only needs sufficient memory to hold the root and the largest overlay. In some overlay systems the overlays are included within the EXE file, whereas in others the overlays are separate files, usually with the OVL extension. You need not keep track of which overlay is in memory or which function is in which overlay; the overlay manager automatically handles loading the appropriate overlay when necessary.

Well, if overlays sound too good to be true, you’re right; they have some drawbacks. They slow your program down, sometimes considerably. All that reloading of overlays from the disk can gum up the works. Reading an instruction from an overlay on the disk can be several thousand times slower than reading the instruction from an already-loaded overlay, so the speed of your program depends heavily on how the overlays are structured. Ideal candidates for overlays are functions that are called only once during a program’s execution, like initialization or error-handling routines. Routines that are used together should be grouped into the same overlay so that multiple overlays needn’t be loaded to accomplish a task. The worst situation is caused by a tight inner loop calling routines in two different overlays. In cases like this, the computer spends more time loading overlays from disk than executing instructions. This phenomenon, called thrashing, is accompanied by grinding from your user’s hard disk and groaning from your users.

Determining an efficient overlay structure is fiendishly difficult, an activity closer to art than to science. Your intuitions about who calls what, particularly in a large program, are often dead wrong. Even when you know which functions are involved in a particular task, it’s still difficult to balance the performance hit with the need to reduce the required memory.

EXAMPLE OF OVERLAY STRUCTURE

Most programmers structure large projects into several source files, using one file for each major system in the program. For example, a hypothetical calendar program that allows the user to add appointments, view a date page, and print the calendar might be composed of the files listed below.

An obvious overlay structure for the program can be illustrated as follows.

Although this structure reduces memory requirements to a bare minimum, it is probably very slow. For example, the primitives in DATEUTIL.C and STRUTIL.C are used throughout the code, so these routines should be placed in the root.

As you analyze the call tree and optimize the overlay structure, you may find yourself putting more and more routines in the program’s root. However, if you put too many routines in the root, your program will need nearly as much memory as the nonoverlaid version. The initialization routines in INIT.C call the hypothetical routines DatabaseInit in DATABASE.C and PrinterInit in PRINTER.C. Although these routines thematically belong in DATABASE.C and PRINTER.C, they should be included in the INIT overlay for best performance. If you move too many routines from where they belong to where they are used, your program may run faster, but it will be harder to read and to maintain the source code. A more balanced overlay structure is shown below.

Producing a good overlay structure requires lengthy and tedious trial-and-error work. As new capabilities are added to your program, the structure quickly becomes obsolete. Programmers working on a large system that contains hundreds of source files and thousands of functions often spend as much time tuning the overlay structure as they do writing code.

PAGED VIRTUAL MEMORY

Because working with overlays is so difficult, computer designers have come up with a radically different approach called paged virtual memory (VM). In a paged virtual memory system, the entire address space of the computer is divided into fixed-size blocks called pages. The address range of the processor can be significantly larger than the memory physically contained in the computer; therefore, only a fraction of the page addresses represent actual memory addresses. The programmer doesn’t have to worry about the amount of memory in a computer that has VM.

All addresses used in a VM program are virtual addresses. The computer’s virtual memory manager maps virtual page addresses to the physical addresses of memory. When a program needs a virtual memory page that is not mapped to a physical page in memory, the virtual memory manager copies the contents of that page from disk to a page of physical memory. The operating system maps the virtual address of the page to the physical address of the page’s contents. This way, when the program reads from a particular virtual address, the computer’s VM mapping scheme ensures that the program reads from the appropriate physical page. The computer doesn’t need room for all the pages containing a program. The more physical pages available, the less disk activity needed and the faster the program runs. The operating system’s VM manager handles loading pages from the disk, swapping modified pages to the disk and translating virtual addresses to physical addresses.

Virtual memory has several advantages over overlays. First, it does not require programmer effort and eliminates the tedious process of creating overlay structures. Second, the program performs efficiently regardless of the amount of memory the user’s computer contains. Most of the program’s execution time is spent in a small fraction of the code. As the program executes, pages containing this core code replace pages with less critical code. The set of pages that make up the often-used code is called the program’s working set. If the working set can fit in the computer’s physical memory, the program executes efficiently and swaps pages only occasionally for infrequently used routines. If the working set cannot fit in the computer’s memory, the computer thrashes, spending more time loading code from the disk than executing the program.

Of course, VM is no panacea either. First, the virtual memory manager and the address translation scheme must be part of the computer hardware. The more powerful members of the IntelÒ CPU family, particularly the 80386 and higher, support address translation. Less powerful CPUs, however, do not support this feature. Second, the virtual memory manager must realistically be an integral part of the operating system. MS-DOS does not support virtual memory.

MOVE BASICS

Microsoft’s new MOVE overlay technology has the best of both the overlay and virtual memory worlds. MOVE is an overlay system but has significant advantages over conventional overlays. Unlike conventional overlays, MOVE allows more than one overlay to reside in memory simultaneously. Like virtual memory, the MOVE memory manager keeps resident as many overlays as will fit. Each overlay need not fully cover a single task; two or three overlays can cooperate to complete the task. When loading a new overlay, MOVE discards the least recently used (LRU) overlay. If there is still insufficient room for the new overlay, MOVE discards the next least recently used overlay, and so on.

With MOVE you can make your overlays smaller and more modular, letting the LRU algorithm determine which overlays stay in memory. Some of your overlays may remain in memory because they are needed for the normal operation of the program. This working set of overlays is similar to the working set of pages in a virtual memory system. Like virtual memory, MOVE programs naturally configure themselves for efficient operation on a given computer. Unlike virtual memory, however, you are not limited to fixed-size pages; you can group functions for better control. For example, if function A is called each time function B is called and only when function B is called, you can group A and B in the same overlay to save the disk time of loading them separately.

MOVE MECHANICS

You don’t need to modify your C source code to create a MOVE application, but you do need to modify your CL and LINK command lines. These changes are described in the “Creating Overlaid Programs” section.

Like a nonoverlaid program, a MOVE application has a single EXE file. The EXE file contains the root and all overlays. The file also contains the overlay manager routines (about 5K), which are automatically added by the linker. When a MOVE application is launched, the program’s startup routine allocates a memory area to store the overlays. This area, called the overlay heap, is distinct from the regular heap used for malloc. When your application calls a function in an overlay that is not currently loaded in RAM, the MOVE manager must read the overlay from disk and copy its contents to the overlay heap before program execution can continue. If the heap does not have enough free space to hold the requested overlay, the MOVE manager discards one or more of the currently resident overlays. The least recently used overlay is discarded first. Because overlays can vary in size, the MOVE manager may have to discard multiple overlays to make sufficient room for the requested overlay.

If your program is running on a computer with EMS or XMS memory, the MOVE manager can create an overlay cache for copying discarded overlays. The program cannot execute overlays directly from this cache because the cache resides above the 640K limit. If a discarded overlay is needed again, the manager copies it from the overlay cache to the overlay heap rather than reading it from the disk. Because reading from the cache is much faster than reading from the disk, the space for your working set is effectively the cache size plus the heap size. The overlay manager routines maintain the overlay cache with an LRU algorithm in a manner similar to the overlay heap.

HEAP AND CACHE MANAGEMENT

The MOVE overlay manager is responsible for loading requested overlays from the disk or cache and copying them to the heap. If there is insufficient contiguous heap space for the requested overlay, the MOVE manager discards the LRU overlay from the heap and checks for contiguous space again. If space is still insufficient, the MOVE manager discards the next LRU overlay and repeats these steps until sufficient contiguous space is available.

At program startup, the MOVE manager attempts to allocate an overlay heap equal to the sum of the program’s three largest overlays. If space is insufficient or there are less than four program overlays, MOVE allocates a heap that is the size of the largest overlay. The remaining computer free memory is retained for the conventional (malloc) heap. (This is default initialization behavior and can be substituted by another scheme if desired.)

If the program is running on a computer with EMS or XMS memory, the MOVE manager attempts to allocate an overlay cache three times the size of the overlay heap. If there is not enough memory for a cache this size, all EMS or XMS memory is used.

When the MOVE manager discards an overlay from the heap, it does not copy the overlay to the cache if a copy of the overlay is already in the cache.

Individual overlays can be up to 64K in size but are usually much smaller. Overlays can be individual OBJ files, as in a conventional overlay system, or they may contain a list of functions. With large overlays, your program’s performance will suffer the problems associated with conventional overlays. Your overlays should be large enough to justify the time it takes to load them from disk. Specifics vary depending on your program, and experimentation will help you find the optimal overlay size and organization. For most programs, an optimal overlay size is about 4K.

If your overlaid program temporarily needs the EMS or XMS memory occupied by the cache, you can use the MOVE application programming interface (API) _movepause function to release the cache memory and _moveresume to restore the cache. This is particularly useful if your program spawns another program that needs EMS or XMS memory to function. The MOVE API functions are described in Appendix A.

HOW DOES MOVE WORK?

One aspect of MOVE seems quite mysterious until you know how it works. How does the overlay manager know when it needs to load an overlay? How do calls to overlaid functions know where to branch in the overlay heap? This magic is accomplished by inserting an additional link between the function and its callers. This link, called a thunk, works like an additional function call. One thunk data structure is created in the root for each far function contained in the overlays. The thunk data structure contains the overlay number containing the function and the offset of the function’s entry point within the overlay. The linker modifies all function calls to overlaid functions so that they call the thunk instead of directly calling the function. When a function calls the thunk, the MOVE manager locates the appropriate overlay in the heap or loads the overlay from the cache or disk and jumps to the offset specified in the thunk.

CREATING OVERLAID PROGRAMS

You create a MOVE application by following the same edit-compile-link development cycle used for all C programs. (The old syntax, link a+(b)+(c), is also supported.) You will need to create an additional file, called a DEF file, for each application. The DEF file is used by the linker and specifies the makeup of the root and of each overlay. A sample DEF file for the hypothetical calendar program is shown below:

EXETYPE DOS

;FUNCTIONS:init DatabaseInit PrinterInit

; Place main, strutil, and dateutil in the root.

FUNCTIONS main OVL:0

FUNCTIONS strutil OVL:0

FUNCTIONS dateutil OVL:0

FUNCTIONS database OVL:1

FUNCTIONS dataform OVL:2

FUNCTIONS init OVL:3

FUNCTIONS printer OVL:4

For more information on the syntax of DEF files, see “Creating Overlaid MS-DOS Programs” and “Creating Module Definition Files” in the C/C++ Environment and Tools manual.

The first step in creating a MOVE application is to determine an appropriate overlay structure. For most programs, a good starting point is to place each OBJ file in its own overlay. The program entry point must be in the root, that is, the normal sequence is _astart followed by main. OBJ files containing universally called primitives should be placed in the root as well.

MOVE gives you control over the placement of individual functions. Instead of moving a function’s source code physically to another file, you specify the function in a FUNCTIONS statement in your application’s DEF file. A function can be specified in this way only if it is a packaged function. Functions can be packaged by specifying the /Gy switch during compilation. For more information on packaging functions, see “CL Command Reference” and “Creating Overlaid MS-DOS Programs” in the C/C++ Environment and Tools manual.

OPTIMIZING OVERLAID PROGRAMS

After you’ve created a MOVE program, you can run it under different memory conditions, assess its performance, and compare the performance of different overlay sizes and structures. A MOVE feature called tracing can help you optimize your overlays. Tracing a MOVE application generates a log file during program execution. The log file contains an entry for each load and discard of an overlay. A separate MS-DOS utility called TRACE reports and summarizes the information in trace log files. The TRACE utility is discussed in Appendix C. For more information on tracing, see “Creating Overlaid MS DOS Programs” in the C/C++ Environment and Tools manual. Future versions of MOVE will include enhanced tools that make designing and optimizing the overlay structure easier.

You can modify some of the characteristics of the MOVE manager. For example, you can change the amount of memory MOVE allocates for the overlay heap and cache by changing the constants and heuristics in the MOVEINIT.C file. For more information, see “Creating Overlaid MS-DOS Programs” in the C/C++ Environment and Tools manual.

APPENDIX A. THE MOVE API

The MOVE API is provided in a library called MOVE.LIB. This library is a component of the C combined libraries for medium and large models. (Another form of the library, MOVETR.LIB, also contains the MOVE API; see Appendix C.) The MOVE API is declared in the MOVEAPI.H file, which is available on disk. This appendix describes MOVE routines and functionality.

The _moveinit Function

MOVE begins an overlaid program with a call to _moveinit, which calculates the heap and cache needed for the overlays and allocates memory for the heap and cache.

You can use the default _moveinit function provided in MOVE.LIB, or you can write your own version of _moveinit and link it to your program. The source code for the default _moveinit function is available in the MOVEINIT.C file.

The _moveinit call occurs before the call to _astart that begins a C program and performs initialization. For this reason, do not call C run-time routines from any version of _moveinit.

The following functions are called from _moveinit:

_movesetheap

_movegetcache

_movesetcache

_movetraceon (only in MOVETR.LIB)

The functions are described in the sections below. In addition, LINK creates several variables that begin with $$; these variables are described in the “LINK Variables” section.

Heap Allocation

The _movesetheap function sets the overlay heap size.

extern unsigned short __far __cdecl _movesetheap(
unsigned short maxovl,
unsigned short minheap,
unsigned short reqheap );

where:

MOVE attempts to allocate the requested amount of memory. If that much memory is not available, MOVE tries to allocate as much as possible. If the amount of available memory is less than the minimum heap requested, MOVE ends the program and issues a run-time error.

Cache Allocation

The _movegetcache function determines the amount of memory available for a cache.

extern void __far __cdecl _movegetcache(
unsigned short __far *expmem,
unsigned short __far *extmem );

where:

The _movesetcache function allocates expanded and extended memory for an overlay cache.

extern unsigned short __far __cdecl _movesetcache(
unsigned short expmem,
unsigned short extmem );

where:

The default _moveinit function requests a cache equal to the sum of all overlays. If _movesetcache cannot allocate the requested amount of memory, it sets a bit in the return value. MOVEAPI.H defines the following constants to represent bits in the return value.

The _movesetcache function sets the following global variables when the overlay cache is allocated:

extern unsigned short __far __cdecl _moveckbxms;

extern unsigned short __far __cdecl _moveckbems;

The _moveckbxms variable is set to the size of the allocated extended memory. The _moveckbems variable is set to the size of the allocated expanded memory.

Freeing and Reallocating Cache Memory

You can temporarily release and then restore the memory allocated for the overlay cache. This is useful when your program spawns another program that uses extended or expanded memory or when you want to prepare for a possible abnormal exit from your program.

The _movepause function frees the cache memory and closes the executable file.

extern void __far __cdecl _movepause( void );

The _moveresume function reallocates memory for the overlay cache and reopens the executable file.

extern void __far __cdecl _moveresume( void );

MOVEAPI.H defines the following variables for use by these functions:

extern unsigned short __far __cdecl _movefpause;

extern unsigned short __far __cdecl _movefpaused;

MOVEAPI.H also defines constants to represent bits in _movefpause and _movefpaused as follows.

The _movepause function reads the value in _movefpause and sets _movefpaused to the value of the action taken by _movepause. Before you call _movepause, set _movefpause to __MOVE_PAUSE_DISK to close the file, and set it to __MOVE_PAUSE_CACHE to free the cache, as in:

_movefpause |= __MOVE_PAUSE_DISK;

_movefpause |= __MOVE_PAUSE_CACHE;

_movepause();

The _moveresume function reads the value in _movefpaused and then clears _movefpaused. The overlays that were in the heap and cache are not restored. Therefore, after a call to _moveresume, the program may at first run slightly more slowly as it makes calls to routines in overlays.

LINK Variables

LINK creates the following variables:

APPENDIX B. MOVE ENVIRONMENT VARIABLES

You can use environment variables at run time to specify the size of the requested overlay heap and overlay cache and the maximum number of overlays. The _moveinit function given in MOVEINIT.C provides environment support; you can compile this function and link it with your program. (MOVETR.LIB includes a version of _moveinit that already contains environment support.)

First, enable environment support by compiling MOVEINIT.C with MOVE_ENV defined. Then specify the resulting MOVEINIT.OBJ when linking your program. With MOVE_ENV defined, MOVEAPI.H declares the following variable:

extern unsigned short __far __cdecl _movesegenv;

Compiling for environment support causes MOVEINIT.C to define a function called _movegetenv. The environment-support version of _moveinit uses _movegetenv to get the values of the following environment variables:

To use these variables, set them to strings that represent the desired settings. Each string must consist of exactly four hexadecimal digits.

APPENDIX C. THE TRACE UTILITY

You can optimize the overlays in your program with the help of the tracing form of the MOVE library (MOVETR.LIB) and the Microsoft MOVE trace utility (TRACE) version 1.0. MOVETR.LIB contains MOVE.LIB and additional routines for tracing overlay behavior.

Create a tracing version of your program as described in the following sections. When you run your program, the tracing functions create a binary file called MOVE.TRC in the directory from which the program is run. After your program ends, use TRACE to read MOVE.TRC. If the tracing results indicate that some functions cause overlays to be swapped frequently, you can reorganize the functions in the overlays by using statements in the module definition file.

Creating a Tracing Version of an Overlaid Program

To create a program that will trace overlay performance, specify MOVETR.LIB in LINK’s libraries field. This causes LINK to use the MOVETR.LIB library instead of the MOVE.LIB component of the default combined library. Use LINK’s /NOE option to prevent conflicts between MOVETR.LIB and the combined library. If you explicitly specify the combined library in the libraries field, list MOVETR.LIB before the combined library.

The Trace Functions

By default, tracing is in effect during the entire run of your program. You do not need to make any changes in your program to enable tracing. However, MOVETR.LIB provides two functions that you can use to turn tracing on and off within your program.

The _movetraceon function turns on tracing.

extern void __far __cdecl _movetraceon( void );

This function opens the MOVE.TRC file and activates tracing. During tracing, information about overlay behavior is written to MOVE.TRC. The default _moveinit function calls _movetraceon at the start of the program if MOVE_PROF is defined; this definition is in MOVETR.LIB.

The _movetraceoff function turns off tracing and closes MOVE.TRC.

extern void __far __cdecl _movetraceoff( void );

The tracing functions are declared in MOVEAPI.H. They are defined only in MOVETR.LIB.

Running TRACE

To run TRACE, use the following syntax:

TRACE [options] [tracefile]

The tracefile is the MOVE.TRC file created during a tracing session. You can specify a path with the filename. If tracefile is not specified, TRACE looks in the current directory for a file called MOVE.TRC.

An option is preceded by an option specifier, either a forward slash (/) or a dash (–). Options are not case sensitive. An option can be abbreviated to its initial letter. Options can appear anywhere on the command line.

TRACE options are:

TRACE Output

TRACE displays information on the tracing session to the standard output device. You can use the redirection operator (>) to save the output in a file. The output is in table format. Each line of output represents an interoverlay transaction. A line of information is organized into the following fields:

The overlay to which to return from the current transaction. (If blank, the overlay in the previous line is implied.)

The physical return address in segment:offset form. (If blank, the address in the previous line is implied.)

The transaction type, which is one of the following:

Present

Load from disk

Load from expanded memory

Load from extended memory

Discard from heap

Cache to expanded memory

Cache to extended memory

Discard from cache

Invalid

The overlay that is the object of the transaction.

The segment in memory where the transaction overlay is loaded.

The interoverlay operation, which is one of the following:

Call function, in which function is:

An overlay number and an offset in default output

A function name if /EXE is used

A decorated function name if /EXE and /MAP are used

Return.

If blank, the Call in the previous line is implied.

TRACE Performance Summary

When you run TRACE with the /SUM option, TRACE displays a summary of overlay performance to the standard output device. The full session is not displayed. You can use the redirection operator (>) to save the output in a file. The summary information is organized into the following fields.

OVERALL

HEAP

TRACE Errors

TRACE issues the following errors and warnings.

TR1001Invalid filename for /EXE

The string specified with the /EXE option was not a valid filename.

TR1005Missing filename for /EXE

The /EXE option must be followed by a colon and a filename, with no spaces in between.

TR1007Unrecognized option

The command line contained an option specifier, either a forward slash (/) or a dash (–), followed by a string that was not recognized as a TRACE option.

TR1010Cannot find trace file

One of the following occurred:

A trace file was specified on the command line, but the specified file does not exist.

No trace file was specified on the command line and TRACE assumed a trace file called MOVE.TRC, but MOVE.TRC does not exist.

TR1011Error opening/reading .EXE file

TRACE either failed to find the executable file specified with /EXE or encountered an error while opening the file.

TR1012Out of memory

The available memory is insufficient for the size of the program being traced.

TR1013Invalid debugging information

The debugging information contained in the executable file was not packed using CVPACK version 4.0.

TR4001Cannot find function name

TRACE could not find a function name to display. TRACE continues to generate output without displaying the function name.

Function names are displayed when the /EXE option is specified. Either the executable file contains corrupt debugging information or a module in the executable file was compiled without the /Zi option for including debugging information.

TR4002Missing debugging information for module

TRACE could not find a symbol to correspond to a given physical address. A module may have been compiled without the /Zi option for including debugging information.