Linux heap structure and the behaviour with malloc() and free()

I have a Debian with a Linux 2.6 Kernel, and I try to understand how the heap works/behaves with malloc() and free(). I tried to search for malloc() and free() algorithm and heap structure, but I couldn't find anything helpful. And unfortunately, I know too less about Linux and how memory works, to understand the source code of free() and malloc().

This is an example code:

int main(int argc, char **argv)
{
    char *a, *b, *c;

    a = malloc(32);
    b = malloc(32);
    c = malloc(32);

    strcpy(a, argv[1]);
    strcpy(b, argv[2]);
    strcpy(c, argv[3]);

    free(c);
    free(b);
    free(a);
}

With gdb and run AAAA BBBB CCCC I can examine the heap. This is the state after the strcpys but before the frees:

(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x41414141  0x00000000
0x804c010:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c020:  0x00000000  0x00000000  0x00000000  0x00000029
0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89

You can see the char arrays very good. Then I tried to figure out why there are 0x29 (dec 41). I would expect something like 0x20 (dec 32) or 0x24 (dec 36).

• Why does the malloc algorithm wastes this space?
• How is it decided that it is 0x29?
• And what does the 0xf89 at the end stands for?
• How does the program keep track on what's allocated and what is free?

Especially I want to understand how free() works. After the three frees, the heap looks like this:

(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x0804c028  0x00000000
0x804c010:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c020:  0x00000000  0x00000000  0x00000000  0x00000029
0x804c030:  0x0804c050  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x00000000  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89

• Why is the char array replaced with this specific adress?
• What is the pseudo code what free does?

Look at this example:

(gdb) run AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADDDDD BBBB CCCC
...
(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x41414141  0x41414141
0x804c010:  0x41414141  0x41414141  0x41414141  0x41414141
0x804c020:  0x41414141  0x41414141  0x44444444  0x00000044
0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
...
(gdb) c
Program exited with code 021.

I have overwritten the 0x29, but the program exits normally. But when I add another byte, I run into a Segmentation Fault:

(gdb) run AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAADDDDD BBBB CCCC
...
(gdb) x/32x 0x804c000
0x804c000:  0x00000000  0x00000029  0x41414141  0x41414141
0x804c010:  0x41414141  0x41414141  0x41414141  0x41414141
0x804c020:  0x41414141  0x41414141  0x44444444  0x00004444
0x804c030:  0x42424242  0x00000000  0x00000000  0x00000000
0x804c040:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c050:  0x00000000  0x00000029  0x43434343  0x00000000
0x804c060:  0x00000000  0x00000000  0x00000000  0x00000000
0x804c070:  0x00000000  0x00000000  0x00000000  0x00000f89
...
(gdb) c
Program received signal SIGSEGV, Segmentation fault.
0x080498b9 in free (mem=0x804c030) at common/malloc.c:3631

The most important question for me is:

• Why do you get a Segmentation fault in free() when you overwrite more bytes?
• and how does the free() algorithm work?
• and how do malloc and free keep track on the adresses?

Thank you very much for reading, kind regards

Most malloc() implementations work by tracking the status of the heap within the heap itself, right before and/or after the allocated blocks of memory. Overrunning an allocated block causes this data to be corrupted -- some of this data may include pointers or lengths, and corrupting those causes the implementation to attempt to access invalid memory locations.

The details of how the malloc() implementation works are dependent on what system and libc you're using. If you're using glibc (which is likely if you're on Linux), there's a pretty good explanation of how it works here:

http://gee.cs.oswego.edu/dl/html/malloc.html

Assuming this is the case, the 0x29 you're seeing is probably a bitwise OR of the block size (32 = 0x20) and some flags. This is possible because all heap allocations are rounded to the nearest 16 bytes (or more!), so the lower eight bits of the size can always be assumed to be zero.