1//! Based on wrapping a stateless Zig Allocator implementation, appropriate for:
2//! - ReleaseFast and ReleaseSmall optimization modes, with multi-threading
3//! enabled.
4//! - WebAssembly or Linux in single-threaded release modes.
5//!
6//! Because the libc APIs don't have client alignment and size tracking, in
7//! order to take advantage of Zig allocator implementations, additional
8//! metadata must be stored in the allocations.
9//!
10//! This implementation stores the metadata just before the pointer returned
11//! from `malloc`, just like many libc malloc implementations do, including
12//! musl. This has the downside of causing fragmentation for allocations with
13//! higher alignment, however most of that memory can be recovered by
14//! preemptively putting the gap onto the freelist.
15const builtin = @import("builtin");
16
17const std = @import("std");
18const assert = std.debug.assert;
19const Alignment = std.mem.Alignment;
20const alignment_bytes = @max(@alignOf(std.c.max_align_t), @sizeOf(Header));
21const alignment: Alignment = .fromByteUnits(alignment_bytes);
22
23const symbol = @import("../c.zig").symbol;
24
25comptime {
26 // Dependency on external errno location.
27 if (builtin.link_libc) {
28 symbol(&malloc, "malloc");
29 symbol(&aligned_alloc, "aligned_alloc");
30 symbol(&posix_memalign, "posix_memalign");
31 symbol(&calloc, "calloc");
32 symbol(&realloc, "realloc");
33 symbol(&reallocarray, "reallocarray");
34 symbol(&free, "free");
35 symbol(&malloc_usable_size, "malloc_usable_size");
36
37 symbol(&valloc, "valloc");
38 symbol(&memalign, "memalign");
39 }
40}
41
42const no_context: *anyopaque = undefined;
43const no_ra: usize = undefined;
44const vtable = switch (builtin.cpu.arch) {
45 .wasm32, .wasm64 => std.heap.WasmAllocator.vtable,
46 else => if (builtin.single_threaded) std.heap.BrkAllocator.vtable else std.heap.SmpAllocator.vtable,
47};
48
49/// Needed because libc memory allocators don't provide old alignment and size
50/// which are required by Zig memory allocators.
51const Header = packed struct(u64) {
52 alignment: Alignment,
53 /// Does not include the extra alignment bytes added.
54 size: Size,
55 canary: Canary = magic,
56
57 comptime {
58 assert(@sizeOf(Header) <= alignment_bytes);
59 }
60
61 const safety = switch (builtin.mode) {
62 .debug, .safe => true,
63 .fast, .small => false,
64 };
65 const max_addr_bits = switch (safety) {
66 true => 48, // Ensures space for Canary bits.
67 false => 64,
68 };
69 const Size = @Int(.unsigned, @min(max_addr_bits, 64 - @bitSizeOf(Alignment), @bitSizeOf(usize)));
70 const Canary = @Int(.unsigned, 64 - @bitSizeOf(Alignment) - @bitSizeOf(Size));
71 const magic: Canary = switch (safety) {
72 true => @truncate(@as(u64, 0x76fa65bebb3d7a39)), // statically chosen entropy
73 false => 0,
74 };
75
76 fn get(base: [*]align(alignment_bytes) u8) Header {
77 const header: *Header = @ptrCast(base - @sizeOf(Header));
78 assert(header.canary == magic);
79 return header.*;
80 }
81
82 fn set(base: [*]align(alignment_bytes) u8, a: Alignment, size: Size) [*]align(alignment_bytes) u8 {
83 const header: *Header = @ptrCast(base - @sizeOf(Header));
84 header.* = .{ .alignment = a, .size = size };
85 return base;
86 }
87};
88
89fn malloc(n: usize) callconv(.c) ?[*]align(alignment_bytes) u8 {
90 const size = std.math.cast(Header.Size, n) orelse return nomem();
91 const ptr: [*]align(alignment_bytes) u8 = @alignCast(
92 vtable.alloc(no_context, n + alignment_bytes, alignment, no_ra) orelse return nomem(),
93 );
94 const base = ptr + alignment_bytes;
95 return Header.set(base, alignment, size);
96}
97
98fn aligned_alloc(alloc_alignment: usize, n: usize) callconv(.c) ?[*]align(alignment_bytes) u8 {
99 return aligned_alloc_inner(alloc_alignment, n) orelse return nomem();
100}
101
102/// Avoids setting errno so it can be called by `posix_memalign`.
103fn aligned_alloc_inner(alloc_alignment: usize, n: usize) ?[*]align(alignment_bytes) u8 {
104 const size = std.math.cast(Header.Size, n) orelse return null;
105 const max_align = alignment.max(.fromByteUnits(alloc_alignment));
106 const max_align_bytes = max_align.toByteUnits();
107 const ptr: [*]align(alignment_bytes) u8 = @alignCast(
108 vtable.alloc(no_context, n + max_align_bytes, max_align, no_ra) orelse return null,
109 );
110 const base: [*]align(alignment_bytes) u8 = @alignCast(ptr + max_align_bytes);
111 return Header.set(base, max_align, size);
112}
113
114fn calloc(elems: usize, len: usize) callconv(.c) ?[*]align(alignment_bytes) u8 {
115 const n = std.math.mul(usize, elems, len) catch return nomem();
116 const base = malloc(n) orelse return null;
117 @memset(base[0..n], 0);
118 return base;
119}
120
121fn realloc(opt_old_base: ?[*]align(alignment_bytes) u8, n: usize) callconv(.c) ?[*]align(alignment_bytes) u8 {
122 if (n == 0) {
123 free(opt_old_base);
124 return null;
125 }
126 const old_base = opt_old_base orelse return malloc(n);
127 const new_size = std.math.cast(Header.Size, n) orelse return nomem();
128 const old_header: Header = .get(old_base);
129 const old_size = old_header.size;
130 const old_alignment = old_header.alignment;
131 const old_alignment_bytes = old_alignment.toByteUnits();
132 const old_ptr = old_base - old_alignment_bytes;
133 const old_slice = old_ptr[0 .. old_size + old_alignment_bytes];
134 const new_base: [*]align(alignment_bytes) u8 = if (vtable.remap(
135 no_context,
136 old_slice,
137 old_alignment,
138 n + old_alignment_bytes,
139 no_ra,
140 )) |new_ptr| @alignCast(new_ptr + old_alignment_bytes) else b: {
141 const new_ptr: [*]align(alignment_bytes) u8 = @alignCast(
142 vtable.alloc(no_context, n + old_alignment_bytes, old_alignment, no_ra) orelse
143 return nomem(),
144 );
145 const new_base: [*]align(alignment_bytes) u8 = @alignCast(new_ptr + old_alignment_bytes);
146 const copy_len = @min(new_size, old_size);
147 @memcpy(new_base[0..copy_len], old_base[0..copy_len]);
148 vtable.free(no_context, old_slice, old_alignment, no_ra);
149 break :b new_base;
150 };
151 return Header.set(new_base, old_alignment, new_size);
152}
153
154fn reallocarray(opt_base: ?[*]align(alignment_bytes) u8, elems: usize, len: usize) callconv(.c) ?[*]align(alignment_bytes) u8 {
155 const n = std.math.mul(usize, elems, len) catch return nomem();
156 return realloc(opt_base, n);
157}
158
159fn free(opt_old_base: ?[*]align(alignment_bytes) u8) callconv(.c) void {
160 const old_base = opt_old_base orelse return;
161 const old_header: Header = .get(old_base);
162 const old_size = old_header.size;
163 const old_alignment = old_header.alignment;
164 const old_alignment_bytes = old_alignment.toByteUnits();
165 const old_ptr = old_base - old_alignment_bytes;
166 const old_slice = old_ptr[0 .. old_size + old_alignment_bytes];
167 vtable.free(no_context, old_slice, old_alignment, no_ra);
168}
169
170fn malloc_usable_size(opt_old_base: ?[*]align(alignment_bytes) u8) callconv(.c) usize {
171 const old_base = opt_old_base orelse return 0;
172 const old_header: Header = .get(old_base);
173 const old_size = old_header.size;
174 return old_size;
175}
176
177fn valloc(n: usize) callconv(.c) ?[*]align(alignment_bytes) u8 {
178 return aligned_alloc(std.heap.pageSize(), n);
179}
180
181fn memalign(alloc_alignment: usize, n: usize) callconv(.c) ?[*]align(alignment_bytes) u8 {
182 return aligned_alloc(alloc_alignment, n);
183}
184
185fn posix_memalign(result: *?[*]align(alignment_bytes) u8, alloc_alignment: usize, n: usize) callconv(.c) c_int {
186 if (alloc_alignment < @sizeOf(*anyopaque)) return @backingInt(std.c.E.INVAL);
187 result.* = aligned_alloc_inner(alloc_alignment, n) orelse return @backingInt(std.c.E.NOMEM);
188 return 0;
189}
190
191/// Libc memory allocation functions must set errno in addition to returning
192/// `null`.
193fn nomem() ?[*]align(alignment_bytes) u8 {
194 @branchHint(.cold);
195 std.c._errno().* = @backingInt(std.c.E.NOMEM);
196 return null;
197}