Corrupted tag in union unless read unions first

Help
1

I’m sort of at a loss as to how to ask this question. I’m building up a tree data structure to test. I wrote a function shortTreeMock() to construct a simple version of the tree.

After building the tree in main(), and when I go to read what’s inside, I find it panics on a corrupted tag on the 52nd node.

Weird thing is, if inside of shortTreeMock(), there is code to loop through all nodes to read and display them, the loop inside of main will not find a corrupted tag on the 52nd node. But if I remove the code to loop through all nodes to read and display them, it will

It seems like the memory would be corrupted unless I read it inside of shortTreeMock() first. This doesn’t make sense. I’m guessing it’s something else. What could be the culprit? How could I find out?

Details below.

Here is the output of zig build run

Leaf Node 49: { 10702, 0, 0, 0, 0, 0, 0, 0 }
Leaf Node 50: { 11047, 0, 0, 0, 0, 0, 0, 0 }
break here
Leaf Node 51: { 11167, 0, 0, 0, 0, 0, 0, 0 }
thread 9979832 panic: switch on corrupt value
/Users/iamwil/projects/code/fruitful_town/database/src/main.zig:20:17: 0x10288b4ff in main (database)
        switch (node) {
                ^
/Users/iamwil/.zvm/0.13.0/lib/std/start.zig:524:37: 0x10288c44b in main (database)
            const result = root.main() catch |err| {
                                    ^
???:?:?: 0x18651e0df in ??? (???)
???:?:?: 0x1f62ffffffffffff in ??? (???)
run
└─ run database failure
error: the following command terminated unexpectedly:
/Users/iamwil/projects/code/fruitful_town/database/zig-out/bin/database 
Build Summary: 5/7 steps succeeded; 1 failed (disable with --summary none)

This is in test_helpers to build the tree

pub fn shortTreeMock(allocator: std.mem.Allocator) !prolly.OrderedMap(u32, u32) {
    const randArr = try randomSortedUniqueArray(allocator, u32, 64, 0, 16384);
    defer allocator.free(randArr);

    const groups = try partition(allocator, u32, randArr, prolly.MAX_NODE_SIZE, prolly.MAX_NODE_SIZE);
    defer allocator.free(groups);

    // create all the child nodes.
    // leave room at [0] for the root.
    var branchNodes: [prolly.MAX_NODE_SIZE + 1]prolly.BranchNode(u32) = undefined;
    for (groups, 0..) |group, groupIndex| {
        var pivots: [prolly.MAX_NODE_SIZE]u32 = undefined;

        // fill in pivots
        for (group, 0..) |elem, idx| {
            pivots[idx] = elem;
        }

        // create branch node
        const branchNode = prolly.BranchNode(u32).initWithPivots(pivots);
        try testing.expect(branchNode.pivots[0] == group[0]);
        try testing.expect(branchNode.pivots[branchNode.pivots.len - 1] == group[branchNode.pivots.len - 1]);

        branchNodes[groupIndex + 1] = branchNode;
    }

    // root pivots are the the min pivot for all child nodes
    var pivots: [prolly.MAX_NODE_SIZE]u32 = undefined;
    for (0..prolly.MAX_NODE_SIZE) |i| {
        pivots[i] = branchNodes[i + 1].pivots[0];
    }
    branchNodes[0] = prolly.BranchNode(u32).initWithPivots(pivots);

    // create all leaf nodes
    var leafNodes: [prolly.MAX_NODE_SIZE * prolly.MAX_NODE_SIZE]prolly.LeafNode(u32, usize) = undefined;
    for (branchNodes[1..], 1..) |childNode, branchIdx| {
        for (childNode.pivots, 0..) |currPivot, pivotIdx| {
            const leafIdx = (branchIdx - 1) * prolly.MAX_NODE_SIZE + pivotIdx;

            // Currently, only a single key in the leaf, because figuring out
            // the next pivot as max for random array is too much work at the moment.
            const keys: [prolly.MAX_NODE_SIZE]u32 = .{ currPivot, 0, 0, 0, 0, 0, 0, 0 };
            const valueIndexes: [prolly.MAX_NODE_SIZE]usize = .{ 0, 0, 0, 0, 0, 0, 0, 0 };

            leafNodes[leafIdx] = prolly.LeafNode(u32, usize)
                .initWithKeyIndexes(keys, valueIndexes);

            std.debug.print("new leaf {}: {any}\n", .{ leafIdx + 9, leafNodes[leafIdx].keys });
        }
    }

    const numNodes = 1 + prolly.MAX_NODE_SIZE + prolly.MAX_NODE_SIZE * prolly.MAX_NODE_SIZE;
    std.debug.print("allocating {} nodes\n", .{numNodes});
    var allNodes: [numNodes]prolly.Node(u32, usize) = undefined;
    var idx: u32 = 0;
    for (0..branchNodes.len) |branchIdx| {
        allNodes[idx] = prolly.Node(u32, usize){ .Branch = branchNodes[branchIdx] };
        idx += 1;
    }
    for (0..leafNodes.len) |leafIdx| {
        allNodes[idx] = prolly.Node(u32, usize){ .Leaf = leafNodes[leafIdx] };
        idx += 1;
    }

    // RIGHT HERE If this code to display the nodes isn't here, the display code in main errors out.
    // for (allNodes, 0..) |node, i| {
    //     switch (node) {
    //         .Branch => |branchNode| {
    //             std.debug.print("p Branch Node {}: ", .{i});
    //             std.debug.print("{any}\n", .{branchNode.pivots});
    //         },
    //         .Leaf => |leafNode| {
    //             std.debug.print("p Leaf Node {}: ", .{i});
    //             std.debug.print("{any}\n", .{leafNode.keys});
    //         },
    //     }
    // }

    const seg = prolly.Segment(u32, u32, prolly.MAX_NODE_SIZE).init();
    var segments: [1]prolly.Segment(u32, u32, prolly.MAX_NODE_SIZE) = .{seg};

    const orderedMap = prolly.OrderedMap(u32, u32).initWithNodes(allocator, allNodes[0..], segments[0..]);
    return orderedMap;
}

This is main that uses the tree. The loop to look in the tree is what errors out at the 52nd node.

pub fn main() !void {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    const orderedMap = try test_helper.shortTreeMock(allocator);

    std.debug.print("number of nodes: {}\n", .{orderedMap.nodes.len});
    for (orderedMap.nodes, 0..) |node, i| {
        if (i == 51) {
            std.debug.print("break here\n", .{});
        }
        switch (node) {
            .Branch => |branchNode| {
                std.debug.print("Branch Node {}: ", .{i});
                std.debug.print("{any}\n", .{branchNode.pivots});
            },
            .Leaf => |leafNode| {
                std.debug.print("Leaf Node {}: ", .{i});
                std.debug.print("{any}\n", .{leafNode.keys});
            },
        }
    }
}
2

Does initWithNodes copy all the node data to allocated memory?
I probably would print out / debug what orderedMap looks like, see if it contains any uninitialized memory.

Also before the switch (node) { you could print the value, but I think using a debugger to step through / backtrack from the panic to the point where the memory of that value is set incorrectly / not at all, would probably the quickest way to identify the problem.

2 Likes
3

Yeah, sounds like stack memory is getting returned here. Easiest way to check is to pass a std.heap.FixedBufferAllocator to the function then use ownsPtr() to see if the nodes are sitting on memory from the allocator.

2 Likes
4

oh, I see. If I created an array of nodes prior to calling initWithNodes, that array of nodes is created in the context of the function, so when it goes out of scope, that array is invalid. If I simply assigned it to the struct like so:

        pub fn initWithNodes(allocator: std.mem.Allocator, newNodes: []Node(K, usize), newSegments: []Segment(K, V, MAX_NODE_SIZE)) Self {
            return Self{
                .allocator = allocator,
                .nodes = newNodes,
                .segments = newSegments,
            };
        }

Then when the struct is returned, it’s pointing to some array of nodes allocated on the stack, which will then progressively get corrupted because we’ve exited the function. Basically, I’m retaining a pointer to memory that was allocated on the stack during function execution, and when the function goes out of scope, it’s no longer valid. Is that correct?

So does that mean I’ll always need to copy nodes from the arguments into the struct, rather than copy the pointer. I assume that’s a big fat yes.

5

There are situations where it is perfectly fine to use just the pointer, for example when the data-structure is just used temporarily while something is being calculated and gets deinit-ed on function exit too.

But if you want to create data-structures that have a longer life time then your function (and its stack memory), then you can’t use stack memory to save your data-structure entries, instead you need something with a longer life time, usually you then use heap allocated memory via allocators, which means you need your initialization code to transfer the data to this heap allocated memory via a copy.

6

Makes sense. I’d known this in theory, but not in practice.

What’s common practice? should I allocate an array on the heap outside of the init to pass in to avoid a copy? Or have the struct handle all its own allocations, so users of the init function don’t have to think about allocations?

7

I think for the common case that is most expected, because it still allows the user to pass in something like a FixedBufferAllocator if the user decides that the memory only needs a stack life time.

But there are also cases where the needed memory is very limited / fixed in size, in those situations sometimes the user passes in a suitably large buffer that is then used as temporary memory.

So overall I think it depends a bit on the specific code and the intended way the user should use it.

2 Likes
8

In std.fmt these get called allocPrint and bufPrint, for example. Where allocPrint takes an allocator, calculates the size of buffer needed, creates it, then calls bufPrint.

It might be nice to have a doc in the Wiki about the naming conventions used in std, because they reflect recurring patterns in Zig code, and following them is useful to users of a library.

3 Likes