操作系统 — 浅析基于glibc的malloc

我就是我 2022-05-20 02:59 218阅读 0赞

# 浅析基于glibc的malloc #

Linux的虚拟内存管理有几个关键概念：

\- 每个进程都有独立的虚拟地址空间，进程访问的虚拟地址并不是真正的物理地址.

\- 虚拟地址可通过每个进程上的页表与物理地址进行映射，获得真正的物理地址.

\- 如果虚拟地址对应物理地址不在物理内存中，则产生缺页中断，真正分配物理地址，同时更新进程的页表;

如果此时物理内存已经耗尽了，则根据内存替换算法淘汰部分页面至物理磁盘当中.

Linux使用虚拟地址，大大增加了进程的寻址空间，由低地址到高地址分别为：

1.只读段：该部分空间只能读，不可写(包括代码段，rodata段(C常量字符串和\#define定义的常量))

2.数据段：保存全局变量，静态变量的空间.

3.堆：就是平时所说的动态内存，malloc/new大部分都来源于此，其中堆定的位置可通过函数brk和sbrk进行动态调整.

4.文件映射区域：如动态库，共享内存等映射物理空间的内存，一般是mmap函数所分配的虚拟地址空间.

5.栈：用于维护函数调用的上下文空间，一般为8M,可通过ulimit -s查看.

6.内核虚拟空间：用户代码不可见的内存区域，由内核管理(页表就存放在内核虚拟空间).

**32位系统由4G的地址空间：**

其中0x08048000~0xbffffff是用户空间，0xc000000~0xffffffff是内核空间，包括内核代码和数据，与进程相关的数据结构

(如页表，内核栈)等. 另外%esp执行栈顶，往低地址方向变化; brk/sbrk函数控制堆顶\_edata往高地址方向变化.

**malloc和free由谁提供？**

一般来说，他们是C Standard Library提供的而不是由操作系统的内核实现. 例如微软的是msvcrt,Linux下是glibc. 这两个

是主流的.今天我们着重了解Linux/glibc.

**malloc的基本原理**：

linux采用的是glibc中堆内存管理ptmalloc实现，虚拟内存的布局规定了malloc申请位置以及大小，malloc一次性能申请小内存(小于128

Kb),分配在堆区(heap)，用sbrk()进行对齐生长，而malloc一次性能申请大内存(大于128kb)分配到的是在共享映射区，而不是在堆区，

采用的mmap()系统调用进行映射. malloc的实现与物理内存是无关的，内核为每个进程维护一张页表，页表存储进程空间内每页的虚拟

地址，页表项中有的虚拟内存页对应着某个物理内存页面，也有的虚拟内存页没有实际的物理页面对应. 无论malloc通过sbrk还是mmap实

现，分配到的内存只是虚拟内存，而且只是虚拟内存的页号，代表这块空间进程可以用，实际上还没有分配到实际的物理页面.等你的进

程访问到这个新分配的内存空间的时候，如果其还没有分配到实际的物理页面，就会产生缺页中断，内核这个时候会给进程分配实际的

物理页面，以与这个未被映射的虚拟页面对应起来.

**ptmalloc中的chunk**

![70][]

![70 1][]

glibc中的malloc实现是基于链表的思想，但远远不止上面那么简单. glibc中是用ptmalloc来管理内存的，不管内存在哪里分配，用什么

办法分配，**用户请求分配的空间在ptmalloc中都是用一个chunk来表示**.用户调用free()之后释放的内存也不会立即返回给操作系统，

他们会被表示成一个chunk，ptmalloc是用特定的数据结构来管理这些chunk，一个**正在使用的chunk结构**大概如下：

![70 2][]

chunk指针指向一个chunk的开始，一个chunk中包含了用户请求的内存区域和相关的控制信息. 图中的mem指针才是真正返回给用户的内存

指针.chunk的第二个区域的最低一位为p，它表示前一个块是否在使用中，P为0则表示前一个chunk为空闲，这时chunk的第一个域

prev\_size才有效，prev\_size表示前一个chunk的size，程序可以使用这个值来找到前一个chunk的开始地址，当p为1时，表示前一个

chunk正在使用中，prev\_size无效，程序也就不可以得到前一个chunk的大小. 不能对前一个chunk进行任何操作. ptmalloc分配的第一个

块总是将P设为1，以防止程序引用到不存在的区域.

Chunk的第二个域的倒数第二个位为M,他表示当前chunk是从哪个内存区域获得的虚拟内存. M为1表示该chunk是从mmap映射区域分配的，

否则是从heap区域分配的.

Chunk地第二个区域的倒数第三个位为A,表示该chunk属于主分配区还是非主分配区. 前者置为1否则置为0.

**空闲chunk在内存中的结构如图所示**：

![70 3][]

当chunk空闲时，其M状态不存在，只有AP状态，原本是用户数据区的地方存储了四个指针，指针fd指向后一个空闲的chunk.而bk指向前一

个空闲的chunk，ptmalloc通过这两个指针将大小相近的chunk连成一个双向链表. 对于large bin中的空闲chunk，还有两个指针，

fd\_nextsize和bk\_nextsize. 这两个指针用于加快在large bin中查找最近匹配的空闲chunk，不同的chunk链表又是通过bins或者

fastbins来组织的.(上面说的相当详细)

2.chunk中的空间复用

为了使得chunk所占用的空间最小，ptmalloc使用了空间复用，一个chunk正在被使用或者已经被free掉，所以chunk中的一些域可以在使

用状态和空闲状态表示不同的意义，来达到空间复用的效果. 以32位系统为例，空闲的时候，一个chunk中至少需要4个size\_t大小的空

间，用来存储prev\_size,size,fd和bk，也就是16kb. chunk的大小要对齐到8kb，当一个chunk处于使用状态时，它的下一个chunk的

prev\_size域肯定是无效的，所以实际上，这个空间可以被当前chunk使用，这听起来有点不可思议,但确实是合理空间复用的例子. 所以

实际上，一个使用中的chunk的大小的计算公式应该是： in\_use\_size = (用户请求大小+8-4) 这里加8是因为需要存储prev\_size和size

，但又因为向下一个chunk"借"了4B，所以要减去4. 最后，因为空闲的chunk和使用中的chunk使用的是同一块空间，所以肯定要取其中

最大者作为实际的分配空间. 既最终的分配空间chunk\_size = max(in\_use\_size，16). 这就是当用户请求内存分配时，ptmalloc实际

需要分配的内存大小.

**主分配区 非主分配区：**

每个进程只有一个主分配区，但可能存在多个非主分配区，ptmalloc根据系统对分配去的争用情况动态增加非主分配区的数量，分配区

的数量一旦增加，就不会在减少了. 主分配区可以访问进程的heap区域和mmap映射区域,也就是说主分配可以使用sbrk和mmap向操作系

统申请虚拟空间. 而非主分配区只能访问检查的mmap映射区域，非主分配区每次使用mmap()向操作系统"批发"HEAP\_MAX\_SIZE（32位默

认1MB，64位系统默认64MB）大小的虚拟内存，当用户向非主分配区请求分配内存时再切割成小块"零售出去"，毕竟系统调用是相对低

效的，直接从用户空间分配内存快多了. 所以ptmalloc在必要的情况下才会调用mmap()函数向操作系统申请虚拟内存.

主分配区可以访问heap区域，如果用户不调用brk()和sbrk()函数，分配程序就可以保证分配到连续的虚拟地址空间，因为每个进程只

有一个主分配区使用sbrk()分配heap区域的虚拟地址. 内核对brk实习可以看成mmap的一个精简版本，相对高效益一点. 如果主分配

区的内存是通过mmap()向系统分配的，当free该内存时，主分配区会直接调用munmap()将该内存归还给系统.、

当某一个线程需要调用malloc()分配内存空间时，该线程先查看线程私有变量是否已经存在一个分配区，如果存在，尝试对该分配区加

锁,如果加锁成功，使用该分配区分配内存，如果失败，该线程搜索循环链表试图获得一个没有加锁的分配区. 如果所有分配区都已经加

锁，那么malloc()会开辟一个新的分配区，把该分配区加入到全局分配区循环链表并加锁，然后使用该分配前进行分配内存操作，在释

放过程中，线程同样试图获得待释放内存所在分区的锁，如果该分配区正在被别的线程使用，则需要等待直到其他线程释放该分配区的

互斥锁之后才可以进行释放操作.

申请小块内存时会产生很多内存碎片，ptmalloc在整理是也需要对分配区加锁操作，每个加速大概需要5~10个cpu指令，而且程序线程

很多的情况下，锁等待时间就会延长，导致malloc性能下降. 一次加锁操作需要消耗100ms左右，正是锁的缘故，导致ptmalloc在多线

程竞争情况下远远落后于tcmalloc.

**空闲chunk的容器：**

用户free掉的内存并不是都会马上归还给系统，ptmalloc会统一管理heap和mmap映射区域中的空闲的chunk，当用户进行下一次分配请求

时，ptmalloc会首先试图在空闲的chunk挑选一块给用户，这样就避免了频繁的系统调用，降低了内存分配的开销, ptmalloc将相似大小

的chunk用双向链表维护起来，这样一个链表被称为一个bin. ptmalloc一共维护128个bin,并使用一个数组来存储这些bin.

![70 4][]

数组中的第一个为unsorted bin，数组中从2开始编号前64个bin称为small bins，同一个small bin中的chunk具有相同的大小. 两个

相邻的small bin中的chunk大小相差为8bytes. small bins中的chunk按照最近使用的顺序进行排列，最后释放的chunk被链接到链表

的头部，而申请chunk是从链表尾部开始，这样，每一个chunk都有相同的机会被ptmalloc选中. small bins后面的bin被称为large bins

large bins中的么一个bin分别包含了一个给定范围内的chunk，其中的chunk按大小序列排序. 相同大小的chunk同样按照最近使用顺序

排列.ptmalloc使用 "smallest-first,best-fit"原则在空闲large bins中查找合适的chunk.

当空闲的chunk被链接到bin中的时候，ptmalloc会把表示该chunk是否处于使用中的标志P设置为0(注意，这个标志位实际上处于下一个

chunk当中)，同时ptmalloc还会检查它前后的chunk是否也是空闲的，如果是的话，ptmalloc会首先把他们合并成为一个大的chunk.

然后将合并后的chunk放到unsorted bin当中. 要注意的是，并不是所有的chunk被释放后就立即被放到bin当中. ptmalloc为了提高分配

的速度，会把一些小的chunk先放到一个叫做fast bins的容器内.

**2.Fast Bins**

一般的情况是，程序在运行时会经常需要申请和释放一些较小的内存空间. 当分配器合并了相邻的几个较小的内存空间. 当分配器合并了

相邻的几个小的chunk之后，也许马上就会有另一个小块内存的请求，这样分配器又需要从大的空闲内存中切分出一块，这样无疑是低效

的. 故而 ptmalloc中在分配过程中引入了fast bins，不大于max\_fast(默认为64kb)的chunk被释放后，首先会被放到fast bins中，

fast bins中的chunk并不会改变他的使用标志P，这样也就无法将他们合并，当需要给用户分配的chunk小于或等于max\_fast时，

ptmalloc首先会在fast bins中查找相应的空闲块，然后才会去查找bins中的空闲chunk. 某个特定的时候，ptmalloc会遍历fast bin中的

chunk将相邻的空闲chunk进行合并，并将合并后的chunk加入unsorted bin当中，然后再将usorted bin里的chunk 加入到bins中.

**3.Unsorted Bin**

Unsorted bin的队列使用bins数组的第一个，如果被用户释放的chunk大于max\_fast,或者fast bins中的空闲chunk合并后，这些chunk首先

会被放到unsorted bin队列中，在进行malloc操作时，如果在fast bins中没有找到合适的chunk，则ptmalloc会先在unsorted bin中查找

合适的空闲空间 chunk,然后才查找bins. 如果unsorted bin不能满足分配要求. malloc便会将unsorted bin中的chunk加入bins中，然

后再从bins中继续进行查找和分配过程，从这个过程可以看出来，unsorted bin可以看做是bins的一个缓冲区，增加它只是为了加快分配

的速度.

**4.Top chunk**

并不是所有的chunk都按照上面的方式来组织，实际上，有三种例外情况. Top chunk，mmaped chunk和last remainder. 下面会分别介绍

这三类

特殊的chunk。 top chunk对于主分配区和非分配区是不一样的.

**对于非主分配区会预先从mmap区域分配一块较大的空闲内存模拟sub-heap**. 通过管理sub-heap来向应用于的需求，因为内存是按地址从

低到高进行分配的，在空闲内存的最高处，必然存在一块空闲的chunk，叫做top chunk. 当bins和fast bins都不能满足分配需要的时候，

ptmalloc会设法在top chunk分配一块内存给用户，如果top chunk上分配所需的内存以满足分配的需要时. 实际上，top chunk在分配时

总是在fast bins和bins之后被考虑，所以，不论top chunk有多大，它都不会被放到fast bins或者bins中. top chunk的大小是随着分配

和回收不停变换的. 如果从top chunk分配内存会导致top chunk减小，如果回收的chunk恰好与top chunk相邻，那么这两个chunk就会

合并成新的top cchunk，从而使top chunk变大. 如果在free时回收的内存大于某个阈值,并且top chunk的大小也超过了收缩阈值.

ptmalloc会收缩sub-heap. 如果top-chunk包含了整个sub-heap，ptmalloc会调用munmap把整个sub-heap的内存返回给操作系统.

由于主分配区是唯一能够映射进程heap区域的分配区，它可以通过sbrk()来增大或是收缩进程heap的大小. ptmalloc在开始时会预先分配

一块较大的空闲内存(heap).主分配区的top chunk在第一次调用malloc时会分配一块(chunk\_size + 128kb)align 4kb大小的空间作为初

始的heap，用户从top chunk分配内存时，可以直接取出一块内存给用户. 在回收内存时，回收的内存恰好与top chunk 相邻则合并成新

的top chunk，当该次回收的空闲内存大小达到某个阈值，并且top chunk的大小也超过了收缩阈值，会执行内存收缩，减小top chunk大

小，但至少要保留一个页大小的空闲内存，从而把内存归还给操作系统. 如果向主分配区的top chunk申请内存，而top chunk中没有空闲

内存，ptmalloc会调用sbrk()将的进程heap的边界brk上移，然后修改top chunk的大小.

**5.mmaped chunk**

当需要分配的chunk足够大，而且fast bins和bins都不能满足要求，甚至top chunk本身也不能满足分配需求时，ptmalloc会直接使用

mmap来直接使用内存映射来将页映射到进程空间. 这样分配的chunk在被free时将直接解除映射，于是就将内存归还给操作系统了,再

次对这样的内存区的引用将导致segmentation fault错误. 这样的chunk也不会包含任何bin中.

**6.Last remainder**

Last remainder是另外一种特殊的chunk，就像top chunk和mmaped chunk一样，不会在任何bins中找到这种chunk，当需要分配一个

small chunk，但在small bins中找不到合适的chunk，如果Last remainder chunk的大小大于所需的small chunk大小，

last remainder chunk被分裂成两个chunk，其中一个chunk返回给用户，另一个chunk变成新的last remainder chunk.

**ptmalloc的响应用户内存分配要求的具体步骤：**

1).获取分配区的锁，为了防止多个线程同时访问同一分配区，在进行分配之前需要取得分配区的锁. 线程先查看线程私有实例中是否已

经存在一个分配区，如果存在尝试对该分配区加锁. 如果加锁成功，使用该分配区分配内存，否则，该线程搜索分配区循环链表试图获

得一个空闲的分配区. 如果所有的分配区都已经加锁了，那么ptmalloc会开辟一个新的分配区，把该分配区加入到全局分配区循环链表和

线程私有实例中并加锁，然后使用该分配区进行分配操作. 开辟出来的新分配区一定为非主分配区，因为主分配区是从父进程哪里继承而

来的，开辟非主分配会调用mmap()创建一个sub-heap，并设置好top chunk.

2).将用户的请求大小转换为实际需要分配的chunk空间大小.

3).判断所需分配chunk的大小是否满足chunk\_size <= max\_fast(max\_fast 默认为 64kb)

如果是的话，则转下一步，否则跳到第5步.

4).首先尝试在fast bins中取一个所需大小的chunk分配给用户，如果可以找到，则分配结束.

否则跳到下一步.

5).判断所需大小是否处于small bins中，既判断chunk\_size < 512kb是否成立，如果chunk大小

处于small bins中 进行下一步，否则转到第7步.

6).根据所需分配的chunk的大小，找到具体所在的某个small bin，从该bin的尾部摘取一个恰好满足大小的small bins中

，若成功，则分配结束. 否则，转到下一步.

7).到了这一步，说明需要分配的是一块大的内存，或者small bins中找不到合适的chunk. 于是，ptmalloc首先会遍历fast bins中的

chunk，将相邻chunk进行合并，并链接到unsorted bin中，然后遍历unsorted bin中的chunk，如果unsorted bin只有一个chunk,并且

这个chunk在上次分配时被使用过，并且所需分配的chunk大小属于small bins，并且chunk的大小等于需要分配的大小，这种情况就直

接将该chunk进行分割分配结束，否则将根据chunk的空间大小将其放入small bins或是large bins中，遍历完成后，进入下一步.

8).到了这一步，说明需要分配的是一块大的内存，或者small bins和unsorted bin中都找不到合适的chunk，并且fast bins和

unsorted bin中所有chunk都清除干净了. 从large bins中按照"smallest-first,best-fit"原则，找一个合适的chunk，从中划分一块

所需大小的chunk，并将剩下的部分链接回到bins中，若操作成功，则分配结束，否则转到下一步.

9).如果搜索fast bins和bins都没有找到合适的chunk,那么就需要操作top chunk来进行分配了，判断top chunk大小是否满足所需的

大小，如果是则从top chunk中分出一块来，否则转到下一步.

10).到了这一步，说明top chunk也不能满足分配要求，所以，于是就有两个选择：如果是主分配区，调用sbrk()，增加top chunk大小.

如果是非分配区，调用mmap来分配一个新的sub-heap，增加top chunk大小; 或者使用mmap()来直接分配，在这里需要依靠chunk的大

小决定到底使用那种方法，判断所需分配的chunk大小是否大于等于mmap分配阈值，如果是的话，则转到下一步，调用mmap分配，否则

跳到第12步，增加top chunk大小.

11).使用mmap系统调用用为程序的内存空间映射一块chunk\_size align 4kb大小的空间，然后将内存指针返回给用户.

12).判断是否为第一次调用malloc，若是主分配区，则需要进行一次初始化工作，分配一块大小为(chunk\_size + 128kb)align 4kb大小

的空间作为初始的heap. 若已经初始化过了，主分配区则调用sbrk()调用heap空间，猪粪分配区则在top chunk中切割出一个chunk，使

之满足分配需求，并将内存指针返回给用户.

总结一下：根据用户请求分配的内存的大小，ptmalloc有可能会在两个地方为用户分配内存空间. 在第一次分配内存时，一般情况下只存

在一个主分配区，但也有可能从父进程哪里继承了多个非主分配区，在这里主要讨论主分配区的情况，brk值等于start\_brk，所以实际上

heap大小为0，top chunk大小也是0，top chunk大小也是0，这时，如果不增加heap大小，就不能满足任何分配要求，所以，若用户的请

求的内存大小小于mmap分配阈值，则ptmalloc会初始化heap。 然后在heap中分配空间给用户，以后的分配就基于这个heap进行. 若是第

一次用户的请求大于mmap分配阈值，则ptmalloc直接使用mmap()分配一块内存给用户,而heap也就没有被初始化，直到用户第一次请求小于

mmap分配阀值的内存分配. 第一次以后的分配就比较复杂了，简单来说，ptmalloc首先会查找fast bins，如果不能找到匹配的chunk，则

查找small bins，若还是不行，把unsorted bin中的chunk全部加入large bins中查找，并查找large bins. 在fast bins和small bins当

中查找都需要精确匹配，而在large bins中查找时，则遵循"smallest-first,best-fit"的原则，不需要精确匹配. 若以上的方法都失败

了，则ptmalloc会考虑使用top chunk，若top chunk也不能满足分配要求. 而且所需chunk大于mmap分配阈值，则使用mmap进行分配，否

则增加heap,增大top chunk以满足分配要求.

内存回收概述：

free()函数接受一个指向分配区域的指针作为参数，释放该指针所指向的chunk.而具体的释放方法则看该chunk所处的位置和该chunk的大

小，free()函数的工作步骤如下：

1).free()函数同样首先需要获取分配区的锁，来保证线程安全.

2).判断传入的指针是否为0，如果为0，则什么都不做，直接return，否则转下一步.

3).判断所需释放的chunk是否为mmaped chunk,如果是，则调用munmap()释放mmaped chunk，解除内存空间映射，该空间不再有效. 如果

开启阈值设定位mmap分配阈值的2倍，释放完成，否则跳到下一步.

4).判断chunk的大小和所处的位置，若chunk\_size <= max\_fast,并且chunk并不位于heap的顶部，也就是说并不与top chunk相邻，则转

到下一步，否则跳到第六步.(因为与top chunk相邻的小chunk会和 top chunk进行合并，所以这里不仅需要判断大小，还需要判断相邻情况)

5).将chunk放到fast bins中，chunk 放入到fast bins中时，并不修改该chunk使用状态位p，也不会和相邻的chunk进行合并，知识放进

去，如此而已，这一步做完之后释放便结束了，程序从free()函数中返回.

6).判断前一个chunk是否处于使用中，如果前一个块也是空闲块，则合并. 并转下一步.

7).判断前一个chunk的下一个块是否为top chunk，如果是，则转到第9步，否则下一步.

8).判断下一个chunk是否处于使用中，如果下一个chunk也是空闲的，则合并，并将合并后的chunk放到unsorted bin中. 注意，这里在合

并的构成中，要更新chunk的大小，以反映合并后的chunk的大小，并转到第10步.

9).如果执行到这一步，说明释放了一个与top chunk相邻的chunk，则无论它有多大，都将它与top chunk合并，并更新top chunk的大小

信息，转下一步

10).判断top chunk的大小是否大于FASTBIN\_CONSOLIDATION\_THRESHOLD(默认64kb),如果是的话，则会触发进行fast bins的合并操作，

fast bins中的chunk将被遍历，并与相邻的空间chunk进行合并，合并后的chunk会被放到unsorted bin中，fast bins将为空，操作完

成之后转下一步.

11).判断top chunk的大小是否大于mmap收缩阈值,如果是的话，对于主分配区，则会试图归还top chunk中的一部分给操作系统. 但是最

先分配的128kb是不会归还的，ptmalloc会一直管理这部分内存，用于响应用户的分配请求：如果为非主分配区，会进行sub-heap

收缩，将top chunk的一部分返回给操作系统. 如果top chunk为整个sub-heap，会把整个sub-heap还回给操作系统，做完这一步之后，

释放结束，从free()函数退出，可以看出，收缩堆的条件是当前free的chunk大小加上前后能合并chunk的大小大于64kb，并且

top chunk的大小要达到mmap收缩阈值，才有可能收缩堆.

[70]: /images/20220520/b92f3dc19ae04b24bdf76fc11b35e3a7.png
[70 1]: /images/20220520/d7450c7d07154d2990e73cf597356ffc.png
[70 2]: /images/20220520/1be556706e7c4a3bb61ff8e9e80ae7b4.png
[70 3]: /images/20220520/763bde80a18f4ceb955481465519fd35.png
[70 4]: /images/20220520/0688abdba0d642d0a151c7c4e7c63516.png