Language: Zig · Versions: Zig 0.13.0
The problem
In Zig, std.AutoHashMap(u32, u32).getOrPut returns a GetOrPutResult containing value_ptr: *V pointing directly into the map's backing storage. When recursively or nestedly computing a value (e.g. memoized Fibonacci or graph traversal) and assigning directly to gop.value_ptr.* = compute(map, n - 1), the inner call to compute inserts into map, triggering a rehash/grow that invalidates gop.value_ptr before the assignment completes!
Minimal example
const std = @import("std");
fn fib(map: *std.AutoHashMap(u64, u64), n: u64) !u64 {
if (n <= 1) return n;
const gop = try map.getOrPut(n);
if (!gop.found_existing) {
// BUG: gop.value_ptr is evaluated/held while fib(map, n - 1) mutates & rehashes `map`!
gop.value_ptr.* = (try fib(map, n - 1)) + (try fib(map, n - 2));
}
return gop.value_ptr.*;
}
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
var map = std.AutoHashMap(u64, u64).init(gpa.allocator());
defer map.deinit();
std.debug.print("fib(20) = {}\n", .{try fib(&map, 20)});
}
Expected
fib(20) = 6765 with zero use-after-free or lost writes.
What happens instead
When map grows during try fib(map, n - 1), the old backing slice is freed (and filled with 0xaa by GeneralPurposeAllocator in Debug mode), so gop.value_ptr.* = ... writes into freed memory (or in ReleaseFast, silently loses the memoized entry and returns garbage from gop.value_ptr.*)!
Beyond calling map.put(n, val) after computing val, what happens if a graph can have cycles (where you need n marked as "in-progress" in the map before recursing) without holding a dangling value_ptr in Zig 0.13?
Your premise holds. getOrPut hands back pointers into the table's storage, and any later insertion that grows the table can invalidate them. I haven't run your example, and I'm not relying on Zig's assignment evaluation order, because the bug doesn't depend on it. The return gop.value_ptr.* after the recursive calls reads the stale pointer even if the assignment happened to work.
The fix for cycles: mark in-progress first, then re-look-up
Once the key is inserted, the placeholder write is safe. That write is the last use of gop. After the recursion, fetch a fresh pointer with getPtr, which can't fail because the key is already in the map.
const State = union(enum) { in_progress, done: u64 };
fn visit(map: *std.AutoHashMap(u32, State), g: Graph, n: u32) !u64 {
const gop = try map.getOrPut(n);
if (gop.found_existing) {
return switch (gop.value_ptr.*) {
.in_progress => error.Cycle, // back-edge detected
.done => |d| d,
};
}
gop.value_ptr.* = .in_progress; // last use of gop; no recursion has happened yet
var acc: u64 = 1;
for (g.edges(n)) |m| acc += try visit(map, g, m); // may rehash `map`
map.getPtr(n).?.* = .{ .done = acc }; // fresh pointer after the recursion
return acc;
}
For your Fibonacci case, which has no cycles, the simplest fix is to compute first and store afterwards:
if (map.get(n)) |v| return v;
const v = (try fib(map, n - 1)) + (try fib(map, n - 2));
try map.put(n, v);
return v;
Why this works
getOrPutallocates the slot up front, so the key is present before you recurse. Inner calls see.in_progressand can detect a cycle.- Zig's hash map docs say that insertion can invalidate pointers and iterators. Treat every
*Vas valid only until the next call that can insert. - Re-looking-up costs one extra hash per node. That is cheaper than any pointer-stability scheme.
Other options
- Pre-sizing:
ensureTotalCapacityonly works if you know a bound on the number of nodes. For unbounded recursion it isn't enough. - Stable storage: if you need long-lived references, store an index in the map and keep the payloads elsewhere. Don't hold
*Vacross calls, and note that anArrayListalso moves when it grows. - Error paths: on an error return the node stays
.in_progress. That is fine if you abandon the map after an error. Otherwise adderrdefer _ = map.remove(n);after the placeholder write.
The getOrPut and getPtr signatures are what I remember from the 0.13 std. If anything fails to compile, check std/hash_map.zig for your exact version.