A cache for object data.
The purpose of this cache is to speed up resolution of deltas by caching the results of resolving delta objects, while maintaining a maximum cache size to avoid excessive memory usage. If the total size of the objects in the cache exceeds the maximum, the cache will begin evicting the least recently used objects: when resolving delta chains, the most recently used objects will likely be more helpful as they will be further along in the chain (skipping earlier reconstruction steps).
Object data stored in the cache is managed by the cache. It should not be freed by the caller at any point after inserting it into the cache. Any objects remaining in the cache will be freed when the cache itself is freed.
const ObjectCache = structconst ObjectCache = struct {
objects: std.AutoHashMapUnmanaged(u64, CacheEntry) = .empty,
lru_nodes: std.DoublyLinkedList = .{},
lru_nodes_len: usize = 0,
byte_size: usize = 0,
const max_byte_size = 128 * 1024 * 1024; // 128MiB
/// A list of offsets stored in the cache, with the most recently used
/// entries at the end.
const LruListNode = struct {
data: u64,
node: std.DoublyLinkedList.Node,
};
const CacheEntry = struct { object: Object, lru_node: *LruListNode };
fn deinit(cache: *ObjectCache, allocator: Allocator) void {
var object_iterator = cache.objects.iterator();
while (object_iterator.next()) |object| {
allocator.free(object.value_ptr.object.data);
allocator.destroy(object.value_ptr.lru_node);
}
cache.objects.deinit(allocator);
cache.* = undefined;
}
/// Gets an object from the cache, moving it to the most recently used
/// position if it is present.
fn get(cache: *ObjectCache, offset: u64) ?Object {
if (cache.objects.get(offset)) |entry| {
cache.lru_nodes.remove(&entry.lru_node.node);
cache.lru_nodes.append(&entry.lru_node.node);
return entry.object;
} else {
return null;
}
}
/// Puts an object in the cache, possibly evicting older entries if the
/// cache exceeds its maximum size. Note that, although old objects may
/// be evicted, the object just added to the cache with this function
/// will not be evicted before the next call to `put` or `deinit` even if
/// it exceeds the maximum cache size.
fn put(cache: *ObjectCache, allocator: Allocator, offset: u64, object: Object) !void {
const lru_node = try allocator.create(LruListNode);
errdefer allocator.destroy(lru_node);
lru_node.data = offset;
const gop = try cache.objects.getOrPut(allocator, offset);
if (gop.found_existing) {
cache.byte_size -= gop.value_ptr.object.data.len;
cache.lru_nodes.remove(&gop.value_ptr.lru_node.node);
cache.lru_nodes_len -= 1;
allocator.destroy(gop.value_ptr.lru_node);
allocator.free(gop.value_ptr.object.data);
}
gop.value_ptr.* = .{ .object = object, .lru_node = lru_node };
cache.byte_size += object.data.len;
cache.lru_nodes.append(&lru_node.node);
cache.lru_nodes_len += 1;
while (cache.byte_size > max_byte_size and cache.lru_nodes_len > 1) {
// The > 1 check is to make sure that we don't evict the most
// recently added node, even if it by itself happens to exceed the
// maximum size of the cache.
const evict_node: *LruListNode = @alignCast(@fieldParentPtr("node", cache.lru_nodes.popFirst().?));
cache.lru_nodes_len -= 1;
const evict_offset = evict_node.data;
allocator.destroy(evict_node);
const evict_object = cache.objects.get(evict_offset).?.object;
cache.byte_size -= evict_object.data.len;
allocator.free(evict_object.data);
_ = cache.objects.remove(evict_offset);
}
}
}