[The World of Linkers—Lab 10] Rewrite Instead of Copy: Constants and Unwind Tables
Rewrite mergeable constants and unwind records. Merging changes where references land; GC removes FDEs for dead code, while retained pointers and indexes must be rebuilt. Theory 05 explains merging; Theory 08 walks through CIE/FDE bytes.
Starting point: class10 code and tests, in the private repository; access is required. Start from class8's ET_EXEC frontend, using class6 layout and class5 relocation. This backend does not incorporate class9's static PIE. The section policy and CLI are supplied.
Implementation tasks
| Task | Interface | Required outcome |
|---|---|---|
| C10.1 | split | Divide supported merge sections into complete byte Pieces |
| C10.2 | merge, locate | Deduplicate whole pieces and map input locations into output groups, retaining interior offsets |
| C10.3 | frames | Validate CIE/FDE records, variable-length fields, and associated relocations |
| C10.4 | unwind_sizes, emit_unwind | Reserve exact sizes, share CIEs, rewrite FDEs, and emit a sorted index |
| C10.5 | lower_prepared | Merge live split inputs, select FDEs, complete layout and patches, and retain the merged-offset mapping |
The supplied link prepares inputs, calls lower_prepared, then uses Lowered::emit to serialize ELF headers and PT_GNU_EH_FRAME. Its image, entry_address, merged, and map describe one layout. Input metadata stays immutable; later stages can use merged to locate merged contents.
The class10 README defines types, the supported subset, and error order. Group constants by flags, entry_size, and normalized alignment rather than name. Share whole Pieces only, without string-suffix merging. The handout's worked mapping derives deduplication, interior offsets, and aligned output coordinates. Ordinary-symbol and STT_SECTION references map offsets and addends differently; follow the handout's rules.
The unwind subset uses 32-bit framing, specified CIE versions and zR/0x1b encoding, and a PC32 at each FDE's initial location. The handout's record and index walkthrough derives CIE sharing, field rewriting, and index sorting from two FDEs. Personalities and LSDA are unsupported, so this lab does not establish C++ exception support. An annotation's references must not retain code that GC would otherwise discard.
The layout interface lower_with also accepts a validated folding map and code order; lower_prepared supplies an empty map and order by default. It redirects code references, drops folded copies' FDEs, and retains merged-piece coordinates in one layout. The caller establishes folding safety: equal machine instructions do not establish compatible unwind descriptions. The README specifies these preconditions and rules.
A concrete locate calculation
Suppose one string group receives hello\0, world\0, then a second input section containing world\0, hi\0, and hello\0. The output group is hello\0world\0hi\0: the second section's world\0 maps to output offset 6, hi\0 to 12, and hello\0 back to 0. A relocation at input offset 8 therefore lands at output offset 14, inside hi\0. An offset equal to a piece end belongs to the next piece, when one exists. locate is consequently “piece-start mapping plus an intra-piece offset”; adding a section base to the original offset is insufficient.
emit_unwind uses final coordinates as well: retained FDEs are sorted by pc_begin, and .eh_frame_hdr records encode each range start together with the emitted record position. A garbage-collected function has no FDE, and a folded copy must not leave a second record for the representative's address.
Preserve two explicit mappings
This class maintains two input-to-output relations. A merge section needs SectionId + input_offset -> group + output_offset; unwind data needs FDE -> code section/range and FDE -> emitted CIE. The first determines where constants and relocations point. The second determines whether the runtime can find the right CFI for an instruction. Neither can be replaced by “section start plus the old offset.”
Implement in this order: validate and split inputs, build the deduplication map, select FDEs for live code, then rewrite the CIE distance, initial location, and search index after layout. Native checks cover shared constant addresses, removal of dead-code FDEs, and runtime lookup through PT_GNU_EH_FRAME; all three are needed to establish a correct rewrite.
Trace each task to its tests
| Task | Key tests | Property established |
|---|---|---|
C10.1 split | split_strings_and_constants, split_rejects_unsupported_shapes | Pieces cover complete input records, and malformed or unsupported shapes are rejected. |
C10.2 merge/locate | merge_shares_pieces_in_first_use_order, locate_maps_interior_offsets | Deduplication order is stable and an interior input offset maps to one output coordinate. |
C10.3 frames | frames_decode_cies_and_fdes, frames_reject_malformed_unsupported_and_relocations | CIE/FDE association, field widths, and relocation boundaries are validated. |
C10.4 unwind_sizes/emit_unwind | unwind_shares_cies_and_sorts_search_table, unwind_rejects_ranges_overlap_and_reservations | Reserved sizes equal the final encoding, the index is PC-sorted, and no write escapes its reservation. |
C10.5 lower_prepared | dead_merge_sections_and_fdes_contribute_nothing, runtime_finds_live_fdes_through_its_program_headers | Dead sections and FDEs disappear after GC, while the runtime finds live FDEs through program headers. |
The local tests establish mapping rules; the native tests establish that the same mappings survive layout and runtime lookup.
Acceptance and what it establishes
From the cloned repository root on native x86-64 Linux:
cargo test --locked -p class10cargo test --locked -p class10 --releasepython3 scripts/grade.py class10Contract tests cover splitting, first-use sharing, interior-offset mappings, truncated records and relocation ownership, shared CIEs, FDE ranges, index ordering, and reservations.
Native checks verify shared constant addresses across objects and removal of dead merge sections and dead-function FDEs. A supplied program finds PT_GNU_EH_FRAME through AT_PHDR, then checks the index and records describing its live functions. GNU ld output supplies an independent comparison. This establishes runtime discovery and interpretation of the specified index, not a complete exception-runtime test.
A fixture without split/annotation inputs must reproduce class8's bytes and map. Other cases check unsupported inputs and CLI maps. Inspect record counts, function ranges, and execution together; a smaller file alone is not acceptance evidence.