HackPluto's Blog

堆的分配原理分析

字数统计: 13.4k阅读时长: 53 min
2019/10/17 Share

这段时间在学习堆溢出,在网上找到了一些好的堆的讲解,在这里做一个总结

参考文献:

基础知识

X86 平台 Linux 进程内存布局

在Linux上,以32 位机器为例,程序在固定位置开始加载,通常是128M处,首先被载入的是.text 段,然后是.data 段,最后是.bss 段。这可以看作是程序的开始空间。程序所能访问的最后的地址是0xbfffffff,也就是到 3G 地址处,3G 以上的 1G 空间是内核使用的,应用程序不可以直接访问。应用程序的堆栈从最高地址处开始向下生长,.bss 段与堆栈之间的空间是空闲的,空闲空间被分成两部分,一部分为 heap,一部分为 mmap 映射区域,mmap 映射区域一般从 TASK_SIZE/3 的地方开始,但在不同的 Linux 内核和机器上,mmap 区域的开始位置一般是不同的。Heap 和 mmap 区域都可以供用户自由使用,但是它在刚开始的时候并没有映射到内存空间内,是不可访问的。栈是区域是唯一不需要映射,用户却可以访问的内存区域。

32 位模式下进程内存经典布局

这种布局是 Linux 内核 2.6.7 以前的默认进程内存布局形式

32 位模式下进程默认内存布局

上图的布局形式是在内核2.6.7 以后才引入的

64 位模式下进程内存布局

对于 AMD64 系统,内存布局采用经典内存布局,text 的起始地址为 0x0000000000400000,堆紧接着 BSS 段向上增长,mmap 映射区域开始位置一般设为 TASK_SIZE/3。

计算一下可知,mmap 的开始区域地址为 0x00002AAAAAAAA000,栈顶地址为0x00007FFFFFFFF000

操作系统内存分配的相关函数

heap 和 mmap 映射区域是可以提供给用户程序使用的虚拟内存空间。那么如何对这两个区域进行操作,操作系统提供了相关的系统调用来完成相关工作。对 heap 的操作,操作系统提供了 brk()函数,C 运行时库提供了 sbrk()函数;对 mmap 映射区域的操作,操作系统提供了 mmap()和 munmap()函数。
这里要提到一个很重要的概念,内存的延迟分配,只有在真正访问一个地址的时候才建立这个地址的物理映射,这是 Linux 内存管理的基本思想之一。Linux 内核在用户申请内存的时候,只是给它分配了一个线性区(也就是虚拟内存),并没有分配实际物理内存;只有当用户使用这块内存的时候,内核才会分配具体的物理页面给用户,这时候才占用宝贵的物理内存。内核释放物理页面是通过释放线性区,找到其所对应的物理页面,将其全部释放的过程。

Heap 操作相关函数

Heap 操作函数主要有两个,brk()为系统调用,sbrk()为 C 库函数。Glibc 的 malloc 函数族(realloc,calloc 等)就调用 sbrk()函数将数据段的下界移动,sbrk()函数在内核的管理下将虚拟地址空间映射到内存,供 malloc()函数使用。

内核数据结构 mm_struct 中的成员变量 start_code 和 end_code 是进程代码段的起始和终止地址,start_data 和 end_data 是进程数据段的起始和终止地址,start_stack 是进程堆栈段起始地址,start_brk 是进程动态内存分配起始地址(堆的起始地址),还有一个 brk(堆的当前最后地址),就是动态内存分配当前的终止地址。C 语言的动态内存分配基本函数是malloc(),在 Linux 上的实现是通过内核的 brk 系统调用。brk()是一个非常简单的系统调用,只是简单地改变 mm_struct 结构的成员变量 brk 的值。

1
2
3
#include <unistd.h>
int brk(void *addr);
void *sbrk(intptr_t increment);

sbrk()的参数 increment 为 0 时,sbrk()返回的是进程的当前 brk 值,
increment 为正数时扩展 brk 值,当 increment 为负值时收缩 brk 值。

Mmap 映射区域操作相关函数

mmap()函数将一个文件或者其它对象映射进内存。文件被映射到多个页上,如果文件的
大小不是所有页的大小之和,最后一个页不被使用的空间将会清零。munmap 执行相反的操
作,删除特定地址区域的对象映射。函数的定义如下:

1
2
3
#include <sys/mman.h>
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);

概述

内存管理的方法

C 风格的内存管理程序

C 风格的内存管理程序主要实现 malloc()和 free()函数。内存管理程序主要通过调用 brk()或者 mmap()进程添加额外的虚拟内存。

池式内存管理

内存池是一种半内存管理方法。内存池帮助某些程序进行自动内存管理,这些程序会经历一些特定的阶段,而且每个阶段中都有分配给进程的特定阶段的内存。例如,很多网络服务器进程都会分配很多针对每个连接的内存——内存的最大生存期限为当前连接的存在期。Apache 使用了池式内存(pooled memory),将其连接拆分为各个阶段,每个阶段都有自己的内存池。在结束每个阶段时,会一次释放所有内存。

Ptmalloc 内存管理概述

简介

Linux 中 malloc 的早期版本是由 Doug Lea 实现的,它有一个重要问题就是在并行处理时多个线程共享进程的内存空间,各线程可能并发请求内存,在这种情况下应该如何保证分配和回收的正确和高效。Wolfram Gloger 在 Doug Lea 的基础上改进使得 Glibc 的 malloc 可以支持多线程——ptmalloc,在glibc-2.3.x.中已经集成了ptmalloc2,这就是我们平时使用的malloc,目前 ptmalloc 的最新版本 ptmalloc3。ptmalloc2 的性能略微比 ptmalloc3 要高一点点。ptmalloc 实现了 malloc(),free()以及一组其它的函数. 以提供动态内存管理的支持。分配器处在用户程序和内核之间,它响应用户的分配请求,向操作系统申请内存,然后将其返回给用户程序,为了保持高效的分配,分配器一般都会预先分配一块大于用户请求的内存,并通过某种算法管理这块内存。来满足用户的内存分配要求,用户释放掉的内存也并不是立即就返回给操作系统,相反,分配器会管理这些被释放掉的空闲空间,以应对用户以后的内存分配要求。也就是说,分配器不但要管理已分配的内存块,还需要管理空闲的内存块,当响应用户分配要求时,分配器会首先在空闲空间中寻找一块合适的内存给用户,在空闲空间中找不到的情况下才分配一块新的内存。

内存管理的设计假设

Ptmalloc 在设计时折中了高效率,高空间利用率,高可用性等设计目标。在其实现代码中,隐藏着内存管理中的一些设计假设,由于某些设计假设,导致了在某些情况下 ptmalloc的行为很诡异。这些设计假设包括:

    1. 具有长生命周期的大内存分配使用 mmap。
    1. 特别大的内存分配总是使用 mmap。
    1. 具有短生命周期的内存分配使用 brk,因为用 mmap 映射匿名页,当发生缺页异常时,linux 内核为缺页分配一个新物理页,并将该物理页清 0,一个 mmap 的内存块需要映射多个物理页,导致多次清 0 操作,很浪费系统资源,所以引入了 mmap分配阈值动态调整机制,保证在必要的情况下才使用 mmap 分配内存。
    1. 尽量只缓存临时使用的空闲小内存块,对大内存块或是长生命周期的大内存块在释放时都直接归还给操作系统。
    1. 对空闲的小内存块只会在 malloc 和 free 的时候进行合并,free 时空闲内存块可能放入 pool 中,不一定归还给操作系统。
    1. 收缩堆的条件是当前 free 的块大小加上前后能合并 chunk 的大小大于 64KB、,并且堆顶的大小达到阈值,才有可能收缩堆,把堆最顶端的空闲内存返回给操作系统。
    1. 需要保持长期存储的程序不适合用 ptmalloc 来管理内存。
    1. 为了支持多线程,多个线程可以从同一个分配区(arena)中分配内存,ptmalloc假设线程 A 释放掉一块内存后,线程 B 会申请类似大小的内存,但是 A 释放的内存跟 B 需要的内存不一定完全相等,可能有一个小的误差,就需要不停地对内存块作切割和合并,这个过程中可能产生内存碎片。

内存管理数据结构概述

Main_arena 与 non_main_arena

在 Doug Lea 实现的内存分配器中只有一个主分配区(main arena),每次分配内存都必须对主分配区加锁,分配完成后释放锁,在 SMP 多线程环境下,对主分配区的锁的争用很激烈,严重影响了 malloc 的分配效率。于是 Wolfram Gloger 在 Doug Lea 的基础上改进使得Glibc 的 malloc 可以支持多线程,增加了非主分配区(non main arena)支持,主分配区与非主分配区用环形链表进行管理。每一个分配区利用互斥锁(mutex)使线程对于该分配区的访问互斥。
主分配区可以访问进程的 heap 区域和 mmap 映射区域,也就是说主分配区可以使用 sbrk 和 mmap向操作系统申请虚拟内存。而非主分配区只能访问进程的 mmap 映射区域,非主分配区每次使用 mmap()向操作系统“批发”HEAP_MAX_SIZE(32 位系统上默认为 1MB,64 位系统默认为 64MB)大小的虚拟内存.主分配区可以访问 heap 区域,如果用户不调用 brk()或是 sbrk()函数,分配程序就可以保证分配到连续的虚拟地址空间,因为每个进程只有一个主分配区使用 sbrk()分配 heap 区域的虚拟内存。内核对 brk 的实现可以看着是 mmap 的一个精简版,相对高效一些。如果主分配区的内存是通过 mmap()向系统分配的,当 free 该内存时,主分配区会直接调用 munmap()将该内存归还给系统。

chunk 的组织

用户请求分配的空间在 ptmalloc 中都使用一个 chunk 来表示。用户调用 free()函数释放掉的内存也并不是立即就归还给操作系统,相反,它们也会被表示为一个 chunk,ptmalloc 使用特定的数据结构来管理这些空闲的 chunk

Chunk 格式

ptmalloc 在给用户分配的空间的前后加上了一些控制信息,用这样的方法来记录分配的信息,以便完成分配和释放工作。一个使用中的 chunk(使用中,就是指还没有被 free 掉)在内存中的样子如图所示:

,chunk 指针指向一个 chunk 的开始,一个 chunk 中包含了用户请求的内存区域和相关的控制信息。图中的 mem 指针才是真正返回给用户的内存指针。chunk 的第二个域的最低一位为 P,它表示前一个块是否在使用中,P 为 0 则表示前一个 chunk 为空闲,这时chunk 的第一个域 prev_size 才有效,prev_size 表示前一个 chunk 的 size,程序可以使用这个值来找到前一个 chunk 的开始地址。当 P 为 1 时,表示前一个 chunk 正在使用中,prev_sizeChunk 的第二个域的倒数第二个位为 M,他表示当前 chunk 是从哪个内存区域获得的虚拟内存。M 为 1 表示该 chunk 是从 mmap 映射区域分配的,否则是从 heap 区域分配的。Chunk 的第二个域倒数第三个位为 A,表示该 chunk 属于主分配区或者非主分配区,如果属于非主分配区,将该位置为 1,否则置为 0。

当 chunk 空闲时,其 M 状态不存在,只有 AP 状态,原本是用户数据区的地方存储了四个指针,指针 fd 指向后一个空闲的 chunk,而 bk 指向前一个空闲的 chunk,ptmalloc 通过这两个指针将大小相近的 chunk 连成一个双向链表。对于 large bin 中的空闲 chunk,还有两个指针,fd_nextsize 和 bk_nextsize,这两个指针用于加快在 large bin 中查找最近匹配的空闲chunk。不同的 chunk 链表又是通过 bins 或者 fastbins 来组织的(bins 和 fastbins 在 3.2.3.3中介绍)。

空闲 chunk 容器

1.Bins

用户 free 掉的内存并不是都会马上归还给系统,ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk,当用户进行下一次分配请求时,ptmalloc 会首先试图在空闲的chunk 中挑选一块给用户,这样就避免了频繁的系统调用,降低了内存分配的开销。ptmalloc将相似大小的 chunk 用双向链表链接起来,这样的一个链表被称为一个 bin。Ptmalloc 一共维护了 128 个 bin,并使用一个数组来存储这些 bin

数组中的第一个为 unsorted bin,数组中从 2 开始编号的前 64 个 bin 称为 small bins,同一个small bin中的chunk具有相同的大小。两个相邻的small bin中的chunk大小相差8bytes。small bins 中的 chunk 按照最近使用顺序进行排列,最后释放的 chunk 被链接到链表的头部,而申请 chunk 是从链表尾部开始
当空闲的 chunk 被链接到 bin 中的时候,ptmalloc 会把表示该 chunk 是否处于使用中的标志 P 设为 0(注意,这个标志实际上处在下一个 chunk 中),同时 ptmalloc 还会检查它前后的 chunk 是否也是空闲的,如果是的话,ptmalloc 会首先把它们合并为一个大的 chunk,然后将合并后的 chunk 放到 unstored bin 中。要注意的是,并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度,会把一些小的的 chunk 先放到一个叫做fast bins 的容器内。

2.Fast Bins

一般的情况是,程序在运行时会经常需要申请和释放一些较小的内存空间。,ptmalloc 中在分配过程中引入了 fast bins,不大于 max_fast (默认值为 64B)的 chunk 被释放后,首先会被放到 fast bins中,fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并,当需要给用户分配的 chunk 小于或等于 max_fast 时,ptmalloc 首先会在 fast bins 中查找相应的空闲块,然后才会去查找bins中的空闲chunk。在某个特定的时候,ptmalloc会遍历fast bins中的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

top chunk 对于主分配区和非主分配区是不一样的。
由于主分配区是唯一能够映射进程 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 的大小。
对于非主分配区会预先从 mmap 区域分配一块较大的空闲内存模拟 sub-heap,通过管理 sub-heap 来响应用户的需求,因为内存是按地址从低向高进行分配的,在空闲内存的最高处,必然存在着一块空闲 chunk,叫做 top chunk。当 bins 和 fast bins 都不能满足分配需要的时候,ptmalloc 会设法在 top chunk 中分出一块内存给用户,如果top chunk 本身不够大,分配程序会重新分配一个 sub-heap,并将 top chunk 迁移到新的sub-heap 上,新的 sub-heap与已有的 sub-heap 用单向链表连接起来,然后在新的 top chunk 上分配所需的内存以满足分配的需要,实际上,top chunk 在分配时总是在 fast bins 和 bins 之后被考虑,所以,不论 topchunk 有多大,它都不会被放到 fast bins 或者是 bins 中。Top chunk 的大小是随着分配和回收不停变换的,如果从 top chunk 分配内存会导致 top chunk 减小,如果回收的 chunk 恰好与 top chunk 相邻,那么这两个 chunk 就会合并成新的 top chunk,从而使 top chunk 变大。如果在 free 时回收的内存大于某个阈值,并且 top chunk 的大小也超过了收缩阈值,ptmalloc会收缩 sub-heap,如果 top-chunk 包含了整个 sub-heap,ptmalloc 会调用 munmap 把整个sub-heap 的内存返回给操作系统。

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 chuk。

sbrk 与 mmap

从进程的内存布局可知,.bss 段之上的这块分配给用户程序的空间被称为 heap (堆)。start_brk 指向 heap 的开始,而 brk 指向 heap 的顶部。可以使用系统调用 brk()和 sbrk()来增加标识 heap 顶部的 brk 值,从而线性的增加分配给用户的 heap 空间。在使 malloc 之前,brk的值等于start_brk,也就是说heap大小为0。ptmalloc在开始时,若请求的空间小于 mmap分配阈值(mmap threshold,默认值为 128KB)时,主分配区会调用 sbrk()增加一块大小为 (128KB + chunk_size) align 4KB 的空间作为 heap。非主分配区会调用 mmap 映射一块大小为HEAP_MAX_SIZE(32 位系统上默认为 1MB,64 位系统上默认为 64MB)的空间作为 sub-heap。这就是前面所说的 ptmalloc 所维护的分配空间,当用户请求内存分配时,首先会在这个区域内找一块合适的 chunk 给用户。当用户释放了 heap 中的 chunk 时,ptmalloc 又会使用 fastbins 和 bins 来组织空闲 chunk。以备用户的下一次分配。若需要分配的 chunk 大小小于 mmap分配阈值,而 heap 空间又不够,则此时主分配区会通过 sbrk()调用来增加 heap 大小,非主分配区会调用 mmap 映射一块新的 sub-heap,也就是增加 top chunk 的大小,每次 heap 增加的值都会对齐到 4KB。当用户的请求超过 mmap 分配阈值,并且主分配区使用 sbrk()分配失败的时候,或是非主分配区在 top chunk 中不能分配到需要的内存时,ptmalloc 会尝试使用 mmap()直接映射一块内存到进程内存空间。使用 mmap()直接映射的 chunk 在释放时直接解除映射,而不再属于进程的内存空间。任何对该内存的访问都会产生段错误。而在 heap 中或是 sub-heap 中分配的空间则可能会留在进程内存空间内,还可以再次引用(当然是很危险的)。当 ptmalloc munmap chunk 时,如果回收的 chunk 空间大小大于 mmap 分配阈值的当前值,并且小于DEFAULT_MMAP_THRESHOLD_MAX(32 位系统默认为 512KB,64 位系统默认为 32MB),ptmalloc 会把 mmap 分配阈值调整为当前回收的 chunk 的大小,并将 mmap 收缩阈值(mmap trim threshold)设置为 mmap 分配阈值的 2 倍。这就是 ptmalloc 的对 mmap分配阈值的动态调整机制,该机制是默认开启的,当然也可以用 mallopt()关闭该机制

内存分配概述

分配算法概述

以 32 系统为例,64 位系统类似

  • 小于等于 64 字节:用 pool 算法分配。
  • 64 到 512 字节之间:在最佳匹配算法分配和 pool 算法分配中取一种合适的。
  • 大于等于 512 字节:用最佳匹配算法分配。
  • 大于等于 mmap 分配阈值(默认值 128KB):根据设置的 mmap 的分配策略进行分配,如果没有开启 mmap 分配阈值的动态调整机制,大于等于128KB 就直接调用 mmap分配。否则,大于等于 mmap 分配阈值时才直接调用 mmap()分配。

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

1) 获取分配区的锁,为了防止多个线程同时访问同一个分配区,在进行分配之前需要
取得分配区域的锁。线程先查看线程私有实例中是否已经存在一个分配区,如果存
在尝试对该分配区加锁,如果加锁成功,使用该分配区分配内存,否则,该线程搜
索分配区循环链表试图获得一个空闲(没有加锁)的分配区。如果所有的分配区都
已经加锁,那么 ptmalloc 会开辟一个新的分配区,把该分配区加入到全局分配区循
环链表和线程的私有实例中并加锁,然后使用该分配区进行分配操作。开辟出来的
新分配区一定为非主分配区,因为主分配区是从父进程那里继承来的。开辟非主分
配区时会调用 mmap()创建一个 sub-heap,并设置好 top chunk。
2) 将用户的请求大小转换为实际需要分配的 chunk 空间大小。
3) 判断所需分配chunk的大小是否满足chunk_size <= max_fast (max_fast 默认为 64B),如果是的话,则转下一步,否则跳到第 5 步。
4) 首先尝试在 fast bins 中取一个所需大小的 chunk 分配给用户。如果可以找到,则分配结束。否则转到下一步。
5) 判断所需大小是否处在 small bins 中,即判断 chunk_size < 512B 是否成立。如果chunk 大小处在 small bins 中,则转下一步,否则转到第 6 步。
6) 根据所需分配的 chunk 的大小,找到具体所在的某个 small bin,从该 bin 的尾部摘取一个恰好满足大小的 chunk。若成功,则分配结束,否则,转到下一步。
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 大小是否满足所需 chunk 的大小,如果是,则从 topchunk 中分出一块来。否则转到下一步。
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。这时,如果不增加 heap大小,就不能满足任何分配要求。所以,若用户的请求的内存大小小于 mmap 分配阈值,则 ptmalloc 会初始 heap。然后在 heap 中分配空间给用户,以后的分配就基于这个 heap进行。若第一次用户的请求就大于 mmap 分配阈值,则 ptmalloc 直接使用 mmap()分配一块内存给用户,而 heap 也就没有被初始化,直到用户第一次请求小于 mmap 分配阈值的内存分配。第一次以后的分配就比较复杂了,简单说来,ptmalloc 首先会查找 fast bins,如果不能找到匹配的 chunk,则查找 small bins。若还是不行,合并 fast bins,把 chunk加入 unsorted bin,在 unsorted bin 中查找,若还是不行,把 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 分配阈值的动态调整机制,并且当前回收的 chunk 大小大于 mmap 分配阈值,将 mmap分配阈值设置为该 chunk 的大小,将 mmap 收缩阈值设定为 mmap 分配阈值的 2倍,释放完成,否则跳到下一步。
4) 判断 chunk 的大小和所处的位置,若chunk_size <= max_fast,并且 chunk 并不位于heap 的顶部,也就是说并不与 top chunk 相邻,则转到下一步,否则跳到第 6 步。(因为与 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) 判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD(默认64KB),如果是的话,则会触发进行 fast bins 的合并操作,fast bins 中的 chunk 将被遍历,并与相邻的空闲 chunk 进行合并,合并后的 chunk 会被放到 unsorted bin 中。fast bins 将变为空,操作完成之后转下一步。
11) 判断 top chunk 的大小是否大于 mmap 收缩阈值(默认为 128KB),如果是的话,对于主分配区,则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的128KB 空间是不会归还的,ptmalloc 会一直管理这部分内存,用于响应用户的分配请求;如果为非主分配区,会进行 sub-heap 收缩,将 top chunk 的一部分返回给操作系统,如果 top chunk 为整个 sub-heap,会把整个 sub-heap 还回给操作系统。做完这一步之后,释放结束,从 free() 函数退出。可以看出,收缩堆的条件是当前free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k,并且要 top chunk 的大小要达到 mmap 收缩阈值,才有可能收缩堆。

源码分析

本部分主要对源代码实现技巧的细节做分析,希望能进一步理解 ptmalloc 的实现,做到终极无惑。主要分析的文件包括 arena.c 和 malloc.c,这两个文件包括了 ptmalloc 的核心实现,其中 arena.c 主要是对多线程支持的实现,malloc.c 定义了公用的 malloc(),free()等函数,实现了基于分配区的内存管理算法。

边界标记法

Ptmalloc 使用 chunk 实现内存管理,对 chunk 的管理基于独特的边界标记法.在不同的平台下,每个 chunk 的最小大小,地址对齐方式是不同的,ptmalloc 依赖平台定义的 size_t 长度,对于 32 位平台,size_t 长度为 4 字节,对 64 位平台,size_t 长度可能为4 字节,也可能为 8 字节,在 Linux X86_64 上 size_t 为 8 字节,这里就以 size_t 为 4 字节和8 字节的情况进行分析。先看一段源代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif
/* The corresponding word size */
#define SIZE_SZ (sizeof(INTERNAL_SIZE_T))
/*
MALLOC_ALIGNMENT is the minimum alignment for malloc'ed chunks.
It must be a power of two at least 2 * SIZE_SZ, even on machines
for which smaller alignments would suffice. It may be defined as
larger than this though. Note however that code and data structures
are optimized for the case of 8-byte alignment.
*/
#ifndef MALLOC_ALIGNMENT
#define MALLOC_ALIGNMENT (2 * SIZE_SZ)
#endif
/* The corresponding bit mask value */
#define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)

Ptmalloc 使用宏来屏蔽不同平台的差异,将 INTERNAL_SIZE_T 定义为 size_t,SIZE_SZ定义为 size_t 的大小,在 32 位平台下位 4 字节,在 64 位平台下位 4 字节或者 8 字节。另外分配 chunk 时必须以 2SIZE_SZ 对齐,MALLOC_ALIGNMENT 和 MALLOC_ALIGN_MASK 是用来处理 chunk 地址对齐的宏,MALLOC_ALIGNMENT是malloc分配的块的最小对齐方式。即使在机器上,它也必须是至少2 SIZE_SZ的2的幂.但是请注意,代码和数据结构针对8字节对齐的情况进行了优化。

Ptmalloc 采用边界标记法将内存划分成很多块,从而对内存的分配与回收进行管理。在ptmalloc 的实现源码中定义结构体 malloc_chunk 来描述这些块

1
2
3
4
5
6
7
8
9
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};

prev_size, 如果该 chunk 的物理相邻的前一地址 chunk(两个指针的地址差值为前一 chunk 大小)是空闲的话,那该字段记录的是前一个 chunk 的大小 (包括 chunk 头)。否则,该字段可以用来存储物理相邻的前一个 chunk 的数据。这里的前一 chunk 指的是较低地址的 chunk 。
size ,该 chunk 的大小,大小必须是 2 SIZE_SZ 的整数倍。如果申请的内存大小不是 2 SIZE_SZ 的整数倍,会被转换满足大小的最小的 2 * SIZE_SZ 的倍数。32 位系统中,SIZE_SZ 是 4;64 位系统中,SIZE_SZ 是 8。 该字段的低三个比特位对 chunk 的大小没有影响,它们从高到低分别表示
——-NON_MAIN_ARENA,记录当前 chunk 是否不属于主线程,1 表示不属于,0 表示属于。
——-IS_MAPPED,记录当前 chunk 是否是由 mmap 分配的。
——-PREV_INUSE,记录前一个 chunk 块是否被分配。一般来说,堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1,以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时,我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。
fd,bk, 指针类型数据,chunk 处于分配状态时,从 fd 字段开始是用户的数据。chunk 空闲时,会被添加到对应的空闲管理链表中,其字段的含义如下
fd 指向下一个(非物理相邻)空闲的 chunk
bk 指向上一个(非物理相邻)空闲的 chunk
通过 fd 和 bk 可以将空闲的 chunk 块加入到空闲的 chunk 块链表进行统一管理
fd_nextsize, bk_nextsize,也是只有 chunk 空闲的时候才使用,不过其用于较大的 chunk(large chunk)。
fd_nextsize 指向前一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
bk_nextsize 指向后一个与当前 chunk 大小不同的第一个空闲块,不包含 bin 的头指针。
一般空闲的 large chunk 在 fd 的遍历顺序中,按照由大到小的顺序排列。这样做可以避免在寻找合适 chunk 时挨个遍历。

malloc_chunk详细信息:
内存块使用“边界标记”方法维护,如下所示:
空闲块的大小都存储在每个块的前面和结尾。 这使得很快将碎片化的块合并为更大的块。size字段还包含表示块是空闲还是正在使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
分配的块如下所示:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk, if allocated | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk, in bytes |M|P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| User data starts here... .
. .
. (malloc_usable_size() bytes) .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

在大多数情况下,“chunk”是块的前面malloc代码,但是“ mem”是返回到用户。 “ Nextchunk”是下一个连续块的开始。块总是以偶数边界开始,因此mem部分(返回给用户)也在偶数字边界上,并且因此,至少双字对齐。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
空闲块存储在循环双向链接列表中,如下所示:
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Size of previous chunk |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`head:' | Size of chunk, in bytes |P|
mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Forward pointer to next chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Back pointer to previous chunk in list |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unused space (may be 0 bytes long) .
. .
. |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
`foot:' | Size of chunk, in bytes |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
1
2
3
4
5
6
7
8
9
10
11
12
13
 /* conversion from malloc headers to user pointers, and back */
#define chunk2mem(p) ((Void_t*)((char*)(p) + 2*SIZE_SZ))
#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - 2*SIZE_SZ))
/* The smallest possible chunk */
#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
/* The smallest size we can malloc is an aligned minimal chunk */
#define MINSIZE \
(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
/* Check if m has acceptable alignment */
#define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
#define misaligned_chunk(p) \
((uintptr_t)(MALLOC_ALIGNMENT == 2 * SIZE_SZ ? (p) : chunk2mem (p)) \
& MALLOC_ALIGN_MASK)

chunk 结构体的前两个域刚好也是 2SIZE_SZ 大小,对于已经分配的 chunk,通过 chunk2mem 宏根据 chunk 地址获得返回给用户的内存地址,反过来通过 mem2chunk 宏根据 mem 地址得到 chunk 地址.宏 aligned_OK 和 misaligned_chunk(p)用于校验地址是否是按 2SIZE_SZ 对齐的。
MIN_CHUNK_SIZE 定义了最小的 chunk 的大小,32 位平台上位 16 字节,64 位平台为 24
字节或是 32 字节。MINSIZE 定义了最小的分配的内存大小,是对 MIN_CHUNK_SIZE 进行了
2*SIZE_SZ 对齐,地址对齐后与 MIN_CHUNK_SIZE 的大小仍然是一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
Check if a request is so large that it would wrap around zero when
padded and aligned. To simplify some other code, the bound is made
low enough so that adding MINSIZE will also not wrap around zero.
*/
#define REQUEST_OUT_OF_RANGE(req) \
((unsigned long)(req) >= \
(unsigned long)(INTERNAL_SIZE_T)(-2 * MINSIZE))

/* pad request bytes into a usable size -- internal version */
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? \
MINSIZE : \
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
/* Same, except also perform argument check */
#define checked_request2size(req, sz) \
if (REQUEST_OUT_OF_RANGE(req)) { \
MALLOC_FAILURE_ACTION; \
return 0; \
} \
(sz) = request2size(req);

重要结构体:
malloc_chunk

1
2
3
4
5
6
7
8
9
10
11
12
struct malloc_chunk {

INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */

struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;

/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};

malloc_state

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct malloc_state {
/* 序列化访问 */
mutex_t mutex;

/* Flags (formerly in max_fast). */
int flags;

#if THREAD_STATS
/* Statistics for locking. Only used if THREAD_STATS is defined. */
long stat_lock_direct, stat_lock_loop, stat_lock_wait;
#endif

/* Fastbins NFASTBINS=10 */
mfastbinptr fastbinsY[NFASTBINS];

/* Base of the topmost chunk -- not otherwise kept in a bin */
mchunkptr top;

/* 剩余部分来自最近一次小请求的拆分 */
mchunkptr last_remainder;

/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];

/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];

/* Linked list */
struct malloc_state *next;

#ifdef PER_THREAD
/* Linked list for free arenas. */
struct malloc_state *next_free;
#endif

/* 在此arena中从系统分配的内存。 */
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};

mfastbinptr,mchunkptr,均为malloc_chunk类型。
fastbinsY 拥有 10(NFASTBINS)个元素的数组,用于存放每个 fast chunk 链表头指针,
所以 fast bins 最多包含 10 个 fast chunk 的单向链表。
top 是一个 chunk 指针,指向分配区的 top chunk。
last_remainder 是一个 chunk 指针,分配区上次分配 small chunk 时,从一个 chunk 中分
裂出一个 small chunk 返回给用户,分裂后的剩余部分形成一个 chunk,last_remainder 就是
指向的这个 chunk。

malloc_par

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct malloc_par {
/* Tunable parameters */
unsigned long trim_threshold;
INTERNAL_SIZE_T top_pad;
INTERNAL_SIZE_T mmap_threshold;
#ifdef PER_THREAD
INTERNAL_SIZE_T arena_test;
INTERNAL_SIZE_T arena_max;
#endif

/* Memory map support */
int n_mmaps;
int n_mmaps_max;
int max_n_mmaps;
/* the mmap_threshold is dynamic, until the user sets
it manually, at which point we need to disable any
dynamic behavior. */
int no_dyn_threshold;

/* Cache malloc_getpagesize */
unsigned int pagesize;

/* Statistics */
INTERNAL_SIZE_T mmapped_mem;
/*INTERNAL_SIZE_T sbrked_mem;*/
/*INTERNAL_SIZE_T max_sbrked_mem;*/
INTERNAL_SIZE_T max_mmapped_mem;
INTERNAL_SIZE_T max_total_mem; /* only kept for NO_THREADS */

/* First address handed out by MORECORE/sbrk. */
char* sbrk_base;
};

_int_malloc

int_malloc 是内存分配的核心函数,其核心思路有如下
它根据用户申请的内存块大小以及相应大小 chunk 通常使用的频度(fastbin chunk, small chunk, large chunk),依次实现了不同的分配方法。
它由小到大依次检查不同的 bin 中是否有相应的空闲块可以满足用户请求的内存。
当所有的空闲 chunk 都无法满足时,它会考虑 top chunk。
当 top chunk 也无法满足时,堆分配器才会进行内存块申请。
在进入该函数后,函数立马定义了一系列自己需要的变量,并将用户申请的内存大小转换为内部的 chunk 大小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
static void *_int_malloc(mstate av, size_t bytes) {
INTERNAL_SIZE_T nb; /* normalized request size */
unsigned int idx; /* associated bin index */
mbinptr bin; /* associated bin */

mchunkptr victim; /* inspected/selected chunk */
INTERNAL_SIZE_T size; /* its size */
int victim_index; /* its bin index */

mchunkptr remainder; /* remainder from a split */
unsigned long remainder_size; /* its size */

unsigned int block; /* bit map traverser */
unsigned int bit; /* bit map traverser */
unsigned int map; /* current word of binmap */

mchunkptr fwd; /* misc temp for linking */
mchunkptr bck; /* misc temp for linking */

const char *errstr = NULL;

/*
Convert request size to internal form by adding SIZE_SZ bytes
overhead plus possibly more to obtain necessary alignment and/or
to obtain a size of at least MINSIZE, the smallest allocatable
size. Also, checked_request2size traps (returning 0) request sizes
that are so large that they wrap around zero when padded and
aligned.
*/

checked_request2size(bytes, nb);

fast bin

如果申请的 chunk 的大小位于 fastbin 范围内,需要注意的是这里比较的是无符号整数。此外,是从 fastbin 的头结点开始取 chunk。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
If the size qualifies as a fastbin, first check corresponding bin.
This code is safe to execute even if av is not yet initialized, so we
can try it without checking, which saves some time on this fast path.
*/

if ((unsigned long) (nb) <= (unsigned long) (get_max_fast())) {
// 得到对应的fastbin的下标
idx = fastbin_index(nb);
// 得到对应的fastbin的头指针
mfastbinptr *fb = &fastbin(av, idx);
mchunkptr pp = *fb;
// 利用fd遍历对应的bin内是否有空闲的chunk块,
do {
victim = pp;
if (victim == NULL) break;
} while ((pp = catomic_compare_and_exchange_val_acq(fb, victim->fd,
victim)) != victim);
// 存在可以利用的chunk
if (victim != 0) {
// 检查取到的 chunk 大小是否与相应的 fastbin 索引一致。
// 根据取得的 victim ,利用 chunksize 计算其大小。
// 利用fastbin_index 计算 chunk 的索引。
if (__builtin_expect(fastbin_index(chunksize(victim)) != idx, 0)) {
errstr = "malloc(): memory corruption (fast)";
errout:
malloc_printerr(check_action, errstr, chunk2mem(victim), av);
return NULL;
}
// 细致的检查。。只有在 DEBUG 的时候有用
check_remalloced_chunk(av, victim, nb);
// 将获取的到chunk转换为mem模式
void *p = chunk2mem(victim);
// 如果设置了perturb_type, 则将获取到的chunk初始化为 perturb_type ^ 0xff
alloc_perturb(p, bytes);
return p;
}
}

small bin

如果获取的内存块的范围处于 small bin 的范围,那么执行如下流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
If a small request, check regular bin. Since these "smallbins"
hold one size each, no searching within bins is necessary.
(For a large request, we need to wait until unsorted chunks are
processed to find best fit. But for small ones, fits are exact
anyway, so we can check now, which is faster.)
*/

if (in_smallbin_range(nb)) {
// 获取 small bin 的索引
idx = smallbin_index(nb);
// 获取对应 small bin 中的 chunk 指针
bin = bin_at(av, idx);
// 先执行 victim = last(bin),获取 small bin 的最后一个 chunk
// 如果 victim = bin ,那说明该 bin 为空。
// 如果不相等,那么会有两种情况
if ((victim = last(bin)) != bin) {
// 第一种情况,small bin 还没有初始化。
if (victim == 0) /* initialization check */
// 执行初始化,将 fast bins 中的 chunk 进行合并
malloc_consolidate(av);
// 第二种情况,small bin 中存在空闲的 chunk
else {
// 获取 small bin 中倒数第二个 chunk 。
bck = victim->bk;
// 检查 bck->fd 是不是 victim,防止伪造
if (__glibc_unlikely(bck->fd != victim)) {
errstr = "malloc(): smallbin double linked list corrupted";
goto errout;
}
// 设置 victim 对应的 inuse 位
set_inuse_bit_at_offset(victim, nb);
// 修改 small bin 链表,将 small bin 的最后一个 chunk 取出来
bin->bk = bck;
bck->fd = bin;
// 如果不是 main_arena,设置对应的标志
if (av != &main_arena) set_non_main_arena(victim);
// 细致的检查,非调试状态没有作用
check_malloced_chunk(av, victim, nb);
// 将申请到的 chunk 转化为对应的 mem 状态
void *p = chunk2mem(victim);
// 如果设置了 perturb_type , 则将获取到的chunk初始化为 perturb_type ^ 0xff
alloc_perturb(p, bytes);
return p;
}
}
}

large bin

当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时,就会考虑是不是 large bin。但是,其实在 large bin 中并没有直接去扫描对应 bin 中的 chunk,而是先利用 malloc_consolidate(参见 malloc_state 相关函数) 函数处理 fast bin 中的 chunk,将有可能能够合并的 chunk 先进行合并后放到 unsorted bin 中,不能够合并的就直接放到 unsorted bin 中,然后再在下面的大循环中进行相应的处理。为什么不直接从相应的 bin 中取出 large chunk 呢?这是 ptmalloc 的机制,它会在分配 large chunk 之前对堆中碎片 chunk 进行合并,以便减少堆中的碎片。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
If this is a large request, consolidate fastbins before continuing.
While it might look excessive to kill all fastbins before
even seeing if there is space available, this avoids
fragmentation problems normally associated with fastbins.
Also, in practice, programs tend to have runs of either small or
large requests, but less often mixtures, so consolidation is not
invoked all that often in most programs. And the programs that
it is called frequently in otherwise tend to fragment.
*/

else {
// 获取large bin的下标。
idx = largebin_index(nb);
// 如果存在fastbin的话,会处理 fastbin
if (have_fastchunks(av)) malloc_consolidate(av);
}

大循环 - 遍历 unsortedbin

如果程序执行到了这里,那么说明 与 chunk 大小正好一致的 bin (fast bin, small bin) 中没有 chunk 可以直接满足需求 ,但是 large chunk 则是在这个大循环中处理。
在接下来的这个循环中,主要做了以下的操作
按照 FIFO 的方式逐个将 unsorted bin 中的 chunk 取出来
如果是 small request,则考虑是不是恰好满足,是的话,直接返回。
如果不是的话,放到对应的 bin 中。
尝试从 large bin 中分配用户所需的内存
该部分是一个大循环,这是为了尝试重新分配 small bin chunk,这是因为我们虽然会首先使用 large bin,top chunk 来尝试满足用户的请求,但是如果没有满足的话,由于我们在上面没有分配成功 small bin,我们并没有对 fast bin 中的 chunk 进行合并,所以这里会进行 fast bin chunk 的合并,进而使用一个大循环来尝试再次分配 small bin chunk。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
Process recently freed or remaindered chunks, taking one only if
it is exact fit, or, if this a small request, the chunk is remainder from
the most recent non-exact fit. Place other traversed chunks in
bins. Note that this step is the only place in any routine where
chunks are placed in bins.

The outer loop here is needed because we might not realize until
near the end of malloc that we should have consolidated, so must
do so and retry. This happens at most once, and only when we would
otherwise need to expand memory to service a "small" request.
*/

for (;;) {
int iters = 0;

unsort bin 遍历

先考虑 unsorted bin,再考虑 last remainder ,但是对于 small bin chunk 的请求会有所例外。
注意 unsorted bin 的遍历顺序为 bk。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 如果 unsorted bin 不为空
// First In First Out
while ((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {
// victim 为 unsorted bin 的最后一个 chunk
// bck 为 unsorted bin 的倒数第二个 chunk
bck = victim->bk;
// 判断得到的 chunk 是否满足要求,不能过小,也不能过大
// 一般 system_mem 的大小为132K
if (__builtin_expect(chunksize_nomask(victim) <= 2 * SIZE_SZ, 0) ||
__builtin_expect(chunksize_nomask(victim) > av->system_mem, 0))
malloc_printerr(check_action, "malloc(): memory corruption",
chunk2mem(victim), av);
// 得到victim对应的chunk大小。
size = chunksize(victim);

SMALL REQUEST

如果用户的请求为 small bin chunk,那么我们首先考虑 last remainder,如果 last remainder 是 unsorted bin 中的唯一一块的话, 并且 last remainder 的大小分割够还可以作为一个 chunk ,为什么没有等号?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

/*
If a small request, try to use last remainder if it is the
only chunk in unsorted bin. This helps promote locality for
runs of consecutive small requests. This is the only
exception to best-fit, and applies only when there is
no exact fit for a small chunk.
*/

if (in_smallbin_range(nb) && bck == unsorted_chunks(av) &&
victim == av->last_remainder &&
(unsigned long) (size) > (unsigned long) (nb + MINSIZE)) {
/* split and reattach remainder */
// 获取新的 remainder 的大小
remainder_size = size - nb;
// 获取新的 remainder 的位置
remainder = chunk_at_offset(victim, nb);
// 更新 unsorted bin 的情况
unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
// 更新 av 中记录的 last_remainder
av->last_remainder = remainder;
// 更新last remainder的指针
remainder->bk = remainder->fd = unsorted_chunks(av);
if (!in_smallbin_range(remainder_size)) {
remainder->fd_nextsize = NULL;
remainder->bk_nextsize = NULL;
}
// 设置victim的头部,
set_head(victim, nb | PREV_INUSE |
(av != &main_arena ? NON_MAIN_ARENA : 0));
// 设置 remainder 的头部
set_head(remainder, remainder_size | PREV_INUSE);
// 设置记录 remainder 大小的 prev_size 字段,因为此时 remainder 处于空闲状态。
set_foot(remainder, remainder_size);
// 细致的检查,非调试状态下没有作用
check_malloced_chunk(av, victim, nb);
// 将 victim 从 chunk 模式转化为mem模式
void *p = chunk2mem(victim);
// 如果设置了perturb_type, 则将获取到的chunk初始化为 perturb_type ^ 0xff
alloc_perturb(p, bytes);
return p;
}

初始取出

1
2
3
/* remove from unsorted list */
unsorted_chunks(av)->bk = bck;
bck->fd = unsorted_chunks(av);

EXACT FIT

如果从 unsorted bin 中取出来的 chunk 大小正好合适,就直接使用。这里应该已经把合并后恰好合适的 chunk 给分配出去了。

1
2
3
4
5
6
7
8
9
10

/* Take now instead of binning if exact fit */
if (size == nb) {
set_inuse_bit_at_offset(victim, size);
if (av != &main_arena) set_non_main_arena(victim);
check_malloced_chunk(av, victim, nb);
void *p = chunk2mem(victim);
alloc_perturb(p, bytes);
return p;
}

PLACE CHUNK IN SMALL BIN

把取出来的 chunk 放到对应的 small bin 中。

1
2
3
4
5
6
/* place chunk in bin */

if (in_smallbin_range(size)) {
victim_index = smallbin_index(size);
bck = bin_at(av, victim_index);
fwd = bck->fd;

PLACE CHUNK IN LARGE BIN

把取出来的 chunk 放到对应的 large bin 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
} else {
// large bin 范围
victim_index = largebin_index(size);
bck = bin_at(av, victim_index); // 当前 large bin 的头部
fwd = bck->fd;

/* maintain large bins in sorted order */
/* 从这里我们可以总结出,largebin 以 fd_nextsize 递减排序。
同样大小的 chunk,后来的只会插入到之前同样大小的 chunk 后,
而不会修改之前相同大小的fd/bk_nextsize,这也很容易理解,
可以减低开销。此外,bin 头不参与 nextsize 链接。*/
// 如果 large bin 链表不空
if (fwd != bck) {
/* Or with inuse bit to speed comparisons */
// 加速比较,应该不仅仅有这个考虑,因为链表里的 chunk 都会设置该位。
size |= PREV_INUSE;
/* if smaller than smallest, bypass loop below */
// bck-bk 存储着相应 large bin 中最小的chunk。
// 如果遍历的 chunk 比当前最小的还要小,那就只需要插入到链表尾部。
// 判断 bck->bk 是不是在 main arena。
assert(chunk_main_arena(bck->bk));
if ((unsigned long) (size) <
(unsigned long) chunksize_nomask(bck->bk)) {
// 令 fwd 指向 large bin 头
fwd = bck;
// 令 bck 指向 largin bin 尾部 chunk
bck = bck->bk;
// victim 的 fd_nextsize 指向 largin bin 的第一个 chunk
victim->fd_nextsize = fwd->fd;
// victim 的 bk_nextsize 指向原来链表的第一个 chunk 指向的 bk_nextsize
victim->bk_nextsize = fwd->fd->bk_nextsize;
// 原来链表的第一个 chunk 的 bk_nextsize 指向 victim
// 原来指向链表第一个 chunk 的 fd_nextsize 指向 victim
fwd->fd->bk_nextsize =
victim->bk_nextsize->fd_nextsize = victim;
} else {
// 当前要插入的 victim 的大小大于最小的 chunk
// 判断 fwd 是否在 main arena
assert(chunk_main_arena(fwd));
// 从链表头部开始找到不比 victim 大的 chunk
while ((unsigned long) size < chunksize_nomask(fwd)) {
fwd = fwd->fd_nextsize;
assert(chunk_main_arena(fwd));
}
// 如果找到了一个和 victim 一样大的 chunk,
// 那就直接将 chunk 插入到该chunk的后面,并不修改 nextsize 指针。
if ((unsigned long) size ==
(unsigned long) chunksize_nomask(fwd))
/* Always insert in the second position. */
fwd = fwd->fd;
else {
// 如果找到的chunk和当前victim大小不一样
// 那么就需要构造 nextsize 双向链表了
victim->fd_nextsize = fwd;
victim->bk_nextsize = fwd->bk_nextsize;
fwd->bk_nextsize = victim;
victim->bk_nextsize->fd_nextsize = victim;
}
bck = fwd->bk;
}
} else
// 如果空的话,直接简单使得 fd_nextsize 与 bk_nextsize 构成一个双向链表即可。
victim->fd_nextsize = victim->bk_nextsize = victim;
}

最终取出

1
2
3
4
5
6
// 放到对应的 bin 中,构成 bck<-->victim<-->fwd。
mark_bin(av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

WHILE 迭代次数

while 最多迭代 10000 次后退出。

1
2
3
4
5

//
##define MAX_ITERS 10000
if (++iters >= MAX_ITERS) break;
}

















CATALOG
  1. 1. 基础知识
    1. 1.1. X86 平台 Linux 进程内存布局
      1. 1.1.1. 32 位模式下进程内存经典布局
      2. 1.1.2. 32 位模式下进程默认内存布局
      3. 1.1.3. 64 位模式下进程内存布局
    2. 1.2. 操作系统内存分配的相关函数
      1. 1.2.1. Heap 操作相关函数
      2. 1.2.2. Mmap 映射区域操作相关函数
  2. 2. 概述
    1. 2.1. 内存管理的方法
    2. 2.2. Ptmalloc 内存管理概述
      1. 2.2.1. 简介
      2. 2.2.2. 内存管理的设计假设
      3. 2.2.3. 内存管理数据结构概述
        1. 2.2.3.1. Main_arena 与 non_main_arena
        2. 2.2.3.2. chunk 的组织
        3. 2.2.3.3. 空闲 chunk 容器
        4. 2.2.3.4. sbrk 与 mmap
      4. 2.2.4. 内存分配概述
        1. 2.2.4.1. 分配算法概述
        2. 2.2.4.2. ptmalloc 的响应用户内存分配要求的具体步骤
      5. 2.2.5. 内存回收概述
  3. 3. 源码分析
    1. 3.1. 边界标记法
      1. 3.1.1. 大循环 - 遍历 unsortedbin