malloc/free的實現
Chunk
C標准庫在管理分配出去的heap時的基本單位是chunk,chunk只是一個邏輯概念，它的數據結構如下：
struct malloc_chunk {
size_t prev_size;
size_t size;
struct malloc_chunk* fd;
struct malloc_chunk* bk;
struct malloc_chunk* fd_nextsize;
struct malloc_chunk* bk_nextsize;
};
如果一個chunk是free的狀態，那麼它的fd和bk就構成一個雙鏈表，記錄著那些已經被用戶free了內存，這樣以後就可以從這裡直接分配或者合並成為大的空閒塊以後再分配。如果一個chunk已經被alloc了，那麼此時從size之後就是用戶的數據，也就是說fd、bk等沒有意義，這個從注釋中不難看出。
當一個chunk被分配出去時，size記錄了這個chunk中實際分配給用戶程序的內存大小，也就是我們調用malloc時的那個參數值，而prev_size記錄的是與當前chunk相鄰的上一個chunk的大小。這樣設計的原因是可以快速地定位/合並相鄰的chunk.例如，如果當前chunk地址為char *p,那麼上/下一個chunk的地址分別就是p-p->prev_size和p+p->size.簡單分析下下面這兩個宏就一目了然了：
（1）從chunk得到用戶指針（這裡SIZE_SZ即sizeof（size_t））
#define chunk2mem（p） （（void_t*）（（char*）（p） + 2*SIZE_SZ））
（2）從用戶指針得到chunk地址
#define mem2chunk（mem） （（mchunkptr）（（char*）（mem） - 2*SIZE_SZ））
在分配內存時，chunk的對其單位是8Byte,這樣size的低3位就都是0,那麼就可以作為其他用途。在glibc中有兩個定義：
#define PREV_INUSE 0x1
#define IS_MMAPPED 0x2
這裡PREV_INUSE記錄了上一個chunk是否被使用（如果被分配則為1），而IS_MMAPPED標識當前chunk是否是通過mmap分配得到。下面這些宏可以加深我們對chunk的理解：
//獲取當前chunk（p）的下一個chunk
#define next_chunk（p） （（mchunkptr）（ （（char*）（p）） + （（p）->size & ~PREV_INUSE） ））
//獲取當前chunk（p）的上一個chunk
#define prev_chunk（p） （（mchunkptr）（ （（char*）（p）） - （（p）->prev_size） ））
//判斷當前chunk（p）是否被使用，注意：p的inuse位信息保存在下一個相鄰chunk的size中
#define inuse（p） （（（（mchunkptr）（（（char*）（p））+（（p）->size & ~PREV_INUSE）））->size） & PREV_INUSE）
//將當前chunk（p）設置為被使用，也即設置下一個相鄰chunk中size的最低位為1
#define set_inuse（p） （（mchunkptr）（（（char*）（p）） + （（p）->size & ~PREV_INUSE）））->size |= PREV_INUSE
malloc數據結構
這個數據結構記錄了系統當前分配內存的狀態，默認情況下，當分配內存小於64B時通過fastbin分配，它是一個caching allocator,也就是說一種memory pool.當分配內存大於512B時，系統按照best-fit算法分配，也就是可以滿足需求的最小size的chunk.介於二者之間的情況比較復雜。
struct malloc_state {
mutex_t mutex;
int flags;
mchunkptr fastbins[NFASTBINS];
mchunkptr top;
mchunkptr last_remainder;
mchunkptr bins[NBINS * 2 - 2];
unsigned int binmap[BINMAPSIZE];
struct malloc_state *next;
INTERNAL_SIZE_T system_mem;
INTERNAL_SIZE_T max_system_mem;
};
malloc實現（void *malloc（size_t size））
該調用在內部實現為_int_malloc（mstate av, size_t bytes）。主要步驟如下：
1、確定內部分配內存大小，它是用宏request2size計算得到。：
#define request2size（req） （（（req） + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE） ? MINSIZE : （（req） + SIZE_SZ + MALLOC_ALIGN_MASK） & ~MALLOC_ALIGN_MASK）
malloc中分配內存的最小值為MINSIZE,它的定義如下：
#define MINSIZE （unsigned long）（（（MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK） & ~MALLOC_ALIGN_MASK））
#define MIN_CHUNK_SIZE （offsetof（struct malloc_chunk, fd_nextsize））
#define MALLOC_ALIGN_MASK （MALLOC_ALIGNMENT - 1）
#define MALLOC_ALIGNMENT （2 * SIZE_SZ）
#define SIZE_SZ （sizeof（INTERNAL_SIZE_T））
#define INTERNAL_SIZE_T size_t
綜合下來，就是說在我們平常的32位機器上malloc最小分配內存為16B,為什麼會這樣呢？（下面是我的理解）因為每塊分配給用戶的內存都是使用chunk來表示的，當chunk分配出去時，prev_size和size表示相鄰上一個chunk和當前chunk的大小，而從fd開始是用戶內存。而加入chunk沒有分配出去，例如被free,那麼此時它會通過fd和bk鏈接成一個雙鏈表，於是，我們至少要表征chunk的前四個數據成員的語義，這就至少需要16B.BTW,從這裡我們不難看到加入零散地分配小內存，其結果必然是大大降低有效內存使用量。
2、如果分配內存很小（<64B），那麼首先嘗試從fastbin中分配。
if （（unsigned long）（nb） <= （unsigned long）（get_max_fast （））） {
long int idx = fastbin_index（nb）；
fb = &（av->fastbins[idx]）；
if （ （victim = *fb） != 0） {
if （__builtin_expect （fastbin_index （chunksize （victim）） != idx, 0））
malloc_printerr （check_action, "malloc（）： memory corruption （fast）",
chunk2mem （victim））；
*fb = victim->fd;
check_remalloced_chunk（av, victim, nb）；
void *p = chunk2mem（victim）；
if （__builtin_expect （perturb_byte, 0））
alloc_perturb （p, bytes）；
return p;
}
}
fastbin_index（nb）：
這是一個宏，定義為#define fastbin_index（sz） （（（（unsigned int）（sz）） 》 3） - 2）。觀察malloc_state數據結構，它有一個fastbin的指針數組，每個數組成員分配是一個單鏈表的表頭，可見fastbin[i]專門用於分配大小為16+8i的內存塊。
*fb = victim->fd:
當執行到這一行時，fastbin[idx]肯定不為空，也就是說當前內存分配可以直接從fastbin中滿足，那麼下面自然是從單鏈表中取下victim這個chunk,而這行賦值語句正是完成這個任務。這裡相當於fastbin[idx]這個指針指向了victim這個chunk的後繼（victim->fd），也就是說將victim從鏈表中移除。
void *p = chunk2mem（victim）
