//! 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 }; /// The program's row at a moment: the chunks of 0x20 in neither list (the /// one malloc has just returned, the one pop has just taken off), then the /// list from `head`. User addresses. fn programRow(a: std.mem.Allocator, rec: *canim.Recording, i: u64, head_at: u64, hp: ?zt.heap.Heap) []const u64 { const list = programList(a, rec, i, head_at); var out: std.ArrayList(u64) = .empty; if (hp) |h| for (h.chunks, 0..) |c, k| { if (k + 1 == h.chunks.len or c.size() != 0x20 or c.free or c.in != .none) continue; if (std.mem.indexOfScalar(u64, list, c.addr + 16) != null) continue; out.append(a, c.addr + 16) catch {}; }; out.appendSlice(a, list) catch {}; return out.items; } 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 value of the stack local `name` of the newest frame, where the debug info places it. fn local(a: std.mem.Allocator, m: canim.Recording.Moment, regs: zt.Regs, name: []const u8) ?u64 { if (regs.rbp <= regs.rsp or regs.rbp - regs.rsp > 512) return null; const out = a.alloc(zt.telescope.Slot, (regs.rbp + 16 - regs.rsp) / 8) catch return null; const slots = zt.telescope.slots(m, ®s, regs.rsp, out) catch return null; for (slots, 0..) |sl, k| if (sl.role == .local and sl.frame == 0 and sl.role.local.offset == 0 and std.mem.eql(u8, sl.role.local.name, name)) { return canim.Recording.word(m, regs.rsp + 8 * k, 8) catch null; }; 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`, in the idea's slot). /// Nothing changes in one frame: the bin's box and the top's crossfade /// (12 f), the top's size and the bin's count are struck, the count fading /// in first (design/motion.md, "The first free"). 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 }; /// Both rows from the free list's first node, under the program's head. const row_x = [2]f32{ 12 + 160 + 28, 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] }; } /// How far through `len` frames from `from` frames after the idea's slot. fn after(now: canim.Now, from: f32, len: f32) f32 { return switch (now.plan.gait) { .walk => if (now.resting()) 1 else std.math.clamp((now.since(.idea, 0) - from / 60.0) / (len / 60.0), 0, 1), .run => std.math.clamp(now.since(.idea, 0) / theme.time.run_ease, 0, 1), .sprint => 1, }; } 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 v = canim.panelAt(f, placed, box).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] = programRow(a, rec, i, l.head_at, heaps[side]); free[side] = if (heaps[side]) |hp| freeList(hp) else &.{}; } // The idea reacts after the bytes: the boxes crossfade (12 f), then a node lifts and travels (36 f). const fade = after(now, 0, 12); const p = canim.ease.glide(after(now, 12, 36)); 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; raised once it has one. const bin: canim.Rect = .{ .x = 12, .y = rows_y[1], .w = 160, .h = h }; const real = [2]bool{ heaps[0] != null and heaps[0].?.tcache != null, heaps[1] != null and heaps[1].?.tcache != null }; for (real, 0..) |is, side| { const shows = if (real[0] == real[1]) @as(f32, if (side == 1) 1 else 0) else if (side == 1) fade else 1 - fade; if (shows <= 0) continue; const bv = v.faded(shows); if (!is) { bv.dashedFrame(bin, t.faint, theme.stroke.rule); bv.label(.mono, theme.size.mono.context, bin, .center, "dummy tcache", t.faint); } else { bv.fill(bin, theme.color.raised); bv.label(.mono, theme.size.mono.context, bin, .center, "tcache 0x20", t.primary); } } // How many it holds, on its shoulder: it fades in (6 f), then is armed and struck as the node lands. const counts = [2]?u16{ if (heaps[0]) |hp| holds(hp) else null, if (heaps[1]) |hp| holds(hp) else null }; if (counts[1] != null and real[1]) { const badge: canim.Rect = .{ .x = bin.x + bin.w - 24, .y = bin.y - 34, .w = 30, .h = 30 }; const changed = counts[0] == null or !real[0] or counts[0].? != counts[1].?; const comes = !real[0] or counts[0] == null; const bv = v.faded(if (comes) after(now, 42, 6) else 1); const heat = if (changed and now.walking()) now.heat(0, null, now.since(.idea, 0) - 60.0 / 60.0) else if (changed) canim.ui.Heat.ember else canim.ui.Heat.none; bv.fill(badge, theme.color.page); const ink = bv.cellWritten(badge, heat, theme.color.page); // Framed, but while the strike's paper is on it. bv.faded(if (heat.level < 1) 1 else 1 - heat.solid * heat.in).frame(badge, t.faint, theme.stroke.rule); const landed = !changed or now.resting() or !now.walking() or now.since(.idea, 0) >= 60.0 / 60.0 + theme.time.strike.in / 2.0; const count = if (landed or comes) counts[1].? else counts[0].?; bv.label(ink.face, theme.size.mono.small, badge, .center, bv.print("{d}", .{count}), if (heat.level >= 1) ink.ink else ui.rgb(t.primary)); } if (real[shown] and 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 place and size; crossfading where the step moved it, its size struck. const tops = [2]?zt.heap.Chunk{ if (heaps[0]) |hp| (if (hp.chunks.len > 0) hp.chunks[hp.chunks.len - 1] else null) else null, if (heaps[1]) |hp| (if (hp.chunks.len > 0) hp.chunks[hp.chunks.len - 1] else null) else null }; const top_r: canim.Rect = .{ .x = box.w - 12 - 160, .y = rows_y[1], .w = 160, .h = h }; const moved = if (tops[0] != null and tops[1] != null) tops[0].?.addr != tops[1].?.addr or tops[0].?.size() != tops[1].?.size() else tops[0] != null or tops[1] != null; for (tops, 0..) |maybe, side| if (maybe) |top| { const shows = if (!moved) @as(f32, if (side == 1) 1 else 0) else if (side == 1) fade else 1 - fade; if (shows <= 0) continue; const tv = v.faded(shows); tv.dashedFrame(top_r, t.faint, theme.stroke.rule); const size_text = tv.print("0x{x}", .{top.size()}); const sx = top_r.x + top_r.w - 16 - tv.width(.mono, theme.size.mono.context, size_text); tv.text(.mono, theme.size.mono.context, top_r.x + 16, theme.baseline(top_r.y, h, theme.size.mono.context), "top", t.dim); var ink: canim.ui.Ink = .{ .ink = ui.rgb(t.dim) }; if (side == 1 and moved and tops[0] != null and now.walking()) ink = tv.cellWritten(.{ .x = sx - 4, .y = top_r.y + 10, .w = tv.width(.mono, theme.size.mono.context, size_text) + 8, .h = 24 }, now.heat(0, null, now.since(.idea, 0) - 12.0 / 60.0), null); tv.text(ink.face, theme.size.mono.context, sx, theme.baseline(top_r.y, h, theme.size.mono.context), size_text, ink.ink); _ = tv.address(top_r.x + 16, top_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 {}; // Who points at each node, before the step and after it: its pin's names crossfade (12 f, with the idea). const regs = [2]zt.Regs{ (now.before().regs(rec.tid) catch null) orelse zt.Regs{}, (now.moment().regs(rec.tid) catch null) orelse zt.Regs{} }; const locals = [2]?u64{ local(a, now.before(), regs[0], "n"), local(a, now.moment(), regs[1], "n") }; const heads = [2]?u64{ canim.Recording.word(now.before(), l.head_at, 8) catch null, canim.Recording.word(now.moment(), l.head_at, 8) catch null }; 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) after(now, 0, 12) else if (to == null) 1 - after(now, 0, 12) else 1; const nv = v.faded(shows); const r: canim.Rect = .{ .x = xy[0], .y = xy[1], .w = w, .h = h }; // On its way between the rows its address goes and comes back (the first and last quarter): it never passes over a pin's names. const travels = s0.row != s1.row or s0.k != s1.k; const label = if (travels) std.math.clamp(@max(1 - 4 * p, 4 * p - 3), 0, 1) else 1; _ = nv.faded(label).address(r.x + 16, r.y - 8, node, .{ .ink = ui.rgb(theme.color.region.heap) }); // Nothing turns in a frame: a node that changes lists turns as it lands (its last 12 f), // and its value and link, where they change and are not struck, crossfade with the idea (12 f). const lands = after(now, 36, 12); const turns = after(now, 0, 12); for ([2]Spot{ s0, s1 }, 0..) |spot, side| { const freed = spot.row == 1; const other_freed = (if (side == 0) s1 else s0).row == 1; const look = if (freed == other_freed) @as(f32, if (side == 1) 1 else 0) else if (side == 1) lands else 1 - lands; if (look <= 0) continue; const lv = nv.faded(look); if (freed) { // Freed: dashed, its first word the link (where the value was), the second hatched, `key`. lv.dashedFrame(r, theme.color.region.heap, theme.stroke.rule); lv.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; lv.line(.{ x0, r.y + h - 4 }, .{ x0 + 12, r.y + 4 }, theme.color.rule, theme.stroke.rule); } lv.text(.mono, theme.size.mono.context, r.x + w - 40, r.y + 16, "key", t.faint); } else { lv.fill(.{ .x = r.x, .y = r.y, .w = w - well, .h = h }, theme.color.raised); lv.fill(.{ .x = r.x + w - well, .y = r.y, .w = well, .h = h }, theme.color.well); // A node changing hands is not struck: its words are the other list's now (the dump strikes them). const heat = if (s0.row == s1.row) now.written(node, 8, .idea, 0) else canim.ui.Heat.none; const cell: canim.Rect = .{ .x = r.x, .y = r.y, .w = w - well, .h = h }; const ink = lv.cellWritten(cell, heat, theme.color.raised); // Struck, the digits change under the strike's fill; else they crossfade. const values = [2]u64{ (canim.Recording.word(now.before(), node, 8) catch null) orelse 0, (canim.Recording.word(now.moment(), node, 8) catch null) orelse 0 }; const struck = heat.level >= 1; const turned = if (struck) @as(f32, if (now.since(.idea, 0) >= theme.time.strike.in / 2.0) 1 else 0) else turns; for (values, [2]f32{ if (values[0] != values[1]) 1 - turned else 0, if (values[0] != values[1]) turned else 1 }) |value, k| { if (k <= 0) continue; // Taken back before the program writes it: the old link, faint, as stored. const stale = value != 0 and value >> 12 == node >> 12; if (stale) lv.faded(k).label(.mono, theme.size.mono.context, cell, .center, lv.print("{x}", .{value}), t.faint) else lv.faded(k).label(ink.face, theme.size.mono.small, cell, .center, lv.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 }; var links: [2]u64 = undefined; for (&links, [2]canim.Recording.Moment{ now.before(), now.moment() }) |*link, lm| { const word = (canim.Recording.word(lm, node + if (freed) @as(u64, 0) else 8, 8) catch null) orelse 0; link.* = if (freed) word ^ (node >> 12) else word; } for (links, [2]f32{ if ((links[0] == 0) != (links[1] == 0)) 1 - turns else 0, if ((links[0] == 0) != (links[1] == 0)) turns else 1 }) |next, k| { if (k <= 0) continue; if (next == 0) { lv.faded(k).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| { lv.faded(k).fill(sq, theme.color.region.heap); const nx = at(ns); if (@abs(nx[1] - r.y) < 1 and nx[0] > r.x) lv.faded(k).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`, the local `n`, and the registers. var names: [2][4][]const u8 = undefined; var count = [2]usize{ 0, 0 }; for (0..2) |side| { if (heads[side] == node) { names[side][count[side]] = "head"; count[side] += 1; } if (locals[side] == node) { names[side][count[side]] = "n"; count[side] += 1; } for ([_][]const u8{ "rax", "rdi" }) |reg| if (regs[side].named(reg) == node and count[side] < 4) { names[side][count[side]] = reg; count[side] += 1; }; } const same = count[0] == count[1] and for (names[0][0..count[0]], names[1][0..count[1]]) |x, y| { if (!std.mem.eql(u8, x, y)) break false; } else true; const turn = if (same) 1 else after(now, 0, 12); for (0..2) |side| { const pin = if (same) @as(f32, if (side == 1) 1 else 0) else if (side == 1) turn else 1 - turn; if (pin > 0 and count[side] > 0) nv.faded(pin).pinUnder(r.x + 40, r.y + h + 2, names[side][0..count[side]], 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 { // On the map its box is as long as its rows. canim.map.measure(.view, (view_len + 15) / 16); 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); // The heap new in this step (the first malloc's): its rows come in, unmarked, over 12 f with memory's slot. const new = !now.resting() and heapAt(f.scratch, c.cursor.rec, now.stops[1]) == null; const comes: f32 = if (new) std.math.clamp(now.since(.memory, 0) / (12.0 / 60.0), 0, 1) else 1; canim.hexdump.fielded(.{ .u = v.u.faded(comes), .rows = v.rows, .box = v.box }, now, cm.tag + cm.pad, .{ .base = view_base, .len = view_len, .fields = fieldsAt(f.scratch, c.cursor.rec, now.stop(.memory)), .was = fieldsAt(f.scratch, c.cursor.rec, now.stops[1]), .watched = if (new) 0 else std.math.maxInt(usize), .pins = true }); 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); } /// A step that changes the tcache, walked (`wave`: as a continue, free /// having been stepped over): after memory has struck, the loupe opens over /// the stack (36 f), its fields strike in it (6 f after, 6 f apart), then /// the idea; it closes with the advance. Never open over a step it does not concern. fn tcacheStep(at: canim.Cursor, s: *anim.Frame, tcache: *const canim.Loupe, wave: bool) void { const tm = theme.time; // A free: its line's instructions first, a cascade onto the call row (the recording stops there, // `break_call`); then the call, stepped over, goes on from that row without firing the line again. const onto = wave and at.rec.own[at.moment(s) + 1] == at.rec.own[at.moment(s)]; if (onto) at.walk(s, .moment, at.moment(s) + 1); const from = at.moment(s); const to = at.rec.next(.line, from); var plan = at.planned(from, to, wave); plan.fires = !onto; const opens = plan.at[1] + 3 * 6.0 / 60.0 + 12.0 / 60.0; const idea = opens + tm.loupe.open + 24.0 / 60.0; const later = @max(idea - plan.at[2], 0); plan.at[2] += later; plan.advance += later; plan.total += later; const start = s.cursor; at.step(s, to, plan, plan.total); const end = s.cursor; s.cursor = start + opens; tcache.open(s); s.cursor = start + plan.advance; tcache.close(s); s.cursor = end; if (at.phraseEnds(from, to)) s.wait(tm.phrase_rest); } fn frame(s: *anim.Frame) void { const rec = canim.open(recordings.heap); const main = rec.call("main", 0); // From main's first line, `push(7)`. var at = canim.cursor(s, rec, rec.lineMoment(24, 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 }); // On the map too: the drawing over the source, the heap's bytes over the registers. ctx.map.add(s, Lists{ .cursor = at, .stage = ctx.map.stage, .head_at = head_at }); ctx.map.add(s, Chunks{ .cursor = at, .stage = ctx.map.stage }); // The tcache, once there is one: a loupe from the row of the chunk it lives in, over the stack. const tc = tcacheOf(rec); const tcache = canim.loupe(s, .{ .cursor = at, .stage = ctx.stage, .from = .{ .row = .{ .at = tc.addr - 8, .name = "tcache", // 76 two-byte counts and 76 pointers (glibc 2.44): 760 bytes. .note = "tcache_perthread_struct \u{00b7} 0x2f8 bytes", .fields = .{ .base = tc.addr, .len = 0x2f8, .fields = &.{ .{ .at = 0, .len = 2, .note = "slots left" }, .{ .at = 0x98, .len = 8, .reads = .pointer, .note = "the head of 0x20" }, } }, } } }); ctx.map.loupes = .{ tcache, null }; var says: canim.Narrator = .{}; const joins = ctx.ties(s); canim.establish(s, .{ ctx.clock, ctx.registers, ctx.stack, ctx.source, ctx.disasm, chunks, lists, joins }); // design/motion.md, "A scene: libc's heap from the inside": each caption // leads the steps it is about, and changes only in a rest. says.line(s, "Three pushes and two pops: what malloc and free\ndo to the heap."); at.hurry(s, .line, lineIn(rec, "push", 0, 11), .{}); says.line(s, "malloc(16) cut a chunk of 0x20 off the top: its size word,\n0x21, then the 16 bytes rax points at. The top is 0x20 smaller."); at.walk(s, .line, lineIn(rec, "push", 0, 15)); // The return to main runs with the two pushes after it. says.line(s, "Two more pushes, at a run: three chunks in a row, each\nwith P set, the chunk before it in use."); at.hurry(s, .line, rec.lineMoment(27, main.enter), .{}); says.line(s, "pop takes the head off the list: head = n->next."); at.hurry(s, .line, lineIn(rec, "pop", 0, 19), .{}); at.walk(s, .line, lineIn(rec, "pop", 0, 20)); says.line(s, "free gave 9's chunk to the tcache, malloc's bin for 0x20.\nIts first word is the link now: 405, which is NULL, safe-linked."); tcacheStep(at, s, tcache, true); at.hurry(s, .line, rec.lineMoment(28, main.enter), .{}); says.line(s, "The second pop: head moves on, to 7's node."); at.hurry(s, .line, lineIn(rec, "pop", 1, 19), .{}); at.walk(s, .line, lineIn(rec, "pop", 1, 20)); says.line(s, "The second free chains to the first: 405455 is 405050 xor 405,\nthe chunk's own address shifted 12. The arc is the pointer it hides."); tcacheStep(at, s, tcache, true); // Walked, the return: this caption's reading time is longer than its steps, and the picture would stand still. at.walk(s, .line, rec.lineMoment(29, main.enter)); says.line(s, "malloc(16) took the bin's head, 405030: the tcache points\nat 405050 again, the key is wiped, the old link stays."); at.hurry(s, .line, lineIn(rec, "push", 3, 11), .{}); tcacheStep(at, s, tcache, false); says.line(s, "push writes 25 over the old link: the list is 25, then 7."); at.walk(s, .line, lineIn(rec, "push", 3, 15)); at.hurry(s, .line, rec.lineMoment(30, main.enter), .{}); says.close(s); }