# malloc glibc - bin、chunck

###### tags: `EOS`

- Reference
1. [翻譯筆記上](https://zhuanlan.zhihu.com/p/24753861)
2. [翻譯筆記下](https://zhuanlan.zhihu.com/p/24790164)
4. [別人的統整!](https://hackmd.io/@ljP_AG30SzmQE5qO-cjcpQ/HkICAjeJg)
5. [原文](https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/comment-page-1/)

## syscall

https://sploitfun.wordpress.com/2015/02/11/syscalls-used-by-malloc/

mmap、brk 是 malloc 下的 library，會再叫底下的 syscall
\
mmap、brk 存放的虛擬記憶體區段

## arena

**每個 thread 放記憶體和相關資訊的空間**

main thread 的空間就是 main arena ，其他都是 thread arena


- malloc_state(arena header): 只有一個，包含 top chunk, bins, last remainder 等信息
(在 malloc 每一次被調用時會查看 malloc_state 是否爲空)

- malloc_chunk: 就是 chunk header, malloc 在管理 heap 時會把 heap 切割成非常多大小不同的 chunk, 每一個 chunk 都有自己的 chunk header 記錄它的狀態等訊息

- heap_info: 因爲電腦核數的限制, 當 thread 超過一定數量時, 一個 arena 就會包含很多個 thread 在使用, 而每一個 thread 都有一個 heap, 所以通過 heap_info(heap header) 去管理,當 arena 中的 heap 不夠用, 系統會通過 mmap 分配更多的 heap 給 arena

## chunk

heap 內含有各種大小的 chunk, malloc 會用需要大小的 chunk。


- NON_MAIN_**A**RENA – This bit is set when this chunk belongs to a thread arena.
- IS_**M**MAPPED – This bit is set when chunk is mmap’d.
- **P**REV_INUSE – This bit is set when previous chunk is allocated.

有四種類型：
1. allocated 已存放
2. free
3. top
4. last remainder

- free chunk


4個指標,指向前後空閒的chunk和其大小。實際大小會少16bytes(指標4bytes* 4)

- top chunk
malloc 在分配記憶體時會從比較小的 chunk 開始找,直到找到適合的. 而 top chunk 就是"最後的防線",如果 top chunk 仍然不符合用戶申請記憶體的需求, malloc 就會調用 sbrk 或 mapp 分配記憶體
- last remainder
是存放在 unsorted bin 中的亂序排放的chunk, malloc 在尋找合適的 chunk 時若不能從 last remainder 中找到就必須到 large bin 裡找.

## bin

管理不同大小的 chunk，類似 bitmap 的功能

有四種類型：
1. fast bin
2. unsorted bin(free chunk)
3. small bin
4. large bin

*找 chunk 的順序：fast bin 開始 ->(沒找到) unsorted bin ->(沒找到) 最後是 small bin 和 large bin*

兩個數列：
1. fastbinsY：記錄所有的 fast bins
2. bins
* bin 1 為 unsorted bin;
* bin 2 到63為 small bin;
* bin 64到126為 large bin。

### fast bin

* fast chunk 的大小爲16、24、32、..、72、80bytes，最大的 fast chunk size 被設置為80字節(chunk unused size 為64字節)
* fast bin 的結構爲單向 link list, 結構中只使用 fd pointer 因爲 fast bin 使用後入先出的演算法
* 不會對 free chunk 進行合並,類似 cache 的使用
* 當 malloc 申請一個 size 的記憶體,實際大小爲該記憶體+16bytes (prev_size, size, fd, bk 這類輔助成員)
* 在初始化的時候 fast bin 是空的,所以即使請求在 fast chunk 大小內的記憶體也會直接跑到 small bin 去處理

使用和刪除
- 當第一次調用 malloc (fast bin 大小),系統執行_int_malloc 發現 fast bin 爲0, small bin 也是0, 這個時候就調用 malloc_consolidate 對 malloc_state(arena header) 初始化:判斷 malloc_state 是否真的爲空
- malloc_state 的初始化由 malloc_init_state(av) 完成,它先對 fast bin 之外所有的 bin 初始化,再對 fast bin 初始化 (因爲兩個的 struct 不同, fast bin 是 single link list , 其他的是 double)
- 再次執行就可以使用 fast bin 了
- 得到第一個來自 fast bin 的 chunk 後,將 chunk 從 fast bin 中 delete, 並將地址返回給用戶
- free 就是把 chunk size 傳入以獲得 chunk 的大小,在把它添加所對應的 bin 中

### Unsorted bin (free chunk)

* 釋放不是現有大小的記憶體,就添加到 unsorted bin
* 這麼做是因爲把 unsorted bin 當成第二層的 cache 來使用, 加快 malloc 的速度
* 以 linked list 的方式串在一起, unsorted bin 中 chunk 的排列方式的是先來先排的。只有等到 unsorted bin 把 fast bin 中的 chunk 和它合並了之後還是找不到適合大小的 chunk 才會被排入 large bin 中

### small bin

* 大小爲8、16、24、...、512bytes
* 先入先出(add 在前, delete 在後)
* 當 malloc 時, fast bin 和 small bin 都還沒有完成初始化, 就會交給 unsorted bin 處理, 找不到合適的就 loop 所有的 bin, 還是不行就交給 top chunk 處理, 最後還是不合就使用 heap 對 top chunk 進行擴充
* 再次調用 small bin 時,如果不爲空則從 small bin 取得 small chunk
* free: 釋放 small chunk 時會先判斷相鄰的 chunk 是否爲空, 是就合併並丟到 unsorted chunk

### large bin

* 512bytes以上, 有63個, 大小可以不一樣
* large chunk 可以添加/刪除在 large bin 的任何位置
* 前32個間隔64,之後16個間隔512,之後8個間隔4096,之後4個32768,之後2個262144,最後一個放全部剩下的
* 同一個 large bin 中的所有 chunk 的大小不一定相同,所以爲了加快搜索, chunk 由大至小排列(大在前, 小在後)
* malloc 操作: 初始化之前與 small 相似
* 在收到請求之後, 若爲 large bin 範圍, 尋找對應的 bin 並查看第一個 chunk (最大) 的 size 夠不夠, 如果大於就往下找, 小於就向後移動一個 bin. 如果找到最小的 chunk 還是比用戶請求的大, 則分割出剛剛好大小的 chunk 出來給用戶, 剩下的丟到 unsorted bin.
* 因爲 large bin 的個數很多,一直找下去會引發很多的page fault, 所以 glibc malloc 設計了 binmap (能夠知道 bin 是否爲空的 bin-by-bin algorithm)
* 當 large bin 都找完了還是找不到足夠的 chunk 就轉由 top chunk 處理