Relocation (computing)


Relocation is the process of assigning load addresses for position-dependent code and data of a program and adjusting the code and data to reflect the assigned addresses. Prior to the advent of multiprocess systems, and still in many embedded systems, the addresses for objects were absolute starting at a known location, often zero. Since multiprocessing systems dynamically link and switch between programs it became necessary to be able to relocate objects using position-independent code.
A linker usually performs relocation in conjunction with symbol resolution, the process of searching files and libraries to replace symbolic references or names of libraries with actual usable addresses in memory before running a program.
Relocation is typically done by the linker at link time, but it can also be done at load time by a relocating loader, or at run time by the running program itself. Some architectures avoid relocation entirely by deferring address assignment to run time; this is known as zero address arithmetic.

Segmentation

s are segmented into various memory segment types. Example segments include code segment, initialized data segment, uninitialized data segment, or others.

Relocation table

The relocation table is a list of pointers created by the translator and stored in the object or executable file. Each entry in the table, or "fixup", is a pointer to an absolute address in the object code that must be changed when the loader relocates the program so that it will refer to the correct location. Fixups are designed to support relocation of the program as a complete unit. In some cases, each fixup in the table is itself relative to a base address of zero, so the fixups themselves must be changed as the loader moves through the table.
In some architectures a fixup that crosses certain boundaries or that is not aligned on a word boundary is illegal and flagged as an error by the linker.

DOS and 16-bit Windows

Far pointers, which point to code or data within a DOS executable, do not have absolute segments, because the actual address of code/data depends on where the program is loaded in memory and this is not known until the program is loaded.
Instead, segments are relative values in the DOS EXE file. These segments need to be corrected, when the executable has been loaded into memory. The EXE loader uses a relocation table to find the segments which need to be adjusted.

32-bit Windows

With 32-bit Windows operating systems it is not mandatory to provide relocation tables for EXE files, since they are the first image loaded into the virtual address space and thus will be loaded at their preferred base address.
For both DLLs and for EXEs which opt into address space layout randomization - an exploit mitigation technique introduced with Windows Vista, relocation tables once again become mandatory because of the possibility that the binary may be dynamically moved before being executed, even though they are still the first thing loaded in the virtual address space.

64-bit Windows

When running native 64-bit binaries on Windows Vista and above, ASLR is mandatory, and thus relocation sections cannot be omitted by the compiler.

Unix-like systems

The Executable and Linkable Format executable format and shared library format used by most Unix-like systems allows several types of relocation to be defined.

Relocation procedure

The linker reads segment information and relocation tables in the object files and performs relocation by:
The following example uses Donald Knuth's MIX architecture and MIXAL assembly language. The principles are the same for any architecture, though the details will change.