lib/gpalloc/src/large/medium/cache.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const pointer_cache = @import("../../cache/root.zig");
  3 const class_policy = @import("class.zig");
  4 const model = @import("../root.zig").model;
  5 
  6 const Allocator = std.mem.Allocator;
  7 const Bin = pointer_cache.PointerBin(model.bin_capacity);
  8 const Class = model.Class;
  9 const Entry = model.Entry;
 10 
 11 pub const Cache = struct {
 12     bins: [model.medium_class_count]Bin = @as([model.medium_class_count]Bin, @splat(.{})),
 13     cached_bytes: usize = 0,
 14     eviction_cursor: usize = 0,
 15 
 16     pub fn pop(self: *Cache, class: Class) ?[*]u8 {
 17         const ptr = self.bins[class.index].pop() orelse return null;
 18         self.cached_bytes -= class.size;
 19         return ptr;
 20     }
 21 
 22     pub fn popAtLeast(self: *Cache, class: Class) ?Entry {
 23         var index = class.index;
 24         while (index < self.bins.len) : (index += 1) {
 25             const cached_class = class_policy.classForIndex(index);
 26             const ptr = self.pop(cached_class) orelse continue;
 27             return .{ .class = cached_class, .ptr = ptr };
 28         }
 29         return null;
 30     }
 31 
 32     pub fn push(
 33         self: *Cache,
 34         class: Class,
 35         ptr: [*]u8,
 36         byte_limit: usize,
 37         allocator: Allocator,
 38         ret_addr: usize,
 39     ) bool {
 40         if (class.size > byte_limit) return false;
 41         if (self.bins[class.index].count >= model.bin_capacity) return false;
 42         while (self.cached_bytes + class.size > byte_limit) {
 43             if (!self.evictOne(allocator, ret_addr)) return false;
 44         }
 45         if (!self.bins[class.index].push(ptr, model.bin_capacity)) return false;
 46         self.cached_bytes += class.size;
 47         return true;
 48     }
 49 
 50     pub fn destroyAll(self: *Cache, allocator: Allocator, ret_addr: usize) void {
 51         for (&self.bins, 0..) |*bin, index| {
 52             const class_size = class_policy.sizeForIndex(index);
 53             while (bin.pop()) |ptr| {
 54                 allocator.rawFree(
 55                     ptr[0..class_policy.backingSizeForClassSize(class_size)],
 56                     model.alignment,
 57                     ret_addr,
 58                 );
 59             }
 60         }
 61         self.cached_bytes = 0;
 62         self.eviction_cursor = 0;
 63     }
 64 
 65     fn evictOne(self: *Cache, allocator: Allocator, ret_addr: usize) bool {
 66         var offset: usize = 0;
 67         while (offset < self.bins.len) : (offset += 1) {
 68             const index = (self.eviction_cursor + offset) % self.bins.len;
 69             const class_size = class_policy.sizeForIndex(index);
 70             const ptr = self.bins[index].pop() orelse continue;
 71             self.cached_bytes -= class_size;
 72             self.eviction_cursor = (index + 1) % self.bins.len;
 73             allocator.rawFree(
 74                 ptr[0..class_policy.backingSizeForClassSize(class_size)],
 75                 model.alignment,
 76                 ret_addr,
 77             );
 78             return true;
 79         }
 80         return false;
 81     }
 82 };
 83 
 84 test "medium cache reuses medium classes" {
 85     var cache_state: Cache = .{};
 86     const allocator = std.testing.allocator;
 87     const class = class_policy.classFor(400 * 1024, .@"1").?;
 88     defer cache_state.destroyAll(allocator, @returnAddress());
 89 
 90     const memory = allocator.rawAlloc(
 91         class_policy.backingSize(class),
 92         model.alignment,
 93         @returnAddress(),
 94     ) orelse return error.OutOfMemory;
 95     try std.testing.expect(cache_state.push(
 96         class,
 97         memory,
 98         class.size,
 99         allocator,
100         @returnAddress(),
101     ));
102 
103     const reused = cache_state.popAtLeast(class) orelse return error.MissingCachedBlock;
104     try std.testing.expectEqual(@intFromPtr(memory), @intFromPtr(reused.ptr));
105     allocator.rawFree(reused.ptr[0..class_policy.backingSize(reused.class)], model.alignment, @returnAddress());
106 }
107 
108 test "medium cache can reuse a larger medium class" {
109     var cache_state: Cache = .{};
110     const allocator = std.testing.allocator;
111     const smaller = class_policy.classFor(320 * 1024, .@"1").?;
112     const larger = class_policy.classFor(400 * 1024, .@"1").?;
113     defer cache_state.destroyAll(allocator, @returnAddress());
114 
115     const memory = allocator.rawAlloc(
116         class_policy.backingSize(larger),
117         model.alignment,
118         @returnAddress(),
119     ) orelse return error.OutOfMemory;
120     try std.testing.expect(cache_state.push(
121         larger,
122         memory,
123         larger.size,
124         allocator,
125         @returnAddress(),
126     ));
127 
128     const reused = cache_state.popAtLeast(smaller) orelse return error.MissingCachedBlock;
129     try std.testing.expectEqual(larger.index, reused.class.index);
130     try std.testing.expectEqual(@intFromPtr(memory), @intFromPtr(reused.ptr));
131     allocator.rawFree(reused.ptr[0..class_policy.backingSize(reused.class)], model.alignment, @returnAddress());
132 }