Heap入門/mallocとfreeの構造,処理,仕組み

[+]Heapの構造について

allocate_chunk{prev_size, size, data}

free_chunk{prev_size, size, fd, bk, free_space}

f:id:ta1se1_sec:20170703183333p:plain

①allocate_chunk{prev_size, size, data}をfreeすると、dataの先頭4バイトがfd、次の4バイトがbkになり、残ったdataがfree_spaceになる。

②各チャンクにおいて、直上チャンクがallocateチャンクの場合、prev_sizeが直上チャンクにuser使用域として奪われる。(ヒープ領域としては自身のモノのまま)

f:id:ta1se1_sec:20170703183445p:plain

つまり、①と②を考慮すると、freeするのに必要な最小構成は

allocate_chunk{prev_size, size, data(fd,bk)}

の4*4バイトとなる。

dataが最小8バイトで、freeするとそれがfd+bkに分解される。

 

[+]freeについて

allocateチャンクがfreeされると、binsのインデックス0とインデックス1に存在するunsorted binにまずは繋がれる。

そして、そのチャンクのsizeごとに振り分けられたbinsに繋がっていく。

具体的な種類としては「small bins」「fast bins」「large bins」などがある。

small binsは8バイトごとにサイズ分けされているため、チャンクをsmall binsに繋ぐ際には、そのチャンクのsizeを8で割った値をインデックスにすれば対応しているbinsのインデックスを特定することができる。

先程述べたように、ひとつのチャンクの最小サイズは16なので、最小サイズのチャンクを格納するsmall binsのインデックスは16÷8で2となり、small binsのインデックス0と1はsmall binsとして使用されない。

ここは時系列順で繋がるunsorted binとして使用されている。

large binsにおいてもそれは同様である。

f:id:ta1se1_sec:20170703183509p:plain

freeチャンクはそれぞれfdとbkという二つの要素を持っており、fdには先頭チャンクのアドレスが、bkには最後尾チャンクのアドレスが格納されている。

先頭チャンクのbkと最後尾チャンクのfdは自身のサイズの管理を担当しているインデックス-1をインデックスとするbinsのアドレスが格納されている。

fast binsにもfd/bkメンバは存在しているのだが、 fast binsはbkメンバを用いない、単方向リストとなっている。

 

[+]Unlinkについて

・XチャンクとPチャンクが隣り合っている場合

・X->sizeのPREV_INUSEが1か(Xの直上チャンクがallocateチャンクか)確認

・(P+P->size)->sizeのPREV_INUSEが0か(Xの直下チャンクがfreeチャンクか)確認

・P->sizeのPREV_INUSEが1か(X自身がallocateチャンクか)確認

・P->fd->bk = P->bk(つまりP->fd+8 = P->bk)

・P->bk->fd = P->fd(つまりP->bk+4 = p->fd)

 

参考/画像提供 : http://www.valinux.co.jp/technologylibrary/document/linux/malloc0001/