[HN Gopher] The curious case of a memory leak in a Zig program
___________________________________________________________________
The curious case of a memory leak in a Zig program
Author : krut-patel
Score : 154 points
Date : 2023-03-19 04:34 UTC (18 hours ago)
(HTM) web link (iamkroot.github.io)
(TXT) w3m dump (iamkroot.github.io)
| Dwedit wrote:
| 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__ wrote:
| 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.
| Jamie9912 wrote:
| I really like how quickly your blog loads, and how each section
| doesn't make another web request
| dundarious wrote:
| 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 https://ziglang.org/learn/
|
| Maybe it's not emphasized enough.
| jmull wrote:
| 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)
| [deleted]
| [deleted]
| olivermuty wrote:
| 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?
| krut-patel wrote:
| 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.
| mirekrusin wrote:
| 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.
| attrutt wrote:
| Seems like a user problem more than anything else
| flohofwoe wrote:
| 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.
| mcherm wrote:
| 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.
| rntz wrote:
| > 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...).
| krut-patel wrote:
| And I am not the only one :)
| https://old.reddit.com/r/Zig/comments/11vbiv1/the_curious_ca...
| gonzus wrote:
| That would be me... Cheers!
| AshamedCaptain wrote:
| 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.
| toxik wrote:
| I feel like this could also be fixed by a simple algorithm to
| keep track of the start index in FixBufAlloc.
| masklinn wrote:
| 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.
| laserbeam wrote:
| > 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.
| 2h wrote:
| > anti-patternic
|
| patternic is not a word.
| dcminter wrote:
| Why? All words are coined at some point.
| smegsicle wrote:
| 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
| 2h wrote:
| well for one, because the correct word "idiomatic" already
| exists:
|
| https://wikipedia.org/wiki/Programming_idiom
| throwawaymaths wrote:
| there'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)
| 2h wrote:
| > anti-patterns
|
| I agree with all that, but patternic is not a word.
| dcminter wrote:
| To you. English has a variety of suffixes that allow for
| exactly this kind of constructive generation of new
| words. Thus 'patternic' is a word precisely because it
| has just been coined. Or do you only ever approve of
| "dictionary" words without pondering where they might
| come from?
| [deleted]
| macintux wrote:
| It is now.
| masklinn wrote:
| 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).
| mort96 wrote:
| 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: https://ziglang.org/documentatio
| n/master/std/#A;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.
| throwawaymaths wrote:
| > 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?
| masklinn wrote:
| > 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.
| mort96 wrote:
| 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.
| judofyr wrote:
| > 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/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.
| [deleted]
| krut-patel wrote:
| 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?
|
| [1]: https://tigerbeetle.com/blog/a-database-without-dynamic-
| memo...
| charcircuit wrote:
| >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.
| kps wrote:
| Zig is a low-level language. You might not have an MMU. You
| might not have a kernel. You might _be_ the kernel.
| charcircuit wrote:
| Maybe if we went back a few decades. But in 2023 having
| access to a MMU and a kernel is normal.
| eatonphil wrote:
| TigerBeetle writes to disk for long-term storage. Data over
| time is the part you can't fit into memory (eventually). :)
| krut-patel wrote:
| > 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 :)
| eatonphil wrote:
| > 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.
| messe wrote:
| 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.
| aserafini wrote:
| Suggestion for the blog post author: make a PR to the Zig docs to
| clarify this if it's not already.
| krut-patel wrote:
| Will do, I have just been procrastinating too much!
| throwbadubadu wrote:
| 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 (:
| shp0ngle wrote:
| There are basically no docs for this allocator.
| masklinn wrote:
| > 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).
|
| 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
| glandium wrote:
| 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.
| Yoric wrote:
| Nit: /last/latest/
| wnoise wrote:
| 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.
| jpcfl wrote:
| 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?
| renox wrote:
| 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.
| jpcfl wrote:
| 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.
| laserbeam wrote:
| 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_ wrote:
| 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.
| mitulvohra wrote:
| 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.
| laserbeam wrote:
| 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.
| masklinn wrote:
| 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
| FixedBufferAllocator
|
| You can probably extend it to
| FixedBufferBumpAllocator
|
| And now the implications are more searchable and clearer.
| ben-schaaf wrote:
| 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.
| throwawaymaths wrote:
| 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.
| mirekrusin wrote:
| 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].
|
| [0] https://ziglang.org/documentation/master/#Choosing-
| an-Alloca...
| vocx2tx wrote:
| 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).
| masklinn wrote:
| 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.
| eternalban wrote:
| You 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/
| vocx2tx wrote:
| > 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 wrote:
| > 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 wrote:
| 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.
| masklinn wrote:
| > 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.
| mort96 wrote:
| 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.
| audunw wrote:
| > It should probably return an error or panic (if free's API
| allows it, I guess).
|
| Then how would you use it in the cases where you want free to
| be a no-op?
|
| I think that's half of the point of the allocator.. free
| shouldn't do _anything_ , certainly not throw an error. You can
| free the buffer behind the allocator later, or for some simple
| command line tools you'll just let the OS free memory when the
| process finishes.
|
| Perhaps some kind of debug message could be OK. Would perhaps
| be nice if you have some problems with allocation, you activate
| debug messages related to allocation, and one of them would be
| "free was called on something other than the last allocation so
| it was ignored"
___________________________________________________________________
(page generated 2023-03-19 23:02 UTC)