Symbols, Passes, and Relocations: What Assemblers Actually Do With Your Labels

Most developers have a mental model of an assembler as a simple table lookup: you write MOV EAX, 1, the assembler finds MOV in a big opcode table, writes out the bytes, and moves on. That picture is not wrong, but it skips the part that makes assemblers non-trivial. Brian Callahan’s walkthrough of assembler internals is a good entry point for understanding what the rest of the machinery actually does.

The real challenge for an assembler is not encoding instructions. It is resolving references to labels that have not been defined yet.

The Forward Reference Problem

Consider this x86 fragment:

    jmp  done
    mov  eax, 1
done:
    ret

When the assembler encounters jmp done, it needs to emit a relative branch instruction. A relative jump on x86 looks like EB <offset> for a short jump, where <offset> is the signed byte distance from the end of the jump instruction to the target. But at the point the assembler sees jmp done, it has not yet seen the done: label. It does not know the offset.

This is the forward reference problem, and it is the reason that naive single-scan assemblers are either wrong or incomplete. Every non-trivial assembly program has forward references. Functions call functions defined later in the file; branch targets jump past inline data; data sections reference code labels.

The Two-Pass Solution

The standard answer, used by NASM, GNU as, YASM, and most production assemblers, is a two-pass architecture.

Pass one scans the source file without emitting any final machine code. Its only job is to assign addresses. It increments a location counter for every byte-producing directive and instruction it encounters, and records every label it sees along with the current location counter value. At the end of pass one, the symbol table is complete: every label in the file has a known address or section offset.

The location counter logic is subtle. For instructions whose encoding size depends on their operand values (x86 has many such instructions), pass one needs to make size estimates. A conditional jump can be encoded as two bytes (short form, ±127 byte range) or six bytes (near form, 32-bit displacement). If pass one guesses short and pass two discovers the target is too far away, the size estimate was wrong and the whole layout shifts. NASM handles this by defaulting to the larger encoding when the target is unknown, which avoids layout instability at the cost of occasionally larger output.

Pass two scans the source again. Now the symbol table is populated, so every label reference can be resolved to a concrete value. The assembler emits actual machine code, substituting label addresses wherever they appear.

The location counter state at the end of pass one (the symbol table) is essentially a compact representation of the entire program’s layout. Pass two uses it like a read-only database.

Symbol Table Structure

A typical symbol table entry carries:

• The name, usually stored in a separate string table, with the entry holding an offset into it
• The value, meaning the section-relative offset at which the label was defined
• The section index, since labels in .text and .data live in different address spaces during assembly
• Binding and visibility: local (file-scoped), global (exported), or external (imported from another object file)

The local/global distinction matters for what happens next. A label declared global in NASM, or with .globl in GNU as, gets exported into the object file’s public symbol table. Other object files can reference it by name, and the linker will match them up at link time. A label without that declaration is invisible outside its object file.

External references, labels that are used in this file but defined in another, cannot be resolved by the assembler at all. The assembler emits a placeholder value and leaves a note for the linker.

Relocation Entries

That note is a relocation entry. Each relocation entry describes one place in the output where an address needs to be filled in later, and by what rule.

In ELF object files, the relocation section (.rel.text or .rela.text) stores arrays of records. Each record contains:

• r_offset: the byte offset within the section where the patch must be applied
• r_info: a packed field encoding both the symbol index and the relocation type
• r_addend (in RELA format): a constant adjustment to add to the resolved address

The relocation types encode the arithmetic the linker must perform. On x86-64:

• R_X86_64_32: write the absolute 32-bit address of the symbol at the offset
• R_X86_64_PC32: write symbol_address + addend - patch_offset, a PC-relative value
• R_X86_64_PLT32: like PC32, but resolve via the procedure linkage table for dynamic linking

A call instruction in x86-64 position-independent code typically generates an R_X86_64_PLT32 relocation. The assembler writes four zero bytes at the call site and emits one relocation entry saying: when you link this, find the symbol, go through the PLT, compute the PC-relative offset, and patch those four bytes.

You can inspect this directly with objdump -r on any .o file:

$ gcc -c example.c && objdump -r example.o

example.o:     file format elf64-x86-64

RELOCATION RECORDS FOR [.text]:
OFFSET           TYPE              VALUE
000000000000000b R_X86_64_PLT32    printf-0x0000000000000004

The -0x4 addend is because x86 relative addresses are measured from the end of the instruction, and CALL is five bytes total (one opcode byte plus the four-byte displacement). The addend corrects for that.

One-Pass Assemblers and Backpatching

Not every assembler uses two passes. Early assemblers, particularly those running on machines with severe memory constraints, used a one-pass approach with backpatching.

In a one-pass assembler, when a forward reference is encountered, the assembler emits a placeholder and pushes the location onto a fix-up list associated with that label name. When the label is eventually defined, the assembler walks the fix-up list and patches all previous uses directly in the output buffer. If the output was being written directly to sequential media (punched tape, magnetic drum), backpatching was impossible, and some early assemblers required the programmer to define all labels before their first use.

Backpatching works for forward references within a single file, but it collides badly with variable-length instruction encodings. If you commit to a short branch and later discover the target is far away, you either need to re-layout the entire program (expensive) or emit a veneer: replace the short branch with a near branch that jumps to an unconditional branch that goes to the real target. The GNU ARM assembler uses exactly this strategy, called a branch island or trampoline, to handle branches that exceed the range of a 24-bit displacement on ARM Thumb code.

What the Assembler Does Not Do

The boundary between assembler and linker is important to keep clear. The assembler:

• Resolves all same-file forward references via two-pass symbol tables
• Encodes instructions
• Generates relocation entries for cross-file references
• Writes an object file with sections, symbol tables, and relocation tables

The linker:

• Combines multiple object files
• Resolves cross-file symbol references using the relocation entries
• Assigns final virtual addresses to all sections
• Optionally produces position-independent executables (PIE) by leaving some relocations for the dynamic linker to apply at load time

When an assembler error says undefined symbol, it means a label was used but never defined in the same source file and was never declared extern. When a linker error says undefined symbol, the label was declared global in one object file, referenced in another, but no object file in the link actually defined it.

These are different failures at different stages, and the distinction matters when debugging build systems.

Macro Assemblers Add a Pre-Pass

Tools like MASM, NASM, and GNU as are macro assemblers. Before the two-pass assembly proper begins, the macro preprocessor runs. It expands %macro / endmacro blocks in NASM or .macro / .endm directives in GNU as, processes %ifdef / %if conditionals, and handles %include file inclusions.

NASM’s macro system is text-substitution based, similar in spirit to the C preprocessor but operating at the token level with some awareness of instruction context. GNU as macros are simpler by default but gain significant power on specific architectures through architecture-specific macro packages.

The macro pre-pass means the symbol table built in pass one corresponds to the post-expansion source, not the original file. Labels inside macro bodies get unique names to avoid collisions across multiple instantiations; NASM uses the %%label syntax for this, where %% is replaced by an assembler-generated unique numeric prefix on each expansion.

Practical Consequences

Understanding this machinery matters when you are reading compiler output or debugging object file toolchains.

When gcc -S emits assembly, every undefined external function call becomes a label use with no local definition, which means the assembler will emit a relocation entry for each one. You can predict the symbol table of an object file by reading the .globl and extern directives in the assembly. You can predict the relocation table by identifying every instruction that references an external or not-yet-defined symbol.

When linking fails with multiply-defined symbols, it usually means two object files both exported the same global label. The fix is to make one of them static or to use a unique name, not to adjust link order.

When dealing with embedded targets that lack a linker (bare-metal firmware loaded directly from a flat binary), the assembler’s two-pass output is the final product, and relocation entries are irrelevant. Tools like NASM’s -f bin output format skip the object file entirely and produce raw bytes, resolving everything at assembly time. Forward references still work because of the two-pass design, but cross-file references are not possible.

The elegance of the two-pass design is that it solves a genuinely hard problem, arbitrary forward references in a structured language, with a simple invariant: by the end of pass one, nothing is unknown. Everything pass two needs is already computed. That separation of concerns is why assemblers that were designed in the 1950s and 1960s still work the same way today.