前言

以STL的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在一切组件（更具体地说是指容器，container）的背后，默默工作，默默付出。但若以 STL 的实现角度而言，第一个需要介绍的就是空间配置器，因为整个STL 的操作对象（所有的数值）都存放在容器之内，而容器一定需要配置空间以置放资料。不先掌握空间配置器的原理，难免在阅读其它STL组件的实现时处处遇到挡路石。
———— 《STL源码剖析》侯捷

考虑到小型区块所可能造成的内存破碎问题，SGI 设计了双层级配置器，第一级配置器直接使用 malloc() 和 free()，第二级配置器则视情况采用不同的策略：当配置区块超过 128 bytes 时，视之为“足够大”，便调用第一级配置器：当配置区块小于 128 bytes 时，视之为“过小”，为了降低额外负担 overhead，便采用复杂的 memory pool 整理方式，而不再求助于第一级配置器。

SGI 第二级配置器的做法是，如果区块够大，超过 128 bytes 时，就移交第一级配置器处理。当区块小于 128 bytes 时，则以内存池( memory pool）管理，此法又称为次层配置（ sub-allocation) ：每次配置一大块内存，并维护对应之自由链表( free-list )。下次若再有相同大小的内存需求，就直接从free-lists中拨出。如果客端释还小额区块，就由配置器回收到 free-ists 中。是的，配置器除了负责配置，也负责回收。为了方便管理，SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数（例如客端要求 30 bytes、就自动调整为32 bytes ），并维护 16 个 free-lists，各自管理大小分别为 8,16,24,32,40,48,56,64,72.80,88,96,104,112,120,128 bytes的小额区块。

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

重要函数的解释

  1. ROUND_UP

    1
    2
    3
    size_t alloc::ROUND_UP(size_t bytes) {
        return ((bytes + __ALIGN - 1) & ~(__ALIGN - 1));
    }

    ROUND_UP的作用是将指定的字节数 bytes 向上取整为一个对齐的值。

    具体解释如下：

    1. __ALIGN 是一个常量，表示内存对齐的边界值，这里为 8。内存对齐是指要求分配的内存块的起始地址是特定字节数的倍数，以提高内存访问效率。
    2. 函数将 bytes 加上 __ALIGN - 1，相当于向上取整。这是因为要满足对齐的要求，如果 bytes 不是 __ALIGN 的倍数，就需要向上调整到下一个 __ALIGN 的倍数。
    3. 使用位运算 & ~(__ALIGN - 1)，实际上是将结果与 __ALIGN - 1 的二进制补码进行按位取反，再进行按位与操作。这个操作会将低位的非零位都置为 0，将高位保持不变。这样可以将结果向下取整到最接近的 __ALIGN 的倍数。
    4. 最终返回的结果就是向上取整到对齐边界的值。

  2. chunk_alloc()

    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
    /// @brief        从内存池中取空间给 free-lists 使用
    /// @param size   申请区块大小，假设 size 已经上调至 8 的倍数
    /// @param nblock 申请到的区块数量
    char* alloc::chunk_alloc(size_t size, size_t& nblock) {
        char* result;
        size_t total_bytes = size * nblock;         // 需要申请的空间大小
        size_t bytes_left = end_free - start_free;  // 内存池剩余空间大小

        // 如果内存池剩余空间足够，直接返回内存池的首地址
        if (bytes_left >= total_bytes) {
            result = start_free;
            start_free += total_bytes;
            return result;
        }

        // 如果内存池剩余空间不足，但是剩余空间足够一个区块，直接返回内存池的首地址
        else if (bytes_left >= size) {
            nblock = bytes_left / size;
            total_bytes = size * nblock;
            result = start_free;
            start_free += total_bytes;
            return result;
        }

        // 如果内存池剩余大小连一个区块都无法满足
        else {
            // 如果内存池还有剩余，把剩余的空间加入到 free-list 中
            if (bytes_left > 0) {
                FreeList** my_free_list = free_list + FREELIST_INDEX(bytes_left);
                ((FreeList*) start_free)->next = *my_free_list;
                *my_free_list = (FreeList*)start_free;
            }
            
            // malloc申请 heap 中两倍 + 额外大小的内存
            // 额外大小：取 heap_size 的 1/16，用来做额外的缓冲。
            size_t bytes_to_get = (total_bytes << 1) + ROUND_UP(heap_size >> 4);
            start_free = (char *)std::malloc(bytes_to_get);  // 直接使用 malloc 申请内存

            // 堆中空间不足，malloc 失败
            if (start_free == 0) {
                FreeList **my_free_list, *p;
                // 在 free-list 中查找是否有尚未用过且足够大的区块
                for (size_t i = size; i < __MAX_BYTES; i+= __ALIGN) {
                    my_free_list = free_list + FREELIST_INDEX(i);
                    p = *my_free_list;
                    // 尚有未用的区块
                    if (p != 0) {
                        *my_free_list = p->next;
                        start_free = (char*)p;
                        end_free = start_free + i;         // 可用的地址范围
                        return chunk_alloc(size, nblock);  // 递归调用
                    }
                }

                // 如果一点内存都没有了的话，就只有调用一级配置器来申请内存了，并且用户没有设置处理例程就抛出异常
                // 这里并没有使用一级配置器或 std::malloc，而是直接抛出异常，因为实际上一级配置器也是使用 malloc()
                // 配置内存，只是多了一个 out-of-memory handler 的处理，简单起见，malloc() 配置失败后直接抛出异常
                std::printf("out of memory!");
                end_free = nullptr;
                throw std::bad_alloc();  // 这里直接抛出异常
            }

            // 申请内存成功后重新修改内存起始地址和结束地址, 重新调用chunk_alloc分配内存
            heap_size += bytes_to_get;             // 更新 heap_size 大小，随着申请的次数逐渐增加
            end_free = start_free + bytes_to_get;  // 更新内存池结束位置
            return(chunk_alloc(size, nblock));     // 递归调用，修正 nblock 的值
        }
    }

    上述的 chunk_alloc() 函数以 end_free - start_free 来判断内存池的水量。如果水量允足，就直接调出20个区块返回给free list。如果水量不足以提供 20 个区块，但还足够供应一个以上的区块，就拨出这不足 20 个区块的空间出去。这时候其 pass by reference 的 nblock 参数将被修改为实际能够供应的区块数。如果内存池连一个区块空间都无法供应，对客端显然无法交待，此时便需利用 malloc() 从 heap 中配置内存，为内存池注入活水源头以应付需求。新水量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。

    举个例子，见图 2-7，假设程序一开始，客端就调用 chunk_alloc(32, 20)，于是 malloc() 配置 40 个 32 bytes 区块，其中第 1 个交出，另 19 个交给 free_list[3] 维护，余 20 个留给内存池。接下来客端调用 chunk_alloc(64,20)，此时 free_list[7] 空空如也，必须向内存池要求支持。内存池只够供应 (32 * 20) / 64 = 10 个 64 bytes 区块，就把这 10 个区块返回，第 1 个交给客端，余 9 个由 free_list[7] 维护。此时内存池全空．接下来再调用 chunk_alloc(96, 20)，此时free_list [11] 空空如也，必须向内存池要求支持，而内存池此时也是空的，于是以 malloc() 配置 40 + n(附加量) 个 96 bytes 区块，其中第 1 个交出，另 19 个交给 free_list[11] 维护，余 20+n (附加量) 个区块留给内存池。

    万一山穷水尽，整个 system heap 空问都不够了（以至无法为内存池注入活水源头）, malloc() 行动失败，chunk_alloc() 就四处寻找有无 “尚有未用区块，且区块够大” 之 free lists。找到了就挖一块交出，找不到就调用第一级配置器。第一级配置器其实也是使用 malloc() 来配置内存，但它有 out-of-memory 处理机制(类似 new-handler 机制)，或许有机会释放其它的内存拿来此处使用。如果可以，就成功，否则发出 bad_alloc 异常。

    2.png

完整实现

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
#ifndef TINYSTL_ALLOC_H_
#define TINYSTL_ALLOC_H_

// 这个头文件包含一个类 alloc，用于分配和回收内存，以内存池的方式实现

#include <new>        // placement new
#include <cstddef>    // ptrdiff_t, size_t
#include <cstdio>     // std::fprintf
#include <cstdlib>    // std::malloc, std::free

namespace tinystl {

// 二级空间配置器的参数设置
enum {__ALIGN = 8};  // 小型区块的上调边界
enum {__MAX_BYTES = 128};  // 小型区块的上限
enum {__NFREELISTS = __MAX_BYTES / __ALIGN};  // free-lists 个数

/// @brief 共用体 FreeList，采用链表的方式管理内存碎片，分配与回收小内存区块
//  这里未使用 volatile，因为不考虑多线程情况
union FreeList {
    union FreeList* next;  // 指向下一个区块
    char data[1];  // 本区块的起始位置
};

/// @brief 二级空间配置器
/// 注意，这里并没有 template 型别参数
class alloc {
private:
    static char*     start_free;  // 内存池起始位置
    static char*     end_free;    // 内存池结束位置
    static size_t    heap_size;   // 申请 heap 空间附加值的大小

    static FreeList* free_list[__NFREELISTS];  // 自由链表

public:
    static void*     allocate(size_t n);
    static void      deallocate(void* p, size_t n);
    static void*     reallocate(void* p, size_t old_sz, size_t new_sz);

private:
    static size_t    ROUND_UP(size_t bytes);                   // 上调边界至 8 的倍数
    static size_t    FREELIST_INDEX(size_t bytes);             // 根据区块大小计算 free-lists 的下标
    static void*     refill(size_t n);                         // 重新填充 free-lists
    static char*     chunk_alloc(size_t size, size_t &nobjs);  // 从内存池中取空间给 free-lists 使用
};

// 静态成员变量的初始化
char* alloc::start_free = nullptr;  // 内存池起始位置
char* alloc::end_free = nullptr;    // 内存池结束位置
size_t alloc::heap_size = 0;        // 申请 heap 空间附加值的大小

/// @brief free-lists，自由链表，初始化为 16 个 nullptr
FreeList* alloc::free_list[__NFREELISTS] = {
    nullptr,nullptr,nullptr,nullptr,nullptr,nullptr,nullptr,nullptr,
    nullptr,nullptr,nullptr,nullptr,nullptr,nullptr,nullptr,nullptr
};

/// @brief 分配大小为 n 的空间
/// @param n  分配空间的大小 
/// @return 分配的空间的首地址
void* alloc::allocate(size_t n) {
    FreeList** my_free_list;  // 指向对应的 free-lists 指针的指针，注意这里是二级指针
    FreeList* result;         // 返回的空间的首地址
    
    // 如果 n 大于 128，直接调用一级配置器
    if (n > static_cast<size_t>(__MAX_BYTES)) {
        // 这里没有使用一级配置器，而是直接调用 std::malloc
        // 但是逻辑相同，几乎都是直接调用 malloc
        return std::malloc(n); 
    }

    // 找到对应的 free-list
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;

    // 如果 free-list 为空，重新填充 free-list
    if (result == nullptr) {
        void* r = refill(ROUND_UP(n));
        return r;
    }

    // 原先的 free-list 首地址的内存块已经被分配出去了，
    // 因此需要更新 free-list 首地址，指向下一个区块
    *my_free_list = result->next;  
    return result;
}

/// @brief 释放 p 指向的大小为 n 的空间
/// @param p  指向空间的首地址
/// @param n  空间的大小
void alloc::deallocate(void* p, size_t n) {
    // 如果 n 大于 128，直接调用一级配置器释放内存
    if (n > static_cast<size_t>(__MAX_BYTES)) {
        // 这里没有使用一级配置器，而是直接调用 std::free
        // 但是逻辑相同，几乎都是直接调用 free
        std::free(p);
        return;
    }
    
    // 将 p 转换为 FreeList* 类型
    FreeList*  q = reinterpret_cast<FreeList*>(p);  
    FreeList** my_free_list;
    
    my_free_list = free_list + FREELIST_INDEX(n);  // 找到对应的 free-lists
    q->next = *my_free_list;                       // 将 q 插入到 free-lists 的头部
    *my_free_list = q;                             // 更新 free-lists 首地址
}

/// @brief 重新为 p 指向的 old_sz 大小的空间分配大小为 new_sz 的空间
/// @param p       指向空间的首地址
/// @param old_sz  旧空间的大小
/// @param new_sz  新空间的大小
/// @return        新空间的首地址
void* alloc::reallocate(void* p, size_t old_sz, size_t new_sz) {
    deallocate(p, old_sz);  // 释放旧空间
    p = allocate(new_sz);   // 重新分配大小为 new_sz 的新空间
    return p;
}

/// @brief       将 bytes 上调至 8 的倍数
/// @param bytes 申请区块大小
/// @return      上调后的空间大小
size_t alloc::ROUND_UP(size_t bytes) {
    return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
}

/// @brief        根据区块大小计算 free-lists 的下标
/// @param bytes  区块大小
/// @return       free-lists 的下标
size_t alloc::FREELIST_INDEX(size_t bytes) {
    return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
}

/// @brief   重新填充 free-lists
/// @param n 申请区块大小
/// @return  申请到的一个区块的首地址
void* alloc::refill(size_t n) {
    size_t nblock = 20;  // 一次性申请的区块数量，指定为 20
    
    // 调用 chunk_alloc 申请 nblock 个大小为 n 的区块
    // 注意这里的 nblock 是引用，因此 chunk_alloc 会修改 nblock 的值
    // 这样才能通过 nblock 来判断最终申请到的区块数量
    char* chunk = chunk_alloc(n, nblock);
    
    FreeList** my_free_list;
    // 这里要注意 * 的修饰范围，才能确保三个变量都声明为 FreeList* 类型
    // FreeList* result, cur, next;  // 这样写是错误的
    FreeList *result, *cur, *next;  

    // 如果只申请到一个区块，直接返回申请到的区块
    if (nblock == 1) return chunk;

    my_free_list = free_list + FREELIST_INDEX(n);
    result = (FreeList*) chunk;  // 返回的空间的首地址
    
    // 由于将第一个区块作为返回值（第一个区块会返回给用户），
    // 因此需要将 free-lists 的首地址偏移 n 个字节，指向下一个区块
    *my_free_list = next = (FreeList*)(chunk + n);
    
    // 将剩余的区块插入到 free-lists 中
    for (size_t i = 1; ; i++) {
        cur = next;
        next = (FreeList*)((char*)next + n);  // 指向下一个区块
        if (nblock - 1 == i) {
            cur->next = nullptr;
            break;
        }
        cur->next = next;
    }

    return result;
}


/// @brief        从内存池中取空间给 free-lists 使用
/// @param size   申请区块大小，假设 size 已经上调至 8 的倍数
/// @param nblock 申请到的区块数量
char* alloc::chunk_alloc(size_t size, size_t& nblock) {
    char* result;
    size_t total_bytes = size * nblock;         // 需要申请的空间大小
    size_t bytes_left = end_free - start_free;  // 内存池剩余空间大小

    // 如果内存池剩余空间足够，直接返回内存池的首地址
    if (bytes_left >= total_bytes) {
        result = start_free;
        start_free += total_bytes;
        return result;
    }

    // 如果内存池剩余空间不足，但是剩余空间足够一个区块，直接返回内存池的首地址
    else if (bytes_left >= size) {
        nblock = bytes_left / size;
        total_bytes = size * nblock;
        result = start_free;
        start_free += total_bytes;
        return result;
    }

    // 如果内存池剩余大小连一个区块都无法满足
    else {
        // 如果内存池还有剩余，把剩余的空间加入到 free-list 中
        if (bytes_left > 0) {
            FreeList** my_free_list = free_list + FREELIST_INDEX(bytes_left);
            ((FreeList*) start_free)->next = *my_free_list;
            *my_free_list = (FreeList*)start_free;
        }
        
        // malloc申请 heap 中两倍 + 额外大小的内存
        // 额外大小：取 heap_size 的 1/16，用来做额外的缓冲。
        size_t bytes_to_get = (total_bytes << 1) + ROUND_UP(heap_size >> 4);
        start_free = (char *)std::malloc(bytes_to_get);  // 直接使用 malloc 申请内存

        // 堆中空间不足，malloc 失败
        if (start_free == 0) {
            FreeList **my_free_list, *p;
            // 在 free-list 中查找是否有尚未用过且足够大的区块
            for (size_t i = size; i < __MAX_BYTES; i+= __ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                // 尚有未用的区块
                if (p != 0) {
                    *my_free_list = p->next;
                    start_free = (char*)p;
                    end_free = start_free + i;         // 可用的地址范围
                    return chunk_alloc(size, nblock);  // 递归调用
                }
            }

            // 如果一点内存都没有了的话，就只有调用一级配置器来申请内存了，并且用户没有设置处理例程就抛出异常
            // 这里并没有使用一级配置器或 std::malloc，而是直接抛出异常，因为实际上一级配置器也是使用 malloc()
            // 配置内存，只是多了一个 out-of-memory handler 的处理，简单起见，malloc() 配置失败后直接抛出异常
            std::printf("out of memory!");
            end_free = nullptr;
            throw std::bad_alloc();  // 这里直接抛出异常
        }

        // 申请内存成功后重新修改内存起始地址和结束地址, 重新调用chunk_alloc分配内存
        heap_size += bytes_to_get;             // 更新 heap_size 大小，随着申请的次数逐渐增加
        end_free = start_free + bytes_to_get;  // 更新内存池结束位置
        return(chunk_alloc(size, nblock));     // 递归调用，修正 nblock 的值
    }
}

}  // namespace tinystl

#endif  // TINYSTL_ALLOC_H_

总结

总的来说，STL 的二级配置器 alloc 使用了 free-list 及内存池的方式解决了单独使用 malloc() 申请空间时存在的诸多问题。

首先是内存碎片问题：已分配的内存块和空闲的内存块交替排列，导致在总体上看，仍有足够的空闲内存，但无法找到足够大的连续内存块来满足分配请求。这会造成可用内存实际上被浪费了，因为无法有效地满足分配请求，即使总体剩余的空闲内存足够大。alloc 使用内存池技术，利用 chunk_alloc() 每次都申请一块较大内存并将其划分为小区块使用，减少了频繁的小块内存分配和释放导致的内存碎片问题。并且，一次性申请较大的内存也有助于降低申请内存时的额外开销。

其次，alloc 使用 free-list 管理小区块内存，小于 128 bytes 的小区块内存统一由 free-list 分配与回收，减少了 malloc() 及 free() 的使用次数，提高了效率。