nordisk/nornir

The executable graph: plan

Status: BUILT (2026-11-06). The description of what is built, with the measured numbers, is exec-graph.md; where this plan and that chapter differ, the chapter is right. The plan as decided: PLAN (2026-11-06). Owner order: Mímir's Rust → graph engine must write a graph that is 1:1 with the code, so that the graph can be executed like a program. This file fixes the format, the rules and the gates before the code is written. Every section says what is built and what is not.

Words: a unit is one crate compiled once. A body is the MIR of one fn, method, closure or coroutine. A site is one statement or terminator of a body. An instance is a body with concrete generic arguments. The boundary is the place where Rust code calls C or the kernel.

0. Design decisions

D1. One graph (owner correction, first decision)

There is ONE form of the MIR facts, and it is lossless. The driver writes the lossless rows only. The lossy form of today is not kept as a second format:

• The name-free fingerprints (the mir_body payload: block fingerprint, terminator kind, successors) become a DERIVED view. One function, mimir_schema::mir::legacy, computes them from the lossless row by the canonical text of today. The driver calls it and writes the result as the derived column it is (the mir_body node keeps its id and its bytes).
• The mir_block payload (statement text, locals, def-use) and the CFG_SUCC edges are NOT written any more. A reader that wants them calls the same function on the same lossless row and gets the same text as today. The lens library, the room's MirSide and the clone lens all read the blocks this way.
• Every crate of the universe gets full facts: own crates, dependencies and the toolchain's crates. The default MIMIR_MIR=local, which left the dependencies with fingerprints only, is removed. The knob stays for a quick development run (off, local), and a dump that used it says so in its stats.json (mir_scope).
• The lenses do not get heavier by default. The lens loader and the room keep reading what a lens needs (the derived fingerprints, CALLS and the other edges). Block detail is derived on demand, for the same units as today (the workspace's own crates), from the same rows.
• The schema goes from 7 to 8. A lake stamped older than 8 is wiped at open and read again from git (rule of mimir-schema/src/lib.rs: the lake is derived data, no backup is needed). The cause: mir_block rows and CFG_SUCC edges leave the node and edge tables, and two tables are added.

D2. Which MIR

The body is rustc's mir_promoted body, as today: built MIR after SimplifyCfg and promotion, before every optimisation. It is the same at every -C opt-level, and it is the body the fingerprints of today come from, so the derived view gives the same values.

mir_promoted is before drop elaboration. Two facts make it executable:

• Drops. A drop(place) in this MIR means "drop if the place is initialised here". The driver runs rustc's own dataflow (MaybeInitializedPlaces and MaybeUninitializedPlaces, the analyses drop elaboration uses) and writes the answer on each drop: live (always initialised: the drop runs), dead (always moved out: the drop does nothing), maybe (decided by a flag at run time: both are possible).
• Coroutines. An async fn body keeps its yield terminators. The executor gives Future::poll on it this meaning: enter at the start or at any resume point, run to the next yield (return Pending) or to return (return Ready). This is what the state machine rustc generates does.

D3. Instances are facts of the same graph, written per program

A generic call or a trait call has no single callee in the body's own text. The callee depends on the instance. A second pass per PROGRAM (cargo mimir-dump --exec, §3) resolves these from the program's entry points, the way rustc's mono collector does, and writes the answers as rows that point at the same body rows. There is no copy of a body per instance. The only bodies this pass writes are the ones no crate owns: compiler shims (drop glue, fn-pointer and closure adapters, vtable shims).

D5. The storage format is a choice (owner decision)

One logical schema, three stores, chosen with --format ipc|znippy|graphar: Arrow IPC with zstd buffers (the default), znippy (the code path of the lenses' graph-package), and graph-ar (vertices = exec.nodes, edges = exec.edges with their properties, GraphAR layout). The store is a small trait in a new crate nornir-mimir-store; the graph-ar store lives in an UNPUBLISHED crate and registers itself through a hook, as the lenses' SnapshotStore does. No published crate depends on graph-ar or knut. Each store has a round-trip test on the same fixture (write, read back, equal rows). §2.5 has the layouts and the measured sizes.

D6. A row's content does not move with the code

Every table carries a content hash, the lake's delta key. Positions are stored relative to the owner's first line, and that line is outside the hash, so inserting a line at the top of a file re-emits nothing. Keys that name a crate have a stable form without the version (code_mir::stable_key), so a dependency bump keeps the identity of every row that names the crate (the rule of schema 5 for node ids).

D4. The C boundary stays a map

libc and assembly are not Rust. The graph ends at the foreign item, and the SYSCALLS map (mimir-ingest/src/boundary/libc_map.rs) says which system calls a C function makes. This plan does not read C control flow. A later step may read the machine code of the linked binary.

1. Dataflow

 cargo mimir-dump  (cargo check, RUSTC_WRAPPER = mimir-driver, every unit)
   │
   │ per unit, after analysis
   ▼
 mir_promoted body ──► lossless row ────────────► <stem>.mir.arrow    code_mir        (1 row / body)
   │                       │
   │                       └─ legacy(row) ──────► nodes.arrow         mir_body.ty     (derived column)
   │ rustc dataflow (drop state)
   ▼
 cargo mimir-dump --exec  (the same workspace once more: cargo check -Zbuild-std, MIR of every crate kept
   │                       in its metadata; only the program's own unit works)
   │ from main / lang_start: Instance::try_resolve, vtables, fn pointers, const eval, static initialisers
   ├─────────────────────────────────────────────► <bin>.inst.arrow   code_instances  (1 row / instance)
   ├─────────────────────────────────────────────► <bin>.mir.arrow    code_mir        (shim bodies only)
   └─────────────────────────────────────────────► <bin>.data.arrow   code_data       (1 row / static or allocation)
   ▼
 lens loader / room MirSide:   legacy(row) on demand ─► mir_block text + CFG_SUCC   (same bytes as schema 7)
 mimir-exec (new crate):       code_mir ⋈ code_instances ⋈ code_data ⋈ SYSCALLS map
   │   abstract interpretation from the entry points
   ▼
 exec.nodes.arrow   boundary call sites (instance, block), system calls, argument facts, marks
 exec.edges.arrow   "the next system call can be", per thread / task entry
 exec.set.json      the possible SET (projection; same shape as mimir.possible-syscalls/1)

2. The format

All three tables are Arrow. Lists are Arrow List columns: one row holds the whole body as parallel arrays (a struct of arrays). A string lives in the row's own pool (strs), and a string column holds indices into it (marked dict below), so a row is self-contained. No text payload is parsed anywhere. The dump files are Arrow IPC with zstd buffer compression by default (D5).

2.1 code_mir: one row per body

Identity = (owner, sub).

Site kinds (st_kind): 0 assign, 1 set discriminant, 2 assume, 3 copy_nonoverlapping, 4 storage live, 5 storage dead, 6 fake read, 7 retag, 8 place mention, 9 type ascription, 10 coverage, 11 const eval counter, 12 nop, 13 backward incompatible drop hint; terminators: 32 goto, 33 switch, 34 return, 35 unreachable, 36 drop, 37 call, 38 tail call, 39 assert, 40 yield, 41 coroutine drop, 42 false edge, 43 false unwind, 44 inline asm, 45 unwind resume, 46 unwind terminate.

What was lossy and is now a value:

2.2 The derived view (mimir_schema::mir::legacy)

For a row r with legacy not null, and its blocks b with blk_flags[b] bit 0 = 0 (no cleanup block), in order:

text(site)      = the schema-7 spelling, from st_kind, st_word, the operand, place and constant pools
                  (a constant prints as k:<short(k_ty)>, a call as call <st_callee>⟨args⟩->dest)
canon(b)        = join over the sites of b with kind in {0,1,2,3, 32..46}:
                    canonical_locals(text(site)) + "\n"
                  then for each local in order of first use: short(local_ty) + ";"
fp(b)           = fnv64(canon(b));  for a call with st_callee:  fnv64(hex16(fp) + st_callee)
succ(b)         = targets of b's terminator whose block is not a cleanup block, roles {0,1,2,7}, in order, deduplicated
mir_body.ty     = "1" ␞ join(␟, legacy + b "=" hex16(fp(b)) ":" term_word ">" join("+", succ(b)))
mir_block.ty    = hex16(fp) ␞ text(term)+pos ␞ first 128 text(stmt)+pos ␞ touched locals with short types ␞ def-use pairs
CFG_SUCC        = (b, s) for s in succ(b)

short is shorten_paths of today, moved into mimir-schema. The gate (§7) proves the function: on the pinned Holger and Gunnar commits the derived mir_body and mir_block bytes are compared with a schema-7 dump of the same commit, row for row.

2.3 code_instances: one row per instance of a program

Identity = inst. Written by the instance pass of a program (§3.2).

2.4 code_data: one row per static or constant allocation

id (the static's moniker, or alloc:<hash> for an allocation a constant points at), ty, size, bytes (binary; at most 64 KiB, truncated says when), mutable, link_section (.init_array makes a constructor), ptr_off / ptr_to (every pointer in the bytes: the offset and the target, an instance key or another id).

3. The instance-resolution rule

3.1 Keys

A key is our own print of a def, a type or an instance, the same in every compiler session (mimir-driver/src/walk/keys.rs). rustc's own print is not used: it prints the paths visible from the crate that looks, and closure positions.

def key       <package>[<target>]@<version>::<def path with disambiguators>      std::fs::File   app[bin=app]@0.1.0::main
type key      primitives by name; an ADT = def key + ⟨args⟩; &T, &mut T, *const T, [T; n], (A,B);
              a generic parameter of the body = #<index>; regions are not printed;
              dyn = its principal + projections + auto traits (sorted); a closure = its def key + the
              arguments of the fn it sits in
instance key  def key + ⟨args⟩;  a compiler shim: {<kind>} + def key + ⟨args⟩

A toolchain crate has no version in its key. code_mir::stable_key gives the version-free form of any key (D6). Before a term of a body is printed, its types are normalised in the post-analysis typing environment of the body, so an opaque type (impl Trait, an async fn's future) prints as its hidden type in both passes.

3.2 The rule

For a body D with generic parameters P, and a term t = (callee, G) in it, where G are the callee's generic arguments written over P:

resolve(D, A, t) = Instance::try_resolve(tcx, fully_monomorphized, callee, G[P := A])

A are the concrete arguments of the instance of D. This is the call rustc's mono collector makes. The results:

• Item(def) → instance (def, args): row kind 0. A foreign item whose symbol a Rust fn of the program defines (the allocator, the panic runtime, a #[no_mangle] fn of another crate) resolves to that fn;
• Virtual(trait method, slot) → kind 1: the receiver is dyn Trait;
• Intrinsic → kind 2; any other foreign item → kind 3 (the boundary);
• a shim (DropGlue, FnPtr, ClosureOnce, Reify, VTable, Clone, ThreadLocal, the async drop shims …) → an instance whose body is the MIR rustc builds for it (tcx.instance_mir), written as a code_mir row of kind shim;
• a drop of a type T → Instance::resolve_drop_in_place(T[P := A]), kind 5 when T needs no drop, kind 1 slot 0 when T is dyn Trait;
• an assert → the panic lang item of its message.

Where it runs: in the instance pass, cargo mimir-dump --exec. It is the same cargo check of the same workspace once more, with -Zbuild-std and with the driver setting -Z always-encode-mir, -Z inline-mir=no and -Z mir-opt-level=0, so the metadata of EVERY crate, the toolchain's included, carries the MIR of every body, not inlined. Every unit compiles; only a program's own unit (a bin target) does work. From lang_start and main (and the constructors) it walks rustc's MIR of each instance it reaches, in every crate, and writes one code_instances row per instance with the resolution of each term. A term of the walked body is joined to the code_mir row of the first pass by (k_def, k_args): the resolution is a function of the term and the instance, not of the site. The source position (res_line, res_col) is the second key.

Why a second pass and not every unit for itself: a unit's own session sees the toolchain's generic bodies only as optimised, inlined MIR (the prebuilt sysroot), whose terms no longer match the bodies of the std dump; and it sees no body at all for a non-generic fn of another crate. The instance pass sees every body in one form. Its cost is one more check of the workspace (measured in the report).

A term of a reached instance that no row answers is listed (unmatched) and widened as schema 7 widened it, so the result stays a true upper bound.

3.3 The widened sites, and how narrow

Only two site kinds stay widened:

• virtual call on dyn Trait method m: the targets are { vt_methods[m] : vtables of Trait built by a REACHED instance }.
• fn pointer call with signature key s: the targets are { fp_inst : fp_sig = s, made by a REACHED instance } ∪ { pointers in reached code_data with that signature }.

"Reached" is part of the fixed point of §4: a vtable built by code the program never runs gives no target. Schema 7 took every impl in the room.

4. The executor (mimir-exec)

A new stable-Rust crate in nornir, no rayon, no petgraph. It reads the three tables for a program's units (from a dump directory, or from the lake through the same reader the room uses) and the SYSCALLS map.

4.1 State

I                  the reached instances
B ⊆ I × block      the boundary sites: a call whose resolution is a foreign item, an inline asm with a
                   syscall instruction, or the raw door
V(i, local)        a value: ⊥ (no value yet) | a set of at most 8 integers | ⊤ (any value)

Values form a lattice with join = set union, and a set that grows past 8 becomes ⊤. Unknown inputs (arguments of an entry, memory, results of the boundary) are ⊤.

4.2 Transfer

Per instance, a forward dataflow over its blocks (all blocks, cleanup included), to a fixed point:

assign  x = const c                V[x] = {c}
assign  x = copy/move y            V[x] = V[y]                  (whole locals; a projected place reads ⊤)
assign  x = op(a, b)               V[x] = { op(u, v) : u ∈ V[a], v ∈ V[b] }   (⊤ if either is ⊤)
assign  x = cast(a)                V[x] = { cast(u) : u ∈ V[a] }              (integer casts)
switch(x; v1→b1 … else→bo)         if V[x] is a set S: take { bi : vi ∈ S } and bo if S ⊄ {v1…}; if ⊤: take all
call f(a1…an) → x, then bt         args of every target instance j:  V(j, param k) ⊔= V[ak];   V[x] = Ret(j)
return                             Ret(i) ⊔= V[_0]
drop(p), state live / maybe        a call of drop_inst (maybe: the skip edge is taken too); state dead: a goto
yield                              poll returns here (Pending); the resume target is an entry of the next poll
unwind edges                       a call or drop with a cleanup target can go there when the callee can unwind
                                   (CanUnwind(j): j reaches `resume`, a panic entry, or a boundary site not known to return)

The interprocedural fixed point is over (I, V, Ret, the vtable and fn pointer sets of §3.3): monotone, all sets finite, so it ends.

4.3 The order relation

For each instance i and each program point, L ⊆ B ∪ {ε} is the set of boundary sites that can be the LAST system call made since i was entered (ε = none yet). Per instance the executor keeps

First(i) ⊆ B      the sites that can be the first system call of a call to i
Last(i)  ⊆ B      the sites that can be the last one before i returns
Eps(i)   ∈ {0,1}  i can return without any system call
Next     ⊆ B × B  "after s the next system call can be s'"

and the transfer is (boolean semiring: sets under ∪, a pair is present or not):

entry of i                L = {ε}
boundary site s           for x ∈ L:  x = ε ? First(i) ∋ s : Next ∋ (x, s);          L' = {s}
call of instance j        for x ∈ L:  x = ε ? First(i) ⊇ First(j) : Next ⊇ {x} × First(j)
                          L' = Last(j) ∪ (Eps(j) ? L : ∅)
merge of two paths        L = L1 ∪ L2
return of i               Last(i) ⊇ L \ {ε};   Eps(i) ∨= (ε ∈ L)

Calls and returns match (a callee returns to its own call site, not to every caller), so Next holds no pair that only a mismatched return could make. The fixed point is the least one. The order graph of an entry e is Next cut to the sites reachable from e, with First(e) as its start nodes.

4.4 Argument facts

At a boundary site of a C function f, the value sets of its arguments are written when they are not ⊤, for the arguments Heimdall's probe records (heimdall-probe/src/facts.rs): socket / socketpair 0, 1, 2; open 1; openat 2; ioctl 1; mmap, mprotect, pkey_mprotect 2; clone 0; prctl 0; fcntl 1. A fact is a set of values, or "any".

4.5 Entries, marks and phases

• Process entry: main through std::rt::lang_start (a row of the std dump; no special case in the walk). The C runtime's start-up before it is the map's startup list, as today, a fixed prefix node.
• The allocator: __rust_alloc and its siblings are foreign items the compiler joins to the global allocator. The executor joins them by rule: to the #[global_allocator] static's GlobalAlloc methods when a unit of the program has one (the driver marks it in code_data), else to __rdl_alloc (std's System), a row of the std dump.
• Thread and task entries: a small DATA table of spawn functions (path → which generic argument is the body): std::thread::spawn, Builder::spawn, spawn_scoped, tokio::spawn, task::spawn, spawn_blocking, spawn_local, Runtime::spawn. An instance of one of them is a mark: the body argument's call_once / poll instance is a new entry. A fn pointer passed to a foreign function is an entry too (pthread_create, sigaction: a signal handler, atexit). Constructors (.init_array) are entries that run before main.
• Phases are marks on the entry's own body, from its shape: the sites before the first loop that holds an accepting call (accept, accept4, epoll_wait, io_uring_enter, poll, select, recvfrom on the boundary), the loop, and the sites after it. When the entry has no such loop, or more than one at the top level, the output says shape unclear and gives no phase. A phase is never guessed.

4.6 Output (Arrow)

exec.nodes: entry, node (the id of §8), instance, block, file, line, callee (link name), syscalls (list; from the map, with the map's sure flag), arg_idx / arg_values (lists), phase, unwind (the site is on a cleanup path). exec.edges: entry, from, to. exec.marks: entries with their kind and spawn site, unmatched terms, widened sites with their target counts, shape unclear notes.

The possible SET is the projection { syscalls(s) : s ∈ B reached }, written in the mimir.possible-syscalls/1 shape. Two checks are tests: SET ⊆ possible_syscalls of today (the widened walk) and SET ⊇ every measured probe set.

5. Worked example: A { B C D }* F

#[tokio::main(flavor = "current_thread")]
async fn main() {
    let f = std::fs::File::open("/etc/hostname").unwrap();   // A: openat
    for _ in 0..n() {
        b();                                                 // B: getpid
        tokio::join!(c(), d());                              // C: getuid, D: getgid (two futures, one thread)
    }
    drop(f);                                                 // F: close
}

code_mir holds main's coroutine body once. The call File::open is a generic term (P: AsRef<Path>); the unit resolves it for &str, and from there the std dump's rows lead to the foreign item open64: boundary site A, map open64 → openat, argument fact flags ∈ {O_RDONLY|O_CLOEXEC}. b calls libc::getpid: site B. join! polls c and d in one loop inside one poll; each can be pending, so inside the join L moves between C and D in both orders. drop(f) is a drop with state live; its glue (drop_in_place::<File> → OwnedFd::drop) reaches close: site F.

First(main) = {A}
Next = { A→B, A→F, B→C, B→D, C→D, D→C, C→B, D→B, C→F, D→F, B→F }
Last(main) = {F}                      (the unwind paths add their own sites, marked unwind)

A real run prints A (B C D | B D C)* F. Every pair of neighbours in it is in Next; F→x is in Next for no x, and no pair ends in A. The test compares exactly this: observed pairs ⊆ Next, observed set = projected set for the sites the program owns, and the two impossible pairs are absent.

2.5 The stores (D5)

Built: crates/mimir-store (ipc, znippy) and the unpublished crates/mimir-store-graphar (graphar, Parquet chunks by default). Layout per store, what is published and the bytes on disk are in exec-graph.md §5.6 and §8.2.

6. Size

Today (schema 7): the nordisk room holds 14.6 M mir_block events and 2 GB of block text for the own crates only; the dependencies carry fingerprints.

Estimate per site in code_mir, uncompressed: 1 + 2 + 4 + 2 + 8 + 4 + 4 + 11 bytes of site columns ≈ 36, plus on average 1.6 operands (5 bytes), 1.3 places (8 bytes) and 0.6 projections (9 bytes) ≈ 24: about 60 bytes per site, and about 4 sites per block with the marker statements. zstd on these columns gives a factor 5 to 8 (small integers, long runs).

bytes ≈ blocks × 4 sites × 60 B ÷ 6
own crates:      14.6 M × 1.5 (cleanup blocks) × 240 B ÷ 6 ≈ 0.9 GB    (today 2 GB of text)
dependencies:    about 5 × the own blocks                  ≈ 4.5 GB
instances + data: about 30 % of the above                  ≈ 1.6 GB
whole universe:  ≈ 7 GB, budget 20 GB (hard limit)

This is an estimate. The measured numbers replace it: every unit's stats.json gets mir_bytes, inst_bytes, data_bytes, rows and sites; the report gives bytes on disk per program and for the whole universe, the dump time against schema 7, and the executor's time and peak memory. If the universe passes 20 GB, the first cuts are the marker statements of dependencies and the type dictionaries, and the report says what was cut.

7. Gates

• Lens goldens: Holger 32/32, Gunnar 23/23, the fixtures and the lib tests of crates/mimir-lens. Byte-identical. If the lossless graph makes a row more correct, the row, the reason and the new value are listed and the golden is pinned again in the same commit. Nothing changes silently.
• The derived view is compared with a schema-7 dump of the same commit, row for row (mir_body.ty, every mir_block.ty, every CFG_SUCC pair).
• Lens speed and memory: lens all on the two pinned dumps, cold and warm, against the schema-7 baseline measured on the same host.
• The possible.rs tests, and clippy with -D warnings.
• Fixtures with a known system-call order, each executed on the graph and compared with a real run recorded in the test (a small ptrace recorder in the test code; the product has no strace dependency): A { B C D }* F with two futures on one tokio thread, a generic + dyn case, a Drop that closes a file, a panic / unwind path, a thread spawn. A RED commit comes before each GREEN one.
• Real programs: Heimdall's heimdall, Holger's scan worker, Gunnar's server, and Iggy 0.9 if it dumps.

8. Node ids (for a run-time recorder)

A boundary node is (<instance key>, block). The symbol column of code_instances gives the instance's v0 symbol, and each node carries the callee's link name and the call's file:line. The exact form a recorder must emit (thread id + next-call pairs) is fixed when the fixtures are green and is added here. Heimdall is not changed by this plan.

9. What is NOT covered

• C, libc and assembly control flow: the map only (D4). A C function the map does not know is listed and can make any call.
• Code loaded at run time (dlopen), and a system call whose number is computed at run time (the raw door with a non-constant number): listed.
• Values in memory: the value sets are per local. A flag that travels through a struct field or the heap is "any".
• Time: the order graph says which call can follow which on ONE entry. It does not order two threads against each other.
• Layout-dependent constants of generic code (size_of::<T>()) are values per instance only where rustc can evaluate them.
• Proc macros and build scripts are programs of the build, not of the product: they are not dumped (as today).
• Unwinding out of foreign code, and longjmp.

10. Order of work

1. This plan.
2. mimir-schema: the three tables, mir::legacy, schema 8. Driver: the lossless writer, the derived mir_body. Lens loader and room: the derived blocks. Gate: the row-for-row comparison and the goldens.
3. Driver: constants, drop state, keys; the instance pass (--exec): the collector, vtables, fn pointers, code_data. nornir-mimir-store: the three stores.
4. mimir-exec: values, the order relation, entries and marks, the output; the fixtures with the recorder.
5. Lake: code_mir, code_instances, code_data as event tables; mimir-room <lake> exec.
6. Real programs, the sizes and times, the node-id form for Heimdall.