C++【STL】| GNU空间配置器alloc刨析，如何管理内存池（附图解）....

文章目录

• • 一、简介
  • 二、stl_construct源码刨析
  • 三、stl_alloc源码刨析
  • • 1、一级配置器实现malloc和free📣📣📣
    • 2、二级配置器如何管理内存池？？？📣📣📣
    • 3、一二级封装
  • 四、内存初始化工具
  • • 1、uninitialized_copy
    • 2、uninitialized_fill
    • 3、uninitialized_fill_n

以下将会介绍gnu2.9下std::alloc的运作，将会看到它是如果管理内存，如何节约内存的时候，减少内存的浪费；
对new delete内存分配知识阔以参数以下文章

C++ |【总结归纳三本书籍系列】一文透彻资源管理，动态内存分配【上】…
C++ |【总结归纳三本书籍系列】一文透彻资源管理，动态内存分配【下】…

一、简介

在STL中将alloc内存配置放置于中，而该配置器将会使用到一些全局函数，此类函数分别置于和
中；
- stl_construct：将为分配器提供对象的构造和析构函数；
- stl_uninitialized：将为分配器提供填充和复制数据的 *** 作；

二、stl_construct源码刨析

destroy分为两个版本：
- 有用的析构函数：则循环调用其析构函数；
- 无用的析构函数：则什么都不做；

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

/** 析构函数 */
template<class T>
inline void destroy(T* p) {
    p->~T();
}

/** 析构函数：循环析构 */
template<class ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last, std::false_type) {
    for(; first < last; ++first)
        destroy(&*first);
}

/** 析构函数： */
template<class ForwardIterator>
inline void _destroy_aux(ForwardIterator first, ForwardIterator last, std::true_type) {
}

/** 析构函数：判断是否有用 */
template<class ForwardIter>
inline void destroy(ForwardIter first, ForwardIter last) {
    _destroy_aux(first, last, std::is_trivially_destructible<ForwardIter>());
}


/** 析构函数 */
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

三、stl_alloc源码刨析

该配置器设计了双层级别：
- 一级配置器：直接使用malloc、free、以及对内存申请失败的处理；
- 二级配置器：将采用复杂的内存池来管理；

该配置器的设计能够解决：
- 满足多线程；
- 当内存不足时的应变措施；
- 考虑小型区块可能造成的内存碎片；

1、一级配置器实现malloc和free📣📣📣

当请求大小大于128时，使用该分配器；
该分配器使用仿照::opertor new的new_headler机制来处理异常；

new_handler参考

#if 0
#   include 
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include
#   define __THROW_BAD_ALLOC std::cerr << "out of memory" << std::endl; exit(1)
#endif


template<int inst>
class __malloc_alloc_template {
private:
    static void *oom_malloc(size_t);

    static void *oom_realloc(void *, size_t);

    static void (*__malloc_alloc_oom_handler)();

public:

    static void *allocate(size_t n) {
        void *ret = malloc(n);
        /* 若失败则直接进入oom_malloc */
        if (nullptr == ret) ret = oom_malloc(n);
        return ret;
    }

    static void deallocate(void *p, size_t) {
        free(p);
    }

    static void *reallocate(void *p, size_t, size_t new_sz) {
        void *ret = realloc(p, new_sz);
        /* 若失败直接进入oom_realloc */
        if (nullptr == ret) ret = oom_realloc(p, new_sz);

        return ret;
    }

    static void (*set_malloc_handler(void (*f)()))() {
        void (*old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = f;
        return old;
    }
};
/** 初始化handler */
template<int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = nullptr;

/** 处理malloc失败 */
template<int inst>
void *__malloc_alloc_template<inst>::oom_malloc(size_t n) {
    void (*my_malloc_handler)();
    void *ret;

    for(;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if(nullptr == my_malloc_handler) { __THROW_BAD_ALLOC; }
        (*my_malloc_handler)();
        ret = malloc(n);
        if(ret) return ret;
    }
}

/** 处理realloc失败 */
template<int inst>
void *__malloc_alloc_template<inst>::oom_realloc(void *p, size_t n) {
    void (*my_malloc_handler)();
    void *ret;

    /* 不断循环尝试 */
    for(;;) {
        my_malloc_handler = __malloc_alloc_oom_handler;
        if(nullptr == my_malloc_handler) { __THROW_BAD_ALLOC; }
        (*my_malloc_handler)();
        ret = realloc(p, n);
        if(ret) return ret;
    }
}

typedef __malloc_alloc_template<0> malloc_alloc;

2、二级配置器如何管理内存池？？？📣📣📣

当向malloc申请一个区块时，其消耗的内存大小是大于我们所获得的，由于后续需要系统回收或处理一些debug调试信息，这些都会随着我们malloc而附着在
上面，每当用户malloc一次就多出一部分，若malloc一万次，那内存的消耗量将会是巨大的；
因此，我们将考虑，如何将附带的这些内存消耗尽量小。故，二级分配器，采用分配大区块，在将区块划分为满足需要的大小提供给用户使用，从而减轻了
这些附着的东西，让更多的内存能够供用户使用，避免浪费；

malloc内存块详细说明

二级分配器维护了一个长度为16的自由链表，每个链表都分别负责不同区块的分配；
- 最小区块为8字节，最大区块为128字节，其中每个间隔为8字节，若用户需要的超过128，则转用一级分配器；

第二配置器头文件

其中的 union obj是一个嵌入式指针的用法，即在内存池链表中、每个区块都嵌套一个指针；

【ROUND_UP】：内存对齐
若要申请的大小为7，则会将其调整为8；
【FREELIST_INDEX】：区块索引
当输入一个区块大小，会返回一个相应的链表索引；

typedef unsigned long long size_t;

enum {__ALIGN = 8};                 // 增长间隔
enum {__MAX_BYTES = 128 };          // 最大区块
enum { __NFREELISTS = __MAX_BYTES / __ALIGN };  // 链表长度

/** 二级分配器 */
template<bool threads, int inst>
class __default_alloc_template {
    typedef __malloc_alloc_template<0> malloc_alloc;
private:
    /** 内存对齐 */
    static size_t ROUND_UP(size_t bytes) {
        return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
    }
public:
    union obj {
        union obj* next;
    };

private:
    /** 内存块链表 */
    static obj* volatile free_list[__NFREELISTS];

    /** 根据区块大小，链表索引 */
    static size_t FREELIST_INDEX(size_t bytes) {
        return (((bytes) + __ALIGN - 1)/ __ALIGN - 1);
    }

    static void *refill(size_t);
    static char *chunk_alloc(size_t, int&);

    static char *start_free;    // 内存池起点
    static char *end_free;      // 内存池尾部
    static size_t heap_size;    // 申请的总容量

public:
    static void *allocate(size_t);
    static void deallocate(void*, size_t);
    static void *reallocate(void*, size_t, size_t);
};

第二配置器cpp

/** 静态成员类内声明类外初始化 */
template<bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = nullptr;

template<bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = nullptr;

template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

template<bool threads, int inst>
typename __default_alloc_template<threads, inst>::obj * volatile
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
        {0};

【allocate】：分配内存
当输入字节大小，则会在链表上查询该对应区块是否有剩余空间，若没有，则申请，若有，则返回；

template<bool threads, int inst>
void *__default_alloc_template<threads, inst>::allocate(size_t n) {
    obj* volatile *my_free_list;
    obj* ret;

    /* 判断是否超出范围，若超出则用第一分配器 */
    if(n > (size_t)__MAX_BYTES) {
        return (malloc_alloc::allocate(n));
    }
    /* 判断会落到哪个链表上 */
    my_free_list = free_list + FREELIST_INDEX(n);
    ret = *my_free_list;

    /* 判断该链表上是否有空间 */
    if(ret == nullptr) {
        /* 该链表上没有，则申请 */
        void* r = refill(ROUND_UP(n));
        return r;
    }
    /* 调整区块 */
    *my_free_list = ret->next;
    return ret;
}

【deallocate】：内存回收；
若内存区块小大大于128则交给一级分配器回收，对应前面的大于128由一级分配器分配；
小于128的内存将会挂回链表中，而没有规划给系统，由于在切割后，分配区块没有记录，故回收将回很困难，直接将其挂回相应区块大小的链表头部；

template<bool threads, int inst>
void __default_alloc_template<threads, inst>::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);
    /* 回收 */
    q->netx = *my_free_list;
    *my_free_list = q;
}

【refill】：重新填充
若没有相应的区块能够满足用户，则重新分配；
分配好内存后，挂到相应的链表上，切将内存块进行切割；

template<bool threads, int inst>
void *__default_alloc_template<threads, inst>::refill(size_t n) {
    /* 系统设定每次分配2*20*n */
    int nobjs= 20;
    char* chunk = chunk_alloc(n, nobjs);    // 获取内存块，nobjs是传出传入值
    obj* volatile *my_free_list;
    obj* ret;
    obj* cur_obj, *next_obj;

    /* 若只分配一个内存块，则后续不需要切割 */
    if(1 == nobjs) return chunk;
    /* 将新分配的内存块挂到对应链表号 */
    my_free_list = free_list + FREELIST_INDEX(n);
    ret = (obj *)chunk;
    *my_free_list = next_obj = (obj*)(chunk + n);

    /* 切割 */
    for(int i=1; ; ++i) {
        cur_obj = next_obj;     // 保存当前位置
        next_obj = (obj*)((char*)next_obj + n); // 位置下调
        /* 若最后一个则退出 */
        if(nobjs - 1 == i) {
            cur_obj->next = nullptr;
            break;
        } else {// 将区块都串起来
            cur_obj->next = next_obj;
        }
    }
    return ret;
}

【chunk_alloc】：分配区块
首先先查看当前内存池是否满足，若满足则返回；
若不满足，则查看减少区块个数后是否满足，满足则返回；
若不满足，则需要申请内存；
	先将剩余的碎片挂起；
	申请内存，成功，则记录余量返回；
	若内存申请失败，则尝试在往大方向的链表上获取区块，递归在次尝试；
	若没有则尝试向一级分配器获取；

template<bool threads, int inst>
char *__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs) {
    char *ret;
    size_t total_bytes = size * nobjs;          // 需要总申请的大小
    size_t bytes_left = end_free - start_free;  // 内存池剩余的容量
    /* 判断剩余容量是否满足总大小 */
    if(bytes_left >= total_bytes) {
        ret = start_free;
        start_free += total_bytes;
        return ret;
    /* 若小于20个区块的大小 */
    }else if(bytes_left >= size) {
        nobjs = bytes_left / size;
        total_bytes = size * nobjs;
        ret = start_free;
        start_free += total_bytes;
        return ret;
    /* 若都不满足，则需要申请 */
    } else {
        /* 若重新申请，则需要的大小 */
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        /* 有余量，切不满足本次申请大小，则将该碎片挂到相应的链表中 */
        if(bytes_left > 0){
            obj* volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((obj*)start_free)->next = *my_free_list;
            *my_free_list = (obj*)start_free;
        }
        /* 申请空间 */
        start_free = (char*) malloc(bytes_to_get);
        /* 若申请失败 */
        if(nullptr == start_free) {
            obj *volatile *my_free_list, *p;
            /* 尝试从较进的链表往右的方向进行查询，其他链表是否右剩余空间，将其拿取 */
            for(int i=size; i<=__MAX_BYTES; i += __ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if(nullptr != p) {  // 不为空，则将其内存纳入内存池，在次进行分配
                    *my_free_list = p->next;
                    start_free = (char*)p;
                    end_free = start_free + i;
                    return chunk_alloc(size, nobjs);
                }
            }
            /* 若其他链表也没有剩余内存，只好向malloc申请，看看是否还能申请到内存 */
            end_free = nullptr;
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
        }
        /* 申请成功将余量添加 */
        heap_size += bytes_to_get;
        /* 将内存池扩大 */
        end_free = start_free + bytes_to_get;
        return chunk_alloc(size, nobjs);
    }
}

3、一二级封装

将一二级封装为模板，通过模板参数传入;

typedef __default_alloc_template<true, 0> alloc;

template<class T, class Alloc>
class simple_alloc{
public:
    static T* allocate(size_t) {
        return 0 == n ? 0 : (T*)Alloc::allocate(n* sizeof(T));
    }
    
    static T* allocate(void) {
        return (T*)Alloc::allocate(sizeof(T));
    }
    
    static void deallocate(T *p, size_t n) {
        if(0 == n)
            Alloc::deallocate(p, n* sizeof(T));
    }
    
    static void deallocate(T* p) {
        Alloc::deallocate(p, sizeof(T));
    }
};

template<class T, class Alloc>
class Vector{
	typedef simple_alloc<T, Alloc> data_allocate;
}

int main() {
	vector<int, alloc> vc;
	return 0;
}

四、内存初始化工具

此类函数运用巧妙的设计让内存的配置与对象的构造行为分离；
且具备`commit or rollbak`语意，若执行完毕则提交，若有失败的，则回滚到先前；

1、uninitialized_copy

它将会使用拷贝构造给每一个对象生成一份copy，放到result；
若在容器中想要使用一个容器在生成一个，即可使用该函数来实现；

template<class InputIter, class ForwardIter>
inline ForwardIter _uinit_copy_aux(InputIter first, InputIter last, ForwardIter result, std::true_type) {
   return copy(first, last, result);
}

template<class InputIter, class ForwardIter>
inline ForwardIter _uinit_copy_aux(InputIter first, InputIter last, ForwardIter result, std::false_type) {
    ForwardIter cur = result;
    for(; first != last; ++first, ++cur)
        construct(&*cur, *first);
    return cur;
}

template<class InputIter, class ForwardIter, class T>
inline ForwardIter _uinit_copy(InputIter first, InputIter last, ForwardIter result, T*) {
    return _uinit_copy_aux(first, last, result, std::is_void<T>());
}

// char*特化版本
inline char* uinit_copy(const char* first, const char* last, char* result) {
    memmove(result, first, last-first);
    return result + (last - first);
}

inline wchar_t* uinit_copy(const wchar_t * first, const wchar_t * last, wchar_t * result){
    memmove(result, first, sizeof(wchar_t ) * (last - first));
    return result + (last - first);
}

template<class InputIter, class ForwardIter>
inline ForwardIter uinit_copy(InputIter first, InputIter last, ForwardIter result) {
    return  _uinit_copy(first, last, result, std::integral_constant<ForwardIter, result>::value);
}

2、uninitialized_fill

若[first, last)都指向未初始化内存，则将x填充该区间；

template<class ForwardIter, class T>
inline void uinit_fill(ForwardIter first, ForwardIter last, const T&x) {
    _uinit_fill(first, last, x, std::integral_constant<ForwardIter, first>::value);
}

template<class ForwardIter, class T, class T1>
inline void _uinit_fill(ForwardIter first, ForwardIter last, const T& x, T1*) {
    _uinit_fill_aux(first, last, std::is_pod<T>());
}

template<class ForwardIterator, class T>
inline void _uinit_fill_aux(ForwardIterator first, ForwardIterator last, const T& x, std::true_type){
    fill(first, last, x);
}

template<class ForwardIterator, class T>
inline void _uinit_fill_aux(ForwardIterator first, ForwardIterator last, const T& x, std::false_type){
    ForwardIterator cur = first;
    for(; cur != last; ++cur) {
        construct(&*cur, x);
    }
}

3、uninitialized_fill_n

若[first, last)都指向未初始化内存，则将x填充从first开始往后的n个位置；

/**
* @brief：处理POD型别，该型别拥有trivial ctor/dtor/copy/assignment函数
* */
template<class ForwardIter, class Size, class T>
inline ForwardIter _uinit_fill_n_aux(ForwardIter first, Size n, const T &x, std::true_type) {
   return std::fill_n(first, n, x);
}

/**
* @brief：处理不为POD型别
* */
template<class ForwardIter, class Size, class T>
inline ForwardIter _uinit_fill_n_aux(ForwardIter first, Size n, const T &x, std::false_type) {
   ForwardIter cur = first;
   for(; n<0; --n, ++cur) {
       construct(&*cur, x);
   }
}

template<class ForwardIter, class Size, class T, class T1>
inline ForwardIter _uinit_fill_n(ForwardIter first, Size n, const T&x, T1*) {
   return _uinit_fill_n_aux(first, n, x, std::is_pod<T>());
}

template<class ForwardIter, class Size, class T>
inline ForwardIter uinit_fill_n(ForwardIter first, Size n, const T &x) {
   return _uinit_fill_n(first, n, x, std::integral_constant<ForwardIter, first>::value);
}

参考：侯捷《C++内存管理》