Linux heap structure and the behaviour with malloc

Question

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

Answer 1

I don't know the details exactly. But in general, it works like this:

Larger malloc()s are handled via mmap(), so we concentrate on the smaller ones. There is somewhere a limit where you can set the threshold.

Smaller malloc()s are handled at the end of the data segment. This can be handled and resized by the glibc with the system calls brk() and sbrk().

After you malloc() a memory block, it has to be held in order to know how much to free when free() is called, and a pointer to the next block has to be kept in order to find them all and to chain them together.

After free()ing a memory block which is at the end, the data segment is reduced with sbrk(). After free()ing a block which is NOT at the end, the block is added to the free list. This is a linked list of free memory blocks in order to reuse them.

0x29, which is 41, is the memory block size you allocated plus a bit of memory to hold the said fields (size and next pointer), which needs 8 bytes. What the 9th is for, I don't know, but it might be that it has to do with alignment.

If you write more than the "promised" 32 bytes, you destroy this linked list and the pointer associated with it. Therefore, free() has wrong data which it trusts and tries to write at an unallowed place, which leads to SIGSEGV.

Answer 2

Why do you get a Segmentation fault in free() when you overwrite more bytes?

Once you pass the end of the space you asked for, you are technically invoking undefined behavior and so anything is possible. Eventually, you will clobber a pointer or a size field in an internal data structure and this corruption may or may not cause a reference wild enough to reference an entire page that isn't present.

That is, the segmentation fault is a consequence of page protection. This works well to protect one entire program from another unrelated one and is a tool used by the operating system to limit damage to a single user-mode address space. This mechanism is not closely synchronized with internal data structures. There is a rough correspondence between valid pointers and valid pages but nothing exact.

and how does the free() algorithm work?

When a block is returned by malloc(), an internal data structure is created so that when that exact block is passed to free(), it will be recognized and linked into a free list. It will be combined with adjacent free blocks if possible.

and how do malloc and free keep track on the adresses?

Since you are running Linux the source code is available and reading it will naturally result in the most exact answer. However, the general answer is that a directory is kept. This directory may be a separate data structure or it may be in the form of a linked list with metadata kept in front of the actual address that is returned.

Why is there wasted space?

It's not precisely wasted. Some of the space may be used for the directory and some may be traded for performance by keeping blocks aligned on cache boundaries. Image a small block that's equal in size to a cache line, or perhaps smaller. If this block overlaps a cache line boundary, keeping it in the cache will require twice as much space as it needs. If this happened everywhere the cache would effectively be half the size and have a lower hit rate. (Well, except for the cases where the neighboring addresses were actually needed.) Using larger blocks will also result in less internal fragmentation which may actually use less memory overall in the steady-state where malloc() and free() calls are balanced in a long-running process.

Answer 3

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.