kit

kit
git clone https://git.ryansepassi.com/git/kit.git
Log | Files | Refs | README

Instrumentation & Dynamic-Analysis Tools

Forward-looking design for a family of debugging and profiling tools in the Valgrind / callgrind / AddressSanitizer / UBSan tradition. The load-bearing decision in this document is that kit's user-mode emulator (src/emu, ../EMU.md) becomes the substrate for the dynamic-binary- instrumentation (DBI) family, and that its design is fixed now, while the emulator is still partial, so the instrumentation contract is built in from the start rather than retrofitted.

Status of the substrate at time of writing:

This is the right moment to get the seams right once.

1. Three substrates, one document's focus

Kit grows three distinct instrumentation substrates. They are complementary, not competing; this document designs A in depth and situates B and C.

Substrate What it observes Mechanism Status
A Emu DBI tools (this doc) Any guest binary, instruction-by-instruction Software emulation + per-block JIT translation; tool hooks at the runtime/lift boundary emu partial (rv64 only)
B Compiler sanitizers kit-compiled programs, from any frontend Compile-time IR instrumentation + a runtime library not started
C Host-JIT debugger / profiler kit-compiled code running natively on the host Software breakpoints, displaced single-step, FP-walk sampling kit dbg shipped, kit prof planned (DEBUG.md)

The three differ on a single axis — where the observed code runs:

Why the emu is the right home for Family A. The emu already is a DBI engine: it disassembles guest basic blocks, lifts them through the CG pipeline, JITs them, and dispatches through a code cache — structurally identical to Valgrind's disassemble-and-resynthesize core, with the kit CG/opt IR playing the role of VEX. Adding the DBI tool family is therefore not a new engine; it is a tool-plugin layer over an engine kit already has. The cost of getting it wrong is high, though: the emu's hot path (dispatch, memory helpers, lifting) is exactly where tools must hook, so the seams must be first-class.

2. The architectural thesis: observation is a first-class emu concern

The emu was conceived as a way to run a guest binary. Once the DBI tool family is a primary customer, the emu's job widens: it must let a tool observe every architecturally-visible event — instruction retirement, memory access, control transfer (call/return/branch), and syscall — with enough fidelity to count, check, shadow, or trap on each, while staying arch-neutral (so a tool written once works for rv64, aa64, x64, and any future guest) and format/OS-neutral.

Valgrind's enduring lesson is one core, many tools: a single instrumentation core exposes a small hook vocabulary, and Memcheck, Callgrind, Cachegrind, Massif, Helgrind are all plugins over it. Kit adopts the same shape. The EmuToolHooks vtable (§4) is that hook vocabulary. Everything else in this document is either (a) making sure the emu's hot seams can drive those hooks without the hooks evaporating under future optimization, or (b) cataloguing the tools that ride them.

Two-way freeness is the prize, and it holds on two axes at once:

3. The four load-bearing decisions

These were settled explicitly during design and shape everything below.

  1. Tool seam = a hook vtable at the runtime boundary (not an IR pass, not an interpreter-only plane). EmuToolHooks is invoked by the runtime helpers, the dispatcher, a thin lift-time shim, and the syscall trampoline. Arch- neutral, shared across JIT and INTERP modes, and — critically — designed to survive block chaining (§7). The CG-IR-pass and interpreter-plane approaches are compositional refinements under this spine (§4.4), not the spine.

  2. Memory = stable indirection whose fast path degrades under tools. When no memory tool is active, the lifter may inline a softmmu/TLB fast path. When any memory tool is active, every access routes through the checked helper seam and fires on_mem_access. "Fast when unobserved, fully observable when needed" — the QEMU/Valgrind answer. Peak throughput is capped only while a memory tool runs (§6).

  3. Stepping = tiered. A single-instruction-block mode (cap the block to one guest instruction) delivers JIT-speed single-step, guest-PC breakpoints, and watchpoints immediately, with no interpreter refactor. A later per-IR-op interpreter yield enables rich interpreter-resident tools (§8).

  4. Scope = full-suite design, one reference impl per class. The hook ABI and seams are general enough for the whole suite (callgrind, cachegrind, memcheck, massif, helgrind, asan/ubsan, strace, a guest debugger); §12 carries a worked reference implementation for one tool in each of the three tool classes (profiler, memory-checker, debugger) to prove the seams.

4. The EmuToolHooks ABI — the spine

A tool is a struct of function pointers plus an opaque user context, registered on a KitEmu before stepping begins. The emu core invokes hooks at fixed observation points. A NULL hook means "not observed" and costs at most one predicted-not-taken branch; a NULL vtable means "no tool", and the emu takes its existing fast paths unchanged.

4.1 The interface

/* include/kit/emu.h — public, embedder-facing */
typedef struct KitEmuToolHooks {
  /* Control flow / profiling. block_id is the guest PC of the block head;
   * stable across re-translation (the bijective emu_block_<pc> identity). */
  void (*on_block_entry)(void* user, KitEmu*, uint64_t block_pc,
                         uint32_t guest_insn_count);
  void (*on_insn_retire)(void* user, KitEmu*, uint64_t guest_pc,
                         const KitDecodedInsn*);        /* step/cachegrind/cov  */
  void (*on_branch)(void* user, KitEmu*, uint64_t from_pc, uint64_t to_pc,
                    KitEmuEdgeKind kind);               /* CALL/RET/JMP/COND    */

  /* Memory. addr/size are guest; is_write distinguishes load vs store;
   * host_ptr is the resolved host pointer AFTER the bounds check (NULL on a
   * faulting access). Return KIT_EMU_TOOL_DENY to convert the access into a
   * guest fault (watchpoint / poisoned-redzone hit). */
  KitEmuToolVerdict (*on_mem_access)(void* user, KitEmu*, uint64_t addr,
                                     uint32_t size, bool is_write,
                                     void* host_ptr, uint64_t guest_pc);

  /* Address-space lifecycle — lets a shadow plane track map/unmap/protect. */
  void (*on_map)(void* user, KitEmu*, uint64_t va, uint64_t len, uint8_t perms);
  void (*on_unmap)(void* user, KitEmu*, uint64_t va, uint64_t len);

  /* Syscalls — strace, and allocation interception via brk/mmap. Fires
   * around the existing single choke point. */
  void (*on_syscall_entry)(void* user, KitEmu*, const KitEmuSyscallRequest*);
  void (*on_syscall_exit)(void* user, KitEmu*, const KitEmuSyscallRequest*,
                          const KitEmuSyscallResult*);

  void* user;
} KitEmuToolHooks;

KitEmuEdgeKind is derived directly from the decode flags already on KitDecodedInsn (KIT_DECODE_CALL/RET/BRANCH/TERMINATOR, include/kit/arch.h), so the emu classifies edges without arch-specific code.

4.2 Where each hook is driven

Hook Driven from Frequency
on_block_entry block prologue (baked in at lift time by a shared shim) once per block execution — survives chaining
on_insn_retire only emitted when a retire-level tool is active; per-guest-insn shim in the lifted body, or naturally in 1-insn-block step mode per instruction
on_branch block epilogue / terminator lowering once per block exit
on_mem_access the __emu_* memory helpers (src/emu/runtime.c) at the emu_addr_space_ptr choke point per guest load/store (tool-active path only)
on_map / on_unmap emu_addr_space_map / _unmap / _protect (src/emu/image.c) per VM change
on_syscall_* emu_syscall trampoline (src/emu/runtime.c) per guest syscall

The crucial design point is where on_block_entry lives. It must be emitted into the block's own prologue (a few CG ops the shared shim prepends to every lifted block), not into the dispatcher loop. Today the dispatcher sees every block because there is no chaining; once chaining lands, blocks jump directly to one another and the dispatcher is bypassed. Counting in the prologue is invariant to that change — this is exactly how real Callgrind bakes counters into the translation rather than the dispatch loop. Driving on_block_entry from the dispatcher would be the easy thing to do today and the wrong thing for the chaining future; the contract forbids it.

4.3 The lift-time shim (how hooks stay arch-neutral)

The per-arch lift_block must not know about tools. Instead, translate_block (src/emu/emu.c:420) wraps the arch lifter:

translate_block:
  decode_block            (arch)
  cg_begin block fn
  tool_prologue(cg, ctx)         <-- shared: emits on_block_entry call iff a
                                     block/profiling tool is active
  arch->emu->lift_block(...)     <-- unchanged per-arch body
  tool_epilogue(cg, ctx)         <-- shared: emits on_branch call iff active
  cg_finish / link / cache

tool_prologue / tool_epilogue emit ordinary CG calls to new runtime helpers (__emu_tool_block_entry, __emu_tool_branch) resolved by emu_runtime_extern_resolver to thin C trampolines that forward to the active KitEmuToolHooks. Because they are emitted by the shared wrapper, every arch gets them for free and the rv64 lifter needs no change to acquire block/branch observation; only the memory hook touches lifter-emitted code, and that is already a helper call in the contract (§10).

4.4 How the other two strategies compose under the spine

The IR-pass and interpreter-plane strategies are not discarded; they slot in as implementations of specific hooks for tools that need more than the boundary gives:

This is the payoff of choosing the vtable as the spine: a tool is defined by which hooks it implements, and the emu is free to drive those hooks from a helper call, an inlined check, an IR-pass insertion, or an interpreter step, whichever the active configuration makes cheapest.

5. Shadow memory as a first-class, extensible plane

Most Family-A tools (memcheck A/V bits, ASan addressability, MSan definedness, DRD/Helgrind access history, a watchpoint set) need shadow memory: metadata indexed by guest address. The emu already has the precedent — every EmuMap carries per-page dirty_pages and translated_pages bitmaps (src/emu/emu.h:91). The design generalizes this into named shadow planes.

/* A tool registers a shadow plane describing bytes-of-shadow per guest byte.
 * The emu allocates/extends/frees the plane in lockstep with EmuMap lifecycle
 * (on_map/on_unmap/protect), so the tool never tracks the VM layout itself. */
typedef struct EmuShadowPlaneDesc {
  const char* name;
  uint32_t shadow_bits_per_byte;   /* memcheck V=8, ASan ~0.125 (1/8), watch=1 */
  uint32_t shadow_bits_per_page;   /* coarse per-page planes (dirty-style)      */
} EmuShadowPlaneDesc;

uint8_t* emu_shadow_for(EmuShadowPlane*, uint64_t va, uint64_t nbytes);

Two reasons this belongs in the emu core, not in each tool:

  1. The emu is the only module that knows the VM layout (EmuAddrSpace is the sole guest→host translator, ../EMU.md). A tool that tracked maps itself would duplicate split/merge/brk/mmap logic and drift.
  2. The generation-counter invalidation that handles self-modifying guest code already touches per-page metadata; shadow planes ride the same machinery, so SMC and mprotect stay correct for shadows automatically.

The fast/slow memory split (§6) reads cleanly against planes: with no plane registered, the inline TLB path returns the host pointer directly; with a plane registered, the access takes the helper path, which computes emu_shadow_for(addr) alongside emu_addr_space_ptr(addr) and calls on_mem_access with both in scope.

6. The memory seam: stable indirection, fast path degrades under tools

Memory access is simultaneously the emu's hottest path and its richest observation point. The decision is to keep a stable indirection that a tool can always intercept, while permitting an inline fast path when unobserved.

guest load/store in a lifted block
        │
        ├── no memory tool active ──> inline softmmu TLB probe
        │                              (va→host_ptr, perm check) ──> host access
        │
        └── memory tool active ─────> __emu_load/store* helper (current path)
                                       │
                                  emu_addr_space_ptr  (bounds/perm, image.c:333)
                                       │
                                  on_mem_access(addr,size,is_write,host_ptr,pc)
                                       │   verdict ALLOW ──> host access
                                       └─  verdict DENY  ──> emu_fault_deliver
                                                            (watchpoint / poison)

Design notes:

7. Block chaining vs. instrumentation (don't paint the corner)

../EMU.md documents chaining as design intent: bump-allocate blocks into one growing RX image (EmuCodeRegion) and patch direct jumps between them, falling back to __emu_dispatch for not-yet-translated edges. Chaining removes the dispatcher round-trip — and with it, any instrumentation that lived in the dispatcher.

The contract that keeps both working:

  1. Block/branch/insn counting lives in the block body (prologue/epilogue shim, §4.3), never in the dispatcher. Counting is then invariant to chaining.
  2. Chaining is disabled while a tool that needs the dispatcher is active. Some tools genuinely want the dispatcher boundary (e.g. a coarse single-step that stops between blocks, or a tool that re-checks a breakpoint set each edge). For those, a tool_requires_dispatch flag forces the one-block-per-image strategy. This is cheap and already the current default; chaining is the opt-in fast mode, and "a heavy tool turns chaining off" is an acceptable, explicit trade.
  3. on_branch is emitted at the terminator, so even under chaining a profiler sees every edge (the patched jump and the hook call coexist; the hook is just more block-body code).

The single rule: no observation may depend on the dispatcher being on the hot path. Encode it in the shim, gate chaining on the tool, and the futures don't collide.

8. Stepping, breakpoints, watchpoints — a guest debugger

This is Family A's debugger (distinct from the host-JIT kit dbg of Family C — see §9). It debugs guest code under emulation.

Tier 1 — single-instruction-block mode (ship first). Add a KitEmu step mode that caps the block to one guest instruction (effectively EMU_MAX_INSTS_PER_BLOCK = 1 for the translate, plus a terminator after the single insn). Then:

Tier 1 gives a usable b/r/s/c/x/p/watch REPL over any guest binary, on any guest arch, with zero interpreter work.

Tier 2 — per-IR-op interpreter yield (later). The interpreter currently runs a whole frame to completion (kit_interp_resume, no per-op hook). Refactoring interp_run_stack to yield between IR ops gives (a) sub-instruction stepping for guest debugging, and (b) the uniform per-op execution point the heaviest shadow-value tools want (Memcheck definedness, taint). This is a real change and is deliberately deferred behind Tier 1 so a working debugger does not block on it.

9. Relationship to the host-JIT debugger and kit prof

Family C (DEBUG.md) and Family A overlap in vocabulary but not in substrate, and the doc must keep them from being conflated:

Family C (kit dbg/kit prof) Family A (emu tools)
Observed code kit-compiled, native, on host CPU any guest binary, on synthetic CPU
Breakpoint software INT3/EBREAK patch, refcounted guest-PC set in on_block_entry
Single-step displaced step on real CPU (ArchDbgOps) 1-insn block / interp yield
Watchpoint needs HW debug regs (blocked, DEBUG.md §8) on_mem_access DENY (free)
Sampling SIGPROF + FP-walk ring (KitProfBuf) deterministic block/insn counts
Speed near-native 10–50×

Shared seams to reuse, not duplicate: the ArchDecodeOps disassembler, the src/debug/dwarf_* symbolication, the KitProfBuf folded-stack ring and flamegraph output (a deterministic emu-callgrind can emit the same folded format kit prof does), and the REPL command engine (DEBUG.md §4 calls for a factored, machine-readable command engine — the emu debugger should consume the same engine so editors get both for one integration cost).

The two are genuinely complementary: Family C answers "how does my native build behave and where is its time going" at native speed; Family A answers "is this binary correct — memory-safe, defined, race-free — and what is its exact instruction-level cost" regardless of source or host arch.

Profiling is one tool with two collectors

A specific and important case of the above: kit's sampling profiler (kit prof, DEBUG.md §7) and the emu's deterministic profiler (§12.1) are not substitutes, and kit prof should not be rebased onto the emu substrate. They answer different questions — the classic perf-vs-callgrind split:

kit prof — sampling (Family C) emu callgrind — counting (Family A)
Measures real wall/CPU time exact instruction counts
µarch effects (cache/branch/TLB) real, captured invisible / only ever simulated
Determinism statistical, varies run to run bit-exact, reproducible
Speed native 10–50×
Target native kit-JIT'd code any guest ELF, any guest arch

Kit's own perf campaign already proves both are needed: macOS sample missed the biggest −O0 win (the O(n²) strtab_add) because sampling sees self-time leaves only, while Linux valgrind callgrind caught it through inclusive instruction attribution. Moving prof onto the emu would lose real timing, the ability to profile long / IO-bound programs (the 10–50× tax), and native-target coverage; and sampling inside the emu is pointless — the emu can count exactly, so exactness is its job.

What they should share is everything downstream of collection:

collectors (front-end)                  shared profile core
──────────────────────                  ───────────────────
host sampler: SIGPROF + FP-walk    ┐
  weight = samples (≈ µs)          ├─> weighted call graph / weighted stacks
emu counter:  on_block_entry +     ┘     → symbolication (kit_dwarf_* / addr_to_sym)
  on_branch shadow call stack            → folded (flamegraph), flat self/cumul,
  weight = instructions (exact)            speedscope / pprof / callgrind.out

Only the raw collection (a sample ring vs a per-block count + edge map) and the cost-unit label (samples ≈ time vs instructions, exact) differ; the two converge at the weighted-call-tree stage and share symbolication and every output format from there on. So the architecture is one profile core, two pluggable collectors: KitProfBuf stays the sampler's raw buffer, the emu counter keeps its own count/edge map, and both lower into the shared aggregation / symbolication / render layer.

CLI: keep kit prof as sampling/native; expose the deterministic collector as kit prof --exact (or kit emu callgrind). The payoff is an in-tree, host-independent, deterministic callgrind that emits the same flamegraph the sampler does — retiring the external-Linux-valgrind dependency the perf campaign currently leans on.

10. Substrate punch-list — make the emu tool-ready now

The highest-value, time-sensitive work, because aa64/x64 lifters are unwritten and chaining is undesigned-in-code. Doing these first means tools are additive later instead of forcing an emu redesign.

  1. Freeze the memory-access contract for lifters. Specify (in ../EMU.md and the ArchEmuOps doc-comment) that every guest load/store must go through the __emu_* memory helpers — never an inlined host access — unless it goes through the sanctioned softmmu TLB intrinsic (§6) that itself preserves the helper fallback. Write this before aa64/x64 lifters exist so all three honor it. The rv64 lifter already complies.
  2. Add the lift-time shim points (tool_prologue/tool_epilogue in translate_block) and the __emu_tool_* runtime trampolines, even if the only tool initially is a no-op. This nails down where block/branch observation enters, arch-neutrally.
  3. Generalize per-page metadata into shadow planes (§5), built on the existing dirty_pages/translated_pages precedent, wired to map/unmap/protect.
  4. Route memory faults uniformly through emu_fault_deliver for all accesses (the checked variants already do; ensure the plain variants and the future TLB path can escalate identically), so a tool DENY verdict has one delivery path.
  5. Land the 1-insn-block step mode (§8 Tier 1) — small, unblocks the whole debugger class, and exercises on_insn_retire end-to-end.
  6. Define KitEmuToolHooks in include/kit/emu.h and a kit_emu_set_tool_hooks(KitEmu*, const KitEmuToolHooks*) setter; thread the active vtable through the runtime trampolines and the syscall trampoline.
  7. Decide the chaining/tool interaction flag (tool_requires_dispatch, §7) as part of the chaining design rather than after it.

Items 1, 2, and 7 are the irreversible-if-skipped ones: they constrain code that is about to be written (the aa64/x64 lifters, the chaining loop). Everything else can be added incrementally.

11. Family B in brief — compiler sanitizers across all frontends

Out of this document's primary scope but recorded so the substrates stay coherent. Family B instruments kit-compiled programs at compile time, and its design centerpiece is that the public CG API is kit's narrow waist: every frontend (C, wasm, toy, future) funnels through kit_cg_*, so instrumenting below that surface gives all frontends the tool for free.

This is a separate roadmap to write when Family A's tier-1 lands; it shares only the philosophy (instrument the narrow waist) with Family A, not the substrate.

12. Reference implementations — one per tool class

Concrete sketches proving the §4 hooks suffice for each class.

12.1 Profiler class — emu callgrind (deterministic)

Goal: exact, reproducible instruction counts with inclusive caller→callee attribution, output in callgrind.out format for callgrind_annotate / KCachegrind, and folded stacks for the shared flamegraph path (§9).

Hooks used: on_block_entry (per-block instruction count from guest_insn_count), on_branch (maintain a shadow call stack: push on CALL, pop on RET, attribute self-cost to the current frame and inclusive cost up the stack), optionally on_mem_access for a Cachegrind-style cache model.

state: shadow call stack of (fn_pc, self_count); map (caller,callee)->count
on_block_entry(pc, n):   cur.self += n; total += n
on_branch(from,to,kind):
    CALL: edges[(cur.fn,to)]++; push(to)
    RET:  pop()
    else: if to starts a known fn, treat as tail edge
on exit: walk frames, write callgrind.out (fn = nearest symbol via DWARF)

Determinism falls out of counting rather than sampling — the same property that makes this directly useful for kit's own -O0 perf campaign (it retires the external-Linux-callgrind dependency the perf work currently leans on, and runs on any host for any guest arch). ~one file (src/emu/tool_callgrind.c) + a driver verb.

12.2 Memory-checker class — emu memcheck (addressability + redzones)

Goal: detect invalid reads/writes, heap buffer overflows, and use-after-free on an unmodified guest binary — Memcheck's core, minus (initially) bit-precise definedness, which waits for the Tier-2 interpreter (§8).

Hooks used: on_mem_access (consult the A-bit shadow plane; DENY → fault on an unaddressable byte), on_syscall_entry/exit (intercept brk/mmap to set addressability), and allocation interception via the import-binding mechanism the emu already has (emu_call_host_import, ../EMU.md): bind the guest's malloc/free so the tool can poison redzones around each block and quarantine freed blocks.

shadow plane "A": 1 bit per guest byte (addressable?)
on_map(va,len):        mark addressable per perms
malloc(n) intercept:   underflow+overflow redzones poisoned; body addressable
free(p)   intercept:   poison body; quarantine (delay reuse) -> use-after-free
on_mem_access(addr,size,is_write,_,pc):
    if any byte in [addr,addr+size) not addressable: report + DENY

The redzone + quarantine logic is identical to ASan's runtime; here it lives in the tool, driven by the import-binding and shadow-plane seams. Adding the V-bit (definedness) plane later is the same plane mechanism plus per-op propagation in the Tier-2 interpreter — the hook vocabulary does not change.

12.3 Debugger class — emu dbg (guest-level interactive debugger)

Goal: a gdb-style REPL over guest execution: breakpoints, single-step, watchpoints, register/memory/backtrace inspection, source listing — for any guest binary and arch.

Hooks used: on_block_entry (breakpoint set probe), 1-insn-block step mode (single-step), on_mem_access DENY (watchpoints). Inspection uses ArchEmuOps accessors, emu_addr_space_ptr, the shared ArchDecodeOps disassembler, and the DWARF consumer for file:line and locals.

b <sym|addr>:  resolve via DWARF/symbols -> guest PC into breakpoint set
r:             kit_emu_step until on_block_entry hits a breakpoint
s:             one 1-insn-block step
watch <addr>:  add to watch set -> on_mem_access DENY on intersect
bt:            FP-walk the guest stack (arch fp/lr offsets from ArchEmuOps)
p <reg|var>:   get_gpr / DWARF loc-expr eval over guest memory
x <addr>:      emu_addr_space_ptr + format

This reuses the factored REPL command engine that DEBUG.md §4 already calls for, so the guest debugger and the host-JIT debugger present one command surface to editors/IDEs.

13. Phasing

  1. Substrate (the §10 punch-list). Hook ABI, lift-time shim, shadow planes, 1-insn step mode, memory-contract freeze, chaining/tool flag. No user-facing tool yet — this is the load-bearing, time-sensitive work.
  2. Tier-1 tools. emu callgrind (§12.1), emu strace (on_syscall_* only — nearly free), and the emu dbg watchpoint/breakpoint/step debugger (§12.3). These exercise every hook except the heaviest and deliver immediate value (including the in-tree deterministic profiler kit's perf work wants).
  3. Memory checker. emu memcheck addressability + redzones (§12.2) on the shadow-plane + import-binding seams.
  4. Tier-2 interpreter yield (§8) → bit-precise definedness (memcheck V-bits / MSan-for-guest), taint, and sub-instruction stepping.
  5. Family B (compiler sanitizers, §11) as its own roadmap once Tier-1 proves the report/runtime patterns.

Each phase is independently shippable; phase 1 is the only one whose omission would force later rework, which is the whole reason this document exists now.

14. Open questions / risks