c语言malloc底层实现 - 木东驿站 - Powered by MoodBlog

CONTENT

c语言malloc底层实现

在使用c语言或者c++的时候,我们若要申请堆内存,都要和malloc打交道(c++ new的底层实现也是malloc)。malloc是实现在用户态的内存管理模块,并不是直接进行系统调用。malloc有多种实现,在linux环境下,malloc主要是采用ptmalloc。本文参考网上博文对ptmalloc原理进行一下总结。

进程内存布局

2018041513242953.png

这是每一个linux进程拥有的虚拟内存布局,这些虚拟内存地址通过页表映射到物理内存,操作系统维护着这个页表。虚拟内存最上层是内核空间映射,所有进程都会把这部分映射到相同的物理内存,用户态是不可以访问这些内存的。

进程空间最顶部是栈,用来存储程序中的局部变量,进程中每一个线程都有自己的栈,栈是自顶向下扩展的。在栈的下面是内存映射段,自顶向下扩展,这部分主要用来映射文件或者直接映射物理内存(匿名映射),内存映射是高效的文件io方法,可以有效减少数据复制次数。加载动态库时采用内存映射,如果使用malloc申请大内存(默认情况下大于128kb属于大内存),将会直接映射一块物理内存,而不是扩展堆内存。再下面是堆,自下向上扩展,mmap和堆相对扩展,这样有利于同时使用mmap内存映射和堆进行内存分配,直到虚拟内存被消耗完毕。bss和data存储全局或静态变量,bss存储未初始化的变量,data存储编译时已经初始化的变量。

多分配区

ptmalloc为改善多线程情况下的性能,采用了多分配区方案,进程拥有一个主分配区,也可以拥有一些非主分配区。各个分配区组成一个环形链表进行关闭,当进程需要配置空间时,先查看当前线程的私有变量是否已经存在一个分配区,如果存在就对该分配区进行加锁然后采取下一步行动。如果加锁失败,就会遍历链表寻找一个正在空闲的分配区,如果找不到就要重新分配一个非主分配区了。当释放内存时,由于需要整理内存,同样需要对分配区进行加锁,如果分配区正在被使用,就要等待互斥锁被释放后再进入分配区释放内存。

要注意以下两点:

(1)进程根据当前分配区征用情况动态的增加非主分配区,一旦增加就不会再减少了。

(2)主分配区既可以使用brk调整堆的上限,也可以使用mmap映射内存,非主分配区只能使用mmap。

chunk

brk(),sbrk(),mmap()属于系统调用,需要切换成内核态,为了减少系统调用的次数,ptmalloc使用内存池对小空间进行统一管理,在用户态实现内存的再分配。ptmalloc把空间分为一个个内存块,内存块拥有一些自己的信息,比如空间大小,是否被使用等等,这个空间块就被称为chunk。

chunk基本结构如下:

struct malloc_chunk {  
  INTERNAL_SIZE_T      prev_size;    
  INTERNAL_SIZE_T      size;
  
  struct malloc_chunk* fd; 
  struct malloc_chunk* bk;  
  
  struct malloc_chunk* fd_nextsize;      
  struct malloc_chunk* bk_nextsize; 
};

prev_size:连续内存中上一块chunk的大小。

size:本chunk大小,另外在最后位记录了三个重要信息:(1)上一个chunk是否正在被使用。(2)当前chunk是否是通过mmap获得的内存(3)当前chunk是否属于非主分配区。

fd、bk:chunk根据大小被连接在不同的链表中,这两个指针用于实现双向链表,指向前一个/下一个chunk。

fd_nextsize:加快查询速度,指向下一个比当前chunk大的空闲chunk。

bk_nextsize:加快查询速度,指向下一个比当前chunk小的空闲chunk。

空闲链表bins

为了减少系统调用次数,ptmalloc维护了一系列链表保存被用户free的内存块,而不是在用户free内存后将其立刻交换给系统。每一个链表称为一个bin,bin可以分为以下几种类型。

fast bin:

fast bins有10个队列,每一个fast bin维护着一组chunk,不同队列之间chunk大小以8字节递增。最大为64B。当用户释放一块不大于max_fast(64B)的chunk时,会被默认放到fast bins上,此后分配小内存时,优先从fast bins开始查找。

unsorted bin:

当用户释放的chunk大小大于fast bin,或者fast bin相邻内存块合并成一个大chunk时,首先会放到unsorted bin里面。用户申请内存时,如果在fast bin没有找到合适的chunk,malloc在small bins或者large bins查询之前,首先会查找unsorted bin,如果没有找到合适的chunk,就会把上面的chunk移动到small bins或者large bins。

samll bins:

小于512B的chunk加入small bin,一共有64个small bin。

large bins:

大于512B的chunk加入large bin,每一个large bin包含给定范围大小的chunk,按照大小递减排序。分配chunk时,遍历寻找一个最接近用户所需空间大小的chunk,切割成两块chunk,一块交给用户,另一块放入unsorted bin。

特殊chunk

top chunk:

分配区顶部的空闲内存,当bins上的chunk都不能满足需求时,就需要从top chunk切一块给用户使用。当top chunk也无法满足用户需求时,就需要调用brk()或者mmap()系统调用来扩容。

mmap chunk:

当需要的内存非常大(阈值128kb),就会直接通过mmap映射到映射内存区,当释放的时候直接交还给系统。

last remainder chunk


内存分配流程

(1)获取一个没有正在空闲的分配区,如果找不到未加锁的分配区,就再创建一个非主分配区。

(2)计算所需资源的chunk大小(需要另外一点空间来记录chunk信息)

(3)如果所需空间小于max_fast,直接去fast_bins寻找合适的空间,找到的话就返回,找不到继续下一步。

(4)判断所需chunk是否小于512B,如果小于就去small bins寻找合适的chunk,找不到或者大于512B就进行下一步。

(5)遍历fast bins中所有的chunk,合并相邻节点,将其移动到unsorted bin。遍历unsorted bin,如果unsorted bin只有一个chunk,并且大于所需空间,就进行切割,剩余的chunk扔回unsorted bin。如果正好有和需求空间大小相同的chunk,直接返回该chunk并从unsorted bin返回。遍历unsorted bin时,将途中chunk放入合适的small bins或者large bins中。如果未分配成功,转入下一步。

(6)在large bins中寻找合适的节点进行切割,剩余空间组成新的chunk放到unsorted bin中。

(7)从top chunk切割空间,如果top chunk也不能满足要求,进行下一步。

(8)如果需要的空间大于mmap阈值(大于128k),直接使用mmap映射一段内存交给用户。否则的话,对top chunk进行扩容,如果是第一次分配,就要分配一块128K+chunk size大小的空间当成分配区,如果不是第一次分配,使用brk()或者mmap()扩容top chunk,切割出一个chunk返回给用户。

小内存: 获取分配区(arena)并加锁 -> fast bins -> small bins -> 合并fast bins加入unsorted bins -> unsorted bins合并,加入small bins或者large bins -> small bins -> large bins -> top chunk(低于mmap阈值) -> mmap(高于mmap 阈值)

大内存:直接mmap


个快快 2019年03月05日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号