lib/bumpalo/src/chunk.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const Allocator = std.mem.Allocator;
4 const Alignment = std.mem.Alignment;
5 const assert = std.debug.assert;
6
7 pub const Chunk = struct {
8 previous: ?*Chunk,
9 data_offset: usize,
10 capacity: usize,
11 cursor_offset: usize,
12 total_capacity: usize,
13 allocation_len: usize,
14 allocation_alignment: Alignment,
15
16 pub fn base(chunk: *Chunk) [*]u8 {
17 return @ptrCast(chunk);
18 }
19
20 pub fn dataStart(chunk: *Chunk) [*]u8 {
21 return chunk.base() + chunk.data_offset;
22 }
23
24 pub fn dataEnd(chunk: *Chunk) [*]u8 {
25 return chunk.dataStart() + chunk.capacity;
26 }
27
28 pub fn cursor(chunk: *Chunk) [*]u8 {
29 return chunk.base() + chunk.cursor_offset;
30 }
31
32 pub fn setCursor(chunk: *Chunk, ptr: [*]u8) void {
33 assert(@intFromPtr(ptr) >= @intFromPtr(chunk.dataStart()));
34 assert(@intFromPtr(ptr) <= @intFromPtr(chunk.dataEnd()));
35 chunk.cursor_offset = @intFromPtr(ptr) - @intFromPtr(chunk.base());
36 }
37
38 pub fn remaining(chunk: *Chunk) usize {
39 assert(chunk.cursor_offset >= chunk.data_offset);
40 assert(chunk.cursor_offset <= chunk.data_offset + chunk.capacity);
41 return chunk.cursor_offset - chunk.data_offset;
42 }
43
44 pub fn usedSlice(chunk: *Chunk) []u8 {
45 return chunk.base()[chunk.cursor_offset .. chunk.data_offset + chunk.capacity];
46 }
47
48 pub fn backingSlice(chunk: *Chunk) []u8 {
49 return chunk.base()[0..chunk.allocation_len];
50 }
51 };
52
53 pub const Iterator = struct {
54 next_chunk: ?*Chunk,
55
56 pub fn next(iterator: *Iterator) ?[]u8 {
57 const chunk = iterator.next_chunk orelse return null;
58 iterator.next_chunk = chunk.previous;
59 return chunk.usedSlice();
60 }
61 };
62
63 pub const CreateOptions = struct {
64 requested_capacity: usize,
65 requested_len: usize,
66 requested_alignment: Alignment,
67 previous: ?*Chunk,
68 max_capacity: ?usize = null,
69 min_alignment: usize,
70 chunk_header_alignment: usize,
71 overhead: usize,
72 typical_page_size: usize,
73 backing_data_capacity_remaining: ?usize = null,
74 };
75
76 pub const BufferOptions = struct {
77 previous: ?*Chunk,
78 min_alignment: usize,
79 chunk_header_alignment: usize,
80 };
81
82 pub fn create(backing_allocator: Allocator, options: CreateOptions) Allocator.Error!*Chunk {
83 const requested_align = options.requested_alignment.toByteUnits();
84 var alignment_bytes: usize = @max(options.chunk_header_alignment, options.min_alignment);
85 alignment_bytes = @max(alignment_bytes, requested_align);
86
87 var capacity = options.requested_capacity;
88 const rounded_request = alignForwardChecked(options.requested_len, alignment_bytes) orelse
89 return error.OutOfMemory;
90 capacity = @max(capacity, rounded_request);
91 var needs_normalize = true;
92 if (options.max_capacity == null) {
93 if (options.backing_data_capacity_remaining) |remaining| {
94 if (capacity == remaining and remaining < options.typical_page_size) {
95 capacity = std.mem.alignBackward(usize, remaining, alignment_bytes);
96 if (capacity < rounded_request) return error.OutOfMemory;
97 needs_normalize = false;
98 }
99 }
100 }
101 if (needs_normalize) {
102 capacity = normalizeCapacity(capacity, alignment_bytes, options.overhead, options.typical_page_size) orelse
103 return error.OutOfMemory;
104 }
105
106 if (options.max_capacity) |limit| {
107 if (capacity > limit) {
108 capacity = std.mem.alignBackward(usize, limit, alignment_bytes);
109 if (capacity == 0 and rounded_request == 0) return error.OutOfMemory;
110 if (capacity < rounded_request) return error.OutOfMemory;
111 }
112 }
113
114 if (options.backing_data_capacity_remaining) |remaining| {
115 if (capacity > remaining) {
116 capacity = std.mem.alignBackward(usize, remaining, alignment_bytes);
117 if (capacity < rounded_request) return error.OutOfMemory;
118 }
119 }
120 if (capacity == 0) return error.OutOfMemory;
121
122 const data_offset = alignForwardChecked(@sizeOf(Chunk), alignment_bytes) orelse
123 return error.OutOfMemory;
124 const allocation_len = std.math.add(usize, data_offset, capacity) catch
125 return error.OutOfMemory;
126 const alignment_enum = Alignment.fromByteUnits(alignment_bytes);
127 const memory = backing_allocator.rawAlloc(allocation_len, alignment_enum, @returnAddress()) orelse
128 return error.OutOfMemory;
129 assert(capacity >= rounded_request);
130 assert(std.mem.isAligned(capacity, alignment_bytes));
131 assert(std.mem.isAligned(@intFromPtr(memory), alignment_bytes));
132 const new_chunk: *Chunk = @ptrCast(@alignCast(memory));
133 const data_end = @intFromPtr(memory) + data_offset + capacity;
134 new_chunk.* = .{
135 .previous = options.previous,
136 .data_offset = data_offset,
137 .capacity = capacity,
138 .cursor_offset = data_end - @intFromPtr(memory),
139 .total_capacity = (if (options.previous) |p| p.total_capacity else 0) + capacity,
140 .allocation_len = allocation_len,
141 .allocation_alignment = alignment_enum,
142 };
143 return new_chunk;
144 }
145
146 pub fn destroyList(backing_allocator: Allocator, first: ?*Chunk) void {
147 var chunk = first;
148 while (chunk) |current_chunk| {
149 const next = current_chunk.previous;
150 destroy(backing_allocator, current_chunk);
151 chunk = next;
152 }
153 }
154
155 pub fn destroyUntil(backing_allocator: Allocator, first: ?*Chunk, stop: *Chunk) void {
156 var chunk = first;
157 while (chunk) |current_chunk| {
158 if (current_chunk == stop) return;
159 const next = current_chunk.previous;
160 destroy(backing_allocator, current_chunk);
161 chunk = next;
162 }
163 unreachable;
164 }
165
166 inline fn destroy(backing_allocator: Allocator, chunk: *Chunk) void {
167 if (chunk.allocation_len != 0) {
168 backing_allocator.rawFree(
169 chunk.backingSlice(),
170 chunk.allocation_alignment,
171 @returnAddress(),
172 );
173 }
174 }
175
176 pub inline fn allocFast(current: *Chunk, len: usize, alignment: Alignment, min_alignment: usize) ?[*]u8 {
177 const requested_align = alignment.toByteUnits();
178 const effective_align = @max(requested_align, min_alignment);
179 const cursor_offset = current.cursor_offset;
180 const data_offset = current.data_offset;
181 if (cursor_offset < data_offset) {
182 @branchHint(.unlikely);
183 return null;
184 }
185
186 const available = cursor_offset - data_offset;
187 const base = current.base();
188 if (effective_align == 1) {
189 if (len > available) {
190 @branchHint(.unlikely);
191 return null;
192 }
193 const new_cursor_offset = cursor_offset - len;
194 assert(new_cursor_offset >= data_offset);
195 current.cursor_offset = new_cursor_offset;
196 return base + new_cursor_offset;
197 }
198
199 if (len > available) {
200 @branchHint(.unlikely);
201 return null;
202 }
203 const base_address = @intFromPtr(base);
204 const unaligned_offset = cursor_offset - len;
205 const aligned_address = Alignment.fromByteUnits(effective_align).backward(
206 base_address + unaligned_offset,
207 );
208 const data_address = base_address + data_offset;
209 if (aligned_address < data_address) {
210 @branchHint(.unlikely);
211 return null;
212 }
213 const new_cursor_offset = aligned_address - base_address;
214 assert(new_cursor_offset >= data_offset);
215 assert(std.mem.isAligned(@intFromPtr(base) + new_cursor_offset, effective_align));
216 current.cursor_offset = new_cursor_offset;
217 return base + new_cursor_offset;
218 }
219
220 pub fn normalizeCapacity(
221 capacity: usize,
222 alignment_bytes: usize,
223 overhead: usize,
224 typical_page_size: usize,
225 ) ?usize {
226 var normalized = capacity;
227 if (normalized < typical_page_size) {
228 const with_overhead = std.math.add(usize, normalized, overhead) catch return null;
229 normalized = std.math.ceilPowerOfTwo(usize, with_overhead) catch return null;
230 normalized -= overhead;
231 } else {
232 const with_overhead = std.math.add(usize, normalized, overhead) catch return null;
233 normalized = alignForwardChecked(with_overhead, typical_page_size) orelse return null;
234 normalized -= overhead;
235 }
236 const result = alignForwardChecked(normalized, alignment_bytes) orelse return null;
237 assert(result >= capacity);
238 return result;
239 }
240
241 pub fn alignForwardChecked(value: usize, alignment: usize) ?usize {
242 assert(std.math.isPowerOfTwo(alignment));
243 const mask = alignment - 1;
244 if (value > std.math.maxInt(usize) - mask) return null;
245 return (value + mask) & ~mask;
246 }
247
248 pub fn createInBuffer(buffer: []u8, options: BufferOptions) ?*Chunk {
249 if (buffer.len == 0) {
250 @branchHint(.unlikely);
251 return null;
252 }
253 const buffer_addr = @intFromPtr(buffer.ptr);
254 const chunk_addr = alignForwardChecked(buffer_addr, options.chunk_header_alignment) orelse return null;
255 const chunk_padding = chunk_addr - buffer_addr;
256 if (chunk_padding >= buffer.len) {
257 @branchHint(.unlikely);
258 return null;
259 }
260
261 const available = buffer.len - chunk_padding;
262 const alignment_bytes = @max(options.chunk_header_alignment, options.min_alignment);
263 const data_offset = alignForwardChecked(@sizeOf(Chunk), alignment_bytes) orelse return null;
264 if (available <= data_offset) {
265 @branchHint(.unlikely);
266 return null;
267 }
268
269 const capacity = std.mem.alignBackward(usize, available - data_offset, alignment_bytes);
270 if (capacity == 0) {
271 @branchHint(.unlikely);
272 return null;
273 }
274
275 assert(chunk_addr + data_offset + capacity <= buffer_addr + buffer.len);
276 const new_chunk: *Chunk = @ptrFromInt(chunk_addr);
277 new_chunk.* = .{
278 .previous = options.previous,
279 .data_offset = data_offset,
280 .capacity = capacity,
281 .cursor_offset = data_offset + capacity,
282 .total_capacity = (if (options.previous) |p| p.total_capacity else 0) + capacity,
283 .allocation_len = 0,
284 .allocation_alignment = Alignment.fromByteUnits(alignment_bytes),
285 };
286 return new_chunk;
287 }
288
289 pub fn allocationFootprint(current: *Chunk) usize {
290 if (current.allocation_len != 0) return current.allocation_len;
291 return current.data_offset + current.capacity;
292 }