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