首页 > 代码库 > 浅析STL allocator

浅析STL allocator

  一般而言,我们习惯的 C++ 内存配置操作和释放操作是这样的:

1 class FOO{};
2 FOO *pf = new FOO;    
3 delete pf;

  我们看其中第二行和第三行,虽然都是只有一句,当是都完成了两个动作。但你 new 一个对象的时候两个动作是:先调用::operator new 分配一个对象大小的内存,然后在这个内存上调用FOO::FOO()构造对象。同样,当你 delete 一个对象的时候两个动作是:先调用FOO::~FOO() 析构掉对象,再调用::operator delete将对象所处的内存释放。为了精密分工,STL 将allocator决定将这两个阶段分开。分别用 4 个函数来实现:

  1.内存的配置:alloc::allocate();

  2.对象的构造:::construct();

  3.对象的析构:::destroy();

  4.内存的释放:alloc::deallocate();

  其中的 construct() 和 destroy()定义在 STL的库文件中,源代码如下:

 1 template <class T>
 2 inline void destroy(T* pointer) {
 3     pointer->~T();                               //只是做了一层包装,将指针所指的对象析构---通过直接调用类的析构函数
 4 }
 5 
 6 template <class T1, class T2>
 7 inline void construct(T1* p, const T2& value) {
 8   new (p) T1(value);                            //用placement new在 p 所指的对象上创建一个对象,value是初始化对象的值。
 9 }
10 
11 template <class ForwardIterator>                //destory的泛化版,接受两个迭代器为参数
12 inline void destroy(ForwardIterator first, ForwardIterator last) {
13   __destroy(first, last, value_type(first));    //调用内置的 __destory(),value_type()萃取迭代器所指元素的型别
14 }
15 
16 template <class ForwardIterator, class T>
17 inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
18   typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
19   __destroy_aux(first, last, trivial_destructor());        //trival_destructor()相当于用来判断迭代器所指型别是否有 trival destructor
20 }
21 
22 
23 template <class ForwardIterator>
24 inline void                                                //如果无 trival destructor ,那就要调用destroy()函数对两个迭代器之间的对象元素进行一个个析构
25 __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
26   for ( ; first < last; ++first)
27     destroy(&*first);
28 }
29 
30 template <class ForwardIterator>                        //如果有 trival destructor ,则什么也不用做。这更省时间
31 inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}
32 
33 inline void destroy(char*, char*) {}          //针对 char * 的特化版
34 inline void destroy(wchar_t*, wchar_t*) {}    //针对 wchar_t*的特化版

  看到上面这么多代码,大家肯定觉得 construct() 和 destroy() 函数很复杂。其实不然,我们看到construct()函数只有几行代码。而 destroy() 稍微多点。但是这么做都是为了提高销毁对象时的效率。为什么要判断迭代器所指型别是否有 trival destructor,然后分别调用不同的执行函数?因为当你要销毁的对象很多的时候,而这样对象的型别的destructor 都是 trival 的。如果都是用__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)来进行销毁的话很费时间,因为没必要那样做。而当你对象的destructor 都是 non-trival 的时候,你又必须要用__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)来析构。所以,我们要判断出对象型别的destructor 是否为 trival,然后调用不同的__destroy_aux。

  说完 construct() 和 destory() ,我们来说说 alloc::allocate() 和 alloc::deallocate(),其源代码在 <stl_alloc.h>中。stl_alloc.h中代码设计的原则如下:

  1.向 system heap 要求空间

  2.考虑多线程状态

  3.考虑内存不足时的应变措施

  4.考虑过多“小型区块”可能造成的内存碎片问题。

  stl_alloc.h中的代码相当复杂,不过没关系。我们今天只看其中的allocate() 和 deallocate()。在讲这两个函数之前,我们还必须来了解一下SGI  STL(SGI限定词是STL的一个版本,因为真正的STL有很多不同公司实现的版本,我们所讨论的都是SGI版本) 配置器的工作原理:

  考虑到小型区块可能造成内存破碎问题(即形成内存碎片),SGI STL 设计了双层级配置器。第一层配置器直接使用malloc() 和 free().第二层配置器则视情况采用不同的策略:但配置区块超过 128 bytes时,调用第一级配置器。当配置区块小于 128 bytes时,采用复杂的 memory pool 方式。下面我们分别简单的介绍一下第一级和第二级配置器:

第一级配置器 _ _malloc_alloc_template:

  由于第一级配置器的配置方法比较简单,代码也容易理解,我在这里全部贴出:

 1 //以下是第第一级配置器
 2 template <int inst>
 3 class __malloc_alloc_template {
 4 
 5 private:
 6 
 7 //以下函数用来处理内存不足的情况
 8 static void *oom_malloc(size_t);
 9 
10 static void *oom_realloc(void *, size_t);
11 
12 static void (* __malloc_alloc_oom_handler)();
13 
14 public:
15 
16 static void * allocate(size_t n)
17 {
18     void *result = malloc(n);                    //第一级配置器,直接使用malloc()
19     //如果内存不足,则调用内存不足处理函数oom_alloc()来申请内存
20     if (0 == result) result = oom_malloc(n);
21     return result;
22 }
23 
24 static void deallocate(void *p, size_t /* n */)
25 {
26     free(p);            //第一级配置器直接使用 free()
27 }
28 
29 static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
30 {
31     void * result = realloc(p, new_sz);            //第一级配置器直接使用realloc()
32     //当内存不足时,则调用内存不足处理函数oom_realloc()来申请内存
33     if (0 == result) result = oom_realloc(p, new_sz);
34     return result;
35 }
36 
37 //设置自定义的out-of-memory handle就像set_new_handle()函数
38 static void (* set_malloc_handler(void (*f)()))()
39 {
40     void (* old)() = __malloc_alloc_oom_handler;
41     __malloc_alloc_oom_handler = f;
42     return(old);
43 }
44 };
45 
46 template <int inst>    
47 void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;  //内存处理函数指针为空,等待客户端赋值
48 
49 template <int inst>
50 void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
51 {
52     void (* my_malloc_handler)();
53     void *result;
54 
55     for (;;) {                                                     //死循环
56         my_malloc_handler = __malloc_alloc_oom_handler;            //设定自己的oom(out of memory)处理函数
57         if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }         //如果没有设定自己的oom处理函数,毫不客气的抛出异常
58         (*my_malloc_handler)();                                    //设定了就调用oom处理函数
59         result = malloc(n);                                        //再次尝试申请
60         if (result) return(result);
61     }
62 }
63 
64 template <int inst>
65 void * __malloc_alloc_template<inst>::oom_realloc(void *p, size_t n)
66 {
67     void (* my_malloc_handler)();
68     void *result;
69 
70     for (;;) {
71         my_malloc_handler = __malloc_alloc_oom_handler;
72         if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }    //如果自己没有定义oom处理函数,则编译器毫不客气的抛出异常
73         (*my_malloc_handler)();                                //执行自定义的oom处理函数
74         result = realloc(p, n);                                //重新分配空间
75         if (result) return(result);                            //如果分配到了,返回指向内存的指针
76     }
77 }

  上面代码看似繁杂,其实流程是这样的:

  1.我们通过allocate()申请内存,通过deallocate()来释放内存,通过reallocate()重新分配内存。

  2.当allocate()或reallocate()分配内存不足时会调用oom_malloc()或oom_remalloc()来处理。

  3.当oom_malloc() 或 oom_remalloc()还是没能分配到申请的内存时,会转如下两步中的一步:

    a).调用用户自定义的内存分配不足处理函数(这个函数通过set_malloc_handler() 来设定),然后继续申请内存!

    b).如果用户未定义内存分配不足处理函数,程序就会抛出bad_alloc异常或利用exit(1)终止程序。

  看完这个流程,再看看上面的代码就会容易理解多了!

第二级配置器 _ _default_alloc_template:

  第二级配置器的代码很多,这里我们只贴出其中的 allocate() 和 dellocate()函数的实现和工作流程(参考侯捷先生的《STL源码剖析》),而在看函数实现代码之前,我大致的描述一下第二层配置器配置内存的机制。

  我们之前说过,当申请的内存大于 128 bytes时就调用第一层配置器。当申请的内存小于 128bytes时才会调用第二层配置器。第二层配置器如何维护128bytes一下内存的配置呢? SGI 第二层配置器定义了一个 free-lists,这个free-list是一个数组,如下图:

  

  这数组的元素都是指针,用来指向16个链表的表头。这16个链表上面挂的都是可以用的内存块。只是不同链表中元素的内存块大小不一样,16个链表上分别挂着大小为

   8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes的小额区块,图如下:

   

  就是这样,现在我们来看allocate()代码:

 static void * allocate(size_t n)
  {
    obj * __VOLATILE * my_free_list;
    obj * __RESTRICT result;
    
    //要申请的空间大于128bytes就调用第一级配置
    if (n > (size_t) __MAX_BYTES) {
        return(malloc_alloc::allocate(n));
    }
    //寻找 16 个free lists中恰当的一个
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == 0) {
        //没找到可用的free list,准备新填充free list
        void *r = refill(ROUND_UP(n));
        return r;
    }
    *my_free_list = result -> free_list_link;
    return (result);
  };

  其中有两个函数我来提一下,一个是ROUND_UP(),这个是将要申请的内存字节数上调为8的倍数。因为我们free-lists中挂的内存块大小都是8的倍数嘛,这样才知道应该去找哪一个链表。另一个就是refill()。这个是在没找到可用的free list的时候调用,准备填充free lists.意思是:参考上图,假设我现在要申请大小为 56bytes 的内存空间,那么就会到free lists 的第 7 个元素所指的链表上去找。如果此时 #7元素所指的链表为空怎么办?这个时候就要调用refill()函数向内存池申请N(一般为20个)个大小为56bytes的内存区块,然后挂到 #7 所指的链表上。这样,申请者就可以得到内存块了。当然,这里为了避免复杂,误导读者我就不讨论refill()函数了。allocate()过程图如下:

  

  学过链表的操作的人不难理解上图,我就不再讲解。下面看deallocate(),代码如下:

 1 static void deallocate(void *p, size_t n)
 2 {
 3     obj *q = (obj *)p;
 4     obj * __VOLATILE * my_free_list;
 5 
 6     //如果要释放的字节数大于128,则调第一级配置器
 7     if (n > (size_t) __MAX_BYTES) {
 8         malloc_alloc::deallocate(p, n);
 9         return;
10     }
11     //寻找对应的位置
12     my_free_list = free_list + FREELIST_INDEX(n);
13     //以下两步将待释放的块加到链表上
14     q -> free_list_link = *my_free_list;    
15     *my_free_list = q;
16 }

  deallocate()函数释放内存的步骤如下图:


  其实这就是一个链表的插入操作,也很简单。不再赘述!上面忘了给链表结点的结构体定义了,如下:

union obj{
    union obj * free_list_link;
    char client_date[1]; 
};

  至此,SGI STL的对象的构造与析构、内存的分配与释放就介绍完毕了。