在堆上分配内存

首先还是看这张经典的进程虚拟内存空间示意图。进程可以通过增加堆的大小来获得额外的内存，所谓堆是一段长度可变的连续虚拟内存，随着内存的分配和释放而增减（如图中示意的向上增长）。通常将堆的内存边界称为program break（程序中断）。

调整program break：brk()和sbrk()

改变堆的大小，其实也就是改变program break的位置。最初，program break正好位于未初始化数据段末尾之后（如图中的&end处）.

在program break的位置抬升之后，程序可以访问新分配的区域内的任何内存地址，而此时物理页尚未分配。内核会在进程首次试图访问这些虚拟内存地址时自动分配新的物理内存页。

传统的UNIX 系统提供了两个操纵program break 的系统调用：brk()和sbrk()，在Linux 中依然可用。

#include <unistd.h>

int brk(void *end_data_segment);
// Returns 0 on success, or -1 on error

void *sbrk(intptr_t increment);
// Returns previous program break on success, or (void *)-1 on error

系统调用brk()会将program break 设置为参数end_data_segment 所指定的位置。由于虚拟内存以页为单位进行分配，end_data_segment 实际会四舍五入到下一个内存页的边界处。

当试图将program break设置为一个低于其初始值（即低于&end）的位置时，有可能会导致无法预知的行为。

program break理应有一个上界，但这取决于一系列因素，包括进程对数据段大小的资源限制、内存映射、共享内存段、共享库的位置等等。

调用sbrk()将program break 在原有地址上增加从参数increment 传入的大小。（在Linux 中，sbrk()是在brk()基础上实现的一个库函数。）用于声明increment 的intptr_t 类型属于整数数据类型。若调用成功，sbrk()返回前一个program break 的地址。换言之，如果program break 增加，那么返回值是指向这块新分配内存起始位置的指针。

在堆上分配内存：malloc()和free()

一般情况下我们都使用malloc函数族来在堆上分配和释放内存而不是brk()和sbrk()系统调用。

#include <stdlib.h>

void *malloc(size_t size);
// Return pointer to allocated memory on success, or NULL on error

malloc()函数在堆上分配参数size字节大小的内存，并返回指向新分配内存起始位置处的指针，其所分配的内存未经初始化。在后面的内容中，我们把这种由malloc单次申请的内存叫做一个内存块。

由于malloc()的返回类型为void*，因而可以将其赋给任意类型的C 指针。malloc()返回的内存块所将采用字节对齐方式，总是适宜于高效访问任何类型的C 语言数据结构。在大多数硬件架构上，这实际意味着malloc是基于8 字节或16 字节边界来分配内存的。

若无法分配内存（或许是因为已经抵达program break 所能达到的地址上限），则malloc()返回NULL，并设置errno 以返回错误信息。

#include <stdlib.h>

void free(void *ptr);

free()函数释放ptr 参数所指向的内存块，该参数应该是之前由malloc()，或者其他堆内存分配函数之一所返回的地址。

一般情况下，free()并不降低program break 的位置，而是将这块内存填加到空闲内存块列表（下一节会详细介绍这个列表的具体实现）中，供后续的malloc()函数循环使用。这么做是出于以下几个原因：

• 被释放的内存块通常会位于堆的中间，而非堆的顶部，因而降低program break是不可能的。
• 这样可以减少调用sbrk()的次数，众所周知系统调用的开销并不小。
• 在大多数情况下，降低program break的位置不会对那些分配大量内存的程序有多少帮助，因为它们通常倾向于持有已分配内存或是反复释放和重新分配内存，而非释放所有内存后再持续运行一段时间。

如果传给free()的是一个空指针，那么函数将什么都不做。

仅当堆顶空闲内存积攒到“足够大”的时候，free()函数才会调用sbrk()来降低program break，至于是否足够大就取决于一些控制参数了，这样就可以有效降低对sbrk()发起调用的次数。

malloc()和free()的实现

malloc()的实现很简单。它首先会扫描之前由free()所释放的空闲内存块列表，以求找到尺寸大于或等于要求的一块空闲内存。如果这一内存块的尺寸正好与要求相当，就把它直接返回给调用者。如果是一块较大的内存，那么将对其进行分割，在将一块大小相当的内存返回给调用者的同时，把较小的那块空闲内存块保留在空闲列表中。

如果在空闲内存列表中根本找不到足够大的空闲内存块，那么malloc()会调用sbrk()以分配更多的内存。为减少对sbrk()的调用次数，malloc()并未只是严格按所需字节数来分配内存，而是以更大幅度（以虚拟内存页大小的数倍）来增加program break，并将超出部分置于空闲内存列表。

至于free()函数的实现则更为有趣。我们前面一直提到一个概念就是空闲内存块列表，但没有做具体的解释。malloc库函数族到底是如何管理这些被用户释放的内存的呢？为了空闲内存的再次分配，肯定需要知道空闲内存的大小，当malloc()分配内存块的时候，会额外分配几个字节来存放这个内存块的大小。这个字段位于这个内存块的起始位置，而malloc()的返回值实际上是这个字段之后的地址，如下图所示：

这样一个内存块就可以组织好了。当用户调用free()尝试释放这块内存的时候，会将这个内存块加入空闲内存块列表，而这个列表其实就是一个双向链表，free()会使用内存块本身的空间来存放链表指针，将自身添加到列表中，如下图所示：

可以想到，随着对内存的不断释放和重新分配，空闲列表中的空闲内存会和已分配的在用内存混杂在一起：

在这里还有一个小技巧，如果一块要释放的内存相邻的两侧也是一个空闲内存块的话，free()会将这些相邻的空闲内存块合并为一整块更大的空闲内存，这样做可以避免在空闲内存列表中出现大量的小内存碎片，这些小内存碎片可能会因为空间太小而难以满足后面的malloc()请求。

从上面的内容我们可以意识到，任何试图访问当前内存块之外的空间的动作都应该被禁止，毕竟如果不小心修改了内存块长度或者两个指针字段，将会导致严重的后果。

在栈上分配内存

和malloc函数包中的函数功能一样，alloca()也可以动态分配内存，不过不是从堆上分配内存，而是通过增加栈帧的大小从栈上分配。根据定义，当前调用函数的栈帧位于堆栈的顶部，故而这种方法是可行的。因此，帧的上方存在扩展空间，只需修改堆栈指针值即可。

#include <alloca.h>

void *alloca(size_t size);
// Return pointer to allocated block of memory

参数size 指定在堆栈上分配的字节数。函数alloca()将指向新分配的内存块的指针作为其返回值。

不需要（实际上也绝不能）调用free()来释放由alloca()分配的内存。同样，也不可能调用
realloc()来调整由alloca()分配的内存大小。

若调用alloca()造成堆栈溢出，则程序的行为无法预知。

使用alloca()来分配内存相对于malloc()有一定优势。其中之一是，alloca()分配内存的速度要快于malloc()，因为编译器将alloca()作为内联代码处理，并通过直接调整堆栈指针来实现。此外，alloca()也不需要维护空闲内存块列表。

另一个优点在于，由alloca()分配的内存随栈帧的移除而自动释放，亦即当调用alloca 的函数返回之时。之所以如此，是因为函数返回时所执行的代码会重置栈指针寄存器，使其指向前一帧的末尾（即，假设堆栈向下增长，则指向恰好位于当前栈帧起始处之上的地址）。由于在函数的所有返回路径中都无需确保去释放所有的已分配内存，一些函数的编码也变得简单得多。