malloc_chunk境界マーキング法と空間多重化
きょうかいマークほう
ptmallocが割り当てた空間統合はmalloc_を用いたchunk構造で管理、malloc_chunkの構造は初めて奇抜で、注釈を見て、しばらくの間コードを分析して、このような境界マークの設計を発見して、malloc_chunk仮想アドレスが互いに隣接している場合,非常に効率的である.
malloc_chunk構造:
まず、malloc_chunkはすべて仮想アドレスで接続されており、chunkの隣接するchunkのアドレスを知る必要があります.各malloc_chunkはすべて自分のsizeを含んで、また仮想アドレスの前のmalloc_を含みますchunk、ここでは後のmallocを記録する必要はありません.chunkのsizeは、後のヘッダアドレスが現在のmalloc_であるためchunkのヘッダアドレス+size,prev_sizeは前のchunkが空いているときに利用できます.前のchunkが使用されている場合、このprev_sizeの空間は前のchunkに徴用される.現在chunkが使用されている場合、fd,bk,fd_nextsize,bk_nextsizeは、すべて無効で、それらはすべて空きチェーンテーブルに関するポインタであり、これらのポインタの空間はすべて空き空間とされています.ptmallocのコメントには空きmalloc_が描かれていますchunkと割り当てられたmalloc_chunkの構造.
アイドルchunkの構造:
上の図は空きchunkの構造の概略図で、図から現在のmalloc_がわかりますchunkのポインタはchunkポインタで、アドレスが隣接する前のポインタを得るにはchunk-prev_sizeでいいです.アドレスの隣接するポインタ,chunk+sizeを得た.ここでfd,bkポインタはbinにおける空き双方向チェーンテーブルである.これはprev_を通じてsizeはmalloc_をchunkの合併過程は非常に迅速である.
コードからアイドルchunkのマージプロセスを見るか、malloc_consolidateの関数のクリップ:
ptmallocが割り当てた空間統合はmalloc_を用いたchunk構造で管理、malloc_chunkの構造は初めて奇抜で、注釈を見て、しばらくの間コードを分析して、このような境界マークの設計を発見して、malloc_chunk仮想アドレスが互いに隣接している場合,非常に効率的である.
malloc_chunk構造:
/*
This struct declaration is misleading (but accurate and necessary).
It declares a "view" into memory allowing access to necessary
fields at known offsets from a given base. See explanation below.
*/
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
まず、malloc_chunkはすべて仮想アドレスで接続されており、chunkの隣接するchunkのアドレスを知る必要があります.各malloc_chunkはすべて自分のsizeを含んで、また仮想アドレスの前のmalloc_を含みますchunk、ここでは後のmallocを記録する必要はありません.chunkのsizeは、後のヘッダアドレスが現在のmalloc_であるためchunkのヘッダアドレス+size,prev_sizeは前のchunkが空いているときに利用できます.前のchunkが使用されている場合、このprev_sizeの空間は前のchunkに徴用される.現在chunkが使用されている場合、fd,bk,fd_nextsize,bk_nextsizeは、すべて無効で、それらはすべて空きチェーンテーブルに関するポインタであり、これらのポインタの空間はすべて空き空間とされています.ptmallocのコメントには空きmalloc_が描かれていますchunkと割り当てられたmalloc_chunkの構造.
アイドルchunkの構造:
上の図は空きchunkの構造の概略図で、図から現在のmalloc_がわかりますchunkのポインタはchunkポインタで、アドレスが隣接する前のポインタを得るにはchunk-prev_sizeでいいです.アドレスの隣接するポインタ,chunk+sizeを得た.ここでfd,bkポインタはbinにおける空き双方向チェーンテーブルである.これはprev_を通じてsizeはmalloc_をchunkの合併過程は非常に迅速である.
コードからアイドルchunkのマージプロセスを見るか、malloc_consolidateの関数のクリップ:
// if (!prev_inuse(p)) { prevsize = p->prev_size; size += prevsize; p = chunk_at_offset(p, -((long) prevsize)); unlink(p, bck, fwd); }
//合併後のif (nextchunk != av->top) { nextinuse = inuse_bit_at_offset(nextchunk, nextsize); if (!nextinuse) { size += nextsize; unlink(nextchunk, bck, fwd); } }
コードから分かるように、前のmalloc_をマージします.chunkプロセスでは、前のmalloc_を取得する必要がないことがわかります.chunkのポインタ、合併の過程は大体現在のchunkポインタを前の位置に移動し、同時にsizeを更新し、chunkポインタを対応するbin双方向チェーンテーブルから乾かすことである.マージの過程からprev_を使っただけであることがわかります.sizeは、前のchunkのポインタを使っていません.前のchunkのポインタがあれば、マージプロセスには必ずこのchunkのsizeが必要です.ここではprev_sizeはマージの速度を速めます.prev方向にマージするにはsizeとchunkポインタを更新し、sizeを更新すればnext方向にマージする必要があります.
くうかんふくごう
malloc_chunkにはsizeが必要で、このchunkの大きさをマークしてmallocの要求を満たすかどうかを決定すると、空きmalloc_に対してchunkではfd,bk,fd_nextsize,bk_nextsizeは必須で、binの空き二重チェーンテーブルです.アイドルでないmalloc_の場合chunkにとってfd,bk,fd_nextsize,bk_nextsizeは役に立たないので,この部分の空間は利用可能な空間として用いられる.ではprev_sizeは複雑で、その状態は仮想アドレスが隣接する前のchunkの状態に依存し、前のchunkが使用状態である場合、このchunkのprev_sizeは意味がなく、マージする必要もないので、前のchunkポインタの位置を知る必要はありません.そのため、この変数の空間は前のchunkに徴用されます.
使用状態のchunk
mallocリクエストのsizeは、構造体のデータサイズを加えてmalloc_chunkのsizeには比べものにならない.#define request2size(req) \ (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ? MINSIZE : \ ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
上記のマクロから、実際のリクエストのサイズはreqにsize_を加えたものであることがわかります.t次に位置合わせ、ここprev_sizeとsizeは2*size_ではありませんtか、でもnext chunkから贈られたprevを計算します.sizeのsize_t.
まとめ
上の分析からmalloc_chunkのデザインは巧みだprevsizeフィールドは、アドレスが隣接する空きの前のchunkを見つけることができ、空きのchunkをマージするのに便利であり、現在のchunkの前のchunkが使用されている場合、prev_sizeの空間は、前のchunkを利用可能な空間として貸すことができる.