Hubbry Logo
Relocation (computing)Relocation (computing)Main
Open search
Relocation (computing)
Community hub
Relocation (computing)
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Relocation (computing)
Relocation (computing)
Relocation (computing)
View on Wikipedia
from Wikipedia

In software development, 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.[1][2]

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.

Segmentation

[edit]

Object files are typically segmented into various memory segment or section types. Example segment types include code segment (.text), initialized data segment (.data), uninitialized data segment (.bss), or others as established by the programmer, such as common segments, or named static segments.

Relocation table

[edit]

The relocation table is a list of addresses created by a compiler or assembler and stored in the object or executable file. Each entry in the table references 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. Entries in the relocation table are known as fixups and 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.[2]

In some architectures, a fixup that crosses certain boundaries (such as a segment boundary) or that is not aligned on a word boundary is illegal and flagged as an error by the linker.[3]

DOS and 16-bit Windows

[edit]

Far pointers (32-bit pointers with segment:offset, used to address 20-bit 640 KB memory space available to DOS programs), which point to code or data within a DOS executable (EXE), do not have absolute segments, because the actual address of code or 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 that need to be adjusted.

Windows

[edit]

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 (ASLR), 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.

Windows executables can be marked as ASLR-compatible. The ability exits in Windows 8 and newer to enable ASLR even for applications not marked as compatible.[4] To run successfully in this environment the relocation sections cannot be omitted by the compiler.

Unix-like systems

[edit]

The Executable and Linkable Format (ELF) executable and shared library format used by most Unix-like systems allows several types of relocation to be defined.[5]: 1–22 

Relocation procedure

[edit]

The linker reads segment information and relocation tables in the object files and performs relocation by:

  • Merging all segments of common type into a single segment of that type
  • Assigning non-overlapping run time addresses to each segment and each symbol, assigning all code (functions) and data (global variables) unique run time addresses
  • Referring to the relocation table to modify symbol references in data and object code so that they point to the assigned run-time addresses.

Example

[edit]

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.

  • (A) Program SUBR is compiled to produce object file (B), shown as both machine code and assembly. The compiler may designate start of the compiled code at an arbitrary location, often location 1 as shown. Location 13 contains the machine code for the jump instruction to statement ST in location 5.
  • (C) If SUBR is later linked with other code it may be stored at a location other than 1. In this example the linker places it at location 120. The address in the jump instruction, which is now at location 133, must be relocated to point to the new location of the code for statement ST, now 125. [1 61 shown in the instruction is the MIX machine code representation of 125].
  • (D) When the program is loaded into memory to run it may be loaded at some location other than the one assigned by the linker. This example shows SUBR now at location 300. The address in the jump instruction, now at 313, needs to be relocated again so that it points to the updated location of ST, 305. [4 49 is the MIX machine representation of 305].

Alternatives

[edit]

Some architectures avoid relocation entirely by deferring address assignment to run time; as, for example, in stack machines with zero address arithmetic or in some segmented architectures where every compilation unit is loaded into a separate segment.

See also

[edit]

References

[edit]

Further reading

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Relocation (computing)

View on Grokipedia
from Grokipedia
In computing, relocation is the process of adjusting the addresses within a program's and segments to reflect its assigned position in , enabling efficient loading and execution of multiple programs in a shared . This adjustment connects symbolic references, such as function calls or data accesses, to their actual runtime locations, preventing address conflicts and supporting modular program construction. Relocation is essential for operating systems to manage dynamically, allowing programs to be positioned anywhere without requiring recompilation. Relocation occurs primarily during two stages: linking and loading. In the linking phase, the linker processes relocation entries in object files—data structures like Elf32_Rel or Elf64_Rela that specify offsets, symbols, and adjustment types—to resolve external references and generate an or . For instance, a call instruction's address is updated by adding the symbol's value and any addend, as seen in types like R_SPARC_32 (symbol value plus addend) or R_386_PC32 (adjusted for position independence). During loading, the operating system applies further adjustments if the program is placed at a different base address than anticipated. In , relocation supports both static and dynamic approaches to address binding. Static relocation modifies addresses at load time, fixing the program's position and simplifying implementation but limiting flexibility. Dynamic relocation, in contrast, uses hardware mechanisms like base and limit registers to translate virtual addresses to physical ones at runtime, enabling swapping, compaction, and sharing without halting execution. This is foundational to advanced techniques such as paging, where page tables act as distributed relocation registers to eliminate external fragmentation. (PIC), which employs relative addressing and via global offset tables, reduces or eliminates the need for relocations in shared libraries, enhancing performance in dynamic linking environments.

Fundamentals

Definition

In computing, relocation refers to the process of modifying addresses within , executables, or libraries to align them with the actual locations where the program or module is loaded into , which often differs from the assumptions made during compilation. This adjustment ensures that references to , , or external symbols function correctly regardless of the final loading position, enabling flexible in operating systems. A key distinction in addressing modes relevant to relocation is between absolute addressing, which embeds fixed addresses that require direct modification during relocation, and relative addressing, which uses offsets from a base address and thus needs less adjustment as the base can be shifted uniformly. Relocation primarily targets absolute references to update them to the correct physical or virtual addresses post-loading. Relocation can occur at different stages: static relocation at link time, where the linker resolves and fixes addresses in the final ; load-time relocation, performed by the operating system's loader to adjust addresses upon program loading into ; and dynamic relocation at runtime, which handles mappings during execution, often using hardware mechanisms or for shared libraries. Relocatable object files, produced by compilers, contain unresolved addresses suitable for later relocation, in contrast to position-dependent executables that assume a fixed loading and may require additional adjustments if moved. Relocation tables record the locations needing adjustment to facilitate this process.

Purpose and Necessity

Relocation in computing arises primarily from the limitations of compilers and assemblers, which generate object code assuming a starting address of zero, while actual load addresses in multitasking operating systems remain unpredictable due to variable memory layouts and shared resources among multiple processes. In such environments, programs cannot be bound to fixed physical addresses at compile time, as the operating system must allocate memory dynamically to accommodate concurrent execution and prevent interference. This necessity is addressed through relocation mechanisms that adjust absolute addresses in the code and data sections post-compilation, typically at link time or load time, ensuring the program executes correctly regardless of its final memory position. The benefits of relocation extend to enabling dynamic loading, where modules or libraries are incorporated into a running program without requiring full relinking, thus supporting modular and reducing overhead in large applications. It facilitates shared libraries by allowing a single instance of code to be loaded once and referenced by multiple processes, with relocation adjusting each process's pointers to the location, thereby promoting efficient utilization and across the . By permitting programs to load at arbitrary addresses, relocation optimizes overall usage in constrained systems, avoiding fragmentation and enabling higher degrees of multiprogramming. In virtual memory systems, relocation plays a critical role in preventing address conflicts by mapping logical (virtual) addresses generated by processes to distinct physical addresses, enforced through hardware like relocation registers or units (MMUs), which isolate processes and protect the operating system from erroneous access. This separation ensures that each process operates within its own , mitigating overlaps that could lead to or security vulnerabilities in multitasking setups. Additionally, in resource-constrained environments, relocation supports overlays, where non-resident portions of a program are swapped into as needed, adjusting addresses to fit the available without disrupting execution. Historically, relocation evolved from the fixed-address assumptions of early mainframe systems in the , where programs were loaded at predetermined locations, to relocatable code essential for systems emerging in the 1960s and 1970s. Pioneering efforts, such as the (CTSS) on the 7090, incorporated dynamic relocation hardware to manage multiple users' programs in core memory, addressing the inefficiencies of and enabling interactive computing with flexible memory allocation. This shift was driven by the demands of multiprogramming and , where unpredictable load positions became the norm, laying the foundation for modern architectures.

Memory Organization

Position-Dependent Code

Position-dependent code, also referred to as absolute code, consists of instructions and that embed absolute memory addresses resolved and hardcoded during the compilation and linking phases, under the assumption that the program will be loaded into at a predetermined fixed base address, such as 0x1000. This approach simplifies code generation by allowing the and linker to produce direct references without additional runtime computations, but it inherently ties the executable's functionality to that specific . In practice, absolute addresses appear in various forms within position-dependent object files and executables. For example, direct branch instructions like JMP 0x1000 in x86 assembly encode the target location as an absolute offset from the start of , assuming the program's base. Similarly, references to global variables or static data involve load and store operations with hardcoded addresses, such as MOV EAX, [0x2000] to access a variable presumed at that . External calls, resolved by the linker, also result in absolute addresses patched into call instructions, like CALL 0x3000 for a function . These embeddings occur in assembly code or higher-level compilations without relative addressing flags, producing object files where addresses are fixed relative to the assumed base. Loading position-dependent code at an address different from the assumed base renders all embedded absolute references invalid, often causing immediate program failure through mechanisms like invalid instruction fetches, data corruption from erroneous memory accesses, or control flow hijacks leading to crashes. In multi-process environments, this can also result in memory overlaps, where the program's segments collide with those of other running applications, exacerbating resource contention or security vulnerabilities. Relocation serves as the corrective process to dynamically adjust these hardcoded addresses at load time to align with the actual memory placement. By contrast, position-independent code avoids such issues through relative or indirect addressing schemes, enabling flexible loading without per-instance modifications.

Segmentation

In computing, segmentation refers to the partitioning of a program into logical sections, each serving a distinct purpose to enable efficient memory management and targeted relocation during loading. Common sections include the .text segment, which contains executable machine code instructions; the .data segment, which holds initialized global and static variables; the .bss segment, which reserves space for uninitialized global and static variables that are zeroed at runtime; and the .rodata segment, which stores read-only constants such as string literals. This division allows the operating system or loader to treat each segment as a self-contained unit, facilitating modular handling in object files like ELF. Relocation in segmented memory models is applied on a per-segment basis, where the base address of each segment is adjusted independently to fit the available physical or layout. For instance, the .text segment's base might be shifted to a new location while keeping relative offsets within the segment intact, ensuring that position-dependent —such as absolute addresses embedded in instructions—requires adjustment only within its own segment boundaries. This approach supports dynamic relocation by allowing segments to be placed non-contiguously, reducing fragmentation and enabling better utilization of space compared to treating the entire program as a monolithic block. Historically, segmentation played a key role in architectures like x86, where it supported near pointers (limited to offsets within a single 64 KB segment) and far pointers (combining a segment selector with an offset for addressing up to 1 MB). By isolating changeable parts such as or into separate segments, this mechanism minimized relocation overhead, as only affected segments needed base address updates during loading, preserving compatibility and relocatability in real-mode environments. Segmentation originated in early systems from the , evolving to provide logical partitioning that enhanced relocation flexibility. To ensure proper loading and alignment with hardware requirements, segments must adhere to specific alignment boundaries, often dictated by the target (e.g., 4-byte or 8-byte for x86). Object file formats incorporate padding bytes between or within sections to achieve this alignment, preventing misalignment faults and optimizing access efficiency during relocation. For example, the ELF format explicitly includes in section headers to maintain required alignments for subsequent sections.

Relocation Data Structures

Relocation Records

A relocation record serves as the basic unit of relocation information in object files, typically structured as a containing an offset, a type, and an addend. The offset specifies the within a section where the adjustment must be applied, the type indicates the manner of relocation (such as absolute or relative addressing), and the addend provides an initial constant value to be added during resolution. Common relocation types include PC-relative adjustments, such as R_386_PC32, which computes the difference between the symbol's and the program's counter for instructions in x86 , and absolute addressing like R_X86_64_64, which directly places a 64-bit value plus addend at the target location. These types encode operations for resolution and computation, varying by but generally focusing on how references to external or are fixed up. Relocation records are generated by assemblers and compilers during the symbol resolution phase of object file creation. In a typical two-pass assembly process, the first pass builds a with labels and their offsets, while the second pass scans the code for unresolved references—such as calls to external functions or data in other sections—and emits a relocation record for each, specifying the section, offset, type, and symbol index to guide later linking. These are compactly encoded, usually spanning 8 to 24 bytes depending on the and whether an explicit addend is included, and are stored in dedicated sections of the , such as .rel for implicit addends or .rela for explicit ones. are often aggregated into tables for efficient processing by the linker.

Relocation Tables

In , relocation tables serve as structured collections of relocation within object or files, organizing them into a contiguous or dedicated section that lists all necessary adjustments for a module. These tables enable linkers and loaders to efficiently identify and modify address references that depend on the final memory layout. For instance, in the (PE) format, the .reloc section functions as such a table, while in the (), sections like .rela.dyn fulfill this role. The structure of a relocation table varies by . In PE, it is organized into blocks indexed by 4 KB memory pages, with each block preceded by a header specifying the Page RVA (base virtual address for the page) and the overall block size (from which the number of 2-byte records can be derived). In ELF, relocation tables are flat arrays of records in dedicated sections, navigated via section headers without internal per-block structures. This organization in PE allows loaders to quickly navigate to relevant portions without parsing the entire file. Relocation tables are generated during the link-time phase, where the linker merges relocation records from multiple input object files into a unified table tailored to the executable's layout. This consolidation resolves inter-module dependencies and prepares a single, cohesive structure for loader use. By arranging records contiguously, relocation tables facilitate processing efficiency, permitting sequential scanning of entries and batch application of address adjustments in a single pass, which minimizes computational overhead during loading.

Platform-Specific Implementations

DOS and 16-bit Windows

In MS-DOS 1.0, released in 1981, the MZ executable format introduced relocation support to enable overlay loading, allowing programs larger than the 64 KB limit of the simpler .COM format by swapping segments in and out of memory as needed. The .EXE file header includes a relocation table offset field at byte 24 (word), pointing to a list of entries that specify locations requiring segment address adjustments during loading. Each relocation entry consists of a 4-byte structure: a 16-bit offset and a 16-bit segment number specifying the location in the executable image requiring adjustment, which the DOS loader uses to add the program's base segment address to hardcoded references, ensuring correct addressing regardless of the load position. This design accommodated the segmented memory model of the x86 , where each segment is limited to 64 KB due to 16-bit offsets, necessitating multiple segments and corresponding fixups for programs exceeding that size. Overlays, managed via the linker option /O, relied on this table to dynamically resolve inter-segment references, with the first overlay loaded by DOS and subsequent ones handled by application code interrupting on a specified vector (default 63h). In 16-bit Windows environments like Windows 3.x, the (NE) format extended this approach for .EXE and .DLL modules, incorporating tables within the segment table to resolve references across modules. These tables process far pointers—32-bit values combining a 16-bit selector (for protected-mode segment descriptors) and a 16-bit offset—to adjust imports and internal jumps, supporting shared libraries and multitasking under the Virtual DOS Machines (VDM) architecture. The 64 KB segment limit persisted, requiring frequent fixups for any cross-segment access and complicating development for memory-intensive applications, as the system lacked native 32-bit addressing until the transition to 32-bit Windows in the mid-1990s.

Modern Windows

In modern Windows operating systems, relocation is primarily managed through the Portable Executable (PE) and Common Object File Format (COFF), where the .reloc section stores base relocation information essential for loading images at addresses different from their preferred base. This section is optional but required for images supporting dynamic loading, and it consists of block-based tables, each aligned to a 4 KB page boundary. Each block begins with a 4-byte Page RVA (Relative Virtual Address) indicating the image base plus the page offset, followed by a 4-byte Block Size specifying the total block length, and then an array of 2-byte WORD entries. These entries encode a relocation type in the high 4 bits and an offset from the Page RVA in the low 12 bits, allowing the loader to adjust addresses efficiently. For 32-bit architectures, the common relocation type IMAGE_REL_BASED_HIGHLOW (value 3) applies the full 32-bit difference between the actual and preferred base addresses to the 32-bit field at the specified offset. In 64-bit modes (PE32+), types like IMAGE_REL_AMD64_ADDR64 are used instead, applying the 64-bit delta to the target field, ensuring compatibility across Windows' 32-bit and 64-bit executables () and dynamic-link libraries (DLLs). Relocations support both EXEs and DLLs by adjusting absolute addresses in , , and tables, enabling shared libraries to load at varying bases without recompilation. The PE optional header's DLL Characteristics flag IMAGE_DLLCHARACTERISTICS_DYNAMIC_BASE (0x0040) marks images as relocatable for such scenarios. Relocation integrates closely with Address Space Layout Randomization (ASLR), a security feature introduced in in 2007 to randomize load bases and mitigate exploits. Since Vista, relocation information became essential for ASLR-enabled images, as the absence of the .reloc section prevents randomization if the preferred base is occupied. In and later, ASLR expanded with system-wide mandatory options, enforced via Windows Defender Exploit Guard or , requiring all compatible images to include relocations for full entropy in base address selection. This ensures even legacy or opt-out binaries are relocated if collisions occur, enhancing protection against memory corruption attacks. The Microsoft Visual C++ linker (link.exe) generates the .reloc section during compilation, with the default behavior stripping relocations from EXEs unless ASLR support is explicitly enabled via the /DYNAMICBASE option. At runtime, the Windows image loader—implemented in ntdll.dll—processes these relocations by calculating the delta between the preferred and actual base, then applying it to each entry in the .reloc table before transferring control to the entry point. This evolved from earlier 16-bit Windows tables by adopting RVA-based blocks for better scalability in protected-mode environments.

Unix-like Systems

In Unix-like systems, the evolution of executable formats significantly influenced relocation mechanisms. The original a.out format, introduced in the for early Unix implementations, provided basic support for position-dependent executables but lacked robust features for dynamic linking and relocations in shared libraries. This shifted in the late 1980s when Unix System Laboratories (USL) developed the Executable and Linking Format (ELF) as part of the System V Release 4 (SVR4) specification, with widespread adoption across Unix-like operating systems occurring in the , including in Solaris, , , , and ; however, some systems like macOS (based on Darwin) use the format instead. ELF addressed limitations of a.out by introducing standardized sections for relocations, enabling more flexible and efficient loading of shared objects. The ELF format organizes relocation information in dedicated sections, primarily .rel for entries without explicit addends and .rela for those with explicit addends stored in the r_addend field of Elf32_Rela or Elf64_Rela structures. These sections contain relocation records that specify the location, type, and symbol for adjustments during loading. For example, on architectures, the R_X86_64_GLOB_DAT relocation type (value 6) is used to resolve global data symbols by placing their absolute addresses into the Global Offset Table (GOT), facilitating access to global offsets in position-dependent contexts. The dynamic linker processes these entries to update references, ensuring correct addressing in loaded objects. In and BSD variants, the —such as ld.so in or rtld-elf.so in —handles relocations at load time for shared objects (.so files). Upon executing a dynamically linked program, the linker identifies dependencies via DT_NEEDED entries in the ELF dynamic section, maps the objects into memory, and applies relocations from .rel(a) sections to resolve symbols and adjust addresses. This process supports both static and dynamic relocations, with the linker rejecting incompatible objects based on ABI versions. Key features in Unix-like ELF implementations enhance efficiency, including lazy binding, where non-essential relocations (e.g., those for functions) are deferred until first use, reducing startup overhead by allowing the linker to skip certain entries during initialization. Additionally, pages are mapped with semantics, enabling multiple processes to share read-only segments while providing private writable copies on modification, thus optimizing memory usage for relocations in multi-process environments.

Relocation Process

Static Relocation

Static relocation is a performed by the linker during the linking phase to resolve symbolic references and adjust addresses in relocatable object files, producing a position-dependent that is fixed to a specific location. This approach embeds all necessary and directly into the final binary, eliminating the need for subsequent address adjustments. Unlike dynamic methods, static relocation fully materializes all dependencies at build time, resulting in a self-contained file ready for direct loading into at a predetermined base . The linking process begins with symbol resolution, where the linker associates each undefined reference in the object files with a corresponding definition, handling global symbols such as functions and initialized variables while flagging errors for duplicates or unresolved items. Relocation records from the input object files, which specify offsets needing adjustment, are then scanned to compute absolute addresses by adding section base addresses or offsets to these relative positions. The linker patches the and directly—updating instruction operands, jump targets, and variable references—merging sections like .text and .data into contiguous blocks without retaining relocation information in the output . This technique is particularly suited for standalone executables that operate without shared libraries, as it resolves all inter-module dependencies upfront, ensuring portability across systems with compatible loaders but requiring recompilation for different base addresses. Tools such as linker ld, which processes ELF object files to generate fixed binaries, and link.exe, used in for producing position-dependent PE executables, implement this phase as a core function.

Load-Time Relocation

Load-time relocation occurs during the runtime loading of images or shared libraries by the operating system's dynamic loader, adjusting absolute es to fit the actual location when the preferred base is unavailable. This ensures that references within the loaded module, such as pointers to or , are correctly resolved relative to the final load position. Unlike compile-time or link-time fixes, load-time relocation defers adjustments until the module is mapped into , allowing flexibility in assignment. The loader initiates the process by mapping the image into virtual memory at an available base address, then reads the relocation table—such as the .reloc section in PE format or .rela.dyn in ELF—to identify entries requiring adjustment. For each entry, it computes the delta as the difference between the actual load base and the preferred base (new_base - preferred_base), adding this value plus any section-specific offset to the target location in memory. In PE files, relocations are organized into page-based blocks, where each block specifies a virtual address and a list of type-offset pairs (e.g., IMAGE_REL_BASED_HIGHLOW for 32-bit absolute adjustments), enabling the loader to apply the delta efficiently across 4KB pages. Similarly, in ELF, the loader processes relocation records by type (e.g., R_386_32 for absolute additions or R_386_PC32 for PC-relative offsets), updating pointers or instructions directly. This step-by-step application ensures the image becomes self-consistent without altering the original file on disk. For dynamic cases involving imports from shared libraries (DLLs in Windows or .so files in Unix-like systems), the loader relocates indirect references using structures like the Global Offset Table (GOT) and Procedure Linkage Table (PLT) in ELF. The GOT holds runtime-resolved addresses for external symbols, while the PLT provides stubs for function calls that initially jump to a lazy binder; upon first invocation, the binder resolves the symbol and updates the corresponding GOT entry with the actual address, avoiding repeated relocations. In PE, the Import Address Table (IAT) serves a similar role, with the loader updating it during binding to point to imported functions in loaded DLLs. These mechanisms support deferred or lazy binding, where not all imports are resolved immediately, reducing initial load overhead. Brief reference to platform-specific tables, such as ELF's .rela sections, underscores how these structures encode the offsets and types needed for such adjustments. Error handling during load-time relocation addresses failures such as unresolved symbols or arithmetic overflows. If a required symbol from a dependency cannot be located, the loader aborts the process and reports an error, preventing execution with incomplete references; for instance, GNU ld and dynamic loaders like ld.so treat unresolved dynamic symbols as fatal unless configured otherwise. Overflows occur when the computed adjustment exceeds the bit width of the target field, such as in 64-bit systems using 32-bit relative relocations (e.g., R_X86_64_PC32), potentially causing memory corruption; the loader may fail the load or truncate the value, depending on the platform, with warnings often issued at link time to preempt runtime issues. In PE, if relocations are stripped and the preferred base is unavailable, loading fails outright. To optimize performance and minimize startup time, loaders process relocations in batches, typically by section or page, applying adjustments en masse before transferring control to the program's . This batched approach, as seen in ELF's sequential handling of .rela entries or PE's page-aligned blocks, reduces context switches and memory accesses, though it can still contribute to delays in large applications with extensive relocation tables. Eager binding resolves all entries upfront for predictability, while lazy binding defers non-critical ones, trading minor runtime costs for faster initial loads.

Examples

Basic Relocation Example

To illustrate basic absolute relocation, consider a simple hypothetical program compiled for a 32-bit x86-like architecture, assuming it will be loaded at memory base address 0x1000. The program's code begins at this base, and at offset 0x10 from the start (absolute address 0x1010 during compilation), there is an instruction mov eax, [global_var] that references a global variable located at absolute address 0x2000. In the object file's machine code, this instruction appears as the opcode A1 (for loading from memory into EAX) followed by the 4-byte little-endian representation of 0x2000, yielding a hex dump segment of A1 00 20 00 00 at that offset. The corresponding relocation record in the object file specifies an absolute type (indicating a direct address adjustment), with the offset 0x10 (relative to the code section start) and an addend of 0x2000 (the original address value embedded in the instruction). This record informs the loader of the location and value needing modification to account for the actual load address. When the loader places the program at base address 0x4000 instead of the assumed 0x1000, it computes the relocation delta as 0x3000 (0x4000 - 0x1000) and applies it by adding this value to the addend in the record. The adjusted address becomes 0x2000 + 0x3000 = 0x5000, and the loader patches the instruction's address field to 0x5000, updating the hex to A1 00 50 00 00. Before adjustment, the code assumes the variable at absolute address 0x2000 given the expected base; after, it correctly references 0x5000, where the global variable is also relocated in the new memory layout. As a result, the program executes correctly, with the instruction now loading from the relocated global variable's position, demonstrating how absolute relocation ensures compatibility across different memory placements without recompilation.

Segmented Relocation Example

In a typical segmented relocation example, consider a program compiled and linked for an x86 real-mode environment, such as under MS-DOS, where the code segment (.text) is positioned at segment address 0x0000 and the data segment (.data) at 0x0010 (one paragraph, or 16 bytes, apart) in the executable file assuming a base load segment of 0x0000. Within the .text segment, a far call instruction references a location in .data at offset 0x0020; this instruction stores the target far pointer as segment 0x0010 followed by offset 0x0020, with the segment word located at offset 0x10 within the overall load module. The relocation table records this inter-segment fixup with a 4-byte entry: the first word (0x0000) indicating the byte offset within the paragraph, and the second word (0x0001) indicating the paragraph offset into the load module (0x001 * 0x10 = 0x10). During loading, the operating system allocates and places the entire load module starting at an actual base segment of 0x4000, shifting both .text to 0x4000 and to 0x4010 to maintain their relative positioning. The loader processes the relocation table sequentially: for the entry at file offset specified in the header, it computes the as (entry. * 0x10) + entry.offset, reads the 16-bit value there (originally 0x0010), adds the base segment (0x4000), and writes back the adjusted value (0x4010). This updates the far call's segment field, ensuring the instruction now targets the correct relocated location. The process can be represented in pseudo-code as:

base_segment = 0x4000 // Actual load base relocation_table_offset = header.reloc_offset // From EXE header num_relocations = header.num_reloc_items for i from 0 to num_relocations - 1: entry_offset = relocation_table_offset + (i * 4) reloc_offset = read_word(entry_offset) // e.g., 0x0000 reloc_paragraph = read_word(entry_offset + 2) // e.g., 0x0001 target_address = (reloc_paragraph * 0x10) + reloc_offset // e.g., 0x10 memory_value = read_word_at_load_module(target_address) // e.g., 0x0010 adjusted_value = memory_value + base_segment // e.g., 0x4010 write_word_at_load_module(target_address, adjusted_value)

base_segment = 0x4000 // Actual load base relocation_table_offset = header.reloc_offset // From EXE header num_relocations = header.num_reloc_items for i from 0 to num_relocations - 1: entry_offset = relocation_table_offset + (i * 4) reloc_offset = read_word(entry_offset) // e.g., 0x0000 reloc_paragraph = read_word(entry_offset + 2) // e.g., 0x0001 target_address = (reloc_paragraph * 0x10) + reloc_offset // e.g., 0x10 memory_value = read_word_at_load_module(target_address) // e.g., 0x0010 adjusted_value = memory_value + base_segment // e.g., 0x4010 write_word_at_load_module(target_address, adjusted_value)

Post-relocation, the far call instruction correctly addresses 0x4010:0x0020, preserving program logic across the segment boundary. A key complication in x86-like segmented setups arises from distinguishing near and far pointers during relocation. Near pointers operate within a single segment using only a 16-bit offset (e.g., for intra-segment jumps or data access), requiring no segment adjustment as offsets are position-independent relative to the base; thus, they typically lack relocation records unless absolute offsets are hardcoded. Far pointers, however, span segments and store a 16-bit segment value followed by a 16-bit offset (e.g., in far call, far jump, or pointer variables), necessitating dedicated relocation entries solely for the segment component to add the load base, while the offset remains unchanged unless separately fixed. This selective handling ensures compatibility in the 1 MB real-mode address space, where improper far pointer adjustment could lead to addressing errors across the 64 KB segment limit. The following table summarizes the address transformations in this example:
ElementLinked Segment:OffsetLoaded Segment:OffsetAdjustment Applied
.text segment0x0000:00000x4000:0000+0x4000 to segment
.data segment0x0010:00000x4010:0000+0x4000 to segment
Far call target0x0010:00200x4010:0020+0x4000 to segment only

Modern Alternatives

Position-Independent Code

Position-independent code (PIC) is a compilation technique that generates machine code capable of executing correctly regardless of its absolute load address in memory, thereby reducing or eliminating the need for traditional relocation during loading. This is achieved primarily through the use of relative addressing modes, where instructions reference locations relative to the current program counter (PC), such as PC-relative jumps and branches that compute offsets from the instruction's position. For data accesses, particularly to global variables and external symbols, PIC employs the Global Offset Table (GOT), a runtime-modifiable data structure that stores absolute addresses resolved by the dynamic linker at load time or lazily during execution. In practice, compilers like GCC generate PIC using the -fPIC flag, which produces code suitable for shared libraries by favoring relative addressing and GOT indirection for all external references, ensuring the text section remains read-only and shareable across processes. This approach limits load-time fixups to only the GOT entries and Procedure Linkage Table (PLT) for function calls, rather than patching the code itself. As a result, relocation tables in PIC-enabled object files are reduced to entries for dynamic symbols only, minimizing processing overhead. The advantages of PIC include enabling (ASLR) for security by allowing flexible loading without code modification, as well as faster startup times due to reduced relocation work, making it the standard for shared object (.so) files in the ELF format. However, PIC introduces a slight runtime overhead from the indirection required for GOT and PLT accesses, which can add a few cycles per external reference compared to direct addressing in position-dependent code. This technique was introduced in the for Unix shared libraries, notably in , to support efficient dynamic linking and code sharing.

Address Space Layout Randomization

Address Space Layout Randomization (ASLR) is a technique designed to exploit the relocation capabilities of and loaders to randomize the layout of , thereby complicating the prediction of addresses needed for exploits such as buffer overflows and attacks. By altering the base addresses of critical regions—including the stack, heap, shared libraries, and executable —ASLR introduces variability that forces attackers to rely on less reliable methods, significantly raising the difficulty of successful exploitation. This randomization occurs each time a is loaded into , leveraging the inherent flexibility of relocation mechanisms to adapt and references dynamically without recompilation. The core reliance of ASLR on relocation information stems from the need for loaders to adjust absolute addresses in executables and libraries to fit the randomly chosen base addresses. During process loading, the operating system's loader consults relocation tables embedded in the executable format (such as ELF on or PE on Windows) to perform these adjustments, ensuring that all internal references—such as jumps, calls, and data accesses—are correctly resolved relative to the new randomized positions. This process prevents attackers from hardcoding memory addresses in exploits, as the actual locations become unpredictable across executions; without proper relocation support, would fail, reverting to fixed layouts vulnerable to prediction. For instance, Windows introduced ASLR in 2007 with , initially randomizing DLLs, the stack, and the heap, while added ASLR support starting with kernel version 2.6.12 in 2005, enabling of the stack, base, and . ASLR implementations vary in scope between partial and full levels to balance with compatibility. Partial ASLR randomizes the stack, heap, and libraries but leaves the main 's at a fixed base , which can still predictable for partial bypasses. Full ASLR extends randomization to the itself, requiring compilation as a position-independent (PIE) for complete coverage, though this demands more computational overhead during loading due to extensive relocations. Developers can opt out of full ASLR for specific binaries using compiler flags like -no-pie in GCC, which disables PIE generation and reverts to position-dependent , useful for legacy software or performance-critical applications where is deemed unnecessary. ASLR works best with position-independent (PIC), which facilitates full by avoiding absolute addressing assumptions. As of 2025, ASLR has evolved through integration with (CFI) mechanisms in major operating systems, enhancing its effectiveness against advanced control-flow hijacking attacks. In , ASLR combines with Control Flow Guard (CFG), Microsoft's CFI implementation, to validate indirect control transfers while randomizing layouts, providing layered defenses that limit gadget discovery even if addresses are partially leaked. Similarly, kernels incorporate CFI variants like Kernel Control-Flow Integrity (KCFI) alongside ASLR, enforcing valid control flows in the kernel space and user processes to mitigate exploits that chain randomized regions. These enhancements ensure ASLR remains a foundational yet adaptable feature in contemporary systems.

References

  1. https://docs.oracle.com/cd/E19957-01/806-0641/chapter6-54839/index.html
  2. https://gabi.xinuos.com/elf/06-reloc.html
  3. https://pages.cs.wisc.edu/~bart/537/lecturenotes/s14.html
  4. https://lass.cs.umass.edu/~shenoy/courses/fall12/lectures/Lec12.pdf
  5. https://pld.cs.luc.edu/courses/264/spr19/notes/linking.html
  6. https://nob.cs.ucdavis.edu/classes/ecs150-2008-04/handouts/memory.pdf
  7. http://www.scs.stanford.edu/07au-cs140/notes/l7.pdf
  8. http://www.staroceans.org/e-book/LinkersAndLoaders.pdf
  9. https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf
  10. http://larch-www.lcs.mit.edu:8001/~corbato/sjcc62/
  11. https://linker.iecc.com/
  12. https://docs.oracle.com/cd/E26505_01/html/E26506/glmqp.html
  13. https://people.eecs.berkeley.edu/~prabal/teaching/resources/eecs373/Assembler.pdf
  14. https://courses.grainger.illinois.edu/ece391/sp2025/docs/riscv-abi-20240829.pdf
  15. https://refspecs.linuxbase.org/elf/gabi4+/ch4.sheader.html
  16. https://pages.cs.wisc.edu/~remzi/OSTEP/vm-segmentation.pdf
  17. https://cdrdv2.intel.com/v1/dl/getContent/671436
  18. https://refspecs.linuxbase.org/elf/gabi4+/ch4.reloc.html
  19. https://docs.oracle.com/cd/E19957-01/806-0641/chapter6-26/index.html
  20. https://www.ucw.cz/~hubicka/papers/abi/node19.html
  21. https://www.cs.princeton.edu/courses/archive/spr11/cos217/lectures/16AssemblersAndLinkers.pdf
  22. https://learn.microsoft.com/en-us/windows/win32/debug/pe-format
  23. https://web.stanford.edu/~ouster/cgi-bin/cs140-spring20/lecture.php?topic=linkers
  24. https://learn.microsoft.com/en-us/windows/win32/debug/pe-format#the-reloc-section-image-only
  25. https://wiki.osdev.org/MZ
  26. https://moddingwiki.shikadi.net/wiki/EXE_Format
  27. https://www.pcjs.org/documents/books/mspl13/msdos/encyclopedia/section4/
  28. https://www.smxrtos.com/doc/pmeasy.pdf
  29. https://devblogs.microsoft.com/oldnewthing/20060717-13/
  30. https://stackoverflow.com/questions/3670757/programs-larger-than-64k-when-using-real-segmented-mode-with-x86-assembly-and-do
  31. https://learn.microsoft.com/en-us/windows/win32/debug/pe-format#base-relocation-block
  32. https://learn.microsoft.com/en-us/windows/win32/debug/pe-format#base-relocation-types
  33. https://learn.microsoft.com/en-us/windows/win32/debug/pe-format#dll-characteristics
  34. https://learn.microsoft.com/en-us/cpp/build/reference/dynamicbase-use-address-space-layout-randomization
  35. https://www.microsoft.com/en-us/msrc/blog/2017/11/clarifying-the-behavior-of-mandatory-aslr
  36. https://maskray.me/blog/2024-05-26-evolution-of-elf-object-file-format
  37. https://www.linuxjournal.com/article/1059
  38. https://refspecs.linuxfoundation.org/elf/x86_64-abi-0.95.pdf
  39. https://refspecs.linuxfoundation.org/elf/elf.pdf
  40. https://man7.org/linux/man-pages/man8/ld.so.8.html
  41. https://docs.oracle.com/cd/E23824_01/html/819-0690/chapter3-7.html
  42. http://csapp.cs.cmu.edu/2e/ch7-preview.pdf
  43. https://sourceware.org/binutils/docs/ld/
  44. https://eli.thegreenplace.net/2011/08/25/load-time-relocation-of-shared-libraries
  45. https://0xrick.github.io/win-internals/pe7/
  46. https://maskray.me/blog/2021-09-19-all-about-procedure-linkage-table
  47. https://sourceware.org/binutils/docs-2.40/ld.html
  48. https://tecnocode.co.uk/2014/10/01/dynamic-relocs-runtime-overflows-and-fpic/
  49. https://docs.oracle.com/cd/E19120-01/open.solaris/819-0690/chapter3-29/index.html
  50. https://www.cs.cmu.edu/~410/doc/segments/segments.html
  51. https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html
  52. https://docs.oracle.com/cd/E19683-01/816-1386/6m7qcoblk/index.html
  53. https://www.sei.cmu.edu/blog/when-aslr-is-not-really-aslr-the-case-of-incorrect-assumptions-and-bad-defaults/
  54. https://cloud.google.com/blog/topics/threat-intelligence/six-facts-about-address-space-layout-randomization-on-windows
  55. https://0x434b.dev/an-introduction-to-address-space-layout-randomization-aslr-in-linux/
  56. https://media.blackhat.com/bh-us-11/DaiZovi/BH_US_11_DaiZovi_iOS_Security_Slides.pdf
  57. https://gcc.gnu.org/onlinedocs/gcc/Invoking-GCC.html#Invoking-GCC
  58. https://learn.microsoft.com/en-us/windows/win32/secbp/control-flow-guard
  59. https://tuxcare.com/blog/kernel-security-mechanisms-how-aslr-and-cfi-enhance-security/
  60. https://www.phoronix.com/news/Linux-6.1-Clang-KCFI-Submitted
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.