lib/deadalloc/src/properties/allocator.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const deadalloc = @import("deadalloc");
4
5 const Allocator = std.mem.Allocator;
6 const Alignment = std.mem.Alignment;
7
8 const Config = deadalloc.Config;
9 const DeadAllocator = deadalloc.DeadAllocator;
10 const Mode = deadalloc.Mode;
11
12 const class_sizes = deadalloc.class_sizes;
13 const max_issues = deadalloc.max_issues;
14 const max_small_size = deadalloc.max_small_size;
15 const min_alignment = deadalloc.min_alignment;
16 const page_size = deadalloc.page_size;
17
18 const PropertyRange = struct {
19 start: usize,
20 end: usize,
21 };
22
23 const PropertyRecord = struct {
24 slice: []u8,
25 fill: u8,
26 };
27
28 pub fn settings() hypothesis.Settings {
29 return hypothesis.Settings.quick()
30 .withSeed(0xde47_a110)
31 .withDatabase("zig-out/hypothesis-failures/deadalloc");
32 }
33
34 fn drawPropertyUsize(conjecture: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
35 return @intCast(try conjecture.drawInteger(
36 @intCast(min),
37 @intCast(max),
38 @intCast(shrink_towards),
39 ));
40 }
41
42 fn drawPropertyMode(conjecture: *hypothesis.ConjectureData) !Mode {
43 return switch (try drawPropertyUsize(conjecture, 0, 2, 0)) {
44 0 => .diehard,
45 1 => .dieharder,
46 else => .exterminator,
47 };
48 }
49
50 fn propertyClassSizeFor(len: usize, alignment: Alignment) usize {
51 const requested_len = @max(len, min_alignment);
52 const requested_alignment = @max(alignment.toByteUnits(), min_alignment);
53 for (class_sizes) |class_size| {
54 if (class_size >= requested_len and class_size >= requested_alignment) return class_size;
55 }
56 return len;
57 }
58
59 fn expectPropertyRangesDisjoint(ranges: []const PropertyRange) !void {
60 for (ranges, 0..) |left, index| {
61 for (ranges[index + 1 ..]) |right| {
62 try std.testing.expect(left.end <= right.start or right.end <= left.start);
63 }
64 }
65 }
66
67 fn propertyActiveBytes(records: []const PropertyRecord) usize {
68 var total: usize = 0;
69 for (records) |record| total += record.slice.len;
70 return total;
71 }
72
73 pub const AllocatorStateProperty = struct {
74 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
75 const mode = try drawPropertyMode(conjecture);
76 var heap = DeadAllocator.init(allocator, .{
77 .mode = mode,
78 .seed = 0x51a7e + @as(u64, @backingInt(mode)),
79 .min_chunk_blocks = 8,
80 .thread_safe = false,
81 .diagnostics = .{ .enabled = true, .red_zone_bytes = 16, .quarantine_epochs = 4 },
82 });
83 defer heap.deinit();
84 const dead_allocator = heap.allocator();
85
86 var active: std.ArrayList(PropertyRecord) = .empty;
87 defer active.deinit(allocator);
88 defer {
89 for (active.items) |record| dead_allocator.free(record.slice);
90 }
91
92 const steps = try drawPropertyUsize(conjecture, 1, 96, 16);
93 var step: usize = 0;
94 while (step < steps) : (step += 1) {
95 const op = try drawPropertyUsize(conjecture, 0, 99, 0);
96 if (op < 55 or active.items.len == 0) {
97 const len = try drawPropertyUsize(conjecture, 1, 4096, 1);
98 const fill: u8 = @intCast(step & 0xff);
99 const slice = try dead_allocator.alloc(u8, len);
100 @memset(slice, fill);
101 try active.append(allocator, .{ .slice = slice, .fill = fill });
102 } else if (op < 80) {
103 const slot = try drawPropertyUsize(conjecture, 0, active.items.len - 1, 0);
104 var record = &active.items[slot];
105 const old_len = record.slice.len;
106 const new_len = try drawPropertyUsize(conjecture, 1, 4096, 1);
107 const resized = try dead_allocator.realloc(record.slice, new_len);
108 const prefix_len = @min(old_len, new_len);
109 for (resized[0..prefix_len]) |byte| try std.testing.expectEqual(record.fill, byte);
110 @memset(resized, record.fill);
111 record.slice = resized;
112 } else {
113 const slot = try drawPropertyUsize(conjecture, 0, active.items.len - 1, 0);
114 dead_allocator.free(active.items[slot].slice);
115 _ = active.swapRemove(slot);
116 }
117
118 var ranges: std.ArrayList(PropertyRange) = .empty;
119 defer ranges.deinit(allocator);
120 for (active.items) |record| {
121 for (record.slice) |byte| try std.testing.expectEqual(record.fill, byte);
122 try ranges.append(allocator, .{
123 .start = @intFromPtr(record.slice.ptr),
124 .end = @intFromPtr(record.slice.ptr) + record.slice.len,
125 });
126 }
127 try expectPropertyRangesDisjoint(ranges.items);
128
129 const report = heap.report();
130 try std.testing.expectEqual(active.items.len, report.live_allocations);
131 try std.testing.expectEqual(propertyActiveBytes(active.items), report.live_bytes);
132 try std.testing.expectEqual(active.items.len, report.leak_count);
133 if (active.items.len == 0) {
134 try std.testing.expect(report.leak_issue == null);
135 } else {
136 const issue = report.leak_issue.?;
137 try std.testing.expectEqual(.leak, issue.kind);
138 try std.testing.expect(issue.requested_len > 0);
139 var matches_active = false;
140 for (active.items) |record| {
141 if (@intFromPtr(record.slice.ptr) == issue.address and record.slice.len == issue.requested_len) {
142 matches_active = true;
143 break;
144 }
145 }
146 try std.testing.expect(matches_active);
147 }
148 try std.testing.expectEqual(@as(usize, 0), report.counters.issueCount());
149 }
150
151 try std.testing.expectEqual(@as(usize, 0), heap.report().counters.invalid_free);
152 try std.testing.expectEqual(@as(usize, 0), heap.report().counters.double_free);
153 try std.testing.expectEqual(@as(usize, 0), heap.report().counters.buffer_overflow);
154 }
155 };
156
157 pub const DiagnosticFaultProperty = struct {
158 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
159 const mode = try drawPropertyMode(conjecture);
160 var heap = DeadAllocator.init(allocator, .{
161 .mode = mode,
162 .seed = 0xfa17_5eed + @as(u64, @backingInt(mode)),
163 .min_chunk_blocks = 8,
164 .thread_safe = false,
165 .diagnostics = .{ .enabled = true, .red_zone_bytes = 16, .quarantine_epochs = 4 },
166 });
167 defer heap.deinit();
168 const dead_allocator = heap.allocator();
169
170 const len = try drawPropertyUsize(conjecture, 2, 512, 8);
171 const fault = try drawPropertyUsize(conjecture, 0, 10, 0);
172 switch (fault) {
173 0 => {
174 var stack_byte: u8 = 0;
175 dead_allocator.rawFree((&stack_byte)[0..1], .@"1", @returnAddress());
176 try std.testing.expectEqual(@as(usize, 1), heap.report().counters.invalid_free);
177 },
178 1 => {
179 const allocation = try dead_allocator.alloc(u8, len);
180 dead_allocator.free(allocation);
181 dead_allocator.free(allocation);
182 try std.testing.expectEqual(@as(usize, 1), heap.report().counters.double_free);
183 },
184 2 => {
185 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
186 ptr[len] = 0xee;
187 dead_allocator.rawFree(ptr[0..len], .@"1", @returnAddress());
188 try std.testing.expectEqual(@as(usize, 1), heap.report().counters.buffer_overflow);
189 },
190 else => {
191 if (fault == 10) {
192 var stack_byte: u8 = 0x5a;
193 const remapped = dead_allocator.rawRemap((&stack_byte)[0..1], .@"1", len, @returnAddress());
194 try std.testing.expect(remapped == null);
195
196 const report = heap.report();
197 try std.testing.expectEqual(@as(usize, 1), report.counters.invalid_free);
198 try std.testing.expectEqual(@as(usize, 0), report.live_allocations);
199 return;
200 }
201
202 if (fault == 9) {
203 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
204 dead_allocator.rawFree(ptr[1..len], .@"1", @returnAddress());
205
206 const report = heap.report();
207 const issue = report.last_issue.?;
208 try std.testing.expectEqual(@as(usize, 1), report.counters.invalid_free);
209 try std.testing.expectEqual(@as(usize, 1), report.live_allocations);
210 try std.testing.expectEqual(.invalid_free, issue.kind);
211 try std.testing.expectEqual(@intFromPtr(ptr) + 1, issue.address);
212 try std.testing.expectEqual(@as(usize, 1), issue.offset);
213 try std.testing.expectEqual(len - 1, issue.requested_len);
214 try std.testing.expect(issue.block_size >= len);
215 try std.testing.expect(issue.allocation_id != 0);
216 try std.testing.expect(issue.allocation_return_address != 0);
217
218 dead_allocator.rawFree(ptr[0..len], .@"1", @returnAddress());
219 return;
220 }
221
222 if (fault == 8) {
223 const allocation = try dead_allocator.alloc(u8, len);
224 const address = @intFromPtr(allocation.ptr);
225 dead_allocator.free(allocation);
226
227 const stale: [*]u8 = @ptrFromInt(address);
228 stale[0] = 0xdf;
229
230 const report = heap.report();
231 const issue = report.last_issue.?;
232 try std.testing.expectEqual(@as(usize, 1), report.counters.use_after_free);
233 try std.testing.expectEqual(.use_after_free, issue.kind);
234 try std.testing.expectEqual(@as(usize, 0), issue.offset);
235 try std.testing.expect(issue.allocation_id != 0);
236 try std.testing.expect(issue.free_return_address != 0);
237 return;
238 }
239
240 if (fault == 7) {
241 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
242 ptr[len] = 0xee;
243
244 const first = heap.report();
245 const second = heap.report();
246 try std.testing.expectEqual(@as(usize, 1), first.counters.buffer_overflow);
247 try std.testing.expectEqual(@as(usize, 1), second.counters.buffer_overflow);
248 return;
249 }
250
251 if (fault == 6) {
252 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
253 const block_size = propertyClassSizeFor(len + 16, .@"1");
254 const offset = try drawPropertyUsize(conjecture, len, block_size - 1, len);
255 dead_allocator.rawFree(ptr[0..len], .@"1", @returnAddress());
256
257 ptr[offset] = 0xdf;
258
259 const report = heap.report();
260 const issue = report.last_issue.?;
261 try std.testing.expectEqual(@as(usize, 1), report.counters.use_after_free);
262 try std.testing.expectEqual(.use_after_free, issue.kind);
263 try std.testing.expectEqual(offset, issue.offset);
264 try std.testing.expect(issue.allocation_id != 0);
265 try std.testing.expect(issue.free_return_address != 0);
266 return;
267 }
268
269 if (fault == 5) {
270 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
271 ptr[len] = 0xee;
272 try std.testing.expect(dead_allocator.rawResize(ptr[0..len], .@"1", len + 1, @returnAddress()));
273 try std.testing.expectEqual(@as(usize, 1), heap.report().counters.buffer_overflow);
274 return;
275 }
276
277 if (fault == 4) {
278 const allocation = try dead_allocator.alloc(u8, len);
279 const address = @intFromPtr(allocation.ptr);
280 dead_allocator.free(allocation);
281
282 const stale: [*]u8 = @ptrFromInt(address);
283 stale[0] = 0xdf;
284
285 const first = heap.report();
286 const second = heap.report();
287 try std.testing.expectEqual(@as(usize, 1), first.counters.use_after_free);
288 try std.testing.expectEqual(@as(usize, 1), second.counters.use_after_free);
289 return;
290 }
291
292 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
293 dead_allocator.rawFree(ptr[0 .. len - 1], .@"1", @returnAddress());
294 try std.testing.expectEqual(@as(usize, 1), heap.report().counters.size_mismatch);
295 },
296 }
297 }
298 };
299
300 pub const AlignmentProperty = struct {
301 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
302 var heap = DeadAllocator.init(allocator, .{
303 .mode = .diehard,
304 .seed = 0xa119_4ed,
305 .min_chunk_blocks = 8,
306 .thread_safe = false,
307 });
308 defer heap.deinit();
309 const dead_allocator = heap.allocator();
310
311 var ranges: std.ArrayList(PropertyRange) = .empty;
312 defer ranges.deinit(allocator);
313 defer {
314 for (ranges.items) |range| {
315 const ptr: [*]u8 = @ptrFromInt(range.start);
316 dead_allocator.rawFree(ptr[0 .. range.end - range.start], .@"1", @returnAddress());
317 }
318 }
319
320 const count = try drawPropertyUsize(conjecture, 1, 64, 8);
321 var index: usize = 0;
322 while (index < count) : (index += 1) {
323 const alignment_shift = try drawPropertyUsize(conjecture, 0, 12, 0);
324 const alignment = Alignment.fromByteUnits(@as(usize, 1) << @as(u6, @intCast(alignment_shift)));
325 const len = try drawPropertyUsize(conjecture, 1, 8192, 1);
326 const ptr = dead_allocator.rawAlloc(len, alignment, @returnAddress()) orelse return error.OutOfMemory;
327 try std.testing.expect(std.mem.isAligned(@intFromPtr(ptr), alignment.toByteUnits()));
328 try ranges.append(allocator, .{
329 .start = @intFromPtr(ptr),
330 .end = @intFromPtr(ptr) + len,
331 });
332 }
333
334 try expectPropertyRangesDisjoint(ranges.items);
335 }
336 };
337
338 pub const LargeAllocationProperty = struct {
339 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
340 var heap = DeadAllocator.init(allocator, .{
341 .mode = .dieharder,
342 .seed = 0xd1e4_a110,
343 .thread_safe = false,
344 });
345 defer heap.deinit();
346 const dead_allocator = heap.allocator();
347
348 const len = max_small_size + try drawPropertyUsize(conjecture, 1, page_size - 1, 1);
349 const rounded_len = std.mem.alignForward(usize, len, page_size);
350 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
351 try std.testing.expect(std.mem.isAligned(@intFromPtr(ptr), page_size));
352 try std.testing.expect(dead_allocator.rawResize(ptr[0..len], .@"1", rounded_len, @returnAddress()));
353 dead_allocator.rawFree(ptr[0..rounded_len], .@"1", @returnAddress());
354 try std.testing.expectEqual(@as(usize, 0), heap.report().live_allocations);
355 }
356 };
357
358 pub const InteriorFreeProperty = struct {
359 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
360 var heap = DeadAllocator.init(allocator, .{
361 .mode = .dieharder,
362 .seed = 0x91e_0a11,
363 .thread_safe = false,
364 .diagnostics = .{ .enabled = true, .red_zone_bytes = 16 },
365 });
366 defer heap.deinit();
367 const dead_allocator = heap.allocator();
368
369 const len = try drawPropertyUsize(conjecture, 2, 2048, 8);
370 const block_size = propertyClassSizeFor(len + 16, .@"1");
371 const offset = try drawPropertyUsize(conjecture, 1, block_size - 1, 1);
372 const ptr = dead_allocator.rawAlloc(len, .@"1", @returnAddress()) orelse return error.OutOfMemory;
373
374 dead_allocator.rawFree((ptr + offset)[0..1], .@"1", @returnAddress());
375
376 const report = heap.report();
377 const issue = report.last_issue.?;
378 try std.testing.expectEqual(@as(usize, 1), report.counters.invalid_free);
379 try std.testing.expectEqual(@as(usize, 1), report.live_allocations);
380 try std.testing.expectEqual(.invalid_free, issue.kind);
381 try std.testing.expectEqual(@intFromPtr(ptr) + offset, issue.address);
382 try std.testing.expectEqual(offset, issue.offset);
383 try std.testing.expectEqual(@as(usize, 1), issue.requested_len);
384 try std.testing.expect(issue.allocation_id != 0);
385
386 dead_allocator.rawFree(ptr[0..len], .@"1", @returnAddress());
387 }
388 };
389
390 pub const RawRemapProperty = struct {
391 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
392 const mode = try drawPropertyMode(conjecture);
393 var heap = DeadAllocator.init(allocator, .{
394 .mode = mode,
395 .seed = 0x4e4d_a9 + @as(u64, @backingInt(mode)),
396 .min_chunk_blocks = 8,
397 .thread_safe = false,
398 .diagnostics = .{ .enabled = true, .red_zone_bytes = 16, .quarantine_epochs = 4 },
399 });
400 defer heap.deinit();
401 const dead_allocator = heap.allocator();
402
403 const alignment_shift = try drawPropertyUsize(conjecture, 0, 8, 0);
404 const alignment = Alignment.fromByteUnits(@as(usize, 1) << @as(u6, @intCast(alignment_shift)));
405 const old_len = try drawPropertyUsize(conjecture, 1, 512, 8);
406 const old_block_size = propertyClassSizeFor(old_len + 16, alignment);
407 const relocates = try drawPropertyUsize(conjecture, 0, 1, 0) == 1;
408 const new_len = if (relocates)
409 old_block_size + try drawPropertyUsize(conjecture, 1, 4096, 1)
410 else
411 try drawPropertyUsize(conjecture, 1, old_block_size - 16, @min(old_len, old_block_size - 16));
412
413 const ptr = dead_allocator.rawAlloc(old_len, alignment, @returnAddress()) orelse return error.OutOfMemory;
414 var index: usize = 0;
415 while (index < old_len) : (index += 1) {
416 ptr[index] = @truncate(index *% 131 +% old_len);
417 }
418
419 const remapped = dead_allocator.rawRemap(ptr[0..old_len], alignment, new_len, @returnAddress()) orelse return error.OutOfMemory;
420 const prefix_len = @min(old_len, new_len);
421 index = 0;
422 while (index < prefix_len) : (index += 1) {
423 try std.testing.expectEqual(@as(u8, @truncate(index *% 131 +% old_len)), remapped[index]);
424 }
425 try std.testing.expect(std.mem.isAligned(@intFromPtr(remapped), alignment.toByteUnits()));
426
427 const live_report = heap.report();
428 try std.testing.expectEqual(@as(usize, 1), live_report.live_allocations);
429 try std.testing.expectEqual(new_len, live_report.live_bytes);
430 try std.testing.expectEqual(@as(usize, 1), live_report.leak_count);
431 try std.testing.expectEqual(@as(usize, 0), live_report.counters.issueCount());
432
433 dead_allocator.rawFree(remapped[0..new_len], alignment, @returnAddress());
434 try std.testing.expect(heap.report().isClean());
435 }
436 };
437
438 pub const DiagnosticHistoryProperty = struct {
439 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
440 var heap = DeadAllocator.init(allocator, .{
441 .mode = .exterminator,
442 .seed = 0x155e_109,
443 .min_chunk_blocks = 8,
444 .thread_safe = false,
445 .diagnostics = .{ .enabled = true },
446 });
447 defer heap.deinit();
448 const dead_allocator = heap.allocator();
449
450 const count = try drawPropertyUsize(conjecture, 1, max_issues + 16, max_issues);
451 var stack_byte: u8 = 0;
452 var index: usize = 0;
453 while (index < count) : (index += 1) {
454 dead_allocator.rawFree((&stack_byte)[0..1], .@"1", @returnAddress());
455 }
456
457 const report = heap.report();
458 const issues = report.issueSlice();
459 const retained = @min(count, max_issues);
460 try std.testing.expectEqual(count, report.counters.invalid_free);
461 try std.testing.expectEqual(retained, issues.len);
462 try std.testing.expectEqual(count - retained, report.issues.dropped);
463 for (issues) |issue| {
464 try std.testing.expectEqual(.invalid_free, issue.kind);
465 try std.testing.expectEqual(@intFromPtr(&stack_byte), issue.address);
466 }
467 }
468 };
469
470 pub const LeakIssueProperty = struct {
471 pub fn property(conjecture: *hypothesis.ConjectureData, allocator: Allocator) !void {
472 var heap = DeadAllocator.init(allocator, .{
473 .mode = .exterminator,
474 .seed = 0x1ea_5eed,
475 .min_chunk_blocks = 8,
476 .thread_safe = false,
477 .diagnostics = .{ .enabled = true },
478 });
479 defer heap.deinit();
480 const dead_allocator = heap.allocator();
481
482 var allocations: std.ArrayList([]u8) = .empty;
483 defer allocations.deinit(allocator);
484 defer {
485 for (allocations.items) |allocation| dead_allocator.free(allocation);
486 }
487
488 const count = try drawPropertyUsize(conjecture, 1, max_issues + 16, max_issues);
489 var expected_bytes: usize = 0;
490 var index: usize = 0;
491 while (index < count) : (index += 1) {
492 const len = try drawPropertyUsize(conjecture, 1, 512, 8);
493 const allocation = try dead_allocator.alloc(u8, len);
494 @memset(allocation, @as(u8, @truncate(index)));
495 try allocations.append(allocator, allocation);
496 expected_bytes += len;
497 }
498
499 const report = heap.report();
500 const issues = report.issueSlice();
501 const retained = @min(count, max_issues);
502 var leak_issues: usize = 0;
503 for (issues) |issue| {
504 try std.testing.expectEqual(.leak, issue.kind);
505 try std.testing.expect(issue.requested_len > 0);
506 try std.testing.expect(issue.allocation_id != 0);
507 leak_issues += 1;
508 }
509
510 try std.testing.expectEqual(count, report.live_allocations);
511 try std.testing.expectEqual(count, report.leak_count);
512 try std.testing.expectEqual(expected_bytes, report.live_bytes);
513 try std.testing.expectEqual(retained, leak_issues);
514 try std.testing.expectEqual(count - retained, report.issues.dropped);
515 try std.testing.expect(report.leak_issue != null);
516 }
517 };
518
519 test "property: allocator operations preserve active ranges" {
520 try hypothesis.checkNamed(AllocatorStateProperty, "deadalloc-state", settings());
521 }
522
523 test "property: diagnostics classify generated allocation faults" {
524 try hypothesis.checkNamed(DiagnosticFaultProperty, "deadalloc-diagnostics", settings());
525 }
526
527 test "property: allocations satisfy requested alignment" {
528 try hypothesis.checkNamed(AlignmentProperty, "deadalloc-alignment", settings());
529 }
530
531 test "property: dieharder large allocations are page granular" {
532 try hypothesis.checkNamed(LargeAllocationProperty, "deadalloc-dieharder-large", settings());
533 }
534
535 test "property: dieharder interior frees retain allocation context" {
536 try hypothesis.checkNamed(InteriorFreeProperty, "deadalloc-dieharder-interior-free", settings());
537 }
538
539 test "property: raw remap preserves prefixes and ownership" {
540 try hypothesis.checkNamed(RawRemapProperty, "deadalloc-raw-remap", settings());
541 }
542
543 test "property: diagnostic issue history is bounded and ordered" {
544 try hypothesis.checkNamed(DiagnosticHistoryProperty, "deadalloc-diagnostic-history", settings());
545 }
546
547 test "property: leak issues are bounded and structured" {
548 try hypothesis.checkNamed(LeakIssueProperty, "deadalloc-leak-issues", settings());
549 }