文章目录
大佬的关于ptmalloc的知识分享的链接
关于ptmalloc的思考
缓存思想
理解缓存思想其实就是一种提高效率的思想
-
请求分配内存时,系统调用 brk() 分配一块比较大的内存作为缓存, 之后即使没有在 Bins 中也找不到, 也不需要每次触发系统调用, 直接切割这块大的内存即可.
缓存的思想,如果没有缓存,那么这将使得每次内存分配都系统调用,速度效率低下 -
释放内存时暂时不还给系统,标记空闲,等下一次需要相同大小,直接使用该块空闲内存即可,从而减少系统调用
-
除了以上两种缓存,Fastbin也是一种缓存手段,对于长度在fastbin范围内的chunk释放后不会放到Bins中,也不会标记为空闲(没有标记为空闲即成功避免合并),下次分配内存时首先查找Fastbins,这就避免了切割
-
而unsorted bin属于刚刚释放的内存与bins之间的缓存。刚刚释放的内存会先放到 Unsorted 缓存, 在下一次内存分配时, 会优先于 Bins 查找, 如果能命中 Unsorted 缓冲最好, 否则就把 Unsorted 中的 chunk 统一整理到对应 Bins.
-
last_remainder也是一种缓存,是切割时剩下的那个,下次切割也从它开始。 大致就是希望一直切割同一个 chunk. 在遍历 Unsorted 时使用, 但是它的使用是有条件的.
chunk结构
large bin补充
对于 large bins, 分割边界是递增的, 举个简单例子: 前 32 个 large bins 的分割边界都是 64 bytes, 之后 16 个 large bins 的分割边界是 512 bytes. 以上仅为字长为 32 位的情况下
32 bins of size 64
16 bins of size 512
8 bins of size 4096
4 bins of size 32768
2 bins of size 262144
1 bin of size what's left
large bin 有些特殊, 空闲 chunk 的存放需要排序, large_bin->bk 为最小 size 的 chunk, large_bin->fd 为最大 size 的 chunk.
fast bin 补充
当进行内存分配时先从 Fastbins 中进行查找, 之后才在 Bins 进行查找; 释放内存时, 当chunk size < max_fast 会先存放到 Fastbins.
Fastbins 的合并(清空), 也就是 malloc_consolidate 这个函数的工作.
- 何时会触发 malloc_consolidate(仅对 _int_malloc 函数而言) ?
- small bins 尚未初始化
- 需要 size 大于 small bins
- malloc_consolidate 如何进行合并 ?
遍历 Fastbins 中的 chunk, 设置每个 chunk 的空闲标志位为 0, 并合并相邻的空闲 chunk, 之后把该 chunk 存放到 unsorted bin 中.
Fastbins 是单向链表, 可以通过 fastbin->fd 遍历 Fastbins.
TRIM_FASTBINS=1 fast bin 会与相邻的 top chunk 进行合并,为0时不会合并
unsorted bin 补充
只有一个 unsorted bin, 进行内存分配查找时先在 Fastbins, small bins 中查找, 之后会在 unsorted bin 中进行查找, 并整理 unsorted bin 中所有的 chunk 到 Bins 中对应的 Bin. unsorted bin 位于 bin[1].
unsorted_bin->fd 指向双向环链表的头结点, unsorted_bin->bk 指向双向环链表的尾节点, 在头部插入新的节点
top chunk 补充
mmaped chunk补充
Last remainder补充
last remainder的产生
bins链(fast bin除外)存在free chunk时,若malloc的请求大小小于free chunk,就会切割这个free chunk,剩余的chunk就是last remainder,last remainder会被放入unsorted bin中
产生last remainder后,malloc_state结构体中的last_remainder成员指针会被初始化,指向这个last_remainder
- 切割unsorted bin
当unsorted bin有free chunk可以给malloc切割使用时:
- 将free chunk放置到对应大小的bins链
- 切割free chunk,产生last remainder
- last remainder放入unsorted bin
- 切割small bin、large bin
- 切割free chunk,产生last remainder
- last remainder放入unsorted bin
malloc_state补充
mmap收缩阈值
M_TRIM_THRESHOLD用于设置mmap收缩阈值,默认值为128KB。自动收缩只会在free时才发生,如果当前free的chunk大小加上前后能合并chunk的大小大于64KB,并且top chunk的大小达到mmap收缩阈值,对于主分配区,调用malloc_trim()返回一部分内存给操作系统,对于非主分配区,调用heap_trim()返回一部分内存给操作系统,在发生内存收缩时,还是从新设置mmap分配阈值和mmap收缩阈值。
mmap分配阈值
M_MMAP_THRESHOLD用于设置mmap分配阈值,默认值为128KB,ptmalloc默认开启动态调整mmap分配阈值和mmap收缩阈值。
当用户需要分配的内存大于mmap分配阈值,ptmalloc的malloc()函数其实相当于mmap()的简单封装,free函数相当于munmap()的简单封装。相当于直接通过系统调用分配内存,回收的内存就直接返回给操作系统了。因为这些大块内存不能被ptmalloc缓存管理,不能重用,所以ptmalloc也只有在万不得已的情况下才使用该方式分配内存。
ptmalloc响应用户内存分配要求工作流程
-
获取分配区的锁, 为了防止多个线程同时访问同一个分配区, 在进行分配之前需要取得分配区域的锁. 线程先查看线程私有实例中是否已经存在一个分配区, 如果存 在尝试对该分配区加锁, 如果加锁成功, 使用该分配区分配内存, 否则, 该线程搜 索分配区循环链表试图获得一个空闲(没有加锁)的分配区. 如果所有的分配区都 已经加锁, 那么 ptmalloc 会开辟一个新的分配区, 把该分配区加入到全局分配区循 环链表和线程的私有实例中并加锁, 然后使用该分配区进行分配操作. 开辟出来的 新分配区一定为非主分配区, 因为主分配区是从父进程那里继承来的. 开辟非主分配区时会调用 mmap()创建一个 sub-heap, 并设置好 top chunk.
-
将用户的请求大小转换为实际需要分配的 chunk 空间大小. 具体查看 request2size 宏 (malloc.c:3332)
-
判断所需分配 chunk 的大小是否满足 chunk_size <= max_fast (max_fast 默认为 64B), 如果是的话, 则转下一步, 否则跳到第 5 步. (malloc.c:3340)
-
首先尝试在 Fastbins 中查找所需大小的 chunk 分配给用户. 如果可以找到, 则分配结束. 否则转到下一步. (malloc.c:3340)
-
判断所需大小是否处在 small bins 中, 即判断 chunk_size < 512B 是否成立. 如果 chunk 大小处在 small bins 中, 则转下一步, 否则转到第 7 步. (malloc.c:3377)
-
根据所需分配的 chunk 的大小, 找到具体所在的某个 small bin, 从该 Bin 的尾部摘取一个恰好满足大小的 chunk. 若成功, 则分配结束, 否则, 转到 8. (malloc.c:3377)
-
到了这一步, 说明需要分配的是一块大的内存, 于是, ptmalloc 首先会遍历 Fastbins 中的 chunk, 将相邻的空闲 chunk 进行合并, 并链接到 unsorted bin 中. 对于 Fastbins 的合并是由
malloc_consolidate
做处理. (malloc.c:3421) -
后序遍历unsort bin,如果存在大小正好合适的chunk,那么便直接拿去使用,结束循环遍历。(后面的就不管了,保持原样
如果大小不是正好,那么便放到相应的bin中去,如果是small bin就放到small bin,是large bin就放到large bin(fast bin被包含在small bin里面了
遍历所有chunk遍历完之后,由于没有一个大小正好的chunk,那么便到刚刚所分配到不同bin中去寻找,如果size是属于small bin的,那么便到small bin中去寻找,如果有比需要的size更大的chunk存在的话,那么就切割,切割剩的一部分如果不小于0x10的话就放到unsort bin中去,如果小于就一起给了。如果small bin当中没有比需要size更大的chunk存在,那么就往large bin中去寻找了(就是在small bin中切割的情况。
在large bin里后序遍历(bk指针开始)。如果找到了比需要size大的chunk,那么也同样切割,切割剩下的一部分不小于0x10则放到unsort bin中去,小于则一起给了。
如果还是没有找到,则到下一步 -
到了这一步说明在对应的 bin 上没有找到合适的大小, 无论是 small bin 还是 large bin, 对于 small bin, 如果没有对应大小的 small bin, 只能 idx+1. 对于 large bin,在上一步的 large bin 并不一定能找到合适的 chunk 进行切割, 因为 large bins 间隔是很大的, 假如当前的 idx 的 large bin 只有一个 chunk, 但是所需 size 大于该 chunk, 这就导致找不到合适的, 只能继续 idx+1, 最后都需要根据 bitmap 找到之后第一个非空闲的 bin. 在这两种情况下找到的 bin 中的 chunk 一定可以进行切割或者全部分配(剩余的 size < MINSIZE) (malloc.c:3649)
-
如果仍然都没有找到合适的 chunk, 那么就需要操作 top chunk 来进行分配了. 判断 top chunk 大小是否满足所需 chunk 的大小, 如果是, 则从 top chunk 中分出一块来. 否则转到下一步. (malloc.c:3749)
-
到了这一步, 说明 top chunk 也不能满足分配要求, 所以, 于是就有了两个选择: 如果是主分配区, 判断是否为第一次调用 ,如果是则需要进行一次初始化工作, 分配一块大小为(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap.若已经初始化过了,则调用 sbrk(), 增加 top chunk 大小,然后top chunk 中切割出一个 chunk。 top chunk 中切割出一个 chunk, 使之满足分配需求, 并将内存指针返回给用户。如果是非主分配区,则判断所需分配的 chunk 大小是否大于等于 mmap 分配阈值 。 如果是的话,则到下一步,否则调用 mmap 来分配一个新的 sub-heap, 增加 top chunk 大小,然后在 top chunk 中切割出一个 chunk, 使之满足分配需求, 并将内存指针返回给用户. 在这里, 需要依靠 chunk 的大小来决定到底使用哪种方法.
-
使用 mmap()来直接分配,用 mmap 系统调用为程序的内存空间映射一块 chunk_size align 4kB 大小的空间. 然后将内存指针返回给用户.
free时工作流程
-
free()函数同样首先需要获取分配区的锁, 来保证线程安全.
-
判断传入的指针是否为 0, 如果为 0, 则什么都不做, 直接 return.否则转下一步.
-
判断 chunk 的大小和所处的位置, 若 chunk_size <= max_fast, 并且 chunk 并不位于 heap 的顶部, 也就是说并不与 Top chunk 相邻, 则转到下一步, 否则跳到第 5 步.(因为与 top chunk 相邻的 chunk(fastbin) ,会与 top chunk 进行合并, 所以这里不仅需要判断大小, 还需要判断相邻情况)
-
将 chunk 放到 Fastbins 中, chunk 放入到 Fastbins 中时, 并不修改该 chunk 使用状 态位 P.也不与相邻的 chunk 进行合并.只是放进去, 如此而已.这一步做完之后 释放便结束了, 程序从 free()函数中返回.
-
判断所需释放的 chunk 是否为 mmaped chunk, 如果是, 则调用 munmap()释放 mmaped chunk, 解除内存空间映射, 该该空间不再有效.如果不是mappedchunk并且开启了 mmap 分配阈值的动态调整机制, 并且当前回收的 chunk 大小大于 mmap 分配阈值, 则将 mmap 分配阈值设置为该 chunk 的大小, 将 mmap 收缩阈值设定为 mmap 分配阈值的 2 倍, 释放完成, 否则跳到下一步.
-
判断前一个 chunk 是否处在使用中, 如果前一个块也是空闲块, 则合并.并转下一步.
-
判断当前释放 chunk 的下一个块是否为 top chunk, 如果是, 则转第 9 步, 否则转 下一步.
-
判断下一个 chunk 是否处在使用中, 如果下一个 chunk 也是空闲的, 则合并, 并将合并后的 chunk 放到 unsorted bin 中.注意, 这里在合并的过程中, 要更新 chunk 的大小, 以反映合并后的 chunk 的大小.并转到第 10 步.
-
如果执行到这一步, 说明释放了一个与 top chunk 相邻的 chunk.则无论它有多大, 都将它与 top chunk 合并, 并更新 top chunk 的大小等信息.转下一步. (malloc.c:3950)
-
判断合并后的 chunk 的大小是否大于 FASTBIN_CONSOLIDATION_THRESHOLD(默认 64KB), 如果是的话, 则会触发进行 Fastbins 的合并操作(malloc_consolidate), Fastbins 中的 chunk 将被遍历, 并与相邻的空闲 chunk 进行合并, 合并后的 chunk 会被放到 unsorted bin 中. Fastbins 将变为空, 操作完成之后转下一步.
-
判断 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 收缩阈值, 才有可能收缩堆.