The curious case of a memory leak in a Zig program

152 points18
judofyr14 hours ago

> As a personal challenge, I strived to explicitly limit the amount of memory needed for solving each AoC problem to something that fits on the stack (typically a few MBs at most).

If the purpose is to "use limited amount memory" I would suggest to use a GeneralPurposeAllocator and setting "enable_memory_limit" and "requested_memory_limit": If the purpose is to "only use the stack", then "allocating a huge chunk and using it with a bump allocator" feels a bit like cheating to be honest...

Another potential challenge is to pre-allocate instead: Have an _initialize_ phase which is allowed to allocate memory and then an _execution_ phase where you're using the allocated memory. This pattern is very common in high-performance programs.

krut-patel13 hours ago

Thanks for the pointers!

> use a GeneralPurposeAllocator and setting "enable_memory_limit" and "requested_memory_limit"

Interesting! I hadn't looked at GeneralPurposeAllocator too closely, but yes these seem like the right way to do things instead of abusing FixedBufferAllocator as I did.

> If the purpose is to "only use the stack"...

Not really, I just had to decide on some arbitrary upper bound on the mem usage, and the default stack size (8MiB) seemed like a decent choice. In retrospect, this challenge only took shape because my solution to Day1 used a FixedBufferAllocator backed by a buffer on the stack, and I realized how easy Zig made it to track allocs. I didn't fiddle too much with the general structure of the solution after that, and made it a "challenge" to see how far I could take it.

> Another potential challenge is to pre-allocate instead

Ah, that sounds much more difficult. This is also what TigerBeetle is doing [1]. But one thing I didn't understand even from that post, how would one deal with data structures that really depend on the input data, like the hashsets in TFA? Simplest way I can think of is to have an arbitrary upperbound on the allocated memory and then keep checking before every operation on any dynamic structure. That sounds tedious. Is there a better way?


messe8 hours ago

I think you might be able to abuse an ArenaAllocator wrapping a FixedBufferAllocator. I haven't tested it, but IIRC, Zig's ArenaAllocator deallocates in reverse order once it's reset (it uses a singly linked list to keep track of allocations, so that's the natural way to do deallocation), so it might play nicely with the underlying FixedBufferAllocator's requirements.

If this is correct, it's likely an undocumented implementation detail, so probably not something you should rely on always being the case.

eatonphil9 hours ago

TigerBeetle writes to disk for long-term storage. Data over time is the part you can't fit into memory (eventually). :)

krut-patel5 hours ago

> TigerBeetle writes to disk for long-term storage

But how does it determine when it should write to disk? Does every write to a potentially OOM operation get preceeded by a check? Take the case of a HashAggregate. The DB clearly cannot know at compile time how many unique keys will be present in the hashtable; it needs to resize at runtime. So does that mean all the hashtables are still using some form of Bump/Arena allocators backed by the pre-allocated memory?

Maybe I should just read the source code :)

eatonphil5 hours ago

> But how does it determine when it should write to disk?

You write fixed sized number of key-value pairs to the file at a time. This is how LSM trees work, you chunk your data up into N sorted keys per chunk. I don't myself understand all the specifics but this is the gist.

> Does every write to a potentially OOM operation get preceeded by a check?

If you allocate memory upfront and don't allocate any more memory, you can't OOM after the initial allocation. That's what TigerBeetle does.

Zig has some nice standard library containers for adding items while asserting that there's capacity. If we miscalculate, it is caught during tests because assertions fail.

charcircuit11 hours ago

>Is there a better way?

Just let the kernel handle it. The virtual memory and mapped memory abstraction the kernel has makes your program's implementation simpler.

kps6 hours ago

Zig is a low-level language. You might not have an MMU. You might not have a kernel. You might be the kernel.

charcircuit3 hours ago

Maybe if we went back a few decades. But in 2023 having access to a MMU and a kernel is normal.

rntz8 hours ago

> If you are hell-bent on using FixedBufferAllocator only and you want to avoid copies, there is a way. Using two buffers (and separate allocators backed by them), it is possible to keep swapping between them after every iteration.

I found this bit lovely: the author has independently reinvented the core idea of semispace copying garbage collectors (see eg

krut-patel5 hours ago
gonzus1 hour ago

That would be me... Cheers!

dundarious6 hours ago

Every recommendation I’ve seen surrounding learning/using zig’s standard library highlights that there is very limited documentation, so you must read the source. Good news, it’s quite readable and navigable — I’ve done it a lot.

I’m not defending nor criticizing that fact or the OP, but it is the state of things today. Even the existence of the library docs is marked “experimental” on

Maybe it’s not emphasized enough.

jmull2 hours ago

IMO, the fact that reading the source is perfectly reasonable advice for the beginner learning zig is a pretty powerful endorsement for the language.

(As someone who did it for AOC 2021)

AshamedCaptain11 hours ago

I know absolutely nothing about Zig (but I know C) and when I read "FixedBufferAllocator" I immediately guessed what the problem would be. I can see why it is claimed as a C replacement.

I am actually kind of surprised the author spent so much time figuring it out. The name of the allocator is not that well-defined, but at least to me it hints of it being simpler rather than full-featured allocator. I would also imagine he's using this in a very anti-patternic way. One would guess the point of this would be to destroy the entire allocator on every iteration, rather than trying to free everything 'nicely' which would be a lot of wasted work. This is a rather common pattern in a lot of "high-level" embedded development like this.

laserbeam8 hours ago

> I am actually kind of surprised the author spent so much time figuring it out.

I wouldn't be. People learn different programming techniques at different times. I'd actually assume quite a lot of programmers don't know what a bump allocator is and eventually run into one in the wild. Kudos for the author for successfully debugging and discovering that.

> One would guess the point of this would be to destroy the entire allocator on every iteration

Not necessarily every iteration, but yes, these allocators are meant to be reset to 0 at a known time, when it's safe to do so.

mort969 hours ago

After reading the description of the problem, I also had the thought, "Maybe FixedBufferAllocator is a bump allocator?". So before reading further, I checked the documentation to see if I was right. Turns out .. there is no documentation for FixedBufferAllocator?

Here's the documentation page:;std:heap.Fix.... It just lists a couple methods, most of which have the description "No documentation provided". From those docs, it doesn't even look like there's a way to allocate memory using the FixedBufferAllocator. You might guess that it implements a bump allocator based on the fact that it only has an 'end_index' and a slice, but wow, I feel like an allocator is the kind of thing you really want to have documented well; especially a bump allocator, and especially especially a bump allocator whose name makes it sound like a general purpose allocator which happens to allocate within a fixed buffer.

I knew it was still early for Zig, but that's a bit disappointing.

throwawaymaths7 hours ago

> I knew it was still early for Zig, but that's a bit disappointing.

They're pretty explicit about not taking too much effort to document stuff in the stdlib, because any given thing in there may or may not make the final cut when the stdlib is stabilized (this is deliberate because they don't want to make people pissed or burned out for putting effort into documentation that winds up getting nuked). While FBA (or something like it) will likely make the cut, I'd say, maybe give them a break?

masklinn8 hours ago

> From those docs, it doesn't even look like there's a way to allocate memory using the FixedBufferAllocator.

There is but not directly through the FBA, you need to get a concrete Allocator struct out of that by calling the allocator() or threadsafeAllocator() functions.

mort968 hours ago

Yeah, I guessed it was something external. I just said it to illustrate how surprisingly incomplete the docs are, I would expect the docs for an allocator to include enough information to figure out how to allocate something with the allocator.

masklinn11 hours ago

That's interesting, all it told me is that it's fixed-size. Without more information, and likely as the author did, I'd have assumed something like a bitmap allocator, which is hardly complicated but is a lot "safer" than a bump allocator in the face of deallocations (though it is sensitive to fragmentation).

toxik9 hours ago

I feel like this could also be fixed by a simple algorithm to keep track of the start index in FixBufAlloc.

masklinn8 hours ago

Not really. If you allocate a bunch of objects then deallocate one in the middle of the sequence neither head or tail will help you. And once you’ve done that you’ve hit holes you can’t track anymore.

To fix this issue you need a completely different allocator design, e.g. a bitmap, which can keep track of individual locations within its buffer.

2h9 hours ago

> anti-patternic

patternic is not a word.

dcminter9 hours ago

Why? All words are coined at some point.

2h9 hours ago

well for one, because the correct word "idiomatic" already exists:

throwawaymaths7 hours ago
smegsicle5 hours ago

it's an idiotic construction— the prefix may be originally greek, but has taken a specific connotation in english, while 'pattern' is from french, and the '-y' suffix is more common in english anyway, so the correct form for the idea would of course be anti-pattern–y

macintux9 hours ago

It is now.

Dwedit6 hours ago

Perhaps that allocator could print a warning message if you're not deleting the last element (when built in debug mode). That would make it a lot more clear how that kind of allocator should be used.

jesse__5 hours ago

I use this pattern a lot and my allocators print a huge warning when they detect this kind of leak. +1 for this suggestion. It's a hard bug to track down in nontrivial code.

aserafini16 hours ago

Suggestion for the blog post author: make a PR to the Zig docs to clarify this if it’s not already.

krut-patel14 hours ago

Will do, I have just been procrastinating too much!

throwbadubadu12 hours ago

Such linear allocators are not too uncommon in embedded / static allocation context, but one definitely needs to know how they work. So first thought was you didn't read the docs, but docs do not clearly state that behavoour that is ugly (:

masklinn10 hours ago

> So first thought was you didn't read the docs, but docs do not clearly state that behavoour that is ugly (:

Yep, neither the name nor what little documentation there is a are really helpful, and that looks to be a long-standing issue (

Seems to me like this allocator should be renamed something like "FixedBufferBumpAllocator", which:

- leaves room for other fixed-buffer allocators (e.g. bitmap, slabs)

- spell out that there's something of note about the allocator, whose drawbacks the developer either would already be aware of or would be able to look up easily

shp0ngle7 hours ago

There are basically no docs for this allocator.

glandium16 hours ago

TL;DR: the author had to figure out the hard way that Zig's FixedBufferAllocator is a bump allocator, and that it doesn't reuse freed memory except when it's the last allocation.

Yoric15 hours ago

Nit: /last/latest/

wnoise6 hours ago

That depends a good deal on your connotations for those words. Either work, so long as you restrict to the "live" allocations. If not, neither work.

jpcfl15 hours ago

What an awful API design choice. It’s a stack allocator that leaks your memory if you don’t free in reverse order. Why would anybody ever want that behavior, let alone as the default?

laserbeam8 hours ago

One often uses these allocators for temporary allocations in contexts where you can reset them at a known time. For example, in a game you put a lot of temporary stuff in them faster than by using a general purpose allocator, and then call .reset() at the end of every frame. You then reuse the same memory buffer next frame.

Every allocator other than a general purpose allocator has a use case where it's faster, and assumes you know what you're doing with it.

Iridescent_15 hours ago

Because this is a specific allocator different from the general purpose allocator which is the "default" option. It is aimed at some specific use cases, when developers want to fine-tune their allocation strategies.

mitulvohra14 hours ago

I get that it is a specific allocator for niche use cases but i think it would be better that free throws some exception if it is done out of order rather than just being a no-op and making the programmer figure it out.

laserbeam8 hours ago

Bump allocators of this type are meant to be reset to 0 at a known time when it's safe to do so. Its perfectly legal to not free in order. You really shouldn't care about freeing in order with them. Instead, one normally pays attention to when reset() is supposed to be called to not break anything.

For games it's easy to find a safe spot (end of frame). For a server, you might have have a pool of bump allocators (1 per connection), and you'd reset them after every http request. etc.

masklinn14 hours ago

I think the out of order bit is fine, in most cases it’s not an issue and may even be necessary. Your proposal would be straight up incompatible with most collections, and greatly limiting to the rest.

But it should be clearly spelled out.

When your type is already called

You can probably extend it to

And now the implications are more searchable and clearer.
mirekrusin13 hours ago

Zig is low level programming language with explicit allocation controls.

This allocator is useful to write extremely efficient algorithms in certain scenarios.

If you wanted to throw on double free, you'd have to track what was freed and this tracking doesn't come for free.

Documentation has section on choosing allocator [0].


ben-schaaf8 hours ago

The point of these kinds of allocators is to not ever free their allocations. Unfortunately not having a free breaks generic code, so having a no-op free is the only real solution.

throwawaymaths8 hours ago

No. You definitely want it to not cause an error/panic (zig does not have exceptions).

1. Frees are never supposed to error

2. You want code to be interchangeable so that you can try out different allocators.

3. Eventually when someone writes a lifetime analysis tool for zig, you'll want to signify the memory as freed

4. If your program is long-running (the bumping is part of a subtask) you probably want the bump allocator to be itself freed on its own lifetime, so you'll eventually free that memory.

renox15 hours ago

It's not the 'default' it's the behaviour of this allocator.

This makes this allocator fast, but it should clearly be named/described I agree.

jpcfl5 hours ago

Thanks. Yeah, that's my point. The naming doesn't make it obvious.

Personally, I would have called this a StackAllocator, that way the alloc/free order requirement is obvious. I would have made the default behavior to 'panic()' if you don't satisfy the precondition of freeing the most recently allocated buffer.

If somebody really wanted to make free a no-op, I'd offer a feature flag to turn that on.

vocx2tx14 hours ago

An allocator that silently does nothing on free if you violate one if its invariants (freeing an allocation that wasn't the latest) seems an incredibly error-prone design? It should probably return an error or panic (if free's API allows it, I guess).

masklinn13 hours ago

It’s not a invariant is the thing.

Transient allocators doing little to nothing on free so you can do all the work at once at end of scope is often what you want, if anything a bump allocator freeing its tip is an optimisation.

The issue is not that it behaves this way, it’s that it’s not obvious at first glance that this is a bump allocator.

vocx2tx13 hours ago

> a bump allocator freeing its tip is an optimisation

That's kinda my point? free is there and does something, but also silently does nothing if you violate a fairly subtle invariant. Kinda the definition of "error-prone", and the whole blog post seems to prove it, as the leak was essentially caused by the author not realizing that free was silently doing nothing. I understand why bump-allocators exist, I'm just saying this particular one's API has quite the footgun.

masklinn12 hours ago

> That's kinda my point?

It’s the exact opposite of your point.

> free is there and does something, but also silently does nothing if you violate a fairly subtle invariant.

Again, not an invariant.

> the leak was essentially caused by the author not realizing that free was silently doing nothing

The leak was caused by the author not knowing this is a bump allocator because that was not clear from the naming (and the documentation is essentially non-existent).

> I'm just saying this particular one's API has quite the footgun.

It’s not the API that’s a footgun, it follows the standard allocator API so it can be used wherever an allocator is expected. If it did not, its usage scope would be extremely limited as you'd only be able to use it for bespoke allocations, and wouldn't be able to use it for allocating e.g. arrays or sets or maps.

throwbadubadu12 hours ago

No, there are contexts where you exactly want this behaviour is what poster above wanted to say, and I agree. But it needs to be well documented.

LoganDark13 hours ago

> invariant

There is absolutely no such invariant here that allocations must be freed in the reverse order that they were allocated in. This was never a part of the contract.

> this particular one's API has quite the footgun

Agreed, however.

eternalban11 hours ago

You are entirely correct. If anything, if I were the OP the title of the blog would be "Naming matters - The curious case of ..."

mort969 hours ago

The point of a bump allocator is to be short-lived, and to be incredibly fast. You want to be able to make a bump allocator with a fixed buffer, pass it to some code which takes a generic allocator (and therefore will call allocate and free in any order), and then free all the memory in one shot at the end. If calling free out of order made it throw, it would be useless for that purpose; it would only be useful for code written specifically to use a bump allocator.

olivermuty14 hours ago

I don’t know zig and I am lazy, can someone explain his comment about why not freeing the input would lower the printed memory usage?

mirekrusin13 hours ago

It's not zig, bump allocator behaves like this in rust or any other language.

It doesn't reclaim space on free - it's no-op.

The only thing you can do without extra tracking is to reclaim space for last allocated buffer - and zig does just that. You can do it because you have all information available to do it, that's the only reason.

You could add extra rule where free on last allocated buffer triggers all reclamations on the tail - but you'd have to add extra tracking stuff - ie. at the end of the buffer that grows inwards.

But this adds extra complication which is outside of scope for this allocator. You can have other one that does it.

krut-patel14 hours ago

In case you were referring to the footnote, it suggests "freeing the input would not lower the printed memory usage".

Let me know if you need a full explanation as to why.

Jamie991210 hours ago

I really like how quickly your blog loads, and how each section doesn't make another web request

attrutt10 hours ago

Seems like a user problem more than anything else

flohofwoe8 hours ago

It's foremost a naming problem, FixedBufferAllocator doesn't hint that it is actually is a bit of a weird mix of a bump and stack allocator (IMHO if it would be a bump allocator it shouldn't have a free function at all, and for a stack allocator the free function should probably be called pop).

However both doesn't match Zig's expected alloc/free allocator interface, which is an interesting design challenge on its own.

mcherm9 hours ago

Not at all. Viewed one way it isn't a problem at all (the user found and fixed the issue). Viewed another way, it is a flaw in the docs for FixedBufferAllocator that it offers a "free()" call but fails to make clear that this only works when freeing at the end of the allocated region.