Resolve a symbol, then relocate its use

Prerequisites: Assembly instructions, object files, and memory addresses.

Learning objectives

• Distinguish symbol resolution from relocation.
• Compute a simple PC-relative relocation.
• Explain the roles of static linking, loading, and dynamic binding.

Separate names from final addresses

A compiler can generate code that calls a function whose definition lives in another source file. At that point the compiler may know the symbol’s name and type contract without knowing its final address. An object file stores machine code, data, symbol information, and relocation records describing fields that still depend on placement or external definitions.

Symbol resolution decides which definition satisfies a reference. Relocation computes the address-dependent value and writes it into the appropriate location or arranges for a later component to do so. These are distinct tasks: finding the right function does not by itself encode a branch displacement that reaches it.

Work a small relocation by hand

Consider an invented instruction format whose branch displacement is target minus the address immediately after the instruction. A four-byte branch begins at address 1000, so its next-instruction address is 1004. If the target is placed at 1120, the displacement is 116. If the instruction instead begins at 2000 while the target remains 1120, the displacement becomes −884.

This is a teaching format, not an assertion that every ISA uses that convention. Real relocations specify exact formulas, field widths, bit layouts, scaling, and overflow rules. In a common notation, S names the symbol value, A an addend, and P the relocation place; some PC-relative relocations use an expression related to S+A−P. The ABI defines the precise interpretation.

A relocation can fail if the target is too far away for the available field. A linker may diagnose that failure or use an architecture-supported transformation such as a longer sequence. Silently truncating a displacement would generally send control to the wrong place.

Loading adds another placement boundary

A static linker combines selected object content into an executable or library. A loader maps executable segments into a process and establishes the initial execution environment. Dynamic linking can defer resolution of shared-library references until load time or, for some mechanisms, first use. Position-independent code uses addressing and indirection strategies that make relocation practical across different load addresses.

A symbol’s existence is not a guarantee that its ABI matches the caller’s expectation. Two components can agree on a name while disagreeing about argument layout or data structure definitions. Versioning and interface discipline therefore matter alongside linker success.

To investigate a linkage failure, classify it first: a missing definition, multiple conflicting definitions, an incompatible object format, an out-of-range relocation, or a runtime lookup failure. Each belongs to a different stage and suggests a different diagnostic. Treating them all as a mysterious compiler error discards the structure that makes them explainable.

Primary reading

• RISC-V ABI specification (RISC-V International).

Practice problem

Using the invented four-byte branch format, compute the displacement for a branch at 4096 targeting 4000. Then assume its signed displacement field ranges from −128 through 127. Would a target at 4300 fit? Explain the difference between finding the symbol successfully and encoding a reachable target.

Worked solution

The next-instruction address for the branch at 4096 is 4100. Target 4000 therefore requires displacement 4000−4100=−100, which lies inside the signed field range and fits. Target 4300 requires 4300−4100=200, which exceeds the maximum 127 and does not fit. Symbol resolution can still succeed because the linker knows exactly which definition and address the name denotes. The failure occurs in encoding the required distance into this instruction’s field. Depending on the real architecture and linker, a longer branch sequence or an intermediate trampoline might solve it; otherwise the linker should report a relocation error. Truncating 200 into the small field would not preserve the specified control flow.

Check your understanding

Which fact does a relocation record primarily describe?

• A source editor’s color theme.
• An address-dependent field that requires adjustment under a specified formula.
• Every possible runtime input.
• The user’s password.

Explanation

Relocation connects final placement or symbol values to encoded machine fields.

A linker finds a target but reports relocation overflow. What is plausible?

• The symbol does not exist anywhere.
• The required encoded value cannot fit the relocation field.
• All source variables must be renamed.
• The program has already completed successfully.

Explanation

Resolution and representability are separate obligations.

Primary reading

• RISC-V ABI specification: RISC-V International

Open the study and save your work →