**侯捷老师的C++笔记--pool_alloc**
G2.9标准分配器的实现
- G2.9 的
std::allocator
只是以::operator new
和::operator delete
完成allocate()
和deallocate()``,没有任何其他的设计,但在实际中,使用的是另一个分配器
std::alloctemplate<class T, class Alloc=alloc> class vector {…};`
- G4.9中的
std::allocator
使用的是类似于这个没有其他设计的allocator
, 另一个叫__pool_alloc
1 | template <class T> |
G2.9 – std::alloc
运行模式
- 首先有一个
free_list
, 存放有16个指针,每个指针从左向右指向(i + 1) * 8字节的chunk - 最小是8个字节,最大是16 * 8 = 128个字节
- 按照用户需要的大小给其分配相应的内存
- 有一个pool, 内存池,未分配的但是已经获取到的内存,使用两个指针指向pool,
start_free and end_free
- 当所需要的区块没有内存或不够时,会在pool里分出
free list(1-20个block)
- 当pool里没有内存时,此时会向系统索要内存(调用
malloc()
),带cookie
- 每次向系统要的内存大小是
(size) * 20 * 2 + RoundUp(0>>4)
- RoundUp是累计申请的内存
- 当pool里不够一个所需要的block时,此时就变成了内存碎片,会放到和其大小最接近的free list前面
- 当内存不够时,会想右边的free list来索取内存块。
源码分析
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// 第一级分配器: 处理比128字节大的, ...
// 第二级分配器: 去掉了multi thread
enum {__ALIGN = 8}; // 小区块的上调边界
enum {__MAX_BYTES = 128}; // 小区块的上限
enum {__NFREELISTS = __MAX_BYTES / __ALIGN}; // free_list的数目
template <bool threads, int inst>
class __default_alloc_template {
private:
// 将用户指定的bytes数目round 到8的倍数
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1)); // if bytes == 14, then return 16
private:
union obj {
union obj* free_list_link; // 相当于next
}; // 改成struct也可
private:
static obj* volatile free_list[__NFREELISTS];
// 找到所需要的free-list的index
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN - 1) / __ALIGN - 1); // if bytes = 8: return 0
}
// return an obj of size n, and optionally adds to size n free list
static void *refill(size_t n); // most important func
// Allocates a chunk fr nobjs of size "size". nobjs may be reduced
// if it is inconvient to allocate the requested number
static char* chunk_alloc(size_t size, int&nobjs); // 传引用,因为可能被改变
// Chunk allocation statement
static char* start_free; // 指向pool的start
static char* end_free; // 指向pool的end
static size_t heap_size; // 分配的累积量
public:
// allocate
static void* allocate(size_t n) // n > 0
{
obj* volatile *my_free_list; // obj**
obj* result;
if (n > (size_t)__MAX_BYTES) { // 第一级
return (malloc_alloc::allocate(n));
}
my_free_list = free_list + FREELIST_INDEX;
result = *my_free_list;
if (result == 0) { // list为空
// refill会填充free list并返回第一个区块的起始地址
void* r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->free_list_link;
return (result);
}
// deallocate, 有缺陷没有free, 还有不是在pool里分配的也可以调用这个函数
static void deallocate(void* p, size_t size) {
obj* q = (obj*)p;
obj* volatile *my_free_list; // obj**
if (n > (size_t) __MAX_BYTES) {
malloc_alloc::deallocate(p, n); // 改用第一级
return;
}
my_free_list = free_list + FREELIST_INDEX;
q->free_list_link = *my_free_list;
*my_free_list = q;
}
}
};
// Returns an object of size n, and optionally adds to size n free list
template ,bool threads, int inst>
void* __default_alloc_template<threads, inst>::
refill(size_t n) // n已经调至8的倍数
{
int nobjs = 20; // 预设取20个,但不一定能够
char* chunk = chunk_alloc(n, nobjs); // nobjs pass by reference
obj* volatile *my_free_list;
obj* result;
obj* current_obj;
obj* next_obj;
int i;
if (1 == nobjs) return(chunk); // 实际拿到的只有一个block
// 将所得到的区块挂上free list
my_free_list = free_list + FREELIST_INDEX(n);
// 在chunk内建立free list
result = (obj*)chunk;
*my_free_list = next_obj = (obj*)(chunk + n);
for (i = 1; ; i++) { // 从1开始,因为0号要返回
current_obj = next_obj;
next_obj = (obj*) ((char*)next_obj + n); // 每个block间隔n个字节
if (nobjs - 1 == i) { // last one
current_obj->free_list_link = 0;
break;
} else
current_obj->free_list_link = next_obj;
}
return (result);
}
// allocate memory in large chunks in order to avoid fragmenting the malloc
// heap too much, assume that size is properly aligned, we hold it locked in pool
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::
chunk_alloc(size_t size, int& nobjs)
{
char* result;
size_t total_bytes = size * nobjs; // 总共所需的bytes
size_t bytes_left = end_free - start_free; // pool中剩余的bytes
if (bytes_left >= total_bytes) { // 满足20
result = start_free;
start_free += total_bytes; // 降级pool水位
return(result);
} else if (bytes_left >= size) { // 满足至少一块
nobjs = bytes_left / size; // 改变需求量
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes; // 降级pool水位
return(result);
} else {
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
// 先将pool做充分利用,处理碎片
if (bytes_left > 0) {
obj* volatile *my_free_list =
free_list + FREELIST_INDEX(bytes_left);
// 将 pool剩余空间编入#号free_list
((obj*)start_free)->free_list_link = *my_free_list;
*my_free_list = (obj*)start_free;
start_free = (char*)malloc(bytes_to_get); // 从system取内存注入pool中
// 如果内存不够导致失败,尝试在右边找
if (0 == start_free) {
int i;
obj* volatile *my_free_list, *p; // obj **my_free_list; obj *p;
for (i = size; i<= __MAX_BYTES; i += __ALIGN) {
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p) { // p不为null, only分出1块给pool
*my_free_list = p->free_list_link;
start_free = (char*)p;
end_free = start_free + 1;
return (chunk_alloc(size, nobjs)); // 递归重新再试一次
}
end_free = 0; // 改用第一级
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)); // 递归调用
}
}
}deallocate
的实现过程: