5

我有一个带有 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（12 月 41 日）。我希望像0x20（12 月 32 日）或0x24（12 月 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
  • 为什么用这个特定的地址替换 char 数组？
  • 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 如何跟踪地址？

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

4

3 回答 3

9

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

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

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

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

于 2012-05-10T19:36:04.347 回答
2

我不知道具体的细节。但总的来说，它是这样工作的：

较大malloc()的 s 通过 处理mmap()，因此我们专注于较小的。有一个限制可以设置阈值。

较小malloc()的 s 在数据段的末尾处理。这可以由 glibc 使用系统调用brk()和sbrk().

在你malloc()一个内存块之后，必须保持它以便知道在free()调用时要释放多少，并且必须保持指向下一个块的指针以便找到它们并将它们链接在一起。

在结束free()一个内存块之后，数据段被减少sbrk()。在free()ing 一个不在末尾的块之后，该块被添加到空闲列表中。这是一个空闲内存块的链表，以便重用它们。

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.

于 2012-05-10T19:36:48.720 回答
0

当您覆盖更多字节时，为什么会在 free() 中出现分段错误？

一旦你通过了你要求的空间的尽头，你在技术上调用了未定义的行为，所以一切皆有可能。最终，您将破坏内部数据结构中的指针或大小字段，并且这种损坏可能会或可能不会导致引用狂野到足以引用不存在的整个页面。

也就是说，分段错误是页面保护的结果。这可以很好地保护一个完整的程序免受另一个不相关的程序的影响，并且是操作系统用来限制对单个用户模式地址空间的破坏的工具。这种机制与内部数据结构没有紧密同步。有效指针和有效页面之间存在粗略的对应关系，但并不准确。

free() 算法是如何工作的？

当 malloc() 返回一个块时，会创建一个内部数据结构，以便当该确切块被传递给 free() 时，它将被识别并链接到一个空闲列表中。如果可能，它将与相邻的空闲块合并。

malloc 和 free 如何跟踪地址？

由于您正在运行 Linux，因此源代码是可用的，阅读它自然会得到最准确的答案。但是，一般的答案是保留一个目录。 这个目录可能是一个单独的数据结构，也可能是一个链表的形式，元数据保存在返回的实际地址的前面。

为什么会浪费空间？

它并没有完全浪费。一些空间可能用于目录，而另一些空间可以通过保持块在缓存边界上对齐来换取性能。对大小与高速缓存行相等或可能更小的小块进行映像。如果此块与高速缓存行边界重叠，则将其保留在高速缓存中将需要两倍的空间。如果这种情况发生在任何地方，缓存实际上将是一半大小并且命中率更低。（嗯，除了实际需要相邻地址的情况。）使用更大的块也将导致更少的内部碎片，这实际上可能在 malloc() 和 free() 调用平衡的稳态中使用更少的内存一个长期运行的过程。

于 2012-05-10T19:36:37.950 回答