Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

10.3 堆与内存管理

相对于栈而言，堆这片内存面临一个稍微复杂的行为模式：在任意时刻，程序可能发出请求，要么申请一段内存，要么释放一段已申请过的内存，而且申请的大小从几个字节到数GB都是有可能的，我们不能假设程序会一次申请多少堆空间，因此，堆的管理显得较为复杂。下面让我们来了解一下堆的工作原理。

10.3.1 什么是堆

光有栈对于面向过程的程序设计还远远不够，因为栈上的数据在函数返回的时候就会被释放掉，所以无法将数据传递至函数外部。而全局变量没有办法动态地产生，只能在编译的时候定义，有很多情况下缺乏表现力。在这种情况下，堆（Heap）是唯一的选择。

堆是一块巨大的内存空间，常常占据整个虚拟空间的绝大部分。在这片空间里，程序可以请求一块连续内存，并自由地使用，这块内存在程序主动放弃之前都会一直保持有效。下面是一个申请堆空间最简单的例子。

int main()
{
    char * p = (char*)malloc(1000);
    /* use p as an array of size 1000*/
    free(p);
}

在第3行用malloc申请了1000个字节的空间之后，程序可以自由地使用这1000个字节，直到程序用free函数释放它。

那么malloc到底是怎么实现的呢？有一种做法是，把进程的内存管理交给操作系统内核去做，既然内核管理着进程的地址空间，那么如果它提供一个系统调用，可以让程序使用这个系统调用申请内存，不就可以了吗？当然这是一种理论上可行的做法，但实际上这样做的性能比较差，因为每次程序申请或者释放堆空间都需要进行系统调用。我们知道系统调用的性能开销是很大的，当程序对堆的操作比较频繁时，这样做的结果是会严重影响程序的性能的。比较好的做法就是程序向操作系统申请一块适当大小的堆空间，然后由程序自己管理这块空间，而具体来讲，管理着堆空间分配的往往是程序的运行库。

运行库相当于是向操作系统"批发"了一块较大的堆空间，然后"零售"给程序用。当全部"售完"或程序有大量的内存需求时，再根据实际需求向操作系统"进货"。当然运行库在向程序零售堆空间时，必须管理它批发来的堆空间，不能把同一块地址出售两次，导致地址的冲突。于是运行库需要一个算法来管理堆空间，这个算法就是堆的分配算法。不过在了解具体的分配算法之前，我们先来看看运行库是怎么向操作系统批发内存的。

10.3.2 Linux进程堆管理

从本章的第一节可知，进程的地址空间中，除了可执行文件、共享库和栈之外，剩余的未分配的空间都可以被用来作为堆空间。Linux下的进程堆管理稍微有些复杂，因为它提供了两种堆空间分配的方式，即两个系统调用：一个是brk()系统调用，另外一个是mmap()。brk()的C语言形式声明如下：

int brk(void* end_data_segment)

brk()的作用实际上就是设置进程数据段的结束地址，即它可以扩大或者缩小数据段（Linux下数据段和BSS合并在一起统称数据段）。如果我们将数据段的结束地址向高地址移动，那么扩大的那部分空间就可以被我们使用，把这块空间拿来作为堆空间是最常见的做法之一（我们还将在第12章详细介绍brk的实现）。Glibc中还有一个函数叫sbrk，它的功能与brk类似，只不过参数和返回值略有不同。sbrk以一个增量（Increment）作为参数，即需要增加（负数为减少）的空间大小，返回值是增加（或减少）后数据段结束地址，这个函数实际上是对brk系统调用的包装，它是通过brk()实现的。

mmap()的作用和Windows系统下的VirtualAlloc很相似，它的作用就是向操作系统申请一段虚拟地址空间，当然这块虚拟地址空间可以映射到某个文件（这也是这个系统调用的最初的作用），当它不将地址空间映射到某个文件时，我们又称这块空间为匿名（Anonymous）空间，匿名空间就可以拿来作为堆空间。它的声明如下：

void *mmap(
   void *start, 
   size_t length, 
   int prot, 
   int flags,
   int fd, 
   off_t offset);

mmap的前两个参数分别用于指定需要申请的空间的起始地址和长度，如果起始地址设置为0，那么Linux系统会自动挑选合适的起始地址。prot/flags这两个参数用于设置申请的空间的权限（可读、可写、可执行）以及映射类型（文件映射、匿名空间等），最后两个参数是用于文件映射时指定文件描述符和文件偏移的，我们在这里并不关心它们。

glibc的malloc函数是这样处理用户的空间请求的：对于小于128KB的请求来说，它会在现有的堆空间里面，按照堆分配算法为它分配一块空间并返回；对于大于128KB的请求来说，它会使用mmap()函数为它分配一块匿名空间，然后在这个匿名空间中为用户分配空间。当然我们直接使用mmap也可以轻而易举地实现malloc函数：

void *malloc(size_t nbytes)
{
    void* ret = mmap(0, nbytes, PROT_READ | PROT_WRITE,
        MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
    if (ret == MAP_FAILED)
        return 0;
    return ret;
}

mmap的详细使用说明请查阅Linux的manpage

由于mmap()函数与VirtualAlloc()类似，它们都是系统虚拟空间申请函数，它们申请的空间的起始地址和大小都必须是系统页的大小的整数倍，对于字节数很小的请求如果也使用mmap的话，无疑是会浪费大量的空间的，所以上述的做法仅仅是演示而已，不具有实用性。

了解了Linux系统对于堆的管理之后，可以再来详细分析一下第6章里面的一个问题，那就是malloc到底一次能够申请的最大空间是多少？为了回答这个问题，就不得不再回头仔细研究一下图9-1了。我们可以看到在有共享库的情况下，留给堆可以用的空间还有两处。第一处就是从BSS段结束到0x40 000 000，即大约1 GB不到的空间；第二处是从共享库到栈的这块空间，大约是2 GB不到。这两块空间大小都取决于栈、共享库的大小和数量。于是可以估算到malloc最大的申请空间大约是2 GB不到，这似乎与在第6章中得到的2.9 GB的实验结论并不一致。

那么事实是怎么样的呢？实际上2.9GB的结论是对的，2GB的推论也并没有错。造成这种差异的是因为不同的Linux内核版本造成的。因为在图9-1里面所看到的共享库的装载地址为0x40 000 000，这实际上已经是过时了的，在Linux内核2.6版本里面，共享库的装载地址已经被挪到了靠近栈的位置，即位于0xbfxxxxxx附近（这一点从前面的章节中察看/proc/xxx/maps也可以验证），所以从0xbfxxxxxx到进程用brk()设置的边界末尾简直是一马平川，中间没有任何空间占用的情况（如果使用静态链接来产生可执行文件，这样就更没有共享库的干扰了）。所以从理论可以推论，2.6版的Linux的malloc的最大空间申请数应该在2.9GB左右（其中可执行文件占去一部分、0x080 400 000之前的地址占去一部分、栈占去一部分、共享库占去一部分）。

还有其他诸多因素会影响malloc的最大空间大小，比如系统的资源限制（ulimit）、物理内存和交换空间的总和等。我曾经在一台只有512MB内存和1.5GB交换空间的机器上测试malloc的最大空间申请数，无论怎样结果都不会超过1.9GB左右，让我十分困惑。后来发现原来是内存+交换空间的大小太小，导致mmap申请空间失败。因为mmap申请匿名空间时，系统会为它在内存或交换空间中预留地址，但是申请的空间大小不能超出空闲内存+空闲交换空间的总和。

10.3.3 Windows进程堆管理

为了了解Windows操作系统是如何"批发"堆空间给应用程序的，还是得先来回顾一下Windows系统中进程的地址空间的分布。一个普通的Windows进程的地址空间分布可以如图10-14所示。


图10-14 Window进程地址空间分布

可以看到，Windows的进程将地址空间分配给了各种EXE、DLL文件、堆、栈。其中EXE文件一般位于0x00 400 000起始的地址；而一部分DLL位于0x10 000 000起始的地址，如运行库DLL；还有一部分DLL位于接近0x80 000 000的位置，如系统DLL，NTDLL.DLL、Kernel32.DLL。

栈的位置则在0x00 030 000和EXE文件后面都有分布，可能有读者奇怪为什么Windows需要这么多栈呢？我们知道，每个线程的栈都是独立的，所以一个进程中有多少个线程，就应该有多少个对应的栈，对于Windows来说，每个线程默认的栈大小是1MB，在线程启动时，系统会为它在进程地址空间中分配相应的空间作为栈，线程栈的大小可以由创建线程时CreateThread的参数指定。

在分配完上面这些地址以后，Windows的进程地址空间已经是支离破碎了。当程序向系统申请堆空间时，只好从这些剩下的还没有被占用的地址上分配。Windows系统提供了一个API叫做VirtualAlloc()，用来向系统申请空间，它与Linux下的mmap非常相似。实际上VirtualAlloc()申请的空间不一定只用于堆，它仅仅是向系统预留了一块虚拟地址，应用程序可以按照需要随意使用。

在使用VirtualAlloc()函数申请空间时，系统要求空间大小必须为页的整数倍，即对于x86系统来说，必须是4096字节的整数倍。很明显，这就是操作系统的"批发"内存的接口函数了，4096字节起批，而且只能是4096字节的整数倍，多了少了都不行。那么应用程序作为最终的"消费者"，如果它直接向操作系统申请内存的话，难免会造成大量的浪费，比如程序只需要4097个字节的空间，它也必须申请8192字节。

当然，在Windows下我们也可以自己实现一个分配的算法，首先通过VirtualAlloc向操作系统一次性批发大量空间，比如10MB，然后再根据需要分配给程序。不过这么常用的分配算法已经被各种系统、库实现了无数遍，一般情况下我们没有必要再重复发明轮子，自己再实现一个，用现成的就可以了。在Windows中，这个算法的实现位于堆管理器（Heap Manager）。堆管理器提供了一套与堆相关的API可以用来创建、分配、释放和销毁堆空间：

  • HeapCreate：创建一个堆。
  • HeapAlloc：在一个堆里分配内存。
  • HeapFree：释放已经分配的内存。
  • HeapDestroy：摧毁一个堆。

这四个API的作用很明显，HeapCreate就是创建一个堆空间，它会向操作系统批发一块内存空间（它也是通过VirtualAlloc()实现的），而HeapAlloc就是在堆空间里面分配一块小的空间并返回给用户，如果堆空间不足的话，它还会通过VirtualAlloc向操作系统批发更多的内存直到操作系统也没有空间可以分配为止。HeapFree和HeapDestroy的作用就更不言而喻了。

Windows 堆管理器的位置

上面四个函数HeapCreate、HeapAlloc、HeapFree和HeapDestroy其实就是堆管理器的核心接口，堆管理器实际上存在于Windows的两个位置。一份是位于NTDLL.DLL中，这个DLL是Windows操作系统用户层的最底层DLL，它负责Windows子系统DLL与Windows内核之间的接口（我们在后面还会介绍Windows子系统），所有用户程序、运行时库和子系统的堆分配都是使用这部分的代码；而在Windows内核Ntoskrnl.exe中，还存在一份类似的堆管理器，它负责Windows内核中的堆空间分配（内核堆和用户的堆不是同一个），Windows内核、内核组件、驱动程序使用堆时用到的都是这份堆分配代码，内核堆管理器的接口都由RtlHeap开头。

每个进程在创建时都会有一个默认堆，这个堆在进程启动时创建，并且直到进程结束都一直存在。默认堆的大小为1MB，不过我们可以通过链接器的/HEAP参数指定可执行文件的默认堆大小，这样系统在创建进程时就会按照可执行文件所指定的大小创建默认堆。当然1MB的堆空间对很多程序来说是不够用的，如果用户申请的空间超过1MB，堆管理器就会扩展堆的大小，它会通过VirtualAlloc向系统申请更多的空间。

通过前面介绍的Windows进程地址空间分布我们知道，一个进程中能够分配给堆用的空间不是连续的。所以当一个堆的空间已经无法再扩展时，我们必须创建一个新的堆。但是这一切都不需要用户操作，因为运行库的malloc函数已经解决了这一切，它实际上是对Heapxxxx系列函数的包装，当一个堆空间不够时，它会在进程中创建额外的堆。

所以进程中可能存在多个堆，但是一个进程中一次性能够分配的最大的堆空间取决于最大的那个堆。从上面的图中我们可以看到，Heap5应该是最大的一个堆，它的大小大约是1.5GB～1.7GB，这取决于进程所加载的DLL数量和大小。我们在前面的章节中说过的Windows下能够通过malloc申请的最大的一块堆空间大约是1.5GB就很好解释了。

Q&A

**Q：**我可以重复释放两次堆里的同一片内存吗？

**A：**不能。几乎所有的堆实现里，都会在重复释放同一片堆里的内存时产生错误。glibc甚至能检测出这样的错误，并给出确切的错误信息。

**Q：**我在有些书里看到说堆总是向上增长，是这样的吗？

**A：**不是，有些较老的书籍针对当时的系统曾做出过这样的断言，这在当时可能是正确的。因为当时的系统多是类unix系统，它们使用类似于brk的方法来分配堆空间，而brk的增长方向是向上的。但随着Windows的出现，这个规律被打破了。在Windows里，大部分堆使用HeapCreate产生，而HeapCreate系列函数却完全不遵照向上增长这个规律。

**Q：**调用malloc会不会最后调用到系统调用或者API？

**A：**这个取决于当前进程向操作系统批发的那些空间还够不够用，如果够用了，那么它可以直接在仓库里取出来卖给用户；如果不够用了，它就只能通过系统调用或者API向操作系统再进一批货了。

**Q：**malloc申请的内存，进程结束以后还会不会存在？

**A：**这是一个很常见的问题，答案是很明确的：不会存在。因为当进程结束以后，所有与进程相关的资源，包括进程的地址空间、物理内存、打开的文件、网络链接等都被操作系统关闭或者收回，所以无论malloc申请了多少内存，进程结束以后都不存在了。

**Q：**malloc申请的空间是不是连续的？

**A：**在分析这个问题之前，我们首先要分清楚"空间"这个词所指的意思。如果"空间"是指虚拟空间的话，那么答案是连续的，即每一次malloc分配后返回的空间都可以看做是一块连续的地址；如果空间是指"物理空间"的话，则答案是不一定连续，因为一块连续的虚拟地址空间有可能是若干个不连续的物理页拼凑而成的。

10.3.4 堆分配算法

我们在前面的章节中已经详细介绍了堆在进程中的地址空间是如何分布的，对于程序来说，堆空间只是程序向操作系统申请划出来的一大块地址空间。而程序在通过malloc申请内存空间时的大小却是不一定的，从数个字节到数个GB都是有可能的。于是我们必须将堆空间管理起来，将它分块地按照用户需求出售给最终的程序，并且还可以按照一定的方式收回内存。其实这个问题可以归结为：如何管理一大块连续的内存空间，能够按照需求分配、释放其中的空间，这就是堆分配的算法。堆的分配算法有很多种，有很简单的（比如这里要介绍的几种方法），也有些很复杂、适用于某些高性能或者有其他特殊要求的场合。

1. 空闲链表

空闲链表（Free List）的方法实际上就是把堆中各个空闲的块按照链表的方式连接起来，当用户请求一块空间时，可以遍历整个列表，直到找到合适大小的块并且将它拆分；当用户释放空间时将它合并到空闲链表中。

我们首先需要一个数据结构来登记堆空间里所有的空闲空间，这样才能知道程序请求空间的时候该分配给它哪一块内存。这样的结构有很多种，这里介绍最简单的一种------空闲链表。

空闲链表是这样一种结构，在堆里的每一个空闲空间的开头（或结尾）有一个头（header），头结构里记录了上一个（prev）和下一个（next）空闲块的地址，也就是说，所有的空闲块形成了一个链表。如图10-15所示。


图10-15 空闲链表分配

在这样的结构下如何分配空间呢？

首先在空闲链表里查找足够容纳请求大小的一个空闲块，然后将这个块分为两部分，一部分为程序请求的空间，另一部分为剩余下来的空闲空间。下面将链表里对应原来空闲块的结构更新为新的剩下的空闲块，如果剩下的空闲块大小为0，则直接将这个结构从链表里删除。图10-16演示了用户请求一块和空闲块2恰好相等的内存空间后堆的状态。


图10-16 空闲链表分配（2）

这样的空闲链表实现尽管简单，但在释放空间的时候，给定一个已分配块的指针，堆无法确定这个块的大小。一个简单的解决方法是当用户请求k个字节空间的时候，我们实际分配k+4个字节，这4个字节用于存储该分配的大小，即k+4。这样释放该内存的时候只要看看这4个字节的值，就能知道该内存块的大小，然后将其插入到空闲链表里就可以了。

当然这仅仅是最简单的一种分配策略，这样的思路存在很多问题。例如，一旦链表被破坏，或者记录长度的那4字节被破坏，整个堆就无法正常工作，而这些数据恰恰很容易被越界读写所接触到。

2. 位图

针对空闲链表的弊端，另一种分配方式显得更加稳健。这种方式称为位图（Bitmap），其核心思想是将整个堆划分为大量的块（block），每个块的大小相同。当用户请求内存的时候，总是分配整数个块的空间给用户，第一个块我们称为已分配区域的头（Head），其余的称为已分配区域的主体（Body）。而我们可以使用一个整数数组来记录块的使用情况，由于每个块只有头/主体/空闲三种状态，因此仅仅需要两位即可表示一个块，因此称为位图。

Q&A

假设堆的大小为1MB，那么我们让一个块大小为128字节，那么总共就有1M/128=8k个块，可以用8k/(32/2)=512个int来存储。这有512个int的数组就是一个位图，其中每两位代表一个块。当用户请求300字节的内存时，堆分配给用户3个块，并将位图的相应位置标记为头或躯体。

图10-17为一个这样的堆的实例。


图10-17 位图分配方式

这个堆分配了3片内存，分别有2/4/1个块，用虚线框标出。其对应的位图将是：

(HIGH) 11 00 00 10 10 10 11 00 00 00 00 00 00 00 10 11 (LOW)

其中11表示H（Head），10表示主体（Body），00表示空闲（Free）。

这样的实现方式有几个优点：

  • 速度快：由于整个堆的空闲信息存储在一个数组内，因此访问该数组时cache容易命中。
  • 稳定性好：为了避免用户越界读写破坏数据，我们只须简单地备份一下位图即可。而且即使部分数据被破坏，也不会导致整个堆无法工作。
  • 块不需要额外信息，易于管理。
  • 当然缺点也是显而易见的：
  • 分配内存的时候容易产生碎片。例如分配300字节时，实际分配了3个块即384个字节，浪费了84个字节。
  • 如果堆很大，或者设定的一个块很小（这样可以减少碎片），那么位图将会很大，可能失去cache命中率高的优势，而且也会浪费一定的空间。针对这种情况，我们可以使用多级的位图。

3. 对象池

以上介绍的堆管理方法是最为基本的两种，实际上在一些场合，被分配对象的大小是较为固定的几个值，这时候我们可以针对这样的特征设计一个更为高效的堆算法，称为对象池。

对象池的思路很简单，如果每一次分配的空间大小都一样，那么就可以按照这个每次请求分配的大小作为一个单位，把整个堆空间划分为大量的小块，每次请求的时候只需要找到一个小块就可以了。

对象池的管理方法可以采用空闲链表，也可以采用位图，与它们的区别仅仅在于它假定了每次请求的都是一个固定的大小，因此实现起来很容易。由于每次总是只请求一个单位的内存，因此请求得到满足的速度非常快，无须查找一个足够大的空间。

实际上很多现实应用中，堆的分配算法往往是采取多种算法复合而成的。比如对于glibc来说，它对于小于64字节的空间申请是采用类似于对象池的方法；而对于大于512字节的空间申请采用的是最佳适配算法；对于大于64字节而小于512字节的，它会根据情况采取上述方法中的最佳折中策略；对于大于128KB的申请，它会使用mmap机制直接向操作系统申请空间。