lib/sql/src/properties/crash.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const sql = @import("sql");
4
5 const file = sql.file;
6 const page = sql.page;
7 const fault = @import("fault/root.zig");
8
9 const property_page_count = 4;
10 const max_plan_steps = 16;
11 const max_boundaries = max_plan_steps + 1;
12
13 const scenario_schema = "tiny.sql.crash.scenario.v1";
14 const generator_revision = "swarm-weights-v2";
15 const scenario_artifact_path = "zig-out/hypothesis-failures/sql-crash-scenario.jhma";
16 const max_scenario_payload = 4 + max_plan_steps * 3 + 12;
17 const max_scenario_artifact = 192;
18
19 const Action = enum {
20 put,
21 commit,
22 checkpoint,
23 };
24
25 const Op = union(enum) {
26 put: struct { slot: usize, value: u8 },
27 commit,
28 checkpoint,
29 };
30
31 const State = [property_page_count]?u8;
32
33 const Boundary = struct {
34 effects: usize,
35 state: State,
36 };
37
38 const CommitRange = struct {
39 start: usize,
40 end: usize,
41 state: State,
42 };
43
44 const RunRecord = struct {
45 boundaries: [max_boundaries]Boundary = undefined,
46 boundary_count: usize = 0,
47 commits: [max_plan_steps]CommitRange = undefined,
48 commit_count: usize = 0,
49
50 fn pushBoundary(self: *RunRecord, boundary: Boundary) void {
51 std.debug.assert(self.boundary_count < max_boundaries);
52 self.boundaries[self.boundary_count] = boundary;
53 self.boundary_count += 1;
54 }
55
56 fn pushCommit(self: *RunRecord, commit: CommitRange) void {
57 std.debug.assert(self.commit_count < max_plan_steps);
58 self.commits[self.commit_count] = commit;
59 self.commit_count += 1;
60 }
61
62 fn boundarySlice(self: *const RunRecord) []const Boundary {
63 return self.boundaries[0..self.boundary_count];
64 }
65
66 fn commitSlice(self: *const RunRecord) []const CommitRange {
67 return self.commits[0..self.commit_count];
68 }
69 };
70
71 const Scenario = struct {
72 ops: [max_plan_steps]Op,
73 op_count: usize,
74 fail_at: usize,
75 byte_cut: usize,
76
77 fn plan(self: *const Scenario) []const Op {
78 std.debug.assert(self.op_count > 0);
79 std.debug.assert(self.op_count <= max_plan_steps);
80 return self.ops[0..self.op_count];
81 }
82 };
83
84 const PlanTraits = struct {
85 noop_action: bool,
86 all_slots: bool,
87 checkpoint_ending: bool,
88 };
89
90 var plan_coverage = hypothesis.Coverage{};
91 var crash_coverage = hypothesis.Coverage{};
92
93 fn testHeader() sql.wal.Header {
94 return .{
95 .sequence = 41,
96 .salt = .{ .first = 0xc0de_f11e, .second = 0x0b5e_55ed },
97 };
98 }
99
100 fn fillImage(image: *[page.size]u8, slot: usize, value: u8) void {
101 @memset(image, 0);
102 image[0] = @intCast(slot + 1);
103 image[1] = value;
104 }
105
106 fn runPlan(
107 allocator: std.mem.Allocator,
108 dir: std.Io.Dir,
109 plan: []const Op,
110 record: ?*RunRecord,
111 ) !void {
112 var database = try file.Database.openForTesting(allocator, dir, .{ .io = fault.io, .header = testHeader() });
113 defer database.deinit();
114
115 var current: State = @splat(null);
116 var pending: State = @splat(null);
117 var transaction: ?file.Transaction = null;
118 defer if (transaction) |*open_transaction| open_transaction.deinit();
119
120 if (record) |target| {
121 target.pushBoundary(.{ .effects = fault.gate.effects, .state = current });
122 }
123
124 for (plan) |op| {
125 switch (op) {
126 .put => |put| {
127 if (transaction == null) {
128 transaction = try database.beginWrite();
129 pending = current;
130 }
131 var image: [page.size]u8 = undefined;
132 fillImage(&image, put.slot, put.value);
133 try transaction.?.putPage(@intCast(put.slot + 1), &image);
134 pending[put.slot] = put.value;
135 },
136 .commit => {
137 var open_transaction = transaction orelse continue;
138 transaction = null;
139 const start = fault.gate.effects;
140 const target_state = pending;
141 defer open_transaction.deinit();
142 _ = try open_transaction.commit(.{});
143 current = target_state;
144 if (record) |target| {
145 target.pushCommit(.{
146 .start = start,
147 .end = fault.gate.effects,
148 .state = target_state,
149 });
150 target.pushBoundary(.{ .effects = fault.gate.effects, .state = current });
151 }
152 },
153 .checkpoint => {
154 if (transaction != null) continue;
155 _ = try database.checkpoint(.{ .restart_header = testHeader() });
156 },
157 }
158 }
159 }
160
161 fn matches(left: State, right: State) bool {
162 for (left, right) |left_value, right_value| {
163 const left_present = left_value != null;
164 const right_present = right_value != null;
165 if (left_present != right_present) return false;
166 if (left_present and left_value.? != right_value.?) return false;
167 }
168 return true;
169 }
170
171 fn drawUsize(conjecture: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
172 return @intCast(try conjecture.drawInteger(
173 @intCast(min),
174 @intCast(max),
175 @intCast(shrink_towards),
176 ));
177 }
178
179 fn drawPlan(conjecture: *hypothesis.ConjectureData, scenario: *Scenario) !void {
180 const steps = try drawUsize(conjecture, 1, max_plan_steps, 4);
181 const weights = try hypothesis.swarm.draw(Action, conjecture, .{});
182 var step: usize = 0;
183 while (step < steps) : (step += 1) {
184 scenario.ops[step] = switch (try weights.choose(conjecture)) {
185 .put => .{ .put = .{
186 .slot = try drawUsize(conjecture, 0, property_page_count - 1, 0),
187 .value = @intCast(try drawUsize(conjecture, 0, 255, 0)),
188 } },
189 .commit => .commit,
190 .checkpoint => .checkpoint,
191 };
192 }
193 scenario.op_count = steps;
194 }
195
196 fn planTraits(plan: []const Op) PlanTraits {
197 std.debug.assert(plan.len > 0);
198 var open = false;
199 var noop = false;
200 var slots: u4 = 0;
201 for (plan) |op| {
202 switch (op) {
203 .put => |put| {
204 open = true;
205 slots |= @as(u4, 1) << @intCast(put.slot);
206 },
207 .commit => {
208 if (open) open = false else noop = true;
209 },
210 .checkpoint => {
211 if (open) noop = true;
212 },
213 }
214 }
215 return .{
216 .noop_action = noop,
217 .all_slots = slots == 0b1111,
218 .checkpoint_ending = plan[plan.len - 1] == .checkpoint,
219 };
220 }
221
222 fn recordPlanCoverage(counters: *hypothesis.Coverage, plan: []const Op) void {
223 const traits = planTraits(plan);
224 counters.record(.valid);
225 if (traits.noop_action) counters.record(.invalid);
226 if (traits.checkpoint_ending) counters.record(.boundary);
227 if (traits.all_slots) counters.record(.large_state);
228 }
229
230 fn recordCrashCoverage(
231 counters: *hypothesis.Coverage,
232 record: *const RunRecord,
233 fail_at: usize,
234 ) void {
235 std.debug.assert(record.boundary_count > 0);
236 counters.record(.valid);
237 if (fail_at < record.boundaries[0].effects) counters.record(.invalid);
238 var torn = false;
239 for (record.commitSlice()) |commit| {
240 if (commit.start <= fail_at and fail_at < commit.end) torn = true;
241 }
242 if (torn) counters.record(.boundary);
243 const last = record.boundaries[record.boundary_count - 1].effects;
244 if (fail_at >= last) counters.record(.large_state);
245 }
246
247 fn countPlan(
248 allocator: std.mem.Allocator,
249 plan: []const Op,
250 record: *RunRecord,
251 ) !usize {
252 var count_tmp = std.testing.tmpDir(.{});
253 defer count_tmp.cleanup();
254 fault.gate.reset(.count, 0, 0);
255 defer fault.gate.reset(.off, 0, 0);
256 try runPlan(allocator, count_tmp.dir, plan, record);
257 const total_effects = fault.gate.effects;
258 try std.testing.expect(total_effects > 0);
259 return total_effects;
260 }
261
262 fn crashAndVerify(
263 allocator: std.mem.Allocator,
264 scenario: *const Scenario,
265 record: *const RunRecord,
266 ) !void {
267 var crash_tmp = std.testing.tmpDir(.{});
268 defer crash_tmp.cleanup();
269 fault.gate.reset(.crash, scenario.fail_at, scenario.byte_cut);
270 defer fault.gate.reset(.off, 0, 0);
271 runPlan(allocator, crash_tmp.dir, scenario.plan(), null) catch |err| switch (err) {
272 error.InputOutput, error.HardwareFailure, error.Unexpected => {},
273 else => return err,
274 };
275 fault.gate.reset(.off, 0, 0);
276
277 var database = try file.Database.openForTesting(allocator, crash_tmp.dir, .{ .header = testHeader() });
278 defer database.deinit();
279 var read = try database.beginRead();
280 defer read.deinit();
281 const snapshot = read.snapshot();
282
283 var recovered: State = @splat(null);
284 var slot: usize = 0;
285 while (slot < property_page_count) : (slot += 1) {
286 var image: [page.size]u8 = undefined;
287 if (try snapshot.copyPage(@intCast(slot + 1), &image) and image[0] != 0) {
288 recovered[slot] = image[1];
289 }
290 }
291
292 var durable: State = @splat(null);
293 for (record.boundarySlice()) |boundary| {
294 if (boundary.effects <= scenario.fail_at) durable = boundary.state;
295 }
296 var in_flight: ?State = null;
297 for (record.commitSlice()) |commit| {
298 if (commit.start <= scenario.fail_at and scenario.fail_at < commit.end) {
299 in_flight = commit.state;
300 }
301 }
302
303 const acceptable = matches(recovered, durable) or
304 (in_flight != null and matches(recovered, in_flight.?));
305 try std.testing.expect(acceptable);
306 }
307
308 fn checkScenario(allocator: std.mem.Allocator, scenario: *const Scenario) !void {
309 var record = RunRecord{};
310 const total_effects = try countPlan(allocator, scenario.plan(), &record);
311 if (scenario.fail_at >= total_effects) return error.StaleScenarioArtifact;
312 try crashAndVerify(allocator, scenario, &record);
313 }
314
315 fn encodeScenario(
316 scenario: *const Scenario,
317 buffer: *[max_scenario_payload]u8,
318 ) []const u8 {
319 std.debug.assert(scenario.byte_cut <= page.size);
320 std.mem.writeInt(u32, buffer[0..4], @intCast(scenario.op_count), .little);
321 var offset: usize = 4;
322 for (scenario.plan()) |op| {
323 switch (op) {
324 .put => |put| {
325 std.debug.assert(put.slot < property_page_count);
326 buffer[offset] = 0;
327 buffer[offset + 1] = @intCast(put.slot);
328 buffer[offset + 2] = put.value;
329 offset += 3;
330 },
331 .commit => {
332 buffer[offset] = 1;
333 offset += 1;
334 },
335 .checkpoint => {
336 buffer[offset] = 2;
337 offset += 1;
338 },
339 }
340 }
341 std.mem.writeInt(u64, buffer[offset..][0..8], @intCast(scenario.fail_at), .little);
342 std.mem.writeInt(u32, buffer[offset + 8 ..][0..4], @intCast(scenario.byte_cut), .little);
343 return buffer[0 .. offset + 12];
344 }
345
346 fn decodeScenario(payload: []const u8) error{InvalidScenario}!Scenario {
347 if (payload.len < 4) return error.InvalidScenario;
348 const op_count: usize = std.mem.readInt(u32, payload[0..4], .little);
349 if (op_count == 0 or op_count > max_plan_steps) return error.InvalidScenario;
350 var scenario = Scenario{ .ops = undefined, .op_count = op_count, .fail_at = 0, .byte_cut = 0 };
351 var offset: usize = 4;
352 var index: usize = 0;
353 while (index < op_count) : (index += 1) {
354 if (offset >= payload.len) return error.InvalidScenario;
355 switch (payload[offset]) {
356 0 => {
357 if (payload.len - offset < 3) return error.InvalidScenario;
358 const slot = payload[offset + 1];
359 if (slot >= property_page_count) return error.InvalidScenario;
360 scenario.ops[index] = .{ .put = .{ .slot = slot, .value = payload[offset + 2] } };
361 offset += 3;
362 },
363 1 => {
364 scenario.ops[index] = .commit;
365 offset += 1;
366 },
367 2 => {
368 scenario.ops[index] = .checkpoint;
369 offset += 1;
370 },
371 else => return error.InvalidScenario,
372 }
373 }
374 if (payload.len - offset != 12) return error.InvalidScenario;
375 const fail_at = std.mem.readInt(u64, payload[offset..][0..8], .little);
376 if (fail_at > std.math.maxInt(u32)) return error.InvalidScenario;
377 scenario.fail_at = @intCast(fail_at);
378 const byte_cut: usize = std.mem.readInt(u32, payload[offset + 8 ..][0..4], .little);
379 if (byte_cut > page.size) return error.InvalidScenario;
380 scenario.byte_cut = byte_cut;
381 return scenario;
382 }
383
384 fn saveScenarioArtifact(path: []const u8, scenario: *const Scenario) !void {
385 var buffer: [max_scenario_payload]u8 = undefined;
386 const payload = encodeScenario(scenario, &buffer);
387 try hypothesis.artifact.save(path, .{
388 .schema = scenario_schema,
389 .revision = generator_revision,
390 }, payload);
391 }
392
393 fn replayScenarioArtifact(allocator: std.mem.Allocator, path: []const u8) !void {
394 var storage: [max_scenario_artifact]u8 = undefined;
395 const entry = (try hypothesis.artifact.load(path, &storage)) orelse return;
396 if (!std.mem.eql(u8, entry.metadata.schema, scenario_schema)) {
397 return error.UnsupportedScenarioSchema;
398 }
399 const scenario = try decodeScenario(entry.payload);
400 try checkScenario(allocator, &scenario);
401 }
402
403 test "property: ordinary file database fences a failed WAL sync" {
404 var tmp = std.testing.tmpDir(.{});
405 defer tmp.cleanup();
406 fault.gate.reset(.off, 0, 0);
407 defer fault.gate.reset(.off, 0, 0);
408
409 var database = try file.Database.openForTesting(std.testing.allocator, tmp.dir, .{
410 .io = fault.io,
411 .header = testHeader(),
412 });
413 defer database.deinit();
414 var image: [page.size]u8 = undefined;
415 fillImage(&image, 0, 91);
416 var transaction = try database.beginWrite();
417 defer transaction.deinit();
418 try transaction.putPage(1, &image);
419 _ = try transaction.commit(.{ .durability = .buffered });
420 fault.gate.resetFile(.once, 0, 0, database.wal_file);
421 try std.testing.expectError(error.InputOutput, database.syncWal());
422 fault.gate.reset(.off, 0, 0);
423 try std.testing.expect(database.requiresRecovery());
424 try std.testing.expectError(error.RecoveryRequired, database.beginRead());
425 }
426
427 pub const CrashRecoveryProperty = struct {
428 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
429 var scenario = Scenario{ .ops = undefined, .op_count = 0, .fail_at = 0, .byte_cut = 0 };
430 try drawPlan(conjecture, &scenario);
431 recordPlanCoverage(&plan_coverage, scenario.plan());
432
433 var record = RunRecord{};
434 const total_effects = try countPlan(allocator, scenario.plan(), &record);
435 scenario.fail_at = try drawUsize(conjecture, 0, total_effects - 1, 0);
436 scenario.byte_cut = try drawUsize(conjecture, 0, page.size, 0);
437 recordCrashCoverage(&crash_coverage, &record, scenario.fail_at);
438
439 crashAndVerify(allocator, &scenario, &record) catch |err| {
440 saveScenarioArtifact(scenario_artifact_path, &scenario) catch {};
441 return err;
442 };
443 }
444 };
445
446 test "property: file recovery restores a committed state after a crash at any durable effect" {
447 if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
448
449 try replayScenarioArtifact(std.testing.allocator, scenario_artifact_path);
450 try hypothesis.checkNamed(
451 CrashRecoveryProperty,
452 "sql-file-crash-recovery",
453 hypothesis.Settings.quick()
454 .withSeed(0x5EED_CA5B)
455 .withDatabase("zig-out/hypothesis-failures/sql"),
456 );
457 try plan_coverage.require(.{ .valid = 25, .invalid = 1, .boundary = 1, .large_state = 1 });
458 try crash_coverage.require(.{ .valid = 25, .invalid = 1, .boundary = 1, .large_state = 1 });
459 }
460
461 test "property: swarm weights reach checkpoint-ending plans" {
462 var counters = hypothesis.Coverage{};
463 var data = hypothesis.ConjectureData.init(std.testing.allocator, 0);
464 defer data.deinit();
465 var example: u64 = 0;
466 while (example < 25) : (example += 1) {
467 data.reset(0x5EED_CA5B +% example);
468 var scenario = Scenario{ .ops = undefined, .op_count = 0, .fail_at = 0, .byte_cut = 0 };
469 try drawPlan(&data, &scenario);
470 recordPlanCoverage(&counters, scenario.plan());
471 }
472 try counters.require(.{ .valid = 25, .boundary = 1 });
473 }
474
475 test "property: scenario artifact replay survives a generator revision change" {
476 if (!@import("sql_test_options").run_property_tests) return error.SkipZigTest;
477 const allocator = std.testing.allocator;
478 var tmp = std.testing.tmpDir(.{});
479 defer tmp.cleanup();
480 const dir_path = try tmp.dir.realPathFileAlloc(std.Options.debug_io, ".", allocator);
481 defer allocator.free(dir_path);
482 var path_buffer: [std.fs.max_path_bytes]u8 = undefined;
483 const path = try std.fmt.bufPrint(&path_buffer, "{s}/scenario.jhma", .{dir_path});
484
485 var saved = Scenario{ .ops = undefined, .op_count = 3, .fail_at = 0, .byte_cut = 7 };
486 saved.ops[0] = .{ .put = .{ .slot = 2, .value = 17 } };
487 saved.ops[1] = .commit;
488 saved.ops[2] = .checkpoint;
489 var record = RunRecord{};
490 const total_effects = try countPlan(allocator, saved.plan(), &record);
491 saved.fail_at = total_effects - 1;
492
493 var buffer: [max_scenario_payload]u8 = undefined;
494 try hypothesis.artifact.save(path, .{
495 .schema = scenario_schema,
496 .revision = "fixed-weight-suffix-v1",
497 }, encodeScenario(&saved, &buffer));
498
499 var storage: [max_scenario_artifact]u8 = undefined;
500 const entry = (try hypothesis.artifact.load(path, &storage)).?;
501 try std.testing.expectEqualStrings(scenario_schema, entry.metadata.schema);
502 try std.testing.expect(!std.mem.eql(u8, generator_revision, entry.metadata.revision));
503 const decoded = try decodeScenario(entry.payload);
504 try std.testing.expectEqual(saved.op_count, decoded.op_count);
505 for (saved.plan(), decoded.plan()) |expected, actual| {
506 try std.testing.expect(std.meta.eql(expected, actual));
507 }
508 try std.testing.expectEqual(saved.fail_at, decoded.fail_at);
509 try std.testing.expectEqual(saved.byte_cut, decoded.byte_cut);
510
511 try replayScenarioArtifact(allocator, path);
512 }
513
514 test "property: scenario decode rejects out-of-domain payloads" {
515 var scenario = Scenario{ .ops = undefined, .op_count = 2, .fail_at = 3, .byte_cut = 9 };
516 scenario.ops[0] = .{ .put = .{ .slot = 1, .value = 5 } };
517 scenario.ops[1] = .checkpoint;
518 var buffer: [max_scenario_payload]u8 = undefined;
519 const payload = encodeScenario(&scenario, &buffer);
520 const decoded = try decodeScenario(payload);
521 try std.testing.expectEqual(scenario.fail_at, decoded.fail_at);
522
523 var mutated: [max_scenario_payload]u8 = undefined;
524 const copy = mutated[0..payload.len];
525 @memcpy(copy, payload);
526 copy[4] = 3;
527 try std.testing.expectError(error.InvalidScenario, decodeScenario(copy));
528 @memcpy(copy, payload);
529 copy[5] = property_page_count;
530 try std.testing.expectError(error.InvalidScenario, decodeScenario(copy));
531 @memcpy(copy, payload);
532 std.mem.writeInt(u32, copy[0..4], max_plan_steps + 1, .little);
533 try std.testing.expectError(error.InvalidScenario, decodeScenario(copy));
534 @memcpy(copy, payload);
535 std.mem.writeInt(u32, copy[payload.len - 4 ..][0..4], page.size + 1, .little);
536 try std.testing.expectError(error.InvalidScenario, decodeScenario(copy));
537 const truncated = payload[0 .. payload.len - 1];
538 try std.testing.expectError(error.InvalidScenario, decodeScenario(truncated));
539 }