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.
Why malloc always does more than I asked for?
21–30 of 52 posts
Re: Why malloc always does more than I asked for?
#22I wrote this bump malloc that I use for very short lived Wasm modules: https://github.com/ncruces/wasm2go/blob/main/libc-gen/c/mall...
Re: Why malloc always does more than I asked for?
#23Your bump allocator suffers from integer overflows turned into buffer overflows when the requested allocation is big enough: if (a->cursor + size > a->limit) return NULL; // out of memory I'd rewrite it like this: if (size > a->limit - a->cursor) return NULL; // out of memory
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.
Re: Why malloc always does more than I asked for?
#24Having 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.
Re: Why malloc always does more than I asked for?
#25> 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 val…
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.
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.
Re: Why malloc always does more than I asked for?
#26Earlier quoted context omitted.
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.
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?
Re: Why malloc always does more than I asked for?
#27I'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.
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.
Re: Why malloc always does more than I asked for?
#28I'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.
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:
int* ptr_to_dest = NULL;
size_t size = 10 * sizeof(int);
size_t allocated = malloc(&ptr_to_dest, size);
if (allocated Re: Why malloc always does more than I asked for?
#29Earlier quoted context omitted.
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 exis…
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.
Re: Why malloc always does more than I asked for?
#30What if I want to allocate only 4 bits?
I bet this is better optimized in Rust.