2209人阅读
C/C++（72）
SGI设计了双层级配置器，第一级配置器直接使用malloc()和free()，第二级配置器则视情况采用不同的策略：当配置区块超过128bytes时，视之为“足够大”，便调用第一级配置器；当配置区小于128bytes时，视之为“过小”，为了降低额外负担，便采用复杂的memory pool 整理方式，而不再求助于第一级配置器。整个设计究竟只开放第一级配置器，取决于_USE_MALLOC是否被定义：
__USE_MALLOC
3 typedef __malloc_alloc_template&0& malloc_
4 typedef malloc_ //令alloc为第一级配置器
6 //令alloc为第二级配置器
7 typedef __default_alloc_template&__NODE_ALLOCATOR_THREADS,0&
8 #endif /*! __USE_MALLOC*/
SGI STL&第一级配置器
template&int inst&
class& __malloc_alloc_template {…} ;
1.allocate()直接使用malloc()，deallocate()直接使用free()。
2.模拟C++的set_new_handler()以处理内存不足的状况。第一级配置器以malloc()，free()，realloc()等C函数执行实际的内存配置、释放、重配置操作。
SGI STL&第二级配置器
template&bool threads,int inst&
class __default_alloc_template {…} ;
1.维护16个自由链表(free lists)，负责16种小型区块的次配置能力。内存池(memory pool)以malloc()配置而得。如果内存不足，转调用第一级配置器。
2.如果需求区块大于128byte，就转调用第一级配置器。
下面是一些具体的理解分享：
default allocator
SGI STL 的头文件defalloc.h中有一个符合标准的名为allocator的内存分配器，它只是简单地将::operator new 和::operator delete做了一层薄薄的封装。在SGI STL的容器和算法部分从来没有用到这个内存分配器。
STL&的内存分配策略
首先简要介绍一下STL中对内存分配的规划
& &&当用户用new构造一个对象的时候，其实内含两种操作：1）调用::operator new申请内存；2）调用该对象的构造函数构造此对象的内容
&&& 当用户用delete销毁一个对象时，其实内含两种操作：1）调用该对象的析构函数析构该对象的内容；2）调用::operator delete释放内存
SGI STL中对象的构造和析构由::construct()和::destroy()负责；内存的申请和释放由alloc:allocate()和alloc:deallocate()负责；此外，SGI STL还提供了一些全局函数，用来对大块内存数据进行操作。
上一段提到的三大模块分别由stl_construct.h,&stl_alloc.h,&stl_uninitialized.h&负责
对象的构造和析构工具(stl_construct.h)
stl_construct.h中提供了两种对象的构造方法，默认构造和赋值构造：
1 template &class _T1, class _T2&
2 inline void _Construct(_T1* __p, const _T2& __value) {
new ((void*) __p) _T1(__value);
6 template &class _T1&
7 inline void _Construct(_T1* __p) {
new ((void*) __p) _T1();
上面两个函数的作用是构造一个类型为T1的对象，并由作为参数的指针p返回。
其中的new (_p) _T1(_value); 中使用了placement new算子，它的作用是通过拷贝的方式在内存地址_p处构造一个_T1对象。（placement new能实现在指定的内存地址上用指定类型的构造函数来构造一个对象）。
在对象的销毁方面，stl_construct.h也提供了两种析构方法：
1 template &class _Tp&
2 inline void _Destroy(_Tp* __pointer) {
__pointer-&~_Tp();
6 template &class _ForwardIterator&
7 inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
__destroy(__first, __last, __VALUE_TYPE(__first));
第一个版本的析构函数接受一个指针，将该指针所指的对象析构掉；第二个版本的析构函数接受first和last两个迭代器，将这两个迭代器范围内的对象析构掉。
在第二个版本的destroy函数里面，运用了STL中惯用的traits技法，traits会得到当前对象的一些特性，再根据特性的不同分别对不同特性的对象调用相应的方法。在stl_construct.h中的destroy中，STL会分析迭代器所指对象的has_trivial_destructor特性的类型（只有两种：true_type和false_type），如果是true_type，STL就什么都不做；如果是false_type，就会调用每个对象的析构函数来销毁这组对象。
除此之外，stl_construct还为一些基本类型的对象提供了特化版本的destroy函数，这些基本类型分别是char, int, float, double, long。当destroy的参数为这些基本类型时，destroy什么都不做。
内存空间管理工具alloc
我想以自底向下的顺序介绍一下STL的allocator。首先说说STL内建的两种分配器，然后介绍STL如何封装这两种分配器对外提供统一的接口，最后用一个vector的例子看看容器如何使用这个allocator。
1 __malloc_alloc_template内存分配器
该分配器是对malloc、realloc以及free的封装：
1 static void* allocate(size_t __n)
void* __result = malloc(__n);
if (0 == __result) __result = _S_oom_malloc(__n);
static void deallocate(void* __p, size_t /* __n */)
free(__p);
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
void* __result = realloc(__p, __new_sz);
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
当调用malloc和realloc申请不到内存空间的时候，会改调用oom_malloc()和oom_realloc()，这两个函数会反复调用用户传递过来的out of memory handler处理函数，直到能用malloc或者realloc申请到内存为止。如果用户没有传递__malloc_alloc_oom_handler，__malloc_alloc_template会抛出__THROW_BAD_ALLOC异常。所以，内存不足的处理任务就交给类客户去完成。
2 __default_alloc_template分配器
这个分配器采用了内存池的思想，有效地避免了内碎片的问题（顺便一句话介绍一下内碎片和外碎片：内碎片是已被分配出去但是用不到的内存空间，外碎片是由于大小太小而无法分配出去的空闲块）。如果申请的内存块大于128bytes，就将申请的操作移交__malloc_alloc_template分配器去处理；如果申请的区块大小小于128bytes时，就从本分配器维护的内存池中分配内存。分配器用空闲链表的方式维护内存池中的空闲空间，空闲链表大概类似于下面的形状：
如上图所示，s_free_list是这些空闲分区链的起始地址组成的数组，大小为16。这16个链表中每个链表中的空闲空间的大小都是固定的，第一个链表的空闲块大小是8bytes, 依次是16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128bytes。
　　另外还有三个指针s_start_free, s_end_free, s_heap_size。它们分别指向整个内存池的起始地址，结束地址和可用空间大小。
分配内存过程：
　　1）如果申请的内存空间大于128bytes, 则交由第一个分配器处理
　　2）分配器首先将申请内存的大小上调至8的倍数n，并根据n找出其对应的空闲链表地址__my_free_list
　　3）如果该空闲链表中有可用的空闲块，则将此空闲块返回并更新__my_free_list，否则转到4）
　　4）到这一步，说明__my_free_list中没有空闲块可用了，分配器会按照下面的步骤处理：
　　a) 试着调用_s_chunk_alloc()申请大小为n*20的内存空间，注意的是，此时不一定能申请到n*20大小的内存空间
b) 如果只申请到大小为n的内存空间，则返回给用户，否则到c)
&&& c) 将申请到的n*x(a中说了，不一定是n*20)内存块取出一个返回给用户，其余的内存块链到空闲链表__my_free_list中
_s_chunk_alloc()的具体过程为：
&&& 1)如果_s_start_free和_s_end_free之间的空间足够分配n*20大小的内存空间，则从这个空间中取出n*20大小的内存空间，更新_s_start_free并返回申请到的内存空间的起始地址，否则转到2)
&&& 2) 如果_s_start_free和_s_end_free之间的空间足够分配大于n的内存空间，则分配整数倍于n的内存空间，更新_s_start_free，由nobj返回这个整数，并返回申请到的内存空间的起始地址；否则转到3）
　　3) 到这一步，说明内存池中连一块大小为n的内存都没有了，此时如果内存池中还有一些内存（这些内存大小肯定小于n），则将这些内存插入到其对应大小的空闲分区链中
　　4) 调用malloc向运行时库申请大小为（2*n*20 + 附加量）的内存空间， 如果申请成功，更新_s_start_free, _s_end_free和_s_heap_size，并重新调用_s_chunk_alloc()，否则转到5)
&　 5) 到这一步，说明4)中调用malloc失败，这时分配器依次遍历16个空闲分区链，只要有一个空闲链，就释放该链中的一个节点，重新调用_s_chunk_alloc()
内存释放过程：
内存的释放过程比较简单，它接受两个参数，一个是指向要释放的内存块的指针p，另外一个表示要释放的内存块的大小n。分配器首先判断n，如果n&128bytes，则交由第一个分配器去处理；否则将该内存块加到相应的空闲链表中。
SGI STL 为了方便用户访问，为上面提到的两种分配器包装了一个接口（对外提供的分配器接口），该接口如下：
1 template&class _Tp, class _Alloc&
2 class simple_alloc {
static _Tp* allocate(size_t __n)
{ return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
static _Tp* allocate(void)
{ return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
static void deallocate(_Tp* __p, size_t __n)
{ if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
static void deallocate(_Tp* __p)
{ _Alloc::deallocate(__p, sizeof (_Tp)); }
用户调用分配器的时候，为simple_alloc的第二个模板参数传递要使用的分配器。
vector(用户方式)使用STL分配器的代码，可以看到vector的基类调用simple_alloc作为其分配器：
1 template &class _Tp, class _Alloc&
2 　　//cobbliu 注：STL vector 的基类
3 class _Vector_base {　　
typedef _Alloc allocator_
allocator_type get_allocator() const { return allocator_type(); }
_Vector_base(const _Alloc&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0) {}
_Vector_base(size_t __n, const _Alloc&)
: _M_start(0), _M_finish(0), _M_end_of_storage(0)
_M_start = _M_allocate(__n);
_M_finish = _M_
_M_end_of_storage = _M_start + __n;
~_Vector_base() { _M_deallocate(_M_start, _M_end_of_storage - _M_start); }
20 protected:
_Tp* _M_end_of_
typedef simple_alloc&_Tp, _Alloc& _M_data_
_Tp* _M_allocate(size_t __n)
{ return _M_data_allocator::allocate(__n); }
void _M_deallocate(_Tp* __p, size_t __n)
{ _M_data_allocator::deallocate(__p, __n); }
基本内存处理工具
除了上面的内存分配器之外，STL还提供了三类内存处理工具：uninitialized_copy(), uninitialized_fill()和uninitialized_fill_n()。这三类函数的实现代码在头文件stl_uninitialized.h中。
uninitialized_copy()像下面的样子：
1 template &class _InputIter, class _ForwardIter&
2 inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result)
return __uninitialized_copy(__first, __last, __result,
__VALUE_TYPE(__result));
uninitialized_copy()会将迭代器_first和_last之间的对象拷贝到迭代器_result开始的地方。它调用的__uninitialized_copy(__first, __last, __result,__VALUE_TYPE(__result))会判断迭代器_result所指的对象是否是POD类型（POD类型是指拥有constructor, deconstructor, copy, assignment函数的类），如果是POD类型，则调用算法库的copy实现；否则遍历迭代器_first~_last之间的元素，在_result起始地址处一一构造新的元素。
uninitialized_fill()像下面的样子：
1 template &class _ForwardIter, class _Tp&
2 inline void uninitialized_fill(_ForwardIter __first,
_ForwardIter __last,
const _Tp& __x)
__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
uninitialized_fill()会将迭代器_first和_last范围内的所有元素初始化为x。它调用的__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first))会判断迭代器_first所指的对象是否是POD类型的，如果是POD类型，则调用算法库的fill实现；否则一一构造。
uninitialized_fill_n()像下面这个样子：
1 template &class _ForwardIter, class _Size, class _Tp&
2 inline _ForwardIter
3 uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
uninitialized_fill_n()会将迭代器_first开始处的n个元素初始化为x。它调用的__uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first))会判断迭代器_first所指对象是否是POD类型，如果是，则调用算法库的fill_n实现；否则一一构造。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：321354次
积分：4443
积分：4443
排名：第5434名
原创：67篇
转载：346篇
评论：20条
(1)(2)(1)(1)(1)(1)(1)(1)(1)(1)(2)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(2)(1)(1)(1)(3)(1)(2)(3)(1)(1)(2)(1)(1)(1)(3)(1)(1)(1)(1)(1)(1)(1)(1)(1)(5)(3)(2)(2)(1)(3)(2)(2)(3)(5)(4)(15)(10)(11)(4)(9)(7)(9)(6)(8)(15)(11)(15)(7)(15)(19)(21)(35)(27)(12)(22)(43)(9)SGI STL中内存池的实现
来源：博客园
最近这两天研究了一下SGI STL中的内存池, 网上对于这一块的讲解很多, 但是要么讲的不完整, 要么讲的不够简单(至少对于我这样的初学者来讲是这样的...), 所以接下来我将把我对于对于SGI STL的理解写下来, 方便以后查阅同时也希望能够对像我一样刚刚接触C++的初学者提供一些帮助吧.
 
首先我们需要明确, 内存池的目的到底是什么?
首先你要知道的是, 我们每次使用new T来初始化类型T的时候, 其实发生了两步操作, 一个叫内存分配, 这一步使用的其实不是new而是operator new(也可以认为就是C语言中的malloc), 这一步是直接和操作系统打交道的, 操作系统可能需要经过相对繁琐的过程才能将一块指向空闲内存的指针返回给用户, 所以这也是new比较耗时的一部分, 而第二步就是使用构造函数初始化该内存, 这是我们比较熟悉的. 既然内存分配耗时, 那我们很容易想到的就是一次性分配一大块内存, 然后在用户需要的时候再划分其中一部分给用户, 这样的话, 一次分配, 多次使用, 自然而然提高了效率, 而用来管理这所谓的一大块内存的数据结构, 也就是今天我们要说的内存池. 另外一个好处在于, 频繁地使用new将导致系统内存空间碎片化严重, 容易导致的后果就是很难找到一块连续的大块内存, 空间利用率低.
 
那么我们先来看看, 内存池的整体结构 :

 
 该内存池可以认为由上面的一个指针数组和下面的自由链表两部分组成, 指针数组中第一个指针指向的是存放内存大小为8bytes的节点串接而成的自由链表, 之后依次是内存而16bytes, 24bytes直到128bytes, 当然在图中我只画出了一个自由链表. 所以内存池的基本思路在于 :
1. 如果用户分配的内存大于128bytes, 直接用malloc, 否则的话找出适合的自由链表, 从其上摘下一个节点将其头指针返回给用户.
2. 释放过程则正好与分配相对应, 如果用户分配的内存大于128bytes, 直接用free, 否则找出适当的自由链表, 将指针所指的该段内存重新连接到自由链表中(注意此时并不返回给操作系统, 因为之后还可以再重复利用). 
这一部分的所对应的代码如下图 :

 1 private:
 2
static const int Align = 8;
 3
static const int MaxBytes = 128;
 4
static const int NumberOfFreeLists = MaxBytes / A
 5
static const int NumberOfAddedNodesForEachTime = 20;
 6 
 7
union node {
 8
union node *
 9
char client[1];
10
};
11 
12
static obj *freeLists[NumberOfFreeLists];

 
为了便于理解, 我对于源代码中的所以属性名都做了相应的改动, 唯一可能存在疑问的是这个node为什么可以用联合体?
这里我们需要搞清楚这么几点, 自由链表上保存的都是一个一个并未使用的节点, 此时我们为了将所有的node串接起来, 我们当然可以独立分配空间来实现这一功能, 如下图, 比较容易想到的做法可能是这样, 用一个结构体来维护指向真正要分配给用户的内存块以及下一个结构体. 但是这样做有两个缺点 :
1.首先它的每一个node都需要额外多出一个指针的空间来保存真正要分配给用户的内存块的地址
2. 其次在将该内存块分配出去之后, 还需要再处理掉该node对应的结构体.

在分析分配函数的代码之前, 我们先来看看几个辅助函数 :

1 private:
2
static size_t ROUND_UP(size_t size) {
3
return ((size + Align - 1) & ~(Align - 1));
4
}
5 
6
static size_t FREELIST_INDEX(size_t size) {
7
return (size + Align - 1) / Align - 1;
8
}

这两个函数作用很简单, 第一个返回的是大于等于输入值的8的倍数, 第二个返回的是可以容纳输入值的最小的自由链表.
 
接下来就是内存池对外的接口, allocate函数的实现代码.

 1 void* alloc::allocate(size_t size) {
 2
if (size & MaxBytes) {
 3
return malloc(size);
 4
}
 5 
 6
size_t index = FREELIST_INDEX(size);
 7
node* theMostSuitableNode = freeLists[index];
 8
if (theMostSuitableNode) {
 9
freeLists[index] = theMostSuitableNode-&
10
return theMostSuitableN
11
else {
13
return refill(ROUND_UP(size));
14
}
15 }

1. 正如我们前面所讲的, 当用户希望得到size大小的内存空间时候, 此时我们只需要找到能够容纳size的最小的自由链表, 因为自由链表中都是还未分配出去的空间, 如果自由链表中还存在节点的话, 直接将该节点分配出去即可, 也就是这里的theMostSuitableNode不为空的情况, 但此时我们要将数组中指向该自由链表的指针指向下一个Node, 因为这个Node已经分配出去了.
2. 另一方面, 如果自由链表中并没有可用的Node(这里有两种情况会导致没有可用的Node, 第一种是曾经分配过, 但是用光了, 第二种是这是该内存池初始化以来第一次使用这个大小的自由链表, 所以还未分配过空间), 我们直接使用refill函数来填充自由链表, 之所以要用ROUND_UP使得它成为8的倍数, 是因为处于效率原因我们可能会一次性分配不止1个Node(这里是20个), 所以这里的空间必须按照Node的大小来分配.
 
所以我们顺蔓摸瓜, 接着来看refill的实现代码.

 1 void* alloc::refill(size_t size) {
 2
size_t num = NumberOfAddedNodesForEachT
 3
char* block = blockAlloc(size, num);
 4
node** currentFreeList = 0;
 5
node *curNode = 0, *nextNode = 0;
 6 
 7
if (num == 1) {
 8
return
 9
else {
11
currentFreeList = freeLists + FREELIST_INDEX(size);
12
*currentFreeList = nextNode = reinterpret_cast&node*&(block + size);
13
for (int i = 1;; ++i) {
14
curNode = nextN
15
nextNode = reinterpret_cast&node*&(reinterpret_cast&char*&(curNode) + size);
16
if (num - 1 == i) {
17
curNode-&next = 0;
18
break;
19
else {
21
curNode-&next = nextN
22
return
25
}
26 }

先解释一下第二行的blockAlloc, 这个函数的作用是去内存池中寻找size * num大小的空间然后划分给当前的自由链表(也就是currentFreeList), 因为一旦调用了refill说明该自由链表已经没有了可分配的Node, 所以我们这里考虑再分配的时候就直接分配了NumberOfAddedNodesForEachTime个(也就是20个). 但是要注意的话其实这里num传进去的是引用, 为什么传引用呢? 因为还有可能会出现内存池空间不够的情况, 此时如果内存池够1个Node但是不够20个的话, 就会将num设置为1, 说明此时只分配了1个Node空间. 所以可以看到第26行的判断中, 当num为1的时候, 直接将block返回给用户即可. 如果不是1的话, 再返回之前要先将剩下个节点串接在自由链表上. 这也就是那个for循环的作用.
 
当然在接触到blockAlloc之前, 我们先来看内存池的另外另个熟悉.

1 static char *startOfPool, *endOfP

这两个变量分别指向内存池所分配的空间中的起点和终点, 之前说道自由链表里面如果没有node了就到内存池中取, 其实就是从startOfPool开始的位置划出所需要的空间.
 
最后直接和内存池接触的当然就是blockAlloc了, 所以我们也来看一下这个函数.

 1 char* alloc::blockAlloc(size_t size, size_t& num) {
 2
char* re = 0;
 3
size_t bytesNeeded = size *
 4
size_t bytesLeft = endOfPool - startOfP
 5 
 6
if (bytesLeft &= bytesNeeded) {
 7
re = startOfP
 8
startOfPool = startOfPool + bytesN
 9
return
10
else if (bytesLeft & size) {
12
num = bytesLeft /
13
re = startOfP
14
startOfPool += num *
15
return
16
else {
18
//TODO
19
}
20 }

这里本来有三种情况, 第一种是说如果空间足够(足够分配20个Node那么大), 就直接分配, 然后把指向内存池中空间起始位置的startOfPool移到新的位置, 第二种是虽然不够分配20个, 但是足够分配一个, 此时使用相同的方式, 只不过需要对num进行改动(因为这里num传的是引用, 所以也没什么大问题), 最后一种情况是说连一个Node的内存都拿不出来, 这种情况需要再向系统申请内存, 我将在下面详细说明. 这里我们先来理一理, 目前的情况...
 
1. 使用allocate向内存池请求size大小的内存空间.
2. allocate根据size找到最适合的自由链表.
　　a. 如果链表不为空, 返回第一个node, 链表头改为第二个node.
　　b. 如果链表为空, 使用blockAlloc请求分配node.
　　　　x. 如果内存池中有大于一个node的空间, 分配竟可能多的node(但是最多20个), 将一个node返回, 其他的node添加到链表中.
　　　　y. 如果内存池只有一个node的空间, 直接返回给用户.
　　　　z. 若果如果连一个node都没有, 再次向操作系统请求分配内存(这就是上面代码中的TODO部分).
 
然后我们还能发现内存池的几个特点 :
1. 刚开始初始化内存池的时候, 其实内存池中并没有内存, 同时所有的自由链表都为空链表.
2. 只有用户第一次向内存池请求内存时, 内存池会依次执行上述过程的 1-&2-&b-&z来完成内存池以及链表的首次填充, 而此时, 其他未使用链表仍然是空的.
 
有了这个整体的了解之后, 我们现在就来看一下, 内存池是如何向操作系统申请内存的 : 
 

 1 char* alloc::blockAlloc(size_t size, size_t& num) {
 2
char* re = 0;
 3
size_t bytesNeeded = size *
 4
size_t bytesLeft = endOfPool - startOfP
 5 
 6
if (bytesLeft &= bytesNeeded) {
 7
re = startOfP
 8
startOfPool = startOfPool + bytesN
 9
return
10
else if (bytesLeft & size) {
12
num = bytesLeft /
13
re = startOfP
14
startOfPool += num *
15
return
16
else {
18
// I am not sure why add ROUND_UP(poolSize && 4)
19
size_t bytesToGet = 2 * bytesNeeded + ROUND_UP(poolSize && 4);
20
if (bytesLeft & 0) {
21
node** theMostSuitableList = freeLists + FREELIST_INDEX(bytesLeft);
22
(reinterpret_cast&node*&(startOfPool))-&next = *theMostSuitableL
23
*theMostSuitableList = reinterpret_cast&node*&(startOfPool);
24
}
25 
26
startOfPool = (char*)malloc(bytesToGet);
27
if (!startOfPool) {
28
node** currentFreeList = 0;
29
node* listHeadNode = 0;
30
for (int i = size + A i &= MaxB i += Align) {
31
currentFreeList = freeLists + FREELIST_INDEX(i);
32
listHeadNode = *currentFreeL
33
if (listHeadNode) {
34
*currentFreeList = listHeadNode-&
35
startOfPool = reinterpret_cast&char*&(listHeadNode);
36
endOfPool = reinterpret_cast&char*&(listHeadNode + i);
37
return blockAlloc(size, num);
38
//if code can run into this place, it means we can no longer get any memeory, so the best way is to throw exception...
41
exit(3);
42
else {
44
poolSize += bytesToG
45
endOfPool = startOfPool + bytesToG
46
return blockAlloc(size, num);
47
}
49 }

 
你会发现空间不足的时候, 首先计算了所需要的内存就是这个bytesToGet, 我在代码中也提到了我也不太清楚后面为什么要加上一个round_up(...), 然后是把当前剩余的内存(如果有剩余的话)分配给合适的节点, 因为每次分配内存都是8的倍数, 所以只要有剩余, 也肯定是8把的倍数, 所以一定能找到合适的节点. 接着就开始分配内存, 如果分配内存失败的话, 那么从size + Align开始(其实源代码好像是从size开始, 但是我感觉此时存有size大小node的自由链表显然是空的, 不然也不会调用这个函数, 所以就直接size + align 开始了), 如果能从那些位置挪出一个node的话(显然挪出来的node要更大), 那么就可以完成分配了, 如果遍历了所有比size大的节点都寻找不到这样一块node的话, 正如我代码中所说的, 运行到那个位置就应该抛异常了. 另外如果分配成功, 更新相应的变量之后, 再次调用该函数进行分配, 此时内存池中有足够的内存分配给自由链表.
 
早这里关于内存的分配的全过程就讲完了, 下面是内存的释放 :

 1 void alloc::deallocate(void* ptr, size_t size) {
 2
if (size & MaxBytes) {
 3
free(ptr);
 4
else {
 6
size_t index = FREELIST_INDEX(size);
 7
static_cast&node*&(ptr)-&next = freeLists[index];
 8
freeLists[index] = static_cast&node*&(ptr);
 9
}
10 }

内存的释放很简单, 如果大于128bytes的, 直接释放(因为也是直接分配过来的), 否则把它挂到相应的链表中, 留待之后使用.
 
到这里, 内存池的实现就算全部讲完了, 但是在真正将它投入到stl的实际使用中之前, 还要进行一层封装.

public:
value_
typedef T*
typedef const T*
const_
typedef T& 
typedef const T&
const_
typedef size_t
size_
typedef ptrdiff_t
difference_
public:
static T *allocate();
static T *allocate(size_t n);
static void deallocate(T *ptr);
static void deallocate(T *ptr, size_t n);

static void construct(T *ptr);
static void construct(T *ptr, const T& value);
static void destroy(T *ptr);
static void destroy(T *first, T *last);
};

template&class T&
T *allocator&T&::allocate(){
return static_cast&T *&(alloc::allocate(sizeof(T)));
template&class T&
T *allocator&T&::allocate(size_t n){
if (n == 0) return 0;
return static_cast&T *&(alloc::allocate(sizeof(T) * n));
template&class T&
void allocator&T&::deallocate(T *ptr){
alloc::deallocate(static_cast&void *&(ptr), sizeof(T));
template&class T&
void allocator&T&::deallocate(T *ptr, size_t n){
if (n == 0) return;
alloc::deallocate(static_cast&void *&(ptr), sizeof(T)* n);
}

template&class T&
void allocator&T&::construct(T *ptr){
new(ptr)T();
template&class T&
void allocator&T&::construct(T *ptr, const T& value){
new(ptr)T(value);
template&class T&
void allocator&T&::destroy(T *ptr){
ptr-&~T();
template&class T&
void allocator&T&::destroy(T *first, T *last){
for (; first != ++first){
first-&~T();
}
}

这也就是我们熟悉的标准库中的allocator的接口...
 
所以最终内存池的思路其实是这样的:
1. 使用allocate向内存池请求size大小的内存空间, 如果需要请求的内存大小大于128bytes, 直接使用malloc.
2. 如果需要的内存大小小于128bytes, allocate根据size找到最适合的自由链表.
　　a. 如果链表不为空, 返回第一个node, 链表头改为第二个node.
　　b. 如果链表为空, 使用blockAlloc请求分配node.
　　　　x. 如果内存池中有大于一个node的空间, 分配竟可能多的node(但是最多20个), 将一个node返回, 其他的node添加到链表中.
　　　　y. 如果内存池只有一个node的空间, 直接返回给用户.
　　　　z. 若果如果连一个node都没有, 再次向操作系统请求分配内存.
　　　　　　①分配成功, 再次进行b过程
　　　　　　②分配失败, 循环各个自由链表, 寻找空间
　　　　　　　　I. 找到空间, 再次进行过程b
　　　　　　　　II. 找不到空间, 抛出异常(代码中并未给出, 只是给出了注释)
3. 用户调用deallocate释放内存空间, 如果要求释放的内存空间大于128bytes, 直接调用free.
4. 否则按照其大小找到合适的自由链表, 并将其插入.
 
特点其实是这样的 :
1. 刚开始初始化内存池的时候, 其实内存池中并没有内存, 同时所有的自由链表都为空链表.
2. 只有用户第一次向内存池请求内存时, 内存池会依次执行上述过程的 1-&2-&b-&z来完成内存池以及链表的首次填充, 而此时, 其他未使用链表仍然是空的.
3. 所有已经分配的内存在内存池中没有任何记录, 释放与否完全靠程序员自觉.
4. 释放内存时, 如果大于128bytes, 则直接free, 否则加入相应的自由链表中而不是直接返还给操作系统.
 
以上是我对于sgi stl内存池的理解, 如果有任何不对的地方, 欢迎指出, 谢谢...
免责声明：本站部分内容、图片、文字、视频等来自于互联网，仅供大家学习与交流。相关内容如涉嫌侵犯您的知识产权或其他合法权益，请向本站发送有效通知，我们会及时处理。反馈邮箱&&&&。
学生服务号
在线咨询，奖学金返现，名师点评，等你来互动