GeneralPurposeAllocator: assertion failure when `retain_metadata` and `never_unmap` are used

[squeek502]

Zig Version

0.13.0-dev.211+6a65561e3

Steps to Reproduce and Observed Behavior

This test case:

const std = @import("std");

test "retain metadata and never unmap" {
    var gpa = std.heap.GeneralPurposeAllocator(.{
        .safety = true,
        .never_unmap = true,
        .retain_metadata = true,
    }){};
    defer std.debug.assert(gpa.deinit() == .ok);
    const allocator = gpa.allocator();

    const alloc = try allocator.alloc(u8, 8);
    allocator.free(alloc);

    const alloc2 = try allocator.alloc(u8, 8);
    allocator.free(alloc2);
}

fails with

C:\Users\Ryan\Programming\Zig\zig\lib\std\debug.zig:403:14: 0xcb146d in assert (test.exe.obj)
    if (!ok) unreachable; // assertion failure
             ^
C:\Users\Ryan\Programming\Zig\zig\lib\std\treap.zig:288:45: 0xcbf017 in next (test.exe.obj)
                            std.debug.assert(previous == current.children[1]);
                                            ^
C:\Users\Ryan\Programming\Zig\zig\lib\std\heap\general_purpose_allocator.zig:443:37: 0xcb4276 in freeRetainedMetadata (test.exe.obj)
                while (empty_it.next()) |node| {
                                    ^
C:\Users\Ryan\Programming\Zig\zig\lib\std\heap\general_purpose_allocator.zig:475:42: 0xcb135d in deinit (test.exe.obj)
                self.freeRetainedMetadata();
                                         ^
C:\Users\Ryan\Programming\Zig\tmp\doublefree.zig:9:38: 0xcb1164 in test.retain metadata and never unmap (test.exe.obj)
    defer std.debug.assert(gpa.deinit() == .ok);
                                     ^

This is likely a regression introduced during #17383

Expected Behavior

The test to pass

[Frojdholm]

This crash is due to buckets being deallocated while traversing the tree. Since in-order traversal is used the parent is destroyed before the right child is visited.

        fn freeRetainedMetadata(self: *Self) void {
                // ...
                var empty_it = self.empty_buckets.inorderIterator();
                while (empty_it.next()) |node| {
                    var bucket = node.key;
                    if (config.never_unmap) {
                        // free page that was intentionally leaked by never_unmap
                        self.backing_allocator.free(bucket.page[0..page_size]);
                    }
                    // alloc_cursor was set to slot count when bucket added to empty_buckets
                    self.freeBucket(bucket, @divExact(page_size, bucket.alloc_cursor));
                    self.bucket_node_pool.destroy(node);  // <-- PARENT DESTROYED BEFORE VISITING RIGHT CHILD
                }
                self.empty_buckets.root = null;
            }
        }

The way I see it there are 3 possible solutions:

1. Switch to post-order traversal, then both children are deallocated before the parent.
2. Make the in-order traversal support deallocation of nodes during iteration.
3. Save the nodes in some other data structure (possibly a linked list) and destroy them at the end after freeing all the buckets.

To me option 1 sounds the best unless there is a specific reason in-order traversal is being used here.

[squeek502]

In-order iteration was purposefully used for detectLeaks since it would then mirror the order of the allocations that were made, but there's no reason that freeRetainedMetadata has to use in-order iteration. Option 1 sounds good to me as well.

[Frojdholm]

I went with a fourth approach that explicitly removes nodes from the tree before destroying them. This causes extra work (walking to the smallest element each iteration and rotations for nodes with right branches), but has the benefit of not creating a public API that could very easily be misused.

The problem with the post-order iterator approach is that it invalidates the tree itself when the first node is deallocated. The iteration only works because each node is being deallocated, but the tree itself cannot be reused. There's probably a better solution that makes it more clear that this iterator should only be used to:

1. Iterate and look at the nodes of the tree (here the InorderIterator is probably better)
2. Destroy each node of the tree.

Related to this the InorderIterator should probably return const pointers since modifying nodes can very easily lead to bugs, such as this use-after-free.