程序员通过动态内存分配(例如 malloc
)来让程序在运行时得到虚拟内存。动态内存分配器会管理一个虚拟内存区域,称为堆(heap)。
动态内存分配器将堆视为一组不同大小的块(block)的集合,每个块就是一个连续的虚拟内存片(chunk),每个块具有两种状态:
在最开始进行内存映射时,堆是与匿名文件关联起来的,所以堆是一个全0的段,即处于空闲状态,它紧跟在未初始的数据段后面,向地址更大的方向延伸,且内核对每个进程都维护了brk
变量来指向堆顶。
动态内存分配器具有两种类型,都要求由应用程序显示分配块,但是由不同实体来负责释放已分配的块:
malloc
来分配块,再通过free
来显示释放已分配的块,C++中的new
和delete
相同。程序使用动态内存分配器来动态分配内存的意义在于:有些数据结构只有在程序运行时才知道大小。通过这种方式就无需通过硬编码方式来指定数组大小,而是根据需要动态分配内存
malloc
和free
函数C中提供了malloc显示分配器,程序可以通过malloc
函数来显式地从堆中分配块
#include <stdlib.h> void *malloc(size_t size); // 返回一个泛型void指针,需要将它强转为int*,才能通过编译
该函数会返回一个指向大小至少为size
字节的未初始化内存块的指针,且根据程序的编译时选择的字长,来确定内存地址对齐的位数,比如-m32
表示32位模式,地址与8对齐,-m64
表示64位模式,地址与16对齐。如果函数出现错误,则返回NULL,并设置errno
。我们也可以使用calloc
函数来将分配的内存块初始化为0,也可以使用realloc
函数来改变已分配块的大小。
程序可以通过free
函数来释放已分配的堆块
#include <stdlib.h> void free(void *ptr);
其中ptr
参数要指向通过malloc
、calloc
或realloc
函数获得的堆内存。
动态内存分配器可以使用mmap
和munmap
函数,也可以使用sbrk
函数来向内核申请堆内存空间,只有先申请获得堆内存空间后,才能尝试对块进行分配让应用程序使用。
#include <unistd.h> void *sbrk(intptr_t incr); int brk(void *addr);
brk
函数会将brk
设置为addr
指定的值。sbrk
函数通过将内核的brk
指针增加incr
来扩展和收缩堆,如果成功返回brk
的旧值,否则返回-1,并将errno设置为ENOMEM
。
incr
小于0时,会减小brk
来解除已分配的堆内存incr
等于0时,会返回当前的brk
值incr
大于0时,会增加brk
来分配更多的堆内存限制:
应用:
malloc
和 free
请求free
请求必须作用于已被分配的 block。分配器
malloc
请求(不能缓存或者给请求重新排序)吞吐量:
malloc
和 5000 次 free
调用,那么吞吐量是 1000 operations/second峰值内存利用率(Peak Memory Utilization):
一个系统中所有进程分配的虚拟内存的全部数量是受磁盘上的交换空间限制的,所以要尽可能最大化内存使用率。
峰值利用率就是[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-r8aEmhDZ-1631889979486)(https://www.zhihu.com/equation?tex=U_k%3D\frac{max_{i\le+k}P_i}{H_k})],即当前的聚合载荷在此之前最大的聚合载荷除以当前的堆的大小。在理想状态下,每个块的内容都是有效载荷,所以利用率为1。
影响内存利用率的主要因素就是内存碎片,分为内部碎片和外部碎片两种。
内部碎片(Internal Fragmentation)
内部碎片指的是对于给定的块,因为对齐和维护堆所需的数据结构的缘故,需要存储的数据(payload)小于分配的块的大小,就会出现无法利用的空间
因为内部碎片的数量取决于之前请求的模式,所以比较量化,可以通过已分配块的大小与其有效载荷的差来量化内部碎片。
外部碎片(External Fragmentation):当空闲的内存合起来够满足一个分配请求,但单独一个空闲内存不够时,就会产生外部碎片。外部碎片比较难进行量化,因为它主要取决于未来请求的模式,所以分配器通常试图维持少量的大的空闲块。
由于地址对齐要求和分配器对块格式的选择,会对最小块的大小有限制,没有已分配的块和空闲块比最小块还小,如果比最小块还小,就会变成外部碎片(所以最小块越大,内部碎片程度越高)。比如这里如果对齐要求是双字8字节的,则最小块大小为双字:第一个字用来保存头部,另一个字用来满足对齐要求。
给定一个指针,我们如何知道需要释放多少内存(即指针所指的块的大小是多少)
在每个块的开头使用一个字大小的区域记录这个块的大小,这个字通常称为header field或header。
也就是说,所有分配的块都需要一个额外的字。
当用户想用malloc请求一个大小为4字的载荷,分配器需要找到大小为5的块。然后返回指向有效载荷开头的指针p0,而不是指向header的指针。
如何记录未分配的块?
方法一:implicit free list
在堆中的每个块的前面放置一个头部,不管是被分配的还是空闲的。我们可以使用header记录的大小来访问堆。
我们称这种方法为implicit free list,因为没有真正的空闲块列表。通过遍历堆中的所有块,我们可以找到堆中的所有空闲块,只需要忽略已分配的块就可以了。
方法二:explicit free list
用块中的一个字指向下一个空闲块。此链表中只有空闲块,寻找空闲块只需要遍历所有的空闲块即可,不需要遍历已分配的块。
方法三:Segregated free list
有多个空闲链表,每个空闲链表包含特定大小或特定大小范围的块,对于不同大小的块有不同的链表。
每个块都需要记录大小和分配状态
malloc
请求的有效载荷。有效载荷的起始地址需要满足8字节的对齐要求。malloc返回的指针指向有效载荷的开始处,而不是指向头部。
我们通过这种数据结构来组织堆内存,通过块头部的块大小来将堆中的所有块链接起来。分配器可以遍历所有块,然后通过块头部的字段来判断该块是否空闲的,来间接遍历整个空闲块集合。我们可以通过一个大小为0的已分配块来作为终止头部(Terminating Header),来表示结束块。
堆的头部也有一个未使用块,目的是让第一块的有效载荷地址为8字节,满足对齐要求。
**注意:**先将有效载荷加上块头部大小,然后再满足对齐要求,得出来的就是块的大小。
当应用请求一个k字节的空闲块时,分配器会搜索空闲链表,并根据不同的**放置策略(Placement Policy)**来确定使用的空闲块:
**首次适配(First Fit):**分配器从头开始搜索空闲链表,选择第一个块大小大于k的空闲块。
**下一次适配(Next Fit):**分配器从上一次查询结束的地方开始进行搜索,选择第一个块大小大于k的空闲块。
**最佳适配(Best Fit):**分配器会查找所有空闲块,选择块大小大于k的最小空闲块。
如果分配器找不到满足要求的空闲块,则会首先尝试将物理上相邻的两个空闲块合并起来创建一个更大的空闲块,如果还是不满足要求,则分配器会调用sbrk
函数来向内核申请额外的堆内存,然后将申请到的新空间当做是一个空闲块。
只需要将指针所指向位置(header)的已分配标志位变为0即可。
void free_block(ptr p) { *p = *p & -2 }
但是如果被释放的块与其他空闲块相邻,则会产生假碎片(Fault Fragmentation)现象,即许多可用的空闲块被分割为小的无法使用的空闲块。所以当我们释放块时,还需要合并与之相邻的空闲块。
优秀的分配器不应该允许有连续的空闲块出现。
释放块有以下的策略:
**立即合并(Immediate Coalescing):**当我们释放一个分配块时,就合并与其相邻的空闲块。
**推迟合并(Deferred Coalescing):**当找不到合适的空闲块时,再扫描整个堆来合并所有空闲块。
合并相邻的空闲块时,我们可以利用header中的块大小找到下一个块的位置,但是我们却没有高效的方法找到前一个块的位置(只能从链表起始处重新遍历一次)。
为了高效合并前一个空闲块,需要使用**边界标记(Boundary Tag)**技术,使得当前块能迅速判断前一个块是否为空闲的。
在块的数据结构中,会添加一个块头部的副本得到脚部。这样当前块从起始位置向前偏移一个字长度,就能得到前一个块的脚部,通过脚部就能判断前一个快是否为空闲的。这实际上就是双向链表,允许我们反向遍历free list
可以将所有情况分成以下几种:
由于引入了脚部,增加了额外开销(overhead),使得内部碎片变多了,并且最小块的大小变大导致外部碎片也变多了。
我们可以对其进行优化,有些情况是不需要边界标记的,只有在合并时才需要脚部,而我们只会在空闲块上进行合并,所以在已分配的块上可以不需要脚部,那空闲块如何判断前一个块是否为已分配的呢?可以在自己的头部的3个位中用一个位来标记前一个块是否为空闲的,如果前一个块为已分配的,则无需关心前一个块的大小,因为不会进行合并;如果前一个块为空闲的,则前一个块自己就有脚部,说明了前一个块的大小,则可以顺利进行合并操作。
因为空闲块中除了头部和脚部以外都是没用的,我们可以在implicit free list的空闲块中加入一个指向前一个空闲块的pred
指针,还有一个指向下一个空闲块的succ
指针,将implicit free list中的空闲块组织成双向链表形式。这样implicit free list就变成了了显式空闲块列表(explicit free list)。
但是这种方法需要更大的空闲最小块,否则不够存放两个指针,这就提高了外部碎片的程度。
对于已分配块,可以通过头部和脚部来得到地址相邻两个块的信息,而对于空闲块,可以通过头部和脚部来得到地址相邻两个块,也可以通过两个指针直接获得相邻的两个空闲块。**注意:**逻辑上看这两个空闲块是相邻的,但物理地址上不一定是相邻的。
显式空闲块链表逻辑上是有序的,但是实际上所连接的空闲块的地址可能是无序的,空闲块可以以任意顺序连接。
比如我们这里存在以下3个空闲块的双向链表,此时想要分配中间的空闲块,且对其进行分割
因为已分配块可以根据指针来定位,所以不需要额外进行链接。而空闲块会从中分割出合适的部分用于分配,其余部分作为新的空闲块,此时只要更新6个指针使其指向和的位置就行。
而当我们想要释放已分配块时,它并不在空闲链表中,要将其放在空闲链表什么位置?
情况一:要释放的块前后都为已分配的块
我们可以通过后面块的头部以及前面块的脚部来得知相邻两个块的已分配状况(这就是保留头部和脚部的意义)。由于相邻的都是已分配的块,所以不会进行空闲块合并,直接更新Root的succ
指针使其指向要释放的块,让要释放的块的pred
指向Root,succ
指向原来第一个空闲块,然后更新原来的第一个空闲块的pred
指针。
情况二:要释放的块前面为空闲块,后面为已分配的块
要释放的块前面为空闲块,则需要将当前块和前一块进行合并。我们可以简单地修改头部和脚部直接将两个空闲块合并,将空闲块的前驱和后继节点指针指向改变,再将合并的新的空闲块插入root的后面。(这是LIFO的做法,对于地址顺序策略,我们不需要将合并的空闲块移动,可以把它留在原地,不更新任何东西)。
情况三:要释放的块后面为空闲块,前面为已分配的块
情况四:当前块的前后两个块都为空闲块
对于前后两个空闲块,直接让其指针前后的两个空闲块修改指针跳过,然后修改头部和脚部进行合并。再插入root的下一个位置
相比于implicit list,explicit list的分配操作与空闲块的数量成线性相关,而不是所有块的数量。因此,对于已分配的块的数量多的情况,explicit list的速度要快得多。
为了减少分配时间,可以使用分离存储(Segregrated Storage)方法,首先将所有空闲块根据块大小分成不同类别,称为大小类(Size Class),比如可以根据2幂次分成,每个类别一条链表,按照类别将空闲链表放入数组中,类似HashMap的实现方式,由此能极大加快分配速度。
当我们想要释放一个块时,需要对其地址周围的空闲块进行合并,然后将其放在合适的大小类中。
分离的空闲链表是当前最好的分配器类型
void foo() { int *p = malloc(128); return; /* p block is now garbage*/ }
在隐式分配器中,分配器会释放程序不再使用的已分配块,自动对其调用free
函数进行释放。则应用程序只需要显示分配自己需要的块,而回收过程由分配器自动完成。
内存分配器如何知道什么时候一个内存区域可以被释放呢?
但是这就要求:
本章主要介绍Mark&Sweep算法,它建立在malloc包的基础上,使得C和C++就有垃圾收集的能力。
垃圾收集器将内存视为一个有向可达图(Reachability Graph),其中:
具有两种节点:
每个指针都被视为图中的一条边
如果一个节点从根节点出发不可达,那么该节点就是垃级。
对于像ML和Java语言,其对指针创建和使用有严格的要求,由此来构建十分精确的可达图,所以能回收所有垃圾。而对于像C和C++这样的语言,垃圾收集器无法维护十分精确的可达图,只能正确地标记所有可达节点,而有一些不可达节点会被错误地标记为可达的,所以会遗留部分垃圾,这种垃圾收集器称为保守的垃圾收集器(Conservative Garbage Collector)。
在C中使用垃圾收集器可以有两种方法:
malloc
函数中。当引用调用malloc
函数来分配块时,如果无法找到合适的空闲块,就会调用垃圾收集器来识别出所有垃圾,并调用free
函数来进行释放。Mark&Sweep垃圾收集器由两个阶段组成:
这两个阶段的伪代码如下所示:
上面实现的困难是:
p
对应的是一个double
类型数据,但是C误以为是指针,而将该数据作为指针又正好指向某个不可达的已分配块中,则分配器会误以为该分配块是可达的,造成无法对该垃圾进行回收。这也是C程序的Mark&Sweep垃圾收集器必须是保守的原因。Dereferencing Bad Pointers
这是非常常见的例子,没有引用对应的地址,少了 &
int val; ... scanf("%d", val);
Reading Uninitialized Memory
不能假设堆中的数据会自动初始化为 0,堆中的数据可以是任意值。(C++中的new与malloc不同!)
/* return y = Ax */ int *matvec(int **A, int *x) { int *y = malloc(N * sizeof(int)); int i, j; for (i = 0; i < N; i++) for (j = 0; j < N; j++) y[i] += A[i][j] * x[j]; return y; }
Overwriting Memory
第一种是分配了错误的大小,下面的例子中,一开始不能用 sizeof(int)
,因为指针的长度不一定和 int 一样。
int **p; p = malloc(N * sizeof(int)); for (i = 0; i < N; i++) p[i] = malloc(M * sizeof(int));
第二个问题是超出了分配的空间,下面代码的 for 循环中,因为使用了 <=
,会写入到其他位置
int **p; p = malloc(N * sizeof (int *)); for (i = 0; i <= N; i++) p[i] = malloc(M * sizeof(int));
第三种是因为没有检查字符串的长度,超出部分就写到其他地方去了(经典的缓冲区溢出攻击也是利用相同的机制)
char s[8]; int i; gets(s); /* reads "123456789" from stdin */
没有正确理解指针的大小以及对应的操作。如果增加一个指针,该指针会往后移动指针所指向对象的大小的字节。比如:如果将int *指针加一,那么该指针会向后移动四个字节。
int *search(int *p, int val) { while (*p && *p != null) p += sizeof(int);// 这会往后移动四个int的大小,也就是16个字节,而不是4个字节 return p; }
引用了指针,而不是其指向的对象,下面的例子中,*size--
一句因为 --
的优先级比较高,所以实际上是对指针进行了操作,正确的应该是 (*size)--
int *BinheapDelete(int **binheap, int *size) { int *packet; packet = binheap[0]; binheap[0] = binheap[*size - 1]; *size--; Heapify(binheap, *size, 0); return (packet); }
引用不存在的变量。注意局部变量会在函数返回的时候失效(所以对应的指针也会无效),这是传引用和返回引用需要注意的,传值的话则不用担心
int *foo() { int val; return &val; }
多次释放同一个块
x = malloc(N * sizeof(int)); // <manipulate x> free(x); y = malloc(M * sizeof(int)); // <manipulate y> free(x);
引用已被释放的块
x = malloc(N * sizeof(int)); // <manipulate x> free(x); // .... y = malloc(M * sizeof(int)); for (i = 0; i < M; i++) y[i] = x[i]++;
没有释放分配的块
foo() { int *x = malloc(N * sizeof(int)); // ... return ; }
只释放了数据结构的一部分:
只释放了链表的一部分
struct list { int val; struct list *next; }; foo() { struct list *head = malloc(sizeof(struct list)); head->val = 0; head->next = NULL; //... free(head); return; }
处理内存bug:
数据结构一致性检查器(consistency checker)
我们写一个函数,确定数据结构应该始终保持结构的不变性,迭代数据结构,检查所有不变量的结构是否为真。检查器需要检查: