From 60e07feef401d9044db3a1c925cb9d1f6d20dac9 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Wed, 11 Nov 2026 23:46:02 -0300 Subject: canim: relations as one data-oriented subsystem; aim; the ASan pair; the introduction's chapters From the user. Relations between panes are one subsystem: per-frame tables of places and values in struct-of-arrays, owned by the frame; the kinds one table of data; a resolver of pure passes (join, filter, priority, cut) unit-tested on hand-written tables. Ported kinds draw byte-identical frames; a synthetic map of 4000 places and 6000 values resolves in 0.56 ms against the old table's 5.7. aim, a word holding a code address tied to its row, is the first new kind, off unless a scene turns it on. The ASan pair: one overflow built plain and with ASan, recorded by instruction; the frame as bytes eight a row; the plain run goes on alone in the column, its return address aimed at main's row until the letters reach it; the fault at ret. The introduction's three chapters are built and tested, not yet exported. Annotations, rows and scrolls that changed in one frame now fade; captions stand twelve seconds at most. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa --- anim/src/relations.zig | 341 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 341 insertions(+) create mode 100644 anim/src/relations.zig (limited to 'anim/src/relations.zig') diff --git a/anim/src/relations.zig b/anim/src/relations.zig new file mode 100644 index 0000000..03165d5 --- /dev/null +++ b/anim/src/relations.zig @@ -0,0 +1,341 @@ +//! The relations' data (design/README.md, "4. Ties"), one table set a +//! frame, and the passes over it. The panels say, as they draw, where each +//! of their things is (`places`: a key, the kind of thing and its address +//! packed in one integer, a box, a pane) and which values they show that +//! could be addresses (`values`: the value, its box, its pane, a reference +//! such as a register's index). A relation is a join of the two on +//! address, or a step's own fact (a touch, a carry, the thread), and the +//! resolver (`ties.zig`) runs it as a pipeline of passes over slices: +//! candidates, `filter` by the knobs, `order` by priority, `cut` to the +//! budget, route, draw. `filter`, `order`, `cut` and `join` are pure, and +//! tested here with tables written by hand. +//! +//! Memory: the tables live in the frame's scratch arena (`sk.Frame.user`), +//! made at the frame's first place and gone with it: no process globals, +//! no allocation per relation, indices rather than pointers. +const std = @import("std"); + +/// The pane a place or a value is drawn in. +pub const Pane = enum(u8) { other, source, disasm, registers, stack, view, drawing, loupe }; + +/// A key: the kind of thing in its top byte, an address (or an index) in the rest. +pub const Key = u64; +pub const kind_shift = 56; +pub const address_mask: u64 = (1 << kind_shift) - 1; + +pub fn keyOf(kind: u8, address: u64) Key { + return @as(u64, kind) << kind_shift | (address & address_mask); +} + +pub fn kindOf(key: Key) u8 { + return @intCast(key >> kind_shift); +} + +pub const Place = struct { key: Key, box: [4]f32, pane: Pane }; +/// `at`: the address of the word that holds it (0: a register's); `ref`: a +/// register's index; `rules`: its panel's left and right rules. +pub const Value = struct { value: u64, box: [4]f32, pane: Pane, ref: u32 = 0, at: u64 = 0, rules: [2]f32 = .{ 0, 0 } }; + +/// One layer's tables: the working frame's, or the map's. +pub const Tables = struct { + places: std.MultiArrayList(Place) = .{}, + values: std.MultiArrayList(Value) = .{}, + /// `places` by key (then by the order they were said), and `values` by + /// value: built once, on the first lookup after a change. + places_by_key: std.ArrayList(u32) = .empty, + values_by_value: std.ArrayList(u32) = .empty, + places_sorted: bool = true, + values_sorted: bool = true, + /// Nanoseconds this frame spent sorting. + sort_ns: u64 = 0, + + pub fn add(t: *Tables, gpa: std.mem.Allocator, place: Place) void { + t.places.append(gpa, place) catch return; + t.places_sorted = false; + } + + pub fn show(t: *Tables, gpa: std.mem.Allocator, value: Value) void { + t.values.append(gpa, value) catch return; + t.values_sorted = false; + } + + /// The index of places by key: sorted once after a change. + pub fn byKey(t: *Tables, gpa: std.mem.Allocator) []const u32 { + if (!t.places_sorted) { + const start = clock(); + sortIndex(gpa, &t.places_by_key, t.places.items(.key)); + t.places_sorted = true; + t.sort_ns += clock() - start; + } + return t.places_by_key.items; + } + + pub fn byValue(t: *Tables, gpa: std.mem.Allocator) []const u32 { + if (!t.values_sorted) { + const start = clock(); + sortIndex(gpa, &t.values_by_value, t.values.items(.value)); + t.values_sorted = true; + t.sort_ns += clock() - start; + } + return t.values_by_value.items; + } + + /// The box of the first place said with `key`: a binary search. + pub fn find(t: *Tables, gpa: std.mem.Allocator, key: Key) ?[4]f32 { + const order = t.byKey(gpa); + const keys = t.places.items(.key); + const i = lowerBound(order, keys, key); + if (i == order.len or keys[order[i]] != key) return null; + return t.places.items(.box)[order[i]]; + } + + /// The indices (into `places`) of the keys in `[lo, hi)`, in key order. + pub fn range(t: *Tables, gpa: std.mem.Allocator, lo: Key, hi: Key) []const u32 { + const order = t.byKey(gpa); + const keys = t.places.items(.key); + return order[lowerBound(order, keys, lo)..lowerBound(order, keys, hi)]; + } + + /// The greatest key of kind `kind` at or below `address`, within `within` of it. + pub fn atOrBelow(t: *Tables, gpa: std.mem.Allocator, kind: u8, address: u64, within: u64) ?u64 { + const order = t.byKey(gpa); + const keys = t.places.items(.key); + const i = lowerBound(order, keys, keyOf(kind, address) + 1); + if (i == 0) return null; + const k = keys[order[i - 1]]; + if (kindOf(k) != kind) return null; + const a = k & address_mask; + return if (address - a < within) a else null; + } +}; + +/// `index` made the permutation of `keys` that sorts them, ties in their order. +fn sortIndex(gpa: std.mem.Allocator, index: *std.ArrayList(u32), keys: []const u64) void { + index.resize(gpa, keys.len) catch return; + for (index.items, 0..) |*v, i| v.* = @intCast(i); + std.sort.pdq(u32, index.items, keys, struct { + fn less(k: []const u64, a: u32, b: u32) bool { + return k[a] < k[b] or (k[a] == k[b] and a < b); + } + }.less); +} + +/// The first position in `order` whose key is not below `key`. +fn lowerBound(order: []const u32, keys: []const u64, key: u64) usize { + var lo: usize = 0; + var hi: usize = order.len; + while (lo < hi) { + const mid = (lo + hi) / 2; + if (keys[order[mid]] < key) lo = mid + 1 else hi = mid; + } + return lo; +} + +/// A value shown and the place of kind `kind` at its address (masked by +/// `mask`: a view's row is its first byte's): indices into the tables. +pub const Pair = struct { value: u32, place: u32 }; + +/// The join of `values` (by value, `by_value` their order) with the +/// places of kind `kind` (by key, `by_key` their order) on address: a merge +/// of the two sorted sides, each value with the first place said at its +/// address. Appends to `out`; a value that is no place's address has none. +pub fn join(values: []const u64, by_value: []const u32, keys: []const Key, by_key: []const u32, kind: u8, mask: u64, out: *std.ArrayList(Pair), gpa: std.mem.Allocator) void { + // The places of the kind: one run of the key order. + const lo = lowerBound(by_key, keys, keyOf(kind, 0)); + const hi = lowerBound(by_key, keys, keyOf(kind + 1, 0)); + const run = by_key[lo..hi]; + // Masking keeps the values' order (a mask clears low bits): one walk. + var p: usize = 0; + for (by_value) |v| { + const want = values[v] & mask & address_mask; + while (p < run.len and keys[run[p]] & address_mask < want) p += 1; + if (p == run.len) break; + if (keys[run[p]] & address_mask == want) out.append(gpa, .{ .value = v, .place = run[p] }) catch return; + } +} + +// ---- The resolver's pure passes. + +/// The kinds of relation, in the order they are drawn. +pub const Kind = enum(u8) { thread, beat, link, projection, touch, carry, code }; + +/// What turns a kind on. `always`: whenever the step has one (the scene's +/// beat, its own facts); the rest only where the author has turned it on +/// (or, for the thread and links, has not turned it off). +pub const Knob = enum(u8) { thread, links, carry, code, always }; + +/// A budget's class: how many of it a frame draws at most. +pub const Class = enum(u8) { standing, beat, step, carry, code }; + +/// A kind's row of data: its knob, its class, its priority (lower first) +/// and how many of it a frame draws at most. +pub const Spec = struct { knob: Knob, class: Class, priority: u8, most: u8 }; + +pub const specs = std.enums.EnumArray(Kind, Spec).init(.{ + .thread = .{ .knob = .thread, .class = .standing, .priority = 0, .most = 1 }, + .beat = .{ .knob = .always, .class = .beat, .priority = 1, .most = 1 }, + .link = .{ .knob = .links, .class = .step, .priority = 2, .most = 1 }, + .projection = .{ .knob = .always, .class = .step, .priority = 3, .most = 1 }, + // The first to give way: three lines at most, so not with a link and a projection. + .touch = .{ .knob = .always, .class = .step, .priority = 4, .most = 1 }, + .carry = .{ .knob = .carry, .class = .carry, .priority = 5, .most = 1 }, + // One at a time: a standing row across panes, or the step's. + .code = .{ .knob = .code, .class = .code, .priority = 6, .most = 1 }, +}); + +/// How many of a class a frame draws at most. +pub const budget = std.enums.EnumArray(Class, u8).init(.{ .standing = 1, .beat = 1, .step = 2, .carry = 1, .code = 1 }); + +/// The knobs as the scene has them this frame. +pub const Knobs = std.enums.EnumSet(Knob); + +/// A relation that could be drawn: its kind, its rank within its kind (a +/// register's place in pwndbg's order, a span's in the step), and the +/// indices of what it ties (`from`, `to`: into a table, or a kind's own). +pub const Candidate = struct { kind: Kind, rank: u32 = 0, from: u32 = 0, to: u32 = 0 }; + +/// Those whose kind's knob is on, in place. +pub fn filter(cands: []Candidate, knobs: Knobs) []Candidate { + var n: usize = 0; + for (cands) |c| if (knobs.contains(specs.get(c.kind).knob)) { + cands[n] = c; + n += 1; + }; + return cands[0..n]; +} + +/// By priority, then rank, then as they came (`from`, each its own). +pub fn byPriority(cands: []Candidate) void { + std.sort.pdq(Candidate, cands, {}, struct { + fn less(_: void, a: Candidate, b: Candidate) bool { + const pa = specs.get(a.kind).priority; + const pb = specs.get(b.kind).priority; + if (pa != pb) return pa < pb; + if (a.rank != b.rank) return a.rank < b.rank; + return a.from < b.from; + } + }.less); +} + +/// The first of each kind up to its most, and of each class up to its +/// budget, in place: what is cut is the least urgent. +pub fn cut(cands: []Candidate) []Candidate { + var per_kind = std.enums.EnumArray(Kind, u8).initFill(0); + var per_class = std.enums.EnumArray(Class, u8).initFill(0); + var n: usize = 0; + for (cands) |c| { + const spec = specs.get(c.kind); + if (per_kind.get(c.kind) >= spec.most or per_class.get(spec.class) >= budget.get(spec.class)) continue; + per_kind.set(c.kind, per_kind.get(c.kind) + 1); + per_class.set(spec.class, per_class.get(spec.class) + 1); + cands[n] = c; + n += 1; + } + return cands[0..n]; +} + +/// Counts and nanoseconds of a frame's relations (`CANIM_RELATIONS=1`: a line a frame on stderr). +pub const Stats = struct { + places: usize = 0, + values: usize = 0, + candidates: usize = 0, + kept: usize = 0, + drawn: usize = 0, + map_places: usize = 0, + map_values: usize = 0, + map_pairs: usize = 0, + ns: struct { sort: u64 = 0, candidates: u64 = 0, passes: u64 = 0, draw: u64 = 0, map: u64 = 0 } = .{}, +}; + +/// Whether to say each frame's counts and times on stderr (`CANIM_RELATIONS=1`), read once. +pub fn reporting() bool { + if (report_on == null) report_on = if (comptime @import("builtin").link_libc) std.c.getenv("CANIM_RELATIONS") != null else false; + return report_on.?; +} +var report_on: ?bool = null; + +pub fn clock() u64 { + var ts: std.os.linux.timespec = undefined; + _ = std.os.linux.clock_gettime(.MONOTONIC, &ts); + return @as(u64, @intCast(ts.sec)) * std.time.ns_per_s + @as(u64, @intCast(ts.nsec)); +} + +// ---- Tests: hand-written tables in, tables out. + +test "a lookup is the first place said with its key, by binary search" { + const gpa = std.testing.allocator; + var t: Tables = .{}; + defer { + t.places.deinit(gpa); + t.places_by_key.deinit(gpa); + } + t.add(gpa, .{ .key = keyOf(3, 0x30), .box = .{ 1, 0, 0, 0 }, .pane = .stack }); + t.add(gpa, .{ .key = keyOf(1, 0x10), .box = .{ 2, 0, 0, 0 }, .pane = .registers }); + t.add(gpa, .{ .key = keyOf(3, 0x30), .box = .{ 3, 0, 0, 0 }, .pane = .stack }); + try std.testing.expectEqual(@as(f32, 1), t.find(gpa, keyOf(3, 0x30)).?[0]); + try std.testing.expectEqual(@as(f32, 2), t.find(gpa, keyOf(1, 0x10)).?[0]); + try std.testing.expect(t.find(gpa, keyOf(3, 0x38)) == null); + // Said after a lookup: the order is made again. + t.add(gpa, .{ .key = keyOf(2, 0x20), .box = .{ 4, 0, 0, 0 }, .pane = .view }); + try std.testing.expectEqual(@as(f32, 4), t.find(gpa, keyOf(2, 0x20)).?[0]); + // A range of one kind, and the nearest at or below an address. + t.add(gpa, .{ .key = keyOf(3, 0x50), .box = .{ 5, 0, 0, 0 }, .pane = .stack }); + try std.testing.expectEqual(@as(usize, 3), t.range(gpa, keyOf(3, 0), keyOf(4, 0)).len); + try std.testing.expectEqual(@as(?u64, 0x30), t.atOrBelow(gpa, 3, 0x48, 64)); + try std.testing.expectEqual(@as(?u64, null), t.atOrBelow(gpa, 3, 0x48, 8)); + try std.testing.expectEqual(@as(?u64, null), t.atOrBelow(gpa, 3, 0x10, 64)); +} + +test "a join pairs each value with the first place at its address, of one kind" { + const gpa = std.testing.allocator; + // Places: rows (kind 14) at 401000, 401004 (twice), 401010; a word (kind 3) at 401004. + const keys = [_]Key{ keyOf(14, 0x401004), keyOf(3, 0x401004), keyOf(14, 0x401000), keyOf(14, 0x401010), keyOf(14, 0x401004) }; + var by_key: std.ArrayList(u32) = .empty; + defer by_key.deinit(gpa); + sortIndex(gpa, &by_key, &keys); + // Values: 401004 (twice), 7fff0000, 401010, 401008. + const values = [_]u64{ 0x401004, 0x7fff0000, 0x401010, 0x401004, 0x401008 }; + var by_value: std.ArrayList(u32) = .empty; + defer by_value.deinit(gpa); + sortIndex(gpa, &by_value, &values); + var out: std.ArrayList(Pair) = .empty; + defer out.deinit(gpa); + join(&values, by_value.items, &keys, by_key.items, 14, ~@as(u64, 0), &out, gpa); + try std.testing.expectEqualSlices(Pair, &.{ .{ .value = 0, .place = 0 }, .{ .value = 3, .place = 0 }, .{ .value = 2, .place = 3 } }, out.items); + // Masked: a view's row is its first byte's (sixteen-aligned). + out.clearRetainingCapacity(); + join(&values, by_value.items, &keys, by_key.items, 14, ~@as(u64, 15), &out, gpa); + try std.testing.expectEqualSlices(Pair, &.{ .{ .value = 0, .place = 2 }, .{ .value = 3, .place = 2 }, .{ .value = 4, .place = 2 }, .{ .value = 2, .place = 3 } }, out.items); +} + +test "the passes: off unless its knob is on, by priority, cut to the budget" { + var cands = [_]Candidate{ + .{ .kind = .touch }, + .{ .kind = .code, .rank = 2 }, + .{ .kind = .link, .rank = 5 }, + .{ .kind = .projection }, + .{ .kind = .link, .rank = 1 }, + .{ .kind = .thread }, + .{ .kind = .code, .rank = 0 }, + }; + // The code kind is off by default: it goes; the rest are on. + var knobs = Knobs.initMany(&.{ .thread, .links, .always }); + var kept = filter(&cands, knobs); + try std.testing.expectEqual(@as(usize, 5), kept.len); + byPriority(kept); + try std.testing.expectEqual(Kind.thread, kept[0].kind); + try std.testing.expectEqual(@as(u32, 1), kept[1].rank); + kept = cut(kept); + // One thread, one link (the first in the registers' order), one projection; the touch gives way. + try std.testing.expectEqual(@as(usize, 3), kept.len); + try std.testing.expectEqualSlices(Kind, &.{ .thread, .link, .projection }, &.{ kept[0].kind, kept[1].kind, kept[2].kind }); + try std.testing.expectEqual(@as(u32, 1), kept[1].rank); + // With no projection the touch is drawn; with the knob on, one code pointer, the first in rank. + var more = [_]Candidate{ .{ .kind = .touch }, .{ .kind = .link }, .{ .kind = .code, .rank = 3 }, .{ .kind = .code, .rank = 1 } }; + knobs.insert(.code); + kept = filter(&more, knobs); + byPriority(kept); + kept = cut(kept); + try std.testing.expectEqualSlices(Kind, &.{ .link, .touch, .code }, &.{ kept[0].kind, kept[1].kind, kept[2].kind }); + try std.testing.expectEqual(@as(u32, 1), kept[2].rank); +} -- cgit v1.3