//! 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 backtrace, 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. const ctx = canim.context(s, at, .{ .split = canim.layout.split.subject, .syscalls = true, .backtrace = true }); const kernel = canim.crossing(s, .{ .cursor = at, .stage = ctx.stage, .view = false }); // The map's drawing: how the program came to be here, the backtrace lens. ctx.map.add(s, canim.Backtrace{ .cursor = at, .stage = ctx.map.stage, .lens = true }); // 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", .since = start, .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, .since = first, }); // 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, .since = handed, }); 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 }); } } }; 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); at.@"continue"(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); at.@"continue"(s, second); s.wait(t.beat); at.@"continue"(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); at.@"continue"(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); }