Problem
ContentCache is a bounded-probe (4-slot window) table, but three paths violate the window invariant (src/hot_cache.zig):
- Overflow eviction strands the new entry. When all 4 window slots are occupied by other keys,
putImpl evicts via clockEvict() — a global CLOCK hand that returns a slot anywhere in the table (L161). The new entry is written there, but get only probes the key's own 4-slot window: the entry can never be found. Its bytes (file contents, up to 64MB apiece) sit stranded in the cache while every lookup for that key misses and re-reads from disk. Under collision pressure the cache degrades to a byte-hoarding miss machine.
- Holes break lookup.
get/remove early-break on !present and key_hash == 0 (L107, L195). A remove resets a slot to empty_slot, so an in-window entry stored past the removed slot becomes unreachable — stranded bytes + permanent misses until eviction happens to reap it.
- Duplicate keys.
putImpl takes the first empty slot in the window before checking the rest of it, so re-putting a key that lives past a hole inserts a second copy: double memory for the same path, inflated count_, and a stale shadow that serves old bytes if the front copy is ever removed.
All three are memory-hoarding/correctness bugs in the layer that fronts every content read.
Failing Test
test_core.zig — fails on current release tip (scenario 1 trips first; 2 and 3 are also red individually):
test "issue-584: ContentCache probe-window — overflow inserts, holes, and duplicate keys" {
const fnvBase = struct {
fn base(key: []const u8, cap: u32) u32 {
var h: u64 = 14695981039346656037;
for (key) |b| {
h ^= b;
h *%= 1099511628211;
}
if (h == 0) h = 1;
return @as(u32, @truncate(h)) % cap;
}
}.base;
// Collect 5 keys sharing one probe-window base in [1, 60].
var bufs: [5][16]u8 = undefined;
var lens: [5]usize = undefined;
var nkeys: usize = 0;
var counts = [_]u8{0} ** 64;
var pick: u32 = 0;
var i: usize = 0;
while (i < 4096) : (i += 1) {
var tmp: [16]u8 = undefined;
const k = std.fmt.bufPrint(&tmp, "k{d}", .{i}) catch unreachable;
const b = fnvBase(k, 64);
if (b < 1 or b > 60) continue;
counts[b] += 1;
if (counts[b] >= 5) {
pick = b;
break;
}
}
try testing.expect(pick != 0);
i = 0;
while (i < 4096 and nkeys < 5) : (i += 1) {
var tmp: [16]u8 = undefined;
const k = std.fmt.bufPrint(&tmp, "k{d}", .{i}) catch unreachable;
if (fnvBase(k, 64) == pick) {
@memcpy(bufs[nkeys][0..k.len], k);
lens[nkeys] = k.len;
nkeys += 1;
}
}
try testing.expectEqual(@as(usize, 5), nkeys);
const k0 = bufs[0][0..lens[0]];
const k1 = bufs[1][0..lens[1]];
const k2 = bufs[2][0..lens[2]];
const k3 = bufs[3][0..lens[3]];
const k4 = bufs[4][0..lens[4]];
// 1) Overflow insert must stay retrievable from its own probe window.
{
var cache = try ContentCache.initAlloc(testing.allocator, 64);
defer cache.deinit();
try cache.put(k0, "v0");
try cache.put(k1, "v1");
try cache.put(k2, "v2");
try cache.put(k3, "v3");
try cache.put(k4, "v4"); // window full -> eviction path
try testing.expect(cache.get(k4) != null);
}
// 2) A hole left by remove() must not hide in-window entries behind it.
// 3) Re-putting such an entry must not create a duplicate copy.
{
var cache = try ContentCache.initAlloc(testing.allocator, 64);
defer cache.deinit();
try cache.put(k0, "v0");
try cache.put(k1, "v1");
try cache.put(k2, "v2");
cache.remove(k1); // hole between k0 and k2
try testing.expect(cache.get(k2) != null);
try cache.put(k2, "v2b");
try testing.expectEqual(@as(u32, 2), cache.len());
}
}Expected
Every entry the cache holds is retrievable via its probe window; a key occupies at most one slot; eviction frees the victim's bytes and the new entry replaces it in-window.
Fix
Keep eviction inside the probe window: second-chance over the 4 window slots (first !ref_bit wins; if all are hot, clear them and take the base slot), free the victim, insert in place. Make putImpl scan the whole window for an existing key before taking the first empty slot, and drop the key_hash == 0 early-breaks in get/remove (4 contiguous probes are cheap). The global clockEvict/hand machinery becomes dead and goes away.
Problem
ContentCacheis a bounded-probe (4-slot window) table, but three paths violate the window invariant (src/hot_cache.zig):putImplevicts viaclockEvict()— a global CLOCK hand that returns a slot anywhere in the table (L161). The new entry is written there, butgetonly probes the key's own 4-slot window: the entry can never be found. Its bytes (file contents, up to 64MB apiece) sit stranded in the cache while every lookup for that key misses and re-reads from disk. Under collision pressure the cache degrades to a byte-hoarding miss machine.get/removeearly-break on!present and key_hash == 0(L107, L195). Aremoveresets a slot toempty_slot, so an in-window entry stored past the removed slot becomes unreachable — stranded bytes + permanent misses until eviction happens to reap it.putImpltakes the first empty slot in the window before checking the rest of it, so re-putting a key that lives past a hole inserts a second copy: double memory for the same path, inflatedcount_, and a stale shadow that serves old bytes if the front copy is ever removed.All three are memory-hoarding/correctness bugs in the layer that fronts every content read.
Failing Test
test_core.zig— fails on current release tip (scenario 1 trips first; 2 and 3 are also red individually):Expected
Every entry the cache holds is retrievable via its probe window; a key occupies at most one slot; eviction frees the victim's bytes and the new entry replaces it in-window.
Fix
Keep eviction inside the probe window: second-chance over the 4 window slots (first
!ref_bitwins; if all are hot, clear them and take the base slot), free the victim, insert in place. MakeputImplscan the whole window for an existing key before taking the first empty slot, and drop thekey_hash == 0early-breaks inget/remove(4 contiguous probes are cheap). The globalclockEvict/handmachinery becomes dead and goes away.