参考Google的TCMalloc内存池实现并发内存池ConcurrentMemoryPool

男娘i 2022-03-18 06:16 505阅读 0赞

## 项目背景 ##

> TCMalloc 是 Google 开发的内存分配器，在不少项目中都有使用，例如在 Golang 中就使用了类似的算法进行内存分配。它具有现代化内存分配器的基本特征：对抗内存碎片、在多核处理器能够 scale。之所以学习 TCMalloc，是因为想对内存管理进行深入理解。

## 解决问题 ##

1.  提高效率
2.  并发处理
3.  内存碎片（内碎片、外碎片）

## 三大块 ##

**thread cache**：一个线程对应一个内存池，需要内存时去 central cache里取资源，如果空间被释放回到thread cache，当thread cache上挂有过多的内存对象是还回给central cache，可均衡资源。此过程不需要加锁！  
**central cache**：用于中间均衡资源，thread cache可向central cache申请资源，central cache若没有则向page cache申请，当thread cache的内存对象过多会将内存还回给central cache，central cache内存过多也会还回给page cache，具体设计之后详解。此过程须加锁！----->解决了锁竞争问题  
**page cache**：合并内存，解决内存碎片问题。若central cache申请空间时，page cache没有空间给他，则page cache会向系统申请空间，这里我们直接调用接口申请系统堆上的空间。此过程需加锁！

![总体框架图][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2hlYmVkNjY2_size_16_color_FFFFFF_t_70]

### thread cache：并发 ###

![ThreadCache][]

#### 如何分配定长 ####

如何分配定长记录？例如，我们有一个 Page 的内存，大小为 4KB，现在要以 N 字节为单位进行分配。为了简化问题，就以 16 字节为单位进行分配。解法有很多，比如，bitmap。4KB / 16 / 8 = 32, 用 32 字节做 bitmap即可，实现也相当简单。  
出于最大化内存利用率的目的，我们使用另一种经典的方式，freelist。将 4KB 的内存划分为 16 字节的单元，每个单元的前8个字节作为节点指针，指向下一个单元。初始化的时候把所有指针指向下一个单元；分配时，从链表头分配一个对象出去；释放时，插入到链表。由于链表指针直接分配在待分配内存中，因此不需要额外的内存开销，而且分配速度也是相当快。

> 注意问题一：在物理上讲，内存的空间分配一直都没有改变，当我们要使用时类似于改变他的使用权，归还时也一样，内存的物理空间地址都没有改变，所以当我们将其划分成一个一个的小块儿并用链表将其挂链，仅仅只是改变一下指针方向，物理上内存的位置并没有改变！

#### 如何分配变长 ####

定长记录的问题很简单，但如何分配变长记录的。对此，我们把问题化归成对多种定长记录的分配问题。我们把所有的变长记录进行“取整”，例如分配7字节，就分配8字节，31字节分配32字节，得到多种规格的定长记录。这里带来了内部内存碎片的问题，即分配出去的空间不会被完全利用，有一定浪费。为了减少内部碎片，我们将内碎片浪费控制在12%左右。如下：

<table> 
 <thead> 
  <tr> 
   <th>[1,128]</th> 
   <th>8 byte对齐</th> 
   <th>freelist[0,16)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>[129,1024]</td> 
   <td>16byte对齐</td> 
   <td>freelist[16,72)</td> 
  </tr> 
  <tr> 
   <td>[1025,8*1024]</td> 
   <td>128byte对齐</td> 
   <td>freelist[72,128)</td> 
  </tr> 
  <tr> 
   <td>[8<em>1024+1,64</em>1024]</td> 
   <td>512byte对齐</td> 
   <td>freelist[128,240)</td> 
  </tr> 
 </tbody> 
</table>

#### 中心线程如何创建多个线程？保证每个线程都有一个ThreadCache？ ####

方式一：ThreadCache\* list：将每个线程连起来，须加锁  
方式二：tls：线程本地存储，相当于每个线程独有的全局变量。每个线程的tls变量相互不影响。起到线程安全作用。

> 例如：static \_declspec(thread) ThreadCache\* tls\_threadcache = nullptr;

### central cache:均衡资源、内存碎片、span处理 ###

![ThreadCache取对象空间][ThreadCache 1]  
SpanList是一个带头双向链表，每一个span是一个节点，span和span挂链，span里挂对象。去span里取空间，先找一个非空span，然后取这个span里的对象，所取大小看实际返回值。为了方便thread cache取还空间，我们把central cache的变长分配和thread cache保持一致，如上图。  
那么ThreadCache如何还对象空间呢？如下图：我们通过对象空间与span的映射，找到对应的span，然后将对象空间头插进入span链表里，即改变指针指向。  
![ThreadCache还对象空间][ThreadCache 2]

### page cache：内存碎片 ###

#### Span如何分配？ ####

对于 Span的管理，我们可以如法炮制：  
还是用多种定长Page来实现变长Page的分配，初始时只有128Page的Span，如果要分配1个Page的Span，就把这个Span分裂成两个，1 + 127，把127再记录下来。对于 Span 的回收，需要考虑Span的合并问题，否则在分配回收多次之后，就只剩下很小的 Span 了，也就是带来了外部碎片问题。为此，释放 Span 时，需要将前后的空闲 Span 进行合并，当然，前提是它们的 Page 要连续。  
那么问题来了，如何知道前后的 Span 在哪里？  
最简单的一种方式，用一个数组记录每个Page所属的 Span，而数组索引就是 Page ID。这种方式虽然简洁明了，但是在 Page 比较少的时候会有很大的空间浪费。为此，我们可以使用 map/unorder\_map这种数据结构，用较少的空间开销，和不错的速度来完成这件事。

### 细节问题处理： ###

把空间申请分成三大块：

1.  **0~64KB**：若要申请这个范围区间的空间大小，我们设计的方法是先去ThreadCache里在对应对象大小的链表中取空间，当申请空间不足时，去CentralCache里找对应对象大小的span里找空间，若任然不够，则去PageCache里取span，当span里有足够的空间，则我们使用慢增长的方式获取空间数目，提高效率。若PageCache里也没有对应空间大小的span，则我们才去系统里申请128页来切割使用。显然，这个范围的空间申请较为频繁。
2.  **64KB~128页**：若我们需要一次性申请这个范围的空间，那么我们需要跳过CentralCache直接去PageCache里申请对应大小的span，若 PageCache里没有足够的空间，那么我们才去系统申请128页的空间来使用。
3.  **128页以上**：若我们需要一次性申请这个范围的空间，这个范围的空间较大，申请参数较为少，而PageCache里也没有对应的span，所以我们直接去系统申请空间来使用。

### 遇到的问题： ###

1.  **多线程并发问题**：考虑了在CentralCache里空间申请及释放操作频繁，在多线程同时进入时，基于效率的考虑，我们设计了桶锁，即每一条SpanList都挂有一个锁，多线程在不同的块儿中申请空间时将不会互相影响；而在PageCache里申请空间时，首先，操作不会太频繁，同时，所设计的结构与CentralCache并不一样，所以我们只用了一把锁将这个pagelist控制起来。这样效率以及并发问题将大大提高。
2.  **空间的地址与对应span的映射问题**：为了方便查找以及空间的释放，我们必需将空间和对应的span映射起来，我们选择了unorder\_map，她的效率要高于map，同时我们的空间也不需要排序，所以用unorder\_map正好。（同时注意，unorder\_map/map的映射仅仅只是改变指针方向，并不会发生深拷贝）

### 存在的不足： ###

1.  **项目的独立性不足**  
    当前实现的项目中我们并没有完全脱离malloc，比如在内存池自身数据结构的管理中，如SpanList中的span等结构，我们还是使用的new Span这样的操作，new的底层使用的是malloc，所以还不足以替换malloc，因为们本身没有完全脱离它。  
    **解决方案**：项目中增加一个定长的ObjectPool的对象池，对象池的内存直接使用brk、VirarulAlloc等向系统申请，new Span替换成对象池申请内存。这样就完全脱离的malloc，就可以替换掉malloc。
2.  **平台及兼容性**

*  linux等系统下面，需要将VirtualAlloc替换为brk等。这个是小问题 。
 *  x64系统下面，当前的实现支持不足。比如：id查找Span得到的映射，我们当前使用的是unorder\_map<id,Span\*>。在64位系统下面，这个数据结构在性能和内存等方面都是撑不住。需要改进后基数树。  
    **具体参考**：基数树(radix tree)

至此，ConcurrentMemoryPool项目的大体结构便呈现在我们眼前了。

> 代码已提交至：[https://github.com/JochebedJX/ConcurrentMemoryPool][https_github.com_JochebedJX_ConcurrentMemoryPool]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0pvY2hlYmVkNjY2_size_16_color_FFFFFF_t_70]: /images/20220318/8265b0a0077f4ef4b7832fa2ea382eef.png
[ThreadCache]: /images/20220318/c1a437be6ee243279a4e71f56189f8a3.png
[ThreadCache 1]: /images/20220318/befcb0eb905148988a85f3e935b88e37.png
[ThreadCache 2]: /images/20220318/bc98d5648df34bae9164449c13c13c4b.png
[https_github.com_JochebedJX_ConcurrentMemoryPool]: https://github.com/JochebedJX/ConcurrentMemoryPool