走进STL - 空间配置器，STL背后的故事
若有迷惑不解之处，或可在此篇找到解答：走近STL -STL概论
1、何为“空间配置器”
a、为何需要先了解空间配置器
从使用STL层面而言，空间配置器并不需要介绍，所以我的“走近STL”系列中并没有它的位置。
但若是从STL实现角度出发，空间配置器确实首要理解的。
作为STL设计背后的故事，空间配置器总是在默默地付出着。为什么你可以使用算法处理数据，为什么可以对容器进行操作，为什么迭代器可以遍历空间，这一切的一切，都有“空间配置器”的功劳。
而如果不经过本章，看后续章节会给自己徒增许多烦恼。
b、SGI STL专属空间配置器
SGI STL 的空间配置器与众不同，且与STL标准规范不同，其名为alloc，而非allocator。
SGI STL allocator未能符合标准，不过这并不会给我们造成困扰，因为我们没什么事儿不会自己去配置这个。而SGI的每一个容器都已经预设好了alloc。举例声明如下：
template <class T,class Alloc = alloc> //预设使用alloc配置器
class vector{···};
- 1
- 2
虽然SGI也配置了allocatalor，但是它自己并不使用，也不建议我们使用，原因是效率比较感人，
因为它只是在基层进行配置/释放空间而已。
c、alloc的优势
三言两语无法说清，也不具说服力，具体请看下面 alloc全貌 的介绍。
（友情提醒：可以参考 2.c - c.1）
2、alloc全貌
a、 C++内存配置操作与释放操作
且看以下小栗子：
class test{···};
test *pf = new test; //配置内存，然后构造对象
···
delete pf; //析构对象，然后释放内存
- 1
- 2
- 3
- 4
- 5
这其中的new包含两个步骤：调用 ::operator new分配内存 ，调用test::test() 创建对象
其中的delete也包含两个步骤：调用test::~test()析构对象，调用 ::operator delete 释放空间
为了精密分工，STL allocator 将这两个步骤分开来，由alloc:allocate()负责内存配置操作，内存释放操作由alloc:deallocate()负责；对象构造操作由 ::construct()负责，对象析构操作由 ::destroy() 负责。
STL标准规则告诉我们，配置器定义于之中，SGI的内含以下两个文件：
#include <stl_alloc.h> //负责内存空间的配置与释放
#include <stl_construct.h> //负责对象内容的构造与析构
- 1
- 2
来看张图：
初学作图，有点丑，还能看。
b、析构和构造的基本函数
construct()和destroy的源代码，睁大眼睛哦，虽然这两个函数不难
//以下是construct()函数
#include <new.h>
template <typename T1,typename t2>
inline void construct(T1 *p,const T2& value)
{
new (p) T1(value); //调用T1::T1(value)
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
//以下是destroy()函数第一版本
template <typename T> //第一版本，接受一个指针
inline void destroy(T *pointer)
{
pointer->~T(); //调用 dtor ~T()
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
//以下是destroy()函数第二版本，接受两个迭代器
template <typename ForwardIterator>
inline void destory(ForwardIterator first,ForwardIterator last)
{
__destory(first,last,value_type(first));
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
//判断元素的数值型别（value type）是否无关痛痒（trivial destructor）
template <typename ForwardIterator,typename T>
inline void __destroy(ForwardIterator first,ForwardIterator last,T*)
{
typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;//注1
__destroy_aux(first,last,trivial_destructor());
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
注1：这一句如果看不懂，我已经备好了排忧解难工具包
//如果是有关痛痒（non-trivial destructor）的
template <typename ForwardIterator,typename T>
inline void __destroy_aux(ForwardIterator first,ForwardIterator last,__false_type)
{
for(;first<last;++first)
{
destroy(&*first);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
//如果是trivial destructor，则no-op
template <typename ForwardIterator,typename T>
inline void __destroy_aux(ForwardIterator first,ForwardIterator last,__true_type){}
- 1
- 2
- 3
- 4
- 5
这么长一串怕是看呆了，再来张图吧，献丑了
c、空间的配置与释放（alloc）
上面那一块是对象的构造和析构，接下来要讲的是对象构造和析构背后的故事——（内存的分配与释放），不要搞混了哦。
c.1 真·alloc设计奥义
对象构造和析构之后的内存管理诸项事宜，由<stl_alloc.h>一律负责。
SGI对此的设计原则如下：
- 向system heap索要空间
- 考虑多线程状态
- 考虑内存不足时的应变措施
- 考虑过多小型区块造成的内存碎片问题
考虑到小型区块可能造成的内存破碎问题，SGI为此设计了双层级配置器。
当配置区块超过128bytes时，称为足够大，使用第一级配置器，直接使用malloc()和free()。
当配置区块不大于128bytes时，为了降低额外负担，直接使用第二级配置器，采用复杂的memory pool处理方式。
无论使用第一级配接器或是第二级配接器，alloc都为其包装了接口，使其能够符合STL标准。
c.2 alloc一级配置器源码（截取）
睁大眼睛吧，看看这鬼斧生工的设计：
#include <new>
//注意，alloc不接受“template 型别参数”，所以就算你定义了也用不上
class __malloc_alloc_template
{
private: //这里面都是函数指针，用来处理内存不足的情况
static void *oom_malloc(size_t);
static void *oom_realloc(void *,size_t);
static void (* __malloc_alloc_oom_handler)();
public: //正常空间配置
static void * allocate(size_t n)
{
void *result = malloc(n); if( 0 == result) result = oom_malloc(n);
return result;
}
//正常空间回收
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 = oom_realloc(p,new_sz);
return result;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
//截取片段，留作向后拓展的部分这里就不提了
//下面为异常情况处理（空间不够）
void *__malloc_alloc_tempate<0>::oom_malloc(size_t n)
{
void (* my_malloc_handler)();
void *result;
for(;;)
{
//不断尝试释放、配置、再释放、再配置
my_malloc_handler = __malloc_alloc_oom_handler;
if( 0 == my_malloc_handler)
{ __THROW_BAD_ALLOC;
} (* my_malloc_handler)(); //调用处理例程，企图释放内存
//这行我看的有点晕，找到的资料里能说服我的是：“调用用户定义函数“。当然，这个用户指的不是咱，是处理例程
//如果有更好的理解，万望不吝赐教。 result = malloc(n); //尝试再次配置内存
if(result) return (result);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
void *__malloc_alloc_tempate<0>::oom_realloc(void *p,size_t n)
{
void (* my_malloc_handler)();
void *result;
for(;;)
{
//不断尝试释放、配置、再释放、再配置
my_malloc_handler = __malloc_alloc_oom_handler;
if( 0 == my_malloc_handler)
{ __THROW_BAD_ALLOC;
} (* my_malloc_handler)(); result = realloc(p,n); //尝试再次配置内存
if(result) return (result);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
SGI 以malloc，而非 ::operator new 来分配内存，有历史因素，也有重配内存的因素在里面吧。
c.3 alloc 二级配置器源码（截取）
如果累了，建议先歇会儿，保护眼睛保护大脑。
接下来的这部分，将会更加的让我们为大师的智慧折服。
第二级配置器多了一些机制，专门针对内存碎片。内存碎片化带来的不仅仅是回收时的困难，配置也是一个负担。额外负担永远无法避免，毕竟系统要划出这么多的资源来管理另外的资源，但是区块越小，额外负担率就越高。
（索求任何一块内存，都得有一些“回扣”要交给系统）
SGI第二级配置器解决了多少问题呢？那就看各位的理解到什么程度了。
SGI第二级配置器的做法是“：sub-allocation （层次架构）：
- 每次分配一大块内存，并维护对应之自由链表（free-list）。
- 下次若再有相同大小的内存需求，则直接从free-lists中取出。
- 如果客端释放小额区块，就收回free-lists.
苍白的文字啊，看图：
清楚明了吧。
为了方便管理，SGI配置器会主动将任何小区块的内存需求量提升至8的倍数，就是整数字节的大小。
如果客端要求2个比特，就会自动分配到8比特。
并维护了16个free-list,图中已明确指出了。
如果我的图太难看，我在别的地方也找了一张：
free-list的节点结构真的是要惊叹的了：
看：
注：如果关于联合体把你困住了，我帮你解决了：工具包
union obj
{
union obj *free_list_link;
char client_data[1];
}
- 1
- 2
- 3
- 4
- 5
乍一看可能平淡无奇，认真一看，那个 union obj共出现了两次。这样有什么好处？
由于union的缘故，从其第一字段来看，obj可被视为一个指针，执行指向另一个obj;
从第二个字段来看，obj可以被看作一个指针，指向实际区块。
这样的好处在于，不会为了维护链表所必须的指针而造成另一次内存浪费。
秀吧，天秀！
好，接下来是第二级配置器的部分实现内容：
enum {__ALIGN = 8}; //小型区块的上调边界
enum {__MAX_BYTES = 128}; //小型区块的上限
enum {__NFREELISTS/ALIGN} //free-list个数
- 1
- 2
- 3
class __default_alloc_template{
private:
//将byte上调至8的倍数
static size_t ROUND_UP(size_t bytes){
return (((bytes)+__ALIGN-1) &~ (__ALIGN -1));
}
private:
//free-list的节点构造
private:
//16个free-list
static obj *volatile free_list[__NFREELISTS];
//根据区块大小，决定使用n号free-list。n从1开始算
static size_t FREELIST_INDEX(size_t bytes) {
return return (((bytes)+__ALIGN-1) / __ALIGN -1);
}
}
···
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
c.4空间配置函数allocate
文字叙述前面已经很详尽了，倒是代码零零散散，这里将代码串起来。
static void *alloc(size_t n)
{
obj * volatile my_free_list;
obj * result;
//一级
if( n > (size_t) __MAX_BYTES)
{
return (malloc_alloc::allocate(n));
}
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if(result == 0)
{
//没有可用free-list,准备重新填充
void *r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->free_list_link;
return (result);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
c.5 空间释放函数deallocate
有配置自然要有相应的释放函数了。
文字叙述已经很详尽了，直接看代码吧。
static void deallocate(void *p,size_t n)
{
obj *q = (obj *)p;
obj *volatile *my_free_list;
if( n > (size_t) __MAX_BYTES)
{
malloc_alloc::deallocate(p,n);
return n;
}
//寻找对应的free list
my_free_list = free_list + FREELIST_INDEX(n);
//调整free_list，回收区块
q->free_list_link = *my_free_list;
*my_free_list = q;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
c.6 重新填充free lists 函数refill
前面将这块放空。始终觉得看不过去。
当分配空间时发现没有可用区块空间了，就需要使用refill从内存池中申请空间。
void * __default_alloc_template</**参数不管它*/>::refill(size_t n)
{
int nobjs = 20;
//调用chunk_alloc(),尝试取得nobjs个区块作为新节点
char *chunk = chunk_alloc(n,nobjs);
obj *volatile *my_free_list;
obj *result;
obj *current_obj,*next_obj;
int i;
if(1 == nobjs) //要是就剩一块儿了，先给调用者
return (chunk);
my_free_list = free_list + FREELIST_INDEX(n);
//睁大眼睛吧
//接下来准备在chunk空间中建立free list
result = (obj *)chunk; //先给调用者来一块
//接下来引导free list来拿地
*my_free_list = next_obj = (obj *)(chunk + n);
//然后将新拿到的地消化吸收
for(i = 1; ;i++) //从1开始，0给别人了
{
current_obj = next_obj;
next_obj = (obj *) ((char *)next_obj+n);
if(nobjs - 1 == i)
{ current_obj->free_list_link = 0; break;
}
else current_obj -> free_list_link = next_obj;
}
return (result);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
c. 内存池的chunk_alloc()操作
从内存池中取空间给free list 使用，是chunk_alloc() 的工作。
char * __default_alloc_template</*参数不管它*/>::chunk_alloc(size_t size,int &nobjs)
{
char * result;
size_t total_bytes = size *nobjs;
size_t bytes_left = end_free - start_free; //内存池还有多少水
if(bytes_left>=total_bytes)
{
result = start_free;
start_free += total_bytes;
return (result);
}
else if(bytes_left >= size) //不够总量，但是总归还是有一些存货的
{
nobjs = bytes_left/size;
total_bytes = size*nobjs;
result = start_free;
start_free += total_bytes;
return (result);
//能给多少多少给多少吧
}
else
{
//一点都没了
size_t byte_to_get = 2*total_bytes + ROUND_UP(heap_size >> 4);
//先找些零零散散的拼一下看看
if(bytes_left>0)
{ obj * volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left); //调整free-list,将残余空间塞进去 ((obj *)start_free)->free_list_link = *my_free_list; *my_free_list = (obj *)start_free;
}
//记得我们开头说过，空间总是从system-heap中索求的，现在是时候去索求了
//这块省略吧，太长了
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
万一山穷水尽，连system heap都没空间了，那就一首凉凉。
篇章说明：
本篇主要来自与侯捷先生的《STL源码剖析》。
我在CSDN上也看到不少此类文章，但是大多是生搬硬套，很多点都讲的不清不楚，我在查资料的时候也是很懵。
所以我尽量把自己能看懂的内容摘取，看不懂的都去查了资料，工具包都嵌在文中了，或注释，或链接。
下一篇章将会是《迭代器》，不过不知道要写多久，这篇整整写了五天。
文章来源: lion-wu.blog.csdn.net，作者：看，未来，版权归原作者所有，如需转载，请联系作者。
原文链接：lion-wu.blog.csdn.net/article/details/105457222
- 点赞
- 收藏
- 关注作者
评论（0）