A more Rigorous specification for the Allocator interface.

[flysand7]

Tangentially related: #957

Motivation

For the past couple days I've been cooking up a PR that documents the core:mem package as a whole and fixes the issues with implementations of various allocators I could find. Upon analysing the source code for the existing implementation of allocators I've identified a few issues related to consistency of implementation between different allocators. Excluding obvious bugs we have the following consistency problems:

1. Behavior upon calling allocator procedure with uninitialized data.

This affects the following allocators: Arena, Scratch, Stack, Small stack, Dynamic Arena (Also known as Dynamic_Pool), Buddy allocator (basically all of them). The following behaviors are currently present in mem package (links point to relevant source code lines in the master branch):

• Arena: No explicit action
• Scratch: Attempt to initialize itself using context.allocator
• Stack: Returns .Invalid_Argument
• Small stack: Returns .Invalid_Argument
• Dynamic arena: Panic
• Buddy allocator: No explicit action

There is no clear rule made for whether an uninitialized allocator should return an .Invalid_Argument error or panic, where as I would argue, calling an allocator function without an initialization of allocator's backing storage should be either an panic or a manifestation of the rule of "making zero value useful", i.e. to initialize the uninitialized allocator upon first allocation request.

2. Changing the allocation's alignment

Someone happened to ask recently over discord, whether it is possible to use realloc to change allocation's alignment. The first answer they received was that it technically should be possible, but in reality some allocators do not handle this case or the behavior is unreliable at best.

For example, the scratch allocator does not handle this case due to an early return:

Odin/core/mem/allocators.odin

Lines 264 to 278 in e72d0ba

	case .Resize, .Resize_Non_Zeroed:
	begin := uintptr(raw_data(s.data))
	end := begin + uintptr(len(s.data))
	old_ptr := uintptr(old_memory)
	if begin <= old_ptr && old_ptr < end && old_ptr+uintptr(size) < end {
	s.curr_offset = int(old_ptr-begin)+size
	return byte_slice(old_memory, size), nil
	}
	data, err := scratch_allocator_proc(allocator_data, .Alloc, size, alignment, old_memory, old_size, loc)
	if err != nil {
	return data, err
	}
	runtime.copy(data, byte_slice(old_memory, old_size))
	_, err = scratch_allocator_proc(allocator_data, .Free, 0, alignment, old_memory, old_size, loc)
	return data, err

Same with stack and small stack:

Odin/core/mem/allocators.odin

Lines 431 to 433 in e72d0ba

	if old_size == size {
	return byte_slice(old_memory, size), nil
	}

All allocators that use default_resize_bytes_align (arena, stack, small )also do not handle this case if size == old_size, due to an early return:

Odin/core/mem/alloc.odin

Lines 240 to 242 in e72d0ba

	if new_size == old_size {
	return old_data, .None
	}

3. Lack of documentation / trust in the interface

Currently there is no documentation surrounding the Allocator API. As such there can be no reasonable expectations as to what is and what isn't allowed on the other side of the interface, as it should be evident from the two examples above.

For example it is not made clear that a lack of error in the alloc() procedure does not mean that the allocated memory can be dereferenced, because the nil allocator returns nil pointers without an error. It is not made clear that Resize with specific arguments must act like Free or Alloc. There's no one to say that query_features can't return the .Mode_Not_Implemented error.

These are purely issues born out of the lack of documentation. And although many of us would consider these things obvious, or at least, obvious by reading the source code, the documentation needs to be a little bit more rigorous when it comes to saying what is and isn't allowed/expected from an allocator implementation.

The proposal

As such this is a proposal for the allocator interface that attempts to capture and expand upon existing implementation. If implemented, it would affect the documentation and implementation of specific allocators, which might be implemented as part of #4209 or otherwise.

---

Implemented modes

At the bare minimum, the allocator must support the following modes and is not allowed to output the .Mode_Not_Implemented error:

• Alloc, Alloc_Non_Zeroed
• Resize, Resize_Non_Zeroed
• Query_Features

If the allocator does not have a meaningful way to resize an allocation, the default implementation should be used (default_resize_bytes_align). Allocators not designed for allocating memory (such as the nil allocator and the panic allocator) are excempt from this rule.

The modes available for querying: Free, Free_All, Query_Info. Other modes will be unavailable for querying on an API level. Alloc will not be an allocator "feature", but rather it's "function".

Initialization

The allocators must be initialized before the first call to any of the allocation functions. Allocators that use a backing allocator to store data, or do not require a backing buffer (such as nil allocator, panic allocator, scratch allocator) may be excempt from the rule. Not initializing the allocator before use should result in a panic.

Non-zeroed modes

The non-zeroed modes must not explicitly zero-initialize any new memory. This requirement is currently violated by a few allocators. If the allocator uses a backing allocator, it must also ask the backing allocator to allocate non-zeroed memory during non-zeroed operations.

Resize implementation

The following parameters are used in a resize operation:

old_memory: rawptr,
old_size: int,
new_size: int,
alignment: int = DEFAULT_ALIGNMENT,

The resize operation must behave as follows (order of checks applies):

1. If old_memory is nil, it should behave just like `alloc(new_size, alignment)
2. If new_size is 0, it should behave just like free(old_memory, old_size)
3. Otherwise the buffer is resized in such a way that it has a new size new_size and alignment alignment.

Notes:

• If old_memory is nil and new_size is 0, realloc should be a no-op.
• If old_size parameter is less than or equal to 0, the allocator assumes an allocation with unknown size. If the allocator requires a size to reallocate an allocation, .Invalid_Argument error must be returned.
• If old_size parameter is greater than 0, the allocator has sufficient metadata to tell the allocation's size from a pointer, and the two sizes are not equal, the .Invalid_Argument error must be returned.
• During (3), If old_memory is not aligned on a boundary specified by alignment, the buffer needs to be moved in such a way that it is aligned.

Alloc implementation

The following parameters are used in an alloc operations:

new_size: int,
alignment: int = DEFAULT_ALIGNMENT,

The following rules apply:

• Implementation can assume the alignment is always a power of two.
• If the new_size is 0, the operation is a no-op.
• If the alignment can not be satisfied, an .Invalid_Argument error should be returned.
• If the allocator does not have enough space to hold a new allocation, .Out_Of_Memory error is returned.

Free implementation

The following parameters are used in a free operation:

old_memory: rawptr,
old_size: int,

The following rules apply:

• If old_memory is nil, the operation is a no-op.
• If old_memory is outside of allocator's backing storage, the .Invalid_Pointer error should be returned.
• If the allocator can stores sufficient allocation metadata, and old_memory is not a valid allocation, the .Invalid_Pointer error should be returned.
• If old_size parameter is less than or equal to 0, the allocator assumes an allocation with unknown size. If the allocator requires a size to free an allocation, .Invalid_Argument error must be returned.
• If old_size parameter is greater than 0, the allocator has sufficient metadata to tell the allocation's size from a pointer, and the two sizes are not equal, the .Invalid_Argument error must be returned.

Affected functionality

• default_resize_bytes_align will see a change where it would check for whether a pointer is aligned to the new alignment, and if not, it will reallocate the memory.
• Scratch allocator, stack alllocator, and small stack allocator will see a change in their resize mode where a check for alignment would be made.
• Allocators will have bugs fixed where an explicit zero-initialization is made within certain non-zero allocation modes.
• Additional checks need to be inserted in certain allocators.

Pretty sure that's it. This proposal tries to capture existing implementation without having to reimplement anything. It is the as strict as I can define the allocation interface without having to change too much.

---

The linked discussion #957 has an interesting suggestion that removes the need for alloc and free modes in the allocation procedure. However in practice, it doesn't make a difference, especially with the changes from #4209, where the allocation procedure does a switch statement and calls respective functions.

[flysand7]

cc @gingerBill @Kelimion @laytan need some feedback.

[Yawning]

Off the top of my head, since I also have been looking at this for a "stupid pet project":

• Some if not all allocators currently assert if the alignment requested is not a power of 2. Should this be codified as a genral requirement (I lean towards yes).
• I interpret "The non-zeroed modes must not explicitly zero-initialize any new memory." as "It is ok that the allocator happens to return zeroed memory, as long as the allocator implementation itself is not clearing said memory", is this the correct reading of that phrase?

[flysand7]

Some if not all allocators currently assert if the alignment requested is not a power of 2. Should this be codified as a genral requirement (I lean towards yes).

Alocators should assert that the alignment is a power of two, but the point is to say that when a user calls an allocation function they shouldn't pass anything other than a power of two. I think having all allocators explicitly asserting po2 alignment is good for this purpose.

"It is ok that the allocator happens to return zeroed memory, as long as the allocator implementation itself is not clearing said memory", is this the correct reading of that phrase?

Yes. I.e. non-zero mode of a hypothetical VirtualAlloc allocator will return zeroed-out memory, and there's nothing to be done about it. The idea is to not avoid extra calls to memset with those situations.

[laytan]

At the bare minimum, the allocator must support the following modes and is not allowed to output the .Mode_Not_Implemented error

I disagree, enforcing .Alloc_Non_Zeroed and .Query_Features is fine I think, but more than that not, .Free_All can't be implemented by the heap allocator already, .Resize can be queried and emulated with a .Alloc, copy and .Free in a layer on top, that emulation is already done here:

Odin/base/runtime/internal.odin

Line 176 in e72d0ba

_mem_resize :: #force_inline proc(ptr: rawptr, old_size, new_size: int, alignment: int = DEFAULT_ALIGNMENT, allocator := context.allocator, should_zero: bool, loc := #caller_location) -> (data: []byte, err: Allocator_Error) {

Even .Alloc could be implemented on a layer on top by first querying if it is supported and then otherwise doing .Alloc_Non_Zeroed and zeroing it.

An additional thing we should do if we enforce a feature, is not allowing it to be queried (because it is enforced to be there).

The resize operation must behave as follows (order of checks applies):

Also don't think this is needed because all the actual resizes usually go through that function I linked which enforces those things. Although it may be good to also have the right behaviour when you just call the allocator function directly, but it does seem like the same logic in two places.

Not initializing the allocator before use should result in a panic.

This goes against the ZII that we go for in Odin, + currently the default temp allocator being initialised only on first use saves that first memory block from being allocated for programs that don't use it.

If old_size parameter is 0

I would make that <= 0

Additionally you should probably define what happens in .Resize when old_size is <= 0 too.

Another tricky thing with .Resize without a correct old_size, is that you can't just allocate a new region, copy, and free the old region (because you don't know how much to copy).

[flysand7]

.Free_All can't be implemented by the heap allocator already

That's a major oversight. Yes, we don't want to enforce that then.

.Alloc_Non_Zeroed

Actually this is a good point, maybe the allocation procedure doesn't need .Alloc mode. We only do non-zeroed verisons and the wrapper layer on top would zero-out the resulting memory. What are your views on that?

.Resize can be queried and emulated with a .Alloc, copy and .Free in a layer on top [...]

My perception is that it's the allocation procedure that is responsible for saying how resize is implemented, which is either the default implementation, or a custom one. Which is to say that the implementation should say what it is. Do you suggest that an allocator should return mode not implemented and the wrapper functions would understand that the allocator needs a default implementation provided for it?

[flysand7]

An additional thing we should do if we enforce a feature, is not allowing it to be queried (because it is enforced to be there).

Good catch, that would also help the API

[flysand7]

This goes against the ZII that we go for in Odin, + currently the default temp allocator being initialised only on first use saves that first memory block from being allocated for programs that don't use it.

This only applies to allocators that use a static backing buffer, such as an arena, a stack or a buddy allocator (iirc). The default temp allocator in Odin allocates memory from a backing allocator and as such does not to be default-initialized.

I don't really want to go into the territory of "if the arena has no backing buffer when you ask to allocate memory, a default one will be allocated using context.allocator. That seems fishy

[flysand7]

The resize operation must behave as follows (order of checks applies):
Also don't think this is needed

No, it is needed. The default resize operation is not the only one, and if the allocator specifies its own resize procedure (like in the case of stack), it needs to adhere to the same rules as the default one.

[flysand7]

Another tricky thing with .Resize without a correct old_size, is that you can't just allocate a new region, copy, and free the old region (because you don't know how much to copy).

This should be the same as free, I'll fix it.

[laytan]

Something to mention is that @Feoramund did this sort of thing with the io.Stream interface a bit ago here: #4112

A test suite like that is something we should have for this too.

[Feoramund]

I've wanted to write a general-purpose test suite for allocators for a while now. They lend themselves easily to generalized testing just like io.Stream because of their feature-query interface.

[flysand7]

That would be great actually, interface tests are good

[Feoramund]

If I were to have a go at writing an Allocator test suite, I'd wait until your PR is finished and the details in this discussion are hammered out, just so we're all on the same page as to how things should be.

[flysand7]

Alright, the PR is merged, we'll still have to have some discussions I guess, right? I'll look into implementations of all allocators and make some notes about whether or not they implement the interfaces correctly and possibly raise some topics for discussion.

[Feoramund]

There was an issue recently (#4195) demonstrating the Dynamic_Pool allocator which has enforced alignment. This made me wonder if we should provide Allocator-type allocators for those sort of allocators, i.e. the ones that have special requirements such as pools where every allocation is the same size, if we should have a different interface entirely (just a handful of procs and a struct), or just not provide specialized allocators like that at all.

[flysand7]

Dynamic pool is an arena, not a pool. It is a misnomer. As far as I know, Odin doesn't have pool allocator in mem.

[laytan]

IMO we should not have allocators that do not take the requested alignment into account at all, these should be fixed or removed.

[flysand7]

How about returning Invalid_Argument if the alignment doesnt match the initial alignment, for those cases that can't be fixed?

[Kelimion]

We also need to define whether free_all is supposed to only free the allocations made on this allocator, or if it is additionally expected to free its own backing allocations, if applicable.

[Feoramund]

My first thought is that the Free_All available from the interface frees all of the allocations made on the interface, and the allocator-specific destroy is the proc that would take care of the backing allocations.

[flysand7]

The way I think about it is that Free_All is used to clean up all of the allocations, in case you want to make more allocations. The typical example is an arena or a dynamic arena.

To highlight the important part, the point is that you might continue doing allocations afterwards. Whereas with destroy you don't intend on doing any further allocations, it's a way of saying that you're done with it.

As to what is expected to be free'd, I'd say whatever makes the most sense, which is usually, to free all of the data of the allocator and reset the state to an initial state with the minimum amount of work. This does include freeing the backing allocators, if that means freeing allocations. Doing otherwise may feel non-sensical for some allocators, such as a mutex allocator that doesn't have it's own memory and the backing allocator is it's only real way it allocates memory. So free all for mutex allocator should do a serialized call to free_all.

[flysand7]

Speaking of this, dynamic arena seems to have a different idea of what the two mean. It has a reset function that frees all allocations, except for unused blocks, and free_all frees unused blocks too. Not sure that's right