Relocation

The core function of relocation is to adjust memory addresses in an object file's code and data sections. These addresses are initially relative or placeholder values. The linker or loader calculates the final absolute addresses based on the memory layout defined by the linker script and the load address, then patches them into the binary.

• Example: A function call call 0x0000 in an object file is changed to call 0x40001000 in the final executable after determining the function's actual location in memory.

Relocation depends on symbol resolution, where undefined references to functions or variables (e.g., printf) are matched with their definitions found in other object files or libraries. The symbol table in each object file is searched to find the address of each symbol. Unresolved symbols cause a linker error.

• Internal vs. External: Resolves both internal symbols (within the same module) and external symbols (from other libraries).
• Strong vs. Weak: Strong symbol definitions (functions, initialized globals) override weak ones.

Object files contain relocation entries (in a .rel or .rela section) that instruct the linker how to patch the code. Each entry specifies:

• Offset: The location in the object file to patch.
• Symbol: Which symbol's address to use.
• Type: The relocation type (e.g., R_X86_64_PC32, R_AARCH64_ADR_PREL_PG_HI21) that defines the exact calculation for the address adjustment, accounting for instruction size and PC-relative vs. absolute addressing.

Static Relocation is performed by the linker during the creation of an executable. All addresses are finalized, producing a ready-to-run binary. Used for static libraries.

Dynamic Relocation is performed by the loader (dynamic linker) at program startup or during runtime for shared libraries (dynamic libraries). Addresses may be adjusted based on where the library is loaded into memory (Address Space Layout Randomization - ASLR). This uses the Procedure Linkage Table (PLT) and Global Offset Table (GOT).

PIC is code that executes correctly regardless of its absolute memory address, essential for shared libraries. It uses PC-relative addressing for code and indirect accesses via the GOT for global data. This minimizes the number of relocation entries required at load time, speeding up startup and enabling ASLR.

• PIE (Position-Independent Executable): An entire executable built as PIC, enhancing security.
• Relocation for PIC primarily involves filling the GOT with correct addresses.

For NPUs and hardware accelerators, relocation is managed by the vendor toolchain and vendor runtime. When compiling kernels for an NPU:

1. The cross-compiler generates object code with unresolved references to device-side APIs or memory buffers.
2. The vendor's linker performs relocation, resolving symbols against the vendor SDK libraries and mapping code/data to the NPU's specific memory map (e.g., SRAM, global memory).
3. The final binary (often embedded in a fat binary or loaded separately) contains addresses valid for that specific NPU architecture's Vendor ISA.

The first phase of relocation involves symbol resolution, where the linker matches every symbolic reference (e.g., a call to a function conv2d()) with its precise definition from an object file or library. Address binding then assigns a tentative virtual address to each symbol. For NPUs, this includes mapping symbols to specific accelerator memory regions (e.g., NPU SRAM, device DRAM) defined by the vendor's memory map. Unresolved symbols at this stage result in linker errors.

Object files contain relocation entries (or relocation records) that identify every place in the code where an address needs adjustment. Each entry specifies:

• The offset within the object file's section.
• The symbol whose address is needed.
• A relocation type defining the exact calculation (e.g., absolute, relative). The linker iterates through these entries, fetching the final address of the referenced symbol and performing the mandated calculation to patch the binary code. NPU toolchains add vendor-specific relocation types for hardware register addresses and tensor memory buffers.

Position-Independent Code (PIC) is designed to execute correctly regardless of its base load address, minimizing the need for load-time relocation. It uses Global Offset Tables (GOT) and Procedure Linkage Tables (PLT) to indirect address references. For NPU kernels, PIC is less common due to the need for maximum performance and deterministic memory layouts. However, Position-Independent Executables (PIE) are used for host-side driver code to enhance security through Address Space Layout Randomization (ASLR).

Relocating code for NPUs introduces unique complexities:

• Multiple Address Spaces: Code must reference host CPU memory, NPU device memory, and mapped hardware registers, each with different base addresses.
• Vendor-Specific Sections: Object files contain special sections (e.g., .nv.info for NVIDIA, .rodata.cl for OpenCL) that require custom relocation logic.
• Kernel Argument Buffers: Addresses for tensor buffers passed to NPU kernels must be relocated to point to their final locations in device memory.
• Shared Library Interposition: Ensuring calls to vendor runtime libraries (e.g., libcudart.so) are correctly resolved on the target system.

Linker scripts (e.g., .ld files) provide explicit control over the relocation process by defining the final memory layout. They are essential for embedded NPU systems. A script specifies:

• MEMORY regions (e.g., NPU_ITCM, DRAM), their origin, length, and attributes.
• SECTION commands dictating where input sections (.text, .data) are placed in output memory.
• Symbol assignments (e.g., _npubuffer_start = .;) to expose layout details to code. This allows engineers to place performance-critical kernel code in fast, tightly-coupled NPU memory (TCM) and data buffers in larger, slower DRAM.

For executables using dynamic/shared libraries, final relocation occurs at load time by the dynamic linker/loader (e.g., ld-linux.so). It performs:

• Runtime relocation (RTLD): Patches the Global Offset Table (GOT) with the actual addresses of dynamically loaded symbols.
• Lazy binding: Defers resolution of function addresses via the Procedure Linkage Table (PLT) until the first call, improving startup speed. In NPU contexts, the vendor runtime library (e.g., AMD ROCm, Intel oneAPI) is typically a dynamic library, and its symbols (like hipMalloc) are resolved and relocated when the host application launches.

A configuration file that provides the linker with a precise memory map for the target hardware. It defines:

• The memory regions available on the NPU (e.g., SRAM, DRAM, cache).
• Where specific sections of code (.text) and data (.data, .bss) should be placed.
• The entry point address for program execution.

The linker uses this script to perform relocation, assigning final, absolute addresses to all symbols based on this layout, which is critical for NPUs with complex, non-uniform memory hierarchies.

The low-level contract between separately compiled program modules and the operating system. It defines the rules for:

• Calling conventions: How functions pass arguments and return values using registers or the stack.
• System call mechanisms.
• Data representation (size, alignment, endianness).
• Object file format (e.g., ELF).

The ABI is essential for relocation because the linker must resolve cross-module references (e.g., function calls) according to these standardized rules to ensure binary compatibility.

The standard file format for executables, object code, shared libraries, and core dumps on many Unix-like systems and embedded platforms, including NPU targets. Key components for relocation include:

• Sections: Contiguous blocks like .text (code), .data (initialized data), and .rel.text (relocation entries for code).
• Segments: Units used by the loader to map sections into memory.
• Relocation tables: Data structures (e.g., REL or RELA sections) that list every symbol reference requiring address adjustment. The linker reads ELF files, processes relocation tables, and writes a new ELF executable with resolved addresses.

The system program (often part of the OS kernel) responsible for loading an executable into memory and preparing it for execution. Its duties related to relocation are:

• Memory allocation: Reserving address space as specified by the ELF program headers.
• Address space layout randomization (ASLR): Applying a random offset to the load address for security, which necessitates runtime relocation.
• Dynamic linking: Loading shared libraries and performing relocation on-the-fly to resolve symbols in those libraries.
• Jumping to the entry point to start execution. For NPUs, a vendor runtime often acts as a specialized loader.

Code that can execute correctly regardless of its absolute address in memory. It is a strategy to minimize the need for relocation at load time, which is crucial for shared libraries and security (ASLR). Techniques include:

• PC-relative addressing: Using offsets from the current program counter (PC) to access data and code.
• Global Offset Table (GOT): A table of pointers to global variables, with a fixed offset from the code.
• Procedure Linkage Table (PLT): A table used for lazy binding of function calls to shared libraries. PIC increases flexibility but may introduce a small performance overhead due to indirection.

The process by which a linker associates each symbolic reference in object code with its precise definition. This is a prerequisite for relocation. The linker:

1. Scans all input object files and libraries to build a global symbol table.
2. For each undefined reference (e.g., a call to printf), it searches the table for a matching definition.
3. Upon finding a match, it records the symbol's eventual address.
4. Relocation then uses these resolved addresses to patch the machine code. Unresolved symbols result in a linker error.