GeneralPurposeAllocator leak explanation

Explain
1

The following code snippet leaks memory when using the GeneralPurposeAllocator and I can’t explain why.

pub fn part2(elfGroupLines: []const u8, allocator: Allocator) !i32 {
    var threeMaxStack = ArrayList(i32).init(allocator);
    var groupsIter = std.mem.tokenizeSequence(u8, elfGroupLines, "\n\n");
    while (groupsIter.next()) |elfLines| {
        var linesIter = std.mem.tokenizeSequence(u8, elfLines, "\n");
        var totalCalories: i32 = 0;
        while (linesIter.next()) |line| {
            totalCalories += try std.fmt.parseInt(i32, line, 10);
        }
        const maybeIndex = findPosition(threeMaxStack.items, totalCalories);
        if (maybeIndex) |index| {
            try threeMaxStack.insert(index, totalCalories);
        } else if (threeMaxStack.items.len < 3) {
            try threeMaxStack.append(totalCalories);
        }
        if (threeMaxStack.items.len == 4) {
            _ = threeMaxStack.pop();
        }
        assert(threeMaxStack.items.len <= 3);
    }
    const items = try threeMaxStack.toOwnedSlice();
    return items[0] + items[1] + items[2];
}

When I run the following test, the code works as expected and no memory is leaked.

test "Day 1, Part 2" {
    var buffer: [32]u8 = undefined;
    var fba = std.heap.FixedBufferAllocator.init(&buffer);
    const allocator = fba.allocator();

    const actual = try part2(input, allocator);

    try expect(actual == 212836);
}

However, when I swap out the FixedBufferAllocator for the GeneralPurposeAllocator, I get the following memory leak.

test "Day 1, Part 2" {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    const allocator = gpa.allocator();
    defer {
        const deinit_status = gpa.deinit();
        if (deinit_status == .leak) expect(false) catch @panic("TEST FAIL");
    }

    const actual = try part2(input, allocator);

    try expect(actual == 212836);
}

Here is the console output of the memory leak.

[gpa] (err): memory address 0x7fb24d300000 leaked: 
/home/christian/.zig/lib/std/array_list.zig:457:67: 0x1083dbe in ensureTotalCapacityPrecise (test)
                const new_memory = try self.allocator.alignedAlloc(T, alignment, new_capacity);
                                                                  ^
/home/christian/.zig/lib/std/array_list.zig:434:51: 0x104b900 in ensureTotalCapacity (test)
            return self.ensureTotalCapacityPrecise(better_capacity);
                                                  ^
/home/christian/.zig/lib/std/array_list.zig:483:41: 0x1045910 in addOne (test)
            try self.ensureTotalCapacity(newlen);
                                        ^
/home/christian/.zig/lib/std/array_list.zig:262:49: 0x1040e5c in append (test)
            const new_item_ptr = try self.addOne();
                                                ^
/home/christian/Coding/Zig/advent_of_code_2022/1_day/src/lib.zig:41:37: 0x1040a53 in part2 (test)
            try threeMaxStack.append(totalCalories);
                                    ^
/home/christian/Coding/Zig/advent_of_code_2022/1_day/src/lib.zig:78:29: 0x104145a in test.Day 1, Part 2 (test)
    const actual = try part2(input, allocator);
                            ^
/home/christian/.zig/lib/compiler/test_runner.zig:95:29: 0x10522ca in mainServer (test)
                test_fn.func() catch |err| switch (err) {
                            ^
/home/christian/.zig/lib/compiler/test_runner.zig:35:26: 0x1046d0e in main (test)
        return mainServer() catch @panic("internal test runner failure");
                         ^
/home/christian/.zig/lib/std/start.zig:514:22: 0x1041bb9 in posixCallMainAndExit (test)
            root.main();
                     ^
/home/christian/.zig/lib/std/start.zig:266:5: 0x1041721 in _start (test)
    asm volatile (switch (native_arch) {

Can someone break down for me why there is a memory leak?

2

My first suspicion is here. You create an owned slice (which calls allocator functions and release the memory to a slice), but the memory is never freed.

I’m actually curious why we’re doing an owned slice here? If it were me…

var threeMaxStack = ArrayList(i32).init(allocator);
defer threeMaxStack.deinit();
// ...
const items = threeMaxStack.items;
return items[0] + items[1] + items[2];

There may be something else but I think it’s worth looking at what toOwnedSlice does.

1 Like
3

And as a last note, I would suggest using something like a std.BoundedArray instead of allocating memory at all. You can create one with the exact size you want and get all the helper functions to do the job.

The issue is we’re allocating memory but not freeing it. It works fine with a fixed buffer allocator because the memory is on the stack:

var buffer: [32]u8 = undefined;
4

Only the GeneralPurposeAllocator reports leaks, which is why nothing got reported with the FixedBufferAllocator, but the leak still happened.
It looks like you’re trying to sum the max 3 calories. That is one very convoluted way of doing this. There is no need for any allocation:

pub fn part2(elfGroupLines: []const u8) !i32 {
    var values: [3]i32 = .{0, 0, 0};
    var groupsIter = std.mem.tokenizeSequence(u8, elfGroupLines, "\n\n");
    while (groupsIter.next()) |elfLines| {
        var linesIter = std.mem.tokenizeSequence(u8, elfLines, "\n");
        var totalCalories: i32 = 0;
        while (linesIter.next()) |line| {
            totalCalories += try std.fmt.parseInt(i32, line, 10);
        }
        
        const mIndex = std.mem.indexOfMin(&values);
        If(values[mIndex] < totalCalories){
            values[mIndex] = totalCalories;
        }
    }
  
    return values[0] + values[1] + values[2];
}
2 Likes
5

Interesting, I went this direction earlier in development. After I discovered toOwnedSlice, I chose to use it because of what it states in the docs.

Its capacity is cleared, making deinit() safe but unnecessary to call.

Is the GeneralPurposeAllocator not quite smart enough to deduce scenarios like this?

Also, if this is in fact an inappropriate time to use toOwnedSlice, when is an appropriate time?

Ah, good call out. I didn’t realize this was a feature unique to GeneralPurposeAllocator.

7

The doc comment stating, that deinit is unnecessary to call refers to the corresponding ArrayList. You still have to free the memory, which toOwnedSlice returns. Hence the name, because you now own the memory, and the ArrayList no longer does. This means, you are responsible for freeing the memory.

So adding an allocator.free(items) call should fix your problem.

3 Likes
8

Gotcha! This was my “Aha!” moment.

So, if my use case is simply reading the items of an ArrayList, threeMaxStack.items is the correct tool for the job.

If I had a sufficiently complex scenario (most definitely not the scenario I described above), toOwnedArray may be the correct tool for the job (and it may save me one line of threeMaxStack.deinit), but at the cost of needing to deinit my newly created Slice from toOwnedArray.

9

I’m glad you’re making progress - I’d like to take a step back and look at the fundamentals here.

deinit calls free on the underlying memory in the array list:

/// Release all allocated memory.
pub fn deinit(self: Self) void {
    if (@sizeOf(T) > 0) {
        self.allocator.free(self.allocatedSlice());
    }
}

And we can see here what allocatedSlice does:

/// Returns a slice of all the items plus the extra capacity, whose memory
/// contents are `undefined`.
pub fn allocatedSlice(self: Self) Slice {
    // `items.len` is the length, not the capacity.
    return self.items.ptr[0..self.capacity];
}

In summary, deinit calls free on the full underlying slice - not just the part of it that is currently used by the array list. It essentially frees everything that the array list is currently hanging onto.

Okay, so what does toOwnedSlice() do? Here’s the code and then we’ll do the breakdown:

/// Its capacity is cleared, making deinit() safe but unnecessary to call.
pub fn toOwnedSlice(self: *Self, allocator: Allocator) Allocator.Error!Slice {
    const old_memory = self.allocatedSlice();
    if (allocator.resize(old_memory, self.items.len)) {
        const result = self.items;
        self.* = .{};
        return result;
    }

    const new_memory = try allocator.alignedAlloc(T, alignment, self.items.len);
    @memcpy(new_memory, self.items);
    @memset(self.items, undefined);
    self.clearAndFree(allocator);
    return new_memory;
}

Basically, the first if statement says “we don’t need all this extra capacity, we only need what is actually used by the array list.” To accomplish this, they shrink it down to the self.items.len (which is smaller than or equal to self.capacity).

In the second case, they allocate only what they need and return the slice to you that is properly sized and free the older one that had extra capacity.

Okay, what does this have to do with ownership? toOwnedSlice ejects the memory from the array list to an “owning” slice. You now own that slice and the array list forgets about it (so if you call deinit on that array list, the array list is like “what memory?” because it’s been evacuated).

I hope that helps :slight_smile:

7 Likes