STL源码分析读书笔记--第二章--空间配置器(allocator)

声明:侯捷先生的STL源码剖析第二章个人感觉讲得蛮乱的,而且跟第三章有关,建议看完第三章再看第二章,网上有人上传了一篇读书笔记,觉得这个读书笔记的内容和编排还不错,我的这篇总结基本就延续了该读书笔记的框架,如果发现有雷同,请勿见怪,这篇文章只是我的个人记录,算不上原创,只是更多的想把概念描述清楚,所以如果您觉得有copy之嫌的话请绕道看您觉得的原链接。在第8部分给出了笔记的参考链接。

 

1.allocator 作用

STL的组件(容器)都需要配置空间以放置资料。这个就是allocator的作用。很简单,实现起来却是最麻烦的。

2.allocator 的标准接口

  • 相关型别(参考读书笔记第三章相关型别的概念)
  •  

    allocator::value_type //所指对象的型别

    allocator::pointer //指向对象的指针

    allocator::const_pointer //指向对象的常量指针

    allocator::reference //对所指对象的引用

    allocator::const_reference 

    allocator::size_type //顾名思义,空间度量

    allocator::difference_type //距离度量

    这些型别都可以供traits榨取。

  • allocator类本身的构造与析构
  • Allocator::rebind//没太懂,一个嵌套的(nested)class template。class rebind<U>拥有唯一成员other, 那是一个typedef,代表allocator<U>。 

     

    allocator::allocator()---默认构造函数

    allocator::allocator(const allocator&)---拷贝构造函数

    template <class U>allocator::allocator(const allocator<U>&) --- 泛化的拷贝构造函数

    allocator::~allocator()---默认的析构函数

  • 取地址函数(等效于&操作符,应该针对特殊的空间配置有特殊的实现)
  • pointer allocator::address(reference x) const ---传回某个对象的地址,算式a.address(x)等同于&x。 

    const_pointer allocator::address(const_reference x) const --- 传回某个const对象的地址,算式a.address(x)等同于&x。

  • 具体实现配置的接口(获得空间)
  • pointer allocator::allocate(size_type n, cosnt void* = 0) --- 配置空间,足以储存n个T对象。第二自变量是个提示。实作上可能会利用它来增进区域性(locality),或完全忽略之。 

    void allocator::deallocate(pointer p, size_type n) ---归还先前分配的空间。 

    size_type allocator::max_size() const --- 传回可成功分配的最大量。

  • construct和destroy函数(获得了空间之后在空间上构建对象)

 

3.几点说明

STL源码分析分析的是SGI版本,SGI版本有个符合部分标准的名为allocator的不接受任何参数的配置器,但是SGI没用它,因为效率不佳,只是对全局new和全局delete的一个封装而已,此配置器的全貌在书中有,不做说明。SGI特殊的空间配置器是std::alloc,为什么它的效率高,有一个原因就是它将内存的配置和对象的构造区分开来了。我们知道,对于下面代码中的new 和delete,

Class Foo{

......

}

 

Foo *of = new Foo;//配置内存,然后构造对象

Delete pf;//将对象析构,然后释放内存

 

其中的new实际上分两步,delete也分两步,以new为例,先调用::operator new配置空间,然后在空间上面构造对象,现在std::alloc对这两步分别特殊实现,以保证高效。

4.std::allocator总览

STL源码分析读书笔记--第二章--空间配置器(allocator)

这幅图是自解释的,看过源码的都知道,这三个文件在memory中被包含进来了,在第2部分也大概说明了stl_alloc.h和stl_construct.h的作用,但是stl_uninitialized.h的作用却没提,它们不属于配置器的内容,但接下来会讲到它们的重要作用。

5.std::alloc的构造与析构基本工具:construct()和destroy()

  • construct()
    • construct()没啥好说的,调用placement new即可。
  • destroy()
    • 这个就有讲究,讲究是效率,它有两个版本,第一个版本接受一个指针参数,这个版本直接调用该对象的析构函数即可,不管这个对象的析构函数是否为non-trivial,开销影响都不大,但是对于第二个版本,它接受一个迭代器区间,那么就得确定对象的析构函数是否有意义,如果没意义,且区间很长,那么这种浪费是不能容忍的,因此,destroy针对这种情况作了优化,主要方法是先获取迭代器所指对象型别,然后通过traits获得对象的一个相关型别:一个是否有non-trivial析构函数的非独立名字。当然要实现这一功能,类中一定声明了这个内嵌型别声明。具体代码如下:
    • //以下是destroy()的第二版本,接受两个迭代器,准备将[first, last)范围内的所有物件析    //构掉,因为不知道这个范围有多大,万一很大,但是每个物件的析构函数都是无关痛    //痒的(triaval destructor),那么一次次呼叫这些无关痛痒的析构函数,对效率是一种损    //害,所以此函数设法找出元素的数值类型,进而利用__type_traits<>选    //择适当措    //施

       

      template <class ForwardIterator>

      // __false_type表明是具有non trivial destructor,所以要循环调用destroy

      inline void  __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {

        for ( ; first < last; ++first)

          destroy(&*first);

      }

       

      template <class ForwardIterator>

      //__true_type表明是具有trivial destructor不需要调用destroy

      inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {} //空函数体

       

      //判断元素的型别,是否有trival destructor

      template <class ForwardIterator, class T>

      inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {

        typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;

        __destroy_aux(first, last, trivial_destructor());

      }

       

      template <class ForwardIterator>

      inline void destroy(ForwardIterator first, ForwardIterator last) {

        __destroy(first, last, value_type(first));

      }

       

      //以下是destroy()第二版本针对迭代器为char*和wchar*的特化版

      Inline void destroy(char*, char*){}

      Inline void destroy(wchar_t*, wcht_t*){}

    • 上述代码中,value_type和traits的实现机制在第三章中有描述。可以看到,destroy()只是包装函数而已,实现时在__destroy()那里编译器分流,然后由__destroy_aux来具体实现。
    • STL源码分析读书笔记--第二章--空间配置器(allocator)
      •  

6.空间的配置与释放,std::alloc

空间配置与释放代码在<stl_alloc.h>中

  • SGI对此的设计哲学:
    • 向system heap申请空间;

      考虑多线程情况;--这个书上没多讲

      考虑内存不足时的应对措施;

      考虑过多小型区块可能造成的内存碎片(fragment)问题;--SGI为此决定设计双层配置器

  • 关于双层配置器

考虑小型区块可能造成的内存碎片问题,SGI设计了双层级配置器,低一级分配器直接使用malloc()和free(), 第二级分配器则视情况采用不同策略:当分配区块超过128bytes,则视之“足够大”,便使用低一级分配器;当分配区块小于128bytes,则视之“过小”,便采用复杂的mempool方式。在mempool里面设计算法以防止内存破碎。

  • 第一级配置器:__malloc_alloc_template

    第一级配置器很简单,主要注意两点:其一,它实际上调用C底层那些函数,比如malloc,free,realloc;其二,要用new-handler机制解决内存不足时出现的状况代码如下:
    #if 0

    #    include<new>

    #     define __THROW_BAD_ALLOC throw bad_alloc

    #elif !defined(__THROW_BAD_ALLOC)

    #    include <iostream.h>

    #    define __THROW_BAD_ALLOC cerr<<"out of memory"<<endl;exit(1)

    #endif

     

    //注意,无「template 型别参数」。至于「非型别参数」inst,完全没派上用场。 

    template <int inst>   

    class __malloc_alloc_template { 

     

    private: 

    //以下都是函数指针,所代表的函式将用来处理内存不足的情况。 

    // oom : out of memory. 

    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);//第一级配置器直接使用 malloc() 

        // 以下,无法满足需求时,改用 oom_malloc() 

        if (0 == result) result = oom_malloc(n); 

        return  result; 

    } 

     

    static void deallocate(void *p, size_t /* n */) 

    { 

    free(p); //第一级配置器直接使用 free() 

    } 

     

    static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz) 

    { 

        void  *  result  =realloc(p, new_sz);//第一级配置器直接使用 realloc() 

        // 以下,无法满足需求时,改用 oom_realloc() 

        if (0 == result) result = oom_realloc(p, new_sz); 

        return  result; 

    } 

     

    //以下模拟 C++的 set_new_handler(). 换句话说,你可以透过它, 

    //指定你自己的 out-of-memory handler 

    static void (* set_malloc_handler(void (*f)()))()//蓝色部分作为参数,最后一个()和void(*)                                    //一起组成void(*)()表示返回值是一个函数指针

    { 

        void  (*  old)()  =  __malloc_alloc_oom_handler; 

    __malloc_alloc_oom_handler = f; 

        return(old); 

    } 

    }; 

     

    // malloc_alloc out-of-memory handling 

    //初值为 0。有待用户设定。 __malloc_alloc_oom_handler是一个函数指针

    template <int inst> 

    void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; 

     

    template <int inst> 

    void * __malloc_alloc_template<inst>::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); 

        } 

    } 

     

    template <int inst> 

    void * __malloc_alloc_template<inst>::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); 

        } 

    } 

     

    //注意,以下直接将参数 inst指定为 0。 

    typedef __malloc_alloc_template<0> malloc_alloc;

  • 第二级配置器:

    如果区块比较小,就移交第二级配置器,采用内存池的思想管理内存,即每次配置一大块内存,然后维护对应之*链表(就是可以空间链表)SGI维护16个链表,分别管理大小依次为8,16,24,….,128bytes的小额区块。freelist的结构如下(以union来设计list自然是为了节省空间,原理见书上,略过不谈):
    union obj { 

           union obj * free_list_link; 

           char  client_data[1];   /* The client sees this.标志是否被使用 */ 

     };

    很自然一件事就是,如果我们申请空间成功,那么从free-list中拿来即可,如果申请不成功呢?

    答案是调用refill() 函数重新分配 空间,当要释放空间时,就将空间重现挂接回free-list.

    刚才说到refill(),refill函数获得的空间由chunk_alloc()函数经由memory pool获得,缺省取得20个新节点,如果能获得足够的空间,自然是直接返回新节点然后串接到free-list上,如果只获得一个节点,直接返回给需要的地方使用,如果一个 都得不到,那么调用malloc从system heap上重新申请空间加入到memory pool中重新chunk,然后返回,调用malloc的次数越多,从system heap 上申请的空间就越多,如果malloc都申请不到,那么看malloc的out of memory机制能否申请到,实在申请不到且从其他大小的free-list上也抠不下来内存的话一般发出bad_alloc异常。

    代码比较复杂,见书上。

 

7.内存处理的基本工具

  • uninitialized_copy
  • uninitialized_fill
  • unintialized_fill_n

这几个函数都是全局的,作用与未初始化的空间之上,这三个函数都满足要么成功构造,要么不构造任何元素这一约束,因此具有一定的安全保证,他们实际都是调用的的其他的函数,比如,uninitialized_copy有一种实现就是是在未初始化内存上调用复制函数constructor(…)复制对象,用它来构造函数具有安全性,防止构造中出现问题。uinitialized_fill的一种实现是是在未初始化内存上调用初始化函数construct(&*i,x),uninitialized_fill_n顾名思义是批量初始化操作。更详细的解释看书上即可。附上书中一张自解释的图吧。

STL源码分析读书笔记--第二章--空间配置器(allocator)

 

8.参考

9.说明

这篇笔记注重讲配置器的思想,细节方面可能有些不准确,请谅解,因为这篇文章本意只是自己的一个备忘录而已。

上一篇:stl源码分析之allocator


下一篇:STL 源码分析六大组件-allocator