1. SGI中的記憶體管理
在SGI中， 其記憶體配置設定把這兩步獨立出了兩個函數：allocate 申請記憶體，construct 調用構造函數，分别在
2.構造和析構的工具
在stl_construct.h中
//第一個版本destory接受一個指針，然後調用析構函數
template <class T>
inline void destroy(T* pointer) {
pointer->~T();
}
//構造函數
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value);
}
//第二個版本的destory,接收兩個疊代器，并根據元素的值的類型來調用析構函數，為__false_type,調用析構，為__true_type,直接不管。
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
for ( ; first < last; ++first)
destroy(&*first);
}
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
__destroy_aux(first, last, trivial_destructor());
}
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
__destroy(first, last, value_type(first));
}
//特化版本的destroy函數。
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}
3.空間配置與釋放
考慮到小型區塊可能造成的記憶體破碎問題，SGI設計了雙層級配置器。第一級配置器直接使用malloc()和free(),第二級配置器對具體問題使用不同的政策。
3.1 第一級配置器
class __malloc_alloc_template {
private:
//以下函數處理記憶體不足的情況
//oom - out of memory
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
public:
static void * allocate(size_t n)
{
void *result = malloc(n); //第一級配置器直接調用malloc
if ( == result) result = oom_malloc(n);//無法滿足需求調用oom_malloc(n)
return result;
}
static void deallocate(void *p, size_t /* n */)
{
free(p);
}
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
void * result = realloc(p, new_sz);
if ( == result) result = oom_realloc(p, new_sz);
return result;
}
//參數為void f(),傳回值也為void f(),用于自己指定oom handle
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
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) { __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) { __THROW_BAD_ALLOC; }
(*my_malloc_handler)();
result = realloc(p, n);
if (result) return(result);
}
}
3.2 二級配置器
template <bool threads, int inst>
class __default_alloc_template {
private:
// Really we should use static const int x = N
// instead of enum { x = N }, but few compilers accept the former.
enum {__ALIGN = }; //小型區塊的上調邊界
enum {__MAX_BYTES = };//小型區塊的上限
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free_list個數
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-) & ~(__ALIGN - ));//上調的__ALIGN的倍數
}
__PRIVATE:
//obj是節點。
union obj {
union obj * free_list_link;
char client_data[]; /* The client sees this. */
};
private:
static obj * __VOLATILE free_list[];
//獲得節點的序号，0開始
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN-)/__ALIGN - );
}
// 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:
/* n must be > 0 */
//yk:記憶體配置設定
static void * allocate(size_t n)
{ //後面介紹
};
/* p may not be 0 */
//yk : free memory
static void deallocate(void *p, size_t n)
{//後面介紹
}
// reallocate memory
static void * reallocate(void *p, size_t old_sz, size_t new_sz);
} ;
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, > alloc;
typedef __default_alloc_template<false, > single_client_alloc;
//成員函數的初始化
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::start_free = ;
template <bool threads, int inst>
char *__default_alloc_template<threads, inst>::end_free = ;
template <bool threads, int inst>
size_t __default_alloc_template<threads, inst>::heap_size = ;
template <bool threads, int inst>
__default_alloc_template<threads, inst>::obj * __VOLATILE
__default_alloc_template<threads, inst> ::free_list[
# ifdef __SUNPRO_CC
__NFREELISTS
# else
__default_alloc_template<threads, inst>::__NFREELISTS
# endif
] = {, , , , , , , , , , , , , , , , };
// The 16 zeros are necessary to make version 4.1 of the SunPro
// compiler happy. Otherwise it appears to allocate too little
// space for the array.
我們最關心的有三點：1. 記憶體池的建立。2.記憶體的配置設定。 3. 記憶體的釋放。
1、SGI記憶體池的結構
内部的結構體為：
union obj {
union obj * free_list_link;
char client_data[]; /* The client sees this. */
};
一個free_list指針指向一個128byte的空間，每個空間根據管理的大小（8,16,32……128），有不同個數的節點數目。為了節省指針的空間， 每個節點為一個union.其中的free_list_link指向下一個空的節點,client_data為柔性數組，大小為目前空間中每個區塊的大小。
static obj * __VOLATILE free_list[];
為一個free_list數組，有16個free_list,每個free_list也為一個obj,它有一個指針，指向自己管理的空間第一個節點，它的free_list_link指向第一個自己管理的大小的空間。比如說，#11号區域，剛開始的時候，它是管理一個96byte的空間的，它自己的占用的空間存放的是這個96byte的起始位址，它的free_list_link也是指向這個位址，如果這個空間被别人申請了，那麼，申請的時候就會讓它指向下一個96byte的空間。
2、記憶體配置設定
記憶體配置設定的源碼如下：
static void * allocate(size_t n)
{
obj * __VOLATILE * my_free_list;
obj * __RESTRICT result;
if (n > (size_t) __MAX_BYTES) {//大于128byte，直接調用一級配置器
return(malloc_alloc::allocate(n));
}
my_free_list = free_list + FREELIST_INDEX(n);//找到合适的序号的位址
result = *my_free_list;
if (result == ) {//沒有找到合适的，準備重新填充
void *r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result -> free_list_link;//重新調整free_list
return (result);
};
3、空間釋放
static void deallocate(void *p, size_t n)
{
obj *q = (obj *)p;
obj * __VOLATILE * my_free_list;
if (n > (size_t) __MAX_BYTES) {//大于128byte,調用第一級配置器
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;
}
4、重新填充 free_list，
當free_list中沒有可用區塊了，就refill()，準備為free_list重新填充空間。新的空間将取自記憶體池，一般取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);//調用chunk_alloc
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
if ( == nobjs) return(chunk);//隻申請到一個區塊，也是慘，直接傳回這個區塊
my_free_list = free_list + FREELIST_INDEX(n);//申請的比較多的話，my_free_list現在指向n大小的free_list
/* Build free list in chunk */
//以下在申請的空間建立free_list
result = (obj *)chunk;//儲存傳回值
*my_free_list = next_obj = (obj *)(chunk + n);//這是第一個
for (i = ; ; i++) {//從第一個開始，第0個給用戶端了。
current_obj = next_obj;
next_obj = (obj *)((char *)next_obj + n);
if (nobjs - == i) {//沒有了
current_obj -> free_list_link = ;
break;
} else {//如果還有，指向下一個obj
current_obj -> free_list_link = next_obj;
}
}
return(result);
}
5、記憶體池
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) {//如果剩餘空間不多，但還是至少有一個size的大小
nobjs = bytes_left/size; //就盡量分給他
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
} else {//實在沒有辦法，隻能去malloc了
size_t bytes_to_get = * total_bytes + ROUND_UP(heap_size >> );
// Try to make use of the left-over piece.
if (bytes_left > ) {//剩餘的空間，直接放到free_list中。因為申請的時候是按8的倍數來申請
//這裡不會有小區塊的問題
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 ( == start_free) {//oh,沒有申請成功
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 ( != 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 = ; // In case of exception.實在沒有空間了，調用一級配置器，看看oom機制
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
//這是申請成功的，調用自己，修正nobjs
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
return(chunk_alloc(size, nobjs));
}
}
舉個例子：
1.調用chunk_allock(32,20):malloc配置設定40個32byte區域，第一塊個用戶端，19塊給free_list[3],剩餘20塊給記憶體池
2.調用chunk_allock(64,20):free_list[7]為空，那麼向記憶體池請求，記憶體池隻有10個，就把這10個給他，第一個交給用戶端，剩餘9個給free_list[7]維護
3（自己加的）.調用chunk_allock(32, 20):free_list[6]為空，記憶體池啥也沒有，如果malloc失敗，在自己free_list[7]找到一塊，把free_list[7]的一個拿出來釋放到記憶體池，然後調用自己，這裡，記憶體池現在有64byte，是以可以申請兩個32bytes,一個給用戶端，一個由free_list[6]維護
4.接下來調用chunk_alloc(96,20):free_list[11]為空，向記憶體池請求，記憶體池也沒有，隻能調用malloc(),40+n個96bytes區塊,d第一個給用戶端，19個給free_list[11],剩餘20+n給記憶體池