【移動應用開發(fā)技術】SGI版本空間配置器

【移動應用開發(fā)技術】SGI版本空間配置器

1、STL中的空間配置器

在STL中，空間配置器分了2組，分別為一級空間配置器和二級空間配置器，但是它們都有自己各自運用的場合；一般說來，一級空間配置器一般分配的空間大于128B，二級空間配置器的分配空間為小于128B.

其中SGI中的STL的空間配置器設計哲學如下：

(1)、向systemheap要求申請空間

(2)、考慮多線程的狀態(tài)

(3)、考慮內(nèi)存不足時的應變措施

(4)、考慮過多"小型區(qū)塊"可能造成的內(nèi)存碎片問題

在剖析源碼時，為了將問題控制在一定的復雜度內(nèi)，以下源碼皆排除多線程狀態(tài)的處理；

0：表示非多線程版本；

inst:表示不關注多線程的問題；2、一級空間配置器

(1)、為內(nèi)存不足做好準備:(1)、拋出異常，也就是輸出一句話；(2)、調(diào)用自己設置的函數(shù)去處理(比如說是釋放一些空間，回收一些碎片的空間)；

一級空間配置器的本質(zhì)：模仿實現(xiàn)了set_new_handler機制；

set_new_handler機制的實現(xiàn)：(1)、定義一個函數(shù)指針；(2)、定義一個函數(shù)；(3)、賦值比較；

(2)、抽取的代碼實現(xiàn)#if

1

#include<iostream>

#include<new>

#include<malloc.h>

using

namespace

std;

//#define

__THROW_BAD_ALLOC

throw

bad_alloc

#define

__THROW_BAD_ALLOC

cerr<<"Throw

bad

alloc,

Out

Of

Memory."<<endl;

exit(1)

//定義異常,就是輸出一句話,并且結束程序.

#elif

!defined

(__THROW_BAD_ALLOC)

//如果沒有定義這個異常,下面就定義

#include<iostream.h>

#define

__THROW_BAD_ALLOC

cerr<<"out

of

memory"<<endl;

exit(1);

#endif

template<int

inst>

class

__malloc_alloc_template{

private:

static

void*

oom_malloc(size_t);

//對申請空間失敗的處理函數(shù)

static

void*

oom_realloc(void

*,

size_t);

//對擴展空間失敗處理的函數(shù)

static

void(*

__malloc_alloc_oom_handler)();

//定義一個函數(shù)指針

public:

static

void*

allocate(size_t

n){

//分配空間

void

*result

=

malloc(n);

if(0

==

result)

result

=

oom_malloc(n);

//分配空間失敗，調(diào)用oom_malloc()函數(shù)

return

result;

//將申請的空間的地址返回

}

static

void

deallocate(void

*p,

size_t){

free(p);

//釋放空間

}

static

void*

reallocate(void

*p,

size_t,

size_t

new_sz){

void

*result

=

realloc(p,

new_sz);

//擴展新空間;

if(0

==

result)

//擴展失敗

oom_realloc(p,new_sz);

//調(diào)用擴展空間失敗的處理函數(shù)

return

result;

}

public:

//set_new_handler(Out_Of_Memory);

static

void(*set_malloc_handler(void(*f)()))(){

//這是一個指針函數(shù),函數(shù)名稱:set_malloc_handler,參數(shù):是一個函數(shù)指針,返回值:是一個函數(shù)指針;

void(*old)()

=

__malloc_alloc_oom_handler;

//將原有空間的地址保存在old中;

__malloc_alloc_oom_handler

=

f;

//將自己定義的函數(shù)地址給__malloc_alloc_oom_handler;

return

old;

//每次可以保存其上一次的地址.

}

};

template<int

inst>

void

(*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)()

=

0;

//對定義的靜態(tài)函數(shù)指針初始化為0;

template<int

inst>

void*

__malloc_alloc_template<inst>::oom_malloc(size_t

n){

//處理空間失敗的問題

void

*result;

void(*

my_malloc_handler)();

//定義一個函數(shù)指針;

for(;;){

my_malloc_handler

=

__malloc_alloc_oom_handler;

if(0

==

my_malloc_handler){

//自己沒有定義處理空間失敗的新函數(shù)

__THROW_BAD_ALLOC;

//異常拋出;程序終止;

}

(*my_malloc_handler)();

//調(diào)用自己編寫的處理函數(shù)(一般都是回收空間之類的);

result

=

malloc(n);

//在此申請分配空間

if(result){

//申請成功

return

result;

//將地址返回;

}//那么，這個程序將會一直持續(xù)到空間分配成功才最終返回.

}

}

template<int

inst>

void*

__malloc_alloc_template<inst>::oom_realloc(void

*p,

size_t

n){

void(*my_malloc_handler)();

//函數(shù)指針

void

*result;

for(;;){

my_malloc_handler

=

__malloc_alloc_oom_handler;

//將這個給其賦值

if(0

==

my_malloc_handler){

//外面沒有定義處理的函數(shù)

__THROW_BAD_ALLOC;

//異常拋出,程序結束.

}

(*my_malloc_handler)();

//調(diào)用自己編寫的處理函數(shù)(一般都是回收空間之類的);

result

=

realloc(p,

n);

//再次擴展空間分配;

if(result){

//擴展成功,就返回

return

result;

}

//一直持續(xù)成功，知道擴展空間分配成功才返回;

}

}

typedef

__malloc_alloc_template<0>

malloc_alloc;

//一級空間配置器:malloc_alloc;第一級空間配置器就是:(1)、對malloc、free的簡單封裝；(2)、模擬C++的set_new_handler()已處理內(nèi)存不足的情況；總結:

(1)、一級空間配置器其實就是先自己開辟空間，要是失敗了;

(2)、調(diào)用處理空間失敗的函數(shù)，在其內(nèi)部，先看我們自己在外面有沒有寫針對這個的處理函數(shù)，要是沒寫，就是異常拋出，程序結束；

(3)、要是寫了，就調(diào)用我們自己寫的函數(shù)，在次分配空間，進入死循環(huán)中，直到空間分配成功，方可退出循環(huán);

還要注意的是:staticvoid(*set_malloc_handler(void(*f)()))()；這是一個指針函數(shù);3、二級空間配置器

(1)、當所分配的空間小于128B時，則以內(nèi)存池去管理;對小額區(qū)塊，自動將內(nèi)存調(diào)至8的倍數(shù),并維護16個自由鏈表,各自管理大小分別為:8162432404856128B的小額區(qū)塊;

(2)、剛開始所分配的內(nèi)存空間，一半當做自由鏈表，一半當做內(nèi)存池；當再次分配同樣大小的空間時，直接先從自由鏈表中分配；當再次分配其他大小空間時，先看內(nèi)存池中有無空間,有的話，直接分配，掛載即可。模型如下：整個分配空間都是很節(jié)省化的:其抽取代碼如下：//二級空間配置器由自由鏈表和內(nèi)存池組成;

enum

{__ALIGN

=

8};

//一塊鏈表8B

enum

{__MAX_BYTES

=

128};

//小于128B調(diào)用二級的

enum

{__NFREELISTS

=

__MAX_BYTES

/

__ALIGN};

//一共分配16個自由鏈表,負責16種次分配能力.

template<bool

threads,

int

inst>

//不考慮多線程狀態(tài);

class

__default_alloc_template{

public:

static

void*

allocate(size_t

n);

//分配空間

static

void

deallocate(void

*p,

size_t

n);

//銷毀空間

static

void*

reallocate(void

*p,

size_t,

size_t

new_sz);

//擴展空間

private:

static

size_t

ROUND_UP(size_t

bytes){

//向上調(diào)整函數(shù);

return

(((bytes)

+

__ALIGN-1)

&

~(__ALIGN-1));

//調(diào)為當前字節(jié)是8的整數(shù)倍.

}

private:

union

obj{

//共用體

union

obj

*

free_list_link;

//自由鏈表的指向

char

client_data[1];

};

private:

static

obj*

volatile

free_list[__NFREELISTS];

//定義了一個指針數(shù)組;

static

size_t

FREELIST_INDEX(size_t

bytes){

//求當前字節(jié)的自由鏈表的下標;

return

((bytes)+__ALIGN-1)

/

__ALIGN-1;

}

private:

static

char

*start_free;

//開始空間的下標

static

char

*end_free;

//結束空間的下標

static

size_t

heap_size;

//堆空間大小

static

void

*refill(size_t

n);

//填充函數(shù)

static

char*

chunk_alloc(size_t

size,

int

&nobjs);

//

};

template<bool

threads,

int

inst>

//以下都是對靜態(tài)變量的初始化,都為0;

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};

template<bool

threads,

int

inst>

void*

__default_alloc_template<threads,

inst>::allocate(size_t

n){

//分配空間的函數(shù)

obj

*

volatile

*my_free_list;

obj

*result;

if(n

>

__MAX_BYTES){

//分配空間的大小大于128B的話，就調(diào)用一級空間配置器

return

malloc_alloc::allocate(n);

}

my_free_list

=

free_list

+

FREELIST_INDEX(n);

//free_list是二維數(shù)組名稱,找往哪個鏈下掛；

result

=

*my_free_list;

//取出其值,因為my_free_list是二階指針;

if(result

==

0){

//沒有內(nèi)存池空間;

void

*r

=

refill(ROUND_UP(n));

//調(diào)用refill()函數(shù)

return

r;

}

*my_free_list

=

result->free_list_link;

//進行掛載連接;

return

result;

}

template<bool

threads,

int

inst>

void*

__default_alloc_template<threads,

inst>::refill(size_t

n){

//沒有可用區(qū)塊時,就調(diào)用refill()函數(shù);

int

nobjs

=

20;//就是要分20塊;

char

*chunk

=

chunk_alloc(n,

nobjs);

//調(diào)用內(nèi)存池函數(shù);

obj

*

volatile

*my_free_list;

obj

*result;

obj

*current_obj,

*next_obj;

int

i;

if(1

==

nobjs){

//當分配到只有一塊空間時,直接返回.

return

chunk;

}

my_free_list

=

free_list

+

FREELIST_INDEX(n);

//找到對應的下標，進行連接的工作;

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>::chunk_alloc(size_t

size,

int

&nobjs){

//內(nèi)存池函數(shù)

char

*result;

//關鍵要明白以下的各種情況;

size_t

total_bytes

=

size

*

nobjs;

//這里的size已經(jīng)是上調(diào)過的字節(jié);求取20*size個字節(jié)的大小

size_t

bytes_left

=

end_free

-

start_free;

//剛開始，遺留字節(jié)為0;

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);

//申請2倍的total_bytes；

if(bytes_left

>

0){

//遺留字節(jié)數(shù)=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;

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);

}

}

end_free

=

0;

start_free

=

(char

*)malloc_alloc::allocate(bytes_to_get);

}

heap_size

+=

bytes_to_get;

//記錄此時堆空間的大小;

end_free

=

start_free

+

bytes_to_get;

//指向了最后;

return

chunk_alloc(size,

nobjs);

//上去在此調(diào)用這個函數(shù);

}

}nobjs=20;這個是經(jīng)驗值，開辟空間留有余地，方便直接查找，以后就不用再次開辟空間了，提高了效率;這個我們自己給不同的字節(jié)情況(小于128B的)，就會知道其中發(fā)生了什么;SGI第二級空間配置器：

(1)、維護16個自由鏈表，分別有16種小型區(qū)塊的配置能力；如果內(nèi)存不足，調(diào)用一級空間配置器(那里有處理程序);

(2)、如果申請空間的需求大于128B,就調(diào)用一級空間配置器.總結:

(1)、二級空間配置器(最后山窮水盡)>調(diào)用一級空間配置器>(1)、拋出異常(2)、調(diào)用自己編寫的處理函數(shù)；

STL內(nèi)存配置思想：C++STL是兩級配置內(nèi)存的，具體來說：第一級負責管理大塊內(nèi)存，要保證有類似new-handler的機制；第二級負責管理小塊內(nèi)存，為了更好的管理內(nèi)存碎片，建立16個鏈表，每個鏈表“穿”著一塊一塊固定大小的內(nèi)存，這16個鏈表（0至15）分別“穿”的內(nèi)存是8、16、24…128倍數(shù)關系。需要內(nèi)存時，從“合適”的鏈表取走(因為這里情況比較多，不能一一說道了)，如果“合適”的鏈表內(nèi)存不夠用了，從內(nèi)存池里拿，如果內(nèi)存池不夠用了，從運行時heap里拿，如果heap也溢出了，就交給第一級配置器，因為它有set_new-handler機制。所以，當堆上的東西用完之后，的趕緊還回來。4、完整代碼、測試代碼、測試結果

(1)、抽取出來的完整代碼#if

1

#include<iostream>

#include<new>

#include<malloc.h>

using

namespace

std;

//#define

__THROW_BAD_ALLOC

throw

bad_alloc

#define

__THROW_BAD_ALLOC

cerr<<"Throw

bad

alloc,

Out

Of

Memory."<<endl;

exit(1)

//定義異常,就是輸出一句話,并且結束程序.

#elif

!defined

(__THROW_BAD_ALLOC)

//如果沒有定義這個異常,下面就定義

#include<iostream.h>

#define

__THROW_BAD_ALLOC

cerr<<"out

of

memory"<<endl;

exit(1);

#endif

template<int

inst>

class

__malloc_alloc_template{

private:

static

void*

oom_malloc(size_t);

//對申請空間失敗的處理函數(shù)

static

void*

oom_realloc(void

*,

size_t);

//對擴展空間失敗處理的函數(shù)

static

void(*

__malloc_alloc_oom_handler)();

//定義一個函數(shù)指針

public:

static

void*

allocate(size_t

n){

//分配空間

void

*result

=

malloc(n);

if(0

==

result)

result

=

oom_malloc(n);

//分配空間失敗，調(diào)用oom_malloc()函數(shù)

return

result;

//將申請的空間的地址返回

}

static

void

deallocate(void

*p,

size_t){

free(p);

//釋放空間

}

static

void*

reallocate(void

*p,

size_t,

size_t

new_sz){

void

*result

=

realloc(p,

new_sz);

//擴展新空間;

if(0

==

result)

//擴展失敗

oom_realloc(p,new_sz);

//調(diào)用擴展空間失敗的處理函數(shù)

return

result;

}

public:

//set_new_handler(Out_Of_Memory);

static

void(*set_malloc_handler(void(*f)()))(){

//這是一個指針函數(shù),函數(shù)名稱:set_malloc_handler,參數(shù):是一個函數(shù)指針,返回值:是一個函數(shù)指針;

void(*old)()

=

__malloc_alloc_oom_handler;

//將原有空間的地址保存在old中;

__malloc_alloc_oom_handler

=

f;

//將自己定義的函數(shù)地址給__malloc_alloc_oom_handler;

return

old;

//每次可以保存其上一次的地址.

}

};

template<int

inst>

void

(*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)()

=

0;

//對定義的靜態(tài)函數(shù)指針初始化為0;

template<int

inst>

void*

__malloc_alloc_template<inst>::oom_malloc(size_t

n){

//處理空間失敗的問題

void

*result;

void(*

my_malloc_handler)();

//定義一個函數(shù)指針;

for(;;){

my_malloc_handler

=

__malloc_alloc_oom_handler;

if(0

==

my_malloc_handler){

//自己沒有定義處理空間失敗的新函數(shù)

__THROW_BAD_ALLOC;

//異常拋出;程序終止;

}

(*my_malloc_handler)();

//調(diào)用自己編寫的處理函數(shù)(一般都是回收空間之類的);

result

=

malloc(n);

//在此申請分配空間

if(result){

//申請成功

return

result;

//將地址返回;

}//那么，這個程序將會一直持續(xù)到空間分配成功才最終返回.

}

}

template<int

inst>

void*

__malloc_alloc_template<inst>::oom_realloc(void

*p,

size_t

n){

void(*my_malloc_handler)();

//函數(shù)指針

void

*result;

for(;;){

my_malloc_handler

=

__malloc_alloc_oom_handler;

//將這個給其賦值

if(0

==

my_malloc_handler){

//外面沒有定義處理的函數(shù)

__THROW_BAD_ALLOC;

//異常拋出,程序結束.

}

(*my_malloc_handler)();

//調(diào)用自己編寫的處理函數(shù)(一般都是回收空間之類的);

result

=

realloc(p,

n);

//再次擴展空間分配;

if(result){

//擴展成功,就返回

return

result;

}

//一直持續(xù)成功，知道擴展空間分配成功才返回;

}

}

typedef

__malloc_alloc_template<0>

malloc_alloc;

//一級空間配置器:malloc_alloc;

/////////////////////////////////////////////////////////////////////////////////////

//二級空間配置器由自由鏈表和內(nèi)存池組成;

enum

{__ALIGN

=

8};

//一塊鏈表8B

enum

{__MAX_BYTES

=

128};

//小于128B調(diào)用二級的

enum

{__NFREELISTS

=

__MAX_BYTES

/

__ALIGN};

//一共分配16個自由鏈表,負責16種次分配能力.

template<bool

threads,

int

inst>

//不考慮多線程狀態(tài);

class

__default_alloc_template{

public:

static

void*

allocate(size_t

n);

//分配空間

static

void

deallocate(void

*p,

size_t

n);

//銷毀空間

static

void*

reallocate(void

*p,

size_t,

size_t

new_sz);

//擴展空間

private:

static

size_t

ROUND_UP(size_t

bytes){

//向上調(diào)整函數(shù);

return

(((bytes)

+

__ALIGN-1)

&

~(__ALIGN-1));

//調(diào)為當前字節(jié)是8的整數(shù)倍.

}

private:

union

obj{

//共用體

union

obj

*

free_list_link;

//自由鏈表的指向

char

client_data[1];

};

private:

static

obj*

volatile

free_list[__NFREELISTS];

//定義了一個指針數(shù)組;

static

size_t

FREELIST_INDEX(size_t

bytes){

//求當前字節(jié)的自由鏈表的下標;

return

((bytes)+__ALIGN-1)

/

__ALIGN-1;

}

private:

static

char

*start_free;

//開始空間的下標

static

char

*end_free;

//結束空間的下標

static

size_t

heap_size;

//堆空間大小

static

void

*refill(size_t

n);

//填充函數(shù)

static

char*

chunk_alloc(size_t

size,

int

&nobjs);

//

};

template<bool

threads,

int

inst>

//以下都是對靜態(tài)變量的初始化,都為0;

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};

template<bool

threads,

int

inst>

void*

__default_alloc_template<threads,

inst>::allocate(size_t

n){

//分配空間的函數(shù)

obj

*

volatile

*my_free_list;

obj

*result;

if(n

>

__MAX_BYTES){

//分配空間的大小大于128B的話，就調(diào)用一級空間配置器

return

malloc_alloc::allocate(n);

}

my_free_list

=

free_list

+

FREELIST_INDEX(n);

//free_list是二維數(shù)組名稱,找往哪個鏈下掛；

result

=

*my_free_list;

//取出其值,因為my_free_list是二階指針;

if(result

==

0){

//沒有內(nèi)存池空間;

void

*r

=

refill(ROUND_UP(n));

//調(diào)用refill()函數(shù)

return

r;

}

*my_free_list

=

result->free_list_link;

//進行掛載連接;

return

result;

}

template<bool

threads,

int

inst>

void*

__default_alloc_template<threads,

inst>::refill(size_t

n){

//沒有可用區(qū)塊時,就調(diào)用refill()函數(shù);

int

nobjs

=

20;//就是要分20塊;

char

*chunk

=

chunk_alloc(n,

nobjs);

//調(diào)用內(nèi)存池函數(shù);

obj

*

volatile

*my_free_list;

obj

*result;

obj

*current_obj,

*next_obj;

int

i;

if(1

==

nobjs){

//當分配到只有一塊空間時,直接返回.

return

chunk;

}

my_free_list

=

free_list

+

FREELIST_INDEX(n);

//找到對應的下標，進行連接的工作;

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>::chunk_alloc(size_t

size,

int

&nobjs){

//內(nèi)存池函數(shù)

char

*result;

//關鍵要明白以下的各種情況;

size_t

total_bytes

=

size

*

nobjs;

//這里的size已經(jīng)是上調(diào)過的字節(jié);求取20*size個字節(jié)的大小

size_t

bytes_left

=

end_free

-

start_free;

//剛開始，遺留字節(jié)為0;

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);

//申請2倍的total_bytes；

if(bytes_left

>

0){

//遺留字節(jié)數(shù)=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;

for(i=size;

i<=__MAX_BYTES;

i

+=

__ALIGN){

my_free_list

=

free_list

+

FREELIST_INDEX(i);

p

=

*my_free_list;