二進制安全pwn基礎bin
對堆操作的是由堆管理器（ptmalloc2）來實現的，而不是操作系統內核。因為程序每次申請或者釋放堆時都需要進行系統調用，系統調用的開銷巨大，當頻繁進行堆操作時，就會嚴重影響程序的性能
概述
我們曾經說過，用戶釋放掉的 chunk 不會馬上歸還給系統，ptmalloc 會統一管理 heap 和 mmap 映射區域中的空閑的 chunk。當用戶再一次請求分配內存時，ptmalloc 分配器會試圖在空閑的 chunk 中挑選一塊合適的給用戶。這樣可以避免頻繁的系統調用，降低內存分配的開銷。
在具體的實現中，ptmalloc 采用分箱式方法對空閑的 chunk 進行管理。首先，它會根據空閑的 chunk 的大小以及使用狀態將 chunk 初步分為 4 類：fast bins，small bins，large bins，unsorted bin。每類中仍然有更細的劃分，相似大小的 chunk 會用雙向鏈表鏈接起來。也就是說，在每類 bin 的內部仍然會有多個互不相關的鏈表來保存不同大小的 chunk。
申請堆塊的本質
堆管理器 ptmalloc2 主要是通過 malloc/free 函數來分配和釋放內存塊。
ptmalloc2 的作用通俗的講就是相當于一個”中間商”，在程序想要申請向系統申請堆空間時，這里的 ptmalloc2 就會申請一塊很大的空間，并根據算法從這些內存中把空間真正的分配給程序。
簡單點說就是下面這個圖中的情況：
free 函數和 bins
bins 這個概念是與內存回收相關的，也就是堆管理器會根據用戶已經申請到的內存空間大小進行釋放，來決定放入哪類 bins 當作去。bins 直接翻譯過來就是”垃圾桶”的意思，所以在系統在決定使用哪個 bins 時可以看作為”垃圾的分類”。
free 函數的使用是和 bins 的分配息息相關的。用一個簡單的例子來理解一下 free 函數的實現原理。
代碼如下：
#include <stdlib.h>
#include <string.h>
int main(){
char *p;
p = malloc(10);
memcpy(p,"Hello",5);
free(p);
return 0;
}
- 程序將 “Hello” 字符串復制到申請到的堆內存空間中。
編譯后用 gdb 調試，在 call memcpy 處下一個斷點，單步后將 “Hello” 復制到堆塊中
繼續使用 x/32gx 0x602010-0x10 命令查看堆塊情況
繼續單步 n，執行 free 函數之后，查看堆塊情況
這里可以看出原本堆塊中存儲的內容已經被清空，然后查看一下 main_arena 的值，發現其中 +0x8 的偏移處，存儲了指向已經 free 了的指針（指向頭部，而不是 user data）
小總結
所以調用 free 函數以后程序做了兩件事：
1.清空此堆塊的 user data
2.將此堆塊的指針存儲到 main_arena 中了（或是 fast bin 中）
fast bin
顧名思義，就是為了快速重新分配回內存而存在的一個結構。
fastbin所包含chunk的大小為16 Bytes, 24 Bytes, 32 Bytes, … , 80 Bytes。當分配一塊較小的內存(mem<=64 Bytes)時，會首先檢查對應大小的fastbin中是否包含未被使用的chunk，如果存在則直接將其從fastbin中移除并返回；否則通過其他方式（剪切top chunk）得到一塊符合大小要求的chunk并返回。引用一張圖：
這里的橫向排列的就是 main_arene（fast bin）的內存地址假如此時 0x0804a000 處的堆塊（實際堆塊中的 size 字段要減去 PREV_INUSE 字段值 1，）已經被 free 了，那么他就會被存儲在表示 40 bytes 的 fast bin 的內存地址里
注意：這里把指針和地址區別開。地址存儲的是指針，64 位的指針占 8 個字節。假設我們現在還是以 64 位下的 malloc(10) 為例子。
根據前面那個 free 函數的例子，查看 main_arena 地址中的指針值我們可以看出來，+0x8 偏移處才是指向 malloc(10) 的堆塊的指針（這個堆塊分配后的 user data 實際大小是 16 字節）
gdb-peda$ x/2gx &main_arena (16 bytes 的鏈表頭)
0x7ffff7dd3760 <main_arena>: 0x0000000000000000 0x0000000000602000所以這個 16 字節的堆塊的指針會被插入屬于他的這個鏈表隊列中，也就是如下的情況。
所以這也就印證了在 main_arena 中分別表示 16 Bytes, 24 Bytes, 32 Bytes, … , 80 Bytes 的內存地址中分別存儲著已經 free 的而且滿足這個大小的 chunk的指針。
fast bin 的特性
1.使用單鏈表來維護釋放的堆塊
也就是和上圖一樣，從main_arena 到 free 第一個塊的地方是采用單鏈表形式進行存儲的，若還有 free 掉的堆塊，則這個堆塊的 fk 指針域就會指針前一個堆塊。
如下圖所示，此時就是一個單鏈表結構
2.采用后進先出的方式維護鏈表（類似于棧的結構）
當程序需要重新 malloc 內存并且需要從fastbin 中挑選堆塊時，會選擇后面新加入的堆塊拿來先進行內存分配
如上圖，如果程序重新請求和上面的堆塊大小一樣時候（malloc），堆管理器就會直接使用 fast bin 里的堆塊。
這里的話也就是直接使用第二次釋放的這個堆塊，然后將這個堆塊從鏈表中移除，接著根據堆塊的 fk 指針找到這個堆塊，此時 main_arena 就指向了這里。也就是恢復到了上面第一個圖中的情況。
small bin
顧名思義，這個是一個 small chunk ，滿足的內存空間比 fast bin 大一點。
如果程序請求的內存范圍不在 fast bin 的范圍內，就會考慮small bin。簡單點說就是大于 80 Bytes 小于某一個值時，就會選擇他。
unsorted bin
當 fast bin、small bin 中的 chunk 都不能滿足用戶請求 chunk 大小時，堆管理器就會考慮使用 unsorted bin 。它會在分配 large chunk 之前對堆中碎片 chunk 進行合并，以便減少堆中的碎片。
unsorted bin 與 fast bin 不同，他使用雙向鏈表對 chunk 進行連接
unsorted 的字面意思就是”不可回收”的意思，可以看作將不可回收的垃圾（不滿足能夠進行內存分配的堆塊）都放到這個”垃圾桶”中。
參考
