10.1 程序的内存布局

现代APP（应用程序）都运行在一个内存空间里，32bit系统有4GB地址空间。APP直接用32bit位地址寻址，称为平坦（flat）的内存模型。该模型中，整个内存是一个统一的地址空间，用户可以用一个32bit指针访问任意内存位置。

OS会将4GB内存空间分段，不同的段有不同的用途，比如Linux默认将高地址1GB分给内核。用户用剩下3GB内存空间，称为用户空间。用户空间里，不同地址区间也有特殊地位。通常，APP使用的内存空间默认区域如下：

1. 栈： 用于维护函数调用上下文，离开了栈，函数调用没法实现。通常位于用户空间最高地址处分配，Linux默认给线程分配栈大小8MB。

$ ulimit -s # 查看栈大小

2. 堆：用来容量APP动态分配的内存区域。当程序用malloc或new分配内存时，得到的内存来自堆。通常位于栈的下方（低地址方向）。堆看可能没有固定统一的存储区域，一般比栈大很多，几十MB到几百MB不等容量。

3. 动态链接库映射区：用于映射装载的动态链接库。Linux为共享库从0x40000000开始的地址分配相应的空间，并将共享库载入到该空间。

4. 可执行文件映像：存储可执行文件在内存里的映像，由装载器在装载时将可执行文件的内存读取，或映射到这里。

5. 保留区：不是一个单一的内存区域，而是对内存中受到保护而禁止访问的内存区域的总称，如大多数OS里，极小地址通常不允许访问，如NULL。C语言将无效指针赋值0，也处于这个考虑，因为0地址正常情况下，不可能有有效访问的数据。

Linux下进程地址空间布局：

图中箭头方向标明可变区尺寸增长方向。

下图是一个简化版的进程地址空间：

TIPS：写程序经常出现“段错误（segment fault）”或者“非法操作，该内存地址不能read/write”的错误信息，是怎么回事？
这是典型的非法指针解引用造成的错误。当指针指向一个不允许读或写的内存地址，而程序试图利用指针来读写改地址的时候，就会出现这个错误。在Linux或Windows的内存布局中，有些地址始终不能读写的，如0地址。还有些地址是一开始不允许读写，APP必事先现请求获取这些地址的读写权，或者某些地址一开始并没有映射到实际的物理内存，APP必须事先请求将这些地址映射到实际的物理地址（commit），之后才能自由读写这片内存。
当指针指向这些区域的时候，对指向它的内存进行读写就会引发错误。造成这样问题普遍原因有2种：

1. 程序员将指针初始化为NULL，之后没有给它一个合理的值就开始使用指针；
2. 程序员没有初始化栈上的指针（随机值），就开始直接使用指针；

10.2 栈与调用习惯

10.2.1 什么是栈

在经典的OS里，栈总是向下增长的。在i386下，栈顶由esp寄存器进行定位。压栈的操作使栈顶地址减小，弹出的操作使栈顶地址增大。
堆栈帧
栈保存了一个函数调用所需要的维护信息，常称为堆栈帧（Stack Frame）或活动记录（Activate Record）。一般包括以下几个方面：

1. 函数的返回地址和参数；
2. 临时变量，包括非静态局部变量，以及编译器自动生成的其他临时变量；
3. 保存的上下文，包括函数调用前后需要保持不变的寄存器；

在i386中，一个函数的活动记录用ebp和esp 2个寄存器划定范围。
esp指向栈的顶部，也就指向了当前函数的获得记录的顶部；ebp指向函数活动记录的一个固定位置，称为帧指针（Frame Pointer）。一个常见活动记录示例：

一个i386下的函数总是这样调用：

1. 把所有或一部分参数压入栈中，如果有其他参数没有入栈，那么使用某些特定的寄存器传递； -- 函数参数
2. 把当前指令的下一条指令的地址压入栈中； -- 返回地址
3. 跳转到函数体执行；

第2步和第3步由指令call一起执行。跳转到函数体之后即开始执行函数，而i386函数体的“标准”开头（函数体）是这样的：

1. push ebp：把epb压入栈中（称为old ebp）；
2. mov ebp,esp：ebp = esp （此时ebp指向栈顶，而此时栈顶就是old ebp）； -- 用于返回时 恢复以前的ebp值
3. 【可选】sub esp,XXX：在栈上分配XXX字节的临时空间； -- 用于返回时恢复寄存器的值
4. 【可选】push XXX：如有必要，保存名为XXX寄存器（可重复多个）；

把ebp压入栈中，是为了在函数返回的时候，便于恢复以前的ebp值。而之所以可能要保存一些寄存器，在于编译器可能要求某些寄存器在调用前后保持不变，那么函数在调用开始时将这些寄存器的值压入栈中，在结束后再取出。函数返回时，标准结尾：

1. 【可选】pop XXX：如有必要，恢复保存过的寄存器（可重复多个）；
2. mov esp,ebp：恢复ESP同时回收局部变量空间；
3. pop ebp：从栈中恢复保存的ebp的值；
4. ret：从栈中取得返回地址，并跳转到该位置；

TIPS：GCC编译器有个参数叫-fomit-frame-pointer可以取消帧指针（ebp），而是通过esp直接计算帧上变量的位置。好处是可以多一个ebp寄存器可供使用，但坏处很多，如帧上寻址速度会变慢，而且无法准确定位函数的调用轨迹（Strace Trace）。除非很清楚在做什么，否则不建议用这个参数。

示例：下面来看看反汇编函数，生成的汇编代码
C源码

int foo()
{
    return 123;
}

用VS 2017在debug模式下，窗口->反汇编，进行查看反汇编代码

int foo()
{
// 第1步 保存ebp，让ebp指向目前栈顶
00DB16F0  push        ebp  // 把ebp压入栈中（old ebp），是函数“标准”开头
00DB16F1  mov         ebp,esp  // ebp = esp，此时ebp指向栈顶，是函数“标准”开头
// 第2步 在栈上开辟一块空间
00DB16F3  sub         esp,0C0h  // 将栈扩大了0xC0个字节，多出来空间值并不确定，用于存储局部变量、某些临时数据及调试信息，是函数“标准”开头【可选】部分
// 第3步 保存寄存器 ebx，esi，edi
// 用于函数返回时恢复（说明函数可能会修改这些寄存器）
00DB16F9  push        ebx  
00DB16FA  push        esi  
00DB16FB  push        edi  
// 第4步 加入调试信息
00DB16FC  lea         edi,[ebp-0C0h]  // edi = ebp - 0xC0
00DB1702  mov         ecx,30h  // exc = 0x30
00DB1707  mov         eax,0CCCCCCCCh  // eax = 0CCCCCCCC
00DB170C  rep stos    dword ptr es:[edi]  
/*
等价于
for (; ecx != 0; --ecx, edi += 4)
    *((int*)edi) = eax;
*/

00DB170E  mov         ecx,offset _3F6EF3D3_testlinux@cpp (0DBC003h)  
00DB1713  call        @__CheckForDebuggerJustMyCode@4 (0DB1203h)  
    return 123;
// 第5步 返回123（0x7B），这里返回值通过eax寄存器传递的
00DB1718  mov         eax,7Bh  
}
// 第6步 从栈上恢复edi, esi, ebx寄存器（与入栈顺序相反）
00DB171D  pop         edi  
00DB171E  pop         esi  
00DB171F  pop         ebx

00DB1720  add         esp,0C0h  // esp = esp + 0xC0
00DB1726  cmp         ebp,esp  // 比较ebp和esp, ebp - esp
00DB1728  call        __RTC_CheckEsp (0DB120Dh)  
// 第7步 恢复进入函数前的esp（栈顶）和ebp（帧指针）
00DB172D  mov         esp,ebp  // esp = ebp, 恢复esp
00DB172F  pop         ebp   //  恢复ebp
// 第8步 使用ret指令返回
00DB1730  ret  

有些场合下，编译器生成函数的进入和退出指令时，并不按标准方式进行。如下列C函数：

1. static函数（不可在编译单元外访问（通常指.c文件））；
2. 函数在本编译单元仅被直接调用，没有显示或隐式取地址（没有使用函数指针指向该函数）；

编译器可以确信满足这两条的函数不会在其他编译单元内被调用，因而可以随意修改这个函数各方面，包括进入和退出指令序列，来达到优化目的。

注意：内联函数不会有入栈、出栈的指令，也不会有返回指令，不是真正意义上的函数。

TIPS：在VC下debug时，常常看到一些没有初始化的变量或内存区域值是“烫”或者“屯”。如：

int main()
{
    char p[12];
}

代码中数组p没有初始化，debug时，设置断点监视数组p时，就能看到数组p值都是“烫”。
这是因为，debug模式第4步，将所有分配出来的栈空间的每个byte都初始化为0xCC。0xCCCC的汉字编码就是烫。0xCDCD汉子编码是屯。

10.2.2 调用惯例

假设有个函数foo：

int foo(int n, float m)
{
    int a = 0, b = 0;
    ...
}

如果函数的调用方法传参时，限压入参数n，再是m，而foo函数却认为其调用方先压入m，后压入n，那么foo内部的m和n的值将会被交换。从而导致不能正确传参。这就需要函数调用方和被调用方，对于函数如何调用有一个明确的规范，这样的约定称为调用惯例（Calling Convention）。一个调用惯例一般规定一下内容：

1. 函数参数的传递顺序和方式
   函数参数传递方式有多种，最常见的是通过栈传递。调用方将参数压入栈中，函数自己再从栈中将参数取出。对于有多个参数的函数，调用惯例要规定调用方参数压栈顺序：从左至右，还是从右至左。
   有些调用惯例，还允许使用寄存器传递参数，以提高性能。

2. 栈的维护方式
   函数将参数压栈后，函数体会被调用，此后需要将压入栈中的参数全部弹出，以使得栈在函数调用前后保持一致。弹出工作可以由调用方来完成，也可以由函数本身来完成。

3. 名字修饰（Name-mangling）的策略
   为了链接的时候，对调用惯例进行区分，调用惯例要对函数本身的名字进行修饰。不同调用惯例有不同名字修饰策略。

C语言里，有多个调用惯例，默认是cdecl。任何一个没有显示指定调用惯例的函数都默认是cdecl惯例。如对于函数foo的声明，完整形式是：

int __cdecl foo(int n, float m);

注意:__cdecl是非标准关键字，在不同的编译器里可能有不同的写法，如在gcc里就不存在__cdecl 这样的关键字，而是用__attribute__((cdecl))。

cdecl内容：

因此，foo被修饰后就变成了_foo。调用foo时，按cdecl参数传递方式，具体堆栈操作如下：
1）将m入栈；
2）将n入栈；
3）调用_foo，该步又分为2个步骤：
a）将返回地址（调用_foo之后下一条指令的地址）压入栈；
b）跳转到_foo执行；

进入foo函数后，栈的构成结构如下图：

foo里面要保存一系列的寄存器，包括函数调用方的ebp，以及要为a和b两个局部变量分配空间。

以上布局中，如果想访问变量n，实际地址使用ebp+8。当foo返回时，程序首先会用pop恢复保存在栈里的寄存器，然后取得返回地址，返回到调用方，调用方再调整esp，将堆栈恢复。

除了cdecl调用惯例，还有别的调用惯例，如stdcall, fastcall等。

naked call调用惯例用在特殊场合，特定是编译器不产生任何包含寄存器代码。
对于C++，因为支持重载及命名空间和成员函数等，一个函数名可以对应多个函数定义，而上面的名字修饰策略无法区分各个不同名函数定义的。因此，C++有一种特殊的调用惯例：thiscall，专门用于类成员函数的调用。其特点是随编译器不同而不同，在VC里this指针存放于ecx寄存器，参数从右到左压栈，而对于gcc、thiscall和cdecl完全一样，只是将this看做函数第一个参数。
C++编译器会对函数名进行修饰，生成唯一的函数，以消除同一函数名（重载函数）的二义性。而不同编译器对函数名进行修饰的规则不同，详见名字修饰 | wikipedia。

10.2.3 函数返回值传递

函数与调用方的交互有2个渠道：参数传递，返回值。eax寄存器是传递返回值的通道：函数将返回值存储在eax中，返回后调用方在读取eax。
eax本身4byte，如果传递 > 4byte的返回值呢？
对于返回5~8byte对象的情况，几乎所有调用惯例都采用eax和edx联合返回方式。其中，eax存储返回值低4byte，edx存储高4byte。
对于超过8byte的返回值类型，通过下面代码来研究：

typedef struct big_thing
{
    char buf[128];
};

big_thing return_test()
{
    big_thing b;
    b.buf[0] = 0;
    return b;
}

int main()
{
    big_thing n = return_test();
}

return_test()返回值类型是128byte的结构，因此不可能直接用eax传递。反汇编main函数：

int main()
{
010817B0  push        ebp  // 保存ebp
010817B1  mov         ebp,esp  // esp = ebp
010817B3  sub         esp,258h  // 扩大栈空间258h byte(&n = (ebp-254h) 落在这个扩充区域)
010817B9  push        ebx  
010817BA  push        esi  
010817BB  push        edi  
010817BC  lea         edi,[ebp-258h]  
010817C2  mov         ecx,96h  
010817C7  mov         eax,0CCCCCCCCh  
010817CC  rep stos    dword ptr es:[edi]  
010817CE  mov         ecx,offset _3F6EF3D3_testlinux@cpp (0108C003h)  
010817D3  call        @__CheckForDebuggerJustMyCode@4 (01081203h)  

    big_thing n = return_test();
010817D8  lea         eax,[ebp-254h]  // 将栈上的一个地址（ebp-254h）存储在eax里
010817DE  push        eax  // 将eax中这个地址压入栈中
010817DF  call        return_test (01081316h)  // 调用return_test函数
010817E4  add         esp,4  // esp = esp + 4
010817E7  mov         ecx,20h  // ecx = 20h
010817EC  mov         esi,eax  // esi = eax = ebp - 254h
010817EE  lea         edi,[ebp-1CCh]  // 将栈上地址(ebp - 1CCh)存储在edi里
010817F4  rep movs    dword ptr es:[edi],dword ptr [esi]  // 复合指令，重复move指令直到ecx寄存器为0

010817F6  mov         ecx,20h  // ecx = 20h
010817FB  lea         esi,[ebp-1CCh]  // 将栈上地址(ebp - 1CCh)存储在esi里
01081801  lea         edi,[n]  // 将栈上地址(n)存储在edi里
01081807  rep movs    dword ptr es:[edi],dword ptr [esi]  // 复合指令, 重复move指令直到edi寄存器为0  
}

rep moves a,b意思是将b指向位置上的若干个双字节（4byte）拷贝到a指向的位置上，拷贝双字的个数由ecx指定。
rep movs及上面3行，含义相当于memcoy(a,b,ecx*4)：

memcpy(ebp - 1CCh, eax, 0x20 * 4);

地址ebp-1CCh就是变量n的地址。0x20个双字节就是128字节，正好是big_thing大小。big_thing n = return_test();及后面的汇编相当于：

return_test(ebp-254h);
memcpy(&n, (void *)eax, sizeof(n)); // eax = ebp-254h = &n, 保存了n的地址

可知，return_test返回的及饿哦固体仍然是eax传出的，不过eax存储是结构体指针。
return_test()如何返回一个结构体？ 下面是return_test汇编：

big_thing return_test()
{
...
    big_thing b;
    b.buf[0] = 0;
01081718  mov         eax,1  // eax = 1
0108171D  imul        ecx,eax,0  // ecx = eax * 0 = 0
01081720  mov         byte ptr b[ecx],0  // b[ecx] = b[0] = 0
    return b;
01081728  mov         ecx,20h  // ecx = 20h
0108172D  lea         esi,[b]  // esi = [b], 存放b的地址
01081733  mov         edi,dword ptr [ebp+8]  // edi = [ebp+8]地址
01081736  rep movs    dword ptr es:[edi],dword ptr [esi]  

01081738  mov         eax,dword ptr [ebp+8]  
}

return b;之后的汇编，可以翻译成：

memcpy([ebp+8], &b, 128);

main函数里的(ebp-258h)是什么内容？
main函数保存ebp之后，直接将栈增大258h，而&n = (ebp-254h)刚刚好落在该扩大的末尾，区间[ebp-254h, ebp-254h+128]也处于这个扩大区域内部。这块区域剩下内容，则留作它用。整体思路是：

1. 首先main函数在栈上额外开辟一个空间，并将这块空间的一部分作为传递返回值的临时对象，这里称为temp；
2. 将temp对象的地址作为隐藏参数传递给return_test函数；
3. return_test函数将数据拷贝给temp对象，并将temp对象的地址用eax传出；
4. return_test返回之后，main函数将eax指向的temp对象的内容拷贝给n；

这也就是说，如果返回值类型的尺寸太大，C语言在函数返回时会用一个临时的栈上内存区域作为中转，结果返回值对象会被拷贝2次。因此，不要轻易返回大尺寸对象，而要用对象引用或者指针，否则函数会在栈上开辟临时对象，不仅占用大量栈空间，而且还会进行频繁的复制以把返回值拷贝回调用处的赋值对象。
C++拷贝对象构造函数，通用会产生临时对象。

注意：返回对象的拷贝情况完全不具备可移植性，不同编译器产生结果可能不同。

TIPS：RVO优化返回值（Return Value Optimization）技术
下面C++代码，return_test函数返回一个对象时，对象要经过2次拷贝构造函数的调用才能完全返回对象的传递：1次是拷贝到栈上的临时对象里，另1次是把临时对象拷贝到存储返回值的对象里。
RVO优化返回值技术，可以 将构造一个cpp_obj对象b，跟将对象b拷贝拷贝到临时对象， 这2步合并成1步。

cpp_obj return_test()
{
    cpp_obj b; // 构造一个cpp_obj对象
    cout << "before return" << endl;
    return b; // 将对象b拷贝到栈上临时对象
}
==> RVO优化返回值技术：将构造一个cpp_obj对象b，跟将对象b拷贝拷贝到临时对象 这2步合并成1步
cpp_obj return_test()
{
    return cpp_obj(); // 直接将cpp_obj对象构造在栈上，减少一次复制过程
}

struct cpp_obj
{
    cpp_obj(){ cout << "ctor" << endl; }
    cpp_obj& operator=(const cpp_obj& rhs){ cout << "*operator=" << endl; return *this; }
    ~cpp_obj(){ cout << "dctor" << endl; }
}

int main()
{
    cpp_obj n;
    n = return_test(); // 从临时对象拷贝回存储返回值的对象n
}

10.3 堆与内存管理

10.3.1 什么是堆？

栈上的数据在函数返回时，会被释放掉，因此无法将数据传递至函数外部。而全局变量没有办法动态地产生，只能在编译的时候定义。而堆（Heap）是解决这个问题的更好选择。
堆是一块巨大内存空间，占据进程的整个虚拟空间的绝大部分。程序可以申请一块连续内存、自由使用，会在程序主动放弃之前一直保持有效。申请堆空间最简单的例子：

int main()
{
    char *p = (char *)malloc(1000); // 申请1000byte堆空间，返回首部指针p
    free(p); // 释放申请的对空间
}

malloc如何实现的？
如果把进程的内存管理交给OS内核去做，提供程序系统调用申请内存。理论上可行，但实际上性能很差，因为每次程序申请或释放堆空间都需要进行系统调用，而系统调用系统开销很大，当程序对堆的操作比较频繁时，会严重影响程序的性能。
比较好的做法是程序向OS申请一块适当大小的堆空间，然后由程序自己管理，具体来说，管理着堆空间分配的往往是程序的运行库。
运行库相当于向OS“批发”一块较大堆空间，然后“零售”给程序用。当全部“售完”或者程序有大量的内存需求时，再跟进实际需求向OS“进货”。运行库在向程序零售对空间时，必须管理它批发来的堆空间，不能把同一块地址出售两次，而导致地址冲突。用于运行库管理堆空间的算法，就是堆的分配算法。
先看运行库如何向OS批发内存，再看堆分配算法。

10.3.2 Linux进程管理

Linux提供了2种堆空间分配方式，即2个系统调用：brk(), mmap()。

• brk

int brk(void *end_data_segment);

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

• mmap

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

malloc()作用类似于Windows下的VirtualAlloc，向OS申请一段虚拟地址空间，当然这块虚拟地址空间可以映射到某个文件（最初的作用），当它不讲地址空间映射到某个文件时，称这块空间为匿名（Anoymous）空间，匿名空间可以拿来作为堆空间。

参数：
start和length 指定需要申请的空间的起始地址和长度，如果起始地址为0（NULL），那么Linux会自动挑选合适的起始地址；
port/flags 用于设置申请的空间权限（可读、可写、可执行）以及映射类型（文件映射、匿名空间等）；
fd和offset 用于文件映射时指定文件描述符和文件偏移；

glibc的malloc这样处理用户空间请求的：对于 < 128KB请求，会在现有堆空间里，按堆分配算法为它分配一块空间并返回；对于 > 128KB的请求，会使用mmap()函数为它分配一块匿名空间，然后这个匿名空间中为用户分配空间。

示例：用mmap实现malloc函数演示，不具备实用性

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

注意：mamap和VirtualAlloc类似，申请空间的起始地址和大小都必须是系统页大小的整数倍，对于字节数很小的请求，如果也用mmap，会造成大量空间浪费。

malloc一次到底能够申请最大空间是多少？
如下图，在有共享库的情况下，留给堆用的空间有两处（unused）：1）从BSS段结束到0x4000 0000，不到1GB空间；2）从共享库到栈这块，不到2GB。这两块空间大小取决于栈，共享库的大小和数量。估算出malloc最大申请空间是约2GB不到，不过有另外一种结论是2.9GB。
事实上，2.9GB结论是对的，2GB推论是基于老的Linux内核版本。Linux内核2.6以后，共享库装载地址已经由0x4000 0000移动到了靠近栈的位置，即0xbfxx xxxx附近（可查看/proc/xxx/maps）。因此，Linux 2.6的malloc最大申请空间数，理论上应该在2.9GB左右。
影响malloc申请最大空间因素：可执行文件，0x8040 0000之前的地址，栈，共享库。其他的还有系统资源限制（ulimit）、物理内存和交换空间的总和等。

10.3.3 Windows进程堆管理

Windows下，进程创建时默认堆大小1MB，用户申请空间超过1MB时，堆管理器就会通过VirtualAlloc向OS申请更多空间。Windows下，通过malloc申请的最大一块堆空间大约1.5GB。
其他略。

• 常见问题

1. 我可以重复释放2次堆里同一片内存吗？
   不能。几乎所有堆实现里，都会在重复释放同一片堆里的内存时产生错误。glibc甚至能检测出这样的错误，并给出错误信息。

2. 我看到有些书说堆总是向上增长，是这样吗？
   不是，有些较老的书籍针对当时的系统做出这样的断言，在当时可能是正确的。因为当时的系统多是类unix系统，使用类似于brk的方法来分配堆空间，而brk的增长方向是向上的。但Windows打破了这个规律，Windows大部分堆使用HeapCreate产生，而HeapCreate系列函数完全不遵照向上增长这个规律。

3. 调用malloc会不会最后调用系统调用或者API？
   取决于当前进程向OS批发的空间十分够用，如果够用，就可以直接在仓库里取出给用户；如果不够用，就只能通过系统调用或API向OS再批发。

4. malloc申请的内存，进程接受后会不会还存在？
   不会存在。因为进程结束以后，所有与进程相关的资源，包括进程的地址空间、物理内存、打开的文件、网络连接等都被OS关闭或回收，因此无论malloc申请了多少内存，进程结束后都不存在。

5. malloc申请的空间是不是连续的？
   如果“空间”指的是虚拟空间，那么答案是连续，每次malloc分配后返回的空间可以看做是一块连续地址；如果空间是指“物理空间”，则答案是不一定连续，因为一块连续的虚拟地址空间有可能是若干个不连续的物理页拼凑而成的。

10.3.4 堆分配算法

堆如何管理一大块连续的内存空间，按需分配、释放其中空间，这就是堆分配算法要解决的问题。堆分配算法有很多种，这里介绍几种：

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

空闲链表结构：在堆里每个空闲空间（free）开头（或结尾）有一个头（header），头结构里记录了上一个（prev）和下一个（next）空闲块的地址，i.e. 所有的空闲块形成了一个链表。如下图：

这样的结构如何分配空间？
首先，在空闲链表里查找足够容纳请求大小的一个空闲块；然后，将这个块分为两部分：程序请求的空间 + 剩余下来的空闲空间。后面，将链表里对应原来空闲块结构更新为新的剩下的空闲块，如果剩下为0，则直接将这个结构从链表里删除。

示例：分配空闲块free(2)，其大小刚好等于申请空间大小，从空闲链表里删去free(2)

优点：实现简单；
缺点：
1）释放空间的时候，给定一个已分配块的指针，堆无法确定这个块的大小。解决办法：当用户请求kbyte空间时，实际分配k+4byte，多出4byte用于存储该分配的大小。释放时，只要看这4byte值，即可知道该快内存大小。
2）一旦链表被破坏，或者记录长度的4byte被破坏，整个堆就无法正常工作。而这些数据恰好容易被越界读写访问到。

2. 位图
位图（bitmap）解决了空闲链表的弊端，更加稳健，核心思想：将整个堆划分为大量的块（block），每个块大小相同。当用户请求内存时，总是分配整数个块空间给用户，第一个块称为已分配区域的头（Head），其余称为已分配区域的主体（Body）。可以用一个整数数组来记录块的使用情况，因为每个块只有头、主体、空闲三种状态，所以仅需2bit即可表示一个块，因此称为位图。

示例1：假设对大小1MB，一个块大小128byte，那么总共有1M/128 = 8K个块，可以用8K/(32/2) = 512个int（1个int 占用32bit，每2个bit表示一个块状态）来存储。这样，有512个int的数组就是一个能表示1MB的位图，其中每2bit代表一个块。当用户请求300byte内存时，堆分配给用户3个块，并将位图相应位置标记为头或躯体。

示例2：位图分配堆的实例

上图堆分配了3片内存，分别有2/4/1个块（虚线框）。对应位图：

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

优点：
1）速度快：整个堆的空闲信息存储在一个数组内，因此访问数组时cache容易命中；
2）稳定性好：为了避免用户越界读写破坏数据，只需简单备份一下位图即可。而且即使部分数据被破坏，也不会导致整个堆无法工作；
3）块不需要额外信息，易于管理；

缺点：
1）分配内存的时候，容易产生碎片。如分配了300byte，实际分配了3个块384byte，浪费84byte；
2）如果堆很大，或者设定的一个块很小（减少碎片），那么位图将会很大，可能失去cache命中率高的优势，而且也会浪费一定空间。针对这种情况，可以使用多级位图。

3. 对象池
空闲链表和位图的堆管理方法是最基本的两种，实际上应用中，被分配对象的大小是较为固定的几个值时，可以针对这一的特征设计一个更为高效的堆算法，称为对象池。

同设计模式里面的享元模式，对象池思路：
如果每次分配的空间大小一样，那么就可以按照这个每次请求分配的大小作为一个单位，把整个堆空间划分为大量的小块，每次请求的时候只需要找到一个小块即可。
对象池的管理访问可以用空闲链表，也可以用位图，区别在于它假定了每次请求的都是一个固定的大小，因此实现容易。因为每次总是请求一个单位的内存，因此请求得到的速度非常快，无需查找一个足够大的空间。

实际上很多现实应用中，堆分配算法往往是采取多种算法复合而成的。如glibc，对于<64byte空间申请采用类似于对象池的方法，而对于>512byte的申请，采用最佳适配算法；对于64byte~512byte的申请，会根据情况采用上述方法的最佳折中策略；对于>128KB申请，会使用mmap机制直接向OS申请空间。

10.4 本章小结

1）回顾了i386体系结构下程序基本内存布局，对内存结构中栈和堆进行详细介绍；
2）学习了栈在函数调用中所发挥的重要作用，以及调用惯例各方面知识；
3）了解了函数传递返回值的各种技术细节；
4）了解了构造堆的主要算法：空闲链表和位图；