Panic when using StringHashMap as a simple set

Help
,
1

i’m using a std.StringHashMap as a simple set – which is to say that the value type is void… the only functions i use are contains() and put()…

while i’ve used this idiom elsewhere in my code, it seems to be doing nasty things in this case…

now here’s the strange part… if i use std.StringArrayHashMap instead, everything works just fine!!!

i do have a workaround – but at the same time, there might be a deeper issue in the runtime library that’s worthy of investigation… as i try to create the smallest example that illustrates this problem, is there anything else i should be mindful of??? is this a “known” problem??? etc.

thread 6052 panic: reached unreachable code
C:\tools\zig-dev\lib\std\debug.zig:403:14: 0x419a3d in assert (zig-em.exe.obj)
    if (!ok) unreachable; // assertion failure
             ^
C:\tools\zig-dev\lib\std\hash_map.zig:1074:19: 0x4e0c5a in putAssumeCapacityNoClobberContext (zig-em.exe.obj)
            assert(!self.containsContext(key, ctx));
                  ^
C:\tools\zig-dev\lib\std\hash_map.zig:1576:58: 0x4d1aa4 in grow (zig-em.exe.obj)
                    map.putAssumeCapacityNoClobberContext(k, v, ctx);
                                                         ^
C:\tools\zig-dev\lib\std\hash_map.zig:1512:30: 0x4ad318 in growIfNeeded (zig-em.exe.obj)
                try self.grow(allocator, capacityForSize(self.load() + new_count), ctx);
                             ^
C:\tools\zig-dev\lib\std\hash_map.zig:1333:34: 0x486992 in getOrPutContextAdapted__anon_10099 (zig-em.exe.obj)
                self.growIfNeeded(allocator, 1, ctx) catch |err| {
                                 ^
C:\tools\zig-dev\lib\std\hash_map.zig:1318:56: 0x4690de in getOrPutContext (zig-em.exe.obj)
            const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
                                                       ^
C:\tools\zig-dev\lib\std\hash_map.zig:1244:52: 0x43ee0a in putContext (zig-em.exe.obj)
            const result = try self.getOrPutContext(allocator, key, ctx);
                                                   ^
C:\tools\zig-dev\lib\std\hash_map.zig:552:45: 0x4066e3 in put (zig-em.exe.obj)
            return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
2

My guess would be that you are unintentionally making a copy of the StringHashMap somewhere and modify it, then continue using the original which has corrupted meta data (Because the copies meta data was updated, but not the original).
Then the error probably happens because the original still thinks it has remaining capacity, while that was already used through the copy and the pointers in the original aren’t valid anymore.

Probably the StringArrayHashMap would hit a similar issue, it just might be that it works with a different capacity and maybe the capacity isn’t reached there yet, making the bug less noticeable.

But I can’t really say without seeing the code.

Make sure the uses of your StringHashMap instance exist at the same address and be careful about how you create it and move it into the location from where it is supposed to be used. Basically compare addresses to see whether you end up with a unwanted copy somewhere.

3

I am running into the same issue. StringArrayHashMap has no issue while StringHashMap fails while trying to grow. Here is an example:

const StringHashMap = std.StringHashMap;
const StringArrayHashMap = std.StringArrayHashMap;

// var h = StringArrayHashMap(u16).init(alloc);
var h = StringHashMap(u16).init(alloc);
defer h.deinit();

for (0..256) |i| {
    const code_point: u21 = @intCast(i);

    var buf: [4]u8 = undefined;
    const bytes_written = try std.unicode.utf8Encode(code_point, &buf);
    const char = buf[0..bytes_written];

    print("code point: {}, bytes written: {}, char: {x} \n", .{
        code_point,
        bytes_written,
        char,
    });

    try h.put(char, 100);
}
4

You are using Pointers to Temporary Memory, your char is only valid until the end of the current iteration of the for loop, instead use an allocator to allocate the string or a buffer of memory that has a longer life time and doesn’t get overridden.

StringArrayHashMap and StringHashMap expect keys to remain valid and unchanged after they were inserted into the hash map, so you need to use memory for your strings that has a longer life time.

As soon as the memory of buf that is on the stack gets overwritten the slice that was inserted as the key now points to different memory then the memory it was inserted with.

Hash maps require keys to remain unchanged, so that the invariants of the data structure aren’t broken. And looking up those values in the data structure actually works. (If keys change, their hashes change and now you have a key at a place where it doesn’t belong)

This breaking of the invariants can have different effects (like one datastructure not immediately failing (appearing to work), while the other is panic-ing), but both use the hash map in an incorrect way and thus will fail eventually. So neither of them is actually working.

I would expect things like:

  • reading keys back out (for example by using an iterator over the map) to display different values than were inserted
  • possibly meta data being corrupted
  • failed assertions if you are lucky
  • and panics if you are lucky (which are actually better then just getting wrong results or corrupted key data)

With your example if you would print the addresses of the keys, the slices would all point to the same address that points to buf that gets repeatedly overwritten and then, after the loop gets replaced by other stack contents.

2 Likes
5

Thanks for the in-depth description!

For myself and others who land here, once allocating keys, make sure too free them too:

        var codebook = StringHashMap(u16).init(alloc);
        defer {
            var key_iter = codebook.keyIterator();
            while (key_iter.next()) |key| {
                alloc.free(key.*);
            }
            codebook.deinit();
        }
2 Likes