内存管理器（六）Glibc malloc 实现（二）--设计模式

女爷i 2022-08-09 11:51 235阅读 0赞

## 前言 ##

上一篇只是简单的介绍了下，关于各个版本的malloc 实现的概况，本来时很详细的，但是写了大半的时候，浏览器崩溃了，很多东西都不见了，所以只有现在的一点了。这次主要介绍ptmalloc ( ) 是如何设计的。

## 分配区数据结构 ##

这个库函数将内存分成一个主分配区和多个非主分配区。其中，一个进程只有一个主分配区，可以有多个非主分配区，这里多个非主分配区的出现，更多的是因为支持多线程的需要，当线程数增大的时候，如果只有一个主分配区肯定会发生等待，影响效率等。但是多线程的处理方式并不是今天处理的重点。
        图示如下：

![这里写图][20151021190758557]

使用主分配区，必须对分配区的内存加锁，然后释放锁，但是为了支持SMP多线程的模式，后来有增加了非主分配区，以保证能减少因为多线程同时争夺同一个锁产生的资源浪费。但是只有主分配区可以访问进程的heap区域和mmap 区域，非主分配区每次只能通过mmap()从内存中“批发“一部分的内存。
        主分配区和非主分配区通过一个环型链表来链接，就像我们上面看到的哪有那个。至于大小，是由一个宏HEAP_MAX_SIZE 来决定的，32位系统是1MB，64位默认是64MB。
        每个线程的默认分配区默认是主分配区，但是会随着调整，逐渐变成非主分配区。

## chunk组织 ##

### 是什么 ###

首先，不管内存分配来自哪里，ptmalloc( )都会使用一个一个chunk来分配它的大小，这些chunk组织都是大小不同的块。根据需求最佳匹配。值得注意的一点是，我们调用free( ) 函数后这段内存步会立即返回给操作系统，是会被库函数暂时组织在一起，当达到释放条件的时候才会归还给操作系统，这也为“内存暴增“问题留下了隐患，但是相对的，如果多次的向操作系统返还内存势必要频繁调用brk(),unmmap()函数，这些调用的使用显然不是免费的，所以我们只能折中。当然库函数的malloc()就是一种折中的方案，所以在不同的场合会发生让人各种措手不及的问题。

### chunk的数据结构 ###

![chunks][]

这就是chunk 的数据结构，是不是很眼熟？其实很类似我们之前的边界标识法的结构，本质上这里使用的就是这种方法。  
第一个部分：上一个块的大小。  
第二个部分：这个块的大小，以及不同状态的标识。  
1.A 1:主分配区 0：非主分配区  
2.M 1：从mmap( )中非配的空间，0：从heap中分配的空间。  
3.p 1:被占用 , 0:未被占用  
第三个部分：这个块的大小，就是下一个块的开始。

但是这是只是一个被占用的块的结构，当一个块为空时，数据结构时会发生变化的。当一个块空闲时，它被放在bin 这个链表中，我们会在它的空闲区域增加俩个指针，来标记它，以至于在分配的时候提速。

![a][]

这是一个空闲的块，这个时候一般把M位置空。因为这个时候它时没有意义的，指针 fd 指向后一个空闲的chunk ，而bk 指向前一个空闲的chunk,ptmalloc 通过使用这两个指针将空闲的内存块设置成一个双向链表，至于后两个指针，我们之前说过，bin 有几种不同的类型，后两个指针是在large bins 中来为加快查找速度的。都是指向前与后的指针。

### 空间复用 ###

这里主要就是根据每一个块的空闲状态，与使用状态来调整其中的指针有无，同样的空间大小却增加了效率，这个就是空间复用。

### chunk 容器 ###

之前，我们说了bin 有不同的类型的bin , 一图胜千言，先上图来看看。

![chunk\_bin][chunk_bin]

![fast bins][]

如上边所介绍的那样，用户free( )的内存不会立即归还给操作系统，ptmalloc ( )会统一管理heap 和 mmap 映射的空间，这些被释放的块暂时就在这个bin 集合中。
            这里还有一个fast bins .这个部分是用来处理分配的较小的内存空间的，MAX_FAST 默认大小是64B大小。当用户需要较小的空间的时候我们就可以宗这里率先分配提高效率。当我们需要找到一个空闲的chunk 的时候。首先找到这里，当然如果是很大的需求，有其他的处理方式，如果没有找到，就将这里的空闲块合并后直接放入unsorted bin .接着我们看下一步。
        现在我们来看看bins .首先看看unsorted bin 部分，上边说了，首先如果识放一些大与64B或者在fast bin中没有找到合适的东西的时候，就在这里查找有没有合适的chunk ，如果还是没有，就将这里的空闲chunk 加入到后边的small bin 和 large bin 中，然后再进行查找。由此看来unsorted bin 可以看成是bin 的一个缓冲区，增加它只是为了加快分配的速度。
        现在说说small bins 和 large bins ，这里一共有126个index ,small bins 是根据公差为8的大小排列的，而后边的是根据index *32 为差值排列的。用来适用存放与分配不同大小块的需求。
    
        还有一个binmap[index]每个分配区还存在这样一个数组，这里使用了位图的原理来辅助提升分配的速度。
    
    下面介绍三种不同的chunk ，这三种chunk 是很特殊的，他们和bin 没有多大的关系，更重要的是提供我们所缺少的分配分离制度，在确定分配大小后，根据大小即刻做出相应的大小处理方式。
    1.Top chunk 
        对于非主分配区，首先使用mmap() 函数来映射一个较大的区域，当在bin 中无法找到一个块时就会直接移动非主分配区的top chunk 来从heap中分配一大块空间。
    2.mmaped chunk
        当需要的空间大到mmap()都不能满足的时候，我们就会使用mmap()函数者直接映射一片内存给需求空间。
    3.last remainder
        这是一种特殊的chunk ,就像top chunk 和 mmaped chunk 一样，当需要分配一个small bin 的时候但是又找不到一个合适的chunk 的时候就会来分割这个块。

### 总结一下响应分配时的具体步骤 ###

1.获取分配区的锁。  
    
    2.根据用户的需要申请的大小算出给与的大小。
    
    3.判断所需要的大小 <= max_fast,是就跳转第5步，否则下一步
    
    4.首先在fast bin 找，找不到就下一步，否则下一步
    
    5.size <= 512B ,判断是否在small bin 中，如果在就下一步，否则就第6步
    
    6.找到一个合适的chunk 大小，否则就下一步
    
    7.到了这一步，可以看到这是一个很大size了，先遍历fast bins 合并空闲块到unsorted bin 再次合并这个块里的大小，再次比对大小信息，如果可以分配就切割大小并且将剩下的部分加入到small bin 或者 large bin 中。如果依然 < SIZE 调转下一步。
    
    8.此时我们就表示我们从fast small unsorted 都找不到合适的块的大小，所以我们就到large bin 中寻找合适的大小。如果没有找到，就调转下一步了。
    
    9.走到这里基本上就是说这个块非常打了，所以我们就动用TOP chunk 改变堆的大小了，如果依然不能满足需求。调转下一步。
    
    10.这时候判断SIZE 和 mmap（）分配阀值的大小。如果大于分配阀值就使用这个函数分配，否则调用sbrk()扩大堆的大小。

### 回收时的策略 ###

1.获取线程锁（永远要保证线程安全）

2.判断是否为mmap()分配，如果是就使用unmmap()函数来直接解除映射

3.将chunk 放入fast bin 中。

4.判断TOP chunk 周围是否为空，如果是就将top chunk 和 其他的合并，然后判断是否大于mmap()的分配阀值，如果大于就调用mmap()释放之。

以上，就是ptmalloc 的基本设计模式，下一篇将对多线程进行详细的整理总结。

[20151021190758557]: /images/20220731/b9573523aca04cb6b1b08da90a0cb85d.png
[chunks]: /images/20220731/3c0d6d5376cf4efc8ca571486d88f763.png
[a]: /images/20220731/5dce587aec9147688ed2500ce6fd7c8d.png
[chunk_bin]: /images/20220731/c945d5bd813e4a00ac76061f795b0bfc.png
[fast bins]: /images/20220731/f8d523891d404a78a5d6c15a4032e36e.png