前言：讓我們繼續(xù)學習新的概念——bin谒兄，學習資料來自莊明強老師的《Glibc 內存管理》衣赶，博客的大部分內容來自這本書伍茄。

0X00 bin 的介紹

簡單來說：bin 就是空閑 chunk 的容器

用戶 free 掉的內存并不是都會馬上歸還給系統(tǒng)淹朋，ptmalloc 會統(tǒng)一管理 heap 和 mmap 映射區(qū)中空閑的 chunk偏塞，當用戶進行下一次分配請求時唱蒸，ptmalloc 會在空閑的 chunk 中選擇一個合適的分配給他，這樣就避免了頻繁地系統(tǒng)調用

ptmalloc 把大小相似的 chunk灸叼，用雙向鏈表連接起來神汹，這樣就形成了一個 bin。ptmalloc 一共維護了 128 個這樣的 bin古今，并使用數(shù)組來存儲這些 bin 如下：

0X01 ptmalloc bin 分類

再回到這張圖慎冤，數(shù)組中的第一個 bin 是 unsorted bin，數(shù)組中從第 2 個到第 64 個 bin 是 small bin沧卢，它的 chunk size 依次遞增 8bytes蚁堤，每個 small bin 中的 chunk 大小相同。small bin 是一個雙向鏈表但狭。雙向鏈表不是循環(huán)鏈表披诗，它是有順序的。在相同大小 chunk 的 bin 中 的排序是按照「最近使用」的順序立磁，也就是說呈队，排在后面的最容易被選中，剛被釋放的放在前面唱歧。

small bin 后面是 large bin

largin bin 中 chunk 的大小不是固定的宪摧，而是有一個范圍。其中的順序是按大小排序的颅崩，越大的放在越下面几于，如果大小相同，按照「最近使用」的順序

當空閑的 chunk 被連接到 bin 的時候沿后，ptmalloc 會把表示該 chunk 是否正在使用的標志 p 設置為 0沿彭。（注意！這個標志實際處在下一個 chunk 中）尖滚。同時喉刘，ptmalloc 還會檢查它前后（物理前后）的 chunk 是否為空，如果為空漆弄，ptmalloc 會把這些 chunk 合并成一個大的 chunk睦裳，然后把合并后的 chunk 放入 unsorted bin 中。但是對于較小的 chunk撼唾，ptmalloc 會把它放入 fast bins 中廉邑。

• Fast Bins

用戶很有可能請求小的內存，而且釋放之后也很可能再次請求小內存。所以合并釋放小內存鬓催，并不明智肺素。在 fast bins 中恨锚，不大于 max_fast （默認值為 64B）的 chunk 被釋放后宇驾，首先會被放到 fast bins 中，fast bins 中的 chunk 并不改變它的使用標志 P猴伶。這樣也就無法將它們合并课舍，當需要給用戶分配的 chunk 小于或等于 max_fast 時，ptmalloc 首先會在 fast bins 中查找相應的空閑塊他挎，如果找不到筝尾，才會去 bins（那個數(shù)組）中查找數(shù)據(jù)塊。

在某個特定的時刻办桨，ptmalloc 會遍歷整個 fast bins 將相鄰的空閑 chunk 進行合并筹淫，并將合并后的 chunk 加入 unsorted bin 中，再加入到其他的 bin 中呢撞。

• unsorted bin

如果被用戶釋放的 chunk 或在 fast bins 中合并的 chunk 大于 max_fast损姜，則 ptmalloc 會把這些 chunk 放入 unsorted bin 中。在查找合適的 chunk 的時候殊霞，首先在 unsorted bin 中查找合適的空閑 chunk摧阅，然后才查找 bins。

如果 unsorted bin 中沒有合適的 chunk绷蹲，則會把 unsorted bin 中的 chunk 加入到 bins 的其他 bin 中棒卷，再進行查找

0X02 特殊的 Chunk

并不是所有的 chunk 都按照上面的方式來組織，實際上祝钢，有三種例外的情況：

Top chunk比规，mmaped chunk 和 last remainder

Top chunk

top chunk 對于主分配區(qū)和非主分配區(qū)是不一樣的

1）對于非主分配區(qū)來說

ptmalloc 會預先從 mmap 區(qū)域劃分一個出一個 sub_heap，用來相應用戶的申請內存的請求拦英。由于內存是從低向高分配的苞俘，在空閑內存的最高處，必然存在著空閑的 chunk龄章，這個就是 top chunk吃谣。在 fast bin 和 bins 都不能滿足用戶的申請請求時，ptmalloc 就會嘗試在 top chunk 中分出一塊內存給用戶做裙。

如果當前的 top chunk 也不夠大岗憋，分配程序會重新分配一個 sub ，并把當前的 top chunk 遷移到新的 sub heap 上锚贱。新的 sub heap 與舊的 sub heap 用單鏈表連接在一起仔戈，然后在新的 sub heap 上分配內存。top chunk 在分配的時候總是在 fast bin 和 bins 之后才被考慮，所以不論 top chunk 有多大监徘，他都不會被放進 fast bin 或者 bin 中

top chunk 會隨著內存的分配變換大小晋修，如果有被釋放的 chunk 與 top chunk 相鄰，增大 top chunk 的大小凰盔。如果回收的內存大于某一個閾值墓卦，并且 Top chunk 也超過了某個收縮閾值，ptmalloc 會收縮 sub heap户敬。

如果 top chunk 包含了整個 sub heap落剪，那么 ptmalloc 會調用 mumap 把整個 sub heap 回收

2）對于主分配區(qū)來說

由于「主分配區(qū)」是唯一能訪進程 heap 區(qū)域的分配區(qū)。他可以通過 brk() sbrk() 增大收縮 heap 的大小尿庐。ptmalloc 在開始的時候忠怖，會預先分配一塊較大的內存，這就是 heap

mmaped chunk

當申請一塊較大的 chunk抄瑟。并且 fast bin 和 bins 都不能滿足分配凡泣，top chunk 也不能滿足的時候，ptmalloc 會使用 mmap 直接分配頁（4 KB）皮假，這樣的 chunk 在被 free 的時候時直接解除映射鞋拟，直接還給操作系統(tǒng)。再次訪問這塊內存钞翔，會報 segment fault 的錯誤严卖。這樣的 chunk 也不會包含在任何 bin 中。

Last remainder

當需要一個小的 chunk 的時候布轿，small chunk 中沒有哮笆，如果 Last remainder chunk 的大小大于所分配的 chunk，那么就會從 Last remainder chunk 中分出去一個 chunk汰扭，剩下的部分還會作為 Last remainder稠肘。和上述的 chunk 一樣， Last remainder 也不屬于任何一個 bin萝毛。