c - Linux 堆结构和 malloc() 和 free() 的行为

Question

我有一个带有 Linux 2.6 内核的 D​​ebian，我试图通过 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 和 run 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

你可以看到 char 数组非常好。然后我试图找出为什么有 0x29 (dec 41)。我希望像 0x20(12 月 32 日)或 0x24(12 月 36 日)这样的东西。

• 为什么 malloc 算法浪费这个空间？
• 如何判断为0x29？
• 最后的 0xf89 代表什么？
• 程序如何跟踪分配的内容和免费的内容？

特别是我想了解free() 是如何工作的。三个 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 如何跟踪地址？

非常感谢您的阅读， 亲切的问候

Answer 1

大多数 malloc() 实现通过在分配的内存块之前和/或之后跟踪堆本身内部堆的状态来工作。溢出分配的 block 会导致此数据被破坏——其中一些数据可能包括指针或长度，并且破坏这些数据会导致实现尝试访问无效的内存位置。

malloc() 实现的细节取决于您使用的系统和 libc。如果您使用的是 glibc(如果您使用的是 Linux，则很可能)，这里有关于它如何工作的很好的解释:

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

假设是这种情况，您看到的 0x29 可能是 block 大小 (32 = 0x20) 和一些标志的按位或。这是可能的，因为所有堆分配都四舍五入到最接近的 16 字节(或更多!)，因此始终可以假定大小的低八位为零。