Understanding the Linker: Symbol Resolution, Relocation, and Strong vs. Weak Symbols

The Linker's Role: A Quick Recap

As a reminder, the linker (ld) takes one or more relocatable object files (.o) and static libraries (.a) as input. Its job is to combine them into a single executable file by:

1. Symbol Resolution: Finding a single, unambiguous definition for every symbol (function or global variable) that is referenced in the input files.
2. Relocation: Assigning final memory addresses to the code and data, and then patching the code and data sections to reflect these final addresses.

Let's break down these two tasks.

Part 1: Symbol Resolution

At its core, symbol resolution is a matching game. The compiler and assembler generate object files where each global function and variable is a symbol. Some symbols are defined within the object file (e.g., a function you wrote), while others are merely referenced (e.g., a call to printf).

The linker's job is to ensure every reference has exactly one corresponding definition among all the object files being linked.

Strong and Weak Symbols

This process becomes interesting when multiple object files define a global symbol with the same name. To handle this, the C linker categorizes symbols as either strong or weak.

• Strong Symbols: These are functions and initialized global variables.
• Weak Symbols: These are uninitialized global variables. A developer can also explicitly mark a function or variable as weak using __attribute__((weak)) with GCC/Clang.

The linker uses the following three rules to resolve duplicate symbol names:

1. Rule 1: Multiple strong symbols with the same name are not allowed. This results in a "multiple definition" linker error.
2. Rule 2: Given one strong symbol and one or more weak symbols with the same name, the linker chooses the strong symbol and silently ignores the weak ones.
3. Rule 3: Given multiple weak symbols with the same name, the linker picks one of them arbitrarily and silently ignores the others.

This behavior, especially with Rules 2 and 3, can lead to very subtle and dangerous bugs. Let's watch a video that explains these concepts and demonstrates a classic bug that arises from a type mismatch between a strong and a weak symbol.

As you saw, the linker's willingness to resolve a strong char with a weak int led to a memory overwrite that corrupted an adjacent variable. This is a perfect example of why understanding these rules is critical for debugging.

The article "Linking" also contains a concise summary of these rules and is a great reference.

Part 2: The Linker's One-Pass Algorithm and Link Order

Another critical aspect of the linker's behavior, especially when dealing with static libraries (.a files), is that it processes its input files in a single pass from left to right on the command line.

This has a profound impact on how you structure your build commands.

• The linker maintains a list of unresolved symbols.
• When it processes an object file (.o), it adds all the code and data from that file to the final executable unconditionally.
• When it processes a static library (.a), it only pulls in object files from that library if they define a symbol that is currently in the unresolved list.

This means the order in which you provide files and libraries to the linker is critical. A common mistake is to place a library before the object file that needs it.

gcc main.o -lmath is correct. The linker processes main.o, sees an unresolved reference to a function like sqrt, and then searches libmath.a to find the definition.

gcc -lmath main.o is incorrect. The linker processes libmath.a, sees no unresolved symbols it needs, discards the library, and then processes main.o, resulting in an undefined reference to 'sqrt' error.

This behavior, and its interaction with weak symbols, is explained masterfully in the following Stack Overflow answer. It's one of the best explanations of practical linker behavior you will find.

Part 3: Relocation

After the linker has successfully resolved all symbols (the symbol resolution step), it performs its second major task: relocation.

Recall that each object file (.o) is compiled in its own little world, with code and data addresses starting from 0. The assembler doesn't know the final memory address of main() or a global variable my_data. When it generates machine code for a function call or a variable access, it leaves a placeholder. It also creates a relocation entry in sections like .rel.text or .rel.data that says, "Hey linker, when you figure out the final address of symbol X, you need to patch the instruction at this offset."

The relocation process has two steps:

1. Merge and Address: The linker merges all sections of the same type (e.g., all .text sections become one big .text section) and assigns final run-time memory addresses to them.
2. Patch References: The linker iterates through the relocation entries and modifies the code and data, replacing placeholders with the final calculated addresses.

The following resource provides an excellent, detailed explanation of this process.

Conclusion

We've now taken a comprehensive look under the hood of the C linker. Understanding these mechanics transforms the linker from a mysterious tool that occasionally produces frustrating errors into a predictable system you can work with effectively.

Key Takeaways:

• Symbol Resolution: The linker associates every symbol reference with a single definition.
• Strong vs. Weak Symbols: This distinction governs how the linker handles duplicate symbol names. The three rules (multiple strong = error; strong wins over weak; arbitrary weak is chosen) are fundamental.
• Linker Algorithm: The linker's one-pass, left-to-right processing of input files makes command-line order critical, especially for resolving symbols from static libraries.
• Relocation: After resolving symbols and assigning final addresses, the linker patches the machine code using relocation entries to ensure all function calls and variable accesses point to the correct run-time locations.

Preview of the Next Lesson:
Our discussion of relocation naturally leads to the next topic: memory layout. In the next lesson, we will identify and explain the standard ELF sections like .text, .data, .bss, and .rodata. You'll learn what kind of data goes where and how these sections are arranged in the final executable file's memory map, a topic directly managed by the linker.