【STL代码剖析】总结笔记（4）：幕后功臣--分配器（allocator）

00 写在前面

【STL代码剖析】总结笔记（3）：vector初识

在前面对于vector的分析中，我们遇到了allocator

template

分配器是贯穿所有容器的存在，即使我们在使用各个容器时并不会用到它，但在背后的空间配置都是分配器的功劳。

这次让我们读懂allocator的原理，帮助我们更好地理解STL。

01 malloc()

所有的分配在最终都会走到malloc()

在c++的层面上也就是operator new()，其底层也是调用了malloc()

你所要的大小只有fill这么大，但malloc会搭配一些其他必要的东西。

所以这就意味着申请空间越大，附加东西比例越小，申请空间小则占用比例越大。

02 概述

再回到allocator的实现，那么allocator的底层也应该是由malloc()支撑的。

先看一个VC的版本：

观察allocator类

class alloctor{
    ...
    pointer allocate(size_type n,const void *)
    	{return (Allocate((difference_type) n,(pointer)0));}
    void deallocate(pointer p,size_type n)
    	{operator delete(p)}
}

allocate调用了Allocate

再看Allocate

template inline
...Allocate(...){
    return ...operator new(...)
}

也就说明VC中allocator底层就是使用malloc()和free()实现的。

先说说为什么allocator我们不常用

因为在分配和释放空间时，都需要声明多少个元素，分配时可定义，但释放时一般不会记得，所以比较难用。
像VC的这种实现方法也会引出一个问题：当元素很小但很多时，额外开销不会很大？

当然是会的。这样就会导致额外开销很大，在这种情况下浪费大量空间。

03 SGI STL中的alloc

在SGI STL中的配置器解决了我们上面提到的这个问题。它也与标准的规范不同，其他分配器使用allocator，而SGI STL中的命名为alloc。

而且不接受任何参数。

比如标准写法为：

vector>iv;

但使用SGI STL allocator就要这样写：

vectoriv;

虽然没能符合标准，但是实际使用起来问题不大，因为在底层都会自行指定分配器，比如开头所说的vector

template

在c++中，内存配置和释放是一套连贯的操作。比如：

class Foo{...};
    Foo *pf = new Foo;
    delete pf;

这里的new操作是两个操作的组合：1.配置内存 2.构造对象

delete操作也是两个操作的组合：1.析构对象 2.释放内存

在STL allocator中将这两个阶段的操作分开，分为对象的构造和析构与空间的配置与释放。

文件结构如下：

#include //负责内存空间的配置与释放
#inlcude //负责对象内容的构造与析构
#inlcude //定义了一些全局函数，用来拷贝填充大块内存

我们前面在vector遇到的处理内存的基本工具就定义在stl_uninitialized.h里面

04 对象的构造与析构：construct()&destroy() construct()

构造函数的实现比较简单：

template 
inline void construct(T1 *p,const T2& value){
    new (p) T1 (value);
}

作用就是将初值value设定到指针所指向的空间。

destroy()

析构函数有两个版本。

第一个版本：

template 
inline void destroy(T* pointer){
    point->~T();
}

比较好理解，直接析构掉指针所指的对象。

第二个版本想要析构迭代器[first,last)范围内的对象，有一些情况的判断：

template 
inline void destroy(ForwardIterator first,ForwardIterator last){//1
    _destroy(first,last,value_type(first));
}

template 
inline void _destroy(ForwardIterator first,ForwardIterator last,T*){//2
    typedef typename _type_traits::has_trivial_destructor trivial_destructor;
    _destroy_aux(first,last,trivial_destructor());
}

template 
inline void _destroy_aux(ForwardIterator first, ForwardIterator last,_false_type){//3
    for(;first
inline void _destroy_aux(ForwardIterator first, ForwardIterator last,_true_type){}//4

下面我们来解读一下这段“套娃”代码。

首先要知道的是trivial destructor。因为我们想要析构的是一个范围，如果这其中每个对象的析构函数都不重要，那么就称为trivial destructor。

所以我们想知道是否需要析构，这样可以避免反复调用。

这里利用value_type()来获取迭代器所指对象的类型
再利用_type_traits来判断是否需要析构函数。这里调用has_trivial_destructor来判断是否为trivial destructor
如果是false_type，那么需要析构
如果是true_type，那么说明不需要析构，直接空操作

## 05 空间的配置与释放：alloc

这里展现了alloc巧妙的设计，也解决了我们前面提到的内存问题。

考虑到小型区块可能造成内存破碎的问题，SGI设计了双层配置器。

第一级配置器采用常用的直接使用malloc()和free()的方法。

第二级配置器则是根据情况采用不同策略：当配置区块超过128bytes时，调用第一级配置器；当配置区块小于128bytes时，采用memory pool整理方式。

第一级配置器

第一级配置器定义为__malloc_alloc_template

由于代码较长，我们之间探讨第一级配置器做了什么。

static void allocate(...){
    直接使用malloc();
    无法满足要求时改用oom_malloc();
}

static void deallocate(...){
    直接使用free();
}

static void reallocate(...){
    直接使用realloc();
    无法满足要求时改用oom_realloc();
}

static void (*set_malloc_handler(...)){...}//仿真c++set_new_handler机制

oom_malloc(),oom_realloc()都是用来处理内存不足的情况的，内部会不断尝试释放内存，再重新尝试配置。（调用set_malloc_handler)

set_malloc_handler类似于c++中的set_new_handler机制，即你可以要求系统在内存配置要求无法被满足时调出一个你指定的函数，也就是在丢出异常前先调用客户端指定的处理例程。

因为c++并未提供realloc()的内存配置，所以要仿真一个set_malloc_handler()

oom_malloc(),oom_realloc()就是一直尝试调用我们前面说的客户端指定处理例程。当然如果没有设定，就会抛出bad_alloc异常信息。（只要严格遵守new对应delete的操作就不会出现问题）

第二级配置器

第二级配置器我们需要重点关注小于128bytes的处理方法。这也是能解决内存破碎问题的关键。

基本原理就是每次配置一大块内存，并维护其自由链表（free-lists），下次的需求可以直接从自由链表中取出。如果客户端返回小额区块，就将其收回。

第二级配置器会主动将小额区块的内存需求量上调至8的倍数。比如需求为30bytes，会自动调整为32bytes.链表维护的都是大小为8的倍数的区块，需要时取出即可。

同时维护16个free-lists，分别为8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128.（对就是8的1到16倍）

主要实现如下：

template 
class _default_alloc_template{
    private:
    	static size_t ROUND_UP(size_t bytes){//将bytes上调至8的倍数
            ...
        }
    
    private:
    	union obj{//free-list节点构造
            union obj *free_list_link;
    	char client_data[1];
        };
    
    private:
    	static obj * volatile free_list[_NFREELIST];
    	static size_t FREELIST_INDEX(size_t bytes){...}//决定使用第n号free-list
    
    private:
    	static void *refill(size_t n);//没有可用区块重新填充
    	static char *chunk_alloc(size_t size,int &nobjs);
    
    public:
    	static void * allocate(size_t n){...}
    	static void dellocate(void *p,size_t n){...}
    	static void * reallocate(void *p,size_t old_sz,size_t new_size);
    	
};

而主要内容是空间配置的相关操作。

allocate()

此函数首先判断区块大小，大于128bytes就调用第一级配置器，小于128bytes就使用free-list，有可用区块就拿来用，没有就将大小上调至8倍数边界，再调用refill()

比如上图示例，首先根据大小为96bytes找到free-list[11]，然后将解引用的取值赋给result，最后重新调整链接关系，再返回result。

static  void* allocate(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);//寻找16个free-list中适合的一个
    result=*my_free_list;
    if(result==0){//没有可用，重新填充
        void * r=refill(ROUND_UP(n));
    }
    
    *my_free_list=result->free_list_link;//重新调整free-list，指向下一个区块
    return (result);
    
};

deallocate()

回收区块即把区块再添加到链表中。

首先让q指向要回收的区块，然后找到对应的free-list，再将区块加入链表，最后调整free-list。

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;//调用第一级配置器
    }
    
    my_free_list=free_list+FREELIST_INDEX(n);//寻找16个free-list中适合的一个
    q->free_list_link=*my_free_list;//回收区块
    *my_free_list=q;//调整free-list
}

refill()

在没有可用区块的时候会进行重新填充，新区块取自内存池，由chunk_alloc()完成。

这里简单写一下refill的工作流程:

refill(size_t n){
    int 区块=20;
	调用chunk_alloc()，尝试取得20个区块作为free-list的新节点

	if(只获得一个区块)
    	就把这个区块分配给调用者，free-list无新节点
	否则free-list准备纳入新节点
    
	在chunk空间内建立free-list：
    	第0块返回给客端
    	从第一块开始将各节点串起来
}

内存池

从内存池中取空间给free-list使用是chunk_alloc()干的事。

再说说chunk_alloc()的工作流程

chunk_alloc(size_t size,int &nobjs){
    首先用end_free-start_free来判断内存池的容量
    
    if(内存池空间满足需要)
        调出20个区块给free-list
        
    else if(内存池空间不能满足需求，但是可以供应一个及以上的区块)
        有多少调用多少，然后修改nobjs为实际值
        
    else(内存池连一个区块的大小都无法提供){
        如果有点残存的空间，可以先找到合适的free-list并且分配给它
      	从heap中分配内存：
            足够的话分配需求量两倍的空间（还有附加量）
            不够的话看看free-list还有没有没使用的空间
           	还是没有只能调用第一级配置器，看看out of memory有没有什么办法
    }
        
     	
}

举个例子：

首先调用chunk_alloc(32,20)，即从内存池中取20个32bytes的空间。

于是malloc()配置40个32bytes的区块。第一块返回给客户端，其余的由free-list[3]维护。剩下的交给内存池（20个）
再=调用chunk_alloc(64,20)，即从内存池取出20个64bytes的空间。因为现在free-list[7]为空，所以需要内存池提供。内存池只能供（32*20）/64=10个。于是第一块返回给客户端，其余由free-list[7]维护。内存池什么都不剩了。
调用chunk_alloc(96,20)，即从内存池中取出20个96bytes的空间。因为free-list[11]为空，内存池也空，所以需要malloc()40+n(附加量)的96bytes区块，还是第一个返回给客户端，其余的交给free-list[11]维护，剩下的20+n由内存池管理。

06 总结

allocator更多的重点内容在【内存管理】处会有更详细地解释。后面也基本不会在明面上遇到allocator。

重点是第二级配置器的处理方法，需要掌握。

【STL代码剖析】总结笔记（4）：幕后功臣--分配器（allocator）

C/C++/C#相关栏目本月热门文章