Heap入門/mallocとfreeの構造,処理,仕組み
[+]Heapの構造について
allocate_chunk{prev_size, size, data}
free_chunk{prev_size, size, fd, bk, free_space}
①allocate_chunk{prev_size, size, data}をfreeすると、dataの先頭4バイトがfd、次の4バイトがbkになり、残ったdataがfree_spaceになる。
②各チャンクにおいて、直上チャンクがallocateチャンクの場合、prev_sizeが直上チャンクにuser使用域として奪われる。(ヒープ領域としては自身のモノのまま)
つまり、①と②を考慮すると、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においてもそれは同様である。
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/