diff options
Diffstat (limited to 'anim/scenes/heap.zig')
| -rw-r--r-- | anim/scenes/heap.zig | 323 |
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); +} |
