天天看点
返回

STL 二级空间配置器实现机制

一：简述

STL 空间配置器（allocator）中分配内存与构造对象分开，在头文件<memory>定义：

1、分配内存由alloc::allocate()负责，内存释放由alloc::deallocate()负责，在<stl_alloc.h>定义。

2、构造对象由::construct()负责，对象析构由::destroy()负责，在<stl_construct.h>定义

//以下是第二级配置器__default_alloc_template定义
//notice:没有"template"类型参数，第二个参数没有派上用处
//第一个参数用于多线程环境下,目前不讨论
template <bool threads, int inst>
class __default_alloc_template
{
private:
    //ROUND_UP()将bytes提升至8的倍数
    static size_t ROUND_UP(size_t bytes)
    {
        return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
    }
private:
    union obj       //free_lists节点构造
    {
        union obj * free_list_link;
        char client_data[1];
    };
private:
    //16个free_lists
    static obj * volatile free_list[__NFREELISTS];
    //根据区块大小，决定使用第n号free-list, n从1算
    static size_t FREELIST_INDEX(size_t bytes)
    {
        return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
    }
    //返回一个大小为n的对象，并可能加入大小为n的其他区块到free list
    static void *refill(size_t n);
    //配置一大块空间，可容纳nobjs个大小为"size"的区块
    //如果配置nobjs个区块有所不便，nobjs可能会降低
    static char* chunk_alloc(size_t size, int& nobjs);

    // chunk allocation state
    static char *start_free;    //内存池起始位置
    static char *end_free;      //内存池结束位置
    static size_t heap_size;    

public:
    static void * allocate(size_t n);
    static void deallocate(void *p, size_t n);
    static void * reallocate(void *p, size_t old_sz, size_t new_sz);
};
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = 0;

template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;

template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

template <bool threads, int inst>
typename __default_alloc_template<threads, inst>::obj * volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] = 
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

二、空间配置器在容器中的使用

   例如：STL中vector部分实现：

templete <class T,class Alloc = alloc>   //alloc定义如下

class vector{

    protected:
        // simple_alloc 定义如下
        typedef simple_alloc<value_type,Alloc> data_allocator; 

        void deallocate(){
            if(...)
                  data_allocator::deallocate( start,end_of_storage - start );
          }
    ...
}


//alloc定义：
//考虑到小型区块可能造成的内存破碎问题，SGI设计了双层级配置器
//SGI STL通过宏定义来决定是否使用一级空间配置器或二级空间配置器
#ifdef _USE_MALLOC  
    ...
    //令alloc为一级配置器
    typedef _malloc_alloc_template<0> malloc_alloc;
    typedef malloc_alloc alloc;

#else
    ...
    //令alloc为二级配置器
    typedef _default_alloc_template<_NODE_ALLOCATOR_THREADS,0> alloc;

#endif


//simple_alloc接口定义
//无论alloc被如何定义，SGI 仍定义一个包装接口，使配置器的接口能够符合STL规范：
//SGI STL容器全都使用这个simple_alloc接口
template<class T,class Alloc>
class simple_alloc{
    public:
        static T *allocate(size_t n){
            return 0==n?0:(T*) Alloc::allocate( n * sizeof(T) );
        }

        static T *allocate(void){
            return (T*) Alloc::allocate( sizeof(T) )
        }

        static void deallocate(T *p,size_t n){
            if(0 !=n ){
                Alloc::delallocate( p, n*sizeof(T) );
            }
        }

        static void deallocate(T *p){
            Alloc::deallocate(  p,sizeof(T) );
        }
}

三、二级配置器 _default_alloc_template::allocate( ) 实现机制：

1、小的内存需求，就直接从free-lists直接拔出。如果需要释放小额区块，就有配置器回收到free-list中。free-lists管理16中小额区块，各自管理大小分别为8,16,24,32,40,48,56,64,72,80,88,96,1,04,112,120,128

2、为了方便管理，SGI第二配置器会主动将任何小额区块上调至8的倍数，比如需要分配30bytes，实际分配32bytes。

3、代码：

template<bool threads, int inst>
void * __default_alloc_template<threads, inst>::allocate(size_t n)
{
    obj * volatile *my_free_list;
    obj * result;
    //大于128字节就调用第一级配置器
    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;
    }
    //调整free list
    *my_free_list = result->free_list_link;
    return (result);
}


//返回一个大小为n的对象，并且可能会为适当的free_list增加节点
//假设size已经适当上调至8的倍数
template <bool threads , int inst>
void *__default_alloc_template<threads , inst>::refill(size_t n)
{
	int nobjs = 20;
	char *chunk = chunk_alloc(n , nobjs)
	Obj * volatile *my_free_list;
	Obj * result;
	Obj * current_obj , *next_obj;
	int i;
 
	if( nobjs == 1)
		return chunk;
	my_free_list = free_list + FREELIST_INDEX(n);
	result = (Obj *)chunk;
	*my_free_list = next_obj = (Obj *)(chunk + n);
	for (i = 1 ; ; ++i ) {
		current_obj = next_obj;
		if (nobjs - 1 == i){
			current_obj -> free_list_link = 0;
			break;
		}
		else {
			current_obj->free_list_link = next_obj;
		}
	}
}


//假设size已经适当上调至8的倍数
//注意参数nobjs是pass bu reference
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::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 bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        //以下试着让内存池的残馀零头还有利用价值
        if(bytes_left > 0)
        {
            //内存池还有一些零头，先配置给适当的free_list
            //首先寻找适当的free_list
            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;
        }

        //配置heap空间，用来补充内存池
        start_free = (char*)malloc(bytes_to_get);
        if(0 == start_free)
        {
            //heap空间不足，malloc()失败
            int i;
            obj *volatile * my_free_list, *p;
            //搜索适当的fee_list
            //适当即"尚有未用区块。且区块足够大"
            for(i = size; i <= __MAX_BYTES; i += __ALIGN)
            {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if(0 != p)
                {
                    //free_list 内尚有未用区块
                    //调整free_list以释放未用区块
                    *my_free_list = p->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free + i;

                    return (chunk_alloc(size, nobjs));
                }
            }
            end_free = 0;
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
        }
        heap_size += bytes_to_get;
        end_free = start_free + bytes_to_get;

        return (chunk_alloc(size, nobjs));
    }
}

4、 总结为七种情况：

     1、分配空间大于 128 bytes，调用级空间配置器（对malloc( )的简单封装）(清况1)

           若分配空间小于  128 bytes ：根据的自由链表下标分配空间：

     2、自由链表对应 free_list 指向不为空，说明有未用空间，调整free_list,分配空间  (清况2)

           若自由链表对应free_list 指向为空，调用 refill( ) 函数，从内存池分配空间：

     3、内存池空间大于要分配空间   （ bytes_left  >= total_bytes ）,调整内存池位置(start，end )  (清况3)

     4、内存池空间只能放一个数据（bytes_left  >=  size）,分配并调整内存池位置  (清况4)

          若一个数据都放不下（bytes_left < size），将内存池中的残余空间先编入（头插到 free_list），并用malloc ( )来分配空间：

      5、malloc( )分配成功，调整内存池位置，递归调用chunk_alloc( )进行分配  (清况5)

           若malloc( )分配失败，在free_list 寻找有无“未用区块”：

      6、free_list 有可用区块，调整free_list 以释放未用区块，调整内存池位置，递归调用chunk_alloc( )进行分配  (清况6)

      7、free_list 无可用区块，此时山穷水尽，调用一级空间配置器，看看 out_of_memory 机制能否尽力  (清况7)

 四、空间释放函数_default_alloc_template::deallocate( )函数 

static void deallocate(void *p, size_t n)
{
    obj *q = (obj *)p;
    obj *volatile * my_free_list;
    //大于128就调用第一级配置器
    if( n > (size_t)_MAX_BYTES ){
        malloc_allocL::deallocate(p,n);
        return ;
    }
    //寻找对应的free_list
    my_free_list = free_list + FREESLIST_INDEX(n);
    //调整free_list,回收区块
    q->free_list_link = *my_free_list;
    *my_free_list= q;
    
}

五、构造对象函数::construct( ) 

#include <new.h>

template <class T1, class T2>
inline void construct(T1 *p ,const T2 &value)
{
    new (p) T1(value);    //placement new; 调用T1::T1(value);
}

六、析构对象函数::destroy( ) 

//第一版本，接受一个指针，直接调用析构函数全部析构
template <class T>
inline void destroy(T* pointer) 
{
    pointer->~T();
}

//以下是destroy()第二版本，接受两个迭代器
//该函数设法找出元素的数值型别，进而利用__type_traits<>求取最适当措施
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
  _destroy( first, last, value_type(first) );
}

//判断元素的数值型别(value_type)是否有trivial 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() );
}

//如果元素型别为non-trivial destructor(有意义)，逐一删除元素
template <class ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last, false_type)
{
  for ( ; first != last; ++first)
       destroy(&*first);
}

//如果元素型别为trivial destructor(无伤大雅)，什么也不做
template <class ForwardIterator>
inline void _destroy_aux(ForwardIterator, ForwardIterator, true_type) {}

//以下是destroy()第二版本针对迭代器为char *和wchar_t的特化版
inline void destroy(char *,char *){}
inline void destroy(wchar_t *,wchar_t *) {}
c++ STL 空间配置器 allocate  deallocate destroy
上一篇: 2.6 使用dd命令安装Linux系统
下一篇: 2.3 为什么建议使用虚拟机来安装Linux？

继续阅读