summaryrefslogtreecommitdiff
path: root/anim/scenes/heap.zig
blob: e227f172ad365d12c27b120d4a1ab6640be53bb3 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
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);
}