1//! Supports single-threaded targets that have a sbrk-like primitive which includes
2//! Linux and WebAssembly.
3//!
4//! On Linux, assumes exclusive access to the brk syscall.
5const BrkAllocator = @This();
6const builtin = @import("builtin");
7
8const std = @import("../std.zig");
9const Allocator = std.mem.Allocator;
10const Alignment = std.mem.Alignment;
11const assert = std.debug.assert;
12const math = std.math;
13
14comptime {
15 if (!builtin.single_threaded) @compileError("unsupported");
16}
17
18next_addrs: [size_class_count]usize = @splat(0),
19/// For each size class, points to the freed pointer.
20frees: [size_class_count]usize = @splat(0),
21/// For each big size class, points to the freed pointer.
22big_frees: [big_size_class_count]usize = @splat(0),
23prev_brk: usize = 0,
24
25var global: BrkAllocator = .{};
26
27pub const vtable: Allocator.VTable = .{
28 .alloc = alloc,
29 .resize = resize,
30 .remap = remap,
31 .free = free,
32};
33
34pub const Error = Allocator.Error;
35
36const max_usize = math.maxInt(usize);
37const ushift = math.Log2Int(usize);
38const bigpage_size: comptime_int = @max(64 * 1024, std.heap.page_size_max);
39const bigpage_count = max_usize / bigpage_size;
40
41/// Because of storing free list pointers, the minimum size class is 3.
42const min_class = math.log2(math.ceilPowerOfTwoAssert(usize, 1 + @sizeOf(usize)));
43const size_class_count = math.log2(bigpage_size) - min_class;
44/// 0 - 1 bigpage
45/// 1 - 2 bigpages
46/// 2 - 4 bigpages
47/// etc.
48const big_size_class_count = math.log2(bigpage_count) + 1;
49
50fn alloc(ctx: *anyopaque, len: usize, alignment: Alignment, return_address: usize) ?[*]u8 {
51 _ = ctx;
52 _ = return_address;
53 // Make room for the freelist next pointer.
54 const actual_len = @max(len +| @sizeOf(usize), alignment.toByteUnits());
55 const slot_size = math.ceilPowerOfTwo(usize, actual_len) catch return null;
56 const class = math.log2(slot_size) - min_class;
57 if (class < size_class_count) {
58 const addr = a: {
59 const top_free_ptr = global.frees[class];
60 if (top_free_ptr != 0) {
61 const node: *usize = @ptrFromInt(top_free_ptr + (slot_size - @sizeOf(usize)));
62 global.frees[class] = node.*;
63 break :a top_free_ptr;
64 }
65
66 const next_addr = global.next_addrs[class];
67 if (next_addr % bigpage_size == 0) {
68 const addr = allocBigPages(1);
69 if (addr == 0) return null;
70 //std.debug.print("allocated fresh slot_size={d} class={d} addr=0x{x}\n", .{
71 // slot_size, class, addr,
72 //});
73 global.next_addrs[class] = addr + slot_size;
74 break :a addr;
75 } else {
76 global.next_addrs[class] = next_addr + slot_size;
77 break :a next_addr;
78 }
79 };
80 return @ptrFromInt(addr);
81 }
82 const bigpages_needed = bigPagesNeeded(actual_len);
83 return @ptrFromInt(allocBigPages(bigpages_needed));
84}
85
86fn resize(
87 ctx: *anyopaque,
88 buf: []u8,
89 alignment: Alignment,
90 new_len: usize,
91 return_address: usize,
92) bool {
93 _ = ctx;
94 _ = return_address;
95 // We don't want to move anything from one size class to another, but we
96 // can recover bytes in between powers of two.
97 const buf_align = alignment.toByteUnits();
98 const old_actual_len = @max(buf.len + @sizeOf(usize), buf_align);
99 const new_actual_len = @max(new_len +| @sizeOf(usize), buf_align);
100 const old_small_slot_size = math.ceilPowerOfTwoAssert(usize, old_actual_len);
101 const old_small_class = math.log2(old_small_slot_size) - min_class;
102 if (old_small_class < size_class_count) {
103 const new_small_slot_size = math.ceilPowerOfTwo(usize, new_actual_len) catch return false;
104 return old_small_slot_size == new_small_slot_size;
105 } else {
106 const old_bigpages_needed = bigPagesNeeded(old_actual_len);
107 const old_big_slot_pages = math.ceilPowerOfTwoAssert(usize, old_bigpages_needed);
108 const new_bigpages_needed = bigPagesNeeded(new_actual_len);
109 const new_big_slot_pages = math.ceilPowerOfTwo(usize, new_bigpages_needed) catch return false;
110 return old_big_slot_pages == new_big_slot_pages;
111 }
112}
113
114fn remap(
115 context: *anyopaque,
116 memory: []u8,
117 alignment: Alignment,
118 new_len: usize,
119 return_address: usize,
120) ?[*]u8 {
121 return if (resize(context, memory, alignment, new_len, return_address)) memory.ptr else null;
122}
123
124fn free(
125 ctx: *anyopaque,
126 buf: []u8,
127 alignment: Alignment,
128 return_address: usize,
129) void {
130 _ = ctx;
131 _ = return_address;
132 const buf_align = alignment.toByteUnits();
133 const actual_len = @max(buf.len + @sizeOf(usize), buf_align);
134 const slot_size = math.ceilPowerOfTwoAssert(usize, actual_len);
135 const class = math.log2(slot_size) - min_class;
136 const addr = @intFromPtr(buf.ptr);
137 if (class < size_class_count) {
138 const node: *usize = @ptrFromInt(addr + (slot_size - @sizeOf(usize)));
139 node.* = global.frees[class];
140 global.frees[class] = addr;
141 } else {
142 const bigpages_needed = bigPagesNeeded(actual_len);
143 const pow2_pages = math.ceilPowerOfTwoAssert(usize, bigpages_needed);
144 const big_slot_size_bytes = pow2_pages * bigpage_size;
145 const node: *usize = @ptrFromInt(addr + (big_slot_size_bytes - @sizeOf(usize)));
146 const big_class = math.log2(pow2_pages);
147 node.* = global.big_frees[big_class];
148 global.big_frees[big_class] = addr;
149 }
150}
151
152inline fn bigPagesNeeded(byte_count: usize) usize {
153 return (byte_count + (bigpage_size + (@sizeOf(usize) - 1))) / bigpage_size;
154}
155
156fn allocBigPages(n: usize) usize {
157 const pow2_pages = math.ceilPowerOfTwoAssert(usize, n);
158 const slot_size_bytes = pow2_pages * bigpage_size;
159 const class = math.log2(pow2_pages);
160
161 const top_free_ptr = global.big_frees[class];
162 if (top_free_ptr != 0) {
163 const node: *usize = @ptrFromInt(top_free_ptr + (slot_size_bytes - @sizeOf(usize)));
164 global.big_frees[class] = node.*;
165 return top_free_ptr;
166 }
167
168 if (builtin.cpu.arch.isWasm()) {
169 comptime assert(std.heap.page_size_max == std.heap.page_size_min);
170 const page_size = std.heap.page_size_max;
171 const pages_per_bigpage = bigpage_size / page_size;
172 const page_index = @wasmMemoryGrow(0, pow2_pages * pages_per_bigpage);
173 if (page_index == -1) return 0;
174 return @as(usize, @intCast(page_index)) * page_size;
175 } else if (builtin.os.tag == .linux) {
176 const prev_brk = global.prev_brk;
177 const start_brk = if (prev_brk == 0)
178 std.mem.alignForward(usize, std.os.linux.brk(0), bigpage_size)
179 else
180 prev_brk;
181 const end_brk = start_brk + pow2_pages * bigpage_size;
182 const new_prev_brk = std.os.linux.brk(end_brk);
183 global.prev_brk = new_prev_brk;
184 if (new_prev_brk != end_brk) return 0;
185 return start_brk;
186 } else {
187 @compileError("no sbrk-like OS primitive available");
188 }
189}
190
191const test_ally: Allocator = .{
192 .ptr = undefined,
193 .vtable = &vtable,
194};
195
196test "small allocations - free in same order" {
197 var list: [513]*u64 = undefined;
198
199 var i: usize = 0;
200 while (i < 513) : (i += 1) {
201 const ptr = try test_ally.create(u64);
202 list[i] = ptr;
203 }
204
205 for (list) |ptr| {
206 test_ally.destroy(ptr);
207 }
208}
209
210test "small allocations - free in reverse order" {
211 var list: [513]*u64 = undefined;
212
213 var i: usize = 0;
214 while (i < 513) : (i += 1) {
215 const ptr = try test_ally.create(u64);
216 list[i] = ptr;
217 }
218
219 i = list.len;
220 while (i > 0) {
221 i -= 1;
222 const ptr = list[i];
223 test_ally.destroy(ptr);
224 }
225}
226
227test "large allocations" {
228 const ptr1 = try test_ally.alloc(u64, 42768);
229 const ptr2 = try test_ally.alloc(u64, 52768);
230 test_ally.free(ptr1);
231 const ptr3 = try test_ally.alloc(u64, 62768);
232 test_ally.free(ptr3);
233 test_ally.free(ptr2);
234}
235
236test "very large allocation" {
237 try std.testing.expectError(error.OutOfMemory, test_ally.alloc(u8, math.maxInt(usize)));
238}
239
240test "realloc" {
241 var slice = try test_ally.alignedAlloc(u8, .of(u32), 1);
242 defer test_ally.free(slice);
243 slice[0] = 0x12;
244
245 // This reallocation should keep its pointer address.
246 const old_slice = slice;
247 slice = try test_ally.realloc(slice, 2);
248 try std.testing.expect(old_slice.ptr == slice.ptr);
249 try std.testing.expect(slice[0] == 0x12);
250 slice[1] = 0x34;
251
252 // This requires upgrading to a larger size class
253 slice = try test_ally.realloc(slice, 17);
254 try std.testing.expect(slice[0] == 0x12);
255 try std.testing.expect(slice[1] == 0x34);
256}
257
258test "shrink" {
259 var slice = try test_ally.alloc(u8, 20);
260 defer test_ally.free(slice);
261
262 @memset(slice, 0x11);
263
264 try std.testing.expect(test_ally.resize(slice, 17));
265 slice = slice[0..17];
266
267 for (slice) |b| {
268 try std.testing.expect(b == 0x11);
269 }
270
271 try std.testing.expect(test_ally.resize(slice, 16));
272 slice = slice[0..16];
273
274 for (slice) |b| {
275 try std.testing.expect(b == 0x11);
276 }
277}
278
279test "large object - grow" {
280 if (builtin.os.tag == .linux) return error.SkipZigTest;
281
282 var slice1 = try test_ally.alloc(u8, bigpage_size * 2 - 20);
283 defer test_ally.free(slice1);
284
285 const old = slice1;
286 slice1 = try test_ally.realloc(slice1, bigpage_size * 2 - 10);
287 try std.testing.expectEqual(slice1.ptr, old.ptr);
288
289 slice1 = try test_ally.realloc(slice1, bigpage_size * 2);
290 slice1 = try test_ally.realloc(slice1, bigpage_size * 2 + 1);
291}
292
293test "realloc small object to large object" {
294 var slice = try test_ally.alloc(u8, 70);
295 defer test_ally.free(slice);
296 slice[0] = 0x12;
297 slice[60] = 0x34;
298
299 // This requires upgrading to a large object
300 const large_object_size = bigpage_size * 2 + 50;
301 slice = try test_ally.realloc(slice, large_object_size);
302 try std.testing.expect(slice[0] == 0x12);
303 try std.testing.expect(slice[60] == 0x34);
304}
305
306test "shrink large object to large object" {
307 var slice = try test_ally.alloc(u8, bigpage_size * 2 + 50);
308 defer test_ally.free(slice);
309 slice[0] = 0x12;
310 slice[60] = 0x34;
311
312 try std.testing.expect(test_ally.resize(slice, bigpage_size * 2 + 1));
313 slice = slice[0 .. bigpage_size * 2 + 1];
314 try std.testing.expect(slice[0] == 0x12);
315 try std.testing.expect(slice[60] == 0x34);
316
317 try std.testing.expect(test_ally.resize(slice, bigpage_size * 2 + 1));
318 try std.testing.expect(slice[0] == 0x12);
319 try std.testing.expect(slice[60] == 0x34);
320
321 slice = try test_ally.realloc(slice, bigpage_size * 2);
322 try std.testing.expect(slice[0] == 0x12);
323 try std.testing.expect(slice[60] == 0x34);
324}
325
326test "realloc large object to small object" {
327 var slice = try test_ally.alloc(u8, bigpage_size * 2 + 50);
328 defer test_ally.free(slice);
329 slice[0] = 0x12;
330 slice[16] = 0x34;
331
332 slice = try test_ally.realloc(slice, 19);
333 try std.testing.expect(slice[0] == 0x12);
334 try std.testing.expect(slice[16] == 0x34);
335}
336
337test "objects of size 1024 and 2048" {
338 const slice = try test_ally.alloc(u8, 1025);
339 const slice2 = try test_ally.alloc(u8, 3000);
340
341 test_ally.free(slice);
342 test_ally.free(slice2);
343}
344
345test "standard allocator tests" {
346 try std.heap.testAllocator(test_ally);
347 try std.heap.testAllocatorAligned(test_ally);
348}