lib/bumpalo/src/properties/buffer.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const bumpalo = @import("bumpalo");
3 const hypothesis = @import("hypothesis");
4
5 const Allocator = std.mem.Allocator;
6 const Alignment = std.mem.Alignment;
7 const Bump = bumpalo.Bump;
8 const CountingAllocator = std.testing.FailingAllocator;
9 const guard_value: u8 = 0xa5;
10 const caller_bytes = 1024;
11 const guard_bytes = 32;
12 const storage_bytes = caller_bytes + guard_bytes * 2;
13
14 const ResetKind = enum(u3) {
15 free_all,
16 retain_current,
17 retain_capacity,
18 retain_zero,
19 retain_tiny,
20 retain_limit,
21 };
22
23 const ResetCase = struct {
24 kind: ResetKind,
25 limit: usize = 512,
26 };
27
28 fn settings() hypothesis.Settings {
29 return hypothesis.Settings.quick()
30 .withSeed(0xCA11_E2B0)
31 .withDatabase("zig-out/hypothesis-failures/bumpalo-caller-buffer");
32 }
33
34 fn drawUsize(
35 conjecture: *hypothesis.ConjectureData,
36 min: usize,
37 max: usize,
38 shrink_towards: usize,
39 ) !usize {
40 return @intCast(try conjecture.drawInteger(
41 @intCast(min),
42 @intCast(max),
43 @intCast(shrink_towards),
44 ));
45 }
46
47 fn drawAlignment(conjecture: *hypothesis.ConjectureData) !Alignment {
48 const shift = try drawUsize(conjecture, 0, 6, 0);
49 return .fromByteUnits(@as(usize, 1) << @as(u6, @intCast(shift)));
50 }
51
52 fn contains(outer: []const u8, inner: []const u8) bool {
53 const outer_start = @intFromPtr(outer.ptr);
54 const outer_end = outer_start + outer.len;
55 const inner_start = @intFromPtr(inner.ptr);
56 return inner_start >= outer_start and
57 inner_start <= outer_end and
58 inner.len <= outer_end - inner_start;
59 }
60
61 fn expectGuards(storage: []const u8, caller_start: usize, caller_len: usize) !void {
62 for (storage[0..caller_start]) |byte| {
63 try std.testing.expectEqual(guard_value, byte);
64 }
65 for (storage[caller_start + caller_len ..]) |byte| {
66 try std.testing.expectEqual(guard_value, byte);
67 }
68 }
69
70 fn expectBalanced(counting: *const CountingAllocator) !void {
71 try std.testing.expectEqual(counting.allocations, counting.deallocations);
72 try std.testing.expectEqual(counting.allocated_bytes, counting.freed_bytes);
73 }
74
75 fn expectAccounting(
76 comptime Arena: type,
77 arena: *Arena,
78 counting: *const CountingAllocator,
79 caller: []const u8,
80 ) !void {
81 var caller_chunks: usize = 0;
82 var backing_chunks: usize = 0;
83 var iterator = arena.iterAllocatedChunks();
84 while (iterator.next()) |chunk| {
85 if (contains(caller, chunk)) {
86 caller_chunks += 1;
87 } else {
88 backing_chunks += 1;
89 }
90 }
91 try std.testing.expect(caller_chunks <= 1);
92 try std.testing.expectEqual(
93 counting.allocations,
94 counting.deallocations + backing_chunks,
95 );
96 try std.testing.expect(counting.freed_bytes <= counting.allocated_bytes);
97 }
98
99 fn expectCallerAllocation(comptime Arena: type, arena: *Arena, caller: []u8) !void {
100 const bytes = try arena.alloc(u8, 1);
101 try std.testing.expect(contains(caller, bytes));
102 }
103
104 fn expectFill(bytes: []const u8, expected: u8) !void {
105 for (bytes) |byte| try std.testing.expectEqual(expected, byte);
106 }
107
108 fn forceSpill(comptime Arena: type, arena: *Arena, caller: []u8) !void {
109 const bytes = try arena.alloc(u8, caller.len + 4096);
110 bytes[0] = 0x5a;
111 try std.testing.expect(!contains(caller, bytes));
112 }
113
114 fn applyReset(
115 comptime Arena: type,
116 arena: *Arena,
117 kind: ResetKind,
118 limit: usize,
119 ) bool {
120 return switch (kind) {
121 .free_all => arena.reset(.free_all),
122 .retain_current => arena.reset(.retain_current),
123 .retain_capacity => arena.reset(.retain_capacity),
124 .retain_zero => arena.reset(.{ .retain_with_limit = 0 }),
125 .retain_tiny => arena.reset(.{ .retain_with_limit = 1 }),
126 .retain_limit => arena.reset(.{ .retain_with_limit = limit }),
127 };
128 }
129
130 fn expectResetPostcondition(
131 comptime Arena: type,
132 arena: *const Arena,
133 kind: ResetKind,
134 limit: usize,
135 did_reset: bool,
136 ) !void {
137 if (!did_reset) return;
138 switch (kind) {
139 .retain_zero => try std.testing.expectEqual(@as(usize, 0), arena.queryCapacity()),
140 .retain_tiny => try std.testing.expect(arena.queryCapacity() <= 1),
141 .retain_limit => try std.testing.expect(arena.queryCapacity() <= limit),
142 .free_all, .retain_current, .retain_capacity => {},
143 }
144 }
145
146 fn exerciseResetCase(reset_case: ResetCase) !void {
147 var storage: [storage_bytes]u8 = @splat(guard_value);
148 const caller_start = guard_bytes + 1;
149 const caller = storage[caller_start .. caller_start + caller_bytes];
150 var counting = CountingAllocator.init(std.testing.allocator, .{});
151 {
152 var arena = try Bump.initBuffer(counting.allocator(), caller);
153 defer arena.deinit();
154 try expectCallerAllocation(Bump, &arena, caller);
155 try forceSpill(Bump, &arena, caller);
156 try expectAccounting(Bump, &arena, &counting, caller);
157 const did_reset = applyReset(Bump, &arena, reset_case.kind, reset_case.limit);
158 try std.testing.expect(did_reset);
159 try expectResetPostcondition(
160 Bump,
161 &arena,
162 reset_case.kind,
163 reset_case.limit,
164 did_reset,
165 );
166 try expectAccounting(Bump, &arena, &counting, caller);
167 try std.testing.expect(arena.reset(.free_all));
168 try expectCallerAllocation(Bump, &arena, caller);
169 try std.testing.expect(arena.reset(.free_all));
170 try expectCallerAllocation(Bump, &arena, caller);
171 try expectAccounting(Bump, &arena, &counting, caller);
172 }
173 try expectBalanced(&counting);
174 try expectGuards(&storage, caller_start, caller.len);
175 }
176
177 fn exerciseFailure(reset_case: ResetCase) !void {
178 var storage: [storage_bytes]u8 = @splat(guard_value);
179 const caller_start = guard_bytes + 1;
180 const caller = storage[caller_start .. caller_start + caller_bytes];
181 var counting = CountingAllocator.init(std.testing.allocator, .{});
182 {
183 var arena = try Bump.initBuffer(counting.allocator(), caller);
184 defer arena.deinit();
185 try forceSpill(Bump, &arena, caller);
186 counting.fail_index = counting.alloc_index;
187 try std.testing.expect(!applyReset(Bump, &arena, reset_case.kind, reset_case.limit));
188 counting.fail_index = std.math.maxInt(usize);
189 try expectCallerAllocation(Bump, &arena, caller);
190 try expectAccounting(Bump, &arena, &counting, caller);
191 }
192 try expectBalanced(&counting);
193 try expectGuards(&storage, caller_start, caller.len);
194 }
195
196 fn exerciseCoveredResets(
197 comptime Arena: type,
198 arena: *Arena,
199 counting: *CountingAllocator,
200 caller: []u8,
201 retained_limit: usize,
202 ) !void {
203 const cases = [_]ResetCase{
204 .{ .kind = .free_all },
205 .{ .kind = .retain_current },
206 .{ .kind = .retain_capacity },
207 .{ .kind = .retain_zero },
208 .{ .kind = .retain_tiny },
209 .{ .kind = .retain_limit, .limit = retained_limit },
210 };
211 for (cases) |reset_case| {
212 try std.testing.expect(arena.reset(.free_all));
213 try forceSpill(Arena, arena, caller);
214 const did_reset = applyReset(Arena, arena, reset_case.kind, reset_case.limit);
215 try std.testing.expect(did_reset);
216 try expectResetPostcondition(
217 Arena,
218 arena,
219 reset_case.kind,
220 reset_case.limit,
221 did_reset,
222 );
223 try expectAccounting(Arena, arena, counting, caller);
224 try std.testing.expect(arena.reset(.free_all));
225 try expectCallerAllocation(Arena, arena, caller);
226 try expectAccounting(Arena, arena, counting, caller);
227 }
228 }
229
230 fn exerciseRandomStep(
231 comptime Arena: type,
232 conjecture: *hypothesis.ConjectureData,
233 arena: *Arena,
234 counting: *CountingAllocator,
235 caller: []u8,
236 ) !void {
237 const op = try drawUsize(conjecture, 0, 99, 0);
238 if (op < 55) {
239 const len = try drawUsize(conjecture, 0, 2048, 1);
240 const alignment = try drawAlignment(conjecture);
241 const bytes = try arena.allocBytes(len, alignment);
242 if (len != 0) bytes[0] = @intCast(op);
243 } else {
244 const raw_kind = try drawUsize(conjecture, 0, 5, 0);
245 const kind: ResetKind = @fromBackingInt(@intCast(raw_kind));
246 const limit = try drawUsize(conjecture, 0, 2048, 1);
247 const can_allocate = kind == .retain_capacity or kind == .retain_limit;
248 const inject = can_allocate and try drawUsize(conjecture, 0, 3, 0) == 0;
249 if (inject) counting.fail_index = counting.alloc_index;
250 const did_reset = applyReset(Arena, arena, kind, limit);
251 counting.fail_index = std.math.maxInt(usize);
252 try expectResetPostcondition(Arena, arena, kind, limit, did_reset);
253 if (!did_reset) {
254 try std.testing.expect(inject);
255 try expectCallerAllocation(Arena, arena, caller);
256 }
257 }
258 try expectAccounting(Arena, arena, counting, caller);
259 }
260
261 fn exerciseProperty(
262 comptime Arena: type,
263 conjecture: *hypothesis.ConjectureData,
264 counting: *CountingAllocator,
265 caller: []u8,
266 ) !void {
267 var arena = try Arena.initBuffer(counting.allocator(), caller);
268 defer arena.deinit();
269 const retained_max = caller.len * 2;
270 const retained_limit = try drawUsize(
271 conjecture,
272 2,
273 retained_max,
274 @min(512, retained_max),
275 );
276 try exerciseCoveredResets(Arena, &arena, counting, caller, retained_limit);
277 const steps = try drawUsize(conjecture, 1, 40, 8);
278 var step: usize = 0;
279 while (step < steps) : (step += 1) {
280 try exerciseRandomStep(Arena, conjecture, &arena, counting, caller);
281 }
282 try std.testing.expect(arena.reset(.free_all));
283 try expectCallerAllocation(Arena, &arena, caller);
284 try expectAccounting(Arena, &arena, counting, caller);
285 }
286
287 fn CallerBufferProperty(comptime Arena: type) type {
288 return struct {
289 pub fn property(
290 conjecture: *hypothesis.ConjectureData,
291 property_allocator: Allocator,
292 ) !void {
293 var storage: [storage_bytes]u8 = @splat(guard_value);
294 const caller_start = try drawUsize(conjecture, 0, guard_bytes, 1);
295 const caller_len = try drawUsize(conjecture, 96, caller_bytes, 256);
296 const caller = storage[caller_start .. caller_start + caller_len];
297 var counting = CountingAllocator.init(property_allocator, .{});
298 try exerciseProperty(Arena, conjecture, &counting, caller);
299 try expectBalanced(&counting);
300 try expectGuards(&storage, caller_start, caller.len);
301 }
302 };
303 }
304
305 const StrongBump = bumpalo.BumpAllocator(16);
306 const DefaultCallerBufferProperty = CallerBufferProperty(Bump);
307 const StrongCallerBufferProperty = CallerBufferProperty(StrongBump);
308
309 test "caller buffer reset modes preserve ownership through teardown" {
310 const cases = [_]ResetCase{
311 .{ .kind = .free_all },
312 .{ .kind = .retain_current },
313 .{ .kind = .retain_capacity },
314 .{ .kind = .retain_zero },
315 .{ .kind = .retain_tiny },
316 .{ .kind = .retain_limit },
317 };
318 for (cases) |reset_case| try exerciseResetCase(reset_case);
319 }
320
321 test "failed retained replacements restore the caller buffer" {
322 try exerciseFailure(.{ .kind = .retain_capacity });
323 try exerciseFailure(.{ .kind = .retain_limit });
324 }
325
326 test "allocator view follows the caller buffer root lifecycle" {
327 var storage: [storage_bytes]u8 = @splat(guard_value);
328 const caller_start = guard_bytes + 1;
329 const caller = storage[caller_start .. caller_start + caller_bytes];
330 var counting = CountingAllocator.init(std.testing.allocator, .{});
331 {
332 var arena = try Bump.initBuffer(counting.allocator(), caller);
333 defer arena.deinit();
334 const allocator_instance = arena.allocator();
335
336 var linked = try allocator_instance.alloc(u8, 16);
337 try std.testing.expect(contains(caller, linked));
338 @memset(linked, 0x16);
339 linked = allocator_instance.remap(linked, 24) orelse return error.RemapFailed;
340 try std.testing.expect(contains(caller, linked));
341 try expectFill(linked[0..16], 0x16);
342 allocator_instance.free(linked);
343 try std.testing.expectEqual(@as(usize, 0), counting.allocations);
344 try expectAccounting(Bump, &arena, &counting, caller);
345
346 const spill = try allocator_instance.alloc(u8, caller.len + 4096);
347 try std.testing.expect(!contains(caller, spill));
348 try std.testing.expect(arena.reset(.retain_current));
349 try expectAccounting(Bump, &arena, &counting, caller);
350
351 var detached = try allocator_instance.alloc(u8, 32);
352 @memset(detached, 0x32);
353 detached = allocator_instance.remap(detached, 48) orelse return error.RemapFailed;
354 try std.testing.expect(!contains(caller, detached));
355 try expectFill(detached[0..32], 0x32);
356 allocator_instance.free(detached);
357 try expectAccounting(Bump, &arena, &counting, caller);
358
359 try std.testing.expect(arena.reset(.free_all));
360 var restored = try allocator_instance.alloc(u8, 16);
361 try std.testing.expect(contains(caller, restored));
362 restored = allocator_instance.remap(restored, 24) orelse return error.RemapFailed;
363 try std.testing.expect(contains(caller, restored));
364 allocator_instance.free(restored);
365 try expectAccounting(Bump, &arena, &counting, caller);
366 }
367 try expectBalanced(&counting);
368 try expectGuards(&storage, caller_start, caller.len);
369 }
370
371 test "property: caller buffer lifecycles preserve allocator ownership" {
372 try hypothesis.checkNamed(
373 DefaultCallerBufferProperty,
374 "bumpalo-caller-buffer",
375 settings(),
376 );
377 }
378
379 test "property: aligned caller buffer lifecycles preserve allocator ownership" {
380 try hypothesis.checkNamed(
381 StrongCallerBufferProperty,
382 "bumpalo-caller-buffer-aligned",
383 settings(),
384 );
385 }