Lesson 8.2: Address Binding

01 Introduction

Lesson 8.1 established the physical basis of memory: a hierarchy of storage levels, with locality of reference making the hierarchy effective, and with main memory and below managed by the operating system. This lesson turns to the first of the operating system's problems: a program is not written in terms of physical memory addresses. It is written in terms of symbols — the names of variables, functions, and labels — and it is compiled into machine code that refers to addresses. The addresses in the compiled program are not the physical addresses that the hardware uses, because the program does not know where in memory it will be loaded, and because it may be loaded at a different location each time it runs.

The process of assigning a definite memory location to a symbol or an address is called address binding. The question of when this binding happens — at compile time, at load time, or at execution time — is the central topic of this lesson. The answer determines what the operating system must do, what the hardware must support, and what the programmer can take for granted.

Consider what happens in the simplest possible scenario. A program is compiled with the assumption that it will be loaded at a fixed physical address — say, address 0x10000. The compiler generates machine code in which every reference to a variable is an absolute address, computed from that starting point. When the program is loaded, the loader must place it at 0x10000 exactly. If the address is already in use — because another program occupies that region — the load cannot succeed. The program cannot be moved, because every address in it would have to be adjusted, and the machine code contains no record of which bytes are addresses and which are data. This is compile-time binding, and it is the simplest and least flexible form.

Now suppose the compiler generates code that refers to addresses relative to the start of the program — "the word at offset 0x200 from the beginning" rather than "the word at address 0x10200". The program can then be loaded at any address, and the loader adjusts the base. This is load-time binding, and it requires the loader to be able to add the load address to every relocatable reference. The program can be loaded anywhere, but it cannot be moved after it starts running, because the adjustments are made once, at load time.

Finally, suppose the program's references remain relative throughout its execution, and the hardware translates them to physical addresses at the moment of each access. The program can then be moved at any time, because its addresses are always interpreted relative to the current base. This is execution-time binding, and it is the mechanism behind every modern memory-management system. It requires the hardware to have a memory-management unit that performs the translation on every access, and it is what allows the operating system to swap programs in and out of memory, to share memory between processes, and to enforce protection.

This lesson presents the three binding times, the distinction between logical and physical addresses that they introduce, and the hardware and software mechanisms that make each possible. It covers the relocation register, the memory-management unit, the difference between static and dynamic linking, position-independent code, and the modern view of address translation as it exists on a contemporary processor. The lesson closes with a discussion of what these mechanisms cost and why every real system uses execution-time binding despite the cost.

Prerequisites

This lesson builds directly on Lesson 8.1. The memory hierarchy, the distinction between what the hardware manages and what the operating system manages, and the three responsibilities of the operating system (allocation, protection, transparency) are all assumed. The process address space from Lesson 3.1 — code, data, heap, and stack segments — is the abstraction that the binding mechanisms realise. No prior knowledge of the memory-management unit is assumed; the relevant hardware is introduced here.

02 Learning objectives

By the end of this lesson you will be able to

Distinguish symbolic, relocatable, and absolute addresses, and explain the translation between them.
Describe the three binding times — compile, load, and execution — and the mechanisms required by each.
Distinguish logical from physical addresses and explain the role of the memory-management unit.
Explain the operation of the relocation register and the base-and-limit scheme.
Describe static and dynamic linking, position-independent code, and the modern view of address translation.

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

03 Required reading

Operating System Concepts — Chapter 9, Section 9.1, Background (the part on address binding), and Section 9.2, Contiguous Memory Allocation, through the introduction of the memory-management unit. The standard treatment of the three binding times and the logical/physical distinction.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.2, A Memory Abstraction: Address Spaces, and Section 3.3, Virtual Memory (the introductory part). A complementary treatment that develops the case for dynamic relocation from first principles.
OSTEP — Chapter 15, Mechanism: Address Translation, and Chapter 16, Segmentation (the introductory part). OSTEP's treatment of the base-and-bounds mechanism is the clearest available explanation of the relocation register.
Bryant, R. E., & O'Hallaron, D. R. — Computer Systems: A Programmer's Perspective, Chapter 7, Linking. The definitive treatment of static and dynamic linking, relocation, and position-independent code from the programmer's and the toolchain's perspective. Read sections 7.1 through 7.7 for the material on the linker, and sections 7.12–7.13 for the material on shared libraries.
Levine, J. R. — Linkers and Loaders. Morgan Kaufmann, 1999. The book-length treatment of the toolchain that performs address binding. Chapter 1 and Chapter 2 are the most relevant.
Linux man pages: man 1 ld, man 1 ld.so, man 8 ldconfig, man 5 elf, man 1 readelf, man 1 objdump, man 2 mmap, man 5 proc (the /proc/<pid>/maps interface).

Reading strategy

Read the Silberschatz section first for the formal definitions and the three binding times. Then read the Bryant & O'Hallaron chapter on linking for the concrete, toolchain-level view: how the linker assigns addresses to symbols, how relocation records are generated and applied, and how shared libraries are made to work despite being loaded at unpredictable addresses. The two views are complementary: the operating-systems view is concerned with the hardware mechanism of translation, while the toolchain view is concerned with the software process that produces the addresses being translated. The lesson's worked example bridges the two by inspecting a real binary with readelf.

04 Core content

4.1 Three kinds of address

A program's addresses exist at three distinct levels of abstraction. Understanding the difference between them is the foundation of everything in this lesson.

Symbolic addresses: The names that appear in source code: counter, main, loop_start, buffer. Symbolic addresses are meaningful to the programmer and to the compiler, but they have no relationship to memory layout. The compiler translates them into addresses in one of the two lower forms, and after compilation the symbols survive only in the symbol table, used by the linker and the debugger.
Relocatable addresses: The form produced by the compiler when the final location of the program is not yet known. A relocatable address is an offset from the beginning of the program or from the beginning of a section: "the word at offset 0x200 from the start of the .data section". The linker and the loader combine relocatable addresses from many object files into a single loadable image, and eventually convert them to absolute addresses.
Absolute addresses: A specific, physical memory address: "the byte at physical address 0x7FFF_5C40_1000". Absolute addresses are what the hardware's memory bus actually uses. They are produced from relocatable addresses by adding a base, and the point at which this addition happens determines the binding time.

The translation chain is: symbolic → relocatable → absolute. Each arrow is performed by a specific tool or mechanism. The compiler performs the first translation, producing object files in which the symbols have been resolved to relocatable addresses (and unresolved symbols are recorded in a table for the linker). The linker or the loader performs the second, combining the relocatable addresses from many object files and, depending on the binding time, either assigning absolute addresses immediately or leaving the references relocatable for the hardware to resolve at runtime.

4.2 The three binding times

The point in a program's life at which a relocatable address is converted to an absolute address is called the binding time. There are three possibilities.

Compile-time binding: The absolute address is known when the program is compiled. If the compiler knows that the program will always be loaded at, say, address 0x10000, it can generate machine code in which every reference is an absolute address computed from that base. The resulting binary is called a load module or an absolute binary. The advantage is that no translation is needed at load time or at execution time: the CPU can fetch instructions and data directly. The disadvantage is severe: the program cannot be moved once it is compiled. If the intended address is occupied by another program, the load fails. The program cannot be swapped out and brought back at a different address. The system cannot run two instances of the program at the same time if both would claim the same fixed address. This form of binding is used in embedded systems with a single fixed task, and in the very earliest batch systems.
Load-time binding: The compiler produces relocatable code, and the loader converts the relocatable addresses to absolute addresses when the program is loaded into memory. The compiler emits a relocation table that records which instructions and data words contain addresses that need to be adjusted, and the loader adds the load address to each of them. The program can be loaded at any address — the loader chooses one based on what is available — but once loaded, it cannot be moved. Moving it would require re-running the relocation, and the relocation table may not be preserved. This form of binding was common in early time-sharing systems, and it is what the original UNIX loader did.
Execution-time binding: The compiler produces relocatable code, and the conversion to absolute addresses happens during execution, on every memory access, performed by a hardware component called the memory-management unit (MMU). The program's addresses, as seen by the CPU, are called logical (or virtual) addresses; the addresses that reach the memory bus are called physical addresses. The MMU translates logical to physical on each access, using information that the operating system has set up. The advantage is complete flexibility: the program can be loaded anywhere, moved at any time, split across non-contiguous physical memory, and even partially resident on disk. The cost is the hardware required for the translation and the overhead of performing it on every access — a cost that is mitigated in practice by the translation lookaside buffer, described in Unit 9. Every modern general-purpose system uses execution-time binding, and the rest of this unit and the next are largely about how it works.

Figure 8.2 — The three address-binding times. In compile-time binding, absolute addresses are produced by the compiler and no further translation occurs. In load-time binding, relocatable code is produced by the compiler and converted to absolute addresses by the linker and loader. In execution-time binding, the compiler and linker produce logical addresses, and the memory-management unit translates each to a physical address at runtime.

4.3 Logical versus physical addresses

The distinction between logical and physical addresses is the central conceptual contribution of execution-time binding. It did not exist before execution-time binding was invented, because in the earlier schemes there was only one kind of address — the physical one — and the distinction between "the address the program refers to" and "the address the hardware uses" was meaningless.

Logical address (also called virtual address): The address that the CPU generates when it executes an instruction — the value of the program counter, the address computed by an addressing mode, the operand of a load or store. A logical address is what the program sees; it is the address in the abstract address space that the process believes it occupies. It is not a physical memory location.
Physical address: The address that the memory bus uses to select a location in the memory chips. A physical address is what the hardware needs to retrieve a byte. It is the address after translation, and it is the address that the memory controller understands.

In a system with execution-time binding, the two kinds of address are distinct, and the mapping between them is maintained by the operating system. The CPU generates logical addresses; the MMU translates them to physical addresses using the mapping the operating system has established; the memory bus delivers the data from the physical location. The program is unaware that any translation is happening — it sees only its own logical address space, which it believes to be its private, contiguous memory.

In a system with compile-time or load-time binding, the two kinds of address coincide. The program refers to physical addresses directly, and there is no translation. The logical address of a variable and its physical address are the same number. This is why the distinction is only meaningful when execution-time binding is in use.

Why the distinction matters

The separation of logical from physical addresses is what makes protection possible. If a process refers to logical addresses and the MMU translates them using a per-process mapping, then the process can only reach the physical memory that the operating system has mapped into its address space. A bug that computes a wild pointer — say, a logical address far outside the process's code and data — produces a translation fault rather than corrupting another process's memory, because the operating system has not mapped any physical memory at that logical address. This is the mechanism that turns a memory-corruption bug into a segmentation fault.

4.4 The memory-management unit

The memory-management unit (MMU) is the hardware component that performs the translation from logical to physical addresses. It sits between the CPU and the memory bus: the CPU issues a logical address, the MMU translates it, and the resulting physical address is placed on the bus. The translation happens on every instruction fetch and every data access, and it must be fast enough not to become the bottleneck of the machine.

The MMU's behaviour depends on the memory-management scheme in use. In the simplest case — the base-and-limit scheme — the MMU holds two registers, and the translation is a single addition. In the more general case — paging, the subject of Unit 9 — the MMU holds a page table base register and consults a page table on each access. In either case, the MMU is programmable: the operating system sets its registers when it switches from one process to another, and the MMU's translation therefore changes to match the address space of the running process.

The MMU is not visible to the program. Programs are written in terms of logical addresses, and they behave identically whether the MMU is translating or not. This is the transparency requirement from Lesson 8.1 in its purest form: the MMU is the mechanism that makes the physical memory layout invisible to the code being run.

4.5 The relocation register and base-and-limit

The simplest execution-time binding mechanism is the base-and-limit scheme, also called the relocation register scheme. The MMU holds two registers:

The base register (or relocation register) holds the physical address at which the process's memory begins.
The limit register (or bound register) holds the size of the process's memory region.

On every memory access, the MMU performs two checks and one addition:

Check the logical address against the limit. If the logical address is greater than or equal to the limit, the access is out of bounds — the program is trying to reach outside its own region — and the MMU raises a fault, which the operating system handles (typically by terminating the process). This check is what enforces protection: a process cannot reach memory outside its own region, no matter what logical address it computes.
Add the base to the logical address. The result is the physical address: physical = logical + base. This is the actual translation.
Perform the access. The physical address is placed on the memory bus, and the memory system fetches or stores the data.

The base-and-limit scheme is extraordinarily simple, and that is its virtue. The translation is a comparison and an addition — a few nanoseconds — and it can be performed on every access without measurable cost. The scheme supports the three requirements of Lesson 8.1 in a minimal form: each process has its own base and limit, so processes can be allocated different regions of memory (allocation); the limit check prevents a process from reaching outside its region (protection); and the program sees only its own logical address space, numbered from 0 to limit (transparency).

The scheme has serious limitations, which the rest of the unit and Unit 9 will address. Because a process's physical memory is a single contiguous region, the operating system must find a contiguous block of physical memory large enough for the process, which leads to the fragmentation problems of Lesson 8.5. The scheme does not allow the process's memory to be split across non-contiguous regions, so the operating system cannot use scattered free blocks. And the scheme does not allow sharing of memory between processes, because each process has a single base register. These limitations motivate segmentation (Lesson 8.6) and paging (Unit 9).

Figure 8.2b — The base-and-limit translation scheme. The MMU holds a base register and a limit register. On each access, it checks the logical address against the limit and, if valid, adds the base to produce the physical address. The limit check enforces protection, and the base addition implements the relocation. The scheme is the simplest form of execution-time binding and is the conceptual foundation of every more elaborate mechanism.

4.6 Static and dynamic linking

Address binding is not confined to the operating system. It also happens in the toolchain, at the moment the linker combines a program's object files with the libraries it uses. The choice between static and dynamic linking is a binding-time decision in the same sense as the three binding times: it determines when a program's references to library functions are resolved, and therefore what the resulting binary contains.

Static linking: The linker copies the code of every library function the program uses into the executable, and resolves all references at link time. The resulting binary contains everything it needs and has no external dependencies. The advantage is simplicity: the binary is self-contained and can be run on any system with the same architecture. The disadvantage is size and duplication: if twenty programs on a system all use the standard C library, the library's code is present twenty times, once in each binary, consuming disk space and (when the programs run) memory. Static linking was the original approach, and it is still used for embedded systems and for programs that must be self-contained.
Dynamic linking: The library code is not copied into the executable. Instead, the linker records a reference to the library, and the actual binding of the reference to a memory address happens at load time or at execution time. The library is loaded once into physical memory (or is already resident), and every process that uses it shares the same copy through the MMU's mapping. The advantage is size and sharing: a hundred programs using the same library consume only one copy of the library's memory. The advantage extends to updates: replacing a library on disk changes the behaviour of every program that uses it, without recompiling any of them. The disadvantage is complexity: dynamic linking requires the program to be relocatable, requires the loader to resolve the references at runtime, and introduces the possibility of dependency conflicts ("DLL hell" on Windows, "shared library versioning" on Linux).

On a Linux system, dynamic linking is the default. A program's executable contains its own code and data, and it refers to shared libraries — files with the .so suffix, for "shared object" — for everything else, including the C library itself. The program is loaded by the dynamic linker (ld.so or ld-linux.so), which reads the program's list of required libraries, loads each one into memory, and resolves the program's references to the library's symbols. This resolution happens either at load time (in the simplest case) or lazily, on the first use of each symbol, which avoids the cost of resolving symbols that are never called.

Dynamic linking is the reason execution-time binding is not just a hardware feature but a system-wide design choice. A dynamically linked program cannot contain absolute addresses for its library functions, because the library may be loaded at a different address in each process. The program's references to those functions must be resolved at runtime, and the resolution must go through the MMU, because the address of the library function in physical memory is not known until the library is loaded. This is achieved by position-independent code.

4.7 Position-independent code

Position-independent code (PIC) is machine code that can be loaded at any address without modification. It achieves this by avoiding absolute addresses entirely: every reference is relative to the current instruction pointer, or is made through a table of pointers whose contents are filled in at load time by the dynamic linker.

The two techniques are worth understanding, because they are the practical realisation of execution-time binding in the toolchain.

PC-relative addressing. On modern architectures (x86-64, ARM64), most instructions that reference data or code can use an addressing mode that computes the target as an offset from the current program counter. Because the offset is the same regardless of where the code is loaded, the instruction works without modification at any load address. The compiler generates PC-relative references wherever it can, which is for most intra-module references.
The Global Offset Table (GOT). For references that cannot be PC-relative — calls to functions in other shared libraries, references to global variables that must have a single address — the compiler creates a table of pointers, the GOT. The code references the GOT by PC-relative addressing, and the GOT's contents are filled in by the dynamic linker at load time with the actual runtime addresses of the symbols. The code itself is unchanged; only the table's contents depend on the load address.
The Procedure Linkage Table (PLT). For calls to functions in other shared libraries, the compiler generates a small stub in the PLT, and the code calls the stub. On the first call, the stub jumps to the dynamic linker, which resolves the target address and patches the PLT entry; on subsequent calls, the stub jumps directly to the resolved function. This is the mechanism of lazy binding: the resolution of a symbol is deferred until it is first used, so programs that use only a fraction of a large library pay only for what they use.

The net effect is that a dynamically linked program contains no absolute addresses for anything it imports. Its own code and its own statically-linked data have addresses that are relative to the module's base, and everything it imports is reached through the GOT and the PLT. The dynamic linker fills in the table entries when the program starts or, lazily, on first use. The program is therefore position-independent, and the operating system can map it into memory at any address — including at different addresses in different processes, which is what allows the same library code to be shared among many processes.

Sharing and copy-on-write

When many processes use the same shared library, the operating system maps the same physical pages into each process's address space. The library's code is read-only and is genuinely shared: all processes read the same bytes, and no process can modify them. The library's data is different: each process needs its own copy, because a global variable in the library must have a different value in each process. The operating system handles this with copy-on-write: the data pages are initially mapped read-only and shared, and when a process writes to one, the kernel makes a private copy for that process. This is the same mechanism that makes fork() efficient, and it is one of the principal advantages of execution-time binding.

4.8 The modern view

The three binding times are the classical framework, and they are still the right way to think about the design space. But in a modern system, the boundaries between them have blurred, and the reality is a combination of all three.

Compile-time decisions. The compiler decides the layout of a program's code and data within its logical address space, and it chooses the addressing modes for each instruction. These decisions fix the relative addresses of everything in the module, but not the absolute addresses. In this sense, modern compilation is a form of relocatable binding: the compiler produces relocatable code, and the absolute addresses are left for later.
Link-time decisions. The static linker combines the object files into a single executable. On a modern system, this executable is usually position-independent: its code and data are arranged in a fixed layout within the module, and all references within the module are relative. The linker also records which shared libraries the program needs and which symbols it imports from each. This is a form of load-time binding for the static parts of the program and a form of execution-time binding for the dynamic parts.
Load-time decisions. The dynamic linker loads the program and its shared libraries into memory, and it fills in the GOT and the PLT with the actual runtime addresses of the imported symbols. This is genuinely load-time binding: the translation from a symbolic reference to a physical address happens once, when the program starts. The lazy variant of the process defers the resolution of each symbol until it is first called, which is a form of execution-time binding for the imports.
Execution-time decisions. The MMU translates every logical address to a physical address at the moment of each access, using the page tables the operating system has set up. This is genuine execution-time binding, and it is the mechanism that makes the entire system work: it is what allows a program to be loaded at an arbitrary physical address, to be moved at any time, to share memory with other processes, and to be protected from them.

The modern system therefore uses all three binding times at once, each for the aspect of the problem it handles best. Compile-time binding is used for the layout within a module, because it costs nothing at runtime. Load-time binding is used for the resolution of imported symbols, because it is a one-time cost that avoids repeated work. Execution-time binding is used for the mapping from logical to physical addresses, because it is the only form that provides the flexibility (movability, sharing, overcommitment) that a modern system requires.

This layering is the practical answer to the question of binding time. It is not a choice between compile-time, load-time, and execution-time binding; it is a choice of which aspect of address resolution to handle at which time. Every modern system chooses the same answer: bind the module's internal layout at compile time, bind the imports at load time, and bind the physical mapping at execution time. The result is a system that is nearly as fast as compile-time binding for the common case, and nearly as flexible as full execution-time binding for everything that matters.

4.9 Common misconceptions

"Logical and physical addresses are the same thing."

They are the same in a system with compile-time or load-time binding, where there is no translation. They are different in a system with execution-time binding, which is every modern system. The distinction is only meaningful when the MMU is translating.

"The compiler assigns physical addresses."

The compiler assigns relocatable addresses — offsets within a module — not physical addresses. Physical addresses are assigned by the loader or by the MMU, depending on the binding time.

"The MMU is software."

The MMU is a hardware component, separate from the CPU, that sits between the CPU and the memory bus. The operating system programs it — setting its base register, its limit register, or its page-table base on each context switch — but the translation itself is performed by hardware.

"Compile-time binding is obsolete."

It survives in embedded systems with a single fixed task, where the program is the only thing running and the address is genuinely known. It also survives in a partial form: the compiler still lays out a program's internal structure, and that layout is fixed relative to the module's base.

"Static linking is faster than dynamic linking."

Static linking avoids the runtime cost of resolving symbols, but that cost is paid once at load time and is negligible for most programs. Dynamic linking saves memory and disk space by sharing library code. The performance difference is usually much smaller than the memory and maintenance difference.

"Position-independent code is a compiler trick."

PIC is a property of the code the compiler generates, but it is required by a system-level design decision: the decision to share library code among processes. Without PIC, shared libraries could not be shared, because each process would need its own copy at a fixed address.

"The base register points to address 0."

The base register holds the physical address at which the process's memory begins, which is the physical address corresponding to the process's logical address 0. It is not necessarily 0 itself; it is the start of the region the operating system allocated to the process.

"Address binding is only about loading programs."

Address binding is a general problem that arises whenever a name must be resolved to a location. It appears in loading, in linking, in function call resolution, in dynamic dispatch in object-oriented languages, and in every layer of the software stack. The three binding times are the framework for all of it.

05 Worked example

The following example traces the base-and-limit translation for several accesses, and then inspects a real Linux binary to see the binding decisions that the toolchain made.

Base-and-limit translation, step by step

A process has been allocated physical memory starting at address base = 8,000 with limit = 2,000. The process's logical address space is therefore 0 through 1,999, and it maps to physical addresses 8,000 through 9,999. The following table traces four memory accesses.

Logical address	Check: logical < limit?	Physical address	Result
0	0 < 2,000: yes	8,000	valid — reads the first byte of the process's memory
1,200	1,200 < 2,000: yes	9,200	valid — reads a byte in the middle of the region
1,999	1,999 < 2,000: yes	9,999	valid — reads the last byte of the region
2,000	2,000 < 2,000: no	—	fault — the access is out of bounds
50,000	50,000 < 2,000: no	—	fault — the access is far outside the region

The pattern is clear. The check against the limit is what enforces protection: any logical address at or beyond the limit is rejected, and the process cannot reach memory outside its own region. The addition of the base is what performs the relocation: the same logical address produces different physical addresses in different processes, because each process has a different base.

Notice that the limit check is performed before the addition, not after. This matters: if the check were performed after the addition, the process could compute a logical address that, when added to the base, happened to land inside the process's region — and would then have reached a valid physical address, even though the logical address was out of bounds. Performing the check first ensures that the boundary is enforced in terms of the process's own address space, which is the address space the process understands.

Two processes sharing the machine

Now consider two processes running concurrently. Process A has base = 8,000, limit = 2,000; process B has base = 15,000, limit = 3,000. Each executes the same code, which accesses logical address 1,200.

Process	Base	Limit	Logical address	Physical address
Process A	8,000	2,000	1,200	9,200
Process B	15,000	3,000	1,200	16,200

The two processes access the same logical address but reach different physical memory. This is the essence of the address-space abstraction: each process has its own private logical address space, numbered from 0, and the MMU translates the logical addresses of the running process to physical addresses using that process's base and limit. The processes are unaware of each other and cannot interfere, because each one's accesses are confined to its own region.

What happens on a context switch

When the operating system switches from Process A to Process B, it must change the MMU's registers. The scheduler saves A's state, loads B's state, and then writes B's base and limit into the base and limit registers. From that moment on, B's logical addresses are translated using B's base. If the operating system forgot to update the registers, B would run with A's translation, and its accesses would reach A's memory — a catastrophic protection failure. The update of the MMU registers is therefore a mandatory part of the context switch, and it is one of the reasons context switching is expensive enough to matter for scheduling policy (Lesson 5.1).

Inspecting a real binary

On a Linux system, the binding decisions made by the toolchain are visible in the executable's ELF headers. Use readelf to inspect a small program.

$ cat > hello.c <<'EOF'
#include <stdio.h>
int main(void) {
    printf("hello, world\n");
    return 0;
}
EOF

$ gcc -o hello hello.c

$ file hello
hello: ELF 64-bit LSB pie executable, x86-64, ...

The key word is pie: Position-Independent Executable. The modern default for Linux executables is a PIE, which means the program's own code is position-independent and can be loaded at any address. The readelf tool shows how this is achieved.

$ readelf -h hello | grep Type
  Type:  DYN (Position-Independent Executable file)

$ readelf -S hello | head -20
There are 30 section headers, starting at offset 0x3a90:

Section Headers:
  [Nr] Name              Type             Address          Offset
  [ 0]                   NULL             0000000000000000 00000000
  [ 1] .interp           PROGBITS         0000000000000318 00000318
  [ 2] .note.gnu.pr[...] NOTE             0000000000000338 00000338
  ...
  [ 5] .dynsym           DYNSYM           00000000000003c0 000003c0
  [ 6] .dynstr           STRTAB           00000000000004a8 000004a8
  ...

The .interp section names the dynamic linker that will load this program (/lib64/ld-linux-x86-64.so.2 on a typical Linux system). The .dynsym and .dynstr sections hold the program's imported symbols and their names. The .rela.dyn and .rela.plt sections, if present, hold the relocation records that the dynamic linker will apply.

To see the dynamic dependencies — the shared libraries the program requires — use ldd or readelf -d.

$ ldd hello
    linux-vdso.so.1 (0x00007ffd6b3d8000)
    libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f...)
    /lib64/ld-linux-x86-64.so.2 (0x00007f...)

$ readelf -d hello | grep NEEDED
 0x0000000000000001 (NEEDED)  Shared library: [libc.so.6]

The program needs libc.so.6, the standard C library. The dynamic linker will load it into memory and resolve the reference to printf when the program starts (or, with lazy binding, the first time printf is called). The library's address is chosen at load time — it is not fixed, as the two different addresses for linux-vdso.so.1 and libc.so.6 in the ldd output above suggest — and the program's call to printf goes through the PLT, which the dynamic linker has patched with the library's runtime address.

Finally, the program's own layout in a running process can be seen in /proc/<pid>/maps. Run the program and inspect its address space.

$ ./hello &
$ PID=$!
$ cat /proc/$PID/maps
55d5c4f0b000-55d5c4f0c000 r--p 00000000 08:01 1234  /home/user/hello
55d5c4f0c000-55d5c4f0d000 r-xp 00001000 08:01 1234  /home/user/hello
55d5c4f0d000-55d5c4f0e000 r--p 00002000 08:01 1234  /home/user/hello
55d5c4f0e000-55d5c4f0f000 r--p 00002000 08:01 1234  /home/user/hello
55d5c4f0f000-55d5c4f10000 rw-p 00003000 08:01 1234  /home/user/hello
55d5c6c8f000-55d5c6cb0000 rw-p 00000000 00:00 0     [heap]
7f9e3c4a0000-7f9e3c4c8000 r--p 00000000 08:01 5678  /usr/lib/.../libc.so.6
7f9e3c4c8000-7f9e3c65d000 r-xp 00028000 08:01 5678  /usr/lib/.../libc.so.6
...
7ffd1a2c0000-7ffd1a2e1000 rw-p 00000000 00:00 0     [stack]

Several features of the address space are visible. The program's own code and data appear as multiple consecutive regions, one per ELF segment, with different permissions: read-only for the data (the r--p regions), read-execute for the code (r-xp), and read-write for the modifiable data (rw-p). The heap is a separate region, also read-write. The libraries appear at high addresses, in a region reserved for shared objects. The stack appears at the very top of the address space, in its own region.

Notice that the program's own regions have a base address — 55d5c4f0b000 in this run — that is not fixed. On a different run, or on a different machine, the base would be different. This is the practical consequence of execution-time binding: the program's logical addresses are the same on every run, but the physical addresses they map to are chosen afresh each time the program is loaded.

Static linking for comparison

Compile the same program with static linking and inspect the difference.

$ gcc -static -o hello_static hello.c
$ file hello_static
hello_static: ELF 64-bit LSB executable, x86-64, ...

$ ls -lh hello hello_static
-rwxr-xr-x 1 user user 16K ... hello
-rwxr-xr-x 1 user user 780K ... hello_static

$ ldd hello_static
    not a dynamic executable

$ readelf -h hello_static | grep Type
  Type:  EXEC (Executable file)

The statically linked binary is nearly fifty times larger, because it contains the C library's code. Its ELF type is EXEC, not DYN: it is a fixed-address executable, not a position-independent one. Its imports are not needed, because everything it uses is inside it. The dynamically linked binary, by contrast, is tiny and depends on the shared libraries that are already loaded on the system.

The trade-off is exactly the one described in section 4.6. The static binary is self-contained and avoids the runtime cost of dynamic linking, but it consumes far more memory and disk space, and its library code is duplicated across every statically linked program on the system. The dynamic binary is small and shares library code with other programs, but it requires the dynamic linker and the libraries to be present, and it pays the cost of resolving symbols at load time. On a modern system, dynamic linking is the default because the memory savings are large and the runtime cost is small.

06 Interactive activity

Activity · inspect address binding in the toolchain

The goal of this activity is to see the address-binding decisions of a real toolchain, to inspect the ELF format that records them, and to observe the difference between static and dynamic linking. Work through the steps in your course VM.

Write a small program. Write the hello.c program from the worked example, compile it, and inspect its file type.
```
gcc -o hello hello.c
file hello
```
The output should say "pie executable" on a modern Linux system, indicating that the program is position-independent. If it says "executable" instead, your toolchain may be configured differently; note the difference and continue.
Inspect the ELF headers. Use readelf to examine the program's ELF structure.
```
readelf -h hello | head -20
readelf -S hello | head -40
readelf -d hello | head -20
```
Identify the following: the ELF type (EXEC or DYN), the entry point address, the section headers, and the dynamic dependencies. Write down what you find.
List the shared libraries. Use ldd to list the program's shared library dependencies.
```
ldd hello
```
Note the libraries it requires and their paths. The presence of libc.so.6 means the program uses the standard C library, and the address shown in parentheses is the load address that the dynamic linker would choose (it may vary between runs).
Inspect the dynamic symbols. Use readelf --dyn-syms to see the program's imported symbols.
```
readelf --dyn-syms hello | head -30
```
The list should include printf and other functions the program uses from the C library. Note that these are undefined (marked UND), meaning they will be resolved at load time by the dynamic linker.
Inspect the relocation records. Use readelf -r to see the relocation records.
```
readelf -r hello
```
The records in .rela.dyn and .rela.plt are the instructions to the dynamic linker for how to patch the program's code once the library's address is known. Note the type of each relocation: R_X86_64_GLOB_DAT and R_X86_64_JUMP_SLOT are the entries for the GOT and the PLT, respectively.
Inspect the running address space. Run the program in the background and inspect its memory map.
```
./hello &
PID=$!
cat /proc/$PID/maps
kill $PID
```
Identify the following regions: the program's own code, data, and read-only data (they will have the program's pathname); the heap; the shared libraries (with paths in /usr/lib or /lib); the stack; and the [vdso] region, which is a small virtual shared object the kernel maps into every process. Write down the addresses of the first and last regions.
Compare static and dynamic linking. Compile the program again with -static and compare the two binaries.
```
gcc -static -o hello_static hello.c
ls -l hello hello_static
file hello_static
ldd hello_static
readelf -h hello_static | grep Type
```
Note the difference in size, in the ELF type, and in the absence of dynamic dependencies. Then run both programs and measure their startup time with time.
```
for i in 1 2 3 4 5; do time ./hello; done
for i in 1 2 3 4 5; do time ./hello_static; done
```
Is the static version measurably faster to start? The difference is the cost of the dynamic linking process, amortised over the program's whole lifetime.
Observe lazy binding. Use LD_BIND_NOW to force the dynamic linker to resolve all symbols at load time rather than lazily, and compare the startup time.
```
time LD_BIND_NOW=1 ./hello
time ./hello
```
If the difference is significant, the program uses lazy binding and the cost of resolving its symbols is deferred to the first call of each. If not, the program is small enough that the resolution cost is negligible either way.
Read the ELF man page. Read man 5 elf and identify the sections you have examined: .interp, .dynsym, .dynstr, .rela.dyn, .rela.plt, .got, and .plt. Write a short paragraph explaining the role of each in the binding process.

Reflect: the toolchain's decisions about address binding are largely invisible to the programmer, who writes the same C code regardless of how the binding is performed. And yet those decisions determine whether the program can be shared among processes, whether it can be updated without recompiling, and how much memory it consumes. Is this the right division of responsibility? Should the programmer be able to control the binding time — for example, choosing static linking for a program that needs to be self-contained — or should the toolchain decide? What information would the programmer need to make a good decision, and is it available at compile time?

07 Knowledge check

Check your understanding

Question 1

Distinguish symbolic, relocatable, and absolute addresses. Which tool or mechanism performs each translation in the chain?

Show answer

Symbolic addresses are the names that appear in source code: variable names, function names, and labels. They are meaningful to the programmer and the compiler, but have no relationship to memory layout. Relocatable addresses are offsets from the beginning of a program or section — "the word at offset 0x200 from the start of the .data section". They are produced by the compiler when the final location of the program is not yet known. Absolute addresses are specific physical memory addresses — "the byte at physical address 0x7FFF5C401000" — and they are what the hardware's memory bus uses. The translation chain is symbolic → relocatable → absolute. The compiler performs the first translation: it resolves symbolic names to relocatable addresses within the object file it produces. The linker combines the relocatable addresses from many object files into a single module, resolving cross-module references and assigning the module's layout. The loader or the MMU performs the last translation, depending on the binding time: the loader adds the load address to each relocatable reference (in load-time binding), and the MMU adds the base register to each logical address (in execution-time binding). In a modern system, all three translations happen: the compiler produces relocatable addresses, the linker produces a position-independent module whose internal references remain relative, and the MMU translates the module's logical addresses to physical addresses at runtime.

Question 2

Describe the three binding times. For each, describe the mechanism it requires, one advantage, and one disadvantage. Which binding time is used by modern systems, and why?

Show answer

The three binding times are compile-time, load-time, and execution-time binding. Compile-time binding produces absolute addresses in the compiled binary; the compiler must know the load address in advance. Its advantage is that no translation is needed at load time or at runtime. Its disadvantage is that the program cannot be moved, cannot be loaded if its address is occupied, and cannot be shared among multiple instances. It is used only in embedded systems with a single fixed task. Load-time binding produces relocatable code, and the loader converts the relocatable addresses to absolute addresses when the program is loaded. Its advantage is that the program can be loaded at any address, chosen by the loader from the available memory. Its disadvantage is that the program cannot be moved after loading, because the relocation is applied once and is not repeated. It was used in early time-sharing systems. Execution-time binding keeps the addresses logical throughout the program's execution, and the MMU translates each to a physical address at the moment of each access. Its advantage is complete flexibility: the program can be loaded anywhere, moved at any time, split across non-contiguous physical memory, shared with other processes, and partially resident on disk. Its disadvantage is the hardware required — the MMU — and the cost of performing the translation on every access, though this cost is mitigated by the translation lookaside buffer. Modern systems use execution-time binding, because it is the only form that supports the requirements of multiprogramming, protection, and overcommitment simultaneously. A modern system actually uses all three binding times for different aspects of the problem: compile-time binding for the layout within a module, load-time binding for resolving imported symbols, and execution-time binding for the physical mapping.

Question 3

Distinguish logical from physical addresses. Why does the distinction only exist when execution-time binding is used? What is the role of the memory-management unit, and what two functions does it perform in the base-and-limit scheme?

Show answer

A logical address (also called a virtual address) is the address that the CPU generates when it executes an instruction — the program counter's value, the address computed by an addressing mode, the operand of a load or a store. It is the address in the abstract address space that the process believes it occupies, and it is not a physical memory location. A physical address is the address that the memory bus uses to select a location in the memory chips. The distinction between the two only exists when execution-time binding is used, because it is only then that the translation happens. In compile-time binding, the compiler produces physical addresses, and the logical address of a variable is the same number as its physical address; the two notions coincide and the distinction is vacuous. In load-time binding, the loader produces physical addresses at load time, and again the two coincide once the program is loaded. Only in execution-time binding are the addresses the program uses distinct from the addresses the memory system uses, because the translation happens on every access, and the program's addresses are never converted to physical form until the moment they are used. The memory-management unit (MMU) is the hardware component that performs the translation. In the base-and-limit scheme, it performs two functions: (1) it checks the logical address against the limit register, raising a fault if the address is out of bounds — this is the protection function; and (2) it adds the base register to the logical address to produce the physical address — this is the relocation function. The check is performed first, on the logical address, so that the boundary is enforced in terms of the process's own address space. The two functions together implement the two requirements that the operating system has of the MMU: protection and relocation.

Question 4

What is position-independent code, and why is it necessary for shared libraries? Describe the two mechanisms that the compiler uses to produce it.

Show answer

Position-independent code (PIC) is machine code that can be loaded at any address without modification. It achieves this by avoiding absolute addresses entirely: every reference is either relative to the current instruction pointer, or is made through a table whose contents are filled in at load time by the dynamic linker. PIC is necessary for shared libraries because a shared library is loaded into a different address in each process that uses it — or, at least, the linker cannot assume a single fixed address — and the library's code must work regardless of where it is loaded. Without PIC, each process that used the library would need its own copy at a fixed address, which is exactly what sharing is supposed to avoid. The two mechanisms the compiler uses are PC-relative addressing and the Global Offset Table (with its companion, the Procedure Linkage Table). PC-relative addressing computes the target of a reference as an offset from the current program counter, which is the same regardless of the code's load address; modern architectures support it for most instructions, and the compiler uses it for intra-module references. The Global Offset Table is a table of pointers that the code accesses PC-relatively; each entry holds the runtime address of a symbol, and the dynamic linker fills the table in when the library is loaded. The Procedure Linkage Table is a similar table of stubs used for function calls, with the additional property that the resolution can be deferred until the first call of each function — a technique called lazy binding. Together, PC-relative addressing and the GOT/PLT allow the compiler to produce code that contains no absolute addresses and that can therefore be loaded anywhere.

Question 5

The classical framework presents the three binding times as alternatives. A modern system uses all three at once. Explain how, and describe what each binding time is used for in a modern Linux program.

Show answer

In a modern system, the three binding times are not alternatives but layers, each handling a different aspect of address resolution. Compile-time binding is used for the layout within a module: the compiler decides where each function and variable will live relative to the module's base, and it generates the machine code with those relative addresses fixed. This costs nothing at runtime and is the fastest possible form of binding for the part of the problem it handles. The compiler also chooses the addressing modes for individual instructions, preferring PC-relative modes that work at any load address. Load-time binding is used for resolving imported symbols: when the program starts, the dynamic linker loads the shared libraries it needs, determines their runtime addresses, and patches the program's GOT and PLT entries with the correct addresses. This is a one-time cost paid at program startup (or, with lazy binding, deferred until first use of each symbol), and it is the mechanism that allows the program to be position-independent despite referring to symbols in libraries it did not compile. Execution-time binding is used for the physical mapping: on every memory access, the MMU translates the program's logical address to a physical address, using the page tables the operating system has set up. This is the most expensive form, because it happens on every access, but it is the only form that provides the flexibility the operating system needs — movability, sharing, and overcommitment. In a modern Linux program, the three are layered: the compiler has fixed the program's internal layout relative to its base; the dynamic linker has resolved the program's imports and filled in the GOT and PLT; and the MMU is translating each logical address to physical on every access, using the mapping the kernel established at execve time. The three work together, each handling the aspect it does best, and the result is a system that is nearly as fast as compile-time binding for the common case and nearly as flexible as full execution-time binding for everything that matters.

08 Unit discussion

Discussion prompt

The three binding times present a genuine design trade-off. Compile-time binding is the fastest — no translation is needed at load time or at runtime — but the least flexible: the program cannot be moved, cannot be shared, and cannot be loaded if its address is occupied. Execution-time binding is the most flexible — the program can be moved, shared, protected, and overcommitted — but requires the MMU and imposes a translation cost on every access. Load-time binding is the middle ground, and it is the form that dominated early time-sharing systems.

Modern systems have settled on execution-time binding because the flexibility it provides — particularly protection and sharing — is considered essential. But the translation cost is real, and it has been mitigated by layers of hardware and software: the translation lookaside buffer, huge pages, and the cache hierarchy itself all exist in part to reduce the cost of address translation.

This raises a question about the future. Processor designs have been moving toward larger address spaces (the transition from 48-bit to 57-bit virtual addresses on x86-64), toward heterogeneous core architectures (big.LITTLE, Apple's performance and efficiency cores), and toward disaggregated memory (compute nodes with remote memory across a fast interconnect). Each of these changes the cost and benefit of address translation. Will execution-time binding continue to be the universal choice, or will some systems move back toward more static forms for the performance-critical parts? What would a system designed around static binding look like, and what would it give up?

Post your response to the Unit 8 discussion forum and reply to at least two classmates. Supports CLO2, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 8.3. Aim to spend 60–90 minutes on it.

Trace the address-binding chain. For a small program you have written, identify the symbolic address of a variable, the relocatable address that the compiler assigned to it (use objdump -d and readelf -s), and the physical address that the variable occupies when the program runs (use gdb to print the address, then compare to /proc/<pid>/maps). Write down the three addresses and explain the translation between them.
Compare binding times. Write a small program, then compile it in three ways: (a) as a normal PIE, (b) with -no-pie, and (c) with -static. For each, run file, ldd, and readelf -h. Tabulate the differences in ELF type, dependencies, and file size. For each, explain which binding time the toolchain used for the program's own addresses.
Inspect a running process's address space. Write a program that prints the addresses of a local variable, a global variable, a heap-allocated buffer, and the main function. Then run it and compare the addresses to the regions in /proc/<pid>/maps. Identify which region each address is in, and explain why the stack and the heap grow in opposite directions.
```
printf("stack:  %p\n", (void*)&local);
printf("global: %p\n", (void*)&global);
printf("heap:   %p\n", (void*)malloc(1));
printf("main:   %p\n", (void*)main);
```
Simulate a base-and-limit MMU. Write a small program that simulates the base-and-limit translation for a list of logical addresses.
```
def translate(logical, base, limit):
    if logical >= limit:
        return None         # fault
    return logical + base

# Test with base=8000, limit=2000
for addr in [0, 1200, 1999, 2000, 50000]:
    result = translate(addr, 8000, 2000)
    print(f"logical {addr:6d} -> {result}")
```
For each address, state whether it is valid or faults. Then modify the simulation to handle two processes with different bases and limits, and verify that the same logical address produces different physical addresses in each.
Analyse the cost of a context switch. The base-and-limit scheme requires the operating system to update the base and limit registers on every context switch. Estimate the cost of this update: on a modern CPU, writing two registers takes a few nanoseconds. Compare this to the cost of the rest of the context switch (saving and restoring registers, flushing the TLB, and so on). What fraction of the total cost does the MMU update represent?
Read the ld.so man page. Read man 8 ld.so and identify the environment variables that control the dynamic linker's behaviour: LD_LIBRARY_PATH, LD_PRELOAD, LD_BIND_NOW, LD_DEBUG. For each, write a sentence describing its effect. Then experiment with LD_DEBUG=libs ./hello to see the dynamic linker's activity in detail.
```
LD_DEBUG=libs ./hello 2>&1 | head -30
```
Explain the trade-offs. Write a short paragraph (150–200 words) comparing static and dynamic linking. Your comparison should address: file size, memory usage, startup time, update behaviour, and dependency management. Then state which you would choose for (a) a high-performance server that starts once and runs for months, (b) an embedded device with a single fixed task, and (c) a general-purpose desktop application. Justify each choice.
Reflect. In your own words, explain why execution-time binding is the right choice for a general-purpose system, even though it imposes a translation cost on every memory access. Then describe one situation in which the translation cost would be a serious problem, and explain how a system designed for that situation might differ.

10 Summary

A program's addresses exist at three levels: symbolic addresses (the names in source code), relocatable addresses (offsets within a module), and absolute addresses (physical memory locations). The translation chain is performed by the compiler, the linker, and the loader or MMU.
The binding time is the point at which a relocatable address is converted to an absolute address. There are three possibilities: compile-time, load-time, and execution-time binding.
Compile-time binding produces absolute addresses in the compiled binary. It requires no runtime translation, but the program cannot be moved or shared. It is used only in fixed embedded systems.
Load-time binding produces relocatable code that the loader converts to absolute addresses at load time. The program can be loaded anywhere, but cannot be moved after loading. It was used in early time-sharing systems.
Execution-time binding keeps addresses logical throughout execution and uses the memory-management unit to translate each to a physical address at the moment of each access. It provides full flexibility — movability, sharing, protection, and overcommitment — at the cost of hardware and runtime overhead. Every modern general-purpose system uses it.
The distinction between logical and physical addresses exists only with execution-time binding. The logical address is what the CPU generates; the physical address is what the memory bus uses. The MMU performs the translation.
In the base-and-limit scheme, the MMU checks the logical address against the limit (raising a fault if it is out of bounds) and adds the base to produce the physical address. The limit check enforces protection; the base addition performs relocation. The scheme is simple and fast but restricts a process to a single contiguous region of physical memory.
Static linking copies library code into the executable at link time. The binary is self-contained but large, and library code is duplicated across programs. Dynamic linking leaves the resolution of library symbols until load time or first use. The binary is small, and library code is shared among processes, at the cost of complexity and a startup cost.
Position-independent code (PIC) is machine code that can be loaded at any address without modification. It is achieved by PC-relative addressing and by the Global Offset Table and Procedure Linkage Table, whose contents are filled in by the dynamic linker. PIC is what makes shared libraries possible.
A modern system uses all three binding times at once, each for a different aspect of the problem: compile-time binding for the internal layout of a module, load-time binding for resolving imported symbols, and execution-time binding for the physical mapping.

Looking ahead

This lesson presented address binding and the distinction between logical and physical addresses. Lesson 8.3 presents dynamic loading and dynamic linking in more detail: the mechanisms by which a program can load code at runtime, the difference between the load-time and runtime forms, and the practical consequences for memory usage and program startup. The lesson also introduces swapping, the first mechanism for handling the case where the total memory demanded by the processes in the system exceeds the physical memory — the overcommitment requirement from Lesson 8.1. That requirement is what motivates paging, the subject of Unit 9.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Sections 9.1–9.2.
Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 7, Linking. The definitive treatment of static and dynamic linking, relocation, and position-independent code.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Sections 3.1–3.2.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapters 15–16. Available online at ostep.org.
Levine, J. R. Linkers and Loaders. Morgan Kaufmann, 1999. Chapters 1–2. The book-length treatment of the toolchain that performs address binding.
Levine, J. R. The Linker and Libraries Guide, part of the Oracle Solaris documentation. A thorough treatment of the ELF format and the linking process.
Tool Interface Standards Committee. Executable and Linkable Format (ELF). The specification of the binary format that records address-binding decisions on Linux and most other Unix-like systems.
Linux man-pages: man 1 ld, man 1 ld.so, man 8 ldconfig, man 5 elf, man 1 readelf, man 1 objdump, man 1 ldd, man 2 mmap, man 5 proc.