[The World of Linkers—Lab 08] Keep What Is Reachable: GC and Link Maps
Collect unreachable storage at section granularity and emit a map explaining KEEP/DROP decisions. Archive extraction determines which objects enter the link; GC determines which sections of those objects enter the output. Theory 05 explains reachability and layout.
Starting point: class8 code and tests, in the private repository; access is required. Reuse archive and symbol selection, class6 layout, and class5 relocation. The CLI, default classifier, ET_EXEC lowering, and link wrapper are supplied. Implement the Prepared frontend state reused by later backends.
Implementation tasks
| Task | Interface | Required outcome |
|---|---|---|
| C8.1 | trace | Traverse Graph iteratively, returning live sections and COMMONs and reporting reachable deferred errors |
| C8.2 | render_map | Sort stable identities, escape arbitrary name bytes, and emit the specified map |
| C8.3 | prepare_with | Validate selected objects, classify sections, resolve references and roots, and build an unplaced live plan |
The class8 README defines types and complete rules. SectionId is a selected-object ordinal plus that object's ELF section index, not an output address. Edges follow selected definitions. Common retains an allocation; Absolute retains no storage; Undefined/Invalid fail only when reached.
Validate all roots in caller order before traversing edges in the specified DFS order. Use an explicit stack rather than the recursive thread stack. The README's graph walkthrough derives a live set and explains the different outcomes for dead references, root validation, and DFS error order. Entry and keep define this course's roots; exports and visibility do not automatically retain constructors, GNU_RETAIN sections, or script-selected content.
Separate structural from application checks: all selected objects' sections, symbols, and RELA tables must be structurally valid, including dead inputs. Only live references generate binding failures and output patches. Prepared preserves stable input identities through immutable accessors; do not reconstruct a plan by parsing the map.
Acceptance and what it establishes
From the cloned repository root on native x86-64 Linux:
cargo test --locked -p class8cargo test --locked -p class8 --releasepython3 scripts/grade.py class8Contract tests cover root-first validation, DFS error order, cycles and deep chains, live COMMONs, and map ordering/escaping. Native tests exercise code-to-data/BSS dependencies, dead cycles, explicit roots, archives, selected definitions, live/dead reference errors, and execution. A valid fixture is also compared with GNU ld.
Check map membership and execution together rather than requiring a smaller file: page alignment can hide the size benefit of removing a small section. The map is not embedded in ELF and must not drive backend layout.
Use four sections for a minimal graph: entry .text.main references .text.helper, .text.dead has no incoming edge, and .data.counter is referenced by helper. With the entry as the root, DFS keeps main, helper, and counter, and drops dead; if counter instead names an undefined symbol, the structure may still be valid until that edge becomes reachable, when binding reports the error. The map records the identities and reasons from this traversal; it must not reconstruct the live set from output addresses.