__malloc_alloc_template分配器:該分配器是對malloc、realloc以及free的封裝：
當調用malloc和realloc申請不到內存空間的時候，會改調用oom_malloc()和oom_realloc()，這兩個函數會反復調用用戶傳遞過來的out of memory handler處理函數，直到能用malloc或者realloc申請到內存為止。
如果用戶沒有傳遞__malloc_alloc_oom_handler，__malloc_alloc_template會拋出__THROW_BAD_ALLOC異常。所以，內存不足的處理任務就交給類客戶去完成。
__default_alloc_template分配器
這個分配器采用了內存池的思想，有效地避免了內碎片的問題（順便一句話介紹一下內碎片和外碎片：內碎片是已被分配出去但是用不到的內存空間，外碎片是由於大小太小而無法分配出去的空閒塊）。
如果申請的內存塊大於128bytes，就將申請的操作移交__malloc_alloc_template分配器去處理；如果申請的區塊大小小於128bytes時，就從本分配器維護的內存池中分配內存。
分配器用空閒鏈表的方式維護內存池中的空閒空間。
#include<iostream>
#include<stdarg.h>
using namespace std;
#define __DEBUG__
static string GetFileName(const string& path)
{
char ch = '/';
#ifdef _WIN32
ch = '\\';
#endif
size_t pos = path.rfind(ch);
if (pos == string::npos)
return path;
else
return path.substr(pos + 1);
}
// 用於調試追溯的trace log
inline static void __trace_debug(const char* function,
const char * filename, int line, char* format, ...)
{
#ifdef __DEBUG__
// 輸出調用函數的信息
fprintf(stdout, "【%s:%d】 %s", GetFileName(filename).c_str(), line, function);
// 輸出用戶打的trace信息
va_list args;
va_start(args, format);
vfprintf(stdout, format, args);
va_end(args);
#endif
}
#define __TRACE_DEBUG(...) \
__trace_debug(__FUNCTION__, __FILE__, __LINE__, __VA_ARGS__);
typedef void(*MallocAllocHandler)();
template <int inst>
class MallocAllocTemplate
{
protected:
static MallocAllocHandler _handler;
static void* Oom_Malloc(size_t n)
{
MallocAllocHandler handler = NULL;
void* ret = NULL;
while (1)
{
handler = _handler;
if (handler == NULL)
{
cout << "out of memory" << endl;
//exit(1);
}
(*handler)();
ret = malloc(n);
if (ret)
return ret;
}
}
public:
static void * Allocate(size_t n)
{
void *result = malloc(n);
if (0 == result) result = Oom_Malloc(n);
__TRACE_DEBUG("調用一級空間配置器開辟內存：ptr:%p,size:%u\n", result,n);
return result;
}
static void Deallocate(void *p, size_t n)
{
free(p);
__TRACE_DEBUG("調用一級空間配置器釋放內存：ptr:%p,size:%u\n", p, n);
}
static void(*SetMallocHandler(MallocAllocHandler f))()
{
void(*old)() = _handler;
_handler = f;
return(old);
}
};
template<int inst> MallocAllocHandler MallocAllocTemplate<inst>::_handler = NULL;
template <bool threads, int inst>
class DefaultAllocTemplate
{
enum { ALIGN = 8 };
enum { MAX_BYTES = 128 };
enum { NFREELISTS = MAX_BYTES / ALIGN };
union Obj {
union Obj * _freeListLink;
char _clientData[1]; /* The client sees this. */
};
static Obj * volatile _freeList[NFREELISTS];//指針數組
static char *_startFree;
static char *_endFree;
static size_t _heapSize;
static size_t FreeListIndex(size_t bytes) {
return (((bytes)+ALIGN - 1) / ALIGN - 1);
}
static size_t RoundUp(size_t bytes) {
return (((bytes)+ALIGN - 1) & ~(ALIGN - 1));
}
static char* chunkAlloc(size_t n, int& nobjs)
{
char* ret = NULL;
size_t totalBytes = n*nobjs;
size_t freeLeft = _endFree - _startFree;
if (freeLeft >= totalBytes)
{
ret = _startFree;
_startFree += totalBytes;
__TRACE_DEBUG("內存池足夠分配空間：ptr:%p,size:%u\n", ret, totalBytes);
return(ret);
}
else if (freeLeft >= n)
{
nobjs = freeLeft / n;
totalBytes = n*nobjs;
ret = _startFree;
_startFree += totalBytes;
__TRACE_DEBUG("內存池只有空間：ptr:%p,size:%u\n", ret, totalBytes);
return(ret);
}
else
{
size_t bytesOfGet = 2 * totalBytes + RoundUp(_heapSize >> 4);
//將剩下的小塊內存掛載
if (freeLeft > 0)
{
Obj* myFreeList = _freeList[FreeListIndex(freeLeft)];
((Obj*)_startFree)->_freeListLink = myFreeList;
_freeList[FreeListIndex(freeLeft)] = (Obj*)_startFree;
}
_startFree =(char*) malloc(bytesOfGet);
if (_startFree == NULL)
{
Obj* myFreeList, *p;
for (int i = n; i < MAX_BYTES; i += ALIGN)
{
myFreeList = _freeList[FreeListIndex(i)];
if (myFreeList != NULL)
{
p = myFreeList;
myFreeList = myFreeList->_freeListLink;
_startFree = (char*)p;
_endFree = _startFree + i;
return chunkAlloc(n, nobjs);//會進入else if
}
}
//空閒鏈表無比n大的內存
_endFree = NULL;//防止_startFree返回0，而_endFree為一個很大的值，誤認為有內存池內存可分配
_startFree = (char*)MallocAllocTemplate<0>::Allocate(bytesOfGet);
}
_heapSize += bytesOfGet;
_endFree = _startFree + bytesOfGet;
return chunkAlloc(n, nobjs);//會進if
}
}
static void* Refill(size_t n)
{
int nobjs = 20;
char * chunk = chunkAlloc(n, nobjs);
Obj* volatile * myFreeList;
Obj* ret;
Obj * currentObj=NULL, *nextObj=NULL;
int i;
if (1 == nobjs) return(chunk);
myFreeList = _freeList + FreeListIndex(n);
ret = (Obj *)chunk;
*myFreeList = nextObj = (Obj *)(chunk + n);
/*for (i = 1;; i++) {
currentObj = nextObj;
nextObj = (Obj *)((char *)nextObj + n);
if (nobjs - 1 == i)
{
currentObj->freeListLink = 0;
break;
}
else
{
currentObj->freeListLink = nextObj;
}
}*/
//
for (i = 0; i < nobjs - 1; ++i)
{
currentObj = nextObj;
nextObj = nextObj + 1;
currentObj->_freeListLink = nextObj;
}
__TRACE_DEBUG("掛載空間到自由鏈表\n");
currentObj->_freeListLink = NULL;
return ret;
}
public:
static void Deallocate(void* p, size_t size)
{
if (size > MAX_BYTES)
{
MallocAllocTemplate<0>::Deallocate(p, size);
__TRACE_DEBUG("調用一級空間配置器釋放內存：ptr:%p,size:%u\n",p,size);
}
else
{
Obj * myFreeList = _freeList[FreeListIndex(size)];
((Obj*)p)->_freeListLink = myFreeList;
_freeList[FreeListIndex(size)] = (Obj*)p;
__TRACE_DEBUG("掛載到自由鏈表釋放內存：ptr:%p,size:%u\n", p, size);
}
}
static void * Allocate(size_t n)
{
Obj * volatile * myFreeList;
Obj * result;
if (n > MAX_BYTES)
{
return(MallocAllocTemplate<1>::Allocate(n));
}
myFreeList = _freeList + FreeListIndex(n);
result = *myFreeList;
if (result == NULL)
{
void* ret = Refill(RoundUp(n));
__TRACE_DEBUG("分配空間：ptr:%p\n", ret);
return ret;
}
*myFreeList = result->_freeListLink;
__TRACE_DEBUG("從自由鏈表直接取：ptr:%p,size:%u\n", result,n);
return result;
}
};
template<bool threads,int inst>
typename DefaultAllocTemplate<threads, inst>::Obj* volatile DefaultAllocTemplate<threads, inst>::_freeList[DefaultAllocTemplate<0, 0>::NFREELISTS] = { 0 };//指針數組
template<bool threads,int inst>
char* DefaultAllocTemplate<threads, inst>::_startFree = NULL;
template<bool threads, int inst>
char* DefaultAllocTemplate<threads, inst>::_endFree = NULL;
template<bool threads, int inst>
size_t DefaultAllocTemplate<threads, inst>::_heapSize = 0;
# ifdef __USE_MALLOC
typedef MallocAllocTemplate<0> Alloc;
typedef MallocAllocTemplate<0> Alloc;
# else
typedef DefaultAllocTemplate<0, 0> Alloc;
typedef DefaultAllocTemplate<0, 0> Alloc;
#endif
template<class T, class Alloc>
class SimpleAlloc
{
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)); }
//將調用傳遞給配置器的成員函數，可能是第一級也可能是第二級
};
void Test1()
{
//MallocAllocTemplate<1> d;
////int *p=(int*)MallocAllocTemplate<1>::Allocate(sizeof(int));
//int *p=(int*)d.Allocate(sizeof(int));
//*p = 2;
//cout << *p << endl;
//d.Deallocate(p, sizeof(int));
//DefaultAllocTemplate<0, 0> a;
//int* p1 = (int*)a.Allocate(sizeof(int));
//*p1 = 3;
//cout << *p1 << endl;
//typedef MallocAllocTemplate<0> Alloc;
// 測試調用一級配置器分配內存
cout << " 測試調用一級配置器分配內存 " << endl;
char*p1 = SimpleAlloc< char, Alloc>::Allocate(129);
SimpleAlloc<char, Alloc>::Deallocate(p1, 129);
// 測試調用二級配置器分配內存
cout << " 測試調用二級配置器分配內存 " << endl;
char*p2 = SimpleAlloc< char, Alloc>::Allocate(128);
char*p3 = SimpleAlloc< char, Alloc>::Allocate(128);
char*p4 = SimpleAlloc< char, Alloc>::Allocate(128);
char*p5 = SimpleAlloc< char, Alloc>::Allocate(128);
SimpleAlloc<char, Alloc>::Deallocate(p2, 128);
SimpleAlloc<char, Alloc>::Deallocate(p3, 128);
SimpleAlloc<char, Alloc>::Deallocate(p4, 128);
SimpleAlloc<char, Alloc>::Deallocate(p5, 128);
for (int i = 0; i < 21; ++i)
{
printf(" 測試第%d次分配 \n", i + 1);
char*p = SimpleAlloc< char, Alloc>::Allocate(128);
}
}
// 測試特殊場景
void Test2()
{
cout << " 測試內存池空間不足分配個 " << endl;
// 8*20->8*2->320
char*p1 = SimpleAlloc< char, Alloc>::Allocate(8);
char*p2 = SimpleAlloc< char, Alloc>::Allocate(8);
cout << " 測試內存池空間不足， 系統堆進行分配 " << endl;
char*p3 = SimpleAlloc< char, Alloc>::Allocate(12);
}
void Test3()
{
cout << " 測試系統堆內存耗盡 " << endl;
SimpleAlloc<char, Alloc>::Allocate(1024 * 1024 * 1024);
//SimpleAlloc<char, Alloc>::Allocate(1024*1024*1024);
SimpleAlloc<char, Alloc>::Allocate(1024 * 1024);
// 不好測試， 說明系統管理小塊內存的能力還是很強的。
for (int i = 0; i < 100000; ++i)
{
char*p1 = SimpleAlloc< char, Alloc>::Allocate(128);
}
}
運行截圖：