+-
std::alloc 分两级层进行内存管理，第一级在接下来的学习中是次要的，主要内容都集中在第二级里。在 G4.9 版本中，第一级已被删除
G2.9 中的一级内存管理
补充说明
class semple_alloc ：应用层内存分配的基本单位是元素个数[ n] ，但底层实现中二级分配的单位是字节，此处便完成元素个数到字节数的转换[ n * sizeof(T) ]
G2.9 中的二级内存管理【重点】
片段一
补充说明
图片中仅保留了内存分配中最原汁原味的部分，其它内容已被剔除方便学习
bool threads, int inst 仅保留接口，实现中已剔除 实现中全部的成员函数和成员变量都是静态的，因此非常容易扩展为 C 版本
ROUND_UP : 将参数值“上调”整为 8 的倍数（计算内存申请追加量会使用）
union obj *free_list_link : 嵌入式指针，连接可用内存块
volatile ： 多线程时使用，此处可暂忽略
free_list[_NFREELISTS] : 包含 16 个元素，每个元素都是指针，指向自由链表
FREELIST_INDEX : 根据所用内存大小计算对应自由链表下标值（“上调”到8的倍数对应的下标值）
refill : 当自由链表为空时调用
start_free、end_free : 指向战备池
heap_size : 分配累计总量（关系到追加量）片段二
补充说明deallocate ：当内存块小于 128 字节时，内存再无法归还给操作系统（free），自由链表将增长至高峰 内存归还难以实现：存在多条自由连链表且链表可能会很长，链表中的内存块经过分配、归还，已无法高效的去判断链表中的哪些内存块是地址上是连续的（cookie） 此种实现不算内存泄露，或许称之为”霸道“。会影响多任务系统中的其它进程
if (n > (size_t)__MAX_BYTES) : 超过 128 字节时使用一级内存管理（malloc、free）片段三
for(i=1; ;++i) ： 循环从 1 开始，因为第 0 个内存块返回给了客户使用片段四
补充说明内存的补充永远是补充到战备池
start_free = (char*)malloc(bytes_to_get)
== 前一章模拟内存不足时的情况就是改动的此处 ==>
start_free = (bytes_to_get + heap_size > 10000) ? 0 : (char*)malloc(bytes_to_get);片段五
alloc 的简单实现
//本處完全模仿 SGI STL, G2.92 的 std::alloc
//放在 namespace 中因此和 std 不衝突
//此手法和 G4.92 ext\__pool_alloc.h 也完全相同.
#define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
//----------------------------------------------
// 第1級配置器。
//----------------------------------------------
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); //直接使用 malloc()
if (0 == result) result = oom_malloc(n);
return result;
}
static void deallocate(void *p, size_t /* n */)
{
free(p); //直接使用 free()
}
static void* reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
void * result = realloc(p, new_sz); //直接使用 realloc()
if (0 == result) result = oom_realloc(p, new_sz);
return result;
}
static void (*set_malloc_handler(void (*f)()))()
{ //類似 C++ 的 set_new_handler().
void (*old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
//----------------------------------------------
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 (0 == my_malloc_handler) { __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 (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)(); //呼叫處理常式，企圖釋放記憶體。
result = realloc(p, n); //再次嘗試配置記憶體。
if (result) return(result);
}
}
//----------------------------------------------
typedef __malloc_alloc_template<0> malloc_alloc;
template<class T, class Alloc>
class simple_alloc {
public:
static T* allocate(size_t n)
{ return 0 == n? 0 : (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 (0 != n) Alloc::deallocate(p, n*sizeof(T)); }
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof(T)); }
};
//----------------------------------------------
//第二級配置器
//----------------------------------------------
enum {__ALIGN = 8}; //小區塊的上調邊界
enum {__MAX_BYTES = 128}; //小區塊的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; //free-lists 個數
//本例中兩個 template 參數完全沒有派上用場
template <bool threads, int inst>
class __default_alloc_template {
private:
//實際上應使用 static const int x = N
//取代 enum { x = N }, 但目前支援該性質的編譯器不多
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}
private:
union obj {
union obj* free_list_link;
};
private:
static obj* volatile free_list[__NFREELISTS];
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}
// Returns an object of size n, and optionally adds to size n free list.
static void *refill(size_t n);
// Allocates a chunk for nobjs of size "size". nobjs may be reduced
// if it is inconvenient to allocate the requested number.
static char *chunk_alloc(size_t size, int &nobjs);
// Chunk allocation state.
static char* start_free;
static char* end_free;
static size_t heap_size;
public:
static void * allocate(size_t n) //n must be > 0
{
obj* volatile *my_free_list; //obj** 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);
}
static void deallocate(void *p, size_t n) //p may not be 0
{
obj* q = (obj*)p;
obj* volatile *my_free_list; //obj** my_free_list;
if (n > (size_t) __MAX_BYTES) {
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;
}
static void * reallocate(void *p, size_t old_sz, size_t new_sz);
};
//----------------------------------------------
// We allocate memory in large chunks in order to
// avoid fragmentingthe malloc heap too much.
// We assume that size is properly aligned.
// We hold the allocation lock.
//----------------------------------------------
template <bool threads, int inst>
char*
__default_alloc_template<threads, inst>::
chunk_alloc(size_t size, int& nobjs)
{
char* result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free;
if (bytes_left >= total_bytes) {
result = start_free;
start_free += total_bytes;
return(result);
} else if (bytes_left >= size) {
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
} else {
size_t bytes_to_get =
2 * total_bytes + ROUND_UP(heap_size >> 4);
// Try to make use of the left-over piece.
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 (0 == start_free) {
int i;
obj* volatile *my_free_list, *p;
//Try to make do with what we have. That can't
//hurt. We do not try smaller requests, since that tends
//to result in disaster on multi-process machines.
for (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, nobjs));
//Any leftover piece will eventually make it to the
//right free list.
}
}
end_free = 0; //In case of exception.
start_free = (char*)malloc_alloc::allocate(bytes_to_get);
//This should either throw an exception or
//remedy the situation. Thus we assume it
//succeeded.
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return(chunk_alloc(size, nobjs));
}
}
//----------------------------------------------
// Returns an object of size n, and optionally adds
// to size n free list.We assume that n is properly aligned.
// We hold the allocation lock.
//----------------------------------------------
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** my_free_list;
obj* result;
obj* current_obj;
obj* next_obj;
int i;
if (1 == nobjs) return(chunk);
my_free_list = free_list + FREELIST_INDEX(n);
//Build free list in chunk
result = (obj*)chunk;
*my_free_list = next_obj = (obj*)(chunk + n);
for (i=1; ; ++i) {
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);
}
//----------------------------------------------
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>
typename __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, };
//----------------------------------------------
//令第2級配置器的名稱為 alloc
typedef __default_alloc_template<false,0> alloc;