malloc and free

[TLV]

My question is about malloc and free functions interworking.

1. Where is the size of allocated by malloc memory is stored?
2. How does free function aware of the size of the memory it deallocates?


Thank you.
(Is it right not to use existing thread eether open a new one? )

[Salem]

Yes, it is best to start a new thread rather than hijacking someone else's.

> 1. Where is the size of allocated by malloc memory is stored?
Usually in some private space use by the memory pool manager.

> 2. How does free function aware of the size of the memory it deallocates?
Using what it stored when the block was allocated.

[TLV]

Thanks a lot!

[ledow]

The implementation of malloc and free do what they need to do behind the scenes. The only exposure you see is what the C standard lets you see. And this is because of a number of things, not least of which is that malloc and free are pretty low-level operations that vary greatly from machine to machine.

Chances are, your "malloc(2)" call didn't actually allocate 2 bytes. Depending on the machine it could have allocated anything from 2 to maybe even 4096 bytes or similarly large values (the origin of this is memory "paging", which you can go read about). So malloc / free not only store how much you asked for, but probably how much was ACTUALLY allocated as well (which is an entirely different thing!). And there are myraid malloc replacements and variations that can do everything from being thread-safe to having more efficient collection, to even storing your data in swap or memory not normally available to a normal C process etc. All malloc really does is know where all the free memory is (or have a facility to be told where they are by the OS), find a suitable way to slice it up, keep track of what's been used and what's not, and then when you ask either a) malloc - find a suitable empty contiguous area(s) of the appropriate size and return it, or b) free - mark a previously-used area and now unused. Usually that's done by some kind of memory table / bitmap. It knows it has 1000 areas of memory it can allocate so it has, somewhere out of your sight, an array of 1000 memory addresses that it can mark as free/used when required.

Hell, you can even write your own malloc "frontend" and find out for yourself. It's not that difficult to do. Malloc a HUGE amount of memory and then handle your own malloc/free calls that chop that memory up into blocks and return an address inside it to each caller. I used one implementation of malloc on a device called the GP2X. The implementation was actually part-normal-malloc and part memory-mapping. It knew the hardware so intimately that it could find the parts of memory only used for boot-up or media decoding or graphics memory and get pointers to them. It then used them as a memory "pool" from which to return ordinary memory allocations transparently using malloc/free. So when you thought you were malloc'ing from standard RAM, you could actually be getting memory that was part of an unused hardware framebuffer in graphics memory, or similar. It allowed me to access nearly twice as much memory as apps that didn't use those tricks could on the same hardware. Similar tricks have allowed people to do everything from working on faulty RAM chips (BadRAM - just allocating only around known-bad parts of memory), to using their graphics card memory as RAM, etc.

Malloc isn't that complicated. All it needs to know is where all the memory is that it can allocate from, how big a piece you want, and then to remember which one it gave you and how big it was so it doesn't give it out to anyone else. Free just looks up what you give it against all the things that malloc has already handed out, sees how much memory you asked for originally and then marks ALL the blocks you were given so they can be reissued to another caller. It's then that you realise why playing with pointers (e.g. pointer arithmetic) to allocated memory before passing them to free() gives you problems, why memory allocated by malloc is rarely zeroed (because it's usually just finished being used by someone else and clearing it every time you free() it is a massive performance hit), why pointers don't point to valid data after free() has occurred on them (because then they could be given to someone else who could write over them at any time!), why realloc can struggle to fit huge arrays into contiguous memory and sometimes has to change WHERE those arrays are allocated, etc.

Seriously, if you want to fully understand malloc / free write your own: my_malloc and my_free. Have your initialisation code allocate, say, a 32Mb block of memory using the system malloc() and then write the core of my_malloc and my_free to slice that up into blocks and allocate them to EVERY OTHER PART of your program (so the only "real" malloc call in the entire program was for the 32Mb block). It's a good way to learn how it works, what information it has to store, and a useful technique to do things like artificially constrain the amount of memory your program can ever use, or find un-free'd memory, etc.