Ramblings about things

Heap, stack, and... something else?

I was doing the Advent of Code puzzles recently to have something to sharpen my zig skills on and I stumbled upon something that had me stumped for a bit.

The task at hand was day 19 of 2015 (part two, though) where you have:

The thing that had me stumped isn't the task itself1, but the fact that I had an invalid free somewhere in the program.

Coming from C++ I thought I'd be well equipped to deal with such errors, but this was a bit of a curveball, albeit obvious in hindsight.

Here's the code and see if you can spot the mistake!

test "invalid free" {
    const allocator = std.testing.allocator;

    // iterative approach to a problem so we'll
    // just keep appending things to this list instead
    // of having a recursion
    var candidates = std.ArrayList([]const u8).empty;
    defer {
        // it is the owner of its elements
        // ergo explicit cleanup is needed
        for (candidates.items) |item| {
            allocator.free(item);
        }
        candidates.deinit(allocator);
    }

    // starting point
    try candidates.append(allocator, "e");

    for (0..std.math.maxInt(u8)) |i| {
        const current_candidate = candidates.items[i];

        // do some calculation to find new candidates
        const new_candidate = try calculate(allocator, current_candidate, i);
        if (new_candidate == null) {
            break;
        }
        try candidates.append(allocator, new_candidate.?);
    }

    // do something with all of the possible candidates
    // ...
}

fn calculate(allocator: std.mem.Allocator, candidate: []const u8, x: usize) !?[]const u8 {
    if (x > 5) {
        return null;
    }
    // a possible failure here is not the topic of this blogpost
    return try allocator.dupe(u8, candidate);
}

const std = @import("std");

Running it with zig-15 test leak.zig we get an error stating that there's an invalid free:

thread 344157 panic: Invalid free
/usr/lib/zig/std/heap/debug_allocator.zig:875:49: 0x1038287 in free (std.zig)
            if (bucket.canary != config.canary) @panic("Invalid free");
                                                ^
/usr/lib/zig/std/mem/Allocator.zig:147:25: 0x1039b26 in free__anon_1850 (std.zig)
    return a.vtable.free(a.ptr, memory, alignment, ret_addr);
                        ^
/tmp/zig_issue/leak.zig:12:27: 0x1035e55 in test.invalid free (leak.zig)
            allocator.free(item);
...

By taking things out to get a minimum reproducible example I got to the point where just appending the starting point of "e" triggered the behavior!

Then it dawned on me. It's neither on the stack nor the heap!

It's embedded in the binary.

The 'something else'

Hardcoded literal strings like "e" are stored in the .rodata (read-only data) section of the ELF file, which means their lifetime is tied to the lifetime of the process itself.

Nobody should free them. It has to be explicitly put on the heap, just like all the other elements.

...
// starting point
-try candidates.append(allocator, "e");
+try candidates.append(allocator, try allocator.dupe(u8, "e"));
...

Even though C++ is a "low-level" language with a lot of footguns, this specific footgun is one that I haven't blown my foot off with until now.

Conclusion

I like zig.

  1. That too, but that's besides the point.↩

#zig