Add general purpose allocator(s) to standard library

[PavelVozenilek]

Looking into https://github.com/zig-lang/zig/blob/master/std/mem.zig I decided to describe my own allocator implementation for a C project. I am not proposing anything here, just would like to point out that projects do strange things and language/stdlib should not restrict them.

I decided to avoid the global allocator (malloc/free) and implement my own variant, something what would strongly protect against bugs.

I implemented three allocator variants:

1. Traditional block allocator, based on Doug Lea's malloc. (Btw, this allocator provides very rich API useful for people obsessed with performance, e.g. allocating several blocks at once or freeing multiple blocks at once.)
2. Incrementing allocator. This one dispensed memory carved out from a big block. When that big block got exhausted it allocated new big block. Deallocation was empty operation.
3. Combination of previous ones, incrementing allocator using single big block, if this block got exhausted it switched to fallback block allocator. This was intended as fast allocator but not wasting too much memory in unexpected situations.

Allocator API (implemented with function pointers) had following features:

1. Instead of having alignment parameter I had several functions: alloc1 (no alignment needed), alloc2, alloc4 and alloc (alignment 8). Keeping number of parameters down looked as good tradeoff.
2. Dealloc always had size of the memory to be freed as its second parameter. This number is always know, I never ever saw data of unknown size hanging around. This feature allowed to keep zero overhead for incrementing allocator (in RELEASE), not a single byte wasted on keeping the size.
3. I dropped realloc. It has little use and resizing almost never succeeds in practice.

Every allocator had choice to automatically drop all still allocated data when the allocator itself was destroyed. The other option was to report unfreed data. This reduced the need to implement and invoke destructor-like functionality everywhere.

Allocated blocks were protected in DEBUG mode:

1. Guarding bytes were put before and after the block. Dealloc always checked if these bytes are intact.
2. Validity of size parameter for dealloc was verified.
3. When program was about to end it checked if there was any leftover allocator with unfreed blocks. These were reported.
4. Block allocators could be thread safe or unsafe. Unsafe allocators did verify they are used from the same thread only (with possibility to be "switched" from one thread to other).
5. Newly allocated memory was filled with random bytes.
6. Deallocated memory was also overwritten with random bytes.
7. There was option to put deallocated memory aside, not to reuse it, and later verify that it was not modified after deallocation through a forgotten pointer.

Other features:

1. In DEBUG mode allocated memory kept file + line where the memory was allocated. It also could record complete stack trace (Win32 supports this, it could be done efficiently).
2. Every allocator had option to take existing memory buffer (assumed to be the stack) to serve initial requests. If the buffer was sufficient it could result in zero OS calls.
3. Incrementing allocators could offload large requests to the fallback block allocator. This allowed to return big memory data back to the system immediatelly.
4. Unit tests checked if everything allocated inside a test was also deallocated there. This in practice killed all the leaks.
5. It was possible to check (in DEBUG) whether any given pointer is valid memory block or points inside a valid memory block.
6. It was possible to fine tune allocator parameters (like size of the big block). For this purpose each allocator (in DEBUG mode) collected detailed statistics and could show them on demand (in browser).
7. Each allocator could have hard limit on total number of allocated bytes. This limit could be changed/disabled in runtime. This allowed to have unit tests for low memory situations.
8. It was possible to force any allocator to fail, from outside the application, via browser. This was to find out application response.

Implementation of all this was large, 10k - 20k of lines of code (with tests). But it was probably worth the effort, saving days of frustrated chasing of memory bugs.

[tiehuis]

Nice write up!

I've been thinking about allocators a little bit lately as well and the current API in zig so I might write down my thoughts here as well.

The current allocator interface is restricted to using memory from global state (i.e. from the os or a pre-allocated array as in the debug allocator). If we had a vtable abstraction (see #130) we could extend the types of allocators that could use the same interface. All the following assumes we have a vtable abstraction.

For example, consider a fixed stack allocator which could be useful for a memory limited embedded system. In the current zig we would need to make the array global and set up a unique allocator across the program. With an interface-like abstraction we could generate types of allocators which fit our requirements locally.

// Return a new allocator backed by a fixed array of size n
pub fn FixedAllocator(comptime N: usize) -> Allocator {
    memory: [N]usize,

   // ...
}

A fixed allocator like this would make zig much more suitable for embedded work as having to resort to global memory for allocations is not always wanted.

This could also be used to implement stack-backed up-front memory allocators with pre-defined limits easily too.

var arena_allocator = ArenaAllocator.init(1024 * 1024);
// ... do some work
arena_allocator.deinit();

Getting back to you, I think we can incorporate a lot of these more complex ideas to dedicated allocators as long as we can generate the implementations easily.

Response

Dealloc always had size of the memory to be freed as its second parameter. This number is always know, I never ever saw data of unknown size hanging around. This feature allowed to keep zero overhead for incrementing allocator (in RELEASE), not a single byte wasted on keeping the size.

I think we can possibly follow this example. Since allocators in zig are generally not global (excluding external ones from c) we should always be able to instead store the metadata in some local state instead. In the case that an allocator does use global state (i.e. is a malloc wrapper) then we can just ignore the parameter (pass 0).

I dropped realloc. It has little use and resizing almost never succeeds in practice.

That's interesting, although i suspect that depending on the type of allocator it could become substantially more useful. Falling back to the default alloc -> copy -> free could always possibly be an option, with an implementation providing a realloc function if it can specialize and improve on this.

Allocated blocks were protected in DEBUG mode:
...

All useful tools. I wonder how far we could get with wrapping existing base allocator functions and injecting wrapper code to perform the require task.

For example:

// Takes an allocator return a modified version which zeros memory on free
pub fn ZeroingAllocator(alloc_instance: Allocator) -> Allocator {
    fn free(alloc_instance: &Allocator, memory: []u8) {
        for (memory) |*p| *p = 0;
        alloc_instance.free(memory);
    }
}

7. Each allocator could have hard limit on total number of allocated bytes. This limit could be changed/disabled in runtime. This allowed to have unit tests for low memory situations.

We could expose functions which return modified allocators with the appropriate limits applied. Limiting an allocator would be as easy as calling LimitedAllocator(8192, IncrementingAllocator) or similar.

End

This was a bit of a tangent. I do like a lot of the things you mentioned and would like to keep them in mind. I do really think that some vtable abstraction would make most of these things much easier to use from a user perspective.

[PavelVozenilek]

My allocator is very complex, it took several iterations, some features were eventually even dropped as not worthy the complexity. I do not suggest to adopt it, just point what may happen.

---

Some people like to start project from a clean sheet. I suspect that among those who try completely new language this number is significant.

It would be handy to have mechanisms which allow existing libraries stay usable even in such situation, when someone decides to reimplement basic functionality like the allocator. (Negative example here is C++ which married to stateless STL allocator concept, and if someone wants to change it he needs to rewrite whole STL, like EA had to.)

I have few half baked ideas, like ability to say "use this code if it compiles":
??? logger.log("..."); // if a logger is present in context use it, otherwise ignore the line
or ability of a library to list features it provides, and then let the user select only feature he needs.

[andrewrk]

I just want to say thank you @PavelVozenilek for all these use cases. Zig thrives on use cases. We might say "no" to certain features but we have a responsibility to have a reasonable solution for any valid use case.

[andrewrk]

@bscheinman there are some interesting tidbits here for your information if you're working on that general purpose memory allocator.

[networkimprov]

Possibly of interest? https://github.com/microsoft/mimalloc
Discussion on Hacker News: https://news.ycombinator.com/item?id=20249743

[andrewrk]

Done in #5998, landed in 069a6f2. There are plenty of follow up issues, but we do now at least have a general purpose allocator to use.