illx10000

青春不是年华，而是心境

stl allocator

2019年8月24日 星期六, 发表于 深圳

如果你对本文有任何的建议或者疑问, 可以在 这里给我提 Issues, 谢谢! :)

stl allocator 是stl中负责空间管理（空间申请/释放）的部分；

1. alloctor和容器

总体来看，stl allocator是一个模版类，通过组合方式和stl中的容器进行组合，例如

std::vector<int> first;   //构造一个int的vector
//实际是是执行下面的构造函数
template < class T, class Alloc = allocator<T> > 
class vector;

stl通过模板参数将空间分配和销毁的任务委托给alloctor
alloctor主要负责四件事：

  1. 分配空间;
  2. 构造对象实例；
  3. 析构对象实例；
  4. 释放空间；

参考这个文章https://zhuanlan.zhihu.com/p/34725232里面的图片

调用顺序

在SGI-STL中，分为两级配置器，第一级配置器主要是对malloc和free的封装，以及处理内存不足时的set new handler处理，第二级配置器实现内存池，避免了小型对象频繁分配导致内存碎片；

1.1 SGI-STL 第二级适配器

以下内容来自于《STL 源码剖析》

SGI第二级配置器做法是，如果区块够大，超过128bytes时，将移交第一级配置器处理。当小于128bytes，则以内存池管理，此法又称为次级配置：每次配置一大块内存，并维护对应之自由链表free-lists。下次若有相同大小的内存需求，直接从free-lists中拨出。如果客端释放小额块区，就由配置器回收到free-lists中

为了方便管理，SGI第二级配置器主动将任何小额块区的内存需求量上调至8的倍数（如，客端要求30bytes，则自动调整为32bytes），并维护16个free-lists，各自分别管理大小为8、16、24、32、……、120、128bytes的小额块区。

这一块的数据结构和代码设计的相当精巧，可以参考下面的链接 https://blog.csdn.net/u013074465/article/details/44560541

在stl_alloc.h这个头文件中，实现了alloc函数，alloc的流程大致为：

  1. 如果分配空间大于128字节，调用以及分配器（malloc和free）;
  2. 否则进行如下判断：
    2.1) 根据申请空间找到对应的空闲链表；
    2.2) 如果对应空闲链表为空，则调用refill先分配free list，然后再分配；

refill的流程发生在对应的链表为非空闲状态的情况下，refill通过调用chunk_alloc为free list填充空间，默认情况下，新区块获取20个新节点;

refill将chunk_alloc获得到的节点通过指针串联起来，相对逻辑比较简单；

其中最复杂的部分应该是chunk_alloc。 参考下面的代码：https://github.com/steveLauwh/SGI-STL/blob/master/SGI-STL%20V3.3/stl_alloc.h
chunk_alloc()函数以 end_free - start_free 来判断内存池的水量。

  1. 如果水量充足，就直接调用 20 个区块返回给 free list；
  2. 如果水量不足以提供 20 个区块，但还最后供应一个以上的区块，就拔出这不足 20 个区块的空间出去这时候其 pass by reference的nobjs参数将被修改为实际能够供应的区块数。
  3. 如果内存池连一个区块空间都无法供应，对客端显然无法交待，此时便需利用 malloc() 从head中配置内存，为内存池注入源头活水以应付需求。新水量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。
    3.1) 如果不能Malloc出来，则从更大的区块尝试借一些区块过来使用；
// 从内存池中取空间
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;  // 计算内存池剩余空间

    if (__bytes_left >= __total_bytes) {  // 内存池剩余空间完全满足申请
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return(__result);
    } 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);
    } else {                             // 内存池剩余空间连一个区块的大小都无法提供                      
        size_t __bytes_to_get = 
	  2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
        // Try to make use of the left-over piece.
	// 内存池的剩余空间分给合适的空闲链表
        if (__bytes_left > 0) {
            _Obj* __STL_VOLATILE* __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;
        }
        _S_start_free = (char*)malloc(__bytes_to_get);  // 配置 heap 空间，用来补充内存池
        if (0 == _S_start_free) {  // heap 空间不足，malloc() 失败
            size_t __i;
            _Obj* __STL_VOLATILE* __my_free_list;
	    _Obj* __p;
            // Try to make do with what we have.  That can't
            // hurt.  We do not try smaller requests, since that tends
            // to result in disaster on multi-process machines.
            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;
                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));
                    // Any leftover piece will eventually make it to the
                    // right free list.
                }
            }
	    _S_end_free = 0;	// In case of exception.
            _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);  // 调用第一级配置器
            // This should either throw an
            // exception or remedy the situation.  Thus we assume it
            // succeeded.
        }
        _S_heap_size += __bytes_to_get;
        _S_end_free = _S_start_free + __bytes_to_get;
        return(_S_chunk_alloc(__size, __nobjs));  // 递归调用自己
    }
}

1.2 STL Allocator代码跟踪

可以参考一下这个博客的跟踪流程：https://blog.csdn.net/My_heart_/article/details/52716830

也可以参考我自己抽取出来的一段代码，一步步调试: 链接为: https://github.com/illx10000/relax/blob/master/algorithm/stl/stl_allocator_debug.cpp

Copyright © 2016 潘** - All rights reserved.