Summary

STL空间配置器

一级空间配置器

当所申请的空间大于128bytes时，stl直接使用一级空间配置器
一级空间配置器其实是对malloc的封装，以及添加了类似new_handler处理内存分配不足的情况
当内存不足时调用oom_malloc尝试回收一些已分配的内存，调用的是__malloc_alloc_oom_handler方法(如果有的话，没有就抛出异常)

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
template<int inst>
class __malloc_alloc_template
{
private:
	static void *oom_malloc(size_t n)//
	{
		void (*my_malloc_handler) () = NULL;
		void *result = NULL;
		for(;;)//不断的去尝试
		{
			my_malloc_handler = __malloc_alloc_oom_handler;
			if(NULL == my_malloc_handler)
			{
				__THROW_BAD_ALLOC;
			}else
			{
				(*my_malloc_handler)();//调用malloc_handler
			}
			result = malloc(n);
			if(NULL != result)
			{
				return result;
			}
		}
	}
	static void *oom_realloc(void *p,size_t n)
	{
		void (*my_malloc_handler) () = NULL;
		void *result = NULL;
		for(;;)
		{
			my_malloc_handler = __malloc_alloc_oom_handler;
			if(NULL == my_malloc_handler)
			{
				__THROW_BAD_ALLOC;
			}else
			{
				(*my_malloc_handler)();
			}
			result = realloc(p,n);
			if(NULL != result)
			{
				return result;
			}
		}
	}
	static void (*__malloc_alloc_oom_handler)();
public:
	static void * allocate(size_t n)
	{
		void * result = malloc(n);
		if(NULL == result)
		{
			result = oom_malloc(n);
		}
		return result;
	}
	static void deallocate(void *p,size_t/*n*/)
	{
		free(p);
	}
	static void *reallocate(void *p,size_t /*old_sz*/,size_t new_sz)
	{
		void result = realloc(p,new_sz);
		if(NULL == result)
		{
			result = oom_realloc(p,new_sz);
		}
		return result;
	}
	// set_new_handler ;
	static void(*set_malloc_handler(void (*f)()))() //参数和返回值全是函数指针
	{
		void (*old)() = __malloc_alloc_oom_handler;
		__malloc_alloc_oom_handler = f;
		return old;
	}

};

template<int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)()= NULL;

typedef __malloc_alloc_template<0> malloc_alloc;

二级空间配置器

二级空间配置器其实是一个内存池，他维持这一个空闲链表数组，所需字节数全上调成8的倍数，然后在空闲链表里面找。
当空闲链表内存块不足时，优先从已申请好的空闲堆内存中填充空闲链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
enum{__ALIGN = 8 };
enum{__MAX_BYTES = 128};
enum{__NFREELIST = __MAX_BYTES/__ALIGN};
union obj                                    //链表的结构，空间的有效利用
{
	union obj *free_list_link;
	char client_data[1];
};
static obj * volatile free_list[__NFREELIST];//空闲链表数组
static size_t FREELIST_INDEX(size_t bytes)
{
	return (bytes + __ALIGN -1) / __ALIGN -1;//寻找在数组中的下标位置
}
static size_t ROUND_UP(size_t bytes)
{
	return (bytes + __ALIGN -1) & ~(__ALIGN-1);//上调成8的倍数
}

static char * start_free; //空闲内存起始地址
static char * end_free;   //空闲内存结束地址
static size_t heap_size;  //空闲堆内存大小

allocate

如果找到了则把那块空间从free_list中非配给用户，没找到则调用refill()填充free_list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void * allocate(size_t n)// 15
{
	obj * volatile * my_free_list = NULL;
	obj *result = NULL;
	if(n > (size_t) __MAX_BYTES)
	{
		return malloc_alloc::allocate(n);
	}
	my_free_list = free_list + FREELIST_INDEX(n);
	result = *my_free_list;
	if(NULL == result)       //如果free_list为空则调用refill填充或直接分配
	{
		void *r = refill(ROUND_UP(n));
		return r;
	}
	*my_free_list = result->free_list_link;
	return result;
}

refill

STL规定refill为内存不足的那块填充20块相应大小的内存块，但是可能出现内存不足的情况所有申请到的不一定是20个内存快(可能只有1个)

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
static void * refill(size_t n) //
{
	int nobjs = 20;
	char *chunk = chunk_alloc(n,nobjs);// 申请内存块
	obj *volatile* my_free_list;
	obj *result;
	obj *current_obj, *next_obj;
	int i;
	if(1==nobjs) return chunk;
	my_free_list=free_list + FREELIST_INDEX(n);
	result=(obj *)chunk;
	*my_free_list=next_obj=(obj *)(chunk+n);
	for(i=1;;i++)                    //将剩余的块连接到空闲链表
	{
		current_obj = next_obj;
		next_obj=(obj *)((char *)next_obj + n);
		if(nobjs -1==i)
		{
			current_obj->free_list_link=0;
			break;
		}
		else
		{
			current_obj->free_list_link=next_obj;
		}
	}
	return result;                //将第一个内存块返回
}

chunk_alloc

chunk_alloc函数分配内存块给free_list,他和refill是维持这个结构的核心。处理了多种内存不足的情况

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
static char * chunk_alloc(size_t size,int &nobjs)
{
	char *result = NULL;
	size_t total_bytes = size*nobjs;
	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)//内存不够分配20块但能分配一块或一块以上
	{
		nobjs = bytes_left/size;
		total_bytes = size*nobjs;
		result = start_free;
		start_free += total_bytes;
		return result;
	}else //剩余内存一块都不能分配
	{
		size_t bytes_to_get=2 *total_bytes+ROUND_UP(heap_size>>4);
		//先给剩余的内存找到合适的free list(先处理start_free——end_free的那段内存)
		if(bytes_left>0)
		{
			obj * volatile *my_free_list=free_list +FREELIST_INDEX(bytes_left);
			((obj *)start_free)->free_list_link= *my_free_list;
			*my_free_list=(obj *)start_free;
		}
		//向堆空间申请内存
		start_free=(char *)malloc(bytes_to_get);
		if(0==start_free)//堆空间不足时
		{
			int i;
			obj *volatile* my_free_list,*p;
			//遍历比他大的free list查看是否还剩有未使用内存
			for(i=size;i<__MAX_BYTES;i+=__ALIGN)
			{
				my_free_list = free_list +FREELIST_INDEX(i);
				p = *my_free_list;
				if(0!=p)//
				{
					*my_free_list = p ->free_list_link;
					start _free = (char *)p;
					end_free = (char *)p;
					//由于nobjs 传的是引用所以递归调用修正nobjs
					return (chunk_alloc(size,nobjs));
				}
			}
			end_free=0;
			//调用一级空间配置器,看看malloc_handler能否挤出内存...
			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));//同上
	}
}

释放内存

1
2
3
4
5
6
7
8
9
10
11
12
13
static void deallocate(void *p,size_t n)
{
	obj * volatile * my_free_list = NULL;
	obj *q = (obj*)p;
	if(n > (size_t) __MAX_BYTES)
	{
		malloc_alloc::deallocate(p,n);
		return ;
	}
	my_free_list = free_list + FREELIST_INDEX(n);
	q->free_list_link = *my_free_list;
	*my_free_list = q;
}

结构图

如图：
二级空间配置器内存结构
参考资料——STL源码剖析