lib/gpalloc/src/page/model.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const config = @import("../root.zig").config;
  3 const size_class = @import("../root.zig").class;
  4 
  5 const assert = std.debug.assert;
  6 const page_size = config.page_size;
  7 
  8 pub const magic: u64 = 0x5441_4c4c_4f43_0001;
  9 
 10 pub const FreeNode = extern struct {
 11     next: ?*FreeNode,
 12 };
 13 
 14 pub const Page = struct {
 15     magic: u64,
 16     class_index: u16,
 17     block_size: u32,
 18     capacity: u16,
 19     live_count: u16,
 20     free_count: u16,
 21     next_unallocated: u16,
 22     block_area_offset: u16,
 23     mapping_base: [*]align(std.heap.page_size_min) u8,
 24     mapping_len: usize,
 25     discarded: bool,
 26     discarded_bytes: u32,
 27     free_list: ?*FreeNode,
 28     next_all: ?*Page,
 29     previous_all: ?*Page,
 30     next_partial: ?*Page,
 31     next_cached: ?*Page,
 32 
 33     pub fn init(
 34         page: *Page,
 35         class_index: usize,
 36         mapping_base: [*]align(std.heap.page_size_min) u8,
 37         mapping_len: usize,
 38     ) void {
 39         const block_size = size_class.size(class_index);
 40         const block_alignment = size_class.blockAlignment(block_size);
 41         const block_area_offset = std.mem.alignForward(usize, @sizeOf(Page), block_alignment);
 42         const capacity = (page_size - block_area_offset) / block_size;
 43         assert(capacity > 0);
 44         assert(capacity <= std.math.maxInt(u16));
 45 
 46         page.* = .{
 47             .magic = magic,
 48             .class_index = @intCast(class_index),
 49             .block_size = @intCast(block_size),
 50             .capacity = @intCast(capacity),
 51             .live_count = 0,
 52             .free_count = @intCast(capacity),
 53             .next_unallocated = 0,
 54             .block_area_offset = @intCast(block_area_offset),
 55             .mapping_base = mapping_base,
 56             .mapping_len = mapping_len,
 57             .discarded = false,
 58             .discarded_bytes = 0,
 59             .free_list = null,
 60             .next_all = null,
 61             .previous_all = null,
 62             .next_partial = null,
 63             .next_cached = null,
 64         };
 65     }
 66 
 67     pub fn blockPtr(page: *Page, index: usize) [*]u8 {
 68         return page.blockArea() + index * page.block_size;
 69     }
 70 
 71     fn blockArea(page: *Page) [*]u8 {
 72         return @as([*]u8, @ptrCast(page)) + page.block_area_offset;
 73     }
 74 
 75     pub fn allocationSlice(page: *Page) []u8 {
 76         return @as([*]u8, @ptrCast(page))[0..page_size];
 77     }
 78 
 79     pub fn mappingSlice(page: *Page) []align(std.heap.page_size_min) u8 {
 80         return page.mapping_base[0..page.mapping_len];
 81     }
 82 
 83     pub fn mappedBytes(page: *Page) usize {
 84         return page.mapping_len;
 85     }
 86 
 87     pub fn discardableSlice(page: *Page) ?[]align(std.heap.page_size_min) u8 {
 88         const start_offset = std.mem.alignForward(usize, page.block_area_offset, std.heap.page_size_min);
 89         if (start_offset >= page_size) return null;
 90         const start_addr = @intFromPtr(page) + start_offset;
 91         const ptr: [*]align(std.heap.page_size_min) u8 = @ptrFromInt(start_addr);
 92         return ptr[0 .. page_size - start_offset];
 93     }
 94 
 95     pub fn allocate(page: *Page) [*]u8 {
 96         const ptr = if (page.free_list) |node| blk: {
 97             page.free_list = node.next;
 98             break :blk @as([*]u8, @ptrCast(node));
 99         } else blk: {
100             assert(page.next_unallocated < page.capacity);
101             const block = page.blockPtr(page.next_unallocated);
102             page.next_unallocated += 1;
103             break :blk block;
104         };
105         page.free_count -= 1;
106         page.live_count += 1;
107         return ptr;
108     }
109 
110     pub fn free(page: *Page, ptr: [*]u8) void {
111         assert(page.magic == magic);
112         assert(page.live_count > 0);
113         const node: *FreeNode = @ptrCast(@alignCast(ptr));
114         node.* = .{ .next = page.free_list };
115         page.free_list = node;
116         page.free_count += 1;
117         page.live_count -= 1;
118     }
119 };
120 
121 test {
122     std.testing.refAllDecls(@This());
123 }
124 
125 test "page allocation materializes untouched blocks lazily" {
126     const class_index = size_class.indexFor(64, .@"1").?;
127     const memory = std.testing.allocator.rawAlloc(page_size, .fromByteUnits(page_size), @returnAddress()) orelse return error.OutOfMemory;
128     defer std.testing.allocator.rawFree(memory[0..page_size], .fromByteUnits(page_size), @returnAddress());
129 
130     const page: *Page = @ptrCast(@alignCast(memory));
131     Page.init(page, class_index, @ptrCast(@alignCast(memory)), page_size);
132 
133     try std.testing.expectEqual(@as(?*FreeNode, null), page.free_list);
134     try std.testing.expectEqual(@as(u16, 0), page.next_unallocated);
135 
136     const first = page.allocate();
137     const second = page.allocate();
138     try std.testing.expectEqual(@as(u16, 2), page.next_unallocated);
139 
140     page.free(first);
141     const reused = page.allocate();
142     try std.testing.expectEqual(@intFromPtr(first), @intFromPtr(reused));
143     try std.testing.expectEqual(@as(u16, 2), page.next_unallocated);
144 
145     const third = page.allocate();
146     try std.testing.expectEqual(@intFromPtr(page.blockPtr(2)), @intFromPtr(third));
147     try std.testing.expectEqual(@as(u16, 3), page.next_unallocated);
148     try std.testing.expectEqual(@as(u16, 3), page.live_count);
149     try std.testing.expectEqual(page.capacity - 3, page.free_count);
150     try std.testing.expect(@intFromPtr(third) != @intFromPtr(second));
151 }