lib/gpalloc/src/properties/allocator.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const gpalloc = @import("gpalloc");
4
5 const draw = @import("draw.zig");
6
7 const Allocator = std.mem.Allocator;
8 const Alignment = std.mem.Alignment;
9 const GpAllocator = gpalloc.GpAllocator;
10 const max_small_size = gpalloc.max_small_size;
11 const size_class = gpalloc.class;
12 const assert = std.debug.assert;
13
14 const Range = struct {
15 start: usize,
16 end: usize,
17 alignment: Alignment = .@"1",
18 };
19
20 const AllocationRecord = struct {
21 slice: []u8,
22 fill: u8,
23 };
24
25 const fine_large_max = 128 * 1024;
26 const medium_large_min = 320 * 1024;
27 const medium_large_max = 512 * 1024;
28 const huge_large_min = 4 * 1024 * 1024 + 1;
29 const huge_large_max = 4 * 1024 * 1024 + 64 * 1024;
30
31 const representative_lengths = [_]usize{
32 16,
33 max_small_size + 1,
34 medium_large_min,
35 huge_large_min,
36 };
37
38 pub fn settings() hypothesis.Settings {
39 return hypothesis.Settings.quick()
40 .withSeed(0x71A1_10C)
41 .withDatabase("zig-out/hypothesis-failures/gpalloc")
42 .withSeedFromEnv();
43 }
44
45 const drawUsize = draw.drawUsize;
46 const drawAlignment = draw.drawAlignment;
47
48 fn drawAllocationLen(conjecture: *hypothesis.ConjectureData) !usize {
49 const variant = try drawUsize(conjecture, 0, 15, 0);
50 return switch (variant) {
51 0...7 => try drawUsize(conjecture, 1, max_small_size, 1),
52 8...11 => try drawUsize(conjecture, max_small_size + 1, fine_large_max, max_small_size + 1),
53 12...13 => try drawUsize(conjecture, medium_large_min, medium_large_max, medium_large_min),
54 else => try drawUsize(conjecture, huge_large_min, huge_large_max, huge_large_min),
55 };
56 }
57
58 fn expectDisjoint(ranges: []const Range) !void {
59 for (ranges, 0..) |left, index| {
60 for (ranges[index + 1 ..]) |right| {
61 try std.testing.expect(left.end <= right.start or right.end <= left.start);
62 }
63 }
64 }
65
66 fn fillSampled(bytes: []u8, fill: u8) void {
67 if (bytes.len <= 4096) {
68 @memset(bytes, fill);
69 return;
70 }
71 @memset(bytes[0..4096], fill);
72 const middle_start = bytes.len / 2 - 128;
73 @memset(bytes[middle_start .. middle_start + 256], fill);
74 @memset(bytes[bytes.len - 256 ..], fill);
75 }
76
77 fn expectSampled(bytes: []const u8, fill: u8) !void {
78 if (bytes.len <= 4096) {
79 try expectRange(bytes, fill);
80 return;
81 }
82 try expectRange(bytes[0..4096], fill);
83 const middle_start = bytes.len / 2 - 128;
84 try expectRange(bytes[middle_start .. middle_start + 256], fill);
85 try expectRange(bytes[bytes.len - 256 ..], fill);
86 }
87
88 fn expectRange(bytes: []const u8, fill: u8) !void {
89 for (bytes) |byte| {
90 try std.testing.expectEqual(fill, byte);
91 }
92 }
93
94 fn appendFilledRecord(
95 active: *std.ArrayList(AllocationRecord),
96 property_allocator: Allocator,
97 tiny_allocator: Allocator,
98 len: usize,
99 fill: u8,
100 ) !void {
101 const slice = try tiny_allocator.alloc(u8, len);
102 fillSampled(slice, fill);
103 try active.append(property_allocator, .{ .slice = slice, .fill = fill });
104 }
105
106 fn isSmallLen(len: usize) bool {
107 return len <= max_small_size;
108 }
109
110 pub const AlignmentProperty = struct {
111 pub fn property(
112 conjecture: *hypothesis.ConjectureData,
113 property_allocator: Allocator,
114 ) !void {
115 var heap = GpAllocator.init(property_allocator, .{});
116 defer heap.deinit();
117 const tiny_allocator = heap.allocator();
118
119 var ranges: std.ArrayList(Range) = .empty;
120 defer ranges.deinit(property_allocator);
121 defer {
122 for (ranges.items) |range| {
123 const ptr: [*]u8 = @ptrFromInt(range.start);
124 const len = range.end - range.start;
125 tiny_allocator.rawFree(ptr[0..len], range.alignment, @returnAddress());
126 }
127 }
128
129 const count = try drawUsize(conjecture, 1, 96, 12);
130 var index: usize = 0;
131 while (index < count) : (index += 1) {
132 const alignment = try drawAlignment(conjecture);
133 const len = try drawUsize(conjecture, 1, max_small_size + 4096, 1);
134 const ptr = tiny_allocator.rawAlloc(len, alignment, @returnAddress()) orelse return error.OutOfMemory;
135 const slice = ptr[0..len];
136 @memset(slice, @truncate(index));
137
138 try std.testing.expect(std.mem.isAligned(@intFromPtr(ptr), alignment.toByteUnits()));
139 try ranges.append(property_allocator, .{
140 .start = @intFromPtr(ptr),
141 .end = @intFromPtr(ptr) + len,
142 .alignment = alignment,
143 });
144 }
145
146 try expectDisjoint(ranges.items);
147 }
148 };
149
150 pub const StateProperty = struct {
151 pub fn property(
152 conjecture: *hypothesis.ConjectureData,
153 property_allocator: Allocator,
154 ) !void {
155 var heap = GpAllocator.init(property_allocator, .{});
156 defer heap.deinit();
157 const tiny_allocator = heap.allocator();
158
159 var active: std.ArrayList(AllocationRecord) = .empty;
160 defer active.deinit(property_allocator);
161 defer {
162 for (active.items) |record| {
163 tiny_allocator.free(record.slice);
164 }
165 }
166
167 for (representative_lengths, 0..) |len, index| {
168 try appendFilledRecord(&active, property_allocator, tiny_allocator, len, @intCast(0x80 + index));
169 }
170
171 const steps = try drawUsize(conjecture, 1, 64, 16);
172 var step: usize = 0;
173 while (step < steps) : (step += 1) {
174 const op = try drawUsize(conjecture, 0, 99, 0);
175 if ((op < 45 and active.items.len < 6) or active.items.len == 0) {
176 const len = try drawAllocationLen(conjecture);
177 const fill: u8 = @intCast(step & 0xff);
178 try appendFilledRecord(&active, property_allocator, tiny_allocator, len, fill);
179 } else if (op < 80) {
180 const slot = try drawUsize(conjecture, 0, active.items.len - 1, 0);
181 var record = &active.items[slot];
182 const old_len = record.slice.len;
183 const new_len = try drawAllocationLen(conjecture);
184 const resized = try tiny_allocator.realloc(record.slice, new_len);
185 const prefix_len = @min(old_len, new_len);
186 record.slice = resized;
187 try expectRange(resized[0..@min(prefix_len, 4096)], record.fill);
188 fillSampled(resized, record.fill);
189 } else {
190 const slot = try drawUsize(conjecture, 0, active.items.len - 1, 0);
191 tiny_allocator.free(active.items[slot].slice);
192 _ = active.swapRemove(slot);
193 }
194
195 var ranges: std.ArrayList(Range) = .empty;
196 defer ranges.deinit(property_allocator);
197 for (active.items) |record| {
198 try expectSampled(record.slice, record.fill);
199 try ranges.append(property_allocator, .{
200 .start = @intFromPtr(record.slice.ptr),
201 .end = @intFromPtr(record.slice.ptr) + record.slice.len,
202 });
203 }
204 try expectDisjoint(ranges.items);
205 }
206 }
207 };
208
209 const StatsModel = struct {
210 small_allocations: u64 = 0,
211 small_frees: u64 = 0,
212 large_allocations: u64 = 0,
213 large_frees: u64 = 0,
214 active_small_bytes: usize = 0,
215 active_large_bytes: usize = 0,
216
217 fn allocate(model: *StatsModel, len: usize) void {
218 if (isSmallLen(len)) {
219 model.small_allocations += 1;
220 model.active_small_bytes += len;
221 } else {
222 model.large_allocations += 1;
223 model.active_large_bytes += len;
224 }
225 }
226
227 fn free(model: *StatsModel, len: usize) void {
228 if (isSmallLen(len)) {
229 model.small_frees += 1;
230 model.active_small_bytes -= len;
231 } else {
232 model.large_frees += 1;
233 model.active_large_bytes -= len;
234 }
235 }
236
237 fn resize(model: *StatsModel, old_len: usize, new_len: usize) void {
238 assert(isSmallLen(old_len) == isSmallLen(new_len));
239 if (isSmallLen(old_len)) {
240 if (new_len > old_len) {
241 model.active_small_bytes += new_len - old_len;
242 } else {
243 model.active_small_bytes -= old_len - new_len;
244 }
245 } else {
246 if (new_len > old_len) {
247 model.active_large_bytes += new_len - old_len;
248 } else {
249 model.active_large_bytes -= old_len - new_len;
250 }
251 }
252 }
253 };
254
255 fn expectStats(heap: *GpAllocator, model: StatsModel) !void {
256 const actual = heap.stats();
257 try std.testing.expectEqual(model.small_allocations, actual.small_allocations);
258 try std.testing.expectEqual(model.small_frees, actual.small_frees);
259 try std.testing.expectEqual(model.large_allocations, actual.large_allocations);
260 try std.testing.expectEqual(model.large_frees, actual.large_frees);
261 try std.testing.expectEqual(model.active_small_bytes, actual.active_small_bytes);
262 try std.testing.expectEqual(model.active_large_bytes, actual.active_large_bytes);
263 }
264
265 pub const StatsTraceProperty = struct {
266 pub fn property(
267 conjecture: *hypothesis.ConjectureData,
268 property_allocator: Allocator,
269 ) !void {
270 var heap = GpAllocator.init(property_allocator, .{ .collect_stats = true });
271 defer heap.deinit();
272 const tiny_allocator = heap.allocator();
273
274 var active: std.ArrayList(AllocationRecord) = .empty;
275 defer active.deinit(property_allocator);
276 defer {
277 for (active.items) |record| {
278 tiny_allocator.free(record.slice);
279 }
280 }
281
282 var model: StatsModel = .{};
283 for (representative_lengths, 0..) |len, index| {
284 try appendFilledRecord(&active, property_allocator, tiny_allocator, len, @intCast(0x40 + index));
285 model.allocate(len);
286 }
287 try expectStats(&heap, model);
288
289 const steps = try drawUsize(conjecture, 1, 96, 16);
290 var step: usize = 0;
291 while (step < steps) : (step += 1) {
292 const op = try drawUsize(conjecture, 0, 99, 0);
293 if ((op < 50 and active.items.len < 8) or active.items.len == 0) {
294 const len = try drawAllocationLen(conjecture);
295 const fill: u8 = @intCast(step & 0xff);
296 try appendFilledRecord(&active, property_allocator, tiny_allocator, len, fill);
297 model.allocate(len);
298 } else if (op < 75) {
299 const slot = try drawUsize(conjecture, 0, active.items.len - 1, 0);
300 var record = &active.items[slot];
301 const old_len = record.slice.len;
302 const min_len = if (isSmallLen(old_len)) @as(usize, 1) else max_small_size + 1;
303 if (old_len > min_len) {
304 const new_len = try drawUsize(conjecture, min_len, old_len, min_len);
305 const expect_in_place = if (isSmallLen(old_len))
306 size_class.indexFor(new_len, .@"1").? == size_class.indexFor(old_len, .@"1").?
307 else
308 true;
309 const resized = tiny_allocator.resize(record.slice, new_len);
310 try std.testing.expectEqual(expect_in_place, resized);
311 if (resized) {
312 record.slice = record.slice[0..new_len];
313 model.resize(old_len, new_len);
314 }
315 }
316 } else {
317 const slot = try drawUsize(conjecture, 0, active.items.len - 1, 0);
318 const record = active.items[slot];
319 tiny_allocator.free(record.slice);
320 model.free(record.slice.len);
321 _ = active.swapRemove(slot);
322 }
323 try expectStats(&heap, model);
324 }
325
326 while (active.items.len != 0) {
327 const record = active.pop().?;
328 tiny_allocator.free(record.slice);
329 model.free(record.slice.len);
330 try expectStats(&heap, model);
331 }
332 }
333 };
334
335 test "property: allocations are aligned and disjoint" {
336 try hypothesis.checkNamed(AlignmentProperty, "gpalloc-alignment", settings());
337 }
338
339 test "property: allocator operations preserve active ranges" {
340 try hypothesis.checkNamed(StateProperty, "gpalloc-state", settings());
341 }
342
343 test "property: stats match generated allocator traces" {
344 try hypothesis.checkNamed(StatsTraceProperty, "gpalloc-stats", settings());
345 }