`
xitonga
  • 浏览: 579378 次
文章分类
社区版块
存档分类
最新评论

STL空间配置器

 
阅读更多

空间配置器

标准规范规定,STL空间配置器是一个名为allocator的模板类,同时也规定了它的必要接口,也就是说allocator类定义形式如下。其中接口allocator::allocate(),allocator::deallocate(),allocator::construct,allocator::destory()这四个接口及其重要。所以我们这里主要分析这四个接口。此外,rebind接口比较难懂,可参见http://blog.csdn.net/walkerkalr/article/details/22263351

template<classT>

class allocator{

}

SGISTL在这个项目上脱离了STL标准,使用一个专属的,拥有次层分配能力的、效率优越的特殊配置器。其名称为alloc而非allocator,而且不接受任何参数。所有SGI STL的容器默认的空间配置器为alloc。虽然SGI也定义有一个符合部分标准、名为allocator的配置器,但SGI从未使用过他,因为SGI的allocator只是在::operator new和::operator delete做了一层薄薄的包装而已,效率不佳。以下提到的allocator指STL 空间配置器,不是SGI的allocator。

SGI特殊的空间配置器,std::alloc

一般用new构造一个对象,先要配置内存,然后调用构造函数。用delete删除一个函数,先要将对象析构,然后释放内存。在STL allocator,内存配置由alloc::allocate()负责,内存释放由alloc::deallocate()负责;对象构造由::construct()负责,对象析构操作由::destroy()负责。

STL配置器定义于<memory>中,SGI<memory>内含以下两个文件

#include<stl_alloc.h>

#include<stl_construct.h>

构造和析构:construt()和destroy()

<stl_construct.h>中定义了construt()和destroy()两个函数,用来构造和析构对象。其中construt()使用placemen new运算子来完成。destroy()有两个版本,一个版本直接调用对象的析构函数即可,另一个需要将一个范围的的对象全部析构。但如果在一个范围内析构对象时,析构函数无关痛痒,多次调用析构函数会影响效率,这里destroy()通过_type_traits<>技术来判断应该在循环中对所指范围内的每一个对象调用destroy(),还是什么也不做就结束。有关_type_traits<>会在后面加以讨论。以下是construct和destroy的示意图:


以下是<stl_construct.h>的部分内容。

#include <new.h>		// 欲使用placement new,需先包含此文件

__STL_BEGIN_NAMESPACE

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

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

// 如果元素的数值型别(value type)有 non-trivial destructor…
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
  for ( ; first < last; ++first)
    destroy(&*first);
}

// 如果元素的数值型别(value type)有 trivial destructor…
template <class ForwardIterator> 
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

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

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

// 以下是destroy() 第二个版本针对迭代器char* 和 wchar_t* 的特化版
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

__STL_END_NAMESPACE

关于palcement new,operator new, new operator可参见http://blog.csdn.net/walkerkalr/article/details/22280895

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

内存配置和释放是由<stl_construct.h>负责。SGI设计了双层级配置器。第一层直接使用malloc()和free(),第二级则视情况采用不同的策略:当配置区块超过128bytes时,便调用第一级配置器;当配置器小于128时,采用了复杂的memory pool整理方式。SGI STL默认采用第二级配置器。但SGI也设置了通过定义_USE_MALLOC宏来直接调用第一级配置器。第一级和第二级配置器关系可见以下两个示意图:



第一级配置器__malloc_alloc_template

第一级配置器主要由__malloc_alloc_template类实现,主要以malloc()、free()、realloc()等C函数执行实际的内存配置、释放、重配置操作,并实现了类似C++ new-handler的机制。它不能使用C++ new-handle机制,是因为它并非使用::operator new来配置内存。当malloc()和alloc()调用不成功后,改调用oom_malloc()和oom_realloc(),这两个函数在内部不断调用内存不足机制所实现的功能,但如果类似C++ new-handler的机制没有实现具体的例程,便会抛出bad_alloc异常或利用exit(1)终止程序。以下是其实现代码:

// 以下是第一级配置器
// 注意:无“template”型别参数,非型别参数inst完全没有排上用场。
template <int inst>
class __malloc_alloc_template {

private:
//以下三个函数用来处理内存不足的情况
static void *oom_malloc(size_t);

static void *oom_realloc(void *, size_t);

#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    static void (* __malloc_alloc_oom_handler)();
#endif

public:

static void * allocate(size_t n)
{
    void *result = malloc(n);	// 第一级配置器直接使用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()
    if (0 == result) result = oom_realloc(p, new_sz);
    return result;
}

//以下类似C++的set_new_handler().换句话说你可以通过它指定自己的out-of-memory handle
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;
    return(old);
}

};

// malloc_alloc out-of-memory handling
// __malloc_alloc_oom_handler初值设为0,有待客户定义
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
#endif

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;

第二级配置器 __default_alloc_template剖析

第二级配置器由__default_alloc_template类负责,该配置器做法是:如果区块大于128bytes,就调用第一级配置器。当小于128bytes时,则以内存池管理,每次配置一大块内存,并维护对应的自由链表free-list。下次若再有相同大小的内存需求,就直接从free-lists中拨出。如果客户释放小额区块,就由配置器回收到free-lists中。为了管理方便,配置器会将主动将任何小额区块的内存需求量上调到8的倍数,并维护16个free-lists,各自管理大小分别为8,16,24,32,40,48,56,83,81,88,96,104,112,120,128bytes的小额区块。free-lists节点结构如下:

union obj{

union obj* free_list_link;

char client_data[1];

};

其示意图如下:


__default_alloc_template该类成员函数allocate()首先判断区块大小,大于128就调用第一级配置器,小于就检查就检查对于的free-list。如果free-list中有可用区块,就直接拿来用,如果没有可用区块,就将区块大小上调值8的倍数边界,然后调用refill(),准备为free list重新填充空间。Refill()将调用chunk_alloc()从内存池中取新的空间给free-list。chunk_alloc()默认取得20个新的区块给free-list,但如果内存池空间不足,获得的节点数可能小于20。chunk_alloc()函数先判断内存池水量是否充足。如果充足,就直接调用20个区块返回给free list。如果水量不足提供20个区块,但还足够提供一个以上的区块,就拨出这不足20个区块的空间出去。如果内存池连一个区块都无法供应,对客户显然无法交代,此时需要利用malloc()从system heap中配置内存,为内存池注入源头活水以应付需求。新水量的大小为需求量的两倍,再加上一个随着配置次数增加而愈来愈大的附加量。新水量会将20个区块大小拨给给free list后,将多出来的20多个区块留给内存池。但万一,system heap空间都不够了,malloc()行动失败,chunk_alloc()就会遍历指向比所需区块大的free lists,找到一个就挖出来,找不到就调用第一级配置器,第一级配置器有out-of-memory处理机制(即类似C++ new-handler的机制),利用这种机制或许有机会释放其他的内存拿来此处使用。如果可以就成功,否则发出bad_alloc异常。

// 以下是第二级配置器
//注意:无“template”型别参数,非型别参数inst完全没有排上用场。
template <bool threads, int inst>
class __default_alloc_template {

private:
# ifndef __SUNPRO_CC
    enum {__ALIGN = 8};		// 小型区块的上调边界
    enum {__MAX_BYTES = 128};	// 小型区块的上限
    enum {__NFREELISTS = __MAX_BYTES/__ALIGN};		// free-lists 个数
# endif
//ROUND_UP将bytes上调至8的倍数
  static size_t ROUND_UP(size_t bytes) {
        return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
  }
private:
  union obj {
        union obj * free_list_link;
        char client_data[1];    /* The client sees this. */
  };
private:
# ifdef __SUNPRO_CC
    static obj * __VOLATILE free_list[]; 
        // Specifying a size results in duplicate def for 4.1
# else
//16个free-lists
    static obj * __VOLATILE free_list[__NFREELISTS]; 
# endif
	//以下函数根据区块大小,决定使用第n号free-list。n从0开始
  static  size_t FREELIST_INDEX(size_t bytes) {
        return (((bytes) + __ALIGN-1)/__ALIGN - 1);
  }

  // Returns an object of size n, and optionally adds to size n free list.
  //返回一个大小为n的对象,并可能加入大小为为n的其他区块到free list
  static void *refill(size_t n);
  // Allocates a chunk for nobjs of size "size".  nobjs may be reduced
  // if it is inconvenient to allocate the requested number.
//配置一大块空间,可容纳nobjs个大小为”size”的区块
//如果配置nobjs个区块有所不便,nobjs可能会降低
  static char *chunk_alloc(size_t size, int &nobjs);

  // Chunk allocation state.
  static char *start_free;	//内存池起始位置。只在chunk_alloc()中变化
  static char *end_free;	//内存池结束位置。只在chunk_alloc()中变化
  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){/*详述于后*/}
}
//下面是static data member的定义于初值设定
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>
__default_alloc_template<threads, inst>::obj * __VOLATILE
__default_alloc_template<threads, inst> ::free_list[
# ifdef __SUNPRO_CC
    __NFREELISTS
# else
    __default_alloc_template<threads, inst>::__NFREELISTS
# endif
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };
//标准接口函数allocate()
static void * allocate(size_t n)
  {
    obj * __VOLATILE * my_free_list;
    obj * __RESTRICT 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);
  };
//标准接口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_alloc::deallocate(p, n);
        return;
}
//寻找对于的free list
    my_free_list = free_list + FREELIST_INDEX(n);
//调整free list,回收区块
    q -> free_list_link = *my_free_list;
    *my_free_list = q;
}

// reallocate实现
template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void *p,
                                                    size_t old_sz,
                                                    size_t new_sz)
{
    void * result;
    size_t copy_sz;
//如果old_sz,new_sz都大于128bytes
    if (old_sz > (size_t) __MAX_BYTES && new_sz > (size_t) __MAX_BYTES) {
        return(realloc(p, new_sz));	//直接调用realloc()
}
//如果新旧内存大小相等,不作处理
if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return(p);
//否则调用allocate()来分配新内存大小
result = allocate(new_sz);
//如果新内存大于旧内存空间大小,将新内存全部复制;
//否则在旧内存空间中拷贝新内存大小的数据
    copy_sz = new_sz > old_sz? old_sz : new_sz;
    memcpy(result, p, copy_sz);
    deallocate(p, old_sz);
    return(result);
}

/* Returns an object of size n, and optionally adds to size n free list.*/
/* We assume that n is properly aligned.                                */
/* We hold the allocation lock.                                         */
// refill的实现:返回一个大小为n的对象,并且有时会为适当的free list增加节点
//假设n已经适当上调至8的倍数
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
int nobjs = 20;
//调用chunk_alloc(),尝试取得nobjs个区块作为free list的新节点
//注意参数nobjs是pass by eference
    char * chunk = chunk_alloc(n, nobjs);	//详述于后
    obj * __VOLATILE * my_free_list;
    obj * result;
    obj * current_obj, * next_obj;
    int i;
	//如果只获得一个区块,这个区块就分配给调用者,free list无新节点
if (1 == nobjs) return(chunk);
//否则准备调整free list,纳入新节点
    my_free_list = free_list + FREELIST_INDEX(n);

    /* Build free list in chunk */
     //以下在chunk空间内建立free list
  result = (obj *)chunk;
//以下引导free list指向新配置的空间(取自内存池)
      *my_free_list = next_obj = (obj *)(chunk + n);
//以下将free list各节点串接起来
      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);
}

内存基本处理工具

基本处理工具有uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n(),他们的实现也都用到了__type_traints技术,其实现示意图如下:


==转载请注明出处,谢谢!

分享到:
评论

相关推荐

    stl_alloc.h(加注释)

    下载的stl_alloc.h源码,自己加了注释,有助于理解stl空间配置器

    C++ 后台工程师面试宝典

    再硬核|5 千字长文+ 30 张图解 | 陪你手撕 STL 空间配置器源码 硬核|万字长文炸裂!手撕 STL 迭代器源码与 traits 编程技法 超硬核 | 2 万字+20 图带你手撕 STL 序列式容器源码 硬核来袭 | 2 万字 + 10 图带你手撕 ...

    内存池(MemPool)

    按照STL空间配置器的思想实现的一个内存池模块,附带了几个简单测试示例。

    标准模板库STL

    一份讲解全面的标准...为STL提供空间配置的系统。 头文件中的主要部分是模板类allocator,它负责产生所有容器中的默认分配器。容器使用allocator完成对内存的操作,allocator提供内存原语以对内存进行统一的存取。

    STL源码剖析.pdg

    2.2 具备次配置力(sub-allocation)的sgi 空间配置器 047 2.2.1 sgi 标准的空间配置器,std::allocator 047 2.2.2 sgi 特殊的空间配置器,std::alloc 049 2.2.3 构造和析构基本工具:construct() 和 destroy() ...

    STL源码剖析完整版

    疱丁解牛(侯捷自序) 前言 第1章 STL概论与版本简介 第2章 空间配置器(allocator) 第3章 迭代器(iterators)概念与traits编程技法 第4章 序列式容器(sequence containers) 第5章 关联式容器(associattive ...

    STL模板与容器资料

    STL模板与容器资料,容器包含vector,list,deque,set,stack等等,模板主要介绍了函数模板和类模板两种

    my-mem-pool:剖析和注释SGI STL二级空间配置器源码与nginx内存池源码,并使用C ++ OOP进行仿写

    我的内存池通过剖析的开源代码可以积累优秀的代码设计思想和良好的编程规范,了解不同的应用场景下不同的内存池实现也是一种重要的能力,本仓库对SGI STL二级空间配置器内核和nginx内存池内核进行了剖析,并使用C ++...

    STL:STL原始码分析

    SIG STL源码分析 前言 本专栏主要以STL源码剖析分析路线来分析SIGSTL3.0源码。...而STL就实现了这样的一个功能,它就是空间配置器。而空间配置器一般是隐藏在各个版本块的组件,实现中我们都看不到它的存在,但是它

    STL源码剖析简体中文完整版(清晰扫描带目录).pdf

    第1 章 STL 概论与著作版本简介 第2 章 空间配置器(allocator) 第3 章 迭代器(iterators)概念与 traits 编程技法 第4 章 序列式容器(sequ ence containers) 第5 章 开关式容器(associated containers) 第6 ...

    STL 源码剖析(侯捷先生译著)

    2.2 具备次配置力(sub-allocation)的SGI 空间配置器 047 2.2.1 SGI 标准的空间配置器,std::allocator 047 2.2.2 SGI 特殊的空间配置器,std::alloc 049 2.2.3 构造和析构基本工具:construct() 和 destroy() ...

    STL模板,常用容器.docx

    1,STL的六大组件:容器container,算法algorithm,迭代器iterator,仿函数,适配器(配接器),空间配置器,,容器和算法是通过迭代器进行无缝连接起来的,STL几乎所有代码都采用了模板类或模板函数。 (1).容器:...

    STL-:SGI STL的二进制剖析以及直接封装的空间配置器代码

    STL-:SGI STL的二进制剖析以及直接封装的空间配置器代码

    AVL_Tree实现STL中的map, set, multimap和multiset

    用AVL-tree数据结构作为底层机制,以STL底层空间配置器和iterator_traits编程技法实作出一个独立的关联式容器(map, set, multimap, multiset),并对外提供接口实现和STL完全兼容的容器。

    SGI_STL-allocate-:这个是我看了SGI_STL源码后,模拟的空间配置器,里面用到了C11的互斥锁,所以大家想用可以在C11下使用

    SGI_STL-分配-这个是我看了SGI_STL源码后,模拟的空间配置器,里面用到了C11的互斥锁,所以大家想用可以在C11下使用。

    C++STL.xmind

    C++stl高级部分思维导图,STL六大组件的交互关系,容器通过空间配置器取得数据存储空间,算法通过迭代器存储容器中的内容,仿函数可以协助算法完成不同的策略变化,适配器可以修饰仿函数

    《STL源码剖析》(候捷 著)

    第2章 空间配置器(allocator) 第3章 迭代器(iterators)概念与traits编程技法 第4章 序列式容器(sequence containers) 第5章 关联式容器(associattive containers) 第6章 算法(algorithms) 第7章 仿函数...

    STL远吗解析

    想想解析c++标准函数,STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函数(functors)六个部分。

    STL源码剖析

    第2章 空间配置器(allocator) 第3章迭代器(iterators)概念与traits编程技法 第4章 序列式容器(sequence containers) 第5章 关联式容器(associattive containers) 第6章 算法(algorithms) 第7章 仿函数...

Global site tag (gtag.js) - Google Analytics