diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/zisp/gc/meta_alloc.zig | 201 |
1 files changed, 103 insertions, 98 deletions
diff --git a/src/zisp/gc/meta_alloc.zig b/src/zisp/gc/meta_alloc.zig index 5e58b7b..8e22abe 100644 --- a/src/zisp/gc/meta_alloc.zig +++ b/src/zisp/gc/meta_alloc.zig @@ -1,8 +1,8 @@ // // = Meta Allocator = // -// Please read the full documentation of the allocation strategy to understand -// what's going on here at a high level: /doc/0/A-meta_alloc.html +// Read the full documentation of the allocation strategy to understand what's +// going on here at a high level: Chapter 0, Appendix A // // That said, a few quick implementation notes follow. // @@ -36,8 +36,8 @@ // { // next_head_idx: u32, // extra_idx_count: u32, -// pad_to_64_bytes: [7]u64, -// extra_idx_array: [32]u32, +// pad_to_64_bytes: [15]u32, +// extra_idx_array: [16]u32, // } // // So, it's not a typical free-list where each node simply points to the next @@ -64,11 +64,26 @@ const std = @import("std"); +/// The units of memory in which slabs are addressed. +const Unit = u64; + +/// Integer that can hold a slab/unit index, plus one overflow bit. +const UnitIdx = u32; + +/// Length of each slab, as in Unit count. +const SLAB_LEN: u32 = 1 << 31; + +/// A slab of memory. +const Slab = [SLAB_LEN]Unit; + +/// A pointer to a slot of allocated memory; N units depenging on size class. +const SlotPtr = [*]Unit; + /// Size classes. -const SIZES: [16]comptime_int = .{ +const SIZES: [16]usize = .{ // Important: Ensure the smallest size class is inherently immune to false - // sharing, and no smaller than: 64 + 4 * ( RESERVE_MAX / 2 ) many bytes. - // That's 192 bytes assuming RESERVE_MAX = 64 (see below). + // sharing, and no smaller than: 64 + @sizeOf(UnitIdx) * ( FSC_MAX / 2 ). + // That's 128 bytes assuming FSC_MAX = 32 (see below). 256, 512, 1024, @@ -87,34 +102,24 @@ const SIZES: [16]comptime_int = .{ 1024 * 1024 * 8, }; -/// Gets the index [0,15] of a size class, from the size value, returning a +/// Gets the index 0 to 15 of a size class, from the size value, returning a /// value greater than 15 if the size is beyond the largest size class. inline fn getSizeClassIndex(size: usize) u8 { // Can't handle size that isn't power of two or below smallest size class. - std.debug.assert(@popCount(size) == 1); - std.debug.assert(size >= SIZES[0]); + if (@popCount(size) != 1) @panic("Only powers of two supported."); + if (size < SIZES[0]) @panic("Can't alloc below smallest size."); - const min: usize = SIZES[0]; - return @ctz(size >> @ctz(min)); + return @ctz(size >> @ctz(SIZES[0])); } -/// The length of each slab in 8-byte units. -const SLAB_LEN: u32 = 0x8000_0000; - -// For convenience: -const Unit = u64; -const SlotPtr = [*]Unit; -const Slab = [SLAB_LEN]Unit; -const Slabs = [SIZES.len]Slab; - /// Pointer to start of all 16 slabs as a contiguous vmem block. -var slabs: *Slabs = undefined; +var slabs: *[SIZES.len]Slab = undefined; /// Free-list head pointer with ABA counter. const FlHead = packed struct(u64) { // Putting aba first leads to slightly better codegen. aba: u32, - idx: u32, + idx: UnitIdx, }; /// Global shared metadata per slab / size class. @@ -125,40 +130,45 @@ const SlabInfo = struct { /// used to mean NULL, since it's an invalid slab index. free_list: FlHead = .{ .aba = 0, .idx = SLAB_LEN }, /// Global slab watermark: Start address of unused vmem, as 8-byte index. - watermark: u32 = 0, + watermark: UnitIdx = 0, }; /// Global shared metadata per slab / size class. var slab_infos: [SIZES.len]SlabInfo = @splat(.{}); -/// Maximum number of slots reserved for a thread, both when bumping the global -/// watermark, and by holding entries in its free slot cache. Note that this -/// means the real number of slots currently reserved by each thread may reach -/// twice this number. (Minus one, since the global watermark is only bumped -/// when an allocation is requested, so one slot is used immediately.) -const RESERVE_MAX = 64; - -/// Given a size class index 0 to 15, returns the number of slots that threads -/// should keep in reserve for that size class. This starts at RESERVE_MAX for -/// the smallest class, and is halved every four size classes. This number is -/// used both for deciding how much to bump the global watermark of a slab to -/// reserve memory for a thread, and to determine the maximum count of entries -/// stored in the thread's free slot cache for that size class. +/// Maximum number of slots reserved by a thread when bumping a slab watermark. +/// Halved after every two size classes, so make sure it's >= 128. +const RESERVE_MAX: u32 = 512; + +/// Maximum number of free slot cache entries before half of them are flushed. +/// Halved after every four size classes, so make sure it's >= 8. +const FSC_MAX: u32 = 32; + +/// Given a size class index 0 to 15, returns the number of slots that a thread +/// should reserve every time it needs to bump the global watermark. Starts at +/// RESERVE_MAX and is halved after every two size classes. inline fn reserveCountForSizeClassIndex(sci: u8) u32 { - return @as(u8, RESERVE_MAX) >> @intCast(sci / 4); + return RESERVE_MAX >> @intCast(sci / 2); +} + +/// Given a size class index 0 to 15, returns the maximum number of entries in +/// the free slot cache of a thread before half of them are flushed. Starts at +/// FSC_MAX and is halved after every four size classes. +inline fn maxFscCountForSizeClassIndex(sci: u8) u32 { + return FSC_MAX >> @intCast(sci / 4); } /// Thread-local metadata per slab / size class. const TlSlabInfo = struct { /// Free slot cache; align to cache line to prevent false sharing and for /// possible SIMD related benefits. - fc: [RESERVE_MAX]u32 align(std.atomic.cache_line) = @splat(0), + fsc: [FSC_MAX]UnitIdx align(std.atomic.cache_line) = @splat(0), /// Current count of entries in free slot cache. - fc_count: u32 = 0, + fsc_count: u32 = 0, /// Start point of memory reserved for this thread. - wm_lo: u32 = 0, + wm_lo: UnitIdx = 0, /// End point of memory reserved for this thread. - wm_hi: u32 = 0, + wm_hi: UnitIdx = 0, }; /// Thread-local metadata per slab / size class. @@ -213,14 +223,14 @@ fn alloc_size_class(sci: u8, size: usize) SlotPtr { const slab: *Slab = &slabs[sci]; // Reuse from thread-local free cache. - if (tl.fc_count > 0) { - tl.fc_count -= 1; - const idx = tl.fc[tl.fc_count]; + if (tl.fsc_count > 0) { + tl.fsc_count -= 1; + const idx = tl.fsc[tl.fsc_count]; return slab[idx..].ptr; } // The size in 8-byte slab/watermark units. - const wm_units: u32 = @intCast(size / 8); + const wm_units: UnitIdx = @intCast(size / 8); // Use part of the reserved memory for this thread. if (tl.wm_lo < tl.wm_hi) { @@ -243,7 +253,7 @@ fn alloc_from_fl( tl: *TlSlabInfo, ) ?SlotPtr { var ptr: SlotPtr = undefined; - var arr: [*]u32 = undefined; + var arr: [*]UnitIdx = undefined; var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire); while (true) : (std.atomic.spinLoopHint()) { @@ -255,7 +265,7 @@ fn alloc_from_fl( // Load this atomically since it's still globally accessible memory; // unordered is fine since we discard it if the following CAS fails. - const next_head = @atomicLoad(u32, &arr[0], .unordered); + const next_head = @atomicLoad(UnitIdx, &arr[0], .unordered); fl_head = @cmpxchgWeak( FlHead, @@ -268,11 +278,11 @@ fn alloc_from_fl( } // Now detached from global; no need for atomics anymore. - tl.fc_count = arr[1]; + tl.fsc_count = arr[1]; - // We can safely copy more than needed since we set fc_count. - const half_max = RESERVE_MAX / 2; - @memcpy(tl.fc[0..half_max], arr[8 .. 8 + half_max]); + // We can safely copy more than needed since we set fsc_count. + const half_max = FSC_MAX / 2; + @memcpy(tl.fsc[0..half_max], arr[16 .. 16 + half_max]); return ptr; } @@ -282,13 +292,13 @@ fn alloc_fresh( slab: *Slab, info: *SlabInfo, tl: *TlSlabInfo, - wm_units: u32, + wm_units: UnitIdx, res_n: u32, ) SlotPtr { // Have to use fresh memory from the top of the slab; bump it by a chunk, // atomically, to reserve memory for this thread. const bump = res_n * wm_units; - const old_wm = @atomicRmw(u32, &info.watermark, .Add, bump, .monotonic); + const old_wm = @atomicRmw(UnitIdx, &info.watermark, .Add, bump, .monotonic); const new_wm = old_wm + bump; // Check only if the old WM was already overflown; chunk count is such that @@ -308,43 +318,43 @@ fn free_size_class(sci: u8, ptr: SlotPtr) void { const tl = &tl_slab_infos[sci]; const slab: *Slab = &slabs[sci]; - const idx: u32 = @intCast(ptr - slab); - const res_n = reserveCountForSizeClassIndex(sci); + const idx: UnitIdx = @intCast(ptr - slab); + const fsc_lim = maxFscCountForSizeClassIndex(sci); - // Still some space in the local free slot cache. - if (tl.fc_count != res_n) { - tl.fc[tl.fc_count] = idx; - tl.fc_count += 1; + // Still some space in the local free slot cache? + if (tl.fsc_count != fsc_lim) { + tl.fsc[tl.fsc_count] = idx; + tl.fsc_count += 1; return; } // Local cache full; need to flush some to global free-list. const info = &slab_infos[sci]; - free_into_fl(info, tl, ptr, idx, res_n / 2); + free_into_fl(info, tl, ptr, idx, fsc_lim / 2); } fn free_into_fl( info: *SlabInfo, tl: *TlSlabInfo, ptr: SlotPtr, - idx: u32, + idx: UnitIdx, n: u32, ) void { // Note: n = 0 is valid and must work. - std.debug.assert(n <= RESERVE_MAX / 2); + std.debug.assert(n <= FSC_MAX / 2); - const arr: [*]u32 = @ptrCast(ptr); - const split = tl.fc_count - n; + const arr: [*]UnitIdx = @ptrCast(ptr); + const split = tl.fsc_count - n; - tl.fc_count = split; + tl.fsc_count = split; // No need for atomic stores; we own this memory exclusively right now, // unless another thread calls free() on the same slot which is a bug. arr[1] = n; // Safe to copy more than needed. - const max = RESERVE_MAX / 2; - @memcpy(arr[8 .. 8 + max], tl.fc[split .. split + max]); + const max = FSC_MAX / 2; + @memcpy(arr[16 .. 16 + max], tl.fsc[split .. split + max]); // Now atomically announce the new free-list head to global visibility. var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire); @@ -368,47 +378,42 @@ fn free_into_fl( /// this function before terminating, or else memory is leaked. export fn flush_thread_reserves() void { var sci: u8 = 0; - var wm_units: u32 = SIZES[0] / 8; + var units: UnitIdx = SIZES[0] / 8; while (sci < SIZES.len) : ({ sci += 1; - wm_units *= 2; + units *= 2; }) { const info = &slab_infos[sci]; const tl = &tl_slab_infos[sci]; const slab: *Slab = &slabs[sci]; + const fsc_lim = maxFscCountForSizeClassIndex(sci); - flush_thread_fc(info, tl, slab); + const chunk_max = fsc_lim / 2; + + // Up to two iterations to flush the entire fsc. + while (tl.fsc_count != 0) { + flush_fsc(info, tl, slab, @min(chunk_max, tl.fsc_count)); + } // Now turn slots between wm_lo and wm_hi into free-list entries; most - // easily done by writing them into tl.fc and reusing the function to - // flush the fc entries. - var i: u32 = 0; - var wm = tl.wm_lo; - while (wm < tl.wm_hi) : ({ - i += 1; - wm += wm_units; - }) { - tl.fc[i] = wm; + // easily done by writing them into tl.fsc and reusing the function to + // flush the fsc entries every time chunk_max + 1 is hit. + while (tl.wm_lo < tl.wm_hi) : (tl.wm_lo += units) { + if (tl.fsc_count > chunk_max) { + flush_fsc(info, tl, slab, chunk_max); + } + tl.fsc[tl.fsc_count] = tl.wm_lo; + tl.fsc_count += 1; + } + if (tl.fsc_count != 0) { + flush_fsc(info, tl, slab, tl.fsc_count - 1); } - tl.fc_count = i; - tl.wm_lo = wm; - flush_thread_fc(info, tl, slab); } } -fn flush_thread_fc(info: *SlabInfo, tl: *TlSlabInfo, slab: *Slab) void { - // Do in two steps if there's too many for a single free-list node. - if (tl.fc_count > RESERVE_MAX / 2) { - tl.fc_count -= 1; - const idx = tl.fc[tl.fc_count]; - const ptr: SlotPtr = slab[idx..].ptr; - free_into_fl(info, tl, ptr, idx, RESERVE_MAX / 2); - } - if (tl.fc_count != 0) { - tl.fc_count -= 1; - const idx = tl.fc[tl.fc_count]; - const ptr: SlotPtr = slab[idx..].ptr; - // Remaining fl_count may be 0; that's fine. - free_into_fl(info, tl, ptr, idx, tl.fc_count); - } +fn flush_fsc(info: *SlabInfo, tl: *TlSlabInfo, slab: *Slab, extras: u32) void { + tl.fsc_count -= 1; + const idx = tl.fsc[tl.fsc_count]; + const ptr: SlotPtr = slab[idx..].ptr; + free_into_fl(info, tl, ptr, idx, extras); } |