8 ms·
The curious case of a memory leak in a Zig program
- glandium 4y agoTL;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.
- Yoric 4y agoNit: /last/latest/
- wnoise 4y agoThat 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.
- jpcfl 4y agoWhat 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?
- Iridescent_ 4y agoBecause 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.
- mitulvohra 4y agoI 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.
- masklinn 4y agoI 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 FixedBufferAllocator You can probably extend it to FixedBufferBumpAllocator And now the implications are more searchable and clearer.
- mirekrusin 4y agoZig 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]. [0] https://ziglang.org/documentation/master/#Choosing-an-Allocator https://ziglang.org/documentation/master/#Choosing-an-Alloca...
- ben-schaaf 4y agoThe 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.
- throwawaymaths 4y agoNo. 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.
- laserbeam 4y agoBump 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.
- renox 4y agoIt'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.
- jpcfl 4y agoThanks. 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.
- laserbeam 4y agoOne 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.
- aserafini 4y agoSuggestion for the blog post author: make a PR to the Zig docs to clarify this if it’s not already.
- krut-patel 4y agoWill do, I have just been procrastinating too much!
- throwbadubadu 4y agoSuch 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 (:
- masklinn 4y 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 (https://github.com/ziglang/zig/issues/3049 https://github.com/ziglang/zig/issues/3049). 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
- shp0ngle 4y agoThere are basically no docs for this allocator.
- olivermuty 4y agoI 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?
- krut-patel 4y agoIn 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.
- mirekrusin 4y agoIt'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.
- judofyr 4y 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": https://github.com/ziglang/zig/blob/8f481dfc3c4f12327499485e3bf10fbbb1023186/lib/std/heap/general_purpose_allocator.zig#L119-L124 https://github.com/ziglang/zig/blob/8f481dfc3c4f12327499485e.... 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-patel 4y agoThanks 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? [1]: https://tigerbeetle.com/blog/a-database-without-dynamic-memory/ https://tigerbeetle.com/blog/a-database-without-dynamic-memo...
- charcircuit 4y ago
- vocx2tx 4y agoAn 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).
- masklinn 4y agoIt’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.
- eternalban 4y agoYou are entirely correct. If anything, if I were the OP the title of the blog would be "Naming matters - The curious case of ..." https://docs.rs/bumpalo/latest/bumpalo/ https://docs.rs/bumpalo/latest/bumpalo/
- vocx2tx 4y 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.
- LoganDark 4y 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.
- throwbadubadu 4y ago
- deleted 4y ago[deleted]
- AshamedCaptain 4y agoI 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.
- masklinn 4y agoThat'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).
- 2h 4y ago> anti-patternic patternic is not a word.
- dcminter 4y agoWhy? All words are coined at some point.
- 2h 4y agowell for one, because the correct word "idiomatic" already exists: https://wikipedia.org/wiki/Programming_idiom https://wikipedia.org/wiki/Programming_idiom
- throwawaymaths 4y agothere's a lot of sunlight between the class of things that are idiomatic and the class of things that are anti-patterns; and there are likely things that are idiomatic but still anti-patterns (yes, you can do this, and if you did this it would look like this, and it causes no regression in this particular case, but don't get in the habit of doing it this way because it can cause a hard-to-spot regression in the general case)
- Jamie9912 4y agoI really like how quickly your blog loads, and how each section doesn't make another web request
- attrutt 4y agoSeems like a user problem more than anything else
- mcherm 4y agoNot 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.
- flohofwoe 4y agoIt'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.
- rntz 4y 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 https://wingolog.org/archives/2022/12/10/a-simple-semi-space-collector https://wingolog.org/archives/2022/12/10/a-simple-semi-space...).
- krut-patel 4y agoAnd I am not the only one :) https://old.reddit.com/r/Zig/comments/11vbiv1/the_curious_case_of_a_memory_leak_in_a_zig_program/jct0ond/ https://old.reddit.com/r/Zig/comments/11vbiv1/the_curious_ca...
- gonzus 4y agoThat would be me... Cheers!
- dundarious 4y agoEvery 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 https://ziglang.org/learn/ https://ziglang.org/learn/ Maybe it’s not emphasized enough.
- jmull 4y agoIMO, 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)
- Dwedit 4y agoPerhaps 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__ 4y agoI 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.
- kprotty 4y agoFixedBufferAllocator is meant to minimally viable like in settings when there's no shared concept of "printing" or an OS for that matter. Check out LoggingAllocator which can take/wrap the former.
- deleted 3y ago[deleted]
- Dwedit 3y agoMaybe put the word "Sequential" in the name (like FixedBufferSequentialAllocator) to really hammer it down that you can't randomly delete. Then also have a movable head pointer so you can still deallocate in either reverse or forward order, it will still successfully free everything.
- deleted 4y ago[deleted]