summaryrefslogtreecommitdiff
path: root/anim/scenes/heap.zig
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-11 00:06:30 -0300
committerGabriel Schneider <[email protected]>2026-11-11 01:16:48 -0300
commitc3d9f7ba5effd615374b1359ad98ecf801559f83 (patch)
tree07f85932abc1df23c722bcd1bd1b3b65bca28f2e /anim/scenes/heap.zig
parentc94ade9e77a811d3ff75ffc2889a65375262ab1f (diff)
downloadcomputeranim-c3d9f7ba5effd615374b1359ad98ecf801559f83.tar.gz
computeranim-c3d9f7ba5effd615374b1359ad98ecf801559f83.zip
canim: a call followed down to the kernel; rows that say what they do; the heap from the inside
From the user. The disassembly can descend: the syscalls scene is glibc's hello by instruction, and open is followed from main through its PLT stub, whose jmp reads the GOT, into libc's wrapper to the syscall row, which crosses to the kernel's window under it, and back up. The band keeps the calls so far as strace writes them. Operands lose their size words and show a width as byte cells only where nothing else says it. A compare shows its values and the flags it leaves, a jump the flags it reads, lea its result, an indirect jump its target and the slot it read, a call that has run its C form. The backtrace has its newest frame at the bottom. A new scene shows glibc 2.44's heap from blocks that exist: chunks read by fields (a size with its bits, a protected pointer), the free list as arcs, the tcache in a loupe, the program's list over malloc's own. Co-Authored-By: Claude Fable 5.2 <[email protected]> Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa
Diffstat (limited to 'anim/scenes/heap.zig')
-rw-r--r--anim/scenes/heap.zig323
1 files changed, 323 insertions, 0 deletions
diff --git a/anim/scenes/heap.zig b/anim/scenes/heap.zig
new file mode 100644
index 0000000..e227f17
--- /dev/null
+++ b/anim/scenes/heap.zig
@@ -0,0 +1,323 @@
+//! libc's heap from the inside (design/motion.md, "A scene: libc's heap
+//! from the inside"; mock 18): `tools/heap.c` (three pushes, two pops, a
+//! push) under glibc 2.44, a line a stop with malloc and free run through.
+//! Not a lens: the blocks the catalogue has, composed. The band's drawing
+//! is `nodes` in two rows (the program's list from `head` over the
+//! tcache's free list for chunks of 0x20, headed by its `bin`); its view
+//! the heap by fields, each size word read as `size`, a node's words as the
+//! program's while it has them and as malloc's (`protected`, `key`) while
+//! malloc does, both lists as `arc`s; the tcache a loupe hung from the row
+//! of the chunk it lives in. Every byte from the recording at the stop
+//! shown (`ztrace.heap.glibc`).
+const std = @import("std");
+const sk = @import("sketch");
+const anim = @import("anim");
+const canim = @import("canim");
+const recordings = @import("recordings");
+const ui = canim.ui;
+const theme = canim.theme;
+const zt = canim.ztrace;
+const t = theme.color.text;
+const cm = theme.metric.context;
+
+pub const background = canim.background;
+pub const scene = anim.Live(frame, struct {});
+
+/// The heap's first bytes, the view's seven rows: three chunks of two rows
+/// each and the next chunk's header.
+const view_base = 0x405000;
+const view_len = 0x70;
+
+/// The heap at a moment, from the recording; null before there is one.
+fn heapAt(a: std.mem.Allocator, rec: *canim.Recording, i: u64) ?zt.heap.Heap {
+ return zt.heap.glibc(a, rec.moment(i), rec.tid) catch null;
+}
+
+/// The chunks of the free list for 0x20, as the tcache holds them, user addresses.
+fn freeList(h: zt.heap.Heap) []const zt.heap.Entry {
+ const tc = h.tcache orelse return &.{};
+ for (tc.bins) |bin| if (bin.in.size() == 0x20) return bin.entries;
+ return &.{};
+}
+
+/// How many chunks the bin for 0x20 holds (2.44 stores the slots left).
+fn holds(h: zt.heap.Heap) ?u16 {
+ const tc = h.tcache orelse return null;
+ for (tc.bins) |bin| if (bin.in.size() == 0x20) {
+ const count = bin.count orelse return @intCast(bin.entries.len);
+ return if (tc.capacity) |cap| cap - count else count;
+ };
+ return 0;
+}
+
+/// The program's list from `head`: its nodes' addresses, in list order.
+fn programList(a: std.mem.Allocator, rec: *canim.Recording, i: u64, head_at: u64) []const u64 {
+ var out: std.ArrayList(u64) = .empty;
+ const m = rec.moment(i);
+ var p = (canim.Recording.word(m, head_at, 8) catch null) orelse return &.{};
+ while (p != 0 and out.items.len < 6) {
+ out.append(a, p) catch break;
+ p = (canim.Recording.word(m, p + 8, 8) catch null) orelse break;
+ }
+ return out.items;
+}
+
+/// A node's place in the drawing at a moment: its row (0 the program's, 1
+/// the free list's) and its index in that row.
+const Spot = struct { row: u8, k: usize };
+
+fn spotOf(program: []const u64, free: []const zt.heap.Entry, node: u64) ?Spot {
+ for (program, 0..) |p, k| if (p == node) return .{ .row = 0, .k = k };
+ for (free, 0..) |e, k| if (e.chunk + 16 == node) return .{ .row = 1, .k = k };
+ return null;
+}
+
+/// The drawing: `nodes` in two rows, the program's list over malloc's free
+/// list, the `bin` heading the second; a node travels between the rows
+/// when it is freed or taken back (36 f, `glide`, with the idea's slot).
+const Lists = struct {
+ cursor: canim.Cursor,
+ stage: *const canim.Stage,
+ head_at: u64,
+
+ const w = 136;
+ const h = 44;
+ const apart = 28;
+ const well = theme.metric.node.pointer_w;
+ const rows_y = [2]f32{ 72, 182 };
+ const row_x = [2]f32{ 160, 12 + 160 + 28 };
+
+ fn at(s: Spot) ui.Vec {
+ return .{ row_x[s.row] + @as(f32, @floatFromInt(s.k)) * (w + apart), rows_y[s.row] };
+ }
+
+ pub fn draw(l: *const Lists, f: *sk.Frame, placed: anim.Placed) void {
+ const box = l.stage.box(placed, .band);
+ if (box.h < cm.tag + 24) return;
+ const u = canim.ui.Ui{ .f = f, .at = placed };
+ const v = u.moved(box.x, box.y).faded(placed.value(l.stage.drawing));
+ v.clip(.{ .x = 0, .y = 0, .w = box.w, .h = box.h });
+ defer v.unclip();
+ const now = l.cursor.now(placed);
+ const rec = l.cursor.rec;
+ const a = f.scratch;
+ _ = v.panel(box.w, box.h, "the chunks of 0x20", .{ .focus = true, .note = "the program's list \u{00b7} malloc's free list" });
+ const stops = [2]u64{ now.stops[1], now.stops[0] };
+ var program: [2][]const u64 = undefined;
+ var free: [2][]const zt.heap.Entry = undefined;
+ var heaps: [2]?zt.heap.Heap = undefined;
+ for (stops, 0..) |i, side| {
+ heaps[side] = heapAt(a, rec, i);
+ program[side] = programList(a, rec, i, l.head_at);
+ free[side] = if (heaps[side]) |hp| freeList(hp) else &.{};
+ }
+ // The idea reacts after the bytes: a node travels with the idea's slot.
+ const p = canim.ease.glide(now.moving(.idea, 0, 36.0 / 60.0));
+ const shown: usize = if (p >= 0.5) 1 else 0;
+ v.text(.sans, theme.size.sans.micro, 12, rows_y[0] + 28, "the program's", t.faint);
+ // The bin: dashed and faint while the thread's tcache is glibc's dummy.
+ const bin: canim.Rect = .{ .x = 12, .y = rows_y[1], .w = 160, .h = h };
+ const hp = heaps[shown];
+ if (hp == null or hp.?.tcache == null) {
+ v.dashedFrame(bin, t.faint, theme.stroke.rule);
+ v.label(.mono, theme.size.mono.context, bin, .center, "dummy tcache", t.faint);
+ } else {
+ v.fill(bin, theme.color.raised);
+ v.label(.mono, theme.size.mono.context, bin, .center, "tcache 0x20", t.primary);
+ // How many it holds, on its shoulder.
+ const badge: canim.Rect = .{ .x = bin.x + bin.w - 24, .y = bin.y - 34, .w = 30, .h = 30 };
+ v.fill(badge, theme.color.page);
+ v.frame(badge, t.faint, theme.stroke.rule);
+ v.label(.mono, theme.size.mono.small, badge, .center, v.print("{d}", .{holds(hp.?) orelse 0}), t.primary);
+ if (free[shown].len > 0) v.route(&.{ .{ bin.x + bin.w, bin.y + h / 2 }, .{ row_x[1] - 2, bin.y + h / 2 } }, theme.color.region.heap, .{ .width = theme.stroke.line, .head = theme.metric.node.arrow_head });
+ }
+ // The top: what is left of the arena, its size.
+ if (hp) |hh| if (hh.chunks.len > 0) {
+ const top = hh.chunks[hh.chunks.len - 1];
+ const r: canim.Rect = .{ .x = box.w - 12 - 160, .y = rows_y[1], .w = 160, .h = h };
+ v.dashedFrame(r, t.faint, theme.stroke.rule);
+ v.label(.mono, theme.size.mono.context, r, .center, v.print("top 0x{x}", .{top.size()}), t.dim);
+ _ = v.address(r.x + 16, r.y - 8, top.addr, .{ .ink = ui.rgb(theme.color.region.heap) });
+ };
+ // Every node of either moment, where it was and where it goes.
+ var nodes: std.ArrayList(u64) = .empty;
+ for (program) |list| for (list) |n| if (std.mem.indexOfScalar(u64, nodes.items, n) == null) nodes.append(a, n) catch {};
+ for (free) |list| for (list) |e| if (std.mem.indexOfScalar(u64, nodes.items, e.chunk + 16) == null) nodes.append(a, e.chunk + 16) catch {};
+ const regs = (now.moment().regs(rec.tid) catch null) orelse zt.Regs{};
+ for (nodes.items) |node| {
+ const from = spotOf(program[0], free[0], node);
+ const to = spotOf(program[1], free[1], node);
+ const s0 = from orelse to.?;
+ const s1 = to orelse from.?;
+ const xy = canim.ui.Vec{ std.math.lerp(at(s0)[0], at(s1)[0], p), std.math.lerp(at(s0)[1], at(s1)[1], p) };
+ const shows: f32 = if (from == null) p else if (to == null) 1 - p else 1;
+ const nv = v.faded(shows);
+ const freed = (if (p >= 0.5) s1 else s0).row == 1;
+ const r: canim.Rect = .{ .x = xy[0], .y = xy[1], .w = w, .h = h };
+ const m = if (p >= 0.5) now.moment() else now.before();
+ _ = nv.address(r.x + 16, r.y - 8, node, .{ .ink = ui.rgb(theme.color.region.heap) });
+ if (freed) {
+ // Freed: dashed, its first word the link (where the value was), the second hatched, `key`.
+ nv.dashedFrame(r, theme.color.region.heap, theme.stroke.rule);
+ nv.fill(.{ .x = r.x + 2, .y = r.y + 2, .w = w / 2 - 2, .h = h - 4 }, theme.color.well);
+ for (0..4) |k| {
+ const x0 = r.x + w / 2 + 8 + @as(f32, @floatFromInt(k)) * 14;
+ nv.line(.{ x0, r.y + h - 4 }, .{ x0 + 12, r.y + 4 }, theme.color.rule, theme.stroke.rule);
+ }
+ nv.text(.mono, theme.size.mono.context, r.x + w - 40, r.y + 16, "key", t.faint);
+ } else {
+ nv.fill(.{ .x = r.x, .y = r.y, .w = w - well, .h = h }, theme.color.raised);
+ nv.fill(.{ .x = r.x + w - well, .y = r.y, .w = well, .h = h }, theme.color.well);
+ const value = (canim.Recording.word(m, node, 8) catch null) orelse 0;
+ const heat = now.written(node, 8, .idea, 0);
+ const ink = nv.cellWritten(.{ .x = r.x, .y = r.y, .w = w - well, .h = h }, heat, theme.color.raised);
+ nv.label(ink.face, theme.size.mono.small, .{ .x = r.x, .y = r.y, .w = w - well, .h = h }, .center, nv.print("{d}", .{@as(i64, @bitCast(value))}), if (heat.level >= 1) ink.ink else ui.rgb(t.primary));
+ }
+ // Its link: the next node in its row, as the pointer protects or holds it.
+ const sq: canim.Rect = .{ .x = if (freed) r.x + 18 else r.x + w - well / 2 - 5, .y = r.y + h / 2 - 5, .w = 10, .h = 10 };
+ const word = (canim.Recording.word(m, node + if (freed) @as(u64, 0) else 8, 8) catch null) orelse 0;
+ const next = if (freed) word ^ (node >> 12) else word;
+ if (next == 0) {
+ nv.line(.{ sq.x - 6, sq.y + 16 }, .{ sq.x + 16, sq.y - 6 }, t.dim, theme.stroke.rule);
+ } else if (spotOf(program[shown], free[shown], next)) |ns| {
+ nv.fill(sq, theme.color.region.heap);
+ const nx = at(ns);
+ if (nx[1] == r.y and nx[0] > r.x) nv.route(&.{ .{ sq.x + 10, r.y + h / 2 }, .{ nx[0] - 2, r.y + h / 2 } }, theme.color.region.heap, .{ .width = theme.stroke.line, .head = theme.metric.node.arrow_head });
+ }
+ // Who points here: `head`, and the registers.
+ var names: [4][]const u8 = undefined;
+ var n: usize = 0;
+ if ((canim.Recording.word(m, l.head_at, 8) catch null) == node) {
+ names[n] = "head";
+ n += 1;
+ }
+ for ([_][]const u8{ "rax", "rdi" }) |reg| if (regs.named(reg) == node and n < names.len) {
+ names[n] = reg;
+ n += 1;
+ };
+ if (n > 0) nv.pinUnder(r.x + 40, r.y + h + 2, names[0..n], theme.color.region.heap, theme.size.mono.context);
+ }
+ }
+};
+
+/// The heap's bytes by fields at the stop shown: each chunk's size word as
+/// `size`, a node's words as the program's (`number`, `pointer`) while it
+/// has them, as malloc's (`protected`, `key`) while malloc does.
+fn fieldsAt(a: std.mem.Allocator, rec: *canim.Recording, i: u64) []const canim.hexdump.Field {
+ var out: std.ArrayList(canim.hexdump.Field) = .empty;
+ const hp = heapAt(a, rec, i) orelse return &.{};
+ const m = rec.moment(i);
+ for (hp.chunks, 0..) |c, k| {
+ if (c.addr + 8 >= view_base + view_len) break;
+ const at = c.addr - view_base;
+ const tcache_chunk = if (hp.tcache) |tc| tc.addr == c.addr + 16 else false;
+ out.append(a, .{ .at = at + 8, .len = 8, .reads = .size, .note = if (k + 1 == hp.chunks.len) "top" else if (tcache_chunk) "tcache" else "" }) catch {};
+ if (c.size() != 0x20 or k + 1 == hp.chunks.len) continue;
+ if (c.in == .tcache) {
+ out.append(a, .{ .at = at + 16, .len = 8, .reads = .protected }) catch {};
+ out.append(a, .{ .at = at + 24, .len = 8, .reads = .bytes, .note = "key" }) catch {};
+ } else {
+ // Taken back, before the program writes it: the old link is still there.
+ const value = (canim.Recording.word(m, c.addr + 16, 8) catch null) orelse 0;
+ const stale = value >> 12 == (c.addr + 16) >> 12;
+ out.append(a, if (stale) .{ .at = at + 16, .len = 8, .reads = .bytes, .note = "the old link" } else .{ .at = at + 16, .len = 8 }) catch {};
+ out.append(a, .{ .at = at + 24, .len = 8, .reads = .pointer }) catch {};
+ }
+ }
+ return out.items;
+}
+
+const Chunks = struct {
+ cursor: canim.Cursor,
+ stage: *const canim.Stage,
+
+ pub fn draw(c: *const Chunks, f: *sk.Frame, placed: anim.Placed) void {
+ const v = canim.hexdump.panel(f, placed, c.stage, "the heap, 405000 to 40506f", &.{});
+ defer v.u.unclip();
+ if (v.rows == 0) return;
+ const now = c.cursor.now(placed);
+ canim.hexdump.fielded(v, now, cm.tag + cm.pad, .{ .base = view_base, .len = view_len, .fields = fieldsAt(f.scratch, c.cursor.rec, now.stop(.memory)) });
+ v.veil(now);
+ }
+};
+
+/// The tcache the program ends with: found once (its heap read at the last stop).
+var tcache_found: ?zt.heap.Tcache = null;
+fn tcacheOf(rec: *canim.Recording) zt.heap.Tcache {
+ if (tcache_found == null) {
+ var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+ const hp = heapAt(arena.allocator(), rec, rec.end()) orelse @panic("heap: no heap in the recording");
+ tcache_found = hp.tcache orelse @panic("heap: no tcache at the end");
+ tcache_found.?.bins = &.{};
+ arena.deinit();
+ }
+ return tcache_found.?;
+}
+
+/// The global the line at moment `i` reads by `[rip + X]` (its first such operand).
+fn globalOf(rec: *canim.Recording, i: u64) u64 {
+ var buf: [256]u8 = undefined;
+ var addr = rec.register(i, "rip");
+ for (0..8) |_| {
+ const here = rec.instruction(i, addr, &buf) orelse break;
+ addr += here.len;
+ const at = std.mem.indexOf(u8, here.text, "[rip + 0x") orelse continue;
+ const close = std.mem.indexOfScalarPos(u8, here.text, at, ']') orelse continue;
+ return addr + (std.fmt.parseInt(u64, here.text[at + 9 .. close], 16) catch continue);
+ }
+ @panic("heap: the line reads no global");
+}
+
+/// The moment of the `n`th call of `function`'s line `line`.
+fn lineIn(rec: *canim.Recording, function: []const u8, n: usize, line: u32) u64 {
+ return rec.lineMoment(line, rec.call(function, n).enter);
+}
+
+fn frame(s: *anim.Frame) void {
+ const rec = canim.open(recordings.heap);
+ const main = rec.call("main", 0);
+ var at = canim.cursor(s, rec, main.enter);
+ at.journey(.line, rec.lineMoment(30, main.enter));
+ at.levels = .{ .idea = .data, .source_rows = 10 };
+ const ctx = canim.context(s, at, .{ .split = canim.layout.split.subject });
+ // `head`, the program's global: where line 13 (`n->next = head;`) reads it, `[rip + X]`.
+ const head_at = globalOf(rec, lineIn(rec, "push", 0, 13));
+ const lists = canim.add(s, Lists{ .cursor = at, .stage = ctx.stage, .head_at = head_at });
+ const chunks = canim.add(s, Chunks{ .cursor = at, .stage = ctx.stage });
+ // The tcache, once there is one: a loupe from the row of the chunk it lives in.
+ const tc = tcacheOf(rec);
+ const tcache = canim.loupe(s, .{ .cursor = at, .stage = ctx.stage, .from = .{ .row = .{
+ .at = tc.addr - 8,
+ .name = "tcache",
+ .note = "tcache_perthread_struct \u{00b7} 0x2f0 bytes",
+ .fields = .{ .base = tc.addr, .len = 0x2f0, .fields = &.{
+ .{ .at = 0, .len = 2, .note = "slots left" },
+ .{ .at = 0x98, .len = 8, .reads = .pointer, .note = "the head of 0x20" },
+ } },
+ } } });
+ var says: canim.Narrator = .{};
+ const tm = theme.time;
+ const joins = ctx.ties(s);
+ canim.establish(s, .{ ctx.clock, ctx.registers, ctx.stack, ctx.source, ctx.disasm, chunks, lists, joins });
+
+ says.line(s, "A list of three, pushed and popped: what malloc and free\ndo to the heap under it, a stop after each.");
+ at.walk(s, .line, lineIn(rec, "push", 0, 12));
+ says.line(s, "malloc(16) cut a chunk of 0x20 off the top: its size word,\n0x21, then the 16 bytes rax points at.");
+ at.walk(s, .line, lineIn(rec, "push", 1, 10));
+ at.hurry(s, .line, rec.lineMoment(26, main.enter), .{});
+ says.line(s, "Three pushes, three chunks in a row, each with P: the chunk\nbefore it is in use. The next pointers are arcs in the bytes.");
+ at.walk(s, .line, lineIn(rec, "pop", 0, 21));
+ says.line(s, "free gives 9's chunk to the tcache, malloc's bin for 0x20.\nIts first word is the link now: 405, NULL safe-linked.");
+ at.walk(s, .line, rec.lineMoment(27, main.enter));
+ tcache.open(s);
+ s.wait(tm.phrase_rest);
+ at.hurry(s, .line, lineIn(rec, "pop", 1, 21), .{});
+ says.line(s, "The second chains to the first: 405455 is 405050 xor 405,\nthe chunk's own address shifted 12.");
+ at.walk(s, .line, rec.lineMoment(28, main.enter));
+ s.wait(tm.phrase_rest);
+ says.line(s, "malloc(16) takes the bin's head back: the tcache points\nat 405050 again, the key is wiped, the old link stays.");
+ at.walk(s, .line, lineIn(rec, "push", 3, 12));
+ at.walk(s, .line, rec.lineMoment(30, main.enter));
+ tcache.close(s);
+ says.close(s);
+}