> so alloc() doesn’t just need to hand back a pointer. it needs to hand back a pointer that’s correctly aligned for whatever type the caller is about to store there.
Malloc doesn't know the required alignment (because has no idea what the type is, everything is cast through void). So all malloc implementations have a minimum alignment guarantee. Typically 16 bytes these days on x86, as that means even 128bit SSE values will end up aligned by default.
You couldn't go below the sizeof(void ) anyway, the backpointer needs to aligned too.
The padding only happens when you use memalign or aligned_malloc to specify a much larger alignment.
> So all malloc implementations have a minimum alignment guarantee. Typically 16 bytes these days on x86
Fun story. Back in the early 2000s, my Delphi OpenGL program randomly crashed when I tried to use vertex buffers. I spent a lot of time checking this and that, before I realized it might be an alignment issue.
Sure enough, Delphi memory allocator at the time only provided 4-byte alignment, while NVIDIA's drivers used aligned SSE instructions which require 16-byte alignment.
So, had to manually align the buffers before passing them to OpenGL.
IMO that sounds either like a bug in Nvidia's drivers (IIRC OpenGL doesn't require that sort of alignment) or -more likely- your code having some other memory related-bug (e.g. accessing data out of bounds) that the extra bytes you got from alignment masked it.
Nah it was definitely NVIDIA's fault. As you say there's nothing in the specs about alignment of those buffers, so they shouldn't be using aligned load instructions.
However Microsoft's malloc at the time was indeed returning 16-byte aligned buffers so they probably didn't notice it in internal testing.
There is no reason an allocation needs to contain any inline metadata. And even if it does, the allocator could choose to make it unalined, and pay the cost of an unalined access on de-allocation.
But most C code out there assumes malloc will always return something that is at least aligned to sizeof(void *), it's very rare to see aligned_alloc. So how is your alloc allocation going to know when it can get away with a smaller alignment?
Even if you are on a cpu that doesn't fault on unaligned memory access, any malloc implementation that doesn't align by default will have serious disadvantages in any benchmarks. IMO, There is no good reason to use an unaligned backpointer.
Yes, large allocations need to be aligned to `alignof(max_align_t)`. But small allocations could have a smaller alignment. For example a single byte allocation can actually be a single byte with no alignment, since types can't have an alignment larger than their size.
This is explained in TFA, where it is mentioned that you can replace inline metadata with a pointer to metadata (or an index), which may be unaligned, if necessary.
However, the pointer to metadata is not really necessary.
The associated metadata could be stored in a table, and the index of the metadata could be computed from the offset of the pointer returned by malloc to the start of the heap (possibly using a hash function).
The ancient versions of the Microsoft C/C++ compilers were using a malloc with inline metadata. I have no idea if they replaced this more recently.
That's a good point, and I could have worded that better. What I implemented accepts an explicit alignment parameter because it made the allocator easier to explain. A real malloc() only guarantees alignment suitable for any object type (typically alignof(max_align_t)), since it has no idea what the caller will store there.
There are two types of load/store instructions, one type requires alignment (vmovdqa), the other can load unaligned data (vmovdqu), in the case of AVX-512 the required alignment is 64 bytes. I assume aligned loads and stores are faster/have lower latency. For SSE/AVX you can look up the alignment requirements in Intel's intrinsics guide [0].
I used the compiler's __builtin_add_overflow in order to deal with that issue in my memory allocator. At this point I'm probably on track to replace every arithmetic operator in the entire codebase with those things.
[ Header ][ ...variable padding... ][ Back Pointer ][ User Memory ]
^ always exactly sizeof(void*)
bytes before User Memory,
no matter how much padding
came before it
and then it says we don't need to align the back pointer and we end up with
[ Header ][ Back Pointer ][ Padding ][ User Memory ]
without a clear explanation of how we now get to the back pointer if it's behind the variable alignment.
Old magazines like The C/C++ Users' Journal and DDJ used to have ads for companies selling malloc()/free() replacement libraries, exactly because a single implementation isn't adequate to all scenarios.
These still exist, like dlmalloc, jemalloc, tmalloc (which has new features). Built-in malloc is good enough for almost everything if you don't have excessive time on your hands, but thinking deeper about memory allocation is one of those things that can make your software higher quality if you have time for it—just like utilising SIMD (also on today's front page) or careful use of caching.
Alternative allocators could make a huge difference to the runtime performance. When multithreading on real multiprocessor systems started to become a thing it was common that all your carefully written threads ended up waiting on the allocator mutex. The win32 heap was particularly prone to this.
Third party allocators improved on this as well as usually avoiding the heap fragmentation problems that system heaps often suffered from back then.
These days the system heaps have improved to a point where you really only need to think about a third party heap for very specialized circumstances. They do usually come with nifty debugging tools though.
I've read some allocator walkthroughs before but I thought that this line stood out:
"to get individual free() working, the allocator needs to remember something about every allocation it handed out. and that’s the moment metadata stops being optional."
That's just a very nice distillation of an important concept.
This becomes particularly important when the allocation and metadata cannot (or should not) be stored in the same address space. An example of this is allocating memory on GPUs.
The conventional approach for allocating memory on GPUs for games and other applications is to use a real-time allocator such as TLSF. However, it is not usually discussed that TLSF is real-time because it stores metadata in-band. It is possible to create a variant of TLSF that preserves its real-time properties while storing metadata out-of-band, but this requires careful consideration.
If you can convince the caller to keep track of that metadata themselves you obviously don’t need to. That can be important.
Something I noticed is that _very often_ the code that is calling malloc(n) is keeping track of n somehow for its own reasons (bounds checking, grow/gap pointers, etc) so merging the value halves stack churn and it’s an easy win.
Well, even that doesn't really work, because optimized allocators typicallly don't allocate exactly the amount that you ask for, they allocate some larger chunk to help with both alignment and fragmentation.
So, most likely, there are two sizes in reality: the size of your user data that you care about; and the size of the memory chunk in which your user data resides, that free() cares about. So, unless you're willing to go for an API like this, you can't rely on the consumer:
int* ptr_to_dest = NULL;
size_t size = 10 * sizeof(int);
size_t allocated = malloc(&ptr_to_dest, size);
if (allocated <= 0 || !ptr_to_dest) {
//handle allocation error
}
//... use ptr_to_dest, size
free(ptr_to_dest, allocated); //careful not to pass size here!
>> If you can convince the caller to keep track of that metadata themselves you obviously don’t need to. That can be important.
> That's why C23 introduce free_sized
Is it? C23 still has free, so there’s no guarantee callers wil use free_sized, so the allocator still has to be able to obtain a block’s size from a pointer.
Because free still exists and there is no “allocate this number of bytes of memory; I promise to free it with a call to free_size” call, you can’t have a malloc implementation that doesn’t track block sizes.
I think the only thing free_size adds is robustness. Allocators can check the passed in size with what they know and abort the program if they do not match. That can thwart some security issues.
> keep track of that metadata themselves you obviously don’t need to
likely it'd a be perf. hit in most cases. They'd have to copy to the tail end (likely) of the allocated area. Or the start and offset the pointer, they'd need to know the size of the metadata and account for that, including aligning it.Hence, the tail feels 'nicer'
It's possible to manually use mmap and forgo malloc entirely, rolling your own arena manager.
Actually yes, the malloc/free API (inherited from the ALLOCATE and FREE statements of PL/I) is too simple.
The metadata that malloc always attaches to the allocated memory would normally be useful for the user (i.e. having access to values like the currently allocated size and the total size of the allocation).
Very frequently, the user must duplicate inside the allocated memory the same information that already exists in the metadata, wasting memory. Also time may be wasted with requests for reallocation, instead of just adjusting the currently allocated size, when this is sufficient.
With a better API, the metadata would have been visible for the user. Being hidden from the user is not a protection in a language like C, where using pointer arithmetic can trash any memory location. Being exposed as non-mutable would have been a better protection.
Moreover, a better metadata structure for malloc should have always included a reference count, to be handled automatically by the compiler, and the malloc/free functions should have been invoked only implicitly, never explicitly.
To play devil's advocate, the problem with exposing more info is you limit the allocator design space.
1) If the app knew about and could use the additional underlying capacity, memory checkers wouldn't be able to find small overflows
2) Calling realloc instead of knowing existing capacity doesn't really provide better performance, at least not asymptotically.
3) If you need to know the requested allocation size, usually its for a dynamic array. Constantly requesting the size from the allocator would often have horrible performance if the size wasn't stored in adjacent metadata, but instead required a lookup operation, as is the case with hardened allocators. In practice hardened allocators probably wouldn't be a thing, or alternatively it would be idiomatic to store the size separately anyhow.
4) Reference counts would impose significant space and layout limitations despite most allocations never needing it.
There's another group who would argue the allocator should require passing the size and alignment to the free function, so allocators can be optimized better. Most of the time this is known statically. I think C2y will add APIs like this, though there's also a proposal to standardize an interface to query allocation capacity. Altogether I wouldn't be surprised if someday people appreciated the balance struck by malloc/free/realloc, especially as a minimal interface for overlaying application-specific allocators or injecting instrumentation. It has a certain elegance, in the sense of nothing left to remove.
You mean 4 bytes? You can't even address 4 bits. Small allocations can be handled by a slab allocator. Most likely implemented via a free list. A general purpose malloc should have that feature. TBH, I would consider allocating such tiny amounts of memory as a programmer error.
As I said, a slab allocator is included as part of general purpose malloc implementations. Rust is not going to be smarter here. I would bet it uses malloc underneath anyway.
Using a fat pointer to address individual bits is a waste of memory. You'd need an offset and length, and you'd have to deal with byte boundaries when accessing data. The only way I see this working is if you had a language that natively supported sub byte types and could deal with alignment of such types natively. Your best bet would be bit fields, which Rust doesn't support natively.
Dynamically allocating tiny amounts of data is a niche issue. You don't want a genetic solution to this anyway, because the efficiency will come from the constraints specific to your problem.
Having to recode malloc and free from "scratch" in school was a great teaching experience and there's not a month since where I don't encounter something that I understand better thanks to that exercise.
> so alloc() doesn’t just need to hand back a pointer. it needs to hand back a pointer that’s correctly aligned for whatever type the caller is about to store there.
Malloc doesn't know the required alignment (because has no idea what the type is, everything is cast through void). So all malloc implementations have a minimum alignment guarantee. Typically 16 bytes these days on x86, as that means even 128bit SSE values will end up aligned by default.
You couldn't go below the sizeof(void ) anyway, the backpointer needs to aligned too.
The padding only happens when you use memalign or aligned_malloc to specify a much larger alignment.
> So all malloc implementations have a minimum alignment guarantee. Typically 16 bytes these days on x86
Fun story. Back in the early 2000s, my Delphi OpenGL program randomly crashed when I tried to use vertex buffers. I spent a lot of time checking this and that, before I realized it might be an alignment issue.
Sure enough, Delphi memory allocator at the time only provided 4-byte alignment, while NVIDIA's drivers used aligned SSE instructions which require 16-byte alignment.
So, had to manually align the buffers before passing them to OpenGL.
IMO that sounds either like a bug in Nvidia's drivers (IIRC OpenGL doesn't require that sort of alignment) or -more likely- your code having some other memory related-bug (e.g. accessing data out of bounds) that the extra bytes you got from alignment masked it.
Nah it was definitely NVIDIA's fault. As you say there's nothing in the specs about alignment of those buffers, so they shouldn't be using aligned load instructions.
However Microsoft's malloc at the time was indeed returning 16-byte aligned buffers so they probably didn't notice it in internal testing.
There is no reason an allocation needs to contain any inline metadata. And even if it does, the allocator could choose to make it unalined, and pay the cost of an unalined access on de-allocation.
True.
But most C code out there assumes malloc will always return something that is at least aligned to sizeof(void *), it's very rare to see aligned_alloc. So how is your alloc allocation going to know when it can get away with a smaller alignment?
Even if you are on a cpu that doesn't fault on unaligned memory access, any malloc implementation that doesn't align by default will have serious disadvantages in any benchmarks. IMO, There is no good reason to use an unaligned backpointer.
Yes, large allocations need to be aligned to `alignof(max_align_t)`. But small allocations could have a smaller alignment. For example a single byte allocation can actually be a single byte with no alignment, since types can't have an alignment larger than their size.
This is explained in TFA, where it is mentioned that you can replace inline metadata with a pointer to metadata (or an index), which may be unaligned, if necessary.
However, the pointer to metadata is not really necessary.
The associated metadata could be stored in a table, and the index of the metadata could be computed from the offset of the pointer returned by malloc to the start of the heap (possibly using a hash function).
The ancient versions of the Microsoft C/C++ compilers were using a malloc with inline metadata. I have no idea if they replaced this more recently.
That's a good point, and I could have worded that better. What I implemented accepts an explicit alignment parameter because it made the allocator easier to explain. A real malloc() only guarantees alignment suitable for any object type (typically alignof(max_align_t)), since it has no idea what the caller will store there.
Isn't 64 bytes needed for AVX512, then?
There are two types of load/store instructions, one type requires alignment (vmovdqa), the other can load unaligned data (vmovdqu), in the case of AVX-512 the required alignment is 64 bytes. I assume aligned loads and stores are faster/have lower latency. For SSE/AVX you can look up the alignment requirements in Intel's intrinsics guide [0].
[0] https://www.intel.com/content/www/us/en/docs/intrinsics-guid...
Your bump allocator suffers from integer overflows turned into buffer overflows when the requested allocation is big enough:
I'd rewrite it like this:I used the compiler's __builtin_add_overflow in order to deal with that issue in my memory allocator. At this point I'm probably on track to replace every arithmetic operator in the entire codebase with those things.
Your test is backwards. I would write it like this:
You're right. Fixed.
thanks for pointing that out. will update the repo and the content!!!
I'm a little confused. We start with
and then it says we don't need to align the back pointer and we end up with without a clear explanation of how we now get to the back pointer if it's behind the variable alignment.This puzzled me as well.
Why bother with dynamic padding and a back pointer? That wastes at least 8 bytes.
You might as well always align to 8 bytes and make your header a multiple of 8.
The back pointer could also be a 1 byte number giving the size of the padding.
Old magazines like The C/C++ Users' Journal and DDJ used to have ads for companies selling malloc()/free() replacement libraries, exactly because a single implementation isn't adequate to all scenarios.
These still exist, like dlmalloc, jemalloc, tmalloc (which has new features). Built-in malloc is good enough for almost everything if you don't have excessive time on your hands, but thinking deeper about memory allocation is one of those things that can make your software higher quality if you have time for it—just like utilising SIMD (also on today's front page) or careful use of caching.
Alternative allocators could make a huge difference to the runtime performance. When multithreading on real multiprocessor systems started to become a thing it was common that all your carefully written threads ended up waiting on the allocator mutex. The win32 heap was particularly prone to this.
Third party allocators improved on this as well as usually avoiding the heap fragmentation problems that system heaps often suffered from back then.
These days the system heaps have improved to a point where you really only need to think about a third party heap for very specialized circumstances. They do usually come with nifty debugging tools though.
I wrote this bump malloc that I use for very short lived Wasm modules: https://github.com/ncruces/wasm2go/blob/main/libc-gen/c/mall...
I've read some allocator walkthroughs before but I thought that this line stood out:
"to get individual free() working, the allocator needs to remember something about every allocation it handed out. and that’s the moment metadata stops being optional."
That's just a very nice distillation of an important concept.
This becomes particularly important when the allocation and metadata cannot (or should not) be stored in the same address space. An example of this is allocating memory on GPUs.
The conventional approach for allocating memory on GPUs for games and other applications is to use a real-time allocator such as TLSF. However, it is not usually discussed that TLSF is real-time because it stores metadata in-band. It is possible to create a variant of TLSF that preserves its real-time properties while storing metadata out-of-band, but this requires careful consideration.
Oh? How do you think munmap does it?
If you can convince the caller to keep track of that metadata themselves you obviously don’t need to. That can be important.
Something I noticed is that _very often_ the code that is calling malloc(n) is keeping track of n somehow for its own reasons (bounds checking, grow/gap pointers, etc) so merging the value halves stack churn and it’s an easy win.
Well, even that doesn't really work, because optimized allocators typicallly don't allocate exactly the amount that you ask for, they allocate some larger chunk to help with both alignment and fragmentation.
So, most likely, there are two sizes in reality: the size of your user data that you care about; and the size of the memory chunk in which your user data resides, that free() cares about. So, unless you're willing to go for an API like this, you can't rely on the consumer:
That's why C23 introduce free_sized [0].
[0] https://en.cppreference.com/c/memory/free_sized
>> If you can convince the caller to keep track of that metadata themselves you obviously don’t need to. That can be important.
> That's why C23 introduce free_sized
Is it? C23 still has free, so there’s no guarantee callers wil use free_sized, so the allocator still has to be able to obtain a block’s size from a pointer.
Or do I overlook something?
I suppose by default it will just call free, but you can substitute different malloc implementations, maybe one with a malloc_no_header function
Because free still exists and there is no “allocate this number of bytes of memory; I promise to free it with a call to free_size” call, you can’t have a malloc implementation that doesn’t track block sizes.
I think the only thing free_size adds is robustness. Allocators can check the passed in size with what they know and abort the program if they do not match. That can thwart some security issues.
> keep track of that metadata themselves you obviously don’t need to
likely it'd a be perf. hit in most cases. They'd have to copy to the tail end (likely) of the allocated area. Or the start and offset the pointer, they'd need to know the size of the metadata and account for that, including aligning it.Hence, the tail feels 'nicer'
It's possible to manually use mmap and forgo malloc entirely, rolling your own arena manager.
munmap has metadata in a separate data structure in the kernl
In the other words, free() is a flawed API. :-)
Actually yes, the malloc/free API (inherited from the ALLOCATE and FREE statements of PL/I) is too simple.
The metadata that malloc always attaches to the allocated memory would normally be useful for the user (i.e. having access to values like the currently allocated size and the total size of the allocation).
Very frequently, the user must duplicate inside the allocated memory the same information that already exists in the metadata, wasting memory. Also time may be wasted with requests for reallocation, instead of just adjusting the currently allocated size, when this is sufficient.
With a better API, the metadata would have been visible for the user. Being hidden from the user is not a protection in a language like C, where using pointer arithmetic can trash any memory location. Being exposed as non-mutable would have been a better protection.
Moreover, a better metadata structure for malloc should have always included a reference count, to be handled automatically by the compiler, and the malloc/free functions should have been invoked only implicitly, never explicitly.
To play devil's advocate, the problem with exposing more info is you limit the allocator design space.
1) If the app knew about and could use the additional underlying capacity, memory checkers wouldn't be able to find small overflows
2) Calling realloc instead of knowing existing capacity doesn't really provide better performance, at least not asymptotically.
3) If you need to know the requested allocation size, usually its for a dynamic array. Constantly requesting the size from the allocator would often have horrible performance if the size wasn't stored in adjacent metadata, but instead required a lookup operation, as is the case with hardened allocators. In practice hardened allocators probably wouldn't be a thing, or alternatively it would be idiomatic to store the size separately anyhow.
4) Reference counts would impose significant space and layout limitations despite most allocations never needing it.
There's another group who would argue the allocator should require passing the size and alignment to the free function, so allocators can be optimized better. Most of the time this is known statically. I think C2y will add APIs like this, though there's also a proposal to standardize an interface to query allocation capacity. Altogether I wouldn't be surprised if someday people appreciated the balance struck by malloc/free/realloc, especially as a minimal interface for overlaying application-specific allocators or injecting instrumentation. It has a certain elegance, in the sense of nothing left to remove.
Efficient and generalized are opposing forces. Malloc is fine for what it is but you can do better by specialising.
glad you found it useful :)
update: thanks to everyone who pointed out the mistake in the back pointer layout. the diagrams and explanation have been corrected.
What if I want to allocate only 4 bits?
I bet this is better optimized in Rust.
You mean 4 bytes? You can't even address 4 bits. Small allocations can be handled by a slab allocator. Most likely implemented via a free list. A general purpose malloc should have that feature. TBH, I would consider allocating such tiny amounts of memory as a programmer error.
No, I meant 4 bits. Assume I have only a small amount of memory, but I need to use an allocator and I don't want to use a custom allocator.
> You can't even address 4 bits.
This is not true, you can use a pointer plus extra offset data, etc.
As I said, a slab allocator is included as part of general purpose malloc implementations. Rust is not going to be smarter here. I would bet it uses malloc underneath anyway.
Using a fat pointer to address individual bits is a waste of memory. You'd need an offset and length, and you'd have to deal with byte boundaries when accessing data. The only way I see this working is if you had a language that natively supported sub byte types and could deal with alignment of such types natively. Your best bet would be bit fields, which Rust doesn't support natively.
Dynamically allocating tiny amounts of data is a niche issue. You don't want a genetic solution to this anyway, because the efficiency will come from the constraints specific to your problem.
Having to recode malloc and free from "scratch" in school was a great teaching experience and there's not a month since where I don't encounter something that I understand better thanks to that exercise.