lib/bumpalo/src/bump.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const observe = @import("alloc_observe");
3 const allocator_vtable = @import("vtable.zig");
4 const chunk_mod = @import("chunk.zig");
5
6 const Allocator = std.mem.Allocator;
7 const Alignment = std.mem.Alignment;
8 const assert = std.debug.assert;
9 const Chunk = chunk_mod.Chunk;
10
11 const CallerRootState = union(enum) {
12 none,
13 linked: *Chunk,
14 detached: *Chunk,
15 };
16
17 const ResetPolicy = union(enum) {
18 free_all,
19 retain_current,
20 retain_capacity,
21 retain_with_limit: usize,
22 };
23
24 pub const default_min_alignment: usize = 1;
25 pub const chunk_alignment: usize = 16;
26 pub const typical_page_size: usize = 0x1000;
27 pub const first_allocation_goal: usize = 1 << 9;
28 pub const malloc_overhead: usize = 16;
29
30 pub const Bump = BumpAllocator(default_min_alignment);
31
32 pub fn BumpAllocator(comptime min_alignment: usize) type {
33 comptime {
34 if (!std.math.isPowerOfTwo(min_alignment)) {
35 @compileError("min_alignment must be a power of two");
36 }
37 if (min_alignment > chunk_alignment) {
38 @compileError("min_alignment may not be larger than chunk_alignment");
39 }
40 }
41
42 return struct {
43 const chunk_header_alignment = @max(chunk_alignment, @alignOf(Chunk));
44 const minimum_alignment = min_alignment;
45 const metadata_size = std.mem.alignForward(usize, @sizeOf(Chunk), chunk_alignment);
46 const overhead = std.mem.alignForward(usize, malloc_overhead + metadata_size, chunk_alignment);
47 pub const default_chunk_capacity = first_allocation_goal - overhead;
48
49 backing_allocator: Allocator,
50 current: ?*Chunk = null,
51 backing_data_capacity_limit: ?usize = null,
52 chunk_growth_goal_bytes: ?usize = null,
53 caller_root: CallerRootState = .none,
54 observation_id: if (observe.enabled) u64 else void,
55 observation_generation: if (observe.enabled) u64 else void =
56 if (observe.enabled) 0 else {},
57
58 const Self = @This();
59 pub const ChunkIterator: type = chunk_mod.Iterator;
60 pub const ResetMode: type = ResetPolicy;
61
62 pub fn init(backing_allocator: Allocator) Self {
63 return .{
64 .backing_allocator = backing_allocator,
65 .observation_id = if (comptime observe.enabled)
66 observe.producerId()
67 else {},
68 };
69 }
70
71 pub inline fn observationId(arena: *const Self) u64 {
72 if (comptime !observe.enabled) return 0;
73 return arena.observation_id;
74 }
75
76 pub inline fn observationIdentity(
77 arena: *const Self,
78 ) observe.Identity {
79 if (comptime !observe.enabled) {
80 return .{
81 .producer_id = 0,
82 .producer = .bump,
83 .generation = 0,
84 .owner_cookie = 0,
85 };
86 }
87 return observe.Identity.movable(
88 arena.observation_id,
89 .bump,
90 arena.observation_generation,
91 );
92 }
93
94 pub fn initCapacity(backing_allocator: Allocator, capacity: usize) Allocator.Error!Self {
95 var arena = Self.init(backing_allocator);
96 if (capacity != 0) {
97 arena.current = try arena.newChunk(capacity, capacity, .@"1", null, null);
98 assert(arena.queryCapacity() >= capacity);
99 }
100 return arena;
101 }
102
103 pub fn deinit(arena: *Self) void {
104 var span = observe.beginLifecycle(
105 arena.observationIdentity(),
106 .end,
107 .deinit,
108 @returnAddress(),
109 );
110 arena.assertCallerRootInvariant();
111 chunk_mod.destroyList(arena.backing_allocator, arena.current);
112 arena.current = null;
113 arena.caller_root = .none;
114 span.finish(.{ .succeeded = true });
115 }
116
117 pub fn allocator(arena: *Self) Allocator {
118 const Table = allocator_vtable.VTable(Self);
119 return .{
120 .ptr = arena,
121 .vtable = &Table.vtable,
122 };
123 }
124
125 pub fn minAlign(_: *const Self) usize {
126 return min_alignment;
127 }
128
129 pub fn backingDataCapacityLimit(arena: *const Self) ?usize {
130 return arena.backing_data_capacity_limit;
131 }
132
133 pub fn setBackingDataCapacityLimit(arena: *Self, limit: ?usize) void {
134 arena.backing_data_capacity_limit = limit;
135 }
136
137 pub fn chunkGrowthGoal(arena: *const Self) ?usize {
138 return arena.chunk_growth_goal_bytes;
139 }
140
141 pub fn setChunkGrowthGoal(arena: *Self, goal: ?usize) void {
142 if (goal) |bytes| assert(bytes >= default_chunk_capacity);
143 arena.chunk_growth_goal_bytes = goal;
144 }
145
146 pub fn reset(arena: *Self, mode: ResetMode) bool {
147 var span = observe.beginLifecycle(
148 arena.observationIdentity(),
149 .invalidate,
150 .reset,
151 @returnAddress(),
152 );
153 const succeeded = switch (mode) {
154 .free_all => blk: {
155 arena.freeAllChunks();
156 break :blk true;
157 },
158 .retain_current => blk: {
159 arena.retainCurrentChunk();
160 break :blk true;
161 },
162 .retain_capacity => arena.retainSingleChunk(
163 arena.queryCapacity(),
164 null,
165 ),
166 .retain_with_limit => |limit| arena.retainSingleChunk(
167 @min(arena.queryCapacity(), limit),
168 limit,
169 ),
170 };
171 span.finish(.{ .succeeded = succeeded });
172 arena.advanceObservationGeneration();
173 return succeeded;
174 }
175
176 pub fn queryCapacity(arena: *const Self) usize {
177 const current = arena.current orelse return 0;
178 return current.total_capacity;
179 }
180
181 pub fn queryCallerDataCapacity(arena: *const Self) usize {
182 return switch (arena.caller_root) {
183 .linked => |root| root.capacity,
184 .none, .detached => 0,
185 };
186 }
187
188 pub fn queryBackingDataCapacity(arena: *const Self) usize {
189 const capacity = arena.queryCapacity();
190 const caller_capacity = arena.queryCallerDataCapacity();
191 assert(caller_capacity <= capacity);
192 return capacity - caller_capacity;
193 }
194
195 pub fn queryUsedCapacity(arena: *const Self) usize {
196 var used: usize = 0;
197 var chunk = arena.current;
198 while (chunk) |c| : (chunk = c.previous) {
199 used += c.usedSlice().len;
200 }
201 return used;
202 }
203
204 pub fn queryCurrentChunkAvailable(arena: *const Self) usize {
205 const current = arena.current orelse return 0;
206 return current.remaining();
207 }
208
209 pub fn queryCapacityIncludingMetadata(arena: *const Self) usize {
210 var bytes: usize = 0;
211 var chunk = arena.current;
212 while (chunk) |c| : (chunk = c.previous) {
213 bytes += chunk_mod.allocationFootprint(c);
214 }
215 return bytes;
216 }
217
218 pub fn clearAndFree(arena: *Self) void {
219 var span = observe.beginLifecycle(
220 arena.observationIdentity(),
221 .invalidate,
222 .clear_and_free,
223 @returnAddress(),
224 );
225 arena.freeAllChunks();
226 span.finish(.{ .succeeded = true });
227 arena.advanceObservationGeneration();
228 }
229
230 pub fn clearRetainingCurrent(arena: *Self) void {
231 var span = observe.beginLifecycle(
232 arena.observationIdentity(),
233 .invalidate,
234 .clear_retaining_current,
235 @returnAddress(),
236 );
237 arena.retainCurrentChunk();
238 span.finish(.{ .succeeded = true });
239 arena.advanceObservationGeneration();
240 }
241
242 pub fn clearRetainingLargest(arena: *Self) void {
243 var span = observe.beginLifecycle(
244 arena.observationIdentity(),
245 .invalidate,
246 .clear_retaining_largest,
247 @returnAddress(),
248 );
249 arena.retainLargestChunk();
250 span.finish(.{ .succeeded = true });
251 arena.advanceObservationGeneration();
252 }
253
254 pub fn clearRetainingCapacity(arena: *Self) bool {
255 var span = observe.beginLifecycle(
256 arena.observationIdentity(),
257 .invalidate,
258 .clear_retaining_capacity,
259 @returnAddress(),
260 );
261 const succeeded = arena.retainSingleChunk(
262 arena.queryCapacity(),
263 null,
264 );
265 span.finish(.{ .succeeded = succeeded });
266 arena.advanceObservationGeneration();
267 return succeeded;
268 }
269
270 pub fn clearRetainingCapacityLimit(arena: *Self, limit: usize) bool {
271 var span = observe.beginLifecycle(
272 arena.observationIdentity(),
273 .invalidate,
274 .clear_retaining_capacity_limit,
275 @returnAddress(),
276 );
277 const succeeded = arena.retainSingleChunk(
278 @min(arena.queryCapacity(), limit),
279 limit,
280 );
281 span.finish(.{ .succeeded = succeeded });
282 arena.advanceObservationGeneration();
283 return succeeded;
284 }
285
286 fn advanceObservationGeneration(arena: *Self) void {
287 if (comptime !observe.enabled) return;
288 arena.observation_generation = std.math.add(
289 u64,
290 arena.observation_generation,
291 1,
292 ) catch @panic("allocator observation generation exhausted");
293 }
294
295 fn freeAllChunks(arena: *Self) void {
296 arena.assertCallerRootInvariant();
297 chunk_mod.destroyList(arena.backing_allocator, arena.current);
298 arena.current = null;
299 arena.restoreCallerRoot();
300 arena.assertCallerRootInvariant();
301 }
302
303 fn retainCurrentChunk(arena: *Self) void {
304 arena.assertCallerRootInvariant();
305 const current = arena.current orelse return;
306 chunk_mod.destroyList(arena.backing_allocator, current.previous);
307 current.previous = null;
308 current.setCursor(current.dataEnd());
309 current.total_capacity = current.capacity;
310 switch (arena.caller_root) {
311 .linked => |root| {
312 if (current != root) arena.caller_root = .{ .detached = root };
313 },
314 .none, .detached => {},
315 }
316 assert(current.remaining() == current.capacity);
317 assert(arena.queryCapacity() == arena.queryCurrentChunkAvailable());
318 arena.assertCallerRootInvariant();
319 }
320
321 fn retainLargestChunk(arena: *Self) void {
322 switch (arena.caller_root) {
323 .none => {},
324 .linked, .detached => {
325 arena.freeAllChunks();
326 return;
327 },
328 }
329 const current = arena.current orelse return;
330 var retained = current;
331 var candidate = current.previous;
332 while (candidate) |chunk| : (candidate = chunk.previous) {
333 if (chunk.capacity > retained.capacity) retained = chunk;
334 }
335 chunk_mod.destroyUntil(arena.backing_allocator, current, retained);
336 chunk_mod.destroyList(arena.backing_allocator, retained.previous);
337 retained.previous = null;
338 retained.setCursor(retained.dataEnd());
339 retained.total_capacity = retained.capacity;
340 arena.current = retained;
341 assert(retained.remaining() == retained.capacity);
342 assert(arena.queryCapacity() == arena.queryCurrentChunkAvailable());
343 }
344
345 fn retainSingleChunk(arena: *Self, requested_capacity: usize, max_capacity: ?usize) bool {
346 arena.assertCallerRootInvariant();
347 const bounded_capacity = if (max_capacity) |limit|
348 @min(requested_capacity, limit)
349 else
350 requested_capacity;
351 if (bounded_capacity == 0) {
352 arena.clearLiveAndDetachCallerRoot();
353 arena.assertCallerRootInvariant();
354 return true;
355 }
356 if (max_capacity) |limit| {
357 const aligned_limit = std.mem.alignBackward(
358 usize,
359 limit,
360 @max(chunk_header_alignment, min_alignment),
361 );
362 if (aligned_limit == 0) {
363 arena.clearLiveAndDetachCallerRoot();
364 arena.assertCallerRootInvariant();
365 return true;
366 }
367 }
368
369 assert(bounded_capacity > 0);
370 if (arena.current) |current| {
371 if (current.previous == null and current.capacity >= bounded_capacity) {
372 if (max_capacity == null or current.capacity <= max_capacity.?) {
373 current.setCursor(current.dataEnd());
374 current.total_capacity = current.capacity;
375 assert(current.remaining() == current.capacity);
376 arena.assertCallerRootInvariant();
377 return true;
378 }
379 }
380 }
381
382 arena.clearLiveAndDetachCallerRoot();
383 const backing_capacity_remaining =
384 arena.backingDataCapacityRemaining();
385 if (backing_capacity_remaining) |remaining| {
386 const aligned_remaining = std.mem.alignBackward(
387 usize,
388 remaining,
389 @max(chunk_header_alignment, min_alignment),
390 );
391 if (max_capacity != null and aligned_remaining == 0) {
392 arena.assertCallerRootInvariant();
393 return true;
394 }
395 }
396 arena.current = arena.newChunkBounded(
397 bounded_capacity,
398 if (max_capacity == null) bounded_capacity else 0,
399 .@"1",
400 null,
401 max_capacity,
402 backing_capacity_remaining,
403 ) catch {
404 arena.restoreCallerRoot();
405 arena.assertCallerRootInvariant();
406 return false;
407 };
408 arena.assertCallerRootInvariant();
409 return true;
410 }
411
412 fn clearLiveAndDetachCallerRoot(arena: *Self) void {
413 chunk_mod.destroyList(arena.backing_allocator, arena.current);
414 arena.current = null;
415 switch (arena.caller_root) {
416 .linked => |root| arena.caller_root = .{ .detached = root },
417 .none, .detached => {},
418 }
419 }
420
421 fn restoreCallerRoot(arena: *Self) void {
422 switch (arena.caller_root) {
423 .none => {},
424 .linked, .detached => |root| {
425 root.previous = null;
426 root.setCursor(root.dataEnd());
427 root.total_capacity = root.capacity;
428 arena.current = root;
429 arena.caller_root = .{ .linked = root };
430 },
431 }
432 }
433
434 fn assertCallerRootInvariant(arena: *const Self) void {
435 switch (arena.caller_root) {
436 .none => {},
437 .linked => |root| {
438 assert(root.previous == null);
439 assert(arena.chunkReachable(root));
440 },
441 .detached => |root| {
442 assert(root.previous == null);
443 assert(!arena.chunkReachable(root));
444 },
445 }
446 }
447
448 fn chunkReachable(arena: *const Self, target: *Chunk) bool {
449 var chunk = arena.current;
450 while (chunk) |current| : (chunk = current.previous) {
451 if (current == target) return true;
452 }
453 return false;
454 }
455
456 pub fn iterAllocatedChunks(arena: *Self) ChunkIterator {
457 return .{ .next_chunk = arena.current };
458 }
459
460 pub inline fn allocValue(arena: *Self, value: anytype) Allocator.Error!*@TypeOf(value) {
461 const T = @TypeOf(value);
462 const ptr = try arena.create(T);
463 ptr.* = value;
464 return ptr;
465 }
466
467 pub inline fn create(arena: *Self, comptime T: type) Allocator.Error!*T {
468 if (@sizeOf(T) == 0) {
469 const address = comptime Alignment.of(T).backward(std.math.maxInt(usize));
470 return @ptrFromInt(address);
471 }
472 const raw = try arena.allocBytes(@sizeOf(T), .of(T));
473 return @ptrCast(@alignCast(raw));
474 }
475
476 pub inline fn alloc(arena: *Self, comptime T: type, len: usize) Allocator.Error![]T {
477 if (@sizeOf(T) == 0) {
478 const address = comptime Alignment.of(T).backward(std.math.maxInt(usize));
479 const ptr: [*]T = @ptrFromInt(address);
480 return ptr[0..len];
481 }
482 const byte_len = if (comptime @sizeOf(T) == 1)
483 len
484 else
485 std.math.mul(usize, @sizeOf(T), len) catch return error.OutOfMemory;
486 const raw = try arena.allocBytes(byte_len, .of(T));
487 const ptr: [*]T = @ptrCast(@alignCast(raw));
488 return ptr[0..len];
489 }
490
491 pub inline fn dupe(arena: *Self, comptime T: type, source: []const T) Allocator.Error![]T {
492 const dest = try arena.alloc(T, source.len);
493 @memcpy(dest, source);
494 return dest;
495 }
496
497 pub inline fn dupeSentinel(
498 arena: *Self,
499 comptime T: type,
500 source: []const T,
501 comptime sentinel: T,
502 ) Allocator.Error![:sentinel]T {
503 const dest = try arena.alloc(T, source.len + 1);
504 @memcpy(dest[0..source.len], source);
505 dest[source.len] = sentinel;
506 return dest[0..source.len :sentinel];
507 }
508
509 pub inline fn dupeZ(arena: *Self, comptime T: type, source: []const T) Allocator.Error![:0]T {
510 return arena.dupeSentinel(T, source, 0);
511 }
512
513 pub inline fn allocFill(arena: *Self, comptime T: type, len: usize, value: T) Allocator.Error![]T {
514 const dest = try arena.alloc(T, len);
515 @memset(dest, value);
516 return dest;
517 }
518
519 pub inline fn allocBytes(arena: *Self, len: usize, alignment: Alignment) Allocator.Error![*]u8 {
520 return arena.tryAllocBytes(len, alignment) orelse error.OutOfMemory;
521 }
522
523 inline fn tryAllocBytes(arena: *Self, len: usize, alignment: Alignment) ?[*]u8 {
524 if (len == 0) {
525 const effective_align = @max(alignment.toByteUnits(), min_alignment);
526 const address = Alignment.fromByteUnits(effective_align).backward(std.math.maxInt(usize));
527 return @ptrFromInt(address);
528 }
529
530 if (arena.tryAllocBytesFast(len, alignment)) |ptr| return ptr;
531 return arena.allocBytesSlow(len, alignment);
532 }
533
534 inline fn tryAllocBytesFast(arena: *Self, len: usize, alignment: Alignment) ?[*]u8 {
535 const current = arena.current orelse {
536 @branchHint(.unlikely);
537 return null;
538 };
539 return allocFast(current, len, alignment, min_alignment);
540 }
541
542 inline fn allocFast(current: *Chunk, len: usize, alignment: Alignment, comptime min_align: usize) ?[*]u8 {
543 return chunk_mod.allocFast(current, len, alignment, min_align);
544 }
545
546 fn allocBytesSlow(arena: *Self, len: usize, alignment: Alignment) ?[*]u8 {
547 assert(len != 0);
548 const remaining_limit = arena.backingDataCapacityRemaining();
549 const previous = arena.current;
550 const min_new_capacity = @max(len, default_chunk_capacity);
551 var base_capacity = min_new_capacity;
552 if (previous) |chunk| {
553 const effective_align = @max(alignment.toByteUnits(), min_alignment);
554 if (std.mem.isAligned(@intFromPtr(chunk.cursor()), effective_align)) {
555 base_capacity = @max(chunk.capacity *| 2, min_new_capacity);
556 }
557 }
558 if (arena.chunk_growth_goal_bytes) |goal| {
559 base_capacity = @min(base_capacity, @max(goal, min_new_capacity));
560 }
561
562 if (remaining_limit) |remaining| {
563 if (remaining < len) return null;
564 if (base_capacity > remaining) base_capacity = remaining;
565 }
566
567 if (base_capacity < len) return null;
568 const new_chunk = arena.newChunk(
569 base_capacity,
570 len,
571 alignment,
572 previous,
573 remaining_limit,
574 ) catch return null;
575 arena.current = new_chunk;
576 const ptr = allocFast(new_chunk, len, alignment, min_alignment).?;
577 assert(std.mem.isAligned(@intFromPtr(ptr), @max(alignment.toByteUnits(), min_alignment)));
578 return ptr;
579 }
580
581 fn backingDataCapacityRemaining(arena: *const Self) ?usize {
582 const limit = arena.backing_data_capacity_limit orelse return null;
583 const allocated = arena.queryBackingDataCapacity();
584 if (allocated >= limit) return 0;
585 return limit - allocated;
586 }
587
588 fn newChunk(
589 arena: *Self,
590 requested_capacity: usize,
591 requested_len: usize,
592 requested_alignment: Alignment,
593 previous: ?*Chunk,
594 backing_data_capacity_remaining: ?usize,
595 ) Allocator.Error!*Chunk {
596 return arena.newChunkBounded(
597 requested_capacity,
598 requested_len,
599 requested_alignment,
600 previous,
601 null,
602 backing_data_capacity_remaining,
603 );
604 }
605
606 fn newChunkBounded(
607 arena: *Self,
608 requested_capacity: usize,
609 requested_len: usize,
610 requested_alignment: Alignment,
611 previous: ?*Chunk,
612 max_capacity: ?usize,
613 backing_data_capacity_remaining: ?usize,
614 ) Allocator.Error!*Chunk {
615 assert(requested_len <= requested_capacity);
616 return chunk_mod.create(arena.backing_allocator, .{
617 .requested_capacity = requested_capacity,
618 .requested_len = requested_len,
619 .requested_alignment = requested_alignment,
620 .previous = previous,
621 .max_capacity = max_capacity,
622 .min_alignment = min_alignment,
623 .chunk_header_alignment = chunk_header_alignment,
624 .overhead = overhead,
625 .typical_page_size = typical_page_size,
626 .backing_data_capacity_remaining = backing_data_capacity_remaining,
627 });
628 }
629
630 pub fn initBuffer(backing_allocator: Allocator, buffer: []u8) Allocator.Error!Self {
631 var arena = Self.init(backing_allocator);
632 if (buffer.len != 0) {
633 const initial = try Self.newChunkInBuffer(buffer, null);
634 arena.current = initial;
635 arena.caller_root = .{ .linked = initial };
636 arena.assertCallerRootInvariant();
637 }
638 return arena;
639 }
640
641 fn newChunkInBuffer(buffer: []u8, previous: ?*Chunk) Allocator.Error!*Chunk {
642 return chunk_mod.createInBuffer(buffer, .{
643 .previous = previous,
644 .min_alignment = min_alignment,
645 .chunk_header_alignment = chunk_header_alignment,
646 }) orelse error.OutOfMemory;
647 }
648 };
649 }
650
651 const ObservationRecorder = struct {
652 events: [32]observe.Event = undefined,
653 count: usize = 0,
654
655 fn sink(self: *ObservationRecorder) observe.Sink {
656 return .{ .context = self, .record = record };
657 }
658
659 fn record(context: *anyopaque, event: observe.Event) void {
660 const self: *ObservationRecorder = @ptrCast(@alignCast(context));
661 assert(self.count < self.events.len);
662 self.events[self.count] = event;
663 self.count += 1;
664 }
665 };
666
667 test "new bump query capacity is zero" {
668 var bump = Bump.init(std.testing.allocator);
669 defer bump.deinit();
670
671 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacity());
672 }
673
674 test "bump clear paths report one lifecycle generation each" {
675 if (!observe.enabled) return error.SkipZigTest;
676 var recorder: ObservationRecorder = .{};
677 var sink = recorder.sink();
678 var session = try observe.install(&sink);
679 defer session.deinit();
680
681 var bump = Bump.init(std.testing.allocator);
682 _ = try bump.allocator().alloc(u8, 16);
683 bump.clearAndFree();
684 bump.clearRetainingCurrent();
685 bump.clearRetainingLargest();
686 _ = bump.clearRetainingCapacity();
687 _ = bump.clearRetainingCapacityLimit(64);
688 try std.testing.expect(bump.reset(.retain_current));
689 bump.deinit();
690
691 const expected_reasons = [_]observe.LifecycleReason{
692 .clear_and_free,
693 .clear_retaining_current,
694 .clear_retaining_largest,
695 .clear_retaining_capacity,
696 .clear_retaining_capacity_limit,
697 .reset,
698 .deinit,
699 };
700 var lifecycle_index: usize = 0;
701 for (recorder.events[0..recorder.count]) |event| {
702 if (event.operation != .lifecycle) continue;
703 try std.testing.expectEqual(
704 expected_reasons[lifecycle_index],
705 event.lifecycle_reason,
706 );
707 try std.testing.expectEqual(
708 @as(u64, @intCast(lifecycle_index)),
709 event.generation,
710 );
711 const expected_disposition: observe.LifecycleDisposition =
712 if (event.lifecycle_reason == .deinit) .end else .invalidate;
713 try std.testing.expectEqual(
714 expected_disposition,
715 event.lifecycle_disposition,
716 );
717 lifecycle_index += 1;
718 }
719 try std.testing.expectEqual(expected_reasons.len, lifecycle_index);
720 }
721
722 test "bump observation identity survives value movement" {
723 if (!observe.enabled) return error.SkipZigTest;
724 var recorder: ObservationRecorder = .{};
725 var sink = recorder.sink();
726 var session = try observe.install(&sink);
727 defer session.deinit();
728
729 var original = Bump.init(std.testing.allocator);
730 _ = try original.allocator().alloc(u8, 16);
731 var moved = original;
732 original = undefined;
733 moved.deinit();
734
735 try std.testing.expectEqual(@as(usize, 2), recorder.count);
736 try std.testing.expectEqual(
737 observe.Operation.alloc,
738 recorder.events[0].operation,
739 );
740 try std.testing.expectEqual(
741 observe.Operation.lifecycle,
742 recorder.events[1].operation,
743 );
744 try std.testing.expectEqual(
745 recorder.events[0].owner_cookie,
746 recorder.events[1].owner_cookie,
747 );
748 try std.testing.expect(recorder.events[0].owner_cookie != 0);
749 }
750
751 test "chunk growth goal bounds geometric reservation without bounding requests" {
752 const goal = 64 * 1024;
753 const allocation_size = 31 * 1024;
754 const allocation_count = 64;
755 var bump = Bump.init(std.testing.allocator);
756 defer bump.deinit();
757 bump.setChunkGrowthGoal(goal);
758
759 for (0..allocation_count) |_| _ = try bump.allocator().alloc(u8, allocation_size);
760
761 try std.testing.expectEqual(@as(?usize, goal), bump.chunkGrowthGoal());
762 try std.testing.expect(bump.reset(.retain_current));
763 try std.testing.expect(bump.queryCapacity() <= goal + typical_page_size);
764 _ = try bump.allocator().alloc(u8, goal * 2);
765 }
766
767 test "clear retaining largest discards an exhausted tail chunk" {
768 var bump = Bump.init(std.testing.allocator);
769 defer bump.deinit();
770 _ = try bump.allocator().alloc(u8, 4096);
771 const largest_capacity = bump.queryCapacity();
772 _ = try bump.allocator().alloc(u8, bump.queryCurrentChunkAvailable());
773 bump.setBackingDataCapacityLimit(largest_capacity + 512);
774 _ = try bump.allocator().alloc(u8, 256);
775 try std.testing.expect(bump.queryCapacity() > largest_capacity);
776
777 bump.clearRetainingLargest();
778
779 try std.testing.expectEqual(largest_capacity, bump.queryCapacity());
780 try std.testing.expectEqual(largest_capacity, bump.queryCurrentChunkAvailable());
781 }
782
783 test "can allocate and mutate values" {
784 var bump = Bump.init(std.testing.allocator);
785 defer bump.deinit();
786
787 const value = try bump.allocValue(@as(u64, 42));
788 try std.testing.expectEqual(@as(u64, 42), value.*);
789 value.* += 1;
790 try std.testing.expectEqual(@as(u64, 43), value.*);
791 }
792
793 test "allocations do not overlap" {
794 var bump = try Bump.initCapacity(std.testing.allocator, 64);
795 defer bump.deinit();
796
797 const a = try bump.allocator().alloc(u8, 16);
798 const b = try bump.allocator().alloc(u8, 16);
799 const a_start = @intFromPtr(a.ptr);
800 const a_end = a_start + a.len;
801 const b_start = @intFromPtr(b.ptr);
802 const b_end = b_start + b.len;
803
804 try std.testing.expect(a_end <= b_start or b_end <= a_start);
805 }
806
807 test "allocator aligns requests" {
808 var bump = try Bump.initCapacity(std.testing.allocator, 513);
809 defer bump.deinit();
810 const allocator_instance = bump.allocator();
811
812 inline for (.{ 2, 4, 8, 16, 32, 64 }) |alignment| {
813 var index: usize = 0;
814 while (index < 1024) : (index += 1) {
815 const bytes = try allocator_instance.alignedAlloc(u8, .fromByteUnits(alignment), alignment);
816 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(bytes.ptr) % alignment);
817 }
818 }
819 }
820
821 test "mixed alignment consumes padding in the current chunk" {
822 var bump = try Bump.initCapacity(std.testing.allocator, 64);
823 defer bump.deinit();
824 const capacity = bump.queryCapacity();
825
826 _ = try bump.allocBytes(1, .@"1");
827 const aligned = try bump.allocBytes(8, .@"8");
828
829 try std.testing.expectEqual(capacity, bump.queryCapacity());
830 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(aligned) % 8);
831 try std.testing.expectEqual(@as(usize, 16), bump.queryUsedCapacity());
832 }
833
834 test "dupe stores independent data" {
835 var bump = Bump.init(std.testing.allocator);
836 defer bump.deinit();
837
838 const source = [_]u16{ 0xfeed, 0xface, 0x00a7, 0xcafe };
839 const dest = try bump.dupe(u16, &source);
840
841 try std.testing.expectEqualSlices(u16, &source, dest);
842 }
843
844 test "dupeZ appends a sentinel" {
845 var bump = Bump.init(std.testing.allocator);
846 defer bump.deinit();
847
848 const dest = try bump.dupeZ(u8, "hello");
849
850 try std.testing.expectEqualStrings("hello", dest);
851 try std.testing.expectEqual(@as(u8, 0), dest.ptr[dest.len]);
852 }
853
854 test "allocFill initializes every element" {
855 var bump = Bump.init(std.testing.allocator);
856 defer bump.deinit();
857
858 const dest = try bump.allocFill(u64, 5, 42);
859 try std.testing.expectEqualSlices(u64, &.{ 42, 42, 42, 42, 42 }, dest);
860 }
861
862 test "zero-length direct allocations do not create chunks" {
863 const StrongBump = BumpAllocator(16);
864 var bump = StrongBump.init(std.testing.allocator);
865 defer bump.deinit();
866
867 const bytes = try bump.allocBytes(0, .@"1");
868 const words = try bump.alloc(u64, 0);
869 const duped = try bump.dupe(u8, "");
870 const filled = try bump.allocFill(u16, 0, 42);
871
872 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(bytes) % 16);
873 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(words.ptr) % 16);
874 try std.testing.expectEqual(@as(usize, 0), duped.len);
875 try std.testing.expectEqual(@as(usize, 0), filled.len);
876 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacity());
877 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacityIncludingMetadata());
878 }
879
880 test "large buffers can be initialized in place" {
881 var bump = Bump.init(std.testing.allocator);
882 defer bump.deinit();
883
884 const bytes = try bump.alloc(u8, 1 << 20);
885 @memset(bytes, 0x5a);
886
887 try std.testing.expectEqual(@as(u8, 0x5a), bytes[0]);
888 try std.testing.expectEqual(@as(u8, 0x5a), bytes[bytes.len - 1]);
889 }
890
891 test "try with capacity too large returns out of memory" {
892 try std.testing.expectError(
893 error.OutOfMemory,
894 Bump.initCapacity(std.testing.allocator, std.math.maxInt(usize)),
895 );
896 }
897
898 test "with capacity keeps allocations in one chunk when it fits" {
899 var bump = try Bump.initCapacity(std.testing.allocator, 1024);
900 defer bump.deinit();
901
902 const initial_capacity = bump.queryCurrentChunkAvailable();
903 _ = try bump.allocator().alloc(u8, 512);
904
905 try std.testing.expect(initial_capacity >= 1024);
906 try std.testing.expect(bump.queryCurrentChunkAvailable() < initial_capacity);
907
908 var iter = bump.iterAllocatedChunks();
909 try std.testing.expect(iter.next() != null);
910 try std.testing.expect(iter.next() == null);
911 }
912
913 test "initial buffer serves allocations without backing allocator" {
914 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });
915 var buffer: [1024]u8 = undefined;
916 var bump = try Bump.initBuffer(failing.allocator(), &buffer);
917 defer bump.deinit();
918
919 const bytes = try bump.alloc(u8, 128);
920 const start = @intFromPtr(&buffer);
921 const end = start + buffer.len;
922 const ptr = @intFromPtr(bytes.ptr);
923
924 try std.testing.expect(ptr >= start);
925 try std.testing.expect(ptr + bytes.len <= end);
926 try std.testing.expect(bump.queryCapacity() > 0);
927 try std.testing.expect(bump.queryCapacityIncludingMetadata() >= bump.queryCapacity());
928 }
929
930 test "initial buffer falls back to backing allocator when full" {
931 var buffer: [256]u8 = undefined;
932 var bump = try Bump.initBuffer(std.testing.allocator, &buffer);
933 defer bump.deinit();
934
935 const first = try bump.alloc(u8, 32);
936 const second = try bump.alloc(u8, 4096);
937 const start = @intFromPtr(&buffer);
938 const end = start + buffer.len;
939
940 try std.testing.expect(@intFromPtr(first.ptr) >= start);
941 try std.testing.expect(@intFromPtr(first.ptr) + first.len <= end);
942 try std.testing.expect(@intFromPtr(second.ptr) < start or @intFromPtr(second.ptr) >= end);
943 try std.testing.expect(bump.queryCapacity() > buffer.len);
944 }
945
946 test "initial buffer survives free_all reset" {
947 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 1 });
948 var buffer: [1024]u8 = undefined;
949 var bump = try Bump.initBuffer(failing.allocator(), &buffer);
950 defer bump.deinit();
951
952 _ = try bump.alloc(u8, 128);
953 _ = try bump.alloc(u8, 4096);
954 try std.testing.expect(bump.queryCapacity() > buffer.len);
955
956 try std.testing.expect(bump.reset(.free_all));
957 try std.testing.expect(bump.queryCapacity() <= buffer.len);
958
959 const bytes = try bump.alloc(u8, 128);
960 const start = @intFromPtr(&buffer);
961 const end = start + buffer.len;
962 const ptr = @intFromPtr(bytes.ptr);
963
964 try std.testing.expect(ptr >= start);
965 try std.testing.expect(ptr + bytes.len <= end);
966 }
967
968 test "initial buffer free_all reset rewinds without backing allocation" {
969 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });
970 var buffer: [1024]u8 = undefined;
971 var bump = try Bump.initBuffer(failing.allocator(), &buffer);
972 defer bump.deinit();
973
974 _ = try bump.alloc(u8, 128);
975 try std.testing.expect(bump.reset(.free_all));
976 try std.testing.expect(bump.queryCapacity() <= buffer.len);
977
978 const bytes = try bump.alloc(u8, 128);
979 const start = @intFromPtr(&buffer);
980 const end = start + buffer.len;
981 const ptr = @intFromPtr(bytes.ptr);
982
983 try std.testing.expect(ptr >= start);
984 try std.testing.expect(ptr + bytes.len <= end);
985 }
986
987 test "reset keeps newest chunk and rewinds it" {
988 var bump = Bump.init(std.testing.allocator);
989 defer bump.deinit();
990
991 var index: usize = 0;
992 while (index < 10_000) : (index += 1) {
993 _ = try bump.allocator().create(u64);
994 }
995
996 var before_count: usize = 0;
997 var before_iter = bump.iterAllocatedChunks();
998 var last_chunk: ?[]u8 = null;
999 while (before_iter.next()) |chunk| {
1000 if (last_chunk == null) last_chunk = chunk;
1001 before_count += 1;
1002 }
1003 try std.testing.expect(before_count > 1);
1004
1005 const chunk = last_chunk.?;
1006 const expected_next = @intFromPtr(chunk.ptr) + chunk.len - @sizeOf(u64);
1007 try std.testing.expect(bump.reset(.retain_current));
1008 const next = try bump.allocator().create(u64);
1009
1010 try std.testing.expectEqual(expected_next, @intFromPtr(next));
1011 var after_iter = bump.iterAllocatedChunks();
1012 try std.testing.expect(after_iter.next() != null);
1013 try std.testing.expect(after_iter.next() == null);
1014 }
1015
1016 test "can iterate over allocated u64 values" {
1017 var bump = Bump.init(std.testing.allocator);
1018 defer bump.deinit();
1019
1020 const max = 4096;
1021 var index: u64 = 0;
1022 while (index < max) : (index += 1) {
1023 const value = try bump.allocValue(index);
1024 try std.testing.expectEqual(index, value.*);
1025 }
1026
1027 var seen = @as([max]bool, @splat(false));
1028 var iter = bump.iterAllocatedChunks();
1029 while (iter.next()) |chunk| {
1030 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(chunk.ptr) % @alignOf(u64));
1031 try std.testing.expectEqual(@as(usize, 0), chunk.len % @sizeOf(u64));
1032 const values = std.mem.bytesAsSlice(u64, chunk);
1033 for (values) |value| {
1034 try std.testing.expect(value < max);
1035 seen[@intCast(value)] = true;
1036 }
1037 }
1038
1039 for (seen) |was_seen| try std.testing.expect(was_seen);
1040 }
1041
1042 test "with capacity preserves reverse allocation order within one chunk" {
1043 inline for (.{ u8, u16, u32, u64 }) |T| {
1044 var bump = try Bump.initCapacity(std.testing.allocator, 256 * @sizeOf(T));
1045 defer bump.deinit();
1046
1047 var index: usize = 0;
1048 while (index < 128) : (index += 1) {
1049 _ = try bump.allocValue(@as(T, @intCast(index)));
1050 }
1051
1052 var iter = bump.iterAllocatedChunks();
1053 const chunk = iter.next() orelse return error.MissingChunk;
1054 try std.testing.expect(iter.next() == null);
1055 const values = std.mem.bytesAsSlice(T, chunk);
1056 try std.testing.expectEqual(@as(usize, 128), values.len);
1057 for (values, 0..) |value, value_index| {
1058 try std.testing.expectEqual(@as(T, @intCast(127 - value_index)), value);
1059 }
1060 }
1061 }
1062
1063 test "force new chunk accepts large odd-sized layouts" {
1064 var bump = Bump.init(std.testing.allocator);
1065 defer bump.deinit();
1066
1067 _ = try bump.allocBytes(1, .@"1");
1068 _ = try bump.allocBytes(100_001, .@"1");
1069 _ = try bump.allocBytes(100_003, .@"1");
1070 }
1071
1072 test "strong and page-sized alignments are honored" {
1073 var bump = Bump.init(std.testing.allocator);
1074 defer bump.deinit();
1075
1076 const cache_line = try bump.allocBytes(4096, .@"64");
1077 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(cache_line) % 64);
1078
1079 const page = try bump.allocBytes(1, .fromByteUnits(0x1000));
1080 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(page) % 0x1000);
1081 }
1082
1083 test "backing data capacity limit blocks new chunks but can be removed" {
1084 var bump = Bump.init(std.testing.allocator);
1085 defer bump.deinit();
1086
1087 bump.setBackingDataCapacityLimit(0);
1088 try std.testing.expectError(error.OutOfMemory, bump.allocValue(@as(u8, 5)));
1089 try std.testing.expect(
1090 (bump.backingDataCapacityLimit() orelse unreachable) >=
1091 bump.queryBackingDataCapacity(),
1092 );
1093
1094 bump.setBackingDataCapacityLimit(null);
1095 const value = try bump.allocValue(@as(u8, 5));
1096 try std.testing.expectEqual(@as(u8, 5), value.*);
1097 }
1098
1099 test "small backing data capacity limit can fit a small request" {
1100 var bump = Bump.init(std.testing.allocator);
1101 defer bump.deinit();
1102
1103 bump.setBackingDataCapacityLimit(64);
1104 const bytes = try bump.allocator().alloc(u8, 1);
1105 try std.testing.expectEqual(@as(usize, 1), bytes.len);
1106 try std.testing.expect(
1107 (bump.backingDataCapacityLimit() orelse unreachable) >=
1108 bump.queryBackingDataCapacity(),
1109 );
1110 }
1111
1112 test "backing allocator failures surface as out of memory" {
1113 var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 });
1114 var bump = Bump.init(failing.allocator());
1115 defer bump.deinit();
1116
1117 try std.testing.expectError(error.OutOfMemory, bump.allocValue(@as(u8, 1)));
1118 }
1119
1120 test "changing backing data capacity limit with live allocations" {
1121 var bump = Bump.init(std.testing.allocator);
1122 defer bump.deinit();
1123
1124 bump.setBackingDataCapacityLimit(512);
1125 _ = try bump.allocValue(@as(u8, 10));
1126
1127 try std.testing.expectError(error.OutOfMemory, bump.allocator().alloc(u8, 2048));
1128
1129 bump.setBackingDataCapacityLimit(16_384);
1130 _ = try bump.allocator().alloc(u8, 2048);
1131 try std.testing.expect(
1132 (bump.backingDataCapacityLimit() orelse unreachable) >=
1133 bump.queryBackingDataCapacity(),
1134 );
1135 }
1136
1137 test "lowered backing data capacity limit blocks future chunks" {
1138 var bump = Bump.init(std.testing.allocator);
1139 defer bump.deinit();
1140
1141 _ = try bump.allocator().alloc(u8, 1);
1142 const current_capacity = bump.queryCapacity();
1143 bump.setBackingDataCapacityLimit(current_capacity - 1);
1144
1145 try std.testing.expectError(error.OutOfMemory, bump.allocator().alloc(u8, current_capacity + 1));
1146 }
1147
1148 test "reset preserves backing data capacity limit" {
1149 var bump = Bump.init(std.testing.allocator);
1150 defer bump.deinit();
1151
1152 bump.setBackingDataCapacityLimit(512);
1153 try std.testing.expect(bump.reset(.retain_current));
1154
1155 try std.testing.expectError(error.OutOfMemory, bump.allocator().alloc(u8, 2048));
1156 try std.testing.expect(
1157 (bump.backingDataCapacityLimit() orelse unreachable) >=
1158 bump.queryBackingDataCapacity(),
1159 );
1160 }
1161
1162 test "caller storage does not consume backing data capacity" {
1163 const limit = 512;
1164 var buffer: [1024]u8 = undefined;
1165 var bump = try Bump.initBuffer(std.testing.allocator, &buffer);
1166 defer bump.deinit();
1167
1168 const caller_capacity = bump.queryCallerDataCapacity();
1169 try std.testing.expect(caller_capacity > 0);
1170 try std.testing.expectEqual(caller_capacity, bump.queryCapacity());
1171 try std.testing.expectEqual(@as(usize, 0), bump.queryBackingDataCapacity());
1172
1173 bump.setBackingDataCapacityLimit(limit);
1174 _ = try bump.alloc(u8, bump.queryCurrentChunkAvailable());
1175 const backed = try bump.alloc(u8, 1);
1176 const buffer_start = @intFromPtr(&buffer);
1177 const backed_start = @intFromPtr(backed.ptr);
1178
1179 try std.testing.expect(backed_start < buffer_start or backed_start >= buffer_start + buffer.len);
1180 try std.testing.expect(bump.queryBackingDataCapacity() > 0);
1181 try std.testing.expect(bump.queryBackingDataCapacity() <= limit);
1182 try std.testing.expectEqual(
1183 bump.queryCapacity(),
1184 bump.queryCallerDataCapacity() + bump.queryBackingDataCapacity(),
1185 );
1186 }
1187
1188 test "free all restores caller capacity outside the backing limit" {
1189 var buffer: [1024]u8 = undefined;
1190 var bump = try Bump.initBuffer(std.testing.allocator, &buffer);
1191 defer bump.deinit();
1192
1193 bump.setBackingDataCapacityLimit(512);
1194 _ = try bump.alloc(u8, bump.queryCurrentChunkAvailable());
1195 _ = try bump.alloc(u8, 1);
1196 try std.testing.expect(bump.queryBackingDataCapacity() > 0);
1197
1198 bump.setBackingDataCapacityLimit(0);
1199 try std.testing.expect(bump.reset(.free_all));
1200 try std.testing.expectEqual(@as(usize, 0), bump.queryBackingDataCapacity());
1201 try std.testing.expect(bump.queryCallerDataCapacity() > 0);
1202 try std.testing.expectEqual(
1203 bump.queryCallerDataCapacity(),
1204 bump.queryCapacity(),
1205 );
1206 }
1207
1208 test "zero backing capacity cannot retain a metadata only chunk" {
1209 var bump = Bump.init(std.testing.allocator);
1210 defer bump.deinit();
1211
1212 _ = try bump.alloc(u8, 1);
1213 bump.setBackingDataCapacityLimit(0);
1214 try std.testing.expect(bump.reset(.{ .retain_with_limit = 16 }));
1215 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacity());
1216 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacityIncludingMetadata());
1217
1218 var chunks = bump.iterAllocatedChunks();
1219 try std.testing.expectEqual(@as(?[]u8, null), chunks.next());
1220 }
1221
1222 test "retain capacity fails when a lowered backing limit cannot replace owned chunks" {
1223 var bump = Bump.init(std.testing.allocator);
1224 defer bump.deinit();
1225
1226 _ = try bump.allocator().alloc(u8, 1 << 9);
1227 _ = try bump.allocator().alloc(u8, 1 << 9);
1228 try std.testing.expect(bump.queryBackingDataCapacity() > 0);
1229
1230 bump.setBackingDataCapacityLimit(0);
1231 try std.testing.expect(!bump.reset(.retain_capacity));
1232 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacity());
1233 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacityIncludingMetadata());
1234 }
1235
1236 test "retain capacity failure restores caller storage below the backing limit" {
1237 var buffer: [1024]u8 = undefined;
1238 var bump = try Bump.initBuffer(std.testing.allocator, &buffer);
1239 defer bump.deinit();
1240
1241 const caller_capacity = bump.queryCallerDataCapacity();
1242 _ = try bump.allocator().alloc(u8, buffer.len + 1);
1243 try std.testing.expect(bump.queryBackingDataCapacity() > 0);
1244
1245 bump.setBackingDataCapacityLimit(0);
1246 try std.testing.expect(!bump.reset(.retain_capacity));
1247 try std.testing.expectEqual(caller_capacity, bump.queryCallerDataCapacity());
1248 try std.testing.expectEqual(caller_capacity, bump.queryCapacity());
1249 try std.testing.expectEqual(@as(usize, 0), bump.queryBackingDataCapacity());
1250 }
1251
1252 test "reset lowers allocated bytes after multiple chunks" {
1253 var bump = Bump.init(std.testing.allocator);
1254 defer bump.deinit();
1255
1256 _ = try bump.allocator().alloc(u8, 1 << 9);
1257 _ = try bump.allocator().alloc(u8, 1 << 9);
1258
1259 const before = bump.queryCapacity();
1260 try std.testing.expect(bump.reset(.retain_current));
1261 const after = bump.queryCapacity();
1262
1263 try std.testing.expect(after < before);
1264 }
1265
1266 test "reset free_all releases every chunk" {
1267 var bump = Bump.init(std.testing.allocator);
1268 defer bump.deinit();
1269
1270 _ = try bump.allocator().alloc(u8, 4096);
1271 try std.testing.expect(bump.queryCapacity() > 0);
1272
1273 try std.testing.expect(bump.reset(.free_all));
1274 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacity());
1275 var iter = bump.iterAllocatedChunks();
1276 try std.testing.expect(iter.next() == null);
1277 }
1278
1279 test "reset retain_capacity collapses to one reusable chunk" {
1280 var bump = Bump.init(std.testing.allocator);
1281 defer bump.deinit();
1282
1283 var index: usize = 0;
1284 while (index < 8) : (index += 1) {
1285 _ = try bump.allocator().alloc(u8, 2048);
1286 }
1287
1288 const before = bump.queryCapacity();
1289 try std.testing.expect(bump.reset(.retain_capacity));
1290 try std.testing.expect(bump.queryCapacity() >= before);
1291
1292 var iter = bump.iterAllocatedChunks();
1293 try std.testing.expect(iter.next() != null);
1294 try std.testing.expect(iter.next() == null);
1295
1296 const retained = bump.queryCapacity();
1297 try std.testing.expect(bump.reset(.retain_capacity));
1298 try std.testing.expectEqual(retained, bump.queryCapacity());
1299 }
1300
1301 test "reset retain_with_limit caps retained capacity" {
1302 var bump = Bump.init(std.testing.allocator);
1303 defer bump.deinit();
1304
1305 _ = try bump.allocator().alloc(u8, 8192);
1306 _ = try bump.allocator().alloc(u8, 8192);
1307
1308 try std.testing.expect(bump.queryCapacity() > 2048);
1309 try std.testing.expect(bump.reset(.{ .retain_with_limit = 2048 }));
1310 try std.testing.expect(bump.queryCapacity() <= 2048);
1311 }
1312
1313 test "clear convenience methods mirror reset modes" {
1314 var bump = Bump.init(std.testing.allocator);
1315 defer bump.deinit();
1316
1317 _ = try bump.allocator().alloc(u8, 4096);
1318 _ = try bump.allocator().alloc(u8, 4096);
1319 const multi_chunk_capacity = bump.queryCapacity();
1320
1321 bump.clearRetainingCurrent();
1322 try std.testing.expect(bump.queryCapacity() < multi_chunk_capacity);
1323 try std.testing.expectEqual(bump.queryCapacity(), bump.queryCurrentChunkAvailable());
1324
1325 _ = try bump.allocator().alloc(u8, 2048);
1326 try std.testing.expect(bump.clearRetainingCapacity());
1327 try std.testing.expectEqual(bump.queryCapacity(), bump.queryCurrentChunkAvailable());
1328
1329 _ = try bump.allocator().alloc(u8, 8192);
1330 try std.testing.expect(bump.clearRetainingCapacityLimit(1024));
1331 try std.testing.expect(bump.queryCapacity() <= 1024);
1332
1333 bump.clearAndFree();
1334 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacity());
1335 }
1336
1337 test "free reclaims only the most recent allocation" {
1338 var bump = try Bump.initCapacity(std.testing.allocator, 128);
1339 defer bump.deinit();
1340 const allocator_instance = bump.allocator();
1341
1342 const capacity = bump.queryCurrentChunkAvailable();
1343 const first = try allocator_instance.alloc(u8, 8);
1344 const second = try allocator_instance.alloc(u8, 8);
1345 allocator_instance.free(first);
1346 try std.testing.expect(bump.queryCurrentChunkAvailable() < capacity);
1347 allocator_instance.free(second);
1348 try std.testing.expect(bump.queryCurrentChunkAvailable() > capacity - 16);
1349 }
1350
1351 test "free reclaims aligned allocation footprint" {
1352 var bump = Bump.init(std.testing.allocator);
1353 defer bump.deinit();
1354 const allocator_instance = bump.allocator();
1355
1356 const bytes = try allocator_instance.alignedAlloc(u8, .@"64", 1);
1357 const capacity = bump.queryCapacity();
1358 try std.testing.expect(bump.queryUsedCapacity() >= 64);
1359
1360 allocator_instance.free(bytes);
1361 try std.testing.expectEqual(capacity, bump.queryCurrentChunkAvailable());
1362 try std.testing.expectEqual(@as(usize, 0), bump.queryUsedCapacity());
1363 }
1364
1365 test "remap can grow most recent allocation by moving downward" {
1366 var bump = try Bump.initCapacity(std.testing.allocator, 128);
1367 defer bump.deinit();
1368 const allocator_instance = bump.allocator();
1369
1370 const bytes = try allocator_instance.alloc(u8, 8);
1371 @memcpy(bytes, "abcdefgh");
1372 const grown = allocator_instance.remap(bytes, 16) orelse return error.RemapFailed;
1373
1374 try std.testing.expectEqualSlices(u8, "abcdefgh", grown[0..8]);
1375 try std.testing.expect(@intFromPtr(grown.ptr) <= @intFromPtr(bytes.ptr));
1376 }
1377
1378 test "remap grow within aligned footprint keeps address" {
1379 var bump = try Bump.initCapacity(std.testing.allocator, 256);
1380 defer bump.deinit();
1381 const allocator_instance = bump.allocator();
1382
1383 const bytes = try allocator_instance.alignedAlloc(u8, .@"64", 65);
1384 @memset(bytes, 0xaa);
1385 const same = allocator_instance.remap(bytes, bytes.len) orelse return error.RemapFailed;
1386 try std.testing.expectEqual(@intFromPtr(bytes.ptr), @intFromPtr(same.ptr));
1387 try std.testing.expectEqual(@as(u8, 0xaa), same[0]);
1388 const grown = allocator_instance.remap(same, 127) orelse return error.RemapFailed;
1389
1390 try std.testing.expectEqual(@intFromPtr(bytes.ptr), @intFromPtr(grown.ptr));
1391 try std.testing.expectEqual(@as(u8, 0xaa), grown[0]);
1392 allocator_instance.free(grown);
1393 }
1394
1395 test "remap shrink preserves prefix and reclaims footprint" {
1396 var bump = Bump.init(std.testing.allocator);
1397 defer bump.deinit();
1398 const allocator_instance = bump.allocator();
1399
1400 const bytes = try allocator_instance.alignedAlloc(u8, .@"64", 96);
1401 const capacity = bump.queryCapacity();
1402 for (bytes, 0..) |*byte, index| byte.* = @intCast(index);
1403
1404 const shrunk = allocator_instance.remap(bytes, 17) orelse return error.RemapFailed;
1405 for (shrunk, 0..) |byte, index| {
1406 try std.testing.expectEqual(@as(u8, @intCast(index)), byte);
1407 }
1408 try std.testing.expect(@intFromPtr(shrunk.ptr) > @intFromPtr(bytes.ptr));
1409
1410 allocator_instance.free(shrunk);
1411 try std.testing.expectEqual(capacity, bump.queryCurrentChunkAvailable());
1412 }
1413
1414 test "resize succeeds only when the allocation footprint is unchanged" {
1415 var bump = try Bump.initCapacity(std.testing.allocator, 512);
1416 defer bump.deinit();
1417 const allocator_instance = bump.allocator();
1418
1419 const same = try allocator_instance.alloc(u8, 32);
1420 @memset(same, 0xbb);
1421 try std.testing.expect(allocator_instance.resize(same, same.len));
1422 try std.testing.expectEqual(@as(u8, 0xbb), same[0]);
1423 allocator_instance.free(same);
1424
1425 const bytes = try allocator_instance.alignedAlloc(u8, .@"64", 65);
1426 @memset(bytes, 0xaa);
1427
1428 try std.testing.expect(allocator_instance.resize(bytes, 127));
1429 const grown_in_place: []align(64) u8 = bytes.ptr[0..127];
1430 try std.testing.expectEqual(@as(u8, 0xaa), grown_in_place[0]);
1431 try std.testing.expect(!allocator_instance.resize(grown_in_place, 64));
1432
1433 allocator_instance.free(grown_in_place);
1434 }
1435
1436 test "realloc preserves prefixes while moving through the allocator interface" {
1437 var bump = try Bump.initCapacity(std.testing.allocator, 256);
1438 defer bump.deinit();
1439 const allocator_instance = bump.allocator();
1440
1441 var bytes = try allocator_instance.alloc(u8, 32);
1442 @memcpy(bytes[0..8], "zigarena");
1443
1444 bytes = try allocator_instance.realloc(bytes, 160);
1445 try std.testing.expectEqualSlices(u8, "zigarena", bytes[0..8]);
1446
1447 bytes = try allocator_instance.realloc(bytes, 12);
1448 try std.testing.expectEqualSlices(u8, "zigarena", bytes[0..8]);
1449 allocator_instance.free(bytes);
1450 }
1451
1452 test "iterated chunks contain allocations newest to oldest" {
1453 var bump = Bump.init(std.testing.allocator);
1454 defer bump.deinit();
1455
1456 _ = try bump.allocValue(@as(u8, 'a'));
1457 _ = try bump.allocValue(@as(u8, 'b'));
1458 _ = try bump.allocValue(@as(u8, 'c'));
1459
1460 var iter = bump.iterAllocatedChunks();
1461 const chunk = iter.next() orelse return error.MissingChunk;
1462 try std.testing.expectEqualSlices(u8, "cba", chunk);
1463 try std.testing.expect(iter.next() == null);
1464 }
1465
1466 test "deterministic allocation ranges never overlap" {
1467 var bump = Bump.init(std.testing.allocator);
1468 defer bump.deinit();
1469 var ranges: std.ArrayList([2]usize) = .empty;
1470 defer ranges.deinit(std.testing.allocator);
1471
1472 var prng = std.Random.DefaultPrng.init(0xB00A10);
1473 const random = prng.random();
1474 var index: usize = 0;
1475 while (index < 512) : (index += 1) {
1476 const len = random.intRangeAtMost(usize, 1, 257);
1477 const alignment_shift: u6 = @intCast(random.intRangeAtMost(u8, 0, 6));
1478 const alignment = Alignment.fromByteUnits(@as(usize, 1) << alignment_shift);
1479 const allocation = try bump.allocBytes(len, alignment);
1480 const start = @intFromPtr(allocation);
1481 const end = start + len;
1482 try std.testing.expectEqual(@as(usize, 0), start % alignment.toByteUnits());
1483 for (ranges.items) |range| {
1484 try std.testing.expect(end <= range[0] or range[1] <= start);
1485 }
1486 try ranges.append(std.testing.allocator, .{ start, end });
1487 }
1488 }
1489
1490 test "chunk iteration contains exact allocation footprints" {
1491 inline for (.{ 1, 2, 4, 8, 16 }) |alignment| {
1492 var bump = try Bump.initCapacity(std.testing.allocator, 513);
1493 defer bump.deinit();
1494
1495 var sizes: std.ArrayList(usize) = .empty;
1496 defer sizes.deinit(std.testing.allocator);
1497
1498 var index: usize = 1;
1499 while (index <= 64) : (index += 1) {
1500 const len = (index % 10 + 1) * alignment;
1501 _ = try bump.allocBytes(len, .fromByteUnits(alignment));
1502 try sizes.append(std.testing.allocator, len);
1503 }
1504
1505 var next_size = sizes.items.len;
1506 var iter = bump.iterAllocatedChunks();
1507 while (iter.next()) |chunk| {
1508 var remaining = chunk.len;
1509 while (remaining > 0) {
1510 if (next_size == 0) return error.ChunkContainsUnexpectedPadding;
1511 next_size -= 1;
1512 const len = sizes.items[next_size];
1513 try std.testing.expect(remaining >= len);
1514 remaining -= len;
1515 }
1516 }
1517 try std.testing.expectEqual(@as(usize, 0), next_size);
1518 }
1519 }
1520
1521 test "reported capacity including metadata bounds backing storage" {
1522 var bump = Bump.init(std.testing.allocator);
1523 defer bump.deinit();
1524
1525 var requested_bytes: usize = 0;
1526 var index: usize = 0;
1527 while (index < 20) : (index += 1) {
1528 const len = index * 17;
1529 _ = try bump.allocFill(u8, len, 0);
1530 requested_bytes += len;
1531
1532 if (requested_bytes == 0) {
1533 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacity());
1534 try std.testing.expectEqual(@as(usize, 0), bump.queryCapacityIncludingMetadata());
1535 } else {
1536 try std.testing.expect(bump.queryCapacity() >= requested_bytes);
1537 try std.testing.expect(bump.queryCapacityIncludingMetadata() > bump.queryCapacity());
1538 try std.testing.expect(bump.queryCapacityIncludingMetadata() < bump.queryCapacity() + 20 * 100);
1539 }
1540 }
1541 }
1542
1543 test "capacity including metadata counts high-alignment chunk headers" {
1544 var bump = Bump.init(std.testing.allocator);
1545 defer bump.deinit();
1546
1547 _ = try bump.allocBytes(1, .fromByteUnits(0x1000));
1548
1549 try std.testing.expect(bump.queryCapacityIncludingMetadata() >= bump.queryCapacity() + 0x1000);
1550 }
1551
1552 test "every active allocation is contained in an iterated chunk" {
1553 var bump = Bump.init(std.testing.allocator);
1554 defer bump.deinit();
1555
1556 var ranges: std.ArrayList([2]usize) = .empty;
1557 defer ranges.deinit(std.testing.allocator);
1558
1559 var index: usize = 0;
1560 while (index < 128) : (index += 1) {
1561 const slice = try bump.alloc(u64, index % 7 + 1);
1562 const start = @intFromPtr(slice.ptr);
1563 try ranges.append(std.testing.allocator, .{ start, start + slice.len * @sizeOf(u64) });
1564 }
1565
1566 for (ranges.items) |range| {
1567 var found = false;
1568 var iter = bump.iterAllocatedChunks();
1569 while (iter.next()) |chunk| {
1570 const chunk_start = @intFromPtr(chunk.ptr);
1571 const chunk_end = chunk_start + chunk.len;
1572 if (chunk_start <= range[0] and range[1] <= chunk_end) {
1573 found = true;
1574 break;
1575 }
1576 }
1577 try std.testing.expect(found);
1578 }
1579 }
1580
1581 const ActiveAllocationRecord = struct {
1582 slice: []u8,
1583 fill: u8,
1584 };
1585
1586 test "allocator state machine preserves ranges and prefixes" {
1587 var bump = Bump.init(std.testing.allocator);
1588 defer bump.deinit();
1589 const allocator_instance = bump.allocator();
1590
1591 var active: std.ArrayList(ActiveAllocationRecord) = .empty;
1592 defer active.deinit(std.testing.allocator);
1593
1594 var prng = std.Random.DefaultPrng.init(0xA110CA7E);
1595 const random = prng.random();
1596
1597 var step: usize = 0;
1598 while (step < 320) : (step += 1) {
1599 const op = random.intRangeLessThan(u8, 0, 100);
1600 if (op < 45 or active.items.len == 0) {
1601 const len = random.intRangeAtMost(usize, 1, 160);
1602 const fill: u8 = @intCast(step & 0xff);
1603 const slice = try allocator_instance.alloc(u8, len);
1604 @memset(slice, fill);
1605 try active.append(std.testing.allocator, .{ .slice = slice, .fill = fill });
1606 } else if (op < 75) {
1607 const slot = random.intRangeLessThan(usize, 0, active.items.len);
1608 var record = &active.items[slot];
1609 const old_len = record.slice.len;
1610 const new_len = random.intRangeAtMost(usize, 1, 224);
1611 const resized = try allocator_instance.realloc(record.slice, new_len);
1612 const prefix_len = @min(old_len, new_len);
1613 for (resized[0..prefix_len]) |byte| {
1614 try std.testing.expectEqual(record.fill, byte);
1615 }
1616 @memset(resized, record.fill);
1617 record.slice = resized;
1618 } else if (op < 90) {
1619 const slot = random.intRangeLessThan(usize, 0, active.items.len);
1620 allocator_instance.free(active.items[slot].slice);
1621 _ = active.swapRemove(slot);
1622 } else {
1623 try std.testing.expect(bump.reset(.retain_current));
1624 active.clearRetainingCapacity();
1625 }
1626
1627 for (active.items, 0..) |record, left_index| {
1628 const left_start = @intFromPtr(record.slice.ptr);
1629 const left_end = left_start + record.slice.len;
1630 for (record.slice) |byte| {
1631 try std.testing.expectEqual(record.fill, byte);
1632 }
1633 for (active.items[left_index + 1 ..]) |other| {
1634 const right_start = @intFromPtr(other.slice.ptr);
1635 const right_end = right_start + other.slice.len;
1636 try std.testing.expect(left_end <= right_start or right_end <= left_start);
1637 }
1638 }
1639 }
1640 }
1641
1642 test "std ArrayList can use the bump allocator" {
1643 var bump = Bump.init(std.testing.allocator);
1644 defer bump.deinit();
1645 const allocator_instance = bump.allocator();
1646
1647 var list: std.ArrayList(u32) = .empty;
1648 defer list.deinit(allocator_instance);
1649
1650 var index: u32 = 0;
1651 while (index < 1000) : (index += 1) {
1652 try list.append(allocator_instance, index);
1653 }
1654
1655 try std.testing.expectEqual(@as(usize, 1000), list.items.len);
1656 try std.testing.expectEqual(@as(u32, 0), list.items[0]);
1657 try std.testing.expectEqual(@as(u32, 999), list.items[999]);
1658 }
1659
1660 test "std ArrayList u8 can use the bump allocator" {
1661 var bump = Bump.init(std.testing.allocator);
1662 defer bump.deinit();
1663 const allocator_instance = bump.allocator();
1664
1665 var string: std.ArrayList(u8) = .empty;
1666 defer string.deinit(allocator_instance);
1667
1668 try string.appendSlice(allocator_instance, "hello");
1669 try string.append(allocator_instance, ' ');
1670 try string.appendSlice(allocator_instance, "bumpalo");
1671
1672 try std.testing.expectEqualStrings("hello bumpalo", string.items);
1673 }