lib/sql/src/properties/history.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const pretty = @import("pretty");
4 const sql = @import("sql");
5
6 const io = std.Options.debug_io;
7
8 fn writeImage(dir: std.Io.Dir, path: []const u8, bytes: []const u8) !void {
9 var file = try dir.createFile(io, path, .{ .read = true, .truncate = true });
10 defer file.close(io);
11 try file.writePositionalAll(io, bytes, 0);
12 try file.setLength(io, bytes.len);
13 }
14
15 const Prefix = struct {
16 length: usize,
17 commits: usize,
18 head: ?sql.Hash,
19 };
20
21 fn validPrefix(boundaries: []const Prefix, length: usize) Prefix {
22 var valid = Prefix{ .length = 0, .commits = 0, .head = null };
23 for (boundaries) |boundary| {
24 if (boundary.length > length) break;
25 valid = boundary;
26 }
27 return valid;
28 }
29
30 fn expectRecovery(recovery: sql.HistoryRecovery, original_length: usize, valid_length: usize) !void {
31 switch (recovery) {
32 .clean => try std.testing.expectEqual(original_length, valid_length),
33 .truncated => |truncation| {
34 try std.testing.expect(original_length != valid_length);
35 try std.testing.expectEqual(original_length, truncation.original_length);
36 try std.testing.expectEqual(valid_length, truncation.valid_length);
37 },
38 }
39 }
40
41 fn expectState(history: *const sql.History, expected: Prefix) !void {
42 const commits = try history.commitEntries(std.testing.allocator);
43 defer std.testing.allocator.free(commits);
44 try std.testing.expectEqual(expected.commits, commits.len);
45 const head = if ((try history.ref("main"))) |ref_value| ref_value.target else null;
46 if (expected.head) |expected_head| {
47 try std.testing.expect(head != null);
48 try std.testing.expect(sql.version.same(expected_head, head.?));
49 } else {
50 try std.testing.expect(head == null);
51 }
52 }
53
54 fn verifyPrefix(dir: std.Io.Dir, path: []const u8, original_length: usize, expected: Prefix) !void {
55 if (original_length == expected.length) {
56 var history = try sql.History.open(std.testing.allocator, dir, .{
57 .path = path,
58 .create = false,
59 .recovery = .reject,
60 });
61 defer history.deinit();
62 try expectRecovery(history.recovery, original_length, expected.length);
63 try std.testing.expectEqual(expected.length, history.len());
64 try expectState(&history, expected);
65 return;
66 }
67
68 try std.testing.expectError(error.TruncatedHistory, sql.History.open(std.testing.allocator, dir, .{
69 .path = path,
70 .create = false,
71 .recovery = .reject,
72 }));
73 try std.testing.expectEqual(original_length, @as(usize, @intCast((try dir.statFile(io, path, .{})).size)));
74 var history = try sql.History.open(std.testing.allocator, dir, .{
75 .path = path,
76 .create = false,
77 .recovery = .truncate,
78 });
79 defer history.deinit();
80 try expectRecovery(history.recovery, original_length, expected.length);
81 try std.testing.expectEqual(expected.length, history.len());
82 try expectState(&history, expected);
83 try std.testing.expectEqual(expected.length, @as(usize, @intCast((try dir.statFile(io, path, .{})).size)));
84 }
85
86 test "property: history recovery reports the exact valid prefix under truncation and flips" {
87 var tmp = std.testing.tmpDir(.{});
88 defer tmp.cleanup();
89
90 var boundaries: [4]Prefix = undefined;
91 const first = sql.Commit.init(sql.version.emptyHash("history-corruption-first"), &.{});
92 var second_parents = [_]sql.Hash{first.hash};
93 const second = sql.Commit.init(sql.version.emptyHash("history-corruption-second"), second_parents[0..]);
94 {
95 var history = try sql.History.open(std.testing.allocator, tmp.dir, .{
96 .path = "source.history",
97 .recovery = .reject,
98 });
99 defer history.deinit();
100 try history.putCommit(first);
101 boundaries[0] = .{ .length = history.len(), .commits = 1, .head = null };
102 try history.putCommit(second);
103 boundaries[1] = .{ .length = history.len(), .commits = 2, .head = null };
104 try history.putRef(.{ .name = "main", .target = first.hash });
105 boundaries[2] = .{ .length = history.len(), .commits = 2, .head = first.hash };
106 try history.putRef(.{ .name = "main", .target = second.hash });
107 boundaries[3] = .{ .length = history.len(), .commits = 2, .head = second.hash };
108 }
109
110 const source = try tmp.dir.readFileAlloc(io, "source.history", std.testing.allocator, .unlimited);
111 defer std.testing.allocator.free(source);
112
113 var length: usize = 0;
114 while (length <= source.len) : (length += 1) {
115 try writeImage(tmp.dir, "truncated.history", source[0..length]);
116 try verifyPrefix(tmp.dir, "truncated.history", length, validPrefix(boundaries[0..], length));
117 }
118
119 const flipped = try std.testing.allocator.dupe(u8, source);
120 defer std.testing.allocator.free(flipped);
121 for (flipped, 0..) |*byte, index| {
122 byte.* ^= 0xff;
123 try writeImage(tmp.dir, "flipped.history", flipped);
124 const expected = validPrefix(boundaries[0..], index);
125 if (expected.length == 0) {
126 if (sql.History.open(std.testing.allocator, tmp.dir, .{
127 .path = "flipped.history",
128 .create = false,
129 .recovery = .reject,
130 })) |opened| {
131 var history = opened;
132 history.deinit();
133 return error.TestUnexpectedResult;
134 } else |err| switch (err) {
135 error.InvalidHistory => {},
136 error.TruncatedHistory => try verifyPrefix(tmp.dir, "flipped.history", source.len, expected),
137 else => return err,
138 }
139 } else {
140 try verifyPrefix(tmp.dir, "flipped.history", source.len, expected);
141 }
142 byte.* ^= 0xff;
143 }
144 }
145
146 const RecoveryProbe = struct {
147 checks: usize = 0,
148
149 fn control(self: *RecoveryProbe) sql.wal.Control {
150 return .{ .context = self, .interrupted_fn = count };
151 }
152
153 fn count(context: ?*anyopaque) bool {
154 const self: *RecoveryProbe = @ptrCast(@alignCast(context.?));
155 self.checks += 1;
156 return false;
157 }
158 };
159
160 const RecoveryCut = struct {
161 target: usize,
162 checks: usize = 0,
163 fired: bool = false,
164
165 fn control(self: *RecoveryCut) sql.wal.Control {
166 return .{ .context = self, .interrupted_fn = interrupt };
167 }
168
169 fn interrupt(context: ?*anyopaque) bool {
170 const self: *RecoveryCut = @ptrCast(@alignCast(context.?));
171 if (self.checks == self.target) {
172 self.fired = true;
173 return true;
174 }
175 self.checks += 1;
176 return false;
177 }
178 };
179
180 const ReplayScenario = struct {
181 commits: usize = 0,
182 durable_length: usize = 0,
183 available_checks: usize = 0,
184 first_cut: usize = 0,
185 second_cut: usize = 0,
186 };
187
188 var replay_coverage = hypothesis.Coverage{};
189
190 fn replaySettings() hypothesis.Settings {
191 var value = hypothesis.Settings.quick()
192 .withSeed(0x7371_6c2d_7265_706c)
193 .withDatabase("zig-out/hypothesis-failures/sql-history-replay-interruption");
194 value.max_examples = 80;
195 value.target_examples = 80;
196 return value;
197 }
198
199 fn expectInterruptedReplay(
200 allocator: std.mem.Allocator,
201 dir: std.Io.Dir,
202 cut: *RecoveryCut,
203 ) !void {
204 if (sql.History.open(allocator, dir, .{
205 .path = "interrupted.history",
206 .create = false,
207 .recovery = .reject,
208 .control = cut.control(),
209 })) |opened| {
210 var history = opened;
211 history.deinit();
212 return error.InterruptionNotReached;
213 } else |err| switch (err) {
214 error.Interrupted => {},
215 else => return err,
216 }
217 if (!cut.fired) return error.InterruptionNotReached;
218 }
219
220 fn diagnoseReplay(
221 allocator: std.mem.Allocator,
222 scenario: ReplayScenario,
223 err: anyerror,
224 ) void {
225 var arena_state = std.heap.ArenaAllocator.init(allocator);
226 defer arena_state.deinit();
227 var report = pretty.diagnostic.Report.init(
228 arena_state.allocator(),
229 "SQL interrupted history replay property failed",
230 ) catch return;
231 defer report.deinit();
232 report.field("error", "{s}", .{@errorName(err)}) catch return;
233 report.field("commits", "{d}", .{scenario.commits}) catch return;
234 report.field("durable length", "{d}", .{scenario.durable_length}) catch return;
235 report.field("available checks", "{d}", .{scenario.available_checks}) catch return;
236 report.field("first cut", "{d}", .{scenario.first_cut}) catch return;
237 report.field("second cut", "{d}", .{scenario.second_cut}) catch return;
238 pretty.diagnostic.writeStderr(&report, .{ .width = 100 });
239 }
240
241 const InterruptedReplayConverges = struct {
242 pub fn property(data: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
243 var scenario = ReplayScenario{};
244 run(data, allocator, &scenario) catch |err| {
245 diagnoseReplay(allocator, scenario, err);
246 return err;
247 };
248 }
249
250 fn run(
251 data: *hypothesis.ConjectureData,
252 allocator: std.mem.Allocator,
253 scenario: *ReplayScenario,
254 ) !void {
255 var tmp = std.testing.tmpDir(.{});
256 defer tmp.cleanup();
257
258 const roots = [_][]const u8{
259 "interrupted-replay-a",
260 "interrupted-replay-b",
261 "interrupted-replay-c",
262 "interrupted-replay-d",
263 "interrupted-replay-e",
264 "interrupted-replay-f",
265 "interrupted-replay-g",
266 "interrupted-replay-h",
267 };
268 scenario.commits = @intCast(try data.drawInteger(1, roots.len, 1));
269 var expected_head: sql.Hash = undefined;
270 {
271 var history = try sql.History.open(allocator, tmp.dir, .{
272 .path = "interrupted.history",
273 .recovery = .reject,
274 });
275 defer history.deinit();
276 for (roots[0..scenario.commits], 0..) |root_name, index| {
277 const root = sql.version.emptyHash(root_name);
278 var parents = [_]sql.Hash{expected_head};
279 const commit = sql.Commit.init(
280 root,
281 if (index == 0) &.{} else parents[0..],
282 );
283 try history.putCommit(commit);
284 expected_head = commit.hash;
285 }
286 try history.putRef(.{ .name = "main", .target = expected_head });
287 scenario.durable_length = history.len();
288 }
289
290 var probe = RecoveryProbe{};
291 {
292 var history = try sql.History.open(allocator, tmp.dir, .{
293 .path = "interrupted.history",
294 .create = false,
295 .recovery = .reject,
296 .control = probe.control(),
297 });
298 history.deinit();
299 }
300 try std.testing.expect(probe.checks > 0);
301 scenario.available_checks = probe.checks;
302 scenario.first_cut = @intCast(try data.drawInteger(0, probe.checks - 1, 0));
303 scenario.second_cut = @intCast(try data.drawInteger(0, probe.checks - 1, probe.checks - 1));
304
305 var first = RecoveryCut{ .target = scenario.first_cut };
306 try expectInterruptedReplay(allocator, tmp.dir, &first);
307 var second = RecoveryCut{ .target = scenario.second_cut };
308 try expectInterruptedReplay(allocator, tmp.dir, &second);
309
310 var recovered = try sql.History.open(allocator, tmp.dir, .{
311 .path = "interrupted.history",
312 .create = false,
313 .recovery = .reject,
314 });
315 defer recovered.deinit();
316 try expectState(&recovered, .{
317 .length = scenario.durable_length,
318 .commits = scenario.commits,
319 .head = expected_head,
320 });
321 try std.testing.expectEqual(scenario.durable_length, recovered.len());
322
323 replay_coverage.record(.valid);
324 if (scenario.first_cut == 0 or scenario.second_cut + 1 == probe.checks) {
325 replay_coverage.record(.boundary);
326 }
327 if (scenario.commits >= 6) replay_coverage.record(.large_state);
328 }
329 };
330
331 test "property: two interrupted history replays converge to the durable head" {
332 replay_coverage = .{};
333 try hypothesis.checkNamed(
334 InterruptedReplayConverges,
335 "sql-history-replay-interruption-convergence",
336 replaySettings(),
337 );
338 try replay_coverage.require(.{ .valid = 1, .boundary = 1, .large_state = 1 });
339 }
340
341 fn byteRangeSettings() hypothesis.Settings {
342 var value = hypothesis.Settings.quick()
343 .withSeed(0x7371_6c2d_6279_7465)
344 .withDatabase("zig-out/hypothesis-failures/sql-history-byte-range");
345 value.max_examples = 1_000;
346 value.target_examples = 1_000;
347 return value;
348 }
349
350 fn drawRangeFactor(
351 data: *hypothesis.ConjectureData,
352 center: u64,
353 ) !u64 {
354 return switch (try data.drawInteger(0, 4, 0)) {
355 0 => try data.drawInteger(0, std.math.maxInt(u64), 0),
356 1 => try data.drawInteger(center -| 1_024, center +| 1_024, center),
357 2 => try data.drawInteger(0, center *| 2, center),
358 3 => std.math.maxInt(u64) - try data.drawInteger(0, 1_024, 0),
359 4 => try data.drawInteger(0, 1_000_000, 0),
360 else => unreachable,
361 };
362 }
363
364 fn expectByteRange(units_per_second: u64, lifetime_seconds: u64) !void {
365 const Range = sql.History.ByteRange;
366 const expected = @as(u128, Range.unit_precision_bytes) *
367 @as(u128, units_per_second) * @as(u128, lifetime_seconds);
368 const actual = Range.total(units_per_second, lifetime_seconds);
369 if (expected > std.math.maxInt(u64)) {
370 try std.testing.expectEqual(@as(?u64, null), actual);
371 return;
372 }
373 try std.testing.expectEqual(@as(u64, @intCast(expected)), actual.?);
374 }
375
376 const HistoryByteRangeProperty = struct {
377 pub fn property(
378 data: *hypothesis.ConjectureData,
379 _: std.mem.Allocator,
380 ) !void {
381 const Range = sql.History.ByteRange;
382 const units_per_second = try drawRangeFactor(
383 data,
384 Range.maximum_units_per_second,
385 );
386 const lifetime_seconds = try drawRangeFactor(
387 data,
388 Range.service_lifetime_seconds,
389 );
390 try expectByteRange(units_per_second, lifetime_seconds);
391 if (units_per_second != std.math.maxInt(u64)) {
392 const lower = Range.total(units_per_second, lifetime_seconds);
393 const upper = Range.total(units_per_second + 1, lifetime_seconds);
394 if (lower != null and upper != null) try std.testing.expect(lower.? <= upper.?);
395 }
396 }
397 };
398
399 test "property: history byte range covers declared scale and overflow boundary" {
400 const Range = sql.History.ByteRange;
401 try std.testing.expectEqual(
402 Range.budget_bytes,
403 Range.total(Range.maximum_units_per_second, Range.service_lifetime_seconds).?,
404 );
405 const maximum_safe_seconds = std.math.maxInt(u64) /
406 Range.maximum_units_per_second;
407 try std.testing.expect(Range.total(
408 Range.maximum_units_per_second,
409 maximum_safe_seconds,
410 ) != null);
411 try std.testing.expect(Range.total(
412 Range.maximum_units_per_second,
413 maximum_safe_seconds + 1,
414 ) == null);
415 try std.testing.expect(
416 @as(u128, Range.budget_bytes) + @as(u128, Range.maximum_append_bytes) <=
417 std.math.maxInt(Range.Count),
418 );
419 try std.testing.expect(@bitSizeOf(usize) >= @bitSizeOf(Range.Count));
420 }
421
422 test "property: history byte range scales exactly and rejects overflow" {
423 try hypothesis.checkNamed(
424 HistoryByteRangeProperty,
425 "sql-history-byte-range",
426 byteRangeSettings(),
427 );
428 }
429
430 const SegmentRange = sql.history.segment.SegmentRange;
431 const EventRange = sql.history.segment.EventRange;
432 const PageRange = sql.history.segment.manifest.PageRange;
433
434 fn segmentedRangeSettings() hypothesis.Settings {
435 var value = hypothesis.Settings.quick()
436 .withSeed(0x7371_6c2d_7365_676d)
437 .withDatabase("zig-out/hypothesis-failures/sql-segmented-range");
438 value.max_examples = 1_000;
439 value.target_examples = 1_000;
440 return value;
441 }
442
443 fn expectUnsignedTotal(
444 comptime Range: type,
445 unit_precision: u64,
446 rate: u64,
447 lifetime: u64,
448 ) !void {
449 const expected = @as(u128, unit_precision) *
450 @as(u128, rate) * @as(u128, lifetime);
451 const actual = Range.total(rate, lifetime);
452 if (expected > std.math.maxInt(u64)) {
453 try std.testing.expectEqual(@as(?u64, null), actual);
454 return;
455 }
456 try std.testing.expectEqual(@as(u64, @intCast(expected)), actual.?);
457 if (rate == std.math.maxInt(u64)) return;
458 const upper = Range.total(rate + 1, lifetime);
459 if (upper != null) try std.testing.expect(actual.? <= upper.?);
460 }
461
462 fn expectPageTotal(segments_per_second: u64, lifetime_seconds: u64) !void {
463 const segment_count = @as(u128, PageRange.unit_precision_segments) *
464 @as(u128, segments_per_second) * @as(u128, lifetime_seconds);
465 const expected = if (segment_count == 0) 0 else (segment_count - 1) / @as(u128, PageRange.segments_per_page) + 1;
466 const actual = PageRange.total(segments_per_second, lifetime_seconds);
467 if (expected > std.math.maxInt(u64)) {
468 try std.testing.expectEqual(@as(?u64, null), actual);
469 return;
470 }
471 try std.testing.expectEqual(@as(u64, @intCast(expected)), actual.?);
472 if (segments_per_second == std.math.maxInt(u64)) return;
473 const upper = PageRange.total(segments_per_second + 1, lifetime_seconds);
474 if (upper != null) try std.testing.expect(actual.? <= upper.?);
475 }
476
477 fn checkSegmentAdvance(data: *hypothesis.ConjectureData) !void {
478 const current = try drawRangeFactor(data, SegmentRange.budget_segments);
479 const actual = SegmentRange.advance(current);
480 if (current < SegmentRange.budget_segments) {
481 try std.testing.expectEqual(current + 1, actual.?);
482 } else try std.testing.expectEqual(@as(?u64, null), actual);
483 }
484
485 fn checkPageAdvance(data: *hypothesis.ConjectureData) !void {
486 const current = try drawRangeFactor(data, PageRange.budget_pages);
487 const increment = try data.drawInteger(0, 2, 1);
488 const actual = PageRange.advance(current, increment);
489 const expected = @as(u128, current) + @as(u128, increment);
490 if (current > 0 and current <= PageRange.budget_pages and
491 increment <= PageRange.maximum_increment_pages and
492 expected <= PageRange.budget_pages)
493 {
494 try std.testing.expectEqual(@as(u64, @intCast(expected)), actual.?);
495 } else try std.testing.expectEqual(@as(?u64, null), actual);
496 }
497
498 fn checkEventAdvance(data: *hypothesis.ConjectureData) !void {
499 const current = try drawRangeFactor(data, EventRange.budget_events);
500 const increment = try drawRangeFactor(
501 data,
502 EventRange.maximum_increment_events,
503 );
504 const actual = EventRange.advance(current, increment);
505 const expected = @as(u128, current) + @as(u128, increment);
506 if (current <= EventRange.budget_events and increment > 0 and
507 increment <= EventRange.maximum_increment_events and
508 expected <= EventRange.budget_events)
509 {
510 try std.testing.expectEqual(@as(u64, @intCast(expected)), actual.?);
511 } else try std.testing.expectEqual(@as(?u64, null), actual);
512 }
513
514 const SegmentedRangeProperty = struct {
515 pub fn property(
516 data: *hypothesis.ConjectureData,
517 _: std.mem.Allocator,
518 ) !void {
519 switch (try data.drawInteger(0, 2, 0)) {
520 0 => {
521 const rate = try drawRangeFactor(
522 data,
523 SegmentRange.maximum_units_per_second,
524 );
525 const lifetime = try drawRangeFactor(
526 data,
527 SegmentRange.service_lifetime_seconds,
528 );
529 try expectUnsignedTotal(
530 SegmentRange,
531 SegmentRange.unit_precision_segments,
532 rate,
533 lifetime,
534 );
535 try checkSegmentAdvance(data);
536 },
537 1 => {
538 const rate = try drawRangeFactor(
539 data,
540 PageRange.maximum_segments_per_second,
541 );
542 const lifetime = try drawRangeFactor(
543 data,
544 PageRange.service_lifetime_seconds,
545 );
546 try expectPageTotal(rate, lifetime);
547 try checkPageAdvance(data);
548 },
549 2 => {
550 const rate = try drawRangeFactor(
551 data,
552 EventRange.maximum_units_per_second,
553 );
554 const lifetime = try drawRangeFactor(
555 data,
556 EventRange.service_lifetime_seconds,
557 );
558 try expectUnsignedTotal(
559 EventRange,
560 EventRange.unit_precision_events,
561 rate,
562 lifetime,
563 );
564 try checkEventAdvance(data);
565 },
566 else => unreachable,
567 }
568 }
569 };
570
571 test "property: segmented counter ranges cover scale and final legal increments" {
572 try std.testing.expectEqual(
573 SegmentRange.budget_segments,
574 SegmentRange.total(
575 SegmentRange.maximum_units_per_second,
576 SegmentRange.service_lifetime_seconds,
577 ).?,
578 );
579 try std.testing.expectEqual(
580 SegmentRange.budget_segments,
581 SegmentRange.advance(SegmentRange.budget_segments - 1).?,
582 );
583 try std.testing.expect(SegmentRange.advance(SegmentRange.budget_segments) == null);
584 try std.testing.expectEqual(
585 PageRange.budget_pages,
586 PageRange.total(
587 PageRange.maximum_segments_per_second,
588 PageRange.service_lifetime_seconds,
589 ).?,
590 );
591 try std.testing.expectEqual(
592 PageRange.budget_pages,
593 PageRange.advance(PageRange.budget_pages - 1, 1).?,
594 );
595 try std.testing.expect(PageRange.advance(PageRange.budget_pages, 1) == null);
596 try std.testing.expectEqual(
597 EventRange.budget_events,
598 EventRange.total(
599 EventRange.maximum_units_per_second,
600 EventRange.service_lifetime_seconds,
601 ).?,
602 );
603 try std.testing.expectEqual(
604 EventRange.budget_events,
605 EventRange.advance(
606 EventRange.budget_events - EventRange.maximum_increment_events,
607 EventRange.maximum_increment_events,
608 ).?,
609 );
610 try std.testing.expect(EventRange.advance(EventRange.budget_events, 1) == null);
611 try std.testing.expect(SegmentRange.total(std.math.maxInt(u64), 2) == null);
612 try std.testing.expect(PageRange.total(
613 std.math.maxInt(u64),
614 std.math.maxInt(u64),
615 ) == null);
616 try std.testing.expect(EventRange.total(std.math.maxInt(u64), 2) == null);
617 }
618
619 test "property: segmented counter ranges are monotonic and reject overflow" {
620 try hypothesis.checkNamed(
621 SegmentedRangeProperty,
622 "sql-segmented-counter-range",
623 segmentedRangeSettings(),
624 );
625 }