Linker - Compiler Design - Computer Science Engineering (CSE)

Introduction

A linker (also called a link editor) is a system program that combines one or more object modules into a single object file suitable for loading and execution. The linker takes as input relocatable object files produced by the assembler and produces an executable image for the loader. Linking is the process of collecting code and data fragments from separate translation units and libraries, resolving references between them, and producing a single binary that the operating system can load and run.

Source code → compiler → assembler → object code → linker → executable file → loader

Overview of Linking

Linking performs several essential tasks that ensure separately compiled program parts work together when executed. The primary responsibilities of a linker are:

• Symbol resolution: associate each symbol reference (for example a call to a function or a reference to a global variable) with exactly one symbol definition.
• Relocation: adjust addresses in code and data sections so that all internal references point to the correct addresses in the final executable image.
• Combining sections: merge code and data sections from different object files into the output sections of the executable.
• Library handling: search and include needed routines from static libraries, or record references to shared libraries for dynamic linking.

When Linking Happens

Linking may occur at different stages:

• Link time (compile time): the traditional static linking step performed by the linker after compilation and assembly, producing a fully linked executable before the program is run.
• Load time: when an executable is loaded into memory, the loader or runtime linker can perform additional linking actions for shared libraries that the executable depends on.
• Run time: some dynamic linking can be deferred until a routine is actually called (lazy binding), so final resolution can happen during program execution.

Types of Linking

Static Linking

In static linking, the linker combines object modules and the required library routines into a single executable file at link time. The static linker resolves all symbol references and performs relocation so that the output file can be loaded and executed directly by the loader.

Two main tasks performed by a static linker:

• Symbol resolution: the linker builds a global symbol table from definitions in object files and libraries, and matches each symbol reference to the appropriate definition.
• Relocation: the linker updates addresses and offsets in code and data sections according to the final layout of the executable image.

Characteristics of static linking:

• The linker copies library routines used by the program into the executable image, which increases the binary size.
• The executable has fewer runtime dependencies because library code is embedded; the program can run even if the original libraries are not present on the target system.
• Static linking can improve startup performance because symbol resolution was already completed at link time.
• Because code is duplicated in each statically linked binary, it uses more disk space and may use more RAM when multiple programs run separately.

Typical file extensions and utilities commonly seen with static linking: object files (.o or .obj), static libraries (.a on Unix, .lib on Windows), and linkers such as ld or the compiler driver (gcc, clang) that invoke the linker.

Dynamic Linking

Dynamic linking defers some or all linking work until load time or run time. The executable image contains references to shared libraries rather than copying the library code into the binary. The system's runtime linker/loader locates the required shared libraries, resolves symbols, and performs relocation when the program is loaded or when a symbol is first used.

Key points about dynamic linking:

• Shared libraries are commonly named .so on Unix-like systems and .dll on Windows.
• Dynamic linking allows multiple running programs to share a single copy of library code in memory, reducing overall RAM usage.
• Relocation for shared libraries generally requires the library to be compiled as position-independent code (PIC) so that the same library image can be loaded at different addresses in different processes.
• Symbol resolution can be performed at load time (eager binding) or deferred until the symbol is first referenced (lazy binding). The mechanism commonly used to support lazy binding includes the Procedure Linkage Table (PLT) and the Global Offset Table (GOT) on ELF systems.
• Dynamic linking supports updates to shared libraries without relinking all dependent programs; however, changes to library interfaces (ABI) may break compatibility.

Advantages of dynamic linking:

• Smaller executable sizes because library code is not copied into each binary.
• Reduced memory footprint when multiple processes share the same library code.
• Ease of updating and patching libraries without recompiling all dependent applications.

Disadvantages and risks of dynamic linking:

• Programs depend on the presence and correct versions of shared libraries at runtime; missing or incompatible libraries can prevent execution (commonly called "dependency hell").
• Run-time resolution adds complexity and potential performance overhead at program start-up or at first use of a routine.
• Security or compatibility problems can arise if a shared library is replaced with an incompatible or malicious version.

How the Linker Works - Process Details

The typical steps carried out by a linker when producing an executable are:

1. Read the object files and libraries that are to be linked.
2. Build a global symbol table containing all symbol definitions and their section addresses (or library references for dynamic linking).
3. For each symbol reference, find the corresponding definition. If a symbol is defined in a library archive, select the member object file that satisfies the reference.
4. Calculate final addresses for sections and symbols according to the chosen layout of the executable.
5. Apply relocation: modify code and data words that refer to addresses so they point to the final addresses.
6. Write the output executable or shared library image, recording dynamic linking metadata (for example, shared library names and relocation records) when required.

Examples and Illustrations

Simple example of symbol resolution across object files:

• File main.c calls function foo(). After compilation, main.o contains an undefined symbol reference to foo.
• File foo.c defines function foo(). After compilation, foo.o contains a definition for symbol foo.
• The linker takes main.o and foo.o, resolves the reference to foo to its definition, performs relocation, and produces an executable.

Example of linking with libraries on Unix-like systems:

• Static library: libm.a can be archived with ar and linked into the executable at link time.
• Shared library: libm.so can be referenced during linking; the produced executable will contain metadata pointing to libm.so so the runtime linker can load it.

Implementation Concepts and Terms

• Relocation records: entries in object files indicating which addresses must be adjusted by the linker and how to compute the new values.
• Symbol table: data structure listing symbols defined and referenced in object files, along with their attributes (local/global, section, value).
• Position-independent code (PIC): code that can execute correctly regardless of its absolute address, used for shared libraries to allow loading at arbitrary addresses without modification of the code bytes.
• Global Offset Table (GOT) and Procedure Linkage Table (PLT): tables used by dynamic linkers to resolve addresses of global variables and function calls at run time (common in ELF-based systems).
• Runtime linker/loader: system component (for example ld.so on many Unix-like systems) that loads an executable and its shared libraries, performs necessary relocations, and resolves dynamic symbols.

Practical Notes for Students

• Understanding linking is important for debugging "undefined reference" errors during build, and for resolving runtime library dependency problems.
• Use compiler/linker driver options to control static or dynamic linking; for example, compilers can pass flags to the linker to link statically or to specify additional library search paths.
• When building shared libraries, enable position-independent code (for example using compiler flags such as -fPIC on many compilers) to ensure safe loading at arbitrary addresses.
• Be aware of symbol visibility and name mangling rules (especially in languages like C++), since these affect symbol resolution during linking.

Conclusion

The linker is a vital component of the build toolchain. It performs symbol resolution, relocation, and section combination, and it decides whether to include library code directly (static linking) or to record references for the runtime linker (dynamic linking). Static linking produces self-contained executables but increases size, while dynamic linking enables code sharing, smaller binaries, and easier updates at the cost of runtime dependencies and additional complexity. Knowledge of how linkers work helps in producing efficient, correct, and portable programs.