lib/stabilizer/src/properties/reference.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 const ReferenceFunction = struct {
48 id: FunctionId,
49 options: FunctionOptions,
50 entry: FunctionEntryState = .trap,
51 stack_pad_unit: ?u8 = null,
52 current: ?LocationId = null,
53 original_base: usize,
54 };
55
56 const ReferenceCodeModel = struct {
57 allocator: Allocator,
58 functions: std.ArrayListUnmanaged(ReferenceFunction) = .empty,
59 locations: std.ArrayListUnmanaged(FunctionLocation) = .empty,
60 live: std.ArrayListUnmanaged(FunctionId) = .empty,
61 next_function_id: FunctionId = 1,
62 next_location_id: LocationId = 1,
63 next_original_base: usize = 0x0800_0000,
64 next_base: usize = 0x2000_0000,
65 next_stack_pad_unit: u8 = 0,
66 rerandomizing: bool = false,
67
68 fn init(allocator: Allocator) ReferenceCodeModel {
69 return .{ .allocator = allocator };
70 }
71
72 fn deinit(self: *ReferenceCodeModel) void {
73 self.functions.deinit(self.allocator);
74 self.locations.deinit(self.allocator);
75 self.live.deinit(self.allocator);
76 self.* = undefined;
77 }
78
79 fn registerFunction(self: *ReferenceCodeModel, options: FunctionOptions) !FunctionId {
80 const normalized = normalizeReferenceFunctionOptions(options);
81 const id = self.next_function_id;
82 self.next_function_id += 1;
83 errdefer self.next_function_id -= 1;
84 const previous_original_base = self.next_original_base;
85 const original_base = self.allocateOriginalBase(normalized.code_size);
86 errdefer self.next_original_base = previous_original_base;
87 try self.functions.append(self.allocator, .{
88 .id = id,
89 .options = normalized,
90 .stack_pad_unit = options.stack_pad_unit,
91 .original_base = original_base,
92 });
93 return id;
94 }
95
96 fn relocate(self: *ReferenceCodeModel, id: FunctionId) !void {
97 const function = self.findFunction(id) orelse return error.UnknownFunction;
98 if (function.current) |current_id| {
99 if (self.findLocation(current_id)) |location| location.defunct = true;
100 }
101 const allocation_size = referenceFunctionAllocationSize(function.options);
102 const location_id = self.next_location_id;
103 self.next_location_id += 1;
104 try self.locations.append(self.allocator, .{
105 .id = location_id,
106 .function = id,
107 .base = self.next_base,
108 .size = allocation_size,
109 });
110 self.next_base += allocation_size + code_alignment;
111 function.current = location_id;
112 function.entry = .forwarding;
113 if (function.stack_pad_unit != null) {
114 function.stack_pad_unit = self.nextStackPadUnit();
115 }
116 try self.markLive(id);
117 }
118
119 fn beginRerandomization(self: *ReferenceCodeModel) void {
120 _ = self.beginRerandomizationAt(0);
121 }
122
123 fn beginRerandomizationAt(self: *ReferenceCodeModel, instruction_pointer: usize) usize {
124 var forwarded_instruction_pointer = instruction_pointer;
125 for (self.live.items) |id| {
126 if (self.findFunction(id)) |function| {
127 if (forwarded_instruction_pointer == function.original_base) {
128 if (function.current) |location_id| {
129 if (self.findLocation(location_id)) |location| {
130 forwarded_instruction_pointer = location.base;
131 }
132 }
133 }
134 function.entry = .trap;
135 }
136 }
137 self.live.clearRetainingCapacity();
138 self.rerandomizing = true;
139 return forwarded_instruction_pointer;
140 }
141
142 fn enterFunction(self: *ReferenceCodeModel, id: FunctionId, roots: []const usize) !?*FunctionLocation {
143 const function = self.findFunction(id) orelse return error.UnknownFunction;
144 return switch (function.entry) {
145 .trap => {
146 try self.trap(id, roots);
147 return self.currentLocation(id);
148 },
149 .forwarding => self.currentLocation(id),
150 };
151 }
152
153 fn trap(self: *ReferenceCodeModel, id: FunctionId, roots: []const usize) !void {
154 if (self.rerandomizing) {
155 for (roots) |root| self.markAddress(root);
156 self.sweep();
157 self.rerandomizing = false;
158 }
159 try self.relocate(id);
160 }
161
162 fn markAddress(self: *ReferenceCodeModel, address: usize) void {
163 for (self.locations.items) |*location| {
164 if (address >= location.base and address < location.base + location.size) {
165 location.marked = true;
166 }
167 }
168 }
169
170 fn sweep(self: *ReferenceCodeModel) void {
171 var index: usize = 0;
172 while (index < self.locations.items.len) {
173 const location = &self.locations.items[index];
174 if (location.defunct and !location.marked) {
175 _ = self.locations.swapRemove(index);
176 } else {
177 location.marked = false;
178 index += 1;
179 }
180 }
181 }
182
183 fn adjustAddress(self: *ReferenceCodeModel, address: usize) usize {
184 for (self.locations.items) |location| {
185 if (address >= location.base and address < location.base + location.size) {
186 const function = self.findFunction(location.function) orelse return address;
187 return function.original_base + (address - location.base);
188 }
189 }
190 return address;
191 }
192
193 fn currentLocation(self: *ReferenceCodeModel, id: FunctionId) ?*FunctionLocation {
194 const function = self.findFunction(id) orelse return null;
195 const current = function.current orelse return null;
196 return self.findLocation(current);
197 }
198
199 fn markLive(self: *ReferenceCodeModel, id: FunctionId) !void {
200 for (self.live.items) |live_id| if (live_id == id) return;
201 try self.live.append(self.allocator, id);
202 }
203
204 fn nextStackPadUnit(self: *ReferenceCodeModel) u8 {
205 const out = self.next_stack_pad_unit;
206 self.next_stack_pad_unit +%= 1;
207 return out;
208 }
209
210 fn allocateOriginalBase(self: *ReferenceCodeModel, size: usize) usize {
211 const base = std.mem.alignForward(usize, self.next_original_base, code_alignment);
212 self.next_original_base = base + std.mem.alignForward(usize, size, code_alignment) + code_alignment;
213 return base;
214 }
215
216 fn findFunction(self: *ReferenceCodeModel, id: FunctionId) ?*ReferenceFunction {
217 for (self.functions.items) |*function| if (function.id == id) return function;
218 return null;
219 }
220
221 fn findLocation(self: *ReferenceCodeModel, id: LocationId) ?*FunctionLocation {
222 for (self.locations.items) |*location| if (location.id == id) return location;
223 return null;
224 }
225 };
226
227 const CodeReferenceProperty = struct {
228 pub fn property(data: *hypothesis.ConjectureData, allocator: Allocator) !void {
229 var code = CodeRandomizer.init(allocator, .{
230 .shuffle_slots = 16,
231 .alignment = code_alignment,
232 }, 0x5245_4643);
233 defer code.deinit();
234 var reference = ReferenceCodeModel.init(allocator);
235 defer reference.deinit();
236
237 const functions = try drawUsize(data, 1, 8, 2);
238 var ids: [8]FunctionId = undefined;
239 var index: usize = 0;
240 while (index < functions) : (index += 1) {
241 const options: FunctionOptions = .{
242 .code_size = try drawUsize(data, 1, 512, 64),
243 .table_size = try drawUsize(data, 0, 128, 0),
244 .table_adjacent = try data.drawBoolean(),
245 .stack_pad_unit = if (try data.drawBoolean())
246 @truncate(try drawUsize(data, 0, max_stack_pad_unit, 0))
247 else
248 null,
249 };
250 ids[index] = try code.registerFunction(options);
251 try std.testing.expectEqual(ids[index], try reference.registerFunction(options));
252 }
253 try expectCodeMatchesReference(&code, &reference, ids[0..functions]);
254
255 const steps = try drawUsize(data, 1, 96, 8);
256 index = 0;
257 while (index < steps) : (index += 1) {
258 const operation = try drawUsize(data, 0, 2, 1);
259 if (operation == 0) {
260 const mode = try drawUsize(data, 0, 2, 0);
261 if (mode == 0 and reference.live.items.len > 0) {
262 const live_index = try drawUsize(data, 0, reference.live.items.len - 1, 0);
263 const id = reference.live.items[live_index];
264 const code_ip = code.originalBase(id).?;
265 const reference_ip = reference.findFunction(id).?.original_base;
266 const code_forwarded = code.beginRerandomizationAt(code_ip);
267 const reference_forwarded = reference.beginRerandomizationAt(reference_ip);
268 try std.testing.expectEqual(code.currentLocation(id).?.base, code_forwarded);
269 try std.testing.expectEqual(reference.currentLocation(id).?.base, reference_forwarded);
270 try std.testing.expectEqual(code_ip, code.adjustAddress(code_forwarded));
271 try std.testing.expectEqual(reference_ip, reference.adjustAddress(reference_forwarded));
272 } else {
273 const id = ids[try drawUsize(data, 0, functions - 1, 0)];
274 const ip = if (mode == 1) code.originalBase(id).? + 1 else 0x7000_0000 + index;
275 try std.testing.expectEqual(ip, code.beginRerandomizationAt(ip));
276 try std.testing.expectEqual(ip, reference.beginRerandomizationAt(ip));
277 }
278 } else {
279 const id = ids[try drawUsize(data, 0, functions - 1, 0)];
280 if (operation == 1) {
281 _ = try code.relocate(id);
282 try reference.relocate(id);
283 } else {
284 var code_roots_buf: [3]usize = undefined;
285 var reference_roots_buf: [3]usize = undefined;
286 const roots_len = try drawLocationRoots(
287 data,
288 &code,
289 &reference,
290 &code_roots_buf,
291 &reference_roots_buf,
292 );
293 _ = try code.enterFunction(id, code_roots_buf[0..roots_len]);
294 _ = try reference.enterFunction(id, reference_roots_buf[0..roots_len]);
295 }
296 }
297 try expectCodeMatchesReference(&code, &reference, ids[0..functions]);
298 }
299 }
300 };
301
302 fn normalizeReferenceFunctionOptions(options: FunctionOptions) FunctionOptions {
303 var out = options;
304 if (out.code_size == 0) out.code_size = 1;
305 return out;
306 }
307
308 fn referenceFunctionAllocationSize(options: FunctionOptions) usize {
309 return if (options.table_adjacent) options.code_size + options.table_size else options.code_size;
310 }
311
312 fn drawLocationRoots(
313 data: *hypothesis.ConjectureData,
314 code: *CodeRandomizer,
315 reference: *ReferenceCodeModel,
316 code_roots: []usize,
317 reference_roots: []usize,
318 ) !usize {
319 if (code.next_location_id <= 1) return 0;
320
321 const limit = try drawUsize(data, 0, code_roots.len, 0);
322 var count: usize = 0;
323 var index: usize = 0;
324 while (index < limit) : (index += 1) {
325 const location_id: LocationId = @intCast(try drawUsize(data, 1, code.next_location_id - 1, 1));
326 const code_location = codeLocation(code, location_id) orelse continue;
327 const reference_location = reference.findLocation(location_id) orelse return error.ReferenceMismatch;
328 const offset = try drawUsize(data, 0, @min(code_location.size, reference_location.size) - 1, 0);
329 code_roots[count] = code_location.base + offset;
330 reference_roots[count] = reference_location.base + offset;
331 count += 1;
332 }
333 return count;
334 }
335
336 fn expectCodeMatchesReference(code: *CodeRandomizer, reference: *ReferenceCodeModel, ids: []const FunctionId) !void {
337 try std.testing.expectEqual(reference.locations.items.len, code.locationCount());
338 try std.testing.expectEqual(reference.rerandomizing, code.rerandomizing);
339 try std.testing.expectEqual(reference.next_function_id, code.next_function_id);
340 try std.testing.expectEqual(reference.next_location_id, code.next_location_id);
341 try std.testing.expectEqual(reference.next_original_base, code.next_original_base);
342 try std.testing.expectEqual(reference.live.items.len, code.live.items.len);
343 for (reference.live.items, 0..) |id, index| {
344 try std.testing.expectEqual(id, code.live.items[index]);
345 }
346
347 var reference_defunct: usize = 0;
348 for (reference.locations.items) |location| {
349 if (location.defunct) reference_defunct += 1;
350 }
351 var code_defunct: usize = 0;
352 for (code.locations.items) |location| {
353 if (location.defunct) code_defunct += 1;
354 }
355 try std.testing.expectEqual(reference_defunct, code_defunct);
356
357 for (reference.locations.items) |expected| {
358 const actual = codeLocation(code, expected.id) orelse return error.ReferenceMismatch;
359 try std.testing.expectEqual(expected.function, actual.function);
360 try std.testing.expectEqual(expected.size, actual.size);
361 try std.testing.expectEqual(expected.defunct, actual.defunct);
362 try std.testing.expectEqual(expected.marked, actual.marked);
363 const offset = if (expected.size == 0) 0 else expected.size / 2;
364 try std.testing.expectEqual(
365 reference.adjustAddress(expected.base + offset),
366 code.adjustAddress(actual.base + offset),
367 );
368 }
369
370 for (ids) |id| {
371 const reference_function = reference.findFunction(id).?;
372 try std.testing.expectEqual(reference_function.entry, code.entryState(id).?);
373 try std.testing.expectEqual(reference_function.original_base, code.originalBase(id).?);
374 try std.testing.expectEqual(reference_function.stack_pad_unit != null, code.stackPadUnit(id) != null);
375 if (code.stackPad(id)) |pad| {
376 try std.testing.expectEqual(@as(usize, pad.unit) * stack_alignment, pad.bytes);
377 }
378 const reference_current = reference.currentLocation(id);
379 const code_current = code.currentLocation(id);
380 if (reference_current) |expected| {
381 const actual = code_current orelse return error.ReferenceMismatch;
382 try std.testing.expectEqual(expected.function, actual.function);
383 try std.testing.expectEqual(expected.size, actual.size);
384 try std.testing.expectEqual(expected.defunct, actual.defunct);
385 } else {
386 try std.testing.expect(code_current == null);
387 }
388 }
389 }
390
391 fn codeLocation(code: *CodeRandomizer, id: LocationId) ?*FunctionLocation {
392 for (code.locations.items) |*location| if (location.id == id) return location;
393 return null;
394 }
395
396 test "pbt: code relocation matches upstream trap sweep model" {
397 try hypothesis.checkNamed(CodeReferenceProperty, "stabilizer-code-reference", settings());
398 }