diff options
Diffstat (limited to 'anim/scenes')
| -rw-r--r-- | anim/scenes/gallery.zig | 8 | ||||
| -rw-r--r-- | anim/scenes/sqlite.zig | 223 |
2 files changed, 227 insertions, 4 deletions
diff --git a/anim/scenes/gallery.zig b/anim/scenes/gallery.zig index 3b66a24..2cc3d9f 100644 --- a/anim/scenes/gallery.zig +++ b/anim/scenes/gallery.zig @@ -256,11 +256,11 @@ fn rowsPage(u: ui.Ui, p: *const Pages) void { panel = u.moved(64, y); const plain = " cur->next = prev;"; const styles: [128]u8 = @splat(0); - rows.line(panel, 0, 880, 22, plain, styles[0..plain.len], .{ .current = 0 }); - rows.line(panel, row, 880, 21, " node *next = cur->next;", styles[0..31], .{ .trail = 0 }); - rows.line(panel, 2 * row, 880, 20, " while (cur) {", styles[0..17], .{ .trail = 1 }); + rows.line(panel, 0, 880, 22, 0, plain, styles[0..plain.len], .{ .current = 0 }); + rows.line(panel, row, 880, 21, 0, " node *next = cur->next;", styles[0..31], .{ .trail = 0 }); + rows.line(panel, 2 * row, 880, 20, 0, " while (cur) {", styles[0..17], .{ .trail = 1 }); const long = " a line of source longer than the panel has room for, which is cut at its end"; - rows.line(panel, 3 * row, 880, 9, long, styles[0..long.len], .plain); + rows.line(panel, 3 * row, 880, 9, 0, long, styles[0..long.len], .plain); y = 750; title(u, 64, y, "bytes"); diff --git a/anim/scenes/sqlite.zig b/anim/scenes/sqlite.zig new file mode 100644 index 0000000..f145da6 --- /dev/null +++ b/anim/scenes/sqlite.zig @@ -0,0 +1,223 @@ +//! A row's way to disk: SQLite (the real one, its amalgamation built -O2) +//! puts three rows into a table in a transaction and commits. The scene +//! follows the first row from the bytecode interpreter into the B-tree, +//! and at the commit the 4 KiB page that holds all three into the kernel, +//! where its bytes are read as the page they are: the header, the cell +//! pointers, the rows at its end, last in first. +//! +//! How it moves (design/motion.md): the context at a breakpoint in +//! `sqlite3_step`, then a `continue` to `sqlite3BtreeInsert` (the backtrace +//! grows two frames, the arguments arrive in the registers); the argument +//! the row is (a struct on the caller's stack) comes in as the view; two +//! more continues, each rowid struck in it; a continue to the commit's +//! `unixWrite`, nine calls under `main`, the page it is handed as the view; +//! the lens changes to the kernel's side, and `pwrite64` crosses; then the +//! page's fields are read, a group at a time, as the captions name them. +const std = @import("std"); +const anim = @import("anim"); +const canim = @import("canim"); +const recordings = @import("recordings"); + +pub const background = canim.background; +pub const scene = anim.Live(frame, struct {}); + +const Field = canim.hexdump.Field; + +/// The breakpoints' stops: the last at or before `before` where the +/// program stopped at `name` (`sqlite3BtreeInsert+4`; a prefix, `unixWrite+`). +fn stopAt(rec: *canim.Recording, name: []const u8, before: u64) u64 { + var i = before + 1; + while (i > 0) { + i -= 1; + const here = rec.strings.get(rec.registers[i].rip) orelse continue; + if (std.mem.startsWith(u8, here, name)) return i; + } + std.debug.panic("sqlite: no stop at {s} before moment {d}", .{ name, before }); +} + +/// The struct the row is handed to the B-tree in (`BtreePayload`, the +/// source's lines 16740 to 16748): its members, from its first byte. +const payload = [_]Field{ + .{ .at = 0, .len = 8, .reads = .pointer }, // pKey: NULL for a table + .{ .at = 8, .len = 8, .mark = 0 }, // nKey: the rowid + .{ .at = 16, .len = 8, .reads = .pointer }, // pData: the record + .{ .at = 24, .len = 8, .reads = .pointer }, // aMem + .{ .at = 32, .len = 2 }, // nMem + .{ .at = 36, .len = 4, .mark = 1 }, // nData: the record's length + .{ .at = 40, .len = 4 }, // nZero +}; + +/// A table's leaf page, as SQLite's file format has it, read from its +/// bytes: the header (type, first freeblock, cells, where their content +/// begins, fragments), the cell pointers after it, and each cell (its +/// payload's length, its rowid, the record's header, the text of its one +/// column). Every number in it is big-endian; every varint here is a byte. +fn leaf(arena: std.mem.Allocator, page: []const u8) []const Field { + std.debug.assert(page[0] == 0x0d); + const cells = std.mem.readInt(u16, page[3..5], .big); + var out: std.ArrayList(Field) = .empty; + out.appendSlice(arena, &.{ + .{ .at = 0, .len = 1, .mark = 0 }, + .{ .at = 1, .len = 2, .reads = .bytes, .big = true, .mark = 0 }, + .{ .at = 3, .len = 2, .big = true, .mark = 0 }, + .{ .at = 5, .len = 2, .reads = .bytes, .big = true, .mark = 0 }, + .{ .at = 7, .len = 1, .reads = .bytes, .mark = 0 }, + }) catch @panic("OOM"); + for (0..cells) |k| out.append(arena, .{ .at = 8 + 2 * k, .len = 2, .big = true, .mark = 1 }) catch @panic("OOM"); + for (0..cells) |k| { + const at: usize = std.mem.readInt(u16, page[8 + 2 * k ..][0..2], .big); + const size = page[at]; + const header = page[at + 2]; + std.debug.assert(size < 0x80 and page[at + 1] < 0x80 and header == 2); + const mark: u8 = @intCast(2 + k); + out.appendSlice(arena, &.{ + .{ .at = at, .len = 1, .reads = .bytes, .mark = mark }, + .{ .at = at + 1, .len = 1, .mark = mark }, + .{ .at = at + 2, .len = 2, .reads = .bytes, .mark = mark }, + .{ .at = at + 4, .len = size - 2, .reads = .text, .mark = mark }, + }) catch @panic("OOM"); + } + return out.items; +} + +fn frame(s: *anim.Frame) void { + const rec = canim.open(recordings.sqlite); + const t = canim.theme.time; + const region = canim.theme.color.region; + + // The commit's write of page 2: 4096 bytes at offset 4096. The pager + // hands it to unixWrite, which calls pwrite64; and back. + const write = for (0..rec.syscalls.len) |k| { + const c = rec.syscalls[rec.syscalls.len - 1 - k]; + if (c.nr == @intFromEnum(std.os.linux.SYS.pwrite64) and c.args[2] == 4096 and c.args[3] == 4096) break c; + } else @panic("sqlite: no write of page 2"); + const handed = stopAt(rec, "unixWrite+4", write.enter); + const back = stopAt(rec, "unixWrite+", write.enter + 1); + std.debug.assert(handed + 1 == write.enter and back == write.enter + 1); + // The three rows' inserts, and the stop before the first: its statement's bytecode starting. + const third = stopAt(rec, "sqlite3BtreeInsert+", handed); + const second = stopAt(rec, "sqlite3BtreeInsert+", third - 1); + const first = stopAt(rec, "sqlite3BtreeInsert+", second - 1); + const start = stopAt(rec, "sqlite3_step+", first); + + var at = canim.cursor(s, rec, start); + at.levels = .{ .source_rows = 10 }; + at.journey(.moment, back); + // The lens is the subject: the call chain, eleven rows, over the + // program column (where the kernel's side comes later), and over the + // state column the bytes the newest call is handed. + var split = canim.layout.split.subject; + split.backtrace = split.band; + const ctx = canim.context(s, at, .{ .split = split, .syscalls = true }); + const kernel = canim.crossing(s, .{ .cursor = at, .stage = ctx.stage, .view = false }); + // What the opening stop's rbx points at: the SQL sqlite3_exec is running. + const sql = canim.add(s, canim.hexdump.Dump{ + .cursor = at, + .stage = ctx.stage, + .about = "the SQL being run, at rbx", + .of = .{ .base = rec.register(start, "rbx"), .len = 32, .fields = &.{.{ .at = 0, .len = 32, .reads = .text }}, .region = region.rodata }, + }); + // The row, as sqlite3BtreeInsert is handed it: rsi. + // (The views keep their marks: in the frame's arena, not on this stack.) + const row_marks = s.new([_]anim.Value{ s.value(0), s.value(0) }); + const row = canim.add(s, canim.hexdump.Dump{ + .cursor = at, + .stage = ctx.stage, + .about = "pX, the row: a BtreePayload, at rsi", + .of = .{ .base = rec.register(first, "rsi"), .len = 48, .fields = &payload, .region = region.stack }, + .marks = row_marks, + }); + // The page, as unixWrite is handed it: rsi. At that stop the debugger + // has read 32 bytes of it (where rsi leads); the kernel takes it whole. + const bytes = write.text; + std.debug.assert(bytes.len == 4096 and bytes[0] == 0x0d and bytes[4] == 3); + std.debug.assert(std.mem.eql(u8, bytes[8..14], &.{ 0x0f, 0xf7, 0x0f, 0xef, 0x0f, 0xe6 })); + std.debug.assert(rec.register(handed, "rsi") == write.args[1]); + const page_marks = s.new([_]anim.Value{ s.value(0), s.value(0), s.value(0), s.value(0), s.value(0) }); + const page = canim.add(s, canim.hexdump.Dump{ + .cursor = at, + .stage = ctx.stage, + .about = "pBuf: page 2 of t.db, at rsi", + .of = .{ .base = write.args[1], .len = 4096, .fields = leaf(s.arena, bytes), .region = region.heap, .seen = .{ .addr = write.args[1], .len = 32 } }, + .marks = page_marks, + }); + const joins = ctx.ties(s); + var says: canim.Narrator = .{}; + + const fade = struct { + fn in(f: *anim.Frame, o: anim.Obj) void { + f.play(.{o.fadeIn()}, .{ .seconds = canim.theme.time.quick, .ease = anim.ease.linear }); + } + fn out(f: *anim.Frame, o: anim.Obj) void { + f.play(.{o.fadeOut()}, .{ .seconds = canim.theme.time.quick, .ease = anim.ease.linear }); + } + }; + // A field read, as the caption names it: framed in, and out when the caption goes. + const mark = struct { + fn in(f: *anim.Frame, v: anim.Value) void { + f.play(.{v.to(1)}, .{ .seconds = canim.theme.time.read.in, .ease = anim.ease.linear }); + } + fn out(f: *anim.Frame, vs: []const anim.Value) void { + const from = f.cursor; + for (vs) |v| { + f.cursor = from; + f.play(.{v.to(0)}, .{ .seconds = canim.theme.time.read.out, .ease = anim.ease.linear }); + } + } + }; + // A continue: straight to the next stop, timed by what it changed. + const walk = struct { + fn to(c: canim.Cursor, f: *anim.Frame, moment: u64) void { + const plan = c.reading(c.moment(f), moment); + c.step(f, moment, plan, plan.total); + } + }.to; + + canim.establish(s, .{ ctx.clock, ctx.registers, ctx.stack, ctx.source, ctx.disasm, sql, ctx.backtrace, joins }); + says.line(s, "SQLite at a breakpoint in `sqlite3_step`, which runs\n`INSERT INTO t VALUES ('alpha')`. Continue:"); + // What rbx showed was this stop's: it goes before the program moves on. + fade.out(s, sql); + walk(at, s, first); + s.wait(t.beat); + // The row it was handed: a struct on its caller's stack. + fade.in(s, row); + + says.line(s, "`sqlite3VdbeExec`, the bytecode's loop, calls the B-tree: `rdi` is\nthe table's cursor, `rsi` the row: rowid 1, a record of 7 bytes."); + // Each field as the caption reaches it: the rowid, then the record's length. + mark.in(s, row_marks[0]); + s.wait(2 * t.beat); + mark.in(s, row_marks[1]); + + says.line(s, "Two more continues, the same call: rowid 2, then 3, records\nof 6 and 7 bytes. The rows are in memory, not yet on disk."); + mark.out(s, row_marks); + walk(at, s, second); + s.wait(t.beat); + walk(at, s, third); + + says.line(s, "`COMMIT`: `unixWrite`, nine calls under `main`, is handed\npage 2 of the file: 4096 bytes, for offset 4096."); + fade.out(s, row); + walk(at, s, handed); + s.wait(t.beat); + fade.in(s, page); + + says.line(s, "`pwrite64` takes it into the kernel: descriptor 3, the page,\n4096 bytes, offset 4096. The kernel says 4096 were written."); + // The lens changes to the kernel's side, where the page goes. + fade.out(s, ctx.backtrace); + fade.in(s, kernel); + s.wait(t.beat); + const crossing = canim.syscalls.Plan.of(write); + at.step(s, back, crossing.step(), crossing.total); + + says.line(s, "Page 2 as the kernel took it: `0d`, a table's leaf; 3 cells;\ntheir offsets, `0ff7 0fef 0fe6`, each a row at the page's end."); + mark.in(s, page_marks[0]); + s.wait(3 * t.beat); + mark.in(s, page_marks[1]); + says.line(s, "Each cell: its length, its rowid, the record's header, the text.\n'alpha' went in first and sits last: cells fill from the end."); + mark.out(s, page_marks[0..2]); + // The rows from the page's end: the first one in, then the next two. + for (page_marks[2..]) |v| { + mark.in(s, v); + s.wait(2 * t.beat); + } + says.close(s); +} |
