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

前言

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

分配区数据结构

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

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

chunk组织

是什么

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

chunk的数据结构

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

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

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

空间复用

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

chunk 容器

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

        如上边所介绍的那样，用户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 的基本设计模式，下一篇将对多线程进行详细的整理总结。

版权声明：本文为博主原创文章，未经博主允许不得转载。