内存分配器dlmalloc 2.8.3源码浅析.doc

目目 录录 1 本文档介绍本文档介绍 1 2 边界标记法 边界标记法 2 3 分箱式内存管理分箱式内存管理 6 4 核心结构体核心结构体 MALLOC STATE 13 5 内存分配相关函数内存分配相关函数 16 5 1 函数DLMALLOC 16 5 2 函数TMALLOC SMALL 25 5 3 函数TMALLOC LARGE 27 5 4 函数SYS ALLOC 32 5 5 函数MMAP ALLOC 39 6 内存回收相关函数内存回收相关函数 42 6 1 函数DLFREE 42 6 2 函数SYS TRIM 47 7 本文档声明本文档声明 50 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 1 页 1 本文档介绍本文档介绍 dlmalloc 是目前一个十分流行的内存分配器 其由 Doug Lea1从 1987 年开始编写 到 目前为止 最新版本为 2 8 32 由于其高效率等特点被广泛的使用和研究 很多 linux 系统 等用的就是 dlmalloc 或其变形 比如 ptmalloc3 dlmalloc 的实现只有一个源文件 还有一个头文件 大概 5000 行 其内注释占了大 量篇幅 由于有这么多注释存在的情况下 表面上看上去很容易懂 的确如此 在不追求 细节的情况 对其大致思想的确很容易了解 没错 就只是了解而已 但是 dlmalloc 作 为一个高品质的佳作 实现上使用了非常多的技巧 在实现细节上不花费一定的精力是没 有办法深入理解其为什么这么做 这么做的好处在哪 只有当真正读懂后回味起来才发现 它是如此美妙 lenky0401 个人博客 4将陆续推出关于 dlmalloc 源码 针对 Doug Lea Malloc 的最新版 Version 2 8 3 的初步解析文章 由于 lenky0401 水平有限 因此也不能完全保证对 dlmalloc 的所有理解都准备无误 但是所有内容均出自个人的理解而并非存心妄自揣测来 愚人耳目 所以如果读者发现其中有什么错误 请勿见怪 如果可以则请来信告之 并欢 迎来信讨论 lenky0401 本文档描述的内容不会包含 dlmalloc 全部代码 但会将这其中涉及到的一些技巧尽量 讲出 我相信对 dlmalloc 源代码不感兴趣的朋友也可以学到这些独立的技巧而使用在自己 的编程实践中 另外 本文档对 dlmalloc 的描述过程中忽略了很多细节 主要是环境和自 定义设置 的反复核认 一致约定在未做说明的情况下就以 32 位平台 8 字节对齐 Ubuntu 8 10 操作系统作为参考环境设置考虑 1 个人主页为 http gee cs oswego edu 2 可以从 ftp g oswego edu pub misc malloc c 获取该源文件 3 主页为 http www malloc de en index html 4 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 2 页 2 边界标记法 边界标记法 dlmalloc 采用所谓的边界标记法将内存划分成很多块 从而对内存的分配与回收进行 管理 在 dlmalloc 的实现源码中定义了两种结构体 malloc chunk 和 malloc tree chunk 来描 述这些块 小于 256 字节的 chunk 块由结构体 malloc chunk 来描述 大于 256 字节的 chunk 块由结构体 malloc tree chunk 来管理 结构体 malloc chunk 和 malloc tree chunk 的定义如下 struct malloc chunk size t prev foot Size of previous chunk if free size t head Size and inuse bits struct malloc chunk fd double links used only if free struct malloc chunk bk typedef struct malloc chunk mchunk typedef struct malloc chunk mchunkptr typedef struct malloc chunk sbinptr The type of bins of chunks struct malloc tree chunk The first four fields must be compatible with malloc chunk size t prev foot size t head struct malloc tree chunk fd struct malloc tree chunk bk struct malloc tree chunk child 2 struct malloc tree chunk parent bindex t index 从它们的定义中可以看到结构体 malloc tree chunk 除了比 malloc chunk 多三个字段以 外 前四个字段和 malloc chunk 完全一样 我们先来看看只考虑使用结构体 malloc chunk 管理 结构体 malloc tree chunk 的管理类似 内存的情况 如下图所示 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 3 页 图 1 边界标记法划分内存 可以有多个连续的被使用中 chunk 块 但是不会有多个连续的空闲 chunk 块 因为连 续的多个空闲 chunk 块可以合并成一个大的空闲 chunk 块 按照边界标记法 结构体 malloc chunk 通过字段 head 和 prev foot 将内存分割成很多 块 从图 1 中 所示 字段 head 记录与本块相关的信息 这包括本 chunk 块大小 本块是 否在使用中 前一 chunk 块是否在使用中 head 一个字段就能存储这么多信息是因为 dlmalloc 在分割内存的时候总是以地址对齐 默认是 8 字节 可以自由设置 但是 8 字节 是最小值并且设置的值必须是 2 为底的幂函数值 即是 alignment 2 n n 为整数且 n 3 的方式来进行的 所以用 head 来存储本 chunk 块大小字节数的话 其末 3bit 位总是 0 因此这三位可以用来存储其它信息 比如 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 4 页 以第 0 位作为标志位 标记前一 chunk 块是否在使用中 为 1 表示使用 为 0 表示空 闲 以第 1 位作为标志位 标记本 chunk 块是否在使用中 为 1 表示使用 为 0 表示空闲 我们来看看它们的各自相关判断代码 define SIZE T ONE size t 1 define SIZE T TWO size t 2 define PINUSE BIT SIZE T ONE define CINUSE BIT SIZE T TWO define cinuse p p head Size of previous chunk if free size t head Size and inuse bits struct malloc chunk fd double links used only if free struct malloc chunk bk 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 8 页 mchunkptr smallbins NSMALLBINS 1 2 其中 mchunkptr在上一小节已经提过 为 typedef struct malloc chunk mchunkptr 而宏NSMALLBINS为32 即是 define NSMALLBINS 32U 因此smallbins为一个具有66 个malloc chunk结构体指针元素的数组 为什么是66个呢 不是32就可以了么 这里Doug Lea 使用了一个技巧 如果按照我们的常规想法 也许会申请32个malloc chunk结构体指针元素的 数组 然后再给链表申请一个头节点 即32个 再让每个指针元素正确指向而形成32个具有 头节点的链表 事实上 对于malloc chunk类型的链表 头节点 其内的prev foot和head字 段是没有任何实际作用的 因此这两个字段所占空间如果不合理使用的话那就是白白的浪费 我们再来看一看66个malloc chunk结构体指针元素的数组占了多少内存空间呢 结果为 66 4 264字节 而32个malloc chunk类型的链表 头节点 需要多少内存呢 32 16 512 真 的是512么 不是 刚才不是说了 prev foot和head这两个字段是没有任何实际作用的 因此 完全可以被重用 覆盖 因此实际需要内存为32 8 256 264大于256 事实上前16个字节都 被浪费掉了 如果考虑到8字节的chunk是不存在的 则浪费更多 那么这66个 malloc chunk结构体指针元素数组所占内存空间就可以存储这32个头节点了 事实上Doug Lea 也是这么做的 我们来看下于此相关的这一句代码 define smallbin at M i sbinptr char typedef struct malloc segment msegmentptr 英文注释很清晰 字段base表示该segment段的起始地址 size表示该segment段的大小 sflags是一个标记字段 两个标记 一个用于标记该segment段是否为通过mmap申请 一个 用于标记该segment段是否已经分配 而字段next用于指向下一个segment段 从而形成单 链表结构 记录该单链表表头的变量同样定义在结构体malloc state内 如下 msegment seg 这是个结构体变量 而不是结构体指针变量 这一点需要注意 刚才已经提到多个 segment 段是通过 next 形成单链表结构来组织管理的 dlmalloc 也没有对它们做其它特别 的索引处理 因此查找某一个 segment 段需要在该单链表内线性扫描查找 不过大多数情 况下 segment 段应该是非常少的 所以并不会造成多大的性能损失 在 dlmalloc 中对 malloc chunk malloc tree chunk malloc segment 给出了一个统一的 管理结构体 那就是前面反复提到的结构体 malloc state 其具体定义如下 struct malloc state binmap t smallmap binmap t treemap 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 14 页 size t dvsize size t topsize char least addr mchunkptr dv mchunkptr top size t trim check size t magic mchunkptr smallbins NSMALLBINS 1 2 tbinptr treebins NTREEBINS size t footprint size t max footprint flag t mflags if USE LOCKS MLOCK T mutex locate lock among fields that rarely change endif USE LOCKS msegment seg typedef struct malloc state mstate 该结构体中的一些字段在前面已经详细分析过了 比如 smallbins treebins 和 seg 其 它几个字段的作用 现在也一一说明如下 smallmap 是一个位图 用于标记对应的 smallbins 链表是否为空 1 表示非空 0 表示 空 treemap 也是一个位图 用于标记对应的 treebins 树是否为空 1 表示非空 0 表示空 dv 和 dvsize 指向一个 chunk 块 dvsize 记录该 chunk 块大小 该 chunk 块具有一个特 点就是 它是从最近的一次被用来服务小于 256 字节内存申请的 chunk 块中分裂出来的 chunk 块 比较拗口 简单点说就是为了更有效的利用程序的局部性原理 即对于应用程 序的一连续小块内存申请请求 dlmalloc 总是尽量从同一个 chunk 块获取空闲内存来满足 这些请求 因此分配给应用程序的内存都是在挨得比较近的地址空间内 从局部性原理可 以知道 这种内存分配方式在一定程度上可以提高应用程序的性能 当然 这种分配方式 只是尽量 如果有其它更好的 chunk 块选择 比如刚好有某个 chunk 大小就是应用程序申 请的内存大小 则会选择其它 chunk 块来分配内存 这在后面具体代码的分析过程中会看 到 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 15 页 top 和 topsize 也是指向一个 chunk 块 topsize 记录该 chunk 块大小 该 chunk 块比较 特殊 它不被任何分箱管理 即既不位于 smallbins 也不位于 treebins 它位于当前活跃 segment 段 即最近被用来分配空间服务应用程序内存请求的 的最顶端 在最顶端的好 处就是它可以自由伸缩 通过库函数 sbrk 因此大小可变 在 segment 段中间的那些 chunk 块大小一般不可变 但是有两种情况会变动 一是分配出去一部分内存用于满足应 用程序申请 此时 chunk 块变小 二是 当应用程序释放内存 free 时 dlmalloc 将检 查该释放内存是否可与前后空闲内存合并 此时就可能导致 chunk 块变大 字段 least addr 用来记录可获取的最小内存地址 直白点说就是相当于一个边界点 用于做越界安全检查 字段 trim check 用来记录一个临界值 我们知道应用程序 free 内存空间时 该释放的 内存空间并没有直接返还给系统而是被送回 dlmalloc 中进行管理 当释放的内存空间越来 越多时 dlmalloc 中管理的空闲 chunk 块也会变得越来越大 即由于多个连续空闲块合并 的结果 对于一个 segment 段中间的空闲 chunk 块没有办法释放给系统 因为释放中间的 空闲 chunk 块会将 segment 段切断 但是对于顶端 top 的 chunk 块则可以自由伸缩的 缩小顶端的 chunk 块也就是将空闲内存真正的返还给系统 那什么时候需要缩小顶端的 chunk 块呢 字段 trim check 就是记录的这个临界值 当顶端的 chunk 块大小大于字段 trim check 记录的值时就要进行缩减操作了 具体情况在后面源码分析时再看 其它几个字段不是我们主要关注的内容且比较简单 比如字段 magic 用于做确认检查 字段 mflags 用于标记一些属性 比如启用 mmap 禁用连续分配 字段 footprint 记 录从系统获得的字节数目 字段 max footprint 记录从系统获得的最大字节数目 字段 mutex 用于多线程互斥锁等等 在此就不做过多介绍了 dlmalloc 定义了一个结构体 malloc state 的全局变量 相关代码如下 static struct malloc state gm define gm 4049 size t nb MAX SMALL REQUEST 被定义为小块内存请求的最大值 define MAX SMALL REQUEST MAX SMALL SIZE CHUNK ALIGN MASK CHUNK OVERHEAD 根据对齐和其它 比如是否具有 foot 等设置 该值具体数据稍有不同 比如为 247 或 248 等 但都比 256 小 在这里我们简单的认定它为 256 4050 if bytes MAX SMALL REQUEST 4051 bindex t idx 4052 binmap t smallbits 对请求内存数目进行对齐处理 另外如果请求内存数目小于最小请求值 MIN REQUEST 则取最小值 chunk 块大小 16 字节 4053 nb bytes SMALLBIN SHIFT 4054 idx small index nb 将箱号的位图标记移到最右边位 4055 smallbits gm smallmap idx 4056 注意 0 x3U 的二进制为 0000 0011 只给出了低 8 位 因此如果它和 smallbits 进 行位与为真 则 smallbits 的低 2 位有三种情况 第一种情况 1 1 第二种情况 0 1 第三种情况 1 0 为 1 表示该对应箱号内存在对应大小的空闲 chunk 块 前两种情况都表示存在大 小刚好和请求大小一致的空闲 chunk 块 而第三种情况表示不存在大小刚好和请求大 小一致的空闲 chunk 块 但是存在大小和请求大小只相差一个箱号的空闲 chunk 块 4057 if smallbits 在第三种情况 1 0 时需要将箱号 idx 加 1 下面这行代码将这三种情况都无 区别的处理了 即在第一二种情况时箱号 idx 并不会加 1 很精巧的代码 4059 idx smallbits Uses next bin if idx empty 找到对应箱号的 chunk 块链头节点 define smallbin at M i sbinptr char 4062 assert chunksize p small index2size idx 将第一块空闲 chunk 块 假设为 chunk 块 A 从链表中拆出 用于分配 环形双 向链表的头节点拆除就不多讲了 4063 unlink first small chunk gm b p idx 本块 chunk 块 A 被用于分配使用 因此需要修改边界标记 宏 small index2size 用于根据箱号计算对应箱内空闲 chunk 块字节数目 define small index2size i i head s PINUSE BIT CINUSE BIT mchunkptr char p s head PINUSE BIT mark inuse foot M p s 该宏第二行用于标记本 chunk 块 A 在使用中 即将被分配使用以满足请求 并且 前一块也在使用中 这是显然的 因为有合并的操作 所以不会存在两个连续的空闲 块 第三行是修改邻接的下一 chunk 块的 PINUSE BIT 标记 表明邻接的下一 chunk 块的前一邻接 chunk 块 即当前正要被分配使用的 chunk 块 A 在使用中 第四行修 改 footers 标记 前面曾经说过 prev foot 用于记录前一邻接 chunk 块的大小 那是在 前一邻接 chunk 块空闲情况 如果前一邻接 chunk 块处于使用状况 prev foot 则用于 记录它们所在的 malloc state 信息 如下 Set foot of inuse chunk to be xor of mstate and seed define mark inuse foot M p s mchunkptr char p s prev foot size t M mparams magic mparams magic 起安全检测作用 4064 set inuse and pinuse gm p small index2size idx 宏 chunk2mem 和 mem2chunk 用于在 chunk 块头地址和实际可用内存起始地址之 间进行相互转换 这点根据 chunk 块结构体 malloc chunk 和 malloc tree chunk 的定义 很容易理解 conversion from malloc headers to user pointers and back define chunk2mem p void char p TWO SIZE T SIZES define mem2chunk mem mchunkptr char mem TWO SIZE T SIZES 4065 mem chunk2mem p debug 编译时用于做安全检测 4066 check malloced chunk gm mem nb 内存申请请求得以满足 跳到最后执行解除互斥锁操作 返回分配的内存起始地 址 就算不考虑块头 对齐等开销 malloc 分配的内存也可能会比应用程序实际应分 配内存多 即前面的第三种情况 1 0 这种情况时 dlmalloc 分配的内存将多出 8 个 字节 由于 8 个字节不足以组成一个 chunk 块 因此也就没有必要进行分割 而是全 部分配给当前申请请求 下面还可以看到这种情况 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 22 页 4067 goto postaction 4068 4069 dv chunk 块不够大 因此在所有空闲 chunk 块中查找可以满足该请求的 chunk 块 4070 else if nb gm dvsize 在 smallbins 中存在可满足该请求的空闲 chunk 块 4071 if smallbits 0 Use chunk in next nonempty smallbin 4072 mchunkptr b p r 4073 size t rsize 4074 bindex t i 下面两个宏用于位操作 我们来看看 idx2bit 宏取第 i 位为 1 其它位都为 0 的掩码 举个例子 idx2bit 3 为 0000 1000 只显示 8 位 下同 define idx2bit i binmap t 1 i left bits 宏取 x 中值为 1 的最小 bit 位的左边 不包括值为 1 的该最小 bit 位 所有 位都为 1 其它位都为 0 的掩码 举个例子 left bits 6 为 1111 1100 因为 6 的二 进制位 0000 0110 值为 1 的最小 bit 位为第 1 位 因此结果为第 1 位左边 不包括 第 1 位 所有位都为 1 其它位都为 0 的掩码 define left bits x x 1 x 1 leftbits 为所有可满足当前申请请求的箱号 4075 binmap t leftbits smallbits fd 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 23 页 4080 assert chunksize p small index2size i 拆出链表的第一个空闲 chunk 块以进行内存分配 4081 unlink first small chunk gm b p i 计算分割该 chunk 块 用于服务内存申请请求 后 该 chunk 块剩余的字节数 4082 rsize small index2size i nb 4083 Fit here cannot be remainderless if 4byte sizes 剩余的字节数太小无法组建一个新的空闲块 因此直接全部分配 这里的判断利用了短路运算符的特性 我们应注意到当前待分配的 chunk 块大小 和申请请求字节大小至少相差两个箱号的字节数目 即剩余字节数至少有 16 字节 当 SIZE T SIZE 4 时 是不可能出现 rsize MIN CHUNK SIZE 为真的情况的 换 句话说 只有当 SIZE T SIZE 4 的情况下 rsize MIN CHUNK SIZE 才有可能为真 至于为什么 可由 MIN CHUNK SIZE 的具体定义找到原因 define MIN CHUNK SIZE MCHUNK SIZE CHUNK ALIGN MASK 新组建空闲 chunk 块结构起始地址 define chunk plus offset p s mchunkptr char p s 4088 r chunk plus offset p nb 设置新组建空闲 chunk 块的标记 包括本块大小 本块的前一邻接块在使用中标识以 及设置 prev foot 数据为前一邻接块大小 define set size and pinuse of free chunk p s p head s PINUSE BIT set foot p s 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 24 页 define set foot p s mchunkptr char p s prev foot s 4089 set size and pinuse of free chunk r rsize 将新组建空闲 chunk 块替换原来的 dv chunk 块 define replace dv M P S size t DVS M dvsize if DVS 0 mchunkptr DV M dv assert is small DVS insert small chunk M DV DVS M dvsize S M dv P 4090 replace dv gm r rsize 4091 获取对应的实际分配内存起始地址 做 debug 检测 跳转等 4092 mem chunk2mem p 4093 check malloced chunk gm mem nb 4094 goto postaction 4095 4096 在 smallbins 中没有可满足该请求的空闲 chunk 块 则试图在 treebins 中查找可满 足该请求的空闲 chunk 块 函数 tmalloc small 的分析在后面给出 4097 else if gm treemap 0 4099 goto postaction 4100 4101 4102 超过最大请求值 4103 else if bytes MAX REQUEST 4104 nb MAX SIZE T Too big to allocate Force failure in sys alloc 4105 else 请求的内存大小在 MAX SMALL REQUEST 和 MAX REQUEST 之间 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 25 页 首先进行对齐处理 CHUNK OVERHEAD 为边界标记占用的空间 CHUNK ALIGN MASK 为对齐设置值 define pad request req req CHUNK OVERHEAD CHUNK ALIGN MASK 试图在 treebins 中查找可满足该请求的空闲 chunk 块 函数 tmalloc large 的分析 在后面给出 4107 if gm treemap 0 4109 goto postaction 4110 4111 4112 从 dv chunk 块内分配 注意各个执行路径 4113 if nb dvsize 4114 size t rsize gm dvsize nb 4115 mchunkptr p gm dv 剩余空间足够大 则进行分割和组建新 chunk 块 4116 if rsize MIN CHUNK SIZE split dv 4117 mchunkptr r gm dv chunk plus offset p nb 4118 gm dvsize rsize 4119 set size and pinuse of free chunk r rsize 4120 set size and pinuse of inuse chunk gm p nb 4121 4122 else exhaust dv 否则的话 直接全部分配完 4123 size t dvs gm dvsize 4124 gm dvsize 0 4125 gm dv 0 4126 set inuse and pinuse gm p dvs 4127 4128 mem chunk2mem p 4129 check malloced chunk gm mem nb 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 26 页 4130 goto postaction 4131 4132 从 top chunk 块内分配 注意各个执行路径 4133 else if nb topsize Split top 4134 size t rsize gm topsize nb 4135 mchunkptr p gm top 4136 mchunkptr r gm top chunk plus offset p nb 4137 r head rsize PINUSE BIT 4138 set size and pinuse of inuse chunk gm p nb 4139 mem chunk2mem p 4140 check top chunk gm gm top 4141 check malloced chunk gm mem nb 4142 goto postaction 4143 4144 最后的办法 直接从系统获取内存空间 函数 sys alloc 的分析在后面给出 4145 mem sys alloc gm nb 4146 4147 postaction 和前面的 PREACTION 宏对应 用于进行解锁操作 define POSTACTION M if use lock M RELEASE LOCK define RELEASE LOCK l pthread mutex unlock l 4148 POSTACTION gm 4149 return mem 4150 4151 4152 return 0 4153 5 2 函数函数 tmalloc small 3693 allocate a small request from the best fitting chunk in a treebin 这里的参数 nb 总是小于等于 256 应注意这点 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 27 页 3694 static void tmalloc small mstate m size t nb 3695 tchunkptr t v 3696 size t rsize 3697 bindex t i 3698 binmap t leastbit least bit m treemap 3699 compute bit2idx leastbit i 3700 3701 v t treebin at m i 请求字节数目 nb child 0 0 t child 0 t child 1 同样应注意到 请求字节数目 nb 256 而 tree 里的每个 chunk 块都大于等于 256 这一点来帮助理解 3704 while t leftmost child t 0 3705 size t trem chunksize t nb 3706 if trem rsize 3707 rsize trem 3708 v t 3709 3710 3711 安全检测 3712 if RTCHECK ok address m v 3713 mchunkptr r chunk plus offset v nb 3714 assert chunksize v rsize nb 3715 if RTCHECK ok next v r 将其拆出 dltree 3716 unlink large chunk m v 剩余空间太小则直接全部分配 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 28 页 3717 if rsize MIN CHUNK SIZE 3718 set inuse and pinuse m v rsize nb 3719 else 否则将剩余空间组建成新的 chunk 块并替换为新的 dv chunk 块 3720 set size and pinuse of inuse chunk m v nb 3721 set size and pinuse of free chunk r rsize 3722 replace dv m r rsize 3723 3724 return chunk2mem v 3725 3726 3727 3728 CORRUPTION ERROR ACTION m 3729 return 0 3730 5 3 函数函数 tmalloc large 3620 allocate a large request from the best fitting chunk in a treebin MAX SMALL REQUEST 对齐值 nb 1 TREEBIN SHIFT 2 define NTREEBINS 32U define SIZE T BITSIZE sizeof size t leftshift for tree index idx 值 0 25 1 25 2 24 3 24 4 23 5 23 6 22 7 22 8 21 9 21 10 20 11 20 12 19 13 19 14 18 15 18 16 17 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 30 页 17 17 18 16 19 16 20 15 21 15 22 14 23 14 24 13 25 13 26 12 27 12 28 11 29 11 30 10 31 0 因此下面这个 sizebits 的值就是将 nb 中起关键码作用的位移到最左边的结果值 3630 size t sizebits nb head 比之前选定的 chunk 块更合适 3635 if trem child 1 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 31 页 根据关键码值进入相应的子树 3641 t t child sizebits SIZE T BITSIZE SIZE T ONE rst 保存包含有最接近 nb 字节数大小 chunk 块的 dltree 子树 3642 if rt 0 将要继续查找的子树为空 则保存 rst 到 t 然后跳出 for 循环 3644 if t 0 3645 t rst set t to least subtree holding sizes nb 3646 break 3647 3648 sizebits treemap 存在 3654 if leftbits 0 3655 bindex t i 选择最合适的分箱 3656 binmap t leastbit least bit leftbits 计算对应箱号 3657 compute bit2idx leastbit i 箱子对应 dltree 根节点 3658 t treebin at m i 3659 3660 3661 执行到这已经可以确定以 t 为根节点的 dltree 中所有 chunk 块都可满足申请请求 下面这个循环只不过试图在这个 dltree 中找到一个最合适的 chunk 块来用于内存分配 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 32 页 最合适的 chunk 块被保存在变量 v 内 3662 while t 0 find smallest of tree or subtree 3663 size t trem chunksize t nb 3664 if trem child 0 0 t child 0 t child 1 3668 t leftmost child t 3669 3670 3671 If dv is a better fit return 0 so malloc will use it 前面在 treebins 中选择的 chunk 块存在 即变量 v 不为空 并且它比 dv chunk 块 更适合 即选择的 chunk 块大小比 dv chunk 块大小更接近当前请求字节数目 用于内 存分配以服务当前申请请求 如果 dv chunk 块更适合用来分配 则本函数将返回 0 因此会在返回到 dlmalloc 函数内再进行在 dv chunk 块的内存分配操作 3672 if v 0 3675 assert chunksize v rsize nb 3676 if RTCHECK ok next v r 3677 unlink large chunk m v 3678 if rsize mparams mmap threshold 函数 mmap alloc 的分析后面给出 3332 void mem mmap alloc m nb 3333 if mem 0 3334 return mem 3335 3336 根据相对优劣排序依次按照如下三种方法从系统获取内存 1 利用 MORECORE 分配连续空间 2 利用 MMAP 分配新空间 3 利用 MORECORE 分配不连续空间 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 34 页 3337 3338 Try getting memory in any of three ways in most preferred to 3339 least preferred order 3340 1 A call to MORECORE that can normally contiguously extend memory 3341 disabled if not MORECORE CONTIGUOUS or not HAVE MORECORE or 3342 or main space is mmapped or a previous contiguous call failed 3343 2 A call to MMAP new space disabled if not HAVE MMAP 3344 Note that under the default settings if MORECORE is unable to 3345 fulfill a request and HAVE MMAP is true then mmap is 3346 used as a noncontiguous system allocator This is a useful backup 3347 strategy for systems with holes in address spaces in this case 3348 sbrk cannot contiguously expand the heap but mmap may be able to 3349 find space 3350 3 A call to MORECORE that cannot usually contiguously extend memory 3351 disabled if not HAVE MORECORE 3352 3353 宏 use noncontiguous 定义如下 define use noncontiguous M M mflags 函数 segment holding 用于查找某一内存地址所属于的 segment 段 具体代码如 下 我们可以看到所谓的查找就是简单的线性扫描查找 Return segment holding given address static msegmentptr segment holding mstate m char addr msegmentptr sp for if addr sp base if sp sp next 0 return 0 内存分配器 dlmalloc 2 8 3 源码浅析 我心永恒 爱无止境第 35 页 3356 msegmentptr ss m top 0 0 segment holding m char m top 3357 size t asize 0 上锁 3358 ACQUIRE MORECORE LOCK 3359 top chunk 块为空 即第一次分配情况 3360 if ss 0 First time through or recovery 获取内存的当前边界点 即所谓的当前中断点 CALL MORECORE 间接的调用 sbrk 函数 函数 sbrk 移动设置新的当前中断点并返回设置之前的中断点 define CALL MORECORE S MORECORE S extern void sbrk ptrdiff t 3361 char base char CALL MORECORE 0 3362 if base CMFAIL 进行对齐处理 这里的对齐一般以一个内存页大小 32 位平台下 大部分情况是 4K 为基准 也可自由设置 比如 64K 3363 asize granularity align nb TOP FOOT SIZE SIZE T ONE 3364 Adjust to end on a page boundary 起始边界不是页对齐 则需要将末尾边界调整为页对齐 define is page aligned S size t S 3367 Can t call MORECORE if size is negative when treated as signed asize 需要小于 HALF MAX SIZE T sbrk 函数的参数是有符号的 如果大于 HALF MAX SIZE T 则传到 sbrk 函数内部则成了负数 define HALF MAX SIZE T MAX SIZE T 2U define MAX SIZE T size t 0 3368 if asize topsize TOP FOOT SIZE SIZE T ONE 3378 Use mem here only if it did continuously extend old space 3379 if asize base ss size 3381 tbase br 3382 tsize asize 3383 3384 3385 部分操作失败的处理 3386 if tbase CMFAIL Cope with partial failure 3387 if br CMFAIL Try to use extend the space we did get 3388 if asize HALF MAX SIZE T 3391 if esize mflags USE NON