Linker (planned work)

This roadmap covers where the kit linker is headed beyond the static and JIT linking it does today. Two strands: incremental linking (making a relink cost O(change) instead of O(program)) and system-linker compatibility (making kit ld a drop-in replacement for the platform linker over kit's target set). For the linker's current architecture, passes, and invariants see ../LINK.md; for the object substrate and per-format machinery see ../OBJ.md; for how a resolved image runs in process see ../JIT.md. Design rationale lives in those docs — this file tracks open work, not background.

Shared invariants

Everything below rests on three linker invariants that the full-link path already upholds and no incremental or compat path may violate:

• Address stability. Once a runtime/file vaddr is observable it never moves. Unchanged atoms keep their bytes and their addresses, so their relocations are never reapplied. Enforced by overwrite-in-slack / append-to-free-slot, never compact.
• Relocations are durable, relative, and symbolic. LinkRelocApply records survive as data, not burned into bytes before emit: (atom, offset-within-atom, kind, target-name, addend), resolved against current placements at apply time. A moved atom needs zero reloc rewriting.
• Content-hash keying, not transient IDs. LinkInputId/LinkSymId are in-process only; any persisted state is keyed by content hashes and symbol names. Determinism is a dedup nicety, not a correctness requirement.

Incrementality is an accelerator gated on a soundness check: a correct-but-slow full link always beats a fast-but-wrong patch, and any path that cannot prove a change local falls back to a clean full link.

---

Incremental linking

Baseline (done): append-only JIT link

The in-process append path is implemented and is the foundation the rest builds on. kit_jit_publish (an append/replace batch over a KitLinkSession, reporting a bumped kit_jit_generation) grows one live KitJit image with additional compiled objects while keeping every previously published runtime address stable: append cursors with reserved RX/R/RW/TLS slack over one master VA reservation, transactional rollback on failure, generation-bumped invalidation of the cached kit_jit_view, resolution against the existing image + append batch + external resolver with duplicate-strong detection, and a dbg REPL that drives compile → append → DWARF refresh with the worker stopped. This is not hot reload: existing code is never replaced or repatched. Mechanics live in ../LINK.md / ../JIT.md / ../DBG.md.

Open

• Pending source-level breakpoints across appends. A b file:line for a file not yet covered stays unresolved until retried. Keep pending source breakpoint specs and arm them automatically after each append.
• Archive reselection on append. v1 resolves an appended snippet against the already-linked image + external resolver only. Let appended inputs pull fresh archive members, sharing the file-incremental soundness gate.
• kit emu's append consumer. Per-basic-block JIT translation wants to grow a single LinkImage as cold blocks land (see ../EMU.md §6). It is a second consumer of the same append machinery and the motivation for the link_resolve_at / link_resolve_extend stubs below.
• Promote the API. kit_jit_publish stays experimental until emu exercises its append/replace batch, then settles as the stable extend surface.

File-based incremental object link (the "m2" redesign)

Not yet built. Goal: after editing one TU in an N-TU project, the link cost is O(changed atoms + their relocations). Compile-side caching, dep scanning, and the build graph are the build system's problem (../BUILD.md) — this is the obj/link substrate that layer stands on. Incremental link is a -O0/-O1 dev feature; release builds always full-link and stay the canonical reproducible artifact.

The current full-link path already preserves the invariants above and carries the hooks the redesign plugs into (see the comments threaded through src/link/link.c / link_layout.c), but none of the patch machinery exists yet. Design intent and the full trigger/rollback set live in ../LINK.md; the actionable items:

• Resolve the panic stubs. link_resolve_at and link_resolve_extend in src/link/link.c are compiler_panic today. They are the public extend-capable surface for both the file-incremental and emu-append consumers. Wiring them into a mutable LinkSession (patch-vs-full decided internally, reported via a FULL / PATCHED / FELL_BACK_FULL outcome, with graceful fallback rather than panic on exhaustion) is the central integration step. Incrementality is the same session made mutable, not a parallel API: a full link is the degenerate cold case.
• Atom model + soundness gate. Under --incremental, frontends emit one section per function/global so each atom is independently placeable; each atom gets a BLAKE2b content id over bytes || align || flags || canonical(relocs). Reuse is sound only when the changed object's interface (defined global names/bindings, COMMON sizes/aligns, undef set) is unchanged and no archive pull-in changes; any symbol-set/binding flip, new archive member, COMDAT/COMMON-merge change, TLS-size shift, import-set change, slack exhaustion, or layout-affecting flag forces a fall-back via a LinkPatchTxn watermark + clean full link. The JIT preflight is the precedent but it panics; converting "detect non-local" into "roll back + full link" is the new control flow.
• Move-on-grow primitive (swappable behind LinkMoveOps.atom_moved). Ship thunk-on-grow first: calls stay direct, a moved atom leaves a jump island at its old slot (reusing the per-arch JIT call-stub shape); no codegen change, data that outgrows its slack falls back to full link. The GOT-cell variant (one cell updated per move, the same primitive hot reload needs) is the convergence target — build it when hot reload is scheduled, so one mechanism serves both; unifying earlier is speculative.
• Persisted incremental state. Side-band and content-addressed (kit is multi-format — not ELF-embedded sections). One blob in the driver/dist BLAKE2b CAS per input/atom: content ids, the LinkAtomPlace table, name-keyed symbol→vaddr bindings, relative+symbolic relocations, free-list
  • cursor state. libkit reads/writes it as opaque bytes through KitWriter; the build system owns key, storage, and lifetime.
• Non-ELF formats. The atom/slack/move core is format-agnostic; order is ELF → COFF/PE (incremental-friendly: IAT-indirected imports, per-page base relocs, side-band PDB) → Mach-O (heaviest — __LINKEDIT fixups, export trie, indirect symtab, per-page code-sign CodeDirectory each need a bounded incremental updater). Until a format's updater lands it falls back to the fast in-process full link.
• rv64 patch path. Small per-arch surface (island/cell shape + branch-into-island reloc kind); follows ELF/aa64 + ELF/x64 by adapting the trampoline shape.
• Incremental build-id. Per-segment FNV-1a subhashes combined Merkle-style so a patch re-hashes only changed segments, replacing the current whole-image O(image) build-id (kept distinct from the BLAKE2b content/CAS keying).
• Determinism regression lock. Object emission is byte-deterministic; lock it with a two-compiles-equal test so cross-machine / shared-cache dedup is safe. Content/name keying stays the correctness backbone, so drift degrades dedup, never correctness.

Frontend contract and debug info

All frontends converge to ObjBuilder at obj_finalize, so the machinery attaches frontend-agnostically (Toy, asm, WASM included, no per-frontend code). To be incrementally safe a frontend must be a pure function of (source, flags, target, deps), declare its external dependency set (C reuses KitDepIter; single-source frontends report none), use stable source-derived symbol names, and expose frontend_id + schema_version that salt the build-system key. Toy's durable-module REPL path is not pure → folds the module snapshot into the key or opts out of caching.

On debug info: on any changed atom, re-emit that TU's full .debug_*. kit emits one monolithic .debug_line and one .debug_info CU with intra-CU DW_FORM_ref4 offsets, so a function's rows can't be spliced in isolation, and a body change rewrites the instruction→line map even without a move. Per-TU regen is O(changed TU) and unchanged TUs stay byte-stable (their atoms keep their addresses). Per-function CUs for O(atom) debug are a future option, not pursued now. See ../DWARF.md.

Acceptance per format

Author the suite test-first (test/link-incremental/, red → green) over a synthetic multi-TU fixture (core TUs archived into a static lib linked into two exes that share it; no third-party deps): in-slack body edit (PATCHED, every vaddr stable, the whole-program resolve counter does not increment), grow-past-slack edit (PATCHED, atom moves, jump island at old address, caller bytes byte-identical), the soundness gate (each non-local edit ⇒ FELL_BACK_FULL matching a from-scratch link), multi-output consistency, determinism, and a no-op relink. The two correctness gates are vaddr-stability on a patch and fall-back on a non-local edit; both must be green before a format is "done." ELF/aa64 + ELF/x64 first; COFF, Mach-O, and rv64 each repeat the bar. See ../TESTING.md.

---

System-linker compatibility

Make kit ld act as the system linker over kit's support set. Near-term driver: Rust through rustc; target: C, Rust, asm objects, archives, DSOs/dylibs/import libs, PIE exes, shared libs, and relocatable links all behaving like the platform linker for the supported arch/OS pairs (Mach-O on macOS aa64/x64; ELF on Linux glibc/musl aa64/x64/rv64, FreeBSD, and freestanding aa64/x64/rv64/rv32; COFF/PE on Windows UCRT MinGW aa64/x64). The linker preserves format boundaries — ELF --as-needed/TLSDESC rules never leak into Mach-O dylib or COFF import-library semantics.

Covered (tested via test-link)

These paths are landed and exercised by the linker harness; only widen as gaps surface:

• System-linker flag acceptance — kit ld takes the common flags Rust passes (GNU -Wl,/-z, target/sysroot, linker scripts, rlibs, -l:name, -static-pie, -nodefaultlibs, hosted/no-startfile, PE/MinGW, Mach-O version/platform), and Rust std + no-std link through it across the support set.
• Relocatable -r links — link_relocatable.c builds a fresh ObjBuilder (preserving object structure + unresolved externals) for KIT_LINK_OUTPUT_RELOCATABLE ET_REL / MH_OBJECT output.
• Shared-library output — -shared / KIT_LINK_OUTPUT_SHARED emits a loadable ET_DYN with .dynsym/.dynstr/.dynamic/.rela.dyn (src/obj/elf/link_dyn.c).
• ELF symbol-version imports — explicit name@VERSION resolution + Verneed/Vernaux synthesis (FreeBSD libc compat); elf_version_import_test.c.
• COFF library-set search — global fixed-point archive search + weak-alias handling matching MinGW/LLVM; coff_archive_fixpoint_test.c, coff_weak_alias_test.c.
• Relocation descriptor + byte-patch coverage — the per-arch RelocDesc table and representative byte patches are pinned (reloc_desc_test.c, reloc_apply_test.c), including the AArch64 TLSDESC and RISC-V TLS-GD relocation spellings.
• Local-exec TLS relaxation — aa64 (the four TLSDESC relocs), x86_64 (TLS-LD/GD), and rv64 (TLS-GD, incl. the compressed gap) relax local defined TLS; jit_tls_relax_test.c, relax paths in src/obj/elf/link.c.

This is a useful subset, not completion. The work below is the gap between "Rust examples link" and "the platform linker can be replaced."

Open workstreams

1. Ordered input and dependency selection (real --as-needed)

The driver parses --as-needed/--no-as-needed into per-input KitLinkMode, but the resolver does not act on it: collect_needed (src/obj/elf/link_dyn.c) pulls every explicitly-supplied DSO into DT_NEEDED regardless of mode. Make as-needed real linker semantics by modeling, per ordered DSO input: current link mode, selected/not-selected state and why, SONAME/fallback identity for DT_NEEDED, and exports made available to later inputs. Then:

• default/no-as-needed DSOs select as explicit deps; as-needed DSOs select only when they satisfy an eligible strong undef at their position;
• unselected as-needed DSOs do not satisfy later references;
• selected DSOs are the DT_NEEDED source; duplicate SONAMEs suppressed preserving first-selected order.
• GNU linker scripts lower into the same ordered model: INPUT/GROUP as today plus AS_NEEDED(...) pushing/restoring as-needed mode for nested DSO or -l tokens, with nested scripts inheriting/restoring mode.
• Mach-O (dylib load commands, weak/imported behavior) and COFF (import libs, auto-imports, weak externals) get separate parity checks, not ELF semantics.

2. ELF TLS model planning

Plan ELF TLS before final reloc application and dynamic-section synthesis. A planner classifies each TLS reloc/sequence by symbol locality/visibility, imported-preemptible vs. non-preemptible, weak-undef, output kind (exe/PIE/shared/-r), static vs. dynamic, and target TLS variant + thread-pointer bias, then picks an explicit action: relax to local-exec, synthesize initial-exec, preserve/synthesize dynamic TLS/TLSDESC, preserve relocs for -r, or reject with a precise diagnostic. This pass owns the decision; arch code owns only the validated instruction-byte rewrite.

3. TLSDESC completion

Today only executable-local cases relax (materializing the local-exec offset). Full support needs: complete per-arch TLSDESC surfaces (RelocKind, ELF mapping, names, descriptor metadata, read/write, objdump); descriptor GOT/data allocation (two words per unique (symbol, addend)); TLSDESC dynamic relocations in .rela.dyn; integration with .dynsym, symbol versions, DT_NEEDED, PIE shifts, section GC, and DSO selection; checked sequence relaxation aa64 → x86_64 → other ELF arches; and shared-library output that preserves/synthesizes dynamic TLS where final layout is unknown. Imported TLSDESC references are real DSO uses and must select their provider under --as-needed (workstream 1).

4. Architecture relocation and relaxation parity

Per-arch reloc coverage + checked relaxations for modern-toolchain code shapes: aa64 ELF (dynamic TLSDESC path, local-sequence relaxation validated as a unit, host GOT/TLS/unwind shapes); x86_64 ELF (full TLS-LD/GD/IE/LE relaxation + TLSDESC once modeled); RISC-V ELF (expand TLS-GD/LD conservatively, compressed variants, preserve dynamic TLS where local relaxation is illegal); Mach-O aa64/x64 (GOT/TLV/unwind parity vs. Apple objects/archives); COFF aa64/x64 (SECREL, unwind, pdata/xdata, CRT object patterns). Every enum addition pins both descriptor table and a byte patch immediately.

5. Shared libraries and relocatable links — broaden coverage

Baseline -shared/-r emit (above) is exercised mostly on final executables. Deliberately broaden: -shared dynamic symbols/relocs/SONAME + install-names/import-tables + per-format TLS; -r preserving relocs and deferring final TLS/layout decisions; PIE vs. non-PIE staying distinct; and copy relocations, protected visibility, weak imports, COMDAT/section groups, init/fini arrays, unwind tables, and build IDs composing with GC and dynamic linking.

6. Runtime/sysroot interoperability

Find the same runtime inputs as the platform toolchain: crt objects + startup ordering; libc/libm/libpthread/librt/libdl/libutil + libc linker scripts; builtins/unwind libs (libgcc_s, compiler-rt, Rust compiler_builtins); dynamic loaders/interpreters; MinGW UCRT CRT + import libs; FreeBSD versioned libc. The driver prefers explicit command-line inputs, then sysroot/target layout, then host defaults only where safe. Runtime validation distinguishes a linker failure from a too-minimal container (e.g. Alpine missing libgcc_s.so.1). See SYSROOTS.md.

7. Diagnostics and tracing

Precise diagnostics for unsupported cases — target, input file/member, symbol, reloc kind, output mode; why a DSO was selected/skipped and which symbol kept an as-needed DSO; why a TLS access can't relax or be represented dynamically; which runtime/sysroot path was searched. Opt-in structured tracing via KIT_TRACE; no global state.

Validation matrix

Per supported arch/OS/libc family, track: Rust std link + runtime exec (where a runner exists), Rust no-std/freestanding link, C/asm object-corpus link, archive order/group behavior, DSO/dylib/import-lib selection, TLS local + imported access, shared-library output, relocatable -r output, and debug/unwind preservation. First priority is the verified Rust support set (a good driver producing real toolchain objects); second is small focused fixtures per feature so failures are explainable without large external runtimes.

kit ld is the system linker for a target when: Rust and C toolchains use it directly with only target/sysroot/runtime config (no per-target wrapper rewrites); exes and shared libs run under the target loader; readelf/otool/llvm-readobj dynamic metadata matches the platform linker for covered cases; -r preserves the relocation surface; local TLS relaxations are legal and checked and dynamic TLS is emitted when required; archive/DSO/import-lib selection follows format semantics; and negative cases fail early with actionable diagnostics.