版权声明:本文为博主原创文章,未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1338350
先给出一张测试空间配置的运行截图(CLion + cmake):
首先本文给出的是类alloc的实现
class alloc{
//............
}
下篇blog给出allocator的实现(allocator主要是把上面的alloc作为静态的成员,做了一些简单的封装),并给出使用配置器allocator完成一个基本的vector(SimpleVec).
template<class T>
class allocator{
//..................
}
template <class T, class Alloc = allocator<T>>
class SimpleVec{
//.....
}
程序中我们经常动态申请,释放内存,这会带来如下两个问题:
内碎片:因为内存对齐/访问效率(CPU取址次数)而产生 如 用户需要3字节,实际得到4或者8字节的问题,其中的碎片是浪费掉的。 外碎片:系统中内存总量足够,但是不连续,所以无法分配给用户使用而产生的浪费。下边简单图解
这两个问题解释清楚之后,就来谈STL空间配置器的实现细节了实现策略
if 用户申请空间 > 128:
调用一级空间配置器
else:
调用二级空间配置器
大致实现为:
二级空间配置器由内存池以及伙伴系统:自由链表组成
一级空间配置器直接封装malloc,free进行处理,增加了C++中的set_handler机制(这里其实也就是个略显牵强的装饰/适配模式了),增加内存分配时客户端可选处理机制。
二级空间配置器:
成员以及接口定义如下:
class alloc{
private:
enum EAlign{ ALIGN = 8};//小型区块的上调边界
enum EMaxBytes{ MAXBYTES = 128};//小型区块的上限,超过的区块由malloc分配
//free-lists的个数
enum ENFreeLists{ NFREELISTS = (EMaxBytes::MAXBYTES / EAlign::ALIGN)};
enum ENObjs{ NOBJS = 20};//每次增加的节点数
private:
//free-lists的节点构造
union obj{
union obj *next;
char client[1];
};
static obj *free_list[ENFreeLists::NFREELISTS];
private:
static char *start_free;//内存池起始位置
static char *end_free;//内存池结束位置
static size_t heap_size;//
private:
//将bytes上调至8的倍数,例如 (1, 3, 7) -> 8, (9, 13) -> 16
static size_t ROUND_UP(size_t bytes){
return ((bytes + EAlign::ALIGN - 1) & ~(EAlign::ALIGN - 1));
}
//根据区块大小,决定使用第n号free-list,n从0开始计算
//例如 (1, 3, 7) -> 0, (9, 13) -> 1
static size_t FREELIST_INDEX(size_t bytes){
return (((bytes)+EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
}
//返回一个大小为n的对象,并可能加入大小为n的其他区块到free-list
static void *refill(size_t n);
//配置一大块空间,可容纳nobjs个大小为size的区块
//如果配置nobjs个区块有所不便,nobjs可能会降低
static char *chunk_alloc(size_t size, size_t& nobjs, int print_count=1);
public:
static void *allocate(size_t bytes);//分配内存
static void deallocate(void *ptr, size_t bytes);//内存回收
// 回收旧内存,分配新内存
static void *reallocate(void *ptr, size_t old_sz, size_t new_sz);
};
首先空间配置会将<128字节的大小转化为8的倍数,分析如下:
// 将任意的整数调整为8的倍数
void test_or_align(){
int a =(5 + 8 - 1) & ~(8 - 1);
int b =(9 + 8 - 1) & ~(8 - 1);
int c =(13 + 8 - 1) & ~(8 - 1);
int d =(17 + 8 - 1) & ~(8 - 1);
cout<<a<<endl; // 8 (5 -》 8)
cout<<b<<endl; // 16 (9 -》 16)
cout<<c<<endl; // 16 (13 -》 16)
cout<<d<<endl; // 24 (17 -》 24)
}
8的倍数转化为free_list的index,分析如下:
void test_freelist_index(){
size_t bytes = 5;
size_t idx = (((bytes) + EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
std::cout<<idx<<endl; //0
bytes = 13;
idx = (((bytes) + EAlign::ALIGN - 1) / EAlign::ALIGN - 1);
std::cout<<idx<<endl; // 1
}
初始化:指针数组全部为空:
char *alloc::start_free = 0;
char *alloc::end_free = 0;
size_t alloc::heap_size = 0;
alloc::obj *alloc::free_list[alloc::ENFreeLists::NFREELISTS] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
};
首先分析,内存分配allocate函数(注意下面的printf主要是为了分析代码的输出)
void *alloc::allocate(size_t bytes){
if (bytes > EMaxBytes::MAXBYTES){//分配大于128字节的内存,直接分配返回
printf("%sallocate size: %d greater than 128, use malloc\n", s4space.c_str(), bytes);
return malloc(bytes);
}
size_t round_up = ROUND_UP(bytes);//输出round up的大小(这里没有意义仅仅输出查看)
printf("allocate size: %d. after round up size is: %d \n", bytes, round_up);
//定位bytes应该分配到那个链表中
size_t index = FREELIST_INDEX(bytes);
obj *list = free_list[index];
if (list){//此list还有空间给我们
printf("free_list has free node, index is: %d\n", index);
free_list[index] = list->next;//使当前空闲节点指向下一个
return list;
}
else{//此list没有足够的空间,需要从内存池里面取空间
return refill(ROUND_UP(bytes));
}
}
可以看到:
1. 当需要的内存 > 128字节,分配器alloc直接free对应的内存
2. 当小于 128 字节,则直接在free_list里面查找看是否有内存可用
3. 2中如果满足不了,则需要在内存池中获取
至于refill后面我们在看。
下面给出deallocate的使用:
void alloc::deallocate(void *ptr, size_t bytes){
if (bytes > EMaxBytes::MAXBYTES){//大于128的节点直接free释放
free(ptr);
}
else{//小于128的节点重新分配给free_list(不释放内存)
size_t index = FREELIST_INDEX(bytes);
obj *node = static_cast<obj *>(ptr);
node->next = free_list[index];
free_list[index] = node;
}
}
1 > 128字节的直接free
2 < 128字节,首先定位到free_list然后指针移位即可
refill代码如下:
//返回一个大小为n的对象,并且有时候会为适当的free list增加节点
//假设bytes已经上调为8的倍数
void *alloc::refill(size_t bytes){
size_t nobjs = ENObjs::NOBJS; // 默认为free_list bytes节点分配20个元素空间
//从内存池里取,nobjs可能没有20个,因此参数是引用
char *chunk = chunk_alloc(bytes, nobjs);
obj **my_free_list = 0;
obj *result = 0;
obj *current_obj = 0, *next_obj = 0;
printf("%srefill %d, objs\n", s4space.c_str(), nobjs);
if (nobjs == 1){//取出的空间只够一个对象使用
return chunk;
}
else{
my_free_list = free_list + FREELIST_INDEX(bytes);
result = (obj *)(chunk);//首个节点直接返回
//剩余的节点分配到对应的free_list中去
*my_free_list = next_obj = (obj *)(chunk + bytes);
//将取出的多余的空间加入到相应的free list里面去
for (int i = 1;; ++i){
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + bytes);
if (nobjs - 1 == i){
current_obj->next = 0;//最后一个指针next 赋值null
break;
}
else{
current_obj->next = next_obj;
}
}
return result;
}
}
接下来chunk_alloc函数:
//假设bytes已经上调为8的倍数
char *alloc::chunk_alloc(size_t bytes, size_t& nobjs, int print_count){
char *result = 0;
size_t total_bytes = bytes * nobjs;
size_t bytes_left = end_free - start_free;//当前有多少剩余的内存
printf("%schunk_alloc round: %d, need total_bytes: %d, bytes_left: %d\n",
s4space.c_str(), print_count, total_bytes, bytes_left);
if (bytes_left >= total_bytes){//内存池剩余空间完全满足需要
result = start_free;
start_free = start_free + total_bytes;
printf("%schunk_alloc round: %d, cater all, return %d objs bytes_left: %d >= total_bytes: %d\n",
s8space.c_str(), print_count, nobjs, bytes_left, total_bytes);
return result;
}//内存池剩余空间不能完全满足需要,但足够供应一个或以上的区块
else if (bytes_left >= bytes){
nobjs = bytes_left / bytes;
total_bytes = nobjs * bytes;
result = start_free;
start_free += total_bytes;
printf("%schunk_alloc round: %d, cater part, return %d objs, size: %d return %d bytes\n",
s8space.c_str(), print_count, nobjs, bytes, total_bytes);
return result;
}
else{//内存池剩余空间连一个区块的大小都无法提供,重新申请
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
printf("%schunk_alloc round: %d, malloc %d\n",
s8space.c_str(), print_count, bytes_to_get);
if (bytes_left > 0){//将原有的剩余的bytes分配给free_list
obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj *)start_free)->next = *my_free_list;
*my_free_list = (obj *)start_free;
}
// start_free 重新分配
start_free = (char *)malloc(bytes_to_get);
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;//每次只会递归一次
return chunk_alloc(bytes, nobjs, ++print_count);
}
}
1. 默认的返回给free_list 20个bytes,如果有则直接返回,
没有则能返回多少个bytes就返回多少个。
2. 满足不了1,则内存中申请需要内存的两倍。
测试函数如下:
void test_alloc_2(){
void * ptr;
size_t n = 10;
ptr = alloc::allocate(n);
cout<<"\n===========================\n"<<endl;
void * ptr2;
size_t n2 = 18;
ptr2 = alloc::allocate(n2);
cout<<"\n===========================\n"<<endl;
void * ptr3;
size_t n3 = 10;
ptr3 = alloc::allocate(n3);
cout<<"\n===========================\n"<<endl;
void * ptr5;
size_t n5 = 7;
ptr5 = alloc::allocate(n5);
cout<<"\n===========================\n"<<endl;
void * ptr4;
size_t n4 = 26;
ptr4 = alloc::allocate(n4);
cout<<"\n===========================\n"<<endl;
void * ptr6;
size_t n6 = 47;
ptr6 = alloc::allocate(n6);
cout<<"\n===========================\n"<<endl;
void * ptr7;
size_t n7 = 5;
ptr7 = alloc::allocate(n7);
alloc::deallocate(ptr, n);
alloc::deallocate(ptr2, n2);
alloc::deallocate(ptr3, n3);
alloc::deallocate(ptr4, n4);
alloc::deallocate(ptr5, n5);
alloc::deallocate(ptr6, n6);
alloc::deallocate(ptr7, n7);
}
1.ptr = alloc::allocate(n);输出如下:
ptr2 = alloc::allocate(n2);
输出如下:
allocate size: 18. after round up size is: 24
chunk_alloc round: 1, need total_bytes: 480, bytes_left: 320
chunk_alloc round: 1, cater part, return 13 objs, size: 24 return 312 bytes
refill 13, objs
默认需要20 * 24个元素,但是内存池中还有320个字节剩余,因此返回 320/24=13个元素。
size_t n3 = 10;
ptr3 = alloc::allocate(n3);
输出如下:
allocate size: 10. after round up size is: 16
free_list has free node, index is: 1