Lab 7: Static Linker — Symbol Resolution and Relocation

Week: 7
Points: 20
Time: ~5 hours
Deliverable: toolchain/linker/ directory + linked binary on silicon + diary/week-07.md

What you ship

• toolchain/linker/linker.py — the static linker
• asm/week-07/sum-to-n.vof — assembled object (copy of Week 6 output)
• asm/week-07/math-stub.vof — stub math library object file
• asm/week-07/linked.bin — flat binary output from the linker
• lab7_link_map.txt — symbol map generated by the linker
• diary/week-07.md

Lab 7.1: Write the linker

Write toolchain/linker/linker.py. The linker reads one or more VOF v1 object files and produces a flat binary. It must implement:

class StaticLinker:
    def __init__(self):
        self.objects = []         # list of loaded VOF objects
        self.symbols = {}         # global symbol table: name -> final address
        self.base_address = 0     # default load address (0x0000_0000)

    def load(self, vof_path):
        """Read a VOF v1 file; add its text section and symbol table to the pool."""
        ...

    def layout(self):
        """Assign final addresses to each object's text section (sequential)."""
        ...

    def resolve(self):
        """Build the global symbol table from all objects' .symtab sections."""
        ...

    def relocate(self):
        """Patch each relocation entry using the resolved symbol table."""
        ...

    def emit_binary(self, output_path):
        """Write the flat binary. Also write a link map to stdout."""
        ...

The linker must:

1. Accept multiple input VOF paths: linker.py a.vof b.vof -o output.bin
2. Place object text sections in the order they appear on the command line
3. Resolve all relocations before emitting
4. Raise LinkerError: undefined symbol <name> for any unresolved relocation
5. Print a link map showing the final address of every symbol

Lab 7.2: Link sum-to-N against a math stub

Create asm/week-07/math-stub.s — a two-instruction stub that exports the symbol math_multiply (just a NOP + RET for now). Assemble it with your Week 6 assembler.

Then modify your sum-to-n.s to call math_multiply and link both objects:

# Assemble both
python3 toolchain/assembler/asm.py asm/week-07/sum-to-n.s -o asm/week-07/sum-to-n.vof
python3 toolchain/assembler/asm.py asm/week-07/math-stub.s -o asm/week-07/math-stub.vof

# Link
python3 toolchain/linker/linker.py asm/week-07/sum-to-n.vof asm/week-07/math-stub.vof \
    -o asm/week-07/linked.bin 2>&1 | tee lab7_link_map.txt

# Verify: the output should be N*4 bytes where N is the total instruction count
wc -c asm/week-07/linked.bin

Confirm that the call instruction in sum-to-n.vof was patched to the correct address of math_multiply in the final binary.

Lab 7.3: Boot the linked binary on Tang Primer 25K

Load linked.bin into the BRAM-backed instruction memory of your Week 5 CPU and run the simulation:

# Convert linked.bin to the hex format your imem expects
python3 -c "
import struct
data = open('asm/week-07/linked.bin','rb').read()
with open('/tmp/linked.hex','w') as f:
    for i in range(0, len(data), 4):
        word = struct.unpack_from('<I', data, i)[0]
        f.write(f'{word:08x}\n')
"

# Simulate
cp /tmp/linked.hex verilog/cpu/sum_to_n.hex
iverilog -o cpu_sim verilog/cpu/cpu.v verilog/cpu/decoder.v verilog/cpu/immgen.v \
    verilog/alu/alu.v verilog/mem/regfile.v verilog/mem/mem.v \
    worksheets/csa-110/lab5_cpu_tb.v
vvp cpu_sim | tee lab7_silicon_output.txt
# Expected: "[PASS] mem[0] = 0x00000037 (55)"

For those on the hardware path: flash the updated bitstream to the Tang Primer 25K. The linked binary should produce the same UART output as Week 5.

Lab 7.4: Toolchain Diary — forward promise to CSA-201

In diary/week-07.md, write two paragraphs addressed to your future self in CSA-201.

Paragraph 1: Describe what your static linker does NOT do yet. At minimum: it does not allocate registers (symbols map to memory addresses, not hardware registers); it does not optimize instruction placement for cache locality; it does not support shared libraries or position-independent code. Name one concrete situation where register allocation at the linker level would have reduced the instruction count in one of your Week 6 programs.

Paragraph 2: Predict what the CSA-201 register allocator will need to know about your linker's output. Specifically: what information would the allocator need in the link map to make good placement decisions for hot code paths?

This entry is graded on specificity, not length. "The linker doesn't allocate registers" earns no credit. "The function math_multiply at address 0x0018 is called 10 times in my loop; if the linker had placed it within ±4KB of the call site, a JAL would have sufficed instead of AUIPC+JALR; the two-instruction sequence added 4 bytes to every call" earns full credit.

Lab 7.5: Seeded error drill — undefined symbol

Modify sum-to-n.s to call a symbol __nonexistent__ that you do not define anywhere. Run the linker and verify it raises:

LinkerError: undefined symbol '__nonexistent__'

Then fix the program (remove the call or add the symbol). Verify the fixed program links cleanly.

Confirm that your linker does not silently emit a zero-patched binary for unresolved symbols. That class of linker bug has caused real production failures; it is worth a deliberate test.

Toolchain Diary

Record in diary/week-07.md:

• CSA-102 comparison: how does the Py6502v linker (or assembler-with-flat-output) compare to this two-stage assembler + linker pipeline? What does the VOF/ELF object format buy you that the flat 6502 model did not need?
• The link map output: paste the symbol table from lab7_link_map.txt and explain what each entry means
• The forward promise to CSA-201 (Lab 7.4 above)
• Seeded-error result

Grading