Wandering Thoughts archives


The C free() API means memory allocation must save some metadata

Here's something that I hadn't really thought about until I was thinking about the effects of malloc() and free() on C APIs: the API of free() in specific more or less requires a conventional C memory allocator to save some metadata about each allocation. This is because free() isn't passed an explicit size of what to free, which implies that it must get this information from elsewhere. The traditional way the C memory allocator does this is to put information about the size of the allocation in a hidden area either before or after the memory it returns (often before, because it's less likely to get accidentally overwritten there).

(That C memory allocators store the size of allocations they've handed out is clear to anyone who's read through the small malloc() implementation in K&R.)

This free() API isn't the only way it could be; a less convenient version would be to pass in an explicit size. But this would be a pain, because in practice a lot of C allocations are variable-sized ones for things like (C) strings. The C free() API is in a sense optimized for blind allocations of variable sized objects. It also allows for a more straightforward optimization in realloc(), where malloc() can round up the size you requested, save that size as the metadata, and then realloc() can expand your nominal allocation into any remaining free space if possible. So there's pretty strong reasons for free() to not require a size even if it normally requires some extra allocator overhead.

Of course you can build C memory allocators that avoid or amortize this overhead, mostly obviously by having free() never do anything (some programs will be perfectly fine with this and it's very fast). A slab allocator that uses size classes doesn't need size metadata for individual allocations that fall into size classes, because the size of an individual allocation is implicit in being allocated in a particular size class's arena. More broadly you can have an allocator interface where programs can set all future memory allocations to come from a particular arena, and then promise to de-allocate the arena all at once and not care about free() otherwise (letting you make free() a no-op while there's an active arena).

(Talloc is an explicit arena setup, as opposed to the implicit one I described, but of course this is an option too.)

programming/CFreeRequiresMetadata written at 21:16:53; Add Comment

Page tools: See As Normal.
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.