空间配置器

发表于 | 分类于 | 浏览 次

STL存在两级空间配置器。其中第一级空间配置器是默认空间配置器。第一级空间配置器用于配置大于128byte的内存，而当申请内存小于等于128bytes时，则求助于第二级空间配置器。

二级空间配置器

如果仅使用第一级空间配置器，那么内存分配过程中存在两个问题：

  1. 内存碎片(外碎片)
  2. 频繁分配小内存，不断调用malloc，进而调用底层的系统调用，产生性能问题

注：
内碎片：因为内存对齐/访问效率而产生的，用户需要3字节，实际得到4字节或8字节的问题，其中多出来的字节就是碎片，被浪费了。
外碎片：系统中内存总量足够，但是由于离散分配导致不连续，所以无法分配给用户使用而产生的浪费。比如，系统依次分配了16、8、16、4、8byte,还剩一个8byte未分配，这时要分配一个24byte的空间，系统回收两个16 byte，总的空间剩余40byte, 但是却分配不出来一个24byte。

二级空间配置器是为解决“频繁分配小内存”而产生的一种算法，其实就是为了消除一级空间配置器的外碎片问题。

allocate，refill，chunk_alloc

调用关系：allocate调用refill，refill调用chunk_alloc。

1
2
3
graph LR
allocate --> refill 
refill --> chunk_alloc

allocate

allocate函数详细过程：
函数原型：void *__default_alloc_template<threads, inst>::allocate(size_t n);
功能：分配指定的n个字节的内存空间。
调用refill时，会将n调整到第一个大于等于n的8的倍数。

流程图

1
2
3
4
5
6
7
8
graph TB
	start(调用allocate分配n个字节的内存空间)
	start --> biggerthan128{分配的内存大于128字节}
	biggerthan128 --> firstlevel[调用第一级空间配置器]
	biggerthan128 --> secondlevel[从16个free list中对应的那个自由链表中取出一块返回给客户端]
	secondlevel --> getsucc{成功取回}
	getsucc -->|是| yessucc[将这一块内存返回给客户端]
	getsucc -->|否| nosucc[调用refill填充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
// n must be > 0, 要分配的内存块大小
template<bool threads, int inst>
void *__default_alloc_template<threads, inst>::allocate(size_t n) {
    obj *volatile *my_free_list;        // 二级指针，my_free_list是一个指针，它保存着另一个指针的地址，后者则指向一个obj类型对象
    obj *result;

    // 大于128就调用第一级配置器
    if (n > (size_t) __MAX_BYTES) {
        return (malloc_alloc::allocate(n));
    }

    // 寻找16个free list中适当的一个
    // my_free_list和free_list+FREELIST_INDEX(n)指向第一个长度为(FREELIST_INDEX(n)+1)*8的可用区块
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;                     // *my_free_list是一个指向obj类型对象的指针
    if (result == 0) {
        // 没找到可用的free list，准备重新填充free list
        //ROUND_UP(n): 向上调整n为8的倍数
        void *r = refill(ROUND_UP(n));
        return r;
    }

    // 令free_list+FREELIST_INDEX(n)指向后续一个长度为(FREELIST_INDEX(n)+1)*8的可用区块
    // my_free_list和free_list+FREELIST_INDEX(n)这两个指针指向同一个obj*类型的元素
    *my_free_list = result->free_list_link;
    return result;
}

FREELIST_INDEX

1
2
3
4
5
6
7
enum {
    __ALIGN = 8
}; // 小型区块的边界

static size_t FREELIST_INDEX(size_t bytes) {
    return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
}

测试程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void test1() {
    cout << FREELIST_INDEX(1) << endl;   // 0(号自由链表):即对应着大小为8字节的区块
    cout << FREELIST_INDEX(12) << endl;  // 1:即对应着大小为16字节的区块
    cout << FREELIST_INDEX(21) << endl;  // 2:即对应着大小为24字节的区块
    cout << FREELIST_INDEX(30) << endl;  // 3:即对应着大小为32字节的区块
    cout << FREELIST_INDEX(33) << endl;  // 4:即对应着大小为40字节的区块
    cout << FREELIST_INDEX(41) << endl;  // 5:即对应着大小为48字节的区块
    cout << FREELIST_INDEX(51) << endl;  // 6:即对应着大小为56字节的区块
    cout << FREELIST_INDEX(60) << endl;  // 7:即对应着大小为64字节的区块
    cout << FREELIST_INDEX(65) << endl;  // 8:即对应着大小为72字节的区块
    cout << FREELIST_INDEX(74) << endl;  // 9:即对应着大小为80字节的区块
    cout << FREELIST_INDEX(85) << endl;  // 10:即对应着大小为88字节的区块
    cout << FREELIST_INDEX(92) << endl;  // 11:即对应着大小为96字节的区块
    cout << FREELIST_INDEX(97) << endl;  // 12:即对应着大小为104字节的区块
    cout << FREELIST_INDEX(105) << endl; // 13:即对应着大小为112字节的区块
    cout << FREELIST_INDEX(116) << endl; // 14:即对应着大小为120字节的区块
    cout << FREELIST_INDEX(121) << endl; // 15:即对应着大小为128字节的区块
}

refill

函数原型：void *__default_alloc_template<threads, inst>::refill(size_t n)
功能：当allocate为客户端分配指定的n(n<=128)个字节的内存，却发现free list空间不足时，就会调用refill()，为free list重新填充空间。
新的空间分配并不由本函数完成，而是调用chunk_alloc来完成。本函数需要完成的是，为chunk_alloc指定需要分配的区块大小(即n个字节)以及区块个数(默认为20)。当chunk_alloc返回分配的内存的首地址时，本函数再根据返回的内存的大小决定是否需要向自由链表中添加内存区块。

流程图

1
2
3
4
5
6
7
graph TB
	start(调用refill) --> setparams[指定chunk_alloc的参数: 需要分配的区块大小,及区块个数]
	setparams --> callchunk[调用chunk_alloc从内存池分配内存]
	callchunk --> getmemory[获取chunk_alloc返回的内存空间首地址]
	getmemory --> hasmorethanone{chunk_alloc返回的内存是否大于一个区块}
	hasmorethanone -->|是| returntoclient[将这一个区块返回给调用者--即allocate]
	hasmorethanone -->|否| savetofreelist[多出的部分添加到free list中, 返回一个区块给allocate]

chunk_alloc

函数原型：char *__default_alloc_template<threads, inst>::chunk_alloc(size_t size, int &nobjs)
参数：size为区块大小(8的倍数，从8-128共16种可能的大小)；
参数：nobjs为期望分配的区块个数，默认为20。
功能：从内存池中取出空间给free list使用。

流程图

1
2
3
4
5
6
7
graph TB
	start(调用chunk_alloc) --> hasenoughmem{内存池剩余空间满足需求}
	hasenoughmem -->|是| yesmem[从内存池中取出n*nobjs个字节的内存,返回给调用者]
	hasenoughmem -->|否| hasoneblock{内存池剩余空间至少有一个区块大小,n个字节}
	hasoneblock -->|是| yesoneblock[从内存池中取出尽量多个区块,返回给调用者]
	hasoneblock -->|否| handleleftmem[将内存池中剩余的内存分配给适当的自由链表]
	handleleftmem --> nooneblock[使用malloc从系统堆中分配内存]
1
2
3
4
5
6
7
8
9
10
graph TD
	nooneblock[使用malloc从系统堆中分配内存]
	nooneblock --> getsucc{分配成功}
	getsucc -->|是| yesget[将新内存放入内存池中]
	yesget --> callagain[再次调用chunk_alloc尝试分配n*nobjs个字节的内存,并返回首地址给调用者]
	getsucc -->|否| noget[遍历free list,希望找到比n个字节的区块大的区块]
	noget --> hasbiggerblock{是否存在比n个字节更大的区块}
	hasbiggerblock -->|是| yesbigger[找到第一个比n个字节大的区块放入内存池]
	yesbigger --> callagain
	hasbiggerblock -->|否| nobigger[调用第一级配置器,补充内存池空间]

几个疑问

为什么自由链表中分配的内存都需要上调到8字节的倍数？

参考文献

[1]二级空间配置器的必要性：http://www.dongcoder.com/detail-67805.html