Структура кучи Linux и поведение с malloc() и free()

У меня есть Debian с Linux 2.6 Kernel, и я пытаюсь понять, как работает/ведет себя куча с помощью malloc()и free(). Я попытался найти алгоритм malloc()и free()и структуру кучи, но ничего полезного не нашел. И, к сожалению, я слишком мало знаю о Linux и о том, как работает память, чтобы понять исходный код free()и malloc().

Вот пример кода:

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);
}

С помощью gdbи запустите AAAA BBBB CCCC. Я могу проверить кучу. Это состояние после strcpys, но до 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

Вы можете очень хорошо видеть массивы символов. Затем я попытался выяснить, почему существуют 0x29 (декабрь 41). Я ожидал что-то вроде 0x20(декабрь 32) или 0x24(декабрь 36).

• Почему алгоритм malloc тратит впустуюэто пространство?
• Как определяется, что это 0x29?
• А что означает 0xf89в конце?
• Как программа отслеживает, что выделено, а что свободно?

Особенно я хочу понять, как работает free(). После трех освобождений куча выглядит так:

(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

• Почему массив символов заменяется этим конкретным адресом?
• Что такое псевдокод, что делает free?

Посмотрите на этот пример:

(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.

Я перезаписал 0x29, но программа завершилась нормально.Но когда я добавляю еще один байт, я сталкиваюсь с ошибкой сегментации:

(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

Самый важный вопрос для меня:

• Почему вы получаете ошибку сегментации в free(), когда перезаписываете больше байтов. ?
• и как работает алгоритм free()?
• и как malloc и free отслеживают адреса?

Большое спасибо за прочтение. с уважением