21.md

内存，第 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。

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的简单但可读的实现如下所示：

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

这些局限性的高级讨论是 。

程序员经常使用calloc而不是在malloc之后显式调用memset，将存储器内容设置为零。注意calloc(x,y)与calloc(y,x)相同，但您应遵循本手册的惯例。

// 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 的内存 _ 总是 _ 为零。

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 版本

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 如下所示：

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 如下所示。

array = realloc(array, 3 * sizeof(int));
// If array is copied to a new location then old allocation will be freed.

强大的版本也会检查NULL返回值。注意realloc可用于增长和缩小分配。

我在哪里可以阅读更多？

请参见手册页！

内存分配快速有多重要？

非常！在大多数应用程序中，分配和取消分配堆内存是一种常见操作。

分配简介

什么是最愚蠢的 malloc 和免费实现以及它有什么问题？

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 以最大的未分配空间为目标，因此如果需要大量分配，则选择较差。

在实践中，首次适合和下一次适合（这里未讨论）通常是常见的放置策略。存在混合方法和许多其他替代方案（请参阅实现内存分配器页面）。

编写堆分配器有哪些挑战？

主要挑战是，

• 需要最小化碎片（即最大化内存利用率）
• 需要高性能
• 繁琐的实现（使用链表和指针算法的大量指针操作）

一些额外的评论：

碎片和性能都取决于应用程序分配配置文件，可以对其进行评估但不能预测，并且在实践中，特定用途条件不足，专用分配器通常可以超出通用实现。

分配器事先不知道程序的内存分配请求。即使我们这样做，这就是背包问题，它已知是 NP 难！

你如何实现内存分配器？

好问题。 实现内存分配器