lib/stabilizer/src/properties/heap.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const stabilizer = @import("stabilizer");
4
5 const Allocator = std.mem.Allocator;
6 const Alignment = std.mem.Alignment;
7
8 const default_shuffle_slots = stabilizer.default_shuffle_slots;
9 const default_region_size = stabilizer.default_region_size;
10 const code_alignment = stabilizer.code_alignment;
11 const stack_alignment = stabilizer.stack_alignment;
12 const rerandomize_interval_ms = stabilizer.rerandomize_interval_ms;
13 const max_stack_pad_unit = stabilizer.max_stack_pad_unit;
14
15 const Reference = stabilizer.Reference;
16 const Marsaglia = stabilizer.Marsaglia;
17 const StackPads = stabilizer.StackPads;
18 const ShuffleAllocator = stabilizer.ShuffleAllocator;
19 const sizeClass = stabilizer.sizeClass;
20 const FunctionId = stabilizer.FunctionId;
21 const LocationId = stabilizer.LocationId;
22 const FunctionOptions = stabilizer.FunctionOptions;
23 const FunctionEntryState = stabilizer.FunctionEntryState;
24 const FunctionLocation = stabilizer.FunctionLocation;
25 const CodeRandomizer = stabilizer.CodeRandomizer;
26 const Runtime = stabilizer.Runtime;
27
28 fn settings() hypothesis.Settings {
29 return hypothesis.Settings.quick()
30 .withSeed(0x57ab_11e5)
31 .withDatabase("zig-out/hypothesis-failures/stabilizer");
32 }
33
34 fn drawUsize(data: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
35 return @intCast(try data.drawInteger(
36 @intCast(min),
37 @intCast(max),
38 @intCast(shrink_towards),
39 ));
40 }
41
42 fn drawAlignment(data: *hypothesis.ConjectureData) !Alignment {
43 const shift = try drawUsize(data, 0, 8, 0);
44 return .fromByteUnits(@as(usize, 1) << @as(u6, @intCast(shift)));
45 }
46
47 test "shuffle allocator reuses frees through the vector" {
48 var heap = ShuffleAllocator.init(std.testing.allocator, .{
49 .shuffle_slots = 4,
50 .max_shuffled_size = 1024,
51 }, 1234);
52 defer heap.deinit();
53 const allocator = heap.allocator();
54
55 const first = try allocator.alloc(u8, 24);
56 @memset(first, 0xaa);
57 allocator.free(first);
58
59 const second = try allocator.alloc(u8, 24);
60 @memset(second, 0xbb);
61 allocator.free(second);
62
63 try std.testing.expect(heap.pools.items.len == 1);
64 }
65
66 const AllocatorRecord = struct {
67 slice: []u8,
68 alignment: Alignment,
69 fill: u8,
70 };
71
72 const AllocatorProperty = struct {
73 pub fn property(data: *hypothesis.ConjectureData, allocator: Allocator) !void {
74 var heap = ShuffleAllocator.init(allocator, .{
75 .pointer_validation = try data.drawBoolean(),
76 .shuffle_slots = 8,
77 .max_shuffled_size = 4096,
78 }, 0x1234_5678);
79 defer heap.deinit();
80 const shuffled = heap.allocator();
81
82 var active: std.ArrayListUnmanaged(AllocatorRecord) = .empty;
83 defer active.deinit(allocator);
84 defer {
85 for (active.items) |record| {
86 shuffled.rawFree(record.slice, record.alignment, @returnAddress());
87 }
88 }
89
90 const steps = try drawUsize(data, 1, 96, 16);
91 var step: usize = 0;
92 while (step < steps) : (step += 1) {
93 const op = try drawUsize(data, 0, 99, 0);
94 if (op < 55 or active.items.len == 0) {
95 const len = try drawUsize(data, 1, 2048, 1);
96 const alignment = try drawAlignment(data);
97 const ptr = shuffled.rawAlloc(len, alignment, @returnAddress()) orelse return error.OutOfMemory;
98 const slice = ptr[0..len];
99 const fill: u8 = @truncate(step);
100 @memset(slice, fill);
101 try std.testing.expect(std.mem.isAligned(@intFromPtr(slice.ptr), alignment.toByteUnits()));
102 try active.append(allocator, .{ .slice = slice, .alignment = alignment, .fill = fill });
103 } else if (op < 80) {
104 const slot = try drawUsize(data, 0, active.items.len - 1, 0);
105 var record = &active.items[slot];
106 const old = record.slice;
107 const new_len = try drawUsize(data, 1, 2048, 1);
108 const resized_ptr = shuffled.rawAlloc(new_len, record.alignment, @returnAddress()) orelse return error.OutOfMemory;
109 const resized = resized_ptr[0..new_len];
110 const prefix_len = @min(old.len, new_len);
111 @memcpy(resized[0..prefix_len], old[0..prefix_len]);
112 shuffled.rawFree(old, record.alignment, @returnAddress());
113 for (resized[0..prefix_len]) |byte| try std.testing.expectEqual(record.fill, byte);
114 @memset(resized, record.fill);
115 record.slice = resized;
116 } else {
117 const slot = try drawUsize(data, 0, active.items.len - 1, 0);
118 shuffled.rawFree(active.items[slot].slice, active.items[slot].alignment, @returnAddress());
119 _ = active.swapRemove(slot);
120 }
121
122 for (active.items) |record| {
123 for (record.slice) |byte| try std.testing.expectEqual(record.fill, byte);
124 }
125 }
126 }
127 };
128
129 test "pbt: shuffled allocator preserves active allocation contents" {
130 try hypothesis.checkNamed(AllocatorProperty, "stabilizer-allocator", settings());
131 }
132
133 const CHeapRecord = struct {
134 ptr: [*]u8,
135 len: usize,
136 fill: u8,
137 };
138
139 const CHeapProperty = struct {
140 pub fn property(data: *hypothesis.ConjectureData, allocator: Allocator) !void {
141 var heap = ShuffleAllocator.init(allocator, .{
142 .pointer_validation = false,
143 .shuffle_slots = 8,
144 .max_shuffled_size = 4096,
145 }, 0x4845_4150);
146 defer heap.deinit();
147
148 var active: std.ArrayListUnmanaged(CHeapRecord) = .empty;
149 defer active.deinit(allocator);
150 defer {
151 for (active.items) |record| {
152 heap.freePointer(record.ptr);
153 }
154 }
155
156 const steps = try drawUsize(data, 1, 96, 16);
157 var step: usize = 0;
158 while (step < steps) : (step += 1) {
159 const op = try drawUsize(data, 0, 99, 0);
160 if (op < 55 or active.items.len == 0) {
161 const fill: u8 = @truncate(step);
162 const use_calloc = try data.drawBoolean();
163 if (use_calloc) {
164 const count = try drawUsize(data, 0, 64, 1);
165 const len = try drawUsize(data, 0, 64, 1);
166 const total = count * len;
167 const ptr = try heap.calloc(count, len);
168 try std.testing.expectEqual(total, ShuffleAllocator.requestedLength(ptr).?);
169 for (ptr[0..total]) |byte| try std.testing.expectEqual(@as(u8, 0), byte);
170 @memset(ptr[0..total], fill);
171 try active.append(allocator, .{ .ptr = ptr, .len = total, .fill = fill });
172 } else {
173 const len = try drawUsize(data, 0, 2048, 1);
174 const ptr = try heap.malloc(len);
175 try std.testing.expectEqual(len, ShuffleAllocator.requestedLength(ptr).?);
176 @memset(ptr[0..len], fill);
177 try active.append(allocator, .{ .ptr = ptr, .len = len, .fill = fill });
178 }
179 } else if (op < 80) {
180 const slot = try drawUsize(data, 0, active.items.len - 1, 0);
181 const old = active.items[slot];
182 const new_len = try drawUsize(data, 0, 2048, 1);
183 const maybe_resized = try heap.realloc(old.ptr, new_len);
184 if (maybe_resized) |resized| {
185 const prefix_len = @min(old.len, new_len);
186 for (resized[0..prefix_len]) |byte| try std.testing.expectEqual(old.fill, byte);
187 try std.testing.expectEqual(new_len, ShuffleAllocator.requestedLength(resized).?);
188 @memset(resized[0..new_len], old.fill);
189 active.items[slot] = .{ .ptr = resized, .len = new_len, .fill = old.fill };
190 } else {
191 try std.testing.expect(ShuffleAllocator.requestedLength(old.ptr) == null);
192 _ = active.swapRemove(slot);
193 }
194 } else {
195 const slot = try drawUsize(data, 0, active.items.len - 1, 0);
196 const freed = active.items[slot].ptr;
197 heap.freePointer(freed);
198 try std.testing.expect(ShuffleAllocator.requestedLength(freed) == null);
199 _ = active.swapRemove(slot);
200 }
201
202 for (active.items) |record| {
203 try std.testing.expectEqual(record.len, ShuffleAllocator.requestedLength(record.ptr).?);
204 for (record.ptr[0..record.len]) |byte| try std.testing.expectEqual(record.fill, byte);
205 }
206 }
207 }
208 };
209
210 test "pbt: c heap operations preserve active allocation contents" {
211 try hypothesis.checkNamed(CHeapProperty, "stabilizer-c-heap", settings());
212 }