Dynamic Loading

01 Introduction

Lesson 8.2 introduced address binding and the distinction between logical and physical addresses. It presented the three binding times and showed how a modern system layers them: compile-time binding for the internal layout of a module, load-time binding for resolving imports, and execution-time binding for the physical mapping. This lesson turns to a different problem: which parts of a program need to be in memory at all?

A program is not a homogeneous blob of code and data. It is a collection of routines — functions, methods, procedures — most of which are never called during any given run. A word processor contains a spell-checker, a print engine, an import filter for a dozen file formats, and a macro language interpreter; a typical session uses only a small fraction of them. A web browser contains support for dozens of network protocols, media codecs, and scripting languages; a page that does not play video does not need the video decoder. The question is whether the operating system should load all of a program into memory when the program starts, or only the parts that are actually used.

Dynamic loading is the answer: load a routine only when it is first called. The program is stored on disk in a relocatable form, and the main program begins execution with only a small portion in memory. When a routine that is not yet in memory is called, a loader — provided as part of the program's own runtime, not by the operating system — locates the routine's object code on disk, loads it into memory, relocates it if necessary, and transfers control to it. The routine stays in memory for the remainder of the program's execution, so subsequent calls to it are direct.

The advantage of dynamic loading is that a routine that is never called is never loaded, and a routine that is called only occasionally is loaded only when needed. The total amount of memory used by the program is therefore determined by the routines it actually executes, not by the routines it contains. For a program like a word processor or a web browser, this can reduce the memory footprint by a factor of ten or more. The corresponding disadvantage is the overhead of loading a routine at the moment it is needed: the first call to a dynamically loaded routine is much slower than a direct call, because it must read the routine from disk and relocate it. On a system with good locality, however, the routines are loaded once at the beginning of the program and the loading cost is amortised over the whole run.

This lesson presents dynamic loading and its relationship to the other mechanisms in the unit. It distinguishes dynamic loading from static loading and from dynamic linking — three concepts that are often confused — and it presents the historical precursor, overlays, which achieved a similar effect in an era before virtual memory. It introduces swapping, the first mechanism for handling the case where the total memory demanded by the system's processes exceeds the physical memory — the overcommitment requirement from Lesson 8.1. And it closes with the observation that the ideas of dynamic loading are the direct ancestors of the demand paging of Unit 9, which generalises them from routines to pages.

02 Learning objectives

This lesson contributes to U8.2 and U8.3, and to course learning outcomes CLO2, CLO4, and CLO6.

03 Required reading

• Operating System Concepts — Chapter 9, Section 9.1, Background, including the discussion of dynamic loading and dynamic linking. The standard treatment of both topics.
• Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.3, Virtual Memory, and Section 3.4, Page Replacement Algorithms (the introductory part). Read for the historical context and for the discussion of overlays.
• OSTEP — Chapter 18, Paging: Introduction, and Chapter 21, Swapping: Mechanisms. The clearest available treatment of how the ideas of dynamic loading generalise into demand paging.
• Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 7, Linking, sections 7.9–7.13, on shared libraries and runtime loading. The book-length treatment of the toolchain that performs dynamic linking.
• Levine, J. R. — Linkers and Loaders. Morgan Kaufmann, 1999. Chapters 1 and 2, and Chapter 8 on dynamic linking. The definitive reference for the mechanics.
• Linux man pages: man 3 dlopen, man 3 dlsym, man 3 dlerror, man 3 dlclose, man 1 ld.so, man 1 ldd, man 2 mprotect, man 5 proc (the /proc/<pid>/maps interface).

04 Core content

4.1 Static loading

Static loading is the default behaviour of a traditional loader. When a program is started, the operating system reads the entire executable image into memory — all its code, all its data, all its statically linked libraries — and only then transfers control to the program's entry point. The program's memory footprint is fixed at load time and does not change throughout its execution (except through explicit requests for more memory, such as malloc and mmap).

Static loading has three properties that made it the natural default in the early days of computing and that it still has today.

• Simplicity. The loader reads the program into memory, sets up the address space, and jumps to the entry point. There is no runtime machinery for loading code, no need to keep track of which routines are resident, and no need to handle the case where a routine must be brought in from disk in the middle of execution. The loader is a small, simple program.
• Predictability. The program's memory footprint is known in advance. The operating system can decide whether the machine has enough memory to run the program before starting it; if it does not, the program is not started. The program's performance is uniform throughout its execution, because there are no loading pauses.
• Direct execution. Once the program is loaded, every instruction fetch and every data access reaches memory directly. There is no indirection, no check for residency, no trampoline through a loader. The program runs at full speed.

The disadvantage of static loading is that the memory footprint includes everything the program might use, whether or not it is used in a given run. A word processor that loads its full feature set — text editor, spell-checker, grammar-checker, print engine, import filters, export filters, macro interpreter, collaboration client, cloud-sync engine — uses memory for all of them, even if the user opens a file, edits it, and saves it without using any of the features except the editor. On a system with limited memory, this can be the difference between the program fitting and not fitting.

4.2 Dynamic loading

Dynamic loading is the alternative: load a routine into memory only when it is first called. The program is stored on disk in a form that allows individual routines to be loaded independently — typically a relocatable object file per routine, or a single module with a table of routine locations. When the program begins, only the main routine and its immediate dependencies are loaded. When a routine is called for the first time, a check determines whether it is already in memory. If it is, the call proceeds directly. If it is not, the dynamic loader is invoked to bring the routine in from disk, relocate it, and transfer control to it.

The check and the loader are part of the program's own runtime, not of the operating system. This is the crucial point, and it is the source of much confusion. In the classical formulation presented in textbooks, the dynamic loader is a routine that the programmer links into the program, and the program itself is responsible for deciding when to call it. The operating system provides only the primitive mechanisms — reading a file, allocating memory, mapping memory — that the dynamic loader uses.

The algorithm of dynamic loading is direct. Every call to a potentially-unloaded routine is transformed into a call to a stub, which performs the following steps:

1. Check whether the target routine is already resident in memory.
2. If it is resident, jump to its entry point. (On subsequent calls, this is the only step.)
3. If it is not resident, locate its object code on disk.
4. Read the object code into a free region of memory.
5. Relocate the code — adjust any addresses in it to reflect its new load address. This is the same process that the loader performs for a program at startup, but performed for a single routine at runtime.
6. Mark the routine as resident, so that subsequent calls will take the fast path in step 2.
7. Transfer control to the routine's entry point.

The key observation is that the routine, once loaded, stays in memory for the rest of the program's execution. It is not evicted when the call returns; there is no replacement policy. This "sticky residency" rule is what makes dynamic loading different from the demand paging of Unit 9, where pages can be evicted and reloaded. In dynamic loading, a routine is either not yet loaded (its first call has not happened) or is resident (its first call has happened and it will never be evicted). The memory usage of the program is therefore monotonically increasing: each newly-loaded routine consumes memory that will not be reclaimed until the program terminates.

4.3 What dynamic loading costs

The trade-off of dynamic loading is between memory and time. The memory saving comes from not loading routines that are never used; the time cost comes from the delay on the first call to each routine that is used. The balance depends on the workload.

For a workload that uses all of a program's routines, the memory saving is zero and the time cost is positive: dynamic loading is strictly worse than static loading. For a workload that uses only a small fraction of the routines, the memory saving is substantial and the time cost is paid only for the routines that are used. For a program that is interactive and starts many routines in quick succession, the time cost may be visible to the user as a stutter at the moment of the first call. For a program that starts once and runs for hours, the time cost is negligible and the memory saving is significant.

There is also a subtle cost in complexity. The program must include the dynamic loader, must keep track of which routines are resident, and must structure the calls to potentially-unloaded routines through stubs. In a modern system, this complexity is largely handled by the toolchain — the linker and the dynamic linker generate the stubs and maintain the state — but in the classical formulation the programmer wrote them. Either way, the mechanism adds a layer of indirection that must be maintained and debugged.

4.4 Dynamic linking revisited

Lesson 8.2 introduced dynamic linking as the toolchain's choice between copying library code into an executable (static linking) or leaving the resolution of library symbols until load time or first use (dynamic linking). It is worth revisiting the distinction between dynamic linking and dynamic loading, because the two are frequently confused and the confusion obscures why both exist.

The two mechanisms are complementary, not competing. Dynamic linking is what allows a library to be shared among processes: without it, every program would have its own copy of every library it uses, and the total memory consumed by libraries on the system would be the sum of the sizes of the libraries each program links. Dynamic loading is what allows a single program's own routines to be loaded on demand: without it, every routine that the program contains would occupy memory whether or not it is ever called.

In a modern system, the two are combined. A program is dynamically linked against its libraries, which means the libraries are shared. And the program's own routines — particularly if it is a large program — may be laid out in a form that allows the operating system's demand paging to load them only as they are used. The distinction between dynamic loading and demand paging blurs at this point: the programmer no longer writes stubs, because the operating system's page fault mechanism does the loading automatically. But the underlying idea — load only what is used — is exactly the idea of dynamic loading.

4.5 Overlays: the historical precursor

Before virtual memory was practical, the problem of running a program larger than physical memory had to be solved by the programmer. The technique was called overlays, and it was the dominant approach from the late 1950s through the 1970s.

An overlay is a portion of a program that shares memory with another portion. The programmer divides the program into overlay segments: a resident portion that is always in memory, and a series of transient portions that occupy the same memory region at different times. The programmer is responsible for knowing which segments can coexist and which must be swapped. When the program reaches the point where segment A must be replaced by segment B, the program itself issues the request to load B into the shared region, overwriting A.

The overlay approach is essentially manual dynamic loading with an additional twist: the program's segments can replace each other, rather than accumulating. It requires the programmer to construct a call graph — a diagram of which routines call which other routines — and to partition the routines into segments such that routines that never call each other can share the same memory. The partition is a graph-colouring problem, and it is NP-hard in general, so the programmer uses heuristics.

Overlays are instructive because they show what the alternative to virtual memory looks like. Without hardware and operating-system support for demand paging, the programmer must solve the loading problem by hand, using knowledge of the program's structure that the operating system does not have. The result is labor-intensive and error-prone: a mistake in the overlay partition causes a routine to be overwritten while it is still in use, and the resulting bug is difficult to diagnose. When virtual memory became practical in the 1970s and 1980s, overlays disappeared, because the operating system could solve the same problem automatically using the page fault mechanism.

4.6 Swapping

Dynamic loading and overlays solve the problem of a single program that is too large for memory. They do not solve the problem of many programs that together are too large for memory. That problem is solved by swapping.

In a swapping system, the operating system moves an entire process's address space — all of its code, data, heap, and stack — between main memory and a region of disk called the swap space (or backing store). When the system needs to free memory for a new process, it swaps out a process that is not currently runnable — a process that is waiting on I/O, for example, or a process that has been preempted for a long time — writing the entire process to disk. When the process is needed again, the system swaps it in, reading it back into memory.

Swapping has several consequences.

• It requires a large amount of disk space. The swap area must be at least as large as the total memory that might be swapped out at once, plus a margin. Systems with tens of gigabytes of physical memory typically allocate tens of gigabytes of swap space.
• It is slow. Writing a process to disk and reading it back is expensive — milliseconds of latency for a large process — and it happens on a time scale that is visible to the user. A system that is swapping heavily is perceived as sluggish or frozen.
• It requires a policy for choosing victims. Which process should be swapped out when memory is needed? The classical policies are based on priority (swap out the lowest-priority process), on the process's recent CPU usage (swap out the process that has used the least CPU recently), and on the process's memory footprint (swap out the largest process, which frees the most memory). The choice matters, because a bad victim-selection policy can lead to thrashing: the system spends all its time swapping processes in and out and no time doing useful work.
• It is coarse-grained. Swapping moves an entire process's address space. If a process has a large address space but is only using a small part of it, the whole thing is moved. The fine-grained alternative — moving individual pages instead of whole processes — is what demand paging provides, and it is what makes modern systems efficient.

Swapping is the direct ancestor of demand paging. The idea is the same: move data between main memory and disk to handle overcommitment. The difference is the granularity. Swapping moves a whole process; demand paging moves a single page. Demand paging is more efficient because it can make better use of partial residency: a process whose working set is small can be fully resident even if its total address space is large. Unit 9 is about demand paging.

Many modern systems do not implement classical swapping, but they do have a swap area, and they do use it for demand paging. The swapon and swapoff commands on Linux control the swap areas, and /proc/swaps lists them. When demand paging evicts a page, it writes the page to swap; when the page is needed again, it reads the page back. The swap area is therefore the backing store for demand paging, and it plays the same role that the swap area played for classical swapping — but at page granularity.

4.7 Modern practice: dlopen and friends

The classical dynamic loader — a routine linked into the program and called explicitly by the programmer — survives in modern systems as the dynamic loading API, provided by the POSIX standard and implemented by the dynamic linker. The API is a small set of functions in <dlfcn.h>:

dlopen

Loads a shared library at runtime and returns a handle to it. The library may be specified by name or by path. The call returns NULL if the library cannot be loaded. The library is mapped into the process's address space, and its dependencies are recursively loaded as well.

dlsym

Looks up a symbol (function or variable) in a loaded library, using the handle returned by dlopen. The call returns the symbol's address, which the caller can cast to the appropriate function pointer type and then call.

dlclose

Unloads a library that was loaded with dlopen. The library's memory is released when its reference count reaches zero. In practice, many libraries are never unloaded, because the reference counting and the possibility of dangling pointers make unloading dangerous.

dlerror

Returns a human-readable string describing the most recent error from dlopen, dlsym, or dlclose. The error string should be retrieved immediately after a failed call, because subsequent calls may overwrite it.

The API is used in several common situations:

• Plugins. A program that supports user-installable plugins — an image editor, a web browser, a build tool — loads the plugin's shared library at runtime when the plugin is invoked. The plugin provides a well-known symbol (its entry point), which the host program looks up with dlsym and calls.
• Optional features. A program that has features that are useful only in some contexts — hardware acceleration, support for a particular file format, a licensing module — can load the feature's library only when the feature is requested. The program's initial memory footprint is smaller, and the code for unused features is not loaded at all.
• Language runtimes. A language runtime that supports foreign-function interfaces — Python's ctypes, Java's JNI, Node.js's node-gyp — loads a native library at runtime, looks up the native functions, and calls them from the interpreted language.
• Dynamic configuration. A program can choose among several implementations of a feature at runtime — for example, choosing the appropriate device driver for the hardware it detects — by loading the corresponding library.

The dlopen API is the modern form of dynamic loading. It loads at library granularity rather than at routine granularity, and it is explicit in the code rather than generated by the toolchain. But the underlying idea — load what you need when you need it — is the same idea that the classical dynamic loader implemented.

4.8 The relationship to virtual memory

Dynamic loading, dynamic linking, and swapping are all solutions to the same underlying problem: the total code and data of the system's programs exceeds the physical memory available to hold it. The problem is overcommitment, introduced in Lesson 8.1 as one of the three requirements that makes memory management difficult.

Each mechanism solves the problem at a different granularity and with different assumptions:

• Overlays solve it at the granularity of programmer-chosen segments, with the programmer responsible for the partition. It requires detailed knowledge of the program's call structure and works only for a single program.
• Dynamic loading solves it at the granularity of routines, with the programmer responsible for identifying which routines should be loaded on demand. It requires per-routine stubs and a runtime loader, and it works for a single program's routines.
• Dynamic linking solves it at the granularity of libraries, with the toolchain and the dynamic linker responsible for the mechanism. It requires position-independent code and a dynamic linker, and it shares library code among all processes on the system.
• Swapping solves it at the granularity of entire processes, with the operating system responsible for the policy. It requires a swap area and a victim-selection policy, and it handles the case where the sum of all processes' addresses spaces exceeds physical memory.
• Demand paging — the subject of Unit 9 — solves it at the granularity of pages, with the operating system responsible for the mechanism and the policy. It requires a page table, a translation lookaside buffer, and a page-replacement policy, and it subsumes the granularities of all the mechanisms above: a page can be part of a routine that is dynamically loaded, part of a library that is dynamically linked, or part of a process that would otherwise be swapped.

The trend is clear: the trend is toward finer granularity and toward moving the responsibility from the programmer to the operating system. Overlays require the programmer to partition the program by hand; dynamic loading requires the programmer to write stubs; dynamic linking moves the mechanism to the toolchain; swapping and demand paging move it to the kernel. Each step makes the mechanism more automatic and more general, at the cost of more complex hardware and operating-system support.

Demand paging is the endpoint of this progression: it handles overcommitment at the finest possible granularity, with no programmer involvement at all, and it generalises all the mechanisms above it. The rest of Unit 8 presents the classical allocation techniques that were used before paging was universal, and Unit 9 presents demand paging itself. The classical techniques — contiguous allocation, fragmentation, segmentation — are not obsolete; they are the foundation on which paging was built, and understanding them is what makes the design of paging legible.

4.9 Common misconceptions

05 Worked example

The following example implements a simple plugin system with dlopen and dlsym, and compares its behaviour to a statically linked version.

/* plugin.h — the interface shared by the calculator and its plugins */
#ifndef PLUGIN_H
#define PLUGIN_H

typedef int (*binary_op_t)(int a, int b);

/* Every plugin exports a symbol named "op" of this type. */
extern binary_op_t op;

#endif

/* add.c — plugin for addition */
#include "plugin.h"

static int add(int a, int b) { return a + b; }
binary_op_t op = add;

/* mul.c — plugin for multiplication */
#include "plugin.h"

static int mul(int a, int b) { return a * b; }
binary_op_t op = mul;

/* calc.c — the host program */
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>
#include "plugin.h"

int main(int argc, char **argv) {
    if (argc != 4) {
        fprintf(stderr, "usage: %s OP A B\n", argv[0]);
        return 1;
    }

    const char *opname = argv[1];
    int a = atoi(argv[2]);
    int b = atoi(argv[3]);

    /* build the library filename: "libOP.so" */
    char libname[256];
    snprintf(libname, sizeof(libname), "./lib%s.so", opname);

    void *handle = dlopen(libname, RTLD_NOW);
    if (!handle) {
        fprintf(stderr, "dlopen: %s\n", dlerror());
        return 1;
    }

    /* clear any previous error */
    dlerror();

    binary_op_t *op_ptr = dlsym(handle, "op");
    const char *err = dlerror();
    if (err) {
        fprintf(stderr, "dlsym: %s\n", err);
        dlclose(handle);
        return 1;
    }

    printf("%s(%d, %d) = %d\n", opname, a, b, (*op_ptr)(a, b));

    dlclose(handle);
    return 0;
}

$ gcc -shared -fPIC -o libadd.so add.c
$ gcc -shared -fPIC -o libmul.so mul.c
$ gcc -o calc calc.c -ldl

$ ./calc add 3 4
add(3, 4) = 7

$ ./calc mul 3 4
mul(3, 4) = 12

$ ./calc div 3 4
dlopen: ./libdiv.so: cannot open shared object file:
        No such file or directory

06 Interactive activity

07 Knowledge check

08 Unit discussion

09 Practice exercise

10 Summary

• Static loading reads the entire program image into memory at startup. It is simple, predictable, and requires no runtime machinery, but its memory footprint includes every routine whether or not it is used.
• Dynamic loading loads a routine into memory only when it is first called. It saves memory by not loading routines that are never used, at the cost of a first-call delay for the routines that are.
• The dynamic loader is part of the program's runtime, not the operating system. The OS provides only the primitive operations — reading files, allocating memory, mapping memory — that the loader uses.
• Sticky residency is the rule that a loaded routine stays in memory for the remainder of the program's execution. There is no eviction, and the program's memory usage under dynamic loading is monotonically increasing.
• Dynamic loading and dynamic linking are different mechanisms for different problems. Dynamic loading loads individual routines on demand; dynamic linking shares entire libraries among processes. The two are complementary and are used together in modern systems.
• Overlays were the historical precursor to dynamic loading. The programmer partitioned the program into segments and arranged for one to overwrite another. Overlays disappeared when demand paging made the same result automatic.
• Swapping moves an entire process address space between memory and disk. It is coarser than demand paging, and classical swapping has largely been superseded by demand paging, but the swap area survives as the backing store for paged-out pages.
• The dlopen API is the modern form of dynamic loading. It loads a shared library at runtime, and it is used for plugin systems, optional features, language runtimes, and dynamic configuration. The functions are dlopen, dlsym, dlclose, and dlerror.
• Dynamic loading, dynamic linking, overlays, swapping, and demand paging are all solutions to the same underlying problem — overcommitment, introduced in Lesson 8.1 — at different granularities and with different assumptions. The trend is toward finer granularity and toward moving the responsibility from the programmer to the operating system.
• Demand paging, the subject of Unit 9, is the endpoint of this progression. It handles overcommitment at the granularity of a page, with no programmer involvement, and it subsumes the granularities of all the mechanisms that came before it.

11 References

• Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Sections 9.1 and 9.2.
• Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 7, Linking, especially sections 7.9–7.13 on shared libraries and runtime loading.
• Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Sections 3.3–3.4.
• Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 18 and 21. Available online at ostep.org.
• Levine, J. R. Linkers and Loaders. Morgan Kaufmann, 1999. Chapters 1–2, and Chapter 8 on dynamic linking.
• Hoare, C. A. R., & Wirth, N. An Axiomatic Definition of the Programming Language PASCAL. Acta Informatica, 1973. The original Pascal report, which mentions the overlay technique in its discussion of program structure.
• Denning, P. J. Virtual Memory. ACM Computing Surveys, 1970. The paper that introduced the working-set model and framed the discussion of paging, which is the direct descendant of dynamic loading.
• Linux man-pages: man 3 dlopen, man 3 dlsym, man 3 dlerror, man 3 dlclose, man 1 ld.so, man 1 ldd, man 8 swapon, man 5 proc.