summaryrefslogtreecommitdiff
path: root/anim/scenes
diff options
context:
space:
mode:
Diffstat (limited to 'anim/scenes')
-rw-r--r--anim/scenes/gallery.zig8
-rw-r--r--anim/scenes/sqlite.zig223
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);
+}