欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

linux堆内存管理malloc分析(3)

程序员文章站 2022-05-12 08:47:26
...

Unsorted bin

当释放较小或较大的chunk的时候,如果系统没有将它们添加对应的bins中,系统就将这些chunk添加到unsorted bin中。为什么要这么做呢?这主要是为了让glibc malloc机制能够有第二次机会重新利用最近释放的chunk(第一次就是fast bins机制)。利用unsorted bin,可以加快内存的分配和释放操作,因为整个操作都不需要花费额外的时间去查找合适的bin了。

unsorted bin的特性如下:

1)unsorted bin的个数:1个。unsorted bin是一个由free chunks组成的循环双链表。

2)Chunk size:在unsorted bin中,对chunk的大小并没有限制,任何大小的chunk都可以归属于unsorted bin中。这就是前言所说的特例了,不过特例并非仅仅一个,后文会介绍。

Small bin

小于512字节的chunk称之为small chunk,small bin就是用于管理small chunk的。就内存的分配和释放速度而言,small bin比larger bin快,但比fast bin慢。

small bin的特性如下:

1)small bin个数:62个。每个small bin是一个由对应free chunk组成的循环双链表。同时small bin采用FIFO算法,内存释放操作就将新释放的chunk添加到链表的front end(前端),分配操作从链表的rear end(尾端)中获取chunk。

2)chunk size:同一个small bin中所有chunk大小是一样的,且第一个small bin中的chunk大小为16字节,后续每个small bin中的chunk大小以此增加8字节,即最后一个small bin的chunk为16+62*8=512字节。

3)合并操作:相邻的free chunk需要进行合并操作,即合并成一个大的free chunk。具体操作见下文free(small chunk)介绍。

4)malloc(small chunk)操作:类似于fast bins,最初所有的small bin进行处理,而是交由unsorted bin处理,如果unsorted bin也处理不了,glibc malloc就以此遍历后续的所有bins,找出第一个满足要求的bin,如果所有的bin都不能满足的话,就转而是用top chunk,如果top chunk大小不够,那么就扩容top chunk,这样就一定满足需求。注意遍历后续bins以及之后的操作同样被large bin所使用,因此,将这部分内容放到large bin的malloc操作中加以介绍。

那么gblic malloc如何初始化这些bins的呢?因为这些bin属于malloc_state结构体,所以在初始化malloc_state的时候就会对这些bin进行初始化,代码如下:

malloc_init_state (mstate av)
{
  int i;
  mbinptr bin;
 
  /* Establish circular links for normal bins */
  for (i = 1; i < NBINS; ++i)
    {
      bin = bin_at (av, i);
      bin->fd = bin->bk = bin;
}
……
}

注意在malloc源码中,将bins数组中的第一个成员索引设置为了1,而不是我们常用的0。从上面代码可以看出在初始化的时候glibc malloc将所有bin的指针都指向了自己,这就代表了这些bin都是空的。

过后,当再次调用malloc(small chunk)的时候,如果该chunk size对应的small bin不为空,就从该small bin链表中取得small chunk,否则就需要交给unsorted bin及之后的逻辑来处理了。

5)free(small chunk):当释放small chunk的时候,先检查该chunk相邻的chunk是否为free,如果是的话就进行合并操作,将这这些chunks合并成新的chunk,然后将他们从small bin中移除,最后将新的chunk添加到unsorted bin中。

Large bin

大于512字节的chunk称之为large chunk,large bin就是用于管理这些large chunk的。

Large bin的特性如下:

1)large bin的数量:63个。Large bin类似于small bin,只是需要注意两点:一是同一个large bin中每个chunk的大小可以不一样,但必须处于某个给定的范围;二是large chunk可以添加,删除在large bin的任何一个位置。

在这63个large bins中,前32个large bin以此以64字节步长为间隔,即第一个large bin中的chunk size为512-575字节,第二个large bin中的chunk size为576-639字节。紧随着其后的16个large bin以此以512字节步长为间隔;之后的8个bin以步长4096字节为间隔;再之后的4个bin以32768字节为间隔;之后的2个bin以262144字节为间隔;剩余的chunk就放到最后一个large bin中。

鉴于同一个large bin中每个chunk的大小不一定相同,因此为了加快内存分配和释放的速度,就将同一个large bin中的所有chunk按照chunk size进行从大到小的排列;最大的chunk放到链表的front end,最小的chunk放到rear end。

2)合并操作:类似于small bin。

3)malloc(large chunk)操作:

初始化完成之前的操作类似于small bin,这里主要讨论large bins初始化完成之后的操作。首先确定用户请求的大小数据哪一个large bin,然后判断该large bin中最大的chunk的size是否大于用户请求的chunk(只需要对比链表中front end的size即可)。如果大于,就从rear end开始遍历该large bin,找到第一个size相等或接近的chunk,分配给用户。如果该chunk大于用户请求的size的话,就从rear end开始遍历该large bin,找到第一个size相等或接近的chunk,分配给用户。如果该chunk大于用户请求的size的话,就将chunk拆除为两个chunk;前者返回给用户,且size等同于用户请求的size;剩余的部分作为一个新的chunk添加到unsorted 中。

如果该large bin中最大的chunk的size小于用户请求的size的话,那么就依次查看后续的large bin是否满足需求的chunk,不过需要注意的是鉴于bin的个数较多(不同bin中的chunk极有可能在不同的内存页中),如果按照上一段中介绍的方法进行遍历的话,就可以发生多次内存页中断操作,进而严重影响检索速度,所以glibc malloc设计了bin map结构来帮助提高bin-by-bin检索速度。bin map记录了各个bin中是否为空,通过bitmap可以避免检索一些空的bin。如果通过bin map找到了下一个非空的large bin的话,就可能只能够上一段方法分配chunk,否则就是用top chunk来分配内存。

4)free(large chunk):类似于small chunk。

linux堆内存管理malloc分析(3)

相关标签: malloc 内存管理