SGI STL 的内存管理

1. 前言

在分析完 nginx 的内存池之后,也想了解一下 C++ 的内存管理,于是就很自然得想到 STL。STL 是一个重量级的作品,据说当时的出现,完全可以说得上是一个划时代意义的作品。泛型、数据结构和算法的分离、底耦合、高复用… 啊,废话不多说了,再说下去让人感觉像王婆卖瓜了。

啊,还忘了得加上两位 STL 大师的名字来聊表我的敬意了。泛型大牛 Alexander  Stepanov 和 Meng Lee(李梦 — 让人浮想的名字啊)。

2. SLT 内存的分配

以一个简单的例子开始。

我们想知道的时候, 当 vec 声明的时候和 push_back 的时候,是怎么分配的。

其实对于一个标准的 STL 容器,当 Vetor<int> vec 的真实语句应该是 vetor<int, allocator<int>>vec,allocator 是一个标准的配置器,其作用就是为各个容器管理内存。这里需要注意的是在 SGI STL 中,有两个配置器:allocator(标准的) 和 alloc(自己实现的,非常经典,这篇文章的主要目的就是为了分析它)。

3. 一个标准的配置器

要写一个配置器并不是很难,最重要的问题是如何分配和回收内存。下面看下一个标准(也许只能称为典型)的配置器的实现:

注:代码有比较大的改动,因为主要是为了理解。

在使用的时候, 只需这样 vector<int, SLD::allocator<int>>vec; 即可。vetor 便会自动调用我们的配置器分配内存了。要自己写个配置器完全可以以这个类为模板。 而需要做的工作便是写下自己的 allocate 和 deallocate 即可。

其实 SGI 的 allocator 就是这样直接调用 operator new 和::operator delete 实现的,不过这样做的话效率就很差了。

4. SGI STL 中的 alloc

4.1 SGI 中的内存管理

SGI STL 默认的适配器是 alloc,所以我们在声明一个 vector 的时候实际上是这样的 vetor<int, alloc<int>>vec. 这个配置器写得非常经典,下面就来慢慢分析它。

在我们敲下如下代码:

CSld* sld = new CSld;的时候其实干了两件事情:

  1. 调用::operator new 申请一块内存(就是 malloc 了)
  2. 调用了 CSld::CSld();

而在 SGI 中, 其内存分配把这两步独立出了两个函数:allocate 申请内存, construct 调用构造函数。他们分别在 <stl_alloc.h>, <stl_construct.h> 中。

SGI 的内存管理比上面所说的更复杂一些, 首先看一些 SGI 内存管理的几个主要文件,如下图所示:

SGI Memory_thumb

<图 1. SGI  内存管理>

在 stl_construct.h 中定义了两个全局函数 construct() 和 destroy() 来管理构造和析构。在 stl_allo.h 中定义了 5 个配置器, 我们现在关心的是 malloc_alloc_template(一级)和 default_alloc_template(二级)。

在 SGI 中,如果用了一级配置器,便是直接使用了malloc() 和 free() 函数,而如果使用了二级适配器,则如果所申请的内存区域大于 128b,直接使用一级适配器,否则,使用二级适配器。而 stl_uninitialized.h 中,则定义了一下全局函数来进行大块内存的申请和复制。

是不是和 nginx 中的内存池很相似啊,不过复杂多了。

4.2 一级配置器:__malloc_alloc_template

上面说过, SGI STL 中, 如果申请的内存区域大于 128B 的时候,就会调用一级适配器,而一级适配器的调用也是非常简单的, 直接用 malloc 申请内存,用 free 释放内存。

可也看下如下的代码:

好了, 很简单把,只是对 malloc,free, realloc 简单的封装。

4.3 二级配置器:__default_alloc_template

按上文所说的,SGI 的 __default_alloc_template 就是一个内存池了。

我们首先来看一下它的代码:

我们最关心的有三点:1. 内存池的创建。2. 内存的分配。 3. 内存的释放。

4.3.1 SGI 内存池的结构

在分析内存池的创建之前我们首先需要看下 SGI 内存池的结构。

在__default_alloc_template 内部,维护着这样一个结构体:

其实一个 free_list 就是一个链表,如下图所示:

link_thumb

<图 2. free_list 的链表表示>

 

这里需要注意的有两点:

一:SGI 内部其实维护着 16 个 free-list,对应管理的大小为 8,16,32……128.

二:_Obj 是一个 union 而不是 sturct, 我们知道,union 中的所有成员的引用在内存中的位置都是相同的。这里我们用 union 就可以把每一个节点需要的额外的指针的负担消除掉。

4.3.2 二级配置器的内存分配:allocate

比如现在我要申请一块 30B 的空间,我要怎么申请呢?

首先会呼叫二级配置器, 调用 allocate,在 allocate 函数之内, 从对应的 32B 的链表中拿出空间。

如果对应的链表空间不足,就会先用填充至 32B,然后用 refill() 冲洗填充该链表。

相应的代码如下:

下面画了一张图来帮助理解:

GetMemory_thumb

<图 3. GetMemory>

4.3.3 二级配置器的内存释放:allocate

有内存的分配,当然得要释放了,下面就来看看是如何释放的:

4.3.4 二级配置器的内存池:chunk_alloc

前面说过,在分配内存时候如果空间不足会调用_S_refill 函数,重新填充空间(ps: 如果这是第一个的话,就是创建了)。而_S_refill 最终调用的又是 chunk_alloc 函数从内存池中提取内存空间。

首先我们看一下它的源代码:

区间 [_S_start_free, _S_end_free) 便是内存池的总空间(参考类:__default_alloc_template 的定义)。

当申请一块内存时候,如果内存池总内存量充足,直接分配,不然就各有各的处理方法了。

下面举一个例子来简单得说明一下:

  1. 当第一次调用 chunk_alloc(32,10) 的时候,表示我要申请 10 块__Obje(free_list), 每块大小 32B,此时,内存池大小为 0,从堆空间申请 32*20 的大小的内存,把其中 32*10 大小的分给 free_list[3](参考图 3)。
  2. 我再次申请 64*5 大小的空间,此时 free_list[7] 为 0, 它要从内存池提取内存,而此时内存池剩下 320B,刚好填充给 free_list[7],内存池此时大小为 0。
  3. 我第三次神奇一耳光 72*10 大小的空间,此时 free_list[8] 为 0,它要从内存池提取内存,此时内存池空间不足,再次从堆空间申请 72*20 大小的空间,分 72*10 给 free_list 用。

整一个 SGI 内存分配的大体流程就是这样了。

5. 小结

SIG 的内存池比 nginx 中的复杂多了。简单得分析一下 + 写这篇文章花了我整整 3 个晚上的时间。

啊,我的青春啊。

1 5 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部