对象池

内容

  1. 关联关系
  2. 一级配置器和二级配置器的关系
  3. 类型萃取
  4. allocator
  5. __malloc_alloc_template静态成员的类外初始化,其中函数指针尤为麻烦

关联关系

弱关联

1
2
3
4
5
6
7
8
class Person
{
private:
Book * pbook;
public:
Student(){}
~Student(){} //不能析构book
}

强关联

1
2
3
4
5
6
7
class Person
{
private:
Book & book;
public:
Student(Book & book) : _book(book){}
}

聚合/组合关系

1
2
3
4
5
6
7
8
9
10
11
class Point
{
private:
float _x;
float _y;
public:
Point(float x = 0.0f, float y = 0.0f) : _x(x), _y(y){}
Point(const Point&) = default;
Point & operator=(const Point&) = default;
~Point(){}
}

new

  1. sizeof
  2. 分配字节空间
  3. 构建 返回地址

delete

  1. 析构
  2. 空间释放

二级配置器

  • 一级配置器的问题
    • 直接的malloc后的数据上下各有一个越界标记。上越界标记之外还有信息,包括申请了多少字节,还有next域、prev域以便连接到链表中进行内存管理。除此之外可能还有有效/失效(是否释放)的标记。
    • 除了包装信息占空间较多之外,还有malloc时花费的时间也多。这样就造成对于比较小的对象数据在malloc时入不敷出。
    • 结论就是:对于较小数据,适用于内存池来进行内存管理。
  • 对于客户端申请较小空间(128bytes)的具体处理流程
    1. 每次配置一大块内存,并维护对应的自由链表(free-list)
    2. 下次如果再有相同大小的内存需求,直接从free-list中取出若干小块。
    3. 如果客户端释放小块内存,就由配置器回收到free-list中。所以配置器除了分配空间,还负责回收空间。
  • 为了方便管理,SGI第二级配置器会主动按任何小块内存的内存需求量计算成8的倍数。(比如客户端要求30bytes,则计算为32bytes。
  • 共维护16个free-lists,各自管理大小分别为8、16、24、32、40、48、56、64、72、80、88、96、104、112、120、128的小额区块。
  • free-lists的单结点结构如下:
1
2
3
4
5
union obj
{
union obj * free_list_link;
char client_data[1]; //the client sees this
}

总览

1
2
3
enum { __ALIGN = 8};
enum { __MAX_BYTES = 128};
enum { __NFREELISTS = __MAX_BYTES / __ALIGN}; // 128 / 8 = 16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<bool threads, int inst>	//参数1:是否考虑多线程,参数2:标识
class __default_alloc_template
{
private:
union obj /* 只是类型定义 */
{
union obj * free_list_link; //next
char client_data[1];
};
private:
static obj * volatile free_list[__NFREELISTS];//volatile修饰obj*,即free_list数组中对于的数据内容。
static char* start_free;//每次配置的一大块'内存' 的内存来源的剩余部分的起始
static char* end_free; //每次配置的一大块'内存' 的内存来源的剩余部分的末尾
static size_t heap_size;//上面提到的都是内存来源,而这个内存来源都是从堆区申请的,堆区申请的总空间数要记录在案
static size_t ROUNT_UP(size_t bytes);
static size_t FREELIST_INDEX(size_t bytes); //hash
static char* chunk_alloc(size_t size, int & nobjs);//size - 对象的大小,nobjs对象的个数
static void* refill(size_t size); //重新填充
public: /* 用户调用 */
static void* allocate(size_t size);
static void deallocate(void* p, size_t n);
static void* reallocate(void* p, size_t old_sz, size_t new_sz);
};

成员初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
// 对free_list[__NFREELISTS]进行初始化。
template<bool threads, int inst> // 1: __default_alloc_template是模板类,需要声明
typename __default_alloc_template<threads, inst>::obj * volatile // 2: obj是__default_alloc_template<threads, inst>类内的类,需要加上“哪个类”,并且要加上"typename"以示"obj"是个类名,而非成员。
__default_alloc_template<threads, inst>::free_list[__NFREELISTS] = {}; // 3: free_list[__NFREELISTS]是__default_alloc_template<threads, inst>类内的成员,需要加上“哪个类”,但无需加"typename"。
// 对start_free进行初始化
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::start_free = nullptr;
// 对end_free进行初始化
template<bool threads, int inst>
char* __default_alloc_template<threads, inst>::end_free = nullptr;
// 对heap_size进行初始化
template<bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;

函数实现

准备工作

1
using malloc_alloc = __malloc_alloc_template<0>;

allocate

相当于单链表的头删法,返回删了的节点的地址给用户用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static void * allocate(size_t size)
{
if(size > (size_t)__MAX_BYTES)
{
return malloc_alloc::allocate(size); //转给一级配置器。
}
obj * result = nullptr;
obj * volatile * my_free_list = nullptr; //是二级指针,要指向obj*
my_free_list = free_list + FREELIST_INDEX(size);
result = *my_free_list;
if(nullptr == result) //说明此下标处无内存块了,需要申请。
{
void * r = refill(ROUND_UP(size));
return r;
}
*my_free_list = result->free_list_link; //把free_list此下标的指针更新到下一个节点。相当于链表的头删法。
return result;
}

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
static void * refill(size_t size)
{
int nobjs = 20;
char * chunk = chunk_alloc(size, nobjs);
//chunk_alloc运行之后,nobjs值可能发生改变。
if(1 == nobjs)
{
//如果nobjs是1,则说明内存块正好用完,不用再处理后续内存区域的链接、移动
return chunk;
}

//接下来,把内存块分崩离析,依次串联。
obj * volatile * my_free_list = NULL;
obj * result = (obj*)chunk;
obj * current_obj = NULL, * next_obj = NULL;
my_free_list = free_list + FREELIST_INDEX(size);
*my_free_list = next_obj = (obj*)(chunk+size);
for(int i = 1; ; ++i)
{
current_obj = next_obj;
next_obj = (obj*)((char*)next_obj + size);
if(i == nobjs-1)//最后一块
{
current_obj->free_list_link = NULL;
break;
}
current_obj->free_list_link = next_obj;
}
return result;
}

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
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 = start_free + total_bytes;
return result;
}
else if(bytes_left >= size)
{
nobjs = bytes_left / size;
total = size * nobjs;

result = start_free;
start_free = start_free + total_bytes;
return result;
}
else //内存不足以分配1个对象,把剩余的插入到其他下标(剩8字节插到0, 16字节插到1, ...),然后再另外申请一个大的
{
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
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(NULL == start_free) //堆区居然没有资源了!无奈之计,只能向比他之后的链表找有无剩余块。
{
obj * volatile * my_free_list = NULL;
for(int i = size; i <= __MAX_BYTES; i += __ALIGN) //注意,i从size开始,而不一定从最小的块大小8开始,因为找比你小的没有用处。得找大的。
{
my_free_list = free_list + FREELIST_INDEX(i);
obj * p = NULL;
if(NULL != p) //找到了比他大的的剩余的了!
{
*my_free_list = (*my_free_list)->free_list_link;
start_free = (char*)p;
end_free = start_free + i;
return chunk_alloc(size, nobjs);
}
}
//如果上面的for循环没能使得其找到合适的内存块,则说明真的是“山穷水尽疑无路”了,只能转1级配置器,抛出异常或者通过handler处理。
start_free = malloc_alloc::allocate(bytes_to_get);
}
end_free = start_free + bytes_to_get;
heap_size += bytes_to_get;
return chunk_alloc(size, nobjs); //递归此函数,相当于重新来一遍流程
}
}

ROUND_UP & INDEX

1
2
3
4
5
6
7
8
9
10
static size_t ROUNT_UP(size_t bytes)
{
// 0 -> 0, 1~8 -> 8, 9~16 - > 16, 17~24 -> 24, ...
return (bytes+ __ALIGN-1) & ~(__ALIGN - 1);
}
static size_t FREELIST_INDEX(size_t bytes)
{
// 1~8 -> 0, 9~16 -> 1, 17~24 -> 2, ...
return ((bytes+ __ALIGN-1) / __ALIGN) - 1;
}

测试allocate

1
2
3
4
5
6
#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;
#else
typedef __default_alloc_template<0, 0> alloc;
#endif
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<class T, class Alloc>
class simple_alloc
{
public:
static T* allocate(size_t n) //申请n个T对象
{
return Alloc::allocate(sizeof(T)*n);
}
static T* allocate()
{
return Alloc::allocate(sizeof(T));
}
void deallocate(T *p, size_t n)
{
if(NULL == p)return;
Alloc::deallocate(p, sizeof(T)*n);
}
void deallocate(T* p)
{
if(NULL == p)return;
Alloc::deallocate(p, sizeof(T));
}
};

引入list进行测试

1
2
3
4
5
6
7
8
9
10
11
12
#include"my_list.h"
using namespace std;
int main()
{
xcg::my_list<char> mylist;

for(int i = 0; i < 23; ++i)
{
mylist.push_back(i + 'a');
}
return 0;
}

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
template<class _Ty, class _A = xcg::alloc>
class my_list
{
public:
typedef _Ty value_type;
typedef _Ty& reference;
typedef _Ty* pointer;
typedef const _Ty& const_reference;
typedef const _Ty* const_pointer;

typedef _A allocator_type;
typedef xcg::simple_alloc<_Node, _A> data_allocate; //simple_alloc中使用的是第二个参数的allocate。在这里即使用_A::allocate,默认参数是xcg::alloc,而根据开关语句,若是使用malloc_alloc则为一级配置器,若为default_alloc则用二级配置器。我们默认使用的是__default_alloc_template<0, 0>。

public:
my_list() : _Head(_Buynode()), _Size(0) {}
protected:
_Nodeptr _Buynode(_Nodeptr _parg = NULL, _Nodeptr _narg = NULL)
{
_Nodeptr _S = data_allocate::allocate();
_Acc::_Prev(_S) = _parg == NULL ? _S : _parg;
_Acc::_Next(_S) = _narg == NULL ? _S : _narg;
return _S;
}
private:
_Nodeptr _Head;
size_t _Size;
};

deallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void deallocate(void * p, size_t size)	// n 表示空间大小
{
if(size > (size_t)__MAX_BYTES)
{
malloc_alloc::deallocate(p, size);
return;
}
//归还给配置器
obj * q = (obj*)p;
obj * volatile * my_free_list = free_list + FREELIST_INDEX(size);
//头插
q->free_list_link = *my_free_list;
*my_free_list = q;
return;
}

测试deallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
iterator erase(iterator _P)
{
_Nodeptr _S = _P++._Mynode();
_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
destroy(&_Acc::_Value(_S)); //不删除节点,而是释放value域。
_Freenode(_);

return _P;
}
void _Freenode(_Nodeptr _P)
{
data_allocate::deallocate(_P);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Object
{
private:
int value;
public:
Object(int x = 0) : value(x)
{
cout << "create object" << this << endl;
}
~Object()
{
cout << "destroy object" << this << endl;
}
};
int main()
{
xcg::my_list<Object> objlist;
for(int i = 0; i < 10; ++i)
{
objlist.push_back(Object(i));
}
objlist.pop_back();
return 0;
}

reallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void* reallocate(void * p, size_t old_sz, size_t new_sz)
{
if(old_sz > (size_t)__MAX_BYTES && new_sz > (size_t)__MAX_BYTES)
{
return malloc_alloc::reallocate(p, old_sz, new_sz);
}
// old_sz == 20, new_sz == 22 -->24, 24
if(ROUND_UP(old_sz) == ROUND_UP(new_sz))
{
return p;
}
// old_sz > 128, new_sz < 128
// old_sz < 128, new_sz < 128
// old_sz < 128, new_sz > 128
size_t sz = old_sz < new_sz ? old_sz : new_sz;
void * s = allocate(new_sz);
memmove(s, p ,sz);
deallocate(p, old, sz);
return s;
}