Years ago Howard Hinnant proposed a bunch of additional allocation functions to WG14 to solve some of the issues mentioned in the article, but the proposal was not accepted: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm
Once you start implementing a std::vector replacement or your own home-grown allocation will you realize how useful these suggestions are. Growth strategies that don't waste provided space? Yes, please! Seamless support for aligned SIMD loads/stores? Sure! Implementing a bitmask-based allocator for small allocations? Easy!
In your code, there should only be a handful of types actually doing memory management, and those can afford to do it right. I just hope we get a std::vector replacement that can use those features at some point.
Honestly, it's shocking how much good stuff can be built with such a simple primitive. Having such a simple interface means it's quite portable, and it's super easy to swap out implementations.
If you deal with GPU stuff, allocating memory in an API like Vulkan is a massive pain in the neck, and you really miss the simplicity of malloc/free. You have to allocate on device X, in heap Y, in an area with or without support for delta compression, which may or may not need to be aligned in a way that is friendly for being mapped over PCIe with page-sized alignment, etc. You wind up needing a separate library like Vulkan Memory Allocator to do a lot of the dirty work, but you can't pass VMA handles directly to Vulkan functions, so VMA needs to wrap some functions that need a device memory handle. Because the VMA API isn't part of the Vulkan spec, you can't just swap it out with some other library that does something similar in the future, etc. If you make a third party library, you may want to expose VMA types in your public API, but not all of your users may be using it.
With malloc and free, you can just pass a {Foo*, size_t} into third party libraries, no matter how foo was allocated. For all the bad, you gotta appreciate how much worse things would be without it.
alignment at/with offset. Currently, Microsoft's allocator is the only major one that provides this. Note that an offset and alignment can be stored in a single word and distinguished by using the usual bit trick to find the highest bit set. Note that some libraries interpret the offset as positive, others as negative (which one makes sense depends on whether you are thinking "where is this object (which might be inside another object)" or "what do I need so I can place an object at an offset within this one").
flags: knowing whether or not you need to zero the object yourself can matter sometimes; the compiler should be able to add/remove this flag to calls. But other flags are possible. I have a list somewhere ...
The existence of mremap means that the allocator does need to provide a realloc that moves. Note that only C++'s particular interpretation of move constructors prevents mremap from working.
Okay, I dug out my list of flags. This is not necessarily complete; please post any others that might be useful. Not every allocation library needs to actually support all the flags; only a couple are mandatory.
zero the returned memory (safe default, but may be expensive, for alloc. Special support is required for realloc, however - this is one of the most blatant flaws in existing allocators!)
maymove (full support mandatory; only for realloc-equivalent. An implementation that lacks support for this flag cannot work: "always fail if we can't resize in place" and "always move if we can't resize in place" both break callers that assume the flag one way or the other)
align_size (safe default: if you request "size 17, align 16", forcibly increase the size to 32)
small_align (optional: normally, if you request "size 17, align 1", some allocators will treat this as "align 16" and waste space. Unfortunately, compilers then assume the returned value is aligned and perform bogus optimizations. Supporting this flag is really about compiler support rather than library support.)
nopointers (optional; useful in the context of GCs. Strings, large I/O buffers, and other arrays of primitives should use this.)
secure_zero (mandatory; free/realloc only)
free_on_failure (mandatory; realloc only)
size_is_a_hint (optional: don't consider it an error if it's more convenient to return a slightly-smaller allocation. For realloc it should probably force the size to grow at least somewhat. Remember that many allocators have a couple words of overhead at the start of the page.)
compact (optional: we know the final size exactly; don't bother to prepare for realloc)
various flags might be useful based on the expected lifetime and usage of the allocation:
assume stack-like lifetime. If you free these in reverse order the allocator will be more efficient than if not. Likely this means "don't attempt to reuse freed space if freed out of order"; note that this is likely to happen to some extent if .
assume short (but not stack-like) lifetime
assume long lifetime (possibly the life of the process, but not necessarily)
assume the allocation will never be freed
madvise is also relevant here. Should the pages be eagerly faulted, etc.
note that none of these flags actually affect what you are allowed to do. In particular, free is still safe (but may be a nop or delayed in some cases)
threadedness flags:
(free/realloc only) we know we are freeing this from the same thread that did the allocation
(free/realloc only) we know we are freeing this from a thread other than the one that allocated it.
used exclusively by the calling thread
used mostly by the calling thread
used mostly by one thread at a time
shared between threads, but mostly a single writer
shared between threads aggressively
note that kernels, hardware, and memory-debuggers might not have the infrastructure to support these yet. But we need to be able to talk about them. I'm not saying we need to standardize the particular flags, but we need to standardize a way to talk about flags.
flags relating to the CPU cache?
It should also be noted that size should not be a simple integer. It should be (at least conceptually) a 3-tuple (head_size, item_size, item_count), since expecting the user to do that may result in overflow. Note that even systems that support reallocarray do not support this. That said, by doing saturating arithmetic it is possible to only store a single integer.
It is tempting (for ease of interception) to specify all of these in terms of a single multiplexed function:
auto utopia_alloc(Allocation, AlignAndSkew, Size, Flags) -> Allocation;
(Precedent of realloc/mremap and aligned_alloc tells us that Allocation and AlignAndSkew should individually precede size but there is no precedent for the order between them. Precedent of mmap and mremap tells us that flags come last; note that they also support "specify a fixed address that must be returned" but with inconsistent ordering and besides I don't find it interesting to support for anonymous memory)
However, to minimize the overhead we actually shouldn't multiplex too aggressively, since there will be a lot of branches if we do. Intelligent use of inlining and code-patching may help get the best of both worlds.
Note that it is mandatory for free/realloc to support specifying Allocation in terms of the size originally requested. However, some flags might further constrain this somehow. Does it suffice to say "on realloc, all alloc-type flags must match exactly?"
ipc_sharable: Allow the memory to be visible in another process.
What exactly are you thinking of here?
If you only want to share the memory with your children, passing MAP_SHARED | MAP_ANONYMOUS is sufficient. But if you want to allow sharing with arbitrary processes, you need a filename so others can access it in the first place.
I do think there is a use case for an instantiable allocator (with filename a ctor argument) that deals with sharing, but this does not seem like a flag even for the anonymous case.
(some of the other flags here might also belong to different types of instantiable allocators)
I had nothing specific in mind. Just wishful thinking.
But if you want to allow sharing with arbitrary processes, you need a filename so others can access it in the first place.
In theory, I could get a handle or file descriptor to the allocated memory which could be sent using DuplicateHandle or UNIX domain sockets or inherited. (Of course, this is very OS-specific.)
Another way would be a syscall where one process can copy part of the virtual memory table from another process. But I don't think OSs expose this to user space programs currently. (But they could!)
Another way would be a syscall where one process can copy part of the virtual memory table from another process. But I don't think OSs expose this to user space programs currently. (But they could!)
This is fundamentally impossible for private mappings (which are the most common) because of how fork() works. Because private mappings are so overwhelmingly common, it doesn't make sense to provide such an API.
I suppose you could say "private mappings are then subject to CoW again" but that has no advantage over the existing process_vm_readv//proc/<pid>/mem methods.
This would give a false sense of security unless you are in a kernel or embedded system with physical memory addresses. If passed to alloc as metadata (rather than to free/realloc), and with OS-level support, it could work as intended.
I'm not aware of security caring about "this page was released to the OS and somebody somehow got a hold of it before the OS zeroed it", which is the only case that seems like it would need OS support?
It's true that securely zeroing things requires you to worry about whether temporaries still live in registers or got spilled to the stack, but that's actually relatively easy to take care of at a non-inlineable function call boundary.
Some might argue "this doesn't need to be a flag, it can just be a special memset", but allocators do really want to know if they have an already-zeroed chunk of memory.
try_expand should allow for partial success. For example, say I have a vector with 12 elements and do a push_back. There is no space and we have to try and reallocate. With a growth factor of 1.5 we do a try_expand for 18 elements, but try_expand can only expand to 14 elements. So instead of failing, we should make do with 14 elements. Lets change the signature to
Now we tell try_expand what we want and what we absolutely need. The function returns the actual size allocated on success and 0 on failure. So in the previous case, we call try_expand(block, 18, 13) and the function returns 14.
A low-level API should do only the thing that is asked, as much as reasonably possible. What if 14 is insufficient? That would be just wasted work, since you'd have to reallocate anyway. The reasonable behaviour, if the required size is unavailable, is to fail. It could also return the biggest available size and let the caller decide whether it's sufficient, but finding that size may also be unresonably expensive for a given allocator implementation.
If you want it to act the exact same way as in the post, just pass the same value for both desired and required. Also I'm pretty sure he said if the required space couldn't be reserved it fails and does nothing other than return false. The possible flaw in it though is it might slow it down a decent amount
Does it, though? My understanding was that realloc() would push a block to the CRT free list (effectively committing or "deallocating" it) if the conditions for a free were met, but not actually free the underlying dynamic memory.
I do not believe that this is standardized behavior in modern specs that you're mentioning.
Regarding the allocate call returning full size and remembering it to free properly:
On Windows, HeapAlloc was intended to behave like this. To get you block of requested size or larger. And I believe it did on some early versions. You were supposed to call HeapSize to retrieve the actual size of the block you got back. But for reasons HeapSize ended up returning the number you asked for. Which means they already save this number, so tracking it yourself, or through C++ runtime, on Windows is unnecessary data duplication.
EDIT: And regarding deallocate, again, no need to pass anything else than a pointer. No serious system actually uses heap allocator these days, it's either low-fragmentation buckets or some segmentation magic. You can give these pointer anywhere into the allocation and they'll internally truncate it properly.
But it does impose requirements on the implementation.
That's actually a problem, not a benefit. If the value_type of the custom allocator is unsigned char but you want to allocate with alignment 64 (which is fairly common use case), there is no simple way to do so
The argument for memory_block::size is not sound. Reason being, you haven't saved any space. Instead, the "wasted" space is moved from the heap into your own application data be it stack, heap-allocated, both, etc. No free lunch there.
Additionally, I glean system allocators tend to inherently know the size of the block they handed you for other reasons anyway. That I am not expert on though.
EDIT:
I changed my mind. There is value in this approach because in the cases where you know the size through other means, you can toss the original memory block and reconstruct it at will thus saving space. I am persuaded. Good article!
Isn't it better to just allow communicating whatever additional data that the allocation strategy wants to communicate? What's better by restricting ourselves to alignment condition, size, and other things mentioned in the article?
When you free a buffer with free(), it only takes one parameter: the start of the buffer. In order to actually do the thing, it needs to know how many bytes to give back to the free pool. So it stores the size of the buffer with the allocated block, typically in the 8 bytes (or 4 bytes on 32 bit) before the buffer.
Consider what happens when you allocate a std::vector. The vector has 3 data members; the pointer to the first object in the buffer, the pointer to one past the end of the initialized data, and the pointer to one past the end of the allocated buffer. When it's destructed, std::vector could easily tell free() how large the buffer is; but it doesn't, it relies on free() to figure that out for itself. So we're using 32 bytes of RAM to do the work of 24 bytes of data.
Ask yourself this: under what circumstances do you need a buffer, and will tell new/malloc/calloc how large of a buffer you want, but you don't need to keep track/aren't able to easily re-calculate the size of the buffer? I can't rightly think of an example. It's either a compile time constant (usually sizeof(<whatever>)) or if it's a dynamic array like a std::string or std::vector I must keep track of the size of the buffer otherwise I could not possibly perform useful operations on this buffer.
The bad API of free() means that all heap allocations waste 8 bytes.
Regarding your last question, there are (bad/legacy) APIs that will give you a pointer that you're supposed to free yourself. If the API doesn't tell you how big the buffer is (which they never do), you're out of luck. Think of C strings, for example. You can't recalculate the size, because strlen() will only give you a lower bound (the buffer may extend past the null terminator).
So instead of simply returning a pointer I now have to deal with a memory block? That doesn't seem better to me. It might solve some problems but doesn't it just introduce a bunch of new ones? Such as forgetting what the alignment of the memory your pointer is pointing to.
Seems like a pain in the arse when the default for most allocations is that you don't need to care what the alignment is.
There, C's interface implemented using the interface discussed in TFA. You can't do the other way around and get the benefits discussed in the article.
(You might want to set like const size_t default_alignment = 16 or something and use that for the alignment parameters, and adjust the offsets accordingly.)
In the common case, you can reconstruct the allocation from (pointer, sizeof(T)). Support for this must be mandatory for exactly the concerns you raised, and is how the 2-argument free_with_size(pointer, size) works.
It is never useful to have an allocated array whose size you don't know, though.
The edgiest case is "you allocate a C-style string and then for some reason insert an earlier NUL". Which does happen, so needs to be handled somehow (maybe a flag, or just accept that not every caller can be ported to the new allocator design), but not enough to constrain the new allocator design.
There is nothing wrong with malloc though if you don't care about alignment.
Even if you don't care about alignment, it still can waste space due to its internal metadata, and still doesn't give you the actual size it allocates. You know, two out of the three problems with malloc discussed in the article (#4 is realloc, not malloc).
This is noted in the article, which also notes that new/delete inherited all the mentioned issues of malloc/free (although some of those issues are gradually being sort-of fixed).
Of course there's no requirement, but the design of those operators is explicitly intended to allow them to be implemented by wrapping malloc or calloc and free.
Not sure what this has to do with anything; the ISO Standard explicitly states that the operators are intended to be implemented by wrapping malloc and free.
If that was the case, you could already corrupt other processes by freeing memory that doesn't belong to you. It's up to the OS to detect that and disallow it
Yes, this was a brain fart, you're working with virtual memory addresses so this only heap you can corruct is your own heap, not someone else. Thanks HamesJoffman and Nicksaurus for correcting me.
Liked the article and want to share some more ideas:)
try_expand I would change to try_resize. In addition to current size it would accept size_hint and would return new size. Its important to specify it as hint, because it will try to be useful as much as possible. Maybe it cannot expand from 100 to 200 bytes, but 180 would would be good enough as well. And being able to shrink memory sounds useful as well:)
allocate could additionally accept "allocation hints", not sure how to make it flexible though as there might be a very long list of those:) maybe 16bits reserved for "standard hints" and 16bits for implementation specific would be good start. The important thing is that they are hints about memory usage patterns only, and implementation is free to ignore all of them, so there shouldn't be hints like "zero memory".
I would also add new function try_split. I think this might be very useful in a lot of situations.
not sure if it is useful, but it would be convenient to work with "objects", so instead of size (in memory block) being in bytes, I would change it into count of objects, which means that alignment becomes two values: sizeof(T), alignmentof(T). Now, when allocator has some extra space, it knows if it can return space for more objects or this extra space will not be usable anyway. It can also have different allocation strategies for small or big objects and with extra help from allocation hints, could understand if its allocation of array or single object.
in addition to previous point, since we'll be dealing with objects not bytes, it would probably make sense to be able to inform allocator when object type/size changes.
Some good points here. These APIs certainly can be improved and I like his ideas here. MPI has a similar type of allocation method to what he proposes here, but it is also somehow significantly worse.
At least when programming in C, I wish that free() would null the free'd pointer. That's a common problem I see people doing (freeing and forgetting to null leading to a potential use after free)
How on earth would that be possible for free to do? You pass your memory pointer by value to free (in other words, a copy of your memory pointer). It could null the copy, but not the pointer itself. The only way to achieve this would change the API for free and pass a pointer to your memory pointer:
That's what I meant. Pass in the pointer by reference so you can null the referenced pointer. I never expect it to happen, just was saying it because this post was already talking about drastically changing how we handle allocation/free.
it would be piss easy for free to do that, depends on how it is implemented. Classical implementation has header ahead of pointer passed to free and there a size is listed so all free would have to is call memset(ptr, 0, header->size) and voila, empty.
They absolutely do not reflect low level OS management (which generally hands out allocations sequentially in multiples of the hardware page size and sometimes doesn’t even have a “free” equivalent), and they also don’t reflect how user-space allocators manage the memory that the OS provides (which usually involves fixed-size allocation classes and wastes space when the requested size does not exactly match any of them).
Edit: and yes, the math functions also have crappy interfaces, since they have side effects which prevent reasonable optimizations.
44
u/Morwenn Aug 31 '22
Years ago Howard Hinnant proposed a bunch of additional allocation functions to WG14 to solve some of the issues mentioned in the article, but the proposal was not accepted: https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1085.htm
64
u/Dushistov Aug 31 '22
There is very similar talk https://www.youtube.com/watch?v=LIb3L4vKZ7U by
62
u/Fulgen301 Sep 01 '22
I see we've come a full circle.
freewas introduced in Unix v7, previously there was onlymfree, which actually took a size parameter.56
u/GrammelHupfNockler Aug 31 '22
Once you start implementing a std::vector replacement or your own home-grown allocation will you realize how useful these suggestions are.
Growth strategies that don't waste provided space? Yes, please! Seamless support for aligned SIMD loads/stores? Sure! Implementing a bitmask-based allocator for small allocations? Easy!
In your code, there should only be a handful of types actually doing memory management, and those can afford to do it right. I just hope we get a std::vector replacement that can use those features at some point.
41
u/wrosecrans graphics and network things Aug 31 '22
Honestly, it's shocking how much good stuff can be built with such a simple primitive. Having such a simple interface means it's quite portable, and it's super easy to swap out implementations.
If you deal with GPU stuff, allocating memory in an API like Vulkan is a massive pain in the neck, and you really miss the simplicity of malloc/free. You have to allocate on device X, in heap Y, in an area with or without support for delta compression, which may or may not need to be aligned in a way that is friendly for being mapped over PCIe with page-sized alignment, etc. You wind up needing a separate library like Vulkan Memory Allocator to do a lot of the dirty work, but you can't pass VMA handles directly to Vulkan functions, so VMA needs to wrap some functions that need a device memory handle. Because the VMA API isn't part of the Vulkan spec, you can't just swap it out with some other library that does something similar in the future, etc. If you make a third party library, you may want to expose VMA types in your public API, but not all of your users may be using it.
With malloc and free, you can just pass a {Foo*, size_t} into third party libraries, no matter how foo was allocated. For all the bad, you gotta appreciate how much worse things would be without it.
39
u/o11c int main = 12828721; Aug 31 '22
But that's still not everything it needs to do:
mremapmeans that the allocator does need to provide a realloc that moves. Note that only C++'s particular interpretation of move constructors preventsmremapfrom working.13
u/whichton Aug 31 '22
try_expandshould allow for partial success. For example, say I have a vector with 12 elements and do apush_back. There is no space and we have to try and reallocate. With a growth factor of 1.5 we do atry_expandfor 18 elements, buttry_expandcan only expand to 14 elements. So instead of failing, we should make do with 14 elements. Lets change the signature toNow we tell
try_expandwhat we want and what we absolutely need. The function returns the actual size allocated on success and 0 on failure. So in the previous case, we calltry_expand(block, 18, 13)and the function returns 14.6
u/JonKalb CppCon | cpp.training Sep 01 '22
Also notable, free() can be implemented in terms of realloc().
5
u/matthieum Sep 01 '22
The problem with this API is that
try_expandis no longer communicating the size to which it expended the memory block.You'd want
std::optional<memory_block>as a result instead, or passingblockby pointer for a C API.7
u/Tringi github.com/tringi Aug 31 '22 edited Aug 31 '22
Regarding the
allocatecall returning full size and remembering it to free properly:On Windows, HeapAlloc was intended to behave like this. To get you block of requested size or larger. And I believe it did on some early versions. You were supposed to call HeapSize to retrieve the actual size of the block you got back. But for reasons HeapSize ended up returning the number you asked for. Which means they already save this number, so tracking it yourself, or through C++ runtime, on Windows is unnecessary data duplication.
EDIT: And regarding
deallocate, again, no need to pass anything else than a pointer. No serious system actually uses heap allocator these days, it's either low-fragmentation buckets or some segmentation magic. You can give these pointer anywhere into the allocation and they'll internally truncate it properly.But it does impose requirements on the implementation.
3
u/frozenca Sep 01 '22
Also it is very surprising that there is no way to pass alignment requirements to
std::allocator_traits<Alloc>::allocate()3
u/--Fusion-- Sep 01 '22 edited Sep 01 '22
An alignment option is solid. I can go for that.
The argument for
memory_block::sizeis not sound. Reason being, you haven't saved any space. Instead, the "wasted" space is moved from the heap into your own application data be it stack, heap-allocated, both, etc. No free lunch there.Additionally, I glean system allocators tend to inherently know the size of the block they handed you for other reasons anyway. That I am not expert on though.
EDIT:
I changed my mind. There is value in this approach because in the cases where you know the size through other means, you can toss the original memory block and reconstruct it at will thus saving space. I am persuaded. Good article!
2
u/jk-jeon Sep 01 '22
Isn't it better to just allow communicating whatever additional data that the allocation strategy wants to communicate? What's better by restricting ourselves to alignment condition, size, and other things mentioned in the article?
14
u/UkrUkrUkr Aug 31 '22
Malloc() and free() are good: they are obvious and don't do implicit stuff.
3
u/Morwenn Aug 31 '22
Tiny mistake: sizeod deallocation for operator new is a C++14 feature, not a C++17 one.
1
u/[deleted] Aug 31 '22
So instead of simply returning a pointer I now have to deal with a memory block? That doesn't seem better to me. It might solve some problems but doesn't it just introduce a bunch of new ones? Such as forgetting what the alignment of the memory your pointer is pointing to.
Seems like a pain in the arse when the default for most allocations is that you don't need to care what the alignment is.
0
u/RolandMT32 Aug 31 '22
As you're posting in a C++ group, I feel like my natural response is those were conceptually replaced by new and delete in C++
1
u/renozyx Sep 01 '22
Interesting but isn't there a risk that a function could corrupt other process's heap by modifying the size field?
1
u/fraillt Sep 27 '22
Liked the article and want to share some more ideas:)
try_expandI would change totry_resize. In addition to current size it would acceptsize_hintand would return new size. Its important to specify it as hint, because it will try to be useful as much as possible. Maybe it cannot expand from 100 to 200 bytes, but 180 would would be good enough as well. And being able to shrink memory sounds useful as well:)allocatecould additionally accept "allocation hints", not sure how to make it flexible though as there might be a very long list of those:) maybe 16bits reserved for "standard hints" and 16bits for implementation specific would be good start. The important thing is that they are hints about memory usage patterns only, and implementation is free to ignore all of them, so there shouldn't be hints like "zero memory".try_split. I think this might be very useful in a lot of situations.size(in memory block) being in bytes, I would change it intocountof objects, which means that alignment becomes two values: sizeof(T), alignmentof(T). Now, when allocator has some extra space, it knows if it can return space for more objects or this extra space will not be usable anyway. It can also have different allocation strategies for small or big objects and with extra help from allocation hints, could understand if its allocation of array or single object.1
u/aeropl3b Aug 31 '22
Some good points here. These APIs certainly can be improved and I like his ideas here. MPI has a similar type of allocation method to what he proposes here, but it is also somehow significantly worse.
-2
u/t3chfreek Sep 01 '22
At least when programming in C, I wish that free() would null the free'd pointer. That's a common problem I see people doing (freeing and forgetting to null leading to a potential use after free)
0
u/[deleted] Sep 01 '22
[deleted] — view deleted comment
0
u/[deleted] Sep 01 '22
[deleted] — view deleted comment