#318 Epic: "be dynamic linking" — address-model migration for fast loading & linkage (ADR 0033)

Epic: "Be dynamic linking" — address-model migration for fast loading & linkage

Tracking issue for the campaign defined in ADR 0033 and PRD-loading-and-linkage.md (both on main, committed 4c9731b). This is an epic; individual stages get their own issues that link back here.

---

1. Goal in one sentence

Move funcl's warm/product loading path from the slow middle of the source → fasl → image spectrum to the fast right end (dynamic linking), so build/funcl-asdf boots to an asdf-ready REPL in a fraction of a second instead of ~2.8 s (image) / ~10 s (fasl replay), by deleting per-object reconstruction and per-site relocation, not by tuning them.

2. Why it is slow today (the problem)

Two root causes, both instances of funcl's absolute-address worldview:

1. Early binding. The compiler bakes each callee's absolute address into every call site, so loading a fasl is an O(reference-sites) relocation re-walk (the per-CO patch pass in the FUNCLFA replay path).
2. Overlay image. save-image serializes the heap by a GC walk (collect reachable objects, index-encode inter-object pointers) and the restore path is O(live-objects) allocate-and-decode. Worse, the image is restored onto an already-cold-booted runtime that has already built its own primordial packages / symbol pool / keyword pool, so restore must reconcile identity (keyword canonicalization, pkgsym-offset rebuild, pool-slot relocation). This reconcile path is the source of a whole bug class (cave#74/#44/#132/#135/#136/#137/#314).

This is the inverse of how C dynamic linking is fast (PC-relative code needs no fixup; GOT/PLT indirection makes relocation O(symbols) not O(references); lazy binding defers resolution to first call).

3. Target architecture — two axes

Read PRD-loading-and-linkage.md for the full statement. In brief:

• Axis A — code/calls = be a .so (fdefn/PLT model). Every cross-module call reaches a module-local linkage table (a GOT) PC-relative; the loader fills one slot per distinct referenced name (O(names)); first use lazily binds through a resolver. COLD stays early-bound — the self-host fixed point must not depend on a mutable cell. This continues ADR 0032.

  • ⚠️ The bar is stricter than "call through the symbol's cell." ADR 0032 B.1/B.2 already route calls through a cell but still emit mov rcx, imm64(symbol-record) per site — that only swaps per-site callee relocation for per-site symbol-record relocation, still O(sites). Axis A is done only when the imm64 leaves the text for a PC-relative load from the linkage slot.

• Axis B — heap = be a CDS relocation-bitmap authoritative core. This is ADR 0025's D2/D3 relocation-bitmap image, plus a new authoritative-world layer:

  • Raw-region dump (heap + code as bytes) + a per-pointer-word relocation bitmap (~1.5 % of heap). Preferred base = delta-0 fast path (no relocation pass). ASLR base = one O(pointers) bitmap walk. Fixed MAP_FIXED is a fast path, never the target — ADR 0025 already classes non-PIE + MAP_FIXED + RWX as a security regression.
  • Authoritative + boot-order inversion (new): the runtime detects the embedded image before cold-booting its primordial world and adopts the image's symbol/keyword/package world wholesale, so there is nothing to reconcile. Deletes the identity-reconcile path entirely.

4. Docs to read first (in order)

1. PRD-loading-and-linkage.md — the target architecture + baked-in constraints + acceptance criteria.
2. docs/decisions/0033-recover-not-rewrite-migration.md — the governing decision (recover, don't rewrite) + the staged migration ordering.
3. docs/decisions/0025-security-posture-and-relocation-bitmap-image.md — Axis B is largely this ADR's D2/D3. The relocation-bitmap format, save/load procedure, and the delta-0-hides-missing-bits trap are all specified here.
4. docs/decisions/0032-warm-call-linkage-through-fn-cells.md — Axis A, Stages A/B already shipped; read the codex-P1 deltas.
5. docs/decisions/0001-gc-algorithm.md + GC.md — exact pointer-slot metadata requirement; the bitmap MUST be built on the same slot descriptors the (future, moving) GC uses, not a private map.
6. docs/decisions/0014-image-format.md — the current FUNCLIMG format Axis B supersedes the loading half of.

5. Code map (accurate as of 4c9731b)

Axis A (compiler + linkage):

• src/cold/compiler.lisp:1098 *ag-call-baked-cell-fn* — hook that resolves a name to its baked cell vaddr.
• src/cold/compiler.lisp:1119 ag-emit-cell-closure-stub — shared closure-cell call stub.
• src/cold/compiler.lisp:1184 ag-call-baked-cell-vaddr — the per-name cell address; :3095/:3097/:3118 are the call-emit sites that currently emit asm-mov-rcx-imm64 (the imm64 that must become PC-relative for A2).
• src/stdlib.lisp:2946 ag-linkage-bind — the bind-and-retry resolver (the _dl_runtime_resolve analog).

Axis B (image + loader + regions):

• src/warm/image.lisp — the image subsystem. Key targets to RETIRE: ag-image-heap-needs-collection-p:841 (drives the GC-walk serializer), the pass-1/pass-2 per-object rebuild (search "pass 2" / "pass-2"), ag-image-canonicalize-heap-keywords (the keyword identity reconcile, cave#314), and the pool-slot relocation passes (ag-image-relocate-restored-pool-*).
• src/cold/cold-loader.lisp:527 ag-load-embedded-image-action — the FUNCLIMG trailer probe / embedded-image entry.
• src/cold/cold-image.lisp — the FUNCLIMG format (magic/header/verify), :338 is-FUNCLIMG? predicate.
• src/cold/elf-tiny.lisp:183 +elf-mmap-vaddr+ = #x40600000 and the other hardcoded MAP_FIXED region bases (runtime heap #x01000000, GC start-map #x20000000, mark stack #x38000000, collectable heap #x50000000) — enumerated in ADR 0025 §Context.
• Makefile build/funcl-asdf recipe — bakes the asdf image and concatenates it (ELF + saved image + u64 offset + FUNCLIMG trailer, SBCL-core style).

6. Migration plan + acceptance gates

Strangler-fig: every new path is built ALONGSIDE the old, proven, then the old retired. The tree is never broken; suite-green at every stage (make test-fast-sharded AND the ANSI run AND (asdf:load-system "alexandria") — the last one is non-negotiable; cave#311 was suite-green while asdf was broken).

Axis A (continues ADR 0032 tracking):

• A1 (DONE) — Stage A cell-first calls + Stage B.1/B.2 bind-and-retry resolver + shared closure stub (baked + pkgsym arms).
• A2 — retire per-site text relocation. Call operand becomes a PC-relative load from a module-local linkage slot; imm64 leaves the text; loader fills O(distinct names). Gate: instruction-count A/B (perf stat -e instructions) on a fixed-name, growing-call-site module — both replay and first-call must stay FLAT against growing sites.
• A3 — widen the linkage table to remaining warm early-bound call classes (funcall dispatch, setf/fdefinition boundary), preserving ADR 0032 notinline/setf semantics.

Axis B (file B1–B6 as sub-issues, cross-ref ADR 0025 D2/D3). Order is deliberately ledger-first so the hard invariant is exercised before anything is deleted:

• B1 — boot seam, dispatch to OLD loader. Add "detect embedded image before cold package construction" but call today's reconstruction path. Zero behavior change. Includes loader-substrate ordering (GC-metadata / region-table init ahead of world-adoption) — real work, not a file-tail read.
• B2 — raw-region dump/load at preferred addresses, behind a flag (ADR 0025 D2 raw dump).
• B3 — build the relocation bitmap immediately, even at delta 0, from the GC slot descriptors (same descriptors the moving GC will use).
• B4 — forced non-zero-delta verifier (THE gate). Restore at a deliberately different base; full suite must pass. Proves the bitmap is complete — a delta-0 test cannot (0025's trap: nothing needs relocating so missing bits don't bite).
• B5 — make image authoritative + flip probe to adopt. Dump the full symbol/keyword/package world; runtime adopts instead of reconciling. Gate: forced-divergence check that no cold path minted a symbol/keyword before adoption ("identity for free" holds only if every pre-image creation path is bypassed/proven loader-private).
• B6 — retire reconcile/reconstruct. Delete ag-image-canonicalize-heap-keywords, pass-1/pass-2, pool-slot relocation, ADR 0014 serializer.

Recommended first PR (smallest de-risk): B1 + B3 — land the boot seam still dispatching to the old loader, and start emitting the relocation bitmap while delta is zero. Builds the load-bearing ledger with zero behavior change and no deletion, so nothing can regress.

7. Invariants / guardrails (do not violate)

• COLD is never touched. Self-host fixed point stays byte-identical (funcl-compile ≡ funcl-compile-2). Cell/linkage indirection and data cores are warm/product-only.
• The elisp cold host is permanent (elisp/). Do not propose retiring it; it is the always-runnable cold-start path.
• Exact pointer-slot knowledge is shared between the relocation bitmap and the future moving GC (ADR 0001). Build on the GC slot descriptors, not a parallel map. Symbol records being non-moving is a policy choice to state, not a GC guarantee.
• Measurement discipline: replay-profile symbol labels LIE for baked/JIT code (map aliasing). Prove wins with instruction-count A/B, compiled-in counters, and boot wall-clock — never profiler labels.

8. funcl-specific gotchas an outside dev WILL hit (each cost us a day)

• Two binaries, two stdlib stories. build/funcl-stage2 runtime-loads ./src/stdlib.lisp from CWD (probe target for stdlib work). build/funcl is image-baked (stdlib + mini-clos snapshotted at build time) — stdlib edits need make build to reach it. A NEW prelude defmacro is silently dropped by stage2's reload — probe new macros against build/funcl after make build, never stage2.
• build/funcl foo.lisp COMPILES the file, it does NOT run it. To RUN forms, pipe to stdin: printf '(form)\n' | build/funcl (REPL echoes each value; only NIL is false, 0 is truthy). --hosted foo.lisp emits ./a.out whose exit code is the last form's value.
• REPL echo doubles values. (prin1 v)(terpri) prints v twice (prin1 + REPL echo). Do not read write-string markers — they merge with the echoed NIL on the same line and read as false bugs. Measure BEHAVIOR, not compiler-internal globals read at the REPL (symbol split makes them read stale).
• ALWAYS memory-cap funcl — it OOMs easily. Wrap runs in systemd-run --user --scope -q -p MemoryMax=8G -p MemorySwapMax=0 -- env FUNCL_MAX_HEAP=6G <cmd>. The Makefile's MEMCAP already wraps builds. gdb: wrap in systemd-run --scope -p MemoryMax=6G.
• gdb on a RESTORED image is unreliable (dynamic address layout; the raise path routes through heap-restored vaddrs). Instrument by BEHAVIOR / compiled-in counters instead.
• make elisp-bytecode after ANY edit to src/cold/*.lisp or elisp/* — the host prefers fresh .elc (5–10× on suites and stage1). Stale .elc is skipped by the newer-than check (costs speed, never correctness).
• Paren-check in lisp-mode (not fundamental-mode) with explicit BALANCED/UNBALANCED via condition-case; && echo OK masks the rc.
• Build ≈ 1 min normal; sharded suite ≈ 10–15 min; serial bootstrap ≈ 50 min. Don't run heavy concurrent jobs during a build (starves single-threaded emacs).

9. Definition of done (all simultaneously)

• build/funcl-asdf boots to asdf-ready in a fraction of a second.
• No per-object heap reconstruction, no identity canonicalization at restore; ≤ 1 bitmap walk under ASLR, 0 at preferred base.
• Fasl load is O(distinct linkage names), not O(reference sites) — proven by the fixed-name/growing-site flat A/B.
• Relocation ledger passes a forced non-zero-delta restore.
• (asdf:load-system "alexandria") loads end to end; redefinition + mini-clos healing still work — at every stage.
• COLD self-host fixed point byte-identical throughout.

10. Scope note

This is an address-model migration — it touches codegen operands, image format, symbol residency, GC slot metadata, and the eventual PIE/ASLR posture. It does NOT touch the language layer (reader, macroexpander, type system, mini-clos, conditions, ELF/PE emitter) — those self-host today and stay as-is. Wide but shallow: how addresses are encoded and relocated, not what the language means.