STL_Allocator

发表于 | 分类于
字数统计: 6.1k | 阅读时长 ≈ 26
格罗宁根 -- 荷兰

STL_Allocator

1. 文件结构

图 1 Allocator 文件结构

Allocator 文件结构以及关键函数如上图所示，分为了两个部分，simpleAlloc，subAllocation。

1.1 simpleAlloc

内部包含 1 个头文件：simpleAlloc.h

1.1.1 simpleAlloc.h

simpleAlloc.h 这是一个简单的空间配置器的例子，实现了部分的接口和功能。

内部调用 ::operator new、 ::operator delete

《STL源码剖析》 – P44 - P47

1.2 subAllocation

内部包含 5 个头文件：

  • allocator.h
  • memory.h
  • alloc.h
  • construct.h
  • uninitialized.h

1.2.1 allocator.h

与 simpleAlloc.h 相类似。它由 SGI 定义的一个符合部分标准，名为 allocator 的配置器，但是 SGI 从未使用过它，也不建议我们使用。主要的原因是效率不佳，只是把 C++ 的 ::operator new 和 ::operator delete 做一层薄薄的包装而已。

《STL源码剖析》 – P48 - P49

但是重要的是 SGI STL 把一级二级配置器封装在 simple_alloc 接口中，所有的 SGI STL 容器都是用这个接口。这个接口定义在 allocator.h 文件中。一二级配置器的关系，接口包装，实际运用方式见下图。

图 2(a) 一级，二级配置器
图 2(b) 一级，二级配置器的包装接口和运用方式

《STL源码剖析》 – P53 - P56

1.2.2 memory.h

内部包含了 3 个头文件：

1
2
3
#include "alloc.h"
#include "construct.h"
#include "uninitialized.h"

alloc.h 定义了一、二级配置器，彼此合作。配置器名为 alloc。利用 allocate() 分配内存，利用 deallocate() 释放内存。

construct.h 定义了全局函数 construct() 和 destroy()，负责对象的构造和析构。

uninitialized.h 定义了一些全局函数，用来填充或复制大块内存数据，这些函数虽然不属于配置器的范畴，但与对象初值设置有关。对于容器的大规模元素初值设置很有帮助。这些函数对于效率都有面面俱到的考虑，最差情况下会调用 construct()，最佳情况则会使用 C 标准函数 memmove() 直接进行内存数据的移动。

《STL源码剖析》 – P50

2. 关键代码

2.1 construct.h

2.1.1 头文件

1
2
#include <new>  // placement new 所需的头文件       
#include "typeTraits.h" // 萃取机所需要的头文件

《STL源码剖析》 – P51

2.1.2 构造

构造函数只有一种，可以使用 placement new

1
2
3
4
template <class T1, class T2>
inline void construct(T1 *p, T2 value) {
    new (p) T1(value);  // placement new, 调用 T1::T1(value)
}

《STL源码剖析》 – P51

2.1.3 析构

析构函数有四个重载函数，版本一就是简单调用对象的析构函数，如下：

1
2
3
4
template <class T>
inline void destroy(T *p) {
    p->~T();
}

版本二接受两个迭代器，并根据不同的元素型别选择调用不同的接口函数。destroy() 内部调用不同型别对应的接口函数 _destroy_aux()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 设法利用traits批量析构对象
template <class ForwardIterator>
inline void destroy(ForwardIterator beg, ForwardIterator end) { 
    /* typename 必须要使用,因为是模板的别名 */
    using is_POD_type = typename _type_traits<ForwardIterator>::is_POD_type; 
    _destroy_aux(beg, end, is_POD_type()); // 根据元素型别调用适配的接口函数
}

// 如果元素的 value_type 存在non—trivial destructor，老老实实调用析构函数
template <class ForwardIterator>
inline void _destroy_aux(ForwardIterator beg, ForwardIterator end, _false_type) {
    for (; beg != end; ++beg) destroy(&*beg);  // 毕竟迭代器不是真正的地址
}

// 存在trivial destructor
// 如果对象的析构函数无关痛痒，那么反复调用它是一种效率上的巨大浪费
/* 因此，若是_true_type 的话就什么也不做就结束*/
template <class ForwardIterator>
inline void _destroy_aux(ForwardIterator, ForwardIterator, _true_type) {}

版本三、四是对应 char* 和 wchar_t* 的特化版本。

1
2
3
// 因为 char* 和 wchar_t* 归于 POD 类型，属于 trivial 类型，--> _true_type
inline void destroy(char *, char *) {}
inline void destroy(wchar_t *, wchar_t *) {}

可以参考 C++ trivial、non-trivial及POD类型

“typeTraits.h” 头文件中有详细的分类

《STL源码剖析》 – P51

2.2 alloc.h

alloc.h 为 sub-Allocation 的主要实现，sub-Allocation 理解为具有次配置的空间配置器，分为两级配置。

  • 一级配置器 _malloc_alloc，分配内存 $> 128\ bytes$
  • 二级配置器 _default_alloc，分配内存 $\leq 128\ bytes$

《STL源码剖析》 – P53 - P56

2.2.1 头文件

1
2
3
#include <cstdlib>   // malloc free realloc
#include <new>		 // bad_alloc 
#include <string.h>  // memcpy

《STL源码剖析》 – P56

2.2.2 一级配置器

一级配置器，主要有两个主要功能：

  • 分配和释放内存
  • 处理内存不足的状况
2.2.2.1 分配和释放内存

allocate() 直接使用 malloc() ；

1
2
3
4
5
6
7
static void *allocate(size_t n) {
	// 使用 malloc 分配内存
	void *result = malloc(n);
	// 如果分配内存失败，调用 oom_malloc 处理， 类似于 new_handler
	if (result == nullptr) result = oom_malloc(n);
	return result;
}

deallocate() 直接使用 free() ；

1
2
// deallocate 释放内存，内部调用 free
static void deallocate(void *p, size_t /*n*/) { free(p); }

reallocate() 直接使用 reallocate() ；

1
2
3
4
5
6
7
8
// reallocate 修改分配内存，内部调用 realloc
static void *reallocate(void *p, size_t /*old_sz*/, size_t new_sz) {
	// 使用 realloc 重新分配内存， 如果 new_sz = nullptr  realloc 等价于 malloc
	void *result = realloc(p, new_sz);
	// 如果分配内存失败，调用 oom_realloc 处理， 类似于 new_handler
	if (result == nullptr) oom_realloc(p, new_sz);
	return result;
}

可以发现，三个函数皆是直接使用库函数来实现，但是进行了内存分配失败的处理 oom_malloc(n)，oom_realloc(n)。

《STL源码剖析》 – P57

2.2.2.2 处理内存不足的状况
1
2
3
4
5
using malloc_handler = void (*)();
//以下函数指针用以处理内存不足的情况 (两个静态函数，一个静态成员变量(函数指针))
static void *oom_malloc(size_t);  // 处理 allocate 失败
static void *oom_realloc(void *, size_t); // 处理 realloc 失败
static malloc_handler __malloc_alloc_oom_handler; // 类似 new_handler 用户处理函数

为了模拟 set_new_handler 行为，需要写一个类似标准版的set_malloc_handler()

1
2
3
4
5
6
7
8
9
// 模拟 C++ 的 set_new_handler(), 可以通过它来指定自己的 out-of-memory handler
// Effective c++ 条款 49
// set_malloc_handler 会将它获得的指针存储起来，然后返回先前（在此调用之前）存储的指针
// 用来管理静态成员变量 __malloc_alloc_oom_handler
static malloc_handler set_malloc_handler(malloc_handler f) {
	malloc_handler old = __malloc_alloc_oom_handler;
	__malloc_alloc_oom_handler = f;
	return old;
} // 类内成员函数 ↑ 共用户调用装配自己的 处理函数
1
2
3
// __malloc_alloc_oom_handler的类外定义，函数指针为 nullptr
typename __malloc_alloc::malloc_handler
    __malloc_alloc::__malloc_alloc_oom_handler = nullptr;

《Effective C++ 3rd》 – 条款49：了解 new-handler 的行为 （P243）

《STL源码剖析》 – P57

oom_malloc() 用来自定义处理 malloc 分配失败的情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void *__malloc_alloc::oom_malloc(size_t n) {
    // void(*new_alloc_handler)();
    malloc_handler new_alloc_handler;  // 定义 new_handler
    void *result;
    for (;;) {  //不断尝试释放、配置
		// 分配失败：找到目前的 new_handing 函数，之前由用户调用 set_malloc_handler 创建
        new_alloc_handler = __malloc_alloc_oom_handler;
        // 只有当 malloc-handling 函数的指针是 null, 才会抛出异常。
        if (!new_alloc_handler) throw std::bad_alloc(); 
        (*new_alloc_handler)();    // 调用 handler，试图释放内存

        result = malloc(n);        // 再次分配内存
        if (result) return result; // 如果成功，返回一个指向分配得来的内存的一个指针
    }
}

oom_realloc() 用来自定义处理 remalloc 分配失败的情况。与上文代码相同，仅仅 行: 8 不同。

1
2
3
4
5
6
7
8
9
10
11
void *__malloc_alloc::oom_realloc(void *p, size_t n) {
    malloc_handler new_alloc_handler; // 定义 new_handler
    void *result; 
    for (;;) {
        new_alloc_handler = __malloc_alloc_oom_handler;
        if (!new_alloc_handler) throw std::bad_alloc();
        (*new_alloc_handler)();
        result = realloc(p, n); 
        if (result) return result;
    }
}

上述的处理函数步骤如下：

  • 用户调用 set_malloc_handler() 自定义自己的处理函数，如果未定义，_malloc_alloc_oom_handler 被默认定义为 nullptr，是一个空指针。

  • 如果出现内存分配失败情况，进入相应的处理函数，oom_malloc() 或者 oom_realloc()

    • 首先定义处理函数 new_alloc_handler 并将 _malloc_alloc_oom_handler 赋给它；
    • 如果用户未定义相应的处理函数，直接抛出异常即可；否则调用用户定义的处理函数，试图解决内存不足的情况；
    • 再次重新调用 malloc() 分配内存；

注意：

  • 设计和设定“内存不足处理函数”是客端的责任。

  • 其中 for (;;) 的使用可以使得处理函数不断尝试处理内存不足情况。

《STL源码剖析》 – P58 - P59

《Effective C++ 3rd》 – 条款51：编写 new 和 delete 时需固守的常规 （P253）

2.2.3 二级配置器

二级配置器多了一些机制，避免太多小额外区块造成内存的碎片。小额区块带来的其实不仅时内存碎片，配置时的额外负担也是一个大问题。额外负担永远无法避免，毕竟系统要靠这多出来的空间来管理内存，如下图所示。但是块区越小，额外负担所占的比例就越大，越显得浪费。

图 3 所求任何一块内存，都得有一些“税”要缴给系统

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

2.2.3.1 自由链表

free​-list​ 节点结构如下，实现技巧如下图 4 所示。

1
2
3
4
5
6
7
8
// free_list节点
    // 由于union特性，并不需要占用额外的内存
	// obj 可以被视为一个指针，指向相同形式的另一个obj
	// obj 也可被视为一个指针，指向实际块区
union obj {
	union obj *free_list_link;  //指向下一节点
	char client_data[1];        //指向资源
};
图 4 自由链表的实现技巧

为了方便管理，SGI 二级配置器会主动使用 ROUND_UP()函数将任何小额区块的内存需求量上调至 8 的倍数，并维护 16 个 free-list 。从 ${8,16,…128}$。使用 FREELIST_INDEX() 函数确定区块编号。

1
2
3
4
5
6
7
8
// freelist参数设定
// 区块上调边界，区块上限，freelist个数
// Effective C++ 所述 enum 惯用法,条款 2
enum __freelist_setting {
    __ALIGN = 8, 
    __MAX_BYTES = 128,
    __NFREELISTS = __MAX_BYTES / __ALIGN  // 16
};

关于 _freelist_setting 的相关操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 将bytes上调至8的倍数
// 例子：(bytes + 7) & ~7  --- >  (bytes + 7) & 1..11000
static size_t ROUND_UP(size_t bytes) {
	return (((bytes) + static_cast<size_t>(__ALIGN) - 1) &
			~(static_cast<size_t>(__ALIGN) - 1));
}
// 创建 free_list[16] 数组, 里面存放 obj* 类型数据
static obj *volatile free_list[__NFREELISTS];

// 决定使用第几号节点，从 0 起算 (本质就是就偏移)
// ((1~7) + 7) / 8 - 1 ---> 0   .... 依次类推
static size_t FREELIST_INDEX(size_t bytes) {
    return (bytes + static_cast<size_t>(__ALIGN) - 1) /
        static_cast<size_t>(__ALIGN) - 1;
}

《STL源码剖析》 – P59 - P61

《Effective C++ 3rd》 – 条款2：尽量用 const,enum,inline 替代 #define （P15）

2.2.3.2 空间配置函数 allocate()

空间配置函数为 allocate()，如果需要分配的内存大于 128 则采用一级配置器，否则从自由链表中拔出内存使用，如果自由链表没有没存就需要调用 refill() 来填充自由链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void *__default_alloc::allocate(size_t n) {  /*n > 0*/
    obj *volatile *my_free_list;
    obj *result;
    // 若 n 大于128,则采用一级配置器
    if (n > __MAX_BYTES) return (malloc_alloc::allocate(n));
    
	// free_list 是一个存 obj*的数组, 数组名为free_list[0]指针
    // 通过 FREELIST_INDEX 求出偏移，并选择采用第几区块，并让 result 指向它
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    
    if (result == nullptr) {
        // 未找到可用free_list，准备填充free_list
        void *r = refill(ROUND_UP(n));
        return r; // 并且返回一个指向内存的指针
    }
    // 将 my_free_list 指向，当前 result 节点的 next (free_list_link)
    *my_free_list = result->free_list_link;
    return result;
}
图 5 区块自 free-list 拔出

《STL源码剖析》 – P62 - P63

2.2.3.3 空间释放函数 deallocate()

同样需要判断区块大小，大于128 字节，使用一级配置器，小于128 字节就找到对应的 free-list，将区块回收。

分为四个步骤

  • 强制类型转换，将 p 转化为 obj* 节点类型 q ，使用 reinterpret_cast 将 void* -> obj*
  • 根据内存的大小确定区块，调用 FREELIST_INDEX()
  • 将 q 的 next 区块指向当前 my_free_list 指向的内存
  • 更新 my_free_list 为 q
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void __default_alloc::deallocate(void *p, size_t n) {
    // p不可为nullptr，大于128字节，就调用一级配置器
    if (n > static_cast<size_t>(__MAX_BYTES))
        malloc_alloc::deallocate(p, n);
    else {
        // 寻找对应的free list, 分为四个步骤 ：
		// 1：强制类型转换，将 p 转化为 q 的 节点类型指针
		// 使用 reinterpret_cast 将 void* -> obj* 
        obj *q = reinterpret_cast<obj *>(p);
		// 2：根据内存的大小确定区块 
        obj *volatile *my_free_list = free_list + FREELIST_INDEX(n);
		// 3：将 q 的下一区块指向当前 my_free_list 指向的内存
        q->free_list_link = *my_free_list;
		// 4：更新 my_free_list 为 q
        *my_free_list = q;
    }
}
图 6 区块回收，纳入 free-list

《STL源码剖析》 – P64 - P65

2.2.3.4 空间重配置函数 reallocate()

根据新旧内存需求的大小关系可以分为五种情况，分别对应这三种处理方式。

  • ① old_sz > 128, new_sz > 128​ ，直接使用 realloc() ；
  • ② ROUND_UP(old_sz) == ROUND_UP(new_sz) <= 128​：直接返回原内存指针即可；
  • ROUND_UP(old_sz) != ROUND_UP(new_sz) ，统一调用 allocate() 函数，只是内部根据 new_sz 的大小使用不同的配置器。
    • ③ old_sz > 128, new_sz <= 128 ：则会使用二级配置器；
    • ④ old_sz <= 128, new_sz > 128 ：则会使用一级配置器；
    • ⑤ old_sz <= 128, new_sz <= 128 ：则会使用二级配置器；

注意：情况 ① 中包含了 ROUND_UP(old_sz) == ROUND_UP(new_sz) > 128

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void *__default_alloc::reallocate(void *p, size_t old_sz, size_t new_sz) {
    void *result;
    size_t copy_sz;
    // 1. old_sz > 128,  new_sz > 128   直接使用 realloc()
    if (old_sz > static_cast<size_t>(__MAX_BYTES) &&
        new_sz > static_cast<size_t>(__MAX_BYTES))
        return realloc(p, new_sz);
    
    // 2. (ROUND_UP(old_sz) == ROUND_UP(new_sz) <= 128
    if (ROUND_UP(old_sz) == ROUND_UP(new_sz)) return p;
    
    // 3. old_sz > 128,  new_sz <= 128 :  则会使用二级配置器
    // 4. old_sz <= 128, new_sz > 128  :  则会使用一级配置器
    // 5. old_sz <= 128, new_sz <= 128 :  则会使用二级配置器
    result = allocate(new_sz);
    // 找到 copy_sz, 即 new_sz 和 old_sz 的最小值
    copy_sz = new_sz > old_sz ? old_sz : new_sz;
    // 将原有内容复制到新内存中
    memcpy(result, p, copy_sz);
    // 释放旧内存
    deallocate(p, old_sz);
    // 返回新内存
    return result;
}

MiniSTL / Allocator / subAllocation / alloc.h : reallocate()

内存池技术（三） 最后 mem_realloc() 讲解

《STL源码剖析》 – P62

2.2.3.5 重新填充 refill()

refill() 的工作就是，从内存池中获取内存。主要通过 chunk_alloc() 函数来获取内存。默认获取 20 个区块内存，由于内存不足，可能会小于这个数字，会根据获得内存的不同进行不同的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 当free_list无可用区块时，重新填充空间
// 新空间取自内存池，默认获取 20 个节点(区块)
// 若内存池不足，则获取的将小于 20
void *__default_alloc::refill(size_t n) { /* 这里的 n 是 8 的倍数 */
    int nobjs = 20;
    // 尝试调用 chunk_alloc,注意 nobjs 以 pass-by-reference 传入
    char *chunk = chunk_alloc(n, nobjs);
    obj *volatile *my_free_list;
    obj *result;
    obj *current_obj, *next_obj;

    // 若只获取了一个区块则直接分配给调用者，不加入free_list
    if (1 == nobjs) return (chunk);

    my_free_list = free_list + FREELIST_INDEX(n);
    // 在 chunk 空间内建立free_list
    result = reinterpret_cast<obj *>(chunk);
    // 引导 free_list 指向内存池分配的空间
    // chunk 指向的内存直接分给用户，free_list指向剩下（19或更少）的区块
    *my_free_list = next_obj = reinterpret_cast<obj *>(chunk + n);
    for (int i = 1;; ++i) {
        current_obj = next_obj;
        next_obj =
            reinterpret_cast<obj *>(reinterpret_cast<char *>(next_obj) + n);
        // 分配到最后时候
		if (nobjs - 1 == i) {
            current_obj->free_list_link = nullptr;
            break;  // 退出
        } else {
            current_obj->free_list_link = next_obj;
        }
    }
    return result;
}

《STL源码剖析》 – P65 - P66

2.2.3.6 内存池

从内存池中取空间给 free-list 使用，是 chunk_alloc() 的工作。在 chunk_alloc()之前需要明确内存池的结构。内存池的结构定义如下，图示如图 7 所示。

1
2
3
4
5
6
7
8
9
// chunk allocation state
static char *start_free;  // 内存池起始位置，只在chunk_alloc()中变化
static char *end_free;    // 内存池结束位置，只在chunk_alloc()中变化
static size_t heap_size;

// 静态成员初始化(类外)
char *__default_alloc::start_free = nullptr;
char *__default_alloc::end_free = nullptr;
size_t __default_alloc::heap_size = 0;
图 7 内存池简图

chunk_alloc() 是内存池的关键函数。

1
2
3
4
5
6
7
8
char *__default_alloc::chunk_alloc(size_t size, int &nobjs) { // size为 8 的整数倍
    char *result;
    size_t total_bytes = size * nobjs;  // 所需要分配的内存
    size_t bytes_left = end_free - start_free;  // 内存池剩余空间
    /* ...
       ...
    */
}

根据内存池的剩余空间与客端需求的关系，有三个处理路径：

  • 所需要分配的内存足够
  • 容量至少满足一个区块的需求
  • 内存池一个区块都无法满足提供

1. 所需要分配的内存足够

1
2
3
4
5
6
7
// 1. 容量满足需求
if (bytes_left >= total_bytes) {
    // 更新 start_free, 并返回内存指针
    result = start_free;
    start_free += total_bytes;
    return result;
}

2. 容量至少满足一个区块的需求

1
2
3
4
5
6
7
8
9
// 2. 容量至少满足一个区块需求
else if (bytes_left > size) {
    // 更新 nobjs, start_free, 并返回内存指针
    nobjs = static_cast<int>(bytes_left / size);
    total_bytes = size * nobjs;
    result = start_free;
    start_free += total_bytes;
    return result;
}

3. 内存池一个区块都无法满足提供

行：5 此时扩大需求量，新需求量是原需求量的二倍与现有内存池大小的十六分之一之和。

行：7-12并做碎片资源回收操作，将内存池中碎片资源加入到对应的自由链表中。

行：14 利用 malloc 函数向 heap 中申请所需内存

由于 malloc 的使用，会存在两种情况

  • heap 空间充足
  • heap 空间不够

前者 直接更新部分参数，并递归调用自身以修正 nobjs，最终返回所需内存，结束调用。（递归操作必定会进入if_else 语句中，下同）

后者

  • 会在大于 size 的自由链表中，尝试分配所需的区块，如果成功找到，则回收至内存池，并递归调用自身以修正 nobjs，最终返回所需内存，结束调用。
  • 如果自由链表中也没有内存，则会调用一级配置器，尝试调用一级配置器观察其能否分配内存，或抛出异常。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 3. 内存池一个区块都无法提供
else {
    // 向 heap 申请注入的内存，heap_size 将随着配置次数增加而增加
    // 扩大需要量,新需求量是原需求量的二倍与现有内存池大小的16分之一之和
    size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);  
    // 当前内存池还有一部分内存，为了不浪费分配给对应的 free_list (最少都为 8)
    if (bytes_left > 0) {
        // 该操作与回收资源类似
        obj *volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left);
        reinterpret_cast<obj *>(start_free)->free_list_link = *my_free_list;
        *my_free_list = reinterpret_cast<obj *>(start_free);
    }
    // 配置 heap 空间以补充内存池 (使用 malloc 函数)
    start_free = reinterpret_cast<char *>(malloc(bytes_to_get));
    if (!start_free) {
        // heap 空间不足，malloc 失败
        obj *volatile *my_free_list;
        obj *p;
        // 1. 先在 free_list 中检查是否有符合需求的区块
        for (size_t i = size; i <= static_cast<size_t>(__MAX_BYTES);
             i += static_cast<size_t>(__ALIGN)) {
            my_free_list = free_list + FREELIST_INDEX(i);
            p = *my_free_list;
            if (p) {
                // 存在足以分配的区块
                *my_free_list = p->free_list_link;  // 抽离当前区块
                start_free = reinterpret_cast<char *>(p);
                end_free = start_free + i;
                // 递归调用以修正 nobjs，此时必然进入 else_if 分支
                return (chunk_alloc(size, nobjs));  
            }
        }
        end_free = nullptr;  // 到处都找不到内存
        // 调用一级配置器观察其能否分配内存，或抛出异常
        start_free = reinterpret_cast<char *>(malloc_alloc::allocate(bytes_to_get));
    }
    // heap 空间充足会运行到该步骤
    heap_size += bytes_to_get;  // 已占用的堆内存
    end_free = start_free + bytes_to_get;
    return chunk_alloc(size, nobjs);  // 调用自身以修正 nobjs
}
图 8 内存池实际操练结果

《STL源码剖析》 – P66 - P69

2.3 内存基本处理工具 uninitialized.h

2.3.1 头文件

1
2
3
4
5
#include <cstring>        // 调用memove()
#include "construct.h"    // 调用构造函数
#include "stl_algobase.h" // 调用 copy()
#include "stl_iterator.h" // 迭代器
#include "typeTraits.h"   // 萃取机

关键的三个函数：

  • uninitialized_copy()
  • uninitialized_fill()
  • uninitialized_fill_n()

2.3.2 uninitialized_copy()

该函数有三个重载版本，分别是一个泛化版本和两个特化版本

两个特化版本：直接使用 memmove() 移动内存

1
2
3
4
5
6
7
8
9
10
//针对char*、wchar_t*存在特化版本 memmove直接移动内存
inline char *uninitialized_copy(const char *first, const char *last, char *result) {
    memmove(result, first, last - first);
    return result + (last - first);
}

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

泛化版本：需要使用萃取机获得型别，后通过不同的型别判断使用何种接口函数。(又是两个特化)

型别：_true_type， _false_type

1
2
3
4
5
6
7
8
template <class InputIterator, class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first,
                                          InputIterator last,
                                          ForwardIterator result) {
    using isPODType =
        typename _type_traits<value_type_t<InputIterator>>::is_POD_type;
    return __uninitialized_copy_aux(first, last, result, isPODType());
}

接口函数：__uninitialized_copy_aux()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// _true_type 说明 trivial 类型，直接调用 STL 中 copy 函数即可
template <class InputIterator, class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first,
                                                InputIterator last,
                                                ForwardIterator result,
                                                _true_type) {
    return MiniSTL::copy(first, last, result);  // in stl_algobase.h
}
// _true_type 说明 non-trivial 类型，使用构造函数来填充
template <class InputIterator, class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first,
                                                InputIterator last,
                                                ForwardIterator result,
                                                _false_type) {
    ForwardIterator cur = result;
    for (; first != last; ++cur, ++first) construct(&*cur, *first);
    return cur;
}

注意：(下同)

is_POD_type 存在两种状态，_true_type, false_type，由萃取机获得。

_true_type 说明 trivial
如果这个类都是 trivial ctor / dtor / copy / assignment 函数
我们对这个类进行构造、析构、拷贝和赋值时可以采用最有效率的方法，不调用无所事事正真的那些 ctor / dtor等，而直接采用内存操作如 *malloc()、memcpy(), memmove()*等提高性能。这也是SGI STL内部干的事情。

_false_type 也就是 non trivial
那么上面的四种函数有(ctor / dtor / copy / assignment) 是 non - trivial 函数，比如 non-trivial ctor、non - trivial copy ，也就是说有意义的函数，里面有一下必要的操作，比如类成员的初始化，释放内存等。这时候只能调用对应的 ctor，copy…

图 9 uninitialized_copy() 的泛型版本与特化版本

可以参考 C++ trivial、non-trivial及POD类型

“typeTraits.h” 头文件中有详细的分类

《STL源码剖析》 – P70, P73 - P75

2.3.3 uninitialized_fill()

该函数是一个泛化版本，但是利用萃取机又可以分为两个特化的接口函数。

泛化版本：需要使用萃取机获得型别，后通过不同的型别判断使用何种接口函数。(两个特化)

型别：_true_type， _false_type

1
2
3
4
5
6
7
template <class ForwardIterator, class T>
inline void uninitialized_fill(ForwardIterator first, ForwardIterator last,
                               const T &value) {
    using isPODType =
        typename _type_traits<value_type_t<ForwardIterator>>::is_POD_type;
    __uninitialized_fill_aux(first, last, value, isPODType());
}

接口函数： __uninitialized_fill_aux()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// _true_type 说明 trivial 类型，直接调用 STL 中 fill 函数即可
template <class ForwardIterator, class T>
inline void __uninitialized_fill_aux(ForwardIterator first,
                                     ForwardIterator last, const T &value,
                                     _true_type) {
    MiniSTL::fill(first, last, value);
}
// _true_type 说明 non-trivial 类型，使用构造函数来填充
template <class ForwardIterator, class T>
void __uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,
                              const T &value, _false_type) {
    ForwardIterator cur = first;
    for (; cur != last; ++cur) construct(&*cur, value);
}
图 10 uninitialized_fill() 的泛型版本与特化版本

《STL源码剖析》 – P71, P75 - P76

2.3.4 uninitialized_fill_n()

该函数是一个泛化版本，但是利用萃取机又可以分为两个特化的接口函数。

泛化版本：需要使用萃取机获得型别，后通过不同的型别判断使用何种接口函数。(两个特化)

型别：_true_type， _false_type

1
2
3
4
5
6
7
template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,
                                            const T &value) {
    using isPODType =
        typename _type_traits<value_type_t<ForwardIterator>>::is_POD_type; 
    return __uninitialized_fill_n_aux(first, n, value, isPODType());      
}

接口函数： __uninitialized_fill_n_aux()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// _true_type 说明 trivial 类型，直接调用 STL 中 fill 函数即可
template <class ForwardIterator, class Size, class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n,
                                                  const T &value, _true_type) {
    return MiniSTL::fill_n(first, n, value);
}

// _true_type 说明 non-trivial 类型，使用构造函数来填充
template <class ForwardIterator, class Size, class T>
ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, Size n,
                                           const T &value, _false_type) {
    ForwardIterator cur = first;
    for (; n > 0; --n, ++cur) construct(&*cur, value);
    return cur;
}
图 11 uninitialized_fill_n() 的泛型版本与特化版本

《STL源码剖析》 – P71 - P73

2.3.5 SGI_STL的扩展

SGI_STL的扩展：

  • uninitializd_copy_copy()
  • uninitialized_copy_fill()
  • uninitialized_fill_copy()

uninitializd_copy_copy()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// __uninitialized_copy_copy
// Copies [first1, last1) into [result, result + (last1 - first1)), and
// copies [first2, last2) into [result, result + (last1 - first1) + (last2 -
// first2)).

template <class InputIterator1, class InputIterator2, class ForwardIterator>
inline ForwardIterator uninitialized_copy_copy(InputIterator1 first1,
                                               InputIterator1 last1,
                                               InputIterator2 first2,
                                               InputIterator2 last2,
                                               ForwardIterator result) {
    ForwardIterator mid = MiniSTL::uninitialized_copy(first1, last1, result);
    try {
        return MiniSTL::uninitialized_copy(first2, last2, mid);
    } catch (std::exception &) {
        destroy(result, mid);
        throw;
    }
}

uninitialized_copy_fill()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// uninitialized_fill_copy
// Fills [result, mid) with x, and copies [first, last) into [mid, mid + (last -
// first)).
template <class ForwardIterator, class T, class InputIterator>
inline ForwardIterator uninitialized_fill_copy(ForwardIterator result,
                                               ForwardIterator mid,
                                               const T &val,
                                               InputIterator first,
                                               InputIterator last) {
    MiniSTL::uninitialized_fill(result, mid, val);
    try {
        return MiniSTL::uninitialized_copy(first, last, mid);
    } catch (std::exception &) {
        destroy(result, mid);
        throw;
    }
}

uninitialized_fill_copy()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// __uninitialized_copy_fill
// Copies [first1, last1) into [first2, first2 + (last1 - first1)), and fills
// [first2 + (last1 - first1), last2) with x.
template <class InputIterator, class ForwardIterator, class T>
inline void uninitialized_copy_fill(InputIterator first1, InputIterator last1,
                                    ForwardIterator first2,
                                    ForwardIterator last2, const T &val) {
    ForwardIterator mid2 = MiniSTL::uninitialized_copy(first1, last1, first2);
    try {
        MiniSTL::uninitialized_fill(mid2, last2, val);
    } catch (std::exception &) {
        destroy(first2, mid2);
        throw;
    }
}

MiniSTL / Allocator / subAllocation / alloc.h : uninitializd_copy_copy()

MiniSTL / Allocator / subAllocation / alloc.h : uninitializd_fill_copy()

MiniSTL / Allocator / subAllocation / alloc.h : uninitializd_copy_fill()

3. 参考资料

《STL源码剖析》

《Effective C++ 3rd》

C++ trivial、non-trivial及POD类型

内存池技术（三） 最后 mem_realloc() 讲解

MiniSTL / Allocator 部分



----------- 本文结束 -----------




0%