STL—内存的配置与释放

上一篇我们介绍了STL对象的构造与析构,这篇介绍STL内存的配置与释放。
STL有两级空间配置器,默认是使用第二级。第二级空间配置器会在某些情况下去调用第一级空间配置器。空间配置器都是在allocate函数内分配内存,在deallocate函数内释放内存。
 
第一级空间配置器
 
第一级配置器只是对malloc函数和free函数的简单封装,在allocate内调用malloc,在deallocate内调用free。同时第一级配置器的oom_malloc函数,用来处理malloc失败的情况。如下所示:
allocate对malloc函数简单封装 :
static void *allocate(size_t n)
{
void *result = malloc(n);
if (NULL == result)
result = oom_malloc(n);
return result;
}

deallocate对free函数简单封装 :

static void deallocate(void *p, size_t) { free(p); }

oom_malloc调用外部提供的malloc失败处理函数,然后重新试着再次调用malloc。重复执行此过程,直到malloc成功为止 :

template <int inst>
void* __malloc_alloc<inst>::oom_malloc(size_t n)
{
void (*my_malloc_handler)();
void *result;
for (;;)
{
my_malloc_handler = malloc_alloc_oom_handler;
if (NULL == my_malloc_handler)
__THROW_BAD_ALLOC;
(*my_malloc_handler)();
result = malloc(n);
if (result)
return result;
}
}

第二级空间配置器

第一级配置器直接调用malloc和free带来了几个问题:
1.内存分配/释放的效率低。2. 当配置大量的小内存块时,会导致内存碎片比较严重。3. 配置内存时,需要额外的部分空间存储内存块信息,所以配置大量的小内存块时,还会导致额外内存负担。
 
第二级配置器维护了一个*链表数组,每次需要分配内存时,直接从相应的链表上取出一个内存节点就完成工作,效率很高。
 
*链表数组
*链表数组其实就是个指针数组,数组中的每个指针元素指向一个链表的起始节点。数组大小为16,即维护了16个链表,链表的每个节点就是实际的内存块,相同链表上的内存块大小都相同,不同链表的内存块大小不同,从8一直到128。如下所示,obj为链表上的节点,free_list就是链表数组。
//*链表
union obj
{
union obj *free_list_link;
char data[];
};
//*链表数组
static obj *volatile free_list[__NFREELISTS];
内存分配
allocate函数内先判断要分配的内存大小,若大于128字节,直接调用第一级配置器,否则根据要分配的内存大小从16个链表中选出一个链表,取出该链表的第一个节点。若相应的链表为空,则调用refill函数填充该链表。如下:
template <bool threads>
void *__default_alloc<threads>::allocate(size_t n)
{
obj *volatile *my_free_list;
obj *result;
if (n > (size_t)__MAX_BYTES) //调用第一级配置器
return malloc_alloc::allocate(n);
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (result == NULL)
{
//第n号链表无内存块,则准备重新填充该链表
void *r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->free_list_link;
return result;
}
填充链表
若allocate函数内要取出节点的链表为空,则会调用refill函数填充该链表。
refill函数内会先调用chunk_alloc函数从内存池分配一大块内存,该内存大小默认为20个链表节点大小,当内存池的内存也不足时,返回的内存块节点数目会不足20个。接着refill的工作就是将这一大块内存分成20份相同大小的内存块,并将各内存块连接起来形成一个链表。如下:
template <bool threads>
void *__default_alloc<threads>::refill(size_t n)
{
int nobjs = __NOBJS;
char *chunk = chunk_alloc(n, nobjs); //从内存池获取内存
if (nobjs == ) //只能分配一块,则直接返回给调用者
return chunk;
obj *volatile *my_free_list;
obj *result, *next_obj, *current_obj;
result = (obj *)chunk;
my_free_list = free_list + FREELIST_INDEX(n);
*my_free_list = next_obj = (obj *)(chunk + n);
for (int i = ; i < nobjs - ; i++) //将剩下的区块添加进链表
{
current_obj = next_obj;
next_obj = (obj *)(char *)(next_obj + n);
current_obj->free_list_link = next_obj;
}
//最后一块
current_obj = next_obj;
current_obj->free_list_link = NULL;
return result;
}
内存池
chunk_alloc函数内管理了一块内存池,当refill函数要填充链表时,就会调用chunk_alloc函数,从内存池取出相应的内存。
在chunk_alloc函数内首先判断内存池大小是否足够填充一个有20个节点的链表,若内存池足够大,则直接返回20个内存节点大小的内存块给refill。如下:
        if (size_left >= total_size)  //内存池剩余空间满足需求
{
result = start_free;
start_free += total_size;
return result;
}

若内存池大小无法满足20个内存节点的大小,但至少满足1个内存节点,则直接返回相应的内存节点大小的内存块给refill;

        else if (size_left >= size)  //剩余空间不能全部满足,但至少满足一块
{
nobjs = size_left / size;
result = start_free;
start_free += nobjs * size;
return result;

若内存池连1个内存节点大小的内存块都无法提供,则chunk_alloc函数会将内存池中那一点点的内存大小分配给其他合适的链表,然后去调用malloc函数分配的内存大小为所需的两倍。若malloc成功,则返回相应的内存大小给refill;若malloc失败,会先搜寻其他链表的可用的内存块,添加到内存池,然后递归调用chunk_alloc函数来分配内存,若其他链表也无内存块可用,则只能调用第一级空间配置器,因为第一级空间配置器有malloc失败的出错处理函数,最终的希望只能寄托在那里了。

如下是整个chunk_alloc函数:
template <bool threads>
char *__default_alloc<threads>::chunk_alloc(size_t size, int& nobjs)
{
size_t total_size = size * nobjs;
char *result;
size_t size_left = end_free - start_free;
if (size_left >= total_size) //内存池剩余空间满足需求
{
result = start_free;
start_free += total_size;
return result;
}
else if (size_left >= size) //剩余空间不能全部满足,但至少满足一块
{
nobjs = size_left / size;
result = start_free;
start_free += nobjs * size;
return result;
}
else //连一个区块都无法满足
{
if (size_left > ) //将残余内存分配给其他合适的链表
{
obj *volatile *my_free_list = free_list + FREELIST_INDEX(size_left);
((obj *)start_free)->free_list_link = *my_free_list; //在头部插入
*my_free_list = (obj *)start_free;
}
size_t bytes_to_get = * total_size + ROUND_UP(heap_size >> );
start_free = (char *)malloc(bytes_to_get);
if (start_free == NULL) //堆空间不足
{
int i;
obj *volatile *my_free_list;
obj *p;
for (i = size; i < __MAX_BYTES; i++)
{
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (p != NULL)
{
*my_free_list = p->free_list_link;
start_free = (char *)p;
end_free = start_free + i;
return chunk_alloc(size, nobjs);
}
}
end_free = NULL;
//调用第一级配置器
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
}
heap_size += bytes_to_get;
end_free = start_free + heap_size;
return chunk_alloc(size, nobjs);
}
}
内存释放
第二级配置器的deallocate函数并不会直接释放内存块。当内存块大小大于128字节时才会直接释放,否则会将内存块回收到相应的链表当中。如下:
void __default_alloc<threads>::deallocate(void *p, size_t n)
{
//大于__MAX_BYTES,则释放该内存
if (n > (size_t)__MAX_BYTES)
malloc_alloc::deallocate(p, n);
obj *q = (obj *)p;
obj *volatile *my_free_list;
my_free_list = free_list + FREELIST_INDEX(n);
//小于__MAX_BYTES,则回收区块,并未释放
q->free_list_link = *my_free_list;
*my_free_list = q;
}

内存对外接口

STL对外提供了一个simple_alloc类,该类提供统一的接口:allocate函数、deallocate函数,使得外部无需关心使用的是几级内存配置器。另外simple_alloc类将外部所需的对象个数转换为字节。如下。

template <typename T, typename Alloc>
class simple_alloc
{
public:
static T *allocate(size_t n) // 个数
{
return n == ? : (T*)Alloc::allocate(n * sizeof(T)); // 将个数转换为字节
} static T *allocate(void)
{
return (T*)Alloc::allocate(sizeof(T));
} static void deallocate(T *p, size_t n) // 个数
{
if (n != )
Alloc::deallocate(p, n * sizeof(T));
} static void deallocate(T *p)
{
Alloc::deallocate(p, sizeof(T));
}
};

(全文完)

附:
一款简易版STL的实现,项目地址:https://github.com/zinx2016/MiniSTL/tree/master/MiniSTL
 
 
 
 
上一篇:Centos下安装软件的常用方法


下一篇:HBase数据库集群配置【转】