Dynamic Memory Allocation

Question

How malloc() stores metadata?

void* p;
void* q;
p = malloc(sizeof(char));
q = malloc(sizeof(int));

I know that the return value p[0] points to the start of allocated block of memory,

than if I iterate and print

p[-1], p[-2].... q[-1], q[-2]....

or p[1], p[2], p[3], p[4].... or q[1], q[2], q[3], q[4]....

I find some value that help malloc() to store data howether I can t understand precisely what that metadata means..I only know that some of them are for block size, for the adress of the next free block but i can t find on the web nothing more

Please, Can you give me some detailed explanation of those value?

Answer 1

How this metadata works and is used depends entirely on the memory management in your libc. Here are some useful writeups to get you started:

• Malloc - Typically, classic malloc.
• DLMalloc - Doug Lee's Malloc.
• GC Malloc - Malloc with garbage collection.
• TC Malloc - Thread caching malloc.

Each of these has different aims, benefits and possible deficiencies. For example, perhaps you are concerned about possible heap overflow issues and protections. This may lead to one choice. Perhaps you are looking for better fragment management. This might lead to the selection of Doug Lee's malloc. You really need to specify which library you are using or research them all to understand how the metadata is used to maintain bins, coalesce adjustment free regions, etc.

Answer 2

David Hoelzer has an excellent answer, but I wanted to follow it up a touch more:

"Meta Data" for malloc is 100% implementation driven. Here is a quick overview of some implementations I have written or used:

• The meta data stores "next" block pointers.
• It stores canary values to make sure you haven't written passed the end of a block
• There is no meta data at all because all the blocks are the same size and they are placed in a stack to allow O(1) access - A Unit Allocator. In this case, you'd hit memory from an adjacent block.
• The data stores next block ptr, prev block ptr, alignment id, block size, and an identifier that tells a memory debugger exactly where the allocation occured. Very useful for leak tracking.
• It hits the previous block's info because the data is stored at the tail of the block instead of the head...

Or mix and match all the above. In any case, reading mem[-1] is a bad idea, and in some cases (thinking embedded systems), could indeed cause a segment fault on only a read if said read happen to address beyond the current memory page and into a forbidden area of memory.

---

Update as per OP

The 4th scheme I described is one that has quite a bit of information per block - 16-bytes of information not being uncommon as that size won't throw off common alignment schemes. It would contain a 4-byte pointer to the next allocated block, a 4-byte pointer to the previous, an identifier for alignment - a single byte can handle this directly for common sizes of 0-256 byte alignement, but that byte could also represent 256 possible alignment enum values instead, 3 bytes of pad or canary values, and a 4-byte unique identifier to identify where in the code the call was made, though it could be made smaller. This can be a lookup value to a debug table that contains __file__, __line__, and whatever other info you wish to save with the alloction.

This would be one of the heavier varieties as it has a lot of information that needs to be updated when values are allocated and freed.

Answer 3

It is illegal to access p[-1], etc in your example. The results will be undefined and maybe cause memory corruption, or segmentation fault. In general you don't get any control over malloc() at all or information about what it is doing.

That said, some malloc() "replacement" libraries will give you finer grained control or information - you link these into your binary "on top" of the system malloc().

Answer 4

The C standard does not specify how malloc stores its metadata (or even if it will have accessible metadata); therefore, the metadata format and location are implementation-dependent. Portable code must therefore never attempt to access or parse the metadata.

Some malloc implementations provide, as an extension, functions like malloc_usable_size or malloc_size which can tell you the size of allocated blocks. While the presence of these functions is also implementation dependent, they are at least reliable and correct ways to get the information you need if they are present.