【STL 源码剖析】系列二：空间配置器 allocator

发表于 更新于 分类于 阅读次数： 30 本文字数： 4.5k 阅读时长 ≈ 15 分钟

前言

STL 的空间配置器，负责的主要工作是容器的空间管理，一般情况下空间都是指内存（存在将空间置于外存的配置器），所以也可称为内存管理器。

读完《STL 源码剖析》第二章内容，需要知道的是：
1.SGI 标准下将空间配置和构造析构分为两个阶段。空间配置是申请和释放内存；构造析构是对象的创建和销毁。
2.SGI 标准下的空间配置器 alloc 具有两级，第一级负责 128 字节以上的空间申请，第二级以内存池的形式管理。二者均以字节为单位管理内存，对外提供标准接口以元素为单位管理内存。

3. 对于未初始化的空间除了构造和析构的支持外，还提供复制、填充、以对象 x 填充的管理操作。

空间配置器 allocator

image-20231008091511056 image-20231008091534119

空间配置器的标准接口

image-20231008105406145 image-20231008105431614 image-20231008105452081

设计一个简单的空间配置器：JJ::allocator

知识点 1：ptrdiff_t 是表示指针之间的差距的数据类型，可以是负数；size_t 是表示数组长度的类型，必须是正数。

知识点 2：**set_new_handler ()** 函数定义在头文件 new 中，当 operator new 函数申请分配内存失败时，会尝试调用错误处理函数，这个函数如果不存在就会抛出异常。使用 set_new_handler 函数可以指定这个 handler 函数。

知识点 3：placement new 指的是在用户指定的内存位置上申请空间。语法格式为：

1
2
3
// address：placement new所指定的内存地址
// ClassConstruct：对象的构造函数
Object * p = new (address) ClassConstruct(...);

知识点 4：作用域解析运算符::(1) 作用 1 是表示指定类中的成员或者命名空间中的成员，比如使用 A::member 表示类 A 中的成员；(2) 作用 2 是当前面没有类或者命名空间时，表示全局作用域符号，可以用于区分同名的全局和局部变量。

1
2
3
4
5
6
7
8
int jmz = 2; //全局变量
int main() {
    int jmz = 3; //局部变量
    jmz = jmz* jmz;//局部=局部*局部
    ::jmz = ::jmz* jmz;//全局=全局*局部
    cout << jmz << endl;
    cout << ::jmz << endl;
}

自定义一个 allocator 类：

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#ifndef _JJALLOC_
#define _JJALLOC_

#include <new> // for placement new
#include <cstddef> // for ptrdiff_t, size_t
#include <cstdlib> // for exit()
#include <climits> // for UINT_MAX
#include <iostream> // for cerr

namespace JJ {

// allocate的实际实现，申请size个T类型的空间
template <typename T>
inline T* _allocate(ptrdiff_t size, T*) {
    set_new_handler(0); // 设置当new失败时的处理函数为空，所以会直接退出
    T* tmp = (T*)(::operator new((size_t)(size * sizeof(T)))); // 申请size个T类型的空间
    // 如果得到空指针
    if (tmp == 0) {
        cerr << "out of memory" << endl;
        exit(1); // 退出
    }

    return tmp;
}

// deallocate的实际实现，释放指定位置内存
template <typename T>
inline void _deallocate(T *buffer) {
    ::operator delete(buffer); // 调用global operator delete
}

// construct的实际实现，在指定位置创建一个对象
template <typename T1, typename T2>
inline void _construct(T1 *p, const T2 &value) {
    new(p) T1(value);
}

// destory的实际实现，调用指定对象的析构函数
template <typename T>
inline void _destory(T *ptr) {
    ptr->~T();
}

// 自定义的空间配置器类
template <typename T>
class allocator {
public:
    // 定义类型
    typedef T           value_type;
    typedef T*          pointer;
    typedef const T*    const_pointer;
    typedef T&          reference;
    typedef const T&    const_reference;
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;

    // 一个嵌套的类模板
    // rebind allacator of type U
    template <typename U>
    struct rebind {
        typedef allocator<U> other;
    }

    // 配置空间，用于存储n个T对象
    // hint used for locality
    pointer allocate(size_type n, const void *hint = 0) {
        return _allocate((difference_type)n, (pointer)0);
    }

    // 归还配置的空间
    void deallocate(pointer p, size_type n) {
        _deallocate(p);
    }

    // 使用T对象value在指定位置p创建一个新对象T
    void construct(pointer p, const T &value) {
        _construct(p, value);
    }

    // 析构指定位置p的对象T
    void destory(pointer p) {
        _destory(p);
    }

    // 返回某个对象的地址
    pointer address(reference x) {
        return (pointer)&x;
    }

    // 返回某个const对象的const地址
    const_pointer const_address(const_reference x) {
        return (const_pointer)&x;
    }

    // 返回可成功配置的最大值
    size_type max_size() const {
        return size_type(UINT_MAX/sizeof(T));
    }

};


} // end of namespace JJ

#endif

使用 MinGW 无法通过编译，因为 SGI STL 的 allocator 并不完全符合 STL 规范，我们编写的符合规范的自然不能搭配使用。

具备层次配置能力的 SGI 空间配置器

image-20231009093741874

SGI 标准的空间配置器 std::allocator

这个 allocator 部分符合 STL 标准，它在文件 defalloc.h 中实现。但是 SGI STL 的容器并不使用它，也不建议我们使用，它存在的意义仅在于为用户提供一个兼容老代码的折衷方法，其实现仅仅是对 new 和 delete 的简单包装因此效率不高。

SGI 特殊的空间配置器 std::alloc

C++ 内存配置操作和释放操作：

1
2
3
class Foo {...};
Foo *pf = new Foo; // 配置内存，然后构造对象
delete pf;	// 析构对象，然后释放内存

new 运算符包括两给阶段的操作：（1）调用::operatro new 配置内存；（2）调用 Foo::Foo () 构造对象内容；

delete 运算符号包括两阶段的操作：（1）调用 Foo::~Foo () 将对象析构；（2）调用::operator delete 释放内存。

image-20231009193732479 image-20231009194118094 image-20231009194159187

构造和析构的基本工具：construct () 和 destory ()

construct () 和 destory () 示意图：
image-20231009200509941

下面是作者注释的 <stl_construct.h> 的部分内容，主要是为了说明 construct 和 destroy 的功能。（不同版本的 SGI STL 代码可能不同，但是设计思路是一致的。）

image-20231009201210619 image-20231009201251845

这两个构造和析构的函数被设计为全局函数，STL 规定配置器应该具有 construct 和 destroy 两个成员函数，但是实际上 SGI STL 中的 std::alloc 配置器并没有遵守这一规则。

关于上面的 construct 函数：接收一个指针 p 和一个初始值 value，改函数的作用就是将初始值 value 设置到指针所指的空间上。（使用 C++ placement new 完成）

关于上面的 destroy 函数：第一个版本接受一个指针，将指针所指的对象析构。第二个版本接收 first 和 last 两个迭代器，准备将 [first, last) 内的对象析构。考虑到这个范围可能很大，并且如果每个对象的析构函数都是 trivial destructor (即系统默认的析构函数)，那么会降低效率。因此这里的方法是先利用 **vaule_type () 获得迭代器所指对象的类型，再利用__type_traits<T>** 判断这种类型的析构函数是否无关痛痒。如果是 (__true_type)，那么什么都不做；如果否 (__false_type)，以循环方式遍历每一个对象，并对于每一个对象调用第一个版本的 destroy ()。

空间配置和释放，std::alloc

image-20231010114141367

为了解决小型区块可能造成的内存破碎的问题，SGI 设计采用了双层配置器，第一级配置器直接使用 malloc 和 free，第二级配置器当配置区块超过 128bytes 时，认为内存够大调用第一级配置器，否则认为过小，采用内存池（memory pool）的方式。第一级和第二级配置器的关系：

image-20231010114558211

无论 alloc 被定为第一级还是第二级配置器，SGI 都为其增加一层包装为 simple_alloc。第一级配置器和第二级配置器的包装以及使用方式：

image-20231010114745673

第一级配置器解析 malloc_alloc_template

第一级配置器以 malloc ()、free ()、realloc () 等 C 函数实现实际的内存配置、释放、重配置操作。

1
2
3
4
void * malloc(size_t size); // 申请大小为size个字节的内存，如果分配成功返回一个void *指针，否则返回空指针
void * realloc(void *ptr, size_t size); // 更改已经分配的内存空间的大小，返回新的空间地址
void * calloc(size_t num, size_t size); // 申请num个大小为size个字节的内存空间
void  free(void *ptr); // 释放指针指向内存

（第一级配置器定义为 template <int inst> class __malloc_alloc_template，在使用时会指定 inst 为 0，

1
typedef __malloc_alloc_template<0> malloc_alloc; // 之后就可以将malloc_alloc作为第一级配置器的名称

这样用户在不知道这个类是什么模板的情况下无法生成其它模板。下面均是类中的成员定义）

image-20231010161734519 image-20231010161806524

由于作者采用的版本仍然使用 malloc 等 C 函数，所以并没有用到 C++ 中的 new-handler 机制（即当 new 申请空间失败时，在抛出 std::bad_alloc 异常之前，可以选择调用一个指定的处理函数，参考《Effective C++》第三版条款 49）。所以这个版本的 SGI 第一级配置器实现了一个类似的 set_malloc_handler：

（下面仍然是第一级配置器类内的成员函数）

image-20231010162652236

（下面是在类外进行 malloc-handler 函数的初始化）

image-20231010162717093 image-20231010162823575

如果第一级配置器的 allocate 和 realloca 在调用 malloc 和 realloc 失败之后，改为调用 oom_malloc 和 oom_realloc，后二者都有内循环，不断调用” 内存不足处理例程 “（即 new-handler），希望能够处理好内存分配工作。但是如果未设置 new-handler（即为空指针时）则直接抛出异常。

image-20231010163535768 image-20231010163624088

第二级配置器解析 default_alloc_template

为什么需要第二级配置器？避免太多小额区块造成内存碎片，以及配置时的额外负担（overhead）。如果区块越小，那么额外负担所占比例就越大。
image-20231010184810091

第二级配置器的做法是：如果申请区块超过 128byte，交给第一级配置器处理；否则以内存池管理，此方法又称为次层配置。

所谓内存池，就是先配置一大块内存，使用自由链表（free-list）管理，当有需要相同大小的内存需求时，从自由链表中取出一块内存使用；如果归还空间，就添加到链表上。

为了方便管理，第二级配置器会把任何区块需求量上调至 8 字节的倍数，一共维护 16 个 free-list，大小分别为 8，16，…，128。free-list 的结点结构为：

1
2
3
4
union obj {
	union obj *free_list_link;
    char client_data[1];
};

使用 union 节省空间的巧妙之处：当没有作为用户使用的空间时，在链表上使用第一个字段指向下一个 obj；当作为用户使用的空间时，使用第二个字段指向实际区块。

image-20231010185528301

下面是第二级配置器的实现内容：

image-20231010185623532 image-20231011153809092 image-20231010185751889 image-20231010185811896

空间配置函数 allocate

接口函数 **allocate () 的主要流程是：先判断区块大小，如果超过 128byte，就交给第一级配置器；小于 128 就检查对应的 free list，如果链表上有可用的区块，就直接取第一块来用，如果没有，就将区块大小上调至 8 的倍数，然后调用 refill ()** 函数为这一个 free list 填充空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void * allocate(size_t n) {
    obj * volatile * my_free_list;
    obj *result;
    // 大于128就调用第一级配置器
    if (n > (size_t)__MAX_BYTES) {
        return malloc_alloc::allocate(n);
    }
    
    // 循环16个free list中适当的一个
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == 0) {
        // 如果free list上没有空闲的区块就重新填充区块
        void *r = refill(ROUND_UP(n));
        return r;
    }
    
    // 取出当前free list的第一个区块
    *my_free_list =- result->free_list_link;
    return result;
}
image-20231011154406479

空间释放函数 deallocate

接口函数 **deallocate ()** 主要流程是：如果内存块大于 128byte，调用第一级配置器释放内存；否则找到区块大小对应的 free list，将这个区块插在链表第一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void deallocate(void *p, size_t n) {
    obj *q = (obj *)p;
    obj * volatile *my_free_list;
    
    // 大于128就调用第一级配置器
    if (n > (size_t)__MAX_BYTES) {
        malloc_alloc::deallocate(p, n);
        return;
    }
    
    // 找到对应大小的free list
    my_free_list = free_list + FREELIST_INDEX(n);
    // 调整free list，将区块插入为第一个
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}
image-20231011161922484

重新填充链表函数 refill

当 allocate 发现适当位置的链表为空时，就调用 **refill ()** 为这一个链表重新填充空间。新的空间取自内存池（由 chunk_alloc 完成）。默认情况下获取 20 个新区块，如果内存池空间不足，获取区块数会小于 20.

image-20231011163212262 image-20231011163410061

内存池 (memory pool) 管理

chunk_allco 函数以 end_free - start_free（单位是字节数）来判断内存池中的空间。
如果空间足够满足总需求量（默认是 20 个需求大小区块），那么直接将空间分配；
如果空间不够总需求量，但是可以满足至少一个（含）以上需求区块大小，那么修改默认返回的区块大小（也就是将 20 转换为实际上能够满足的区块数量），然后将这些空间返回；
如果空间连一个需求的区块大小都不能满足，那么就需要向堆区申请内存，申请内存大小为 2 倍的总需求量加上一个随着分配次数越来越大的附加量。不过在正式向堆区申请内存之前，先将内存池中的零头分配给适当的 free list。之后正式调用 malloc 函数向堆区申请内存。如果申请成功，那么就调用自身将需求满足；如果申请失败，那么先尝试将 free list 中未使用并且足够大的（也就是空间至少大于 1 个需求区块大小）区块拿出来，补充内存池空间，然后调用自己分配内存。如果 free list 后面的均为空，那么最后尝试将任务交给第一级配置器尝试进行分配。

image-20231015172629792 image-20231015172815949 image-20231015173027951 image-20231015173123208 image-20231015173205110

总结

无论是第一级还是第二级配置器，最终都被 simple_alloc 包装：

image-20231015173352882

使用配置器的方法：

image-20231015173532284 image-20231015173546855

缺省参数 alloc 已经被 typename 为第一级配置器或者第二级配置器，SGI STL 将其设置为第二级配置器。

内存处理基本工具

STL 定义五个全局函数，用于处理未初始化空间。前两个是用于构造的 construct 和用于析构的 destroy，另外三个是 uninitialized_copy ()、uninitialized_fill ()、uninitialized_fill_n ()，对应着高层次函数 copy、fill、fill_n。如果想要使用这三个此层次函数，应该包含头文件 memory，但是实际定义于 stl_uninitialized。

概述

uninitialized_copy：

1
2
3
template <typename InputIterator, typename ForwardIterator>
ForwardIterator
uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result);

将内存的申请与对象的初始化行为分开，主要负责完成对象的初始化功能。

对于目的地 result，调用复制构造函数，利用 [first, last) 的每一个迭代器指向的对象复制一个新的对象。相当于调用了 construct (&*(result + (i - first)), *i)，在相应的位置产生相应的复制品。

如果需要实现一个容器，容器的全区间构造函数（range constructor）通常以两个步骤完成：
1. 申请内存空间，足以包含范围内所有元素；
2. 使用 uninitialized_copy 在内存空间上构造元素。

C++ 标准要求具有 commit or rollback 特性，也就是要么构造出所有元素，要么一个都不构造。

uninitialized_fill：

1
2
template <typename ForwardIterator, typename T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T &x);

将内存的申请与对象的初始化行为分开，主要负责完成对象的初始化功能。

对于 [first, last) 迭代器指向的内存，均使用 x 进行初始化。也就是对于范围内的每个迭代器 i 指向的内存地址调用 construct (&*i, x)。

同样需要具有 commit or rollback 特性。

uninitialized_fill_n：

1
2
3
template <typename ForwardIterator, typename Size, typename T>
ForwardIterator
uninitialized_fill_n(ForwardIterator first, Size n, const T &x);

将内存的申请与对象的初始化行为分开，为指定范围内的所有元素设定相同的初始值。

对于 [first, first + n) 范围内的每一个迭代器指向的内存调用复制构造函数，产生 x 的复制品。

同样需要具有 commit or rollback 特性。

源代码

uninitialized_fill_n：

image-20231016091351869 image-20231016091507205 image-20231016091617090

uninitialized_copy：

image-20231016091714181 image-20231016091755619 image-20231016091905466 image-20231016091935680

uninitialized_fill：

image-20231016092012397 image-20231016092106840

源代码总结

image-20231016092217446