《STL源码剖析》笔记：空间配置器
2017-09-25 本文已影响0人
wayyyy
在书中介绍了有2个空间配置器：
- 第一个是适合直接用的
malloc/free，简单包装了下，并实现了类似C++ new-handler机制。 - 第二个用的是一个建立在一个内存池和
free_list上面的次级配置器，实现了更灵活的内存管理。
一级配置器
二级配置器
二级配置器多了些机制，避免了太多小额区块造成的内存碎片。整体做法是：如果区块足够大，超128bytes 时，就移交第一级配置器处理，当区块小于128bytes时，则以内存池管理。
二级配置器整体配置如图：
二级空间配置器.jpg
内存池就是从堆中申请的大块的内存，负责填充free_list。内存池直接由malloc分配，用2个指针表示，start_free指针表示当前内存池剩余内存的起始地址。
内存池.jpg
free_list
union obj
{
union obj *free_list_link;
char client_data[1]; // 没什么用
};
enum { _ALIGN = 8 }; // 小型区块下限
enum { _MAX_BYTES = 128 }; // 小型区块上限
enum { _NFREELISTS = _MAX_BYTES / _ALIGN }; // free_list 个数
free_list是指针数组。每一个数组槽内指向的是一个由指定大小的内存块连接起来的list。客户申请内存，就将其中相应的内存从list"拔下"，客户归还内存则就内存插入相应的list中。
free_list.jpg
空间配置器
class alloc
{
private:
static obj* free_list[_NFREELISTS]; // obj数组
private:
static char *start_free; // 内存池起始位置
static char *end_free; // 内存池结束位置
static size_t heap_size;
private:
/* 将bytes上调至8的倍数 */
static size_t ROUND_UP(size_t bytes)
{
return (((bytes) + _ALIGN - 1) & ~(_ALIGN - 1));
}
/* 根据区块大小使用第n号free_list */
static size_t FREELIST_INDEX(size_t bytes)
{
return (((bytes) + _ALIGN - 1) / _ALIGN - 1);
}
/* 为free_list某个大小的list增加节点 */
static void *refill(size_t n);
static char *chunk_alloc(size_t size, int &nobjs);
public:
static void *allocate(size_t n);
static void deallocate(void *p, size_t n);
static void *reallocate(void *p, size_t old_size, size_t new_size);
};
- 空间配置函数
void* alloc::allocate(size_t n)
{
obj **my_free_list, *list;
if (n > (size_t) _MAX_BYTES) // 当需要的内存大于某个节点，就调用malloc
return malloc(n);
my_free_list = free_list + FREELIST_INDEX(n); // 指向第n号list
list = *my_free_list;
if (list) {
*my_free_list = list->free_list_link; // 从list头部"拔出一个内存"，返回给客户
return list;
} else
return refill(ROUND_UP(n)); // 如果当前list为空，则重新申请内存填充该list
}
- 空间释放函数
void alloc::deallocate(void *p, size_t n)
{
obj *q = (obj *) p;
obj **my_free_list;
if (n > (size_t)_MAX_BYTES) // 当需要的内存大于某个节点，就调用free
free(p);
else { // 当需要的内存小于某个节点，就将其保存至某个list下
my_free_list = free_list + FREELIST_INDEX(n); // my_free_list指向第n号list
q->free_list_link = *my_free_list;
*my_free_list = q;
}
}
- 从内存池取出内存供给free list使用
chunk_alloc.png
// 从内存池取出空间给free_list使用(第n号)(假定size已经适当调整为8的倍数)
char *alloc::chunk_alloc(size_t size, int &n_objs)
{
char *result;
size_t total_bytes = size * n_objs; // 需要的内存总量
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) {
// 内存池剩余空间不能完全满足需求量,但足够供应一个(含)以上的区块
n_objs = bytes_left / size; // 计算可以供应几个区块
/* 更新start_free指针 */
total_bytes = n_objs * size;
result = start_free;
start_free += total_bytes;
return result;
} else {
// 内存池剩余空间连一个区块的大小都不满足
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
// 试着让内存池中残余零头还有利用价值
if ( bytes_left > 0 ) {
// 将内存池残余内存配给适当的free_list(更小的size的list);
obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);
((obj *) start_free)->free_list_link = *my_free_list;
*my_free_list = (obj *) start_free;
}
// 配置heap空间, 用来补充内存池
start_free = (char *) malloc(bytes_to_get);
if (nullptr == start_free) {
obj *p, **my_free_list;
// heap空间不足,搜寻适当的free_list("未用区块,且区块够大")
for (int 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 = start_free + i;
return chunk_alloc(size, n_objs);
}
}
end_free = 0;
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return chunk_alloc(size, n_objs);
}
}
参考资料
[1] 《STL源码剖析》侯捷
