lib/gpalloc/src/large/cache.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const pointer_cache = @import("../cache/root.zig");
3 const size_class = @import("../root.zig").class;
4 const class_policy = @import("class.zig");
5 const model = @import("model.zig");
6
7 const Allocator = std.mem.Allocator;
8 const Bin = pointer_cache.PointerBin(model.bin_capacity);
9 const Class = model.Class;
10 const Entry = model.Entry;
11
12 pub const Cache = struct {
13 bins: [model.class_count]Bin = @as([model.class_count]Bin, @splat(.{})),
14 cached_bytes: usize = 0,
15 eviction_cursor: usize = 0,
16
17 pub fn pop(self: *Cache, class: Class) ?[*]u8 {
18 const ptr = self.bins[class.index].pop() orelse return null;
19 self.cached_bytes -= class.size;
20 return ptr;
21 }
22
23 pub fn popAtLeast(self: *Cache, class: Class) ?Entry {
24 const end_index = if (class.index < model.small_class_count)
25 model.small_class_count
26 else
27 self.bins.len;
28 var index = class.index;
29 while (index < end_index) : (index += 1) {
30 const cached_class = class_policy.classForIndex(index);
31 const ptr = self.pop(cached_class) orelse continue;
32 return .{ .class = cached_class, .ptr = ptr };
33 }
34 return null;
35 }
36
37 pub fn push(
38 self: *Cache,
39 class: Class,
40 ptr: [*]u8,
41 byte_limit: usize,
42 allocator: Allocator,
43 ret_addr: usize,
44 ) bool {
45 if (class.size > byte_limit) return false;
46 if (self.bins[class.index].count >= model.bin_capacity) return false;
47 while (self.cached_bytes + class.size > byte_limit) {
48 if (!self.evictOne(allocator, ret_addr)) return false;
49 }
50 if (!self.bins[class.index].push(ptr, model.bin_capacity)) return false;
51 self.cached_bytes += class.size;
52 return true;
53 }
54
55 pub fn destroyAll(self: *Cache, allocator: Allocator, ret_addr: usize) void {
56 for (&self.bins, 0..) |*bin, index| {
57 const class_size = class_policy.sizeForIndex(index);
58 while (bin.pop()) |ptr| {
59 allocator.rawFree(ptr[0..class_policy.backingSizeForClassSize(class_size)], model.alignment, ret_addr);
60 }
61 }
62 self.cached_bytes = 0;
63 self.eviction_cursor = 0;
64 }
65
66 fn evictOne(self: *Cache, allocator: Allocator, ret_addr: usize) bool {
67 var offset: usize = 0;
68 while (offset < self.bins.len) : (offset += 1) {
69 const index = (self.eviction_cursor + offset) % self.bins.len;
70 const class_size = class_policy.sizeForIndex(index);
71 const ptr = self.bins[index].pop() orelse continue;
72 self.cached_bytes -= class_size;
73 self.eviction_cursor = (index + 1) % self.bins.len;
74 allocator.rawFree(
75 ptr[0..class_policy.backingSizeForClassSize(class_size)],
76 model.alignment,
77 ret_addr,
78 );
79 return true;
80 }
81 return false;
82 }
83 };
84
85 test "large cache admits newer classes by evicting cached blocks" {
86 var cache_state: Cache = .{};
87 const allocator = std.testing.allocator;
88 const first = class_policy.classFor(size_class.max_small_size + 1, .@"1").?;
89 const second = class_policy.classFor(first.size + 1, .@"1").?;
90
91 const first_memory = allocator.rawAlloc(
92 class_policy.backingSize(first),
93 model.alignment,
94 @returnAddress(),
95 ) orelse return error.OutOfMemory;
96 try std.testing.expect(cache_state.push(
97 first,
98 first_memory,
99 first.size,
100 allocator,
101 @returnAddress(),
102 ));
103 try std.testing.expectEqual(first.size, cache_state.cached_bytes);
104
105 const second_memory = allocator.rawAlloc(
106 class_policy.backingSize(second),
107 model.alignment,
108 @returnAddress(),
109 ) orelse return error.OutOfMemory;
110 try std.testing.expect(cache_state.push(
111 second,
112 second_memory,
113 second.size,
114 allocator,
115 @returnAddress(),
116 ));
117 try std.testing.expectEqual(second.size, cache_state.cached_bytes);
118 try std.testing.expect(cache_state.pop(first) == null);
119
120 const reused = cache_state.pop(second) orelse return error.MissingCachedBlock;
121 try std.testing.expectEqual(@intFromPtr(second_memory), @intFromPtr(reused));
122 allocator.rawFree(reused[0..class_policy.backingSize(second)], model.alignment, @returnAddress());
123 }
124
125 test "large cache reuses multi-megabyte blocks" {
126 var cache_state: Cache = .{};
127 const allocator = std.testing.allocator;
128 const class = class_policy.classFor(5 * 1024 * 1024 + 1, .@"1").?;
129
130 try std.testing.expectEqual(@as(usize, 8 * 1024 * 1024), class.size);
131 const memory = allocator.rawAlloc(
132 class_policy.backingSize(class),
133 model.alignment,
134 @returnAddress(),
135 ) orelse return error.OutOfMemory;
136 try std.testing.expect(cache_state.push(
137 class,
138 memory,
139 class.size,
140 allocator,
141 @returnAddress(),
142 ));
143
144 const reused = cache_state.popAtLeast(class) orelse return error.MissingCachedBlock;
145 try std.testing.expectEqual(class.index, reused.class.index);
146 try std.testing.expectEqual(@intFromPtr(memory), @intFromPtr(reused.ptr));
147 allocator.rawFree(reused.ptr[0..class_policy.backingSize(reused.class)], model.alignment, @returnAddress());
148 }
149
150 test "large cache does not reuse huge blocks for fine large requests" {
151 var cache_state: Cache = .{};
152 const allocator = std.testing.allocator;
153 const fine = class_policy.classFor(size_class.max_small_size + 512, .@"1").?;
154 const huge = class_policy.classFor(17 * 1024 * 1024 + 1, .@"1").?;
155
156 const memory = allocator.rawAlloc(
157 class_policy.backingSize(huge),
158 model.alignment,
159 @returnAddress(),
160 ) orelse return error.OutOfMemory;
161 try std.testing.expect(cache_state.push(
162 huge,
163 memory,
164 huge.size,
165 allocator,
166 @returnAddress(),
167 ));
168
169 try std.testing.expect(cache_state.popAtLeast(fine) == null);
170 const reused = cache_state.popAtLeast(huge) orelse return error.MissingCachedBlock;
171 allocator.rawFree(reused.ptr[0..class_policy.backingSize(reused.class)], model.alignment, @returnAddress());
172 }
173
174 test "large cache can reuse a larger cached class" {
175 var cache_state: Cache = .{};
176 const allocator = std.testing.allocator;
177 const smaller = class_policy.classFor(5 * 1024 * 1024 + 1, .@"1").?;
178 const larger = class_policy.classFor(17 * 1024 * 1024 + 1, .@"1").?;
179
180 const memory = allocator.rawAlloc(
181 class_policy.backingSize(larger),
182 model.alignment,
183 @returnAddress(),
184 ) orelse return error.OutOfMemory;
185 try std.testing.expect(cache_state.push(
186 larger,
187 memory,
188 larger.size,
189 allocator,
190 @returnAddress(),
191 ));
192
193 const reused = cache_state.popAtLeast(smaller) orelse return error.MissingCachedBlock;
194 try std.testing.expect(reused.class.size >= smaller.size);
195 try std.testing.expectEqual(larger.index, reused.class.index);
196 try std.testing.expectEqual(@intFromPtr(memory), @intFromPtr(reused.ptr));
197 allocator.rawFree(reused.ptr[0..class_policy.backingSize(reused.class)], model.alignment, @returnAddress());
198 }