STL空間配置器(一)
20640 ワード
STL （ ）
Author:胡建Time:2016/4/5これはSTL学習の第1部であり、空間アダプタ、いわゆる空間アダプタは、メモリを管理するための器具である.STLにとって、スペースアダプタは正常に動作する基礎であり、効率的に動作するために動力を提供します.STLを使用する場合は、ユーザーと直接付き合うのではなく、すべてのSTLが構築された後、さまざまなメモリ申請を黙々とサポートしています.c++ユーザーにとって、newとdeleteはよく知っていて、この2つの関数はそれぞれメモリの申請と解放を完成することができて、cの中のmallocとfreeと同じように、SGIには標準空間アダプタがあって、同時に1つの特殊な空間アダプタがあって、標準空間アダプタは:std::allocatorで、者の1つのアダプタはnewとdeleteの浅い包装に対してだけで、だから技術的な含有量はあまりないので、SGIではこの標準アダプタを使ったことがありません.もう1つの空間アダプタはstd:allocで、これは二次分配能力を持つ特殊な空間アダプタで、1級と2級のアダプタを持っていて、それらは協調して動作します.Std::allocの主な考え方は、空間サイズのしきい値を定義することです.128 bytes、申請された空間が128 bytesより大きい場合は、第1レベルの空間アダプタを呼び出して割り当てを完了し、128 bytes未満であれば、第2レベルの空間アダプタを長く呼び出して完了します.第1レベルのアダプタでは、mallocとfreeを直接呼び出してメモリの割り当てと解放を完了します(newとdeleteは呼び出されません).最も重要なのは、第1レベルのアダプタはnew-handleメカニズムを持っており、ユーザーはout-of-memoryが発生したときの処理関数を指定することができます.SGIでは、第1レベルのallocが失敗したとき、oom_が呼び出されます.alloc関数でメモリの割り当てを試みますが、oomがnew-handler関数を指定していないことに気づいたら、どうしようもありません!投げ出します_THROW_BAD_ALLOCという異常は、以下が第1段アダプタの主な流れ(allocにとって、他はreallocのように):1、空間分配器の「分線器」
static void * allocate(size_t n)
{
void *result = malloc(n);// ， malloc
if (0 == result) result = oom_malloc(n);// ， ，oom(out of memeory)
return result;// void* ，
}nは私たちが申請したいメモリです.mallocが要求を満たすことができれば、直接返します.そうしないとoom_に渡します.malloc()で処理します.2、new-handlerを持つoom_malloc
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);// ， ， ，
// ， ....
}
}その中の_malloc_alloc_oom_handlerはユーザーが設定したnew-handlerで、次の関数でこのハンドルを設定できます.
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;//old handler of outing of memory
__malloc_alloc_oom_handler = f;//new handler for hander the out of memory
return(old);
}見たところoom_mallocも何もしていませんが、メモリを繰り返し申請していますか?一つのサイクルでoom_handler->malloc….ある時点でメモリに申請に成功するのを待っていれば、交差点に戻ることができます!!
第2レベルのコンフィギュレーションを重点的に見てみましょう.これこそSGIの古典(個人)です.第2レベルのコンフィギュレーションがどのように「使用」されているかを再認識する必要があります.ユーザーが申請したメモリサイズが128 bytes未満の場合、SGIコンフィギュレーションの「スプリッタ」はこの作業を第2レベルのディスペンサに渡して完了します.このとき、2段目のディスペンサが動作し始めます.第2段分配器の原理は比較的に簡単で、メモリプールに大きなメモリ空間を申請して、それから大きさによって16組に分けて、(8,16.....128)、それぞれの大きさは1つのfree_に対応しますListチェーンテーブル、このチェーンテーブルの上のノードは使用可能なメモリ空間で、注意しなければならないのは、コンフィギュレータは8の倍数のメモリしか割り当てられません.もしユーザーが申請したメモリの大きさが8の倍数未満であれば、コンフィギュレータは勝手にユーザーのために8の倍数に引き上げます.だから、境界を超えているのにシステムがあなたの行為を阻止していない場合があります.SGI空間配置器があなたを救ったことを知っているはずです.もちろん、第2レベルのコンフィギュレータの原理はそんなに簡単ではありません.第2レベルのコンフィギュレータがメモリをどのように管理するかについては、ユーザーにメモリを割り当て、メモリを回収し始めます.ユーザがメモリを申請すると、第2レベルのコンフィギュレータはまずこの空間サイズを8の倍数に引き上げ、対応するfree_を見つけます.Listチェーンテーブルは、チェーンテーブルにまだ空きノードがある場合は、次のノードを直接ユーザーに割り当て、対応するチェーンテーブルが空の場合は、このチェーンテーブルのノードを再申請する必要があります.デフォルトは20個です.メモリプールがこのサイズのノードを20個支払うのに十分ではありませんが、ノードサイズのメモリを1つ以上支払うのに十分な場合は、完了可能なノードの数を返します.このサイズのノードが1つも満たされない場合は、メモリプールを再申請する必要があります.要求されたメモリプールのサイズは:2*total_bytes+ROUND_UP(heap_size>>4),total_bytesは申請したメモリサイズで、SGIは2倍以上のメモリを申請します.メモリフラグメントの問題を回避するには、元のメモリプールに残っていたメモリをfree_に割り当てる必要があります.Listチェーンテーブル.メモリプールがメモリの申請に失敗した場合、つまりheap_sizeが要求を支払うのに十分でない場合、SGIのサブコンフィギュレータは最後の絶技を使用します.->free_を表示します.List配列は、使用されていないメモリが十分に大きいかどうかを確認します.これらの方法が要求を満たすことができない場合は、第1レベルのコンフィギュレーションしか呼び出せません.第1レベルのコンフィギュレーションはmallocでメモリを割り当てますが、new-handlerメカニズム(out-of-memory)があり、成功しなければbad_を投げ出すしかありません.alloc異常で割当てが終了します.前述したコンフィギュレーションの「スプリッタ」は、実は二次コンフィギュレーションの入り口であり、二次コンフィギュレーションが128 bytesよりも多くのメモリを割り当てる必要があることを発見した場合、第1のコンフィギュレーションに任せて完了します.そうしないと、自分で完了します.次に、このセカンダリ・コンフィギュレータがどのように実装されているかを見てみましょう.
enum {__ALIGN = 8};// ， 30bytes ， 32bytes
enum {__MAX_BYTES = 128};// ，
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};//free-list ， 8 128， 16 私は何を言う必要がないと信じて、上のコードは最も小川の最大の空間の大きさを定義して、必要なチェーンテーブルの個数で、どうしてこれを定義しますか?すなわち、SGI STLのコンフィギュレーションが頻繁に二次コンフィギュレーションを呼び出すと、16-128、32-256などの二次コンフィギュレーションに入る条件を変更することができます.セカンダリ・コンフィギュレータはメモリの破片の問題を解決しますが、メモリ管理に余分な負担をもたらし、free_を調整する必要がある可能性があります.Listは、逆に第1段コンフィギュレーションを呼び出すこともあるので、コンフィギュレーションに入る区間が合理的ではないと思ったら、自分で調整することができます!(でも死ぬな!).
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}上の関数はbytesに最も近い8で割り切れる整数を返し、取ります.
freeを見てみましょうListのノードのデータ構造:
union obj {
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};このようにunionを巧みに運用してノードを管理し、まだ割り当てられていない場合はfree_list_linkが有効で、ユーザーに割り当てられている場合はclient_data[1]は有効です.余計な無駄遣いはしない!次の定義はfreeですListチェーンテーブル配列は、各配列要素がチェーンテーブルに対応します.
static obj * __VOLATILE free_list[];
次の関数は、要求されたメモリに対応する空きチェーンテーブルを見つけます.SGIは、ユーザのメモリ申請サイズを8の倍数に引き上げることに注意してください.
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}セカンダリ・コンフィギュレーションではメモリ・プールが使用されるので、メモリ・プールの区間を次に示します.
static char *start_free; //
static char *end_free;// 次は感動的なメモリ割り当て関数です.この関数はまず区間サイズを判断し、128 bytesより大きい場合は、第1レベルのコンフィギュレーションを呼び出し、128 bytesより小さい場合は対応するfree_を探します.Listチェーンテーブルは、使用可能なものがあれば直接取り、ない場合は関数refillを呼び出してノード(20個)を再割り当てします.
/* n must be > 0 */
static void * allocate(size_t n)
{
obj * __VOLATILE * my_free_list;
obj * __RESTRICT result;
// 128bytes，
if (n > (size_t) __MAX_BYTES) {
return(malloc_alloc::allocate(n));
}
// free_list
my_free_list = free_list + FREELIST_INDEX(n);
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
# ifndef _NOTHREADS
/*REFERENCED*/
lock lock_instance;
# endif
result = *my_free_list;
// ，
if (result == 0) {
//refill （20 ）
void *r = refill(ROUND_UP(n));
return r;
}
// free_list ，
*my_free_list = result -> free_list_link;
return (result);
};申請があればメモリを回収する必要があります.次は、区間サイズを判断し、128 bytesより大きい場合は第1レベルの構成器を直接呼び出してメモリを回収し、128 bytesより小さい場合は対応するfree_に回収します.Listチェーンテーブルでは、比較的簡単です.
/* p may not be 0 */
static void deallocate(void *p, size_t n)
{
obj *q = (obj *)p;
obj * __VOLATILE * my_free_list;
// 128bytes，
if (n > (size_t) __MAX_BYTES) {
malloc_alloc::deallocate(p, n);
return;
}
//
my_free_list = free_list + FREELIST_INDEX(n);
// acquire lock
# ifndef _NOTHREADS
/*REFERENCED*/
lock lock_instance;
# endif /* _NOTHREADS */
//
q -> free_list_link = *my_free_list;
*my_free_list = q;
// lock is released here
}次にrefill関数を見てみましょう.この関数はチェーンテーブルにノードを再割り当てする作業を完了します.新しいスペースはメモリプールから取り込まれます(メモリプールはchunk_allocで管理されます).デフォルトでは20個の新しいノードしか取りませんが、20個未満のノードがある可能性があります.
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
int nobjs = 20; // 20
// 20
char * chunk = chunk_alloc(n, nobjs);
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
// ， 1 ， ，
if (1 == nobjs) return(chunk);
// free_list ，
//my_free_list
my_free_list = free_list + FREELIST_INDEX(n);
/* Build free list in chunk */
result = (obj *)chunk;// ！
// free_list
*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);
}次は最も重要で最も難しいメモリプールです.もちろん、次の関数はメモリプールからfree_にスペースを取り出すだけです.リストは使っただけです.しかし、全体の過程は曲がりくねっていて、古典的で、よく味わう必要があります.素晴らしいデザインです.
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;
// ， ok
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);
}
// ， ， heap
// 2
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;
}
// ， malloc！！！
start_free = (char *)malloc(bytes_to_get);
// malloc
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.
// ， free_list
// ！！！
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;
// free_list ， ！
// ？ ， ！！！
return(chunk_alloc(size, nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
// ， ， ， out-of-memory
// malloc ， new-handler
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));
}
}上記の内容を説明した後、二次構成器がどのように動作しているのかよく知っているはずですが、実は、第1段構成器は第2段構成器に合わせるために存在し、二次構成器の設計原理に重点を置いていることがわかります.最後に、コンフィギュレーションの流れを説明します.
Alloc_bytes is the ask memory.
If(Alloc_bytes>128)
First_alloc work start...
Else
Second_alloc work start....
In Second_alloc:
If(free_list!=NULL)
Get an node of this free list and return it
Else
Refill function start to work...
Chunk_alloc function start to work..
In chunk_alloc:
If memory pool’s size bigger wanted,just assign
Else if the memory pool’s size can reach more than 1 nodes
Then alloc...
Else
First allocator start to work...
...call itself ....————————–2016/4/5胡健———————