# 内存，第 1 部分：堆内存简介 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Memory%2C-Part-1%3A-Heap-Memory-Introduction> ## C 动态内存分配 ## 当我打电话给 malloc 时会发生什么？ 函数`malloc`是 C 库调用，用于保留连续的内存块。与栈内存不同，内存保持分配状态，直到使用相同的指针调用`free`。还有`calloc`和`realloc`，将在下面讨论。 ## malloc 可以失败吗？ 如果`malloc`无法再保留更多内存，则返回`NULL`。强大的程序应该检查返回值。如果您的代码假定`malloc`成功但它没有，那么当您尝试写入地址 0 时，您的程序可能会崩溃（segfault）。 ## 堆在哪里，它有多大？ 堆是进程内存的一部分，它没有固定的大小。当您调用`malloc`（`calloc`，`realloc`）和`free`时，堆存储器分配由 C 库执行。 首先快速回顾一下进程内存：进程是程序的运行实例。每个进程都有自己的地址空间。例如，在 32 位机器上，您的进程可以获得大约 40 亿个地址，但并非所有这些地址都有效，甚至映射到实际物理内存（RAM）。在进程内存中，您将找到可执行代码，栈空间，环境变量，全局（静态）变量和堆。 通过调用`sbrk`，C 库可以增加堆的大小，因为程序需要更多的堆内存。由于堆和栈（每个线程一个）需要增长，我们将它们放在地址空间的两端。因此，对于典型的体系结构，堆将向上生长并且栈向下增长。 真实性：现代操作系统内存分配器不再需要`sbrk` - 相反，它们可以请求虚拟内存的独立区域并维护多个内存区域。例如，可以将千兆字节请求放置在与小分配请求不同的存储器区域中。然而，这个细节是一个不必要的复杂性：碎片化和有效分配内存的问题仍然适用，因此我们将在这里忽略这种实现，并将写入就像堆是单个区域一样。 如果我们编写一个多线程程序（稍后会详细介绍），我们将需要多个栈（每个线程一个），但只有一个堆。 在典型的体系结构中，堆是`Data segment`的一部分，并从代码和全局变量的上方开始。 ## 程序需要调用 brk 或 sbrk 吗？ 通常不会（虽然调用`sbrk(0)`会很有趣，因为它会告诉您堆当前的结束位置）。而程序使用`malloc,calloc,realloc`和`free`，它们是 C 库的一部分。当需要额外的堆内存时，这些函数的内部实现将调用`sbrk`。 ```c void *top_of_heap = sbrk(0); malloc(16384); void *top_of_heap2 = sbrk(0); printf("The top of heap went from %p to %p \n", top_of_heap, top_of_heap2); ``` 输出示例：`The top of heap went from 0x4000 to 0xa000` ## 什么是 calloc？ 与`malloc`不同，`calloc`将内存内容初始化为零，并且还采用两个参数（项目数和每个项目的字节大小）。 `calloc`的简单但可读的实现如下所示： ```c void *calloc(size_t n, size_t size) { size_t total = n * size; // Does not check for overflow! void *result = malloc(total); if (!result) return NULL; // If we're using new memory pages // just allocated from the system by calling sbrk // then they will be zero so zero-ing out is unnecessary, memset(result, 0, total); return result; } ``` 这些局限性的高级讨论是 [](http://locklessinc.com/articles/calloc/) 。 程序员经常使用`calloc`而不是在`malloc`之后显式调用`memset`，将存储器内容设置为零。注意`calloc(x,y)`与`calloc(y,x)`相同，但您应遵循本手册的惯例。 ```c // Ensure our memory is initialized to zero link_t *link = malloc(256); memset(link, 0, 256); // Assumes malloc returned a valid address! link_t *link = calloc(1, 256); // safer: calloc(1, sizeof(link_t)); ``` ## 为什么 sbrk 首先返回的内存初始化为零？ 如果操作系统没有将物理 RAM 的内容清零，则一个进程可能会了解先前使用过该内存的另一个进程的内存。这将是一个安全漏洞。 不幸的是，这意味着对于在释放任何内存之前的`malloc`请求和简单程序（最终使用系统中新保留的内存），内存 _ 通常为 _ 为零。然后程序员错误地写 C 程序，假设 malloc 的内存 _ 总是 _ 为零。 ```c char* ptr = malloc(300); // contents is probably zero because we get brand new memory // so beginner programs appear to work! // strcpy(ptr, "Some data"); // work with the data free(ptr); // later char *ptr2 = malloc(308); // Contents might now contain existing data and is probably not zero ``` ## 为什么 malloc 总是将内存初始化为零？ 性能！我们希望 malloc 尽可能快。将内存清零可能是不必要的。 ## 什么是 realloc 以及何时使用它？ `realloc`允许您调整先前在堆上分配的现有内存分配（通过 malloc，calloc 或 realloc）。 realloc 最常见的用途是调整用于保存值数组的内存。下面提出了一个简单但可读的 realloc 版本 ```c void * realloc(void * ptr, size_t newsize) { // Simple implementation always reserves more memory // and has no error checking void *result = malloc(newsize); size_t oldsize = ... //(depends on allocator's internal data structure) if (ptr) memcpy(result, ptr, newsize < oldsize ? newsize : oldsize); free(ptr); return result; } ``` INCORRECT 使用 realloc 如下所示： ```c int *array = malloc(sizeof(int) * 2); array[0] = 10; array[1] = 20; // Ooops need a bigger array - so use realloc.. realloc (array, 3); // ERRORS! array[2] = 30; ``` 上面的代码包含两个错误。首先，我们需要 3 * sizeof（int）字节而不是 3 字节。其次，realloc 可能需要将存储器的现有内容移动到新位置。例如，可能没有足够的空间，因为已经分配了相邻的字节。正确使用 realloc 如下所示。 ```c array = realloc(array, 3 * sizeof(int)); // If array is copied to a new location then old allocation will be freed. ``` 强大的版本也会检查`NULL`返回值。注意`realloc`可用于增长和缩小分配。 ## 我在哪里可以阅读更多？ 请参见[手册页](http://man7.org/linux/man-pages/man3/malloc.3.html)！ ## 内存分配快速有多重要？ 非常！在大多数应用程序中，分配和取消分配堆内存是一种常见操作。 ## 分配简介 ## 什么是最愚蠢的 malloc 和免费实现以及它有什么问题？ ```c void* malloc(size_t size) // Ask the system for more bytes by extending the heap space. // sbrk Returns -1 on failure void *p = sbrk(size); if(p == (void *) -1) return NULL; // No space left return p; } void free() {/* Do nothing */} ``` 上述实现存在两个主要缺点： * 系统调用很慢（与库调用相比）。我们应该保留大量的内存，只是偶尔要求系统提供更多内存。 * 没有重用已释放的内存。我们的程序永远不会重用堆内存 - 它只是不断要求更大的堆。 如果在典型程序中使用此分配器，则该过程将很快耗尽所有可用内存。相反，我们需要一个可以有效使用堆空间的分配器，并且只在必要时请求更多内存。 ## 什么是贴装策略？ 在程序执行期间，内存被分配和解除分配（释放），因此堆内存中的间隙（空洞）可以重新用于将来的内存请求。内存分配器需要跟踪当前分配的堆的哪些部分以及哪些部分可用。 假设我们当前的堆大小是 64K，但并非所有的大小都在使用中，因为一些早期的 malloc 内存已被程序释放： | 16KB 免费 | 分配 10KB | 1KB 免费 | 分配 1KB | 30KB 免费 | 分配 4KB | 2KB 免费 | | --- | --- | --- | --- | --- | --- | --- | 如果执行了 2KB 的新 malloc 请求（`malloc(2048)`），`malloc`应该在哪里保留内存？它可以使用最后 2KB 的孔（恰好是完美的尺寸！）或者它可以分开另外两个自由孔中的一个。这些选择代表不同的放置策略。 无论选择哪个孔，分配器都需要将孔分成两个：新分配的空间（将返回到程序中）和一个较小的孔（如果有剩余空间）。 完美贴合策略找到足够大小（至少 2KB）的最小孔： | 16KB free | 10KB allocated | 1KB free | 1KB allocated | 30KB free | 4KB allocated | `2KB HERE!` | | --- | --- | --- | --- | --- | --- | --- | 最差的策略是找到足够大的最大孔（所以将 30KB 的孔分成两个）： | 16KB free | 10KB allocated | 1KB free | 1KB allocated | `2KB HERE!` | `28KB free` | 4KB allocated | 2KB free | | --- | --- | --- | --- | --- | --- | --- | --- | 第一个拟合策略找到第一个足够大小的可用孔（将 16KB 孔分成两个）： | `2KB HERE!` | `14KB free` | 10KB allocated | 1KB free | 1KB allocated | 30KB free | 4KB allocated | 2KB free | | --- | --- | --- | --- | --- | --- | --- | --- | ## 什么是外部碎片？ 在下面的例子中，64KB 的堆内存中，分配了 17KB，47KB 是免费的。但是，最大的可用块只有 30KB，因为我们可用的未分配堆内存被分段为更小的块。 | `16KB free` | 10KB allocated | 1KB free | 1KB allocated | 30KB free | 4KB allocated | 2KB free | | --- | --- | --- | --- | --- | --- | --- | ## 放置策略对外部碎片和性能有何影响？ 不同的策略以非显而易见的方式影响堆内存的碎片，这只能通过数学分析或在真实条件下仔细模拟（例如模拟数据库或 Web 服务器的内存分配请求）来发现。例如，乍一看最合适似乎是一个很好的策略，但是，如果我们找不到一个尺寸合适的孔，那么这个位置会产生许多微小的不可用孔，导致高度碎裂。它还需要扫描所有可能的孔。 首次合身的优势在于它不会评估所有可能的展示位置，因此速度更快。 由于 Worst-fit 以最大的未分配空间为目标，因此如果需要大量分配，则选择较差。 在实践中，首次适合和下一次适合（这里未讨论）通常是常见的放置策略。存在混合方法和许多其他替代方案（请参阅实现内存分配器页面）。 ## 编写堆分配器有哪些挑战？ 主要挑战是， * 需要最小化碎片（即最大化内存利用率） * 需要高性能 * 繁琐的实现（使用链表和指针算法的大量指针操作） 一些额外的评论： 碎片和性能都取决于应用程序分配配置文件，可以对其进行评估但不能预测，并且在实践中，特定用途条件不足，专用分配器通常可以超出通用实现。 分配器事先不知道程序的内存分配请求。即使我们这样做，这就是[背包问题](http://en.wikipedia.org/wiki/Knapsack_problem)，它已知是 NP 难！ ## 你如何实现内存分配器？ 好问题。 [实现内存分配器](https://github.com/angrave/SystemProgramming/wiki/Memory%2C-Part-2%3A-Implementing-a-Memory-Allocator)