Where Do malloc() / free() Store Allocated Sizes and Addresses?

Question

Hi,

where do malloc() and free() store the allocated addresses and their sizes (Linux GCC)? I've read that some implementations store them somewhere before the actual allocated memory, but I could not confirm that in my tests.

The background, maybe someone has another tip for this: I'm experimenting a little bit with analyzing the heap memory of a process in order to determine the current value of a string in the other process. Accessing the process heap memory and strolling through it is no problem. However, because the value of the string changes and the process allocates a new part of the memory each time, the string's address changes. Because the string has a fixed format it's still easy to find, but after a few changes the old versions of the string are still in the heap memory (probably freed, but still not reused / overwritten) and thus I'm not able to tell which string is the current one.

So, in order to still find the current one I want to check if a string I find in the memory is still used by comparing its address against the addresses malloc/free know about.

ciao, Elmar

Answer 1

There are lots of ways in which malloc/free can store the size of the memory area. For example, it might be stored just before the area returned by malloc. Or it might be stored in a lookup table elsewhere. Or it might be stored implicitly: some areas might be reserved for specific sizes of allocations.

To find out how the C library in Linux (glibc) does this, get the source code from http://ftp.gnu.org/gnu/glibc/ and look at the malloc/malloc.c file. There is some documentation at the top, and it refers to A Memory Allocator by Doug Lea.

Answer 2

This is up to the implementation of the standard library, of course. So your best bet would probably be to dig through the source of the library (glibc is the default on Linux) and see if you can figure it out. It is probably not going to be trivial.

Answer 3

Most commonly, glibc will try to reduce inefficiencies in the heap by preallocating chunks and reusing free()d chunks. The aim of malloc and free is to do this quickly and avoid too much fragmentation. This depends on the hardware too; different architectures have different caching mechanisms. Virtual memory mapping per-process is also a concern here. Looking through the malloc source, what you will find is that no one system keeps a table of addresses, although free()d space is kept for a while incase it's needed again shortly.

In short, this is managed per-process. Tracking the address space of other processes is going to be tricky on the heap, as often allocation is non-contiguous. You might have more luck writing a patch for glibc forcing it to create a stack-table in the process whos location you know, and can suck out heap allocations -or-

more interestingly, replace the glibc malloc(), free() and realloc() in the target process with your own implementation in the ELF symbol table. You might even be able to do this at runtime with the right method, using the dlopen interface and a bit of brute force.