STL-空间配置器分析（内存的配置和释放）

冷不防 2022-05-31 01:42 185阅读 0赞

#### 首先通过STL源码剖析中的一个插图有个初步的印象，接下来再详细解释。（由于是繁体，图中的记忆体也就是所谓的“内存池 ”） ####

![这里写图片描述][SouthEast]

--------------------

#### 一级空间配置器： ####

> 对malloc，free函数的简单封装；添加了增加\_malloc\_alloc\_oom\_handle处理机制对malloc失败后的情况进行了处理；

#### 申请内存： ####

> **1、void\* allocate(size\_t n) ：**调用malloc函数，如果malloc失败，调用\_S\_oom\_malloc(n)函数；否则malloc开辟成功返回；  
> **2、void\* reallocate(void\* \_p, size\_t new\_size)：**调用realloc函数，realloc失败，调用\_S\_oom\_malloc(n)函数；否则realloc开辟成功返回；

#### 释放内存： ####

> **void deallocate(void\* \_p)：**内部封装free函数。

--------------------

#### **一级配置器简化流程图：** ####

![这里写图片描述][SouthEast 1]

##### 简化后的源码分析如下： #####

template <int __inst> //预留，整个过程中都没有用到
    class __malloc_alloc_template {
    private:
        static void* _S_oom_malloc(size_t);     //malloc失败调用的函数
        static void(*__malloc_alloc_oom_handler)(); //用户自定义的处理内存不足的函数
    
    public:
        //如果申请成功，直接返回
        //申请失败调用_S_oom_malloc处理函数
        static void* allocate(size_t __n)
        {
            void* __result = malloc(__n);   
            if (0 == __result) __result = _S_oom_malloc(__n);
            return __result;
        }
    
        //释放空间直接调用free即可
        static void deallocate(void* __p)
        {
            free(__p);
        }
    };
    
    // malloc_alloc out-of-memory handling
    //初始值置为0，等待用户自定义释放内存函数
    template <int __inst>
    void(*__malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
    
    
    //之前malloc，realloc函数申请失败都会首先调用该函数
    template <int __inst>
    void* __malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
    {
        void(*__my_malloc_handler)();
        void* __result;
    
        //如果用户自定义了__malloc_alloc_oom_handler函数，则一直调用直到内存申请成功
        //若未定义__malloc_alloc_oom_handler函数，则直接抛出异常。
        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);
        }
    }

--------------------

#### **二级空间配置器：** ####

##### 二级空间配置器主要是为了解决外内存碎片的问题，所以引入了以下的结构： #####

##### **一、整体结构：** #####

> ##### 由start\_free和end\_free共同维护的一片狭义内存池，以及一个自由链表，该自由链表其实是一个指针数组，每个元素都可指向了一段分配好的内存块；由于是SGI3.0版本的STL，年代较久；当时认为128字节就是大块内存，所以将128分为16块； 每个下标下方对应的都是对应内存大小块的内存。 #####

##### 每个自由链表的节点类型： #####

union _Obj {
            union _Obj* _M_free_list_link;   /* 相当于是next指针 */
            char _M_client_data[1];    /* The client sees this.        */
      };

##### 图示结构如下： #####

##### 其中0,1,2代表的是下标，8,16,24则是该下标位置下挂的内存块所对应的大小 #####

![这里写图片描述][SouthEast 2]

--------------------

##### 简化后源码分析如下（只考虑单线程情况下） #####

enum {_ALIGN = 8}; //小块的上调边界
     enum {_MAX_BYTES = 128}; //小块边界的上限
     enum {_NFREELISTS = 16}; //first_list的个数
    
    template<bool threads, int inst> 
    //thread为true，代表多线程
    class _DeafaultAllocTemplate
    {
        //first-list的节点
        struct _Obj{
            _Obj* _freeListLink;    //相当于_next指针，指向下一块内存
        };
    
    private:
        //狭义内存池  start和end只在chunk函数中会改变
        static char* _startFree;
        static char* _endFree;
        static size_t _heapSize;
    
        //自由链表
        static _Obj* _freeList[_NFREELIST];
    
    private:
    
        //给申请内存块的大小，返回该大小在指针数组中对应的下标
        static size_t _GetFreeListIndex(size_t n)
        {
            //将整体值跃迁到下一个区间
            return ((n + _ALIGN - 1) / _ALIGN - 1);
        }
    
        //返回离n上调到最近的8的倍数 例如 n=7, return 8
        static size_t _RoundUp(size_t n)
        {
            return (n + _ALIGN - 1) & ~(_ALIGN - 1);
        }
    
        //在自由链表中获取内存块
        static void* _Refill(size_t n);
    
        //在内存池中申请内存nobjs个对象，每个对象内存大小为n，
        //nobjs为输出型参数，可用来判断实际开辟了几个内存块
        static char* _chunkAlloc(size_t n, int& nobjs);    
    
    public:
        //申请内存
        static void* Allocate(size_t n);
        //释放内存
        static void* DeAllocate(void* p, size_t n);
    };

--------------------

##### **二、关键成员函数分析：** #####

##### **<1>：Allocate函数：** #####

> ##### 判断所申请内存块大小是否大于128，如果大于128则直接调用一级空间配置；反之则将n上调至最近的8的倍数处，然后再去自由链表中相应的结点下面找，如果该结点下面还存在未使用的内存，则直接取下该块内存，返回内存地址；否则调用refill函数去内存池中申请，剩下的事就交给refill了。 #####

static void* allocate(size_t __n)
    {
        void* __ret = 0;
    
        //如果申请的内存块大小超过MAX_BYTES,就直接调用一级空间配置器
        if (__n > (size_t)_MAX_BYTES) {
            __ret = malloc_alloc::allocate(__n);
        }
        else 
        {
            //找到对应内存块大小的下标
            _Obj** __my_free_list = _S_free_list + _S_freelist_index(__n);
            _Obj* __result = *__my_free_list;
            //如果当前下标对应的链表中没有可用的内存块，就调用refill
            //refill函数会返回一块对应大小内存块的地址
            if (__result == 0)
                __ret = _S_refill(_S_round_up(__n));
    
            //有对应大小的内存块就直接从头上取一块返回
            else {
                *__my_free_list = __result->_M_free_list_link;
                __ret = __result;
            }
        }
        return __ret;
    };

## ![这里写图片描述][SouthEast 3] ##

##### **<2>：deallocate函数：** #####

> ##### deallocate函数作用就是按照申请内存块的情况，将对应的内存块归还给不同的地方；更详细的解释见下面 #####

static void deallocate(void* __p, size_t __n)
    {
        //如果归还内存块的大小大于MAX_BYTES
        //则说明开辟的时候就调用一级空间配置器，所以直接交给一级处理
        if (__n > (size_t)_MAX_BYTES)
            malloc_alloc::deallocate(__p, __n);
        //剩下的情况就是在freelist上取的内存块，则需要找到对应位置进行头插
        else {
            _Obj* __my_free_list = _S_free_list + _S_freelist_index(__n);
            _Obj* __q = (_Obj*)__p;
    
            __q->_M_free_list_link = *__my_free_list;
            *__my_free_list = __q;
        }
    }

![这里写图片描述][SouthEast 4]

--------------------

##### **<3>：refill函数：**重新填充自由链表 #####

> ##### STL默认一次申请nobjs=20个，将多余的挂在自由链表上，这样能够提高效率。进入refill函数后，先调chunk\_alloc(size\_t n,size\_t& nobjs)函数去内存池中申请，如果申请成功的话，再回到refill函数。由于nobjs是输出型参数，在chunk函数内部会根据申请的大块内存大小，确定nobjs的值。 #####
> 
> ##### 回到refill函数后就有两种情况，如果nobjs=1的话则表示内存池只够分配一个，这时候只需要返回这个地址就可以了。否则就表示nobjs大于1，则将多余的内存块挂到自由链表上。如果chunk\_alloc失败的话，在该函数内部有处理机制。 #####

template <bool __threads, int __inst>
    void* __default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
    {
        //初始nobjs为20，最好的情况下能一次开辟20个对应大小的内存块；剩下情况再处理
        int __nobjs = 20;
        //chunk_alloc向内存池申请空间，但是能成功申请的块数不定，通过输出型参数nobjs确定
        char* __chunk = _S_chunk_alloc(__n, __nobjs);
        _Obj** __my_free_list;
        _Obj* __result;
        _Obj* __current_obj;
        _Obj* __next_obj;
        int __i;
    
        //如果只成功申请了一块，则直接返回该块地址
        if (1 == __nobjs) return(__chunk);
    
        //用申请来的大块内存往自由链表中挂内存块
        __my_free_list = _S_free_list + _S_freelist_index(__n);
    
        //第一块记录下来返回
        __result = (_Obj*)__chunk;
    
        //将剩余的全部挂入链表下面
        *__my_free_list = __next_obj = (_Obj*)(__chunk + __n);
        for (__i = 1; ; __i++) {
            __current_obj = __next_obj;
            __next_obj = (_Obj*)((char*)__next_obj + __n);
            if (__nobjs - 1 == __i) {
                __current_obj->_M_free_list_link = 0;
                break;
            }
            else {
                __current_obj->_M_free_list_link = __next_obj;
            }
        }
        return(__result);
    }

--------------------

##### **<4>：chunk\_alloc函数：**处理内存池的问题，返回大块内存给refill函数使用。 #####

> ##### 在chunk\_alloc函数中存在三种情况 #####
> 
> ##### 1、内存池剩余空间足够开辟20\* n的空间，直接分配返回给refill函数使用； #####
> 
> ##### 2、内存池剩余空间至少能够分配一个大小为n的大块内存，但是不够20个，重新计算nobjs，分配并返回； #####
> 
> ##### 3、内存池空间不足n，先将内存池剩余空间挂到对应自由链表中，再次malloc申请空间。 #####
> 
> ##### 3.1若此时malloc成功，再次调用chunk\_alloc分配内存返回； #####
> 
> ##### 3.2若malloc失败，去比当前n大的自由链表中找闲置的内存块：如果有，则将该块内存返回给内存池，再次调用chunk\_alloc；否则调用一级空间配置器，期待内存不足处理机制能否处理。 #####

template <bool __threads, int __inst>
    char* __default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs)
    {
        char* __result;
        size_t __total_bytes = __size * __nobjs;    //总申请字节大小
        size_t __bytes_left = _S_end_free - _S_start_free;  //内存池中剩余字节数
    
        //1、如果剩余内存大小够开辟20个所申请类型大小的空间
        //就返回此时的start_free，然后将start_free再向后挪动total——bytes
        if (__bytes_left >= __total_bytes) {
            __result = _S_start_free;
            _S_start_free += __total_bytes;
            return(__result);
        }
    
        //2、如果剩余大小不够开20个，但是最少能开一个
        //更新此时最多能开的nobjs，返回地址
        else if (__bytes_left >= __size) {
            __nobjs = (int)(__bytes_left / __size);
            __total_bytes = __size * __nobjs;
            __result = _S_start_free;
            _S_start_free += __total_bytes;
            return(__result);
        }
    
        //3、走到此时，说明内存池中连一个size大小的空间都申请不到
        else {
            //先计算出一会malloc的字节大小
            size_t __bytes_to_get =
                2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
    
            // 将内存池剩余空间挂到对应的链表中
            if (__bytes_left > 0) {
                _Obj** __my_free_list =
                    _S_free_list + _S_freelist_index(__bytes_left);
    
                ((_Obj*)_S_start_free)->_M_free_list_link = *__my_free_list;
                *__my_free_list = (_Obj*)_S_start_free;
            }
    
            //3、1此时内存池中也空了，直接进行malloc
            _S_start_free = (char*)malloc(__bytes_to_get);
    
            //3、2如果malloc失败，尝试去比当前内存块大的链表中取出一块先用 
            if (0 == _S_start_free) {
                size_t __i;
                _Obj** __my_free_list;
                _Obj* __p;
    
                for (__i = __size;
                    __i <= (size_t)_MAX_BYTES;
                    __i += (size_t)_ALIGN) {
                    __my_free_list = _S_free_list + _S_freelist_index(__i);
                    __p = *__my_free_list;
                    //如果后续链表有空闲内存块，再次调用该函数，此时已经保证能开辟一个size大小的内存块
                    if (0 != __p) {
                        *__my_free_list = __p->_M_free_list_link;
                        _S_start_free = (char*)__p;
                        _S_end_free = _S_start_free + __i;
                        return(_S_chunk_alloc(__size, __nobjs));
                    }
                }
                //此时内存空间十分吃紧
                //调用一级空间配置器，期待__malloc_alloc_oom_handler能够解决该问题。
                _S_end_free = 0;    
                _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
            }
            //malloc成功，再次向内存池申请空间
            _S_heap_size += __bytes_to_get;
            _S_end_free = _S_start_free + __bytes_to_get;
            return(_S_chunk_alloc(__size, __nobjs));
        }
    }

--------------------

#### **二级配置器简化流程图：** ####

![这里写图片描述][SouthEast 5]

--------------------

#### 关于空间配置器的优缺点 ####

##### 优点：空间配置器的出现就是为了尽量避免外碎片的出现。（外碎片指：当系统中有n个字节的空间时，我们却不能开辟出来，就说明此时内存中存在很严重的外碎片问题）； #####

##### 缺点：空间配置器虽然避免了外碎片的出现，但是引入了内碎片的问题。（内碎片值：由于在自由链表中取内存块大小都是取的8的倍数，但是实际应用中可能只会用到前5个字节，而后三个字节就是引发的内碎片） #####

--------------------

注：有部分截图来源于侯捷的STL源码剖析

[SouthEast]: /images/20220531/b53f64447b054dc49d7a493613bd780e.png
[SouthEast 1]: /images/20220531/709e7bd1c6fe4dedbdfb147e2076de12.png
[SouthEast 2]: /images/20220531/65d58aafadb84534b2bd88dd92557217.png
[SouthEast 3]: /images/20220531/d7a4a79dc08741c0a480d609abb886a9.png
[SouthEast 4]: /images/20220531/1810b18f5cce48be9256f8c21772f9f8.png
[SouthEast 5]: /images/20220531/d4666c0a277f4543bdae02e340210a4d.png