mplus-outline-fonts 4 / glibc_2.9 malloc.c
malloc.c のコメントを読む。
/* malloc_chunk の詳細 (以下は、Colin Plumb により若干修正された説明をふくむ ) メモリの chunk は Knuth または Standish などで説明されている `boundary tag' 方式を使って保持されている。 (これらの技術の統計につ いては Paul Wilson による論文 ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps を参照すること) あ いている chunk のサイズはそれぞれの chunk の先頭と末端の両方に記録 される。 これにより、とても速く分割された chunk を大きな chunk に統 合することができるようになる。 サイズのフィールドは chunk が使用中 かいなかを判別するビットも保持する。 使用中(allocated)の chunk はこのようになる: chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 使用されていれば、前の chunk のサイズ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | バイト単位の chunk のサイズ |M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ここからユーザのデータ... . . . . (malloc_usable_size() bytes) . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | chunk のサイズ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ "chunk" は malloc のコードの大部分のために使われる、chunk の先頭の アドレスであり、 "mem" はユーザに返されるポインタである。 "nextchunk" は次の隣接した chunk の開始点である。 chunk は必ずちょうど word 境界から始まる。 なので、 mem の部分(ユー ザに返される部分)もまたちょうど word 境界から始まり、したがって少な くとも 2 word が並べられる (aligned)。 開いている chunk は環状双方向リンクリスト(circular doubly-linked lists) に保持され、このようになっている。 chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 前の chunk のサイズ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | バイト単位の chunk のサイズ |P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | リストの次の chunk へのポインタ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | リストの前の chunk へのポインタ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 未使用領域 (長さは 0 bytes かもしれない) . . . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | バイト単位の chunk のサイズ | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ P (PREV_INUSE) bit は chunk サイズ(常に2 word の倍数)の使われない下 位の bit に保持される。 この bit は*前の* chunk が使用中であるかど うかを判別する。 この bit が *クリア* されていれば、この chunk のサ イズの前の word は前の chunk のサイズを保持していて、 前の chunk の front を見つけるに使うことができる。The very first chunk allocated(訳駐: 先に chunk を allocate しておくことで malloc のコス トを下げること?) は必ずこの bit を set して、存在しない(または、所 有されていない)メモリへのアクセスをふせいでいる。 prev_inuse が set されていたならば、 前の chunk のサイズを知ることは*できない*し、 そうしようとすればメモリアドレス fault をひきおこしかねない。 この chunk の`foot' が実は*次の* chunk の prev_size となっているこ とに注意。これで alignments などがやりやすくなるが、このコードを拡 張したり改造したりする人を混乱させる原因にもなっている。 これらには2つ例外がある。 1. 特別な chunk `top' は次の隣接した chunk が存在しないので、末尾の サイズフィールドを使用しない。 初期化後は、 `top' は常に存在しな くてはならない。 `top' が MINSIZE byte よりも短くなれば、再確保 される。 2. mmap を使って確保された chunk はサイズフィールドの下から二番目 の bit M (IS_MMAPPED) が set される。 これらの chunk は一つずつ確 保されるので、末尾のサイズフィールドを必ず必要とする。 */