史上最骚のSTL空间分配器
Time: 2020-08-30 Tags: binaryLink: 史上最骚のSTL空间分配器
中规中矩的分配器
此分析是针对C++11以前的较低版本STL来说
allocator是一个对::operator new和::operator delete的简单包装。没有较高的分配效率，因此常常被弃用。
以下是它的核心代码：
template <class T>
inline T* allocate(ptrdiff_t size,T*){
set_new_handler(0);
T* tmp = (T*)(::operator new((size_t)(size * sizeof(T)));
if (tmp == 0){
cerr << "Out of memory" << endl;
exit(1);
}
return 0;
}
template <class T>
void deallocate(T* buffer){
::operator delete(buffer);
}
由此可见其简陋性。
特(zui)殊(sao)的分配器
基本思想
- 将内存空间的分配与释放和对象内容的构造与析构分开。
在<stl_construct.h>中定义construct和distory函数，在<stl_alloc.h>中定义一个内存池。
- 采用多级配置器的内存处理方法。
第一级分配器直接使用malloc和free，第二层配置器视情况采用不同的分配策略。当内存块大于128bytes时视之为“足够大”，使用第一级配置器；当内存块小于128bytes时，视之为“过小”，则采用memory pool进行分配。
第一级配置器剖析
第一级配置器：__malloc_alloc_template
源码：
#if 0
# include <new>
# define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
# include <iostream>
#define __THROW_BAD_ALLOC \
std::cerr << "out of memory" << std::endl; \
exit(1);
#endif
template <int inst>
class __malloc_alloc_template{
private:
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
static void (*__malloc_alloc_oom_handler)();
public:
static void *allocate(size_t n){
void *result = malloc(n);
if (result == 0)
result = oom_malloc(n);
return result;
}
static void deallocate(void *p, size_t){
free(p);
}
static void* reallocate(void *p,size_t,size_t new_size){
void *result = realloc(p, new_size);
if (result == 0)
result = oom_realloc(p, new_size);
return result;
}
static void (* set_malloc_handler(void (*f)()))(){
void (*old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return (old);
}
}; // end of __malloc_alloc_template
template <int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
template <int inst>
void *__malloc_alloc_template<inst>::oom_malloc(size_t n){
void (*my_malloc_handler)();
void *result;
for (;;){
my_malloc_handler = __malloc_alloc_oom_handler;
if(my_malloc_handler == 0) {
__THROW_BAD_ALLOC;
}
(*my_malloc_handler)();
result = malloc(n);
if(result)
return (result);
}
}
template <int inst>
void * __malloc_alloc_template<inst>::oom_realloc(void *p,size_t n){
void (*my_malloc_handler)();
void *result;
for (;;){
my_malloc_handler = __malloc_alloc_oom_handler;
if (my_malloc_handler == 0){
__THROW_BAD_ALLOC;
}
(*my_malloc_handler)();
result = malloc(n);
if(result)
return (result);
}
}
程序使用了malloc、free、realloc 进行内存的分配、释放和重分配。因为c++没有提供对应realloc()的操作，因此不能直接使用set_new_handler()。因此仿真了一个类似的set_new_handler()。
另外程序在内存不足时使用递归调用的“内存不足处理”函数。期望每次调用获得足够的内存而圆满完成任务。
第二级配置器剖析
第二级配置器：__default_alloc_template
这一级配置器以内存池管理。每一次配置一大块内存，并维护对应的自由链表。下次再有相同大小的内存需求，就直接从free-lists中拔出。用户归还内存时，配置器会将其回收到free-lists中。此外，为了方便管理，二级配置器会自动把小块内存上调至8的倍数。自由链表有16个，他们管理的大小分别为8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128bytes。
部分源码：
enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};
template <bool threads,int inst>
class __default_alloc_template{
private:
static size_t ROUND_UP(size_t bytes){
return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
}
private:
union obj
{
union obj *free_list_link;
char client_date[1];
};
private:
static obj *volatile free_list[__NFREELISTS];
static size_t FREELIST_INDEX(size_t bytes){
return (((bytes) + __ALIGN - 1) / __ALIGN - 1);
}
static void *refill(size_t n);
static char *chunk_alloc(size_t size, int &nobjs);
static char *start_free;
static char *end_free;
static size_t heap_size;
public:
static void *allocate(size_t n);
static void deallocate(void *p,size_t n);
static void *reallocate(void *p, size_t old_sz, size_t new_sz);
}; // end of __default_alloc_template
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = 0;
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = 0;
template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = 0;
template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj *volatile __default_alloc_template<threads, inst>::free_list[__NFREELISTS] =
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,};
每个节点用一个联合体obj组成。它相当于一个指针。这样做其实是为了不浪费额外的内存。
在二级配置器中，allocate首先判断区块的大小，如果小于128bytes就调用第一级配置器，小于128bytes时就去检查对应的free_list。如果没有可用的内存块，就上调大小，并调用refill。
static void *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 == 0){
void *r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->free_list_link;
return (result);
}
很清晰。
deallocate也是同样的思路。
static void deallocate(void *p,size_t n){
obj *q = (obj *)p;
obj *volatile *my_free_list;
if (n > (size_t) __MAX_BYTES){
q = 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;
}
对于reallocate，直接使用上面的两个现成函数即可。
static void *reallocate(void *p, size_t old_sz, size_t new_sz){
deallocate(p, old_sz);
p = allocate(new_sz);
return p;
}
重新装填refill：
在allocate发现free list中没有合适的区块时，调用refill进行重新装填。缺省得到20个新节点，但是有时内存不足，可能得不到这么多。
template<bool threads,int inst>
void *__default_alloc_template<threads,inst>::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 (nobjs == 1) // Only one free list returned
return (chunk);
// ready to adjust the free list
my_free_list = free_list + FREELIST_INDEX(n);
result = (obj *)chunk; // this chunk will be returned
*my_free_list = next_obj = (obj *)(chunk + n);
for (i = 1;;i++){ // add all the chunks to free list
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);
}
返回20个新节点并将其加入到free list中，成为链表的一部分。