lib/bumpalo/src/properties/capacity.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 Bump = bumpalo.Bump;
7 const CountingAllocator = std.testing.FailingAllocator;
8 const guard_value: u8 = 0x6d;
9 const guard_bytes = 32;
10 const caller_bytes = 1024;
11 const storage_bytes = caller_bytes + guard_bytes * 2;
12
13 fn settings() hypothesis.Settings {
14 return hypothesis.Settings.quick()
15 .withSeed(0xCA9A_C17E)
16 .withDatabase("zig-out/hypothesis-failures/bumpalo-capacity");
17 }
18
19 fn drawUsize(
20 conjecture: *hypothesis.ConjectureData,
21 min: usize,
22 max: usize,
23 shrink_towards: usize,
24 ) !usize {
25 return @intCast(try conjecture.drawInteger(
26 @intCast(min),
27 @intCast(max),
28 @intCast(shrink_towards),
29 ));
30 }
31
32 fn contains(outer: []const u8, inner: []const u8) bool {
33 const outer_start = @intFromPtr(outer.ptr);
34 const outer_end = outer_start + outer.len;
35 const inner_start = @intFromPtr(inner.ptr);
36 return inner_start >= outer_start and
37 inner_start <= outer_end and
38 inner.len <= outer_end - inner_start;
39 }
40
41 fn expectAccounting(
42 arena: *const Bump,
43 counting: *const CountingAllocator,
44 caller_capacity: usize,
45 ) !void {
46 const backing_capacity = arena.queryBackingDataCapacity();
47 const linked_caller_capacity = arena.queryCallerDataCapacity();
48 const active_backing_chunks = counting.allocations - counting.deallocations;
49 try std.testing.expectEqual(
50 arena.queryCapacity(),
51 backing_capacity + linked_caller_capacity,
52 );
53 try std.testing.expect(
54 linked_caller_capacity == 0 or linked_caller_capacity == caller_capacity,
55 );
56 try std.testing.expectEqual(
57 backing_capacity == 0,
58 active_backing_chunks == 0,
59 );
60 }
61
62 fn exhaustCurrent(arena: *Bump) !void {
63 const available = arena.queryCurrentChunkAvailable();
64 if (available != 0) _ = try arena.alloc(u8, available);
65 }
66
67 fn exercise(
68 arena: *Bump,
69 counting: *CountingAllocator,
70 caller: []u8,
71 caller_capacity: usize,
72 limit: usize,
73 request: usize,
74 ) !void {
75 arena.setChunkGrowthGoal(Bump.default_chunk_capacity);
76 arena.setBackingDataCapacityLimit(limit);
77 try exhaustCurrent(arena);
78 const backed = try arena.alloc(u8, request);
79 try std.testing.expect(!contains(caller, backed));
80 try std.testing.expect(arena.queryBackingDataCapacity() <= limit);
81 try expectAccounting(arena, counting, caller_capacity);
82
83 const first_backing_capacity = arena.queryBackingDataCapacity();
84 try exhaustCurrent(arena);
85 const additional = try arena.alloc(u8, 1);
86 try std.testing.expect(!contains(caller, additional));
87 try std.testing.expect(
88 arena.queryBackingDataCapacity() > first_backing_capacity,
89 );
90 try std.testing.expect(arena.queryBackingDataCapacity() <= limit);
91 try expectAccounting(arena, counting, caller_capacity);
92
93 const linked_backing_capacity = arena.queryBackingDataCapacity();
94 try std.testing.expect(arena.reset(.retain_current));
95 try std.testing.expect(
96 arena.queryBackingDataCapacity() > 0 and
97 arena.queryBackingDataCapacity() < linked_backing_capacity,
98 );
99 try std.testing.expectEqual(@as(usize, 0), arena.queryCallerDataCapacity());
100 try expectAccounting(arena, counting, caller_capacity);
101
102 try std.testing.expect(arena.reset(.free_all));
103 try std.testing.expectEqual(@as(usize, 0), arena.queryBackingDataCapacity());
104 try std.testing.expectEqual(caller_capacity, arena.queryCallerDataCapacity());
105 try expectAccounting(arena, counting, caller_capacity);
106
107 arena.setBackingDataCapacityLimit(0);
108 _ = try arena.alloc(u8, 1);
109 try exhaustCurrent(arena);
110 try std.testing.expectError(error.OutOfMemory, arena.alloc(u8, 1));
111 try std.testing.expectEqual(@as(usize, 0), arena.queryBackingDataCapacity());
112 try expectAccounting(arena, counting, caller_capacity);
113
114 arena.setBackingDataCapacityLimit(512);
115 _ = try arena.alloc(u8, 1);
116 try std.testing.expect(arena.queryBackingDataCapacity() > 0);
117 arena.setBackingDataCapacityLimit(0);
118 try std.testing.expect(arena.reset(.{ .retain_with_limit = 16 }));
119 try std.testing.expectEqual(@as(usize, 0), arena.queryCapacity());
120 try expectAccounting(arena, counting, caller_capacity);
121 try std.testing.expect(arena.reset(.free_all));
122 try std.testing.expectEqual(caller_capacity, arena.queryCallerDataCapacity());
123 try expectAccounting(arena, counting, caller_capacity);
124 }
125
126 pub const CallerCapacityProperty = struct {
127 pub fn property(
128 conjecture: *hypothesis.ConjectureData,
129 property_allocator: Allocator,
130 ) !void {
131 var storage: [storage_bytes]u8 = @splat(guard_value);
132 const caller_start = try drawUsize(conjecture, 0, guard_bytes, 1);
133 const caller_len = try drawUsize(conjecture, 128, caller_bytes, 256);
134 const caller = storage[caller_start .. caller_start + caller_len];
135 const limit = try drawUsize(conjecture, 512, 1024, 512);
136 const representable_limit = std.mem.alignBackward(
137 usize,
138 limit,
139 bumpalo.chunk_alignment,
140 );
141 const request = try drawUsize(
142 conjecture,
143 1,
144 @min(representable_limit, 128),
145 1,
146 );
147 var counting = CountingAllocator.init(property_allocator, .{});
148 {
149 var arena = try Bump.initBuffer(counting.allocator(), caller);
150 defer arena.deinit();
151 const caller_capacity = arena.queryCallerDataCapacity();
152 try std.testing.expect(caller_capacity > 0);
153 try exercise(
154 &arena,
155 &counting,
156 caller,
157 caller_capacity,
158 limit,
159 request,
160 );
161 }
162 try std.testing.expectEqual(counting.allocations, counting.deallocations);
163 try std.testing.expectEqual(counting.allocated_bytes, counting.freed_bytes);
164 for (storage[0..caller_start]) |byte| {
165 try std.testing.expectEqual(guard_value, byte);
166 }
167 for (storage[caller_start + caller.len ..]) |byte| {
168 try std.testing.expectEqual(guard_value, byte);
169 }
170 }
171 };
172
173 test "property: caller storage is outside the backing data capacity limit" {
174 try hypothesis.checkNamed(
175 CallerCapacityProperty,
176 "bumpalo-caller-capacity",
177 settings(),
178 );
179 }