有关SGI STL的alloc

    在STL的利用者层面上，空间设置器一般是隐藏的，利用者不必要知道其具体实现细节即
可进利用用；但是从STL的实现角度来说，由于整个STL的操作对象都存放在容器之内，而容器
必要设置肯定的空间来进行存放数据，因此，想要实现或者说深入了解STL的第一步便是掌握
空间设置器的原理。

目次
紧张还是说说SGI版本的STL的设置器

---

我们知道，stl有容器，空间设置器，适配器，迭代器，仿函数以及算法这6个组件：他们之间的运行关系大概是：容器通过设置器去获得数据和存储空间，算法通过迭代器获取容器内容,仿函数可以协助算法完成不同的计谋变化,配接器可以修饰或套界仿函数。
allocator是STL的紧张构成，但是一般用户不怎么熟悉他，由于allocator隐藏在所有容器（包括vector）身后，默默完成内存设置与开释，对象构造和析构的工作。

首先我们知道c++中内存分配和开释操作是由new和delete去完成的

1. class A {};
2. A* p = new A;
3. //...执行其他操作
4. delete p;
6. 在我们使用new来建造一个对象的时候，一般是分为两个步骤的：
7.         1.调用::operator new()来构建空间；
8.         2.调用对象的构造函数。
9.         注：::operator new内部由malloc实现、省略指针转换这步。
11.         同理，当我们使用delete函数的时候：
12.         1.调用对象的析构函数
13.         2.调用::operator delete()释放空间。
14.         注：::operator delete内部由free实现

复制代码

在STL的实现中，为了精细分工、STL allocator决定将上述步骤的两阶段操作分开来，内存
设置操作由alloc::allocate()负责，内存开释由alloc::deallocate负责，对象构建
操作由construct负责，对象析构操作由destroy负责。对于实现我就不过多赘述了
下面紧张还是说说SGI版本的STL的设置器

对于SGI STL的实现来说、他这里含有了两个不同的空间设置器
第一个是一个符合部门尺度、名为allocatr的设置器std::allocator

2. 仅仅是将::operator new()和
3. ::operator delete()做了一层简单的封装，因此效率比较差。

复制代码

它存在的意义仅在于为用户提供一个兼容老代码的折衷方法，我们不建议利用，而且SGI内部也倒霉用这种尺度的设置器，看一下了解一下

1. #ifnedf DEFALLOC_H
2. #define DEFALLOC_H
4. #include <new.h>
5. #include <stddef.h>
6. #include <stdlib.h>
7. #include <limits.h>
8. #include <iostream.h>
9. #include <algobase.h>
11. template <class T>
12. inline T* allocate(ptrdiff_t size, T*) {
13.     set_new_handler(0);
14.     T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
15.     if (tmp == 0) {
16.         cerr << "out of memory" << endl;
17.         exit(1);
18.     }
19.     return tmp;
20. }
22. template <class T>
23. inline void deallocate(T* buffer) {
24.     ::operator delete(buffer);
25. }
27. template <class T>
28. class allocator {
29. public:
30.     typedef T value_type;
31.     typedef T* pointer;
32.     typedef const T* const_pointer;
33.     typedef T& reference;
34.     typedef const T& const_reference;
35.     typedef size_t size_type;
36.     typedef ptrdiff_t difference_type;
38.     pointer allocate(size_type n) { return ::allocate((difference_type)n, (pointer)0); }
39.     void deallocate(pointer p) { ::deallocator(p); }
40.     pointer address(reference x) { return (pointer)&x; }
41.     const_pointer const_address(const_reference x) { return (const_pointer)&x; }
42.     size_type init_page_size() {
43.         return max(size_type(1), size_type(UINT_MAX/sizeof(T)));
44.     }
45. };
47. class allocator<void> {
48. public:
49.     typedef void* pointer;
50. }；

复制代码

第二个是我们必要重点掌握的特殊设置器 std::alloc

这个设置器是SGI STL的默认设置器，它在<memory>中实现。
<memory>中包含三个文件：

• <stl_construct.h>：定义了全局函数construct()和destroy()，负责对象构造和析构。
  
• <stl_alloc.h>：内存设置和开释在此处实现，其内部有两级设置器，第一级结构简单，封装malloc()和free()，第二级实现了自由链表和内存池，用于提升大量小额内存设置时的性能。
  
• <stl_uninitialiezed.h>：一些用于用于填充和拷贝大块内存的全局函数。
  

对象构造和/析构，与内存设置/开释是分离实现的。

1. SGI对于alloc函数的要求如下所示：
2.         1.向system heap要求空间
3.         2.考虑多线程状态
4.         3.考虑内存不足的应变措施
5.         4.考虑过多“小型区块”可能造成的内存碎片问题。

复制代码

 

 两层设置器的关系如下：
根据情况来判定，如果设置区块大于128bytes，说明“足够大”，调用第一级设置器，而小于等于128bytes，则采用复杂内存池（memory pool）来管理。

同时为了自由选择，STL又规定了 __USE_MALLOC 宏，如果它存在则直接调用第一级设置器，不但是直接调用第二级设置器。SGI未定义该宏，也就是说默认利用第二级设置器
 由于一级设置器存在内存碎片的问题，所以有了二级设置器

转自《STL源码剖析》 的SGI STL特殊设置器的内部实现图

图示左边是用户代码，右边是STL的内部。
我们可以看到，用户代码实例化一个vector对象，vector对象调用alloc的接口，注意，不同于之前尺度的allocator，这里不必要实例化一个空间设置器，只必要调用alloc的静态函数就行了。
std::alloc的接口与尺度非常相似：

• static T* allocate()函数负责空间设置，返回一个T对象巨细的空间。
  
• static T* allocate(size_t)函数负责批量空间设置。
  
• static void deallocate(T*)函数负责空间开释。
  
• static void deallocate(T*,size_t)函数负责批量空间开释。
  

在接口之下，我们看到另有两级设置器，上面的接口根据情况调用这两个设置器，第二级设置器实现了内存池和自由链表，当步调多次进行小空间的设置时，可以从内存池和自由链表中获取空间，减少系统调用，提升性能。当进行大空间的设置时，上面的接口直接调用第一级设置器。终极，它们都是用malloc()和free()来设置和开释空间。
一般C++开发者了解到此已经足够应付大多数开发场景了。
这样看起来std::alloc的结构还算清晰，但是实际实现还会出现多种边界情况，比如，当系统调用malloc()空间不足时，我们必要让第一级设置器来处理，这大概涉及从第二级设置器中回收已经缓存但还未利用的空间，事情就变得繁琐了。
下面来手撕两层设置器的实现：

• 一级空间设置器
  

一级设置器直接用C中的malloc()以及free()函数来进行处理，当我们的内存分配不足的时候，我们调用oom_malloc()函数和oom_realloc进行处理,这两个函数里面都有循环，不断地去调用“内存不足，要调用例程”，行止理。

1. #if 1
2. #include<new>
3. #define __THROW_BAD_ALLOC throw bad_alloc
4. #else !defined(__THROW_BAD_ALLOC)
5. #define __THROW_BAD_ALLOC cerr<<"out of memory"<<endl;
6. #endif
8. template<int inst>
9. class __malloc_alloc_template
10. {
11. private:
12.         static void* oom_malloc(size_t);//malloc--指针函数
13.         static void* oom_realloc(void*, size_t);//realloc--指针函数
14.         static void(*__malloc_alloc_oom_handler)();//函数指针
15. public:
16.         static void* allocate(size_t n)//申请空间
17.         {
18.                 void* result = malloc(n);//第一级配置器直接使用malloc
19.                 //如果无法满足需求，费用oom_malloc()
20.                 if (result == 0) {
21.                         result == oom_malloc(n);
22.                 }
23.                 return result;
24.         }
25.         static void deallocate(void* p, size_t)
26.         {
27.                 free(p);//第一级配置器直接使用free()
28.         }
29.         static void* reallocate(void* p, size_t)//不够了追加,是对allocate的补救
30.         {
31.                 void* result = realloc(p, new_sz);//第一级配置器直接使用realloc
32.                 //无法满足需求，改用oom_realloc()
33.                 if (result == 0) {
34.                         result = oom_realloc(p, new_sz);
35.                         return result;
36.                 }
37.         }
38.         //下面这个可以通过他去指定自己的
39.         //out-of-memory handler
40.         static void (*set_malloc_handler(void(*f)()))()
41.         {
42.                 void (*old)() = __malloc_alloc_oom_handler;
43.                 __malloc_alloc_oom_handler = f;
44.                 return old;
45.         }
46. };
47. //初始值为0，可以在客户端自己设定
48. template<int inst>
49. void(*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
51. template<int inst>
52. void* __malloc_alloc_template<inst>::oom_malloc(size_t n)
53. {
54.         void (*my_malloc_handler)();
55.         void* result;
56.         for (;;)//死循环，不断尝试释放，配置，释放，配置。。
57.         {       
58.                 my_malloc_handler = __malloc_alloc_oom_handler;
59.                 if (0 == my_malloc_handler)
60.                 {
61.                         __THROW_BAD_ALLOC;
62.                 }
63.                 (*my_malloc_handler)();//调用处理例程，企图释放内存
64.                 result = malloc(n);//尝试配置内存
65.                 if (result)
66.                         return result;
67.         }
68. }
69. template<int inst>
70. void* __malloc_alloc_template<inst>::oom_realloc(void* p, size_t n)
71. {
72.         void (*my_malloc_handler)();
73.         void* result;
74.         for (;;)
75.         { //不断尝试释放、配置、再释放、再配置。。
76.                 my_malloc_handler = __malloc_alloc_oom_handler;
77.                 if (0 == my_malloc_handler)
78.                 {
79.                         __THROW_BAD_ALLOC;
80.                 }
81.                 (*my_malloc_handler)();//调用处理例程、企图释放释放内存
82.                 result = realloc(p, n);//再次尝试配置内存
83.                 if (result)
84.                         return result;
85.         }
86. }
87. typedef __malloc_alloc_template<0> malloc_alloc;
89. void Out_Of_Memory()//测试
90. {
91.         cout << "this is out of memory" << endl;
92.         // exit(1);
93. }
94. //测试
95. int main()
96. {
97.         __malloc_alloc_template<0>::set_malloc_handler(Out_Of_Memory);
98.         int* p = (int*)__malloc_alloc_template<0>::allocate(sizeof(int) * 536870911);
99.         return 0;
100. }

复制代码

• 二级空间设置器
  

       第二级空间设置器多了一些机制，避免太多小额区块造成的内存的碎片，小额区块带来的其实
不仅是内存碎片，设置时的额外负担也是一个大问题(cookie)，SGI第二级设置器的做法是，
如果区块够大，超过4096bytes时，就移交第一级设置器，否则就以内存池的方式管理：每次
设置一大块内存，并维护对应的自由链表，下次若再有雷同巨细的内存需求，就直接从free list
中拔出。如果哀求端开释小额内存，就由设置器回收到free list中，为了方便管理，SGI第二级
设置器会主动将任何小额区块的内存需求量上调至8的倍数。
 
   

1. typedef __malloc_alloc_template<0> malloc_alloc;
2. enum { __ALIGN = 8 };//小区块的上调边界
3. enum { __MAX_BYTES = 128 };//小型区块的上线
4. enum { __NFREELISTS = __MAX_BYTES / __ALIGN };//自由链表个数
6. template<bool threads, int inst>
7. class __default_alloc_template
8. {
9. private:
10.         //把ROUND_UP上调到8的倍数
11.         static size_t ROUND_UP(size_t bytes)
12.         {
13.                 return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));
14.         }
15. private:
16.         union obj//共用体
17.         {
18.                 union obj* free_list_link;
19.                 char client_data[1];
20.         };
21. private:
22.         //16个自由链表
23.         static obj* free_list[__NFREELISTS];
24.         //下面根据区块的大小，决定使用第n号free_list，n从1开始算
25.         static size_t FREELIST_INDEX(size_t bytes)
26.         {
27.                 return ((bytes)+__ALIGN - 1) / __ALIGN - 1;
28.         }
29.         //返回一个大小为n的对象，并可能加入大小为n的其他区块到 free list
30.         static void* refill(size_t n)
31.         {
32.                 int nobjs = 20;
33.                 char* chunk = chunk_alloc(n, nobjs);
34.                 obj** my_free_list;
35.                 obj* result;
36.                 char* current_obj, * next_obj;
37.                 int i;
38.                 if (1 == nobjs)
39.                         return chunk;
40.                 my_free_list = free_list + FREELIST_INDEX(n);
41.                 result = (obj*)chunk;
42.                 *my_free_list = next_obj = (obj*)(chunk + n);
43.                 for (i = 1;; i++)//把free list各个节点串起来
44.                 {
45.                         current_obj = next_obj;
46.                         next_obj = (obj*)((char*)next_obj + n);
47.                         if (nobjs - 1 == i)
48.                         {
49.                                 current_obj->free_list_link = 0;
50.                                 break;
51.                         }
52.                         else
53.                         {
54.                                 current_obj->free_list_link = next_obj;
55.                         }
56.                 }
57.                 return result;
58.         }
59.         //配置一大块空间，可以容纳nogjs个大小为size的区块
60.         //内存池
61.         static char* chunk_alloc(size_t size, int& nobjs)
62.         {
63.                 char* result;
64.                 size_t total_bytes = size * nobjs;  //8*20
65.                 size_t bytes_left = end_free - start_free;
66.                 if (bytes_left >= total_bytes)
67.                 {//内存池剩余空间完全满足需求量
68.                         result = start_free;
69.                         start_free += total_bytes;
70.                         return result;
71.                 }
72.                 else if (bytes_left >= size)
73.                 {//不完全满足，但够一个以上的区块
74.                         nobjs = bytes_left / size;
75.                         total_bytes = size * nobjs;
76.                         result = start_free;
77.                         start_free += total_bytes;
78.                         return result;
79.                 }
80.                 else
81.                 {//一个区块也无法提供
82.                         //320
83.                         size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
84.                         if (bytes_left > 0)
85.                         {
86.                                 obj** my_free_list = free_list + REFFLIST_INDEX(bytes_left);
87.                                 ((obj*)start_free)->free_list_link = *my_free_list;
88.                                 *my_free_list = (obj*)start_free;
89.                         }
90.                         start_free = (char*)malloc(bytes_to_get);
91.                         if (0 == start_free)
92.                         {
93.                                 int i;
94.                                 obj** my_free_list, * p;
95.                                 for (i = size; i <= __MAX_BYTES; i += __ALIGN)
96.                                 {
97.                                         my_free_list = free_list + FREELIST_INDEX(i);
98.                                         if (0 != p)
99.                                         {
100.                                                 *my_free_list = p->free_list_link;
101.                                                 start_free = (char*)p;
102.                                                 end_free = start_free + i;
103.                                                 return chunk_alloc(size, nobjs);
104.                                         }
105.                                 }
106.                                 end_free = 0;
107.                                 start_free = (char*)malloc_alloc::allocate(bytes_to_get);
109.                         }
110.                         heap_size += bytes_to_get;
111.                         end_free = start_free + bytes_to_get;
112.                         return (chunk_alloc(size, nobjs));
113.                 }
114.         }
115.         static char* start_free;//内存池起始位置
116.         static char* end_free;//内存池结束位置
117.         static size_t heap_size;
118. public:
119.         //空间申请的接口
120.         //首先判断区块的大小，如果大于 128bytes –> 调用第一级配置器；
121.         //小于128bytes–> 就检查对应的 free_list（如果没有可用区块，就将区块上调至 8 倍数的边界，
122.         //然后调用 refill(), 为 free list 重新填充空间。
123.         static void* allocate(size_t n)
124.         {
125.                 obj** my_free_list;
126.                 obj* result;
127.                 if (n > (size_t)__MAX_BYTES)  //如果>128 调用一级
128.                 {
129.                         return (malloc_alloc::allocate(n));
130.                 }
131.                 //寻找16个free list的适合的一个
132.                 my_free_list = free_list + FREELIST_INDEX(n);
133.                 result = *my_free_list;
134.                 if (result == 0)
135.                 {//没有找到可用的，准备重新填充free list
136.                         void* r = refill(ROUND_UP(n));
137.                         return r;
138.                 }
139.                 *my_free_list = result->free_list_link;
140.                 return result;
141.         }
142.         //释放空间
143.         static void deallocate(void* p, size_t n)
144.         {
145.                 obj* q = (obj*)p;
146.                 obj* volatile* my_free_list;
147.                 if (n > (size_t)__MAX_BYTES)
148.                 {
149.                         malloc_alloc::deallocate(p, n);
150.                         return;
151.                 }
152.         }
153.         static void* reallocate(void* p, size_t old_sz, size_t new_sz);
155. };
156. template<bool threads, int inst>
157. char* __default_alloc_template<threads, inst>::start_free = 0;
158. template<bool threads, int inst>
159. char* __default_alloc_template<threads, inst>::end_free = 0;
161. template<bool threads, int inst>
162. size_t __default_alloc_template<threads, inst>::heap_size = 0;
163. template<bool threads, int inst>
164. __default_alloc_template<threads, inst>::obj*
165. __default_alloc_template<threads, inst>::free_list[__NFREELISTS] = { 0,0,0,0,0,0 }

复制代码

 推荐阅读：_herongweiV的博客-CSDN博客
二级空间设置器的原理剖析和简单实现_ 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。