lib/gpalloc/src/allocator.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const sys = @import("sys");
3 const sys_thread = sys.thread;
4 const bin_mod = @import("bin.zig");
5 const cache_policy = @import("cache/root.zig");
6 const config_mod = @import("config.zig");
7 const large_cache_policy = @import("large/root.zig");
8 const page_mod = @import("page/root.zig");
9 const size_class = @import("class.zig");
10 const stats_mod = @import("stats.zig");
11
12 const Allocator = std.mem.Allocator;
13 const Alignment = std.mem.Alignment;
14 const assert = std.debug.assert;
15 const Config = config_mod.Config;
16 const Stats = stats_mod.Stats;
17 const min_alignment = config_mod.min_alignment;
18 const page_size = config_mod.page_size;
19 const max_small_size = config_mod.max_small_size;
20 const magic = page_mod.magic;
21 const Page = page_mod.Page;
22 const Bin = bin_mod.Bin;
23
24 const ThreadCache = cache_policy.ThreadCache;
25 const cpuCountThreadCacheActiveLimit = cache_policy.cpuCountThreadCacheActiveLimit;
26 const defaultThreadCacheActiveLimit = cache_policy.defaultThreadCacheActiveLimit;
27 const loadThreadCache = cache_policy.loadThreadCache;
28 const loadThreadCacheForAllocFastPath = cache_policy.loadThreadCacheForAllocFastPath;
29 const loadThreadCacheForSmallFastPath = cache_policy.loadThreadCacheForSmallFastPath;
30 const localThreadCacheBinCount = cache_policy.localThreadCacheBinCount;
31 const popLocalThreadCacheBin = cache_policy.popLocalThreadCacheBin;
32 const pushLocalThreadCacheBin = cache_policy.pushLocalThreadCacheBin;
33 const storeThreadCache = cache_policy.storeThreadCache;
34
35 const ThreadCacheReleaseMode = enum {
36 unregister,
37 destructor,
38 };
39
40 const PageCreateResult = struct {
41 page: *Page,
42 mapped: bool,
43 };
44
45 const ThreadCacheExit = struct {
46 var mutex: std.atomic.Mutex = .unlocked;
47 var initialized: bool = false;
48 var available: bool = false;
49 var key: sys.thread.ThreadSpecificKey = .{};
50
51 fn ensureKey() ?sys.thread.ThreadSpecificKey {
52 if (!sys.thread.threadSpecificDestructorsSupported()) return null;
53
54 lock();
55 defer unlock();
56
57 if (!initialized) {
58 key = sys.thread.createThreadSpecificKey(threadCacheExitDestructor) catch {
59 initialized = true;
60 available = false;
61 return null;
62 };
63 initialized = true;
64 available = true;
65 }
66 return if (available) key else null;
67 }
68
69 fn currentKey() ?sys.thread.ThreadSpecificKey {
70 if (!sys.thread.threadSpecificDestructorsSupported()) return null;
71
72 lock();
73 defer unlock();
74
75 return if (initialized and available) key else null;
76 }
77
78 fn lock() void {
79 while (!mutex.tryLock()) std.atomic.spinLoopHint();
80 }
81
82 fn unlock() void {
83 mutex.unlock();
84 }
85 };
86
87 fn threadCacheExitDestructor(value: *anyopaque) callconv(.c) void {
88 const self: *GpAllocator = @ptrCast(@alignCast(value));
89 const cache = loadThreadCache() orelse return;
90 if (cache.owner != threadCacheOwner(self)) return;
91 self.releaseThreadCache(cache, .destructor, @returnAddress());
92 }
93
94 fn threadCacheOwner(self: *GpAllocator) *anyopaque {
95 return @ptrCast(self);
96 }
97
98 fn threadCacheAllocator(owner: *anyopaque) *GpAllocator {
99 return @ptrCast(@alignCast(owner));
100 }
101
102 fn assertSmallBlockClass(ptr: [*]u8, class_index: usize) void {
103 if (comptime !std.debug.runtime_safety) return;
104 const page = page_mod.fromBlock(ptr);
105 assert(page.magic == magic);
106 assert(page.class_index == class_index);
107 }
108
109 pub const GpAllocator = struct {
110 backing_allocator: Allocator,
111 config: Config,
112 backing_mutex: std.atomic.Mutex,
113 bin_mutexes: [size_class.count]std.atomic.Mutex,
114 bins: [size_class.count]Bin,
115 active_thread_cache_limit: usize,
116 active_thread_cache_count: usize,
117 retained_thread_caches: ?*ThreadCache,
118 retained_thread_cache_count: usize,
119 cached_empty_pages: ?*Page,
120 cached_empty_page_count: usize,
121 large_cache: large_cache_policy.Cache,
122 stats_data: stats_mod.AtomicStats,
123 medium_large_cache: ?*large_cache_policy.MediumCache,
124
125 const Self = @This();
126
127 pub fn init(backing_allocator: Allocator, config: Config) Self {
128 var effective_config = config;
129 if (effective_config.collect_stats) {
130 effective_config.thread_cache = false;
131 effective_config.large_cache = false;
132 }
133
134 return .{
135 .backing_allocator = backing_allocator,
136 .config = effective_config,
137 .backing_mutex = .unlocked,
138 .bin_mutexes = @as([size_class.count]std.atomic.Mutex, @splat(.unlocked)),
139 .bins = @as([size_class.count]Bin, @splat(.{})),
140 .active_thread_cache_limit = effective_config.thread_cache_active_limit,
141 .active_thread_cache_count = 0,
142 .retained_thread_caches = null,
143 .retained_thread_cache_count = 0,
144 .cached_empty_pages = null,
145 .cached_empty_page_count = 0,
146 .large_cache = .{},
147 .stats_data = .{},
148 .medium_large_cache = null,
149 };
150 }
151
152 pub fn deinit(self: *Self) void {
153 self.releaseCurrentThreadCache(@returnAddress());
154
155 self.lockAllBins();
156 defer self.unlockAllBins();
157
158 for (&self.bins) |*bin| {
159 self.destroyBinPages(bin, @returnAddress());
160 }
161 self.lockBacking();
162 defer self.unlockBacking();
163 self.large_cache.destroyAll(self.backing_allocator, @returnAddress());
164 self.destroyMediumLargeCache(@returnAddress());
165 self.destroyCachedEmptyPages(@returnAddress());
166 self.destroyRetainedThreadCaches();
167 self.stats_data.reset();
168 }
169
170 pub fn allocator(self: *Self) Allocator {
171 return .{
172 .ptr = self,
173 .vtable = &vtable,
174 };
175 }
176
177 pub fn rawAlloc(self: *Self, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
178 assert(len > 0);
179
180 if (size_class.indexFor(len, alignment)) |class_index| {
181 if (self.useThreadCache()) {
182 if (loadThreadCacheForAllocFastPath()) |cache| {
183 if (cache.owner == threadCacheOwner(self)) {
184 if (popLocalThreadCacheBin(cache, class_index)) |ptr| return ptr;
185 }
186 }
187 }
188 return self.rawAllocSmallSlow(class_index, len, ret_addr);
189 }
190
191 return self.rawAllocLarge(len, alignment, ret_addr);
192 }
193
194 noinline fn rawAllocSmallSlow(self: *Self, class_index: usize, len: usize, ret_addr: usize) ?[*]u8 {
195 if (self.useThreadCache()) {
196 return self.allocSmallThreadCached(class_index, ret_addr);
197 }
198 self.lockBin(class_index);
199 defer self.unlockBin(class_index);
200 return self.allocSmall(class_index, len, ret_addr);
201 }
202
203 noinline fn rawAllocLarge(self: *Self, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
204 const large_class = if (self.useLargeCache()) large_cache_policy.classFor(len, alignment) else null;
205 self.lockBacking();
206 defer self.unlockBacking();
207 const ptr = if (large_class) |class| blk: {
208 const entry = self.large_cache.popAtLeast(class) orelse large_cache_policy.Entry{
209 .class = class,
210 .ptr = self.backing_allocator.rawAlloc(large_cache_policy.backingSize(class), large_cache_policy.alignment, ret_addr) orelse return null,
211 };
212 break :blk large_cache_policy.initializeHeader(entry.ptr, entry.class);
213 } else if (self.useMediumLargeCache(len, alignment)) blk: {
214 const class = large_cache_policy.mediumClassFor(len, alignment).?;
215 const entry = if (self.medium_large_cache) |cache|
216 cache.popAtLeast(class) orelse large_cache_policy.Entry{
217 .class = class,
218 .ptr = self.backing_allocator.rawAlloc(large_cache_policy.mediumBackingSize(class), large_cache_policy.alignment, ret_addr) orelse return null,
219 }
220 else
221 large_cache_policy.Entry{
222 .class = class,
223 .ptr = self.backing_allocator.rawAlloc(large_cache_policy.mediumBackingSize(class), large_cache_policy.alignment, ret_addr) orelse return null,
224 };
225 break :blk large_cache_policy.initializeMediumHeader(entry.ptr, entry.class);
226 } else (self.backing_allocator.rawAlloc(len, alignment, ret_addr) orelse return null);
227 self.addStatU64(&self.stats_data.large_allocations, 1);
228 self.addStatUsize(&self.stats_data.active_large_bytes, len);
229 return ptr;
230 }
231
232 pub fn rawResize(self: *Self, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
233 _ = ret_addr;
234 assert(memory.len > 0);
235 assert(new_len > 0);
236
237 if (size_class.indexFor(memory.len, alignment)) |class_index| {
238 assertSmallBlockClass(memory.ptr, class_index);
239 const new_class = size_class.indexFor(new_len, alignment) orelse return false;
240 if (new_class != class_index) return false;
241 if (self.useThreadCache()) {
242 return true;
243 }
244 self.lockBin(class_index);
245 defer self.unlockBin(class_index);
246 self.resizeSmall(memory.len, new_len);
247 return true;
248 }
249
250 return self.rawResizeLarge(memory, alignment, new_len);
251 }
252
253 noinline fn rawResizeLarge(self: *Self, memory: []u8, alignment: Alignment, new_len: usize) bool {
254 const new_class = size_class.indexFor(new_len, alignment);
255 if (new_class != null) return false;
256 if (self.useLargeCache() and large_cache_policy.classFor(memory.len, alignment) != null) {
257 const header = large_cache_policy.headerFromUserPointer(memory.ptr);
258 const class = large_cache_policy.classFromHeader(header) orelse unreachable;
259 if (large_cache_policy.classFor(new_len, alignment) == null) return false;
260 if (new_len <= class.size) {
261 self.resizeLarge(memory.len, new_len);
262 return true;
263 }
264 return false;
265 }
266 if (self.useMediumLargeCache(memory.len, alignment)) {
267 const header = large_cache_policy.mediumHeaderFromUserPointer(memory.ptr);
268 const class = large_cache_policy.mediumClassFromHeader(header) orelse unreachable;
269 if (large_cache_policy.mediumClassFor(new_len, alignment) == null) return false;
270 if (new_len <= class.size) {
271 self.resizeLarge(memory.len, new_len);
272 return true;
273 }
274 return false;
275 }
276
277 if (self.usesCachedLargeRepresentation(new_len, alignment)) return false;
278 self.lockBacking();
279 defer self.unlockBacking();
280 if (!self.backing_allocator.rawResize(memory, alignment, new_len, @returnAddress())) return false;
281 self.resizeLarge(memory.len, new_len);
282 return true;
283 }
284
285 pub fn rawRemap(self: *Self, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
286 assert(memory.len > 0);
287 assert(new_len > 0);
288
289 if (size_class.indexFor(memory.len, alignment)) |class_index| {
290 assertSmallBlockClass(memory.ptr, class_index);
291 const new_class = size_class.indexFor(new_len, alignment) orelse return null;
292 if (new_class != class_index) return null;
293 if (self.useThreadCache()) {
294 return memory.ptr;
295 }
296 self.lockBin(class_index);
297 defer self.unlockBin(class_index);
298 self.resizeSmall(memory.len, new_len);
299 return memory.ptr;
300 }
301
302 return self.rawRemapLarge(memory, alignment, new_len, ret_addr);
303 }
304
305 noinline fn rawRemapLarge(self: *Self, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
306 const new_class = size_class.indexFor(new_len, alignment);
307 if (new_class != null) return null;
308 if (self.useLargeCache() and large_cache_policy.classFor(memory.len, alignment) != null) {
309 const header = large_cache_policy.headerFromUserPointer(memory.ptr);
310 const class = large_cache_policy.classFromHeader(header) orelse unreachable;
311 if (large_cache_policy.classFor(new_len, alignment) == null) return null;
312 if (new_len <= class.size) {
313 self.resizeLarge(memory.len, new_len);
314 return memory.ptr;
315 }
316 return null;
317 }
318 if (self.useMediumLargeCache(memory.len, alignment)) {
319 const header = large_cache_policy.mediumHeaderFromUserPointer(memory.ptr);
320 const class = large_cache_policy.mediumClassFromHeader(header) orelse unreachable;
321 if (large_cache_policy.mediumClassFor(new_len, alignment) == null) return null;
322 if (new_len <= class.size) {
323 self.resizeLarge(memory.len, new_len);
324 return memory.ptr;
325 }
326 return null;
327 }
328
329 if (self.usesCachedLargeRepresentation(new_len, alignment)) return null;
330 self.lockBacking();
331 defer self.unlockBacking();
332 const ptr = self.backing_allocator.rawRemap(memory, alignment, new_len, ret_addr) orelse return null;
333 self.resizeLarge(memory.len, new_len);
334 return ptr;
335 }
336
337 pub fn rawFree(self: *Self, memory: []u8, alignment: Alignment, ret_addr: usize) void {
338 assert(memory.len > 0);
339
340 if (size_class.indexFor(memory.len, alignment)) |class_index| {
341 assertSmallBlockClass(memory.ptr, class_index);
342 if (self.useThreadCache()) {
343 if (loadThreadCacheForSmallFastPath()) |cache| {
344 if (cache.owner == threadCacheOwner(self)) {
345 const cache_limit = cache_policy.threadClassLimit(class_index);
346 if (pushLocalThreadCacheBin(cache, class_index, memory.ptr, cache_limit)) return;
347 }
348 }
349 }
350 self.rawFreeSmallSlow(class_index, memory, ret_addr);
351 return;
352 }
353
354 self.rawFreeLarge(memory, alignment, ret_addr);
355 }
356
357 noinline fn rawFreeSmallSlow(self: *Self, class_index: usize, memory: []u8, ret_addr: usize) void {
358 if (self.useThreadCache()) {
359 self.freeSmallThreadCached(class_index, memory.ptr, ret_addr);
360 return;
361 }
362 self.lockBin(class_index);
363 defer self.unlockBin(class_index);
364 self.freeSmall(page_mod.fromBlock(memory.ptr), class_index, memory, ret_addr);
365 }
366
367 noinline fn rawFreeLarge(self: *Self, memory: []u8, alignment: Alignment, ret_addr: usize) void {
368 self.addStatU64(&self.stats_data.large_frees, 1);
369 self.subStatUsize(&self.stats_data.active_large_bytes, memory.len);
370 const large_class = if (self.useLargeCache()) large_cache_policy.classFor(memory.len, alignment) else null;
371 self.lockBacking();
372 defer self.unlockBacking();
373 if (large_class != null) {
374 const header = large_cache_policy.headerFromUserPointer(memory.ptr);
375 const class = large_cache_policy.classFromHeader(header) orelse unreachable;
376 const base = large_cache_policy.baseFromUserPointer(memory.ptr);
377 if (self.large_cache.push(class, base, self.config.large_cache_limit_bytes, self.backing_allocator, ret_addr)) return;
378 self.backing_allocator.rawFree(base[0..large_cache_policy.backingSize(class)], large_cache_policy.alignment, ret_addr);
379 return;
380 }
381 if (self.useMediumLargeCache(memory.len, alignment)) {
382 const header = large_cache_policy.mediumHeaderFromUserPointer(memory.ptr);
383 const class = large_cache_policy.mediumClassFromHeader(header) orelse unreachable;
384 const base = large_cache_policy.mediumBaseFromUserPointer(memory.ptr);
385 if (self.mediumLargeCacheLocked()) |cache| {
386 if (cache.push(class, base, self.mediumLargeCacheLimit(), self.backing_allocator, ret_addr)) return;
387 }
388 self.backing_allocator.rawFree(base[0..large_cache_policy.mediumBackingSize(class)], large_cache_policy.alignment, ret_addr);
389 return;
390 }
391 self.backing_allocator.rawFree(memory, alignment, ret_addr);
392 }
393
394 pub fn rawFreeThreadCachedSmallBlock(self: *Self, ptr: [*]u8, ret_addr: usize) void {
395 assert(self.useThreadCache());
396 const page = page_mod.fromBlock(ptr);
397 self.freeSmallThreadCached(@intCast(page.class_index), ptr, ret_addr);
398 }
399
400 pub fn stats(self: *Self) Stats {
401 return self.stats_data.snapshot();
402 }
403
404 pub fn flushThreadCacheForCurrentThread(self: *Self) void {
405 self.releaseCurrentThreadCache(@returnAddress());
406 }
407
408 fn destroyBinPages(self: *Self, bin: *Bin, ret_addr: usize) void {
409 var page = bin.all;
410 while (page) |current| {
411 const next = current.next_all;
412 self.destroyPage(current, ret_addr);
413 page = next;
414 }
415 bin.clear();
416 }
417
418 fn lockBin(self: *Self, class_index: usize) void {
419 if (!self.config.thread_safe) return;
420 while (!self.bin_mutexes[class_index].tryLock()) {
421 std.atomic.spinLoopHint();
422 }
423 }
424
425 fn unlockBin(self: *Self, class_index: usize) void {
426 if (self.config.thread_safe) self.bin_mutexes[class_index].unlock();
427 }
428
429 fn lockBacking(self: *Self) void {
430 if (!self.config.thread_safe) return;
431 while (!self.backing_mutex.tryLock()) {
432 std.atomic.spinLoopHint();
433 }
434 }
435
436 fn unlockBacking(self: *Self) void {
437 if (self.config.thread_safe) self.backing_mutex.unlock();
438 }
439
440 fn lockAllBins(self: *Self) void {
441 if (!self.config.thread_safe) return;
442 for (0..self.bin_mutexes.len) |class_index| self.lockBin(class_index);
443 }
444
445 fn unlockAllBins(self: *Self) void {
446 if (!self.config.thread_safe) return;
447 var index = self.bins.len;
448 while (index > 0) {
449 index -= 1;
450 self.unlockBin(index);
451 }
452 }
453
454 fn useThreadCache(self: *Self) bool {
455 return self.config.thread_cache;
456 }
457
458 fn allocSmall(self: *Self, class_index: usize, requested_len: usize, ret_addr: usize) ?[*]u8 {
459 const ptr = self.reserveSmallBlock(class_index, ret_addr) orelse return null;
460 self.recordSmallAllocation(requested_len);
461 return ptr;
462 }
463
464 fn reserveSmallBlock(self: *Self, class_index: usize, ret_addr: usize) ?[*]u8 {
465 const bin = &self.bins[class_index];
466 if (bin.partial == null) {
467 const created = self.createPage(class_index, ret_addr) orelse return null;
468 const page = created.page;
469 bin.addPage(page);
470 if (created.mapped) {
471 self.addStatU64(&self.stats_data.pages_allocated, 1);
472 self.addStatUsize(&self.stats_data.mapped_small_bytes, page.mappedBytes());
473 }
474 }
475
476 const page = bin.partial.?;
477 if (page.live_count == 0) {
478 self.restoreDiscardedPage(page);
479 if (bin.empty_count > 0) {
480 bin.empty_count -= 1;
481 self.subStatUsize(&self.stats_data.retained_empty_pages, 1);
482 }
483 }
484 const ptr = page.allocate();
485 bin.popIfFull(page);
486 return ptr;
487 }
488
489 fn freeSmall(self: *Self, page: *Page, class_index: usize, memory: []u8, ret_addr: usize) void {
490 self.releaseSmallBlockFromPage(page, class_index, memory.ptr, ret_addr);
491 self.recordSmallFree(memory.len);
492 }
493
494 fn releaseSmallBlock(self: *Self, class_index: usize, ptr: [*]u8, ret_addr: usize) void {
495 self.releaseSmallBlockFromPage(page_mod.fromBlock(ptr), class_index, ptr, ret_addr);
496 }
497
498 fn releaseSmallBlockFromPage(self: *Self, page: *Page, class_index: usize, ptr: [*]u8, ret_addr: usize) void {
499 const bin = &self.bins[class_index];
500 assert(page.magic == magic);
501 assert(page.class_index == class_index);
502
503 const was_full = page.free_count == 0;
504 page.free(ptr);
505 if (was_full) bin.pushPartial(page);
506
507 if (page.live_count == 0) {
508 if (bin.empty_count < self.config.empty_page_retention_limit) {
509 bin.empty_count += 1;
510 self.addStatUsize(&self.stats_data.retained_empty_pages, 1);
511 self.discardRetainedEmptyPage(page);
512 } else {
513 bin.removePartial(page);
514 bin.removeAll(page);
515 if (self.retainCachedEmptyPage(page)) {
516 self.addStatUsize(&self.stats_data.retained_empty_pages, 1);
517 return;
518 }
519
520 const mapped_bytes = page.mappedBytes();
521 self.destroyPage(page, ret_addr);
522 self.addStatU64(&self.stats_data.pages_freed, 1);
523 self.subStatUsize(&self.stats_data.mapped_small_bytes, mapped_bytes);
524 }
525 }
526 }
527
528 fn discardRetainedEmptyPage(self: *Self, page: *Page) void {
529 if (self.config.page_provider != .os) return;
530 if (self.config.retained_empty_page_policy != .discard_unused) return;
531 const discarded_len = page_mod.discardUnused(page) orelse return;
532 self.addStatU64(&self.stats_data.empty_page_discards, 1);
533 self.addStatUsize(&self.stats_data.discarded_small_bytes, discarded_len);
534 }
535
536 fn restoreDiscardedPage(self: *Self, page: *Page) void {
537 const discarded_bytes = page_mod.restoreDiscarded(page) orelse return;
538 self.subStatUsize(&self.stats_data.discarded_small_bytes, discarded_bytes);
539 }
540
541 fn recordSmallAllocation(self: *Self, requested_len: usize) void {
542 self.addStatU64(&self.stats_data.small_allocations, 1);
543 self.addStatUsize(&self.stats_data.active_small_bytes, requested_len);
544 }
545
546 fn recordSmallFree(self: *Self, released_len: usize) void {
547 self.addStatU64(&self.stats_data.small_frees, 1);
548 self.subStatUsize(&self.stats_data.active_small_bytes, released_len);
549 }
550
551 fn allocSmallThreadCached(self: *Self, class_index: usize, ret_addr: usize) ?[*]u8 {
552 const cache = self.currentThreadCache(ret_addr) orelse {
553 self.lockBin(class_index);
554 defer self.unlockBin(class_index);
555 return self.reserveSmallBlock(class_index, ret_addr);
556 };
557 if (popLocalThreadCacheBin(cache, class_index)) |ptr| return ptr;
558
559 return self.allocSmallThreadCachedSlow(cache, class_index, ret_addr);
560 }
561
562 noinline fn allocSmallThreadCachedSlow(
563 self: *Self,
564 cache: *ThreadCache,
565 class_index: usize,
566 ret_addr: usize,
567 ) ?[*]u8 {
568 self.refillThreadCacheBin(cache, class_index, ret_addr);
569 return popLocalThreadCacheBin(cache, class_index);
570 }
571
572 fn freeSmallThreadCached(self: *Self, class_index: usize, ptr: [*]u8, ret_addr: usize) void {
573 const cache = self.currentThreadCacheSmallFastPath(ret_addr) orelse {
574 self.lockBin(class_index);
575 defer self.unlockBin(class_index);
576 self.releaseSmallBlock(class_index, ptr, ret_addr);
577 return;
578 };
579
580 const cache_limit = cache_policy.threadClassLimit(class_index);
581 if (pushLocalThreadCacheBin(cache, class_index, ptr, cache_limit)) return;
582
583 self.freeSmallThreadCachedSlow(cache, class_index, ptr, cache_limit, ret_addr);
584 }
585
586 noinline fn freeSmallThreadCachedSlow(
587 self: *Self,
588 cache: *ThreadCache,
589 class_index: usize,
590 ptr: [*]u8,
591 cache_limit: u16,
592 ret_addr: usize,
593 ) void {
594 self.drainLocalThreadCacheBin(cache, class_index, cache_policy.threadDrainCount(cache_limit), ret_addr);
595 if (pushLocalThreadCacheBin(cache, class_index, ptr, cache_limit)) return;
596
597 self.lockBin(class_index);
598 defer self.unlockBin(class_index);
599 self.releaseSmallBlock(class_index, ptr, ret_addr);
600 }
601
602 inline fn currentThreadCache(self: *Self, ret_addr: usize) ?*ThreadCache {
603 if (loadThreadCache()) |cache| {
604 if (cache.owner == threadCacheOwner(self)) return cache;
605 }
606 return self.currentThreadCacheSlow(ret_addr);
607 }
608
609 inline fn currentThreadCacheSmallFastPath(self: *Self, ret_addr: usize) ?*ThreadCache {
610 if (loadThreadCacheForSmallFastPath()) |cache| {
611 if (cache.owner == threadCacheOwner(self)) return cache;
612 }
613 return self.currentThreadCacheSlow(ret_addr);
614 }
615
616 noinline fn currentThreadCacheSlow(self: *Self, ret_addr: usize) ?*ThreadCache {
617 if (loadThreadCache()) |cache| {
618 if (cache.owner) |owner| {
619 threadCacheAllocator(owner).releaseThreadCache(cache, .unregister, ret_addr);
620 } else {
621 const storage_owner = cache.storage_owner orelse threadCacheOwner(self);
622 threadCacheAllocator(storage_owner).retireThreadCache(cache);
623 storeThreadCache(null);
624 }
625 }
626
627 const cache = self.createThreadCache() orelse return null;
628 cache.owner = threadCacheOwner(self);
629 storeThreadCache(cache);
630 self.registerThreadCacheExit();
631 return cache;
632 }
633
634 fn flushCurrentThreadCache(self: *Self, ret_addr: usize) void {
635 const cache = loadThreadCache() orelse return;
636 if (cache.owner != threadCacheOwner(self)) return;
637 self.flushThreadCache(cache, ret_addr);
638 }
639
640 fn releaseCurrentThreadCache(self: *Self, ret_addr: usize) void {
641 const cache = loadThreadCache() orelse return;
642 if (cache.owner == threadCacheOwner(self)) {
643 self.releaseThreadCache(cache, .unregister, ret_addr);
644 return;
645 }
646 if (cache.storage_owner != threadCacheOwner(self)) return;
647 self.unregisterThreadCacheExit();
648 self.retireThreadCache(cache);
649 storeThreadCache(null);
650 }
651
652 fn flushThreadCache(self: *Self, cache: *ThreadCache, ret_addr: usize) void {
653 for (0..size_class.count) |class_index| {
654 self.drainLocalThreadCacheBin(cache, class_index, std.math.maxInt(usize), ret_addr);
655 }
656 if (cache.owner == threadCacheOwner(self)) cache.owner = null;
657 }
658
659 fn releaseThreadCache(
660 self: *Self,
661 cache: *ThreadCache,
662 mode: ThreadCacheReleaseMode,
663 ret_addr: usize,
664 ) void {
665 self.flushThreadCache(cache, ret_addr);
666 if (mode == .unregister) self.unregisterThreadCacheExit();
667 self.retireThreadCache(cache);
668 if (loadThreadCache() == cache) {
669 storeThreadCache(null);
670 }
671 }
672
673 fn createThreadCache(self: *Self) ?*ThreadCache {
674 self.lockBacking();
675 defer self.unlockBacking();
676
677 const active_limit = self.resolveThreadCacheActiveLimit();
678 if (self.active_thread_cache_count >= active_limit) return null;
679
680 if (self.retained_thread_caches) |cache| {
681 self.retained_thread_caches = cache.next_retained;
682 self.retained_thread_cache_count -= 1;
683 self.active_thread_cache_count += 1;
684 cache.reset(threadCacheOwner(self));
685 return cache;
686 }
687
688 const cache = self.backing_allocator.create(ThreadCache) catch return null;
689 self.active_thread_cache_count += 1;
690 cache.reset(threadCacheOwner(self));
691 return cache;
692 }
693
694 fn resolveThreadCacheActiveLimit(self: *Self) usize {
695 if (self.active_thread_cache_limit == 0) {
696 self.active_thread_cache_limit = defaultThreadCacheActiveLimit();
697 }
698 return self.active_thread_cache_limit;
699 }
700
701 fn retireThreadCache(self: *Self, cache: *ThreadCache) void {
702 assert(cache.owner == null);
703 assert(cache.storage_owner == threadCacheOwner(self));
704 self.lockBacking();
705 defer self.unlockBacking();
706
707 assert(self.active_thread_cache_count > 0);
708 self.active_thread_cache_count -= 1;
709
710 if (self.retained_thread_cache_count < self.config.thread_cache_retention_limit) {
711 cache.next_retained = self.retained_thread_caches;
712 self.retained_thread_caches = cache;
713 self.retained_thread_cache_count += 1;
714 return;
715 }
716
717 cache.storage_owner = null;
718 self.backing_allocator.destroy(cache);
719 }
720
721 fn destroyRetainedThreadCaches(self: *Self) void {
722 var cache = self.retained_thread_caches;
723 while (cache) |current| {
724 const next = current.next_retained;
725 current.storage_owner = null;
726 self.backing_allocator.destroy(current);
727 cache = next;
728 }
729 self.retained_thread_caches = null;
730 self.retained_thread_cache_count = 0;
731 }
732
733 fn registerThreadCacheExit(self: *Self) void {
734 if (!self.config.flush_thread_cache_on_thread_exit) return;
735 const key = ThreadCacheExit.ensureKey() orelse return;
736 _ = sys.thread.setThreadSpecificValue(key, self);
737 }
738
739 fn unregisterThreadCacheExit(self: *Self) void {
740 const key = ThreadCacheExit.currentKey() orelse return;
741 if (sys.thread.getThreadSpecificValue(key)) |value| {
742 if (value != @as(*anyopaque, @ptrCast(self))) return;
743 _ = sys.thread.setThreadSpecificValue(key, null);
744 }
745 }
746
747 fn refillThreadCacheBin(self: *Self, cache: *ThreadCache, class_index: usize, ret_addr: usize) void {
748 self.lockBin(class_index);
749 defer self.unlockBin(class_index);
750
751 const cache_limit = cache_policy.threadClassLimit(class_index);
752 const cached_count = localThreadCacheBinCount(cache, class_index);
753 const refill_count = @min(cache_policy.threadRefillCount(class_index), @as(usize, cache_limit) - cached_count);
754 const bin = &self.bins[class_index];
755 var count: usize = 0;
756 while (count < refill_count) {
757 const ptr = bin.local_transfer.pop() orelse break;
758 assert(pushLocalThreadCacheBin(cache, class_index, ptr, cache_limit));
759 count += 1;
760 }
761 while (count < refill_count) {
762 const reserved = self.reserveSmallBlocksForThreadCache(
763 cache,
764 class_index,
765 refill_count - count,
766 cache_limit,
767 ret_addr,
768 );
769 if (reserved == 0) return;
770 count += reserved;
771 }
772 }
773
774 fn reserveSmallBlocksForThreadCache(
775 self: *Self,
776 cache: *ThreadCache,
777 class_index: usize,
778 limit: usize,
779 cache_limit: u16,
780 ret_addr: usize,
781 ) usize {
782 const bin = &self.bins[class_index];
783 if (bin.partial == null) {
784 const created = self.createPage(class_index, ret_addr) orelse return 0;
785 const page = created.page;
786 bin.addPage(page);
787 if (created.mapped) {
788 self.addStatU64(&self.stats_data.pages_allocated, 1);
789 self.addStatUsize(&self.stats_data.mapped_small_bytes, page.mappedBytes());
790 }
791 }
792
793 const page = bin.partial.?;
794 if (page.live_count == 0) {
795 self.restoreDiscardedPage(page);
796 if (bin.empty_count > 0) {
797 bin.empty_count -= 1;
798 self.subStatUsize(&self.stats_data.retained_empty_pages, 1);
799 }
800 }
801
802 const batch_count = @min(limit, @as(usize, page.free_count));
803 var count: usize = 0;
804 while (count < batch_count) : (count += 1) {
805 const ptr = page.allocate();
806 assert(pushLocalThreadCacheBin(cache, class_index, ptr, cache_limit));
807 }
808 bin.popIfFull(page);
809 return count;
810 }
811
812 fn drainLocalThreadCacheBin(
813 self: *Self,
814 cache: *ThreadCache,
815 class_index: usize,
816 limit: usize,
817 ret_addr: usize,
818 ) void {
819 if (localThreadCacheBinCount(cache, class_index) == 0) return;
820
821 self.lockBin(class_index);
822 defer self.unlockBin(class_index);
823
824 const bin = &self.bins[class_index];
825 var count: usize = 0;
826 while (count < limit) : (count += 1) {
827 const ptr = popLocalThreadCacheBin(cache, class_index) orelse return;
828 self.releaseLocalCachedBlockToCentral(bin, class_index, ptr, ret_addr);
829 }
830 }
831
832 fn releaseLocalCachedBlockToCentral(
833 self: *Self,
834 bin: *Bin,
835 class_index: usize,
836 ptr: [*]u8,
837 ret_addr: usize,
838 ) void {
839 if (bin.local_transfer.push(ptr, cache_policy.transferClassLimit(class_index))) return;
840 self.releaseSmallBlock(class_index, ptr, ret_addr);
841 }
842
843 fn resizeSmall(self: *Self, old_len: usize, new_len: usize) void {
844 if (new_len >= old_len) {
845 self.addStatUsize(&self.stats_data.active_small_bytes, new_len - old_len);
846 } else {
847 self.subStatUsize(&self.stats_data.active_small_bytes, old_len - new_len);
848 }
849 }
850
851 fn resizeLarge(self: *Self, old_len: usize, new_len: usize) void {
852 if (new_len >= old_len) {
853 self.addStatUsize(&self.stats_data.active_large_bytes, new_len - old_len);
854 } else {
855 self.subStatUsize(&self.stats_data.active_large_bytes, old_len - new_len);
856 }
857 }
858
859 fn createPage(self: *Self, class_index: usize, ret_addr: usize) ?PageCreateResult {
860 return switch (self.config.page_provider) {
861 .backing_allocator => blk: {
862 self.lockBacking();
863 defer self.unlockBacking();
864 if (self.popCachedEmptyPage(class_index)) |page| {
865 break :blk .{ .page = page, .mapped = false };
866 }
867 break :blk .{
868 .page = page_mod.createFromBacking(self.backing_allocator, class_index, ret_addr) orelse return null,
869 .mapped = true,
870 };
871 },
872 .os => .{ .page = page_mod.createFromOs(class_index) orelse return null, .mapped = true },
873 };
874 }
875
876 fn destroyPage(self: *Self, page: *Page, ret_addr: usize) void {
877 switch (self.config.page_provider) {
878 .backing_allocator => {
879 self.lockBacking();
880 defer self.unlockBacking();
881 page_mod.destroyInBacking(self.backing_allocator, page, ret_addr);
882 },
883 .os => page_mod.destroyFromOs(page),
884 }
885 }
886
887 fn popCachedEmptyPage(self: *Self, class_index: usize) ?*Page {
888 const page = self.cached_empty_pages orelse return null;
889 self.cached_empty_pages = page.next_cached;
890 self.cached_empty_page_count -= 1;
891 self.subStatUsize(&self.stats_data.retained_empty_pages, 1);
892 const mapping_base = page.mapping_base;
893 const mapping_len = page.mapping_len;
894 Page.init(page, class_index, mapping_base, mapping_len);
895 return page;
896 }
897
898 fn retainCachedEmptyPage(self: *Self, page: *Page) bool {
899 if (self.config.page_provider != .backing_allocator) return false;
900 if (self.config.empty_page_retention_limit == 0) return false;
901 if (self.config.empty_page_reuse_limit == 0) return false;
902
903 self.lockBacking();
904 defer self.unlockBacking();
905
906 if (self.cached_empty_page_count >= self.config.empty_page_reuse_limit) return false;
907
908 page.magic = 0;
909 page.next_all = null;
910 page.previous_all = null;
911 page.next_partial = null;
912 page.next_cached = self.cached_empty_pages;
913 self.cached_empty_pages = page;
914 self.cached_empty_page_count += 1;
915 return true;
916 }
917
918 fn destroyCachedEmptyPages(self: *Self, ret_addr: usize) void {
919 var page = self.cached_empty_pages;
920 while (page) |current| {
921 const next = current.next_cached;
922 switch (self.config.page_provider) {
923 .backing_allocator => page_mod.destroyInBacking(self.backing_allocator, current, ret_addr),
924 .os => page_mod.destroyFromOs(current),
925 }
926 page = next;
927 }
928 self.cached_empty_pages = null;
929 self.cached_empty_page_count = 0;
930 }
931
932 fn addStatU64(self: *Self, counter: *stats_mod.AtomicU64, amount: u64) void {
933 if (!self.config.collect_stats) return;
934 stats_mod.addU64(counter, amount);
935 }
936
937 fn addStatUsize(self: *Self, counter: *stats_mod.AtomicUsize, amount: usize) void {
938 if (!self.config.collect_stats) return;
939 stats_mod.addUsize(counter, amount);
940 }
941
942 fn subStatUsize(self: *Self, counter: *stats_mod.AtomicUsize, amount: usize) void {
943 if (!self.config.collect_stats) return;
944 stats_mod.subUsize(counter, amount);
945 }
946
947 fn useLargeCache(self: *Self) bool {
948 return self.config.large_cache;
949 }
950
951 fn useMediumLargeCache(self: *Self, len: usize, alignment: Alignment) bool {
952 return self.config.large_cache and large_cache_policy.mediumClassFor(len, alignment) != null;
953 }
954
955 fn usesCachedLargeRepresentation(self: *Self, len: usize, alignment: Alignment) bool {
956 if (!self.useLargeCache()) return false;
957 return large_cache_policy.classFor(len, alignment) != null or self.useMediumLargeCache(len, alignment);
958 }
959
960 fn mediumLargeCacheLimit(self: *Self) usize {
961 return @min(self.config.large_cache_limit_bytes, large_cache_policy.medium_default_limit_bytes);
962 }
963
964 fn mediumLargeCacheLocked(self: *Self) ?*large_cache_policy.MediumCache {
965 if (self.medium_large_cache) |cache| return cache;
966 const cache = self.backing_allocator.create(large_cache_policy.MediumCache) catch return null;
967 cache.* = .{};
968 self.medium_large_cache = cache;
969 return cache;
970 }
971
972 fn destroyMediumLargeCache(self: *Self, ret_addr: usize) void {
973 const cache = self.medium_large_cache orelse return;
974 cache.destroyAll(self.backing_allocator, ret_addr);
975 self.backing_allocator.destroy(cache);
976 self.medium_large_cache = null;
977 }
978 };
979
980 const vtable: Allocator.VTable = .{
981 .alloc = allocatorAlloc,
982 .resize = allocatorResize,
983 .remap = allocatorRemap,
984 .free = allocatorFree,
985 };
986
987 fn allocatorAlloc(ctx: *anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8 {
988 const self: *GpAllocator = @ptrCast(@alignCast(ctx));
989 return self.rawAlloc(len, alignment, ret_addr);
990 }
991
992 fn allocatorResize(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool {
993 const self: *GpAllocator = @ptrCast(@alignCast(ctx));
994 return self.rawResize(memory, alignment, new_len, ret_addr);
995 }
996
997 fn allocatorRemap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
998 const self: *GpAllocator = @ptrCast(@alignCast(ctx));
999 return self.rawRemap(memory, alignment, new_len, ret_addr);
1000 }
1001
1002 fn allocatorFree(ctx: *anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void {
1003 const self: *GpAllocator = @ptrCast(@alignCast(ctx));
1004 self.rawFree(memory, alignment, ret_addr);
1005 }
1006
1007 const threaded_test_threads = 4;
1008 const threaded_test_batch = 128;
1009 const threaded_test_rounds = 16;
1010 const thread_cache_remote_test_batch = 128;
1011 const thread_cache_flush_test_batch = 256;
1012 const sys_thread_exit_batch = 256;
1013 const cross_thread_free_batch = 64;
1014
1015 const ThreadedTestWork = struct {
1016 allocator: Allocator,
1017 len: usize,
1018 seed: u8,
1019 };
1020
1021 const ThreadCacheRemoteWork = struct {
1022 heap: *GpAllocator,
1023 allocator: Allocator,
1024 handoff: *std.atomic.Value(u32),
1025 records: *[thread_cache_remote_test_batch][]u8,
1026 };
1027
1028 const ThreadCacheFlushWork = struct {
1029 heap: *GpAllocator,
1030 allocator: Allocator,
1031 records: *[thread_cache_flush_test_batch][]u8,
1032 };
1033
1034 const SysThreadExitWorker = struct {
1035 allocator: Allocator,
1036 records: *[sys_thread_exit_batch][]u8,
1037
1038 fn allocateAndFree(work: *SysThreadExitWorker) void {
1039 for (work.records, 0..) |*record, index| {
1040 const bytes = work.allocator.alloc(u8, 48) catch @panic("allocation failed");
1041 bytes[0] = @truncate(index);
1042 record.* = bytes;
1043 }
1044 for (work.records.*) |record| {
1045 work.allocator.free(record);
1046 }
1047 }
1048 };
1049
1050 const ActiveThreadCacheLimitWorker = struct {
1051 heap: *GpAllocator,
1052 allocator: Allocator,
1053 used_cache: bool = false,
1054
1055 fn allocateAndFree(work: *ActiveThreadCacheLimitWorker) void {
1056 const bytes = work.allocator.alloc(u8, 48) catch @panic("allocation failed");
1057 work.allocator.free(bytes);
1058 work.used_cache = if (loadThreadCache()) |cache| cache.owner == @as(*anyopaque, @ptrCast(work.heap)) else false;
1059 work.heap.flushThreadCacheForCurrentThread();
1060 }
1061 };
1062
1063 const CrossThreadFreeWorker = struct {
1064 heap: *GpAllocator,
1065 records: *[cross_thread_free_batch][]u8,
1066 allocator: Allocator,
1067
1068 fn freeAll(work: *CrossThreadFreeWorker) void {
1069 for (work.records.*) |record| work.allocator.free(record);
1070 work.heap.flushThreadCacheForCurrentThread();
1071 }
1072 };
1073
1074 test "small allocations are aligned and mutable" {
1075 var heap = GpAllocator.init(std.testing.allocator, .{});
1076 defer heap.deinit();
1077 const allocator_instance = heap.allocator();
1078
1079 inline for (.{ 1, 2, 4, 8, 16, 32, 64, 256 }) |alignment| {
1080 const bytes = try allocator_instance.alignedAlloc(u8, .fromByteUnits(alignment), 37);
1081 defer allocator_instance.free(bytes);
1082 try std.testing.expectEqual(@as(usize, 0), @intFromPtr(bytes.ptr) % alignment);
1083 @memset(bytes, 0xa5);
1084 try std.testing.expectEqual(@as(u8, 0xa5), bytes[0]);
1085 }
1086 }
1087
1088 test "small freed blocks are reused while the page remains active" {
1089 var heap = GpAllocator.init(std.testing.allocator, .{});
1090 defer heap.deinit();
1091 const allocator_instance = heap.allocator();
1092
1093 const first = try allocator_instance.alloc(u8, 64);
1094 const second = try allocator_instance.alloc(u8, 64);
1095 allocator_instance.free(first);
1096 const third = try allocator_instance.alloc(u8, 64);
1097 defer allocator_instance.free(third);
1098 defer allocator_instance.free(second);
1099
1100 try std.testing.expectEqual(@intFromPtr(first.ptr), @intFromPtr(third.ptr));
1101 }
1102
1103 test "stats mode stores cache-disabled effective config" {
1104 var heap = GpAllocator.init(std.testing.allocator, .{ .collect_stats = true });
1105 defer heap.deinit();
1106
1107 try std.testing.expect(heap.config.collect_stats);
1108 try std.testing.expect(!heap.config.thread_cache);
1109 try std.testing.expect(!heap.config.large_cache);
1110 }
1111
1112 test "empty small pages are retained by default" {
1113 var heap = GpAllocator.init(std.testing.allocator, .{ .collect_stats = true });
1114 const allocator_instance = heap.allocator();
1115
1116 const first = try allocator_instance.alloc(u8, 16);
1117 allocator_instance.free(first);
1118
1119 var stats = heap.stats();
1120 try std.testing.expectEqual(@as(u64, 1), stats.pages_allocated);
1121 try std.testing.expectEqual(@as(u64, 0), stats.pages_freed);
1122 try std.testing.expectEqual(@as(usize, 1), stats.retained_empty_pages);
1123 try std.testing.expectEqual(page_size, stats.mapped_small_bytes);
1124
1125 const second = try allocator_instance.alloc(u8, 16);
1126 stats = heap.stats();
1127 try std.testing.expectEqual(@intFromPtr(first.ptr), @intFromPtr(second.ptr));
1128 try std.testing.expectEqual(@as(usize, 0), stats.retained_empty_pages);
1129 allocator_instance.free(second);
1130
1131 heap.deinit();
1132 }
1133
1134 test "empty small pages can be released immediately" {
1135 var heap = GpAllocator.init(std.testing.allocator, .{ .empty_page_retention_limit = 0, .collect_stats = true });
1136 const allocator_instance = heap.allocator();
1137
1138 const bytes = try allocator_instance.alloc(u8, 16);
1139 allocator_instance.free(bytes);
1140
1141 const stats = heap.stats();
1142 try std.testing.expectEqual(@as(u64, 1), stats.pages_allocated);
1143 try std.testing.expectEqual(@as(u64, 1), stats.pages_freed);
1144 try std.testing.expectEqual(@as(usize, 0), stats.retained_empty_pages);
1145 try std.testing.expectEqual(@as(usize, 0), stats.mapped_small_bytes);
1146 heap.deinit();
1147 }
1148
1149 test "empty page retention limit releases excess pages" {
1150 var heap = GpAllocator.init(std.testing.allocator, .{
1151 .empty_page_retention_limit = 1,
1152 .empty_page_reuse_limit = 0,
1153 .collect_stats = true,
1154 });
1155 const allocator_instance = heap.allocator();
1156
1157 var blocks: std.ArrayList([]u8) = .empty;
1158 defer blocks.deinit(std.testing.allocator);
1159
1160 var index: usize = 0;
1161 while (index < 9000) : (index += 1) {
1162 try blocks.append(std.testing.allocator, try allocator_instance.alloc(u8, 16));
1163 }
1164 for (blocks.items) |block| allocator_instance.free(block);
1165
1166 const stats = heap.stats();
1167 try std.testing.expect(stats.pages_allocated > 1);
1168 try std.testing.expectEqual(@as(usize, 1), stats.retained_empty_pages);
1169 try std.testing.expectEqual(stats.pages_allocated - 1, stats.pages_freed);
1170
1171 heap.deinit();
1172 }
1173
1174 test "empty page cache reuses excess pages across classes" {
1175 var heap = GpAllocator.init(std.testing.allocator, .{
1176 .empty_page_retention_limit = 1,
1177 .empty_page_reuse_limit = 1,
1178 .collect_stats = true,
1179 });
1180 const allocator_instance = heap.allocator();
1181
1182 var blocks: std.ArrayList([]u8) = .empty;
1183 defer blocks.deinit(std.testing.allocator);
1184
1185 var index: usize = 0;
1186 while (index < 9000) : (index += 1) {
1187 try blocks.append(std.testing.allocator, try allocator_instance.alloc(u8, 16));
1188 }
1189 for (blocks.items) |block| allocator_instance.free(block);
1190
1191 var stats = heap.stats();
1192 try std.testing.expect(stats.pages_allocated > 1);
1193 try std.testing.expectEqual(@as(usize, 2), stats.retained_empty_pages);
1194 try std.testing.expectEqual(stats.pages_allocated - 2, stats.pages_freed);
1195
1196 const pages_allocated = stats.pages_allocated;
1197 const reused = try allocator_instance.alloc(u8, 32);
1198 stats = heap.stats();
1199 try std.testing.expectEqual(pages_allocated, stats.pages_allocated);
1200 try std.testing.expectEqual(@as(usize, 1), stats.retained_empty_pages);
1201 allocator_instance.free(reused);
1202
1203 heap.deinit();
1204 }
1205
1206 test "large allocations bypass small pages" {
1207 var heap = GpAllocator.init(std.testing.allocator, .{ .collect_stats = true });
1208 defer heap.deinit();
1209 const allocator_instance = heap.allocator();
1210
1211 const bytes = try allocator_instance.alloc(u8, max_small_size + 1);
1212 @memset(bytes, 0x7c);
1213 allocator_instance.free(bytes);
1214
1215 const stats = heap.stats();
1216 try std.testing.expectEqual(@as(u64, 1), stats.large_allocations);
1217 try std.testing.expectEqual(@as(u64, 1), stats.large_frees);
1218 try std.testing.expectEqual(@as(u64, 0), stats.pages_allocated);
1219 }
1220
1221 test "realloc preserves data across class changes" {
1222 var heap = GpAllocator.init(std.testing.allocator, .{});
1223 defer heap.deinit();
1224 const allocator_instance = heap.allocator();
1225
1226 var bytes = try allocator_instance.alloc(u8, 24);
1227 @memset(bytes, 0x2a);
1228 bytes = try allocator_instance.realloc(bytes, 200);
1229 defer allocator_instance.free(bytes);
1230
1231 for (bytes[0..24]) |byte| {
1232 try std.testing.expectEqual(@as(u8, 0x2a), byte);
1233 }
1234 }
1235
1236 test "realloc moves small shrinks to the length size class" {
1237 var heap = GpAllocator.init(std.testing.allocator, .{ .collect_stats = true });
1238 const allocator_instance = heap.allocator();
1239
1240 var bytes = try allocator_instance.alloc(u8, 200);
1241 @memset(bytes, 0x5d);
1242 const ptr = bytes.ptr;
1243
1244 bytes = try allocator_instance.realloc(bytes, 24);
1245 try std.testing.expect(@intFromPtr(ptr) != @intFromPtr(bytes.ptr));
1246 try std.testing.expectEqual(@as(usize, 24), heap.stats().active_small_bytes);
1247 for (bytes) |byte| try std.testing.expectEqual(@as(u8, 0x5d), byte);
1248
1249 bytes = try allocator_instance.realloc(bytes, 128);
1250 try std.testing.expectEqual(@as(usize, 128), heap.stats().active_small_bytes);
1251 for (bytes[0..24]) |byte| try std.testing.expectEqual(@as(u8, 0x5d), byte);
1252
1253 allocator_instance.free(bytes);
1254 try std.testing.expectEqual(@as(usize, 0), heap.stats().active_small_bytes);
1255 heap.deinit();
1256 }
1257
1258 test "small resize stays inside the length size class" {
1259 var heap = GpAllocator.init(std.testing.allocator, .{ .flush_thread_cache_on_thread_exit = false });
1260 const allocator_instance = heap.allocator();
1261
1262 var bytes = try allocator_instance.alloc(u8, 200);
1263 const ptr = bytes.ptr;
1264 try std.testing.expect(allocator_instance.resize(bytes, 196));
1265 bytes.len = 196;
1266 try std.testing.expect(allocator_instance.resize(bytes, 224));
1267 bytes.len = 224;
1268 try std.testing.expect(!allocator_instance.resize(bytes, 24));
1269 try std.testing.expect(!allocator_instance.resize(bytes, 225));
1270
1271 bytes = try allocator_instance.realloc(bytes, 24);
1272 try std.testing.expect(@intFromPtr(ptr) != @intFromPtr(bytes.ptr));
1273 allocator_instance.free(bytes);
1274
1275 const reused = try allocator_instance.alloc(u8, 200);
1276 try std.testing.expectEqual(@intFromPtr(ptr), @intFromPtr(reused.ptr));
1277 allocator_instance.free(reused);
1278 heap.deinit();
1279 }
1280
1281 test "thread-safe small allocations run across size classes" {
1282 var heap = GpAllocator.init(std.testing.allocator, .{ .collect_stats = true });
1283 const allocator_instance = heap.allocator();
1284
1285 const sizes = [_]usize{ 16, 48, 256, 2048 };
1286 var work: [threaded_test_threads]ThreadedTestWork = undefined;
1287 var threads: [threaded_test_threads]sys_thread.JoinHandle = undefined;
1288
1289 for (&threads, 0..) |*thread, index| {
1290 work[index] = .{
1291 .allocator = allocator_instance,
1292 .len = sizes[index],
1293 .seed = @truncate(index * 17),
1294 };
1295 thread.* = try sys_thread.spawn(threadedStressWorker, .{&work[index]});
1296 }
1297 for (threads) |thread| thread.join();
1298
1299 const stats = heap.stats();
1300 const expected = threaded_test_threads * threaded_test_batch * threaded_test_rounds;
1301 try std.testing.expectEqual(@as(u64, expected), stats.small_allocations);
1302 try std.testing.expectEqual(@as(u64, expected), stats.small_frees);
1303 try std.testing.expectEqual(@as(usize, 0), stats.active_small_bytes);
1304
1305 heap.deinit();
1306 }
1307
1308 test "thread cache tolerates freeing on another thread" {
1309 var heap = GpAllocator.init(std.testing.allocator, .{});
1310 const allocator_instance = heap.allocator();
1311
1312 var handoff = std.atomic.Value(u32).init(0);
1313 var records: [thread_cache_remote_test_batch][]u8 = undefined;
1314 const work: ThreadCacheRemoteWork = .{
1315 .heap = &heap,
1316 .allocator = allocator_instance,
1317 .handoff = &handoff,
1318 .records = &records,
1319 };
1320 const consumer = try sys_thread.spawn(threadCacheRemoteFreeWorker, .{&work});
1321
1322 for (&records, 0..) |*record, index| {
1323 const bytes = try allocator_instance.alloc(u8, 48);
1324 @memset(bytes, @truncate(index));
1325 record.* = bytes;
1326 }
1327 handoff.store(1, .release);
1328 while (handoff.load(.acquire) != 2) {
1329 std.atomic.spinLoopHint();
1330 }
1331 consumer.join();
1332
1333 heap.deinit();
1334 }
1335
1336 test "worker can explicitly flush its thread cache before exit" {
1337 var heap = GpAllocator.init(std.testing.allocator, .{});
1338 defer heap.deinit();
1339 const allocator_instance = heap.allocator();
1340
1341 var freed_records: [thread_cache_flush_test_batch][]u8 = undefined;
1342 var work: ThreadCacheFlushWork = .{
1343 .heap = &heap,
1344 .allocator = allocator_instance,
1345 .records = &freed_records,
1346 };
1347
1348 const thread = try sys_thread.spawn(threadCacheFlushWorker, .{&work});
1349 thread.join();
1350
1351 var reused_count: usize = 0;
1352 var allocated_records: [thread_cache_flush_test_batch][]u8 = undefined;
1353 for (&allocated_records) |*record| {
1354 const bytes = try allocator_instance.alloc(u8, 48);
1355 record.* = bytes;
1356 if (containsTestPointer(thread_cache_flush_test_batch, &freed_records, bytes.ptr)) reused_count += 1;
1357 }
1358 for (allocated_records) |record| allocator_instance.free(record);
1359
1360 try std.testing.expectEqual(@as(usize, thread_cache_flush_test_batch), reused_count);
1361 }
1362
1363 test "small pages can be provisioned directly from the OS" {
1364 if (!sys.memory.anonymousMappingSupported()) return error.SkipZigTest;
1365
1366 var heap = GpAllocator.init(std.testing.allocator, .{
1367 .empty_page_retention_limit = 0,
1368 .collect_stats = true,
1369 .page_provider = .os,
1370 });
1371 const allocator_instance = heap.allocator();
1372
1373 const bytes = try allocator_instance.alloc(u8, 16);
1374 @memset(bytes, 0x6d);
1375
1376 var stats = heap.stats();
1377 try std.testing.expectEqual(@as(u64, 1), stats.pages_allocated);
1378 try std.testing.expectEqual(page_size, stats.mapped_small_bytes);
1379
1380 allocator_instance.free(bytes);
1381 stats = heap.stats();
1382 try std.testing.expectEqual(@as(u64, 1), stats.pages_freed);
1383 try std.testing.expectEqual(@as(usize, 0), stats.mapped_small_bytes);
1384
1385 heap.deinit();
1386 }
1387
1388 test "retained OS pages can discard unused block memory" {
1389 if (!sys.memory.anonymousMappingSupported()) return error.SkipZigTest;
1390
1391 var heap = GpAllocator.init(std.testing.allocator, .{
1392 .collect_stats = true,
1393 .page_provider = .os,
1394 .retained_empty_page_policy = .discard_unused,
1395 });
1396 const allocator_instance = heap.allocator();
1397
1398 const first = try allocator_instance.alloc(u8, 16);
1399 allocator_instance.free(first);
1400
1401 var stats = heap.stats();
1402 try std.testing.expectEqual(@as(u64, 1), stats.pages_allocated);
1403 try std.testing.expectEqual(@as(u64, 0), stats.pages_freed);
1404 try std.testing.expectEqual(@as(u64, 1), stats.empty_page_discards);
1405 try std.testing.expectEqual(@as(usize, 1), stats.retained_empty_pages);
1406 try std.testing.expect(stats.discarded_small_bytes > 0);
1407 try std.testing.expect(stats.discarded_small_bytes < page_size);
1408
1409 const second = try allocator_instance.alloc(u8, 16);
1410 @memset(second, 0x73);
1411 stats = heap.stats();
1412 try std.testing.expectEqual(@intFromPtr(first.ptr), @intFromPtr(second.ptr));
1413 try std.testing.expectEqual(@as(usize, 0), stats.retained_empty_pages);
1414 try std.testing.expectEqual(@as(usize, 0), stats.discarded_small_bytes);
1415 allocator_instance.free(second);
1416
1417 heap.deinit();
1418 }
1419
1420 test "sys thread exit hook flushes partial local thread cache" {
1421 if (!sys.thread.threadSpecificDestructorsSupported()) return error.SkipZigTest;
1422
1423 var heap = GpAllocator.init(std.testing.allocator, .{});
1424 defer heap.deinit();
1425 const allocator_instance = heap.allocator();
1426
1427 var freed_records: [sys_thread_exit_batch][]u8 = undefined;
1428 var work: SysThreadExitWorker = .{
1429 .allocator = allocator_instance,
1430 .records = &freed_records,
1431 };
1432
1433 const thread = try sys_thread.spawn(SysThreadExitWorker.allocateAndFree, .{&work});
1434 thread.join();
1435
1436 var reused_count: usize = 0;
1437 var allocated_records: [sys_thread_exit_batch][]u8 = undefined;
1438 for (&allocated_records) |*record| {
1439 const bytes = try allocator_instance.alloc(u8, 48);
1440 record.* = bytes;
1441 if (containsTestPointer(sys_thread_exit_batch, &freed_records, bytes.ptr)) reused_count += 1;
1442 }
1443 for (allocated_records) |record| allocator_instance.free(record);
1444
1445 try std.testing.expectEqual(@as(usize, sys_thread_exit_batch), reused_count);
1446 }
1447
1448 fn threadedStressWorker(work: *const ThreadedTestWork) void {
1449 var records: [threaded_test_batch][]u8 = undefined;
1450 var round: usize = 0;
1451 while (round < threaded_test_rounds) : (round += 1) {
1452 for (&records, 0..) |*record, index| {
1453 const bytes = work.allocator.alloc(u8, work.len) catch @panic("allocation failed");
1454 @memset(bytes, @truncate(index + round + work.seed));
1455 record.* = bytes;
1456 }
1457 for (records) |record| {
1458 std.mem.doNotOptimizeAway(record.ptr);
1459 work.allocator.free(record);
1460 }
1461 }
1462 }
1463
1464 fn threadCacheRemoteFreeWorker(work: *const ThreadCacheRemoteWork) void {
1465 while (work.handoff.load(.acquire) == 0) {
1466 std.atomic.spinLoopHint();
1467 }
1468 for (work.records.*) |record| {
1469 std.mem.doNotOptimizeAway(record.ptr);
1470 work.allocator.free(record);
1471 }
1472 work.handoff.store(2, .release);
1473 work.heap.flushThreadCacheForCurrentThread();
1474 }
1475
1476 fn threadCacheFlushWorker(work: *const ThreadCacheFlushWork) void {
1477 for (work.records, 0..) |*record, index| {
1478 const bytes = work.allocator.alloc(u8, 48) catch @panic("allocation failed");
1479 bytes[0] = @truncate(index);
1480 record.* = bytes;
1481 }
1482 for (work.records.*) |record| work.allocator.free(record);
1483 work.heap.flushThreadCacheForCurrentThread();
1484 }
1485
1486 fn containsTestPointer(comptime count: usize, records: *const [count][]u8, ptr: [*]u8) bool {
1487 for (records.*) |record| {
1488 if (record.ptr == ptr) return true;
1489 }
1490 return false;
1491 }
1492
1493 test {
1494 std.testing.refAllDecls(@This());
1495 std.testing.refAllDecls(size_class);
1496 std.testing.refAllDecls(cache_policy);
1497 std.testing.refAllDecls(large_cache_policy);
1498 std.testing.refAllDecls(stats_mod);
1499 }
1500
1501 test "thread cache refill batches small classes more aggressively" {
1502 const small_class = size_class.indexFor(48, .@"1").?;
1503 const medium_class = size_class.indexFor(200, .@"1").?;
1504 const large_class = size_class.indexFor(2048, .@"1").?;
1505
1506 try std.testing.expectEqual(@as(usize, cache_policy.thread_extra_class_refill_max), cache_policy.threadRefillCount(small_class));
1507 try std.testing.expectEqual(@as(usize, 256), cache_policy.threadRefillCount(medium_class));
1508 try std.testing.expectEqual(@as(usize, cache_policy.threadClassLimit(large_class)), cache_policy.threadRefillCount(large_class));
1509 }
1510
1511 test "thread cache drain stages blocks in central transfer cache" {
1512 var heap = GpAllocator.init(std.testing.allocator, .{ .flush_thread_cache_on_thread_exit = false });
1513 const allocator_instance = heap.allocator();
1514 const class_index = comptime size_class.indexFor(48, .@"1").?;
1515 const record_count = comptime cache_policy.transferClassLimit(class_index);
1516
1517 var records: [record_count][]u8 = undefined;
1518 for (&records, 0..) |*record, index| {
1519 const bytes = try allocator_instance.alloc(u8, 48);
1520 bytes[0] = @truncate(index);
1521 record.* = bytes;
1522 }
1523 for (records) |record| allocator_instance.free(record);
1524
1525 heap.flushCurrentThreadCache(@returnAddress());
1526 try std.testing.expectEqual(@as(usize, cache_policy.transferClassLimit(class_index)), heap.bins[class_index].local_transfer.count);
1527
1528 for (records[0..cache_policy.transferClassLimit(class_index)]) |*record| {
1529 record.* = try allocator_instance.alloc(u8, 48);
1530 }
1531 try std.testing.expectEqual(@as(usize, 0), heap.bins[class_index].local_transfer.count);
1532
1533 for (records[0..cache_policy.transferClassLimit(class_index)]) |record| allocator_instance.free(record);
1534 heap.deinit();
1535 }
1536
1537 test "public thread-cache flush releases heap-owned cache storage" {
1538 var heap = GpAllocator.init(std.testing.allocator, .{ .flush_thread_cache_on_thread_exit = false });
1539 const allocator_instance = heap.allocator();
1540
1541 const bytes = try allocator_instance.alloc(u8, 48);
1542 allocator_instance.free(bytes);
1543 try std.testing.expect(loadThreadCache() != null);
1544 try std.testing.expectEqual(@as(usize, 1), heap.active_thread_cache_count);
1545
1546 heap.flushThreadCacheForCurrentThread();
1547 try std.testing.expect(loadThreadCache() == null);
1548 try std.testing.expectEqual(@as(usize, 0), heap.active_thread_cache_count);
1549 try std.testing.expectEqual(@as(usize, 1), heap.retained_thread_cache_count);
1550
1551 const second = try allocator_instance.alloc(u8, 48);
1552 allocator_instance.free(second);
1553 try std.testing.expect(loadThreadCache() != null);
1554 try std.testing.expectEqual(@as(usize, 1), heap.active_thread_cache_count);
1555 try std.testing.expectEqual(@as(usize, 0), heap.retained_thread_cache_count);
1556
1557 heap.deinit();
1558 try std.testing.expect(loadThreadCache() == null);
1559 try std.testing.expectEqual(@as(usize, 0), heap.active_thread_cache_count);
1560 }
1561
1562 test "default active thread-cache limit resolves from CPU count" {
1563 var heap = GpAllocator.init(std.testing.allocator, .{ .flush_thread_cache_on_thread_exit = false });
1564 const allocator_instance = heap.allocator();
1565
1566 try std.testing.expectEqual(@as(usize, 0), heap.active_thread_cache_limit);
1567
1568 const bytes = try allocator_instance.alloc(u8, 48);
1569 allocator_instance.free(bytes);
1570
1571 try std.testing.expectEqual(defaultThreadCacheActiveLimit(), heap.active_thread_cache_limit);
1572 try std.testing.expectEqual(cpuCountThreadCacheActiveLimit(), heap.active_thread_cache_limit);
1573
1574 heap.deinit();
1575 }
1576
1577 test "active thread-cache limit falls back to central bins" {
1578 var heap = GpAllocator.init(std.testing.allocator, .{
1579 .flush_thread_cache_on_thread_exit = false,
1580 .thread_cache_active_limit = 1,
1581 });
1582 const allocator_instance = heap.allocator();
1583
1584 const bytes = try allocator_instance.alloc(u8, 48);
1585 allocator_instance.free(bytes);
1586 try std.testing.expect(loadThreadCache().?.owner == @as(*anyopaque, @ptrCast(&heap)));
1587 try std.testing.expectEqual(@as(usize, 1), heap.active_thread_cache_limit);
1588 try std.testing.expectEqual(@as(usize, 1), heap.active_thread_cache_count);
1589
1590 var work: ActiveThreadCacheLimitWorker = .{
1591 .heap = &heap,
1592 .allocator = allocator_instance,
1593 };
1594 const thread = try sys_thread.spawn(ActiveThreadCacheLimitWorker.allocateAndFree, .{&work});
1595 thread.join();
1596
1597 try std.testing.expect(!work.used_cache);
1598 try std.testing.expectEqual(@as(usize, 1), heap.active_thread_cache_count);
1599
1600 heap.flushThreadCacheForCurrentThread();
1601 try std.testing.expectEqual(@as(usize, 0), heap.active_thread_cache_count);
1602 try std.testing.expectEqual(@as(usize, 1), heap.retained_thread_cache_count);
1603
1604 heap.deinit();
1605 }
1606
1607 test "large cache retains reusable large blocks" {
1608 var heap = GpAllocator.init(std.testing.allocator, .{});
1609 const allocator_instance = heap.allocator();
1610 const len = max_small_size + 512;
1611
1612 const first = try allocator_instance.alloc(u8, len);
1613 const ptr = first.ptr;
1614 allocator_instance.free(first);
1615 try std.testing.expect(heap.large_cache.cached_bytes > 0);
1616
1617 const second = try allocator_instance.alloc(u8, len);
1618 try std.testing.expectEqual(@intFromPtr(ptr), @intFromPtr(second.ptr));
1619 allocator_instance.free(second);
1620 heap.deinit();
1621 }
1622
1623 test "large cache resizes only inside the same large class" {
1624 var heap = GpAllocator.init(std.testing.allocator, .{});
1625 defer heap.deinit();
1626 const allocator_instance = heap.allocator();
1627
1628 const len = max_small_size + 512;
1629 const bytes = try allocator_instance.alloc(u8, len);
1630 try std.testing.expect(allocator_instance.resize(bytes, len + 256));
1631 try std.testing.expect(!allocator_instance.resize(bytes, len + 4096));
1632 allocator_instance.free(bytes);
1633 }
1634
1635 test "large cache preserves actual class when reusing a larger block" {
1636 var heap = GpAllocator.init(std.testing.allocator, .{});
1637 defer heap.deinit();
1638 const allocator_instance = heap.allocator();
1639
1640 const larger_len = max_small_size + 32 * 1024;
1641 const smaller_len = max_small_size + 512;
1642 const first = try allocator_instance.alloc(u8, larger_len);
1643 const ptr = first.ptr;
1644 allocator_instance.free(first);
1645
1646 const second = try allocator_instance.alloc(u8, smaller_len);
1647 try std.testing.expectEqual(@intFromPtr(ptr), @intFromPtr(second.ptr));
1648 try std.testing.expect(allocator_instance.resize(second, larger_len));
1649 const grown: []u8 = second.ptr[0..larger_len];
1650 allocator_instance.free(grown);
1651 }
1652
1653 test "medium large cache retains Barnes-sized page runs" {
1654 var heap = GpAllocator.init(std.testing.allocator, .{});
1655 const allocator_instance = heap.allocator();
1656 const len = 400 * 1024;
1657
1658 const first = try allocator_instance.alloc(u8, len);
1659 const ptr = first.ptr;
1660 allocator_instance.free(first);
1661 try std.testing.expect(heap.medium_large_cache != null);
1662 try std.testing.expect(heap.medium_large_cache.?.cached_bytes > 0);
1663
1664 const second = try allocator_instance.alloc(u8, len);
1665 try std.testing.expectEqual(@intFromPtr(ptr), @intFromPtr(second.ptr));
1666 allocator_instance.free(second);
1667 heap.deinit();
1668 }
1669
1670 test "medium large cache resizes only inside medium classes" {
1671 var heap = GpAllocator.init(std.testing.allocator, .{});
1672 defer heap.deinit();
1673 const allocator_instance = heap.allocator();
1674
1675 const len = 400 * 1024;
1676 const bytes = try allocator_instance.alloc(u8, len);
1677 const resized_len = len + 1024;
1678 try std.testing.expect(allocator_instance.resize(bytes, resized_len));
1679 var resized = bytes;
1680 resized.len = resized_len;
1681 try std.testing.expect(!allocator_instance.resize(resized, large_cache_policy.max_small_cached_size));
1682 try std.testing.expect(!allocator_instance.resize(resized, large_cache_policy.max_medium_cached_size + 1));
1683 allocator_instance.free(resized);
1684 }
1685
1686 test "uncached large remap does not shrink into medium cache representation" {
1687 var heap = GpAllocator.init(std.testing.allocator, .{});
1688 defer heap.deinit();
1689 const allocator_instance = heap.allocator();
1690
1691 const uncached_len = large_cache_policy.max_medium_cached_size + 64 * 1024;
1692 const medium_len = 400 * 1024;
1693 var bytes = try allocator_instance.alloc(u8, uncached_len);
1694 @memset(bytes[0..medium_len], 0xa5);
1695
1696 try std.testing.expect(allocator_instance.remap(bytes, medium_len) == null);
1697 bytes = try allocator_instance.realloc(bytes, medium_len);
1698 defer allocator_instance.free(bytes);
1699 try std.testing.expectEqual(@as(usize, medium_len), bytes.len);
1700 for (bytes[0..1024]) |byte| try std.testing.expectEqual(@as(u8, 0xa5), byte);
1701 }
1702
1703 test "array list owned slice from uncached large capacity frees as medium cache allocation" {
1704 var heap = GpAllocator.init(std.testing.allocator, .{});
1705 defer heap.deinit();
1706 const allocator_instance = heap.allocator();
1707
1708 var list: std.ArrayList(u8) = .empty;
1709 defer list.deinit(allocator_instance);
1710 try list.ensureTotalCapacityPrecise(allocator_instance, large_cache_policy.max_medium_cached_size + 64 * 1024);
1711 try list.appendNTimes(allocator_instance, 0x6e, 400 * 1024);
1712
1713 const owned = try list.toOwnedSlice(allocator_instance);
1714 defer allocator_instance.free(owned);
1715 try std.testing.expectEqual(@as(usize, 400 * 1024), owned.len);
1716 for (owned[0..1024]) |byte| try std.testing.expectEqual(@as(u8, 0x6e), byte);
1717 }
1718
1719 test "cross-thread free drains through the freeing thread cache" {
1720 var heap = GpAllocator.init(std.testing.allocator, .{});
1721 const allocator_instance = heap.allocator();
1722
1723 var records: [cross_thread_free_batch][]u8 = undefined;
1724 for (&records, 0..) |*record, index| {
1725 const bytes = try allocator_instance.alloc(u8, 48);
1726 bytes[0] = @truncate(index);
1727 record.* = bytes;
1728 }
1729
1730 heap.flushCurrentThreadCache(@returnAddress());
1731 const page = page_mod.fromBlock(records[0].ptr);
1732 try std.testing.expectEqual(@as(u16, @intCast(cache_policy.threadRefillCount(page.class_index))), page.live_count);
1733
1734 var work: CrossThreadFreeWorker = .{
1735 .heap = &heap,
1736 .records = &records,
1737 .allocator = allocator_instance,
1738 };
1739 const thread = try sys_thread.spawn(CrossThreadFreeWorker.freeAll, .{&work});
1740 thread.join();
1741
1742 const expected_refill = cache_policy.threadRefillCount(page.class_index);
1743 try std.testing.expectEqual(expected_refill, heap.bins[page.class_index].local_transfer.count);
1744 heap.deinit();
1745 }