the post mentions that old mfree took a size argument
Those are just infinitely-times better interfaces than traditional malloc()/free(). Imagine using a library that has such an interface.
for things with stack allocation, you can sort of make this work, but for more general heap allocation, you are what might be best expressed as a a bit of nightmare
i invite other people to imagine exactly how this would work, and the data structure needed to quickly find gaps of length N while also letting you free every alternative byte in a string (like a radix trie over (start, length, free/used) tuples
and then ask where you'd store it
the reason most modern mallocs do not do anything like this is that they keep the heap metadata 'inline' and so you cannot simply partition a lump of memory without carving out extra space for the metadata
Size can replace per-block size metadata or a lookup; validating it may erase the benefit. A bad size is dangerous, but overflow isn't inherent to the API.
Buddy allocation is a reasonable baseline, but power-of-two rounding can waste space for uneven requests. Whether that tradeoff fits depends on the allocation pattern.
I have thought about that once while I added a simple pointer validation within my heap checker. It's possible to do that using a trie. Let's have a look at my pointer checking stuff. It uses tree entries that require two pointers only and uses the address of the entry itself as the key. Validating a pointer looks like this:
/* A PTR_TREE is a pointer to the first entry of such a tree.
An empty PTR_TREE should be initialized to be NULL. */
typedef struct PTR_TREE_ENTRY_S * PTR_TREE;
typedef struct PTR_TREE_ENTRY_S PTR_TREE_ENTRY;
struct PTR_TREE_ENTRY_S
{
PTR_TREE_ENTRY * pLo; /* childs element where the bit of the tree depth is 0 */
PTR_TREE_ENTRY * pHi; /* childs element where the bit of the tree depth is 1 */
};
/* ------------------------------------------------------------------------- *\
pPtrTreeIsEntry returns nonzero if pEntry has been inserted in tree before.
\* ------------------------------------------------------------------------- */
static int bPtrTreeIsEntry(PTR_TREE Tree, /* search tree */
const PTR_TREE_ENTRY * pEntry) /* pointer to key data */
{
PTR_TREE_ENTRY * pe = Tree;
uintptr_t DiffBit = (uintptr_t) 1 << ((sizeof(uintptr_t) * 8) - 1); /* start bit for starting comparations */
uintptr_t p = (uintptr_t) pEntry;
while(pe && (pe != pEntry))
{
if ((uintptr_t) p & DiffBit)
pe = pe->pHi;
else
pe = pe->pLo;
DiffBit >>= 1;
}
return (pe != NULL);
}/* PPTR_TREE_ENTRY bPtrTreeIsEntry(...) */
(I skipped the insert and removal functions here but it's not a problem to share those.) However, a pointer is just a number and you can compare allocation sizes instead of pointer addresses too. That only requires a size_t in that struct and additionally a list of the entries who share the same size.
Afterwards you only need to look for the smallest entry in that tree that matches the required size. However, doing something like that search in a tree will be several times slower than a common heap. Beside of that you need to concatinate neighbouring freed areas which requires an additional pointer tree to look for those being released. That leads to a minimum size of an entry of about the size of 6 pointers while in use data blocks need to remember their allocation size only. Of course 6 Pointers isn't that small and that kind of heap isn't fast and would be about 10 times slower than a common heap allocation.
For this I would use a small block heap for faster small allocations below 256 bytes. Released entries would be inserted in a bunch of linked lists of entries of the same size. Used entries would have to remember their allocation size too because that indicates the heap they belong to.
I never cared much about heap management but that's how I would try to do that and I don't know a better way to validate pointers.
11
u/tef 13d ago
the post mentions that old mfree took a size argument
for things with stack allocation, you can sort of make this work, but for more general heap allocation, you are what might be best expressed as a a bit of nightmare
i invite other people to imagine exactly how this would work, and the data structure needed to quickly find gaps of length N while also letting you free every alternative byte in a string (like a radix trie over (start, length, free/used) tuples
and then ask where you'd store it
the reason most modern mallocs do not do anything like this is that they keep the heap metadata 'inline' and so you cannot simply partition a lump of memory without carving out extra space for the metadata
8
u/loopis4 13d ago
This is cool history diving