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
|
//! 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;
// Read as the caption names them: the page's type, then the rest of its
// header (3 cells), then the cell pointers, then each cell.
out.appendSlice(arena, &.{
.{ .at = 0, .len = 1, .mark = 0 },
.{ .at = 1, .len = 2, .reads = .bytes, .big = true, .mark = 1 },
.{ .at = 3, .len = 2, .big = true, .mark = 1 },
.{ .at = 5, .len = 2, .reads = .bytes, .big = true, .mark = 1 },
.{ .at = 7, .len = 1, .reads = .bytes, .mark = 1 },
}) catch @panic("OOM");
for (0..cells) |k| out.append(arena, .{ .at = 8 + 2 * k, .len = 2, .big = true, .mark = 2 }) 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(3 + 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);
// Where a row's bytes go is the story, by their addresses: pwndbg's chains (`annotation = .whole`).
at.levels = .{ .source_rows = 8, .annotation = .whole };
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), 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,
});
// rdi, the table's cursor, opened as the caption names it; rsi, the row, linked to the view's row it points at.
const btcursor = canim.loupe(s, .{ .cursor = at, .stage = ctx.stage, .from = .{ .register = "rdi" } });
const joins, const row_link = ctx.tiesWith(s, "rsi", 1.0);
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.");
// As the caption names them: rdi's cursor opened under it (a beat of
// its own), then rsi linked to the row; then each field: the rowid, the record's length.
const named = s.cursor;
btcursor.open(s);
row_link.play(s);
s.cursor = named + t.loupe.open + row_link.total();
btcursor.close(s);
// Spread over the caption's reading: never more than 2 s still.
s.wait(1.4);
mark.in(s, row_marks[0]);
s.wait(2.0);
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);
// Back in `unixWrite`, 44 lines up from the call it waited on (more
// than the map's column of sqlite3.c holds round it): the panes fade
// through (24 f each way), the strips going over first.
var coming_back = crossing.step();
coming_back.travel = 2 * t.move;
coming_back.total += coming_back.travel - t.step;
at.step(s, back, coming_back, coming_back.total);
// Each field as the caption reaches it, 2 s apart: the picture is never still longer.
says.line(s, "Page 2 as the kernel took it: `0d`, a table's leaf; 3 cells,\nat `0ff7 0fef 0fe6`: each a row at the page's end.");
for (page_marks[0..3], 0..) |v, k| {
s.wait(if (k == 0) 0.4 else 2.0);
mark.in(s, v);
}
says.line(s, "Each cell: its length, rowid, header and text. 'alpha'\nwent in first and sits last: cells fill from the end.");
mark.out(s, page_marks[0..3]);
// The rows from the page's end: the first one in, then the next two.
for (page_marks[3..], 0..) |v, k| {
s.wait(if (k == 0) 0.4 else 2.0);
mark.in(s, v);
}
says.close(s);
}
|