STL笔记（5）——空间配置器Allocator（三）

ゞ浴缸里的玫瑰 2022-08-21 02:04 126阅读 0赞

# STL笔记（5）——空间配置器Allocator（三） #

## 概述 ##

STL中提供一级配置器和二级配置器，当配置区块大于128 bytes时，则使用一级配置器，否则使用二级配置器。  
在STL中不论一级配置器还是二级配置器，都被重命名为**`alloc`**，在源码中有如下定义：

typedef __malloc_alloc_template<0> malloc_alloc;//第一级配置器
    # ifdef __USE_MALLOC
    typedef malloc_alloc alloc;
    # else
    typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;//第二级配置器

## 第一级配置器 ##

一级配置器比较简单，它直接使用**`malloc()`和`free()`**这两个函数，不过，需要模拟一个C++ new handler机制（当内存配置无法要求时的一个操作或者函数）

/*stl_alloc.h*/
    //第一级配置器使用的是malloc、realloc、free等c函数执行实际的内存配置、释放、重配置操作，
    //所以不能使用set_new_handler（这是operator new的东西），
    //而是需要自己仿照set_new_handler来编写设置处理函数。
    //用来处理内存不足的情况 oom: out_of_memory
    static void* _S_oom_malloc(size_t);
    static void* _S_oom_realloc(void*, size_t);
    
    #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
      static void (* __malloc_alloc_oom_handler)();
    #endif

之前书中提到作为一个空间配置器需要实现的一些结构，其中就包括**`allocate()`**等函数：

/*stl_alloc.h*/
     static void* allocate(size_t __n)
      {
        void* __result = malloc(__n);//第一级配置器直接使用了malloc()
        //内存不足使用oom_malloc
        if (0 == __result) __result = _S_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 = _S_oom_realloc(__p, __new_sz);
        return __result;
      }

第一级配置器源码中让我最头疼的就是它模拟的`set_new_handler`这一部分，实际上是用了函数指针的内容，写法上看起来就很晦涩：

/*stl_alloc.h*/
    static void (* __set_malloc_handler(void (*__f)()))()
    {
        void (* __old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = __f;
        return(__old);
    }
    //把上述函数改写一下。
    typedef void (*PF)(); //我们定义一个函数指针类型PF代表void (*)()类型
    static PF __set_malloc_handler(PF __f) {
        PF old = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = __f;
        return (old);
    }

以函数指针作为参数，返回函数指针，设置新的handler，并返回旧的handler.

通过上述函数模拟`set_new_handler()`  
例如：

/*stl_alloc.h*/
    // malloc_alloc out-of-memory handling
    //处理内存不足的情况函数指针直接设置0
    //类似set_new_handler(0)
    #ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
    template <int __inst>
    void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
    #endif

下述用法，循环使用`new_handler`处理，直到`new_handler==0`抛出异常

/*stl_alloc.h*/
    template <int __inst>
    void*
    __malloc_alloc_template<__inst>::_S_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);
        }
    }

## 第二级配置器 ##

第二级配置器多了一些机制，避免太多小额区块造成内存的碎片。小额区块不仅是内存碎片，还有配置时的额外负担。第二级配置器有点难懂，我自己的理解：  
1. 首先大于128 bytes 肯定交给以及配置器了，那么二级配置器做的事情都是小于等于128bytes的。  
2. 因为内存对其等原因小于等于128 bytes可以有16种情况，分别是8,16,32….128，都是8的倍数(16\*8=128)  
3. 先不考虑那个union的问题，维护了一个链表数组（大小当然是16），数组中每个元素都指向一个链表，而链表中的每个节点大小又固定，分别是8，16…128 bytes，例如freelist\[0\]中保存的指针指向节点为8bytes的链表。

然后就是细节了：  
首先是让我头痛很久的一个结构：

/*stl_alloc.h*/
    __PRIVATE:
      union _Obj {
            union _Obj* _M_free_list_link;//free-lists 节点，这种方式节省了使用传统结构体方式的指针开销4
            char _M_client_data[1]; //柔性指针   /* The client sees this.        */
      };

这种用法到底是什么意思？  
首先，一个普通的单链表，我们通常是这样写的：

typedef struct Node
    {
        ElemType data;              //单链表中的数据域 
        struct Node *next;          //单链表的指针域 
    }Node,*LinkedList;

它包括了数据域和指针域，而这两片区域是独立的。  
而union中的成员共用内存。  
`char _M_client_data[1]; //柔性指针`用\_M\_client\_data来表示一个地址，从客户端的角度来看它是数据的首地址，通常还可以写做`char _M_client_data[0]; //柔性指针`  
而从 `union _Obj* _M_free_list_link;`角度去看，它表示指向下一个结构的指针。

如何节约内存？  
先看其源码：

/*stl_alloc.h*/
    //1.如果大于128直接交给一级配置器
    //大于 128 bytes
    if (__n > (size_t) _MAX_BYTES) {
        __ret = malloc_alloc::allocate(__n);//直接调用第一级配置器
    }
    //2.小于128时，假设为n，先把n调整为8的倍数
    //上调至8的倍数
    static size_t
    _S_round_up(size_t __bytes) 
    { return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }//化为2进制计算
    
    //3.根据调整后的大小选择链表数组中不同的索引(index)
    //选择n号free-list   取决于bytes大小
    static  size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
    }
    
    //4.在不考虑refill的情况下，调整。
    //其实就是删除头结点的过程
    _Obj* __STL_VOLATILE* __my_free_list;
    _Obj* __RESTRICT __result = *__my_free_list;
    *__my_free_list = __result -> _M_free_list_link;
    __ret = __result;
    return __ret;

返回的\_\_ret指针所指向的地址就可以直接使用，由于这里使用union所以，\_\_ret的地址就等于\_\_ret->\_M\_client\_data，这里就省去了数据域和指针域区分的内存开销，一物两用。这就回答了这种方式如何节省开销了。

同样的，如果不用了，就要回收区块，前3步与allocator类似，最后回收区块实际就是往头结点之前插入节点的过程：

/*stl_alloc.h*/
    static void deallocate(void* __p, size_t __n)
    {
    if (__n > (size_t) _MAX_BYTES)//大于128 bytes直接调用第一级配置器
        malloc_alloc::deallocate(__p, __n);
    else {
        _Obj* __STL_VOLATILE*  __my_free_list= _S_free_list + _S_freelist_index(__n);//找到 freelist 序号
        _Obj* __q = (_Obj*)__p;
        __q -> _M_free_list_link = *__my_free_list;
        *__my_free_list = __q;//回收区块
        }
      }

注：在侯老师的书中不考虑多线程，因此锁的部分我直接删掉了。